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

Ο γραμμικός προγραμματισμός διαμορφώθηκε ως ξεχωριστό τμήμα των εφαρμοσμένων μαθηματικών στις δεκαετίες 40 - 50. 20ος αιώνας χάρη στο έργο του σοβιετικού επιστήμονα, βραβευμένου με Νόμπελ L.V. Καντόροβιτς. Το 1939 δημοσίευσε το έργο «Μαθηματικές Μέθοδοι Οργάνωσης και Σχεδιασμού Παραγωγής», στο οποίο, χρησιμοποιώντας μαθηματικά, έλυνε οικονομικά προβλήματα σχετικά με την καλύτερη φόρτωση μηχανών, την κοπή υλικών με το χαμηλότερο κόστος, τη διανομή αγαθών σε διάφορους τρόπους μεταφοράς. και άλλοι, προτείνοντας τη μέθοδο επίλυσης παραγόντων 8 .

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

Η έννοια του γραμμικού προγραμματισμού εισήχθη από τον Αμερικανό μαθηματικό D. Dantzig, ο οποίος το 1949 πρότεινε έναν αλγόριθμο για την επίλυση ενός προβλήματος γραμμικού προγραμματισμού, που ονομάζεται «μέθοδος Simplex».

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

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

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

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

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

Ορισμός 1 9 . Ο γραμμικός προγραμματισμός (LP) είναι ένας κλάδος του μαθηματικού προγραμματισμού, ο οποίος είναι κλάδος των μαθηματικών και μελετά μεθόδους εύρεσης ακραίων (μεγαλύτερων και μικρότερων) τιμών μιας γραμμικής συνάρτησης πεπερασμένου αριθμού μεταβλητών, στα άγνωστα των οποίων γραμμικοί περιορισμοί επιβάλλονται.

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

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

Ένα γενικό πρόβλημα γραμμικού προγραμματισμού (LPP) είναι να βρεθεί η ακραία τιμή (μέγιστη ή ελάχιστη) μιας γραμμικής συνάρτησης που ονομάζεται στόχος 10:

από n μεταβλητές Χ 1 , Χ 2 , …, Χ nμε επιβαλλόμενους λειτουργικούς περιορισμούς:

(3.2)

και άμεσοι περιορισμοί (απαίτηση μη αρνητικότητας μεταβλητών)

, (3.3)

όπου ένα ij , σι Εγώ , ντο ιδίνονται σταθερές.

Στο σύστημα των περιορισμών (3.2), τα πρόσημα "μικρότερο ή ίσο με", "ίσο με", "μεγαλύτερο ή ίσο με" μπορούν να εμφανίζονται ταυτόχρονα.

Το ZLP σε μια συντομότερη σημειογραφία έχει τη μορφή:

,

με περιορισμούς:

;

.

