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

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

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

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

Τυπικά χαρακτηριστικά προβλημάτων πολλαπλών βημάτων.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ας ξεκινήσουμε από το τελευταίο στάδιο. Έστω οι πιθανές καταστάσεις του συστήματος στην αρχή του ου σταδίου. Βρίσκουμε:

Για τα δύο τελευταία στάδια παίρνουμε:

Επίσης:

…………………….

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

Παράδειγμα λύσης προβλήματος

Το έργο

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

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

Διατέθηκαν κονδύλια, εκατομμύρια νομισματικές μονάδες

Εταιρία

№1

№2

№3

№4

Αύξηση της παραγωγής σε επιχειρήσεις, εκατομμύρια νομισματικές μονάδες.

100

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

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

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

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

Διατέθηκαν κονδύλια

100

Βήμα 1

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

Βήμα 2

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

Βήμα 3

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

Βήμα 4

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

0 0 0 0 0 20 10 12 12 16 40 31 31 36 37 60 42 43 48 52 80 62 62 67 73 100 76 76 79 85

Απάντηση

Το βέλτιστο σχέδιο για τη διανομή 100 μονάδων πόρων μεταξύ 4 επιχειρήσεων:

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

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

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

Παραδείγματα σχετικών προβλημάτων

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

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

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

ΑΦΗΡΗΜΕΝΗ

Εισαγωγή

Δυναμικός προγραμματισμός- μια μέθοδος βελτιστοποίησης προσαρμοσμένη σε λειτουργίες στις οποίες η διαδικασία λήψης αποφάσεων μπορεί να χωριστεί σε στάδια (βήματα). Τέτοιες πράξεις ονομάζονται πολλαπλά βήματα.

Η αρχή της ανάπτυξης του δυναμικού προγραμματισμού χρονολογείται από τη δεκαετία του '50 του εικοστού αιώνα. και συνδέεται με το όνομα του Richard Ernest Bellman.

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

ü κατά την ανάπτυξη κανόνων διαχείρισης αποθεμάτων·

ü κατά την κατανομή των επενδυτικών πόρων μεταξύ εναλλακτικών έργων·

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

1. Γενική διατύπωση του προβλήματος δυναμικού προγραμματισμού

δυναμικός προγραμματισμός εξισώσεων bellman

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

Ας συμβολίσουμε με Χ κ απόφαση διαχείρισης στο kth βήμα (k=1, 2, …, n). Μεταβλητές Χ κ ικανοποιούν ορισμένους περιορισμούς και υπό αυτή την έννοια ονομάζονται παραδεκτοί (Χ κ μπορεί να είναι ένας αριθμός, ένα σημείο σε ν-διάστατο χώρο ή ένα ποιοτικό χαρακτηριστικό).

Έστω X=(X 1, Χ 2, …, Χ n ) - έλεγχος που μεταφέρει το σύστημα S από την κατάσταση s 0να δηλώνω s n . Ας υποδηλώσουμε με s κ κατάσταση του συστήματος (που χαρακτηρίζεται από ένα συγκεκριμένο σύνολο παραμέτρων και τις συγκεκριμένες τιμές τους) μετά το kth βήμα ελέγχου. Επιπλέον, η κατάσταση του συστήματος s κ στο τέλος του kth βήματος εξαρτάται μόνο από την προηγούμενη κατάσταση s κ-1 και απόφαση διαχείρισης στο k-ο βήμα Χ κ (δηλαδή δεν εξαρτάται άμεσα από προηγούμενες συνθήκες και αποφάσεις διαχείρισης). Αυτή η απαίτηση ονομάζεται «καμία συνέπεια» και μπορεί να εκφραστεί με τις ακόλουθες εξισώσεις καταστάσεων:

Έτσι, λαμβάνουμε μια ακολουθία καταστάσεων s0, s1, …, sk-1, sk, …, sn-1, sn. Στη συνέχεια, η διαδικασία διαχείρισης n-βημάτων μπορεί να απεικονιστεί σχηματικά ως εξής:

Αφήστε τον δείκτη απόδοσης του kth βήματος να εκφραστεί με κάποια συνάρτηση:

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

Στη συνέχεια, το πρόβλημα βελτιστοποίησης βήμα προς βήμα (πρόβλημα δυναμικού προγραμματισμού) διατυπώνεται ως εξής: προσδιορίστε ένα τέτοιο αποδεκτό στοιχείο ελέγχου X που μεταφέρει το σύστημα S από την κατάσταση s0 στην κατάσταση sn, στην οποία η αντικειμενική συνάρτηση Z παίρνει τη μεγαλύτερη (μικρότερη ) αξία.

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

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

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

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

Η κατάσταση sk μετά το kth βήμα ελέγχου εξαρτάται μόνο από την προηγούμενη κατάσταση sk-1 και τον έλεγχο Xk («καμία συνέπεια»).

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

2. Αρχή βελτιστοποίησης και εξισώσεις Bellman

Αρχή βελτιστοποίησηςδιατυπώθηκε για πρώτη φορά από τον Richard Ernest Bellman το 1953 (όπως ερμηνεύεται από τον E.S. Wentzel):

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

ΣΧΕΤΙΚΑ ΜΕ. Ο Bellman διατύπωσε επίσης τις συνθήκες κάτω από τις οποίες ισχύει η αρχή. Η κύρια απαίτηση είναι ότι η διαδικασία ελέγχου πρέπει να είναι χωρίς ανάδραση, δηλ. Ο έλεγχος σε αυτό το βήμα δεν πρέπει να επηρεάζει τα προηγούμενα βήματα.

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

Στο τελευταίο βήμα, με βάση την κατάσταση του συστήματος s n-1 διαχειριστική απόφαση Χ n μπορεί να προγραμματιστεί τοπικά βέλτιστα, δηλ. με βάση μόνο τις εκτιμήσεις αυτού του βήματος.

Εξετάστε το τελευταίο ένατο βήμα:

μικρό n-1 - κατάσταση του συστήματος στην αρχή του nου βήματος.

μικρό n - τελική κατάσταση του συστήματος.

Χ n - Έλεγχος στο nο βήμα.

φά n (μικρό n-1 , Χ n ) είναι η αντικειμενική συνάρτηση (απόδοση) του ν ου βήματος.

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

Ας υποδηλώσουμε με το βέλτιστο (για βεβαιότητα θα πάρουμε το μέγιστο) της αντικειμενικής συνάρτησης - δείκτη της αποτελεσματικότητας του nου βήματος, με την προϋπόθεση ότι στην αρχή του τελευταίου βήματος το σύστημα S ήταν σε αυθαίρετη κατάσταση sn-1 , και στο τελευταίο βήμα ο έλεγχος ήταν βέλτιστος.

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

Η μεγιστοποίηση πραγματοποιείται σε όλους τους αποδεκτούς ελέγχους Xn.

Η λύση Xn στην οποία επιτυγχάνεται αυτό εξαρτάται επίσης από το sn-1 και ονομάζεται βέλτιστη υπό συνθήκη λύση στο nο βήμα. Ας το χαρακτηρίσουμε με.

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

Ας εξετάσουμε ένα πρόβλημα δύο βημάτων: προσθέστε το (n-1) -ο στο ν-ο βήμα.

Για οποιεσδήποτε καταστάσεις sn-2, αυθαίρετες αποφάσεις διαχείρισης Xn-1 και βέλτιστο έλεγχο στο nο βήμα, η τιμή της αντικειμενικής συνάρτησης στα δύο τελευταία βήματα υπολογίζεται από τον τύπο:

Σύμφωνα με την αρχή της βελτιστότητας του Bellman για κάθε s n-2 η λύση πρέπει να επιλεγεί έτσι ώστε, μαζί με τον βέλτιστο έλεγχο στο τελευταίο (ν) βήμα, να οδηγεί στο βέλτιστο της αντικειμενικής συνάρτησης στα δύο τελευταία βήματα. Επομένως, είναι απαραίτητο να βρεθεί η βέλτιστη έκφραση (6) για όλες τις αποδεκτές αποφάσεις διαχείρισης Xn-1 :

Ονομάζεται το υπό όρους μέγιστο της αντικειμενικής συνάρτησης υπό βέλτιστο έλεγχο στα δύο τελευταία βήματα. Πρέπει να σημειωθεί ότι η έκφραση σε σγουρές αγκύλες στον τύπο (6) εξαρτάται μόνο από τα sn-2 και Xn-1, αφού το sn-1 μπορεί να βρεθεί από την εξίσωση των καταστάσεων (1) με:

Ο αντίστοιχος έλεγχος Xn-1 στο (n-1) βήμα συμβολίζεται με και ονομάζεται βέλτιστος έλεγχος υπό όρους στο (n-1) βήμα.

Τα βέλτιστα υπό όρους της αντικειμενικής συνάρτησης προσδιορίζονται ομοίως για βέλτιστο έλεγχο σε βήματα (n-k+1), ξεκινώντας από το k-ο έως το τέλος, με την προϋπόθεση ότι στην αρχή του k-ου βήματος το σύστημα ήταν σε κατάσταση sk -1:

Ο έλεγχος Xk στο kth βήμα, στο οποίο επιτυγχάνεται το μέγιστο σύμφωνα με το (8), συμβολίζεται και ονομάζεται βέλτιστος υπό όρους έλεγχος στο kth βήμα.

Οι εξισώσεις (5) και (8) ονομάζονται επαναλαμβανόμενες εξισώσεις Bellman (αντίστροφο σχήμα). Η διαδικασία επίλυσης αυτών των εξισώσεων ονομάζεται περιορισμένη βελτιστοποίηση.

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

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

, …, - βέλτιστα στοιχεία ελέγχου υπό όρους στο nth, (n-1) - th, …, στο 1ο βήμα.

Χρησιμοποιώντας αυτές τις ακολουθίες, μπορούμε να βρούμε μια λύση στο πρόβλημα δυναμικού προγραμματισμού με τα n και s0:

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

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

Η βέλτιστη λύση στο πρόβλημα σε αυτή την περίπτωση βρίσκεται σύμφωνα με το ακόλουθο σχήμα:

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

Επιλέξτε μια μέθοδο για τη διαίρεση της διαδικασίας διαχείρισης σε βήματα.

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

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

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

Καθορίζεται η βέλτιστη τιμή της αντικειμενικής συνάρτησης και η βέλτιστη λύση.

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

Υπάρχει ένα ορισμένο ποσό πόρων s0 που πρέπει να διανεμηθεί σε n επιχειρηματικές οντότητες για τρέχουσες δραστηριότητες κατά την υπό εξέταση περίοδο (μήνας, τρίμηνο, εξάμηνο, έτος κ.λπ.) προκειμένου να επιτευχθεί ένα συνολικό μέγιστο κέρδος. Το μέγεθος των επενδύσεων πόρων xi (;) στις δραστηριότητες κάθε οικονομικής οντότητας είναι πολλαπλάσιο μιας ορισμένης τιμής h. Είναι γνωστό ότι κάθε οικονομική οντότητα, ανάλογα με τον όγκο των κεφαλαίων που χρησιμοποιήθηκαν xi για την υπό εξέταση περίοδο, αποφέρει κέρδος ύψους fi(xi) (δεν εξαρτάται από την επένδυση πόρων σε άλλες οικονομικές οντότητες).

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

