Η μέθοδος Simplex είναι μια αντικειμενική συνάρτηση. Γραμμικός προγραμματισμός. Απλή μέθοδος

Αυτή η μέθοδος είναι μια μέθοδος σκόπιμης απαρίθμησης λύσεων υποστήριξης ενός προβλήματος γραμμικού προγραμματισμού. Επιτρέπει, σε πεπερασμένο αριθμό βημάτων, είτε να βρει τη βέλτιστη λύση, είτε να αποδείξει ότι δεν υπάρχει βέλτιστη λύση.

Το κύριο περιεχόμενο της μεθόδου simplex έχει ως εξής:

1. Υποδείξτε έναν τρόπο για να βρείτε τη βέλτιστη λύση υποστήριξης
2. Υποδείξτε τη μέθοδο μετάβασης από τη μία λύση υποστήριξης στην άλλη, στην οποία η τιμή της αντικειμενικής συνάρτησης θα είναι πιο κοντά στη βέλτιστη, δηλ. υποδείξτε έναν τρόπο βελτίωσης της λύσης αναφοράς
3. Ορίστε κριτήρια που σας επιτρέπουν να σταματήσετε έγκαιρα την αναζήτηση λύσεων υποστήριξης για τη βέλτιστη λύση ή να ακολουθήσετε το συμπέρασμα σχετικά με την απουσία βέλτιστης λύσης.

Αλγόριθμος της απλής μεθόδου για την επίλυση προβλημάτων γραμμικού προγραμματισμού

Για να λυθεί το πρόβλημα απλή μέθοδοςπρέπει να κάνετε τα εξής:

1. Φέρτε την εργασία στην κανονική φόρμα
2. Βρείτε την αρχική λύση υποστήριξης με "βάση μονάδας" (εάν δεν υπάρχει λύση υποστήριξης, τότε το πρόβλημα δεν έχει καμία λύση λόγω της ασυμβατότητας του συστήματος περιορισμών)
3. Υπολογίστε τις εκτιμήσεις των διανυσμάτων επεκτάσεων με βάση τη λύση υποστήριξης και συμπληρώστε τον πίνακα της μεθόδου simplex
4. Εάν ικανοποιηθεί το κριτήριο για τη μοναδικότητα της βέλτιστης λύσης, τότε η λύση στο πρόβλημα τελειώνει
5. Εάν πληρούται η προϋπόθεση για την ύπαρξη ενός συνόλου βέλτιστων λύσεων, τότε με μια απλή απαρίθμηση θα βρεθούν όλες οι βέλτιστες λύσεις

Ένα παράδειγμα επίλυσης ενός προβλήματος χρησιμοποιώντας τη μέθοδο simplex

Παράδειγμα 26.1

Λύστε το πρόβλημα χρησιμοποιώντας τη μέθοδο simplex:

Απόφαση:

Φέρνουμε το πρόβλημα σε κανονική μορφή.

Για να γίνει αυτό, στην αριστερή πλευρά του πρώτου περιορισμού ανισότητας, εισάγουμε μια επιπλέον μεταβλητή x 6 με συντελεστή +1. Η μεταβλητή x 6 περιλαμβάνεται στην αντικειμενική συνάρτηση με συντελεστή μηδέν (δηλαδή δεν περιλαμβάνεται).

Παίρνουμε:

Βρείτε την αρχική λύση υποστήριξης. Για αυτό, οι ελεύθερες (άλυτες) μεταβλητές εξισώνονται στο μηδέν x1 = x2 = x3 = 0.

Παίρνουμε λύση αναφοράς X1 = (0,0,0,24,30,6) με βάση τη μονάδα B1 = (A4, A5, A6).

Υπολογίζουμε εκτιμήσεις αποσύνθεσης φορέασυνθήκες βάσει του διαλύματος αναφοράς σύμφωνα με τον τύπο:

Δ k = C b X k - c k

• C b = (c 1, c 2, ..., c m) - διάνυσμα συντελεστών της αντικειμενικής συνάρτησης με βασικές μεταβλητές
• X k = (x 1k, x 2k, ..., x mk) είναι ο φορέας επέκτασης του αντίστοιχου διανύσματος A k στη βάση της λύσης υποστήριξης
• C k - συντελεστής της αντικειμενικής συνάρτησης στη μεταβλητή x k.

Οι εκτιμήσεις των διανυσμάτων που περιλαμβάνονται στη βάση είναι πάντα μηδενικές. Η λύση υποστήριξης, οι συντελεστές επέκτασης και οι εκτιμήσεις των επεκτάσεων των διανυσμάτων συνθηκών με βάση τη λύση υποστήριξης γράφονται στο απλός πίνακας:

Πάνω από τον πίνακα, για τη διευκόλυνση του υπολογισμού των εκτιμήσεων, γράφονται οι συντελεστές της αντικειμενικής συνάρτησης. Η πρώτη στήλη "Β" περιέχει τα διανύσματα που περιλαμβάνονται στη βάση της λύσης αναφοράς. Η σειρά γραφής αυτών των διανυσμάτων αντιστοιχεί στους αριθμούς των επιτρεπόμενων αγνώστων στις εξισώσεις περιορισμού. Η δεύτερη στήλη του πίνακα "C b" καταγράφει τους συντελεστές της αντικειμενικής συνάρτησης με τις βασικές μεταβλητές στην ίδια σειρά. Με τη σωστή θέση των συντελεστών αντικειμενικής συνάρτησης στη στήλη "C b", οι εκτιμήσεις των διανυσμάτων μονάδας που περιλαμβάνονται στη βάση είναι πάντα ίσες με μηδέν.

Η τελευταία σειρά του πίνακα με εκτιμήσεις Δ k στη στήλη "A 0" καταγράφει τις τιμές της αντικειμενικής συνάρτησης στο διάλυμα αναφοράς Z (X 1).

