Ένα παράδειγμα επίλυσης ενός προβλήματος. Μέθοδος Simplex για την επίλυση LLP. Παράδειγμα επίλυσης άμεσου και διπλού προβλήματος χρησιμοποιώντας τη μέθοδο simplex
Κλωστή, κουμπιά και ύφασμα χρησιμοποιούνται για την κατασκευή τριών τύπων πουκάμισων. Τα αποθέματα νήματος, κουμπιών και υφάσματος, οι κανόνες κατανάλωσής τους για το ράψιμο ενός πουκάμισου αναφέρονται στον πίνακα. Βρείτε το μέγιστο κέρδος και το βέλτιστο πλάνο παραγωγής προϊόντος που το εξασφαλίζει (βρείτε).
| πουκάμισο 1 | πουκάμισο 2 | πουκάμισο 3 | Αποθεματικά | κλωστές (μ.) | 1 | 9 | 3 | 96 | κουμπιά (τεμ.) | 20 | 10 | 30 | 640 | υφάσματα ( | 1 | 2 | 2 | 44 | Κέρδος (r.) | 2 | 5 | 4 |
Η λύση του προβλήματος
Πρότυπο κτίριο
Μέσω και τον αριθμό των πουκάμισων του 1ου, 2ου και 3ου τύπου που προορίζονται για κυκλοφορία.
Τότε οι περιορισμοί πόρων θα μοιάζουν με αυτό:
Επιπλέον, σύμφωνα με το νόημα της εργασίας
Αντικειμενική συνάρτηση που εκφράζει το ληφθέν κέρδος:
Παίρνουμε το ακόλουθο πρόβλημα γραμμικού προγραμματισμού:
Αναγωγή ενός προβλήματος γραμμικού προγραμματισμού σε κανονική μορφή
Ας περιορίσουμε το πρόβλημα σε κανονική μορφή. Ας εισάγουμε πρόσθετες μεταβλητές. Εισάγουμε όλες τις πρόσθετες μεταβλητές στην αντικειμενική συνάρτηση με συντελεστή ίσο με μηδέν. Προσθέτουμε επιπλέον μεταβλητές στα αριστερά των περιορισμών που δεν έχουν προτιμώμενη μορφή και λαμβάνουμε ισότητες.
Επίλυση του προβλήματος με τη μέθοδο simplex
Συμπληρώστε τον πίνακα simplex:
Δεδομένου ότι λύνουμε το πρόβλημα στο μέγιστο, η παρουσία αρνητικών αριθμών στη γραμμή δείκτη κατά την επίλυση του προβλήματος στο μέγιστο υποδηλώνει ότι δεν έχουμε λάβει τη βέλτιστη λύση και ότι είναι απαραίτητο να προχωρήσουμε από τον πίνακα της 0ης επανάληψης στον επόμενο.
Προχωράμε στην επόμενη επανάληψη ως εξής:
αντιστοιχεί η πρώτη στήλη
Η βασική γραμμή καθορίζεται από την ελάχιστη αναλογία ελεύθερων όρων και μελών της κύριας στήλης (απλές σχέσεις):
Στη διασταύρωση της στήλης κλειδιού και της γραμμής κλειδιού βρίσκουμε το στοιχείο ενεργοποίησης, δηλ. 9.
Τώρα προχωράμε στη σύνταξη της 1ης επανάληψης: Αντί για μοναδιαίο διάνυσμα, εισάγουμε το διάνυσμα .
Στον νέο πίνακα, στη θέση του στοιχείου ενεργοποίησης γράφουμε 1, όλα τα άλλα στοιχεία της στήλης κλειδιού είναι μηδενικά. Τα βασικά στοιχεία συμβολοσειράς χωρίζονται στο στοιχείο ενεργοποίησης. Όλα τα άλλα στοιχεία του πίνακα υπολογίζονται χρησιμοποιώντας τον κανόνα του ορθογωνίου.
Η στήλη κλειδιού για την 1η επανάληψη αντιστοιχεί σε
Το στοιχείο επίλυσης είναι ο αριθμός 4/3. Εξάγουμε το διάνυσμα από τη βάση και εισάγουμε το διάνυσμα. Παίρνουμε τον πίνακα της 2ης επανάληψης.
Η στήλη κλειδιού για τη 2η επανάληψη αντιστοιχεί σε
Βρίσκουμε τη γραμμή κλειδί, για αυτό ορίζουμε:
Το στοιχείο επίλυσης είναι ο αριθμός 10/3. Εξάγουμε το διάνυσμα από τη βάση και εισάγουμε το διάνυσμα. Παίρνουμε τον πίνακα της 3ης επανάληψης.
| № | BP | γ Β | Α ο | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | Simplex | 2 | 5 | 4 | 0 | 0 | 0 | σχέση | 0 | x 4 | 0 | 96 | 1 | 9 | 3 | 1 | 0 | 0 | 32/3 | x 5 | 0 | 640 | 20 | 10 | 30 | 0 | 1 | 0 | 64 | x 6 | 0 | 44 | 1 | 2 | 2 | 0 | 0 | 1 | 22 | F j - c j | 0 | -2 | -5 | -4 | 0 | 0 | 0 | 1 | x 2 | 5 | 32/3 | 1/9 | 1 | 1/3 | 1/9 | 0 | 0 | 32 | x 5 | 0 | 1600/3 | 170/9 | 0 | 80/3 | -10/9 | 1 | 0 | 20 | x 6 | 0 | 68/3 | 7/9 | 0 | 4/3 | -2/9 | 0 | 1 | 17 | F j - c j | 160/3 | -13/9 | 0 | -7/3 | 5/9 | 0 | 0 | 2 | x 2 | 5 | 5 | -1/12 | 1 | 0 | 1/6 | 0 | -1/4 | -- | x 5 | 0 | 80 | 10/3 | 0 | 0 | 10/3 | 1 | -20 | 24 | x 3 | 4 | 17 | 7/12 | 0 | 1 | -1/6 | 0 | 3/4 | 204/7 | F j - c j | 93 | -1/12 | 0 | 0 | 1/6 | 0 | 7/4 | 3 | x 2 | 5 | 7 | 0 | 1 | 0 | 1/4 | 1/40 | -3/4 | x 1 | 2 | 24 | 1 | 0 | 0 | 1 | 3/10 | -6 | x 3 | 4 | 3 | 0 | 0 | 1 | -3/4 | -7/40 | 17/4 | F j - c j | 95 | 0 | 0 | 0 | 1/4 | 1/40 | 5/4 |
Στη γραμμή ευρετηρίου, όλοι οι όροι είναι μη αρνητικοί, επομένως προκύπτει η ακόλουθη λύση στο πρόβλημα γραμμικού προγραμματισμού (το γράφουμε από τη στήλη των ελεύθερων όρων):
Είναι απαραίτητο να ράψετε 24 πουκάμισα 1ου τύπου, 7 πουκάμισα 2ου τύπου και 3 πουκάμισα 3ου τύπου. Σε αυτή την περίπτωση, το κέρδος που θα ληφθεί θα είναι μέγιστο και θα ανέρχεται σε 95 ρούβλια.
Μπορείτε να βρείτε βοήθεια για την επίλυση των προβλημάτων σας σχετικά με αυτό το θέμα στέλνοντας ένα μήνυμα στο VKontakte, το Viber ή συμπληρώνοντας τη φόρμα. Το κόστος επίλυσης της εργασίας για το σπίτι ξεκινά από 7 BYR. ανά εργασία (200 ρωσικά ρούβλια), αλλά όχι λιγότερο από 10 ρούβλια Λευκορωσίας. (300 RUB) για ολόκληρη την παραγγελία. Λεπτομερές σχέδιο. Το κόστος της ηλεκτρονικής βοήθειας στις εξετάσεις (στην περίπτωση αυτή απαιτείται προπληρωμή 100%) είναι από 30 BYR. (1000 ρωσικά ρούβλια) για την επίλυση του εισιτηρίου.
Εάν η πρόταση προβλήματος περιέχει περιορισμούς με το πρόσημο ≥, τότε μπορούν να αναχθούν στη μορφή ∑a ji b j πολλαπλασιάζοντας και τις δύο πλευρές της ανισότητας με -1. Ας εισαγάγουμε m πρόσθετες μεταβλητές x n+j ≥0(j =1,m) και ας μετατρέψουμε τους περιορισμούς στη μορφή ισοτήτων
(2)
Ας υποθέσουμε ότι όλες οι αρχικές μεταβλητές του προβλήματος x 1 , x 2 ,..., x n είναι μη βασικές. Τότε οι πρόσθετες μεταβλητές θα είναι βασικές και μια συγκεκριμένη λύση στο σύστημα περιορισμών έχει τη μορφή
x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m. (3)
Εφόσον σε αυτήν την περίπτωση η τιμή της συνάρτησης στόχου F 0 = 0, μπορούμε να αναπαραστήσουμε την F(x) ως εξής:
F(x)=∑c i x i +F 0 =0 (4)
Ο αρχικός πίνακας απλού (simplex πίνακας 1) συντάσσεται με βάση τις εξισώσεις (2) και (4). Εάν πριν από τις πρόσθετες μεταβλητές x n+j υπάρχει ένα σύμβολο «+», όπως στην (2), τότε όλοι οι συντελεστές μπροστά από τις μεταβλητές x i και τον ελεύθερο όρο b j εισάγονται στον πίνακα simplex χωρίς αλλαγές. Κατά τη μεγιστοποίηση της συνάρτησης στόχου, οι συντελεστές εισάγονται στην κάτω σειρά του πίνακα simplex με αντίθετα πρόσημα. Οι ελεύθεροι όροι στον πίνακα simplex καθορίζουν τη λύση στο πρόβλημα.
Ο αλγόριθμος για την επίλυση του προβλήματος είναι ο εξής:
1ο βήμα. Τα μέλη της στήλης ελεύθερα μέλη προβάλλονται. Εάν είναι όλα θετικά, τότε έχει βρεθεί μια αποδεκτή βασική λύση και θα πρέπει να προχωρήσουμε στο βήμα 5 του αλγορίθμου, που αντιστοιχεί στην εύρεση της βέλτιστης λύσης. Εάν ο αρχικός πίνακας simplex έχει αρνητικούς ελεύθερους όρους, τότε η λύση δεν είναι έγκυρη και πρέπει να πάτε στο βήμα 2.
2ο βήμα. Για να βρεθεί μια αποδεκτή λύση, πραγματοποιείται και είναι απαραίτητο να αποφασιστεί ποιες από τις μη βασικές μεταβλητές να συμπεριληφθούν στη βάση και ποια μεταβλητή να αφαιρεθεί από τη βάση.
Τραπέζι 1.
| βασικές μεταβλητές | Δωρεάν μέλη υπό περιορισμούς | Μη βασικές μεταβλητές | |||||
| x 1 | x 2 | ... | x l | ... | x n|||
| x n+1 | β 1 | ένα 11 | ένα 12 | ... | ένα 1 λίτρο | ... | ένα 1n |
| x n+2 | β 2 | ένα 21 | ένα 22 | ... | ένα 2 λ | ... | ένα 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n+r | β2 | ένα r1 | ένα r2 | ... | ένα rl | ... | arn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n+m | b m | ένα m1 | ένα m2 | ... | ένα ml | ... | ένα μν |
| F(x)max | F 0 | -γ 1 | -γ 2 | ... | -γ 1 | ... | -c n |
Για να το κάνετε αυτό, επιλέξτε οποιοδήποτε από τα αρνητικά στοιχεία της στήλης των ελεύθερων όρων (έστω b 2 που οδηγεί ή επιλύει. Εάν δεν υπάρχουν αρνητικά στοιχεία στη σειρά με αρνητικό ελεύθερο όρο, τότε το σύστημα των περιορισμών είναι ασυνεπές και το πρόβλημα δεν έχει λύση.
Ταυτόχρονα, η μεταβλητή που είναι η πρώτη που αλλάζει πρόσημο όταν αυξάνεται το επιλεγμένο NP x l εξαιρείται από το BP. Αυτό θα είναι x n+r, ο δείκτης r του οποίου καθορίζεται από τη συνθήκη
εκείνοι. η μεταβλητή που έχει τη μικρότερη αναλογία του ελεύθερου όρου προς το στοιχείο της επιλεγμένης κύριας στήλης. Αυτή η σχέση ονομάζεται σχέση απλού. Θα πρέπει να λαμβάνονται υπόψη μόνο οι θετικές σχέσεις απλού.
Καλείται η γραμμή που αντιστοιχεί στη μεταβλητή x n+r οδηγώντας, ή επιτρέποντας. Το στοιχείο του πίνακα simplex a rl, που βρίσκεται στη διασταύρωση της πρώτης γραμμής και της κύριας στήλης, ονομάζεται κύριο στοιχείο ή στοιχείο επίλυσης.Η εύρεση του κύριου στοιχείου ολοκληρώνει την εργασία με κάθε κανονικό πίνακα simplex.
3ο βήμα. Υπολογίζεται ένας νέος πίνακας simplex, τα στοιχεία του οποίου υπολογίζονται εκ νέου από τα στοιχεία του πίνακα simplex του προηγούμενου βήματος και σημειώνονται με πρώτο, δηλ. b" j , a" ji , c" i , F" 0 . Τα στοιχεία υπολογίζονται εκ νέου χρησιμοποιώντας τους ακόλουθους τύπους:
Αρχικά, ο νέος πίνακας simplex θα συμπληρώσει τη γραμμή και τη στήλη που προηγήθηκαν στον προηγούμενο πίνακα simplex. Η έκφραση (5) σημαίνει ότι το στοιχείο a" rl στη θέση του κύριου στοιχείου είναι ίσο με το αντίστροφο του στοιχείου του προηγούμενου πίνακα απλού. Τα στοιχεία της σειράς a ri διαιρούνται με το κύριο στοιχείο και τα στοιχεία του Η στήλη a jl διαιρείται επίσης με το κύριο στοιχείο, αλλά λαμβάνονται με το αντίθετο πρόσημο Τα στοιχεία b" r και c" l υπολογίζονται σύμφωνα με την ίδια αρχή.
Οι υπόλοιποι τύποι μπορούν εύκολα να γραφτούν χρησιμοποιώντας .
Το παραλληλόγραμμο είναι κατασκευασμένο σύμφωνα με τον παλιό πίνακα simplex με τέτοιο τρόπο ώστε μία από τις διαγώνιές του να σχηματίζεται από τα επαναυπολογισμένα (a ji) και τα κύρια (a rl) στοιχεία (Εικ. 1). Η δεύτερη διαγώνιος καθορίζεται μοναδικά. Για να βρεθεί ένα νέο στοιχείο a" ji, το γινόμενο των στοιχείων της αντίθετης διαγωνίου διαιρούμενο με το κύριο στοιχείο αφαιρείται από το στοιχείο a ji (αυτό υποδεικνύεται από το σύμβολο "-" δίπλα στο κελί). Στοιχεία b" j, (j≠r) και c" i υπολογίζονται εκ νέου με τον ίδιο τρόπο. (i≠l).
4ο βήμα. Η ανάλυση του νέου πίνακα simplex ξεκινά με το 1ο βήμα του αλγορίθμου. Η δράση συνεχίζεται μέχρι να βρεθεί μια εφικτή βασική λύση, δηλ. όλα τα στοιχεία της κινητής στήλης πρέπει να είναι θετικά.
5ο βήμα. Πιστεύουμε ότι έχει βρεθεί μια αποδεκτή βασική λύση. Εξετάζουμε τους συντελεστές της ευθείας της συνάρτησης στόχου F(x) . Ένα σημάδι της βελτιστότητας ενός πίνακα simplex είναι η μη αρνητικότητα των συντελεστών για μη βασικές μεταβλητές στη σειρά F.
Ρύζι. 1. Κανόνας ορθογωνίου
Εάν μεταξύ των συντελεστών της σειράς F υπάρχουν αρνητικοί (με εξαίρεση τον ελεύθερο όρο), τότε πρέπει να προχωρήσετε σε άλλη βασική λύση. Κατά τη μεγιστοποίηση της αντικειμενικής συνάρτησης, η βάση περιλαμβάνει μία από τις μη βασικές μεταβλητές (για παράδειγμα x l), η στήλη της οποίας αντιστοιχεί στη μέγιστη απόλυτη τιμή του αρνητικού συντελεστή c l στην κάτω σειρά του πίνακα simplex. Αυτό σας επιτρέπει να επιλέξετε τη μεταβλητή της οποίας η αύξηση οδηγεί σε βελτίωση της συνάρτησης στόχου. Η στήλη που αντιστοιχεί στη μεταβλητή x l ονομάζεται προπορευόμενη στήλη. Ταυτόχρονα, αυτή η μεταβλητή x n+r εξαιρείται από τη βάση, ο δείκτης r της οποίας καθορίζεται από την ελάχιστη σχέση απλού:
Η σειρά που αντιστοιχεί στο x n+r ονομάζεται προπορευόμενη και το στοιχείο του πίνακα simplex a rl, που βρίσκεται στη τομή της πρώτης γραμμής και της κύριας στήλης, ονομάζεται ηγετικό στοιχείο.
6ο βήμα. σύμφωνα με τους κανόνες που περιγράφονται στο βήμα 3. Η διαδικασία συνεχίζεται μέχρι να βρεθεί η βέλτιστη λύση ή να διαπιστωθεί ότι δεν υπάρχει.
Κατά τη βελτιστοποίηση λύσης, εάν όλα τα στοιχεία στην κύρια στήλη δεν είναι θετικά, τότε δεν μπορεί να επιλεγεί η πρώτη γραμμή. Σε αυτή την περίπτωση, η συνάρτηση στην περιοχή των εφικτών λύσεων στο πρόβλημα δεν περιορίζεται από πάνω και F max ->&∞.
Εάν, στο επόμενο βήμα της αναζήτησης ενός άκρου, μία από τις βασικές μεταβλητές γίνει ίση με μηδέν, τότε η αντίστοιχη βασική λύση ονομάζεται εκφυλισμένη. Σε αυτήν την περίπτωση, εμφανίζεται ένας λεγόμενος κύκλος, που χαρακτηρίζεται από το γεγονός ότι ο ίδιος συνδυασμός BPs αρχίζει να επαναλαμβάνεται με μια ορισμένη συχνότητα (η τιμή της συνάρτησης F διατηρείται) και είναι αδύνατο να μεταβείτε σε μια νέα εφικτή βασική λύση . Το looping είναι ένα από τα κύρια μειονεκτήματα της μεθόδου simplex, αλλά είναι σχετικά σπάνιο. Στην πράξη, σε τέτοιες περιπτώσεις, συνήθως αρνούνται να εισαγάγουν στη βάση τη μεταβλητή της οποίας η στήλη αντιστοιχεί στη μέγιστη απόλυτη τιμή του αρνητικού συντελεστή στη συνάρτηση στόχου και επιλέγουν τυχαία μια νέα λύση βάσης.
Παράδειγμα 1. Λύστε το πρόβλημα
max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)
Χρησιμοποιώντας τη μέθοδο simplex και δώστε μια γεωμετρική ερμηνεία της διαδικασίας επίλυσης.
Μια γραφική ερμηνεία της λύσης του προβλήματος παρουσιάζεται στο Σχ. 2. Η μέγιστη τιμή της συνάρτησης στόχου επιτυγχάνεται στην κορυφή του ODZP με συντεταγμένες . Ας λύσουμε το πρόβλημα χρησιμοποιώντας πίνακες simplex. Ας πολλαπλασιάσουμε τον δεύτερο περιορισμό με το (-1) και ας εισαγάγουμε πρόσθετες μεταβλητές για να φέρουμε τις ανισότητες στη μορφή ισοτήτων.
Παίρνουμε τις αρχικές μεταβλητές x 1 και x 2 ως μη βασικές και θεωρούμε τις επιπλέον x 3, x 4 και x 5 ως βασικές και συνθέτουμε έναν πίνακα απλού (simplex πίνακα 2). Η λύση που αντιστοιχεί στον πίνακα του simplex. 2, δεν ισχύει. το κύριο στοιχείο σκιαγραφείται και επιλέγεται σύμφωνα με το βήμα 2 του προηγούμενου αλγορίθμου. Ο παρακάτω πίνακας simplex. Το σχήμα 3 ορίζει μια αποδεκτή βασική λύση η κορυφή του ODZP στο Σχ. 1 αντιστοιχεί σε αυτήν. 2 Το κύριο στοιχείο περιγράφεται και επιλέγεται σύμφωνα με το 5ο βήμα του αλγορίθμου επίλυσης προβλημάτων. Τραπέζι Το 4 αντιστοιχεί στη βέλτιστη λύση του προβλήματος, επομένως: x 1 = x 5 = 0; x 2 = 4; x 3 = 3; x 4 = 8; F max = 20.
Ρύζι. 2. Γραφική λύση του προβλήματος
Μέθοδος Simplex− αυτή είναι μια μέθοδος τακτικής απαρίθμησης των σχεδίων αναφοράς (η τάξη διασφαλίζεται από μια μονότονη αλλαγή στην τιμή της αντικειμενικής συνάρτησης κατά τη μετάβαση στο επόμενο σχέδιο). Σε αυτήν την περίπτωση, είναι απαραίτητο να τηρηθεί η αρχή: κάθε επόμενο βήμα πρέπει να βελτιώνει ή, σε ακραίες περιπτώσεις, να μην επιδεινώνει την τιμή της αντικειμενικής συνάρτησης.
Για να λύσουμε το ZLP μέθοδο simplexφέρεται σε κανονική μορφή, δηλ. Από περιορισμούς - ανισότητες - επιβάλλεται να γίνουν περιορισμοί - ισότητα. Για να γίνει αυτό, ένας πρόσθετος μη αρνητικός παράγοντας εισάγεται σε κάθε περιορισμό μεταβλητή ισολογισμούμε πρόσημο «+» αν το πρόσημο ανισότητας είναι «£» και με «–» αν το πρόσημο ανισότητας είναι «³».
Στη συνάρτηση αντικειμενικού, αυτές οι πρόσθετες μεταβλητές περιλαμβάνονται με μηδενικούς συντελεστές, δηλ. η καταχώρηση της αντικειμενικής συνάρτησης δεν θα αλλάξει. Κάθε μεταβλητή που δεν υπόκειται στη συνθήκη μη αρνητικότητας μπορεί να αναπαρασταθεί ως η διαφορά δύο μη αρνητικών μεταβλητών: .
Εάν οι περιορισμοί εργασιών αντικατοπτρίζουν τη διαθεσιμότητα και την κατανάλωση πόρων, τότε η αριθμητική τιμή της πρόσθετης μεταβλητής στο σχέδιο εργασιών, γραμμένη σε κανονική μορφή, είναι ίση με την ποσότητα του αχρησιμοποίητου πόρου.
Για να λύσουμε το πρόβλημα χρησιμοποιώντας τη μέθοδο simplex που θα χρησιμοποιήσουμε συντομευμένοι πίνακες simplex συστημάτων γραμμικών εξισώσεων και η τροποποιημένη μέθοδος εξάλειψης Jordan.
1. Κάνοντας το πρώτο σχέδιο αναφοράς
Το καθήκον παραμένει το ίδιο. Ας φέρουμε την τυπική μορφή του συστήματος των ανισοτήτων (1) στην κανονική μορφή του συστήματος των εξισώσεων εισάγοντας πρόσθετες μεταβλητές ισορροπίας Χ 3 , Χ 4 , Χ 5 ,Χ 6 .
ή 
Από οικονομική άποψη, οι τιμές των πρόσθετων μεταβλητών Χ 3 , Χ 4 , Χ 5 καθορίζουν τις υπόλοιπες πρώτες ύλες μετά την πώληση των προϊόντων.
Ο πίνακας του προκύπτοντος συστήματος εξισώσεων έχει τη μορφή:
Μπορεί να φανεί ότι στη μήτρα ΕΝΑη βασική ελάσσονα της 4ης τάξης είναι μια ορίζουσα που αποτελείται από συντελεστές μονάδας για πρόσθετες μεταβλητές Χ 3 , Χ 4 , Χ 5 ,Χ 6, αφού είναι διαφορετικό από το μηδέν και ίσο με 1. Αυτό σημαίνει ότι τα διανύσματα στηλών για αυτές τις μεταβλητές είναι γραμμικά ανεξάρτητα, δηλ. μορφή βάση, και τις αντίστοιχες μεταβλητές Χ 3 , Χ 4 , Χ 5 ,Χ 6 είναι βασικός(κύριος). Μεταβλητές Χ 1 , Χ 2 θα κληθεί Ελεύθερος(μη πυρήνα).
Εάν ελεύθερες μεταβλητές Χ 1 και Χ 2 ορίστε διαφορετικές τιμές, στη συνέχεια, λύνοντας το σύστημα σε σχέση με τις βασικές μεταβλητές, λαμβάνουμε άπειρο αριθμό μερικών λύσεων. Αν στις ελεύθερες μεταβλητές δίνονται μόνο μηδενικές τιμές, τότε από το άπειρο σύνολο συγκεκριμένων λύσεων μπορεί κανείς να επιλέξει βασικές λύσεις– βασικά σχέδια.
Για να μάθετε αν οι μεταβλητές μπορούν να είναι βασικές, είναι απαραίτητο να υπολογίσετε μια ορίζουσα που αποτελείται από τους συντελεστές αυτών των μεταβλητών. Εάν αυτή η ορίζουσα δεν είναι ίση με μηδέν, τότε αυτές οι μεταβλητές μπορεί να είναι βασικές.
Ο αριθμός των βασικών λύσεων και ο αντίστοιχος αριθμός ομάδων βασικών μεταβλητών δεν μπορεί να είναι μεγαλύτερος από , όπου n– συνολικός αριθμός μεταβλητών, r– αριθμός βασικών μεταβλητών, r≤ Μ≤ n.
Για το έργο μας r = 4; n= 6. Τότε 
, δηλ. Είναι δυνατές 15 ομάδες των 4 βασικών μεταβλητών (ή 15 βασικών λύσεων).
Ας λύσουμε το σύστημα εξισώσεων για τις βασικές μεταβλητές Χ 3 , Χ 4 , Χ 5 ,Χ 6:
Υποθέτοντας ότι οι ελεύθερες μεταβλητές Χ 1 = 0, Χ 2 = 0, λαμβάνουμε τις τιμές των βασικών μεταβλητών: Χ 3 = 312; Χ 4 = 15; Χ 5 = 24;Χ 6 = –10, δηλ. η βασική λύση θα είναι = (0; 0; 312; 15; 24; -10).
Αυτή η βασική λύση είναι Απαράδεκτος, επειδή Χ 6 = –10 ≤ 0, και σύμφωνα με τις συνθήκες των περιορισμών Χ 6 ≥ 0. Επομένως, αντί για τη μεταβλητή Χ 6 ως βάση πρέπει να ληφθεί μια άλλη μεταβλητή από τις ελεύθερες Χ 1 ή Χ 2 .
Θα εκτελέσουμε την περαιτέρω λύση χρησιμοποιώντας συντομευμένους πίνακες simplex, συμπληρώνοντας τις σειρές του πρώτου πίνακα με τους συντελεστές συστήματος ως εξής (Πίνακας 1):
Τραπέζι 1
φά-η γραμμή λέγεται δείκτης. Γεμίζεται με συντελεστές της αντικειμενικής συνάρτησης που λαμβάνονται με αντίθετα πρόσημα, αφού η εξίσωση της συνάρτησης μπορεί να αναπαρασταθεί ως φά = 0 – (– 4Χ 1 – 3Χ 2).
Στη στήλη ελεύθερα μέλη β iυπάρχει ένα αρνητικό στοιχείο σι 4 = –10, δηλ. Η λύση συστήματος δεν είναι έγκυρη. Για να επιτευχθεί μια εφικτή λύση (σχέδιο αναφοράς), το στοιχείο σιΤο 4 πρέπει να γίνει μη αρνητικό.
Επιλέγω Χ 6 -χορδή με αρνητικό ελεύθερο όρο. Αυτή η γραμμή περιέχει αρνητικά στοιχεία. Επιλέξτε οποιοδήποτε από αυτά, για παράδειγμα, "–1" στο Χ 1 -στήλη, και ΧΗ στήλη 1 λαμβάνεται ως στήλη ανάλυσης(θα καθορίσει ότι η μεταβλητή Χ 1 θα μετακινηθεί από το ελεύθερο στο βασικό).
Χωρίζουμε ελεύθερα μέλη β iστα αντίστοιχα στοιχεία α είναιστήλη ανάλυσης, παίρνουμε αξιολογικές σχέσειςΘ Εγώ= = (24, 15, 12, 10). Από αυτά επιλέγουμε το μικρότερο θετικό (minΘ Εγώ=10), που θα αντιστοιχεί γραμμή άδειας. Η συμβολοσειρά ενεργοποίησης ορίζει τη μεταβλητή x j, το οποίο στο επόμενο βήμα προεξέχει από τη βάση και γίνεται ελεύθερο. Να γιατί ΧΗ γραμμή 6 είναι η γραμμή ενεργοποίησης και το στοιχείο "–1". επιτρεπτικό στοιχείο. Ας το κυκλώσουμε. Μεταβλητές Χ 1 και Χ 6 ανταλλάσσονται.
Εκτιμώμενοι λόγοι Θ Εγώσε κάθε γραμμή καθορίζονται σύμφωνα με τους κανόνες:
1) Θ Εγώ= αν β iΚαι α είναιέχουν διαφορετικά σημάδια?
2) Θ Εγώ= ∞, αν β i= 0 και α είναι < 0;
3) Θ Εγώ= ∞, αν α είναι = 0;
4) Θ Εγώ= 0 αν β i= 0 και α είναι > 0;
5)Θ Εγώ= αν β iΚαι α είναιέχουν τα ίδια σημάδια.
Εκτελούμε ένα βήμα τροποποιημένης εξάλειψης Jordan (JEME) με ένα στοιχείο επίλυσης και καταρτίζουμε έναν νέο πίνακα (Πίνακας 2) σύμφωνα με τον ακόλουθο κανόνα:
1) στη θέση του στοιχείου επίλυσης (RE), ορίζεται μια τιμή που είναι το αντίστροφό του, δηλ. ;
2) τα στοιχεία της συμβολοσειράς ενεργοποίησης χωρίζονται σε RE.
3) τα στοιχεία της στήλης ανάλυσης χωρίζονται σε RE και το πρόσημο αλλάζει.
4) τα υπόλοιπα στοιχεία βρίσκονται σύμφωνα με τον κανόνα του ορθογωνίου:
Από το τραπέζι 2 είναι σαφές ότι οι ελεύθεροι όροι σε β i- η στήλη είναι μη αρνητική, επομένως, προκύπτει η αρχική εφικτή λύση - πρώτο σχέδιο αναφοράς= (10; 0; 182; 5; 4; 0). Σε αυτή την περίπτωση, η τιμή της συνάρτησης φά() = 40. Γεωμετρικά αυτό αντιστοιχεί στην κορυφή φά(10; 0) πολύγωνο διαλύματος (Εικ. 1).
πίνακας 2
2. Ελέγχουμε το σχέδιο για βελτιστοποίηση.Το σχέδιο αναφοράς δεν είναι το βέλτιστο, αφού στο φά-Η γραμμή έχει αρνητικό συντελεστή «–4». Βελτιώνουμε το σχέδιο.
3. Εύρεση νέου σχεδίου αναφοράς
Επιλέγουμε το επιτρεπόμενο στοιχείο σύμφωνα με τον κανόνα:
Επιλέγουμε τον μικρότερο αρνητικό συντελεστή σε φά-γραμμή "–4", η οποία ορίζει τη στήλη ανάλυσης - Χ 6; μεταβλητός Χ 6 μετατρέπονται σε βασικά.
Βρίσκουμε τις σχέσεις Θ Εγώ, ανάμεσά τους επιλέγουμε το μικρότερο θετικό που αντιστοιχεί στη γραμμή ανάλυσης:
ελάχ Θ Εγώ = ελάχ(14, 5, 2, ∞) = 2, επομένως, Χ 5-γραμμών – ενεργοποίηση, μεταβλητή Χ 5 μετατρέπονται σε δωρεάν (μεταβλητές Χ 5 και Χ 6 ανταλλάσσονται).
Στη διασταύρωση της γραμμής και της στήλης επίλυσης υπάρχει ένα στοιχείο επίλυσης "2".
Πραγματοποιούμε το βήμα SMGI και χτίζουμε ένα τραπέζι. 3 σύμφωνα με τον παραπάνω κανόνα και παίρνουμε ένα νέο σχέδιο αναφοράς = (12; 0; 156; 3; 0; 2).
Πίνακας 3
4. Έλεγχος του νέου σχεδίου αναφοράς για βελτιστοποίηση
Το σχέδιο αναφοράς δεν είναι επίσης το βέλτιστο, αφού στο φά-Η γραμμή έχει αρνητικό συντελεστή «–1». Τιμή συνάρτησης φά() = 48, που γεωμετρικά αντιστοιχεί στην κορυφή μι(12; 0) πολύγωνο διαλύματος (Εικ. 1). Βελτιώνουμε το σχέδιο.
5. Εύρεση νέου σχεδίου αναφοράς
ΧΗ στήλη 2 είναι επιτρεπτή, αφού σε φά-γραμμή, ο μικρότερος αρνητικός συντελεστής “–1” είναι μέσα Χ 2-στήλη (Δ 2 = –1). Βρίσκουμε το μικρότερο Θ Εγώ: ελάχ Θ Εγώ = ελάχ(≈ 9, 6, ∞, 24) = 6, επομένως, Χ 4-γραμμή - επιτρέποντας. Στοιχείο ανάλυσης "1/2". Ανταλλαγή μεταβλητών Χ 2 και Χ 4 . Πραγματοποιούμε το βήμα SMGI και χτίζουμε ένα τραπέζι. 4, έχουμε ένα νέο σχέδιο αναφοράς = (9; 6; 51; 0; 0; 5).
6. Έλεγχος του σχεδίου αναφοράς για βελτιστοποίηση
ΣΕ φά-γραμμή, όλοι οι συντελεστές είναι μη αρνητικοί, επομένως, το σχέδιο αναφοράς είναι βέλτιστο. Γεωμετρικά αντιστοιχεί σε ένα σημείο ρε(9;6) (βλ. Εικ. 1). Το βέλτιστο σχέδιο δίνει τη μέγιστη τιμή της αντικειμενικής συνάρτησης 
c.u.
Εάν πρέπει να λύσετε ένα πρόβλημα γραμμικού προγραμματισμού χρησιμοποιώντας πίνακες simplex, τότε η ηλεκτρονική μας υπηρεσία θα σας βοηθήσει πολύ. Η μέθοδος simplex περιλαμβάνει τη διαδοχική αναζήτηση σε όλες τις κορυφές του εύρους των αποδεκτών τιμών προκειμένου να βρεθεί η κορυφή όπου η συνάρτηση παίρνει μια ακραία τιμή. Στο πρώτο στάδιο, βρίσκεται κάποια λύση, η οποία βελτιώνεται σε κάθε επόμενο βήμα. Αυτή η λύση ονομάζεται βασική. Ακολουθεί η σειρά των ενεργειών κατά την επίλυση ενός προβλήματος γραμμικού προγραμματισμού χρησιμοποιώντας τη μέθοδο simplex:
Το πρώτο βήμα. Στον καταρτισμένο πίνακα, πρώτα απ 'όλα, πρέπει να κοιτάξετε τη στήλη με τα ελεύθερα μέλη. Εάν υπάρχουν αρνητικά στοιχεία σε αυτό, τότε είναι απαραίτητο να προχωρήσετε στο δεύτερο βήμα, εάν όχι, τότε στο πέμπτο.
Δεύτερο βήμα.
Τραπέζι 1.
| βασικές μεταβλητές | Δωρεάν μέλη υπό περιορισμούς | Μη βασικές μεταβλητές | |||||
| x 1 | x 2 | ... | x l | ... | Στο δεύτερο βήμα, είναι απαραίτητο να αποφασίσετε ποια μεταβλητή θα εξαιρεθεί από τη βάση και ποια θα συμπεριληφθεί για να υπολογιστεί εκ νέου ο πίνακας simplex. Για να το κάνετε αυτό, κοιτάξτε τη στήλη με ελεύθερους όρους και βρείτε ένα αρνητικό στοιχείο σε αυτήν. Η γραμμή με αρνητικό στοιχείο θα ονομάζεται προπορευόμενη. Σε αυτό βρίσκουμε το μέγιστο αρνητικό στοιχείο σε συντελεστή, η αντίστοιχη στήλη είναι η υποτελής. Εάν υπάρχουν αρνητικές τιμές μεταξύ των δωρεάν όρων, αλλά όχι στην αντίστοιχη σειρά, τότε ένας τέτοιος πίνακας δεν θα έχει λύσεις. Η μεταβλητή στην πρώτη γραμμή που βρίσκεται στη στήλη των ελεύθερων όρων εξαιρείται από τη βάση και η μεταβλητή που αντιστοιχεί στην πρώτη στήλη περιλαμβάνεται στη βάση. | ||
| x n+1 | β 1 | ένα 11 | ένα 12 | ... | ένα 1 λίτρο | ... | ένα 1n |
| x n+2 | β 2 | ένα 21 | ένα 22 | ... | ένα 2 λ | ... | ένα 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n+r | β2 | ένα r1 | ένα r2 | ... | ένα rl | ... | arn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n+m | b m | ένα m1 | ένα m2 | ... | ένα ml | ... | ένα μν |
| F(x)max | F 0 | -γ 1 | -γ 2 | ... | -γ 1 | ... | -c n |
x n
Τέταρτο βήμα. Εάν μετά τον επανυπολογισμό έχουν απομείνει αρνητικά στοιχεία στη στήλη των ελεύθερων όρων, τότε πηγαίνετε στο πρώτο βήμα, εάν δεν υπάρχουν, τότε στο πέμπτο.
Πέμπτο βήμα. Εάν έχετε φτάσει στο πέμπτο βήμα, τότε έχετε βρει μια λύση που είναι αποδεκτή. Ωστόσο, αυτό δεν σημαίνει ότι είναι βέλτιστο. Θα είναι βέλτιστο μόνο εάν όλα τα στοιχεία στη συμβολοσειρά F είναι θετικά. Εάν αυτό δεν συμβαίνει, τότε είναι απαραίτητο να βελτιώσουμε τη λύση, για την οποία βρίσκουμε την πρώτη γραμμή και στήλη για τον επόμενο επανυπολογισμό χρησιμοποιώντας τον ακόλουθο αλγόριθμο. Αρχικά, βρίσκουμε τον ελάχιστο αρνητικό αριθμό στη συμβολοσειρά F, εξαιρουμένης της τιμής της συνάρτησης. Η στήλη με αυτόν τον αριθμό θα είναι η πρώτη. Για να βρούμε την πρώτη γραμμή, βρίσκουμε την αναλογία του αντίστοιχου ελεύθερου όρου και του στοιχείου από την πρώτη στήλη, με την προϋπόθεση ότι είναι θετικά. Η ελάχιστη αναλογία θα σας επιτρέψει να προσδιορίσετε την κύρια γραμμή. Υπολογίζουμε ξανά τον πίνακα χρησιμοποιώντας τους τύπους, δηλ. μεταβείτε στο βήμα 3.
Μέθοδος Dual Simplexβασίζεται στη θεωρία της δυαδικότητας (βλ. λύση του διπλού προβλήματος) και χρησιμοποιείται για την επίλυση προβλημάτων γραμμικού προγραμματισμού, οι ελεύθεροι όροι των οποίων το b i μπορεί να λάβει οποιεσδήποτε τιμές και το σύστημα περιορισμών καθορίζεται από ανισότητες σημασίας "≤", "≥" ή την ισότητα "=".Σκοπός της υπηρεσίας. Ηλεκτρονική αριθμομηχανή που χρησιμοποιείται για την επίλυση προβλημάτων γραμμικού προγραμματισμού Μέθοδος Pστις ακόλουθες φόρμες εγγραφής: η βασική μορφή εγγραφής της μεθόδου simplex, με τη μορφή πίνακα simplex, στην τροποποιημένη μέθοδο simplex.
Οδηγίες για την επίλυση προβλημάτων μέθοδος dual simplex. Επιλέξτε τον αριθμό των μεταβλητών και τον αριθμό των σειρών (αριθμός περιορισμών), κάντε κλικ στο Επόμενο. Η λύση που προκύπτει αποθηκεύεται σε ένα αρχείο Word (δείτε παράδειγμα λύσης που χρησιμοποιεί τη μέθοδο dual simplex).
Ταυτόχρονα, περιορισμοί όπως x i ≥ 0μην το λάβεις υπόψη σου.Τα ακόλουθα χρησιμοποιούνται επίσης με αυτήν την αριθμομηχανή:
Γραφική μέθοδος επίλυσης ZLP
Λύση του προβλήματος των μεταφορών
Επίλυση παιχνιδιού μήτρας
Χρησιμοποιώντας την ηλεκτρονική υπηρεσία, μπορείτε να προσδιορίσετε την τιμή ενός παιχνιδιού μήτρας (κάτω και άνω όρια), να ελέγξετε για την παρουσία ενός σημείου σέλας, να βρείτε μια λύση σε μια μικτή στρατηγική χρησιμοποιώντας τις ακόλουθες μεθόδους: minimax, μέθοδος simplex, γραφική (γεωμετρική ) μέθοδος, μέθοδος Brown.
Ακρότατο συνάρτησης δύο μεταβλητών
Προβλήματα δυναμικού προγραμματισμού
Διανείμετε 5 ομοιογενείς παρτίδες αγαθών μεταξύ τριών αγορών, ώστε να έχετε το μέγιστο εισόδημα από την πώλησή τους. Τα έσοδα από πωλήσεις σε κάθε αγορά G(X) εξαρτώνται από τον αριθμό των πωλούμενων παρτίδων του προϊόντος Χ και παρουσιάζονται στον πίνακα.
| Όγκος προϊόντος X (σε παρτίδες) | Εισόδημα G(X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 1 | 28 | 30 | 32 |
| 2 | 41 | 42 | 45 |
| 3 | 50 | 55 | 48 |
| 4 | 62 | 64 | 60 |
| 5 | 76 | 76 | 72 |
Στη μέθοδο P, το βέλτιστο σχέδιο προκύπτει μετακινώντας κατά μήκος ψευδοπλάνων. Ψευδοπλάνο- ένα σχέδιο στο οποίο ικανοποιούνται οι συνθήκες βελτιστοποίησης και μεταξύ των τιμών των βασικών μεταβλητών x i υπάρχουν αρνητικοί αριθμοί. Αλγόριθμος για τη μέθοδο dual simplexπεριλαμβάνει τα ακόλουθα βήματα:
- Κατάρτιση ψευδοσχεδίου. Το σύστημα περιορισμών του αρχικού προβλήματος οδηγεί σε ένα σύστημα ανισοτήτων με τη σημασία «≤».
- Έλεγχος του σχεδίου για βελτιστοποίηση. Εάν η συνθήκη βελτιστοποίησης δεν ικανοποιείται στο προκύπτον σχέδιο αναφοράς, τότε το πρόβλημα επιλύεται χρησιμοποιώντας τη μέθοδο simplex.
- Επιλογή πρώτης γραμμής και στήλης. Μεταξύ των αρνητικών τιμών των βασικών μεταβλητών, επιλέγονται οι μεγαλύτερες σε απόλυτη τιμή. Η γραμμή που αντιστοιχεί σε αυτήν την τιμή είναι η πρώτη.
- Υπολογισμός νέου σχεδίου αναφοράς. Το νέο σχέδιο προκύπτει με τον επανυπολογισμό του πίνακα simplex χρησιμοποιώντας τη μέθοδο Jordan-Gauss. Στη συνέχεια, προχωρήστε στο στάδιο 2.
Παράδειγμα. Η εταιρεία πρέπει να παράγει μονάδες Α1, μονάδες Α2 και μονάδες Α3 σύμφωνα με το σχέδιο παραγωγής. Κάθε τύπος προϊόντος μπορεί να παραχθεί σε δύο μηχανές.
Πώς να κατανείμετε την εργασία των μηχανών έτσι ώστε ο συνολικός χρόνος που δαπανάται για την εκτέλεση του σχεδίου να είναι ελάχιστος; Δίνεται ο πίνακας κόστους και ο χρόνος του κάθε μηχανήματος. Καταγράψτε το μοντέλο της υπό μελέτη πράξης σε μορφή που να επιτρέπει τη χρήση της μεθόδου P.
Είναι γνωστό ότι η περιεκτικότητα σε n θρεπτικά συστατικά Α, Β και Γ στη διατροφή πρέπει να είναι τουλάχιστον μονάδες m1, m2, m3 αντίστοιχα. Τρεις τύποι τροφών περιέχουν αυτά τα θρεπτικά συστατικά. Η περιεκτικότητα σε θρεπτικές μονάδες σε ένα κιλό για κάθε τύπο προϊόντος φαίνεται στον πίνακα. Καθορίστε μια καθημερινή διατροφή που να παρέχει την απαιτούμενη ποσότητα θρεπτικών συστατικών με ελάχιστο κόστος.
Εργασία: Λύστε το πρόβλημα χρησιμοποιώντας τον αλγόριθμο της μεθόδου dual simplex.
Ας ανάγουμε το σύστημα των περιορισμών στο σύστημα των ανισοτήτων νοήματος ≤ πολλαπλασιάζοντας τις αντίστοιχες ευθείες με (-1).
Ας προσδιορίσουμε την ελάχιστη τιμή της αντικειμενικής συνάρτησης F(X) = 4x 1 + 2x 2 + x 3 υπό τις ακόλουθες συνθήκες περιορισμού.
- x 1 - x 2 ≤-10
2x 1 + x 2 - x 3 ≤8
Για να κατασκευάσουμε το πρώτο σχέδιο αναφοράς, ανάγουμε το σύστημα των ανισοτήτων σε ένα σύστημα εξισώσεων εισάγοντας πρόσθετες μεταβλητές (μετάβαση στην κανονική μορφή).
Στην πρώτη ανισότητα νοήματος (≤), εισάγουμε τη βασική μεταβλητή x 4 . Στη δεύτερη ανισότητα νοήματος (≤), εισάγουμε τη βασική μεταβλητή x 5 .
-1x 1 -1x 2 + 0x 3 + 1x 4 + 0x 5 = -10
2x 1 + 1x 2 -1x 3 + 0x 4 + 1x 5 = 8
Ο πίνακας συντελεστών A = a(ij) αυτού του συστήματος εξισώσεων έχει τη μορφή:
| Α= |
|
x 4, x 5,
Υποθέτοντας ότι οι ελεύθερες μεταβλητές είναι ίσες με μηδέν, λαμβάνουμε το πρώτο σχέδιο αναφοράς:
X1 = (0,0,0,-10,8)
| Βάση | σι | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 4 | -10 | -1 | -1 | 0 | 1 | 0 |
| x 5 | 8 | 2 | 1 | -1 | 0 | 1 |
| F(X0) | 0 | -4 | -2 | -1 | 0 | 0 |
Επανάληψη #1
Το σχέδιο 0 σε έναν πίνακα simplex είναι ένα ψευδο-πλάνο, επομένως προσδιορίζουμε την πρώτη γραμμή και στήλη.
Η κύρια γραμμή θα είναι η πρώτη γραμμή και η μεταβλητή x 4 θα πρέπει να προέρχεται από τη βάση.
3. Ορισμός νέας βασικής μεταβλητής. Η ελάχιστη τιμή του θ αντιστοιχεί στη 2η στήλη, δηλ. η μεταβλητή x 2 πρέπει να εισαχθεί στη βάση.
| Βάση | σι | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 4 | -10 | -1 | -1 | 0 | 1 | 0 |
| x 5 | 8 | 2 | 1 | -1 | 0 | 1 |
| F(X0) | 0 | -4 | -2 | -1 | 0 | 0 |
| θ | 0 | -4: (-1) = 4 | -2: (-1) = 2 | - | - | - |
4. Επανυπολογισμός του πίνακα simplex. Πραγματοποιούμε μετασχηματισμούς του πίνακα simplex χρησιμοποιώντας τη μέθοδο Jordano-Gauss.
| Βάση | σι | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 5 | -2 | 1 | 0 | -1 | 1 | 1 |
| F(X0) | 20 | -2 | 0 | -1 | -2 | 0 |
Ας παρουσιάσουμε τον υπολογισμό κάθε στοιχείου με τη μορφή πίνακα:
| σι | x 1 | x 2 | x 3 | x 4 | x 5 |
| -10: -1 | -1: -1 | -1: -1 | 0: -1 | 1: -1 | 0: -1 |
| 8-(-10 1):-1 | 2-(-1 1):-1 | 1-(-1 1):-1 | -1-(0 1):-1 | 0-(1 1):-1 | 1-(0 1):-1 |
| 0-(-10 -2):-1 | -4-(-1 -2):-1 | -2-(-1 -2):-1 | -1-(0 -2):-1 | 0-(1 -2):-1 | 0-(0 -2):-1 |
Επανάληψη #2
1. Έλεγχος του κριτηρίου βελτιστοποίησης.
Το σχέδιο 1 σε έναν πίνακα simplex είναι ένα ψευδο-πλάνο, επομένως προσδιορίζουμε την πρώτη γραμμή και στήλη.
2. Ορισμός νέας ελεύθερης μεταβλητής.
Μεταξύ των αρνητικών τιμών των βασικών μεταβλητών, επιλέγουμε τη μεγαλύτερη σε απόλυτη τιμή.
Η δεύτερη γραμμή θα είναι η πρώτη και η μεταβλητή x 5 θα πρέπει να προέρχεται από τη βάση.
3. Ορισμός νέας βασικής μεταβλητής. Η ελάχιστη τιμή του θ αντιστοιχεί στην τρίτη στήλη, δηλ. η μεταβλητή x 3 πρέπει να εισαχθεί στη βάση.
Στη διασταύρωση της πρώτης γραμμής και στήλης υπάρχει ένα στοιχείο επίλυσης (RE) ίσο με (-1).
| Βάση | σι | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 5 | -2 | 1 | 0 | -1 | 1 | 1 |
| F(X0) | 20 | -2 | 0 | -1 | -2 | 0 |
| θ | 0 | - | - | -1: (-1) = 1 | - | - |
4. Επανυπολογισμός του πίνακα simplex. Πραγματοποιούμε μεταμορφώσεις.
| Βάση | σι | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 3 | 2 | -1 | 0 | 1 | -1 | -1 |
| F(X1) | 22 | -3 | 0 | 0 | -3 | -1 |
| σι | x 1 | x 2 | x 3 | x 4 | x 5 |
| 10-(-2 0):-1 | 1-(1 0):-1 | 1-(0 0):-1 | 0-(-1 0):-1 | -1-(1 0):-1 | 0-(1 0):-1 |
| -2: -1 | 1: -1 | 0: -1 | -1: -1 | 1: -1 | 1: -1 |
| 20-(-2 -1):-1 | -2-(1 -1):-1 | 0-(0 -1):-1 | -1-(-1 -1):-1 | -2-(1 -1):-1 | 0-(1 -1):-1 |
Στη στήλη βάσης, όλα τα στοιχεία είναι θετικά. Ας περάσουμε στον κύριο αλγόριθμο της μεθόδου simplex.
Επανάληψη #3
1. Έλεγχος του κριτηρίου βελτιστοποίησης.
Δεν υπάρχουν θετικές τιμές μεταξύ των τιμών συμβολοσειράς ευρετηρίου. Επομένως, αυτός ο πίνακας καθορίζει το βέλτιστο σχέδιο για το πρόβλημα.
| Βάση | σι | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 3 | 2 | -1 | 0 | 1 | -1 | -1 |
| F(X1) | 22 | -3 | 0 | 0 | -3 | -1 |
Το βέλτιστο σχέδιο μπορεί να γραφτεί ως εξής: x 1 = 0, x 2 = 10, x 3 = 2
F(X) = 2 10 + 1 2 = 22
