11.4. ΜΕΘΟΔΟΣ DUAL SIMPLEX
Από τα αποτελέσματα των προηγούμενων παραγράφων προκύπτει ότι για να ληφθεί μια λύση στο αρχικό πρόβλημα, μπορεί κανείς να πάει στο διπλό και, χρησιμοποιώντας εκτιμήσεις του βέλτιστου σχεδίου του, να καθορίσει τη βέλτιστη λύση στο αρχικό πρόβλημα.
Η μετάβαση στο διπλό πρόβλημα δεν είναι απαραίτητη, αφού αν λάβουμε υπόψη τον πρώτο πίνακα simplex με πρόσθετη βάση μονάδας, είναι εύκολο να παρατηρήσουμε ότι το αρχικό πρόβλημα είναι γραμμένο στις στήλες και το διπλό στις σειρές.
Όπως φάνηκε, κατά την επίλυση ενός άμεσου προβλήματος σε οποιαδήποτε επανάληψη, η διαφορά, δηλ. μέγεθος -συντελεστής της μεταβλητής, ισούται με τη διαφορά μεταξύ της δεξιάς και της αριστερής πλευράς του αντίστοιχου περιορισμού του διπλού προβλήματος. Εάν, κατά την επίλυση ενός άμεσου προβλήματος με μια μεγιστοποιημένη αντικειμενική συνάρτηση, η επανάληψη δεν οδηγεί σε μια βέλτιστη λύση, τότε τουλάχιστον για μία μεταβλητή και μόνο στο βέλτιστο για όλεςδιαφορά.
Λαμβάνοντας υπόψη αυτή τη συνθήκη λαμβάνοντας υπόψη τη δυαδικότητα, μπορούμε να γράψουμε
.
Έτσι, εάν, Οτι . Αυτό σημαίνει ότι όταν η λύση στο άμεσο πρόβλημα δεν είναι βέλτιστη, η λύση στο διπλό πρόβλημα δεν είναι εφικτή. Στην άλλη πλευρά 
στο . Επομένως, η βέλτιστη λύση στο άμεσο πρόβλημα αντιστοιχεί σε μια αποδεκτή λύση στο διπλό πρόβλημα.
Αυτό κατέστησε δυνατή την ανάπτυξη μιας νέας μεθόδου για την επίλυση προβλημάτων γραμμικού προγραμματισμού, η οποία αρχικά παράγει μια απαράδεκτη, αλλά «καλύτερη από τη βέλτιστη» λύση (στη συνήθη μέθοδο simplex, πρώτα βρίσκει κανείς δεκτός, Αλλά υποβέλτιστηλύση). Η νέα μέθοδος, που ονομάζεται μέθοδος dual simplex, διασφαλίζει την εκπλήρωση των προϋποθέσεων για τη βελτιστοποίηση της λύσης και τη συστηματική «προσέγγισή» της στην περιοχή των εφικτών λύσεων. Όταν η λύση που προκύπτει είναι εφικτή, η επαναληπτική διαδικασία των υπολογισμών τελειώνει, αφού και αυτή η λύση είναι βέλτιστη.
Η μέθοδος dual simplex καθιστά δυνατή την επίλυση προβλημάτων γραμμικού προγραμματισμού των οποίων τα συστήματα περιορισμού, με θετική βάση, περιέχουν ελεύθερους όρους οποιουδήποτε πρόσημου. Αυτή η μέθοδος σάς επιτρέπει να μειώσετε τον αριθμό των μετασχηματισμών του συστήματος περιορισμών, καθώς και το μέγεθος του πίνακα simplex. Ας εξετάσουμε την εφαρμογή της μεθόδου dual simplex χρησιμοποιώντας ένα παράδειγμα.
Παράδειγμα. Βρείτε το ελάχιστο μιας συνάρτησης 
υπό περιορισμούς
.
Ας προχωρήσουμε στην κανονική μορφή:
υπό περιορισμούς
Ο αρχικός πίνακας simplex έχει τη μορφή
|
Βασικός μεταβλητές |
Χ 1 |
Χ 2 |
Χ 3 |
Χ 4 |
Χ 5 |
Λύση |
|
Χ 3 Χ 4 Χ 5 |
–3 –4 |
–1 –3 |
–3 –6 |
|||
|
–2 |
–1 |
Λύση αρχικής βάσηςβέλτιστη, αλλά όχι αποδεκτή.
Όπως η συνηθισμένη μέθοδος simplex, η μέθοδος επίλυσης που εξετάζεται βασίζεται στη χρήση των συνθηκών αποδοχής και βελτιστοποίησης.
Προϋπόθεση παραδεκτού. Η μεγαλύτερη μεταβλητή επιλέγεται ως η εξαιρούμενη μεταβλητή. απόλυτη τιμήαρνητική βασική μεταβλητή (αν υπάρχουν εναλλακτικές, η επιλογή γίνεται αυθαίρετα). Εάν όλες οι βασικές μεταβλητές είναι μη αρνητικές, η διαδικασία υπολογισμού τελειώνει, καθώς η λύση που προκύπτει είναι εφικτή και βέλτιστη.
Κατάσταση βέλτιστη. Η μεταβλητή που περιλαμβάνεται στη βάση επιλέγεται μεταξύ των μη βασικών μεταβλητών ως εξής. Υπολογίζονται οι λόγοι των συντελεστών της αριστερής πλευράς-εξισώσεις στους αντίστοιχους συντελεστές της εξίσωσης που σχετίζονται με την εξαιρούμενη μεταβλητή. Οι λόγοι με θετικό ή μηδενικό παρονομαστή δεν λαμβάνονται υπόψη. Στο πρόβλημα ελαχιστοποίησης, η μεταβλητή εισόδου πρέπει να αντιστοιχεί στον μικρότερο από τους καθορισμένους λόγους και στο πρόβλημα μεγιστοποίησης, ο λόγος που είναι ο μικρότερος σε απόλυτη τιμή (αν υπάρχουν εναλλακτικές, η επιλογή γίνεται αυθαίρετα). Εάν οι παρονομαστές όλων των αναλογιών είναι μηδέν ή θετικοί, το πρόβλημα δεν έχει εφικτές λύσεις.
Μετά την επιλογή των μεταβλητών που θα συμπεριληφθούν στη βάση και θα εξαιρεθούν, για να ληφθεί η επόμενη λύση, πραγματοποιείται η συνήθης λειτουργία μετατροπής των σειρών ενός πίνακα simplex.
Σε αυτό το παράδειγμα, η εξαιρούμενη μεταβλητή είναι. Οι λόγοι που υπολογίζονται για τον προσδιορισμό της νέας μεταβλητής βάσης δίνονται στον ακόλουθο πίνακα:
|
Μεταβλητές |
Χ 1 |
Χ 2 |
Χ 3 |
Χ 4 |
Χ 5 |
|
Η εξίσωση Χ 4 - εξίσωση |
–2 –4 |
–1 –3 |
|||
|
Στάση |
Επιλέγεται η συμπεριλαμβανόμενη μεταβλητή Χ 2. Η επακόλουθη μετατροπή συμβολοσειράς οδηγεί σε έναν νέο πίνακα simplex:
|
Βασικός μεταβλητές |
Χ 1 |
Χ 2 |
Χ 3 |
Χ 4 |
Χ 5 |
Λύση |
|
Χ 3 Χ 2 Χ 5 |
–1 –1 |
|||||
Νέα λύση επίσης βέλτιστη, αλλά ακόμα απαράδεκτη. Ως νέα εξαιρούμενη μεταβλητή επιλέγουμε (αυθαίρετα) Χ 3. Ας ορίσουμε τη μεταβλητή που θα συμπεριληφθεί.
|
Μεταβλητές |
Χ 1 |
Χ 2 |
Χ 3 |
Χ 4 |
Χ 5 |
|
Η εξίσωση Χ 4 - εξίσωση |
|||||
|
στάση |
Εάν η πρόταση προβλήματος περιέχει περιορισμούς με το πρόσημο ≥, τότε μπορούν να αναχθούν στη μορφή ∑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ο βήμα του αλγορίθμου. Η δράση συνεχίζεται μέχρι να βρεθεί μια εφικτή βασική λύση, δηλ. όλα τα στοιχεία της float στήλης πρέπει να είναι θετικά.
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είναι μια επαναληπτική διαδικασία κατευθυνόμενης λύσης ενός συστήματος εξισώσεων βήμα προς βήμα, η οποία ξεκινά με μια λύση αναφοράς και αναζητώντας καλύτερη επιλογήκινείται κατά μήκος των γωνιακών σημείων της περιοχής εφικτής λύσης, βελτιώνοντας την τιμή της αντικειμενικής συνάρτησης έως ότου η αντικειμενική συνάρτηση φτάσει τη βέλτιστη τιμή.Σκοπός της υπηρεσίας. Η υπηρεσία προορίζεται για διαδικτυακές λύσειςΠροβλήματα γραμμικού προγραμματισμού (LPP) χρησιμοποιώντας τη μέθοδο simplex στις ακόλουθες μορφές συμβολισμού:
- με τη μορφή πίνακα simplex (μέθοδος μετασχηματισμού της Ιορδανίας). βασική φόρμα εγγραφής?
- Τροποποιημένη μέθοδος Simplex. σε μορφή στήλης? σε μορφή γραμμής.
Οδηγίες. Επιλέξτε τον αριθμό των μεταβλητών και τον αριθμό των σειρών (αριθμός περιορισμών). Η λύση που προκύπτει αποθηκεύεται σε αρχείο Word και Excel.
Σε αυτήν την περίπτωση, μην λαμβάνετε υπόψη περιορισμούς όπως x i ≥ 0. Εάν δεν υπάρχουν περιορισμοί στην εργασία για μερικά x i, τότε το ZLP πρέπει να μετατραπεί σε KZLP ή να χρησιμοποιήσετε αυτήν την υπηρεσία. Κατά την επίλυση, η χρήση καθορίζεται αυτόματα M-μέθοδος(απλή μέθοδος με τεχνητή βάση) και μέθοδος απλού δύο σταδίων.Τα ακόλουθα χρησιμοποιούνται επίσης με αυτήν την αριθμομηχανή:
Γραφική μέθοδος επίλυσης 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 |
Αλγόριθμος μεθόδου Simplexπεριλαμβάνει τα ακόλουθα βήματα:
- Κατάρτιση του πρώτου βασικού σχεδίου. Μετάβαση στην κανονική μορφή του προβλήματος γραμμικού προγραμματισμού εισάγοντας μη αρνητικές πρόσθετες μεταβλητές ισορροπίας.
- Έλεγχος του σχεδίου για βελτιστοποίηση. Εάν υπάρχει τουλάχιστον ένας συντελεστής σειράς δείκτη λιγότερο από το μηδέν, τότε το σχέδιο δεν είναι βέλτιστο και πρέπει να βελτιωθεί.
- Προσδιορισμός της κύριας στήλης και γραμμής. Από τους αρνητικούς συντελεστές της γραμμής του δείκτη επιλέγεται ο μεγαλύτερος σε απόλυτη τιμή. Στη συνέχεια, τα στοιχεία της στήλης ελεύθερου μέλους του πίνακα simplex χωρίζονται σε στοιχεία του ίδιου πρόσημου της κύριας στήλης.
- Κατασκευή νέου σχεδίου αναφοράς. Η μετάβαση σε ένα νέο σχέδιο πραγματοποιείται ως αποτέλεσμα του επανυπολογισμού του πίνακα simplex χρησιμοποιώντας τη μέθοδο Jordan-Gauss.
Εάν είναι απαραίτητο να βρεθεί το άκρο της αντικειμενικής συνάρτησης, τότε μιλάμε γιασχετικά με την εύρεση της ελάχιστης τιμής (F(x) → min , δείτε το παράδειγμα μιας λύσης για την ελαχιστοποίηση μιας συνάρτησης) και της μέγιστης τιμής ((F(x) → max , δείτε το παράδειγμα μιας λύσης για τη μεγιστοποίηση μιας συνάρτησης)
Μια ακραία λύση επιτυγχάνεται στο όριο της περιοχής των εφικτών λύσεων σε μία από τις κορυφές των γωνιακών σημείων του πολυγώνου ή στο τμήμα μεταξύ δύο γειτονικών γωνιακών σημείων.
Θεμελιώδες Θεώρημα Γραμμικού Προγραμματισμού. Εάν η αντικειμενική συνάρτηση ZLP φτάσει σε μια ακραία τιμή σε κάποιο σημείο στην περιοχή των εφικτών λύσεων, τότε παίρνει αυτήν την τιμή στο γωνιακό σημείο. Εάν η αντικειμενική συνάρτηση ZLP φτάσει σε μια ακραία τιμή σε περισσότερα από ένα γωνιακά σημεία, τότε παίρνει την ίδια τιμή σε οποιονδήποτε από τους κυρτούς γραμμικούς συνδυασμούς αυτών των σημείων.
Η ουσία της μεθόδου simplex. Η μετακίνηση στο βέλτιστο σημείο πραγματοποιείται μετακινώντας από το ένα γωνιακό σημείο στο γειτονικό, το οποίο φέρνει όλο και πιο γρήγορα το X opt. Ένα τέτοιο σχήμα για την απαρίθμηση σημείων, ονομάζεται μέθοδος simplex, που προτείνει ο R. Danzig.
Τα γωνιακά σημεία χαρακτηρίζονται από m βασικές μεταβλητές, επομένως η μετάβαση από ένα γωνιακό σημείο σε ένα γειτονικό μπορεί να επιτευχθεί αλλάζοντας μόνο μία βασική μεταβλητή στη βάση σε μια μεταβλητή από μη βάση.
Εφαρμογή της ισχύουσας μεθόδου simplex διάφορα χαρακτηριστικάκαι δηλώσεις προβλημάτων, το LP έχει διάφορες τροποποιήσεις.
Η κατασκευή πινάκων simplex συνεχίζεται μέχρι να επιτευχθεί η βέλτιστη λύση. Πώς μπορείτε να χρησιμοποιήσετε έναν πίνακα simplex για να προσδιορίσετε ότι η λύση σε ένα πρόβλημα γραμμικού προγραμματισμού είναι η βέλτιστη;
Εάν η τελευταία γραμμή (τιμές της αντικειμενικής συνάρτησης) δεν περιέχει αρνητικά στοιχεία, επομένως, θα βρει το βέλτιστο σχέδιο.
Παρατήρηση 1. Εάν μία από τις βασικές μεταβλητές είναι ίση με μηδέν, τότε το ακραίο σημείο που αντιστοιχεί σε μια τέτοια βασική λύση είναι εκφυλισμένο. Ο εκφυλισμός εμφανίζεται όταν υπάρχει ασάφεια στην επιλογή της γραμμής καθοδήγησης. Μπορεί να μην παρατηρήσετε καθόλου τον εκφυλισμό του προβλήματος εάν επιλέξετε μια άλλη γραμμή ως οδηγό. Σε περίπτωση ασάφειας, θα πρέπει να επιλεγεί η σειρά με τον χαμηλότερο δείκτη για να αποφευχθεί ο βρόχος.
Παρατήρηση 2. Έστω σε κάποιο ακραίο σημείο όλες οι διαφορές του simplex μη αρνητικές D k ³ 0 (k = 1..n+m), δηλ. προκύπτει μια βέλτιστη λύση και υπάρχει A k - ένα διάνυσμα χωρίς βάση για το οποίο D k = 0. Τότε το μέγιστο επιτυγχάνεται τουλάχιστον σε δύο σημεία, δηλ. υπάρχει ένα εναλλακτικό βέλτιστο. Εάν εισάγουμε αυτή τη μεταβλητή x k στη βάση, η τιμή της αντικειμενικής συνάρτησης δεν θα αλλάξει.
Παρατήρηση 3. Η λύση του διπλού προβλήματος βρίσκεται στον τελευταίο πίνακα simplex. Οι τελευταίες m συνιστώσες του διανύσματος των διαφορών του απλού (στις στήλες των μεταβλητών ισορροπίας) είναι η βέλτιστη λύση στο διπλό πρόβλημα. Οι τιμές των αντικειμενικών συναρτήσεων των άμεσων και διπλών προβλημάτων στα βέλτιστα σημεία συμπίπτουν.
Παρατήρηση 4. Κατά την επίλυση του προβλήματος ελαχιστοποίησης, εισάγεται στη βάση το διάνυσμα με τη μεγαλύτερη θετική διαφορά απλού. Στη συνέχεια, εφαρμόζεται ο ίδιος αλγόριθμος όπως και για το πρόβλημα μεγιστοποίησης.
Εάν προσδιορίζεται η προϋπόθεση «Είναι απαραίτητο να καταναλωθούν πλήρως οι πρώτες ύλες τύπου III», τότε η αντίστοιχη προϋπόθεση είναι ισότητα.
Εάν έχετε ήδη κατανοήσει τη γραφική μέθοδο επίλυσης προβλημάτων γραμμικού προγραμματισμού, ήρθε η ώρα να προχωρήσετε στο μέθοδο simplex. Σε αντίθεση με την πρώτη, πρακτικά δεν έχει περιορισμούς στο πρόβλημα (οποιοσδήποτε αριθμός μεταβλητών, διαφορετικά σημάδιακ.λπ.) και τροποποιείται ανάλογα με τον τύπο του προβλήματος (για παράδειγμα, η μέθοδος M ή η μέθοδος τεχνητής βάσης).
Κατά την επίλυση ενός προβλήματος χρησιμοποιώντας τη μέθοδο simplex, οι υπολογισμοί συνήθως πραγματοποιούνται (για συμπαγή και σαφήνεια) σε πίνακες (μέθοδος απλού πίνακα πινάκων) και ο τελευταίος πίνακας με τη βέλτιστη λύση περιέχει σημαντικές πρόσθετες πληροφορίες: τη λύση στο διπλό πρόβλημα, τους υπόλοιπους πόρους , πληροφορίες σχετικά με σπάνιους πόρους, κ.λπ., που επιτρέπει την οικονομική ανάλυση ενός προβλήματος γραμμικού προγραμματισμού (βλ. παράδειγμα 3 παρακάτω).
Παραδείγματα λύσεων σε προβλήματα που χρησιμοποιούν τη μέθοδο simplex δημοσιεύονται δωρεάν για τη διευκόλυνσή σας - μελετήστε, αναζητήστε παρόμοια, λύστε. Εάν χρειάζεστε βοήθεια με εργασίες όπως αυτή, μεταβείτε στη διεύθυνση: Λύση προσαρμοσμένου γραμμικού προγραμματισμού.
Επίλυση προβλημάτων με τη μέθοδο simplex: διαδικτυακά παραδείγματα
Εργασία 1.Η εταιρεία παράγει ράφια μπάνιου σε δύο μεγέθη - Α και Β. Οι αντιπρόσωποι πωλήσεων εκτιμούν ότι στην αγορά θα μπορούσαν να πωληθούν έως και 550 ράφια την εβδομάδα. Κάθε ράφι τύπου Α απαιτεί 2 m2 υλικού και κάθε ράφι τύπου Β απαιτεί 3 m2 υλικού. Η εταιρεία μπορεί να λάβει έως και 1200 m2 υλικού την εβδομάδα. Για την κατασκευή ενός ραφιού τύπου Α απαιτούνται 12 λεπτά χρόνου μηχανής και για την κατασκευή ενός ραφιού τύπου Β - 30 λεπτά. Το μηχάνημα μπορεί να χρησιμοποιηθεί 160 ώρες την εβδομάδα. Εάν το κέρδος από την πώληση ράφια τύπου Α είναι 3 νομισματικές μονάδες και από ράφια τύπου Β - 4 νομισματικές μονάδες. μονάδες, τότε πόσα ράφια κάθε τύπου πρέπει να παράγονται την εβδομάδα;
Σχεδίαση μαθηματικού μοντέλου και επίλυση του ZLP με τη μέθοδο simplex (pdf, 33 Kb)
Εργασία 2.Λύστε ένα πρόβλημα γραμμικού προγραμματισμού χρησιμοποιώντας τη μέθοδο simplex. 
Λύση με τη μέθοδο simplex με τεχνητή βάση (pdf, 45 Kb)
Εργασία 3.Η εταιρεία παράγει 3 είδη προϊόντων: Α1, Α2, Α3, χρησιμοποιώντας δύο τύπους πρώτων υλών. Είναι γνωστά τα κόστη κάθε τύπου πρώτης ύλης ανά μονάδα παραγωγής, τα αποθέματα πρώτων υλών για την περίοδο προγραμματισμού, καθώς και το κέρδος από μια μονάδα παραγωγής κάθε τύπου.
- Πόσα είδη κάθε τύπου πρέπει να παραχθούν για να μεγιστοποιηθεί το κέρδος;
- Προσδιορίστε την κατάσταση κάθε τύπου πρώτης ύλης και τη συγκεκριμένη αξία του.
- Προσδιορίστε το μέγιστο διάστημα για αλλαγές στα αποθέματα κάθε τύπου πρώτης ύλης, εντός του οποίου η δομή του βέλτιστου σχεδίου, π.χ. Η ονοματολογία παραγωγής δεν θα αλλάξει.
- Προσδιορίστε την ποσότητα των παραγόμενων προϊόντων και το κέρδος από την παραγωγή κατά την αύξηση του αποθέματος ενός από τους σπάνιους τύπους πρώτων υλών στη μέγιστη δυνατή τιμή (εντός του δεδομένου εύρους παραγωγής).
- Προσδιορίστε τα διαστήματα μεταβολής του κέρδους από μια μονάδα παραγωγής κάθε τύπου στα οποία το βέλτιστο σχέδιο που προκύπτει δεν θα αλλάξει.
Επίλυση προβλήματος γραμμικού προγραμματισμού με οικονομική ανάλυση (pdf, 163 Kb)
Εργασία 4.Λύστε ένα πρόβλημα γραμμικού προγραμματισμού χρησιμοποιώντας τη μέθοδο simplex: 
Λύση με χρήση της μεθόδου απλού πίνακα με αναζήτηση για το σχέδιο αναφοράς (pdf, 44 Kb)
Εργασία 5.Λύστε ένα πρόβλημα γραμμικού προγραμματισμού χρησιμοποιώντας τη μέθοδο simplex: 
Λύση με τη μέθοδο του απλού πίνακα (pdf, 47 Kb)
Εργασία 6.Λύστε το πρόβλημα χρησιμοποιώντας τη μέθοδο simplex, θεωρώντας ως αρχικό σχέδιο αναφοράς το σχέδιο που δίνεται στην συνθήκη: 
Λύση με χειροκίνητη μέθοδο simplex (pdf, 60 Kb)
Εργασία 7.Λύστε το πρόβλημα χρησιμοποιώντας την τροποποιημένη μέθοδο Simplex.
Για την παραγωγή δύο τύπων προϊόντων Α και Β, χρησιμοποιούνται τρεις τύποι τεχνολογικού εξοπλισμού. Για την παραγωγή μιας μονάδας προϊόντος Α, ο εξοπλισμός του πρώτου τύπου χρησιμοποιεί a1=4 ώρες, ο εξοπλισμός του δεύτερου τύπου a2=8 ώρες και ο εξοπλισμός του τρίτου τύπου a3=9 ώρες. Για την παραγωγή μιας μονάδας προϊόντος Β, ο εξοπλισμός του πρώτου τύπου χρησιμοποιεί b1=7 ώρες, ο εξοπλισμός του δεύτερου τύπου b2=3 ώρες και ο εξοπλισμός του τρίτου τύπου b3=5 ώρες.
Ο εξοπλισμός του πρώτου τύπου μπορεί να λειτουργήσει για την παραγωγή αυτών των προϊόντων για όχι περισσότερο από t1=49 ώρες, ο εξοπλισμός του δεύτερου τύπου για όχι περισσότερο από t2=51 ώρες, ο εξοπλισμός του τρίτου τύπου για όχι περισσότερο από t3=45 ώρες.
Το κέρδος από την πώληση μιας μονάδας τελικού προϊόντος Α είναι ALPHA = 6 ρούβλια και το προϊόν Β είναι BETTA = 5 ρούβλια.
Εκπόνηση σχεδίου παραγωγής για τα προϊόντα Α και Β, εξασφαλίζοντας μέγιστο κέρδος από την πώλησή τους.
Λύση με την τροποποιημένη μέθοδο simplex (pdf, 67 Kb)
Εργασία 8.Βρείτε τη βέλτιστη λύση χρησιμοποιώντας τη μέθοδο dual simplex 
Λύση με τη μέθοδο dual simplex (pdf, 43 Kb)
Παραδείγματα λύσεων σε προβλήματα γραμμικού προγραμματισμού
Μέθοδοι επίλυσης προβλημάτων γραμμικού προγραμματισμού
Λύσεις αναφοράς σε ένα πρόβλημα γραμμικού προγραμματισμού
Ας δοθεί ένα πρόβλημα γραμμικού προγραμματισμού με κανονικό συμβολισμό
υπο προυποθεσεις
Θα υποδηλώσουμε με το σύνολο των συστημάτων λύσεων (2) – (3). Ας υποθέσουμε ότι , πού είναι η κατάταξη του πίνακα , και είναι ο αριθμός των εξισώσεων στο σύστημα (2).
Από το σύστημα των διανυσμάτων στηλών του πίνακα, επιλέγουμε κάποιο γραμμικά ανεξάρτητο υποσύστημα διανυσμάτων. Υπάρχει γιατί . Αυτό το σύστημα αποτελεί τη βάση στο . Ας υποδηλώσουμε με , . Ας καλέσουμε σύνολο βασικών αξιών ευρετήριο, - υπομήτρα βάσης μήτρες Θα καλέσουμε τις συντεταγμένες του διανύσματος βασικός , αν μη βασική σε διαφορετική περίπτωση.
Ας γράψουμε το σύστημα (2) με τη μορφή . Ας χωρίσουμε τους όρους στην αριστερή πλευρά σε βασικούς και μη βασικούς, δηλαδή
Ας ορίσουμε μια συγκεκριμένη λύση αυτού του συστήματος ως εξής. Ας ορίσουμε όλες τις μη βασικές μεταβλητές ίσες με το μηδέν στην (4). Τότε το σύστημα (4) θα πάρει τη μορφή
Ας καλέσουμε (5) βασικό υποσύστημα σύστημα εξισώσεων (2). Ας συμβολίσουμε με ένα διάνυσμα που αποτελείται από τις βασικές συντεταγμένες του διανύσματος. Τότε το σύστημα (2) μπορεί να ξαναγραφτεί σε μορφή διανύσματος-μήτρας
Δεδομένου ότι ο υπομήτρας είναι βασικός, αυτό
μη εκφυλισμένος. Επομένως, το σύστημα (6) έχει μια μοναδική λύση. Η συγκεκριμένη λύση του συστήματος (2) που προκύπτει με αυτόν τον τρόπο θα ονομάζεται λύση αναφοράς πρόβλημα άμεσου γραμμικού προγραμματισμού που αντιστοιχεί στη βάση. (Μερικές φορές ονομάζεται και η λύση αναφοράς βασικός ). Όπως μπορούμε να δούμε, η βάση αντιστοιχεί σε μια ενιαία λύση υποστήριξης. Προφανώς, ο αριθμός των λύσεων υποστήριξης είναι πεπερασμένος.
Για αυτή τη βάση, προσδιορίζουμε επίσης τη λύση αναφοράς στο πρόβλημα του διπλού γραμμικού προγραμματισμού. Θυμηθείτε ότι το πρόβλημα διπλό προς το κανονικό έχει τη μορφή
υπο προυποθεσεις
Ας γράψουμε το σύστημα (8) στη μορφή
Θυμηθείτε ότι το σύνολο των λύσεων στο σύστημα (8) συμβολίζεται με .
Ας ορίσουμε το διάνυσμα των διπλών μεταβλητών από την προϋπόθεση της εκπλήρωσης των βασικών περιορισμών στο σύστημα (9) ως ισότητες. Παίρνουμε το παρακάτω σύστημα γραμμικές εξισώσεις:
Ας υποδηλώσουμε με ένα διάνυσμα που αποτελείται από ba-
συντεταγμένες zis του διανύσματος. Στη συνέχεια, το σύστημα (10) μπορεί να ξαναγραφτεί σε μορφή διανύσματος-μήτρας
Το σύστημα (11) έχει επίσης μια μοναδική λύση.
Ας τον φωνάξουμε υποστηρίζοντας (βασικός )απόφαση πρόβλημα διπλού γραμμικού προγραμματισμού που αντιστοιχεί στη βάση. Αυτή η λύση αναφοράς προσδιορίζεται επίσης μοναδικά.
Έτσι, οποιαδήποτε βάση αντιστοιχεί σε δύο διανύσματα - δύο λύσεις υποστήριξης και προβλήματα άμεσου και διπλού γραμμικού προγραμματισμού, αντίστοιχα.
Ας ορίσουμε περαιτέρω τους ακόλουθους τύπους βάσεων και λύσεων υποστήριξης. Εάν όλες οι συντεταγμένες της λύσης υποστήριξης είναι μη αρνητικές, τότε καλείται η βάση στην οποία αντιστοιχεί αυτή η λύση υποστήριξης δεκτός σχέδιο αναφοράς πρόβλημα άμεσου γραμμικού προγραμματισμού, και ονομάζεται η λύση αναφοράς που αντιστοιχεί στην ίδια βάση ψευδοπλάνο διπλό πρόβλημα. Μάλιστα, για να είναι παραδεκτή η βάση, αρκεί η μη αρνητικότητα των συντεταγμένων βάσης. Σημειώστε ότι το σχέδιο αναφοράς είναι ένα εφικτό διάνυσμα του προβλήματος γραμμικού προγραμματισμού ().
Εάν η λύση αναφοράς ικανοποιεί όλους τους περιορισμούς (9) του διπλού προβλήματος, τότε η βάση στην οποία αντιστοιχεί αυτή η λύση αναφοράς ονομάζεται διπλής ισχύος . Στην περίπτωση αυτή καλείται το διάνυσμα σχέδιο αναφοράς πρόβλημα διπλού γραμμικού προγραμματισμού και η λύση αναφοράς που αντιστοιχεί στην ίδια βάση
λέγεται ψευδοπλάνο άμεση εργασία.
Για το διπλό παραδεκτό μιας βάσης, αρκεί να ικανοποιούνται μόνο μη βασικές ανισότητες. Σημειώστε ότι το σχέδιο αναφοράς είναι ένα εφικτό διάνυσμα του προβλήματος διπλού γραμμικού προγραμματισμού ().
Σημειώνουμε τις διαφορές μεταξύ της αριστερής και της δεξιάς πλευράς των ανισώσεων (9) με , . Στη συνέχεια, το διπλό παραδεκτό μιας βάσης μπορεί να διαπιστωθεί ελέγχοντας τη μη αρνητικότητα όλων . Σημειώστε ότι, όπως προκύπτει άμεσα από τον ορισμό, όλα τα υπολείμματα βάσης είναι ίσα με μηδέν ().
Παράδειγμα επίλυσης άμεσου και διπλού προβλήματος χρησιμοποιώντας τη μέθοδο simplex
Επομένως, αρκεί να διασφαλίσουμε ότι οι ανισότητες ισχύουν για όλους.
Θεώρημα 1.ΑφήνωΚαι– λύσεις αναφοράς του προβλήματος γραμμικού προγραμματισμού που αντιστοιχούν σε συγκεκριμένη βάση, τότε ισχύει η ισότητα .
Απόδειξη . Από τους ορισμούς των λύσεων υποστήριξης είναι εύκολο να ληφθούν οι ισότητες
οπότε ακολουθεί η εγκυρότητα του θεωρήματος.
Θεώρημα 2. (Κριτήριο βελτιστοποίησης για λύσεις υποστήριξης) Εάν βάσηείναι ταυτόχρονα παραδεκτό και διπλά παραδεκτό, τότε οι αντίστοιχες λύσεις υποστήριξηςΚαιαποτελούν λύσεις, αντίστοιχα, των προβλημάτων άμεσου και διπλού γραμμικού προγραμματισμού.
Απόδειξη. Η εγκυρότητα αυτής της δήλωσης προκύπτει από τη θεωρία της δυαδικότητας στον γραμμικό προγραμματισμό και το Θεώρημα 1.
Θεώρημα 3.Μια αποδεκτή λύση στο πρόβλημα (1) – (3) είναι ένα σχέδιο αναφοράς του προβλήματος εάν και μόνο εάν είναι η κορυφή ενός κυρτού πολυεδρικού συνόλου.
Απόδειξη. Αφήνω – σχέδιο αναφοράς του προβλήματος (1) – (3). Ας το αποδείξουμε – πάνω από το σετ . Εξ ορισμού, σχέδιο αναφοράς – αποδεκτή λύση αναφοράς που αντιστοιχεί σε κάποια βάση, δηλαδή – επίλυση συστήματος γραμμικών εξισώσεων ως προς τις μεταβλητές
Είναι εύκολο να δει κανείς ότι αυτό το σύστημα έχει μια μοναδική λύση. Αυτό σημαίνει ότι το επίπεδο στήριξης του προσώπου που περιέχει το σημείο , έχει διάσταση 0. Επομένως, – πάνω από το σετ .
Πίσω. Αφήνω – το πάνω μέρος του σετ. Ας το αποδείξουμε – σχέδιο αναφοράς του προβλήματος (1) – (3). Εφόσον είναι κορυφή, είναι μια όψη του συνόλου του οποίου η διάσταση είναι μηδέν. Επομένως, το διάνυσμα υπάρχουν τουλάχιστον μηδενικά συστατικά, το σύνολο των αριθμών των οποίων συμβολίζουμε . Ετσι, – η μόνη λύση στο σύστημα
Οπου . Επομένως, μένει να αποδειχθεί ότι το σύστημα των διανυσμάτων είναι γραμμικά ανεξάρτητο. Ας υποθέσουμε το αντίθετο. Τότε υπάρχουν αριθμοί που δεν είναι όλοι ίσοι με το μηδέν, έτσι ώστε . Να γιατί
Αυτό σημαίνει ότι το σύστημα (12) έχει μια λύση διαφορετική από , πράγμα που έρχεται σε αντίθεση με τη μοναδικότητα της λύσης του. Έτσι, είναι η βάση και το διάνυσμα – το αντίστοιχο σχέδιο αναφοράς του προβλήματος (1) – (3). Αυτό ήταν το ζητούμενο.
Σημειώστε ότι μια αποδεκτή λύση στο πρόβλημα (7), (8) (το διπλό πρόβλημα (1) – (3)) είναι επίσης ένα σχέδιο υποστήριξης εάν και μόνο εάν είναι η κορυφή του αποδεκτού συνόλου.
Ημερομηνία δημοσίευσης: 2015-01-10; Διαβάστε: 695 | Παραβίαση πνευματικών δικαιωμάτων σελίδας
Studopedia.org - Studopedia.Org - 2014-2018 (0,005 s)…
Για βεβαιότητα, υποθέτουμε ότι το πρόβλημα που επιλύεται είναι να βρεθεί το ελάχιστο.
1. Μειώστε το πρόβλημα γραμμικού προγραμματισμού σε κανονική μορφή.
Μετά την εισαγωγή πρόσθετων μεταβλητό σύστημαΟι εξισώσεις και μια γραμμική συνάρτηση γράφονται με μια μορφή που ονομάζεται εκτεταμένο σύστημα:
Υποθέτουμε ότι όλες οι πρόσθετες μεταβλητές έχουν το ίδιο πρόσημο με τους ελεύθερους όρους. αλλιώς χρησιμοποιούμε το λεγόμενο Μ– μια μέθοδος που θα συζητηθεί παρακάτω.
2. Ορίστε βασικές και ελεύθερες μεταβλητές.
3. Εισάγουμε το αρχικό εκτεταμένο σύστημα στον πρώτο πίνακα simplex. Η τελευταία σειρά του πίνακα, που δίνει την εξίσωση για γραμμική συνάρτησηονομάζονται στόχοι εκτίμηση. Δείχνει τους συντελεστές της συνάρτησης στόχου. Στην αριστερή στήλη του πίνακα σημειώνουμε τις κύριες μεταβλητές (βάση), στις επόμενες στήλες σημειώνουμε τους συντελεστές για τις ελεύθερες μεταβλητές. Η προτελευταία στήλη περιέχει ελεύθερα μέλη του εκτεταμένου συστήματος. Η τελευταία στήλη προετοιμάζεται για τις σχέσεις εκτίμησης που απαιτούνται για τον προσδιορισμό της βασικής μεταβλητής με βάση τη σχέση (6.29).
4. Προσδιορίστε τη δυνατότητα επίλυσης του προβλήματος με τιμές σύμφωνα με τα Θεωρήματα 6.7,…, 6.9.
5. Επιλέξτε το στοιχείο επίλυσης (αναφοράς).
Επίλυση προβλήματος παραγωγής με τη μέθοδο του απλού πίνακα
Εάν δεν πληρούται το κριτήριο βελτιστοποίησης (δεν πληρούνται οι προϋποθέσεις του Θεωρήματος 6.7 ή 6.8), τότε ο μεγαλύτερος απόλυτος αρνητικός συντελεστής στην τελευταία σειρά καθορίζει τη στήλη επίλυσης (αναφοράς). 
.
Συνθέτουμε τις εκτιμώμενες αναλογίες κάθε γραμμής σύμφωνα με τους ακόλουθους κανόνες:
1 0) εάν όλα και έχουν διαφορετικά πρόσημα.
2 0) αν όλα και ;
3 0) αν ;
4 0) 0 αν και ;
5 0) εάν και έχουν τα ίδια σημάδια.
Ας ορίσουμε. Εάν δεν υπάρχει τελικό ελάχιστο, τότε το πρόβλημα δεν έχει τελικό βέλτιστο (). Εάν το ελάχιστο είναι πεπερασμένο, τότε επιλέξτε τη γραμμή q, στο οποίο επιτυγχάνεται (οποιοδήποτε, αν υπάρχουν πολλά από αυτά), και ονομάστε το τη γραμμή επίλυσης (αναφοράς). Στη διασταύρωση της γραμμής και της στήλης επίλυσης υπάρχει ένα στοιχείο επίλυσης (αναφοράς).
6 0) Μεταβείτε στον επόμενο πίνακα σύμφωνα με τους κανόνες:
α) στην αριστερή στήλη γράφουμε μια νέα βάση: αντί για την κύρια μεταβλητή - μια μεταβλητή, δηλ. Ας ανταλλάξουμε τις μεταβλητές και ;
β) τοποθετήστε 1 στη θέση του στοιχείου στήριξης.
γ) αφήστε τα στοιχεία του αρχικού πίνακα στις υπόλοιπες θέσεις της σειράς αναφοράς στον νέο πίνακα.
δ) στις υπόλοιπες θέσεις στη στήλη αναφοράς, βάλτε τα αντίστοιχα στοιχεία του αρχικού πίνακα, πολλαπλασιαζόμενα επί –1.
δ) για τα υπόλοιπα ελεύθερες θέσειςστοιχεία , , στον νέο πίνακα γράψτε τους αριθμούς , , , που βρίσκονται ως εξής:
Για να απλοποιηθούν οι υπολογισμοί χρησιμοποιώντας αυτούς τους τύπους, μπορούν να διατυπωθούν ως "Κανόνες ορθογωνίου"(Εικ. 6.8): τα στοιχεία στις διαγώνιες ενός ορθογωνίου με κορυφές (ή , , , , ή , , , ) πολλαπλασιάζονται (το γινόμενο που δεν περιέχει το στοιχείο στήριξης λαμβάνεται με αρνητικό πρόσημο) και τα γινόμενα που προκύπτουν είναι προστέθηκε?
στ) διαιρέστε όλα τα ληφθέντα στοιχεία του νέου πίνακα με το στοιχείο αναφοράς.
7 0) Χρησιμοποιώντας την τιμή του στοιχείου, προσδιορίστε εάν έχει βρεθεί η βέλτιστη τιμή της αντικειμενικής συνάρτησης. Εάν η απάντηση είναι αρνητική, συνεχίστε την απόφαση (επιστροφή στο σημείο 6).
Ρύζι. 6.8. Κανόνας ορθογωνίου για τον προσδιορισμό των αριθμών:
α − , β − , γ − .
Εξετάζεται ένας αλγόριθμος για τη μετατροπή πινάκων simplex για μη εκφυλισμένες αποδεκτές βασικές λύσεις, δηλ. η κατάσταση που περιγράφεται στο Θεώρημα 6.9 εκπληρώθηκε. Εάν το αρχικό πρόβλημα γραμμικού προγραμματισμού είναι εκφυλισμένο, τότε κατά την επίλυσή του χρησιμοποιώντας τη μέθοδο simplex, μπορεί να εμφανιστούν εκφυλισμένες βασικές λύσεις. Σε αυτή την περίπτωση, είναι δυνατά βήματα αδράνειας της μεθόδου simplex, π.χ. επαναλήψεις στις οποίες φά(Χ)δεν αλλάζει. Το looping είναι επίσης δυνατό, δηλ. μια ατελείωτη ακολουθία αδρανών βημάτων. Για την αποτροπή του, έχουν αναπτυχθεί ειδικοί αλγόριθμοι - αντικυκλίνες. Ωστόσο, στη συντριπτική πλειονότητα των περιπτώσεων, τα βήματα αδράνειας αντικαθίστανται από βήματα με μείωση της αντικειμενικής συνάρτησης και η διαδικασία επίλυσης ολοκληρώνεται ως αποτέλεσμα ενός πεπερασμένου αριθμού επαναλήψεων.
Παράδειγμα 6.8.Λύστε το πρόβλημα που δίνεται στο παράδειγμα 6.7 χρησιμοποιώντας τη μέθοδο simplex.
⇐ Προηγούμενο45678910111213Επόμενο ⇒
Ημερομηνία δημοσίευσης: 2015-01-23; Διαβάστε: 174 | Παραβίαση πνευματικών δικαιωμάτων σελίδας
Studopedia.org - Studopedia.Org - 2014-2018 (0,002 s)…
Αρχική >> Παράδειγμα αρ. 3. Μέθοδος Simplex. Εύρεση της μεγαλύτερης τιμής μιας συνάρτησης (τεχνητή βάση)
Μέθοδος Simplex
| — | x 1 | + | x 2 | ≥ | 1 | |
| x 1 | + | 3 | x 2 | ≤ | 15 | |
| — | 2 | x 1 | + | x 2 | ≤ | 4 |
| Μια μεταβλητή ονομάζεται βασική για μια δεδομένη εξίσωση εάν περιλαμβάνεται σε δεδομένη εξίσωσημε συντελεστή ένα και δεν περιλαμβάνεται στις υπόλοιπες εξισώσεις (εφόσον υπάρχει θετικός αριθμός στη δεξιά πλευρά της εξίσωσης). Εάν κάθε εξίσωση έχει μια μεταβλητή βάσης, τότε το σύστημα λέγεται ότι έχει μια βάση. Η ιδέα της μεθόδου simplex είναι η μετάβαση από τη μια βάση στην άλλη, λαμβάνοντας μια τιμή συνάρτησης που δεν είναι τουλάχιστον μικρότερη από την υπάρχουσα (κάθε βάση αντιστοιχεί σε μια μεμονωμένη τιμή συνάρτησης). Πώς πραγματοποιείται η μετάβαση από τη μια βάση στην άλλη; |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> W = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | Αγ. μέλος | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | W - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 0 |
| x 1 | x 2 | S 1 | S 2 | S 3 | Αγ. μέλος | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F - 13 |
| S 1 = 0 S 2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
Δεν υπάρχουν θετικοί συντελεστές μεταξύ των επιλεγμένων συντελεστών σειρών. Επομένως βρέθηκε υψηλότερη τιμήσυναρτήσεις ΣΤ.
Απάντηση:
x 1 = 3 x 2 = 4
F max = 13
Πηγαίνετε στη λύση του προβλήματός σας
© 2010-2018, για οποιεσδήποτε ερωτήσεις παρακαλώ γράψτε στο [email προστατευμένο]
Το έργο
Για την πώληση τριών ομάδων αγαθών, μια εμπορική επιχείρηση διαθέτει τρεις τύπους περιορισμένων υλικών και νομισματικών πόρων στο ποσό των b 1 = 240, b 2 = 200, b 3 = 160 μονάδες. Ταυτόχρονα, για την πώληση 1 ομάδας αγαθών για 1 χιλιάδες ρούβλια. κύκλος εργασιών εμπορευμάτων, ο πόρος του πρώτου τύπου καταναλώνεται σε ποσότητα 11 = 2 μονάδες, ο πόρος του δεύτερου τύπου σε ποσότητα α 21 = 4 μονάδες, ο πόρος του τρίτου τύπου σε ποσότητα 31 = 4 μονάδες. Για την πώληση 2 και 3 ομάδων αγαθών για 1 χιλιάδες ρούβλια. Ο κύκλος εργασιών καταναλώνεται σύμφωνα με τον πόρο του πρώτου τύπου σε ποσότητα 12 = 3, α 13 = 6 μονάδες, ο πόρος του δεύτερου τύπου σε ποσότητα 22 = 2, α 23 = 4 μονάδες, ο πόρος του ο τρίτος τύπος στο ποσό των a 32 = 6, a 33 = 8 μονάδες . Κέρδος από την πώληση τριών ομάδων αγαθών ανά 1 χιλ.
Μέθοδος Simplex για την επίλυση ZLP
τρίψιμο. ο κύκλος εργασιών είναι αντίστοιχα c 1 = 4, c 2 = 5, c 3 = 4 (χιλιάδες ρούβλια). Προσδιορίστε τον προγραμματισμένο όγκο και τη δομή του εμπορικού κύκλου εργασιών έτσι ώστε το κέρδος εμπορική επιχείρησηήταν το μέγιστο.
Στο άμεσο πρόβλημα του προγραμματισμού κύκλου εργασιών, επιλύεται με μέθοδο simplex, συνθέτω διπλό πρόβλημαγραμμικός προγραμματισμός.
Εγκαθιστώ συζευγμένα ζεύγη μεταβλητώνάμεσα και διπλά προβλήματα.
Σύμφωνα με συζυγή ζεύγη μεταβλητών, από τη λύση του άμεσου προβλήματος προκύπτει λύση του διπλού προβλήματος, στο οποίο παράγεται αξιολόγηση πόρων, δαπανώνται για την πώληση αγαθών.
Επίλυση του προβλήματος με τη μέθοδο simplex
Έστω x 1, x 2, x 3 ο αριθμός των προϊόντων που πωλήθηκαν, σε χιλιάδες ρούβλια, 1, 2, 3 - οι ομάδες της, αντίστοιχα. Επειτα μαθηματικό μοντέλοη εργασία έχει τη μορφή:
F = 4 x 1 + 5 x 2 + 4 x 3 ->μέγ
Λύνουμε τη μέθοδο simplex.
Εισάγουμε πρόσθετες μεταβλητές x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 για να μετατρέψουμε τις ανισότητες σε ισότητες.
Ας πάρουμε ως βάση το x 4 = 240. x 5 = 200; x 6 = 160.
Εισάγουμε τα δεδομένα πίνακας simplex
Πίνακας Simplex Νο. 1
Αντικειμενική λειτουργία:
0 240 + 0 200 + 0 160 = 0
Υπολογίζουμε τις εκτιμήσεις χρησιμοποιώντας τον τύπο:
Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0
Δεδομένου ότι υπάρχουν αρνητικές εκτιμήσεις, το σχέδιο δεν είναι βέλτιστο. Χαμηλότερη βαθμολογία:
Εισάγουμε τη μεταβλητή x 2 στη βάση.
Ορίζουμε μια μεταβλητή που προκύπτει από τη βάση. Για να γίνει αυτό, βρίσκουμε τη μικρότερη μη αρνητική αναλογία για τη στήλη x2.
= 26.667
Μικρότερο μη αρνητικό: Q 3 = 26.667. Από τη βάση εξάγουμε τη μεταβλητή x 6
Διαιρέστε την 3η γραμμή με το 6.
Από την 1η γραμμή, αφαιρέστε την 3η γραμμή, πολλαπλασιαζόμενη επί 3
Από τη 2η γραμμή, αφαιρέστε την 3η γραμμή, πολλαπλασιαζόμενη επί 2
Υπολογίζουμε:
Παίρνουμε έναν νέο πίνακα:
Πίνακας Simplex Νο. 2
Αντικειμενική λειτουργία:
0 160 + 0 440/3 + 5 80/3 = 400/3
Υπολογίζουμε τις εκτιμήσεις χρησιμοποιώντας τον τύπο:
Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1)/3 + 5 1/6 - 0 = 5/6
Εφόσον υπάρχει αρνητική εκτίμηση Δ 1 = - 2/3, το σχέδιο δεν είναι βέλτιστο.
Εισάγουμε τη μεταβλητή x 1 στη βάση.
Ορίζουμε μια μεταβλητή που προκύπτει από τη βάση. Για να γίνει αυτό, βρίσκουμε τη μικρότερη μη αρνητική αναλογία για τη στήλη x 1.
Μικρότερο μη αρνητικό: Q 3 = 40. Εξάγουμε τη μεταβλητή x 2 από τη βάση
Διαιρέστε την 3η γραμμή με τα 2/3.
Από τη 2η γραμμή, αφαιρέστε την 3η γραμμή, πολλαπλασιαζόμενη επί 8/3
Υπολογίζουμε:
Παίρνουμε έναν νέο πίνακα:
Πίνακας Simplex Νο. 3
Αντικειμενική λειτουργία:
0 160 + 0 40 + 4 40 = 160
Υπολογίζουμε τις εκτιμήσεις χρησιμοποιώντας τον τύπο:
Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1) + 4 1/4 - 0 = 1
Δεδομένου ότι δεν υπάρχουν αρνητικές αξιολογήσεις, το σχέδιο είναι βέλτιστο.
Η λύση του προβλήματος:
Απάντηση
x 1 = 40; x2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x6 = 0; F max = 160
Δηλαδή, είναι απαραίτητο να πουληθεί ο πρώτος τύπος αγαθών στο ποσό των 40 χιλιάδων.
τρίψιμο. Τα προϊόντα των τύπων 2 και 3 δεν χρειάζεται να πωληθούν. Σε αυτή την περίπτωση, το μέγιστο κέρδος θα είναι F max = 160 χιλιάδες ρούβλια.
Λύση του διπλού προβλήματος
Το διπλό πρόβλημα έχει τη μορφή:
Z = 240 y 1 + 200 y 2 + 160 y 3 -> min
Εισάγουμε πρόσθετες μεταβλητές y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 για να μετατρέψουμε τις ανισότητες σε ισότητες.
Τα συζευγμένα ζεύγη μεταβλητών του άμεσου και του διπλού προβλημάτων έχουν τη μορφή:
Από τον τελευταίο πίνακα Simplex Νο. 3 του άμεσου προβλήματος, βρίσκουμε τη λύση στο διπλό πρόβλημα:
Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;
Απάντηση
y 1 = 0; y2 = 0; y 3 = 1; Z min = 160;
Η μέθοδος simplex είναι μια υπολογιστική διαδικασία που βασίζεται στην αρχή της διαδοχικής βελτίωσης των λύσεων κατά τη μετάβαση από ένα σημείο βάσης (βασική λύση) στο άλλο. Σε αυτήν την περίπτωση, η τιμή της αντικειμενικής συνάρτησης βελτιώνεται.
Η βασική λύση είναι μία από τις αποδεκτές λύσεις που βρίσκονται στις κορυφές της περιοχής των αποδεκτών τιμών. Ελέγχοντας κορυφή μετά από κορυφή του απλού για βέλτιστη, φτάνουν στο επιθυμητό βέλτιστο. Η μέθοδος simplex βασίζεται σε αυτήν την αρχή.
Ένα απλό είναι ένα κυρτό πολύγωνο σε ν-διάστατο χώρο με n+1 κορυφές που δεν βρίσκονται στο ίδιο υπερεπίπεδο (το υπερεπίπεδο διαιρεί το χώρο σε δύο ημιδιάστημα).
Για παράδειγμα, η γραμμή των περιορισμών του προϋπολογισμού διαιρεί τα αγαθά σε διαθέσιμα και μη διαθέσιμα.
Έχει αποδειχθεί ότι εάν υπάρχει μια βέλτιστη λύση, τότε σίγουρα θα βρεθεί μετά από έναν πεπερασμένο αριθμό επαναλήψεων (βημάτων), εκτός από τις περιπτώσεις «ποδηλασίας».
Ο αλγόριθμος της μεθόδου simplex αποτελείται από διάφορα στάδια.
Πρώτο στάδιο. Δημιουργείται ένα αρχικό μοντέλο βελτιστοποίησης. Στη συνέχεια, ο αρχικός πίνακας συνθηκών μετατρέπεται στη μειωμένη κανονική μορφή, η οποία, μεταξύ όλων των άλλων κανονικών μορφών, διακρίνεται από το γεγονός ότι:
α) οι δεξιές πλευρές των συνθηκών (ελεύθεροι όροι bi) είναι μη αρνητικές ποσότητες.
β) οι ίδιες οι συνθήκες είναι ισότητες.
γ) ο πίνακας συνθηκών περιέχει έναν πλήρη υπομήτρα μονάδας.
Εάν οι ελεύθεροι όροι είναι αρνητικοί, τότε και οι δύο πλευρές της ανισότητας πολλαπλασιάζονται με - 1 και το πρόσημο της ανισότητας αντιστρέφεται. Για να μετατραπούν οι ανισότητες σε ισότητες, εισάγονται πρόσθετες μεταβλητές, οι οποίες συνήθως υποδεικνύουν την ποσότητα των πόρων που υποχρησιμοποιήθηκαν. Αυτή είναι η οικονομική τους σημασία.
Τέλος, εάν, μετά την προσθήκη πρόσθετων μεταβλητών, ο πίνακας συνθηκών δεν περιέχει πλήρη υπομήτρα ταυτότητας, τότε εισάγονται τεχνητές μεταβλητές που δεν έχουν κανένα οικονομικό νόημα. Εισάγονται αποκλειστικά για να αποκτήσουν τον υπομήτρα ταυτότητας και να ξεκινήσουν τη διαδικασία επίλυσης του προβλήματος χρησιμοποιώντας τη μέθοδο simplex.
Σε μια βέλτιστη λύση στο πρόβλημα, όλες οι τεχνητές μεταβλητές (AI) πρέπει να είναι ίσες με μηδέν. Για να γίνει αυτό, εισάγονται τεχνητές μεταβλητές στην αντικειμενική συνάρτηση του προβλήματος με μεγάλους αρνητικούς συντελεστές (-M) κατά την επίλυση του προβλήματος στο μέγιστο, και με μεγάλους θετικούς συντελεστές (+M) όταν το πρόβλημα επιλύεται στο ελάχιστο. Σε αυτήν την περίπτωση, ακόμη και μια ασήμαντη μη μηδενική τιμή της τεχνητής μεταβλητής θα μειώσει (αυξήσει) απότομα την τιμή της αντικειμενικής συνάρτησης. Συνήθως, το M πρέπει να είναι 1000 φορές μεγαλύτερο από τις τιμές των συντελεστών για τις κύριες μεταβλητές.
Δεύτερη φάση. Κατασκευάζεται ένας αρχικός πίνακας simplex και βρίσκεται κάποια αρχική βασική λύση. Το σύνολο των μεταβλητών που σχηματίζουν τον υπομήτρα ταυτότητας λαμβάνεται ως η αρχική λύση βάσης. Οι τιμές αυτών των μεταβλητών είναι ίσες με τους ελεύθερους όρους. Όλες οι άλλες μεταβλητές εκτός βάσης είναι μηδενικές.
Τρίτο στάδιο. Ο έλεγχος της βασικής λύσης για βελτιστοποίηση πραγματοποιείται χρησιμοποιώντας ειδικές εκτιμήσεις των συντελεστών της αντικειμενικής συνάρτησης. Εάν όλες οι εκτιμήσεις των συντελεστών της αντικειμενικής συνάρτησης είναι αρνητικές ή ίσες με μηδέν, τότε η υπάρχουσα βασική λύση είναι βέλτιστη. Εάν τουλάχιστον μία εκτίμηση του συντελεστή αντικειμενικής συνάρτησης είναι μεγαλύτερη από το μηδέν, τότε η υπάρχουσα βασική λύση δεν είναι βέλτιστη και πρέπει να βελτιωθεί.
Τέταρτο στάδιο. Μετάβαση σε μια νέα βασική λύση. Προφανώς, το βέλτιστο σχέδιο θα πρέπει να περιλαμβάνει μια μεταβλητή που αυξάνει την αντικειμενική συνάρτηση στο μέγιστο βαθμό. Κατά την επίλυση προβλημάτων για μέγιστο κέρδος, το βέλτιστο σχέδιο περιλαμβάνει προϊόντα των οποίων η παραγωγή είναι πιο κερδοφόρα. Αυτό καθορίζεται από το μέγιστο θετική αξίαεκτίμηση του συντελεστή της αντικειμενικής συνάρτησης.
Η στήλη του πίνακα simplex με αυτόν τον αριθμό σε αυτήν την επανάληψη ονομάζεται γενική στήλη.
Για να βρεθεί η γενική σειρά, όλα τα ελεύθερα μέλη (πόροι) χωρίζονται στα αντίστοιχα στοιχεία της γενικής στήλης (ποσοστό κατανάλωσης πόρων ανά μονάδα προϊόντος). Το μικρότερο επιλέγεται από τα αποτελέσματα που λαμβάνονται. Η αντίστοιχη γραμμή σε μια δεδομένη επανάληψη ονομάζεται γενική γραμμή. Αντιστοιχεί στον πόρο που περιορίζει την παραγωγή σε μια δεδομένη επανάληψη.
Ένα στοιχείο ενός πίνακα simplex που βρίσκεται στην τομή μιας γενικής στήλης και μιας γραμμής ονομάζεται γενικό στοιχείο.
Στη συνέχεια, όλα τα στοιχεία της γενικής συμβολοσειράς (συμπεριλαμβανομένου του ελεύθερου μέλους) χωρίζονται στο γενικό στοιχείο. Ως αποτέλεσμα αυτής της λειτουργίας, το γενικό στοιχείο γίνεται ίσο με ένα. Στη συνέχεια, είναι απαραίτητο όλα τα άλλα στοιχεία της γενικής στήλης να γίνουν ίσα με μηδέν, δηλ. η γενική στήλη πρέπει να γίνει ενιαία. Όλες οι γραμμές (εκτός από τη γενική) μετατρέπονται ως εξής. Τα στοιχεία της νέας σειράς που προκύπτουν πολλαπλασιάζονται με το αντίστοιχο στοιχείο της γενικής στήλης και το γινόμενο που προκύπτει αφαιρείται από τα στοιχεία της παλιάς σειράς.
Λαμβάνουμε τις τιμές των νέων βασικών μεταβλητών στα αντίστοιχα κελιά της στήλης των ελεύθερων όρων.
Πέμπτο στάδιο. Η προκύπτουσα βασική λύση ελέγχεται ως προς τη βέλτιστη λειτουργία (δείτε το τρίτο στάδιο). Εάν είναι βέλτιστο, τότε οι υπολογισμοί σταματούν. Διαφορετικά, είναι απαραίτητο να βρεθεί μια νέα βασική λύση (τέταρτο στάδιο) κ.λπ.
Μέθοδος Simplex
Παράδειγμα επίλυσης προβλημάτων βελτιστοποίησης γραμμικού προγραμματισμού με χρήση της μεθόδου simplex
Ας είναι απαραίτητο να βρεθεί το βέλτιστο σχέδιο για την παραγωγή δύο τύπων προϊόντων (x1 και x2).
Αρχικά δεδομένα:
Ας δημιουργήσουμε ένα μοντέλο βελτιστοποίησης
– περιορισμός πόρων A;
– περιορισμός πόρων Β.
Ας περιορίσουμε το πρόβλημα στη μειωμένη κανονική μορφή. Για να γίνει αυτό, αρκεί να εισαγάγετε πρόσθετες μεταβλητές X3 και X4. Ως αποτέλεσμα, οι ανισότητες μετατρέπονται σε αυστηρές ισότητες.
Ας φτιάξουμε τον αρχικό πίνακα simplex και ας βρούμε την αρχική βασική λύση. Θα είναι πρόσθετες μεταβλητές, καθώς αντιστοιχούν σε έναν υπομήτρα μονάδας.
1η επανάληψη. Βρείτε τη γενική στήλη και τη γενική γραμμή:
Το γενικό στοιχείο είναι 5.
2η επανάληψη. Η βασική λύση που βρέθηκε δεν είναι η βέλτιστη, γιατί η γραμμή βαθμολογίας (Fj-Cj) περιέχει ένα θετικό στοιχείο. Βρείτε τη γενική στήλη και τη γενική γραμμή:
max(0,0,3,-1,4,0) = 0,2
Η λύση που βρέθηκε είναι βέλτιστη, αφού τα πάντα ειδικές αξιολογήσειςοι αντικειμενικές συναρτήσεις Fj – Cj είναι ίσες με μηδέν ή αρνητικές. F(x)=29 x1=2; x2=5.
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | |||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| - | x 1 | + | x 2 | - | S 1 | + | R 1 | = | 1 | |||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> W = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | Αγ. μέλος | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | W - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 0 |
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| 4 | x 1 | + | 3 | S 1 | + | S 2 | = | 12 | |||||||||
| - | x 1 | + | S 1 | + | S 3 | = | 3 |
| x 1 | x 2 | S 1 | S 2 | S 3 | Αγ. μέλος | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F - 13 |
| S 1 = 0 S 2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |