Διατυπώστε το μοντέλο | Δοκιμή και σφάλμα | Λύστε το Μοντέλο
Χρησιμοποιήστε το διαλυτικό μέσα Προέχω να βρω το μέγιστη ροή από τον κόμβο S στον κόμβο T σε ένα κατευθυνόμενο δίκτυο. Τα σημεία σε ένα δίκτυο ονομάζονται κόμβοι (S, A, B, C, D, E και T). Οι γραμμές σε ένα δίκτυο ονομάζονται τόξα (SA, SB, SC, AC, κ.λπ.).
Διατυπώστε το Μοντέλο
Το μοντέλο που πρόκειται να λύσουμε φαίνεται ως εξής στο Excel.
1. Για να διατυπωθεί αυτό πρόβλημα μέγιστης ροής, απαντήστε στις ακόλουθες τρεις ερωτήσεις.
ένα. Ποιες είναι οι αποφάσεις που πρέπει να ληφθούν; Για αυτό το πρόβλημα, χρειαζόμαστε το Excel για να βρούμε τη ροή σε κάθε τόξο. Για παράδειγμα, εάν η ροή στο SB είναι 2, το κελί D5 ισούται με 2.
σι. Ποιοι είναι οι περιορισμοί σε αυτές τις αποφάσεις; Η καθαρή ροή (Flow Out - Flow In) του κόμβου A, B, C, D και E πρέπει να είναι ίση με 0. Με άλλα λόγια, Flow Out = Flow In. Επίσης, κάθε τόξο έχει σταθερή χωρητικότητα. Η ροή σε κάθε τόξο πρέπει να είναι μικρότερη από αυτή τη χωρητικότητα.
ντο. Ποιο είναι το συνολικό μέτρο απόδοσης για αυτές τις αποφάσεις; Το συνολικό μέτρο απόδοσης είναι η μέγιστη ροή, οπότε ο στόχος είναι να μεγιστοποιηθεί αυτή η ποσότητα. Η μέγιστη ροή ισούται με τη ροή έξω από τον κόμβο S.
2. Για να καταστήσετε το μοντέλο πιο κατανοητό, δημιουργήστε τις ακόλουθες ονομαζόμενες περιοχές.
| Όνομα εύρους | Κύτταρα |
|---|---|
| Από | Β4: Β15 |
| Προς το | C4: C15 |
| Ροή | D4: D15 |
| Χωρητικότητα | F4: F15 |
| SupplyDemand | Κ5: Κ9 |
| MaximumFlow | Δ17 |
3. Εισάγετε τις ακόλουθες λειτουργίες.
Επεξήγηση: Οι συναρτήσεις SUMIF υπολογίζουν την Καθαρή Ροή κάθε κόμβου. Για τον κόμβο Α, η πρώτη συνάρτηση SUMIF αθροίζει τις τιμές στη στήλη Ροή με ένα "Α" στη στήλη Από (Έξοδος). Η δεύτερη συνάρτηση SUMIF αθροίζει τις τιμές στη στήλη Ροή με ένα "Α" στη στήλη Προς (Ροή σε). Η μέγιστη ροή ισούται με την τιμή στο κελί I4, η οποία είναι η ροή έξω από τον κόμβο S. Επειδή ο κόμβος A, B, C, D και E έχει καθαρή ροή 0, η ροή από τον κόμβο S θα ισούται με ροή In του κόμβου T.
Δοκιμή και σφάλμα
Με αυτήν τη διατύπωση, καθίσταται εύκολη η ανάλυση οποιασδήποτε δοκιμαστικής λύσης.
1. Για παράδειγμα, η διαδρομή SADT με ροή 2. Η διαδρομή SCT με ροή 4. Η διαδρομή SBET με ροή 2. Αυτές οι διαδρομές δίνουν συνολική ροή 8.
Δεν είναι απαραίτητο να χρησιμοποιείτε δοκιμή και σφάλμα. Θα περιγράψουμε στη συνέχεια πώς το Επίλυση Excel μπορεί να χρησιμοποιηθεί για να βρει γρήγορα τη βέλτιστη λύση.
Λύστε το Μοντέλο
Για να βρείτε τη βέλτιστη λύση, εκτελέστε τα ακόλουθα βήματα.
1. Στην καρτέλα Δεδομένα, στην ομάδα Ανάλυση, κάντε κλικ στην επιλογή Επίλυση.
Σημείωση: δεν μπορείτε να βρείτε το κουμπί Solver; Κάντε κλικ εδώ για να φορτώσετε το πρόσθετο Solver.
Εισαγάγετε τις παραμέτρους επίλυσης (διαβάστε παρακάτω). Το αποτέλεσμα πρέπει να είναι σύμφωνο με την παρακάτω εικόνα.
Έχετε την επιλογή να πληκτρολογήσετε τα ονόματα εύρους ή να κάνετε κλικ στα κελιά του υπολογιστικού φύλλου.
2. Πληκτρολογήστε MaximumFlow για τον στόχο.
3. Κάντε κλικ στο Max.
4. Εισαγάγετε τη ροή για την αλλαγή κυψελών μεταβλητής.
5. Κάντε κλικ στην επιλογή Προσθήκη για να εισαγάγετε τον ακόλουθο περιορισμό.
6. Κάντε κλικ στην επιλογή Προσθήκη για να εισαγάγετε τον ακόλουθο περιορισμό.
7. Επιλέξτε «Κάντε τις μη περιοριστικές μεταβλητές μη αρνητικές» και επιλέξτε «Simplex LP».
8. Τέλος, κάντε κλικ στην επιλογή Επίλυση.
Αποτέλεσμα:
Η βέλτιστη λύση:
Συμπέρασμα: η διαδρομή SADT με ροή 2. Η διαδρομή SCT με ροή 4. Η διαδρομή SBET με ροή 2. Η διαδρομή SCET με ροή 2. Η διαδρομή SACET με ροή 1. Η διαδρομή SACDT με ροή 1. Αυτές οι διαδρομές δίνουν μέγιστη ροή 12.
