Η ουσία των μεθόδων δυναμικού προγραμματισμού. Η έννοια του δυναμικού προγραμματισμού

Ο φθηνότερος τρόπος

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

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

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

Η έννοια του «δυναμικού προγραμματισμού» χρησιμοποιήθηκε για πρώτη φορά τη δεκαετία του 1940 από τον Richard Bellman για να περιγράψει τη διαδικασία εύρεσης λύσης σε ένα πρόβλημα όπου η απάντηση σε ένα πρόβλημα μπορεί να ληφθεί μόνο αφού λυθεί ένα άλλο πρόβλημα που «προηγείται».
Έτσι, ο Αμερικανός μαθηματικός και ένας από τους κορυφαίους ειδικούς στον τομέα των μαθηματικών και της τεχνολογίας υπολογιστών - Ρίτσαρντ Ερνστ Μπέλμαν- έγινε ο πατέρας του δυναμικού προγραμματισμού.

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

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

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

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

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

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

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

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

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

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

Ρύζι. 1.1. Μια άτυπη εξήγηση της ιδιότητας βελτιστοποίησης των υποπροβλημάτων

Η άτυπη εξήγηση συζητείται με περισσότερες λεπτομέρειες.

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

Αρχικά, εξετάστε τα προβλήματα βελτιστοποίησης (εργασίες 1-5):

1. Διαδρομή βέλτιστου μήκους

Παράδειγμα:Υπάρχει κάποιος οδικός χάρτης που παρουσιάζεται με τη μορφή γραφήματος. Στόχος μας: να βγούμε από το σημείο ΕΝΑστο σημείο σι. Αυτό πρέπει να γίνει με τέτοιο τρόπο ώστε να ελαχιστοποιείται η απόσταση ή η σπατάλη καυσίμου.

Αντικειμενική λειτουργίαεδώ είναι η απόσταση από ΕΝΑπριν σι. Εκείνοι. στόχος μας είναι να ελαχιστοποιήσουμε την απόσταση.

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

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

2. Αντικατάσταση μηχανήματος (ελαχιστοποίηση του κόστους)

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

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

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

3. Ανταλλαγή χαρτοφυλακίου

Παράδειγμα:Παίζοντας στο χρηματιστήριο, αγορά μετοχών οποιωνδήποτε εταιρειών


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

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

4. Κατάρτιση σχεδίου βέλτιστης παραγωγής (logistics)

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


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

Μεταβλητή επιλογής:επιλέγοντας πόσες καρέκλες ή τραπέζια πρέπει να φτιαχτούν για να έχουν αρκετή εργασία.

5. Παιχνίδια (πιθανολογικά ή μη)

Παράδειγμα:Συμμετοχή σε διάφορα παιχνίδια


Αντικειμενική λειτουργία:μεγιστοποίηση της πιθανότητας νίκης ή μεγιστοποίηση της μέσης νίκης κ.λπ.

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

Τα προβλήματα 1 - 5 είναι παραδείγματα προβλημάτων βελτιστοποίησης.

Συνδυαστική:

6. Γραφήματα και δέντρα

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

7. Πρόβλημα ανταλλαγής νομισμάτων ή αριθμός τρόπων επιστροφής αλλαγών

Παράδειγμα:Υπάρχουν νομίσματα διαφορετικής ονομαστικής αξίας, με ποιους τρόπους μπορείτε να επιστρέψετε τα ρέστα.

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

Η έννοια του δυναμικού προγραμματισμού

Μια άτυπη εξήγηση της βελτιστοποίησης των υποπροβλημάτων DP.

Ας σκεφτούμε άτυποςιδέα DP.

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

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

• πόσες καρέκλες να παραχθούν - μεταβλητή X1,
• πόσοι πίνακες να παραχθούν - μεταβλητή X2,
• πόσοι εργαζόμενοι να προσληφθούν - μεταβλητή X3,
• ... Xn.

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

Ως εκ τούτου, η ΑΣ προτείνει τα εξής:

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

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