Ας εισαγάγουμε υπόψη τη συνάρτηση - το υπό όρους βέλτιστο συνολικό κέρδος που λαμβάνεται από τις k-th, (k+1) - th, ..., n-th οικονομικές οντότητες, εάν οι πόροι στο ποσό του sk-1 () ήταν βέλτιστα κατανεμημένα μεταξύ τους. Το σύνολο των πιθανών αποφάσεων διαχείρισης σχετικά με το μέγεθος των κατανεμημένων πόρων στο k-ο βήμα μπορεί να παρουσιαστεί ως εξής: .

Τότε οι επαναλαμβανόμενες εξισώσεις της R.E. Bellman (αντίστροφο διάγραμμα) θα μοιάζει με:

Παράδειγμα.Υπάρχει ένα ορισμένο ποσό πόρων s0=100, οι οποίοι πρέπει να κατανεμηθούν σε n=4 επιχειρηματικές οντότητες για τρέχουσες δραστηριότητες κατά την υπό εξέταση περίοδο (μήνας) προκειμένου να επιτευχθεί το συνολικό μέγιστο κέρδος. Το μέγεθος της επένδυσης των πόρων xi (;) στις δραστηριότητες κάθε οικονομικής οντότητας είναι πολλαπλάσιο της τιμής h=20 και προσδιορίζεται από το διάνυσμα Q. Είναι γνωστό ότι κάθε οικονομική οντότητα, ανάλογα με τον όγκο των κεφαλαίων που χρησιμοποιεί xi για την υπό εξέταση περίοδο, αποφέρει κέρδος ύψους fi(xi) () (δεν εξαρτάται από την επένδυση πόρων σε άλλες οικονομικές οντότητες):

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

Λύση.Ας δημιουργήσουμε τις επαναλαμβανόμενες εξισώσεις του Bellman (αντίστροφο σχήμα):

Ας προσδιορίσουμε τα μέγιστα υπό όρους σύμφωνα με το (13), τα αποτελέσματα υπολογισμού παρουσιάζονται στον Πίνακα 1.

Πίνακας 1. Υπολογισμός βέλτιστου υπό όρους

μικρό κ-1 Χ κ μικρό κ k=3k=2k=1 123456789101112000000000000200200+20=20 22 200+22=22 2200+22=22 22020022+0=22 17+0=1714+0=14400400+33=33 42 200+42=42 4200+42=42 420202022+20=42 17+22=3914+22=3640021+0=2120+0=2026+0=26600600+46=46 55 200+55=55 59 20 0+59=59 590204022+33=5517+42=59 14+42=56402021+20=4120+22=4226+22=4860037+0=3732+0=3235+0=35800800+30=30 68 200+68=68 72 200+72=72 73 20206022+46=6817+55=7214+59=73 404021+33=5420+42=6426+42=68602037+20=5732+22=5435+22=5780067+0=6761+0=6152+0=5210001000+42=42 87 800+87=87 8700+87=87 870208022+30=5217+68=8514+72=86406021+46=6720+55=7526+59=85604037+33=7032+42=7435+42=77802067+20=87 61+22=8352+22=74100058+0=5872+0=7261+0=61Με βάση τα αποτελέσματα της βελτιστοποίησης υπό όρους, θα προσδιορίσουμε τη βέλτιστη κατανομή των πόρων:

Έτσι, η βέλτιστη κατανομή πόρων είναι:

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

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

συμπέρασμα

