Παράδειγμα επίλυσης άμεσων και διπλών προβλημάτων με τη μέθοδο simplex. Επίλυση προβλημάτων γραμμικού προγραμματισμού με τη μέθοδο simplex
Ακολουθεί μια χειροκίνητη (όχι βοηθητική) λύση δύο προβλημάτων με τη μέθοδο simplex (παρόμοια με τη λύση μικροεφαρμογών) με λεπτομερείς εξηγήσεις για να κατανοήσετε τον αλγόριθμο για την επίλυση προβλημάτων με τη μέθοδο simplex. Το πρώτο πρόβλημα περιέχει πρόσημα ανισότητας μόνο " ≤ " (πρόβλημα με αρχική βάση), το δεύτερο μπορεί να περιέχει πρόσημα " ≥ ", " ≤ " ή " = " (πρόβλημα με τεχνητή βάση), λύνονται σε διαφορετικά τρόπους.
Μέθοδος Simplex, λύση προβλήματος με αρχική βάση
1)Μέθοδος Simplexγια ένα πρόβλημα με αρχική βάση (όλα τα σημάδια των ανισοτήτων περιορισμού είναι " ≤ ").
Ας γράψουμε το πρόβλημα κανονικόςμορφή, δηλ. ξαναγράφουμε τους περιορισμούς ανισότητας ως ισότητες, προσθέτοντας ισολογισμοίμεταβλητές:
Αυτό το σύστημα είναι ένα σύστημα με βάση (βάση s 1, s 2, s 3, καθένα από αυτά περιλαμβάνεται σε μία μόνο εξίσωση του συστήματος με συντελεστή 1), x 1 και x 2 είναι ελεύθερες μεταβλητές. Τα προβλήματα για τα οποία χρησιμοποιείται η μέθοδος simplex πρέπει να έχουν τις ακόλουθες δύο ιδιότητες: - το σύστημα περιορισμών πρέπει να είναι ένα σύστημα εξισώσεων με βάση. -Οι ελεύθεροι όροι όλων των εξισώσεων στο σύστημα πρέπει να είναι μη αρνητικοί.
Το σύστημα που προκύπτει είναι ένα σύστημα με βάση και οι ελεύθεροι όροι του είναι μη αρνητικοί, επομένως μπορούμε να εφαρμόσουμε μέθοδο simplex. Συντάξτε τον πρώτο πίνακα simplex (Επανάληψη 0) για την επίλυση του προβλήματος μέθοδο simplex, δηλ. πίνακα συντελεστών της αντικειμενικής συνάρτησης και σύστημα εξισώσεων για τις αντίστοιχες μεταβλητές. Εδώ "BP" σημαίνει τη στήλη των βασικών μεταβλητών, "Λύση" - η στήλη των δεξιών τμημάτων των εξισώσεων του συστήματος. Η λύση δεν είναι η βέλτιστη, γιατί υπάρχουν αρνητικοί συντελεστές στη γραμμή z.
επανάληψη μεθόδου simplex 0
|
Στάση |
|||||||
Για να βελτιώσουμε τη λύση, ας προχωρήσουμε στην επόμενη επανάληψη μέθοδο simplex, παίρνουμε τον παρακάτω πίνακα simplex. Για αυτό πρέπει να επιλέξετε ενεργοποίηση στήλης, δηλ. μια μεταβλητή που θα μπει στη βάση στην επόμενη επανάληψη της μεθόδου simplex. Επιλέγεται από τον μεγαλύτερο αρνητικό συντελεστή στη σειρά z (στο μέγιστο πρόβλημα) - στην αρχική επανάληψη της μεθόδου simplex, αυτή είναι η στήλη x 2 (συντελεστής -6).
Στη συνέχεια επιλέξτε συμβολοσειρά άδειας, δηλ. μια μεταβλητή που θα αφήσει τη βάση στην επόμενη επανάληψη της μεθόδου simplex. Επιλέγεται από τη μικρότερη αναλογία της στήλης "Απόφαση" προς τα αντίστοιχα θετικά στοιχεία της στήλης επίλυσης (στήλη "Αναλογία") - στην αρχική επανάληψη, αυτή είναι η σειρά s 3 (συντελεστής 20).
Επιτρεπτικό στοιχείοβρίσκεται στη διασταύρωση της στήλης επίλυσης και της σειράς επίλυσης, το κελί του επισημαίνεται με χρώμα, είναι ίσο με 1. Επομένως, στην επόμενη επανάληψη της μεθόδου simplex, η μεταβλητή x 2 θα αντικαταστήσει το s 1 στη βάση. Σημειώστε ότι η σχέση δεν αναζητείται στη συμβολοσειρά z, υπάρχει μια παύλα "-". Εάν υπάρχουν πανομοιότυπες ελάχιστες αναλογίες, τότε επιλέγεται οποιαδήποτε από αυτές. Εάν όλοι οι συντελεστές στη στήλη ανάλυσης είναι μικρότεροι ή ίσοι με 0, τότε η λύση στο πρόβλημα είναι άπειρη.
Ας συμπληρώσουμε τον παρακάτω πίνακα «Επανάληψη 1». Θα το λάβουμε από τον πίνακα "Επανάληψη 0". Ο σκοπός των περαιτέρω μετασχηματισμών είναι να μετατραπεί η στήλη ενεργοποίησης x2 σε μία στήλη (με ένα αντί για το στοιχείο ενεργοποίησης και μηδενικά αντί για τα υπόλοιπα στοιχεία).
1) Υπολογισμός της γραμμής x 2 του πίνακα "Επανάληψη 1". Αρχικά, διαιρούμε όλα τα μέλη της σειράς επίλυσης s 3 του πίνακα "Iteration 0" με το στοιχείο επίλυσης (είναι ίσο με 1 in αυτή η υπόθεση) αυτού του πίνακα, παίρνουμε τη γραμμή x 2 στον πίνακα Επαναλήψεις 1. Επειδή το στοιχείο επίλυσης σε αυτήν την περίπτωση είναι ίσο με 1, τότε η σειρά s 3 του πίνακα "Επανάληψη 0" θα ταιριάζει με τη σειρά x 2 του πίνακα "Επανάληψη 1". Η σειρά x 2 του πίνακα "Επανάληψη 1" λάβαμε 0 1 0 0 1 20, οι υπόλοιπες σειρές του πίνακα "Επανάληψη 1" θα ληφθούν από αυτήν τη σειρά και οι σειρές του πίνακα "Επανάληψη 0" ως εξής:
2) Υπολογισμός της σειράς z του πίνακα "Επανάληψη 1". Στη θέση του -6 στην πρώτη σειρά (γραμμή z) στη στήλη x2 του πίνακα "Επανάληψη 0", θα πρέπει να υπάρχει το 0 στην πρώτη σειρά του πίνακα "Επανάληψη 1". Για να γίνει αυτό, πολλαπλασιάζουμε όλα τα στοιχεία της σειράς x 2 του πίνακα "Επανάληψη 1" 0 1 0 0 1 20 επί 6, παίρνουμε 0 6 0 0 6 120 και προσθέτουμε αυτή τη σειρά με την πρώτη σειρά (z - σειρά) του πίνακα "Επανάληψη 0" -4 -6 0 0 0 0, παίρνουμε -4 0 0 0 6 120. Το μηδέν 0 εμφανίστηκε στη στήλη x 2, ο στόχος επιτεύχθηκε. Τα στοιχεία της στήλης άδειας x 2 επισημαίνονται με κόκκινο χρώμα.
3) Υπολογισμός της σειράς s 1 του πίνακα "Επανάληψη 1". Στη θέση 1 σε s, η 1 σειρά του πίνακα "Επανάληψη 0" πρέπει να είναι 0 στον πίνακα "Επανάληψη 1". Για να γίνει αυτό, πολλαπλασιάζουμε όλα τα στοιχεία της σειράς x 2 του πίνακα "Επανάληψη 1" 0 1 0 0 1 20 με -1, παίρνουμε 0 -1 0 0 -1 -20 και προσθέτουμε αυτή τη σειρά με το s 1 - το σειρά του πίνακα "Επανάληψη 0" 2 1 1 0 0 64, παίρνουμε τη σειρά 2 0 1 0 -1 44. Το απαιτούμενο 0 λαμβάνεται στη στήλη x 2.
4) Υπολογισμός της σειράς s 2 του πίνακα "Επανάληψη 1". Στη θέση 3 στη σειρά 2 του πίνακα "Επανάληψη 0" πρέπει να είναι 0 στον πίνακα "Επανάληψη 1". Για να γίνει αυτό, πολλαπλασιάζουμε όλα τα στοιχεία της σειράς x 2 του πίνακα "Επανάληψη 1" 0 1 0 0 1 20 με -3, παίρνουμε 0 -3 0 0 -3 -60 και προσθέτουμε αυτή τη σειρά με το s 1 - το σειρά του πίνακα "Επανάληψη 0" 1 3 0 1 0 72, παίρνουμε τη σειρά 1 0 0 1 -3 12. Το απαιτούμενο 0 προκύπτει στη στήλη x 2. Η στήλη x 2 στον πίνακα "Επανάληψη 1" έχει γίνει single, περιέχει το ένα 1 και το υπόλοιπο 0.
Οι σειρές του πίνακα "Επανάληψη 1" λαμβάνονται σύμφωνα με τον ακόλουθο κανόνα:
New Row = Old Row - (Old Row Permission Factor)*(New Row).
Για παράδειγμα, για τη γραμμή z έχουμε:
Παλιά συμβολοσειρά z (-4 -6 0 0 0 0) -(-6)*Νέα συμβολοσειρά z -(0 -6 0 0 -6 -120) = Νέα συμβολοσειρά z (-4 0 0 0 6 120) .
Για τους παρακάτω πίνακες, ο επανυπολογισμός των στοιχείων του πίνακα γίνεται με παρόμοιο τρόπο, οπότε τον παραλείπουμε.
επανάληψη μεθόδου simplex 1
|
Στάση |
|||||||
Επιτρεπτή στήλη x 1 , επιτρεπτή σειρά s 2 , s 2 φεύγει από τη βάση, x 1 εισάγεται στη βάση. Με τον ίδιο ακριβώς τρόπο, παίρνουμε τους υπόλοιπους πίνακες simplex μέχρι να ληφθεί ένας πίνακας με όλους τους θετικούς συντελεστές στη σειρά z. Αυτό είναι ένα σημάδι ενός βέλτιστου πίνακα.
επανάληψη μεθόδου simplex 2
|
Στάση |
|||||||
Η επίλυση της στήλης s 3 , η επίλυση της σειράς s 1 , s 1 εξέρχεται από τη βάση, το s 3 εισέρχεται στη βάση.
επανάληψη μεθόδου simplex 3
|
Στάση |
|||||||
Στη σειρά z, όλοι οι συντελεστές είναι μη αρνητικοί, επομένως, προκύπτει η βέλτιστη λύση x 1 = 24, x 2 = 16, z max = 192.
Αυτή η μέθοδος είναι μια μέθοδος στοχευμένης απαρίθμησης των λύσεων αναφοράς του προβλήματος γραμμικός προγραμματισμός. Επιτρέπει έναν πεπερασμένο αριθμό βημάτων είτε για να βρεθεί η βέλτιστη λύση είτε για να διαπιστωθεί ότι δεν υπάρχει βέλτιστη λύση.
Το κύριο περιεχόμενο της μεθόδου simplex είναι το εξής:- Καθορίστε μια μέθοδο για την εύρεση της βέλτιστης λύσης αναφοράς
- Καθορίστε τη μέθοδο μετάβασης από τη μια λύση αναφοράς στην άλλη, στην οποία η τιμή της αντικειμενικής συνάρτησης θα είναι πιο κοντά στη βέλτιστη, δηλ. υποδεικνύουν έναν τρόπο βελτίωσης της λύσης αναφοράς
- Ορίστε τα κριτήρια που σας επιτρέπουν να σταματήσετε έγκαιρα την απαρίθμηση των λύσεων υποστήριξης στη βέλτιστη λύση ή να ακολουθήσετε το συμπέρασμα ότι δεν υπάρχει βέλτιστη λύση.
Αλγόριθμος της μεθόδου simplex για την επίλυση προβλημάτων γραμμικού προγραμματισμού
Για να λυθεί το πρόβλημα μέθοδο simplexπρέπει να κάνετε τα εξής:- Φέρτε το πρόβλημα σε κανονική μορφή
- Βρείτε μια αρχική λύση αναφοράς με "βάση μονάδας" (αν δεν υπάρχει λύση αναφοράς, τότε το πρόβλημα δεν έχει λύση λόγω της ασυμβατότητας του συστήματος των περιορισμών)
- Υπολογίστε τις εκτιμήσεις των διανυσματικών επεκτάσεων ως προς τη βάση της λύσης αναφοράς και συμπληρώστε τον πίνακα της μεθόδου simplex
- Εάν το κριτήριο για τη μοναδικότητα της βέλτιστης λύσης ικανοποιηθεί, τότε η λύση του προβλήματος τελειώνει
- Εάν η προϋπόθεση για την ύπαρξη ενός συνόλου βέλτιστων λύσεων ικανοποιείται, τότε με απλή απαρίθμηση, βρίσκονται όλες οι βέλτιστες λύσεις
Ένα παράδειγμα επίλυσης του προβλήματος με τη μέθοδο simplex
Παράδειγμα 26.1Λύστε το πρόβλημα χρησιμοποιώντας τη μέθοδο simplex:
Λύση:
Φέρνουμε το πρόβλημα στην κανονική μορφή.
Για να γίνει αυτό, εισάγουμε μια πρόσθετη μεταβλητή x 6 με τον συντελεστή +1 στην αριστερή πλευρά του πρώτου περιορισμού ανισότητας. Η μεταβλητή x 6 περιλαμβάνεται στην αντικειμενική συνάρτηση με συντελεστή μηδέν (δηλαδή δεν περιλαμβάνεται).
Παίρνουμε:
Βρίσκουμε την αρχική λύση αναφοράς. Για να γίνει αυτό, εξισώνουμε τις ελεύθερες (μη λυμένες) μεταβλητές με μηδέν x1 = x2 = x3 = 0.
Παίρνουμε λύση αναφοράςΧ1 = (0.0.0.24.30.6) με βάση μονάδας Β1 = (Α4, Α5, Α6).
Υπολογίζω εκτιμήσεις αποσύνθεσης διανυσμάτωνσυνθήκες με βάση το διάλυμα αναφοράς σύμφωνα με τον τύπο:
Δ k \u003d C b X k - c k
- C b = (с 1 , с 2 , ... , σ m) είναι το διάνυσμα των συντελεστών αντικειμενικής συνάρτησης με βασικές μεταβλητές
- X k = (x 1k , x 2k , ... , x mk) είναι το διάνυσμα διαστολής του αντίστοιχου διανύσματος A k ως προς τη βάση της λύσης αναφοράς
- C k - συντελεστής της αντικειμενικής συνάρτησης για τη μεταβλητή x k.
Οι εκτιμήσεις των διανυσμάτων που περιλαμβάνονται στη βάση είναι πάντα ίσες με μηδέν. Η λύση αναφοράς, οι συντελεστές των επεκτάσεων και οι εκτιμήσεις των επεκτάσεων των διανυσμάτων συνθηκών ως προς τη βάση της λύσης αναφοράς γράφονται στο πίνακας simplex:
Πάνω από τον πίνακα, για τη διευκόλυνση του υπολογισμού των εκτιμήσεων, αναγράφονται οι συντελεστές της αντικειμενικής συνάρτησης. Η πρώτη στήλη "Β" περιέχει τα διανύσματα που περιλαμβάνονται στη βάση της λύσης αναφοράς. Η σειρά εγγραφής αυτών των διανυσμάτων αντιστοιχεί στους αριθμούς των επιτρεπόμενων αγνώστων στις εξισώσεις περιορισμών. Στη δεύτερη στήλη του πίνακα «Με β» γράφονται οι συντελεστές της αντικειμενικής συνάρτησης με βασικές μεταβλητές με την ίδια σειρά. Με τη σωστή διάταξη των συντελεστών της αντικειμενικής συνάρτησης στη στήλη «C b», οι εκτιμήσεις των μοναδιαίων διανυσμάτων που περιλαμβάνονται στη βάση είναι πάντα ίσες με μηδέν.
Στην τελευταία σειρά του πίνακα με εκτιμήσεις Δ k στη στήλη "A 0" οι τιμές της αντικειμενικής συνάρτησης αναγράφονται στη λύση αναφοράς Z(X 1).
Η αρχική λύση αναφοράς δεν είναι βέλτιστη, αφού στο μέγιστο πρόβλημα οι εκτιμήσεις Δ 1 = -2, Δ 3 = -9 για τα διανύσματα A 1 και A 3 είναι αρνητικές.
Σύμφωνα με το θεώρημα βελτίωσης της λύσης αναφοράς, εάν στο μέγιστο πρόβλημα τουλάχιστον ένα διάνυσμα έχει αρνητική εκτίμηση, τότε μπορεί να βρεθεί μια νέα λύση αναφοράς στην οποία η τιμή της αντικειμενικής συνάρτησης θα είναι μεγαλύτερη.
Ας προσδιορίσουμε ποιο από τα δύο διανύσματα θα οδηγήσει σε μεγαλύτερη αύξηση της αντικειμενικής συνάρτησης.
Η προσαύξηση της αντικειμενικής συνάρτησης βρίσκεται με τον τύπο: .
Υπολογίζουμε τις τιμές της παραμέτρου θ 01 για την πρώτη και την τρίτη στήλη χρησιμοποιώντας τον τύπο:
Παίρνουμε θ 01 = 6 για l = 1, θ 03 = 3 για l = 1 (πίνακας 26.1).
Βρίσκουμε την αύξηση της αντικειμενικής συνάρτησης όταν το πρώτο διάνυσμα ΔZ 1 = - 6 * (- 2) = 12 εισάγεται στη βάση και το τρίτο διάνυσμα ΔZ 3 = - 3 * (- 9) = 27.
Επομένως, για ταχύτερη προσέγγιση της βέλτιστης λύσης, είναι απαραίτητο να εισαχθεί το διάνυσμα Α3 στη βάση της λύσης αναφοράς αντί για το πρώτο διάνυσμα της βάσης Α6, καθώς το ελάχιστο της παραμέτρου θ 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. Επομένως, εξάγουμε το δεύτερο διάνυσμα βάσης Α4 από τη βάση. Εκτελούμε τον μετασχηματισμό Jordan με το στοιχείο x 22 = 3, λαμβάνουμε την τρίτη λύση αναφοράς X3 = (0.7.10.0.63.0) B2 = (A3, A2, A5) (πίνακας 26.3).
Αυτή η λύση είναι η μόνη βέλτιστη, αφού για όλα τα διανύσματα που δεν περιλαμβάνονται στη βάση, οι εκτιμήσεις είναι θετικές
Δ 1 \u003d 7/2, Δ 4 \u003d 2, Δ 6 \u003d 7/2.
Απάντηση: max Z(X) = 201 σε X = (0,7,10,0,63).
Μέθοδος γραμμικού προγραμματισμού στην οικονομική ανάλυση
Μέθοδος γραμμικού προγραμματισμούκαθιστά δυνατή την αιτιολόγηση της βέλτιστης οικονομικής λύσης ενόψει των σοβαρών περιορισμών που σχετίζονται με τους πόρους που χρησιμοποιούνται στην παραγωγή (πάγια στοιχεία ενεργητικού, υλικά, εργατικοί πόροι). Η εφαρμογή αυτής της μεθόδου στην οικονομική ανάλυση μας επιτρέπει να επιλύουμε προβλήματα που σχετίζονται κυρίως με τον προγραμματισμό των δραστηριοτήτων του οργανισμού. Αυτή η μέθοδος βοηθά στον προσδιορισμό των βέλτιστων τιμών εξόδου, καθώς και της κατεύθυνσης των περισσότερων αποτελεσματική χρήσητους πόρους που διαθέτει ο οργανισμός.
Χρησιμοποιώντας αυτή τη μέθοδο, πραγματοποιείται η επίλυση των λεγόμενων ακραίων προβλημάτων, η οποία συνίσταται στην εύρεση των ακραίων τιμών, δηλαδή του μέγιστου και του ελάχιστου συναρτήσεων των μεταβλητών.
Αυτή η περίοδος βασίζεται στην απόφαση του συστήματος γραμμικές εξισώσειςσε εκείνες τις περιπτώσεις που τα αναλυόμενα οικονομικά φαινόμενα συνδέονται με μια γραμμική, αυστηρά λειτουργική εξάρτηση. Η μέθοδος γραμμικού προγραμματισμού χρησιμοποιείται για την ανάλυση μεταβλητών παρουσία ορισμένων περιοριστικών παραγόντων.
Η λύση του λεγόμενου προβλήματος μεταφοράς με τη μέθοδο του γραμμικού προγραμματισμού είναι αρκετά συνηθισμένη. Το περιεχόμενο αυτής της εργασίας είναι η ελαχιστοποίηση των δαπανών που προκύπτουν σε σχέση με τη λειτουργία των οχημάτων υπό τους υφιστάμενους περιορισμούς σχετικά με τον αριθμό των οχημάτων, τη μεταφορική τους ικανότητα, τη διάρκεια της εργασίας τους, εάν υπάρχει ανάγκη εξυπηρέτησης του μέγιστου αριθμού πελατών .
Εκτός, αυτή τη μέθοδοβρίσκει ευρεία εφαρμογή στην επίλυση του προβλήματος του προγραμματισμού. Αυτό το καθήκον συνίσταται σε μια τέτοια κατανομή του χρόνου λειτουργίας του προσωπικού αυτού του οργανισμού, που θα ήταν η πιο αποδεκτή τόσο για τα μέλη αυτού του προσωπικού όσο και για τους πελάτες του οργανισμού.
Ο στόχος είναι να μεγιστοποιηθεί ο αριθμός των πελατών που εξυπηρετούνται, περιορίζοντας ταυτόχρονα τον αριθμό των διαθέσιμων μελών του προσωπικού και τις ώρες εργασίας.
Έτσι, η μέθοδος γραμμικού προγραμματισμού είναι πολύ διαδεδομένη στην ανάλυση της τοποθέτησης και χρήσης του διάφορα είδηπόρους, καθώς και στη διαδικασία σχεδιασμού και πρόβλεψης των δραστηριοτήτων των οργανισμών.
Ωστόσο, ο μαθηματικός προγραμματισμός μπορεί να εφαρμοστεί και σε εκείνα τα οικονομικά φαινόμενα, η σχέση μεταξύ των οποίων δεν είναι γραμμική. Για το σκοπό αυτό μπορούν να χρησιμοποιηθούν μέθοδοι μη γραμμικού, δυναμικού και κυρτού προγραμματισμού.
Ο μη γραμμικός προγραμματισμός βασίζεται στη μη γραμμική φύση της αντικειμενικής συνάρτησης ή των περιορισμών ή και των δύο. Οι μορφές της αντικειμενικής συνάρτησης και των ανισοτήτων περιορισμών υπό αυτές τις συνθήκες μπορεί να είναι διαφορετικές.
Ο μη γραμμικός προγραμματισμός χρησιμοποιείται στην οικονομική ανάλυση, ιδίως όταν καθορίζεται η σχέση μεταξύ δεικτών που εκφράζουν την αποτελεσματικότητα των δραστηριοτήτων του οργανισμού και τον όγκο αυτής της δραστηριότητας, τη δομή του κόστους παραγωγής, τις συνθήκες της αγοράς κ.λπ.
Ο δυναμικός προγραμματισμός βασίζεται στη δημιουργία ενός δέντρου αποφάσεων. Κάθε βαθμίδα αυτού του δέντρου χρησιμεύει ως στάδιο για τον προσδιορισμό των συνεπειών της προηγούμενης απόφασης και για την εξάλειψη των αναποτελεσματικών παραλλαγών αυτής της απόφασης. Έτσι, ο δυναμικός προγραμματισμός έχει χαρακτήρα πολλαπλών βημάτων, πολλαπλών σταδίων. Αυτός ο τύπος προγραμματισμού χρησιμοποιείται στην οικονομική ανάλυση προκειμένου να βρεθούν οι καλύτερες επιλογές για την ανάπτυξη του οργανισμού τόσο τώρα όσο και στο μέλλον.
Ο κυρτός προγραμματισμός είναι ένας τύπος μη γραμμικού προγραμματισμού. Αυτός ο τύπος προγραμματισμού εκφράζει τη μη γραμμική φύση της σχέσης μεταξύ των αποτελεσμάτων των δραστηριοτήτων του οργανισμού και των δαπανών που πραγματοποιούνται από αυτόν. Ο κυρτός (αλλιώς κοίλος) προγραμματισμός αναλύει κυρτές αντικειμενικές συναρτήσεις και κυρτά συστήματα περιορισμού (σημεία επιτρεπόμενες τιμές). Ο κυρτός προγραμματισμός χρησιμοποιείται στην ανάλυση της οικονομικής δραστηριότητας για την ελαχιστοποίηση του κόστους και ο κοίλος προγραμματισμός χρησιμοποιείται για τη μεγιστοποίηση του εισοδήματος υπό τις συνθήκες των υφιστάμενων περιορισμών στη δράση των παραγόντων που επηρεάζουν τους αναλυόμενους δείκτες αντίθετα. Κατά συνέπεια, υπό τους τύπους προγραμματισμού που εξετάζουμε, οι κυρτές αντικειμενικές συναρτήσεις ελαχιστοποιούνται και οι κοίλες μεγιστοποιούνται.
Εάν πρέπει να λύσετε ένα πρόβλημα γραμμικού προγραμματισμού χρησιμοποιώντας πίνακες simplex, τότε το δικό μας ηλεκτρονική υπηρεσίαθα σας βοηθήσει πολύ. Η μέθοδος simplex συνεπάγεται μια διαδοχική απαρίθμηση όλων των κορυφών του εύρους των αποδεκτών τιμών προκειμένου να βρεθεί η κορυφή όπου η συνάρτηση παίρνει μια ακραία τιμή. Στο πρώτο στάδιο, βρίσκεται κάποια λύση, η οποία βελτιώνεται σε κάθε επόμενο βήμα. Μια τέτοια λύση ονομάζεται βασική. Ακολουθεί μια ακολουθία ενεργειών κατά την επίλυση ενός προβλήματος γραμμικού προγραμματισμού χρησιμοποιώντας τη μέθοδο simplex:
Το πρώτο βήμα. Στον καταρτισμένο πίνακα, πρώτα απ 'όλα, πρέπει να κοιτάξετε τη στήλη με τα ελεύθερα μέλη. Εάν περιέχει αρνητικά στοιχεία, τότε είναι απαραίτητο να προχωρήσετε στο δεύτερο βήμα, εάν όχι, τότε στο πέμπτο.
Δεύτερο βήμα. Στο δεύτερο βήμα, είναι απαραίτητο να αποφασίσετε ποια μεταβλητή να εξαιρέσετε από τη βάση και ποια να συμπεριλάβετε για να υπολογίσετε εκ νέου τον πίνακα του simplex. Για να το κάνουμε αυτό, κοιτάμε τη στήλη με ελεύθερα μέλη και βρίσκουμε ένα αρνητικό στοιχείο σε αυτήν. Μια γραμμή με αρνητικό στοιχείο θα ονομάζεται η κύρια. Σε αυτό βρίσκουμε το μέγιστο αρνητικό στοιχείο σε απόλυτη τιμή, η στήλη που αντιστοιχεί σε αυτό είναι ο ακόλουθος. Εάν υπάρχουν αρνητικές τιμές μεταξύ των ελεύθερων μελών, αλλά όχι στην αντίστοιχη σειρά, τότε ένας τέτοιος πίνακας δεν θα έχει λύσεις. Η μεταβλητή στην πρώτη γραμμή, η οποία βρίσκεται στη στήλη των ελεύθερων μελών, εξαιρείται από τη βάση και η μεταβλητή που αντιστοιχεί στην πρώτη στήλη περιλαμβάνεται στη βάση.
Τραπέζι 1.
| μεταβλητές βάσης | Δωρεάν μέλη σε περιορισμούς | Μη βασικές μεταβλητές | |||||
| x 1 | x2 | ... | x l | ... | x n | ||
| xn+1 | β 1 | ένα 11 | ένα 12 | ... | ένα 1 λίτρο | ... | ένα 1n |
| xn+2 | β 2 | ένα 21 | ένα 22 | ... | ένα 2 λ | ... | ένα 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+r | β2 | ένα r1 | ένα r2 | ... | ένα rl | ... | ένα rn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+m | b m | ένα m1 | ένα m2 | ... | aml | ... | αμν |
| F(x)max | F0 | -γ 1 | -γ 2 | ... | -γ 1 | ... | -c n |
Τρίτο βήμα. Στο τρίτο βήμα, υπολογίζουμε ξανά ολόκληρο τον πίνακα simplex χρησιμοποιώντας ειδικούς τύπους, αυτοί οι τύποι μπορούν να φανούν χρησιμοποιώντας .
Τέταρτο βήμα. Εάν, μετά τον επανυπολογισμό, παραμένουν αρνητικά στοιχεία στη στήλη των ελεύθερων μελών, τότε μεταβείτε στο πρώτο βήμα, εάν δεν υπάρχει κανένα, τότε μεταβείτε στο πέμπτο.
Πέμπτο βήμα. Εάν έχετε φτάσει στο πέμπτο βήμα, τότε έχετε βρει μια λύση που είναι αποδεκτή. Ωστόσο, αυτό δεν σημαίνει ότι είναι βέλτιστο. Θα είναι βέλτιστο μόνο εάν όλα τα στοιχεία στη σειρά F είναι θετικά. Εάν αυτό δεν συμβαίνει, τότε είναι απαραίτητο να βελτιώσουμε τη λύση, για την οποία βρίσκουμε την πρώτη γραμμή και στήλη για τον επόμενο επανυπολογισμό σύμφωνα με τον ακόλουθο αλγόριθμο. Αρχικά, βρίσκουμε τον ελάχιστο αρνητικό αριθμό στη σειρά F, εξαιρουμένης της τιμής της συνάρτησης. Η στήλη με αυτόν τον αριθμό θα είναι η πρώτη. Για να βρούμε την πρώτη γραμμή, βρίσκουμε την αναλογία του αντίστοιχου ελεύθερου μέλους και του στοιχείου από την προπορευόμενη στήλη, με την προϋπόθεση ότι είναι θετικά. Η ελάχιστη αναλογία θα καθορίσει την κύρια γραμμή. Υπολογίζουμε ξανά τον πίνακα σύμφωνα με τους τύπους, δηλ. μεταβείτε στο βήμα 3.
Μέθοδος Simplexείναι μια επαναληπτική διαδικασία κατευθυνόμενης λύσης ενός συστήματος εξισώσεων σε βήματα, η οποία ξεκινά με μια λύση αναφοράς και αναζητά η καλύτερη επιλογήκινείται κατά μήκος των γωνιακών σημείων της περιοχής εφικτής λύσης που βελτιώνουν την τιμή της αντικειμενικής συνάρτησης έως ότου η αντικειμενική συνάρτηση φτάσει τη βέλτιστη τιμή.Ανάθεση υπηρεσίας. Η υπηρεσία προορίζεται για διαδικτυακές λύσειςΠροβλήματα γραμμικού προγραμματισμού (LPP) χρησιμοποιώντας τη μέθοδο simplex στις ακόλουθες μορφές:
- με τη μορφή πίνακα simplex (μέθοδος μετασχηματισμών Jordan). βασική μορφή εγγραφής?
- Τροποποιημένη μέθοδος Simplex. σε μορφή στήλης? σε μορφή γραμμής.
Εντολή. Επιλέξτε τον αριθμό των μεταβλητών και τον αριθμό των σειρών (αριθμός περιορισμών). Το διάλυμα που προκύπτει αποθηκεύεται σε Αρχείο Wordκαι υπερέχει.
Σε αυτήν την περίπτωση, μην λαμβάνετε υπόψη περιορισμούς του τύπου x i ≥ 0. Εάν δεν υπάρχουν περιορισμοί στην εργασία για κάποιο x i, τότε το LLP πρέπει να μειωθεί σε KZLP ή να χρησιμοποιήσετε αυτήν την υπηρεσία. Η λύση καθορίζει αυτόματα τη χρήση M-μέθοδος(απλή μέθοδος με τεχνητή βάση) και μέθοδος απλού δύο σταδίων.Τα ακόλουθα χρησιμοποιούνται επίσης με αυτήν την αριθμομηχανή:
Γραφική μέθοδος επίλυσης LLP
Λύση του μεταφορικού προβλήματος
Λύση παιχνιδιού Matrix
Με τη βοήθεια της υπηρεσίας online λειτουργίαμπορείτε να προσδιορίσετε την τιμή του παιχνιδιού matrix (κάτω και άνω όρια), ελέγξτε την παρουσία σημείο σέλας, βρείτε μια λύση στη μικτή στρατηγική με μεθόδους: minimax, μέθοδος simplex, γραφική (γεωμετρική) μέθοδος, μέθοδος Brown.
Ακρότατο συνάρτησης δύο μεταβλητών
Προβλήματα δυναμικού προγραμματισμού
Διανείμετε 5 ομοιογενείς παρτίδες αγαθών σε τρεις αγορές με τέτοιο τρόπο ώστε να έχετε το μέγιστο εισόδημα από την πώλησή τους. Τα έσοδα από την πώληση σε κάθε αγορά G(X) εξαρτώνται από τον αριθμό των πωληθέντων παρτίδων αγαθών 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 , δείτε το παράδειγμα επίλυσης της μεγιστοποίησης της συνάρτησης)
Μια ακραία λύση επιτυγχάνεται στο όριο της περιοχής των εφικτών λύσεων σε μία από τις κορυφές των γωνιακών σημείων του πολυγώνου ή στο τμήμα μεταξύ δύο γειτονικών γωνιακών σημείων.
Θεμελιώδες θεώρημα γραμμικού προγραμματισμού. Εάν η συνάρτηση στόχου LLP φτάσει σε μια ακραία τιμή σε κάποιο σημείο στην περιοχή των εφικτών λύσεων, τότε παίρνει αυτήν την τιμή στο γωνιακό σημείο. Εάν η συνάρτηση στόχου LLP φτάσει σε μια ακραία τιμή σε περισσότερα από ένα γωνιακά σημεία, τότε παίρνει την ίδια τιμή σε οποιονδήποτε από τους κυρτούς γραμμικούς συνδυασμούς αυτών των σημείων.
Η ουσία της μεθόδου simplex. Η κίνηση προς το βέλτιστο σημείο πραγματοποιείται μετακινώντας από το ένα γωνιακό σημείο στο επόμενο, το οποίο φέρνει όλο και πιο γρήγορα το X opt. Ένα τέτοιο σχήμα απαρίθμησης σημείων, ονομάζεται μέθοδος simplex, που προτείνει ο R. Danzig.
Τα γωνιακά σημεία χαρακτηρίζονται από m βασικές μεταβλητές, επομένως η μετάβαση από ένα γωνιακό σημείο σε ένα γειτονικό μπορεί να γίνει αλλάζοντας μόνο μία βασική μεταβλητή στη βάση σε μια μεταβλητή από τη μη βάση.
Η εφαρμογή της μεθόδου simplex, λόγω των διαφόρων χαρακτηριστικών και διατυπώσεων των προβλημάτων LP, έχει διάφορες τροποποιήσεις.
Η κατασκευή πινάκων simplex συνεχίζεται μέχρι να επιτευχθεί η βέλτιστη λύση. Πώς να χρησιμοποιήσετε έναν πίνακα simplex για να προσδιορίσετε ότι η λύση ενός προβλήματος γραμμικού προγραμματισμού είναι η βέλτιστη;
Εάν η τελευταία σειρά (τιμές αντικειμενικών συναρτήσεων) δεν περιέχει αρνητικά στοιχεία, τότε θα βρει το βέλτιστο σχέδιο.
Παρατήρηση 1. Εάν μία από τις βασικές μεταβλητές είναι ίση με μηδέν, τότε το ακραίο σημείο που αντιστοιχεί σε μια τέτοια βασική λύση είναι εκφυλισμένο. Ο εκφυλισμός εμφανίζεται όταν υπάρχει ασάφεια στην επιλογή της πρώτης σειράς. Μπορεί να μην παρατηρήσετε καθόλου τον εκφυλισμό του προβλήματος εάν επιλέξετε μια άλλη γραμμή ως οδηγό. Σε περίπτωση ασάφειας, θα πρέπει να επιλέγεται η σειρά με τον χαμηλότερο δείκτη για να αποφευχθεί ο βρόχος.
Παρατήρηση 2. Έστω σε κάποιο ακραίο σημείο όλες οι διαφορές του απλού να είναι μη αρνητικές D k ³ 0 (k = 1..n+m), δηλ. προκύπτει η βέλτιστη λύση και υπάρχει τέτοιο Α k - ένα μη βασικό διάνυσμα, για το οποίο D k = 0. Τότε το μέγιστο επιτυγχάνεται τουλάχιστον σε δύο σημεία, δηλ. υπάρχει ένα εναλλακτικό βέλτιστο. Εάν εισάγουμε αυτή τη μεταβλητή x k στη βάση, η τιμή της αντικειμενικής συνάρτησης δεν θα αλλάξει.
Παρατήρηση 3. Η λύση του διπλού προβλήματος βρίσκεται στον τελευταίο πίνακα simplex. Οι τελευταίες m συνιστώσες του διανύσματος των διαφορών του απλού (σε στήλες των μεταβλητών ισορροπίας) είναι η βέλτιστη λύση του διπλού προβλήματος. Εννοια αντικειμενικές λειτουργίεςάμεσα και διπλά προβλήματα συμπίπτουν στα βέλτιστα σημεία.
Παρατήρηση 4. Κατά την επίλυση του προβλήματος ελαχιστοποίησης, το διάνυσμα με τη μεγαλύτερη θετική διαφορά απλού εισάγεται στη βάση. Επιπλέον, εφαρμόζεται ο ίδιος αλγόριθμος όπως και για το πρόβλημα μεγιστοποίησης.
Αν τεθεί η προϋπόθεση «Είναι απαραίτητο να καταναλωθούν πλήρως οι πρώτες ύλες τύπου III», τότε η αντίστοιχη προϋπόθεση είναι ισότητα.
Για την κατασκευή τριών τύπων πουκάμισων χρησιμοποιούνται κλωστές, κουμπιά και ύφασμα. Τα αποθέματα κλωστών, κουμπιών και υφασμάτων, τα ποσοστά κατανάλωσής τους για το ράψιμο ενός πουκάμισου αναφέρονται στον πίνακα. Βρείτε το μέγιστο κέρδος και το βέλτιστο πρόγραμμα κυκλοφορίας προϊόντος που το εξασφαλίζει (εύρεση ).
| πουκάμισο 1 | πουκάμισο 2 | πουκάμισο 3 | Αποθέματα | κλωστές (μ.) | 1 | 9 | 3 | 96 | κουμπιά (τεμ.) | 20 | 10 | 30 | 640 | το πανί ( | 1 | 2 | 2 | 44 | Κέρδος (R.) | 2 | 5 | 4 |
Η λύση του προβλήματος
Πρότυπο κτίριο
Μέσω και τον αριθμό των πουκάμισων του 1ου, 2ου και 3ου τύπου, που προορίζονται για κυκλοφορία.
Τότε τα όρια πόρων θα μοιάζουν με αυτό:
Επιπλέον, σύμφωνα με το νόημα της εργασίας
Συνάρτηση στόχος που εκφράζει το ληφθέν κέρδος:
Λαμβάνουμε το ακόλουθο πρόβλημα γραμμικού προγραμματισμού:
Αναγωγή ενός προβλήματος γραμμικού προγραμματισμού σε κανονική μορφή
Ας φέρουμε το πρόβλημα στην κανονική μορφή. Ας εισάγουμε πρόσθετες μεταβλητές. Εισάγουμε όλες τις πρόσθετες μεταβλητές στην αντικειμενική συνάρτηση με συντελεστή ίσο με μηδέν. Προσθέτουμε επιπλέον μεταβλητές στα αριστερά μέρη των περιορισμών που δεν έχουν προτιμώμενη μορφή και παίρνουμε ισότητες.
Επίλυση του προβλήματος με τη μέθοδο simplex
Συμπληρώστε τον πίνακα simplex:
Δεδομένου ότι λύνουμε το πρόβλημα για το μέγιστο, η παρουσία αρνητικών αριθμών στη γραμμή δείκτη κατά την επίλυση του προβλήματος για το μέγιστο υποδηλώνει ότι δεν έχουμε λάβει τη βέλτιστη λύση και ότι είναι απαραίτητο να μετακινηθούμε από τον πίνακα της 0ης επανάληψης στο το επόμενο.
Η μετάβαση στην επόμενη επανάληψη πραγματοποιείται ως εξής:
αντιστοιχίες κορυφαίων στηλών
Η βασική γραμμή καθορίζεται από τις ελάχιστες αναλογίες ελεύθερων μελών και μελών της κύριας στήλης (αναλογίες απλών):
Στη διασταύρωση της στήλης κλειδιού και της γραμμής κλειδιού, βρίσκουμε το στοιχείο ενεργοποίησης, δηλ. εννέα.
Τώρα ας αρχίσουμε να συντάσσουμε την 1η επανάληψη: Αντί για μοναδιαίο διάνυσμα, εισάγουμε ένα διάνυσμα .
ΣΕ νέο τραπέζιγράφουμε 1 στη θέση του στοιχείου ενεργοποίησης, όλα τα άλλα στοιχεία της στήλης κλειδιού είναι μηδενικά. Τα βασικά στοιχεία συμβολοσειράς διαιρούνται με το επιτρεπτικό στοιχείο. Όλα τα άλλα στοιχεία του πίνακα υπολογίζονται σύμφωνα με τον κανόνα του ορθογωνίου.
Βασική στήλη για αντιστοιχίσεις 1ης επανάληψης
Το στοιχείο επίλυσης είναι ο αριθμός 4/3. Συνάγουμε το διάνυσμα από τη βάση και εισάγουμε το διάνυσμα. Παίρνουμε τον πίνακα της 2ης επανάληψης.
Η στήλη κλειδιού για τη 2η επανάληψη αντιστοιχεί σε
Βρίσκουμε τη γραμμή κλειδιού, για αυτό ορίζουμε:
Το στοιχείο επίλυσης είναι ο αριθμός 10/3. Συνάγουμε το διάνυσμα από τη βάση και εισάγουμε το διάνυσμα. Παίρνουμε τον πίνακα της 3ης επανάληψης.
| № | BP | γ Β | Α ο | x 1 | x2 | x 3 | x4 | x5 | x6 | Simplex | 2 | 5 | 4 | 0 | 0 | 0 | συγγένειες | 0 | x4 | 0 | 96 | 1 | 9 | 3 | 1 | 0 | 0 | 32/3 | x5 | 0 | 640 | 20 | 10 | 30 | 0 | 1 | 0 | 64 | x6 | 0 | 44 | 1 | 2 | 2 | 0 | 0 | 1 | 22 | F j - c j | 0 | -2 | -5 | -4 | 0 | 0 | 0 | 1 | x2 | 5 | 32/3 | 1/9 | 1 | 1/3 | 1/9 | 0 | 0 | 32 | x5 | 0 | 1600/3 | 170/9 | 0 | 80/3 | -10/9 | 1 | 0 | 20 | x6 | 0 | 68/3 | 7/9 | 0 | 4/3 | -2/9 | 0 | 1 | 17 | F j - c j | 160/3 | -13/9 | 0 | -7/3 | 5/9 | 0 | 0 | 2 | x2 | 5 | 5 | -1/12 | 1 | 0 | 1/6 | 0 | -1/4 | -- | x5 | 0 | 80 | 10/3 | 0 | 0 | 10/3 | 1 | -20 | 24 | x 3 | 4 | 17 | 7/12 | 0 | 1 | -1/6 | 0 | 3/4 | 204/7 | F j - c j | 93 | -1/12 | 0 | 0 | 1/6 | 0 | 7/4 | 3 | x2 | 5 | 7 | 0 | 1 | 0 | 1/4 | 1/40 | -3/4 | x 1 | 2 | 24 | 1 | 0 | 0 | 1 | 3/10 | -6 | x 3 | 4 | 3 | 0 | 0 | 1 | -3/4 | -7/40 | 17/4 | F j - c j | 95 | 0 | 0 | 0 | 1/4 | 1/40 | 5/4 |
Στη γραμμή ευρετηρίου, όλα τα μέλη είναι μη αρνητικά, οπότε προκύπτει η ακόλουθη λύση του προβλήματος γραμμικού προγραμματισμού (το γράφουμε από τη στήλη των ελεύθερων μελών):
Είναι απαραίτητο να ράψετε 24 πουκάμισα 1ου τύπου, 7 πουκάμισα 2ου τύπου και 3 πουκάμισα 3ου τύπου. Σε αυτή την περίπτωση, το κέρδος που θα ληφθεί θα είναι μέγιστο και θα ανέλθει σε 95 ρούβλια.
Μπορείτε να βρείτε βοήθεια για την επίλυση των προβλημάτων σας σε αυτό το θέμα στέλνοντας ένα μήνυμα στο VKontakte, στο Viber ή συμπληρώνοντας τη φόρμα. Το κόστος επίλυσης της εργασίας για το σπίτι ξεκινά από 7 BYR. ανά εργασία (200 ρωσικά ρούβλια), αλλά όχι λιγότερο από 10 ρούβλια Λευκορωσίας. (300 ρωσικά ρούβλια) για ολόκληρη την παραγγελία. Λεπτομερής διάταξη. Το κόστος βοήθειας στις διαδικτυακές εξετάσεις (σε αυτή την περίπτωση απαιτείται προπληρωμή 100%) - από 30 BYR. (1000 Ρωσικά ρούβλια) για την απόφαση του εισιτηρίου.