• Αφού βρούμε τη βέλτιστη λύση για την πρώτη υποεργασία, παίρνουμε την δευτερεύουσα εργασία για δύο μεταβλητές X1 και X2 και τη λύνουμε χρησιμοποιώντας την ήδη βρεθεί λύση για την πρώτη υποεργασία.
• Λαμβάνουμε μια λύση για μια μεγαλύτερη υποεργασία, όπου εμφανίζονται οι μεταβλητές X1 και X2. Στη συνέχεια, χρησιμοποιώντας τη λύση που προέκυψε, αναλαμβάνουμε υποεργασίες που καλύπτουν τα Χ1, Χ2 και Χ3.
• Και έτσι συνεχίζουμε μέχρι να βρούμε μια λύση για όλο το γενικό πρόβλημα.

Επίσημη ιδέα του DP

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

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

Το γεγονός είναι ότι:

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

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

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

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

Ένα απλό παράδειγμα επίλυσης προβλημάτων με χρήση DP

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

Παράδειγμα:Είναι απαραίτητο να υπολογίσετε το άθροισμα των n αριθμών: 1 + 2 + 3 + ... + n

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

• Ας ξεκινήσουμε με το άθροισμα του πρώτου στοιχείου, δηλ. απλά πάρτε το πρώτο στοιχείο:
  F(1) = 1
• Τώρα, χρησιμοποιώντας τη λύση για το πρώτο στοιχείο, λύνουμε
  F(2) = F(1) + 2 = 1 + 2 = 3, δηλ. πρέπει να πάρετε το άθροισμα του πρώτου στοιχείου και να προσθέσετε το δεύτερο στοιχείο σε αυτό
• F(3) = F(2) + 3 = 6
• Συνεχίζουμε κατ' αναλογία και λαμβάνουμε την αντικειμενική συνάρτηση:
  F(n) = F(n-1) + An

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

Ένα απλό παράδειγμα όπου το DP εξακολουθεί να χρησιμοποιείται αδικαιολόγητα (τεχνητά) καταδεικνύει την αρχή των ιδεών του DP.

Ας δούμε ένα άλλο παράδειγμα.

Παράδειγμα:υπάρχει μια σκάλα n σκαλοπατιών, μπροστά από την οποία υπάρχει ένα άτομο που είναι πίσω 1 Το βήμα μπορεί είτε να ανέβει στο επόμενο βήμα είτε να πηδήξει πάνω από ένα σκαλί. Ερώτηση: με πόσους τρόπους μπορεί να φτάσει στο τελευταίο σκαλοπάτι;

Ας εξετάσουμε τις απλούστερες επιλογές (υποεργασίες):

Ας δούμε ένα παράδειγμα βημάτων i

Πώς μπορούμε να φτάσουμε στο βήμα i:

1. από το βήμα i-1, και θα μπορούσαμε να φτάσουμε στο βήμα i-1 με τρόπους i-1
2. από το βήμα i-2, και θα μπορούσαμε να φτάσουμε στο βήμα i-2 με τρόπους i-2

Για παράδειγμα, πώς να φτάσετε 4ο βήμα:

Οτι., συνολικός αριθμός τρόπωνφτάστε στο βήμα i:
f(a i) = f(a i-1) + f(a i-2)

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

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

Ασκηση 1:εφαρμόστε ένα παράδειγμα για τα πρώτα δέκα βήματα (ουσιαστικά τους 10 πρώτους αριθμούς της σειράς Fibonacci) χρησιμοποιώντας αναδρομή.

Συμπληρώστε τον κωδικό:

var c:ακέραιος; διαδικασία getKolSposob(i,n: ακέραιος); ξεκινήστε να γράφετε (i+n," "); Inc(c); αν ... τότε getKolSposob(...,...) τέλος; έναρξη c:=1; getKolSposob(0,1); τέλος.