Ο δυναμικός προγραμματισμός είναι ένας τομέας μαθηματικού προγραμματισμού που περιλαμβάνει ένα σύνολο τεχνικών και εργαλείων για την εύρεση της βέλτιστης λύσης, καθώς και τη βελτιστοποίηση κάθε βήματος στο σύστημα και την ανάπτυξη μιας στρατηγικής ελέγχου, δηλαδή η διαδικασία ελέγχου μπορεί να αναπαρασταθεί ως διαδικασία πολλαπλών βημάτων. Ο δυναμικός προγραμματισμός, χρησιμοποιώντας βήμα προς βήμα σχεδιασμό, επιτρέπει όχι μόνο την απλοποίηση της λύσης του προβλήματος, αλλά και την επίλυση εκείνων των προβλημάτων που δεν μπορούν να εφαρμοστούν με μεθόδους μαθηματικής ανάλυσης. Η απλούστευση της λύσης επιτυγχάνεται με τη σημαντική μείωση του αριθμού των υπό μελέτη επιλογών, καθώς αντί να επιλύεται ένα σύνθετο πολυμεταβλητό πρόβλημα μία φορά, η μέθοδος προγραμματισμού βήμα προς βήμα περιλαμβάνει την επίλυση σχετικά απλών προβλημάτων πολλές φορές. Όταν σχεδιάζουμε μια διαδικασία βήμα προς βήμα, προχωράμε από τα συμφέροντα ολόκληρης της διαδικασίας στο σύνολό της, δηλ. Όταν παίρνετε μια απόφαση σε ένα συγκεκριμένο στάδιο, είναι πάντα απαραίτητο να έχετε κατά νου τον τελικό στόχο. Ωστόσο, ο δυναμικός προγραμματισμός έχει και τα μειονεκτήματά του. Σε αντίθεση με τον γραμμικό προγραμματισμό, στον οποίο η μέθοδος simplex είναι καθολική, δεν υπάρχει τέτοια μέθοδος στον δυναμικό προγραμματισμό. Κάθε εργασία έχει τις δικές της δυσκολίες και σε κάθε περίπτωση είναι απαραίτητο να βρεθεί η καταλληλότερη μέθοδος λύσης. Το μειονέκτημα του δυναμικού προγραμματισμού είναι επίσης η πολυπλοκότητα της επίλυσης πολυδιάστατων προβλημάτων. Ένα πρόβλημα δυναμικού προγραμματισμού πρέπει να πληροί δύο προϋποθέσεις. Η πρώτη συνθήκη συνήθως ονομάζεται συνθήκη απουσίας επακόλουθου αποτελέσματος και η δεύτερη είναι η συνθήκη προσθετικότητας της αντικειμενικής συνάρτησης του προβλήματος. Στην πράξη, υπάρχουν προβλήματα σχεδιασμού στα οποία τυχαίοι παράγοντες παίζουν σημαντικό ρόλο, επηρεάζοντας τόσο την κατάσταση του συστήματος όσο και το κέρδος. Υπάρχει διαφορά μεταξύ ντετερμινιστικών και στοχαστικών προβλημάτων δυναμικού προγραμματισμού. Σε ένα ντετερμινιστικό πρόβλημα, ο βέλτιστος έλεγχος είναι μοναδικός και προσδιορίζεται εκ των προτέρων ως ένα άκαμπτο πρόγραμμα ενεργειών. Σε ένα στοχαστικό πρόβλημα, ο βέλτιστος έλεγχος είναι τυχαίος και επιλέγεται κατά τη διάρκεια της ίδιας της διαδικασίας, ανάλογα με την τυχαία κατάσταση. Σε ένα ντετερμινιστικό σχήμα, που περνά από τη διαδικασία σταδιακά από το τέλος στην αρχή, υπάρχει επίσης μια ολόκληρη σειρά βέλτιστων ελέγχων υπό όρους σε κάθε στάδιο, αλλά από όλους αυτούς τους ελέγχους, μόνο ένας πραγματοποιήθηκε τελικά. Αυτό δεν συμβαίνει σε ένα στοχαστικό σχήμα. Κάθε ένας από τους βέλτιστους ελέγχους υπό όρους μπορεί πραγματικά να εφαρμοστεί εάν η προηγούμενη πορεία της τυχαίας διαδικασίας οδηγήσει το σύστημα στην αντίστοιχη κατάσταση. Η αρχή της βέλτιστης είναι η βάση για τη σταδιακή επίλυση προβλημάτων δυναμικού προγραμματισμού. Τυπικοί εκπρόσωποι των οικονομικών προβλημάτων του δυναμικού προγραμματισμού είναι τα λεγόμενα προβλήματα παραγωγής και αποθήκευσης, προβλήματα διανομής επενδύσεων κεφαλαίου, προβλήματα προγραμματισμού παραγωγής και άλλα. Τα προβλήματα δυναμικού προγραμματισμού χρησιμοποιούνται στον προγραμματισμό των δραστηριοτήτων μιας επιχείρησης, λαμβάνοντας υπόψη τις αλλαγές στην ανάγκη για προϊόντα με την πάροδο του χρόνου. Στη βέλτιστη κατανομή των πόρων μεταξύ των επιχειρήσεων σε κατεύθυνση ή χρόνο. Η περιγραφή των χαρακτηριστικών του δυναμικού προγραμματισμού και των τύπων προβλημάτων που μπορούν να διατυπωθούν στο πλαίσιό του πρέπει απαραίτητα να είναι πολύ γενική και κάπως ασαφής, αφού υπάρχει μια τεράστια ποικιλία διαφορετικών προβλημάτων που ταιριάζουν στο σχήμα δυναμικού προγραμματισμού. Μόνο η μελέτη ενός μεγάλου αριθμού παραδειγμάτων δίνει μια σαφή κατανόηση της δομής του δυναμικού προγραμματισμού.

Βιβλιογραφία

Οικονομικά και μαθηματικά μοντέλα και μέθοδοι. Γραμμικός προγραμματισμός: Ένα εγχειρίδιο για σπουδαστές οικονομικών ειδικοτήτων / Συντάχθηκε από: Smirnov Yu.N., Shibanova E.V., Naberezhnye Chelny: KamPI Publishing House, 2004, 81 p.
Επιχειρησιακή Έρευνα στα Οικονομικά: Εγχειρίδιο. εγχειρίδιο για πανεπιστήμια / N.Sh. Kremer, Β.Α. Πούτκο, Ι.Μ. Trishin, Μ.Ν. Friedman; Εκδ. καθ. N.Sh. Κρέμερ. - Μ.: ΕΝΟΤΗΤΑ, 2000. - 407 σελ.
Kuznetsov A.V. και άλλα Ανώτερα μαθηματικά: Ματ. προγραμματισμός: Textbook/A.V. Kuznetsov, V.A. Σάκοβιτς, Ν.Ι. Κρύο; Υπό γενική εκδ. A.V. Κουζνέτσοβα. - Μν.: Πιο ψηλά. σχολείο, 1994. - 286 σελ.: ill.

Φροντιστήριο

Χρειάζεστε βοήθεια για τη μελέτη ενός θέματος;

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

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

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

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

Το διαχειριζόμενο σύστημα 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.

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

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

Δημοσιεύτηκε στις http://www.allbest.ru/

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