Διάνυσμα ` Χ = (Χ 1 , Χ 2 , …, Χ n) των οποίων τα στοιχεία ικανοποιούν τους λειτουργικούς και άμεσους περιορισμούς του προβλήματος ονομάζονται σχέδιο(ή αποδεκτή λύση) ZLP.

Σχηματίζονται όλες οι αποδεκτές λύσεις τομέα προβλήματα γραμμικού προγραμματισμού ή γκάμα εφικτών λύσεων (ODR). Εφικτή λύση που αποδίδει το μέγιστο ή το ελάχιστο της αντικειμενικής συνάρτησης φά(`Χ), ονομάζεται βέλτιστο σχέδιο προβλήματος και συμβολίζεται φά(`Χ * ), όπου ` Χ * =(Χ 1 * , Χ 2 * , …, Χ n * ).

Μια άλλη μορφή γραφής ZLP:

,

όπου φά(`Χ * ) είναι η μέγιστη (ελάχιστη) τιμή φά(ΑΠΟ, Χ) ανέλαβε όλες τις λύσεις που περιλαμβάνονται στο σετ ΠΙΘΑΝΕΣ ΛΥΣΕΙΣ Χ .

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

Για τη σύνταξη ενός μαθηματικού μοντέλου, είναι απαραίτητο:

1) ορίστε μεταβλητές.

2) συνθέτουν μια αντικειμενική συνάρτηση με βάση τον στόχο της εργασίας.

3) καταγράψτε ένα σύστημα περιορισμών, λαμβάνοντας υπόψη τους δείκτες στην κατάσταση του προβλήματος και τα ποσοτικά τους πρότυπα.

2. Η έννοια του γραμμικού προγραμματισμού. Τύποι προβλημάτων γραμμικού προγραμματισμού

Ο γραμμικός προγραμματισμός (LP) είναι ένα από τα πρώτα και πιο διεξοδικά μελετημένα τμήματα του μαθηματικού προγραμματισμού. Ήταν ο γραμμικός προγραμματισμός που ήταν το τμήμα από το οποίο άρχισε να αναπτύσσεται η ίδια η πειθαρχία του «μαθηματικού προγραμματισμού». Ο όρος "προγραμματισμός" στο όνομα του κλάδου δεν έχει καμία σχέση με τον όρο "προγραμματισμός (δηλαδή, μεταγλώττιση ενός προγράμματος) για έναν υπολογιστή" δεν έχει καμία σχέση με αυτόν. η πειθαρχία του «γραμμικού προγραμματισμού» προέκυψε πριν από την εποχή που οι υπολογιστές άρχισαν να χρησιμοποιούνται ευρέως για την επίλυση μαθηματικών, μηχανικών, οικονομικών και άλλων προβλημάτων.

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

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

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

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

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

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

Γραφική μέθοδος για την επίλυση του προβλήματος LP.

Μέθοδος Simplex;

Επίλυση του προβλήματος LP χρησιμοποιώντας το υπολογιστικό φύλλο Excel.

3. Η έννοια του μη γραμμικού προγραμματισμού

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

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

Σε αυτό το άρθρο, θα εξετάσουμε μια τέτοια μέθοδο για την επίλυση προβλημάτων NP όπως η μέθοδος των πολλαπλασιαστών Lagrange.

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

4. Δυναμικός προγραμματισμός

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

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

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

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

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

Αφήστε τη διαδικασία βελτιστοποίησης να χωριστεί σε n βήματα. Σε κάθε βήμα, είναι απαραίτητο να οριστούν δύο τύποι μεταβλητών - μια μεταβλητή κατάστασης S και μια μεταβλητή ελέγχου X. Η μεταβλητή S καθορίζει σε ποιες καταστάσεις μπορεί να βρίσκεται το σύστημα δίνεται κ-ουβήμα. Ανάλογα με το S, μπορούν να εφαρμοστούν ορισμένα στοιχεία ελέγχου σε αυτό το βήμα, τα οποία χαρακτηρίζονται από τη μεταβλητή X. Η εφαρμογή του ελέγχου X στο kth βήμα φέρνει κάποιο αποτέλεσμα Wk(S,Xk) και θέτει το σύστημα σε κάποια νέα κατάσταση S"(S Για κάθε πιθανή κατάσταση στο kth βήμα, μεταξύ όλων των δυνατών ελέγχων, ο βέλτιστος έλεγχος X*k επιλέγεται έτσι ώστε το αποτέλεσμα που επιτυγχάνεται στα βήματα από k έως n να είναι βέλτιστο. Το αριθμητικό χαρακτηριστικό αυτού του αποτελέσματος ονομάζεται Η συνάρτηση Bellman Fk(S) εξαρτάται από τον αριθμό βήματος k και την κατάσταση του συστήματος S.

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

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

ΣΕ γενική εικόναΤο πρόβλημα δυναμικού προγραμματισμού διατυπώνεται ως εξής: απαιτείται να προσδιοριστεί ένας τέτοιος έλεγχος X* που μεταφέρει το σύστημα από την αρχική κατάσταση S0 στην τελική κατάσταση Sn, στην οποία η αντικειμενική συνάρτηση F(S0,X*) παίρνει τη μεγαλύτερη ( μικρότερη) αξία.

Τα χαρακτηριστικά του μαθηματικού μοντέλου δυναμικού προγραμματισμού είναι τα εξής:

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

η αντικειμενική συνάρτηση είναι αθροιστική και ισούται με το άθροισμα των αντικειμενικών συναρτήσεων κάθε βήματος

η επιλογή του χειριστηρίου Xk σε κάθε βήμα εξαρτάται μόνο από την κατάσταση του συστήματος σε αυτό το βήμα Sk-1 και δεν επηρεάζει τα προηγούμενα βήματα (όχι ανατροφοδότηση);

η κατάσταση του συστήματος Sk μετά από κάθε βήμα ελέγχου εξαρτάται μόνο από την προηγούμενη κατάσταση του συστήματος Sk-1 και από αυτήν την ενέργεια ελέγχου Xk (χωρίς επακόλουθο) και μπορεί να γραφτεί ως εξίσωση κατάστασης:

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

ο βέλτιστος έλεγχος X* είναι ένα διάνυσμα που καθορίζεται από την ακολουθία βέλτιστων σταδιακών ελέγχων:

X*=(X*1, X*2, …, X*k, …, X*n),

ο αριθμός των οποίων καθορίζει τον αριθμό των βημάτων της εργασίας.

Βελτιστοποίηση υπό όρους. Όπως σημειώθηκε παραπάνω, στις αυτό το στάδιοΗ συνάρτηση Bellman και τα βέλτιστα χειριστήρια βρίσκονται για όλες τις πιθανές καταστάσεις σε κάθε βήμα, ξεκινώντας από το τελευταίο, σύμφωνα με τον αλγόριθμο backsweep. Στο τελευταία ντηΤο βήμα για να βρείτε το βέλτιστο στοιχείο ελέγχου X*n και την τιμή της συνάρτησης Bellman Fn(S) δεν είναι δύσκολο, καθώς

Fn(S)=max(Wn(S, Xn)),

όπου αναζητείται το μέγιστο σε όλες τις πιθανές τιμές του Xn.

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

Fk(S)=max(Wk(S,Xk)+Fk+1(S"(S,Xk))). (1)

Αυτό το μέγιστο (ή το ελάχιστο) καθορίζεται από όλες τις πιθανές τιμές της μεταβλητής ελέγχου X για k και S.

Βελτιστοποίηση χωρίς όρους. Αφού βρεθούν η συνάρτηση Bellman και τα αντίστοιχα βέλτιστα στοιχεία ελέγχου για όλα τα βήματα από το nο έως το πρώτο (στο πρώτο βήμα k=1, η κατάσταση του συστήματος είναι ίση με την αρχική του κατάσταση S0), το δεύτερο στάδιο επίλυσης του προβλήματος διεξάγεται. Ο βέλτιστος έλεγχος βρίσκεται στο πρώτο βήμα X1, η εφαρμογή του οποίου θα φέρει το σύστημα στην κατάσταση S1(S,x1*), γνωρίζοντας το οποίο, χρησιμοποιώντας τα αποτελέσματα της βελτιστοποίησης υπό όρους, μπορούμε να βρούμε τον βέλτιστο έλεγχο στο δεύτερο βήμα , και ούτω καθεξής μέχρι το τελευταίο ένατο βήμα.

Εργαστηριακές εργασίες#1 (πρόβλημα γραμμικού προγραμματισμού)

Για μια δεδομένη μαθηματική διατύπωση του προβλήματος LP, υποθέτοντας την πρόσθετη συνθήκη της μη αρνητικότητας των μεταβλητών, εκτελέστε τις ακόλουθες ενέργειες:

Λύστε το πρόβλημα γραφικά.

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

Φτιάξτε έναν πίνακα simplex.

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

Πραγματοποιήστε σταδιοποίηση διπλό πρόβλημα LP;

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

Ελέγξτε τα αποτελέσματα της λύσης σε ένα υπολογιστικό φύλλο του Excel.

Ετοιμάστε μια αναφορά με αποτελέσματα για κάθε στοιχείο.

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

, παίρνουμε

σχεδιάστε τις οριακές γραμμές.

Γραμμική συνάρτηση F=f(x) είναι η ευθύγραμμη εξίσωση c1x1 + c2x2 = const. Ας σχεδιάσουμε τη συνάρτηση στόχο για f(x)=0. για να κατασκευάσουμε μια ευθεία γραμμή 3x1 + 4x2 = 0, κατασκευάζουμε το διάνυσμα ακτίνας N = (3; 4) και σχεδιάζουμε μια ευθεία κάθετη σε αυτήν μέσω του σημείου 0. Μετακινούμε την κατασκευασμένη ευθεία F=0 παράλληλα προς τον εαυτό της προς την κατεύθυνση του διανύσματος N.

Από το σχήμα 1 προκύπτει ότι αυτή η ευθεία γίνεται η γραμμή αναφοράς σε σχέση με το κατασκευασμένο πολύγωνο των λύσεων στο σημείο Β, όπου η συνάρτηση F παίρνει τη μέγιστη τιμή της. Το σημείο Β βρίσκεται στην τομή των ευθειών 0,7x1 + 2x2 ≤ 13,1 και 2,3x1 + 2x2 = 23/ Για να προσδιορίσουμε τις συντεταγμένες του, λύνουμε το σύστημα των εξισώσεων:

Βέλτιστο σχέδιο εργασιών: x1 = 6,187; х2 = 4,38, αντικαθιστώντας τις τιμές των χ1 και χ2 στην αντικειμενική συνάρτηση, λαμβάνουμε Fmax= 3*6,187+4*4,38=36,08.

Έτσι, για να έχετε το μέγιστο κέρδος των 36,06 $, πρέπει να προγραμματίσετε την παραγωγή 6 μονάδων. προϊόντα P1 και 4 μονάδες. προϊόντα P2.

Κανονική μορφή του προβλήματος LP. Ας γράψουμε το πρόβλημα κατανομής πόρων σε κανονική μορφή. Προσθέτοντας μη αρνητικές μεταβλητές x3 ≥ 0, x4 ≥ 0, x5 ≥ 0 στο αρχικό σύστημα περιορισμών, έχουμε:

Τραπέζι Simplex LP. Στην περίπτωση των βασικών μεταβλητών (x3, x4, x5), ο αρχικός πίνακας simplex θα μοιάζει με:

Τραπέζι 1.

Αντιστοιχεί ήδη στο βασικό σχέδιο x(0) = T (στήλη ελεύθερων μελών).

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

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

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

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

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

Λύστε το πρόβλημα χρησιμοποιώντας τη μέθοδο 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).

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

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

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

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

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

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

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

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

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

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

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

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

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