Δυναμικός προγραμματισμός. Το πρόβλημα της βέλτιστης κατανομής πόρων. Κατανομή πόρων με χρήση μεθόδου δυναμικού προγραμματισμού
Πλάνο μαθήματος
Ακαδημαϊκή πειθαρχίαΜΑΘΗΜΑΤΙΚΕΣ ΜΕΘΟΔΟΙ ΚΑΙ ΜΟΝΤΕΛΑ ΣΤΗΝ ΟΙΚΟΝΟΜΙΚΗ
Θέμα μαθήματος Επίλυση διαφόρων πρακτικών προβλημάτων ΔΠ με χρήση μαθηματικών μεθόδων.
Στόχοι μαθήματος
Να αναπτύξουν δεξιότητες επίλυσης προβλημάτων δυναμικού προγραμματισμού.
Ανάπτυξη της ποιότητας του μυαλού, της προσοχής και των ακαδημαϊκών εργασιακών δεξιοτήτων των μαθητών.
Ενστάλαξη πειθαρχίας και αποφασιστικότητας στους μαθητές.
Εξοπλισμός μαθήματοςΣημειώσεις διάλεξης, V.P. Agaltsov «Μαθηματικές μέθοδοι στον προγραμματισμό».
Κατά τη διάρκεια των μαθημάτων:
Ώρα διοργάνωσης:
έλεγχος απουσιών, συμπλήρωση του ημερολογίου.
Επικαιροποίηση γνώσεων αναφοράς: απαντήσεις σε ερωτήσεις ασφαλείας
Ποιες εργασίες ονομάζονται πολλαπλά βήματα;
Ποια μαθηματική συσκευή χρησιμοποιείται για την επίλυση προβλημάτων πολλαπλών βημάτων;
Τι είναι ο βέλτιστος έλεγχος u*;
Ποιος είναι ο αλγόριθμος για τη μέθοδο διαδοχικής προσέγγισης δύο κύκλων;
Δώστε παραδείγματα προβλημάτων βέλτιστης κατανομής πόρων.
Εκμάθηση νέου υλικού:
Κλασικά προβλήματα δυναμικού προγραμματισμού
Πρόβλημα μεγαλύτερης κοινής υποακολουθίας: Λαμβάνοντας υπόψη δύο ακολουθίες, πρέπει να βρείτε τη μεγαλύτερη κοινή υποακολουθία.
Πρόβλημα εύρεσης της μεγαλύτερης αυξανόμενης υποακολουθίας: δεδομένου μιας ακολουθίας, πρέπει να βρείτε τη μεγαλύτερη αύξουσα υποακολουθία.
Πρόβλημα εκδοτικής απόστασης (απόσταση Levenshtein): με δεδομένες δύο συμβολοσειρές, πρέπει να βρείτε τον ελάχιστο αριθμό διαγραφών, αντικαταστάσεων και προσθηκών χαρακτήρων που μετατρέπουν μια συμβολοσειρά σε άλλη.
Το πρόβλημα του υπολογισμού των αριθμών Fibonacci
Το πρόβλημα της σειράς πολλαπλασιασμού πινάκων: δεδομένων πινάκων, ..., απαιτείται η ελαχιστοποίηση του αριθμού των βαθμωτών πράξεων για τον πολλαπλασιασμό τους.
Πρόβλημα επιλογής τροχιάς
Πρόβλημα Διαδοχικής Λήψης Απόφασης
Πρόβλημα Αξιοποίησης Εργασίας
Πρόβλημα διαχείρισης αποθεμάτων
Το πρόβλημα του σακιδίου: από ένα απεριόριστο σύνολο αντικειμένων με τις ιδιότητες «κόστος» και «βάρος», απαιτείται να επιλεγεί ένας συγκεκριμένος αριθμός αντικειμένων με τέτοιο τρόπο ώστε να επιτευχθεί το μέγιστο συνολικό κόστος με περιορισμένο συνολικό βάρος.
Αλγόριθμος Floyd-Warshall: βρείτε τις μικρότερες αποστάσεις μεταξύ όλων των κορυφών ενός σταθμισμένου κατευθυνόμενου γραφήματος.
Αλγόριθμος Bellman-Ford: βρείτε τη συντομότερη διαδρομή σε ένα σταθμισμένο γράφημα μεταξύ δύο δεδομένων κορυφών.
Μέγιστο ανεξάρτητο σύνολο κορυφών σε ένα δέντρο: δεδομένου ενός δέντρου, βρείτε το μέγιστο σύνολο κορυφών έτσι ώστε να μην συνδέονται δύο από αυτές με μια άκρη.
Παράδειγμα: Βέλτιστη κατανομή πόρων
Κεφάλαιο 40 εκατομμύρια ρούβλια. ο επενδυτής πρέπει να επενδύσει σε τέσσερα επενδυτικά σχέδια προκειμένου να αποκτήσει το μέγιστο εισόδημα. Η κερδοφορία των έργων δίνεται στον πίνακα (οι επενδύσεις είναι πολλαπλάσιες των 8 εκατομμυρίων ρούβλια)
u
Κέρδος από την υλοποίηση
f4(u)
f3(u)
f2(u)
f1(u)
55
39
120
115
10 0
120
135
134
14 0
145
158
147
Λύση:
Αυτό είναι ένα πρόβλημα δυναμικού προγραμματισμού. Η λύση αποτελείται από δύο στάδια. Στο πρώτο στάδιο (από τέλος σε αρχή) αναζητούμε μια υπό όρους βέλτιστη λύση, στο δεύτερο (από την αρχή μέχρι το τέλος) αναζητούμε τη βέλτιστη λύση του προβλήματος.
Στάδιο 1.
Κατανέμουμε το κεφάλαιο μεταξύ τεσσάρων έργων και υπολογίζουμε το κέρδος που έχουμε μεγάλο (Εγώ ), Εγώ = 8,16,24,32,40.
1 βήμα: Επενδύονται κεφάλαια στο τέταρτο έργο.
L(8)= 55
L(16)=58
L(24)=90
L(32)=100
L(40)=140
Βήμα 2: Τα κεφάλαια επενδύονται στο τέταρτο και τρίτο έργο.
u
Κέρδος από την υλοποίηση
1 βήμα
f3(u)
55
39
10 0
120
14 0
145
Βήμα 3: Τα κεφάλαια επενδύονται στο τέταρτο, τρίτο (βήμα 2) και δεύτερο έργο.
u
Κέρδος από την υλοποίηση
Βήμα 2
f 2(u)
94
108
120
135
135
175
158
175
134
214
147
Στάδιο 2:
Στο τέταρτο βήμα, επιλέγουμε το μέγιστο από τις λαμβανόμενες τιμές κέρδους L (40) = 214.
Και επιστρέφοντας με αντίστροφη σειρά από πίνακα σε πίνακα (από 4 βήματα έως 1) επιλέγουμε τέτοιες τιμές εισοδήματος στις οποίες προκύπτει η τιμή 214.
Μέγιστο εισόδημα 214 εκατομμύρια ρούβλια. από τα επενδυμένα κεφάλαια μπορούν να ληφθούν με την ακόλουθη διανομή κεφαλαίων:
1 έργο - 0 εκατομμύρια ρούβλια.
2 έργο - 24 εκατομμύρια ρούβλια.
3ο έργο - 8 εκατομμύρια ρούβλια.
4 έργο - 8 εκατομμύρια ρούβλια.
Ενοποίηση νέου υλικού:
5. Συνοψίζοντας το μάθημα: συμπεράσματα, αξιολογήσεις, εργασίες για το σπίτι:
(2) ρήτρα 5.1
Ср12: διαμόρφωση και αφομοίωση του περιεχομένου του θεωρητικού υλικού
Υπογραφή δασκάλου
- 1,03 MBΑς δώσουμε μια μαθηματική διατύπωση της αρχής της βελτιστότητας. Για απλότητα, θα υποθέσουμε ότι δίνονται οι αρχικές x 0 και οι τελικές x T καταστάσεις του συστήματος. Ας συμβολίσουμε με z 1 (x 0 , u 1) την τιμή της συνάρτησης στόχου στο πρώτο στάδιο με την αρχική κατάσταση του συστήματος x 0 και με τον έλεγχο u 1 , με z 2 (x 1 , u 2) την αντίστοιχη τιμή της συνάρτησης στόχου μόνο στο δεύτερο στάδιο, .., μέσω
z i (x i -1 ,u i) - στο i-ο στάδιο, ..., μέσω z N (x N -1 , u N) - στο N-ο στάδιο. Είναι προφανές ότι
Είναι απαραίτητο να βρεθεί ο βέλτιστος έλεγχος u*= (; ;...;), έτσι ώστε να αποδίδει το άκρο της αντικειμενικής συνάρτησης (1) υπό περιορισμούς.
Για να λύσουμε αυτό το πρόβλημα, το βυθίζουμε σε μια οικογένεια παρόμοιων. Ας εισάγουμε κάποια σημειογραφία. Έστω, αντίστοιχα, οι περιοχές
ορισμοί για παρόμοια προβλήματα στο τελευταίο στάδιο, τα δύο τελευταία, κ.λπ.
– πεδίο ορισμού του αρχικού προβλήματος. Ας συμβολίσουμε με F 1 (x N -1), F 2 (x N -2), ..., F k (x N -k), ..., F N (x 0), αντίστοιχα, τη βέλτιστη υπό όρους Οι τιμές της συνάρτησης στόχου στο τελευταίο στάδιο, δύο τελευταίες, κ.λπ., στο k τελευταίο, κ.λπ., σε όλα τα Ν στάδια.
Ας ξεκινήσουμε από το τελευταίο στάδιο. Έστω x N-1 οι πιθανές καταστάσεις του συστήματος στην αρχή του Νου σταδίου. Βρίσκουμε:
F 1 (x N -1) = z N (x N -1, u N). (2)
Για τα δύο τελευταία στάδια παίρνουμε
F2 (x N-2) = (Z N-1 (x N-2, u N-1) + F1 (x N-1)). (3)
Επίσης:
F3 (x N-3) = (Z N-2 (x N-3, u N-2) + F2 (x N-2)). (4)
………………………………………………….
F k (x N-k) = (z N-k +1 (x N-k, u N-k +1) + F k-1 (x N-k +1)). (5)
…………………………………………………..
F N (x 0) = (z 1 (x 0, u 1) + F N -1 (x 1)). (6)
Η έκφραση (6) είναι μια μαθηματική αναπαράσταση της αρχής της βελτιστότητας. Η έκφραση (5) είναι η γενική μορφή γραφής της υπό όρους βέλτιστης τιμής της συνάρτησης στόχου για τα k υπόλοιπα στάδια. Οι εκφράσεις (2) – (6) ονομάζονται συναρτησιακές εξισώσεις Bellman. Η επαναλαμβανόμενη (επαναλαμβανόμενη) φύση τους είναι ξεκάθαρα ορατή, δηλαδή, για να βρείτε τον βέλτιστο έλεγχο σε N βήματα, πρέπει να γνωρίζετε τον υπό όρους βέλτιστο έλεγχο στα προηγούμενα N – 1 στάδια κ.λπ. Επομένως, οι συναρτησιακές εξισώσεις ονομάζονται συχνά επαναλαμβανόμενες (επαναλαμβανόμενες) Σχέσεις Bellman.
- Χαρακτηριστικά προβλημάτων δυναμικού προγραμματισμού
Με βάση τα παραπάνω, μπορούμε να επισημάνουμε τα ακόλουθα χαρακτηριστικά των προβλημάτων δυναμικού προγραμματισμού.
- Θεωρούμε ένα σύστημα του οποίου η κατάσταση σε κάθε βήμα προσδιορίζεται από το διάνυσμα x t. Μια περαιτέρω αλλαγή στην κατάστασή του εξαρτάται μόνο από τη δεδομένη κατάσταση x t και δεν εξαρτάται από το πώς το σύστημα έφτασε σε αυτήν την κατάσταση. Τέτοιες διαδικασίες ονομάζονται διεργασίες χωρίς αποτέλεσμα.
- Σε κάθε βήμα επιλέγεται μία λύση u t, υπό την επίδραση της οποίας το σύστημα μετακινείται από την προηγούμενη κατάσταση x t -1 στη νέα κατάσταση x t . Αυτή η νέα κατάσταση είναι συνάρτηση της κατάστασης στην αρχή του διαστήματος x t -1 και της απόφασης u t που υιοθετήθηκε στην αρχή του διαστήματος, δηλαδή x t = x t (x t -1,u t).
- Η ενέργεια σε κάθε βήμα συνδέεται με ένα ορισμένο κέρδος (έσοδο, κέρδος) ή ζημία (κόστος), που εξαρτώνται από την κατάσταση στην αρχή του βήματος (στάδιο) και την απόφαση που λαμβάνεται.
- Μπορούν να επιβληθούν περιορισμοί στα διανύσματα κατάστασης και ελέγχου, ο συνδυασμός των οποίων αποτελεί την περιοχή των εφικτών λύσεων.
- Απαιτείται να βρεθεί ένας τέτοιος αποδεκτός έλεγχος u t για κάθε βήμα t προκειμένου να ληφθεί η ακραία τιμή της συνάρτησης στόχου για όλα τα βήματα T.
Οποιαδήποτε έγκυρη ακολουθία ενεργειών για κάθε βήμα που μεταφέρει το σύστημα από την αρχική κατάσταση στην τελική κατάσταση ονομάζεται στρατηγική ελέγχου. Μια στρατηγική ελέγχου που οδηγεί σε μια ακραία τιμή της αντικειμενικής συνάρτησης ονομάζεται βέλτιστη.
Η γεωμετρική ερμηνεία του προβλήματος δυναμικού προγραμματισμού έχει ως εξής. Έστω n η διάσταση του χώρου κατάστασης. Σε κάθε χρονική στιγμή, οι συντεταγμένες του συστήματος έχουν μια πολύ συγκεκριμένη τιμή. Με μια αλλαγή στο χρόνο t, οι τιμές συντεταγμένων του διανύσματος κατάστασης μπορούν να αλλάξουν. Ας ονομάσουμε τη μετάβαση ενός συστήματος από τη μια κατάσταση στην άλλη τροχιά της κίνησής του στον χώρο καταστάσεων. Μια τέτοια μετάβαση πραγματοποιείται επηρεάζοντας τις συντεταγμένες κατάστασης. Ο χώρος στον οποίο οι καταστάσεις του συστήματος χρησιμεύουν ως συντεταγμένες ονομάζεται χώρος φάσης. Το πρόβλημα δυναμικού προγραμματισμού μπορεί να ερμηνευτεί ιδιαίτερα καθαρά εάν ο χώρος καταστάσεων είναι δισδιάστατος. Η περιοχή των πιθανών καταστάσεων σε αυτή την περίπτωση θα απεικονίζεται με ένα συγκεκριμένο σχήμα, οι αρχικές και τελικές καταστάσεις του συστήματος - με σημεία x 0 (Εικ. 1). Έλεγχος είναι η επιρροή που μεταφέρει το σύστημα από την αρχική κατάσταση στην τελική κατάσταση. Για πολλά οικονομικά προβλήματα, η αρχική ή η τελική κατάσταση δεν είναι γνωστή, αλλά είναι γνωστή η περιοχή X 0 ή X T στην οποία ανήκουν αυτά τα σημεία.
Εικόνα 1
Στη συνέχεια, τα αποδεκτά σημεία ελέγχου μεταφέρουν από την περιοχή X 0 στο X T . Το πρόβλημα δυναμικού προγραμματισμού μπορεί να διατυπωθεί γεωμετρικά ως εξής: βρείτε μια τροχιά φάσης που ξεκινά από την περιοχή X 0 και τελειώνει στην περιοχή X T για την οποία η συνάρτηση στόχου φτάνει σε μια ακραία τιμή. Εάν η αρχική και η τελική κατάσταση ενός προβλήματος δυναμικού προγραμματισμού είναι γνωστές, τότε μιλάμε για πρόβλημα με σταθερά άκρα. Εάν η αρχική και η τελική περιοχή είναι γνωστές, τότε μιλάμε για πρόβλημα με ελεύθερα άκρα.
- ΠΡΟΒΛΗΜΑ ΔΙΑΝΟΜΗΣ ΠΟΡΩΝ
2.1 Γενική δήλωση του προβλήματος
Ας εξετάσουμε την εφαρμογή της μεθόδου δυναμικού προγραμματισμού χρησιμοποιώντας το παράδειγμα της κατανομής κεφαλαίων μεταξύ έξι αντικειμένων ανακατασκευής μιας επιχείρησης ύδρευσης πόλης:
1. Κεντρικός σταθμός άντλησης και διήθησης.
2. Ανατολικός σταθμός άντλησης και διήθησης.
3. Αντλιοστάσιο νερού.
4. Κεντρικός σταθμός αερισμού.
5. Σταθμός ανατολικού αερισμού.
6. Εξοχικός σταθμός αερισμού.
Το συνολικό ποσό των κεφαλαίων που παρέχονται για την ανάπτυξη δεν υπερβαίνει τα 195 χιλιάδες εθνικού νομίσματος. Με βάση τεχνικούς και οικονομικούς υπολογισμούς, διαπιστώθηκε ότι ως αποτέλεσμα της ανακατασκευής, ανάλογα με το ύψος των δαπανών, οι εγκαταστάσεις θα έχουν την παραγωγικότητα που φαίνεται στον Πίνακα 1.1. Είναι απαραίτητο να καθοριστεί η βέλτιστη κατανομή των κεφαλαίων μεταξύ των αντικειμένων ανακατασκευής, η οποία θα εξασφαλίσει τη μέγιστη αύξηση της παραγωγικότητας αυτών των αντικειμένων. Έτσι, αυτό το πρόβλημα χρησιμοποιεί ένα κριτήριο βελτιστοποίησης - τη συνολική παραγωγικότητα των επιχειρήσεων των αντικειμένων ανακατασκευής.
Πίνακας 1.1 Εισαγωγή δεδομένων για την παραγωγικότητα αντικειμένων ανακατασκευής
Αριθμός σειράς αντικειμένου |
Όγκος πόρων που διατίθενται για την ανάπτυξη εγκαταστάσεων (χιλιάδες UAH) |
|||||||||||||
Παραγωγικότητα αντικειμένων ως αποτέλεσμα ανάπτυξης (χιλιάδες m3) |
||||||||||||||
- Μπλοκ διάγραμμα του προγράμματος
Εικόνα 1. Κύριο πρόγραμμα
QtObj – αριθμός αντικειμένων
QtRes – αριθμός πόρων
effMatrix - πίνακας απόδοσης αντικειμένου,
distVector – διάνυσμα κατανεμημένων πόρων
Βήμα 1: Βελτιστοποίηση υπό όρους
Βήμα 2. Βελτιστοποίηση χωρίς όρους
I = QtObj-1.0 σχηματίζουν το διανυσματικό αποτέλεσμα
Εικόνα 2. Εισαγωγή δεδομένων
distVector – διάνυσμα απόστασης, effMatrix = πίνακας απόδοσης
εάν εισαχθούν όλα τα στοιχεία του πίνακα
εάν το διάνυσμα απόδοσης δεν είναι
αρνητικός
Εικόνα 3. Βελτιστοποίηση υπό όρους,
σχηματίζουμε έναν πίνακα εξόδου (το μέγιστο της συνάρτησης στόχου)
outMatrix – μέγιστη μήτρα στόχου
QtObj – αριθμός αντικειμένων
QtRes – αριθμός πόρων
Matrix – matrix απόδοσης
distVect – διάνυσμα απόστασης (διάνυσμα πόρων)
όχι ναι Εάν η πρώτη επιχείρηση
Βρίσκοντας το μέγιστο
ναι maxItem = θερμοκρασία; outMatrix[i][j] = maxItem
- Δομή αλγορίθμου προγράμματος
- Εισαγωγή δεδομένων – κλάση DataDlg.
Μέλη μεταβλητής τάξης.
//διάνυσμα για την αποθήκευση του όγκου των πόρων
std:: vector
//μήτρας απόδοσης αντικειμένου
int** effMatrix;
//συνάρτηση για τη μετατροπή μιας συμβολοσειράς σε αριθμό
int StringToInt(CString);
//λειτουργία για τον έλεγχο της ορθότητας των δεδομένων που έχουν εισαχθεί
BOOL FillMatrix();
//Λειτουργία καθαρισμού πόρων μετά το κλείσιμο του παραθύρου
εικονικό BOOL DestroyWindow();
//συνάρτηση αρχικοποίησης διαλόγου
εικονικό BOOL OnInitDialog();
- Υπολογισμός αποτελεσμάτων - η κύρια τάξη του προγράμματος courseWorkDlg
Μέλη μεταβλητής τάξης
intValue; //τιμή απόδοσης
int MaxIndex;// μέγιστος δείκτης στο διάνυσμα πόρων
int Facility;//enterprise
int Recource;//αφιερωμένος πόρος
Στοιχείο ** outMatrix; //μήτρα μέγιστου στόχου
std:: vector
void BuildOutMatrix(int**,std::vector
afx_msg void OnBnClickedButton1();
εικονικό BOOL DestroyWindow();//εκκαθάριση πόρων προγράμματος
- Αναφορά κλάσης αποτελεσμάτων εξόδου
Ο σκοπός αυτής της κλάσης είναι να εξάγει το διάνυσμα αποτελέσματος σε μορφή πίνακα.
2.4 Αποτελέσματα του προγράμματος
Αρχική εισαγωγή δεδομένων
- Εισαγωγή δεδομένων για την παραγωγικότητα αντικειμένων ανακατασκευής
- Εάν δεν είναι συμπληρωμένα όλα τα πεδία
- Εάν εισαχθεί λανθασμένος χαρακτήρας
Σωστή εισαγωγή δεδομένων
Εμφάνιση αποτελέσματος
- Εισαγωγή δεδομένων
Αποτέλεσμα του προγράμματος
Αρχική εισαγωγή δεδομένων
Εισαγωγή στην παραγωγικότητα του αντικειμένου
Εφαρμογή.
Καταχώριση προγράμματος
int DataDlg::StringToInt(CString str)
const wchar_t* s = T2CW(str);
int val = _wtoi(s);
// είναι συμπληρωμένα όλα τα πεδία;
BOOL DataDlg::FillMatrix()
bool flag = αληθινό;
για (int i = 0; i< Cells.GetSize(); i ++){
για (int j = 0 ; j< Cells.GetAt(i)->Edits.GetSize(); j++)(
CEdit * temp = Cells.GetAt(i)->Edits.GetAt(j) ;
if (temp->m_hWnd != NULL)(
temp->GetWindowText(str);
if (str.IsEmpty())(
MessageBox(L"Πρέπει να συμπληρωθούν όλα τα πεδία", L"Σφάλμα", MB_ICONERROR | MB_OK);
Περιγραφή της δουλειάς
Σκοπός αυτής της εργασίας είναι να εφαρμόσει σε υπολογιστή μια λύση στο πρόβλημα της βέλτιστης κατανομής των κεφαλαίων για την επέκταση της παραγωγής.
Στόχοι του μαθήματος:
Εξετάστε τις θεωρητικές πτυχές της επίλυσης προβλημάτων δυναμικού προγραμματισμού. την επαναλαμβανόμενη φύση προβλημάτων αυτού του τύπου· Οι αρχές της βελτιστοποίησης του Bellman.
Ανάπτυξη αλγορίθμου. Μπλοκ διαγράμματα. Δομή αλγορίθμου.
Υπολογιστική εφαρμογή του αναπτυγμένου αλγορίθμου στην επιλεγμένη γλώσσα προγραμματισμού.
Περιεχόμενο
ΕΙΣΑΓΩΓΗ……………………………………………………………2
Δυναμικός προγραμματισμός
Βασικές έννοιες…………………4
Αρχές δυναμικού προγραμματισμού. Συναρτησιακές εξισώσεις Bellman…………………….5
Χαρακτηριστικά προβλημάτων δυναμικού προγραμματισμού……………….10
Πρόβλημα κατανομής πόρων…………………………12
Γενική δήλωση του προβλήματος…………………………….13
Μπλοκ διάγραμμα του προγράμματος
Δομή αλγορίθμου προγράμματος
Αποτέλεσμα του προγράμματος
συμπέρασμα
Βιβλιογραφία
Αυτοί οι τύποι εργασιών βασίζονται σε Λειτουργίες Bellmanκαι η λύση χρησιμοποιεί τη μέθοδο σάρωσης προς τα πίσω (βλ. Τυπικές εργασίες). Μπορείτε επίσης να χρησιμοποιήσετε την υπηρεσία Διαδικασία απευθείας μετάβασης.
Οδηγίες. Επιλέξτε τον αριθμό των επιχειρήσεων και τον αριθμό των γραμμών (τον αριθμό των αποτελεσματικών επενδυτικών επιλογών), κάντε κλικ στο Επόμενο (βλ. Συμπληρωματικό παράδειγμα). Εάν τα έσοδα και τα υπόλοιπα των επιχειρήσεων δίνονται με τη μορφή των συναρτήσεων f(x) και g(x), το πρόβλημα επιλύθηκε χρησιμοποιώντας αυτήν την αριθμομηχανή.
Παράδειγμα Νο. 1. Προσδιορίστε το βέλτιστο σχέδιο για την επέκταση της παραγωγής τριών επιχειρήσεων, εάν το ετήσιο κέρδος τους είναι γνωστό ελλείψει επενδύσεων και με επένδυση 1, 2, 3 ή 4 εκατομμυρίων.
| στ1 | στ2 | f3 | x i |
| 40 | 30 | 35 | 0 |
| 90 | 110 | 95 | 1 |
| 395 | 385 | 270 | 2 |
| 440 | 470 | 630 | 3 |
| 620 | 740 | 700 | 4 |
Στάδιο Ι. Βελτιστοποίηση υπό όρους.
1ο βήμα. k = 3.
| ε 2 | u 3 | e 3 = e 2 - u 3 | f 3 (u 3) | F* 3 (e 3) | u 3 (ε 3) |
| 1 | 0 | 1 | 35 | ||
| 1 | 0 | 95 | 95 | 1 | |
| 2 | 0 | 2 | 35 | ||
| 1 | 1 | 95 | |||
| 2 | 0 | 270 | 270 | 2 | |
| 3 | 0 | 3 | 35 | ||
| 1 | 2 | 95 | |||
| 2 | 1 | 270 | |||
| 3 | 0 | 630 | 630 | 3 | |
| 4 | 0 | 4 | 35 | ||
| 1 | 3 | 95 | |||
| 2 | 2 | 270 | |||
| 3 | 1 | 630 | |||
| 4 | 0 | 700 | 700 | 4 |
2ο βήμα. k = 2.
| ε 1 | u 2 | e 2 = e 1 - u 2 | f 2 (u 2) | F* 2 (e 1) | F 1 (u 2 ,e 1) | F* 2 (e 2) | u 2 (ε 2) |
| 1 | 0 | 1 | 30 | 95 | 125 | 125 | 0 |
| 1 | 0 | 110 | 0 | 110 | |||
| 2 | 0 | 2 | 30 | 270 | 300 | ||
| 1 | 1 | 110 | 95 | 205 | |||
| 2 | 0 | 385 | 0 | 385 | 385 | 2 | |
| 3 | 0 | 3 | 30 | 630 | 660 | 660 | 0 |
| 1 | 2 | 110 | 270 | 380 | |||
| 2 | 1 | 385 | 95 | 480 | |||
| 3 | 0 | 470 | 0 | 470 | |||
| 4 | 0 | 4 | 30 | 700 | 730 | ||
| 1 | 3 | 110 | 630 | 740 | 740 | 1 | |
| 2 | 2 | 385 | 270 | 655 | |||
| 3 | 1 | 470 | 95 | 565 | |||
| 4 | 0 | 740 | 0 | 740 |
3ο βήμα. k = 1.
| ε 0 | u 1 | e 1 = e 0 - u 1 | f 1 (u 1) | F* 1 (e 0) | F 0 (u 1 ,e 0) | F* 1 (e 1) | u 1 (ε 1) |
| 1 | 0 | 1 | 40 | 125 | 165 | 165 | 0 |
| 1 | 0 | 90 | 0 | 90 | |||
| 2 | 0 | 2 | 40 | 385 | 425 | 425 | 0 |
| 1 | 1 | 90 | 125 | 215 | |||
| 2 | 0 | 395 | 0 | 395 | |||
| 3 | 0 | 3 | 40 | 660 | 700 | 700 | 0 |
| 1 | 2 | 90 | 385 | 475 | |||
| 2 | 1 | 395 | 125 | 520 | |||
| 3 | 0 | 440 | 0 | 440 | |||
| 4 | 0 | 4 | 40 | 740 | 780 | 780 | 0 |
| 1 | 3 | 90 | 660 | 750 | |||
| 2 | 2 | 395 | 385 | 780 | |||
| 3 | 1 | 440 | 125 | 565 | |||
| 4 | 0 | 620 | 0 | 620 |
Σημείωση: Οι στήλες 1 (επενδυμένα κεφάλαια), 2 (έργο) και 3 (υπόλοιπο κεφαλαίων) είναι ίδιες και για τους τρεις πίνακες, επομένως θα μπορούσαν να γίνουν κοινοί. Η στήλη 4 συμπληρώνεται με βάση τα αρχικά δεδομένα για τις συναρτήσεις εισοδήματος, οι τιμές στη στήλη 5 λαμβάνονται από τη στήλη 7 του προηγούμενου πίνακα, η στήλη 6 συμπληρώνεται με το άθροισμα των τιμών των στηλών 4 και 5 (οι στήλες 5 και 6 λείπουν από τον πίνακα του 3ου βήματος).
Η στήλη 7 καταγράφει τη μέγιστη τιμή της προηγούμενης στήλης για μια σταθερή αρχική κατάσταση και η στήλη 8 καταγράφει το στοιχείο ελέγχου από τη στήλη 2, το οποίο φτάνει το μέγιστο 7.
Στάδιο II. Βελτιστοποίηση χωρίς όρους.
Από τον πίνακα του 3ου βήματος έχουμε F* 1 (e 0 = 4 εκατομμύρια ρούβλια) = 780 χιλιάδες ρούβλια, δηλαδή το μέγιστο κέρδος από την επένδυση e 0 = 4 εκατομμύρια ρούβλια. ίσο με 780 χιλιάδες ρούβλια.
Από τον ίδιο πίνακα διαπιστώνουμε ότι η πρώτη επιχείρηση πρέπει να κατανεμηθεί u* 1 (e 0 = 4 εκατομμύρια ρούβλια) = 0 εκατομμύρια ρούβλια.
Σε αυτή την περίπτωση, το υπόλοιπο των κεφαλαίων θα είναι: e 1 = e 0 - u 1, e 1 = 4 - 0 = 4 εκατομμύρια ρούβλια.
Από τον πίνακα του 2ου βήματος έχουμε F* 2 (e 1 = 4 εκατομμύρια ρούβλια) = 740 χιλιάδες ρούβλια, δηλ. μέγιστο κέρδος σε e 1 = 4 εκατομμύρια ρούβλια. ίσο με 740 χιλιάδες ρούβλια.
Από τον ίδιο πίνακα διαπιστώνουμε ότι η δεύτερη επιχείρηση πρέπει να κατανεμηθεί u* 2 (e 1 = 4 εκατομμύρια ρούβλια) = 1 εκατομμύριο ρούβλια.
Σε αυτή την περίπτωση, το υπόλοιπο των κεφαλαίων θα είναι: e 2 = e 1 - u 2, e 2 = 4 - 1 = 3 εκατομμύρια ρούβλια.
Η τελευταία επιχείρηση λαμβάνει 3 εκατομμύρια ρούβλια. Έτσι, μια επένδυση 4 εκατομμυρίων ρούβλια. πρέπει να διανεμηθεί ως εξής: στην πρώτη επιχείρηση δεν πρέπει να διατεθεί τίποτα, στη δεύτερη επιχείρηση θα πρέπει να διατεθούν 1 εκατομμύριο ρούβλια, στην τρίτη επιχείρηση θα πρέπει να διατεθούν 3 εκατομμύρια ρούβλια, γεγονός που θα εξασφαλίσει μέγιστο κέρδος 780 χιλιάδων ρούβλια.
Παράδειγμα Νο. 2. Υπάρχουν 4 επιχειρήσεις, μεταξύ των οποίων είναι απαραίτητο να διανεμηθούν 100 χιλιάδες συμβατικές μονάδες. μονάδες κεφάλαια. Οι αξίες της αύξησης της παραγωγής στην επιχείρηση, ανάλογα με τα διατεθέντα κεφάλαια X, παρουσιάζονται στον πίνακα. Καταρτίστε ένα βέλτιστο σχέδιο για την κατανομή κεφαλαίων για τη μεγιστοποίηση της συνολικής αύξησης της παραγωγής.
Η μέθοδος δυναμικού προγραμματισμού σας επιτρέπει να επιλύσετε με επιτυχία πολλά οικονομικά προβλήματα (βλ., για παράδειγμα,). Ας εξετάσουμε ένα από τα πιο απλά τέτοια προβλήματα. Έχουμε στη διάθεσή μας κάποιο αποθεματικό κεφαλαίων (πόρων) Κ, το οποίο πρέπει να διανεμηθεί μεταξύ των επιχειρήσεων. Κάθε μία από τις επιχειρήσεις, όταν επενδύονται κάποια κεφάλαια σε αυτήν, παράγει εισόδημα που εξαρτάται, δηλαδή, αντιπροσωπεύει κάποιο είδος λειτουργίας Δίνονται όλες οι λειτουργίες (φυσικά, αυτές οι λειτουργίες δεν μειώνονται).
Το ερώτημα είναι πώς θα πρέπει να κατανεμηθούν τα κεφάλαια Κ μεταξύ των επιχειρήσεων ώστε συνολικά να παράγουν μέγιστο εισόδημα;
Αυτό το πρόβλημα επιλύεται εύκολα χρησιμοποιώντας τη μέθοδο δυναμικού προγραμματισμού. Αν και στη διατύπωσή του δεν περιέχει καμία αναφορά χρόνου, εξακολουθεί να είναι δυνατό να ξεδιπλωθεί νοερά η λειτουργία της διανομής κεφαλαίων με κάποια σειρά, θεωρώντας ότι το πρώτο βήμα είναι η επένδυση κεφαλαίων στην επιχείρηση, το δεύτερο - σε κ.λπ.
Το διαχειριζόμενο σύστημα S σε αυτή την περίπτωση είναι τα κεφάλαια ή οι πόροι που διανέμονται. Η κατάσταση του συστήματος S πριν από κάθε βήμα χαρακτηρίζεται από έναν αριθμό S - το διαθέσιμο απόθεμα κεφαλαίων που δεν έχουν ακόμη επενδυθεί. Σε αυτό το έργο, η «διαχείριση βημάτων» είναι τα κεφάλαια που διατίθενται στις επιχειρήσεις. Απαιτείται να βρεθεί ο βέλτιστος έλεγχος, δηλαδή ένα τέτοιο σύνολο αριθμών για τα οποία το συνολικό εισόδημα είναι μέγιστο:
Ας λύσουμε αυτό το πρόβλημα πρώτα σε γενική μορφή, και στη συνέχεια για συγκεκριμένα αριθμητικά δεδομένα. Ας βρούμε για κάθε βήμα το υπό όρους βέλτιστο κέρδος (από αυτό το βήμα μέχρι το τέλος), αν προσεγγίσαμε αυτό το βήμα με ένα αποθεματικό κεφαλαίων S. Ας υποδηλώσουμε το υπό όρους βέλτιστο κέρδος , και τον αντίστοιχο υπό όρους βέλτιστο έλεγχο - τα κεφάλαια που επενδύθηκαν η επιχείρηση -
Ας ξεκινήσουμε τη βελτιστοποίηση από το τελευταίο βήμα. Ας προσεγγίσουμε αυτό το βήμα με ισοζύγιο κεφαλαίων S. Τι πρέπει να κάνουμε; Προφανώς, επενδύστε ολόκληρο το ποσό S στην επιχείρηση, επομένως, ο υπό όρους βέλτιστος έλεγχος στο βήμα: δώστε στην τελευταία επιχείρηση όλα τα διαθέσιμα κεφάλαια S, δηλ.
και το υπό όρους βέλτιστο κέρδος
Δεδομένου ενός ολόκληρου φάσματος τιμών του S (εντοπίζοντάς τες αρκετά κοντά), θα γνωρίζουμε για κάθε τιμή του S . Το τελευταίο βήμα είναι βελτιστοποιημένο.
Ας περάσουμε στο προτελευταίο βήμα. Ας το προσεγγίσουμε με ένα αποθεματικό κεφαλαίων S. Ας υποδηλώσουμε το υπό όρους βέλτιστο κέρδος στα δύο τελευταία βήματα: (το οποίο είναι ήδη βελτιστοποιημένο). Εάν διαθέσουμε κεφάλαια στην επιχείρηση στο βήμα, τότε θα μείνουν για το τελευταίο βήμα τα κέρδη μας στα δύο τελευταία βήματα θα είναι ίσα με
και πρέπει να βρείτε ένα στο οποίο αυτό το κέρδος είναι το μέγιστο:
Το σύμβολο σημαίνει ότι η μέγιστη τιμή λαμβάνεται σε όλες τις πιθανές τιμές (δεν μπορούμε να βάλουμε περισσότερες από S), από την έκφραση σε σγουρές αγκύλες. Αυτό το μέγιστο είναι το υπό όρους βέλτιστο κέρδος για τα δύο τελευταία βήματα και η τιμή στην οποία επιτυγχάνεται αυτό το μέγιστο είναι ο υπό όρους βέλτιστος έλεγχος στο βήμα.
και ο αντίστοιχος βέλτιστος υπό όρους έλεγχος είναι η τιμή στην οποία επιτυγχάνεται αυτό το μέγιστο.
Συνεχίζοντας με αυτόν τον τρόπο, θα φτάσουμε τελικά στην επιχείρηση Εδώ δεν θα χρειαστεί να αλλάξουμε τις τιμές του S. γνωρίζουμε με βεβαιότητα ότι το απόθεμα των κεφαλαίων πριν από το πρώτο βήμα είναι ίσο με Κ:
Έτσι, βρέθηκε το μέγιστο κέρδος (εισόδημα) από όλες τις επιχειρήσεις. Τώρα το μόνο που μένει είναι να «διαβαστούν οι συστάσεις». Η τιμή στην οποία επιτυγχάνεται το μέγιστο (13,4) είναι ο βέλτιστος έλεγχος στο 1ο βήμα.
Αφού επενδύσουμε αυτά τα κεφάλαια στην πρώτη επιχείρηση, θα μας απομείνουν. «Διαβάζοντας» τη σύσταση για αυτήν την τιμή του S, διαθέτουμε το βέλτιστο ποσό κεφαλαίων στη δεύτερη επιχείρηση: και ούτω καθεξής μέχρι το τέλος.
Τώρα ας λύσουμε ένα αριθμητικό παράδειγμα. Το αρχικό απόθεμα κεφαλαίων (τυποποιημένες μονάδες) και απαιτείται η βέλτιστη κατανομή του σε πέντε επιχειρήσεις Για λόγους απλότητας, υποθέτουμε ότι επενδύονται μόνο ολόκληρα ποσά κεφαλαίων. Οι συναρτήσεις εισοδήματος δίνονται στον Πίνακα 13.1.
Πίνακας 13.1
Σε κάθε στήλη, ξεκινώντας από ένα ορισμένο ποσό επένδυσης, το εισόδημα σταματά να αυξάνεται (στην πραγματικότητα, αυτό αντιστοιχεί στο γεγονός ότι κάθε επιχείρηση είναι σε θέση να «υιοθετήσει» μόνο ένα περιορισμένο ποσό κεφαλαίων).
Ας πραγματοποιήσουμε τη βελτιστοποίηση υπό όρους όπως περιγράφεται παραπάνω, ξεκινώντας από το τελευταίο, 5ο βήμα. Κάθε φορά που πλησιάζουμε στο επόμενο βήμα, έχοντας ένα απόθεμα κεφαλαίων;, προσπαθούμε να διαθέσουμε ένα ή άλλο ποσό κεφαλαίων για αυτό το βήμα, παίρνουμε τα κέρδη σε αυτό το βήμα σύμφωνα με τον πίνακα 13.1, τα προσθέτουμε με τα ήδη βελτιστοποιημένα κέρδη σε όλα τα επόμενα βήματα μέχρι το τέλος (λαμβάνοντας υπόψη ότι έχουμε ήδη λιγότερα κεφάλαια, μόνο για το ποσό των κεφαλαίων που έχουμε διαθέσει) και βρίσκουμε την επένδυση στην οποία αυτό το ποσό φτάνει στο μέγιστο. Αυτή η επένδυση είναι ο υπό όρους βέλτιστος έλεγχος σε αυτό το βήμα και το μέγιστο από μόνο του είναι το υπό όρους βέλτιστο κέρδος.
Ο Πίνακας 13.2 δείχνει τα αποτελέσματα της βελτιστοποίησης υπό όρους για όλα τα βήματα. Ο πίνακας είναι κατασκευασμένος ως εξής: η πρώτη στήλη δίνει τις αξίες του αποθέματος των κεφαλαίων S με τις οποίες προσεγγίζουμε αυτό το βήμα. Ο πίνακας χωρίζεται περαιτέρω σε πέντε ζεύγη στηλών, που αντιστοιχούν στον αριθμό βήματος.
Πίνακας 13.2
Η πρώτη στήλη κάθε ζεύγους δίνει την τιμή του βέλτιστου ελέγχου υπό όρους, η δεύτερη - το υπό όρους βέλτιστο κέρδος. Ο πίνακας είναι γεμάτος από αριστερά προς τα δεξιά, από πάνω προς τα κάτω. Η απόφαση στο πέμπτο - τελευταίο - βήμα είναι αναγκαστική: διατίθενται όλα τα κεφάλαια. Σε όλα τα άλλα βήματα, η λύση πρέπει να βελτιστοποιηθεί. Ως αποτέλεσμα της διαδοχικής βελτιστοποίησης του 5ου, 4ου, 3ου, 2ου και 1ου βήματος, θα λάβουμε μια πλήρη λίστα με όλες τις συστάσεις για βέλτιστο έλεγχο και το άνευ όρων βέλτιστο κέρδος W για ολόκληρη τη λειτουργία - σε αυτήν την περίπτωση είναι ίσο με 5,6 . Στις δύο τελευταίες στήλες του Πίνακα 13.2, συμπληρώνεται μόνο μία σειρά, αφού γνωρίζουμε ακριβώς την κατάσταση του συστήματος πριν από την έναρξη του πρώτου βήματος: . Τα βέλτιστα στοιχεία ελέγχου σε όλα τα βήματα επισημαίνονται με ένα πλαίσιο. Έτσι, λάβαμε το τελικό συμπέρασμα: πρέπει να διαθέσουμε δύο μονάδες από τις δέκα στην πρώτη επιχείρηση, πέντε μονάδες στη δεύτερη, δύο στην τρίτη, καμία στην τέταρτη και μία μονάδα στην πέμπτη. Με την κατανομή αυτή το εισόδημα θα είναι μέγιστο και ίσο με 5,6.