Η αρχική λύση υποστήριξης δεν είναι η βέλτιστη, καθώς στο μέγιστο πρόβλημα οι εκτιμήσεις Δ 1 = -2, Δ 3 = -9 για τα διανύσματα Α1 και Α3 είναι αρνητικές.

Σύμφωνα με το θεώρημα για τη βελτίωση της λύσης υποστήριξης, εάν στο μέγιστο πρόβλημα τουλάχιστον ένας φορέας έχει αρνητική εκτίμηση, τότε μπορεί να βρεθεί μια νέα λύση υποστήριξης, στην οποία η τιμή της αντικειμενικής συνάρτησης θα είναι μεγαλύτερη.

Ας προσδιορίσουμε ποιο από τα δύο διανύσματα θα οδηγήσει σε μεγαλύτερη αύξηση της αντικειμενικής συνάρτησης.

Η αύξηση της αντικειμενικής συνάρτησης εντοπίζεται από τον τύπο :.

Υπολογίζουμε τις τιμές της παραμέτρου θ 01 για την πρώτη και την τρίτη στήλη χρησιμοποιώντας τον τύπο:

Παίρνουμε θ 01 = 6 με l = 1, θ 03 = 3 με l = 1 (πίνακας 26.1).

Βρίσκουμε την αύξηση της αντικειμενικής συνάρτησης εισάγοντας το πρώτο διάνυσμα ΔΖ 1 = - 6 * (- 2) = 12 στη βάση και το τρίτο διάνυσμα ΔΖ 3 = - 3 * (- 9) = 27.

Επομένως, για ταχύτερη προσέγγιση της βέλτιστης λύσης, είναι απαραίτητο να εισαχθεί ο φορέας A3 στη βάση της λύσης υποστήριξης αντί του πρώτου διανύσματος της βάσης A6, καθώς το ελάχιστο της παραμέτρου θ 03 επιτυγχάνεται στην πρώτη σειρά (l = 1).

Πραγματοποιούμε τον μετασχηματισμό Jordan με το στοιχείο X13 = 2, λαμβάνουμε τη δεύτερη λύση υποστήριξης X2 = (0,0,3,21,42,0) με τη βάση B2 = (A3, A4, A5). (πίνακας 26.2)

Αυτή η λύση δεν είναι βέλτιστη, καθώς ο φορέας Α2 έχει αρνητική εκτίμηση Δ2 = - 6. Για να βελτιωθεί η λύση, είναι απαραίτητο να εισαχθεί ο φορέας Α2 στη βάση του διαλύματος υποστήριξης.

Προσδιορίστε τον αριθμό του διανύσματος που προέρχεται από τη βάση. Για να γίνει αυτό, υπολογίζουμε την παράμετρο θ 02 για τη δεύτερη στήλη, είναι ίση με 7 για l = 2. Επομένως, από τη βάση αντλούμε τη δεύτερη βάση φορέα A4. Πραγματοποιούμε τον μετασχηματισμό Jordan με το στοιχείο x 22 = 3, λαμβάνουμε την τρίτη λύση αναφοράς X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (πίνακας 26.3).

Αυτή η λύση είναι η μόνη βέλτιστη, καθώς για όλους τους φορείς που δεν περιλαμβάνονται στη βάση της εκτίμησης, είναι θετικοί

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Απάντηση: max Z (X) = 201 σε X = (0,7,10,0,63).

Μέθοδος γραμμικού προγραμματισμού στην οικονομική ανάλυση

Μέθοδος γραμμικού προγραμματισμούκαθιστά δυνατή την τεκμηρίωση της βέλτιστης οικονομικής λύσης σε συνθήκες σοβαρών περιορισμών που σχετίζονται με τους πόρους που χρησιμοποιούνται στην παραγωγή (πάγια περιουσιακά στοιχεία, υλικά, εργατικοί πόροι). Η εφαρμογή αυτής της μεθόδου στην οικονομική ανάλυση σας επιτρέπει να λύσετε προβλήματα που σχετίζονται κυρίως με τον προγραμματισμό των δραστηριοτήτων του οργανισμού. Αυτή η μέθοδος βοηθά στον προσδιορισμό των βέλτιστων τιμών εξόδου, καθώς και της κατεύθυνσης των περισσότερων αποτελεσματική χρήσητους πόρους παραγωγής που διατίθενται στον οργανισμό.

Με τη βοήθεια αυτής της μεθόδου, πραγματοποιείται η λύση των λεγόμενων ακραίων προβλημάτων, η οποία συνίσταται στην εύρεση των ακραίων τιμών, δηλαδή της μέγιστης και ελάχιστης λειτουργίας των μεταβλητών ποσοτήτων.

Αυτή η περίοδος βασίζεται στη λύση του συστήματος γραμμικές εξισώσειςσε περιπτώσεις όπου τα αναλυθέντα οικονομικά φαινόμενα συνδέονται με γραμμική, αυστηρά λειτουργική εξάρτηση. Η γραμμική μέθοδος προγραμματισμού χρησιμοποιείται για την ανάλυση μεταβλητών παρουσία ορισμένων περιοριστικών παραγόντων.

Η λύση του λεγόμενου προβλήματος μεταφοράς χρησιμοποιώντας τη μέθοδο γραμμικού προγραμματισμού είναι πολύ κοινή. Το περιεχόμενο αυτής της εργασίας είναι να ελαχιστοποιήσει το κόστος που προκύπτει σε σχέση με τη λειτουργία των οχημάτων υπό τους όρους των υφιστάμενων περιορισμών σχετικά με τον αριθμό των οχημάτων, τη χωρητικότητα τους, τη διάρκεια της λειτουργίας τους, εάν υπάρχει ανάγκη συντήρησης του μέγιστου αριθμός πελατών.

