Μαθηματικός Προγραμματισμός
Class Notes
Μέθοδος Simplex
Έστω το ακόλοθου γραμμικό πρόβλημα:
\[\begin{array}{cc} max & z = x_1 + x_2 \\ υπ. \\ & \ \ x_1 + x_2 \leq{4} \\ & 2x_1 + x_2 \leq{7} \\ & \ \ \ \ \ \ \ \ \ \ x_2 \leq{2} \\ & x_1 \geq{0}, x_2 \geq{0} \end{array}\]Για κάθε γραμμή που έχουμε προσθέτουμε και μία βασική μεταβλητή. Άρα προσθέτουμε τις βασικές μεταβητές \(x_3, x_4, x_5\) την κάθε μία στην δική της γραμμή. Οπότε έχουμε:
\[\begin{array}{cc} max & z = x_1 + x_2 \\ υπ. \\ & \ \ x_1 + x_2 & + x_3 & & \ \ \ \ \ \ \ \ = 4 \\ & 2x_1 + x_2 & &+ x_4 & \ \ \ \ \ \ \ \ = 7 \\ & \ \ \ \ \ \ \ \ \ \ x_2 & & & +x_5 = 2 \\ & x_1 \geq{0}, x_2 \geq{0}, x_3 \geq{0}, x_4 \geq{0}, x_5 \geq{0} \end{array}\]Μετακινούμε όλα τα στοιχεία του \(z\) στην αριστερή πλευρά. Οπότε θα έχουμε:
\[z - x_1 - x_2 = 0\]Τώρα απλά πρέπει να φτιάξουμε τον πίνακα.
| \(C_κ\) | \(K\) | \(X_κ\) |
|---|---|---|
| 0 | 3 | 4 |
| 0 | 4 | 7 |
| 0 | 5 | 2 |
| 0 |
| \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) |
|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 |
| 2 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| -1 | -1 | 0 | 0 | 0 |
Πρώτος πίνακας:
\(C_κ\) : Είναι οι τιμές των βασικών μεταβλητών στην γραμμική συνάρτηση.
\(K\) : Είναι οι βασικές μεταβλητές.
\(X_κ\) : Είναι στην ουσία οι τιμές στο δεξί μέρος κάθε γραμμής.
Δεύτερος πίνακας:
Είναι απλά το γραμμικό σύστμα σε μορφή μήτρας.
Βασικές και Μη Βασικές μεταβλητές
Κάθε στήλη του 2ου πύνακα που αποτελείται μόνο από ένα κελί με τιμή \(1\) και όλα τα υπόλοιπα με τιμή \(0\) είναι μία βασική μεταβλητή.
Μη βασικές μεταβλητές είναι οι στήλες του πίνακα που αποτελούνται από άλλες τιμές.
Το σημείο Pivot
Τώρα πρέπει να βρούμε το σημείο Pivot. Για να το βρούμε πρέπει να έχουμε την Pivot στήλη και την Pivot γραμμή.
Αρχίζουμε με την Pivot στήλη την οποία βρίσκουμε απλά ψάχνοντας την μικρότερη αρνητική τιμή στην τελευταία γραμμή του 2ου πίνακα. Αφότου την βρούμε την σημειώνουμε (συνήθως με ένα βέλος ή έναν αστερίσκο).
Σημείωση: Αν δεν υπάρχει αρνητική τιμή τότε σταματάμε εκεί.
| \(C_κ\) | \(K\) | \(X_κ\) |
|---|---|---|
| 0 | 3 | 4 |
| 0 | 4 | 7 |
| 0 | 5 | 2 |
| 0 |
| \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) |
|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 |
| 2 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| -1 | -1 | 0 | 0 | 0 |
Στην περίπτωση μας απλά διαλέγουμε όποια στήλη θέλουμε. Εγώ διάλεξα την στήλη \(x_1\).
Τώρα πρέπει να βρούμε την Pivot γραμμή. Στην ουσία είναι η γραμμή με το μικρότερο μη αρνητικό ratio.
Για να βρούμε το ratio κάθε γραμμής απλά κάνουμε την εξής διαίρεση:
\[X_κ / Pivot_c\]Δηλαδή διαιρούμε κάθε κελί της στήλης \(X_κ\) με κάθε κελί της Pivot στήλης που βρήκαμε προηγουμένος.
Σημείωση: Αν δεν μπορούμε να βρούμε μη αρνητικό ratio σε καμία γραμμή τότε σταματάμε γιατί το πρόβλημα δεν έχει λύση.
| \(C_κ\) | \(K\) | \(X_κ\) |
|---|---|---|
| 0 | 3 | 4 |
| 0 | 4 | 7 |
| 0 | 5 | 2 |
| 0 |
| \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) | Ratios |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 4 / 1 = 4 |
| 2 | 1 | 0 | 1 | 0 | 7 / 2 = 3.5 |
| 0 | 1 | 0 | 0 | 1 | 2 / 0 = :( |
| -1 | -1 | 0 | 0 | 0 |
Το μικρότερο μη αρνητικό ratio βρίσκεται στην 2η γραμμή, η οποία είναι και η Pivot γραμμη.
Κυκλώνουμε το κελί στην τομή της Pivot στήλης με την Pivot γραμμή, στην περίπτωση μας είναι ο αριθμός \(2\).
| \(C_κ\) | \(K\) | \(X_κ\) |
|---|---|---|
| 0 | 3 | 4 |
| 0 | 4 | 7 |
| 0 | 5 | 2 |
| 0 |
| \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) | Ratios |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 4 / 1 = 4 |
| (2) | 1 | 0 | 1 | 0 | 7 / 2 = 3.5 |
| 0 | 1 | 0 | 0 | 1 | 2 / 0 = :( |
| -1 | -1 | 0 | 0 | 0 |
Τώρα που έχουμε το Pivot σημείο πρέπει να κάνουμε τις απαραίτητες γραμμοπράξεις έτσι ώστε η στήλη που βρίσκεται αυτό το σημείο να μετατραπέι σε βασική μεταβλητή.
Δηλαδή το κελί του Pivot σημείου να γίνει \(1\) και η όλη υπόλοιπη στήλη να γίνει \(0\).
Σημείωση: Οι γραμμοπράξεις επιρεάζουν ολόκληρο τον 2ο πίνακα καθώς και την στήλη \(X_κ\) του 1ου πίνακα.
Οι γραμμοπράξεις είναι οι εξής:
\[R_2 \rightarrow{R_2 / 2}\] \[R_1 \rightarrow{R_1 - R_2}\] \[R_4 \rightarrow{R_4 + R_2}\]Μετά από αυτές τις γραμμοπράξεις έχουμε τον ακόλουθο πίνακα.
| \(C_κ\) | \(K\) | \(X_κ\) |
|---|---|---|
| 0 | 3 | 1/2 |
| 1 | 1 | 7/2 |
| 0 | 5 | 2 |
| 7/2 |
| \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) |
|---|---|---|---|---|
| 0 | 1/2 | 1 | -1/2 | 0 |
| 1 | 1/2 | 0 | 1/2 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | -1/2 | 0 | 1/2 | 0 |
Όπως είπαμε και πριν η στήλη \(K\) μας δείχνει τις βασικές μεταβλητες. Πλέον οι βασικές μεταβλητές είναι η \(x_1\), \(x_3\) και \(x_5\). Άρα την θέση της \(x_4\) πήρε η \(x_1\).
Αλλάξαμε και μία τιμή στην στήλη \(C\) το οποίο έγινε επειδή πλέον η \(x_1\) είναι βασική μεταβλητή και υπάρχει στην αρχική γραμμική συνάρτηση (\(z\)).
Παρατηρούμε όμως ότι στην τελευταία γραμμή του πίνακα υπάρχει ακόμα αρνητική τιμή. Άρα πρέπει να επαναλάβουμε την διαδικασία.
| \(C_κ\) | \(K\) | \(X_κ\) |
|---|---|---|
| 0 | 3 | 1/2 |
| 1 | 1 | 7/2 |
| 0 | 5 | 2 |
| 7/2 |
| \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) | Ratios |
|---|---|---|---|---|---|
| 0 | (1/2) | 1 | -1/2 | 0 | (1/2) / (1/2) = 1 |
| 1 | 1/2 | 0 | 1/2 | 0 | (7/2) / (1/2) = 7 |
| 0 | 1 | 0 | 0 | 1 | 2/1 = 2 |
| 0 | -1/2 | 0 | 1/2 | 0 |
Βρήκαμε το Pivot στοιχείο και τώρα πρέπει να κάνουμε τις γραμμοπράξεις.
Οι οποίες είναι οι εξής:
\[\begin{array}{cc} R_1 \rightarrow{2R_1} \\ R_2 \rightarrow{R_2 - \frac{1}{2} R_1} \\ R_3 \rightarrow{R_3 - R_1} \end{array}\]| \(C_κ\) | \(K\) | \(X_κ\) |
|---|---|---|
| 1 | 2 | 1 |
| 1 | 1 | 3 |
| 0 | 5 | 1 |
| 4 |
| \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) |
|---|---|---|---|---|
| 0 | 1 | 2 | -1 | 0 |
| 1 | 0 | -1 | 1 | 0 |
| 0 | 0 | -2 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 |
Οπότε η λύση είναι:
\[\begin{array}{cc} x_1 = 3 \\ x_2 = 1 \\ z = 4 \end{array}\]Το μεγάλο M
Για να καταλάβουμε ότι ένα γραμμικό σύστημα θέλει την μέθοδο του μεγάλου Μ (αν δεν μας το λέει) απλά κοιτάμε τους περιορισμούς του συστήματος μας για να βρούμε μία ανάμιξη \(\leq{}\) και \(\geq{}\).
Έστω το ακόλοθου γραμμικό πρόβλημα:
\[\begin{array}{cc} max & z = x_1 + 3x_2 \\ υπ. \\ & \ \ x_1 + x_2 \geq{12} \\ & x_1 + 2x_2 \leq{16} \\ \\ & x_1 \geq{0}, x_2 \geq{0} \end{array}\]Τώρα όπως και στον Simplex προσθέτουμε τις έξτρα μεταβλητές μας. Μόνο που σε κάθε γραμμή που έχει \(\geq{}\) την αφαιρούμε.
\[\begin{array}{cc} max & z = x_1 + 3x_2 \\ υπ. \\ & \ \ x_1 + x_2 & - x_3 & & \ \ \ \ \ = 12 \\ & x_1 + 2x_2 & & + x_4 & \ \ \ \ \ \ = 16 \\ \\ & x_1 \geq{0}, x_2 \geq{0}, x_3 \geq{0}, x_4 \geq{0}, x_5 \geq{0} \end{array}\]Τώρα όμως υπάρχει ένα πρόβλημα.
Αν \(x_1 = 0\) και \(x_2 = 0\) τότε:
\[\begin{array}{cc} -x_3 = 12 \iff x_3 = -12 \\ x_4 = 16 \end{array}\]Για να διορθώσουμε το από πάνω χρησιμοποιούμε μία τεχνιτή μεταβλήτή την \(α\) (για να ξεχωρίζει δεν την ονομάζω \(x\)).
Και για κάθε \(α\) που έχουμε βάζουμε ένα \(-Μα\) στην γραμμική συνάρτηση μας.
\[\begin{array}{cc} max & z = x_1 + 3x_2 - Μα \\ υπ. \\ & \ \ x_1 + x_2 & - x_3 & +α & \ \ \ \ \ = 12 \\ & x_1 + 2x_2 & & + x_4 & \ \ \ \ \ \ = 16 \\ \\ & x_1 \geq{0}, x_2 \geq{0}, x_3 \geq{0}, x_4 \geq{0}, a \geq{0} \end{array}\]Και \(z - x_1 - 3x_2 + Μα = 0\)
Δημιουργούμε τους πίνακες που ξέρουμε από τον Simplex.
| \(C_κ\) | \(K\) | \(X_κ\) |
|---|---|---|
| 0 | - | 12 |
| 0 | 4 | 16 |
| 0 |
| \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(α\) |
|---|---|---|---|---|
| 1 | 1 | -1 | 0 | 1 |
| 1 | 2 | 0 | 1 | 0 |
| -1 | -3 | 0 | 0 | \(Μ\) |
Τώρα όμως υπάρχει ένα πρόβλημα. Έχουμε μόνο μία βασική μεταβλητή καθώς η \(x_3\) έχει \(-1\).
Για να το φτιάξουμε αυτό θα διαλέξουμε άλλη στήλη για να την κάνουμε βασική μεταβλητή. Μας βολεύει η στήλη \(α\) να γίνει βασική.
Για να το πετύχουμε όμως αυτό θα πρέπει στην τελεταία γραμμή να υπάρχει \(0\).
Οπότε κάνουμε την εξής γραμμοπράξη:
\[R_3 \rightarrow{R_3 - MR_1}\]Οπότε ο πίνακας θα γίνει έτσι:
| \(C_κ\) | \(K\) | \(X_κ\) |
|---|---|---|
| -\(M\) | α | 12 |
| 0 | 4 | 16 |
| -12 \(Μ\) |
| \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(α\) |
|---|---|---|---|---|
| 1-\(M\) | 1 | -1 | 0 | 1 |
| 1 | 2 | 0 | 1 | 0 |
| -\(Μ\)-1 | -\(Μ\)-3 | \(Μ\) | 0 | 0 |
Τώρα πρέπει να βρούμε το Pivot σημείο.
| \(C_κ\) | \(K\) | \(X_κ\) |
|---|---|---|
| 1 | α | 12 |
| 0 | 4 | 16 |
| -12 \(Μ\) |
| \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(α\) | Ratios |
|---|---|---|---|---|---|
| 1 | 1 | -1 | 0 | 1 | 12 / 1 = 12 |
| 1 | (2) | 0 | 1 | 0 | 16 / 2 = 8 |
| -\(Μ\) -1 | -\(Μ\)-3 | \(Μ\) | 0 | 0 |
Το Pivot σημείο είναι το \(2\) και τώρα πρέπει να κάνουμε τις γραμμοπράξεις:
\[R_2 \rightarrow R_2 / 2\] \[R_1 \rightarrow R_1 - R_2\]
O νέος πίνακας είναι ο εξής:
| \(C_κ\) | \(K\) | \(X_κ\) |
|---|---|---|
| -\(M\) | α | 4 |
| 3 | \(x_2\) | 8 |
| -4 \(M\)+24 |
| \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(α\) |
|---|---|---|---|---|
| 1/2 | 0 | -1 | -1/2 | 1 |
| 1/2 | 1 | 0 | 1/2 | 0 |
| -\(Μ\)/2 + 1/2 | 0 | \(Μ\) | \(M\)/2 + 3/2 | 0 |
Υπάρχει ακόμα αρνητική τιμή στην τελευταία γραμμή του πίνακα άρα επαναλαμβάνουμε την διαδικασία.
Βρίσκουμε το Pivot σημείο.
| \(C_κ\) | \(K\) | \(X_κ\) |
|---|---|---|
| -\(M\) | α | 4 |
| 3 | \(x_2\) | 8 |
| -4 \(M\) +24 |
| \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(α\) | Ratios |
|---|---|---|---|---|---|
| (1/2) | 0 | -1 | -1/2 | 1 | 4 / (1/2) = 8 |
| 1/2 | 1 | 0 | 1/2 | 0 | 8 / (1/2) = 16 |
| - \(Μ\) /2 + 1/2 | 0 | \(Μ\) | \(M\)/2 + 3/2 | 0 |
Κάνουμε τις εξής γραμμοπράξεις:
\[R_1 \rightarrow 2 R_1\] \[R_2 \rightarrow R_2 - \frac{1}{2} R_2\]Οπότε ο νέος πίνακας είναι ο εξής:
| \(C_κ\) | \(K\) | \(X_κ\) |
|---|---|---|
| 1 | \(x_1\) | 8 |
| 3 | \(x_2\) | 4 |
| 20 |
| \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) |
|---|---|---|---|
| 1 | 0 | -2 | -1 |
| 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 2 |
Η στήλη \(a\) δεν χρειάζεται πλέον οπότε την διαγράφουμε.
Οπότε η λύση είναι:
\[x_1 = 8\] \[x_2 = 4\] \[z = 20\]Πρόβλημα Μεταφοράς
Στα συγκεκριμένα προβλήματα υπάρχουν 3 μέθοδοι για την επίλυση τους:
- Μέθοδος της Βορειοδυτικής Γωνίας
- Μέθοδος Βόγκελ
- Μέθοδος ελαχίστου κόστους
Γενικά ισχύει πως η μέθοδος της Βορειοδυτικής Γωνίας είναι και η λιγότερη αποδοτική οπότε είναι καλό να επιλέγουμε μία από τις άλλες μεθόδους.
Ο μόνος λόγος να χρησιμοποιοήσουμε αυτήν την μέθοδο είναι να μας το ζητάει η άσκηση.
Έστω ότι έχουμε τον πίνακα:
| D1 | D2 | D3 | Προσφορά | |
|---|---|---|---|---|
| S1 | 20 | 11 | 10 | 50 |
| S2 | 8 | 12 | 7 | 80 |
| S3 | 9 | 10 | 7 | 50 |
| Ζήτηση | 80 | 80 | 20 |
Το πρώτο πράγμα που κάνουμε πριν καν αποφασίσουμε ποια μέθοδο να χρησιμοποιήσουμε είναι να υπολογίσουμε το άθροισμα της Ζήτησης και της Προσφοράς. Το οποίο πρέπει να είναι ίσο για να συνεχίσουμε, η περίπτωση που δεν είναι ίσο είναι ειδική και θα δούμε αργότερα τι κάνουμε σε αυτή.
Στην περίπτωση μας έχουμε:
\(\textrm{Ζήτηση} = 80 + 80 + 20 = 180\).
\(\textrm{Προσφορά} = 50 + 80 + 50 = 180\).
Οπότε εφόσον \(\textrm{Ζήτηση} = \textrm{Προσφορά}\) μπορούμε να συνεχίσουμε με την λύση.
Θα την λύσω και με τις 3 μεθόδους.
- Βορειοδυτική Γωνία
| D1 | D2 | D3 | Προσφορά | |
|---|---|---|---|---|
| S1 | 20 | 11 | 10 | 50 |
| S2 | 8 | 12 | 7 | 80 |
| S3 | 9 | 10 | 7 | 50 |
| Ζήτηση | 80 | 80 | 20 | 180 / 180 |
Στην μέθοδο αυτή πάντα διαλέγουμε το τέρμα πάνω αριστερά κελί του πίνακα (ακα Βορειοδυτικό κελί).
Τώρα που σημειώσαμε το κελί πρέπει να συγκρίνουμε την Ζήτηση με την Προσφορά σε αυτή την γραμμή και στήλη.
Υπάρχουν 3 περιπτώσεις:
\[\begin{align} \textrm{Ζήτηση} > \textrm{Προσφορά} \\ \textrm{Ζήτηση} < \textrm{Προσφορά} \\ \textrm{Ζήτηση} = \textrm{Προσφορά} \end{align}\]Γενικά εμάς μας νοιάζει η μικρότερη τιμή αλλά στην περίπτωση που είναι ίσες απλώς διαλέγουμε μία από τις δύο.
Στην περίπτωση μας παρατηρούμε ότι \(\textrm{Ζήτηση} > \textrm{Προσφορά}\). Άρα εμείς θα πάρουμε την \(\textrm{Προσφορά}\).
Τώρα κάνουμε τις εξής πράξεις:
\[\textrm{Προσφορά} - \textrm{Προσφορά}\] \[\textrm{Ζήτηση} - \textrm{Προσφορά}\]Δηλαδή \(50 - 50 = 0\) και \(80 - 50 = 30\).
Οπότε ο πίνακας θα είναι κάπως έτσι:
Στην ουσία προσθέσαμε 1 νέα γραμμή και 1 νέα στήλη στον πίνακα όπου δείχνουν τις αλλαγές (στην Προσφορά και στην Ζήτηση) μετά την επιλογή ενός συγκεκριμένου κελιού, στην περίπτωση μας του κελιού (1,1).
Προφανώς θα αρχίζεται πάντα με το κελί (1,1) επειδή όπως είπαμε και πριν είναι το τέρμα πιο πάνω και αριστερο κελί.
Βλέπουμε όμως ότι έχουμε διαγράψει τα κελιά (1,2), (1,3) και (1,4). Αυτό γιατί όπως βλέπουμε έχουμε πλέον \(0\) \(\textrm{Προσφορά}\) και όποτε έχουμε \(0\) \(\textrm{Προσφορά}\) ή \(0\) \(\textrm{Ζήτηση}\) διαγράφουμε την αντίστοιχη γραμμή ή στήλη.
Τέλος στο κελί (1,1) δεν έχουμε πλεον \(20\) αλλά έχουμε \(50\). Αυτό γιατί κάθε φορά που κάνουμε την από πάνω διαδικασία σημειώνουμε τον μικρότερο αριθμό στο κελί που διαλέξαμε.
Και όπως βρήκαμε πριν ο μικρότερος ήταν αυτός της \(\textrm{Προσφοράς}\) οπότε τον βάζουμε στην θέση του \(20\).
Επαναλαμβάνουμε την διαδικασία:
Διαλέγουμε πάλι το τέρμα πάνω και αριστερά κελί (που δεν έχουμε ήδη χρησιμοποιήσει) και στην περίπτωση μας είναι το κελί (2,1). Τώρα συγκρίνουμε πάλι \(\textrm{Ζήτηση}\) με \(\textrm{Προσφορά}\):
\[\textrm{Ζήτηση} = 30\] \[\textrm{Προσφορά} = 80\]Βλέπουμε ότι \(\textrm{Ζήτηση} < \textrm{Προσφορά}\) οπότε διαλέγουμε την \(\textrm{Ζήτηση}\).
Οπότε κάνουμε τις πράξεις \(\textrm{Ζήτηση} - \textrm{Ζήτηση}\) και \(\textrm{Προσφορά} - \textrm{Ζήτηση}\) και απλά φτιάχνουμε τον πίνακα:
Σημείωση: Θα έχω με πορτοκαλί τα κελιά που έχουμε ήδη χρησιμοποιήσει.
Επαναλαμβάνουμε την διαδικασία:
Διαλέγουμε πάλι το τέρμα πάνω και αριστερά κελί (που δεν έχουμε ήδη χρησιμοποιήσει) και στην περίπτωση μας είναι το κελί (2,2). Τώρα συγκρίνουμε πάλι \(\textrm{Ζήτηση}\) με \(\textrm{Προσφορά}\):
\[\textrm{Ζήτηση} = 80\] \[\textrm{Προσφορά} = 50\]Βλέπουμε ότι \(\textrm{Ζήτηση} > \textrm{Προσφορά}\) οπότε διαλέγουμε την \(\textrm{Προσφορά}\).
Και κάνουμε τις πράξεις \(\textrm{Προσφορά} - \textrm{Προσφορά}\) και \(\textrm{Ζήτηση} - \textrm{Προσφορά}\) και απλά φτιάχνουμε τον πίνακα:
Επαναλαμβάνουμε την διαδικασία:
Διαλέγουμε πάλι το τέρμα πάνω και αριστερά κελί (που δεν έχουμε ήδη χρησιμοποιήσει) και στην περίπτωση μας είναι το κελί (3,2). Τώρα συγκρίνουμε πάλι \(\textrm{Ζήτηση}\) με \(\textrm{Προσφορά}\):
\[\textrm{Ζήτηση} = 30\] \[\textrm{Προσφορά} = 50\]Βλέπουμε ότι \(\textrm{Ζήτηση} < \textrm{Προσφορά}\) οπότε διαλέγουμε την \(\textrm{Ζήτηση}\).
Και κάνουμε τις πράξεις \(\textrm{Ζήτηση} - \textrm{Ζήτηση}\) και \(\textrm{Προσφορά} - \textrm{Ζήτηση}\) και απλά φτιάχνουμε τον πίνακα:
Επαναλαμβάνουμε την διαδικασία:
Διαλέγουμε πάλι το τέρμα πάνω και αριστερά κελί (που δεν έχουμε ήδη χρησιμοποιήσει) και στην περίπτωση μας είναι το κελί (3,3). Τώρα συγκρίνουμε πάλι \(\textrm{Ζήτηση}\) με \(\textrm{Προσφορά}\):
\[\textrm{Ζήτηση} = 20\] \[\textrm{Προσφορά} = 20\]Βλέπουμε ότι \(\textrm{Ζήτηση} = \textrm{Προσφορά}\) οπότε δεν έχει σημασία πιο θα διαλέξουμε.
Και κάνουμε τις πράξεις \(\textrm{Ζήτηση} - \textrm{Ζήτηση}\) και \(\textrm{Προσφορά} - \textrm{Ζήτηση}\) και απλά φτιάχνουμε τον πίνακα:
Πλέον δεν έχουμε άλλο κελί να διαλέξουμε καθώς \(\textrm{Ζήτηση}\) και \(\textrm{Προσφορά}\) είναι \(0\).
Τώρα φτιάχνουμε τον πίνακα με τις καινούριες τιμές (στην ουσία καθαρίζουμε λίγο τον από πάνω πίνακα).
Ο νέος πίνακας θα είναι αυτός:
Αυτή είναι η βασική λύση του προβλήματος (κανονικά τώρα θα έπρεπε να δούμε αν είναι και βέλτιστη αλλά αυτό θα το κάνουμε αργότερα).
- Μέθοδος Ελαχίστου Κόστους
Έστω ότι έχουμε τον πίνακα:
| D1 | D2 | D3 | Προσφορά | |
|---|---|---|---|---|
| S1 | 20 | 11 | 10 | 50 |
| S2 | 8 | 12 | 7 | 80 |
| S3 | 9 | 10 | 7 | 50 |
| Ζήτηση | 80 | 80 | 20 |
Στη μέθοδο αυτή διαλέγουμε κάθε φορά το κελί με την μικρότερη αριθμητική τιμή. Μετά κάνουμε την ίδια διαδικασία με αυτή της Βορειοδυτικής Γωνίας.
Στην ουσία το μόνο που αλλάζει είναι ο τρόπος επιλογής του κελιού.
Στην περίπτωση μας η μικρότερη τιμή του πίνακα είναι ο αριθμός $7$. Αλλά παρουσιάζεται σε δύο κελιά, είμαστε ελεύεθεροι να διαλέξουμε όποιο από τα δύο θέλουμε.
Τώρα συγκρίνουμε τις τιμές της \(\textrm{Ζήτησης}\) και της \(\textrm{Προσφοράς}\).
\[\textrm{Ζήτηση} = 20\] \[\textrm{Προσφορά} = 80\]Παρατηρούμε ότι \(\textrm{Ζήτηση} < \textrm{Προσφορά}\) άρα διαλέγουμε την \(\textrm{Ζήτηση}\) και κάνουμε τις εξής πράξεις:
\[\textrm{Ζήτηση} - \textrm{Ζήτηση} = 20 - 20 = 0\] \[\textrm{Προσφορά} - \textrm{Ζήτηση} = 80 - 20 = 60\]Οπότε θα έχουμε τον εξής πίνακα:
Επαναλαμβάνουμε την διαδικασία:
Διαλέγουμε πάλι το κελί με την μικρότερη αριθμητική τιμή (που δεν έχουμε ήδη χρησιμοποιήσει) και στην περίπτωση μας είναι το κελί (2,1). Τώρα συγκρίνουμε πάλι \(\textrm{Ζήτηση}\) με \(\textrm{Προσφορά}\):
\[\textrm{Ζήτηση} = 80\] \[\textrm{Προσφορά} = 60\]Βλέπουμε ότι \(\textrm{Ζήτηση} > \textrm{Προσφορά}\) οπότε διαλέγουμε την \(\textrm{Προσφορά}\).
Και κάνουμε τις πράξεις \(\textrm{Προσφορά} - \textrm{Προσφορά}\) και \(\textrm{Ζήτηση} - \textrm{Προσφορά}\) και απλά φτιάχνουμε τον πίνακα:
Επαναλαμβάνουμε την διαδικασία:
Διαλέγουμε πάλι το κελί με την μικρότερη αριθμητική τιμή (που δεν έχουμε ήδη χρησιμοποιήσει) και στην περίπτωση μας είναι το κελί (3,1). Τώρα συγκρίνουμε πάλι \(\textrm{Ζήτηση}\) με \(\textrm{Προσφορά}\):
\[\textrm{Ζήτηση} = 20\] \[\textrm{Προσφορά} = 50\]Βλέπουμε ότι \(\textrm{Ζήτηση} < \textrm{Προσφορά}\) οπότε διαλέγουμε την \(\textrm{Ζήτηση}\).
Και κάνουμε τις πράξεις \(\textrm{Ζήτηση} - \textrm{Ζήτηση}\) και \(\textrm{Προσφορά} - \textrm{Ζήτηση}\) και απλά φτιάχνουμε τον πίνακα:
Επαναλαμβάνουμε την διαδικασία:
Διαλέγουμε πάλι το κελί με την μικρότερη αριθμητική τιμή (που δεν έχουμε ήδη χρησιμοποιήσει) και στην περίπτωση μας είναι το κελί (3,2). Τώρα συγκρίνουμε πάλι \(\textrm{Ζήτηση}\) με \(\textrm{Προσφορά}\):
\[\textrm{Ζήτηση} = 80\] \[\textrm{Προσφορά} = 30\]Βλέπουμε ότι $\textrm{Ζήτηση} > \textrm{Προσφορά}$ οπότε διαλέγουμε την $\textrm{Προσφορά}$.
Και κάνουμε τις πράξεις $\textrm{Προσφορά} - \textrm{Προσφορά}$ και $\textrm{Ζήτηση} - \textrm{Προσφορά}$ και απλά φτιάχνουμε τον πίνακα:
Επαναλαμβάνουμε την διαδικασία:
Διαλέγουμε πάλι το κελί με την μικρότερη αριθμητική τιμή (που δεν έχουμε ήδη χρησιμοποιήσει) και στην περίπτωση μας είναι το κελί (1,2). Τώρα συγκρίνουμε πάλι $\textrm{Ζήτηση}$ με $\textrm{Προσφορά}$:
\[\textrm{Ζήτηση} = 50 \\ \textrm{Προσφορά} = 50 \\\]Βλέπουμε ότι $\textrm{Ζήτηση} = \textrm{Προσφορά}$ οπότε δεν έχει σημασία πιο θα διαλέξουμε.
Και κάνουμε τις πράξεις $\textrm{Ζήτηση} - \textrm{Ζήτηση}$ και $\textrm{Προσφορά} - \textrm{Ζήτηση}$ και απλά φτιάχνουμε τον πίνακα:
Πλέον δεν έχουμε άλλο κελί να διαλέξουμε καθώς $\textrm{Ζήτηση}$ και $\textrm{Προσφορά}$ είναι $0$.
Τώρα φτιάχνουμε τον πίνακα με τις καινούριες τιμές (στην ουσία καθαρίζουμε λίγο τον από πάνω πίνακα).
Ο νέος πίνακας θα είναι αυτός:
Αυτή είναι η βασική λύση του προβλήματος (κανονικά τώρα θα έπρεπε να δούμε αν είναι και βέλτιστη αλλά αυτό θα το κάνουμε αργότερα).
Πρόβλημα Ανάθεσης
Αυτά τα προβλήματα είναι αρκετά εύκολα και σε αντίθεση με τα προβλήματα μεταφοράς λύνονται με έναν αλγόριθμο τον Ουγγρικό Αλγόριθμο.
Έστω ότι πρέπει να βρούμε την ανάθεση ελαχίστου κόστους στον ακόλουθο πίνακα:
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| Α | 9 | 6 | 5 | 6 |
| Β | 6 | 8 | 9 | 5 |
| Γ | 8 | 7 | 6 | 8 |
| Δ | 7 | 7 | 8 | 5 |
Το πρώτο πράγμα που κάνουμε είναι να τσεκάρουμε άν ο αριθμός των Γραμμών είναι ίσος με τον αριθμό των Στηλών.
Στην περίπτωση μας είναι ίσοι αφού $4=4$.
</br>
Τώρα πρέπει να βρούμε την μικρότερη αριθμιτική τιμή του πίνακα σε κάθε γραμμή.
Αφότου την βρούμε την αφαιρούμε από κάθε κελί σε εκείνη την γραμμή.
Δηλαδή οι πράξεις για την πρώτη γραμμή είναι:
\[9 - 5 = 4 \\ 6 - 5 = 1 \\ 5 - 5 = 0 \\ 6 - 5 = 1\]Ο νέος πίνακας θα είναι αυτός:
</br> </br>
Τώρα πρέπει να κάνουμε την ίδια διαδικασία για κάθε στήλη.
</br>
Βρήκαμε την μικρότερη αριθμητική τιμή για κάθε στήλη και τώρα κάνουμε τις πράξεις. Ο νέος πίνακας θα είναι:
Στον πίνακα αυτό πάμε και κυκλώνουμε/πλαισιώνουμε ένα μηδενικό για κάθε γραμμή/στήλη.
Δηλαδή αν πλαισιώσουμε το μηδενικό στο κελί $(1,2)$ δεν θα μπορέσουμε να πλαισιώσουμε άλλο μηδενικό στην γραμμή $1$ ή στην στήλη $2$.
Επιλέγουμε τα μηδενικά έτσι ώστε να ισχύει:
\[\textrm{Πλήθος Πλαισιωμένων Μηδενικών = Πλήθος Γραμμών}\]Αν ισχύει το από πάνω σταματάμε, αν όμως βρούμε μικρότερο αριθμό πλαισιωμένων μηδενικών συνεχίζουμε.
</br>
Στην περίπτωση μας έχουμε:
Έχουμε $\textrm{Πλήθος Πλαισιωμένων Μηδενικών = Πλήθος Γραμμών}$ αφού $4=4$.
</br>
Τώρα μηδενίζουμε όλων τον πίνακα εκτός από τα πλαισιωμένα μηδενικά τα οποία γίνονται $1$.
Βρήκαμε την λύση, το μόνο που μένει είναι να πάμε στον αρχικό πίνακα και να σημειώσουμε τις τιμές όπου στον τελικό μας πίνακα έχουμε $1$.
Οπότε η λύση του προβλήματος είναι:
\[Α = 6 \\ Β = 6 \\ Γ = 6 \\ Δ = 5\]Και το συνολικό κόστος είναι:
\[z = Α + Β + Γ + Δ = 6 + 6 + 6 + 5 = 23\]</br>
Σημείωση: Αν πάμε πίσω στο σημείο που πλαισιώνουμε τα μηδενικά…
Μπορούμε να δούμε ότι υπάρχει και άλλη επιλογή πέρα από αυτή που βρήκαμε.
Δηλαδή μπορούμε να πλαισιώσουμε και έτσι:
</br>
Τώρα κάνουμε την διαδικασία που μηδενίζουμε όλο τον πίνακα εκτός από τα πλαισιωμένα μηδενικά:
Οπότε η εναλλακτική λύση του προβλήματος είναι:
\[Α = 5 \\ Β = 6 \\ Γ = 7 \\ Δ = 5\]Και το συνολικό κόστος είναι:
\[z = Α + Β + Γ + Δ = 5 + 6 + 7 + 5 = 23\]Το συμπέρασμα είναι ότι το πρόβλημα έχει δύο λύσεις που προφανώς βγάζουν το ίδιο αποτέλεσμα.
Γενικά είναι καλό να ψάχνουμε αν το πρόβλημα έχει εναλλακτική λύση.
</br>
- Ειδικές περιπτώσεις στο πρόβλημα ανάθεσης
- Να βρεθεί η ανάθεση μέγιστης απόδοσης.
- Γραμμές και στήλες να μην είναι ίσες.
Ας αρχίσουμε με την πρώτη περίπτωση καθώς δεν αλλάζει σχεδόν τίποτα με όσα έχουμε ήδη κάνει.
</br>
Έστω ότι έχουμε τον ακόλουθο πίνακα και πρέπει να βρούμε την ανάθεση μέγιστης απόδοσης:
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| Α | 12 | 17 | 15 | 16 | 14 |
| Β | 11 | 14 | 10 | 12 | 15 |
| Γ | 16 | 12 | 16 | 17 | 18 |
| Δ | 15 | 15 | 13 | 14 | 18 |
| Ε | 13 | 14 | 16 | 18 | 14 |
Το πρώτο πράγμα που κάνουμε είναι να ελέγξουμε όπως και πριν αν έχουμε το πλήθος των γραμμών είναι ίσο με αυτό των στηλών.
Στην δική μας περίπτωση είναι καθώς $\textrm{Γραμμές} = 5$ και $\textrm{Στήλες} = 5$.
</br>
Τώρα πρέπει να βρούμε την μέγιστη αριθμητική του πίνακα και μετά να αφαιρέσουμε τον πίνακα από αυτή, δηλαδή:
Η μέγιστη αριθμητική τιμή του πίνακα είναι: $\textrm{max} = 18$.
Εμείς απλά πρέπει να κάνουμε την πράξη: $\textrm{max} - \textrm{matrix}_{i,j}$.
</br>
Για παράδειγμα η πρώτη γραμμή μετά την από πάνω πράξη θα γίνει έτσι:
\[18 - 12 = 6 \\ 18 - 17 = 1 \\ 18 - 15 = 3 \\ 18 - 16 = 2 \\ 18 - 14 = 4\]</br>
Οπότε ο νέος πίνακας θα είναι:
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| Α | 6 | 1 | 3 | 2 | 4 |
| Β | 7 | 4 | 8 | 6 | 3 |
| Γ | 2 | 6 | 2 | 1 | 0 |
| Δ | 3 | 3 | 5 | 4 | 0 |
| Ε | 5 | 4 | 2 | 0 | 4 |
</br>
Από εδώ και πέρα η διαδικασία είναι ακριβώς η ίδια με το προηγούμενο παράδειγμα που λύσαμε, δηλαδή:
Βρίσκουμε την μικρότερη αριθμιτική τιμή του πίνακα σε κάθε γραμμή και μετά την αφαιρούμε από την αντίστοιχη γραμμή.
</br>
Δηλαδή οι πράξεις για την πρώτη γραμμή είναι:
\[6 - 1 = 5 \\ 1 - 1 = 0 \\ 3 - 1 = 2 \\ 2 - 1 = 1 \\ 4 - 1 = 3\]Και ο νέος πίνακας θα είναι αυτός:
</br>
Τώρα πρέπει να κάνουμε την ίδια διαδικασία για κάθε στήλη του πίνακα:
</br>
Κάνουμε τις πράξεις και δημιουργούμε τον καινούριο πίνακα:
</br>
Σε αυτόν τον πίνακα πάμε και κυκλώνουμε/πλαισιώνουμε ένα μηδενικό για κάθε γραμμή/στήλη.
Δηλαδή αν πλαισιώσουμε το μηδενικό στο κελί $(3,1)$ δεν θα μπορέσουμε να πλαισιώσουμε άλλο μηδενικό στην γραμμή $3$ ή στην στήλη $1$.
Επιλέγουμε τα μηδενικά έτσι ώστε να ισχύει:
\[\textrm{Πλήθος Πλαισιωμένων Μηδενικών = Πλήθος Γραμμών}\]Αν ισχύει το από πάνω σταματάμε, αν όμως βρούμε μικρότερο αριθμό πλαισιωμένων μηδενικών συνεχίζουμε.
</br>
Στην περίπτωση μας όμως έχουμε:
Αυτό που πρέπει να κάνουμε είναι περάσουμε με γραμμές τον πίνακα έτσι ώστε να έχουμε καλύψει όλα τα μηδενικά του πίνακα (με όσο το δυνατόν λιγότερες γραμμές γίνεται).
</br>
Καλύψαμε λοιπόν όλα τα μηδενικά του πίνακα και ο αριθμός των γραμμών που χρειαστήκαμε είναι $4$.
Τώρα αυτό που πρέπει να κάνουμε είναι να βρούμε το μικρότερο στοιχείο από τα μη καλυμμένα στοιχεία του πίνακα.
</br>
Στην περίπτωση μας είναι ο αριθμός $1$. Αφότου τον βρούμε απλά τον αφαιρούμε από όλα τα μη καλυμμένα στοιχεία και τον προσθέτουμε στα διπλά καλυμμένα στοιχεία του πίνακα.
Σημείωση: Με μπλε είναι τα μη καλυμμένα στοιχεία ενώ με πορτοκαλί είναι τα διπλά καλυμμένα στοιχεία.
</br>
Δηλαδή ο πίνακας μας θα είναι ο εξής μετά τις πράξεις:
Τώρα επαναλαμβάνουμε την διαδικασία των πλαισιωμένων μηδενικών.
</br>
Οπότε θα έχουμε τον ακόλουθο πίνακα:
</br>
Οπότε τώρα κάνουμε την διαδικασία όπου μηδενίζουμε όλα τα στοιχεία του πίνακα εκτός από τα πλαισωμένα μηδενικά τα οποία γίνονται $1$.
Πάω στο επόμενο βήμα κατευθέιαν (κανονικά όμως πρέπει να φαίνεται).
Το αποτέλεσμα είναι:
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| Α | 0 | 17 | 0 | 0 | 0 |
| Β | 0 | 0 | 0 | 0 | 15 |
| Γ | 0 | 0 | 16 | 0 | 0 |
| Δ | 15 | 0 | 0 | 0 | 0 |
| Ε | 0 | 0 | 0 | 18 | 0 |
Και το συνολικό κόστος είναι:
\[z = Α + Β + Γ + Δ + Ε = 17 + 15 + 16 + 15 + 18 = 81\]