Εργασία 2:
Λύση 15ου τύπου εργασιών Ενιαίας Πολιτικής Εξέτασης (Γραφήματα. Εύρεση του αριθμού των μονοπατιών).

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

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

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

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

Ακολουθίες

Ακολουθία Fibonacci φά nδίνεται από τους τύπους: φά 1 = 1, φά 2 = 1,
Fn = φά n - 1 + φά n- 2 στις n> 1. Πρέπει να βρω φά nκατά αριθμό n.

Μια λύση που μπορεί να φαίνεται λογική και αποτελεσματική είναι η επίλυση με χρήση αναδρομής:

Int F(int n) (αν (n< 2) return 1; else return F(n - 1) + F(n - 2); }
Χρησιμοποιώντας μια τέτοια λειτουργία, θα λύσουμε το πρόβλημα "από το τέλος" - θα μειώσουμε βήμα προς βήμα nμέχρι να φτάσουμε σε γνωστές αξίες.

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

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

Int F(int n) ( if (A[n] != -1) return A[n]; if (n< 2) return 1; else { A[n] = F(n - 1) + F(n - 2); return A[n]; } }
Η λύση που δίνεται είναι σωστή και αποτελεσματική. Αλλά για αυτό το πρόβλημα ισχύει επίσης μια απλούστερη λύση:

F = 1; F = 1; για (i = 2; i< n; i++) F[i] = F + F;
Αυτή η λύση μπορεί να ονομαστεί λύση "από την αρχή" - πρώτα συμπληρώνουμε τις γνωστές τιμές και μετά βρίσκουμε την πρώτη άγνωστη τιμή ( φά 3), μετά το επόμενο κ.λπ., μέχρι να φτάσουμε στο επιθυμητό.

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

Μονοδιάστατος Δυναμικός Προγραμματισμός

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

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

Στο n < 32 полный перебор потребует нескольких секунд, а при n= 64 η εξαντλητική αναζήτηση δεν είναι κατ' αρχήν εφικτή. Για να λύσουμε το πρόβλημα χρησιμοποιώντας τη μέθοδο δυναμικού προγραμματισμού, μειώνουμε το αρχικό πρόβλημα σε δευτερεύουσες εργασίες.

Στο n = 1, n= 2 η απάντηση είναι προφανής. Ας υποθέσουμε ότι έχουμε ήδη βρει κ n - 1 , κ n- 2 — ο αριθμός τέτοιων ακολουθιών μήκους n- 1 και n - 2.

Ας δούμε πόσο μπορεί να είναι το μήκος της ακολουθίας n. Αν ο τελευταίος χαρακτήρας του είναι 0, τότε ο πρώτος n- 1 — οποιαδήποτε σωστή ακολουθία μήκους
n- 1 (δεν έχει σημασία αν τελειώνει με μηδέν ή ένα - ακολουθεί το 0). Υπάρχουν μόνο τέτοιες ακολουθίες κ n- 1 . Εάν ο τελευταίος χαρακτήρας είναι ίσος με 1, τότε ο προτελευταίος χαρακτήρας πρέπει να είναι ίσος με 0 (αλλιώς θα υπάρχουν δύο στη σειρά) και ο πρώτος
n- 2 χαρακτήρες - οποιαδήποτε έγκυρη ακολουθία μήκους n- 2, ο αριθμός τέτοιων ακολουθιών είναι ίσος κ n - 2 .

Ετσι, κ 1 = 2, κ 2 = 3, κ n = κ n - 1 + κ n- 2 στις n> 2. Δηλαδή, αυτή η εργασία καταλήγει στην εύρεση των αριθμών Fibonacci.

2D Δυναμικός Προγραμματισμός

Ακολουθούν μερικές διατυπώσεις τέτοιων εργασιών:

Εργασία 2. n*Μκύτταρα. Μπορείτε να κάνετε βήματα ενός κελιού προς τα δεξιά ή προς τα κάτω. Μετρήστε με πόσους τρόπους μπορείτε να φτάσετε από το επάνω αριστερό κελί στο κάτω δεξιά κελί.

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

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

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

