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

Μια γενίκευση της έννοιας ενός τμήματος για πολλά σημεία είναι ο κυρτός γραμμικός συνδυασμός τους.

Το σημείο Χ ονομάζεται κυρτός γραμμικός συνδυασμόςσημεία, εάν πληρούνται οι προϋποθέσεις

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

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

Θεώρημα 1.1. Ένα κυρτό n-διάστατο πολύεδρο είναι ένας κυρτός γραμμικός συνδυασμός των γωνιακών σημείων του.

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

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

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

Φόρμα εγγραφής Matrix:

Εδώ ΜΕ– πίνακας γραμμών, ΕΝΑ– πίνακας συστήματος, Χ– μήτρα-στήλη μεταβλητών, ΣΕ– μήτρα-στήλη ελεύθερων μελών:

Διανυσματική μορφή εγγραφής:

όπου τα διανύσματα αντιστοιχούν στις στήλες των συντελεστών για τους αγνώστους.

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

Θεώρημα 1.2. Το σύνολο όλων των εφικτών λύσεων στο σύστημα περιορισμών ενός προβλήματος γραμμικού προγραμματισμού είναι κυρτό.

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

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

δηλ. λύση Χικανοποιεί το σύστημα (1.3). Αλλά από τότε Χ>0, δηλ. η λύση ικανοποιεί τη συνθήκη μη αρνητικότητας.

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

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

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

Απόδειξη:Θα υποθέσουμε ότι το πολύεδρο της λύσης είναι δεσμευμένο. Ας υποδηλώσουμε τα γωνιακά του σημεία με , και η βέλτιστη λύση είναι μέσω Χ*. Επειτα F(X*)³ F(X)για όλα τα σημεία Χπολύεδρο των διαλυμάτων. Αν Χ*είναι ένα γωνιακό σημείο, τότε το πρώτο μέρος του θεωρήματος αποδεικνύεται.

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

Επειδή F(X)είναι μια γραμμική συνάρτηση, παίρνουμε

Σε αυτή την αποσύνθεση, επιλέγουμε το μέγιστο μεταξύ των τιμών. Αφήστε το να αντιστοιχεί στο γωνιακό σημείο Xk(1 £ κ£ R); ας το χαρακτηρίσουμε με Μ,εκείνοι. . Ας αντικαταστήσουμε κάθε τιμή στην έκφραση (1.5) με αυτήν τη μέγιστη τιμή Μ.Επειτα

Με παραδοχή Χ* είναι η βέλτιστη λύση, επομένως, αφενός, αλλά, αφετέρου, έχει αποδειχθεί ότι
F(X*)£ Μ,επομένως, , όπου Xk– γωνιακό σημείο. Υπάρχει λοιπόν ένα γωνιακό σημείο Xk, στην οποία η γραμμική συνάρτηση παίρνει τη μέγιστη τιμή της.

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

Αφήνω Χ– ένας κυρτός γραμμικός συνδυασμός αυτών των γωνιακών σημείων, δηλ.

Στην περίπτωση αυτή, δεδομένου ότι η συνάρτηση F(X)– γραμμικό, παίρνουμε

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

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

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

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

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

Απόδειξη:Έστω μια αποδεκτή βασική λύση του συστήματος περιορισμών του LLP (1.4), στο οποίο η πρώτη Τσυνιστώσα είναι οι κύριες μεταβλητές και οι υπόλοιπες p - tσυστατικό – μη κύριες μεταβλητές ίσες με μηδέν στη βασική λύση (εάν αυτό δεν συμβαίνει, τότε οι αντίστοιχες μεταβλητές μπορούν να επαναριθμηθούν). Ας το δείξουμε Χ

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

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

όπου (υποθέτουμε ότι , γιατί αλλιώς το σημείο Χσυμπίπτει με το σημείο Χ 1 ή Χ 2).

Ας γράψουμε τη διανυσματική ισότητα (1.6) σε μορφή συντεταγμένων:

