Ισορροπημένο πρόβλημα μεταφοράς: Vogel, MODI και Βορειοδυτική Γωνία

Γρήγορη απάντηση: ποια μέθοδος χρησιμοποιώ; Η Βορειοδυτική Γωνία δίνει μια γρήγορη αρχική εφικτή λύση, χωρίς να λαμβάνει υπόψη τα κόστη. Η Vogel δίνει επίσης αρχική εφικτή λύση, αλλά χρησιμοποιεί ποινές και συνήθως ξεκινά από χαμηλότερο κόστος. Η MODI εφαρμόζεται μετά από αρχική λύση, για να ελέγξει αν η λύση είναι βέλτιστη και να τη βελτιώσει αν χρειάζεται. Στην πράξη, για μια ολοκληρωμένη λύση ξεκινάμε με Vogel και μετά ελέγχουμε με MODI. Αν η άσκηση ζητά συγκεκριμένα Βορειοδυτική Γωνία, τη χρησιμοποιούμε για την αρχική λύση και μετά μπορούμε να συνεχίσουμε με MODI. Αν θέλεις να φτιάξεις παρόμοιες ασκήσεις για εξάσκηση, μπορείς να χρησιμοποιήσεις και τη δημιουργία ασκήσεων του Mathimatikos. Στα προβλήματα μεταφοράς θέλουμε να μεταφέρουμε προϊόντα από ορισμένες πηγές, για παράδειγμα εργοστάσια ή αποθήκες, προς ορισμένους προορισμούς, για παράδειγμα καταστήματα ή κέντρα κατανάλωσης, με το μικρότερο δυνατό κόστος. Κάθε πηγή έχει μια διαθέσιμη ποσότητα και κάθε προορισμός έχει μια ζητούμενη ποσότητα. Επίσης, για κάθε διαδρομή από πηγή προς προορισμό γνωρίζουμε το μοναδιαίο κόστος μεταφοράς. Ο στόχος είναι να αποφασίσουμε πόσες μονάδες θα στείλουμε από κάθε πηγή προς κάθε προορισμό, ώστε: 1. να μη στείλουμε περισσότερα από όσα διαθέτει κάθε πηγή, 2. να καλύψουμε ακριβώς τη ζήτηση κάθε προορισμού, 3. να πετύχουμε το ελάχιστο συνολικό κόστος. 1. Μαθηματική μορφή προβλήματος μεταφοράς Έστω ότι έχουμε: πηγές A1, A2, \ldots, Am, προορισμούς K1, K2, \ldots, Kn, προσφορά ai στην πηγή Ai, ζήτηση bj στον προορισμό Kj, μοναδιαίο κόστος μεταφοράς c{ij} από την πηγή Ai προς τον προορισμό Kj, ποσότητα μεταφοράς x{ij} από την πηγή Ai προς τον προορισμό Kj. Το συνολικό κόστος είναι: Z=\sum{i=1}^{m}\sum{j=1}^{n} c{ij}x{ij}. Θέλουμε να ελαχιστοποιήσουμε το Z, με περιορισμούς: \sum{j=1}^{n}x{ij}=ai για κάθε πηγή Ai, και: \sum{i=1}^{m}x{ij}=bj για κάθε προορισμό Kj. Επίσης: x{ij}\ge 0. 2. Πότε το πρόβλημα είναι ισορροπημένο; Ένα πρόβλημα μεταφοράς λέγεται ισορροπημένο όταν το άθροισμα των προσφορών είναι ίσο με το άθροισμα των ζητήσεων. Δηλαδή: \sum ai=\sum bj. Αν τα δύο αθροίσματα είναι ίσα, τότε μπορούμε να εφαρμόσουμε κανονικά τις μεθόδους Βορειοδυτικής Γωνίας, Vogel και MODI. Αν δεν είναι ίσα, τότε πριν ξεκινήσουμε πρέπει να κάνουμε το πρόβλημα ισορροπημένο. Αν η προσφορά είναι μεγαλύτερη από τη ζήτηση Προσθέτουμε έναν φανταστικό προορισμό με ζήτηση ίση με τη διαφορά: \sum ai\sum bj. Συνήθως τα κόστη προς τον φανταστικό προορισμό μπαίνουν ίσα με 0, γιατί η ποσότητα αυτή αντιστοιχεί σε προϊόν που περισσεύει. Αν η ζήτηση είναι μεγαλύτερη από την προσφορά Προσθέτουμε μια φανταστική πηγή με προσφορά ίση με τη διαφορά: \sum bj\sum ai. Συνήθως τα κόστη από τη φανταστική πηγή μπαίνουν ίσα με 0, εκτός αν η άσκηση δίνει κάποιο πρόστιμο ή ειδικό κόστος ανικανοποίητης ζήτησης. 3. Πότε χρησιμοποιώ Βορειοδυτική Γωνία, πότε Vogel και πότε MODI; Οι τρεις μέθοδοι δεν κάνουν ακριβώς την ίδια δουλειά. Βορειοδυτική Γωνία Η μέθοδος της Βορειοδυτικής Γωνίας δίνει μια αρχική βασική εφικτή λύση. Ξεκινάμε από το πάνω αριστερό κελί του πίνακα, δηλαδή από τη βορειοδυτική γωνία. Βάζουμε όσο μπορούμε, δηλαδή το ελάχιστο ανάμεσα στην προσφορά της γραμμής και στη ζήτηση της στήλης. Μετά προχωράμε δεξιά ή κάτω, ανάλογα με το τι μηδενίστηκε. Η μέθοδος αυτή είναι απλή και γρήγορη, αλλά έχει ένα βασικό μειονέκτημα: δεν λαμβάνει υπόψη τα κόστη. Άρα τη χρησιμοποιούμε κυρίως: όταν ζητείται ρητά από την άσκηση, όταν θέλουμε γρήγορα μια αρχική εφικτή λύση, όταν μαθαίνουμε τη βασική λογική των προβλημάτων μεταφοράς. Μέθοδος Vogel Η μέθοδος Vogel δίνει επίσης αρχική βασική εφικτή λύση, αλλά συνήθως καλύτερη από τη Βορειοδυτική Γωνία. Η βασική ιδέα της Vogel είναι ότι δεν κοιτάμε μόνο το μικρότερο κόστος. Κοιτάμε και πόσο θα μας κοστίσει αν δεν χρησιμοποιήσουμε την καλύτερη επιλογή μιας γραμμής ή μιας στήλης. Για αυτό υπολογίζουμε ποινές. Η ποινή μιας γραμμής ή στήλης είναι: p=c2c1. Εδώ c1 είναι το μικρότερο κόστος της γραμμής ή στήλης και c2 είναι το δεύτερο μικρότερο κόστος. Όσο μεγαλύτερη είναι η ποινή, τόσο πιο σημαντικό είναι να χρησιμοποιήσουμε το φθηνότερο κελί αυτής της γραμμής ή στήλης. Τη Vogel τη χρησιμοποιούμε: όταν ζητείται αρχική λύση με καλή ποιότητα, όταν θέλουμε να ξεκινήσουμε κοντά στη βέλτιστη λύση, πριν εφαρμόσουμε MODI. Μέθοδος MODI Η MODI δεν είναι μέθοδος για να βρούμε αρχική λύση. Είναι μέθοδος ελέγχου βελτιστότητας και βελτίωσης. Δηλαδή: 1. πρώτα βρίσκουμε μια αρχική βασική εφικτή λύση με Βορειοδυτική Γωνία ή Vogel, 2. μετά εφαρμόζουμε MODI για να δούμε αν η λύση είναι βέλτιστη, 3. αν δεν είναι βέλτιστη, τη βελτιώνουμε, 4. επαναλαμβάνουμε μέχρι να φτάσουμε στη βέλτιστη λύση. Για πρόβλημα ελαχιστοποίησης, η λύση είναι βέλτιστη όταν όλα τα μειωμένα κόστη είναι μη αρνητικά: \Delta{ij}\ge 0. 4. Λυμένη άσκηση ισορροπημένου προβλήματος μεταφοράς Μια εταιρεία διαθέτει τρεις αποθήκες A1,A2,A3 και θέλει να στείλει προϊόντα σε τέσσερα καταστήματα K1,K2,K3,K4. Οι προσφορές, οι ζητήσεις και τα μοναδιαία κόστη δίνονται στον πίνακα: | Πηγή | K1 | K2 | K3 | K4 | Προσφορά | ||:|:|:|:|:| | A1 | 10 | 7 | 9 | 8 | 100 | | A2 | 6 | 8 | 5 | 11 | 80 | | A3 | 9 | 6 | 7 | 10 | 120 | | Ζήτηση | 70 | 90 | 60 | 80 | 300 | Να βρεθεί το σχέδιο μεταφοράς ελάχιστου κόστους. Να χρησιμοποιηθεί πρώτα η μέθοδος Vogel και στη συνέχεια η μέθοδος MODI. 5. Έλεγχος ισορροπίας Υπολογίζουμε το άθροισμα των προσφορών: 100+80+120=300. Υπολογίζουμε το άθροισμα των ζητήσεων: 70+90+60+80=300. Άρα: \sum ai=\sum bj=300. Το πρόβλημα είναι ισορροπημένο. Συνεπώς δεν χρειάζεται να προσθέσουμε φανταστική γραμμή ή φανταστική στήλη. 6. Τι θα έδινε η Βορειοδυτική Γωνία; Η Βορειοδυτική Γωνία ξεκινά από το κελί (A1,K1). Βήμα 1 Στο κελί (A1,K1) βάζουμε: x{11}=\min(100,70)=70. Η ζήτηση του K1 καλύπτεται και η προσφορά του A1 μένει: 10070=30. Βήμα 2 Προχωράμε στο κελί (A1,K2): x{12}=\min(30,90)=30. Η πηγή A1 εξαντλείται και η ζήτηση του K2 μένει: 9030=60. Βήμα 3 Προχωράμε στο κελί (A2,K2): x{22}=\min(80,60)=60. Η ζήτηση του K2 καλύπτεται και η προσφορά του A2 μένει: 8060=20. Βήμα 4 Προχωράμε στο κελί (A2,K3): x{23}=\min(20,60)=20. Η πηγή A2 εξαντλείται και η ζήτηση του K3 μένει: 6020=40. Βήμα 5 Προχωράμε στο κελί (A3,K3): x{33}=\min(120,40)=40. Η ζήτηση του K3 καλύπτεται και η προσφορά του A3 μένει: 12040=80. Βήμα 6 Τέλος, στο κελί (A3,K4): x{34}=80. Ο πίνακας της Βορειοδυτικής Γωνίας είναι: | Πηγή | K1 | K2 | K3 | K4 | Προσφορά | ||:|:|:|:|:| | A1 | 70 | 30 | 0 | 0 | 100 | | A2 | 0 | 60 | 20 | 0 | 80 | | A3 | 0 | 0 | 40 | 80 | 120 | | Ζήτηση | 70 | 90 | 60 | 80 | 300 | Το κόστος είναι: C{\mathrm{NW}}=70\cdot 10+30\cdot 7+60\cdot 8+20\cdot 5+40\cdot 7+80\cdot 10. Άρα: C{\mathrm{NW}}=700+210+480+100+280+800=2570. Η λύση είναι εφικτή, αλλά δεν ξέρουμε αν είναι βέλτιστη. Επίσης, επειδή η Βορειοδυτική Γωνία δεν κοιτάζει τα κόστη, συχνά δίνει ακριβότερη αρχική λύση. 7. Αρχική λύση με τη μέθοδο Vogel Στη μέθοδο Vogel υπολογίζουμε σε κάθε βήμα τις ποινές γραμμών και στηλών. Η ποινή είναι: p=c2c1. Μετά: 1. επιλέγουμε τη μεγαλύτερη ποινή, 2. μέσα στη γραμμή ή στήλη της μεγαλύτερης ποινής επιλέγουμε το κελί με το μικρότερο κόστος, 3. κάνουμε τη μέγιστη δυνατή κατανομή, 4. διαγράφουμε τη γραμμή ή τη στήλη που καλύφθηκε, 5. επαναλαμβάνουμε. Βήμα 1: αρχικές ποινές Οι ποινές γραμμών είναι: για A1: τα δύο μικρότερα κόστη είναι 7 και 8, άρα ποινή 87=1, για A2: τα δύο μικρότερα κόστη είναι 5 και 6, άρα ποινή 65=1, για A3: τα δύο μικρότερα κόστη είναι 6 και 7, άρα ποινή 76=1. Οι ποινές στηλών είναι: για K1: τα δύο μικρότερα κόστη είναι 6 και 9, άρα ποινή 96=3, για K2: τα δύο μικρότερα κόστη είναι 6 και 7, άρα ποινή 76=1, για K3: τα δύο μικρότερα κόστη είναι 5 και 7, άρα ποινή 75=2, για K4: τα δύο μικρότερα κόστη είναι 8 και 10, άρα ποινή 108=2. Η μεγαλύτερη ποινή είναι 3, στη στήλη K1. Στη στήλη K1 το μικρότερο κόστος είναι: c{21}=6. Άρα κάνουμε κατανομή στο κελί (A2,K1): x{21}=\min(80,70)=70. Η ζήτηση του K1 καλύπτεται. Η προσφορά του A2 μένει: 8070=10. Βήμα 2 Η στήλη K1 κλείνει. Μένουν οι στήλες K2,K3,K4. Η γραμμή A2 έχει πλέον διαθέσιμη προσφορά 10. Στη γραμμή A2 τα κόστη που απομένουν είναι 8,5,11. Τα δύο μικρότερα είναι 5 και 8, άρα η ποινή είναι: 85=3. Η μεγαλύτερη ποινή είναι τώρα στη γραμμή A2. Το μικρότερο κόστος στη γραμμή αυτή είναι: c{23}=5. Άρα: x{23}=\min(10,60)=10. Η πηγή A2 εξαντλείται. Η ζήτηση του K3 μένει: 6010=50. Βήμα 3 Η γραμμή A2 κλείνει. Μένουν οι γραμμές A1,A3 και οι στήλες K2,K3,K4. Οι μεγαλύτερες ποινές εμφανίζονται στις στήλες K3 και K4. Επιλέγουμε τη στήλη K3, όπου το μικρότερο κόστος είναι: c{33}=7. Άρα: x{33}=\min(120,50)=50. Η στήλη K3 κλείνει. Η προσφορά του A3 μένει: 12050=70. Βήμα 4 Μένουν οι στήλες K2,K4 και οι γραμμές A1,A3. Στη γραμμή A3 τα κόστη που απομένουν είναι 6 και 10, άρα η ποινή είναι: 106=4. Η μεγαλύτερη ποινή είναι στη γραμμή A3. Το μικρότερο κόστος εκεί είναι: c{32}=6. Άρα: x{32}=\min(70,90)=70. Η πηγή A3 εξαντλείται. Η ζήτηση του K2 μένει: 9070=20. Βήμα 5 Μένει μόνο η γραμμή A1. Οι υπόλοιπες ζητήσεις είναι: K2=20,\qquad K4=80. Άρα: x{12}=20,\qquad x{14}=80. Ο πίνακας της αρχικής λύσης Vogel είναι: | Πηγή | K1 | K2 | K3 | K4 | Προσφορά | ||:|:|:|:|:| | A1 | 0 | 20 | 0 | 80 | 100 | | A2 | 70 | 0 | 10 | 0 | 80 | | A3 | 0 | 70 | 50 | 0 | 120 | | Ζήτηση | 70 | 90 | 60 | 80 | 300 | Το κόστος της λύσης Vogel είναι: C{\mathrm{Vogel}}=20\cdot 7+80\cdot 8+70\cdot 6+10\cdot 5+70\cdot 6+50\cdot 7. Άρα: C{\mathrm{Vogel}}=140+640+420+50+420+350=2020. Η Vogel έδωσε κόστος 2020, ενώ η Βορειοδυτική Γωνία έδωσε κόστος 2570. Αυτό δείχνει γιατί η Vogel είναι συνήθως καλύτερη αρχική μέθοδος. 8. Έλεγχος με MODI Τώρα ελέγχουμε αν η λύση Vogel είναι βέλτιστη. Έχουμε m=3 γραμμές και n=4 στήλες. Μια μη εκφυλισμένη βασική λύση πρέπει να έχει: m+n1=3+41=6 βασικά κελιά. Τα βασικά κελιά της λύσης Vogel είναι: (A1,K2),\ (A1,K4),\ (A2,K1),\ (A2,K3),\ (A3,K2),\ (A3,K3). Είναι ακριβώς 6, άρα η λύση δεν είναι εκφυλισμένη. Βήμα 1: υπολογισμός δυναμικών Στη MODI βρίσκουμε αριθμούς ui για τις γραμμές και vj για τις στήλες, ώστε για κάθε βασικό κελί να ισχύει: ui+vj=c{ij}. Θέτουμε αυθαίρετα: u1=0. Από το βασικό κελί (A1,K2): u1+v2=7 \Rightarrow 0+v2=7 \Rightarrow v2=7. Από το βασικό κελί (A1,K4): u1+v4=8 \Rightarrow 0+v4=8 \Rightarrow v4=8. Από το βασικό κελί (A3,K2): u3+v2=6 \Rightarrow u3+7=6 \Rightarrow u3=1. Από το βασικό κελί (A3,K3): u3+v3=7 \Rightarrow 1+v3=7 \Rightarrow v3=8. Από το βασικό κελί (A2,K3): u2+v3=5 \Rightarrow u2+8=5 \Rightarrow u2=3. Από το βασικό κελί (A2,K1): u2+v1=6 \Rightarrow 3+v1=6 \Rightarrow v1=9. Άρα: u1=0,\qquad u2=3,\qquad u3=1 και: v1=9,\qquad v2=7,\qquad v3=8,\qquad v4=8. Βήμα 2: υπολογισμός μειωμένων κοστών Για κάθε μη βασικό κελί υπολογίζουμε: \Delta{ij}=c{ij}uivj. Τα μη βασικά κελιά είναι: | Μη βασικό κελί | Υπολογισμός | \Delta{ij} | ||:|:| | (A1,K1) | 1009 | 1 | | (A1,K3) | 908 | 1 | | (A2,K2) | 8(3)7 | 4 | | (A2,K4) | 11(3)8 | 6 | | (A3,K1) | 9(1)9 | 1 | | (A3,K4) | 10(1)8 | 3 | Όλα τα \Delta{ij} είναι θετικά. Για πρόβλημα ελαχιστοποίησης, όταν όλα τα μειωμένα κόστη είναι μη αρνητικά: \Delta{ij}\ge 0, η λύση είναι βέλτιστη. Άρα η λύση Vogel είναι ήδη βέλτιστη. 9. Τελική απάντηση Το βέλτιστο σχέδιο μεταφοράς είναι: | Πηγή | K1 | K2 | K3 | K4 | Προσφορά | ||:|:|:|:|:| | A1 | 0 | 20 | 0 | 80 | 100 | | A2 | 70 | 0 | 10 | 0 | 80 | | A3 | 0 | 70 | 50 | 0 | 120 | | Ζήτηση | 70 | 90 | 60 | 80 | 300 | Δηλαδή: x{12}=20,\quad x{14}=80,\quad x{21}=70,\quad x{23}=10,\quad x{32}=70,\quad x{33}=50. Το ελάχιστο κόστος είναι: C{\min}=2020. 10. Τι πρέπει να θυμάσαι Πρώτα ελέγχουμε αν το πρόβλημα είναι ισορροπημένο. Αν: \sum ai=\sum bj, τότε προχωράμε κανονικά. Αν δεν είναι ίσα, προσθέτουμε φανταστική γραμμή ή φανταστική στήλη. Η Βορειοδυτική Γωνία δίνει αρχική εφικτή λύση, αλλά δεν κοιτάζει τα κόστη. Η Vogel δίνει επίσης αρχική εφικτή λύση, αλλά χρησιμοποιεί ποινές και συνήθως οδηγεί σε καλύτερο αρχικό κόστος. Η MODI εφαρμόζεται μετά από μια αρχική λύση, για να ελέγξει αν η λύση είναι βέλτιστη ή αν μπορεί να βελτιωθεί. Για πρόβλημα ελαχιστοποίησης: αν όλα τα \Delta{ij}\ge 0, η λύση είναι βέλτιστη, αν υπάρχει κάποιο \Delta{ij}<0, η λύση δεν είναι βέλτιστη και χρειάζεται βελτίωση με κλειστό κύκλο. Στο συγκεκριμένο παράδειγμα, η Vogel έδωσε αρχική λύση κόστους 2020 και η MODI έδειξε ότι αυτή η λύση είναι ήδη βέλτιστη. 11. Συχνά λάθη Λάθος 1: Ξεκινάμε χωρίς έλεγχο ισορροπίας Πριν εφαρμόσουμε οποιαδήποτε μέθοδο, πρέπει να ελέγξουμε αν το συνολικό άθροισμα προσφορών είναι ίσο με το συνολικό άθροισμα ζητήσεων. Λάθος 2: Μπερδεύουμε τη Vogel με τη MODI Η Vogel δίνει αρχική λύση. Η MODI ελέγχει και βελτιώνει μια λύση που ήδη έχουμε. Λάθος 3: Νομίζουμε ότι η Βορειοδυτική Γωνία δίνει πάντα καλή λύση Η Βορειοδυτική Γωνία δίνει εφικτή λύση, όχι απαραίτητα καλή λύση. Στο παράδειγμα έδωσε κόστος 2570, ενώ η Vogel έδωσε 2020. Λάθος 4: Ξεχνάμε τον αριθμό των βασικών κελιών Σε πρόβλημα με m γραμμές και n στήλες, μια μη εκφυλισμένη βασική λύση πρέπει να έχει: m+n1 βασικά κελιά. Αν έχει λιγότερα, έχουμε εκφυλισμό και χρειάζεται προσοχή πριν εφαρμόσουμε MODI. Λάθος 5: Διαβάζουμε λάθος τα μειωμένα κόστη Σε πρόβλημα ελαχιστοποίησης, αρνητικό μειωμένο κόστος σημαίνει ότι μπορούμε να μειώσουμε το συνολικό κόστος. Αν όλα τα μειωμένα κόστη είναι μη αρνητικά, η λύση είναι βέλτιστη. 12. Μικρή άσκηση για εξάσκηση Δοκίμασε να λύσεις μόνος σου το παρακάτω ισορροπημένο πρόβλημα μεταφοράς. Βρες πρώτα αρχική λύση με Vogel και μετά έλεγξε τη λύση με MODI. | Πηγή | K1 | K2 | K3 | Προσφορά | ||:|:|:|:| | A1 | 4 | 8 | 6 | 40 | | A2 | 5 | 3 | 7 | 60 | | A3 | 6 | 4 | 5 | 50 | | Ζήτηση | 50 | 70 | 30 | 150 | Πρώτα έλεγξε ότι: 40+60+50=50+70+30=150. Αφού ολοκληρώσεις τη λύση, σύγκρινε το αποτέλεσμα με μια δεύτερη αρχική λύση από τη Βορειοδυτική Γωνία. Έτσι φαίνεται καθαρά γιατί η επιλογή αρχικής μεθόδου επηρεάζει το κόστος που παίρνουμε πριν από τη MODI.

Ισορροπημένο πρόβλημα μεταφοράς: Vogel, MODI και Βορειοδυτική Γωνία

Περισσότερα άρθρα

Ενεργό Μάθημα: Μετασχηματισμοί και Αντίστροφες Συναρτήσεις

Ενεργό Μάθημα: Λογαριθμικές Συναρτήσεις