Τροποποιημένη μέθοδος 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και αριθμός Nr(β ( q)) για μια στήλη που προέρχεται από τη βάση. Ας προχωρήσουμε στο σημείο 3° του αλγορίθμου.
3°. Επανυπολογισμός σε σχέση με τη νέα βάση στοιχείων της στήλης βΚαι μήτρεςΔ -1. Μετάβαση σε νέα βάση β ( q+1) , το οποίο προκύπτει εισάγοντας το β ( q) στήλη α λκαι βγάζοντας μια στήλη από αυτό a r, πραγματοποιείται σύμφωνα με τύπους παρόμοιους με τους τύπους (1.28)-(1.31). Μοιάζουν σαν:
Ορίζουμε τον αριθμό της τρέχουσας επανάληψης q: =q+l και πηγαίνουμε στο πρώτο σημείο του αλγορίθμου.
Συμπερασματικά, τονίζουμε ότι λόγω των παραπάνω πλεονεκτημάτων, είναι η τροποποιημένη μέθοδος simplex που χρησιμοποιείται στην πραγματικότητα σε λογισμικό σχεδιασμένο για την επίλυση προβλημάτων κανονικού γραμμικού προγραμματισμού.
1.5.2. Ένα παράδειγμα επίλυσης ενός ZLP χρησιμοποιώντας μια τροποποιημένη μέθοδο 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.
ΤΡΟΠΟΠΟΙΗΜΕΝΗ ΜΕΘΟΔΟΣ SIMPLEX Η μέθοδος simplex δεν είναι η πιο αποτελεσματική
διαδικασία υπολογιστή, αφού υπολογίζει και
αποθηκεύει πληροφορίες που δεν χρειάζονται για το ρεύμα
επανάληψη και μπορεί να μην χρησιμοποιηθεί καθόλου για
λήψη αποφάσεων κατά τις επόμενες επαναλήψεις. Για
συντελεστές μη κύριων μεταβλητών στην εξίσωση
(0), συντελεστές των εισαγόμενων κύριων μεταβλητών
σε άλλες εξισώσεις και στις δεξιές πλευρές των εξισώσεων στο
Κάθε επανάληψη χρησιμοποιεί μόνο τη σχετική
πληροφορίες. Επομένως, χρειάζεται μια διαδικασία που
μπορούν να αποκτήσουν αυτές τις πληροφορίες αποτελεσματικά, χωρίς
υπολογισμούς και αποθήκευση όλων των άλλων συντελεστών
(αυτή είναι η τροποποιημένη μέθοδος simplex).
είναι απαραίτητα αυτή τη στιγμή και σημαντικά δεδομένα
μεταφέρει σε πιο συμπαγή μορφή.
Χρησιμοποιεί πράξεις μήτρας, άρα
είναι απαραίτητο να περιγραφεί το πρόβλημα χρησιμοποιώντας πίνακες.
ΚΕΦΑΛΑΙΑ γράμματα με έντονους χαρακτήρες
αντιπροσωπεύουν πίνακες, κεφαλαία γράμματα,
αυτά με έντονους χαρακτήρες αντιπροσωπεύουν
φορείς.
Τα πλάγια γράμματα είναι βαθμωτές ποσότητες, με επισήμανση μηδέν
Το (0) δηλώνει το μηδενικό διάνυσμα (τα στοιχεία του είναι ίσα
μηδέν, τόσο σειρές όσο και στήλες), μηδέν (0)
αντιπροσωπεύει τον κανονικό αριθμό 0. Χρησιμοποιώντας
πίνακες τυπική μορφή γραμμικού μοντέλου
ο προγραμματισμός έχει τη μορφή: Μεγιστοποίηση Z = c x,
σύμφωνα με
A x ≤ b και x ≥ 0,
όπου c είναι διάνυσμα γραμμής
x, b και 0 διανύσματα στηλών Α - μήτρα
Για επαυξημένη μορφή, διάνυσμα στήλης
εικονικές μεταβλητές:
Περιορισμοί:
I = (m × m πίνακας ταυτότητας)
0 = (n + m στοιχεία του μηδενικού διανύσματος) Εύρεση βασικής εφικτής λύσης
Η γενική προσέγγιση της μεθόδου simplex είναι η απόκτηση
ακολουθία βελτίωσης λύσεων ΟΑ έως
μέχρι να βρεθεί η βέλτιστη
λύση. Ένα από τα βασικά χαρακτηριστικά
Τροποποιημένη μέθοδος Simplex - πώς
βρίσκει μια νέα λύση OD αφού την ορίσει
κύρια (βασική) και μη βασική (μη βασική)
μεταβλητές. Δεδομένων αυτών των μεταβλητών, το προκύπτον
κύρια λύση – λύση m εξισώσεων
Στην οποία n μη βασικές μεταβλητές από n + m
στοιχεία
τίθενται ίσα με το μηδέν. Καταργώντας αυτές τις n μεταβλητές μηδενίζοντας τις,
παίρνουμε ένα σύστημα εξισώσεων m με m μεταβλητές
(κύριες (βασικές) μεταβλητές):
πού είναι το διάνυσμα των βασικών μεταβλητών:
που λαμβάνεται εξαιρώντας τα μη βασικά (μη βασικά)
μεταβλητές: Και ο βασικός πίνακας
Το αποτέλεσμα που προκύπτει εξαιρώντας τις στήλες που αντιστοιχούν σε
συντελεστές μη βασικών μεταβλητών από .
(Επιπλέον, τα στοιχεία xB και οι στήλες Β είναι σε διαφορετικές
εντάξει). Η μέθοδος simplex εισάγει μόνο βασικά
μεταβλητές τέτοιες ώστε το Β να είναι μη εκφυλισμένο, άρα
ο αντίστροφος πίνακας Β-1 θα υπάρχει πάντα.
Για να λύσουμε B x B = b, και οι δύο πλευρές πολλαπλασιάζονται με B-1:
Β-1 Β x Β = Β-1 β. Το cB είναι ένα διάνυσμα του οποίου τα στοιχεία είναι συντελεστές
αντικειμενικές συναρτήσεις (συμπεριλαμβανομένων των μηδενικών για το εικονικό
μεταβλητές) για τα αντίστοιχα xB στοιχεία.
Η αντικειμενική συνάρτηση για αυτή τη βασική λύση είναι: Παράδειγμα:
- Επανάληψη 0
Έτσι
Έτσι
10.
- Επανάληψη 1Έτσι
Έτσι
11.
- Επανάληψη 2Έτσι
Έτσι
12. Μορφή μήτρας για το τρέχον σύνολο εξισώσεων
Μορφή μήτρας για ένα σύνολο εξισώσεων,εμφανίζεται στον πίνακα simplex για οποιαδήποτε επανάληψη
την αρχική μέθοδο simplex. Για το σύστημα πηγής
εξισώσεις, η μορφή του πίνακα είναι:
Αλγεβρικές πράξεις που εκτελούνται με τη μέθοδο του simplex (πολλαπλασιάστε την εξίσωση με μια σταθερά και προσθέστε
γινόμενο μιας εξίσωσης από μια άλλη) εκφράζονται σε
μορφή μήτρας, αφού πολλαπλασιαστούν και τα δύο μέρη
το αρχικό σύστημα εξισώσεων στο αντίστοιχο
μήτρες
13.
14.
Αυτός ο πίνακας θα έχει τα ίδια στοιχεία με τον πίνακα ταυτότηταςμήτρα, εκτός από το ότι κάθε προϊόν
για μια ορισμένη αλγεβρική πράξη θα χρειαστεί
ο χώρος που απαιτείται για την εκτέλεση αυτής της λειτουργίας,
χρησιμοποιώντας πολλαπλασιασμό πίνακα. Ακόμα και μετά το επεισόδιο
αλγεβρικές πράξεις σε πολλές επαναλήψεις,
μπορούμε ακόμα να συμπεράνουμε ότι αυτός ο πίνακας
θα πρέπει να είναι για όλη τη σειρά, χρησιμοποιώντας αυτά που γνωρίζουμε
η δεξιά πλευρά του νέου συστήματος εξισώσεων. Μετά από οποιαδήποτε
επαναλήψεις, xB = B-1b και Z = cB B-1b, άρα οι δεξιές πλευρές
το νέο σύστημα εξισώσεων πήρε τη μορφή
15.
Αφού κάνουμε την ίδια σειράαλγεβρικές πράξεις και με τις δύο πλευρές
αρχικό σύνολο, για να πολλαπλασιάσετε το δικαίωμα και
στην αριστερή πλευρά, χρησιμοποιούμε την ίδια μήτρα.
Ως εκ τούτου,
Επιθυμητή μορφή μήτρας του συστήματος εξισώσεων
μετά από οποιαδήποτε επανάληψη:
16.
Παράδειγμα: μορφή μήτρας που λήφθηκε μετά την επανάληψη 2για το πρόβλημα του εργοστασίου γυαλιού χρησιμοποιώντας B-1 και cB:
17.
Χρησιμοποιώντας τις ποσότητες xB = B-1 b και Z = cB B-1 b:18.
Μόνο το B-1 πρέπει να ληφθεί για υπολογισμόόλους τους αριθμούς του πίνακα simplex από τον αρχικό
παραμέτρους εργασίας (A, b, cB). Οποιοσδήποτε από αυτούς τους αριθμούς
μπορεί να ληφθεί μεμονωμένα ως
Κατά κανόνα, εκτελείται μόνο πολλαπλασιασμός διανυσμάτων
(μία σειρά ανά στήλη) αντί για πλήρη
πολλαπλασιασμός μήτρας. Απαιτούμενοι αριθμοί για
η εκτέλεση επαναλήψεων της μεθόδου simplex μπορεί να είναι
λάβετε όσο χρειάζεται χωρίς να ξοδέψετε
περιττοί υπολογισμοί για να λάβετε όλους τους αριθμούς.
19. Σύντομη επισκόπηση της τροποποιημένης μεθόδου simplex
1. Αρχικοποίηση: Όπως στην αρχική μέθοδο simplex.2. Επανάληψη: Βήμα 1 Προσδιορίστε το εισαγόμενο βασικό (κύριο)
μεταβλητές: Όπως στην αρχική μέθοδο simplex.
Βήμα 2 Προσδιορίστε τις εξερχόμενες μεταβλητές βάσης: Όπως στο πρωτότυπο
μέθοδο simplex, με εξαίρεση την καταμέτρηση μόνο εκείνων που είναι απαραίτητα για
από αυτούς τους αριθμούς [συντελεστές των εισαγόμενων βασικών μεταβλητών σε
κάθε εξίσωση εκτός από την Εξ. (0), και στη συνέχεια, για κάθε αυστηρά
θετικός συντελεστής, η δεξιά πλευρά αυτής της εξίσωσης].
Βήμα 3 Προσδιορίστε μια νέα λύση OD: Λάβετε B-1 και ορίστε xB=B-1b.
3. Ανάλυση βελτιστοποίησης: Όπως στην αρχική μέθοδο simplex, για
εκτός από την καταμέτρηση μόνο των αριθμών που απαιτούνται για αυτήν την ανάλυση,
δηλ. συντελεστές μη βασικών (μη βασικών) μεταβλητών σε
Εξίσωση (0).
Στο βήμα 3 της επανάληψης, το B-1 μπορεί να ληφθεί κάθε φορά χρησιμοποιώντας
τυπικό πρόγραμμα υπολογιστή για αντιστροφή (αναστροφή)
μήτρες. Δεδομένου ότι το B (τότε B-1) αλλάζει ελάχιστα από μία επανάληψη σε
άλλο, είναι πιο αποτελεσματικό να αποκτήσετε ένα νέο B-1 (σημαίνει B-1 νέο) από
Β-1 στην προηγούμενη επανάληψη (Β-1 παλιά). (Για την αρχική λύση ΟΑ).
Η βασική ιδέα της τροποποιημένης μεθόδου simplex είναι να χρησιμοποιήσει τον τρέχοντα αντίστροφο πίνακα (και τα αρχικά δεδομένα του προβλήματος) για να εκτελέσει τους απαραίτητους υπολογισμούς για τον προσδιορισμό των μεταβλητών που θα συμπεριληφθούν και θα εξαιρεθούν. Η αναπαράσταση ενός αντίστροφου πίνακα σε πολλαπλασιαστική μορφή σάς επιτρέπει να υπολογίσετε μια ακολουθία αντίστροφων πινάκων απευθείας από τα δεδομένα προέλευσης χωρίς να χρησιμοποιείτε πολλαπλές πράξεις αντιστροφής για κάθε βάση. Όπως και στη συνηθισμένη μέθοδο simplex, στην περίπτωση αυτή η αρχική βάση είναι πάντα ο πίνακας ταυτότητας I, το αντίστροφο του οποίου είναι αυτός ο ίδιος ο πίνακας. Επομένως, εάν 
- ακολουθία αντίστροφων πινάκων που αντιστοιχούν στις επαναλήψεις 1, 2,…,i, και 
είναι η ακολουθία των πινάκων που αντιστοιχούν σε αυτούς, λοιπόν
Η ακολουθία των αντικαταστάσεων οδηγεί στον ακόλουθο τύπο:
(2.23)
Θα πρέπει να τονιστεί ότι η πολλαπλασιαστική αναπαράσταση του αντίστροφου πίνακα δεν είναι απαραίτητη διαδικασία για την εφαρμογή του υπολογιστικού σχήματος της τροποποιημένης μεθόδου simplex και σε κάθε επανάληψη μπορεί να χρησιμοποιηθεί οποιαδήποτε από τις μεθόδους για την αντιστροφή της τρέχουσας βάσης. Όταν χρησιμοποιείται η τροποποιημένη μέθοδος Simplex, είναι σημαντικό οι αντίστροφοι πίνακες να υπολογίζονται με τρόπο που να μειώνει τον αντίκτυπο των σφαλμάτων στρογγυλοποίησης της μηχανής.
Τα βήματα του αλγορίθμου της τροποποιημένης μεθόδου simplex είναι ουσιαστικά τα ίδια με αυτά του συμβατικού αλγορίθμου μεθόδου simplex. Αφού βρεθεί η αρχική βάση I, προσδιορίζεται το αντίστοιχο διάνυσμα συντελεστών της αντικειμενικής συνάρτησης 
, τα στοιχεία του οποίου σχηματίζονται ανάλογα με το αν οι αρχικές βασικές μεταβλητές είναι υπολειμματικές (πλεοναστικές) ή τεχνητές.
2.7.2. Πολλαπλασιαστική αναπαράσταση αντίστροφου πίνακα
Στην πολλαπλασιαστική αναπαράσταση της αντίστροφης μήτρας, χρησιμοποιείται μια πράξη άλγεβρας μήτρας για τον υπολογισμό των στοιχείων της αντίστροφης μήτρας προς τη νέα μήτρα διανυσμάτων βάσης από τον γνωστό αντίστροφο πίνακα της προηγούμενης βάσης, με την προϋπόθεση ότι οι δύο υπό εξέταση βάσεις διαφέρουν μόνο σε διάνυσμα μιας στήλης. Αυτή η μέθοδος αναπαράστασης του αντίστροφου πίνακα είναι βολική για χρήση στο υπολογιστικό σχήμα της μεθόδου simplex, καθώς οι βάσεις που αντιστοιχούν σε κάθε δύο διαδοχικές επαναλήψεις διαφέρουν μόνο σε μία στήλη (ως αποτέλεσμα της αντικατάστασης του διανύσματος στήλης που έχει εξαλειφθεί στην τρέχουσα βάση με νέο διάνυσμα στήλης). Με άλλα λόγια, ο τρέχων πίνακας βάσης 
και έναν νέο πίνακα βάσης 
, που αντιστοιχεί στην επόμενη επανάληψη, διαφέρουν μόνο σε μία στήλη. Με την πολλαπλασιαστική παράσταση του αντίστροφου πίνακα 
που αντιστοιχεί στη νέα βάση, υπολογίζεται πολλαπλασιάζοντας στα αριστερά το αντίστροφο του τρέχοντος πίνακα 
σε μια μήτρα που σχηματίζεται σύμφωνα με ορισμένους κανόνες 
.
Ας ορίσουμε τη μήτρα ταυτότητας 
με τον εξής τρόπο:
(2.24)
Οπου 
- ένα διάνυσμα στήλης μονάδας με το i-ο στοιχείο ίσο με ένα και τα υπόλοιπα στοιχεία ίσο με μηδέν. Ας υποθέσουμε ότι οι πίνακες είναι γνωστοί 
Και 
και διάνυσμα 
μήτρες 
αντικαθίσταται από ένα νέο διάνυσμα 
; όπως συνηθίζεται όταν περιγράφεται η μέθοδος simplex, το διάνυσμα 
ορίζεται ως περιλαμβάνεται στη βάση, και το διάνυσμα 
- όπως εξαιρείται από τη βάση. Για να απλοποιήσουμε τη σύνταξη μαθηματικών σχέσεων, χρησιμοποιούμε τον ακόλουθο ορισμό 
,εν 
θα αντιπροσωπεύει το kth στοιχείο 
. Στη συνέχεια, ο νέος αντίστροφος πίνακας 
μπορεί να υπολογιστεί χρησιμοποιώντας τον ακόλουθο τύπο:
(2.25)
υπό την προϋπόθεση ότι 
. Αν 
, πίνακες 
δεν υπάρχει. Σημειώστε ότι η μήτρα 
που λαμβάνονται από τη μήτρα 
αντικαθιστώντας το διάνυσμα της r-ης στήλης 
στήλη 
.
Ας εξετάσουμε μια μέθοδο για την επίλυση του προβλήματος της 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. Αξιολόγηση των απαιτήσεων πόρων για κάθε λειτουργία. αναθεώρηση του επιχειρησιακού σχεδίου λαμβάνοντας υπόψη την παροχή πόρων ή
ανακατανομή χρημάτων ή άλλων πόρων που θα βελτιώσουν το σχέδιο.
Μόλις η λίστα έχει καταρτιστεί, η λογική ακολουθία των πράξεων μπορεί να απεικονιστεί χρησιμοποιώντας ένα γράφημα. Υπάρχουν διάφοροι τύποι γραφημάτων, αλλά τα πιο ευρέως χρησιμοποιούμενα είναι τα λεγόμενα γραφήματα κορυφής και βέλους.
Λαμβάνοντας υπόψη τις δυνατότητες των σύγχρονων PPP που χρησιμοποιούν μια τροποποιημένη μέθοδο simplex με πολλαπλασιαστική αναπαράσταση του πίνακα, η αντιστοίχιση του επόμενου διανύσματος στην κατηγορία των διανυσμάτων που εξασφαλίζουν συμβατότητα ή ασυμβατότητα απαιτεί μόνο μερικές επαναλήψεις μετά την τροποποίηση του γενικευμένου πίνακα
ΤΡΟΠΟΠΟΙΗΜΕΝΗ ΜΕΘΟΔΟΣ SIMPLEX
Ένα υπολογιστικό σχήμα που βασίζεται στον μετασχηματισμό των αντίστροφων πινάκων. Αναλύοντας την υπολογιστική διαδικασία της μεθόδου simplex από την άποψη της εκτίμησης της έντασης εργασίας, είναι εύκολο να παρατηρήσουμε ότι η πιο κρίσιμη από αυτή την άποψη είναι η διαδικασία επανυπολογισμού των τιμών των A και b κατά τη μετάβαση από το ένα βασικό σχέδιο στο άλλο ( ρήτρα 3 του αλγορίθμου). Ωστόσο, στην περίπτωση που ο αριθμός των περιορισμών του προβλήματος m είναι σαφώς μικρότερος από τον αριθμό των μεταβλητών i, είναι δυνατό να επιτευχθεί σημαντική εξοικονόμηση πόρων εκτελώντας στην επόμενη επανάληψη q τον μετασχηματισμό Jordan-Gauss όχι στον πίνακα A(p () από τον D Chr(αρχική στήλη aChr O. Αυτές οι σκέψεις βασίζονται στη βάση του υπολογιστικού σχήματος της μεθόδου simplex, που βασίζεται στον μετασχηματισμό των αντίστροφων πινάκων, που ονομάζεται επίσης μέθοδος τροποποιημένου απλού. Αυτός ο αλγόριθμος προτάθηκε για πρώτη φορά το 1951 στο έργα του L. V. Kantorovich.
Το υπολογιστικό σχήμα της τροποποιημένης μεθόδου simplex αντιστοιχεί στο σύστημα των πινάκων 7] και T q). Ο Πίνακας 7J (Εικ. 1.7) είναι κοινός σε όλες τις επαναλήψεις και χρησιμεύει για τη λήψη
Κατ' αναλογία με την παράγραφο 1.4.1, θα περιγράψουμε το επίσημο σχήμα του αλγορίθμου της τροποποιημένης μεθόδου simplex.
Συμπερασματικά, τονίζουμε ότι λόγω των παραπάνω πλεονεκτημάτων, είναι η τροποποιημένη μέθοδος simplex που στην πραγματικότητα χρησιμοποιείται σε λογισμικό σχεδιασμένο για την επίλυση προβλημάτων κανονικού γραμμικού προγραμματισμού.
Ένα παράδειγμα επίλυσης ενός ZLP χρησιμοποιώντας μια τροποποιημένη μέθοδο simplex. Ας παρουσιάσουμε μια λύση στο πρόβλημα που εξετάστηκε προηγουμένως (1.34)-(1.35), με βάση τη χρήση της διαδικασίας της τροποποιημένης μεθόδου simplex. Κατ' αναλογία με την ρήτρα 1.4.3
Ας επιστρέψουμε για άλλη μια φορά στον πίνακα T (Εικ. 1.8), που προέκυψε στην τελική επανάληψη της διαδικασίας της τροποποιημένης μεθόδου simplex. Ας εξετάσουμε λεπτομερέστερα τη μηδενική σειρά του πίνακα A 4p(
Έτσι, ένα σημαντικό πλεονέκτημα της τροποποιημένης μεθόδου simplex είναι ότι επιτρέπει σε κάποιον να βρει ταυτόχρονα βέλτιστα σχέδια τόσο για τα άμεσα όσο και για τα διπλά προβλήματα.
Συμπερασματικά, σημειώνουμε ότι σε αυτή την ενότητα εξετάσαμε μια παραλλαγή του διπλού αλγορίθμου που αντιστοιχεί στην τυπική μέθοδο simplex. Δεν είναι δύσκολο να μαντέψει κανείς ότι υπάρχει επίσης μια επιλογή που βασίζεται σε ένα τροποποιημένο simplex (ένα σχήμα που σχετίζεται με τον μετασχηματισμό των αντίστροφων πινάκων), αλλά επειδή αυτό το θέμα ενδιαφέρει κυρίως από την άποψη της τεχνολογίας οργάνωσης υπολογισμούς, δεν θα σταθούμε σε αυτό. Εάν θέλετε, μπορείτε να βρείτε μια βαθιά και λεπτομερή περιγραφή αυτής της έκδοσης του αλγορίθμου. Σημειώνουμε μόνο ότι έχει τα ίδια θεμελιώδη πλεονεκτήματα με την τροποποιημένη μέθοδο simplex.
Η τροποποιημένη μέθοδος Simplex είναι ένα υπολογιστικό σχήμα που σχετίζεται με τον μετασχηματισμό των αντίστροφων πινάκων.
Διατυπώστε τις κύριες διαφορές μεταξύ της τροποποιημένης μεθόδου simplex και της τυπικής μεθόδου.
Να αναφέρετε τα πλεονεκτήματα της τροποποιημένης μεθόδου simplex.
Θα διαφέρει ο αριθμός των επαναλήψεων κατά την επίλυση του ίδιου προβλήματος κατά την επίλυσή του χρησιμοποιώντας την τυπική και τροποποιημένη μέθοδο simplex;
Η μέθοδος αποσύνθεσης αναπτύχθηκε για την επίλυση προβλημάτων γραμμικού προγραμματισμού υψηλών διαστάσεων με δομή μπλοκ. Η υπολογιστική του διαδικασία βασίζεται κυρίως στις ιδέες της τροποποιημένης μεθόδου simplex. Ωστόσο, η σημασία της μεθόδου Dantzig-Wolfe δεν έγκειται μόνο και (όχι τόσο) στα υπολογιστικά της πλεονεκτήματα, αλλά στην ικανότητα να δίνει μια ουσιαστική οικονομική ερμηνεία. Η μέθοδος περιλαμβάνει την αποσύνθεση του αρχικού προβλήματος (5.6)-(5.9) σε τοπικές εργασίες που αντιστοιχούν σε ξεχωριστά μέρη της ένωσης (στην περίπτωση αυτή, επιχειρήσεις) και στην κύρια εργασία (που αντιστοιχεί στο σύνολο του συσχετισμού και συνδέει αυτές τις τοπικές εργασίες) .
R. B. Dubina, K. E. Chernin. Πρόγραμμα εκπαίδευσης και καταγραφής σε πίνακες M.B για την τροποποιημένη μέθοδο Simplex - Συλλογή προγραμμάτων υπολογιστή Ural. L., Arkt. και την Ανταρκτική. Ινστιτούτο, 1966.
Μεταξύ των μεθόδων για την εύρεση της βέλτιστης λύσης, η πιο ευρέως χρησιμοποιούμενη μέθοδος είναι η μέθοδος ακολουθίας. βελτίωση μιας αποδεκτής λύσης (MAS), η οποία έχει μεγάλο αριθμό υπολογιστικών υλοποιήσεων (