Επειδή Όλες οι μεταβλητές και οι συντελεστές είναι μη αρνητικές, τότε από την τελευταία p-tισότητες προκύπτει ότι , δηλ. στις αποφάσεις Χ 1 , Χ 2 και Χσύστημα εξισώσεων (1.4) τιμών p - tτα στοιχεία είναι ίσα με μηδέν σε αυτή την περίπτωση. Αυτά τα στοιχεία μπορούν να θεωρηθούν ως τιμές μη πρωταρχικών μεταβλητών. Αλλά οι τιμές των μη βασικών μεταβλητών καθορίζουν μοναδικά τις τιμές των κύριων, επομένως,

Όλα λοιπόν Πσυστατικό σε διαλύματα Χ 1 , Χ 2 και Χσυμπίπτουν και επομένως τα σημεία Χ 1 και Χ 2 συγχώνευση, η οποία έρχεται σε αντίθεση με την υπόθεση. Ως εκ τούτου, Χ– γωνιακό σημείο του πολυεδρικού διαλύματος.

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

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

Ετσι, βέλτιστος γραμμική συνάρτησηΤα προβλήματα γραμμικού προγραμματισμού θα πρέπει να αναζητηθούν σε έναν πεπερασμένο αριθμό από τις εφικτές βασικές λύσεις του.

Ας εξετάσουμε το κύριο πρόβλημα γραμμικού προγραμματισμού (LPLP): βρείτε μη αρνητικές τιμές των μεταβλητών x1, x2, ..., xn, ικανοποιώντας m συνθήκες - ισότητες

και μεγιστοποίηση της γραμμικής συνάρτησης αυτών των μεταβλητών

Για λόγους απλότητας, υποθέτουμε ότι όλες οι συνθήκες (1) είναι γραμμικά ανεξάρτητες (r=m), και θα ακολουθήσουμε τη συλλογιστική μας με αυτήν την υπόθεση.

Ας ονομάσουμε αποδεκτή λύση του OLP οποιοδήποτε σύνολο μη αρνητικών τιμών x1, x2, ..., xn που ικανοποιεί τις συνθήκες (1) Ας ονομάσουμε βέλτιστη αυτή από τις αποδεκτές λύσεις που μεγιστοποιεί τη συνάρτηση (2). Πρέπει να βρούμε τη βέλτιστη λύση.

Αυτό το πρόβλημα έχει πάντα λύση; Όχι πάντα.

Το ZLP είναι άλυτο (δεν έχει βέλτιστη λύση):

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

Σχήμα 1 - Ασυνέπεια του συστήματος περιορισμών

Λόγω του απεριόριστου χαρακτήρα της αντικειμενικής συνάρτησης στο σύνολο των λύσεων. Με άλλα λόγια, όταν λύνουμε το LLP στο μέγιστο, η τιμή της αντικειμενικής συνάρτησης τείνει στο άπειρο, και στην περίπτωση του LLP στο ελάχιστο - στο μείον άπειρο, όπως φαίνεται στο Σχήμα 2.

Εικόνα 2 - Απεριόριστος χαρακτήρας της αντικειμενικής συνάρτησης στο σύνολο των λύσεων

Το ZLP είναι επιλύσιμο:

Το σύνολο λύσεων αποτελείται από ένα μόνο σημείο. Είναι επίσης βέλτιστο, όπως φαίνεται στο σχήμα 3.

Εικόνα 3 - Το σύνολο των λύσεων αποτελείται από ένα σημείο

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

Εικόνα 4 - Η μόνη βέλτιστη λύση

Η βέλτιστη λύση του ZLP δεν είναι μοναδική. Το διάνυσμα N είναι κάθετο σε μία από τις πλευρές του συνόλου λύσεων. Σε αυτήν την περίπτωση, οποιοδήποτε σημείο στο τμήμα ΑΒ είναι βέλτιστο, όπως φαίνεται στο Σχήμα 5.

Εικόνα 5 - Η βέλτιστη λύση δεν είναι μοναδική

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

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

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

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

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

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

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

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

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

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

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

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

Έτσι, η εφαρμογή της μεθόδου simplex χωρίζεται σε δύο στάδια:

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

Εύρεση της βέλτιστης λύσης στην περίπτωση συμβατότητας του συστήματος περιορισμών.