Εκτός, αυτή η μέθοδοςβρίσκει ευρεία εφαρμογή στην επίλυση του προβλήματος προγραμματισμού. Αυτή η εργασία συνίσταται σε μια τέτοια κατανομή του χρόνου λειτουργίας του προσωπικού ενός δεδομένου οργανισμού, ο οποίος θα ήταν ο πιο αποδεκτός τόσο για τα μέλη αυτού του προσωπικού όσο και για τους πελάτες του οργανισμού.

Αυτή η αποστολή είναι να μεγιστοποιήσει τον αριθμό των πελατών που εξυπηρετούνται στο πλαίσιο των περιορισμών στον αριθμό των διαθέσιμων μελών του προσωπικού, καθώς και το ταμείο των ωρών εργασίας.

Έτσι, η μέθοδος γραμμικού προγραμματισμού είναι αρκετά κοινή στην ανάλυση τοποθέτησης και χρήσης. ΔΙΑΦΟΡΕΤΙΚΟΙ ΤΥΠΟΙπόρων, καθώς και στη διαδικασία σχεδιασμού και πρόβλεψης των δραστηριοτήτων των οργανισμών.

Ωστόσο, ο μαθηματικός προγραμματισμός μπορεί να εφαρμοστεί σε αυτά τα οικονομικά φαινόμενα, η σχέση μεταξύ των οποίων δεν είναι γραμμική. Για το σκοπό αυτό, μπορούν να χρησιμοποιηθούν μη γραμμικές, δυναμικές και κυρτές μέθοδοι προγραμματισμού.

Ο μη γραμμικός προγραμματισμός βασίζεται στη μη γραμμική φύση της αντικειμενικής συνάρτησης ή περιορισμών ή και τα δύο. Οι μορφές της αντικειμενικής λειτουργίας και οι ανισότητες των περιορισμών υπό αυτές τις συνθήκες μπορεί να είναι διαφορετικές.

Ο μη γραμμικός προγραμματισμός χρησιμοποιείται στην οικονομική ανάλυση, ιδίως όταν καθορίζει τη σχέση μεταξύ δεικτών που εκφράζουν την αποτελεσματικότητα των δραστηριοτήτων ενός οργανισμού και τον όγκο αυτής της δραστηριότητας, τη διάρθρωση του κόστους παραγωγής, τις συνθήκες της αγοράς κ.λπ.

Ο δυναμικός προγραμματισμός βασίζεται στη δημιουργία ενός δέντρου αποφάσεων. Κάθε επίπεδο αυτού του δέντρου χρησιμεύει ως στάδιο για τον προσδιορισμό των συνεπειών της προηγούμενης απόφασης και για την εξάλειψη των αναποτελεσματικών επιλογών για αυτήν την απόφαση. Με αυτόν τον τρόπο, δυναμικός προγραμματισμόςέχει πολλών σταδίων, πολλαπλών σταδίων φύση. Αυτός ο τύπος προγραμματισμού χρησιμοποιείται στην οικονομική ανάλυση προκειμένου να βρει τις καλύτερες επιλογές για την ανάπτυξη ενός οργανισμού, τόσο τώρα όσο και στο μέλλον.

Ο κυρτός προγραμματισμός είναι μια μορφή μη γραμμικού προγραμματισμού. Αυτός ο τύπος προγραμματισμού εκφράζει τη μη γραμμική φύση της σχέσης μεταξύ των αποτελεσμάτων των δραστηριοτήτων του οργανισμού και του κόστους που συνεπάγεται. Ο κυρτός (γνωστός και ως κοίλος) προγραμματισμός αναλύει κυρτές αντικειμενικές συναρτήσεις και κυρτά συστήματα περιορισμών (σημεία αποδεκτές τιμές). Ο κυρτός προγραμματισμός χρησιμοποιείται στην ανάλυση της οικονομικής δραστηριότητας για την ελαχιστοποίηση του κόστους και ο κοίλος προγραμματισμός χρησιμοποιείται για τη μεγιστοποίηση του εισοδήματος υπό τις συνθήκες των υφιστάμενων περιορισμών στη δράση παραγόντων που επηρεάζουν τους αναλυθέντες δείκτες με τον αντίθετο τρόπο. Κατά συνέπεια, στους υπό εξέταση τύπους προγραμματισμού, οι κυρτές αντικειμενικές συναρτήσεις ελαχιστοποιούνται και οι κοίλες αυτές μεγιστοποιούνται.

Σύντομη θεωρία

Έχουν προταθεί πολλές διαφορετικές μέθοδοι για την επίλυση προβλημάτων γραμμικού προγραμματισμού. Ωστόσο, η απλή μέθοδος αποδείχθηκε η πιο αποτελεσματική και καθολική μεταξύ τους. Πρέπει να σημειωθεί ότι για την επίλυση ορισμένων προβλημάτων, άλλες μέθοδοι μπορεί να είναι πιο αποτελεσματικές. Για παράδειγμα, για ένα LPP με δύο μεταβλητές, η βέλτιστη μέθοδος είναι και για μια λύση, η πιθανή μέθοδος. Η μέθοδος simplex είναι βασική και ισχύει για οποιοδήποτε ZPL σε κανονική μορφή.

Σε σχέση με το κύριο θεώρημα του γραμμικού προγραμματισμού, η σκέψη προκύπτει φυσικά από την ακόλουθη πορεία Λύσεις LPPμε οποιονδήποτε αριθμό μεταβλητών. Βρείτε με κάποιο τρόπο όλα τα ακραία σημεία του σχεδιασμού πολυέδρου (δεν υπάρχουν περισσότερα από) και συγκρίνετε τις τιμές της αντικειμενικής λειτουργίας σε αυτά. Αυτός ο τρόπος επίλυσης ακόμη και με σχετικά μικρό αριθμό μεταβλητών και περιορισμών είναι πρακτικά μη πραγματοποιημένος, καθώς η διαδικασία εύρεσης των ακραίων σημείων είναι συγκρίσιμη σε δυσκολία με την επίλυση του αρχικού προβλήματος. Επιπλέον, ο αριθμός των ακραίων σημείων του σχεδίου πολυέδρου μπορεί αποδειχθεί πολύ μεγάλη. Σε σχέση με αυτές τις δυσκολίες, προέκυψε το πρόβλημα της ορθολογικής απαρίθμησης ακραίων σημείων.

