Προβλήματα Ελαχιστοποίησης – Δυϊκό Πρόβλημα
Μέχρι εδώ παρουσιάστηκε αναλυτικά και με παραδείγματα η μέθοδος Simplex για τα προβλήματα μεγιστοποίησης του «κέρδους», δηλ., για τα προβλήματα που έχουν τους περιορισμούς με « ≤ » και την αντικειμενική συνάρτηση « max(P) ».
Η άλλη μεγάλη κατηγορία προβλημάτων είναι τα προβλήματα ελαχιστοποίησης του «κόστους», δηλ., τα προβλήματα που έχουν τους περιορισμούς με « ≥ » και την αντικειμενική συνάρτηση « min(C) ».
Όπως αποδεικνύεται θεωρητικά, για κάθε πρόβλημα ελαχιστοποίησης μπορεί να διατυπωθεί ένα αντίστοιχο πρόβλημα μεγιστοποίησης το οποίο λέγεται δυϊκό πρόβλημα. Όταν λύσουμε το δυϊκό πρόβλημα μεγιστοποίησης με τη μέθοδο Simplex, έχουμε ταυτόχρονα λύσει και το αρχικό πρόβλημα ελαχιστοποίησης.
Έστω ότι μας δίνεται ένα ΠΓΠ ελαχιστοποίησης όπως το παρακάτω:
ΥΤΠ:
2·Χ1 + 5·Χ2 ≥ 50
Χ1 + 3·Χ2 ≥ 27
Χ1, Χ2 ≥ 0
ΑΣ:
Να ελαχιστοποιηθεί το: C = 16·Χ1 + 45·Χ2
Το Δυϊκό Πρόβλημα ορίζεται ως εξής: α) γράφουμε τους συντελεστές των περιορισμών και του κόστους σε μορφή πίνακα, β) βρίσκουμε τον ανάστροφό του, και, γ) από τον νέο πίνακα ξαναδημιουργούμε νέους περιορισμούς με ≤ και την νέα ΑΣ κέρδους P:
| 2·Χ1 + 5·Χ2 ≥ 50 Χ1 + 3·Χ2 ≥ 27 16·Χ1 + 45·Χ2 = C |
=> | 2 5 50 1 3 27 16 45 C |
Αναστροφή => |
2 1 16 5 3 45 50 27 P |
=> | 2·Y1 + Y2 ≤ 16 5·Y1 + 3·Y2 ≤ 45 50·Y1 + 27·Y2 = P |
ΥΤΠ:
2·Y1 + Y2 ≤ 16
5·Y1 + 3·Y2 ≤ 45
Y1, Y2 ≥ 0
ΑΣ:
Να μεγιστοποιηθεί το: P = 50·Y1 + 27·Y2
Λύνοντας το δυϊκό πρόβλημα μεγιστοποίησης με τη μέθοδο Simplex, όταν βρούμε τη βέλτιστη λύση, οι μεταβλητές περιθωρίου θα περιέχουν τη βέλτιστη λύση του αρχικού προβλήματος ελαχιστοποίησης. Για το λόγο αυτό τις μεταβλητές περιθωρίου τις ονομάζουμε με Χ1, Χ2, κλπ., αντί των S1, S2, κλπ.
ΠΑΡΑΔΕΙΓΜΑ ΛΥΣΗΣ
Αν λύσουμε το παραπάνω παράδειγμα θα έχουμε:
Αρχικό Σύστημα Simplex:
2·Y1 + Y2 + Χ1 = 16
5·Y1 + 3·Y2 + Χ2 = 45
- 50·Y1 - 27·Y2 + P = 0
Αρχικός Πίνακας Simplex:
| β.μ. | Y1 | Y2 | Χ1 | X2 | P | ||
| X1 | 2 | 1 | 1 | 0 | 0 | 16 | 16/2=8 |
| X2 | 5 | 3 | 0 | 1 | 0 | 45 | 45/5=9 |
| P | -50 | -40 | 0 | 0 | 1 | 0 |
1η επανάληψη της Simplex:
| β.μ. | Y1 | Y2 | Χ1 | X2 | P | ||
| Y1 | 1 | ½ | ½ | 0 | 0 | 8 | 16 |
| X2 | 0 | ½ | -5/2 | 1 | 0 | 5 | 10 |
| P | 0 | -2 | 25 | 0 | 1 | 400 |
2η επανάληψη της Simplex:
| β.μ. | Y1 | Y2 | Χ1 | X2 | P | |
| Y1 | 1 | 0 | 3 | -1 | 0 | 3 |
| Y2 | 0 | 1 | -5 | 2 | 0 | 10 |
| P | 0 | 0 | 15 | 4 | 1 | 420 |
Το δυϊκό πρόβλημα έχει βέλτιστη λύση τη Y1 = 3, Y2 = 10 & P = 420,
Το αρχικό πρόβλημα ελαχιστοποίησης θα έχει βέλτιστη λύση τη Χ1 = 15, Χ2 = 4 & C = 420, η οποία δίνεται από τη τελευταία γραμμή του πίνακα Simplex της τελικής λύσης στις αντίστοιχες στήλες των μεταβλητών περιθωρίου.