Ο αλγόριθμος για τη μετάβαση στην επόμενη εφικτή λύση είναι ο εξής:

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

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

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

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

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

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

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

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

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

Οι παράμετροι των εργασιών περιορίζονται στους ακόλουθους δείκτες ορίων:

• αριθμός αγνώστων – 200.
• αριθμός τύπων περιορισμών σε αγνώστους – 100.
• ο αριθμός των περιοριστικών συνθηκών για αγνώστους είναι 400.

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

• προπαρασκευαστικές εργασίες;
• αποσφαλμάτωση της λύσης.
• ανάλυση λύσης.

Η ακολουθία των απαραίτητων προπαρασκευαστικών εργασιών που εκτελούνται κατά την επίλυση προβλημάτων οικονομικής και μαθηματικής μοντελοποίησης με χρήση MS Excel φαίνεται στο μπλοκ διάγραμμα του Σχήματος 1.6.

Ρύζι. 1.6.

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

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

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

Έτσι, στο πλαίσιο διαλόγου του προγράμματος βελτιστοποίησης "Αναζήτηση λύσης" πρέπει να ορίσουμε τον ακόλουθο αλγόριθμο στόχο:

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

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

Οι τιμές των μεταβλητών πρέπει να βρίσκονται εντός των καθορισμένων ορίων του αριθμού των αρχικών στοιχείων του συστήματος

Αριθμός αρχικών στοιχείων του συστήματος

Αριθμός καθορισμένων τύπων πόρων

Ο εντοπισμός σφαλμάτων της λύσης είναι απαραίτητος όταν το πρόγραμμα εμφανίζει ένα μήνυμα σχετικά με αρνητικά αποτελέσματα (Εικόνα 1.7):

Ρύζι. 1.7.

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

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

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

Η οικονομική ανάλυση έχει τους ακόλουθους στόχους:

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

Πιθανές μέθοδοι ανάλυσης παρουσιάζονται στο διάγραμμα στο Σχήμα 1.8.

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

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

• «τι θα γίνει αν…»
• "Τι χρειάζεται για να..."

Η ανάλυση για την απάντηση στην πρώτη ερώτηση ονομάζεται ανάλυση παραλλαγής; ανάλυση για την απάντηση στο δεύτερο ερώτημα καλείται προσαρμοσμένες λύσεις.

Η ανάλυση παραλλαγών μπορεί να είναι των εξής τύπων:

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

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

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

Εργασίες βελτιστοποίησης: γενικές πληροφορίες

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

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

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

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

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

PPP: σκεύασμα, ταξινόμηση

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

Ένα γενικό ZLP είναι ένα πρόβλημα της μορφής

υπό περιορισμούς

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

Ένα σημαντικό χαρακτηριστικό του ZLP είναι ότι το άκρο της αντικειμενικής συνάρτησης επιτυγχάνεται στο όριο της περιοχής των εφικτών λύσεων.

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

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

ΠΑΠ: παραδείγματα

Πρόβλημα μείγματος

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

Πρόβλημα κατανομής πόρων

Η εταιρεία παράγει nδιάφορα προϊόντα, η παραγωγή των οποίων απαιτεί Μδιάφορους τύπους πόρων. Τα αποθέματα των χρησιμοποιημένων πόρων είναι περιορισμένα και ανέρχονται αντίστοιχα β 1, β 2,…, b m c.u. Επιπλέον, είναι γνωστοί οι τεχνολογικοί συντελεστές ένα ij, που δείχνουν πόσες μονάδες Εγώ- Απαιτείται ο πόρος για την παραγωγή μιας μονάδας προϊόντος ι-ο τύπος (). Το κέρδος που λαμβάνει μια επιχείρηση από την πώληση ενός προϊόντος ι-ου τύπου, ανέρχεται σε γ ινομισματικές μονάδες Είναι απαραίτητο να καταρτιστεί ένα σχέδιο για την παραγωγή προϊόντων, το κέρδος της επιχείρησης κατά την εφαρμογή του οποίου θα είναι το μεγαλύτερο.