Για την επέκταση της παραγωγικής ικανότητας τριών επιχειρήσεων Α, Β και Γ, διατίθεται ένας ορισμένος αριθμός μονάδων πρόσθετης ηλεκτρικής ενέργειας σε ποσότητα x 0 = 8 μονάδες. Η ηλεκτρική ενέργεια μπορεί να απελευθερωθεί με τη μορφή 1, 2, 3, 4, 5, 6, 7 και 8 μονάδων. Επενδύοντας x i μονάδες ηλεκτρικής ενέργειας στην ανάπτυξη της i-ης επιχείρησης, μπορείτε να λάβετε έσοδα από i μονάδες στην επιχείρηση. Υπάρχουν διάφορες επιλογές x i (k) για την κατανομή πρόσθετης ηλεκτρικής ενέργειας. Φέρνουν εισόδημα στο i (k), k=1,n. Πιθανές επιλογές για την ανάπτυξη των επιχειρήσεων δίνονται στον Πίνακα 1. Το συνολικό εισόδημα για όλες τις επιχειρήσεις πρέπει να είναι μέγιστο, δηλαδή y=? y i (k)>μέγ

Τραπέζι 1. Επιλογές ανάπτυξης επιχειρήσεων

Επιλογή ια	Επιχείρηση Α	Επιχείρηση Β	Επιχείρηση Γ

Μαθηματικός σκαλωσιά καθήκοντα:

y=? στο Εγώ (ια)> Μέγιστη

?Χ Εγώ (κ);χ 0

Λύση:

Ας αρχίσουμε να εξετάζουμε τη διαδικασία για την επίλυση του προβλήματος από το τελευταίο (3 βήματα) στάδιο (Πίνακας 2), στο οποίο οι επενδύσεις κατανέμονται στην επιχείρηση Γ. Ως λύση στην εξίσωση αναζητείται ο βέλτιστος έλεγχος υπό όρους στο τρίτο στάδιο

g C (S 2)=max k f c, x C (k)?S 2, k=1,2,3,4

Τραπέζι 2. Βέλτιστες υπό όρους λύσεις (βήμα 3)

κατάσταση		Ελεγχος

Υπάρχουν τέσσερις δυνατότητες για επένδυση κεφαλαίων - έλεγχοι τεσσάρων βημάτων x C (1) = 0 μονάδες, x C (2) = 1 μονάδα, x C (3) = 2 μονάδες, x C (4) = 3 μονάδες. και εννέα θεωρητικά πιθανές καταστάσεις του συστήματος S 2 που προηγούνται της κατανομής κεφαλαίων στην επιχείρηση C - οι όγκοι των επενδύσεων που δεν κατανεμήθηκαν στο 3ο στάδιο: 0,1,2,3,4,5,6,7,8.

Ας υποθέσουμε ότι το σύστημα ήταν σε κατάσταση S 2 =2. Τότε, για τον έλεγχο του βήματος x C (2) = 1, το εισόδημα του C (2) θα είναι ίσο με 3 μονάδες. (Πίνακας 3) και ο έλεγχος βήματος x C (3) = 2 θα είναι ο βέλτιστος για αυτήν την κατάσταση, δίνοντας υπό όρους μέγιστο κέρδος g c (S 2) = 5. Εάν το σύστημα ήταν στην κατάσταση S 2 =3, τότε επιτρέπονται όλα τα βήματα ελέγχου: x C (1) = 0 μονάδες, x C (2) = 1 μονάδα, x C (3) = 2 μονάδες, x C (4) = 3 μονάδες , και ο βέλτιστος έλεγχος θα είναι x C (4) = 3, που παρέχει υπό όρους μέγιστο κέρδος g c (S 2) = 6.

Πίνακας 3 Κατανομή επενδύσεων δυναμικού προγραμματισμού

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

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

g A (S 1)=max k f A +g c], x A (k)?S 1, k=1,2,3,4

Έτσι, για την κατάσταση S 1 =3 με έλεγχο βήματος x A (2) = 1 λαμβάνουμε:

g A (S 1)=max k f A +g c ]

Max k 4+g c =4+5=9, όπου βρίσκουμε από τον Πίνακα 1, και g c από τον Πίνακα 3. Όλες οι καταστάσεις συμπληρώνονται παρόμοια.

Τραπέζι 4. Βέλτιστες υπό όρους λύσεις (βήμα 2)

κατάσταση	f A +g γ	Ελεγχος

Εδώ προκύπτουν καταστάσεις στις οποίες η βέλτιστη λύση δεν θα είναι η μόνη. Έτσι, στην κατάσταση S 1 = 3, τα βήματα ελέγχου x A (2) = 1 και x A (3) = 2 θα είναι υπό όρους βέλτιστη, δίνοντας το ίδιο. κέρδος g A (S 1)=9

Τραπέζι 5. Βέλτιστες άνευ όρων λύσεις (βήμα 1)

Στο πρώτο στάδιο (Πίνακας 5) - η κατανομή των επενδύσεων στην επιχείρηση Β - υπάρχει μόνο μία προηγούμενη κατάσταση του συστήματος, που αντιστοιχεί στην αρχική κατάσταση S 0 =8. Το άνευ όρων βέλτιστο κέρδος καθορίζεται από την έκφραση:

y * = g B (S 0) = max k (f A +g A) x in (k)?S 0 =x 0, k=1,2,3,4,5

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

Το σχήμα για την εύρεση όλων των βέλτιστων επιλογών για την κατανομή των επενδύσεων μεταξύ των επιχειρήσεων (Πίνακας 6) παρουσιάζεται στο Σχήμα 1.

Τραπέζι 6. Βέλτιστη κατανομή των επενδύσεων.

Σχήμα 1. Σχέδιο βέλτιστης κατανομής των επενδύσεων μεταξύ των επιχειρήσεων

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

Δημοσιεύτηκε στο Allbest.ru

...

Παρόμοια έγγραφα

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

εργασία μαθήματος, προστέθηκε στις 25/04/2015

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

εργασία μαθήματος, προστέθηκε 30/12/2010

