Μέθοδος Simplex για επίλυση γραμμικού προγραμματισμού. Γραμμικός προγραμματισμός. Μέθοδος Simplex
Ας σκεφτούμε μέθοδο simplexγια την επίλυση προβλημάτων γραμμικού προγραμματισμού (LP). Βασίζεται στη μετάβαση από το ένα σχέδιο αναφοράς στο άλλο, κατά την οποία αυξάνεται η τιμή της αντικειμενικής συνάρτησης.
Ο αλγόριθμος της μεθόδου simplex έχει ως εξής:
- Μετατρέπουμε το αρχικό πρόβλημα σε κανονική μορφή εισάγοντας πρόσθετες μεταβλητές. Για ανισότητες της μορφής ≤, εισάγονται πρόσθετες μεταβλητές με πρόσημο (+), αλλά αν της μορφής ≥, τότε με πρόσημο (-). Πρόσθετες μεταβλητές εισάγονται στην αντικειμενική συνάρτηση με αντίστοιχα πρόσημα με συντελεστή ίσο με 0 , επειδή η συνάρτηση στόχος δεν πρέπει να αλλάξει την οικονομική της σημασία.
- Τα διανύσματα καταγράφονται Πιαπό τους συντελεστές των μεταβλητών και τη στήλη των ελεύθερων όρων. Αυτή η ενέργεια καθορίζει τον αριθμό των μοναδιαίων διανυσμάτων. Ο κανόνας είναι ότι πρέπει να υπάρχουν τόσα μοναδιαία διανύσματα όσες και ανισότητες στο σύστημα των περιορισμών.
- Μετά από αυτό, τα δεδομένα προέλευσης εισάγονται σε έναν πίνακα simplex. Τα μοναδιαία διανύσματα εισάγονται στη βάση και με την εξαίρεση τους από τη βάση, βρίσκεται η βέλτιστη λύση. Οι συντελεστές της αντικειμενικής συνάρτησης γράφονται με το αντίθετο πρόσημο.
- Ένα σημάδι βελτιστοποίησης για ένα πρόβλημα LP είναι ότι η λύση είναι βέλτιστη εάν υπάρχει φά– στη σειρά όλοι οι συντελεστές είναι θετικοί. Κανόνας για την εύρεση της στήλης ενεργοποίησης - προβλήθηκε φά– μια συμβολοσειρά και από τα αρνητικά της στοιχεία επιλέγεται το μικρότερο. Διάνυσμα Πιη περιεκτικότητά του γίνεται επιτρεπτή. Ο κανόνας για την επιλογή ενός στοιχείου επίλυσης - συντάσσονται οι λόγοι των θετικών στοιχείων της στήλης ανάλυσης προς τα στοιχεία του διανύσματος P 0και ο αριθμός που δίνει τη μικρότερη αναλογία γίνεται το στοιχείο επίλυσης ως προς το οποίο θα υπολογιστεί εκ νέου ο πίνακας simplex. Η γραμμή που περιέχει αυτό το στοιχείο ονομάζεται γραμμή ενεργοποίησης. Εάν δεν υπάρχουν θετικά στοιχεία στη στήλη επίλυσης, τότε το πρόβλημα δεν έχει λύση. Αφού προσδιορίσουν το στοιχείο επίλυσης, προχωρούν σε επανυπολογισμό ενός νέου πίνακα απλούστερου.
- Κανόνες για τη συμπλήρωση ενός νέου πίνακα simplex. Η μονάδα τοποθετείται στη θέση του στοιχείου επίλυσης και τα άλλα στοιχεία θεωρούνται ίσα 0 . Το διάνυσμα επίλυσης προστίθεται στη βάση, από την οποία εξαιρείται το αντίστοιχο μηδενικό διάνυσμα και τα υπόλοιπα διανύσματα βάσης γράφονται χωρίς αλλαγές. Τα στοιχεία της γραμμής ανάλυσης διαιρούνται με το στοιχείο ανάλυσης και τα υπόλοιπα στοιχεία υπολογίζονται εκ νέου σύμφωνα με τον κανόνα του ορθογωνίου.
- Αυτό γίνεται μέχρι φά– όλα τα στοιχεία της χορδής δεν θα γίνουν θετικά.
Ας εξετάσουμε την επίλυση του προβλήματος χρησιμοποιώντας τον αλγόριθμο που συζητήθηκε παραπάνω.
Δεδομένος:
Φέρνουμε το πρόβλημα σε κανονική μορφή:
Συνθέτουμε τα διανύσματα:
Συμπληρώστε τον πίνακα simplex:
:
Ας υπολογίσουμε εκ νέου το πρώτο στοιχείο του διανύσματος P 0, για το οποίο φτιάχνουμε ένα ορθογώνιο αριθμών: και παίρνουμε: 
.
Εκτελούμε παρόμοιους υπολογισμούς για όλα τα άλλα στοιχεία του πίνακα simplex:
Στο ληφθέν σχέδιο φά- η γραμμή περιέχει ένα αρνητικό στοιχείο - · (-5/3), διάνυσμα Σ 1. Περιέχει στη στήλη του ένα μόνο θετικό στοιχείο, το οποίο θα είναι το στοιχείο ενεργοποίησης. Ας υπολογίσουμε ξανά τον πίνακα σχετικά με αυτό το στοιχείο:
Δεν υπάρχουν αρνητικά στοιχεία φά– γραμμή σημαίνει βρέθηκε βέλτιστο σχέδιο:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).
- Ashmanov S. A. Γραμμικός προγραμματισμός, M: Nauka, 1998,
- Βέντσελ Ε.Σ. Operations Research, M: Σοβιετικό Ραδιόφωνο, 2001,
- Kuznetsov Yu.N., Kuzubov V.I., Voloshenko A.B. Μαθηματικός προγραμματισμός, Μ: Ανώτατο Σχολείο, 1986.
Προσαρμοσμένη Λύση Γραμμικού Προγραμματισμού
Μπορείτε να παραγγείλετε οποιεσδήποτε εργασίες σε αυτόν τον κλάδο στον ιστότοπό μας. Μπορείτε να επισυνάψετε αρχεία και να καθορίσετε προθεσμίες στις
Μία από τις μεθόδους για την επίλυση προβλημάτων βελτιστοποίησης ( συνήθως συνδέεται με την εύρεση του ελάχιστου ή του μέγιστου) ο γραμμικός προγραμματισμός ονομάζεται . Μέθοδος Simplexπεριλαμβάνει μια ολόκληρη ομάδα αλγορίθμων και μεθόδων για την επίλυση προβλημάτων γραμμικού προγραμματισμού. Μία από αυτές τις μεθόδους, η οποία περιλαμβάνει την καταγραφή των δεδομένων προέλευσης και τον επανυπολογισμό τους σε έναν ειδικό πίνακα, ονομάζεται μέθοδος απλού πίνακα.
Ας εξετάσουμε τον αλγόριθμο της μεθόδου του απλού πίνακα χρησιμοποιώντας το παράδειγμα της λύσης έργο παραγωγής, το οποίο καταλήγει στην εύρεση ενός σχεδίου παραγωγής που εξασφαλίζει το μέγιστο κέρδος.
Εισαγωγή δεδομένων για το πρόβλημα της μεθόδου simplex
Η εταιρεία παράγει 4 είδη προϊόντων μεταποιώντας τα σε 3 μηχανήματα.
Τα χρονικά πρότυπα (ελάχ./τεμάχιο) για την επεξεργασία προϊόντων σε μηχανές καθορίζονται από τον πίνακα Α:
Το ταμείο χρόνου λειτουργίας του μηχανήματος (ελάχ.) καθορίζεται στον πίνακα Β:
Το κέρδος από την πώληση κάθε μονάδας προϊόντος (RUB/τεμάχιο) δίνεται από τον πίνακα C:
Σκοπός του έργου παραγωγής
Καταρτίστε ένα σχέδιο παραγωγής που θα μεγιστοποιήσει το κέρδος της επιχείρησης.
Επίλυση του προβλήματος με τη μέθοδο του απλού πίνακα
(1) Ας υποδηλώσουμε με Χ1, Χ2, Χ3, Χ4 τον προγραμματισμένο αριθμό προϊόντων κάθε τύπου. Τότε το επιθυμητό σχέδιο: ( Χ1, Χ2, Χ3, Χ4)
(2) Ας γράψουμε τους περιορισμούς του σχεδίου με τη μορφή ενός συστήματος εξισώσεων:
(3) Τότε το κέρδος-στόχος είναι:
Δηλαδή, το κέρδος από την εκπλήρωση του σχεδίου παραγωγής θα πρέπει να είναι μέγιστο.
(4) Για να λύσουμε το προκύπτον πρόβλημα ακραίου υπό όρους, αντικαθιστούμε το σύστημα των ανισοτήτων με ένα σύστημα γραμμικών εξισώσεων εισάγοντας επιπλέον μη αρνητικές μεταβλητές σε αυτό ( Χ5, Χ6, Χ7).
(5) Ας δεχτούμε το εξής σχέδιο αναφοράς:
X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80
(6) Ας εισάγουμε τα δεδομένα πίνακας simplex:
Στην τελευταία γραμμή εισάγουμε τους συντελεστές της αντικειμενικής συνάρτησης και την ίδια την τιμή της με το αντίθετο πρόσημο.
(7) Επιλέξτε στην τελευταία γραμμή μέγιστος (modulo) ένας αρνητικός αριθμός.
Ας υπολογίσουμε b = N / Items_of_the_selected_column
Μεταξύ των υπολογισμένων τιμών του b επιλέγουμε ελάχιστα.
Η τομή της επιλεγμένης στήλης και γραμμής θα μας δώσει το στοιχείο επίλυσης. Αλλάζουμε τη βάση σε μια μεταβλητή που αντιστοιχεί στο στοιχείο επίλυσης ( Χ5 έως Χ1).
- Το ίδιο το στοιχείο επίλυσης μετατρέπεται σε 1.
- Για στοιχεία της γραμμής ανάλυσης – a ij (*) = a ij / RE ( δηλαδή διαιρούμε κάθε στοιχείο με την τιμή του στοιχείου επίλυσης και λαμβάνουμε νέα δεδομένα).
- Για στοιχεία της στήλης ανάλυσης, απλώς μηδενίζονται.
- Υπολογίζουμε ξανά τα υπόλοιπα στοιχεία του πίνακα χρησιμοποιώντας τον κανόνα του ορθογωνίου.
a ij (*) = a ij – (A * B / RE)
Όπως μπορείτε να δείτε, παίρνουμε το τρέχον κελί που επανυπολογίζεται και το κελί με το στοιχείο επίλυσης. Σχηματίζουν αντίθετες γωνίες του ορθογωνίου. Στη συνέχεια, πολλαπλασιάζουμε τις τιμές από τα κελιά των άλλων 2 γωνιών αυτού του ορθογωνίου. Αυτή η δουλειά ( ΕΝΑ * σι) διαιρέστε με το στοιχείο επίλυσης ( ΣΧΕΤΙΚΑ ΜΕ). Και αφαιρέστε από το τρέχον κελί που επανυπολογίζεται ( ένα ij) τι συνέβη. Παίρνουμε μια νέα τιμή - a ij (*).
(9) Ελέγξτε ξανά την τελευταία γραμμή ( ντο) επί παρουσία αρνητικών αριθμών. Εάν δεν υπάρχουν, έχει βρεθεί το βέλτιστο σχέδιο, προχωράμε στο τελευταίο στάδιο επίλυσης του προβλήματος. Εάν υπάρχει, το σχέδιο δεν είναι ακόμη βέλτιστο και ο πίνακας simplex πρέπει να υπολογιστεί ξανά.
Εφόσον έχουμε και πάλι αρνητικούς αριθμούς στην τελευταία γραμμή, ξεκινάμε μια νέα επανάληψη των υπολογισμών.
(10) Δεδομένου ότι δεν υπάρχουν αρνητικά στοιχεία στην τελευταία γραμμή, αυτό σημαίνει ότι βρήκαμε το βέλτιστο σχέδιο παραγωγής! Δηλαδή: θα παράγουμε εκείνα τα προϊόντα που έχουν μετακινηθεί στη στήλη "Βάση" - X1 και X2. Γνωρίζουμε το κέρδος από την παραγωγή κάθε μονάδας παραγωγής ( μήτρα Γ). Απομένει να πολλαπλασιάσουμε τους όγκους παραγωγής που βρέθηκαν των προϊόντων 1 και 2 με κέρδος ανά 1 τεμάχιο, παίρνουμε το τελικό ( ανώτατο όριο! ) κέρδος για ένα δεδομένο σχέδιο παραγωγής.
ΑΠΑΝΤΗΣΗ:
Χ1 = 32 τεμ., Χ2 = 20 τεμ., Χ3 = 0 τεμ., Χ4 = 0 τεμ.
P = 48 * 32 + 33 * 20 = 2.196 τρίψτε.
Galyautdinov R.R.
© Η αντιγραφή υλικού επιτρέπεται μόνο εάν υπάρχει απευθείας υπερσύνδεσμος προς
Εάν πρέπει να λύσετε ένα πρόβλημα γραμμικού προγραμματισμού χρησιμοποιώντας πίνακες simplex, τότε η ηλεκτρονική μας υπηρεσία θα σας βοηθήσει πολύ. Η μέθοδος simplex περιλαμβάνει τη διαδοχική αναζήτηση σε όλες τις κορυφές του εύρους των αποδεκτών τιμών προκειμένου να βρεθεί η κορυφή όπου η συνάρτηση παίρνει μια ακραία τιμή. Στο πρώτο στάδιο, βρίσκεται κάποια λύση, η οποία βελτιώνεται σε κάθε επόμενο βήμα. Αυτή η λύση ονομάζεται βασική. Ακολουθεί η σειρά των ενεργειών κατά την επίλυση ενός προβλήματος γραμμικού προγραμματισμού χρησιμοποιώντας τη μέθοδο simplex:
Το πρώτο βήμα. Στον καταρτισμένο πίνακα, πρώτα απ 'όλα, πρέπει να κοιτάξετε τη στήλη με τα ελεύθερα μέλη. Εάν υπάρχουν αρνητικά στοιχεία σε αυτό, τότε είναι απαραίτητο να προχωρήσετε στο δεύτερο βήμα, εάν όχι, τότε στο πέμπτο.
Δεύτερο βήμα.
Στο δεύτερο βήμα, είναι απαραίτητο να αποφασίσετε ποια μεταβλητή θα εξαιρεθεί από τη βάση και ποια θα συμπεριληφθεί για να υπολογιστεί εκ νέου ο πίνακας simplex. Για να το κάνετε αυτό, κοιτάξτε τη στήλη με ελεύθερους όρους και βρείτε ένα αρνητικό στοιχείο σε αυτήν. Η γραμμή με αρνητικό στοιχείο θα ονομάζεται προπορευόμενη. Σε αυτό βρίσκουμε το μέγιστο αρνητικό στοιχείο σε συντελεστή, η αντίστοιχη στήλη είναι η υποτελής. Εάν υπάρχουν αρνητικές τιμές μεταξύ των δωρεάν όρων, αλλά δεν υπάρχουν στην αντίστοιχη σειρά, τότε ένας τέτοιος πίνακας δεν θα έχει λύσεις. Η μεταβλητή στην πρώτη γραμμή που βρίσκεται στη στήλη των ελεύθερων όρων εξαιρείται από τη βάση και η μεταβλητή που αντιστοιχεί στην πρώτη στήλη περιλαμβάνεται στη βάση.
| Τραπέζι 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 | ... | F 0 | ... | -γ 2 |
-c n
Τρίτο βήμα. Στο τρίτο βήμα, υπολογίζουμε εκ νέου ολόκληρο τον πίνακα simplex χρησιμοποιώντας ειδικούς τύπους.
Πέμπτο βήμα. Εάν έχετε φτάσει στο πέμπτο βήμα, τότε έχετε βρει μια λύση που είναι αποδεκτή. Ωστόσο, αυτό δεν σημαίνει ότι είναι βέλτιστο. Θα είναι βέλτιστο μόνο εάν όλα τα στοιχεία στη συμβολοσειρά F είναι θετικά. Εάν αυτό δεν συμβαίνει, τότε είναι απαραίτητο να βελτιώσουμε τη λύση, για την οποία βρίσκουμε την πρώτη γραμμή και στήλη για τον επόμενο επανυπολογισμό χρησιμοποιώντας τον ακόλουθο αλγόριθμο. Αρχικά, βρίσκουμε τον ελάχιστο αρνητικό αριθμό στη συμβολοσειρά F, εξαιρουμένης της τιμής της συνάρτησης. Η στήλη με αυτόν τον αριθμό θα είναι η πρώτη. Για να βρούμε την πρώτη γραμμή, βρίσκουμε την αναλογία του αντίστοιχου ελεύθερου όρου και του στοιχείου από την πρώτη στήλη, με την προϋπόθεση ότι είναι θετικά. Η ελάχιστη αναλογία θα σας επιτρέψει να προσδιορίσετε την κύρια γραμμή. Υπολογίζουμε ξανά τον πίνακα χρησιμοποιώντας τους τύπους, δηλ. μεταβείτε στο βήμα 3.
| - | 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 |
. Αλγόριθμος μεθόδου Simplex
Παράδειγμα 5.1.Λύστε το παρακάτω πρόβλημα γραμμικού προγραμματισμού χρησιμοποιώντας τη μέθοδο simplex:
Λύση:
Εγώ επανάληψη:
x3, x4, x5, x6 x1,x2. Ας εκφράσουμε τις βασικές μεταβλητές ως ελεύθερες:
Ας μειώσουμε την αντικειμενική συνάρτηση στην ακόλουθη μορφή:
Με βάση το πρόβλημα που προκύπτει, θα σχηματίσουμε τον αρχικό πίνακα simplex:
Πίνακας 5.3
Γνήσιος πίνακας simplex
Αξιολογικές Σχέσεις |
||||
Σύμφωνα με τον ορισμό της βασικής λύσης, οι ελεύθερες μεταβλητές είναι ίσες με μηδέν και οι τιμές των βασικών μεταβλητών είναι ίσες με τις αντίστοιχες τιμές των ελεύθερων αριθμών, δηλαδή:
Στάδιο 3: έλεγχος της συμβατότητας του συστήματος περιορισμών PAP.
Σε αυτήν την επανάληψη (στον Πίνακα 5.3), το πρόσημο της ασυνέπειας του συστήματος περιορισμού (σύμβολο 1) δεν προσδιορίζεται (δηλαδή δεν υπάρχει γραμμή με αρνητικό ελεύθερο αριθμό (εκτός από τη γραμμή της αντικειμενικής συνάρτησης) στην οποία δεν θα υπήρχε να είναι τουλάχιστον ένα αρνητικό στοιχείο (δηλ. αρνητικός συντελεστής για μια ελεύθερη μεταβλητή)).
Σε αυτήν την επανάληψη (στον Πίνακα 5.3), το πρόσημο του απεριόριστου της αντικειμενικής συνάρτησης (σύμβολο 2) δεν προσδιορίστηκε (δηλαδή, δεν υπάρχει στήλη με αρνητικό στοιχείο στη σειρά της αντικειμενικής συνάρτησης (εκτός από τη στήλη των ελεύθερων αριθμών ) στο οποίο δεν θα υπήρχε τουλάχιστον ένα θετικό στοιχείο) .
Δεδομένου ότι το βασικό διάλυμα που βρέθηκε δεν περιέχει αρνητικά συστατικά, είναι αποδεκτό.
Στάδιο 6: Έλεγχος βελτιστοποίησης.
Η βασική λύση που βρέθηκε δεν είναι βέλτιστη, αφού σύμφωνα με το κριτήριο βελτιστοποίησης (σημείο 4) δεν πρέπει να υπάρχουν αρνητικά στοιχεία στη γραμμή της αντικειμενικής συνάρτησης (ο ελεύθερος αριθμός αυτής της γραμμής δεν λαμβάνεται υπόψη κατά την εξέταση αυτού του κριτηρίου). Επομένως, σύμφωνα με τον αλγόριθμο της μεθόδου simplex, περνάμε στο στάδιο 8.
Εφόσον η βασική λύση που βρέθηκε είναι αποδεκτή, θα αναζητήσουμε τη στήλη επίλυσης σύμφωνα με το ακόλουθο σχήμα: προσδιορίζουμε τις στήλες με αρνητικά στοιχεία στη σειρά της αντικειμενικής συνάρτησης (εκτός από τη στήλη των ελεύθερων αριθμών). Σύμφωνα με τον Πίνακα 5.3, υπάρχουν δύο τέτοιες στήλες: στήλη « x1"και στήλη" x2" Από τέτοιες στήλες, επιλέγεται αυτή που περιέχει το μικρότερο στοιχείο στη γραμμή της συνάρτησης προορισμού. Αυτή θα είναι η επιτρεπτή. στήλη " x2" περιέχει το μικρότερο στοιχείο (–3) σε σύγκριση με τη στήλη " x1
Για να προσδιορίσουμε τη γραμμή επίλυσης, βρίσκουμε τις θετικές εκτιμώμενες αναλογίες των ελεύθερων αριθμών προς τα στοιχεία της στήλης επίλυσης, η γραμμή που αντιστοιχεί στη μικρότερη αναλογία θετικής αξιολόγησης είναι αποδεκτή ως επιλυμένη.
Πίνακας 5.4
Γνήσιος πίνακας simplex
Στον Πίνακα 5.4, η μικρότερη θετική σχέση αξιολόγησης αντιστοιχεί στη γραμμή " x5», επομένως, θα είναι επιτρεπτή.
Το στοιχείο που βρίσκεται στην τομή της στήλης ενεργοποίησης και της γραμμής ενεργοποίησης γίνεται αποδεκτό ως ενεργό. Στο παράδειγμά μας, αυτό είναι το στοιχείο που βρίσκεται στη διασταύρωση της γραμμής " x5"και στήλες" x2».
Το στοιχείο επίλυσης εμφανίζει μια βάση και μια ελεύθερη μεταβλητή που πρέπει να αντικατασταθούν στον πίνακα simplex για να μεταβείτε σε μια νέα «βελτιωμένη» βασική λύση. Στην περίπτωση αυτή πρόκειται για μεταβλητές x5Και x2, στον νέο πίνακα simplex (Πίνακας 5.5) τα ανταλλάσσουμε.
9.1. Μετασχηματισμός του αναλυτικού στοιχείου.
Το στοιχείο ανάλυσης του Πίνακα 5.4 μετατρέπεται ως εξής:
Εισάγουμε το αποτέλεσμα που προκύπτει σε ένα παρόμοιο κελί στον Πίνακα 5.5.
9.2. Μετατροπή συμβολοσειράς ανάλυσης.
Διαιρούμε τα στοιχεία της γραμμής επίλυσης του πίνακα 5.4 με το στοιχείο επίλυσης αυτού του πίνακα simplex, τα αποτελέσματα χωρούν σε παρόμοια κελιά του νέου πίνακα simplex (πίνακας 5.5). Οι μετασχηματισμοί των στοιχείων συμβολοσειράς ανάλυσης δίνονται στον Πίνακα 5.5.
9.3. Μετατροπή της στήλης ανάλυσης.
Διαιρούμε τα στοιχεία της στήλης ανάλυσης του Πίνακα 5.4 με το στοιχείο ανάλυσης αυτού του πίνακα simplex και το αποτέλεσμα λαμβάνεται με το αντίθετο πρόσημο. Τα αποτελέσματα που προέκυψαν χωρούν σε παρόμοια κελιά του νέου πίνακα simplex (Πίνακας 5.5). Οι μετασχηματισμοί των στοιχείων της στήλης ανάλυσης δίνονται στον Πίνακα 5.5.
9.4. Μετασχηματισμός των υπολοίπων στοιχείων του πίνακα simplex.
Ο μετασχηματισμός των υπολοίπων στοιχείων του πίνακα simplex (δηλαδή των στοιχείων που δεν βρίσκονται στη γραμμή επίλυσης και στη στήλη επίλυσης) πραγματοποιείται σύμφωνα με τον κανόνα "ορθογώνιο".
Για παράδειγμα, σκεφτείτε να μετατρέψετε ένα στοιχείο που βρίσκεται στη διασταύρωση της γραμμής " x3" και στήλες "", θα το υποδηλώσουμε υπό όρους " x3" Στον Πίνακα 5.4, σχεδιάζουμε νοερά ένα ορθογώνιο, η μία κορυφή του οποίου βρίσκεται στο κελί του οποίου την τιμή μετασχηματίζουμε (δηλαδή στο κελί " x3"), και η άλλη (διαγώνια κορυφή) βρίσκεται σε ένα κελί με ένα στοιχείο επίλυσης. Οι άλλες δύο κορυφές (της δεύτερης διαγωνίου) προσδιορίζονται μοναδικά. Στη συνέχεια, η μετασχηματισμένη τιμή του κελιού " x3" θα είναι ίση με την προηγούμενη τιμή αυτού του κελιού μείον το κλάσμα, στον παρονομαστή του οποίου είναι το στοιχείο επίλυσης (από τον Πίνακα 5.4) και στον αριθμητή είναι το γινόμενο δύο άλλων αχρησιμοποίητων κορυφών, δηλ.:
« x3»: .
Οι τιμές των άλλων κελιών μετατρέπονται με παρόμοιο τρόπο:
« x3 x1»: ;
« x4»: 
;
« x4 x1»: ;
« x6»: 
;
« x6 x1»: ;
«»: 
;
« x1»: 
.
Ως αποτέλεσμα αυτών των μετασχηματισμών, προέκυψε ένας νέος πίνακας simplex (Πίνακας 5.5).
II επανάληψη:
Στάδιο 1: κατάρτιση πίνακα simplex.
Πίνακας 5.5
Simplex τραπέζιII επαναλήψεις
Εκτιμώμενος σχέση |
||||
| ||||
|
|
Στάδιο 2: προσδιορισμός της βασικής λύσης.
Ως αποτέλεσμα των μετασχηματισμών simplex, ελήφθη μια νέα βασική λύση (Πίνακας 5.5):
Όπως μπορείτε να δείτε, με αυτή τη βασική λύση η τιμή της αντικειμενικής συνάρτησης = 15, η οποία είναι μεγαλύτερη από την προηγούμενη βασική λύση.
Η ασυνέπεια του συστήματος περιορισμών σύμφωνα με το χαρακτηριστικό 1 στον Πίνακα 5.5 δεν έχει εντοπιστεί.
Στάδιο 4: έλεγχος του ορίου της αντικειμενικής συνάρτησης.
Το απεριόριστο της αντικειμενικής συνάρτησης σύμφωνα με το κριτήριο 2 στον Πίνακα 5.5 δεν αποκαλύπτεται.
Στάδιο 5: έλεγχος του παραδεκτού της βασικής λύσης που βρέθηκε.
Η βασική λύση που βρέθηκε σύμφωνα με το κριτήριο 4 δεν είναι η βέλτιστη, καθώς η γραμμή της αντικειμενικής συνάρτησης του πίνακα simplex (Πίνακας 5.5) περιέχει ένα αρνητικό στοιχείο: –2 (ο ελεύθερος αριθμός αυτής της γραμμής δεν λαμβάνεται υπόψη όταν εξετάζεται αυτό χαρακτηριστικό γνώρισμα). Επομένως, προχωράμε στο στάδιο 8.
Στάδιο 8: προσδιορισμός του στοιχείου επίλυσης.
8.1. Ορισμός της στήλης ανάλυσης.
Η βασική λύση που βρέθηκε είναι αποδεκτή προσδιορίζουμε τις στήλες με αρνητικά στοιχεία στη σειρά της αντικειμενικής συνάρτησης (εκτός από τη στήλη των ελεύθερων αριθμών). Σύμφωνα με τον Πίνακα 5.5, υπάρχει μόνο μία τέτοια στήλη: « x1" Επομένως, το αποδεχόμαστε ως επιτρεπόμενο.
8.2. Ορισμός συμβολοσειράς ενεργοποίησης.
Σύμφωνα με τις λαμβανόμενες τιμές των θετικών σχέσεων αξιολόγησης στον Πίνακα 5.6, το ελάχιστο είναι η σχέση που αντιστοιχεί στη γραμμή " x3" Επομένως, το αποδεχόμαστε ως επιτρεπόμενο.
Πίνακας 5.6
Simplex τραπέζιII επαναλήψεις
Εκτιμώμενος σχέση |
||||
3/1=3 – λεπ |
||||
Στάδιο 9: μετασχηματισμός του πίνακα simplex.
Οι μετασχηματισμοί του πίνακα simplex (Πίνακας 5.6) εκτελούνται με τον ίδιο τρόπο όπως στην προηγούμενη επανάληψη. Τα αποτελέσματα μετασχηματισμών στοιχείων του πίνακα simplex δίνονται στον Πίνακα 5.7.
III επανάληψη
Με βάση τα αποτελέσματα των μετασχηματισμών simplex της προηγούμενης επανάληψης, συνθέτουμε έναν νέο πίνακα simplex:
Πίνακας 5.7
Simplex τραπέζιIII επαναλήψεις
Εκτιμώμενος σχέση |
||||
| ||||
|
|
Στάδιο 2: προσδιορισμός της βασικής λύσης.
Ως αποτέλεσμα των μετασχηματισμών simplex, ελήφθη μια νέα βασική λύση (Πίνακας 5.7):
Στάδιο 3: έλεγχος της συμβατότητας του συστήματος περιορισμών.
Η ασυνέπεια του συστήματος περιορισμών σύμφωνα με το χαρακτηριστικό 1 στον Πίνακα 5.7 δεν έχει εντοπιστεί.
Στάδιο 4: έλεγχος του ορίου της αντικειμενικής συνάρτησης.
Το απεριόριστο της αντικειμενικής συνάρτησης σύμφωνα με το κριτήριο 2 στον Πίνακα 5.7 δεν αποκαλύπτεται.
Στάδιο 5: έλεγχος του παραδεκτού της βασικής λύσης που βρέθηκε.
Η βασική λύση που βρέθηκε σύμφωνα με το κριτήριο 3 είναι αποδεκτή, καθώς δεν περιέχει αρνητικά συστατικά.
Στάδιο 6: έλεγχος της βελτιστοποίησης της βασικής λύσης που βρέθηκε.
Η βασική λύση που βρέθηκε σύμφωνα με το κριτήριο 4 δεν είναι η βέλτιστη, καθώς η γραμμή της αντικειμενικής συνάρτησης του πίνακα simplex (Πίνακας 5.7) περιέχει ένα αρνητικό στοιχείο: –3 (ο ελεύθερος αριθμός αυτής της γραμμής δεν λαμβάνεται υπόψη όταν εξετάζεται αυτό χαρακτηριστικό γνώρισμα). Επομένως, προχωράμε στο στάδιο 8.
Στάδιο 8: προσδιορισμός του στοιχείου επίλυσης.
8.1. Ορισμός της στήλης ανάλυσης.
Η βασική λύση που βρέθηκε είναι αποδεκτή προσδιορίζουμε τις στήλες με αρνητικά στοιχεία στη σειρά της αντικειμενικής συνάρτησης (εκτός από τη στήλη των ελεύθερων αριθμών). Σύμφωνα με τον Πίνακα 5.7, υπάρχει μόνο μία τέτοια στήλη: « x5" Επομένως, το αποδεχόμαστε ως επιτρεπόμενο.
8.2. Ορισμός συμβολοσειράς ενεργοποίησης.
Σύμφωνα με τις λαμβανόμενες τιμές των θετικών σχέσεων αξιολόγησης στον Πίνακα 5.8, το ελάχιστο είναι η σχέση που αντιστοιχεί στη γραμμή " x4" Επομένως, το αποδεχόμαστε ως επιτρεπόμενο.
Πίνακας 5.8
Simplex τραπέζιIII επαναλήψεις
Εκτιμώμενος σχέση |
||||
5/5=1 – λεπ |
||||
Στάδιο 9: μετασχηματισμός του πίνακα simplex.
Οι μετασχηματισμοί του πίνακα simplex (Πίνακας 5.8) εκτελούνται με τον ίδιο τρόπο όπως στην προηγούμενη επανάληψη. Τα αποτελέσματα μετασχηματισμών στοιχείων του πίνακα simplex δίνονται στον Πίνακα 5.9.
IV επανάληψη
Στάδιο 1: κατασκευή νέου πίνακα simplex.
Με βάση τα αποτελέσματα των μετασχηματισμών simplex της προηγούμενης επανάληψης, συνθέτουμε έναν νέο πίνακα simplex:
Πίνακας 5.9
Simplex τραπέζιIV επαναλήψεις
Εκτιμώμενος σχέση |
||||
| –(–3/5)=3/5 | |||
–(1/5)=–1/5 | ||||
| –(9/5)=–9/5 | |||
|
| –(–3/5)=3/5 |
Στάδιο 2: προσδιορισμός της βασικής λύσης.
Ως αποτέλεσμα των μετασχηματισμών simplex, ελήφθη μια νέα βασική λύση σύμφωνα με τον Πίνακα 5.9, η λύση είναι η εξής:
Στάδιο 3: έλεγχος της συμβατότητας του συστήματος περιορισμών.
Η ασυνέπεια του συστήματος περιορισμών σύμφωνα με το χαρακτηριστικό 1 στον Πίνακα 5.9 δεν έχει εντοπιστεί.
Στάδιο 4: έλεγχος του ορίου της αντικειμενικής συνάρτησης.
Το απεριόριστο της αντικειμενικής συνάρτησης σύμφωνα με το κριτήριο 2 στον Πίνακα 5.9 δεν αποκαλύπτεται.
Στάδιο 5: έλεγχος του παραδεκτού της βασικής λύσης που βρέθηκε.
Η βασική λύση που βρέθηκε σύμφωνα με το κριτήριο 3 είναι αποδεκτή, καθώς δεν περιέχει αρνητικά συστατικά.
Στάδιο 6: έλεγχος της βελτιστοποίησης της βασικής λύσης που βρέθηκε.
Η βασική λύση που βρέθηκε σύμφωνα με το χαρακτηριστικό 4 είναι η βέλτιστη, καθώς δεν υπάρχουν αρνητικά στοιχεία στη γραμμή της αντικειμενικής συνάρτησης του πίνακα simplex (Πίνακας 5.9) (ο ελεύθερος αριθμός αυτής της γραμμής δεν λαμβάνεται υπόψη κατά την εξέταση αυτού του χαρακτηριστικού) .
Στάδιο 7: έλεγχος της εναλλακτικότητας της λύσης.
Η λύση που βρέθηκε είναι μοναδική, αφού δεν υπάρχουν μηδενικά στοιχεία στη γραμμή της αντικειμενικής συνάρτησης (Πίνακας 5.9) (ο ελεύθερος αριθμός αυτής της γραμμής δεν λαμβάνεται υπόψη κατά την εξέταση αυτού του χαρακτηριστικού).
Απάντηση: η βέλτιστη τιμή της αντικειμενικής συνάρτησης του υπό εξέταση προβλήματος =24, η οποία επιτυγχάνεται στο.
Παράδειγμα 5.2.Να λύσετε το παραπάνω πρόβλημα γραμμικού προγραμματισμού με την προϋπόθεση ότι η αντικειμενική συνάρτηση είναι ελαχιστοποιημένη:
Λύση:
Εγώ επανάληψη:
Στάδιο 1: σχηματισμός του αρχικού πίνακα simplex.
Το αρχικό πρόβλημα γραμμικού προγραμματισμού δίνεται σε τυπική μορφή. Ας το φέρουμε σε κανονική μορφή εισάγοντας μια πρόσθετη μη αρνητική μεταβλητή σε κάθε έναν από τους περιορισμούς ανισότητας, π.χ.
Στο προκύπτον σύστημα εξισώσεων, παίρνουμε ως επιτρεπόμενες (βασικές) μεταβλητές x3, x4, x5, x6, τότε οι ελεύθερες μεταβλητές θα είναι x1,x2. Ας εκφράσουμε τις βασικές μεταβλητές ως ελεύθερες.