Διατυπώστε το μοντέλο | Δοκιμή και σφάλμα | Λύστε το Μοντέλο
Χρησιμοποιήστε το διαλυτικό μέσα Προέχω να βρω το συντομότερη διαδρομή από τον κόμβο S στον κόμβο T σε μη κατευθυνόμενο δίκτυο. Τα σημεία σε ένα δίκτυο ονομάζονται κόμβοι (S, A, B, C, D, E και T). Οι γραμμές σε ένα δίκτυο ονομάζονται τόξα (SA, SB, SC, AC, κ.λπ.).
Διατυπώστε το Μοντέλο
Το μοντέλο που πρόκειται να λύσουμε φαίνεται ως εξής στο Excel.
1. Για να διατυπωθεί αυτό πρόβλημα συντομότερης διαδρομής, απαντήστε στις ακόλουθες τρεις ερωτήσεις.
ένα. Ποιες είναι οι αποφάσεις που πρέπει να ληφθούν; Για αυτό το πρόβλημα, χρειαζόμαστε το Excel για να μάθουμε εάν ένα τόξο βρίσκεται στη συντομότερη διαδρομή ή όχι (Ναι = 1, Όχι = 0). Για παράδειγμα, εάν το SB είναι μέρος της συντομότερης διαδρομής, το κελί F5 ισούται με 1. Αν όχι, το κελί F5 ισούται με 0.
σι. Ποιοι είναι οι περιορισμοί σε αυτές τις αποφάσεις; Η καθαρή ροή (Flow Out - Flow In) κάθε κόμβου πρέπει να είναι ίση με την προσφορά/ζήτηση. Ο κόμβος S πρέπει να έχει μόνο ένα εξερχόμενο τόξο (Net Flow = 1). Ο κόμβος T πρέπει να έχει μόνο ένα εισερχόμενο τόξο (Net Flow = -1). Όλοι οι άλλοι κόμβοι θα πρέπει να έχουν ένα εξερχόμενο τόξο και ένα εισερχόμενο τόξο εάν ο κόμβος βρίσκεται στη συντομότερη διαδρομή (Καθαρή ροή = 0) ή καμία ροή (Καθαρή ροή = 0).
ντο. Ποιο είναι το συνολικό μέτρο απόδοσης για αυτές τις αποφάσεις; Το συνολικό μέτρο απόδοσης είναι η συνολική απόσταση της συντομότερης διαδρομής, οπότε ο στόχος είναι να ελαχιστοποιηθεί αυτή η ποσότητα.
2. Για να καταστήσετε το μοντέλο πιο κατανοητό, δημιουργήστε τις ακόλουθες ονομαζόμενες περιοχές.
| Όνομα εύρους | Κύτταρα |
|---|---|
| Από | Β4: Β21 |
| Προς το | C4: C21 |
| Απόσταση | D4: D21 |
| Πηγαίνω | F4: F21 |
| NetFlow | I4: I10 |
| SupplyDemand | Κ4: Κ10 |
| Συνολική απόσταση | F23 |
3. Εισάγετε τις ακόλουθες λειτουργίες.
Επεξήγηση: Οι συναρτήσεις SUMIF υπολογίζουν την Καθαρή Ροή κάθε κόμβου. Για τον κόμβο S, η συνάρτηση SUMIF αθροίζει τις τιμές στη στήλη Μετάβαση με ένα "S" στη στήλη Από. Ως αποτέλεσμα, μόνο τα κελιά F4, F5 ή F6 μπορούν να είναι 1 (ένα εξερχόμενο τόξο). Για τον κόμβο Τ, η συνάρτηση SUMIF αθροίζει τις τιμές στη στήλη Μετάβαση με ένα "Τ" στη στήλη Προς. Ως αποτέλεσμα, μόνο το κελί F15, F18 ή F21 μπορεί να είναι 1 (ένα εισερχόμενο τόξο). Για όλους τους άλλους κόμβους, το Excel εμφανίζεται στη στήλη Από και Προς. Η Συνολική Απόσταση ισούται με το ολικό προϊόν της Απόστασης και της Μετάβασης.
Δοκιμή και σφάλμα
Με αυτήν τη διατύπωση, καθίσταται εύκολη η ανάλυση οποιασδήποτε δοκιμαστικής λύσης.
1. Για παράδειγμα, η διαδρομή SBET έχει συνολική απόσταση 16.
Δεν είναι απαραίτητο να χρησιμοποιείτε δοκιμή και σφάλμα. Θα περιγράψουμε στη συνέχεια πώς το Επίλυση Excel μπορεί να χρησιμοποιηθεί για να βρει γρήγορα τη βέλτιστη λύση.
Λύστε το Μοντέλο
Για να βρείτε τη βέλτιστη λύση, εκτελέστε τα ακόλουθα βήματα.
1. Στην καρτέλα Δεδομένα, στην ομάδα Ανάλυση, κάντε κλικ στην επιλογή Επίλυση.
Σημείωση: δεν μπορείτε να βρείτε το κουμπί Solver; Κάντε κλικ εδώ για να φορτώσετε το πρόσθετο Solver.
Εισαγάγετε τις παραμέτρους επίλυσης (διαβάστε παρακάτω). Το αποτέλεσμα πρέπει να είναι σύμφωνο με την παρακάτω εικόνα.
Έχετε την επιλογή να πληκτρολογήσετε τα ονόματα εύρους ή να κάνετε κλικ στα κελιά του υπολογιστικού φύλλου.
2. Πληκτρολογήστε TotalDistance για τον στόχο.
3. Κάντε κλικ στο ελάχ.
4. Πληκτρολογήστε Go for the Changing Variable Cells.
5. Κάντε κλικ στην επιλογή Προσθήκη για να εισαγάγετε τον ακόλουθο περιορισμό.
6. Επιλέξτε «Κάντε τις μη περιοριστικές μεταβλητές μη αρνητικές» και επιλέξτε «Simplex LP».
7. Τέλος, κάντε κλικ στην επιλογή Επίλυση.
Αποτέλεσμα:
Η βέλτιστη λύση:
Συμπέρασμα: Το SADCT είναι η συντομότερη διαδρομή με συνολική απόσταση 11.