Δυναμική μέθοδος προγραμματισμού και τα κύρια στάδια της. Βέλτιστη στρατηγική αντικατάστασης εξοπλισμού. Ελαχιστοποίηση του κόστους κατασκευής και λειτουργίας επιχειρήσεων. Βέλτιστη κατανομή πόρων στην STROYKROVLYA LLC και επενδύσεις στην PKT Khimvolokno.

εργασία μαθήματος, προστέθηκε 01/08/2015

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

διατριβή, προστέθηκε 08/07/2013

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

εργασία μαθήματος, προστέθηκε 14/01/2011

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

δοκιμή, προστέθηκε στις 15/10/2010

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

εργασία μαθήματος, προστέθηκε 16/12/2013

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

παρουσίαση, προστέθηκε 12/02/2014

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

διατριβή, προστέθηκε 02/11/2017

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

Εργαστηριακές εργασίες

Επιστήμη Υπολογιστών, Κυβερνητική και Προγραμματισμός

Κεφάλαια Χ που κατανέμονται σε ποια επιχείρηση αποφέρει κέρδη στο τέλος του έτους. Οι συναρτήσεις δίνονται σε έναν πίνακα: X f1X f2X f3X f4X 1 8 6 3 4 2 10 9 4 6 3 11 11 7 8 4 12 13 11 13 5 18 15 18 16 Προσδιορίστε πόσα χρήματα χρειάζεται να διατεθούν σε κάθε επιχείρηση ότι το συνολικό κέρδος ισούται με το άθροισμα των κερδών που έλαβε από κάθε επιχείρηση ήταν το μεγαλύτερο. Έστω το ποσό των κεφαλαίων που διατίθενται σε ποια επιχείρηση. Οι εξισώσεις στο μθ βήμα ικανοποιούν την προϋπόθεση: είτε δεν κατανέμουμε τίποτα σε ποια επιχείρηση: είτε όχι περισσότερο από αυτό...

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

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

Σύντομες θεωρητικές πληροφορίες

Η κατασκευή ενός μοντέλου δυναμικού προγραμματισμού (DP) και η εφαρμογή της μεθόδου DP για την επίλυση του προβλήματος καταλήγει στα εξής:

επιλέξτε μια μέθοδο διαίρεσης της διαδικασίας διαχείρισης σε βήματα.
ορίστε παραμέτρους κατάστασης και μεταβλητές ελέγχου X k σε κάθε βήμα.
Καταγράψτε τις εξισώσεις κατάστασης.
εισάγουν αντικειμενικές συναρτήσειςκ το βήμα και η συνολική αντικειμενική συνάρτηση.
εισαγάγετε υπόψη υπό όρους μέγιστα (ελάχιστα) και υπό όρους βέλτιστο έλεγχο σε kο βήμα: .
Καταγράψτε το κύριο DP για το υπολογιστικό κύκλωμαΕξισώσεις Bellmanγια και σύμφωνα με τον κανόνα:

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

α) και

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

Δήλωση του προβλήματος δυναμικού προγραμματισμού σε γενική μορφή.

Το έργο . Για το επόμενο έτος προγραμματίζονται οι δραστηριότητες τεσσάρων βιομηχανικών επιχειρήσεων. Αρχικά κεφάλαια: USD Το ποσό της επένδυσης σε κάθε επιχείρηση είναι πολλαπλάσιο της 1 συμβατικής μονάδας. ΕγκαταστάσειςΧ, κατανεμήθηκε κ

f 1 (X)	f2(X)	f 3 (X)	f 4 (X)

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

Λύση. Έστω το ποσό των κεφαλαίων που διατέθηκανκ -η επιχείρηση. Το συνολικό κέρδος είναι ίσο. ΜεταβλητέςΧ πληρούν τους περιορισμούς: . Απαιτείται να βρεθούν μεταβλητές που ικανοποιούν αυτούς τους περιορισμούς και να μεγιστοποιήσουν τη συνάρτησηΖ.

Διάγραμμα λύσης το πρόβλημα με τη χρήση της μεθόδου DP έχει την ακόλουθη μορφή: η διαδικασία επίλυσης της διανομής κεφαλαίων μπορεί να θεωρηθεί ως διαδικασία 4 βημάτων, ο αριθμός βήματος συμπίπτει με τον αριθμό της επιχείρησης. επιλογή των εξισώσεων μεταβλητών στις 1, 2, 3, 4 βήματα ανάλογα. - η τελική κατάσταση της διαδικασίας διανομής είναι ίση με μηδέν, επειδή όλα τα κεφάλαια πρέπει να επενδύονται στην παραγωγή,=0 .

Οι εξισώσεις κατάστασης και το σχήμα κατανομής μπορούν να παρασταθούν ως:

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

Ας εισαγάγουμε υπόψη μια συνάρτηση - το υπό όρους βέλτιστο κέρδος που λαμβάνεται από το ith, ( k +1 )ου, ..., 4ης επιχειρήσεων, εάν τα κεφάλαια κατανεμήθηκαν βέλτιστα μεταξύ τους). Οι εξισώσεις στο βήμα ικανοποιούν την συνθήκη: (ήκ Δεν διαθέτουμε τίποτα στην -η επιχείρηση: είτε όχι περισσότερο από αυτό που διαθέτουμε kο βήμα :).

Οι εξισώσεις του Bellman έχουν τη μορφή:

Οι εξισώσεις λύνονται με διαδοχική βελτιστοποίηση κάθε βήματος.

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