Η ουσία της απλής μεθόδου έχει ως εξής. Εάν κάποιο ακραίο σημείο και η τιμή της αντικειμενικής συνάρτησης είναι γνωστά, τότε όλα τα ακραία σημεία στα οποία η αντικειμενική συνάρτηση παίρνει τη χειρότερη τιμή είναι προφανώς περιττά. Ως εκ τούτου, είναι φυσικό να προσπαθούμε να βρούμε έναν τρόπο να πάει από ένα δεδομένο ακραίο σημείο σε ένα καλύτερο δίπλα σε μια άκρη, από ένα ακόμη καλύτερο (όχι χειρότερο) σημείο κ.λπ. Για αυτό, πρέπει να έχετε ένα σημάδι ότι δεν υπάρχουν καθόλου καλύτερα ακραία σημεία από αυτό το ακραίο σημείο. Αυτή είναι η γενική ιδέα της ευρέως χρησιμοποιούμενης μεθόδου simplex (η μέθοδος διαδοχικής βελτίωσης του σχεδίου) για την επίλυση του LPP. Έτσι, με αλγεβρικούς όρους, η μέθοδος simplex προϋποθέτει:

1. την ικανότητα εύρεσης του αρχικού σχεδίου αναφοράς ·
2. την παρουσία ενός σημείου βελτιστοποίησης του σχεδίου αναφοράς ·
3. την ικανότητα μετάβασης σε ένα μη φτωχό βασικό σχέδιο.

Ένα παράδειγμα επίλυσης του προβλήματος

Το έργο

Για την πώληση τριών ομάδων αγαθών, μια εμπορική επιχείρηση έχει τρεις τύπους περιορισμένων υλικών και νομισματικών πόρων σε ποσό ,,, μονάδων. Ταυτόχρονα, για την πώληση 1 ομάδας προϊόντων για 1.000 ρούβλια. Ο κύκλος εργασιών δαπανάται στον πόρο του πρώτου τύπου στον αριθμό μονάδων, στον πόρο του δεύτερου τύπου στον αριθμό μονάδων, στον πόρο του τρίτου τύπου στον αριθμό μονάδων. Για την πώληση 2 και 3 ομάδων προϊόντων για 1.000 ρούβλια. Ο κύκλος εργασιών δαπανάται, αντίστοιχα, ο πόρος του πρώτου τύπου σε ποσότητα, μονάδες, πόροι του δεύτερου τύπου σε ποσότητα, μονάδες, πόροι του τρίτου τύπου σε ποσότητα, μονάδες. Κέρδος από την πώληση τριών ομάδων αγαθών για 1.000 ρούβλια. ο κύκλος εργασιών είναι, αντιστοίχως, χιλιάδες ρούβλια.

• Προσδιορίστε τον προγραμματισμένο όγκο και τη δομή του κύκλου εργασιών, έτσι ώστε το κέρδος της εμπορικής επιχείρησης να είναι το μέγιστο.
• Στο άμεσο πρόβλημα του προγραμματισμού του κύκλου εργασιών, που επιλύεται με τη μέθοδο simplex, δημιουργήστε ένα πρόβλημα διπλού γραμμικού προγραμματισμού.
• Δημιουργήστε συζευγμένα ζεύγη μεταβλητών των άμεσων και διπλών προβλημάτων.
• Σύμφωνα με συζευγμένα ζεύγη μεταβλητών, από τη λύση του άμεσου προβλήματος, λάβετε τη λύση διπλή εργασία, που εκτιμά τους πόρους που δαπανήθηκαν για την πώληση αγαθών.

Εάν η είσοδό σας στη συνεδρία εξαρτάται από την επίλυση ενός προβλήματος και δεν έχετε ούτε τον χρόνο ούτε την επιθυμία να καθίσετε για τους υπολογισμούς - χρησιμοποιήστε τις δυνατότητες του ιστότοπου. Η παραγγελία εργασιών είναι θέμα λίγων λεπτών. Μπορείτε να διαβάσετε περισσότερες λεπτομέρειες (πώς να αφήσετε ένα αίτημα, τιμές, όρους, τρόποι πληρωμής) στη σελίδα Αγορά γραμμικού προγραμματισμού επίλυσης προβλημάτων ...

Η λύση του προβλήματος

Δημιουργία του μοντέλου

Μέσω υποδηλώνει τον κύκλο εργασιών του 1ου, 2ου και τρίτου είδους εμπορευμάτων, αντίστοιχα.

Στη συνέχεια, η αντικειμενική συνάρτηση που εκφράζει το κέρδος είναι:

Περιορισμοί σε υλικούς και νομισματικούς πόρους:

Επιπλέον, κατά την έννοια του προβλήματος

Έχουμε το ακόλουθο πρόβλημα γραμμικού προγραμματισμού:

Φέρνοντας στην κανονική μορφή του ZLP

Ας φέρουμε το πρόβλημα σε κανονική μορφή. Για να μετατρέψουμε τις ανισότητες σε ισοτιμίες, εισάγουμε επιπλέον μεταβλητές. Οι μεταβλητές περιλαμβάνονται στους περιορισμούς με συντελεστή 1. Εισάγουμε όλες τις πρόσθετες μεταβλητές στην αντικειμενική συνάρτηση με συντελεστή ίσο με μηδέν.

