Ποια είναι η διαδικασία υπολογισμού στον πίνακα μεταφοράς. Γενικό σχέδιο για την επίλυση του προβλήματος των μεταφορών με τη χρήση της μεθόδου δυναμικού. Αναλυτικές οδηγίες για την επίλυση ενός προβλήματος μεταφοράς
Κάτω από την ονομασία πρόβλημα μεταφοράς, ένα ευρύ φάσμα προβλημάτων συνδυάζεται με ένα μόνο μαθηματικό μοντέλο. Αυτές οι εργασίες σχετίζονται με εργασίες γραμμικός προγραμματισμόςκαι μπορεί να λυθεί με τη γνωστή μέθοδο simplex. Ωστόσο, ένα τυπικό πρόβλημα μεταφοράς έχει μεγάλος αριθμόςμεταβλητές και η επίλυσή του με τη μέθοδο του simplex είναι περίπλοκη. Από την άλλη, η μήτρα του συστήματος των περιορισμών πρόβλημα μεταφοράςείναι πολύ μοναδικό, επομένως, για την επίλυσή του, αναπτύχθηκε ειδικές μεθόδους. Αυτές οι μέθοδοι, όπως μέθοδο simplex, μας επιτρέψτε να βρούμε την αρχική λύση υποστήριξης και στη συνέχεια, βελτιώνοντάς την, να λάβουμε μια ακολουθία λύσεων υποστήριξης που τελειώνει με τη βέλτιστη λύση.
Γενικά χαρακτηριστικά του προβλήματος των μεταφορών
Κατάσταση:
Το ομοιογενές φορτίο συγκεντρώνεται σε m προμηθευτές σε όγκους a 1, a 2, ... a m.
Αυτό το φορτίο πρέπει να παραδοθεί σε n καταναλωτές στους τόμους b 1, b 2 ... b n.
Γνωστός C ij, i=1,2,...m; j=1,2,...n — το κόστος μεταφοράς μονάδων φορτίου από κάθε i-ο προμηθευτή σε κάθε j-ο καταναλωτή.
Απαιτείται η κατάρτιση σχεδίου μεταφοράς στο οποίο τα αποθέματα όλων των προμηθευτών μεταφέρονται πλήρως, τα αιτήματα όλων των καταναλωτών ικανοποιούνται πλήρως και το συνολικό κόστος μεταφοράς όλων των εμπορευμάτων είναι ελάχιστο.
Τα αρχικά δεδομένα της εργασίας μεταφοράς γράφονται με τη μορφή πίνακα:
Τα αρχικά δεδομένα της εργασίας μπορούν να παρουσιαστούν ως:
- διάνυσμα A=(a 1 ,a 2 ,...,a m) αποθέματα προμηθευτών
- διάνυσμα B=(b 1 ,b 2 ,...,b n) αιτήματα καταναλωτών
- πίνακες κόστους:
Μαθηματικό μοντέλο του προβλήματος μεταφοράς
Οι μεταβλητές (άγνωστες) του προβλήματος μεταφοράς είναι x ij , i=1,2,...,m j=1,2,...,n - ο όγκος μεταφοράς από τον i-ο προμηθευτή σε κάθε j-ο καταναλωτής.
Αυτές οι μεταβλητές μπορούν να γραφτούν ως πίνακας μεταφοράς:
Δεδομένου ότι το προϊόν C ij *X ij καθορίζει το κόστος μεταφοράς αγαθών από τον i-ο προμηθευτή στον j-ο καταναλωτή, το συνολικό κόστος μεταφοράς όλων των αγαθών είναι ίσο με:
Σύμφωνα με τις συνθήκες του προβλήματος, απαιτείται η εξασφάλιση ενός ελάχιστου συνολικού κόστους.
Επομένως, η αντικειμενική συνάρτηση του προβλήματος έχει τη μορφή: 
Το σύστημα περιορισμών προβλήματος αποτελείται από δύο ομάδες εξισώσεων.
Η πρώτη ομάδα εξισώσεων m περιγράφει το γεγονός ότι τα αποθέματα όλων των m προμηθευτών εξάγονται πλήρως και έχει τη μορφή: 
Η δεύτερη ομάδα n εξισώσεων εκφράζει την απαίτηση να ικανοποιηθούν πλήρως οι απαιτήσεις και των n καταναλωτών και έχει τη μορφή:
Λαμβάνοντας υπόψη την προϋπόθεση της μη αρνητικότητας του κυκλοφοριακού όγκου μαθηματικό μοντέλοως εξής:
Στο εξεταζόμενο μοντέλο του προβλήματος των μεταφορών, θεωρείται ότι τα συνολικά αποθέματα των προμηθευτών είναι ίσα με τις συνολικές απαιτήσεις των καταναλωτών, δηλαδή:
Ένα τέτοιο πρόβλημα ονομάζεται πρόβλημα με τη σωστή ισορροπία και το μοντέλο προβλήματος κλειστό. Εάν αυτή η ισότητα δεν ικανοποιηθεί, τότε το πρόβλημα ονομάζεται πρόβλημα με λάθος ισορροπία, και το μοντέλο προβλήματος είναι Άνοιξε.
Παράδειγμα 34.1Μαθηματική διατύπωση του προβλήματος μεταφοράςείναι: βρείτε μεταβλητές εργασιών X=(x ij), i=1,2,...,m; j=1,2,...,n, ικανοποιώντας το σύστημα περιορισμών (αριθμός 2 στο μαθηματικό μοντέλο), (3), συνθήκες μη αρνητικότητας (4) και διασφαλίζοντας ένα ελάχιστο αντικειμενική λειτουργία (1)
Δημιουργήστε ένα μαθηματικό μοντέλο του προβλήματος μεταφοράς, τα αρχικά δεδομένα του οποίου δίνονται στον Πίνακα 34.2
Λύση:
1. Εισάγουμε μεταβλητές εργασιών (πίνακας μεταφοράς):
2. Καταγράφουμε τον πίνακα κόστους:
3. Η αντικειμενική συνάρτηση του προβλήματος είναι ίση με το άθροισμα των γινομένων όλων των αντίστοιχων στοιχείων των πινάκων C και X.
Αυτή η συνάρτηση, η οποία καθορίζει το συνολικό κόστος όλων των μεταφορών, πρέπει να φτάσει μια ελάχιστη τιμή.
4. Ας δημιουργήσουμε ένα σύστημα περιορισμών για το πρόβλημα.
Το άθροισμα όλων των αποστολών στην πρώτη σειρά του πίνακα X πρέπει να είναι ίσο με τα αποθέματα του πρώτου προμηθευτή και το άθροισμα των μεταφορών στη δεύτερη σειρά του πίνακα X πρέπει να είναι ίσο με τα αποθέματα του δεύτερου προμηθευτή: 
Αυτό σημαίνει ότι τα αποθέματα των προμηθευτών αφαιρούνται στο σύνολό τους.
Τα ποσά μεταφοράς σε κάθε στήλη του πίνακα X πρέπει να είναι ίσα με τα αιτήματα των αντίστοιχων καταναλωτών:
Αυτό σημαίνει ότι οι ανάγκες των καταναλωτών ικανοποιούνται πλήρως.
Είναι επίσης απαραίτητο να ληφθεί υπόψη ότι η μεταφορά δεν μπορεί να είναι αρνητική:
Απάντηση: Έτσι, το μαθηματικό μοντέλο του υπό εξέταση προβλήματος γράφεται ως εξής:
Βρείτε τις μεταβλητές του προβλήματος που παρέχουν ένα ελάχιστο της αντικειμενικής συνάρτησης (1) και ικανοποιούν το σύστημα των περιορισμών (2) και των συνθηκών μη αρνητικότητας (3). 
Ένα από τα πιο κοινά και δημοφιλή προβλήματα βελτιστοποίησηςστα logistics - πρόβλημα μεταφοράς. ΣΕ κλασική μορφήπεριλαμβάνει την εύρεση του βέλτιστου ( εκείνοι. σχετίζεται με ελάχιστο κόστος ) σχέδιο μεταφοράς φορτίου.
Για παράδειγμα, έχουμε μια αλυσίδα καταστημάτων λιανικής που απαιτούν μια ορισμένη ποσότηταεμπορεύματα. Υπάρχει επίσης μια σειρά από αποθήκες προμηθευτών όπου αποθηκεύονται τα απαιτούμενα εμπορεύματα. Επιπλέον, κάθε αποθήκη έχει διαφορετική ποσότητα αποθεμάτων αυτών των αγαθών. Επιπλέον, γνωρίζουμε τα τιμολόγια - τα έξοδα μεταφοράς 1 προϊόντος από κάθε αποθήκη σε κάθε κατάστημα.
Υπάρχει ανάγκη να αναπτυχθεί ένα σχέδιο μεταφοράς ώστε τα καταστήματα να λαμβάνουν την απαιτούμενη ποσότητα εμπορευμάτων με με το χαμηλότερο κόστοςγια μεταφορά. Σε τέτοιες ακριβώς περιπτώσεις (και σε πολλές άλλες) πρέπει να λυθεί το πρόβλημα των μεταφορών.
Θεωρητικό υλικό για το πρόβλημα των μεταφορών
(Πρόβλημα Monge-Kantorovich) - μαθηματικό πρόβλημαγραμμικός προγραμματισμός ειδικού τύπουσχετικά με την αναζήτηση βέλτιστη κατανομήομοιογενή αντικείμενα από την μπαταρία μέχρι τους δέκτες ελαχιστοποιώντας το κόστος μετακίνησης.
Για ευκολία κατανόησης, θεωρείται ως πρόβλημα στο βέλτιστο σχέδιο μεταφοράς εμπορευμάτων από σημεία αναχώρησης ( για παράδειγμα, αποθήκες) στα σημεία κατανάλωσης ( για παράδειγμα, καταστήματα), με ελάχιστο συνολικό κόστος μεταφοράς.
Έχει την εξής μορφή:
Οπου: Ζ- έξοδα μεταφοράς εμπορευμάτων.
Χ- όγκος φορτίου
ντο- κόστος (τιμολόγιο) μεταφοράς μιας μονάδας φορτίου.
ΕΝΑ- απόθεμα προμηθευτή·
σι- αίτημα καταναλωτή·
Μ- αριθμός προμηθευτών·
n- αριθμός καταναλωτών.
Γενικό σχέδιο για την επίλυση του προβλήματος των μεταφορών με τη χρήση της μεθόδου δυναμικού
Το πρόβλημα των μεταφορών μπορεί να λυθεί διάφορες μεθόδους, ξεκινώντας από τη μέθοδο simplex και απλή αναζήτηση, και τελειώνοντας με τη μέθοδο. Μία από τις πιο χρησιμοποιούμενες και κατάλληλες μεθόδους για τις περισσότερες περιπτώσεις είναι η επαναληπτική βελτίωση του σχεδίου μεταφοράς.
Η ουσία του είναι η εξής: βρίσκουμε ένα συγκεκριμένο σχέδιο αναφοράς και το ελέγχουμε βέλτιστη (Z → ελάχ). Εάν το σχέδιο είναι βέλτιστο, έχει βρεθεί μια λύση. Αν όχι, βελτιώστε το σχέδιο όσες φορές χρειάζεται μέχρι να βρεθεί βέλτιστο σχέδιο.
Παρακάτω είναι αλγόριθμος για την επίλυση ενός προβλήματος μεταφοράςστην πιο γενική μορφή:
- Κατασκευή τραπεζιού μεταφοράς.
- Έλεγχος της εργασίας για κλείσιμο.
- Συλλογή σχέδιο αναφοράς.
- Έλεγχος του σχεδίου υποστήριξης για εκφυλισμό.
- Υπολογισμός δυναμικών για το σχέδιο μεταφοράς.
- Έλεγχος του σχεδίου αναφοράς για βελτιστοποίηση.
- Ανακατανομή προμηθειών.
- Αν βέλτιστη λύσηβρέθηκε, μεταβείτε στο βήμα 9, εάν όχι, μεταβείτε στο βήμα 5.
- Υπολογισμός του συνολικού κόστους μεταφοράς εμπορευμάτων.
- Κατασκευή γραφήματος μεταφοράς.
Αναλυτικές οδηγίες για την επίλυση ενός προβλήματος μεταφοράς
1. Κατασκευή τραπεζιού μεταφοράς
Κατασκευάζουμε έναν πίνακα όπου υποδεικνύουμε τα αποθέματα υλικών που είναι διαθέσιμα στις αποθήκες των προμηθευτών ( Ολα συμπεριλαμβάνονται), και τις ανάγκες των εργοστασίων ( Bj) σε αυτά τα υλικά.
Στην κάτω δεξιά γωνία των κελιών του πίνακα εισάγουμε την τιμή των τιμολογίων για τη μεταφορά φορτίου ( Cij).
Ας υποδηλώσουμε το συνολικό απόθεμα φορτίου από όλους τους προμηθευτές με το σύμβολο ΕΝΑ, και συμβολίζεται η συνολική ζήτηση φορτίου για όλους τους καταναλωτές σι.
Το μεταφορικό πρόβλημα λέγεται κλειστό, Αν Α=Β. Αν A ≠ B, τότε καλείται το πρόβλημα μεταφοράς Άνοιξε. Οταν κλειστό πρόβλημαΌλες οι προμήθειες φορτίου θα αφαιρεθούν από τους προμηθευτές και όλα τα αιτήματα των καταναλωτών θα ικανοποιηθούν. Οταν ανοιχτή εργασίαΓια να το λύσετε αυτό, θα πρέπει να εισαγάγετε εικονικούς προμηθευτές ή καταναλωτές.
Ας ελέγξουμε την εργασία για κλείσιμο:
A = 10 + 20 + 30 = 60
Β = 15 + 20 + 25 = 60
A = B, επομένως αυτό το πρόβλημα μεταφοράς έχει κλείσει.
3. Κατάρτιση σχεδίου αναφοράς
Συνθέτει προκαταρκτικά ( υποστηρίζοντας) σχέδιο μεταφοράς. Δεν χρειάζεται να είναι βέλτιστο. Αυτό είναι απλώς ένα είδος «σχέδιο», «σκίτσο», βελτιώνοντας το οποίο σταδιακά θα φτάσουμε στο βέλτιστο σχέδιο.
Υπάρχουν διαφορετικά μεθόδους για την εύρεση ενός σχεδίου αναφοράς. Τα πιο συνηθισμένα είναι τα ακόλουθα:
α) Μέθοδος Βορειοδυτικής Γωνίας. προβολή
Η ουσία της μεθόδου είναι απλή - τα κελιά του πίνακα μεταφοράς γεμίζονται διαδοχικά στο μέγιστο πιθανούς όγκουςμεταφορά, προς την κατεύθυνση από πάνω προς τα κάτωΚαι απο αριστερά προς δεξιά. Δηλαδή, το επάνω αριστερό κελί συμπληρώνεται πρώτα ( «βορειοδυτικό» κελί), μετά το επόμενο στα δεξιά κ.λπ. Μετά πηγαίνετε στο νέα γραμμήκαι γεμίζουμε ξανά από αριστερά προς τα δεξιά. Και ούτω καθεξής μέχρι να γεμίσει τελείως το τραπέζι.
Μπορείτε να βρείτε μια λεπτομερή περιγραφή της μεθόδου και ένα παράδειγμα.
β) Μέθοδος ελάχιστου στοιχείου. προβολή
Η μέθοδος είναι ότι για να γεμίσετε τα κελιά του πίνακα μεταφοράς, επιλέξτε ένα κελί με ελάχιστοςτιμολογιακή αξία. Στη συνέχεια επιλέγεται το επόμενο κελί με τη χαμηλότερη χρέωση και ούτω καθεξής μέχρι να γεμίσει ο πίνακας ( όλα τα αποθέματα και οι ανάγκες θα μηδενιστούν).
γ) Προσέγγιση Vogel. προβολή
Η βάση της μεθόδου είναι η εύρεση διαφορές(modulo) μεταξύ ενός ζεύγους ελάχιστων τιμολογίων σε κάθε γραμμή και στήλη. Στη συνέχεια, στη γραμμή ή στη στήλη με μέγιστοςη διαφορά γεμίζει το κελί με το μικρότεροδασμολόγιο. Στη συνέχεια, όλες αυτές οι ενέργειες επαναλαμβάνονται ξανά, μόνο που σε αυτήν την περίπτωση τα γεμισμένα κελιά δεν λαμβάνονται πλέον υπόψη.
Μπορείτε να βρείτε μια λεπτομερή περιγραφή της προσέγγισης Vogel και ένα παράδειγμα
δ) Μέθοδος διπλής προτίμησης. προβολή
Η ουσία της μεθόδου είναι ότι τα κελιά με το χαμηλότερο τιμολόγιο επισημαίνονται σε σειρές και στη συνέχεια σε στήλες. Στη συνέχεια τα κελιά συμπληρώνονται με την ακόλουθη σειρά: πρώτα τα κελιά με δύο σημάδια, μετά με ένα, τέλος χωρίς σημάδια.
Μπορείτε να βρείτε μια λεπτομερή περιγραφή της μεθόδου και ένα παράδειγμα
4. Έλεγχος του σχεδίου υποστήριξης για εκφυλισμό
Τα κελιά του πίνακα στα οποία καταγράφονται μεταφορές εκτός του μηδενός ονομάζονται βασικός, και τα υπόλοιπα (άδειο) - Ελεύθερος.
Το σχέδιο ονομάζεται εκφυλισμένος, αν ο αριθμός των βασικών κελιών σε αυτό είναι μικρότερος από m + n -1. Εάν κατά την επίλυση του προβλήματος επιτευχθεί ένα εκφυλισμένο σχέδιο, τότε πρέπει να αναπληρωθεί εισάγοντας μηδενική μεταφορά στον αριθμό των κυττάρων που λείπουν και έτσι μετατρέποντας αυτά τα κύτταρα σε βασικά ( το συνολικό υπόλοιπο και το συνολικό κόστος μεταφοράς του σχεδίου δεν θα αλλάξει). Ωστόσο, είναι αδύνατο να συμπληρώσετε το σχέδιο επιλέγοντας κελιά τυχαία. Το σχέδιο πρέπει να είναι άκυκλο!
Ένα σχέδιο ονομάζεται ακυκλικό εάν τα βασικά του κύτταρα δεν περιέχουν κύκλους. Κύκλοςστον πίνακα μεταφοράς υπάρχουν πολλά κελιά που συνδέονται με μια κλειστή πολυγραμμή έτσι ώστε δύο γειτονικές κορυφές της πολύγραμμης να βρίσκονται είτε στην ίδια γραμμή είτε στην ίδια στήλη. Παρακάτω είναι παράδειγμα βρόχου:
Μια διακεκομμένη γραμμή μπορεί να έχει σημεία αυτοτομής, αλλά όχι στα κελιά του κύκλου.
Αριθμός βασικών κελιών = 5
m + n – 1 = 3 + 3 – 1 = 5
Κατά συνέπεια, το αρχικό σχέδιο μεταφοράς δεν είναι εκφυλισμένο.
5. Υπολογισμός δυναμικών για το σχέδιο μεταφοράς
Για να αναλύσετε τα ληφθέντα σχέδια και την επακόλουθη βελτίωσή τους, είναι βολικό να εισέλθετε πρόσθετα χαρακτηριστικάσημεία προέλευσης και προορισμού, που ονομάζονται δυναμικά.
Αυτή η μέθοδος βελτίωσης των σχεδίων μεταφοράς ονομάζεται πιθανή μέθοδος . Υπάρχουν και άλλες μέθοδοι για την επαναληπτική βελτίωση του σχεδίου μεταφοράς, αλλά δεν θα τις εξετάσουμε εδώ.
Έτσι, ας συγκρίνουμε κάθε προμηθευτή Ai και κάθε καταναλωτή Bj με τις τιμές UiΚαι Vjκατά συνέπεια, ώστε για όλα τα βασικά κελιά του σχεδίου να ικανοποιείται η ακόλουθη σχέση:
Ui + Vj = Cij
Προσθήκη στον πίνακα μεταφοράς επιπλέον γραμμήκαι μια στήλη για το Ui και το Vj.
Ας υποθέσουμε ότι U1 = 0.
Τότε μπορούμε να βρούμε V3 = C13 – U1 = 1 – 0 = 1.
Γνωρίζοντας το V3, μπορούμε τώρα να βρούμε το U3:
Κατ' αναλογία, υπολογίζουμε όλα τα υπόλοιπα δυναμικά:
6. Έλεγχος του σχεδίου για βέλτιστη χρήση με τη μέθοδο του δυναμικού
Για κάθε ελεύθερο κελί του σχεδίου, υπολογίζουμε τις διαφορές
ΔCij = Cij – (Ui + Vj)
και γράψτε τις τιμές που προκύπτουν στην κάτω αριστερή γωνία των αντίστοιχων κελιών.
Το σχέδιο είναι άριστος, εάν όλες οι διαφορές ΔCij ≥ 0.
ΣΕ σε αυτήν την περίπτωσησχέδιο - υποβέλτιστη(ΔC22< 0), и его следует улучшить путем перераспределения поставок.
7. Αναδιανομή προμηθειών
Ας βρούμε το κελί με το μεγαλύτερο απόλυτη τιμήαρνητική διαφορά ΔCij και κατασκευάστε έναν κύκλο στον οποίο, εκτός από αυτό το κελί, όλα τα άλλα είναι βασικά. Ένας τέτοιος κύκλος υπάρχει πάντα και είναι μοναδικό.
Ας σημειώσουμε το κελί με αρνητική διαφορά ΔCij με πρόσημο «+», το επόμενο με σύμβολο «-» και ούτω καθεξής, ένα προς ένα.
Στη συνέχεια βρίσκουμε την ελάχιστη τιμή του φορτίου στα κελιά του κύκλου με το σύμβολο «-» (εδώ είναι 5) και την εισάγουμε στο ελεύθερο κελί με το σύμβολο «+». Στη συνέχεια περνάμε διαδοχικά από όλα τα κελιά του κύκλου, αφαιρώντας και προσθέτοντας εναλλάξ την ελάχιστη τιμή σε αυτά (σύμφωνα με τα σημάδια με τα οποία επισημαίνονται αυτά τα κελιά: όπου το μείον αφαιρεί, όπου το συν προσθέτει).
Παίρνουμε νέο σχέδιο αναφοράςΜεταφορά:
Επειδή υπάρχουν περισσότερα βασικά κελιά από m + n – 1, κάνουμε το βασικό κελί με μηδενική τιμή ελεύθερο:
Υπολογίζουμε πάλι τις πιθανές τιμές και τη διαφορά ΔCij:
Αυτή τη φορά όλες οι διαφορές ΔCij των κυττάρων είναι θετικές, επομένως, βρέθηκε η βέλτιστη λύση.
8. Εάν βρεθεί η βέλτιστη λύση, μεταβείτε στο βήμα 9, εάν όχι, μεταβείτε στο βήμα 5.
Βρήκαμε τη βέλτιστη λύση, οπότε προχωρήστε στο σημείο 9.
9. Υπολογισμός του συνολικού κόστους μεταφοράς εμπορευμάτων
Ας υπολογίσουμε συνολικό κόστος αποστολήςφορτίο ( Ζ), που αντιστοιχεί στο βέλτιστο σχέδιο που βρήκαμε, σύμφωνα με τον τύπο:
Zmin = 10 ∙ 1 + 15 ∙ 3 + 5 ∙ 2 + 15 ∙ 1 + 15 ∙ 2 = 110 den. μονάδες
Το συνολικό κόστος παράδοσης όλων των προϊόντων, για μια βέλτιστη λύση, είναι 110 φωλιά. μονάδες
10. Κατασκευή γραφήματος μεταφοράς
Έχοντας βρει το βέλτιστο σχέδιο μεταφοράς, θα κατασκευάσουμε. Οι κορυφές του γραφήματος θα είναι «αποθήκες» και «καταστήματα». Στις κορυφές υποδεικνύουμε τους αντίστοιχους όγκους αποθεμάτων και αναγκών. Τα τόξα που συνδέουν τις κορυφές του γραφήματος θα αντιστοιχούν σε μη μηδενικές μεταφορές. Θα υπογράψουμε κάθε τέτοιο τόξο, υποδεικνύοντας τον όγκο του μεταφερόμενου φορτίου.
Το αποτέλεσμα θα είναι ένα γράφημα παρόμοιο με αυτό που φαίνεται παρακάτω:
Αυτό ήταν, λύθηκε το μεταφορικό πρόβλημα. Συγχαρητήρια!
Πρακτική εφαρμογή του μεταφορικού προβλήματος
Το πρόβλημα μεταφοράς χρησιμοποιείται σε πολλές περιπτώσεις. Αυτή είναι η βελτιστοποίηση της προμήθειας πρώτων υλών και προμηθειών μεταποιητικές επιχειρήσεις. Αυτή είναι η βελτιστοποίηση της παράδοσης των αγαθών από τις αποθήκες σε Καταστήματα λιανικής. Αυτό είναι βελτιστοποίηση μεταφορά επιβατών, και πολλά, πολλά άλλα.
Galyautdinov R.R.
© Η αντιγραφή υλικού επιτρέπεται μόνο εάν υπάρχει απευθείας υπερσύνδεσμος προς
Οδηγίες. Για να βρεθεί λύση στο πρόβλημα των μεταφορών στο online λειτουργίαεπιλέξτε τη διάσταση του πίνακα τιμολογίων (αριθμός προμηθευτών και αριθμός καταστημάτων).Τα ακόλουθα χρησιμοποιούνται επίσης με αυτήν την αριθμομηχανή:
Γραφική μέθοδος επίλυσης ZLP
Μέθοδος Simplex για την επίλυση ZLP
Επίλυση ενός παιχνιδιού μήτρας
Χρησιμοποιώντας την υπηρεσία online, μπορείτε να προσδιορίσετε την τιμή ενός παιχνιδιού matrix (κάτω και ανώτερα όρια), να ελέγξετε τη διαθεσιμότητα σημείο σέλας, βρείτε μια λύση σε μια μικτή στρατηγική χρησιμοποιώντας τις ακόλουθες μεθόδους: minimax, μέθοδος simplex, γραφική (γεωμετρική) μέθοδος, μέθοδος Brown.
Ακρότατο συνάρτησης δύο μεταβλητών
Προβλήματα δυναμικού προγραμματισμού
Το πρώτο στάδιο επίλυσης του μεταφορικού προβλήματοςείναι ο προσδιορισμός του τύπου του (ανοιχτό ή κλειστό, ή αλλιώς ισορροπημένο ή μη ισορροπημένο). Κατά προσέγγιση μέθοδοι ( μεθόδους για την εύρεση ενός σχεδίου αναφοράς) επιτρέπω δεύτερο στάδιο λύσηςσε ένα μικρό αριθμό βημάτων να επιτευχθεί μια αποδεκτή, αλλά όχι πάντα βέλτιστη, λύση στο πρόβλημα. Αυτή η ομάδα μεθόδων περιλαμβάνει τις ακόλουθες μεθόδους:
- διαγραφή (μέθοδος διπλής προτίμησης).
- βορειοδυτική γωνία?
- ελάχιστο στοιχείο?
- Προσεγγίσεις Vogel.
Λύση αναφοράς στο πρόβλημα των μεταφορών
Η λύση αναφοράς στο πρόβλημα των μεταφορώνείναι κάθε εφικτή λύση για την οποία τα διανύσματα συνθήκης που αντιστοιχούν στις θετικές συντεταγμένες είναι γραμμικά ανεξάρτητα. Για έλεγχο γραμμική ανεξαρτησίαδιανύσματα συνθηκών που αντιστοιχούν στις συντεταγμένες μιας αποδεκτής λύσης, χρησιμοποιούνται κύκλοι.ΚύκλοςΜια ακολουθία κελιών σε έναν πίνακα εργασιών μεταφοράς ονομάζεται στην οποία δύο και μόνο γειτονικά κελιά βρίσκονται στην ίδια γραμμή ή στήλη και το πρώτο και το τελευταίο βρίσκονται επίσης στην ίδια γραμμή ή στήλη. Ένα σύστημα διανυσμάτων συνθηκών προβλήματος μεταφοράς είναι γραμμικά ανεξάρτητο εάν και μόνο εάν δεν μπορεί να σχηματιστεί κύκλος από τα αντίστοιχα κελιά του πίνακα. Επομένως, μια αποδεκτή λύση στο πρόβλημα των μεταφορών, i=1,2,...,m; j=1,2,...,n είναι μια αναφορά μόνο εάν δεν μπορεί να σχηματιστεί κύκλος από τα κελιά του πίνακα που καταλαμβάνει.
Κατά προσέγγιση μέθοδοι επίλυσης του προβλήματος μεταφοράς.
Μέθοδος διασταύρωσης (μέθοδος διπλής προτίμησης). Εάν υπάρχει ένα κατειλημμένο κελί σε μια γραμμή ή στήλη ενός πίνακα, τότε δεν μπορεί να συμπεριληφθεί σε κανέναν κύκλο, αφού ένας κύκλος έχει δύο και μόνο δύο κελιά σε κάθε στήλη. Επομένως, μπορείτε να διαγράψετε όλες τις σειρές του πίνακα που περιέχουν ένα κατειλημμένο κελί, στη συνέχεια να διαγράψετε όλες τις στήλες που περιέχουν ένα κατειλημμένο κελί και, στη συνέχεια, να επιστρέψετε στις γραμμές και να συνεχίσετε να διαγράφετε γραμμές και στήλες. Εάν, ως αποτέλεσμα της διαγραφής, διαγράφονται όλες οι γραμμές και οι στήλες, αυτό σημαίνει ότι από τα κατειλημμένα κελιά του πίνακα είναι αδύνατο να επιλέξετε ένα τμήμα που σχηματίζει έναν κύκλο και το σύστημα των αντίστοιχων διανυσμάτων συνθηκών είναι γραμμικά ανεξάρτητο, και η λύση είναι μια αναφορά. Εάν, μετά τη διαγραφή, παραμείνουν μερικά κελιά, τότε αυτά τα κελιά σχηματίζουν έναν κύκλο, το σύστημα των αντίστοιχων φορέων συνθηκών εξαρτάται γραμμικά και η λύση δεν είναι αναφορά.
Μέθοδος Βορειοδυτικής Γωνίαςαποτελείται από τη διαδοχική επανάληψη μεταξύ των γραμμών και των στηλών του πίνακα μεταφοράς, ξεκινώντας από την αριστερή στήλη και η πάνω σειρά, και γράψτε τις μέγιστες δυνατές αποστολές στα κατάλληλα κελιά του πίνακα, ώστε να μην ξεπεραστούν οι δυνατότητες του προμηθευτή ή οι ανάγκες του καταναλωτή που αναφέρονται στην εργασία. Σε αυτή τη μέθοδο, δεν δίνεται προσοχή στις τιμές παράδοσης, καθώς προϋποτίθεται περαιτέρω βελτιστοποίηση των αποστολών.
Μέθοδος Minimal Element. Με απλότητα αυτή τη μέθοδοακόμα πιο αποτελεσματική από, για παράδειγμα, τη μέθοδο Northwest Angle. Επιπλέον, η μέθοδος ελάχιστου στοιχείου είναι σαφής και λογική. Η ουσία του είναι ότι στον πίνακα μεταφοράς συμπληρώνονται πρώτα τα κελιά με τα χαμηλότερα τιμολόγια και μετά τα κελιά με τα υψηλά τιμολόγια. Δηλαδή επιλέγουμε μεταφορά με το ελάχιστο κόστος παράδοσης φορτίου. Αυτή είναι μια προφανής και λογική κίνηση. Είναι αλήθεια ότι δεν οδηγεί πάντα στο βέλτιστο σχέδιο.
Μέθοδος προσέγγισης Vogel. Με τη μέθοδο της προσέγγισης Vogel, σε κάθε επανάληψη, βρίσκεται η διαφορά μεταξύ των δύο ελάχιστων τιμολογίων που αναγράφονται σε αυτές για όλες τις στήλες και όλες τις γραμμές. Αυτές οι διαφορές καταγράφονται σε μια ειδικά καθορισμένη γραμμή και στήλη στον πίνακα συνθηκών προβλημάτων. Μεταξύ των υποδεικνυόμενων διαφορών, επιλέγεται το ελάχιστο. Στη γραμμή (ή στη στήλη) στην οποία αντιστοιχεί αυτή η διαφορά καθορίζεται το ελάχιστο τιμολόγιο. Το κελί στο οποίο είναι γραμμένο συμπληρώνεται σε αυτήν την επανάληψη.
Παράδειγμα Νο. 1. Πίνακας δασμών (εδώ ο αριθμός των προμηθευτών είναι 4, ο αριθμός των καταστημάτων είναι 6):
| 1 | 2 | 3 | 4 | 5 | 6 | Αποθεματικά | |
| 1 | 3 | 20 | 8 | 13 | 4 | 100 | 80 |
| 2 | 4 | 4 | 18 | 14 | 3 | 0 | 60 |
| 3 | 10 | 4 | 18 | 8 | 6 | 0 | 30 |
| 4 | 7 | 19 | 17 | 10 | 1 | 100 | 60 |
| Ανάγκες | 10 | 30 | 40 | 50 | 70 | 30 |
∑a = 80 + 60 + 30 + 60 = 230
∑b = 10 + 30 + 40 + 50 + 70 + 30 = 230
Ο όρος ισορροπίας πληρούται. Προμηθεύει ίσες ανάγκες. Άρα, το μοντέλο του μεταφορικού προβλήματος έκλεισε. Εάν το μοντέλο ήταν ανοιχτό, θα ήταν απαραίτητο να εισαχθούν πρόσθετοι προμηθευτές ή καταναλωτές.
Επί δεύτερο επίπεδοδιενεργείται έρευνα σχέδιο αναφοράςμεθόδους που δίνονται παραπάνω (η πιο συνηθισμένη είναι μέθοδος ελάχιστου κόστους).
Για να δείξουμε τον αλγόριθμο, παρουσιάζουμε μόνο μερικές επαναλήψεις.
Επανάληψη Νο. 1. Ελάχιστο στοιχείο μήτρας ίσο με μηδέν. Για αυτό το στοιχείο, τα αποθέματα είναι 60 και οι απαιτήσεις είναι 30. Από αυτά επιλέγουμε τον ελάχιστο αριθμό 30 και τον αφαιρούμε (βλ. πίνακα). Ταυτόχρονα, διαγράφουμε την έκτη στήλη από τον πίνακα (οι ανάγκες της είναι ίσες με 0).
| 3 | 20 | 8 | 13 | 4 | Χ | 80 |
| 4 | 4 | 18 | 14 | 3 | 0 | 60 - 30 = 30 |
| 10 | 4 | 18 | 8 | 6 | Χ | 30 |
| 7 | 19 | 17 | 0 | 1 | Χ | 60 |
| 10 | 30 | 40 | 50 | 70 | 30 - 30 = 0 | 0 |
Επανάληψη Νο. 2. Και πάλι ψάχνουμε για το ελάχιστο (0). Από το ζευγάρι (60;50) επιλέγουμε τον ελάχιστο αριθμό 50. Διαγράψτε την πέμπτη στήλη.
| 3 | 20 | 8 | Χ | 4 | Χ | 80 |
| 4 | 4 | 18 | Χ | 3 | 0 | 30 |
| 10 | 4 | 18 | Χ | 6 | Χ | 30 |
| 7 | 19 | 17 | 0 | 1 | Χ | 60 - 50 = 10 |
| 10 | 30 | 40 | 50 - 50 = 0 | 70 | 0 | 0 |
Επανάληψη Νο. 3. Συνεχίζουμε τη διαδικασία μέχρι να επιλέξουμε όλες τις ανάγκες και τις προμήθειες.
Επανάληψη Νο. Το στοιχείο που αναζητάτε είναι 8. Για αυτό το στοιχείο, οι προμήθειες είναι ίσες με τις απαιτήσεις (40).
| 3 | Χ | 8 | Χ | 4 | Χ | 40 - 40 = 0 |
| Χ | Χ | Χ | Χ | 3 | 0 | 0 |
| Χ | 4 | Χ | Χ | Χ | Χ | 0 |
| Χ | Χ | Χ | 0 | 1 | Χ | 0 |
| 0 | 0 | 40 - 40 = 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 3 | 4 | 5 | 6 | Αποθεματικά | |
| 1 | 3 | 20 | 8 | 13 | 4 | 100 | 80 |
| 2 | 4 | 4 | 18 | 14 | 3 | 0 | 60 |
| 3 | 10 | 4 | 18 | 8 | 6 | 0 | 30 |
| 4 | 7 | 19 | 17 | 0 | 1 | 100 | 60 |
| Ανάγκες | 10 | 30 | 40 | 50 | 70 | 30 |
Ας μετρήσουμε τον αριθμό των κατειλημμένων κελιών του πίνακα, υπάρχουν 8 από αυτά, αλλά θα πρέπει να είναι m + n - 1 = 9. Επομένως, το σχέδιο υποστήριξης είναι εκφυλισμένο. Χτίζουμε νέο σχέδιο. Μερικές φορές πρέπει να δημιουργήσετε πολλά σχέδια αναφοράς πριν βρείτε ένα μη εκφυλισμένο.
| 1 | 2 | 3 | 4 | 5 | 6 | Αποθεματικά | |
| 1 | 3 | 20 | 8 | 13 | 4 | 100 | 80 |
| 2 | 4 | 4 | 18 | 14 | 3 | 0 | 60 |
| 3 | 10 | 4 | 18 | 8 | 6 | 0 | 30 |
| 4 | 7 | 19 | 17 | 0 | 1 | 100 | 60 |
| Ανάγκες | 10 | 30 | 40 | 50 | 70 | 30 |
Ως αποτέλεσμα, προκύπτει το πρώτο σχέδιο υποστήριξης, το οποίο ισχύει, αφού ο αριθμός των κατειλημμένων κελιών του πίνακα είναι 9 και αντιστοιχεί στον τύπο m + n - 1 = 6 + 4 - 1 = 9, δηλ. το σχέδιο αναφοράς είναι μη εκφυλισμένος.
Τρίτο στάδιοσυνίσταται στη βελτίωση του σχεδίου αναφοράς που βρέθηκε. Εδώ χρησιμοποιούν πιθανή μέθοδοςή μέθοδο διανομής. Σε αυτό το στάδιο, η ορθότητα της λύσης μπορεί να παρακολουθηθεί μέσω της συνάρτησης κόστους F(x) . Εάν μειωθεί (με την επιφύλαξη ελαχιστοποίησης του κόστους), τότε η λύση είναι σωστή.
Παράδειγμα Νο. 2. Χρησιμοποιώντας τη μέθοδο ελάχιστης χρέωσης, παρουσιάστε ένα αρχικό σχέδιο για την επίλυση ενός προβλήματος μεταφοράς. Ελέγξτε τη βελτιστοποίηση χρησιμοποιώντας τη μέθοδο δυναμικού.
| 30 | 50 | 70 | 10 | 30 | 10 | |
| 40 | 2 | 4 | 6 | 1 | 1 | 2 |
| 80 | 3 | 4 | 5 | 9 | 9 | 6 |
| 60 | 4 | 3 | 2 | 7 | 8 | 7 |
| 20 | 5 | 1 | 3 | 5 | 7 | 9 |
Παράδειγμα Νο. 3. Τέσσερα εργοστάσια ζαχαροπλαστικής μπορούν να παράγουν τρία είδη προϊόντων ζαχαροπλαστικής. Δαπάνες για την παραγωγή εκατό βάρους (πεντάδας) προϊόντων ζαχαροπλαστικής από κάθε εργοστάσιο, παραγωγική ικανότηταεργοστάσια (centners το μήνα) και οι ημερήσιες ανάγκες σε προϊόντα ζαχαροπλαστικής (centners το μήνα) αναφέρονται στον πίνακα. Καταρτίστε ένα σχέδιο παραγωγής ζαχαροπλαστικής που ελαχιστοποιεί το συνολικό κόστος παραγωγής.
Σημείωση. Εδώ, μπορείτε πρώτα να μεταφέρετε τον πίνακα κόστους, αφού για την κλασική διατύπωση του μεταφορικού προβλήματος προηγούνται οι χωρητικότητες (παραγωγή) και μετά οι καταναλωτές.
Παράδειγμα αρ. 4. Για την κατασκευή εγκαταστάσεων προμηθεύονται τούβλα από τρία (I, II, III) εργοστάσια. Τα εργοστάσια διαθέτουν 50, 100 και 50 χιλιάδες μονάδες σε αποθήκες, αντίστοιχα. τούβλα Τα αντικείμενα απαιτούν 50, 70, 40 και 40 χιλιάδες τεμάχια, αντίστοιχα. τούβλα Τα τιμολόγια (δεν. μονάδες/χίλιες μονάδες) δίνονται στον πίνακα. Δημιουργήστε ένα σχέδιο μεταφοράς που ελαχιστοποιεί το συνολικό κόστος μεταφοράς.
θα κλείσει εάν:Α) α=40, β=45
Β) α=45, β=40
Β) α=11, β=12
Κατάσταση κλειστού προβλήματος μεταφοράς: ∑a = ∑b
Βρίσκουμε, ∑a = 35+20+b = 55+b; ∑b = 60+a
Παίρνουμε: 55+b = 60+a
Ισότητα θα παρατηρηθεί μόνο όταν a=40, b=45