Βήμα 3 . Κάνουμε υποθέσεις σχετικά με το υπόλοιπο των κεφαλαίων στο 3ο βήμα: μπορεί να πάρει τιμές 0,1,2,3,4,5 (=0, εάν όλα τα κεφάλαια δοθούν στην 1η και 2η επιχείρηση κ.λπ.). Ανάλογα με αυτό, επιλέγουμε και συγκρίνουμε τις αθροιστικές τιμές για διαφορετικές τιμές σε σταθερές τιμές. Για καθεμία, το μέγιστο από αυτές τις τιμές είναι το υπό όρους βέλτιστο κέρδος που επιτυγχάνεται με τη βέλτιστη κατανομή των κεφαλαίων μεταξύ της 3ης και της 4ης επιχείρησης. Οι λαμβανόμενες τιμές για δίνονται στον πίνακα στις στήλες 5 και 6, αντίστοιχα.

S k-1	k =3	k =2	k =1
	f 3 (X 3 )+	f 2 (X 2 )+	f 1 (X 1 )+


	0+4=4 3+0=3	0+4=4 6+0=6	0+6=6 8+0=8
	0+6=6 3+4=7 4+0=4	0+7=7 6+4=10 9+0=9	0+10=10 8+6=14 10+0=10
	0+8=8 3+6=9 4+4=8 7+0=7	0+9=9 6+7=13 9+4=13 11+0=11	0+13=13 8+10=18 10+6=16 11+0=11
	0+13=13 3+8=11 4+6=10 7+4=11 11+0=11	0+13=13 6+9=15 9+7=16 11+4=15 13+0=13	0+16=16 8+13=21 10+10=20 11+6=17 12+0=12
	0+16=16 3+13=16 4+8=12 7+6=13 11+4=15 18+0=18	0+18=18 6+13=19 9+9=18 11+7=18 13+4=17 15+0=15	0+19=19 8+16=24 10+13=23 11+10=21 12+6=18 18+0=18

2 βήμα k =2. Για όλες τις πιθανές τιμές, οι τιμές για και βρίσκονται στις στήλες 8 και 9, αντίστοιχα. οι πρώτοι όροι στη στήλη 7 οι τιμές λαμβάνονται από τη συνθήκη, οι δεύτεροι όροι λαμβάνονται από τη στήλη 5 όταν.

1 βήμα . Η βελτιστοποίηση υπό όρους πραγματοποιείται στον πίνακα στο k = 1 για.

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

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

Ομοίως, όταν, και;

Πότε, και;

Συγκρίνοντας τις λαμβανόμενες τιμές, λαμβάνουμε στο.

Υπολογίζοντας, παίρνουμε και από τον πίνακα της στήλης 9 βρίσκουμε. Στη συνέχεια βρίσκουμε και στη στήλη 6. Τέλος, και. Βέλτιστη λύση.

Απάντηση. Το μέγιστο συνολικό κέρδος είναι 24 USD. υπό τον όρο ότι σε 1 επιχείρηση διατίθεται 1 USD. Στη 2η επιχείρηση διατέθηκαν 2 USD. 3η επιχείρηση - 1 USD; 4η επιχείρηση - 1 USD

Υλοποίηση της εργασίας σε MS Excel

Η εισαγωγή των αρχικών δεδομένων στον πίνακα φαίνεται στο Σχ. 1.

Εικ.1. Εισαγωγή δεδομένων προέλευσης στα κελιά του φύλλου εργασίας MS Excel

2. Η σειρά συμπλήρωσης των κελιών του πίνακα:

1). Στο κελί Ε 15 εισαγάγετε τον τύπο INDEX($B$3:$F$8,MATCH($C15,$B$3:$B$8),G$12+1) και αντιγράψτε τον τύπο στην περιοχή των κελιών μεΕ 15 έως Ε 35.

2). Στο κελί F 15 εισαγάγετε τον τύπο

INDEX($B$3:$F$8,MATCH($D15,$B$3:$B$8),5) και αντιγράψτε τον τύπο στην περιοχή των κελιών με F 15 έως F 35.

3). Στο κελί G 15 εισαγάγετε τον τύπο E 15+ F 15 και αντιγράψτε τον τύπο στην περιοχή: G 15 - G 35.

4). Βρίσκουμε τη μέγιστη τιμή για κάθε κατάσταση από 0 έως 5, για αυτό το σκοπό στο κελίΗ 15 πληκτρολογήστε τον τύπο MAX(G15); μετά την εισαγωγή ενός τύπου σε ένα κελίΗ 16 πρέπει να αλλάξετε το εύρος από G 16 έως G 16: G 17, κλπ. σε όλη τη στήλη μέχρι το κελίΗ 30 (Εικ. 2α).

3. Βρείτε την τιμή ελέγχου που αντιστοιχεί στη μέγιστη τιμή της συνάρτησης, για το σκοπό αυτό στο κελίεγώ 15 ας εισάγουμε τον τύπο INDEX($ C 15: G 15; MATCH(H 15; G 15;0);1), αντιγράψτε τον τύπο στο κελίεγώ 16 και αυξήστε το εύρος, με αποτέλεσμα το κελίεγώ 16 παίρνουμε: INDEX($ C 16: G 17; MATCH(H 16; G 16: G 17;0);1). Στη συνέχεια, αντιγράψτε τον τύπο στα κελιάεγώ 18, εγώ 21, εγώ 25, εγώ 30 , αυξάνοντας σταδιακά το εύρος (Εικ. 2β)

Εικ.2α. Τύπος φύλλου εργασίας με τύπους, k = 3.

