Μέθοδος Simplex στην καθαρή της μορφή στο διαδίκτυο. Ένα παράδειγμα επίλυσης ενός προβλήματος. Μέθοδος Simplex για την επίλυση ZLP
Σκοπός της υπηρεσίας. Η υπηρεσία έχει σχεδιαστεί για την ηλεκτρονική επίλυση προβλημάτων γραμμικού προγραμματισμού (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, καθώς και ένα παράδειγμα επίλυσης ενός διπλού προβλήματος.
Το έργο
Για την πώληση τριών ομάδων αγαθών, μια εμπορική επιχείρηση διαθέτει τρεις τύπους περιορισμένων υλικών και νομισματικών πόρων στο ποσό των 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 χιλιάδες ρούβλια. ο κύκλος εργασιών είναι αντίστοιχα 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 ->μέγ
0)))(~)" title="delim(lbrace)(matrix(4)(1)(2x_1 + 3x_2 + 6x_3= 0)))(~)">!}
Λύνουμε τη μέθοδο 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
Title="delim(lbrace)(matrix(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}
Εισάγουμε πρόσθετες μεταβλητές 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;
Σύντομη θεωρία
Πολλές διαφορετικές μέθοδοι έχουν προταθεί για την επίλυση προβλημάτων γραμμικού προγραμματισμού. Ωστόσο, η μέθοδος simplex αποδείχθηκε η πιο αποτελεσματική και καθολική μεταξύ τους. Θα πρέπει να σημειωθεί ότι κατά την επίλυση ορισμένων προβλημάτων, άλλες μέθοδοι μπορεί να είναι πιο αποτελεσματικές. Για παράδειγμα, για ένα ZLP με δύο μεταβλητές, η βέλτιστη μέθοδος είναι , και για την επίλυσή του χρησιμοποιείται η μέθοδος του δυναμικού. Η μέθοδος simplex είναι βασική και εφαρμόζεται σε οποιοδήποτε PPL σε κανονική μορφή.
Σε σχέση με το κύριο θεώρημα του γραμμικού προγραμματισμού, προκύπτει φυσικά η σκέψη για τον ακόλουθο τρόπο επίλυσης του LLP με οποιονδήποτε αριθμό μεταβλητών. Βρείτε με κάποιο τρόπο όλα τα ακραία σημεία του πολυέδρου των σχεδίων (δεν υπάρχουν περισσότερα από αυτά) και συγκρίνετε τις τιμές της αντικειμενικής συνάρτησης σε αυτά. Μια τέτοια λύση, ακόμη και με σχετικά μικρό αριθμό μεταβλητών και περιορισμών, είναι πρακτικά αδύνατη, καθώς η διαδικασία εύρεσης ακραίων σημείων είναι συγκρίσιμη σε δυσκολία με την επίλυση του αρχικού προβλήματος, και επιπλέον, ο αριθμός των ακραίων σημείων του πολυέδρου των σχεδίων μπορεί να να είναι πολύ μεγάλο. Σε σχέση με αυτές τις δυσκολίες, προέκυψε το πρόβλημα της ορθολογικής απαρίθμησης των ακραίων σημείων.
Η ουσία της μεθόδου simplex είναι η εξής. Εάν κάποιο ακραίο σημείο και η τιμή της αντικειμενικής συνάρτησης σε αυτό είναι γνωστά, τότε προφανώς δεν χρειάζονται όλα τα ακραία σημεία στα οποία η αντικειμενική συνάρτηση παίρνει τη χειρότερη τιμή. Ως εκ τούτου, η φυσική επιθυμία είναι να βρείτε έναν τρόπο να μετακινηθείτε από ένα δεδομένο ακραίο σημείο σε ένα καλύτερο δίπλα στην άκρη, από αυτό σε ένα ακόμα καλύτερο (όχι χειρότερο) κ.λπ. Για να το κάνετε αυτό, πρέπει να έχετε ένα σημάδι ότι δεν υπάρχουν καλύτερα ακραία σημεία από ένα δεδομένο ακραίο σημείο. Αυτή είναι η γενική ιδέα της πιο ευρέως χρησιμοποιούμενης επί του παρόντος μεθόδου simplex (μέθοδος διαδοχικής βελτίωσης του σχεδίου) για την επίλυση του ZLP. Έτσι, με αλγεβρικούς όρους, η μέθοδος simplex υποθέτει:
- την ικανότητα εύρεσης ενός αρχικού σχεδίου αναφοράς·
- παρουσία ένδειξης βελτιστοποίησης του σχεδίου αναφοράς.
- την ικανότητα να μεταβείτε σε ένα μη χειρότερο σχέδιο αναφοράς.
Παράδειγμα λύσης προβλήματος
Το έργο
Για να πουλήσει τρεις ομάδες αγαθών, μια εμπορική επιχείρηση διαθέτει τρεις τύπους περιορισμένων υλικών και νομισματικών πόρων στο ποσό των , , , μονάδων. Ταυτόχρονα, για την πώληση 1 ομάδας αγαθών για 1 χιλιάδες ρούβλια. Ο κύκλος εργασιών των εμπορευμάτων καταναλώνει τον πόρο του πρώτου τύπου στον αριθμό των μονάδων, τον πόρο του δεύτερου τύπου στον αριθμό των μονάδων, τον πόρο του τρίτου τύπου στον αριθμό των μονάδων. Για την πώληση 2 και 3 ομάδων αγαθών για 1 χιλιάδες ρούβλια. Ο κύκλος εργασιών των εμπορευμάτων δαπανάται σύμφωνα με τον πόρο του πρώτου τύπου σε ποσό , μονάδες, πόροι του δεύτερου τύπου σε ποσό , μονάδες, πόροι του τρίτου τύπου σε ποσό , μονάδες. Κέρδος από την πώληση τριών ομάδων αγαθών για 1 χιλιάδες ρούβλια. ο κύκλος εργασιών είναι, αντίστοιχα, χιλιάδες ρούβλια.
- Προσδιορίστε τον προγραμματισμένο όγκο και τη δομή του εμπορικού κύκλου εργασιών έτσι ώστε το κέρδος της εμπορικής επιχείρησης να μεγιστοποιηθεί.
- Για το άμεσο πρόβλημα του προγραμματισμού κύκλου εργασιών, που επιλύεται με τη μέθοδο simplex, δημιουργήστε ένα πρόβλημα διπλού γραμμικού προγραμματισμού.
- Καθιερώστε συζευγμένα ζεύγη μεταβλητών των άμεσων και διπλών προβλημάτων.
- Σύμφωνα με συζευγμένα ζεύγη μεταβλητών, από τη λύση του άμεσου προβλήματος, προκύπτει μια λύση στο διπλό πρόβλημα, στο οποίο υπολογίζονται οι πόροι που δαπανώνται για την πώληση αγαθών.
Εάν η είσοδος σας στη συνεδρία εξαρτάται από την επίλυση ενός συνόλου προβλημάτων και δεν έχετε ούτε τον χρόνο ούτε την επιθυμία να καθίσετε για υπολογισμούς, χρησιμοποιήστε τις δυνατότητες του ιστότοπου. Η παραγγελία εργασιών διαρκεί μόνο λίγα λεπτά. Μπορείτε να διαβάσετε αναλυτικά (τρόπος υποβολής αιτήματος, τιμές, όροι, τρόποι πληρωμής) στη σελίδα Αγορά λύσεων σε προβλήματα γραμμικού προγραμματισμού...
Η λύση του προβλήματος
Πρότυπο κτίριο
Ας υποδηλώσουμε τον κύκλο εργασιών του 1ου, 2ου και τρίτου τύπου αγαθών, αντίστοιχα.
Στη συνέχεια, η αντικειμενική συνάρτηση που εκφράζει το κέρδος που ελήφθη:
Περιορισμοί στους υλικούς και χρηματικούς πόρους:
Επιπλέον, σύμφωνα με το νόημα της εργασίας
Παίρνουμε το ακόλουθο πρόβλημα γραμμικού προγραμματισμού:
Αναγωγή στην κανονική μορφή του ZLP
Ας περιορίσουμε το πρόβλημα σε κανονική μορφή. Για να μετατρέψουμε τις ανισότητες σε ισότητες, εισάγουμε πρόσθετες μεταβλητές. Οι μεταβλητές περιλαμβάνονται στους περιορισμούς με συντελεστή 1. Εισάγουμε όλες τις πρόσθετες μεταβλητές στην αντικειμενική συνάρτηση με συντελεστή ίσο με μηδέν.
Ο περιορισμός έχει μια προτιμώμενη μορφή εάν, με τη δεξιά πλευρά να είναι μη αρνητική, η αριστερή πλευρά έχει μια μεταβλητή που εισάγεται με συντελεστή ίσο με ένα και οι υπόλοιποι περιορισμοί ισότητας έχουν συντελεστή ίσο με μηδέν. Στην περίπτωσή μας, οι περιορισμοί 1ος, 2ος, 3ος έχουν προτιμώμενη μορφή με τις αντίστοιχες βασικές μεταβλητές.
Λύση με τη μέθοδο simplex
Συμπληρώνουμε τον πίνακα simplex της 0ης επανάληψης.
| BP | Simplex σχέση |
8 | 6 | 4 | 0 | 0 | 0 | 0 | 520 | 16 | 18 | 9 | 1 | 0 | 0 | 65/2 | 0 | 140 | 7 | 7 | 2 | 0 | 1 | 0 | 20 | 0 | 810 | 9 | 2 | 1 | 0 | 0 | 1 | 90 | 0 | -8 | -6 | -4 | 0 | 0 | 0 |
Δεδομένου ότι λύνουμε το πρόβλημα στο μέγιστο, η παρουσία αρνητικών αριθμών στη γραμμή δείκτη κατά την επίλυση του προβλήματος στο μέγιστο υποδηλώνει ότι δεν έχουμε λάβει τη βέλτιστη λύση και ότι είναι απαραίτητο να προχωρήσουμε από τον πίνακα της 0ης επανάληψης στον επόμενο.
Προχωράμε στην επόμενη επανάληψη ως εξής:
Η κύρια στήλη αντιστοιχεί σε .
Η βασική γραμμή καθορίζεται από την ελάχιστη αναλογία ελεύθερων όρων και μελών της κύριας στήλης (απλές σχέσεις):
Στη διασταύρωση της στήλης κλειδιού και της γραμμής κλειδιού βρίσκουμε το στοιχείο ενεργοποίησης, δηλαδή 7.
Τώρα αρχίζουμε να συντάσσουμε την 1η επανάληψη. Αντί για μοναδιαίο διάνυσμα, εισάγουμε το διάνυσμα .
Στον νέο πίνακα, στη θέση του στοιχείου ενεργοποίησης γράφουμε 1, όλα τα άλλα στοιχεία της στήλης κλειδιού είναι μηδενικά. Τα βασικά στοιχεία συμβολοσειράς χωρίζονται στο στοιχείο ενεργοποίησης. Όλα τα άλλα στοιχεία του πίνακα υπολογίζονται χρησιμοποιώντας τον κανόνα του ορθογωνίου.
Παίρνουμε τον πίνακα της 1ης επανάληψης:
| BP | Simplex σχέση |
8 | 6 | 4 | 0 | 0 | 0 | 0 | 200 | 0 | 2 | 31/7 | 1 | -16/7 | 0 | 1400/31 | 8 | 20 | 1 | 1 | 2/7 | 0 | 1/7 | 0 | 70 | 0 | 630 | 0 | -7 | -11/7 | 0 | -9/7 | 1 | - | 160 | 0 | 2 | -12/7 | 0 | 8/7 | 0 |
Η στήλη κλειδιού για την 1η επανάληψη αντιστοιχεί σε .
Βρίσκουμε τη γραμμή κλειδιού, για αυτό ορίζουμε:
Στη διασταύρωση της στήλης κλειδιού και της γραμμής κλειδιού βρίσκουμε το στοιχείο ενεργοποίησης, δηλ. 31/7.
Το διάνυσμα προέρχεται από τη βάση και το διάνυσμα εισάγεται.
Παίρνουμε τον πίνακα της 2ης επανάληψης:
| BP | Simplex σχέση |
8 | 6 | 4 | 0 | 0 | 0 | 4 | 1400/31 | 0 | 14/31 | 1 | 7/31 | -16/31 | 0 | 8 | 220/31 | 1 | 27/31 | 0 | -2/31 | 9/31 | 0 | 0 | 21730/31 | 0 | -195/31 | 0 | 11/31 | -65/31 | 1 | 7360/31 | 0 | 86/31 | 0 | 12/31 | 8/31 | 0 |
Στη γραμμή ευρετηρίου, όλοι οι όροι είναι μη αρνητικοί, επομένως προκύπτει η ακόλουθη λύση στο πρόβλημα γραμμικού προγραμματισμού (το γράφουμε από τη στήλη των ελεύθερων όρων):
Έτσι, είναι απαραίτητο να πουληθούν 7,1 χιλιάδες ρούβλια. αγαθά του 1ου τύπου και 45,2 χιλιάδες ρούβλια. εμπορεύματα 3ου τύπου. Δεν συμφέρει να πουλήσεις ένα προϊόν 2ου τύπου. Σε αυτή την περίπτωση, το κέρδος θα είναι μέγιστο και θα ανέλθει σε 237,4 χιλιάδες ρούβλια. Εάν εφαρμοστεί το βέλτιστο σχέδιο, ο υπόλοιπος πόρος του 3ου τύπου θα είναι 701 μονάδες.
Πρόβλημα διπλού LP
Ας γράψουμε ένα μοντέλο του διπλού προβλήματος.
Για να δημιουργήσετε ένα διπλό πρόβλημα, πρέπει να χρησιμοποιήσετε τους ακόλουθους κανόνες:
1) εάν το άμεσο πρόβλημα λυθεί στο μέγιστο, τότε το διπλό πρόβλημα λύνεται στο ελάχιστο και αντίστροφα.
2) στο μέγιστο πρόβλημα, οι περιορισμοί ανισότητας έχουν την έννοια ≤ και στο πρόβλημα ελαχιστοποίησης έχουν την έννοια ≥.
3) κάθε περιορισμός του άμεσου προβλήματος αντιστοιχεί σε μια μεταβλητή του διπλού προβλήματος και αντίστροφα, κάθε περιορισμός του διπλού προβλήματος αντιστοιχεί σε μια μεταβλητή του άμεσου προβλήματος.
4) ο πίνακας του συστήματος περιορισμών του διπλού προβλήματος λαμβάνεται από τον πίνακα του συστήματος περιορισμών του αρχικού προβλήματος με μεταφορά στο εθνικό δίκαιο.
5) οι ελεύθεροι όροι του συστήματος των περιορισμών του άμεσου προβλήματος είναι συντελεστές των αντίστοιχων μεταβλητών της αντικειμενικής συνάρτησης του διπλού προβλήματος και αντίστροφα.
6) εάν επιβάλλεται συνθήκη μη αρνητικότητας στη μεταβλητή του άμεσου προβλήματος, τότε ο αντίστοιχος περιορισμός του διπλού προβλήματος γράφεται ως περιορισμός ανισότητας, αν όχι, τότε ως περιορισμός ισότητας.
7) εάν οποιοσδήποτε περιορισμός του άμεσου προβλήματος γραφτεί ως ισότητα, τότε η συνθήκη μη αρνητικότητας δεν επιβάλλεται στην αντίστοιχη μεταβλητή του διπλού προβλήματος.
Μεταφέρουμε τη μήτρα του αρχικού προβλήματος:
Ας περιορίσουμε το πρόβλημα σε κανονική μορφή. Ας εισάγουμε πρόσθετες μεταβλητές. Εισάγουμε όλες τις πρόσθετες μεταβλητές στην αντικειμενική συνάρτηση με συντελεστή ίσο με μηδέν. Προσθέτουμε επιπλέον μεταβλητές στα αριστερά των περιορισμών που δεν έχουν προτιμώμενη μορφή και λαμβάνουμε ισότητες.
Λύση του προβλήματος του διπλού LP
Αντιστοιχία μεταξύ των μεταβλητών του αρχικού και του διπλού προβλήματος:
Με βάση τον πίνακα simplex, προέκυψε η ακόλουθη λύση στο πρόβλημα του διπλού γραμμικού προγραμματισμού (το γράφουμε από την κάτω γραμμή):
Έτσι, ο πόρος του πρώτου τύπου είναι ο πιο σπάνιος. Η βαθμολογία του είναι μέγιστη και ίση με . Ο πόρος του τρίτου τύπου είναι περιττός - η διπλή του τιμή είναι μηδέν. Κάθε επιπλέον μονάδα αγαθών της 2ης ομάδας που πωλείται θα μειώσει το βέλτιστο κέρδος κατά
Εξετάζεται μια γραφική μέθοδος για την επίλυση ενός προβλήματος γραμμικού προγραμματισμού (LPP) με δύο μεταβλητές. Χρησιμοποιώντας το παράδειγμα ενός προβλήματος, δίνεται μια λεπτομερής περιγραφή της κατασκευής ενός σχεδίου και της εύρεσης λύσης.
Λύση του προβλήματος των μεταφορών
Το πρόβλημα μεταφοράς, το μαθηματικό του μοντέλο και οι μέθοδοι επίλυσης εξετάζονται λεπτομερώς - εύρεση του σχεδίου αναφοράς με τη μέθοδο ελάχιστου στοιχείου και αναζήτηση της βέλτιστης λύσης με τη μέθοδο δυνητικού.
Λήψη αποφάσεων υπό συνθήκες αβεβαιότητας
Η λύση ενός παιχνιδιού στατιστικού πίνακα υπό συνθήκες αβεβαιότητας εξετάζεται χρησιμοποιώντας τα κριτήρια Wald, Savage, Hurwitz, Laplace και Bayes. Χρησιμοποιώντας ένα παράδειγμα προβλήματος, παρουσιάζεται λεπτομερώς η κατασκευή ενός πίνακα πληρωμών και ενός πίνακα κινδύνου.
Εάν πρέπει να λύσετε ένα πρόβλημα γραμμικού προγραμματισμού χρησιμοποιώντας πίνακες 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 | -γ 2 | ... | -γ 1 | ... | -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 |