Ο περιορισμός έχει μια προτιμώμενη μορφή εάν, εάν η δεξιά πλευρά είναι μη αρνητική, η αριστερή πλευρά έχει μια μεταβλητή που εισάγει με έναν συντελεστή ίσο με έναν και τους υπόλοιπους περιορισμούς ισότητας - με έναν συντελεστή ίσο με μηδέν. Στην περίπτωσή μας, ο 1ος, ο 2ος, ο 3ος περιορισμός έχουν μια προτιμώμενη μορφή με τις αντίστοιχες βασικές μεταβλητές.

Απλή λύση

Συμπληρώνουμε τον απλό πίνακα της 0ης επανάληψης.

ΒΡ

Απλός συγγένειες

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ης επανάληψης στην επόμενη.

Η μετάβαση στην επόμενη επανάληψη πραγματοποιείται ως εξής:

Οι κορυφαίες στήλες ταιριάζουν.

Η σειρά κλειδιών καθορίζεται από την ελάχιστη αναλογία ελεύθερων μελών και μελών της αρχικής στήλης (simplex σχέσεις):

Στη διασταύρωση της στήλης κλειδιού και της σειράς κλειδιών, βρίσκουμε το στοιχείο επίλυσης, δηλαδή 7.

Τώρα ας αρχίσουμε τη συλλογή της 1ης επανάληψης. Αντί για ένα διάνυσμα μονάδων, εισάγουμε ένα διάνυσμα.

Στον νέο πίνακα, στη θέση του στοιχείου επίλυσης, γράψτε 1, όλα τα άλλα στοιχεία της στήλης κλειδιού είναι μηδενισμένα. Τα βασικά στοιχεία γραμμής υποδιαιρούνται σε επιτρεπόμενο στοιχείο. Όλα τα άλλα στοιχεία του πίνακα υπολογίζονται σύμφωνα με τον κανόνα ορθογωνίου.

Παίρνουμε τον πίνακα της 1ης επανάληψης:

ΒΡ

Απλός συγγένειες

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ης επανάληψης:

ΒΡ

Απλός συγγένειες

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. Στο παράδειγμα της εργασίας, παρουσιάζεται λεπτομερώς η κατασκευή ενός πίνακα πληρωμών και ενός πίνακα κινδύνου.

Εάν η δήλωση προβλήματος περιέχει περιορισμούς με το σύμβολο ≥, τότε μπορούν να μειωθούν στη μορφή ja 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)

Ο αρχικός απλός πίνακας (απλός πίνακας 1) καταρτίζεται με βάση τις εξισώσεις (2) και (4). Εάν οι πρόσθετες μεταβλητές x n + j προηγούνται από το σύμβολο "+", όπως στο (2), τότε όλοι οι συντελεστές πριν από τις μεταβλητές x i και τον ελεύθερο όρο b j εισάγονται στον πίνακα απλών αμετάβλητων. Όταν η συνάρτηση στόχου μεγιστοποιηθεί, οι συντελεστές της συνάρτησης στόχου εισάγονται στην κατώτατη γραμμή του απλού πίνακα με αντίθετα σημάδια. Οι δωρεάν όροι στον απλό πίνακα καθορίζουν τη λύση του προβλήματος.

Ο αλγόριθμος για την επίλυση του προβλήματος έχει ως εξής:

1ο βήμα. Τα μέλη της στήλης δωρεάν μέλους μετακινούνται. Εάν όλα είναι θετικά, τότε έχει βρεθεί μια εφικτή βασική λύση και πρέπει να προχωρήσουμε στο βήμα 5 του αλγορίθμου, που αντιστοιχεί στην εξεύρεση της βέλτιστης λύσης. Εάν ο αρχικός πίνακας simplex έχει αρνητικούς ελεύθερους όρους, τότε η λύση δεν είναι έγκυρη και πρέπει να προχωρήσετε στο βήμα 2.

2ο βήμα. Για την εξεύρεση μιας εφικτής λύσης πραγματοποιείται, ενώ είναι απαραίτητο να αποφασιστεί ποιες από τις μη βασικές μεταβλητές θα συμπεριληφθούν στη βάση και ποια μεταβλητή θα συναχθεί από τη βάση.

Τραπέζι 1.

x ν

βασικές μεταβλητές	Δωρεάν μέλη σε περιορισμούς	Μη βασικές μεταβλητές
		x 1	x 2	...	x λ	...
x n + 1	β 1	ένα 11	ένα 12	...	ένα 1l	...	ένα 1n
x n + 2	β 2	21	22	...	ένα 2l	...	ένα 2n
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n + r	β2	ένα r1	ένα r2	...	ένα rl	...	ένα rn
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n + μ	β μ	ένα m1	ένα m2	...	ένα ml	...	ένα χιλ
F (x) μέγ	ΣΤ 0	-γ 1	-γ 2	...	-γ 1	...	-γ ν