Έτσι, για ένα κελί ( Εγώ, ι) ο αριθμός των διαδρομών A[i][j] θα είναι ίσος με
A[j] + A[i], δηλαδή το πρόβλημα μειώνεται σε δύο δευτερεύουσες εργασίες. Αυτή η υλοποίηση χρησιμοποιεί δύο παραμέτρους − ΕγώΚαι ι- επομένως, σε σχέση με αυτό το πρόβλημα μιλάμε για δισδιάστατο δυναμικό προγραμματισμό.

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

Στο πρόβλημα 3, σε ένα κελί με συντεταγμένες ( Εγώ, ι) μπορούμε να πάρουμε από κελιά με συντεταγμένες
(Εγώ- 1, j), ( Εγώ, ι- 1) και ( Εγώ - 1, ι- 1). Ας υποθέσουμε ότι για καθένα από αυτά τα τρία κελιά έχουμε ήδη βρει τη διαδρομή του ελάχιστου βάρους και τοποθετήσαμε τα ίδια τα βάρη σε W[j], W[i],
W. Για να βρείτε το ελάχιστο βάρος για ( Εγώ, ι), πρέπει να επιλέξετε το ελάχιστο από τα βάρη W[j], W[i], W και να προσθέσετε σε αυτό τον αριθμό που είναι γραμμένος στο τρέχον κελί:

W[i][j] = min(W[j], W[i], W) + A[i][j];

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

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

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

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

Επακόλουθα προβλήματα

Εργασία 4.Δίνεται μια ακολουθία ακεραίων. Είναι απαραίτητο να βρεθεί η μεγαλύτερη αυστηρά αυξανόμενη ακολουθία του.

Ας αρχίσουμε να λύνουμε το πρόβλημα από την αρχή - θα αναζητήσουμε την απάντηση, ξεκινώντας από τους πρώτους όρους αυτής της ακολουθίας. Για κάθε αριθμό Εγώθα αναζητήσουμε τη μεγαλύτερη αυξανόμενη υποακολουθία που τελειώνει με ένα στοιχείο στη θέση Εγώ. Αφήστε την αρχική ακολουθία να αποθηκευτεί στον πίνακα Α. Στον πίνακα L θα καταγράψουμε τα μήκη των μέγιστων υποακολουθιών που τελειώνουν με το τρέχον στοιχείο. Ας βρούμε όλα τα L[i] για 1<= Εγώ <= κ- 1. Τώρα μπορείτε να βρείτε το L[k] ως εξής. Εξετάζουμε όλα τα στοιχεία του A[i] για 1<= Εγώ < κ- 1. Αν
Ολα συμπεριλαμβάνονται]< A[k], то κΤο ου στοιχείο μπορεί να γίνει συνέχεια της υποακολουθίας που τελειώνει με το στοιχείο A[i]. Το μήκος της προκύπτουσας υποακολουθίας θα είναι 1 μεγαλύτερο από το L[i]. Για να βρείτε το L[k], πρέπει να περάσετε από όλα Εγώαπό 1 έως k - 1:
L[k] = max(L[i]) + 1, όπου το μέγιστο λαμβάνεται για όλα Εγώέτσι ώστε A[i]< A[k] и
1 <= Εγώ < κ.

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

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

Ας εξετάσουμε τη λύση σε αυτό το πρόβλημα χρησιμοποιώντας το παράδειγμα της ακολουθίας 2, 8, 5, 9, 12, 6. Δεδομένου ότι δεν υπάρχει στοιχείο πριν από το 2, η μέγιστη υποακολουθία περιέχει μόνο ένα στοιχείο - L = 1, και δεν υπάρχει κανένα πριν it - N = 0. Επιπλέον,
2 < 8, поэтому 8 может стать продолжением последовательности с предыдущим элементом. Тогда L = 2, N = 1.