Εικ. 2β (δεξιά πλευρά του φύλλου εργασίας με τύπους, k =3

Ως αποτέλεσμα παίρνουμε:

Ρύζι. 3 . Το αποτέλεσμα του πρώτου βήματος ( k = 3).

4. Επιλέξτε μια περιοχήΕ 15: Ι 35, εκτελέστε την εντολήΑντίγραφο J 15 και εκτελέστε την εντολήΕισάγετε .

5. Ας αλλάξουμε τον τύπο συνάρτησης. Σε κύτταραΚ 15, Κ 16, Κ 18, Κ 21, Κ 25, Κ 30 εισάγουμε, αντίστοιχα, τις μέγιστες τιμές του προηγούμενου βήματος που βρίσκονται στα κελιάΗ 15, Η 16, Η 18, Η 21, Η 25, Η 30. Στα υπόλοιπα κελιά τοποθετούμε τις τιμέςστην ίδια στήλη και αντίστοιχες με τις προηγούμενες S k . :

Στο κελί Κ 17 αντιγράψτε τις τιμές του κελιού K15.

στα κελιά K19 και K20 τιμές K16 και K17.

σε τιμές K22:K24 · K18:K20;

σε τιμές K26:K29 · K21:K24;

σε τιμές K31:K35 · K25:K29;

Ως αποτέλεσμα παίρνουμε:

Εικ.4. Το αποτέλεσμα του δεύτερου βήματος ( k = 2).

6. Επιλέξτε μια περιοχή κελιών J15: N 35, εκτελέστε την εντολήαντίγραφο , τοποθετήστε τον κέρσορα στο κελίΟ 15, εκτελέστε την εντολήΕισάγετε . Ως αποτέλεσμα, λαμβάνουμε έναν ολοκληρωμένο πίνακα με μια λύση για k =1 (Εικ.5)

7. Ας εξηγήσουμε τα αποτελέσματα που προέκυψαν: στο. Υπολογίζοντας, παίρνουμε και από τον πίνακα της στήλης 12 βρίσκουμε. Στη συνέχεια προσδιορίζουμε και από τη στήλη 6. Τέλος, και. Έτσι, η βέλτιστη τιμή και η τιμή της συνάρτησης είναι 24 cu, η οποία είναι σύμφωνη με τα δεδομένα που λαμβάνονται χειροκίνητα.

Εικ.6. Το αποτέλεσμα του τρίτου βήματος ( k = 1).

Ασκήσεις ελέγχου. Επιλογές.

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

f 1 (X)	f2(X)	f 3 (X)	f 4 (X)

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

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

f 1 (X)	f2(X)	f 3 (X)

Καθώς και άλλα έργα που μπορεί να σας ενδιαφέρουν
58796.		Γεωγραφική Προοπτική	977,5 KB
	Μέχρι το τέλος του μαθήματος θα πρέπει να είστε σε θέση να αναγνωρίζετε και να κατανοείτε νέες λέξεις και συνδυασμούς λέξεων στο κείμενο, να διαβάζετε και να κατανοείτε την ουσία και τις λεπτομέρειες παρά τις φυσικές δυσκολίες.
58797.		Πληροφορίες και διαδικασίες πληροφόρησης. Υπολογιστικό σύστημα	128 KB
	Zagalny χαρακτηρισμός αυτών. Κανόνες ασφαλείας στον λογαριασμό PEOM. Επιστήμη των υπολογιστών. Έννοιες της πληροφορίας. Πληροφορίες και θόρυβος. Πληροφοριακές διαδικασίες. Πληροφορίες και ειδοποίηση.
58798.		Λειτουργικά συστήματα	126 KB
	Τραπέζι εργασίας. Βασικά αντικείμενα των Windows. Όραση του αντικειμένου. Λειτουργίες, εξουσίες και βασικές εντολές για εργασία με αντικείμενα. Μενού περιβάλλοντος αντικειμένου. Οι ετικέτες είναι για το σκοπό τους.
58799.		Βασικά στοιχεία της ρομποτικής με δίσκους	144,5 KB
	Zagalny χαρακτηρισμός αυτών. Μορφοποίηση δίσκου. Διάγνωση και ανασυγκρότηση δίσκων. Ενημερωμένες πληροφορίες στο δίσκο. Κανόνες εγγραφής και ανάγνωσης πληροφοριών από δισκέτες.
58800.		Επεξεργαστής κειμένου	190 KB
	Συστήματα επεξεργασίας κειμένου και οι κύριες λειτουργίες τους. Έμπνευση για ένα πρόγραμμα επεξεργασίας κειμένου. Διεπαφή επεξεργαστή. Σειρά πληροφοριών. Λειτουργίες οθόνης, vikoristannya vikon.
58801.		Επεξεργαστής γραφικών	708 KB
	Zagalny χαρακτηρισμός αυτών. Γραφικά μηχανών. Γραφική οθόνη. Γραφικό σύστημα επεξεργασίας πληροφοριών. Τα ένθετα είναι σχέδια πρωτόγονων γραφικών όταν εργάζεστε με έναν επεξεργαστή. Τύποι αρχείων γραφικών.
58802.		Ηλεκτρονικοί πίνακες	280,5 KB
	Ναβχάλνα. Περιγράψτε ένα νέο θέμα και επισημάνετε τον ρόλο του στο μάθημα της επιστήμης των υπολογιστών. Εισαγάγετε την έννοια του ηλεκτρονικού πίνακα. Εξοικείωση των μαθητών με προγράμματα επεξεργασίας ET, κανόνες εισαγωγής και επεξεργασίας πληροφοριών στο ET και μεθόδους μορφοποίησης ET.
58803.		Συστήματα διαχείρισης βάσεων δεδομένων (DBMS)	156,5 KB
	Αφιερώματα Basi. Πραγματική βάση δεδομένων τεκμηρίωσης. Iєrarchical, merezheva, σχεσιακό μοντέλο της βάσης δεδομένων. Τα κύρια στοιχεία της βάσης δεδομένων: πεδίο, εγγραφή, αρχείο. DBMS.