Τα προβλήματα που αφορούν μείγματα και κατανομή πόρων συχνά γράφονται σε μορφή πίνακα.

Πόροι	Ανάγκες			Αποθεματικά
	Β 1	…	Bn
Α'1				β 1
…				…
Είμαι				b m
Κέρδος	γ 1	…	c n

Τα προβλήματα μείξης και κατανομής πόρων μπορούν να λυθούν με διάφορους τρόπους:

• γραφική μέθοδος (στην περίπτωση μικρού αριθμού μεταβλητών σε μαθηματικό μοντέλο);
• μέθοδο simplex (αν ο αριθμός των μεταβλητών σε ένα μαθηματικό μοντέλο είναι μεγαλύτερος από δύο).

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

Για λόγους σαφήνειας και ευκολίας αντίληψης, η κατάσταση του προβλήματος μεταφοράς συνήθως γράφεται στον ακόλουθο πίνακα:

Γενικά, η επίλυση ενός προβλήματος μεταφοράς πραγματοποιείται σε διάφορα στάδια:

• Στάδιο Ι: κατασκευή του αρχικού σχεδίου αναφοράς.
• Στάδιο ΙΙ: έλεγχος του σχεδίου αναφοράς για βελτιστοποίηση.
• Στάδιο III: αποσαφήνιση του σχεδίου αναφοράς εάν δεν είναι βέλτιστο.

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

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

- για κατειλημμένα κελιά,
- για μη κατειλημμένα κελιά.

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

συμπέρασμα

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

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

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

1. Bandi B. Βασικές αρχές γραμμικού προγραμματισμού: Μεταφρ. από τα Αγγλικά – Μ.: Ραδιόφωνο και Επικοινωνίες, 1989. – 176 σελ.
2. Kremer N.Sh. Επιχειρησιακή Έρευνα στα Οικονομικά: Proc. εγχειρίδιο για πανεπιστήμια / N.Sh. Kremer, Β.Α. Πούτκο, Ι.Μ. Trishin, Μ.Ν. Friedman; Εκδ. καθ. N.Sh. Κρέμερ. – Μ.: ΕΝΟΤΗΤΑ, 2005. – 407 σελ.

Λύση προσαρμοσμένων μεθόδων βελτιστοποίησης

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

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

Έτσι, το γενικό πρόβλημα γραμμικού προγραμματισμού (GLP) μπορεί να διατυπωθεί ως εξής.

Βρείτε τιμές πραγματικών μεταβλητών για τις οποίες αντικειμενική λειτουργία

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

Ως γνωστόν, μια διατεταγμένη συλλογή αξιών nοι μεταβλητές , , … αντιπροσωπεύονται από ένα σημείο στον n-διάστατο χώρο. Σε αυτό που ακολουθεί θα υποδείξουμε αυτό το σημείο Χ=( , , … ).

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

, ΕΝΑ– πίνακας μεγεθών,

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

Βέλτιστη λύση (βέλτιστο σχέδιο)ένα πρόβλημα γραμμικού προγραμματισμού ονομάζεται λύση Χ=( , , … ), που ανήκει στην αποδεκτή περιοχή και για την οποία η γραμμική συνάρτηση Qπαίρνει τη βέλτιστη (μέγιστη ή ελάχιστη) τιμή.

Θεώρημα. Το σύνολο όλων των εφικτών λύσεων στο σύστημα περιορισμών ενός προβλήματος γραμμικού προγραμματισμού είναι κυρτό.

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

Τελεία Χπου ονομάζεται κυρτός γραμμικός συνδυασμός πόντους εάν πληρούνται οι προϋποθέσεις

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

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

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

Βασική λύση του συστήματος Μγραμμικές εξισώσεις με n μεταβλητές είναι μια λύση στην οποία όλα n-mΟι μη βασικές μεταβλητές είναι μηδέν. Στα προβλήματα γραμμικού προγραμματισμού τέτοιες λύσεις ονομάζονται αποδεκτές βασικές λύσεις (σχέδια αναφοράς).

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

Ένα σημαντικό συμπέρασμα προκύπτει από τα παραπάνω θεωρήματα:

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

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