Το μόνο στοιχείο μικρότερο από το A = 5 είναι το A = 2, επομένως το 5 μπορεί να γίνει συνέχεια μιας μόνο υποακολουθίας - αυτής που περιέχει 2. Τότε
L = L + 1 = 2, N = 1, αφού το 2 βρίσκεται στη θέση 1. Ομοίως, εκτελούμε άλλα τρία βήματα του αλγορίθμου και παίρνουμε το τελικό αποτέλεσμα.

Τώρα επιλέγουμε το μέγιστο στοιχείο στον πίνακα L και από τον πίνακα N ανακατασκευάζουμε την ίδια την υποακολουθία 2, 5, 9, 12.

Ένα άλλο κλασικό πρόβλημα δυναμικού προγραμματισμού είναι το πρόβλημα παλίνδρομου.

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

Ας συμβολίσουμε αυτή τη συμβολοσειρά με S και τα σύμβολά της με S[i], 1<= Εγώ <= n. Θα εξετάσουμε πιθανές υποσυμβολοσειρές αυτής της συμβολοσειράς με Εγώου ιου σύμβολο, τα συμβολίζουμε με μικρό(Εγώ, ι). Θα γράψουμε τα μήκη των μέγιστων παλίνδρομων για υποσυμβολοσειρές σε έναν τετράγωνο πίνακα L: L[i][j] είναι το μήκος του μέγιστου παλινδρόμου που μπορεί να ληφθεί από την υποσυμβολοσειρά μικρό(Εγώ, ι).

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

Ας μας δοθεί τώρα μια υποσυμβολοσειρά μικρό(Εγώ, ι). Εάν οι πρώτοι (S[i]) και οι τελευταίοι (S[j]) χαρακτήρες της υποσυμβολοσειράς δεν ταιριάζουν, τότε ένας από αυτούς πρέπει να διαγραφεί. Μετά μας μένει η υποσυμβολοσειρά μικρό(Εγώ, ι- 1) ή μικρό(Εγώ + 1, ι) - δηλαδή, ανάγουμε το πρόβλημα σε μια δευτερεύουσα εργασία: L[i][j] = max(L[i], L[j]). Εάν ο πρώτος και ο τελευταίος χαρακτήρες είναι ίσοι, τότε μπορούμε να αφήσουμε και τους δύο, αλλά πρέπει να γνωρίζουμε τη λύση στο πρόβλημα μικρό(Εγώ + 1, ι - 1):
L[i][j] = L + 2.

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

Αποδεικνύεται ότι θα γεμίσουμε τον πίνακα διαγώνια, ξεκινώντας από την κύρια διαγώνιο που οδηγεί από την επάνω αριστερή γωνία προς την κάτω δεξιά. Για υποσυμβολοσειρές μήκους 3, λαμβάνονται οι ακόλουθες τιμές: σε μια υποσυμβολοσειρά ABA, το πρώτο και το τελευταίο γράμμα είναι ίσα, άρα
L = L + 2. Στις υπόλοιπες υποσυμβολοσειρές, το πρώτο και το τελευταίο γράμμα είναι διαφορετικά.

BAC: L = max(L, L) = 1.
ACC: L = max(L, L) = 2.
CCB: L = max(L, L) = 2.
CBA: L = max(L, L) = 1.

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

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

Κατάλογος των πηγών που χρησιμοποιήθηκαν……………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………

1. Δυναμικός προγραμματισμός. ΒΑΣΙΚΕΣ ΕΝΝΟΙΕΣ.

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

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

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

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

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

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

Για διαδικασίες συνεχούς χρόνου, ο δυναμικός προγραμματισμός θεωρείται ως μια περιοριστική έκδοση ενός σχήματος διακριτής λύσης. Τα αποτελέσματα που λαμβάνονται σε αυτή την περίπτωση πρακτικά συμπίπτουν με εκείνα που λαμβάνονται με τις μέγιστες μεθόδους των L. S. Pontryagin ή Hamilton-Jacobi-Bellman.

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