Μέθοδος εύρεσης της μέγιστης ροής. Ένα παράδειγμα εύρεσης της μέγιστης ροής χρησιμοποιώντας τη μέθοδο Ford-Fulkerson
Χαμιλτονιανοί κύκλοι
Το γράφημα δίνεται με τη μορφή πίνακα, όπου τα κελιά καθορίζουν το κόστος μετακίνησης μεταξύ σημείων. Το σύμβολο ∞ τοποθετείται στην κύρια διαγώνιο για να εξαλείψει την ανούσια διαδρομή μέσα στον εαυτό της.
Επειδή Εάν ο προκύπτων πίνακας περιέχει μια στήλη χωρίς μηδενικά στοιχεία, τότε θα βρούμε το ελάχιστο στοιχείο σε αυτόν και θα το αφαιρέσουμε από όλα τα στοιχεία αυτής της στήλης.
| ΕΝΑ | σι | ντο | ρε | |
| ΕΝΑ | ∞ | |||
| σι | ∞ | |||
| ντο | ∞ | |||
| ρε | ∞ |
Ας αθροίσουμε όλα τα αφαιρούμενα στοιχεία και ας πάρουμε το κάτω όριο του κύκλου σε= 2+2+3+2+1=10
1.2. Ας αξιολογήσουμε όλα τα μηδενικά στοιχεία του πίνακα.
Είναι βολικό να παρουσιάζεται η εκτίμηση των μηδενικών σε έναν πίνακα.
| ΕΝΑ | σι | ντο | ρε | |
| ΕΝΑ | ||||
| σι | ||||
| ντο | ||||
| ρε |
θ=max γ=γ A C =2
1.3. Ας χωρίσουμε το σύνολο των μονοπατιών σε δύο υποσύνολα: Q A.C.– διαδρομές που περιέχουν τόξο (AC) και Q A.C.– διαδρομές που δεν περιέχουν τόξο (AC). Για το δεύτερο υποσύνολο το κάτω όριο θα είναι: σε / = σε + θ =10+2=12.
Για να υπολογίσουμε το όριο για το πρώτο υποσύνολο, μετακινούμαστε στον πίνακα κατά μία τάξη μεγέθους χαμηλότερα, διαγράφοντας τη σειρά A και τη στήλη C. Στον νέο πίνακα για την εξάλειψη της αντίστροφης διαδρομής (CA), βάζουμε το σύμβολο ∞ στο αντίστοιχο κελί.
Ας υπολογίσουμε το όριο του πίνακα που προκύπτει 2+0=2
και προσθέστε το στο κάτω περίγραμμα του βρόχου. Το ποσό αυτό σε // =10+2=12 και θα είναι το όριο για το πρώτο υποσύνολο.
1.4. Ας συγκρίνουμε τα όρια όλων των κορυφών που κρέμονται και ας επιλέξουμε την κορυφή με το μικρότερο όριο. Εάν υπάρχουν δύο από αυτές τις κορυφές, επιλέξτε οποιαδήποτε από αυτές. Αυτή είναι η κορυφή του Q A.C., του οποίου το κατώτερο όριο =12.
Ας επιλέξουμε το μέγιστο των εκτιμήσεων θ=max γ=γ BD =3
σε / =12+3=15.
1.6. Εκτελούμε όλα τα επόμενα σημεία παρόμοια με τα προηγούμενα.
Ας επιλέξουμε το μέγιστο των εκτιμήσεων θ=max γ=γ C B =∞
σε / =σε+ θ=∞
| ΕΝΑ | |
| ρε |
Όλες οι σειρές και οι στήλες αυτού του πίνακα περιέχουν μηδενικά. Επομένως, το όριο παραμένει ίσο με 12.
ΕΡΓΟ. Βρείτε την τιμή της μέγιστης ροής στο δίκτυο μεταφορών.
ΔΗΛΩΣΗ ΠΡΟΒΛΗΜΑΤΟΣ.
Εξετάστε το πρόβλημα μεταφοράς στο δίκτυο ( Ι, Δ, Γ) με δεδομένες χωρητικότητες τόξου c(i,j).
Ας επιλέξουμε δύο σταθερές κορυφές: μικρό- πηγή και t– αποστράγγιση. Ροή στο δίκτυο s→t ας ονομάσουμε την αριθμητική συνάρτηση φά, που ορίζεται σε ένα σύνολο τόξων και ικανοποιεί τις ακόλουθες γραμμικές εξισώσεις και ανισώσεις:
0≤ f(i,j) ≤c(i,j)για οποιαδήποτε (i,j)
Απαιτείται για τη μεγιστοποίηση μιας μεταβλητής x
Κόψτε το Λσε ένα δίκτυο που χωρίζει κορυφές s t
ονομάζεται το σύνολο των τόξων 
Με όποιον τρόπο s→t περιέχει τουλάχιστον ένα κομμένο τόξο.
ΚΡΙΤΗΡΙΑ ΒΕΛΤΙΣΤΟΤΗΤΑΣ: σε ένα πραγματικό δίκτυο, η τιμή μιας αυθαίρετης ροής δεν υπερβαίνει την απόδοση της κοπής και η τιμή της μέγιστης ροής είναι ίση με την ελάχιστη απόδοση της κοπής.
ΠΑΡΑΔΕΙΓΜΑ 3.12.
Μ 9 Κ
Μ 8 Κ
ΠΑΡΑΔΕΙΓΜΑ 3.13.
Μ 2 Κ
ΔΙΑΛΥΜΑ :
Η χωρητικότητα του εξερχόμενου τόξου (T,B) υπερβαίνει τη συνολική χωρητικότητα των τόξων που εισέρχονται στην αντίστοιχη κορυφή. Για να γίνει πραγματικό το δίκτυο αντικαθιστούμε c(T,B)=5.
Ας βρούμε και ας υπολογίσουμε την τιμή των χωρητικοτήτων διεκπεραίωσης όλων των περικοπών. (K,V) – (T,V) κοπή με ελάχιστη απόδοση =6. Επομένως, η μέγιστη ροή =6.
Ένα δίκτυο με πολλαπλές πηγές και καταβόθρες μπορεί να μειωθεί σε ένα δίκτυο με μία πηγή και ένα νεροχύτη.
ΠΑΡΑΔΕΙΓΜΑ. Έστω να υπάρχουν πολλές πηγές S και νεροχύτες Τ (πρόβλημα μεταφοράς). Ας επεκτείνουμε το δίκτυο προσθέτοντας δύο κόμβους s*, t* και όλα τα τόξα (s*, S) , (T,t*). Ας ορίσουμε τη συνάρτηση χωρητικότητας με ρύθμιση
ΤΡΟΠΟΣ ΤΟΠΟΘΕΤΗΣΗΣ ΣΗΜΑΤΩΝ.
1. Αρχική ροή f(i,j) = 0.
Ας αντιστοιχίσουμε ετικέτες στις κορυφές αυτού του δικτύου που θα έχουν τη μορφή (i+, ε)ή
(i - , ε).Ας σημειώσουμε την πηγή (-, ∞),
εκείνοι . ε(σ)= ∞.
2. Για οποιαδήποτε σημειωμένη κορυφή εγώ
επιλέξτε όλες τις κορυφές χωρίς ετικέτα ι
για το οποίο f(i,j)
Επαναλαμβάνουμε αυτή τη λειτουργία μέχρι να σημειωθεί η αποστράγγιση. Εάν η ροή παραμένει χωρίς ετικέτα, τότε η ροή που βρέθηκε είναι μέγιστη και το σύνολο τόξων που συνδέει τις σημειωμένες κορυφές με τις μη επισημασμένες σχηματίζουν μια ελάχιστη τομή.
3. Αφήστε το απόθεμα να φέρει ετικέτα (j+, ε(t)), Τότε f(j,t)αντικαταστήστε με f(j,t)+ε(t). Εάν το απόθεμα είναι μαρκαρισμένο (j-, ε(t)), Αυτό f(j,t)αντικαταστήστε με f(j,t)-ε(t). Ας πάμε στην κορυφή ι. Αν ιέχει σημάδι (i+, ε(j)), μετά αντικαθιστούμε f(i,j)επί f(i,j)+ε(t), και αν (i-, ε(j)), f(j,i)αντικαταστήστε με f(j,i)-ε(t). Ας πάμε στην κορυφή εγώ. Επαναλαμβάνουμε αυτή τη λειτουργία μέχρι να φτάσουμε στην πηγή μικρό.Η αλλαγή ροής σταματά, όλα τα σημάδια διαγράφονται και πηγαίνετε στο βήμα 2
ΠΑΡΑΔΕΙΓΜΑ 3.14.
Μ 4 Κ
| 1 βήμα | A → (-, ∞) M → (A+,8) P → (A+,3) K → (P+,3) T → (P+,3) B → (T+,3) | f(T,B)=3 f(P,T)=3 f(A,P)=3 f(P,K)=0 f(A,M)=0 f(M,P)=0 f(M,K)=0 f(M,T)=0 f(K,T)=0 f( Κ, Β)=0 |
| Βήμα 2 | A → (-, ∞) M → (A+,8) P → (M+,1) K → (M+,4) T → (M+,2) | f(K,B)=3 f(M,K)=3 f(A,M)=3 f(T,B)=3 f(P,T)=3 f(A,P)=3 f(P,K)=0 f(M,T)=0 f(M,P)=0 f(K,T)=0 |
| Βήμα 3 | A → (-, ∞) M → (A+,5) P → (M+,1) K → (M+,1) T → (M+,2) B → (T+,2) | f(T,B)=5 f(M,T)=2 f(A,M)=5 f(K,B)=3 f(M,K)=3 f(P,T)=3 f(A,P)=3 f(P,K)=0 f(M,P)=0 f(K,T)=0 |
| Βήμα 4 | A → (-, ∞) M → (A+,3) P → (M+,1) K → (M+,1) T → (P+,1) B → (T+,1) | f(A,M)=6 f(T,B)=6 f(P,T)=4 f(M,P)=1 f(M,T)=2 f(K,B)=3 f(M,K)=3 f(A,P)=3 f(P,K)=0 f(K,T)=0 |
| Βήμα 5 | A → (-, ∞) M → (A+,2) P → (M-,1) K → (M+,1) T → (K+,1) B → (T+,1) | f(A,M)=7 f(M,K)=4 f(K,T)=1 f(T,B)=7 f(P,T)=4 f(M,P)=1 f( Μ,Τ)=2 f(K,B)=3 f(A,P)=3 f(P,K)=0 |
| Βήμα 6 | A → (-, ∞) M → (A+,1) | Η ροή είναι βέλτιστη f=10 Ελάχιστη περικοπή: M→T-M→R-M→ΝΑ |
ΕΡΓΟ. Βρείτε την υψηλότερη ροή στο δίκτυο
ΑΛΓΟΡΙΘΜΟΣ
Ας συμβολίσουμε την κορυφή s= x 0 . Όλα τα άλλα είναι x i.
Στάδιο 1.
1. Επιλέξτε οποιοδήποτε μονοπάτι όλα τα τόξα δεν είναι κορεσμένα.
2. Αυξάνουμε την ποσότητα ροής κατά μήκος αυτής της διαδρομής κατά ένα μέχρι να μην υπάρχει κορεσμένο τόξο σε αυτό.
Συνεχίζουμε τη διαδικασία αύξησης της ροής μέχρι να κατασκευαστεί η πλήρης ροή, δηλ. οποιαδήποτε διαδρομή θα περιέχει τουλάχιστον ένα κορεσμένο τόξο.
Στάδιο 2.
2. Εάν το х i είναι ήδη σημειωμένη κορυφή, τότε σημειώνουμε (+i) όλες τις μη επισημασμένες κορυφές στις οποίες πηγαίνουν ακόρεστα τόξα από х i, και με τον δείκτη (–i) όλες οι μη επισημασμένες κορυφές από τις οποίες πηγαίνουν τόξα με μη μηδενική ροή σε х i.
3. Εάν ως αποτέλεσμα αυτής της διαδικασίας σημειωθεί μια κορυφή t, στη συνέχεια μεταξύ μικρόΚαι tυπάρχει ένα μονοπάτι του οποίου όλες οι κορυφές σημειώνονται με τους αριθμούς των προηγούμενων κορυφών. Αυξάνουμε τη ροή σε όλα τα τόξα αυτής της διαδρομής κατά ένα εάν, όταν μετακινούμαστε από μικρόΝα tο προσανατολισμός του τόξου συμπίπτει με την κατεύθυνση κίνησης και μειώνεται κατά ένα εάν το τόξο έχει τον αντίθετο προσανατολισμό. Ας προχωρήσουμε στο βήμα 1.
4. Όταν η κορυφή tείναι αδύνατο να επισημανθεί ότι η διαδικασία έχει τερματιστεί και η ροή που προκύπτει είναι η μεγαλύτερη ροή του δικτύου.
ΣΗΜΕΙΩΜΑ. Μπορείτε να πάτε στο στάδιο 2 χωρίς να ολοκληρώσετε το πρώτο στάδιο (βλ. παράδειγμα 3.16).
ΠΑΡΑΔΕΙΓΜΑ 3.15.
9
ΔΙΑΛΥΜΑ:
Βρέθηκε πλήρης ροή σε ένα δεδομένο δίκτυο μεταφορών. Τα κορεσμένα τόξα επισημαίνονται
Σε αυτό το δίκτυο, μπορείτε επίσης να επισημάνετε την τελική κορυφή και το αποτέλεσμα της σήμανσης θα είναι το ίδιο. Αλλάζοντας τη ροή, παίρνουμε ένα δίκτυο στο οποίο είναι αδύνατο να σημειωθεί η τελική κορυφή, επομένως η ροή σε αυτό είναι η μεγαλύτερη και ίση με 10.
ΠΑΡΑΔΕΙΓΜΑ 3.16.
8 2 1
Βρέθηκε ημιτελής ροή σε ένα δεδομένο δίκτυο μεταφορών
Ας σημειώσουμε το δίκτυο και ας αυξήσουμε τη ροή σε αυτό σύμφωνα με τον αλγόριθμο. παίρνουμε
Σε αυτό το δίκτυο, μπορείτε επίσης να επισημάνετε την τελική κορυφή και το αποτέλεσμα της σήμανσης θα είναι το ίδιο. Αλλάζοντας τη ροή, παίρνουμε ένα δίκτυο στο οποίο είναι αδύνατο να σημειωθεί η τελική κορυφή, επομένως η ροή σε αυτό είναι η μεγαλύτερη και ίση με 6.
Ενότητα IV. ΔΥΝΑΜΙΚΟΣ ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΣ.
Ο δυναμικός προγραμματισμός χρησιμοποιείται για την εύρεση βέλτιστων λύσεων πολλαπλών σταδίων. Για παράδειγμα, μακροπρόθεσμος σχεδιασμός για αντικατάσταση εξοπλισμού. δραστηριότητα του κλάδου επί σειρά ετών. Χρησιμοποιεί την αρχή της βελτιστοποίησης, σύμφωνα με την οποία κάθε νέα μερική λύση πρέπει να είναι βέλτιστη σε σχέση με την επιτευχθείσα κατάσταση.
Είναι καλύτερο να λύνεις ένα απλό πρόβλημα πολλές φορές παρά να λύνεις ένα δύσκολο μία φορά.
ΠΡΟΒΛΗΜΑ 1. Σχετικά με την πιο συμφέρουσα διαδρομή μεταξύ δύο σημείων.
Απαιτείται η κατασκευή μονοπατιού που συνδέει δύο σημεία Α και Β, εκ των οποίων το δεύτερο βρίσκεται στα βορειοανατολικά του πρώτου. Για απλότητα, ας πούμε ότι η χάραξη ενός μονοπατιού αποτελείται από μια σειρά βημάτων και σε κάθε βήμα μπορούμε να κινηθούμε είτε προς τα βόρεια είτε προς τα ανατολικά. Τότε κάθε διαδρομή είναι μια κλιμακωτή διακεκομμένη γραμμή, τα τμήματα της οποίας είναι παράλληλα με έναν από τους άξονες συντεταγμένων. Το κόστος κατασκευής καθενός από αυτά τα τμήματα είναι γνωστά.
ΠΑΡΑΔΕΙΓΜΑ 4.1. Βρείτε την ελάχιστη διαδρομή από το Α στο Β.
Το τελευταίο βήμα είναι να επιτύχουμε το T.V. Πριν από το τελευταίο βήμα, θα μπορούσαμε να βρισκόμαστε σε σημεία από όπου θα μπορούσαμε να φτάσουμε στο T.V. Υπάρχουν δύο τέτοια σημεία (το σύστημα θα μπορούσε να βρίσκεται σε μία από τις δύο καταστάσεις). Για καθένα από αυτά, υπάρχει μόνο μία επιλογή για να φτάσετε στο t.V: για ένα - μετακινηθείτε ανατολικά. για το άλλο - προς τα βόρεια. Ας γράψουμε κόστος 4 και 3 σε κάθε περίπτωση.
4
Τώρα ας βελτιστοποιήσουμε το προτελευταίο βήμα. Μετά το προηγούμενο βήμα, θα μπορούσαμε να καταλήξουμε σε ένα από τα τρία σημεία: C 1, C 2, C 3.
Για το σημείο C 1, υπάρχει μόνο ένα στοιχείο ελέγχου (ας το σημειώσουμε με ένα βέλος) - μετακινηθείτε ανατολικά και το κόστος θα είναι 2 (σε αυτό το βήμα) + 4 (στο επόμενο βήμα) = 6. Ομοίως, για το στοιχείο Γ 3 το κόστος θα είναι 2+3=5. Για το t.C 2 υπάρχουν δύο χειριστήρια: πηγαίνετε ανατολικά ή βόρεια. Στην πρώτη περίπτωση, το κόστος θα είναι 3+3=6 και στη δεύτερη περίπτωση – 1+4=5. Αυτό σημαίνει ότι ο υπό όρους βέλτιστος έλεγχος είναι να πάτε βόρεια. Ας το σημειώσουμε με ένα βελάκι και ας εισάγουμε τα αντίστοιχα κόστη.
| |
| |
| |
| ΕΡΓΑΣΙΑ 2. Σχετικά με τη φόρτωση του αυτοκινήτου (σχετικά με το σακίδιο). Υπάρχουν Ν στοιχεία. Γνωστό βάρος ένα i και αξία φ i κάθε στοιχείο. Απαιτείται για να γεμίσει ένα σακίδιο ικανό να κρατήσει ≤ βάρος R , ένα τέτοιο σύνολο αντικειμένων που θα είχαν τη μεγαλύτερη αξία.
Η διαδικασία φόρτωσης ενός σακιδίου μπορεί να χωριστεί σε N βήματα. Σε κάθε βήμα αποφασίζουμε την ερώτηση: να πάρουμε αυτό το αντικείμενο ή να μην το πάρουμε; Σε κάθε βήμα υπάρχουν μόνο 2 στοιχεία ελέγχου: control = 1, αν πάρουμε αυτό το στοιχείο. και 0 – αν δεν το πάρουμε. Η κατάσταση του συστήματος πριν από το επόμενο βήμα χαρακτηρίζεται από το βάρος S, το οποίο παραμένει στη διάθεσή μας μέχρι το τέλος της πλήρους φόρτωσης μετά την ολοκλήρωση των προηγούμενων βημάτων (κάποια είδη έχουν ήδη φορτωθεί), π.χ. ο ελεύθερος χώρος στο σακίδιο. ΑΛΓΟΡΙΘΜΟΣ. 1. Ας ξεκινήσουμε από το τελευταίο βήμα. Ας κάνουμε διάφορες υποθέσεις για τον ελεύθερο χώρο στο σακίδιο: S=0,1,…R. Ας βάλουμε το τελευταίο αντικείμενο στο σακίδιο αν έχει αρκετό αποθηκευτικό χώρο. 2. Σε κάθε προηγούμενο βήμα, για όλες τις πιθανές καταστάσεις S, εξετάζουμε 2 επιλογές: λήψη ή μη λήψη του αντικειμένου. Ας βρούμε το κέρδος σε κάθε περίπτωση ως το άθροισμα των κερδών στο τρέχον βήμα και στο επόμενο ήδη βελτιστοποιημένο βήμα. Θα εισάγουμε τα αποτελέσματα στον βοηθητικό πίνακα. 3. Στο πρώτο βήμα, θεωρούμε μόνο τη μόνη δυνατή κατάσταση S=R. 4. Ας βρούμε μια λύση «προχωρώντας προς τα πίσω», π.χ. Λαμβάνοντας βέλτιστο έλεγχο στο πρώτο βήμα, αλλάζουμε την κατάσταση του συστήματος στο δεύτερο βήμα: S=R– x 1 a 1και επιλέξτε το βέλτιστο στοιχείο ελέγχου x 2 για αυτήν την κατάσταση. Και τα λοιπά. ΠΑΡΑΔΕΙΓΜΑ 4.2. Αρχικά στοιχεία
Κύριο τραπέζι
Βοηθητικό τραπέζι.
Απάντηση: x 4 =0; x 3 =1; x 2 =0; x 1 =1; W=15 ΕΡΓΑΣΙΑ 3. Σχετικά με την κατανομή των πόρων. Υπάρχουν N επιχειρήσεις P 1, P 2,… P N, καθεμία από τις οποίες παράγει εισόδημα φ k (x) εάν της διατεθεί ένας πόρος στο ποσό των x. Απαιτείται η κατανομή του διαθέσιμου πόρου στην ποσότητα Α μεταξύ των αντικειμένων έτσι ώστε το συνολικό εισόδημα να είναι μέγιστο. Έστω x k το ποσό του πόρου που διατίθεται στην kth επιχείρηση. Στη συνέχεια το πρόβλημα που εξετάζεται ανάγεται σε ένα συμβατικό πρόβλημα μη γραμμικού προγραμματισμού.
Ας διατυπώσουμε το πρόβλημα ως πρόβλημα δυναμικού προγραμματισμού. Για το πρώτο βήμα θα κάνουμε την επένδυση κεφαλαίων στην επιχείρηση P 1, για το δεύτερο - στην P 2, κ.λπ. Το διαχειριζόμενο σύστημα σε αυτή την περίπτωση είναι τα κεφάλαια που διανέμονται. Η κατάσταση του συστήματος πριν από κάθε βήμα χαρακτηρίζεται από μία παράμετρο - το διαθέσιμο απόθεμα κεφαλαίων που δεν έχουν ακόμη επενδυθεί. Σε αυτό το πρόβλημα, οι βηματικοί έλεγχοι είναι τα κεφάλαια που διατίθενται στις επιχειρήσεις. Απαιτείται να βρεθεί ο βέλτιστος έλεγχος (x 1, x 2,...x N), στον οποίο το συνολικό εισόδημα είναι μέγιστο: | 1,1 0,5 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S=3 | 0,1 0,5 | 1,1 1,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S=4 | 0,1 0,5 | 2,1 1,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S=5 | 0,1 0,5 2,5 | 3,1 2,5 2,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| i=1 S=5 | 0,5 1,5 | 3,1 1,1 | 3,1 3,5 2,1 2,6 |
Απάντηση: x 1 =1; x 3 =0; x 3 =4; W=3,5
ΓΕΝΙΚΕΥΜΕΝΟΣ ΑΛΓΟΡΙΘΜΟΣ
1. Περιγράψτε το σύστημα. Δηλαδή, μάθετε ποιες παράμετροι χαρακτηρίζουν την κατάσταση του ελεγχόμενου συστήματος πριν από κάθε βήμα. Είναι σημαντικό να είστε σε θέση να ρυθμίσετε σωστά και «σεμνά» την εργασία, χωρίς να την επιβαρύνετε με περιττές λεπτομέρειες, απλοποιώντας όσο το δυνατόν περισσότερο την περιγραφή του ελεγχόμενου συστήματος.
2. Χωρίστε τη λειτουργία σε βήματα (στάδια). Όλοι οι εύλογοι περιορισμοί που επιβάλλονται στη διοίκηση πρέπει να ληφθούν υπόψη εδώ. Το βήμα πρέπει να είναι αρκετά μικρό, ώστε η διαδικασία βελτιστοποίησης ελέγχου βήματος να είναι αρκετά απλή. και το βήμα, ταυτόχρονα, δεν πρέπει να είναι πολύ μικρό ώστε να μην γίνονται περιττοί υπολογισμοί που περιπλέκουν τη διαδικασία εύρεσης της βέλτιστης λύσης, αλλά δεν οδηγούν σε σημαντική αλλαγή στο βέλτιστο της αντικειμενικής συνάρτησης.
3. Μάθετε το σύνολο των στοιχείων ελέγχου βημάτων x i για κάθε βήμα και τους περιορισμούς που επιβάλλονται σε αυτά.
4. Προσδιορίστε τι κέρδος φέρνει ο έλεγχος x i στο βήμα i, αν πριν από αυτό το σύστημα ήταν στην κατάσταση S, δηλ. καταγράψτε τις συναρτήσεις πληρωμής:
w i =f i (S, x i)
5. Προσδιορίστε πώς αλλάζει η κατάσταση του συστήματος υπό την επίδραση του ελέγχου x i στο πρώτο βήμα, δηλ. εγγραφή συναρτήσεων αλλαγής κατάστασης.
S / =φ i (S, x i)
6. Καταγράψτε την κύρια εξίσωση επαναλαμβανόμενου δυναμικού προγραμματισμού, εκφράζοντας το υπό όρους βέλτιστο κέρδος μέσω μιας ήδη γνωστής συνάρτησης
W i (S)= max(f i (S, x i)+W i+1 (φ i (S, x i)))
7. Πραγματοποιήστε βελτιστοποίηση υπό όρους του τελευταίου βήματος, κάνοντας διάφορες υποθέσεις για το πώς τελείωσε το προτελευταίο βήμα και για καθεμία από αυτές τις παραδοχές βρείτε τον υπό όρους (επιλεγμένο με βάση την προϋπόθεση ότι το βήμα τελείωσε με κάτι) βέλτιστο έλεγχο στο τελευταίο βήμα.
W m (S)= max(f m (S, x m))
8. Εκτελέστε βελτιστοποίηση υπό όρους, ξεκινώντας από το προτελευταίο βήμα και τελειώνοντας με το πρώτο βήμα (πίσω πίσω).
9. Πραγματοποιήστε άνευ όρων βελτιστοποίηση του ελέγχου, «διαβάζοντας» τις αντίστοιχες συστάσεις σε κάθε βήμα: πάρτε τον βέλτιστο έλεγχο που βρέθηκε στο πρώτο βήμα και αλλάξτε την κατάσταση του συστήματος, βρείτε τον βέλτιστο έλεγχο για την κατάσταση που βρέθηκε στο δεύτερο βήμα κ.λπ. . μέχρι το τελευταίο βήμα.
ΑΡΧΗ ΤΗΣ ΒΕΛΤΙΣΤΟΤΗΤΑΣ. Όποια και αν είναι η κατάσταση του συστήματος πριν από το επόμενο βήμα, είναι απαραίτητο να επιλέξετε τον έλεγχο σε αυτό το βήμα, έτσι ώστε το κέρδος σε αυτό το βήμα συν το βέλτιστο κέρδος σε όλα τα επόμενα βήματα να είναι μέγιστο.
Η αρχή του δυναμικού προγραμματισμού δεν συνεπάγεται ότι κάθε βήμα βελτιστοποιείται χωριστά, ανεξάρτητα από τα άλλα. Ποιο είναι το νόημα της επιλογής ενός ελέγχου του οποίου η αποτελεσματικότητα είναι μέγιστη σε ένα συγκεκριμένο βήμα, εάν αυτό το βήμα θα μας στερήσει την ευκαιρία να κερδίσουμε καλά στα επόμενα βήματα;
Στην πράξη, υπάρχουν περιπτώσεις που μια επέμβαση πρέπει να προγραμματιστεί για απεριόριστα μεγάλο χρονικό διάστημα. Το μοντέλο για μια τέτοια περίπτωση είναι μια ελεγχόμενη διαδικασία άπειρων βημάτων, όπου όλα τα βήματα είναι ίσα. Εδώ η συνάρτηση νίκης και η συνάρτηση αλλαγής κατάστασης δεν εξαρτώνται από τον αριθμό βήματος.
Ενότητα V. ΜΟΝΤΕΛΟΠΟΙΗΣΗ ΠΡΟΣΟΜΟΙΩΣΗΣ
Ακραία περίπτωση: εάν η μήτρα έχει το ίδιο χρώμα - η απάντηση είναι 0.Ας προσθέσουμε πλασματική πηγή και στραγγίζουμε. Από την πηγή μέχρι όλες τις λευκές κορυφές σχεδιάζουμε άκρες με βάρος Β (το κόστος για να τις ξαναβάψουμε μαύρες). Από τις μαύρες κορυφές μέχρι την αποστράγγιση τραβάμε άκρες με βάρος W (το κόστος για να το ξαναβάψουμε λευκό). Και ανάμεσα σε όλες τις γειτονικές κορυφές (είτε είναι ίδια είτε διαφορετικά χρώματα) τοποθετούμε μια άκρη με βάρος G (γκρίζα γραμμή). Η τιμή της μέγιστης ροής θα είναι η απάντηση στο πρόβλημα.
Πηγή: Παν-ουκρανική Σχολική Ολυμπιάδα στην Πληροφορική, 2007, Ημέρα 1
Διάλυμα
Το μόνο που χρειαζόμαστε είναι να χωρίσουμε κάθε κορυφή στα δύο και ανάμεσά τους να βάλουμε μια άκρη με βάρος ίσο με τον περιορισμό χωρητικότητας αυτής της κορυφήςΔιάλυμα
Στο κλασικό πρόβλημα ελάχιστης κοπής, οι άκρες πρέπει να αφαιρεθούν. Κανένα πρόβλημα! Ας χωρίσουμε τις κορυφές σε 2 και ας βάλουμε μια άκρη μεταξύ τους με βάρος 1. Τότε η απάντηση στο πρόβλημα είναι να βρούμε την ελάχιστη τομή στο γράφημα (που είναι η μέγιστη ροή).Πηγή: Χειμερινό σχολείο του Χάρκοβο για τον προγραμματισμό, 2009, Ημέρα 3
Αφού μετακινηθείτε μέσω του αυτόματου από το i στο j κατά μήκος της ακμής k, όλες οι μεταβάσεις από το i κατά μήκος της ακμής k, καθώς και όλες οι μεταβάσεις στο j κατά μήκος της ακμής k, διαγράφονται. Πρέπει να εκτυπώσετε τον αριθμό των διαδρομών από το Α έως το Β κατά μήκος ενός τέτοιου αυτόματου.
Διάλυμα
Το πρόβλημα καταλήγει στην εύρεση του μέγιστου αριθμού μονοπατιών χωρίς περισσότερες από μία ακμές του ίδιου χρώματος να προέρχονται από μία κορυφή. Ας περιορίσουμε το πρόβλημα στην εύρεση της μέγιστης ροής. Για κάθε κορυφή, θα δημιουργήσουμε k+1 κορυφές στο ανακατασκευασμένο δίκτυο. Η πρώτη κορυφή θα είναι η είσοδος, οι υπόλοιπες κορυφές θα αντιπροσωπεύουν τα χρώματα. Από την κορυφή εισόδου σχεδιάζουμε κατά μήκος μιας ακμής χωρητικότητας 1 σε κάθε μία από τις k κορυφές που αντιστοιχούν στο χρώμα. Από τις κορυφές που αντιστοιχούν στο χρώμα i σχεδιάζουμε όλες τις άκρες του χρώματος i στις εισόδους των άκρων των άκρων. Έχοντας βρει τη μέγιστη ροή σε ένα τέτοιο δίκτυο, λαμβάνουμε τον μέγιστο αριθμό διαδρομών που ικανοποιούν την απαιτούμενη ιδιότητα.Διάλυμα
Ας φτιάξουμε ένα δίκτυο. Ας δημιουργήσουμε μια κορυφή για κάθε τύπο νομίσματος. Αυτές οι κορυφές θα αντιστοιχούν στα νομίσματά σας. Πρέπει να συλλέξουμε όσο το δυνατόν περισσότερα μοναδικά νομίσματα, οπότε ας σχεδιάσουμε την άκρη χωρητικότητας 1 στο νεροχύτη από κάθε τέτοια κορυφή. Στις κορυφές που αντιστοιχούν στα νομίσματα που έχετε αρχικά, θα σχεδιάσουμε μια ακμή της οποίας η χωρητικότητα είναι ίση με τον αριθμό τέτοιων νομισμάτων που έχετε.Για κάθε μέλος του συλλόγου (εκτός από 1, δηλαδή εσάς) θα δημιουργήσουμε μία κορυφή. Αυτή η κορυφή μπορεί να δεχθεί το πολύ ένα νόμισμα που δεν έχει και να δώσει
το πολύ κ-1 νομίσματα, από τα οποία έχει κ (k > 1). Φυσικά, το μέλος του κλαμπ δίνει ένα νόμισμα σε αντάλλαγμα για ένα που έλαβε.
Έτσι, σε κάθε τέτοια κορυφή πρέπει να σχεδιάσετε ένα άκρο χωρητικότητας 1 από τις κορυφές που αντιστοιχούν σε νομίσματα που δεν έχει αυτό το μέλος του κλαμπ. Και από αυτές τις κορυφές πρέπει να σχεδιάσετε άκρες με χωρητικότητα k i - 1 έως την κορυφή i, που αντιστοιχούν σε νομίσματα από τα οποία ένα μέλος του κλαμπ έχει περισσότερα από ένα.
Το κατασκευασμένο δίκτυο αντικατοπτρίζει τις διαδικασίες ανταλλαγής στο κλαμπ. Η μέγιστη ροή σε ένα τέτοιο δίκτυο θα είναι ίση με τον μέγιστο αριθμό νομισμάτων που μπορείτε να συλλέξετε.
Πηγή: Χειμερινό σχολείο του Χάρκοβο για τον προγραμματισμό, 2009, Ημέρα 4
Δίνεται περιγραφή του συστήματος ψύξης. Είναι απαραίτητο να μάθετε πώς το υγρό μπορεί να περάσει μέσα από τους σωλήνες έτσι ώστε να πληρούνται όλες οι καθορισμένες προϋποθέσεις.
Διάλυμα
Αυτό είναι ένα πρόβλημα εύρεσης κυκλοφορίας σε ένα δίκτυο με δεδομένους χαμηλότερους περιορισμούς στα άκρα. Εάν μια ροή πρέπει να περάσει κατά μήκος της άκρης (u, v) στο τμήμα , τότε το ανακατασκευασμένο δίκτυο θα έχει τρεις άκρες (από, έως, βάρος): (u, v, r - l), (S, v, l) , (u, T, l). S, T - εισήχθη επιπλέον αποστράγγιση και πηγή, αντίστοιχα. Στην πραγματικότητα, περνάμε την απαιτούμενη ελάχιστη ροή κατά μήκος της άκρης και στη συνέχεια την εξισορροπούμε ώστε να έχουμε κυκλοφορία.Λύστε το πρόβλημα της εύρεσης της μέγιστης ροής σε ένα δίκτυο μεταφορών χρησιμοποιώντας τον αλγόριθμο Ford-Fulkerson και κατασκευάστε ένα τμήμα δικτύου S.
Αρχικά δεδομένα:
Δίνεται ένα δίκτυο S(X,U)
- πηγή του δικτύου· - αποχέτευση δικτύου, όπου ∈X; ∈Χ.
Οι τιμές χωρητικότητας τόξου καθορίζονται στην κατεύθυνση του προσανατολισμού του τόξου: από τον δείκτη i στον δείκτη j.
r = 39; r = 44; r = 33; r = 53; r = 10;
r = 18; r = 95; r = 16; r = 23; r = 61;
r = 81; r = 71; r = 25; r = 15; r = 20
1. Ορίστε μηδενική ροή στο δίκτυο (σε όλα τα τόξα η τιμή ροής είναι 0). Η μηδενική ροή είναι η αρχική επιτρεπόμενη ροή στο δίκτυο. Η τιμή ροής σε κάθε τόξο θα υποδεικνύεται εκτός της χωρητικότητας του τόξου.). Η τιμή ροής ίση με "0" δεν καθορίζεται.
2. Επιλέξτε (αυθαίρετα) μια διαδρομή στο δίκτυο που οδηγεί από την κορυφή x0 στην κορυφή x7:
Χ0-Χ1-Χ4-Χ6-Χ7
3. Βρείτε 
και αυξήστε τη ροή κατά αυτό το ποσό. Το άκρο X1-X4 επισημαίνεται ως θεωρείται. 
4. Επιλέξτε μια άλλη διαδρομή, για παράδειγμα: X0-X2-X5-X7, βρείτε 
και αυξήστε τη ροή κατά αυτό το ποσό. Το άκρο X0-X2 επισημαίνεται ως θεωρείται. 
5. Επιλέξτε μια άλλη διαδρομή, για παράδειγμα: X0-X3-X2-X5-X7, βρείτε και αυξήστε τη ροή κατά αυτό το ποσό. Το άκρο X3-X2 επισημαίνεται ως θεωρείται. 
6. Δεν υπάρχουν άλλα μονοπάτια από το X0 στο X7, ας συνοψίσουμε την αύξηση της ροής: 25+10+20=55.
Συμπέρασμα: η μέγιστη ροή είναι 55.
2) Κατασκευάστε ένα τμήμα του δικτύου S.
Η διαδικασία «σημείωσης κορυφής».
Αρχική κατάσταση: όλες οι κορυφές είναι χωρίς ετικέτα.
Στην κορυφή X0 εκχωρείται μια ετικέτα. Σε όλες τις κορυφές για τις οποίες το τόξο δεν είναι κορεσμένο εκχωρούνται σημάδια (κόκκινοι κύκλοι) 
Ορίζουμε τόξα ελάχιστης κοπής: αυτά είναι τόξα των οποίων οι αρχές βρίσκονται σε σημαδεμένες κορυφές και των οποίων τα άκρα βρίσκονται σε μη επισημασμένες κορυφές.
Αυτά είναι τα τόξα:
Έτσι, η ελάχιστη περικοπή αυτού του δικτύου 
Υπολογισμός της μέγιστης τιμής ροής
Κατά τον σχεδιασμό της ορθολογικής διανομής των προϊόντων στο δίκτυο διανομής, είναι απαραίτητο να συντονιστεί η χωρητικότητα του καναλιού με τις ανάγκες των πελατών και με την ικανότητα της μονάδας παραγωγής. Αυτή η κατηγορία προβλημάτων επιλύεται με την εύρεση της μέγιστης ροής.
Ας εξετάσουμε ένα δίκτυο διανομής (Εικ. 4.21), στο οποίο τα σημεία 0 (είσοδος, για παράδειγμα, αποθήκη τελικών προϊόντων ενός κατασκευαστή) και n (έξοδος, κέντρα διανομής, αποθήκες οργανισμών χονδρικής και λιανικής, καταναλωτής) και κάθε τόξο (τμήμα) σημεία σύνδεσης εγώ Και j, ο αριθμός dij > 0 συσχετίζεται, καλείται διακίνησης τόξα. Η τιμή απόδοσης χαρακτηρίζει τη μέγιστη επιτρεπόμενη ποσότητα ροής υλικού που μπορεί να περάσει κατά μήκος του αντίστοιχου τόξου ανά μονάδα χρόνου.
Ρύζι. 4.21.
Η ποσότητα των προϊόντων που διέρχεται κατά μήκος ενός τόξου από εγώ να ι , θα το ονομάσουμε ροή κατά μήκος του τόξου ( εγώ ,ι ) και συμβολίζεται με . Είναι προφανές ότι
Αν λάβουμε υπόψη ότι ολόκληρη η ροή υλικού που εισέρχεται στο ενδιάμεσο σημείο του δικτύου πρέπει να εξέλθει εντελώς από αυτό, παίρνουμε
Από τη φυσική απαίτηση της ισότητας των ροών στην είσοδο και στην έξοδο έχουμε
Θα ονομάσουμε την τιμή του Z την τιμή της ροής στο δίκτυο και θα θέσουμε το πρόβλημα της μεγιστοποίησης του Z υπό τις παραπάνω συνθήκες.
Η εύρεση της μέγιστης ροής καταλήγει στην εύρεση της απόδοσης της ελάχιστης περικοπής.
Ας εξετάσουμε έναν καθολικό αλγόριθμο αναζήτησης σε μορφή πίνακα.
Το αρχικό στάδιο του αλγορίθμου αποτελείται από την κατασκευή μιας μήτρας ρε 0, στις οποίες εισάγονται οι τιμές απόδοσης (για ένα μη προσανατολισμένο τόξο παίρνουμε τις συμμετρικές τιμές των στοιχείων του πίνακα).
Τα κύρια βήματα του αλγορίθμου είναι η εύρεση μιας συγκεκριμένης διαδρομής και η διόρθωση της ροής κατά μήκος αυτής της διαδρομής.
Όταν βρίσκουμε μια διαδρομή, χρησιμοποιούμε μια διαδικασία σήμανσης. Σημειώνουμε με το σύμβολο * τη μηδενική γραμμή και στήλη του πίνακα (είσοδος δικτύου). Στην 0η γραμμή που αναζητούμε, σημειώστε τις αντίστοιχες στήλες με δείκτες
και μετακινήστε τις ετικέτες στηλών στις σειρές. Στη συνέχεια, παίρνουμε την σημασμένη σειρά i, αναζητούμε μια στήλη χωρίς επισήμανση με , στην οποία αντιστοιχίζουμε ετικέτες ευρετηρίου
Μεταφέρουμε τις ετικέτες στηλών στις σειρές και συνεχίζουμε αυτή τη διαδικασία μέχρι να επισημανθεί η ν η στήλη.
Στη συνέχεια, χρησιμοποιώντας τους δείκτες, βρίσκουμε τη διαδρομή που οδήγησε στην η-η κορυφή και μειώνουμε τη χωρητικότητα των τόξων της διαδρομής (στοιχεία μήτρας) κατά V n και αυξήστε τα συμμετρικά στοιχεία κατά το ίδιο ποσό.
Αυτή η διαδικασία συνεχίζεται μέχρι τη σήμανση n -Τα μπλουζάκια δεν θα γίνουν ακατόρθωτα.
Η μέγιστη ροή μπορεί να βρεθεί αφαιρώντας από τον αρχικό πίνακα ρε 0, που προκύπτει μετά την παραπάνω διόρθωση του πίνακα χωρητικότητας:
Παράδειγμα 4.4
Η παραγωγή βρίσκεται στη Μόσχα. Για τη διανομή προϊόντων, η εταιρεία προσελκύει μεσάζοντες που συνεργάζονται με την εταιρεία μέσω κέντρων διανομής σε διάφορα επίπεδα. Στο ευρωπαϊκό τμήμα της Ρωσίας υπάρχει μια επιχείρηση χονδρικής 1, η οποία εξυπηρετείται από ένα κεντρικό κέντρο διανομής. Η επιχείρηση χονδρικής 2 δραστηριοποιείται στο κοντινό εξωτερικό (Ουκρανία, Λευκορωσία) και εξυπηρετείται από ένα περιφερειακό κέντρο διανομής. Η εταιρεία έχει τους δικούς της πελάτες στην τοπική αγορά (Μόσχα και περιοχή της Μόσχας) - λιανοπωλητές που λαμβάνουν προϊόντα από το κέντρο διανομής της πόλης. Τα περιφερειακά και τα κέντρα διανομής πόλεων ανανεώνονται από το κεντρικό κέντρο διανομής.
Ας επισημάνουμε ένα τμήμα του δικτύου διανομής:
- αποθήκη τελικών προϊόντων μιας μεταποιητικής επιχείρησης ·
- κεντρικό κέντρο διανομής?
- περιφερειακό κέντρο διανομής·
- κέντρο διανομής της πόλης ·
- δύο επιχειρήσεις χονδρικής?
- κατάστημα λιανικής που ανήκει στην εταιρεία·
- καταναλωτές.
Ρύζι. 4.22.
Ας ορίσουμε κάθε σύνδεσμο του δικτύου διανομής με έναν αριθμό και ας βάλουμε τη χωρητικότητα πάνω από τα τόξα. Η ικανότητα διακίνησης, ανάλογα με τον τύπο της ζεύξης, μπορεί να εκφραστεί ως προς τον όγκο της παραγωγικής ικανότητας, την προγραμματισμένη ανάγκη (ζήτηση) των καταναλωτών και τη χωρητικότητα της αγοράς.
Το γράφημα του δικτύου διανομής προϊόντων φαίνεται στο Σχ. 4.23. Ας φτιάξουμε μια μήτρα ρε 0, στην οποία εισάγουμε τις τιμές των χωρητικοτήτων διεκπεραίωσης των συνδέσεων του δικτύου διανομής (Εικ. 4.24).
Ρύζι. 4.23.
Ρύζι. 4.24.
Από τη μηδενική σειρά σημειώνουμε τις κορυφές (γραμμές-στήλες) 1, 2 και 3 με δείκτες μ = 0 και V, ίσο με 30,10 και 10.
Από τη σημειωμένη γραμμή 1, σημειώστε τις κορυφές 4 και 5 με δείκτες μ = 1 και V4 = min (30,15) = 15, V5 = min (30,10) = 10.
Από τη γραμμή 3 σημειώνουμε την κορυφή 6 και, τέλος, από τη γραμμή 4 – κορυφή 7 (Εικ. 4.25).
Ρύζι. 4.25.
Επιστρέφοντας κατά μήκος μ βρίσκουμε τη διαδρομή: στην κορυφή 7 από 4, στην κορυφή 4 από 1, στην κορυφή 1 από 0. ρυθμιστικά στοιχεία ρε 0 ανά τιμή ροής V7 = 15.
Το επόμενο βήμα δίνει μια διαδρομή με ροή 5 (Εικ. 4.26).
Ρύζι. 4.26.
Το επόμενο βήμα δίνει το αποτέλεσμα που φαίνεται στο Σχ. 4.27.
Ρύζι. 4.27.
Δεν είναι δυνατή η περαιτέρω σήμανση. Από εδώ λαμβάνουμε τη μήτρα μέγιστης ροής (Εικ. 4.28).
Ρύζι. 4.28.
Ως αποτέλεσμα της εφαρμογής του αλγορίθμου για την εύρεση της μέγιστης ροής στο δίκτυο, τα αποτελέσματα που παρουσιάζονται στο Σχ. 4.29. Τα ζεύγη αριθμών σε αγκύλες που εμφανίζονται στα τόξα του γραφήματος υποδεικνύουν τη μέγιστη απόδοση του τόξου και τον προτεινόμενο όγκο αγαθών που παρέχονται στο δίκτυο.
Αλγόριθμος για τον υπολογισμό της μέγιστης ροής στα δίκτυα
ΒΗΜΑ 1. Αρχικές εργασίες.Τρέχουσα αξία Ένα τΣτη μέγιστη ροή στο δίκτυο εκχωρείται η τιμή 0. ΒΗΜΑ 2. Επιλογή ανεξάρτητων διαδρομών στο δίκτυο και προσδιορισμός των ροών σε αυτές.Από ολόκληρο το σύνολο των πιθανών διαδρομών στο δίκτυο από την πηγή στο βυθό, επιλέγουμε ανεξάρτητες διαδρομές Μ 1 , … , Μ κ, που δεν έχει κοινές κορυφές εκτός από την αρχική (πηγή v και) και τελικό (στραγγ v με). Για κάθε επιλεγμένη διαδρομή Μ ι(1£ εγώ£ κ) καθορίστε τη μέγιστη ροή ΕΝΑ(Μ ι).ΒΗΜΑ 3. Διόρθωση της τρέχουσας τιμής της μέγιστης ροής στο δίκτυο.Προσθέτουμε αυτά που βρίσκονται σε ΒΗΜΑ 2τιμές μέγιστων ροών σε ανεξάρτητες διαδρομές Μ 1 , … , Μ κστην τρέχουσα συνολική μέγιστη ροή δικτύου: Ένα τ:= A t + A(Μ 1)+ Α(Μ 2)+…+ Α(Μ κ)ΒΗΜΑ 4. Διόρθωση δικτύου.Βρέθηκε στο ΒΗΜΑ 2μέγιστες ροές ΕΝΑ(Μ 1), … , ΕΝΑ(Μ κ) αφαιρείται από τη χωρητικότητα των αντίστοιχων τόξων δικτύου. Τα τόξα με μηδενική υπολειπόμενη χωρητικότητα αφαιρούνται. ΒΗΜΑ 5. Έλεγχος ολοκλήρωσης του αλγορίθμου.Εάν μετά τη διόρθωση δεν έχουν απομείνει διαδρομές από την πηγή στο δίκτυο v καισε απόθεμα v με, τότε η απαιτούμενη μέγιστη ροή στο δίκτυο είναι ίση με το ρεύμα που βρέθηκε ΕΝΑ:= A t, ο αλγόριθμος τερματίζεται επειδή έχει εξαντληθεί όλη η χωρητικότητα του δικτύου. Εάν στο προσαρμοσμένο δίκτυο υπάρχουν διαδρομές από την πηγή v καισε απόθεμα v με, μετά πηγαίνετε στο ΒΗΜΑ 2και συνέχιση της εκτέλεσης του αλγορίθμου . Παράδειγμα 2.Βρείτε τη μέγιστη ροή στο δίκτυο στο Σχ. 1.15 χρησιμοποιώντας αυτόν τον αλγόριθμο. Λύση.ΒΗΜΑ 1. Αρχικές εργασίες. Ένα τ: = 0.I επανάληψη. ΒΗΜΑ 2. Επιλογή ανεξάρτητων διαδρομών στο δίκτυο και προσδιορισμός των ροών σε αυτές.Ως Μ 1 διαδρομή ( v και =V 1 , V 2 , V 5 , v s =V 7), εξετάζεται στο παράδειγμα 1. Για αυτόν ΕΝΑ(Μ 1) = 10.
Είναι επίσης εύκολο να απομονώσεις ανεξάρτητους Μ 1 διαδρομή Μ 2 = (v και =V 1 , V 3 , V 6 , v s =V 7). Ας υπολογίσουμε τη μέγιστη απόδοση για αυτό και ας προσαρμόσουμε την απόδοση των τόξων: ΕΝΑ(Μ 2)=ελάχ{ρε 13 , δ 36 , δ 67 } =ελάχ{45, 40, 30} = 30. ρε 13 ¢ =δ 13 - 30 = 15, δ 36 ¢ =δ 36 - 30 = 10, δ 67 ¢ =δ 67 - 30 = 0.
ΒΗΜΑ 3. Διόρθωση της τρέχουσας τιμής της μέγιστης ροής στο δίκτυο. Ένα τ:= A t + A(Μ 1)+ Α(Μ 2) = 0 + 10+ 30 = 40.ΒΗΜΑ 4. Διόρθωση δικτύου.Βρέθηκε στο ΒΗΜΑ 2μέγιστες ροές ΕΝΑ(Μ 1), Α(Μ 2) σε διαδρομές Μ 1 , ΜΤο 2 αφαιρείται από τη χωρητικότητα των τόξων τους. Τα τόξα με μηδενική υπολειπόμενη χωρητικότητα αφαιρούνται. Το αποτέλεσμα δίνεται στο Σχ. 1.16 α. α) β) Εικ. 1.16. Το αποτέλεσμα της διόρθωσης δικτύου μετά από επαναλήψεις εγώΚαι ΒΗΜΑ 5. Έλεγχος ολοκλήρωσης του αλγορίθμου.Στο προσαρμοσμένο δίκτυο (Εικ. 1.16 α) υπάρχουν διαδρομές από την πηγή v καισε απόθεμα v με, Για παράδειγμα Μ 3 = (v και =V 1 , V 4 , V 2 , V 5 , v s =V 7). Συνέχιση της εκτέλεσης του αλγορίθμου .II επανάληψη. ΒΗΜΑ 2.Ως η μόνη ανεξάρτητη διαδρομή που ακολουθούμε Μ 3 = (v και =V 1 , V 4 , V 2 , V 5 , v s =V 7). Για αυτόν:
ΕΝΑ(Μ 3)=ελάχ{ρε 14 , δ 42 , δ 25 , δ 57 } =ελάχ{15, 10, 10, 15} = 10.
ρε 14¢ =δ 14 - 10 = 5, δ 42 ¢ =δ 42 - 10 = 0, δ 25 ¢ =δ 25 - 10 = 0, δ 57 ¢ =δ 57 - 10 = 5.
ΒΗΜΑ 3. A t:= A t + A(Μ 3) = 40 + 10= 50.ΒΗΜΑ 4. Διόρθωση δικτύου.Μέγιστη ροή ΕΝΑ(Μ 3) αφαιρέστε από τα τόξα της διαδρομής Μ 13. Το αποτέλεσμα δίνεται στο Σχ. 1.16 β.
ΒΗΜΑ 5.Δεν έχουν απομείνει διαδρομές από πηγή προς βύθιση στο προσαρμοσμένο δίκτυο. ΕΝΑ:= A t:= 50, ολοκλήρωση του αλγορίθμου. Απάντηση:η μέγιστη ροή στο δίκτυο στο Σχ. 1.15 είναι 50.Εάν προσδιορίζονται πολλές πηγές στο δίκτυο, ολοκληρώνεται με την εισαγωγή μιας νέας κοινής πηγής, η οποία συνδέεται με τις αρχικές πηγές μέσω τόξων με απεριόριστη χωρητικότητα. Στη συνέχεια, το πρόβλημα λύνεται χρησιμοποιώντας τον συνηθισμένο αλγόριθμο. Οι απαιτούμενες ροές μέσω των αρχικών πηγών θα είναι ροές κατά μήκος των τόξων που προστέθηκαν πρόσφατα που εισέρχονται σε αυτά από μια νέα κοινή πηγή. Κάντε το ίδιο εάν υπάρχουν πολλές αποχετεύσεις στο δίκτυο.
Σχεδιασμός δικτύου
Οποιαδήποτε εργασία σχεδιασμού ή κατασκευής ενός αρκετά σύνθετου αντικειμένου ( σχέδιο) μπορεί να αναλυθεί σε έναν αριθμό μικρότερων βημάτων συνιστωσών. Ο χρονισμός ολόκληρου του έργου εξαρτάται από τη σωστή επιλογή της σειράς αυτών των βημάτων.
Όλο το φάσμα των ενεργειών για την υλοποίηση του έργου παρουσιάζεται ως σύνολο εκδηλώσειςΚαι εργοστάσιο. Τα γεγονότα ονομάζονται μεμονωμένα στάδια ενός έργου. Η εργασία είναι η διαδικασία ολοκλήρωσής της. Ολόκληρο το σύνολο των εκδηλώσεων και των εργασιών που απαιτούνται για την ολοκλήρωση του έργου μπορεί να αναπαρασταθεί με τη μορφή ενός διπολικού δικτύου G =({v και, v z} , V, X), στο οποίο:
α) τα πάντα εκδηλώσειςσημειώνεται από ένα σύνολο κορυφών V,τονίζεται μεταξύ αυτών αρχικό συμβάν v και(έναρξη εργασιών) και τελικό γεγονός v z(ολοκλήρωση όλου του έργου), ορίζουν οι εσωτερικές κορυφές του δικτύου ενδιάμεσα γεγονότα- τα στάδια που πρέπει να ολοκληρωθούν κατά την υλοποίηση του έργου,
β) τα πάντα εργασίαυποδεικνύονται με τόξα που συνδέουν ζεύγη γεγονότων - κορυφών.
Η γραφική αναπαράσταση αυτού του δικτύου ονομάζεται διάγραμμα δικτύου.Για να υποδείξετε τη σειρά των ενεργειών, εισαγάγετε επίσης το διάγραμμα δικτύου πλασματικά έργα, τα οποία δεν σχετίζονται με την εκτέλεση ενεργειών. Τα αντίστοιχα έργα υποδεικνύονται με διακεκομμένα τόξα.
Ως παράδειγμα, εξετάστε την οργάνωση κάποιας παραγωγής. Το έργο απαιτεί τις ακόλουθες εργασίες:
I) έρευνα μάρκετινγκ, II) έρευνα πριν από το έργο για εξοπλισμό, III) οργάνωση δικτύου πωλήσεων, IV) διεξαγωγή διαφημιστικής εκστρατείας, V) ανάπτυξη τεχνικών προδιαγραφών για εξοπλισμό παραγωγής, VI) ανάπτυξη τεχνικής τεκμηρίωσης για χώρους παραγωγής και επικοινωνίες, VII) αγορά βασικού εξοπλισμού, VIII) σχεδιασμός και κατασκευή μη τυποποιημένου εξοπλισμού, IX) κατασκευή εγκαταστάσεων παραγωγής και εγκατάσταση επικοινωνιών, X) εγκατάσταση βασικού εξοπλισμού, XI) εγκατάσταση μη τυποποιημένου εξοπλισμού, XII) θέση σε λειτουργία.
Αυτά τα έργα θα τα υποδηλώσουμε στο διάγραμμα δικτύου με τόξα με αντίστοιχους αριθμούς.
Οι εκδηλώσεις σε αυτό το έργο θα είναι οι εξής:
1) έναρξη εργασιών (αρχική εκδήλωση), 2) ολοκλήρωση έρευνας μάρκετινγκ, 3) ολοκλήρωση έρευνας πριν από το έργο, 4) οργάνωση δικτύου πωλήσεων, 5) οργάνωση διαφημιστικής καμπάνιας, 6) προετοιμασία τεχνικών προδιαγραφών παραγωγής εξοπλισμός, 7) ολοκλήρωση της ανάπτυξης της τεχνικής τεκμηρίωσης για εγκαταστάσεις παραγωγής και επικοινωνιών, 8) ολοκλήρωση της αγοράς βασικού εξοπλισμού, 9) ολοκλήρωση του σχεδιασμού και κατασκευής μη τυποποιημένου εξοπλισμού, 10) ολοκλήρωση της κατασκευής εγκαταστάσεων παραγωγής και εγκατάσταση επικοινωνιών, 11) ολοκλήρωση εγκατάστασης εξοπλισμού και εργασίες θέσης σε λειτουργία,
12) ολοκλήρωση του έργου (τελική εκδήλωση).
Συσχετίζουμε κορυφές με αντίστοιχους αριθμούς σε γεγονότα. Το χρονοδιάγραμμα δικτύου για το έργο φαίνεται στο Σχ. 1.17:
Εικ.1.17. Χρονοδιάγραμμα υλοποίησης του δικτύου