Για να το κάνετε αυτό, επιλέξτε οποιοδήποτε από τα αρνητικά στοιχεία της στήλης ελεύθερου μέλους (ας είναι το b 2 που οδηγεί ή επιλύει. Εάν δεν υπάρχουν αρνητικά στοιχεία στη σειρά με ένα αρνητικό ελεύθερο μέλος, τότε το σύστημα περιορισμών είναι ασύμβατο και το Το πρόβλημα δεν έχει λύση.

Συγχρόνως, η μεταβλητή που είναι το πρώτο σημάδι αλλαγής με αύξηση του επιλεγμένου NP x l εξαιρείται από το BP. Αυτό θα είναι x n + r, ο δείκτης r του οποίου καθορίζεται από τη συνθήκη

εκείνοι. η μεταβλητή που αντιστοιχεί στη μικρότερη αναλογία του ελεύθερου μέλους προς το μέλος της επιλεγμένης περιστρεφόμενης στήλης. Αυτή η σχέση ονομάζεται απλή σχέση. Πρέπει να λαμβάνονται υπόψη μόνο οι θετικές απλές σχέσεις.

Η συμβολοσειρά που αντιστοιχεί στη μεταβλητή x n + r καλείται πρωτοπόρος ή ανεκτικός. Το στοιχείο του απλού πίνακα a rl, που στέκεται στη διασταύρωση της αρχικής σειράς και της αρχικής στήλης, ονομάζεται το στοιχείο κορυφής ή επίλυσης.Η εύρεση του περιστρεφόμενου στοιχείου καταλήγει να λειτουργεί με κάθε διαδοχικό πίνακα απλών.

3ο βήμα. Υπολογίζεται ένας νέος πίνακας simplex, τα στοιχεία του οποίου υπολογίζονται εκ νέου από τα στοιχεία του πίνακα simplex του προηγούμενου βήματος και επισημαίνονται με ένα prime, δηλ. b "j, a" ji, c "i, F" 0. Τα στοιχεία υπολογίζονται εκ νέου σύμφωνα με τους ακόλουθους τύπους:

Πρώτον, ο νέος πίνακας simplex θα συμπληρώσει τη σειρά και τη στήλη που οδηγούσαν στον προηγούμενο πίνακα simplex. Η έκφραση (5) σημαίνει ότι το στοιχείο a "rl στη θέση του αρχικού στοιχείου είναι ίσο με το αντίστροφο του στοιχείου του προηγούμενου πίνακα απλού. Τα στοιχεία της σειράς a ri διαιρούνται από το αρχικό στοιχείο και τα στοιχεία του η στήλη a jl διαιρείται επίσης από το αρχικό στοιχείο, αλλά λαμβάνονται με το αντίθετο σύμβολο. Τα στοιχεία b "r και c" l υπολογίζονται με τον ίδιο τρόπο.

Οι υπόλοιποι τύποι είναι εύκολο να γραφτούν χρησιμοποιώντας.

Το ορθογώνιο είναι κατασκευασμένο σύμφωνα με τον παλιό απλό πίνακα με τέτοιο τρόπο ώστε μία από τις διαγώνιες του να σχηματίζεται από τα επανυπολογισμένα στοιχεία (a ji) και οδηγητικά (a rl) στοιχεία (Εικ. 1). Η δεύτερη διαγώνια προσδιορίζεται μοναδικά. Για να βρείτε ένα νέο στοιχείο "ji, το προϊόν των στοιχείων της αντίθετης διαγώνιας διαιρούμενο με το αρχικό στοιχείο αφαιρείται από το στοιχείο a ji (αυτό υποδεικνύεται από το σύμβολο" - "δίπλα στο κελί). Τα στοιχεία b" j, (j ≠ r) και c "i, (i ≠ l).

4ο βήμα. Η ανάλυση ενός νέου πίνακα απλού ξεκινά με το 1ο βήμα του αλγορίθμου. Η δράση συνεχίζεται έως ότου βρεθεί μια εφικτή βασική λύση, δηλαδή όλα τα μέλη της στήλης δωρεάν μέλους πρέπει να είναι θετικά.

5ο βήμα. Πιστεύουμε ότι έχει βρεθεί μια εφικτή βασική λύση. Εξετάζουμε τους συντελεστές της γραμμής της συνάρτησης στόχου F (x). Ένα κριτήριο για τη βελτιστοποίηση ενός απλού πίνακα είναι η μη αρνητικότητα των συντελεστών για μη βασικές μεταβλητές στη σειρά F.

Σύκο. 1. Κανόνας ορθογωνίου

Εάν μεταξύ των συντελεστών της γραμμής F υπάρχουν αρνητικοί (εκτός από την αναχαίτιση), τότε πρέπει να πάτε σε μια άλλη βασική λύση. Κατά τη μεγιστοποίηση της συνάρτησης στόχου, η βάση περιλαμβάνει εκείνη των μη βασικών μεταβλητών (για παράδειγμα, x l), η στήλη της οποίας αντιστοιχεί στη μέγιστη απόλυτη τιμή του αρνητικού συντελεστή c l στην κάτω σειρά του πίνακα simplex. Αυτό καθιστά δυνατή την επιλογή της μεταβλητής της οποίας η αύξηση οδηγεί σε βελτίωση της συνάρτησης στόχου. Η στήλη που αντιστοιχεί στη μεταβλητή x l ονομάζεται η πρώτη στήλη. Ταυτόχρονα, αυτή η μεταβλητή x n + r εξαιρείται από τη βάση, ο δείκτης r της οποίας καθορίζεται από τη σχέση ελάχιστης απλής:

Η σειρά που αντιστοιχεί στο x n + r ονομάζεται το αρχικό και το στοιχείο του απλού πίνακα a rl, που στέκεται στη διασταύρωση της αρχικής σειράς και της αρχικής στήλης, καλείται ηγετικό στοιχείο.

6ο βήμα. σύμφωνα με τους κανόνες που καθορίζονται στο βήμα 3. Η διαδικασία συνεχίζεται έως ότου βρεθεί μια βέλτιστη λύση ή συμπεραίνεται ότι δεν υπάρχει.

Εάν κατά τη διάρκεια της βελτιστοποίησης της λύσης στην πρώτη στήλη όλα τα στοιχεία δεν είναι θετικά, τότε δεν μπορεί να επιλεγεί η πρώτη γραμμή. Σε αυτήν την περίπτωση, η λειτουργία στον τομέα των εφικτών λύσεων του προβλήματος δεν περιορίζεται παραπάνω και F max -> & ∞.

Εάν, στο επόμενο βήμα στην αναζήτηση ενός άκρου, μία από τις βασικές μεταβλητές γίνεται ίση με το μηδέν, τότε η αντίστοιχη βασική λύση ονομάζεται εκφυλισμός. Σε αυτήν την περίπτωση, εμφανίζεται ένα λεγόμενο βρόχο, το οποίο χαρακτηρίζεται από το γεγονός ότι με μια συγκεκριμένη συχνότητα αρχίζει να επαναλαμβάνεται ο ίδιος συνδυασμός BP (διατηρείται η τιμή της συνάρτησης F) και είναι αδύνατο να μετακινηθείτε σε μια νέα αποδεκτή βασική λύση. Ο βρόχος είναι ένα από τα κύρια μειονεκτήματα της μεθόδου simplex, αλλά είναι σχετικά σπάνιο. Στην πράξη, σε τέτοιες περιπτώσεις, συνήθως αρνούνται να εισαγάγουν στη βάση τη μεταβλητή της οποίας η στήλη αντιστοιχεί στη μέγιστη απόλυτη τιμή του αρνητικού συντελεστή στη συνάρτηση στόχου και κάνουν μια τυχαία επιλογή μιας νέας βασικής λύσης.

Παράδειγμα 1. Λύστε το πρόβλημα

μέγιστο (F (x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)

Απλή μέθοδος και δώστε μια γεωμετρική ερμηνεία της διαδικασίας λύσης.

Η γραφική ερμηνεία της λύσης του προβλήματος φαίνεται στο Σχ. 2. Η μέγιστη τιμή της συνάρτησης στόχου επιτυγχάνεται στην κορυφή του ODZP με συντεταγμένες. Ας λύσουμε το πρόβλημα χρησιμοποιώντας απλούς πίνακες. Πολλαπλασιάζουμε τον δεύτερο περιορισμό με (-1) και εισάγουμε πρόσθετες μεταβλητές για να φέρουμε ανισότητες στη μορφή ισοτιμιών, και στη συνέχεια

Οι αρχικές μεταβλητές x 1 και x 2 θεωρούνται μη βασικές και οι πρόσθετες x 3, x 4 και x 5 θεωρούνται βασικές και συνθέτουμε έναν πίνακα απλών (πίνακας 2). Λύση που αντιστοιχεί στον απλό πίνακα. Το 2 δεν είναι έγκυρο. το στοιχείο περιστροφής περιγράφεται και επιλέγεται σύμφωνα με το βήμα 2 του προηγούμενου αλγορίθμου. Ο επόμενος πίνακας simplex. 3 καθορίζει την αποδεκτή βασική λύση · αντιστοιχεί στην κορυφή του ODZP στο Σχ. 2 Το στοιχείο περιστροφής περιγράφεται και επιλέγεται σύμφωνα με το 5ο βήμα του αλγορίθμου για την επίλυση του προβλήματος. Αυτί. 4 αντιστοιχεί στη βέλτιστη λύση του προβλήματος, επομένως: x 1 = x 5 = 0; x 2 = 4; x 3 = 3; x 4 = 8; F max = 20.

Σύκο. 2. Γραφική λύση του προβλήματος

Μου άρεσε; Σελιδοδείκτης

Επίλυση προβλημάτων με τη μέθοδο simplex: διαδικτυακά παραδείγματα

Στόχος 1.Η εταιρεία κατασκευάζει ράφια μπάνιου σε δύο μεγέθη - Α και Β. Οι αντιπρόσωποι πωλήσεων εκτιμούν ότι έως 550 ράφια μπορούν να πωλούνται στην αγορά την εβδομάδα. Κάθε ράφι τύπου Α απαιτεί 2 m2 υλικού και το ράφι τύπου B απαιτεί 3 m2 υλικού. Η εταιρεία μπορεί να λάβει έως και 1200 m2 υλικού ανά εβδομάδα. Για την κατασκευή ενός ραφιού τύπου Α, απαιτούνται 12 λεπτά χρόνου μηχανής και για την κατασκευή ενός ραφιού τύπου Β - 30 λεπτά. το μηχάνημα μπορεί να χρησιμοποιηθεί 160 ώρες την εβδομάδα. Εάν το κέρδος από την πώληση ραφιών τύπου Α είναι 3 νομισματικές μονάδες και από την πώληση ραφιών τύπου Β - 4 den. μονάδες, τότε πόσα ράφια κάθε τύπου πρέπει να παράγονται την εβδομάδα;

Στόχος 2.Λύστε το πρόβλημα γραμμικού προγραμματισμού χρησιμοποιώντας τη μέθοδο simplex.

Στόχος 3.Η εταιρεία παράγει 3 τύπους προϊόντων: A1, A2, A3, χρησιμοποιώντας δύο τύπους πρώτων υλών. Είναι γνωστά το κόστος των πρώτων υλών κάθε τύπου ανά μονάδα παραγωγής, τα αποθέματα πρώτων υλών για την προγραμματισμένη περίοδο, καθώς και το κέρδος από μια μονάδα παραγωγής κάθε τύπου.

1. Πόσα προϊόντα κάθε τύπου πρέπει να παραχθούν για να λάβουν το μέγιστο κέρδος;
2. Προσδιορίστε την κατάσταση κάθε τύπου πρώτης ύλης και τη συγκεκριμένη αξία της.
3. Προσδιορίστε το μέγιστο διάστημα αλλαγών στα αποθέματα κάθε τύπου πρώτης ύλης, εντός του οποίου η δομή του βέλτιστου σχεδίου, δηλ. η ονοματολογία του τεύχους δεν θα αλλάξει.
4. Προσδιορίστε την ποσότητα των προϊόντων και το κέρδος από την απελευθέρωση με αύξηση του αποθέματος ενός από τους σπάνιους τύπους πρώτων υλών στο μέγιστο δυνατό (εντός των ορίων της δεδομένης ονοματολογίας της παραγωγής).
5. Προσδιορίστε τα διαστήματα αλλαγής στα κέρδη από μια μονάδα παραγωγής κάθε τύπου, κατά την οποία το προκύπτον βέλτιστο σχέδιο δεν θα αλλάξει.

Εργασία 4.Λύστε το πρόβλημα γραμμικού προγραμματισμού χρησιμοποιώντας τη μέθοδο simplex:

Εργασία 5.Λύστε το πρόβλημα γραμμικού προγραμματισμού χρησιμοποιώντας τη μέθοδο simplex:

Εργασία 6.Λύστε το πρόβλημα χρησιμοποιώντας τη μέθοδο simplex, λαμβάνοντας υπόψη το σχέδιο που δίνεται στην κατάσταση ως το αρχικό σχέδιο αναφοράς:

Εργασία 7.Λύστε το πρόβλημα χρησιμοποιώντας την τροποποιημένη απλή μέθοδο.
Για την παραγωγή δύο τύπων προϊόντων Α και Β, χρησιμοποιούνται τρεις τύποι τεχνολογικού εξοπλισμού. Για την παραγωγή μιας μονάδας προϊόντος Α, χρησιμοποιείται εξοπλισμός του πρώτου τύπου a1 = 4 ώρες, εξοπλισμός του δεύτερου τύπου, a2 = 8 ώρες και εξοπλισμός του τρίτου τύπου, a3 = 9 ώρες. Για την παραγωγή μιας μονάδας προϊόντος Β, χρησιμοποιείται εξοπλισμός του πρώτου τύπου b1 = 7 ώρες, εξοπλισμός του δεύτερου τύπου, b2 = 3 ώρες και εξοπλισμός του τρίτου τύπου, b3 = 5 ώρες.
Για την κατασκευή αυτών των προϊόντων, ο εξοπλισμός του πρώτου τύπου μπορεί να λειτουργήσει όχι περισσότερο από t1 = 49 ώρες, εξοπλισμός του δεύτερου τύπου όχι περισσότερο από t2 = 51 ώρες, εξοπλισμός του τρίτου τύπου όχι περισσότερο από t3 = 45 ώρες.
Το κέρδος από την πώληση μιας μονάδας τελικού προϊόντος Α είναι ALPHA = 6 ρούβλια και το προϊόν Β - BETTA = 5 ρούβλια.
Εκπονήστε ένα σχέδιο για την παραγωγή των προϊόντων Α και Β, διασφαλίζοντας το μέγιστο κέρδος από την πώληση τους.

Εργασία 8.Βρείτε τη βέλτιστη λύση με τη μέθοδο διπλού απλού

Εξετάζεται ένα παράδειγμα επίλυσης του προβλήματος με τη μέθοδο simplex, καθώς και ένα παράδειγμα επίλυσης του διπλού προβλήματος.

Το έργο

Για την πώληση τριών ομάδων αγαθών, μια εμπορική επιχείρηση διαθέτει τρεις τύπους περιορισμένων υλικών και νομισματικών πόρων στο ποσό των b 1 = 240, b 2 = 200, b 3 = 160 μονάδες. Ταυτόχρονα, για την πώληση 1 ομάδας προϊόντων για 1.000 ρούβλια. ο κύκλος εργασιών δαπανάται στον πόρο του πρώτου τύπου στο ποσό των 11 = 2 μονάδων, στον πόρο του δεύτερου τύπου στο ποσό των 21 = 4 μονάδων, στον πόρο του τρίτου τύπου στο ποσό των 31 = 4 μονάδες. Για την πώληση 2 και 3 ομάδων προϊόντων για 1.000 ρούβλια. ο κύκλος εργασιών δαπανάται, αντίστοιχα, του πόρου του πρώτου τύπου στο ποσό των 12 = 3, ενός 13 = 6 μονάδων, του πόρου του δεύτερου τύπου στο ποσό των 22 = 2, 23 = 4 μονάδων, πόρος του τρίτου τύπου στο ποσό 32 = 6, 33 = 8 μονάδες ... Κέρδος από την πώληση τριών ομάδων αγαθών για 1.000 ρούβλια. ο κύκλος εργασιών είναι, αντίστοιχα, 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 =" (! LANG: 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.

Εισάγουμε τα δεδομένα στο απλός πίνακας

Απλός αριθμός τραπεζιού 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 στη βάση.

Ορίζουμε μια μεταβλητή που αφήνει τη βάση. Για να το κάνετε αυτό, βρείτε το μικρότερο μη αρνητικό λόγο για τη στήλη x 2.

= 26.667

Μικρότερο μη αρνητικό: Q 3 = 26.667. Παράγουμε τη μεταβλητή x 6 από τη βάση

Διαιρέστε την 3η σειρά με 6.
Από την 1η γραμμή, αφαιρέστε την 3η γραμμή, πολλαπλασιασμένη επί 3
Από τη 2η γραμμή, αφαιρέστε την 3η γραμμή πολλαπλασιαζόμενη με 2

Υπολογίζουμε:

Παίρνουμε νέο τραπέζι:

Απλός αριθμός τραπεζιού 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

Υπολογίζουμε:

Παίρνουμε ένα νέο τραπέζι:

Απλός αριθμός τραπεζιού 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; x 2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x 6 = 0; F max = 160

Δηλαδή, είναι απαραίτητο να πουλήσουμε προϊόντα πρώτου τύπου σε ποσότητα 40 χιλιάδες ρούβλια. Δεν είναι απαραίτητο να πουλάτε προϊόντα 2ου και 3ου τύπου. Σε αυτήν την περίπτωση, το μέγιστο κέρδος θα είναι F max = 160 χιλιάδες ρούβλια.

Λύση του διπλού προβλήματος

Το διπλό πρόβλημα είναι:

Z = 240 y 1 + 200 y 2 + 160 y 3 -> λ

Τίτλος = "(! LANG: 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 για να μετατρέψετε τις ανισότητες σε ισοτιμίες.

Τα συζευγμένα ζεύγη μεταβλητών των άμεσων και διπλών προβλημάτων έχουν τη μορφή:

Από τον τελευταίο απλό πίνακα του αριθ. 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;