Μαθήματα: Μέθοδος Simplex σε μορφή παρουσίασης. Τροποποιημένη μέθοδος Simplex για την επίλυση προβλημάτων προγραμματισμού στόχων
1.5.1. Ένα υπολογιστικό σχήμα που βασίζεται στον μετασχηματισμό των αντίστροφων πινάκων.Αναλύοντας υπολογιστική διαδικασίαμέθοδος Simplex από την άποψη της αξιολόγησης της έντασης εργασίας, είναι εύκολο να διαπιστωθεί ότι το πιο κρίσιμο από αυτή την άποψη είναι το στάδιο του εκ νέου υπολογισμού των τιμών ΕΝΑΚαι σικατά τη μετάβαση από το ένα βασικό σχέδιο στο άλλο (ρήτρα 3 του αλγορίθμου). Ωστόσο, στην περίπτωση που ο αριθμός των περιορισμών του προβλήματος Μσαφώς λιγότερες μεταβλητές n, μπορείτε να επιτύχετε σημαντική «εξοικονόμηση» εκτελώντας την επόμενη επανάληψη qΟ μετασχηματισμός Jordan-Gauss όχι πάνω από μήτρα ΕΝΑ(β ( q)), και πάνω από τον πίνακα Δ -1 (β ( q)). Αυτό λαμβάνει επίσης υπόψη το γεγονός ότι, εάν είναι απαραίτητο, χρησιμοποιώντας τον τύπο (1.26), μπορείτε πάντα να λάβετε ΕΝΑ(β ( q)) κατά Δ -1 (β ( q)). Επιπλέον, για να εκτελέσουμε τις ενέργειες της διαδικασίας simplex που περιγράφηκε παραπάνω, δεν χρειαζόμασταν πραγματικά έναν πίνακα ΕΝΑ(β ( q)) εξ ολοκλήρου. Στην πραγματικότητα, μόνο η γραμμή βαθμολογίας χρησιμοποιήθηκε σε αυτό ένα 0 (β ( q)) και κορυφαία στήλη α λ(β ( q)). Αυτές οι εκτιμήσεις αποτελούν τη βάση του υπολογιστικού σχήματος της μεθόδου simplex, που βασίζεται στον μετασχηματισμό των αντίστροφων πινάκων, ο οποίος ονομάζεται επίσης τροποποιημένη μέθοδος Simplex. Πρώτα αυτόν τον αλγόριθμοπροτάθηκε το 1951 στα έργα του L. V. Kantorovich.
Υπολογιστικό κύκλωμαη τροποποιημένη μέθοδος simplex αντιστοιχεί σε ένα σύστημα πινάκων Τ 1 και Τ 2 (q) . Τραπέζι Τ 1 (ρύζι. 1.7) είναι κοινή για όλες τις επαναλήψεις και χρησιμεύει για τη λήψη μιας γραμμής εκτιμήσεων για την τρέχουσα γραμμή βάσης ένα 0 (β ( q)). Αν συμβολίσουμε με δ Εγώ(β ( q)) (ΕγώÎ 0: Μ) σειρές του πίνακα Δ -1 (β ( q)), στη συνέχεια από το (1.26), συγκεκριμένα, προκύπτει ότι
Όπως φαίνεται από ρύζι. 1.7, ΤΤο 1 αποτελείται από τρία μπλοκ:
Ø Ø το κέντρο περιέχει τον πίνακα Α;
Ø Ø στο αριστερό μπλοκ του πίνακα σε κάθε επανάληψη προστίθενται μηδέν σειρές του πίνακαΔ -1 (β ( q))για την τρέχουσα βάση;
Ø Ø κάτω μπλοκ που βρίσκεται κάτω από τη μήτρα Α, σε κάθε επανάληψη συμπληρώνεται με μια γραμμή εκτιμήσεων του τρέχοντος προγράμματος, που υπολογίζεται με τον τύπο (1.42).
Simplex τραπέζι Τ 2 (q) εμφανίζεται στο ρύζι. 1.8, αντιστοιχεί στην αποδεκτή βάση KZLP β ( q) παραλήφθηκε στις qη επανάληψη. Στήλη Ν(β ( q)) περιέχει τους αριθμούς των στηλών βάσης (με τη σειρά εμφάνισης στη βάση). στήλη σι(β ( q)) - συνιστώσες του διανύσματος περιορισμού σε σχέση με την τρέχουσα βάση β ( q) ; Δ -1 (β ( q)) - αντίστροφος πίνακας προς τον πίνακα εκτεταμένων στηλών της τρέχουσας βάσης β ( q) ; γραφική παράσταση α λπεριέχει ένα εκτεταμένο διάνυσμα συνθηκών που εισάγονται στη βάση κατά την τρέχουσα επανάληψη και το επόμενο γράφημα περιέχει συντεταγμένες α λ(β ( q)) της ίδιας στήλης στην τρέχουσα βάση β ( q) .
Κατ' αναλογία με την παράγραφο 1.4.1, περιγράφουμε το επίσημο σχήμα του αλγορίθμου τροποποιημένη μέθοδος Simplex.
0-στάδιο. Εύρεση μιας εφικτής γραμμής βάσης.
1. Για την εξεύρεση μιας αποδεκτής βάσης, μπορεί να εφαρμοστεί η μέθοδος ελαχιστοποίησης των υπολειμμάτων, που συζητείται στην παράγραφο 1.4.5. Στην περίπτωση αυτή για την επίλυση του βοηθητικού προβλήματος χρησιμοποιείται η διαδικασία της τροποποιημένης μεθόδου simplex. Ως αποτέλεσμα του σταδίου 0 λαμβάνουμε μια εφικτή βασική γραμμή Χ(β (1)) και την αντίστοιχη μήτρα Δ-1 (β (1)) και διάνυσμα σι(β(1)).
2. Συμπληρώστε το κεντρικό μέρος του πίνακα Τ 1 που περιέχει τη μήτρα ΕΝΑ.
3. Περιεχόμενα του πίνακα Δ -1 (β (1)) και του διανύσματος σι(β (1)), που ελήφθη στο στάδιο αναζήτησης αποδεκτού βασικού σχεδίου, μεταφέρεται στον πίνακα Τ 2 (1) .
4. Ορίστε τον αριθμό της τρέχουσας επανάληψης qίσο με 1 και πηγαίνετε στο στάδιο I.
Στάδιο 1. Τυπική επανάληψη του αλγορίθμου- πραγματοποιήθηκε για το επόμενο βασικό σχέδιο Χ(β ( q)).
1°. Έλεγχος της βελτιστοποίησης του τρέχοντος σχεδίου γραμμής βάσης. Περιεχόμενα της μηδενικής σειράς του πίνακα Τ 2 (q) - δ 0 (β ( q)) ξαναγράφεται στην αντίστοιχη στήλη του πίνακα Τ 1 . Με τον τύπο (1.42) υπολογίζουμε και συμπληρώνουμε τη γραμμή ένα 0 (β ( q)). Βλέπουμε τη γραμμή βαθμολογίας ένα 0 (β ( q)). Υπάρχουν δύο επιλογές:
1. ένα 0 (β ( q))≥0 -σχέδιο που αντιστοιχεί στην τρέχουσα βάση του προβλήματος, άριστος.Ολοκληρώθηκε η υπολογιστική διαδικασία. Σύμφωνα με τους τύπους (1.33) και (1.32), διαγράφεται το βέλτιστο σχέδιο για το πρόβλημα Χ* = Χ(β ( q)) Και βέλτιστη τιμήαντικειμενική λειτουργία φά(Χ*) = φά(Χ(β ( q))).
1". Στη γραμμή βαθμολογιών ένα 0 (β ( q)) υπάρχει τουλάχιστον ένα στοιχείο ένα 0, ι(β ( q))<0, т. е. имеющий отрицательную оценку. Следовательно, план Χ(β ( q)) - υποβέλτιστη. Επιλέγεται ο αριθμός μεγάλο, που αντιστοιχεί σε ένα στοιχείο που έχει ελάχιστη (μέγιστη σε απόλυτη τιμή) αρνητική βαθμολογία:
μεγάλοη στήλη μήτρας ΕΝΑγίνεται κύριοςκαι πρέπει να εισαχθεί στην επόμενη βάση. Ας προχωρήσουμε στο σημείο 2° του αλγορίθμου.
2°. Ορισμός στήλης που προέρχεται από βάση. Ξαναγράφοντας την κύρια στήλη α λαπό το τραπέζι Τ 1 στον τρέχοντα πίνακα Τ 2 (q) . Σύμφωνα με τον τύπο α λ(β ( q)) = Δ -1 (β ( q))α λσυμπληρώστε την αντίστοιχη στήλη στον πίνακα Τ 2 (q) . Υπάρχουν δύο επιλογές:
2». Για όλους ΕγώО 1: m a i, l(β ( q))≤0. Συμπεραίνεται ότι απεριόριστος αντικειμενική λειτουργία και η υπολογιστική διαδικασία τελειώνει.
2". Υπάρχει τουλάχιστον ένας δείκτης ΕγώО 1: Μ, για το οποίο a i, l(β ( q))>0. Σύμφωνα με τον κανόνα (1.27), η τοποθεσία καθορίζεται rκαι αριθμός N r(β ( q)) για μια στήλη που προέρχεται από τη βάση. Ας προχωρήσουμε στο σημείο 3° του αλγορίθμου.
3°. Επανυπολογισμός σε σχέση με τη νέα βάση στοιχείων της στήλης βΚαι μήτρεςΔ -1. Μετάβαση σε νέα βάση β ( q+1) , το οποίο προκύπτει εισάγοντας το β ( q) στήλη α λκαι βγάζοντας μια στήλη από αυτό a r, πραγματοποιείται σύμφωνα με τύπους παρόμοιους με τους τύπους (1.28)-(1.31). Μοιάζουν σαν:
Ορίζουμε τον αριθμό της τρέχουσας επανάληψης q: =q+l και πηγαίνουμε στο πρώτο σημείο του αλγορίθμου.
Συμπερασματικά, τονίζουμε ότι, λόγω των παραπάνω πλεονεκτημάτων, στην πραγματικότητα χρησιμοποιείται η τροποποιημένη μέθοδος simplex λογισμικό, σχεδιασμένο για την επίλυση κανονικών προβλημάτων γραμμικός προγραμματισμός.
1.5.2. Παράδειγμα αποφάσεις ΣΔΙΤτροποποιημένη μέθοδος Simplex.Ας παρουσιάσουμε μια λύση στο πρόβλημα που εξετάστηκε προηγουμένως (1.34)-(1.35), με βάση τη χρήση της διαδικασίας της τροποποιημένης μεθόδου simplex. Κατ' αναλογία με την ενότητα 1.4.3, ξεκινά με την επιλογή μιας προφανούς αρχικής βάσης που σχηματίζεται από τις στήλες (5,2,3). Για αυτό, Δ -1 (β ( q)) Και σι(β ( q)), συμπληρώνοντας λοιπόν τους αρχικούς πίνακες Τ 1 και ΤΤο 2(1) δεν είναι δύσκολο.
Στην πρώτη επανάληψη ξαναγράφουμε τη μηδενική γραμμή
από Τ 2 (1) ίντσες Τ 1 και πολλαπλασιάζοντάς το με τον πίνακα ΕΝΑ, λαμβάνουμε μια σειρά αξιολογήσεων
Επειδή έναΤο 0 (β (1)) περιέχει αρνητικά στοιχεία, τότε συμπεραίνουμε ότι το σχέδιο που αντιστοιχεί στη βάση β (1) δεν είναι βέλτιστο και, επιλέγοντας τη μικρότερη αρνητική εκτίμηση (-88), λαμβάνουμε τον αριθμό της στήλης που έχει εισαχθεί η βάση, μεγάλο= 4.
Ξαναγράφοντας τη στήλη
από το τραπέζι Τ 1 in Τ 2 (1) και υπολογίστε εκ νέου τις συντεταγμένες του σε σχέση με την τρέχουσα βάση, δηλαδή πολλαπλασιάστε τον πίνακα Δ -1 (β ( q)), που βρίσκεται στον πίνακα Τ 2 (1) στα αριστερά, επάνω ΕΝΑ 4 .
Αφού συμπληρώσετε τον πίνακα Τ 2 (1) Με τα δεδομένα της στήλης που εισάγονται στη νέα βάση, μπορείτε να προχωρήσετε στον προσδιορισμό του αριθμού της στήλης εξόδου. Αυτή η διαδικασία πραγματοποιείται σε πλήρη αναλογία με τη συμβατική μέθοδο simplex. Έχοντας εξετάσει τις σχέσεις των στοιχείων β i(β(1)) και a i, l(β (1)) για ( ΕγώО1: m| a i, l(β (1))>0) και αφού προσδιορίσουμε το ελάχιστο από αυτά, διαπιστώνουμε ότι r= 2. Επομένως, η στήλη με τον αριθμό Ν 2 (β ( q)) = 2 πρέπει να προκύψει από τη βάση. Έτσι, αποκτούμε μια άλλη αποδεκτή βάση για το πρόβλημα με Ν(β (2)) = (5, 4, 3). Στοιχείο έναΤο 2.3(β(1)) προηγείται (κυκλωμένο). Εφαρμόζοντας τους τύπους (1.43)-(1.46), περνάμε στον πίνακα simplex που αντιστοιχεί στη δεύτερη επανάληψη Τ 2 (2) και ορίστε τον δείκτη της τρέχουσας επανάληψης q = 2.
Επανάληψη των ίδιων βημάτων (μπορείτε εύκολα να τα ακολουθήσετε από τους πίνακες που δίνονται εδώ) Τ 2 (2) και Τ 2 (3), στην τρίτη επανάληψη λαμβάνουμε το βέλτιστο σχέδιο του προβλήματος και τη βέλτιστη τιμή της αντικειμενικής συνάρτησης, τα οποία εξάγονται από τη δεύτερη στήλη του πίνακα Τ 2 (3) . Είναι εύκολο να παρατηρήσουμε ότι στη διαδικασία επίλυσης «περάσαμε» την ίδια ακολουθία αποδεκτών βασικών σχεδίων που συναντήσαμε στην ενότητα 1.4.3.
Πρόβλημα βελτιστοποίησηςστα μαθηματικά είναι το πρόβλημα της εύρεσης του άκρου μιας πραγματικής συνάρτησης σε μια συγκεκριμένη περιοχή. Κατά κανόνα, λαμβάνονται υπόψη τομείς που ανήκουν και ορίζονται από ένα σύνολο ισοτήτων και ανισοτήτων.
3.1. Περιγραφή
Το πρόβλημα γραμμικού προγραμματισμού είναι ότι είναι απαραίτητο να μεγιστοποιηθεί ή να ελαχιστοποιηθεί κάποια γραμμική συνάρτηση σε έναν πολυδιάστατο χώρο κάτω από δεδομένους γραμμικούς περιορισμούς.
Καθεμία από τις γραμμικές ανισότητες σε μεταβλητές οριοθετεί ένα μισό διάστημα στον αντίστοιχο γραμμικό χώρο. Ως αποτέλεσμα, όλες οι ανισότητες δέσμευαν ένα συγκεκριμένο πολύεδρο (πιθανώς άπειρο), που ονομάζεται επίσης πολυεδρικός κώνος.
Η εξίσωση W(x) = c, όπου W(x) είναι η γραμμική συνάρτηση που πρέπει να μεγιστοποιηθεί (ή να ελαχιστοποιηθεί), δημιουργεί το υπερεπίπεδο L(c). Η εξάρτηση από το c δημιουργεί μια οικογένεια παράλληλων υπερεπίπεδων. Στην περίπτωση αυτή, το ακραίο πρόβλημα παίρνει την ακόλουθη διατύπωση: απαιτείται να βρεθεί το μεγαλύτερο c έτσι ώστε το υπερεπίπεδο L(c) να τέμνει το πολύεδρο τουλάχιστον σε ένα σημείο. Σημειώστε ότι η τομή ενός βέλτιστου υπερεπίπεδου και ενός πολυέδρου θα περιέχει τουλάχιστον μία κορυφή και θα είναι περισσότερες από μία εάν η τομή περιέχει μια ακμή ή μια όψη διαστάσεων k. Επομένως, το μέγιστο της συνάρτησης μπορεί να αναζητηθεί στις κορυφές του πολυέδρου. Η αρχή της μεθόδου simplex είναι ότι επιλέγεται μία από τις κορυφές του πολυέδρου, μετά την οποία αρχίζει η κίνηση κατά μήκος των άκρων του από κορυφή σε κορυφή προς την κατεύθυνση της αύξησης της τιμής της συνάρτησης. Όταν η μετάβαση κατά μήκος μιας ακμής από την τρέχουσα κορυφή σε μια άλλη κορυφή με υψηλότερη λειτουργική τιμή είναι αδύνατη, θεωρείται ότι έχει βρεθεί η βέλτιστη τιμή του c.
Η ουσία της μεθόδου simplex είναι ότι αν ο αριθμός των αγνώστων περισσότερος αριθμόςεξισώσεις, λοιπόν αυτό το σύστημααβέβαιο με αμέτρητες λύσεις. Για την επίλυση του συστήματος, όλα τα άγνωστα χωρίζονται αυθαίρετα σε βασικά και δωρεάν. Ο αριθμός των βασικών μεταβλητών καθορίζεται από τον αριθμό των γραμμικά ανεξάρτητων εξισώσεων. Οι υπόλοιποι άγνωστοι είναι ελεύθεροι. Τους δίνονται αυθαίρετες τιμές και στη συνέχεια αντικαθίστανται στο σύστημα. Σε οποιοδήποτε σύνολο ελεύθερων αγνώστων μπορεί να δοθεί ένας άπειρος αριθμός αυθαίρετων τιμών, που θα δώσει έναν άπειρο αριθμό λύσεων. Εάν όλα τα δωρεάν άγνωστα οριστούν στο μηδέν, τότε η λύση θα αποτελείται από τις τιμές των βασικών αγνώστων. Αυτή η λύση ονομάζεται βασική.
Στη θεωρία του γραμμικού προγραμματισμού, υπάρχει ένα θεώρημα που δηλώνει ότι μεταξύ των βασικών λύσεων του συστήματος μπορεί κανείς να βρει τις βέλτιστες, και σε ορισμένες περιπτώσεις, αρκετές βέλτιστες λύσεις, οι οποίες θα παρέχουν όλες ένα άκρο της αντικειμενικής συνάρτησης. Έτσι, αν βρείτε κάποιο βασικό σχέδιο και στη συνέχεια το βελτιώσετε, θα πάρετε βέλτιστη λύση. Η μέθοδος simplex βασίζεται σε αυτήν την αρχή.
Η ακολουθία των υπολογισμών που χρησιμοποιούν τη μέθοδο simplex μπορεί να χωριστεί σε δύο κύριες φάσεις:
1. εύρεση της αρχικής κορυφής του συνόλου των εφικτών λύσεων.
2. διαδοχική μετάβαση από κορυφή σε κορυφή, που οδηγεί στη βελτιστοποίηση της τιμής της αντικειμενικής συνάρτησης.
Σε ορισμένες περιπτώσεις, η αρχική λύση είναι προφανής ή ο ορισμός της δεν απαιτεί σύνθετους υπολογισμούς - για παράδειγμα, όταν όλοι οι περιορισμοί αντιπροσωπεύονται από ανισότητες της μορφής «μικρότερο ή ίσο με» (τότε το μηδενικό διάνυσμα είναι απολύτως αποδεκτή λύση, αν και, πιθανότατα, απέχει πολύ από το βέλτιστο). Σε τέτοια προβλήματα, η πρώτη φάση της μεθόδου simplex μπορεί να παραλειφθεί εντελώς. Η μέθοδος simplex χωρίζεται ανάλογα σε μονή φάσηΚαι
διφασικό.
3.2. Αλγόριθμος μεθόδου Simplex
Ενισχυμένη δήλωση προβλήματος
Εξετάστε το ακόλουθο πρόβλημα γραμμικού προγραμματισμού:
Τώρα ας θέσουμε αυτό το πρόβλημα σε μια ισοδύναμη ενισχυμένη μορφή. Είναι απαραίτητο να μεγιστοποιήσετε το Z, όπου:
Εδώ x είναι οι μεταβλητές από την αρχική γραμμική συνάρτηση. x s – νέες μεταβλητές που συμπληρώνουν τις παλιές με τέτοιο τρόπο ώστε η ανισότητα να μετατρέπεται σε ισότητα. γ – συντελεστές της αρχικής γραμμικής συνάρτησης. Το Z είναι η μεταβλητή που πρέπει να μεγιστοποιηθεί. Τα ημιδιάστημα και στην τομή σχηματίζουν ένα πολύεδρο που αντιπροσωπεύει το σύνολο των εφικτών λύσεων. Η διαφορά μεταξύ του αριθμού των μεταβλητών και των εξισώσεων δίνει τον αριθμό των βαθμών ελευθερίας. Με απλά λόγια, αν λάβουμε υπόψη την κορυφή ενός πολυέδρου, αυτός είναι ο αριθμός των ακμών κατά μήκος των οποίων μπορούμε να συνεχίσουμε να κινούμαστε.
Στη συνέχεια, μπορούμε να εκχωρήσουμε την τιμή 0 σε αυτόν τον αριθμό μεταβλητών και να καλέσουμε
Ας εξηγήσουμε τους υπολογισμούς a i , j ¢χρησιμοποιώντας τον «κανόνα του ορθογωνίου». Είναι απαραίτητο να λάβετε το στοιχείο ενεργοποίησης ακ, sκαι συνδέστε το νοερά με τον συντελεστή του οποίου τη νέα τιμή θέλετε να βρείτε. Αυτή η γραμμή πρέπει να θεωρείται η κύρια διαγώνιος είναι κατασκευασμένο πάνω της, οι πλευρές του οποίου είναι σειρές και στήλες. Πρέπει να σχεδιάσετε μια δευτερεύουσα διαγώνιο στο ορθογώνιο, τότε η τιμή του νέου συντελεστή θα είναι ίση με την αρχική του τιμή, από την οποία αφαιρείται το γινόμενο των στοιχείων που βρίσκονται στη δευτερεύουσα διαγώνιο διαιρούμενο με το στοιχείο επίλυσης. Ας εξηγήσουμε αυτές τις ενέργειες στο διάγραμμα (Εικ. 1.9). Πριν συμπληρώσετε τον πίνακα simplex, θα πρέπει να παρουσιαστούν οι αρχικές εξισώσεις στη φόρμα (1.21). |
|||||
|
|||||
|
|||||
Ας δούμε την ουσία των μετασχηματισμών της μεθόδου simplex χρησιμοποιώντας το παράδειγμα 1.4. Ας θυμηθούμε τις ανισότητες περιορισμών και την αντικειμενική συνάρτηση από αυτό το παράδειγμα και ας βρούμε Μέγιστηαντικειμενική συνάρτηση χρησιμοποιώντας την παραπάνω μέθοδο:
F = 908X 1 + 676X 2 ® μέγ.
X 1 + X 2 14,
X 2 10,
10 X 1 + 8 X 2 120,
7X 1 + 5 X 2 70,
4X 1 + 2X 2 28,
| |
Ας το μετατρέψουμε σε κανονική μορφή εισάγοντας πρόσθετες μεταβλητές Xj 0, και μετατρέποντας τις ανισότητες σε ισότητες. Πρέπει να σημειωθεί ότι εάν υπάρχει σύμβολο "" στην ανισότητα, τότε με μια ελεύθερη μεταβλητή γράφουν "-", διαφορετικά - "+":
X 1 + X 2 = 14 - X 3,
X 2 = 10 - X 4,
10 X 1 + 8 X 2 = 120 - X 5,
7X 1 + 5 X 2 = 70 - X 6,
4X 1 + 2X 2 = 28 - X 7.
Για να ξεκινήσετε τη διαδικασία της μεθόδου simplex, πρέπει πρώτα να βρείτε μια λύση αναφοράς από το σύνολο των βασικών λύσεων του προκύπτοντος συστήματος εξισώσεων. Λαμβάνοντας αυτό υπόψη, υπάρχουν τρία στάδια στην επίλυση προβλημάτων χρησιμοποιώντας τη μέθοδο simplex:
Εύρεση της αρχικής βασικής λύσης και σχηματισμός του αρχικού πίνακα simplex.
Προσδιορισμός αποδεκτής λύσης.
Προσδιορισμός της βέλτιστης λύσης.
1ο στάδιο
Αρχικός βασική λύσησυστήματα που βρίσκουμε υποθέτοντας ελεύθερες μεταβλητές Χ 1Και Χ 2 .
Επειτα X 3 = 14 - X 1 - X 2,
X 4 = 10 - X 2,
X 5 =120 - 10X 1 - 8X 2,
X 6 = 70 - 10X 1 - 5X 2,
X 7 = 28 - 4X 1 - 2X 2,
F = 908X 1 + 676X 2 = 0.
Ας μετατρέψουμε αυτές τις εξισώσεις σε κανονική εμφάνιση:
X 3 = 14 - (X 1 + X 2),
X 4 = 10 - (0X 1 + X 2),
X 5 =120 - (10X 1 + 8X 2),
X 6 = 70 - (7X 1 + 5X 2),
X 7 = 10 - (4X 1 + 2X 2),
F = 0 + 908 X 1 + 676 X 2.
Γράφουμε το προκύπτον σύστημα εξισώσεων με τη μορφή του αρχικού πίνακα simplex (Πίνακας 1.9). Στον πίνακα 1.9 δεν υπάρχουν αρνητικά δωρεάν μέλη. Κατά συνέπεια, έχουμε λάβει μια λύση υποστήριξης (αποδεκτή), καθώς αποδεκτή λύση είναι οποιαδήποτε μη αρνητική λύση (για την οποία > 0 ), αλλά δεν είναι βέλτιστο.
Προφανώς, αν για όλα τα άγνωστα στην αντικειμενική συνάρτηση φάΕάν οι συντελεστές ήταν θετικοί, τότε θα επιτευχθεί η μέγιστη τιμή φά. Από αυτό προκύπτει σημάδι βέλτιστης αποδεκτής λύσης: V φά- η σειρά του πίνακα simplex δεν πρέπει να έχει αρνητικούς συντελεστές.
Πίνακας 1.9
| Βασικές Μεταβλητές X β | Δωρεάν μέλος | Δωρεάν μεταβλητές | |
| Χ 1 | Χ 2 | ||
| Χ 3 | |||
| Χ 4 | |||
| Χ 5 | |||
| Χ 6 | |||
| Χ 7 | |||
| φά | - 908 | - 676 |
2ο στάδιο
Ας θυμηθούμε ότι η κύρια λειτουργία της μεθόδου simplex είναι ουσιαστικά ότι κάποια βασική μεταβλητή αντικαθίσταται από μια ελεύθερη μεταβλητή . Σε αυτήν την περίπτωση, η λειτουργία αντικατάστασης εκτελείται υπό τις ακόλουθες προϋποθέσεις:
Τιμή αντικειμενικής συνάρτησης φάη νέα (παραδεκτή) λύση αναφοράς πρέπει να είναι μεγαλύτερη από την προηγούμενη.
Η νέα λύση του συστήματος πρέπει επίσης να είναι αναφοράς (παραδεκτή).
Στο παράδειγμά μας, η πρώτη συνθήκη ικανοποιείται εάν το στοιχείο ενεργοποίησης είναι θετικό και επιλέγεται στη στήλη αρνητικού συντελεστή φά- γραμμές.
Η δεύτερη συνθήκη ικανοποιείται εάν το στοιχείο διαχωρισμού βρεθεί ως η ελάχιστη θετική αναλογία των στοιχείων της στήλης ελεύθερων μελών προς τα αντίστοιχα στοιχεία της στήλης διαχωρισμού.
Σύμφωνα με τον κανόνα που αναφέρθηκε παραπάνω, για να βρεθεί μια αποδεκτή λύση, οι βασικές και οι ελεύθερες μεταβλητές ανταλλάσσονται. Για να το κάνετε αυτό, βρείτε ένα στοιχείο επίλυσης (το πλαισιώνεται στον Πίνακα 1.9). Στην περίπτωσή μας, η επιτρεπτή στήλη θα πρέπει να είναι σαν Χ 1 , Έτσι Χ 2. Διαίρεση ελεύθερων μεταβλητών με τις αντίστοιχες τιμές τους Χ 1Και Χ 2 (εκτός από τη γραμμή φά), βρίσκουμε τη μικρότερη θετική τιμή. Είναι σημαντικό να σημειωθεί ότι για τη στήλη Χ 1 :
Είναι σημαντικό να σημειωθεί ότι για τη στήλη Χ 2:
Η μικρότερη αναλογία 28/4 ορίζει τη γραμμή επίλυσης και τη στήλη επίλυσης και η τομή της στήλης επίλυσης και της γραμμής επίλυσης είναι το στοιχείο επίλυσης ένα ks= 4. Στον πίνακα. 1.9 σημειώνουμε τη στήλη αδειοδότησης και τη γραμμή άδειας με βέλη (®). Έχοντας αποφασίσει ένα ks, δημιουργήστε τον παρακάτω πίνακα, στον οποίο οι μεταβλητές που περιλαμβάνονται στη γραμμή και τη στήλη του στοιχείου επίλυσης ανταλλάσσονται ᴛ.ᴇ. μετατρέψτε τις βασικές μεταβλητές σε ελεύθερες και τις ελεύθερες σε βασικές.
Στο παράδειγμά μας, ανταλλάσσουμε τις μεταβλητές Χ 7 Και Χ 1 , σημειώνεται στον πίνακα. 1,9 βέλη. Συντελεστές του νέου πίνακα. Το 1,10 βρίσκεται από τους συντελεστές του παλιού πίνακα. 1.9, χρησιμοποιώντας τις εκφράσεις που δίνονται στον πίνακα. 1.8 και τον «κανόνα του ορθογωνίου». Στον πίνακα 1.10 πάλι δεν έχουμε βέλτιστη λύση.
Πίνακας 1.10
| Βασικές Μεταβλητές X β | Ελεύθερο Μέλος Β | Δωρεάν μεταβλητές | |||||||||||
| Χ 7 | Χ 2 | ||||||||||||
| Χ 3 | - 1/4 | 1/2 | |||||||||||
| Χ 4 | |||||||||||||
| Χ 5 | -5/2 | ||||||||||||
| Χ 6 | -7/4 | 3/2 | |||||||||||
| Χ 1 | 1/4 | 1/2 | |||||||||||
| φά | -222 | ||||||||||||
Σύμφωνα με τους κανόνες που περιγράφονται παραπάνω στον πίνακα. 1.10 βρίσκουμε το στοιχείο επίλυσης 1 και χτίζουμε έναν νέο πίνακα. 1.11 αντικαθιστώντας τη βάση ( Χ 4Και Χ 2). Τονίζουμε ιδιαίτερα ότι για να βρούμε το στοιχείο επίλυσης πρέπει να επιλέξουμε τη μικρότερη θετική τιμή, ᴛ.ᴇ. Δεν θεωρούμε αρνητικές σχέσεις ελεύθερων όρων με τους συντελεστές της στήλης ανάλυσης.
3ο στάδιο
Ας ελέγξουμε αν η λύση που βρέθηκε είναι η βέλτιστη και για το παράδειγμά μας - η μέγιστη. Για να γίνει αυτό, θα αναλύσουμε την αντικειμενική συνάρτηση φά: F = 8576 + 227 X 7 + 222 X 4.
Η αντικειμενική συνάρτηση δεν περιέχει αρνητικούς συντελεστές και έχει υψηλότερη τιμήΣτον τελευταίο πίνακα, πήραμε τη βέλτιστη λύση:
X 3 = 2; X 2 = 10; X 5 = 20; X 6 = 6; X 1 = 2; X 7 = X 4 = 0;
F max = 8576.
Σημειώστε ότι τα αποτελέσματα της επίλυσης της μεθόδου simplex και της γραφικής μεθόδου είναι τα ίδια.
Σύμφωνα με την εξεταζόμενη ακολουθία, ο αλγόριθμος της μεθόδου simplex πρέπει να έχει τα ακόλουθα μπλοκ:
1. Εύρεση της αρχικής βασικής (αναφοράς) λύσης και σχηματισμός του αρχικού πίνακα.
2. Εύρεση του στοιχείου επίλυσης ένα ks(εύρεση του αρνητικού ελεύθερου όρου - β i < 0 и минимального отношенияb i / a ij; αν δεν υπάρχουν αρνητικοί συντελεστές στη σειρά του αρνητικού ελεύθερου όρου, τότε το πρόβλημα είναι άλυτο).
3. Επανυπολογισμός νέο τραπέζισύμφωνα με τους τύπους του πίνακα. 1.8.
4. Έλεγχος ύπαρξης αρνητικού ελεύθερου όρου. Εάν υπάρχει, τότε προχωρήστε στο βήμα 2. Η απουσία αρνητικού ελεύθερου όρου σημαίνει ότι έχει ληφθεί μια λύση αναφοράς (αποδεκτή).
5. Παρόμοια με τα βήματα 2 - 4, ο πίνακας υπολογίζεται εκ νέου κατά την αναζήτηση της βέλτιστης λύσης.
Επίλυση του προβλήματος LP χρησιμοποιώντας τη μέθοδο simplex σε μορφή πίνακα
Απαιτείται για ελαχιστοποίηση 
,
υπό περιορισμούς
στο " Χ³ 0.
Ας εισάγουμε διανύσματα:
ντο= (C 1 , ... , C n) - διάνυσμα εκτιμήσεων,
Χ= (X 1 , ... , X n) - διάνυσμα μεταβλητών,
σι= (B 1 , ... , B m) - διάνυσμα περιορισμών
και μήτρα
ΕΝΑ=
μέγεθος (mn) - πίνακας συντελεστών περιορισμού.
Τότε το πρόβλημα LP θα έχει την εξής ερμηνεία:
ελαττώνω F=CX
υπο προυποθεσεις AX = b, X 0.
Αυτό το πρόβλημα μπορεί να γραφτεί σε μορφή πίνακα:
Ας εισάγουμε τη σημειογραφία:
A * = 
- εδώ είναι η μήτρα ΕΝΑ* μέγεθος (m+1)(n+1).
Σύμφωνα με την παραπάνω μέθοδο, βρίσκεται το στοιχείο διαχωρισμού ένα ks.
Το επόμενο βήμα της μεθόδου simplex είναι η διαδικασία εξάλειψης Gaussian, η οποία σας επιτρέπει να κάνετε όλους τους συντελεστές σε μικρό- στήλη m, εκτός ένα ks, μηδέν, ένα ks- ίσο με ένα.
Είναι σημαντικό να σημειωθεί ότι για τη μέθοδο simplex σε μορφή πίνακα, η επανάληψη της μεθόδου simplex είναι ισοδύναμη με τον πολλαπλασιασμό εξίσωση μήτραςαριστερά στο επόμενο τετράγωνη μήτρα:
|
, Οπου κ 0; μικρό 0.
Αν όλες οι στήλες του πίνακα ΕΝΑχωρίστε σε βασικά σικαι μη βασικά Ν,τότε το πρόβλημα LP μπορεί να γραφτεί ως εξής:
,
Οπου CbΚαι Γ Ν- αντίστοιχες διανυσματικές συνιστώσες Γ, Χ β, Χ Ν- βασικές και μη βασικές μεταβλητές.
Για να επιλέξετε αρχικές μεταβλητές βάσης x β θα πρέπει να πολλαπλασιάσετε την εξίσωση στα αριστερά με τον πίνακα:
Οπου R= Cb B-1.
Ως αποτέλεσμα παίρνουμε
,
Οπου Εγώ- μήτρα ταυτότητας.
Από αυτό προκύπτει ότι οι σχετικές εκτιμήσεις για μη βασικές μεταβλητές
c j = c j - C b B -1 a j = c j - Ra j .
Η βάση θα είναι αποδεκτή εάν οι ελεύθεροι όροι των μεταβλητών βάσης είναι μη αρνητικοί, ᴛ.ᴇ. B -1 b ³ 0.
Αν γ ι³ 0 για , τότε η βάση είναι η βέλτιστη λύση στο πρόβλημα. Το διάνυσμα ονομάζεται διάνυσμα τρέχουσας τιμής. Κάθε σειρά πολλαπλασιάζεται με ένα διάνυσμα Rκαι αφαιρείται από τη γραμμή του συντελεστή κόστους προκειμένου να εξαλειφθούν οι συντελεστές κόστους για τις υποκείμενες μεταβλητές.
Εάν το πρόβλημα LP δεν προσδιορίζεται στο κανονική μορφή, ᴛ.ᴇ.
ελαττώνω F=CX
υπο προυποθεσεις AX b , X 0,
Στη συνέχεια, εισάγοντας αδύναμες μεταβλητές, μπορούν να γραφτούν στη μορφή
Η μέθοδος εξάλειψης σειρών για έναν πίνακα είναι ισοδύναμη με τον πολλαπλασιασμό αυτού του πίνακα από τα αριστερά με Β-1, Οπου σι- βάση υπομήτρας ΕΝΑ, Επειτα
,
ᴛ.ᴇ. μήτρα που λαμβάνεται στη θέση του πίνακα ταυτότητας Εγώ, θα είναι ο αντίστροφος πίνακας για την τρέχουσα βάση. Σχετικές αξιολογήσεις που βρίσκονται παραπάνω μήτρα ταυτότητας, θα
,
αφού είναι μοναδιαία διανύσματα.
Επειδή F= C b B -1 b = Rb,η τρέχουσα τιμή της αντικειμενικής συνάρτησης είναι ίση με το γινόμενο του διανύσματος των τρεχουσών τιμών του πίνακα ΕΝΑστο αρχικό διάνυσμα σι.
Παράδειγμα.
Δημοσιεύτηκε στο ref.rf
φά =
5X 1 + 6X 2 + 3X 3 + 4X 4 + 5X 5® min
υπό περιορισμούς
2X 1 + 3X 3 + 4X 4 + 2X 5 = 10 ,
3X 2 + 3X 4 + 6X 5 = 9,
| |
Για αυτό το παράδειγμαμήτρα ΕΝΑ*θα μοιάζει
.
Αφήνω Χ 1Και Χ 2- βασικές μεταβλητές.
Μήτρα σιμοιάζει με
.
Στη συνέχεια ο αντίστροφος πίνακας Β-1έχει την παρακάτω μορφή
.
Να σας το υπενθυμίσουμε 
, όπου ο παρακείμενος πίνακας που αποτελείται από αλγεβρικά συμπληρώματα στοιχείων β ικορίζουσα του πίνακα σι.
Η ορίζουσα ισούται με:
= 
.
Επομένως, η μήτρα σιόχι ιδιαίτερο.
Αλγεβρικές προσθήκεςΤα στοιχεία της ορίζουσας έχουν τις ακόλουθες έννοιες:
b 11 = 3, b 12 = 0, b 12 = 0, b 22 = 2; εκείνοι . .
Πολλαπλασιάζοντας με , βρίσκουμε αντίστροφη μήτρα:
.
Ο φορέας των τρεχουσών τιμών θα είναι
R = C b B -1 =
=
.
Να σας το υπενθυμίσουμε Cb-διανυσματικά στοιχεία βάσης ντο:
Τότε = 
.
Για να επιλέξετε την αρχική βάση χρειάζεστε έναν πίνακα ΕΝΑ*αριστερά πολλαπλασιάζεται με μήτρα
=
.
Το στοιχείο επίλυσης βρίσκεται σε ένα τετράγωνο.
Η επανάληψη της μεθόδου simplex είναι ισοδύναμη με τον πίνακα που προκύπτει πολλαπλασιασμένος από τα αριστερά επί τον ακόλουθο πίνακα:
.
Αυτός ο πίνακας λαμβάνεται από τον πίνακα (1.23)
Εδώ aks = 2;
a 11 = 1; a 12 = - a 0s / a ks = - 12/2 = - 6;
a 13 = 0 ; a 21 = 0 ; a 22 = 1/ a ks = 1/2 ; a23 = 0;
a 31 = 0 ; a 32 = - a ms / a ks = -1/2 ; a 33 = 1.
Τότε έχουμε
=
(1.24)
Το αναλυτικό στοιχείο τοποθετείται σε τετράγωνο.
Η επόμενη επανάληψη της μεθόδου simplex είναι ισοδύναμη με τον αριστερό πολλαπλασιασμό με τον πίνακα
.
=
.
Ως εκ τούτου, Fmin =11; Χ 4=7/3; Χ 5=1/3; Χ 1 = Χ 2 = Χ 3=0.
Τροποποιημένη μέθοδος Simplex (MSM) διαφορετική από τη συνηθισμένη μέθοδο simplex (ΕΚ) γιατί μέσα ΕΚΌλα τα στοιχεία των πινάκων simplex υπολογίζονται εκ νέου σε κάθε επανάληψη και όταν λαμβάνεται ο επόμενος πίνακας, όλοι οι προηγούμενοι πίνακες, συμπεριλαμβανομένου του αρχικού, δεν αποθηκεύονται. ΣΕ MSMο αρχικός πίνακας αποθηκεύεται και σε κάθε επανάληψη καθορίζονται τα εξής: μια σειρά σχετικών εκτιμήσεων ντοεισάγεται στη βάση και την τρέχουσα τιμή του διανύσματος των δεξιών πλευρών των περιορισμών. Για να προσδιοριστούν όλα τα στοιχεία του πίνακα μετά j-η επανάληψη ΕΚ, αρκεί να γνωρίζουμε τη μήτρα Β-1, που αντιστοιχεί σε αυτόν τον πίνακα, τον αρχικό πίνακα και τους δείκτες των τρεχουσών βασικών μεταβλητών. Στη συνέχεια το τρέχον διάνυσμα R = C b B -1(οι δείκτες των τρεχουσών βασικών μεταβλητών καθορίζουν ποια στοιχεία του διανύσματος εκτιμήσεων από τον πίνακα πηγής περιλαμβάνονται στο διάνυσμα Γ β); =Β -1 β, Οπου σιλαμβάνεται από τον αρχικό πίνακα και οποιαδήποτε στήλη του νέου πίνακα = Β-1ένα ι , Οπου ένα ι - στήλη του πίνακα πηγής.
Ας δοθεί τώρα ο πίνακας πηγών Β-1, που αντιστοιχεί στον πίνακα Εγώη επανάληψη. Για να πάρουμε το matrix Β-1, αντίστοιχος (i+1)-Για την επανάληψη, πρέπει να ορίσετε μια μη βασική στήλη Εγώο πίνακας που πρέπει να εισαχθεί στη βάση. Από ΕΚσυνεπάγεται ότι πρέπει να μπει στη βάση αν C j<0. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, крайне важно вычислить C jΓια Εγώου πίνακες, επιλέξτε μεταξύ τους<0, а затем вычислить
ένα μικρό = Β-1και = Β -1 β (= C j - Ra ι ).
Έχοντας βρει το στοιχείο επίλυσης και χρησιμοποιώντας τα στοιχεία των διανυσμάτων και , βρίσκουμε τον πίνακα Β-1για τον παρακάτω πίνακα.
Παράδειγμα.Χρησιμοποιώντας την τροποποιημένη μέθοδο simplex για ελαχιστοποίηση
F = 5X 1 + 6X 2 + 3X 3 + 4X 4 + 5X 5 ® min
με περιορισμούς:
2X 1 + 3X 3 + 4X 4 + 2X 5 = 10,
3X 2 + 3X 4 + 6X 5 = 9,
| |
Επιλογή ως βασικές μεταβλητές Χ 1Και Χ 2, λάβαμε την ακόλουθη εργασία: F = 43 - 9/2X 3 - 12X 4 - 12X 5
Ας εξετάσουμε μια μέθοδο για την επίλυση του προβλήματος της CPU χρησιμοποιώντας τις ιδέες της μεθόδου simplex. Το κύριο χαρακτηριστικό των εργασιών της CPU είναι ο σχεδιασμός της αντικειμενικής συνάρτησης και των μεταβλητών που υποδεικνύουν αποκλίσεις από το επιθυμητό επίπεδο επίτευξης στόχου. Εάν λάβουμε υπόψη αυτά τα χαρακτηριστικά, τότε η συνήθης μέθοδος μπορεί να χρησιμοποιηθεί για την επίλυση τέτοιων προβλημάτων. μέθοδο simplex. Ας το επεξηγήσουμε αυτό χρησιμοποιώντας το παράδειγμα που συζητήθηκε προηγουμένως. Ο αλγόριθμος απλοποιείται σε κάποιο βαθμό λόγω του γεγονότος ότι η αρχική βασική λύση είναι προφανής. Ο ρόλος των βασικών μεταβλητών για το αρχικό σχέδιο εδώ παίζεται από αρνητικές αποκλίσεις "d", οι οποίες περιλαμβάνονται στο μοντέλο με συντελεστές +1. Είναι πιο δύσκολο με τη γραμμή για τους συντελεστές της αντικειμενικής συνάρτησης, δηλ. με γραμμή αξιολόγησης. Όπως γνωρίζουμε, οι συντελεστές για αποκλίσεις στην αντικειμενική συνάρτηση μιας εργασίας CPU είναι βάρη που ταξινομούν τους στόχους κατά προτεραιότητα. Οι αριθμητικές τους τιμές, κατά κανόνα, δεν καθορίζονται. Είναι σημαντικό ο συντελεστής απόκλισης για έναν περιορισμό στόχο με υψηλότερη προτεραιότητα να είναι σημαντικά μεγαλύτερος από τον συντελεστή απόκλισης από έναν στόχο χαμηλότερης προτεραιότητας. Επομένως, για τη διευκόλυνση των υπολογισμών, η γραμμή αξιολόγησης χωρίζεται σε πολλές γραμμές (ανάλογα με τον αριθμό των προτεραιοτήτων) και οι υπολογισμοί πραγματοποιούνται για κάθε γραμμή ξεχωριστά.
Άρα, αφήστε το πρόβλημα να λυθεί min Z = P 1 d 1 - + P 2 d 2 - + P 3 d 3 + + P 4 d 4 - ,
υπό την προϋπόθεση ότι
7x 1 + 6x 2 + d 1 - – d 1 + = 30;
2x 1 + 3x 2 + d 2 - – d 2 + = 12;
6x 1 + 5x 2 + d 3 - – d 3 + = 30;
x 2 + d 4 - – d 4 + = 7;
x 1 , x 2 , d i - , d i + ³ 0 (i = ).
Ας δημιουργήσουμε τον αρχικό πίνακα simplex (Πίνακας 5.1.)
Πίνακας 5.1 – Αρχικός πίνακας simplex
| C j C B | Βάση | Λύση | 0 x 1 | 0 x 2 | P 1 d 1 - | P 2 d 2 - | d 3 - | P 4 d 4 - | d 1 + | d 2 + | P 3 d 3 + | d 4 + | q |
| P 1 P 2 P 4 | d 1 - d 2 - d 3 - d 4 - | 7 | -1 | -1 | -1 | -1 | 30/7 30/6 - | ||||||
| Z j – С j | P 4 P 3 P 2 P 1 | -1 | -1 | -1 | -1 |
Όπως είναι γνωστό, τα στοιχεία της γραμμής αξιολόγησης (Z j – C j) υπολογίζονται σύμφωνα με τον κανόνα: «το στοιχείο της επάνω σειράς αφαιρείται από το άθροισμα των γινομένων των στοιχείων της στήλης «C in» κατά τα στοιχεία της αντίστοιχης στήλης.» Για παράδειγμα, για τη στήλη «λύση», το στοιχείο «Z j – C j» ισούται με: Р 1 *30 + Р 2 *12 + 0* 30 + р 4 *7 – 0 = 30Р 1 + 12Р 2 + 7Р 4 και οι συντελεστές για το αντίστοιχο P i (i = ) γράφονται σε αυτή τη στήλη στο μπλοκ "Z j – C j" (διαβάστε από κάτω προς τα πάνω). Για τη στήλη "x 1": P 1 *7 + P 2 *2 + 0 * 6 + P 4 *0 – 0 = 7P 1 + 2P 2, και αυτοί είναι οι συντελεστές για P 1 και P 2 στο μπλοκ " Z j – C j ", κ.λπ.
Εφόσον το πρόβλημα της CPU επιλύεται πάντα στο ελάχιστο, η λύση θα είναι βέλτιστη εάν όλα τα στοιχεία της γραμμής αξιολόγησης δεν είναι θετικά. Στην περίπτωσή μας, δύο εκτιμήσεις (στις στήλες "x 1" και "x 2") είναι θετικές, επομένως, το σχέδιο δεν είναι βέλτιστο. Για να προσδιορίσουμε τη μεταβλητή που περιλαμβάνεται στη βάση, στην πρώτη επανάληψη προσδιορίζουμε τη μεγαλύτερη θετική εκτίμηση. Καθορίζεται από το πρόσημο του συντελεστή στο P 1, επειδή P 1 >> P 2 >> P 3 >> P 4 . Εάν οι συντελεστές για το P 1 είναι ίσοι, «ανεβαίνουμε» στην παραπάνω γραμμή και επιλέγουμε τον μεγαλύτερο συντελεστή εκεί. Σε περίπτωση πλήρους ισότητας σε όλες τις σειρές, επιλέγεται οποιαδήποτε από αυτές. Στην περίπτωσή μας, η στήλη επίλυσης θα είναι η στήλη "x 1" (από 7 > 6). Η σειρά επίλυσης επιλέγεται με τον ίδιο τρόπο όπως στη μέθοδο simplex - σύμφωνα με τον μικρότερο λόγο simplex q (διαιρούμε τα στοιχεία της στήλης "λύση" με τα θετικά στοιχεία της στήλης επίλυσης). Στον Πίνακα 5.1, ο μικρότερος λόγος q βρίσκεται στην πρώτη σειρά. Έτσι, στην επόμενη επανάληψη, η μεταβλητή "x 1" εισάγεται στη βάση, εξάγεται το "d 1 -". Υπολογίζουμε ξανά τον πίνακα όπως στη συνηθισμένη μέθοδο simplex (Πίνακας 5.2.)
Πίνακας 5.2 – Δεύτερος πίνακας simplex
| C j C B | Βάση | Λύση | x 1 | x 2 | P 1 d 1 - | P 2 d 2 - | d 3 - | P 4 d 4 - | d 1 + | d 2 + | P 3 d 3 + | d 4 + | q |
| P 2 P 4 | x 1 d 2 - d 3 - d 4 - | 30/7 24/7 30/7 | 6/7 9/7 1/7 | 1/7 2/7 6/7 | 1/7 2/7 6/7 | -1 | -1 | -1 | 30/6 24/9 - | ||||
| Z j – C j | P 4 P 3 P 2 P 1 | 24/7 | 9/7 | 2/7 -1 | 2/7 | -1 | -1 | -1 |
Όπως μπορούμε να δούμε, στη δεύτερη επανάληψη, το d 2 - αφαιρείται από τη βάση και το x 2 εισάγεται στη βάση. Και ούτω καθεξής μέχρι να έχουμε τη βέλτιστη λύση. Μετά την 4η επανάληψη παίρνουμε τον πίνακα 5.3.
Πίνακας 5.3 – Τελικός πίνακας simplex
| C j C B | Βάση | Λύση | x 1 | x 2 | P 1 d 1 - | P 2 d 2 - | d 3 - | P 4 d 4 - | d 1 + | d 2 + | P 3 d 3 + | d 4 + |
| Σ 4 | d 2 + x 2 d 1 + d 4 - | 1,6 1,2 0,2 -1,2 | -1 | -1 | 0,6 0,2 1,2 -0,2 | -0,6 -0,2 -1,2 0,2 | -1 | |||||
| Z j – C j | P 4 P 3 P 2 P 1 | -1,2 | -1 | -1 | -0,2 | 0,2 -1 | -1 |
Το γεγονός ότι υπάρχει ένα θετικό στοιχείο στη σειρά στο P 4 (στη στήλη d 3 +) σημαίνει ότι ο τέταρτος στόχος δεν έχει επιτευχθεί πλήρως. Σε αυτήν την περίπτωση, η συνάρτηση στόχος είναι ίση με P 4, αυτή είναι η ελάχιστη δυνατή τιμή της. Γενικά, η εκτίμηση της μεταβλητής d 3 + είναι ίση με (0,2 P 4 – P 3), και αφού P 3 >> P 4, είναι τελικά αρνητική. Όλες οι άλλες εκτιμήσεις είναι μη θετικές, επομένως, το σχέδιο είναι βέλτιστο από την άποψη της μεθόδου simplex.
Η λύση σε αυτό το πρόβλημα μπορεί να σχολιαστεί ως εξής. Για να ολοκληρώσετε την εργασία, είναι απαραίτητο να παραχθεί ένα δεύτερο προϊόν σε ποσότητα 6 μονάδων. (x 2 = 6). Μην απελευθερώνετε το πρώτο προϊόν. Παράλληλα, το πρώτο και το δεύτερο γκολ ξεπέρασαν κατά 6 μονάδες. (d 1 + = d 2 + = 6), και το τέταρτο υποεκπληρώνεται από 1 μονάδα. (d 4 - =1). Έτσι, το κέρδος που εισπράχθηκε ήταν 6 μονάδες. περισσότερο από το επιθυμητό επίπεδο, ο πρώτος πόρος χρησιμοποιήθηκε πάνω από το κανονικό όριο κατά 6 μονάδες και τα προϊόντα του 2ου τύπου δεν μπορούσαν να παραχθούν στον επιθυμητό όγκο - αντί για 7 μονάδες. κυκλοφόρησε 6 (ο 2ος πόρος έλειπε, η «εξοικονόμησή» του είναι στόχος υψηλότερης προτεραιότητας).
Εν κατακλείδι, ως παράδειγμα δημιουργίας ενός μοντέλου για μια εργασία CPU, ας δημιουργήσουμε ένα μοντέλο για μια άλλη εργασία.
Παράδειγμα 5.2. Η διοίκηση της πόλης σχεδιάζει να επεκτείνει τις αθλητικές εγκαταστάσεις. Ο προϋπολογισμός της πόλης διέθεσε 5,4 εκατομμύρια ρούβλια για αυτούς τους σκοπούς. Προγραμματίστηκε επιπλέον η κατασκευή τεσσάρων τύπων αθλητικών εγκαταστάσεων: γήπεδα τένις, πισίνες, μικροστάδια (αθλητικά γήπεδα) και γυμναστήρια. Τα στοιχεία για τα έργα αυτά είναι τα ακόλουθα (Πίνακας 5.4).
Πίνακας 5.4 – Πληροφορίες για αντικείμενα υπό κατασκευή
Λύση.Η πόλη έχει διαθέσει 20 εκτάρια ελεύθερου χώρου για αυτούς τους σκοπούς, αλλά εάν χρειαστεί, αυτή η έκταση μπορεί να αυξηθεί. Κατά την υλοποίηση αυτού του έργου, η διοίκηση θέτει τους ακόλουθους στόχους κατά σειρά σπουδαιότητας:
1) πληρούν το προβλεπόμενο ποσό?
2) οι κατασκευασμένες αθλητικές εγκαταστάσεις πρέπει να παρέχουν τουλάχιστον 14.000 επισκέψεις την εβδομάδα.
3) στο μέτρο του δυνατού, να καλύψει την αναμενόμενη ζήτηση για αθλητικές εγκαταστάσεις. Κατά τη δημιουργία της αντικειμενικής συνάρτησης για αυτούς τους αντικειμενικούς περιορισμούς, χρησιμοποιήστε βάρη ανάλογα με την αναμενόμενη χρήση.
4) κατά την υλοποίηση του έργου, εάν είναι δυνατόν, να μην καταλαμβάνουν περισσότερο από τον παραχωρημένο χώρο ελεύθερος χώροςσε 20 εκτάρια.
Κατά τη σύνταξη ενός μοντέλου για αυτήν την εργασία, θα έχουμε κατά νου ότι οι περιορισμοί κατά τη διατύπωση στόχων δεν είναι κατηγορικοί και μπορούν είτε να υπερκαλυφθούν είτε να μην εκπληρωθούν.
Μεταβλητές εργασίες: x 1, x 2, x 3, x 4 - αντίστοιχα, ο αριθμός των κατασκευών που κατασκευάστηκαν: γήπεδα τένις, πισίνες, αθλητικά γήπεδα και γυμναστήρια.
Όλοι οι περιορισμοί θα είναι στοχευμένοι, περιορισμούς συστήματοςΟχι.
Ο πρώτος στόχος είναι να καλυφθεί το ποσό που έχει διατεθεί:
120x 1 + 600x 2 + 480x 3 + 1.200x 4 + d 1 - – d 1 + = 5.400.
Ελαχιστοποιούμε την «υπερβολική δαπάνη»: min Z = P 1 d 1 + .
Ο δεύτερος στόχος είναι τουλάχιστον 14.000 επισκέψεις την εβδομάδα:
500 x 1 + 1.000x 2 + 2.000x 3 + 1.500x 4 + d 2 - – d 2 + = 14.000
Ελαχιστοποιούμε τις «υπό-επισκέψεις». Λαμβάνοντας υπόψη τον πρώτο στόχο έχουμε:
min Z = P 1 d 1 + + P 2 d 2 - .
Η υλοποίηση του τρίτου στόχου θα απαιτήσει την εφαρμογή 4 περιορισμών για κάθε τύπο δομής:
x 1 + d 3 - – d 3 + = 8;
x 2 + d 4 - – d 4 + = 3;
x 3 + d 5 - – d 5 + = 3;
x 4 + d 6 - – d 6 + = 2.
Ελαχιστοποιούμε την «υπο-εκπλήρωση». Αυτός είναι ο τρίτος πιο σημαντικός στόχος, επομένως στη συνάρτηση αντικειμενικού και οι 4 όροι θα έχουν συντελεστή P 3, αλλά με διαφορετικές κλίμακες:
min Z = P 1 d 1 + + P 2 d 2 - + 0,5P 3 d 3 - + P 3 d 4 - + 2P 3 d 5 - + 1,5P 3 d 6 - .
Τέταρτο γκολ: 0,8x 1 + 5x 2 + 3,2x 3 + 1,6x 4 + d 7 - – d 7 + = 20.
Αντικειμενική λειτουργία λαμβάνοντας υπόψη όλους τους στόχους:
min Z = P 1 d 1 + + P 2 d 2 - + 0,5P 3 d 3 - + P 3 d 4 - + 2P 3 d 5 - + 1,5P 3 d 6 - + P 4 d 7 + .
Έτσι, το μοντέλο προβλήματος θα έχει τη μορφή:
Βρείτε min Z = P 1 d 1 + + P 2 d 2 - + 0,5P 3 d 3 - + P 3 d 4 - + 2P 3 d 5 - + 1,5P 3 d 6 - + P 4 d 7 +
υπό την προϋπόθεση ότι
120x 1 + 600x 2 + 480x 3 + 1200x 4 + d 1 - – d 1 + = 5 400,
500x 1 + 1.000x 2 + 2.000x 3 + 1.500x 4 + d 2 - – d 2 + = 14.000,
x 1 + d 3 - – d 3 + = 8,
x 2 + d 4 - – d 4 + = 3,
x 3 + d 5 - – d 5 + = 3,
x 4 + d 6 - – d 6 + = 2,
0,8x 1 + 2x 2 + 3,2x 3 + 1,6x 4 + d 7 - – d 7 + = 20.
x j ³ 0 (j = ) ; d i -, d i + ³ 0 (i = ).
Εάν αυτό το πρόβλημα λυθεί χρησιμοποιώντας τη συνηθισμένη μέθοδο simplex, τότε στα βάρη P i πρέπει να δοθούν συγκεκριμένες τιμές, αλλά λάβετε υπόψη ότι P 1 >> P 2 >>...>> P 7 . Αναπτηγμένος ειδικά προγράμματαγια την επίλυση τέτοιων προβλημάτων. Εφαρμόζοντας ένα από αυτά (το πρόγραμμα QM for Window), λαμβάνουμε την ακόλουθη βέλτιστη λύση (Πίνακας 5.5):
Πίνακας 5.5 – Λύση του προβλήματος από το παράδειγμα 5.2.
(Προγραμματισμός στόχος)
x 1 = 8, x 2 = 3, x 3 = 3, x 4 = 1, d 2 + = 500, d 6 - = 1, d 7 + = 3,6. (d 7 + = –653.994 είναι ο κωδικοποιημένος αριθμός 3.6 - υποδεικνύεται στη γραμμή Προτεραιότητας 4). Η υποδεικνυόμενη υποεκπλήρωση (Μη επίτευξη) στη γραμμή Προτεραιότητας 3, ίση με 1,5, λαμβάνει υπόψη τον συντελεστή στάθμισης στη συνάρτηση στόχου στο ).
Έτσι, με τα κονδύλια που διατέθηκαν είναι δυνατή η κατασκευή 8 γηπέδων τένις, 3 πισίνες, 3 μίνι στάδια και ένα γυμναστήριο. Όπως βλέπουμε, ο τέταρτος στόχος υποεκπληρώνεται από 1 (d = 1), δηλ. αντί των δύο που έχουν προγραμματιστεί, θα κατασκευαστεί ένα γυμνάσιο. Υπέρβαση του δεύτερου στόχου (d 2 + = 500), δηλ. αντί για 14.000 επισκέψεις, είναι πιθανές 14.500 Ο 4ος στόχος ήταν επίσης υπέρβαση (d 7 + = 3,6), δηλ. αντί των 20 εκταρίων που έχουν διατεθεί για τις αθλητικές αυτές εγκαταστάσεις, θα απαιτηθούν 23,6 στρέμματα.
Κεφάλαιο 6. Μέθοδοι προγραμματισμός δικτύουκαι διαχείριση
Οι μέθοδοι σχεδιασμού δικτύου καθιστούν δυνατή την ανάλυση ενός συνόλου εργασιών, το οποίο περιλαμβάνει μεγάλος αριθμόςαλληλένδετες λειτουργίες. Μπορείτε να προσδιορίσετε την πιθανή διάρκεια όλων των εργασιών, το κόστος τους, την πιθανή εξοικονόμηση χρόνου ή Χρήματα, καθώς και ποιες εργασίες δεν μπορούν να καθυστερήσουν χωρίς να καθυστερήσει το έργο στο σύνολό του. Το πρόβλημα της παροχής πόρων είναι επίσης σημαντικό. Μέθοδοι ανάλυση δικτύουμπορεί να χρησιμοποιηθεί κατά τη μεταγλώττιση ημερολογιακό σχέδιοεκτέλεση εργασιών που ικανοποιούν υφιστάμενους περιορισμούςγια την παροχή πόρων.
Η ανάλυση κάθε έργου πραγματοποιείται σε τρία στάδια:
1. Διαίρεση του έργου σε έναν αριθμό ξεχωριστών εργασιών (ή πράξεων), από τις οποίες στη συνέχεια συντάσσεται ένα λογικό διάγραμμα.
2. Εκτίμηση της διάρκειας κάθε λειτουργίας. την κατάρτιση χρονοδιαγράμματος έργου και την ανάδειξη των εργασιών που καθορίζουν την ολοκλήρωση του έργου στο σύνολό του.
3. Αξιολόγηση των απαιτήσεων πόρων για κάθε λειτουργία. αναθεώρηση του επιχειρησιακού σχεδίου λαμβάνοντας υπόψη την παροχή πόρων ή
ανακατανομή χρημάτων ή άλλων πόρων που θα βελτιώσουν το σχέδιο.
Μόλις η λίστα έχει καταρτιστεί, η λογική ακολουθία των πράξεων μπορεί να απεικονιστεί χρησιμοποιώντας ένα γράφημα. Υπάρχει Διάφοροι τύποιγραφήματα, αλλά τα πιο ευρέως χρησιμοποιούμενα είναι τα λεγόμενα γραφήματα κορυφής και βέλους.
Στείλτε την καλή δουλειά σας στη βάση γνώσεων είναι απλή. Χρησιμοποιήστε την παρακάτω φόρμα
Φοιτητές, μεταπτυχιακοί φοιτητές, νέοι επιστήμονες που χρησιμοποιούν τη βάση γνώσεων στις σπουδές και την εργασία τους θα σας είναι πολύ ευγνώμονες.
Παρόμοια έγγραφα
Γεωμετρική λύση τυπικές εργασίεςγραμμικός προγραμματισμός με δύο μεταβλητές. Καθολική μέθοδοςλύσεις κανονικό πρόβλημα. Η κύρια ιδέα της μεθόδου simplex, υλοποίηση χρησιμοποιώντας ένα παράδειγμα. Πινακοποιημένη υλοποίηση μιας απλής μεθόδου simplex.
περίληψη, προστέθηκε 15/06/2010
Είδη προβλημάτων γραμμικού προγραμματισμού και διατύπωση προβλημάτων. Η ουσία της βελτιστοποίησης ως κλάδος των μαθηματικών και τα χαρακτηριστικά των κύριων μεθόδων επίλυσης προβλημάτων. Η έννοια της μεθόδου simplex, πραγματικά εφαρμοσμένα προβλήματα. Αλγόριθμος και στάδια επίλυσης του προβλήματος μεταφοράς.
εργασία μαθημάτων, προστέθηκε 17/02/2010
Επίλυση προβλημάτων γραμμικού προγραμματισμού με χρήση γραφικών και απλών μεθόδων. Λύση του προβλήματος διπλή από την αρχική. Ορισμός βέλτιστο σχέδιοανάθεση καταναλωτών σε προμηθευτές ομοιογενούς φορτίου, με την επιφύλαξη ελαχιστοποίησης της συνολικής χιλιομετρικής απόστασης των οχημάτων.
δοκιμή, προστέθηκε 15/08/2012
Χρησιμοποιώντας τη μέθοδο simplex για την επίλυση προβλημάτων γραμμικού προγραμματισμού για τον υπολογισμό του ημερήσιου όγκου παραγωγής. Έλεγχος του σχεδίου για βελτιστοποίηση. Επανυπολογισμός πίνακας simplexΜέθοδος Jordan-Gauss. Κατάρτιση μοντέλου μεταφορικού προβλήματος.
δοκιμή, προστέθηκε 18/02/2014
Οικονομικό και μαθηματικό μοντέλο απόκτησης μέγιστου κέρδους, η λύση του γραφική μέθοδος. Αλγόριθμος επίλυσης προβλήματος γραμμικού προγραμματισμού με τη μέθοδο του simplex. Συλλογή διπλά προβλήματακαι και αυτή γραφική λύση. Λύση πίνακα πληρωμών.
δοκιμή, προστέθηκε 05/11/2014
Βασικά μαθηματική μοντελοποίηση οικονομικές διαδικασίες. γενικά χαρακτηριστικάγραφικές και απλές μέθοδοι για την επίλυση προβλημάτων άμεσου και διπλού γραμμικού προγραμματισμού. Χαρακτηριστικά της διατύπωσης και της μεθοδολογίας για την επίλυση του προβλήματος των μεταφορών.
εργασία μαθήματος, προστέθηκε 11/12/2010
Συλλογή μαθηματικό μοντέλοκαθήκοντα. Υπολογισμός του βέλτιστου σχεδίου μεταφοράς με το ελάχιστο κόστος με τη μέθοδο του δυναμικού. Η καλύτερη επιλογήειδικό κινητό εξοπλισμό για τεχνική υποστήριξηΔΙΟΙΚΗΣΗ ΠΑΡΑΓΩΓΗΣ.
δοκιμή, προστέθηκε 06/01/2014
