Τώρα έχουμε επιτέλους τα κατάλληλα εργαλεία (συγκεκριμένα την εξίσωση (4)), ώστε να λύσουμε ένα ΓΠ. Συγκεκριμένα ας θεωρήσουμε το ακόλουθο ΓΠ.:
(5) \(x_2, \geq 0\)
Ας ονομάσουμε την παραπάνω γραφή του ΓΠ (Π1). Δεν θα κάνουμε κάτι άλλο από το να υλοποιήσουμε την μέθοδο που περιγράψαμε στην Κεφάλαιο 2.0. Παρατηρούμε ότι η αρχή των αξόνων \( (x_1, x_2) = (0, 0) \) είναι μια λύση για το (Π1), με τιμή της συνάρτησης στόχου \( z = 0 \). Από γεωμετρικής άποψης για να συμβαίνει αυτό συμβαίνει επειδή η αρχή των αξόνων είναι μια κορυφή του πολυτόπου των περιορισμών.
Φυσικά στόχος μας είναι να αυξήσουμε την συνάρτηση στόχο, πως μπορούμε να το κάνουμε αυτό; Θα αυξήσουμε είτε την \(x_1\), είτε την \(x_2\). Ας προσπαθήσουμε με την \(x_1\). Πόσο; Όσο περισσότερο μπορούμε, ώστε να διατηρούνται οι περιορισμοί. Κρατάμε σταθερό το \(x_2\) σταθερό, \(x_2 = 0\).
(1) \( x_1 \leq 2 + \frac{x_2}{2} \) \(\overset{x_2 = 0}{=} 2 \)
(2) \( x_1 \leq 9 - 2x_2\) \(\overset{x_2 = 0}{=} 9\)
(3) \(x_1 \leq 3 + x_2\) \(\overset{x_2 = 0}{=} 3\)
Παρατηρούμε ότι \(x_1 \leq 2, x_1 \geq 3\). Άρα δεν μπορούμε να αυξήσουμε την \(x_1\) και να πάρουμε μία εφικτή λύση. Άρα μας μένει η \(x_2\), πάλι κρατάμε την \(x_1\) σταθερή, \(x_1 = 0\) έχουμε:
(1) \(x_2 \geq -4 + 2x_1\) \(\overset{x_1 = 0}{=} -4\)
(2) \(x_2 \leq 4.5 - \frac{x_1}{2}\) \(\overset{x_1 = 0}{=} 4.5\)
(3) \(x_2 \leq 3 + x_1\) \(\overset{x_1 = 0}{=} 3\)
Άρα \(x_2 \in [-4, 3]\), άρα θέτουμε \(x_2 = 3\) και έχουμε τιμή της συνάρτησης στόχου, \(z = 15\). Θα λέμε ότι η (3) είναι σφιχτή, έχουμε μετατρέψει την ανισότητα σε ισότητα:
$$ x_2 = 3 + x_1 $$
Η κορυφή που βρισκόμαστε δίνεται από τις εξισώσεις:
\(-x_1 + x_2 = 3\), \(x_1 = 0\)
Γεωμετρικά βρισκόμαστε στην κορυφή Β στα σχήματα 1, 2.
Οι εξισώσεις είναι σε Εσσιανή Κανονική Μορφή! Άρα μπορούμε να χρησιμοποιήσουμε τα αποτελέσματα του Κεφαλαίου 2 και ξέρουμε πως να δούμε τον κόσμο από τα μάτια της κορυφής Β (σαν να ήταν η αρχή των αξόνων), ας ονομάσουμε το σύστημα αξόνων όπου το B είναι η αρχή \(S_B\), ενώ τον χώρο που είμαστε τώρα θα το λέμε \(S_E\). Για κάθε σημείο \( (x_1, x_2) \) του \(S_E\) θα το απεικονίσουμε στο σημαίο \( (y_1, y_2) \) του \( S_B \), ως εξής:
\(y_1 = x_1 \)
\(y_2 = 3 + x_1 - x_2\)
λέμε τον παραπάνω μετασχηματισμό \((Μ)\). Αρκεί τώρα να ξαναγράψουμε το (Π1), λύνοντας τους μετασχηματισμούς \((Μ)\).
\(x_1 = y_1 \)
\(x_2 = -y_2 + y_1 + 3\)
οι παραπάνω εξισώσεις συνιστούν τον αντίστροφο μετασχηματισμό \((M^{-1})\).
σ.σ.: \(z = 2y_1 + 5(-y_2 + y_1 +3)\)
(1) \(2y_1 - (-y_2 + y_1 + 3) \leq 4\)
(2) \(y_1 + 2(-y_2 + y_1 + 3) \leq 9\)
(3) \(-y_1 + (-y_2 + y_1 + 3) \leq 3\)
(4) \(y_1 \geq 0\)
(5) \(-y_2 + y_1 + 3 \geq 0\)
ή
σ.σ.: \(z = 7y_1 -5y_2 +15\)
(1) \( y_2 \leq 5 \)
(2) \( 3y_1 - 2y_2 \leq 3 \)
(3) \(y_2 \geq 0 \)
(4) \( y_1 \geq 0 \)
(5) \(-y_1 + y_2 \geq 3 \)
το φέρνουμε σε πιο οικεία μορφή:
σ.σ.: \(z = 7y_1 -5y_2 +15\)
(1') \(y_2 \leq 5\)
(2') \( 3y_1 - 2y_2 \leq 3\)
(3') \(-y_1 + y_2 \leq 3\)
(4') \(y_1 \geq 0\)
(5') \(y_2 \geq 0\)
Ονομάζουμε την μορφή αυτή του ΓΠ (Π2). Ας κάνουμε τώρα μερικές παρατηρήσεις:
Επαναλαμβάνοντας την διαδικασία μπορούμε να πάμε από το (Π2) στο (Π3), το οποίο παραθέτουμε παρακάτω:
σ.σ.: \(z = 22 - \frac{7}{3}z_1 - \frac{1}{3}z_2\)
υ.π.
(1'') \(-\frac{1}{3}z_1 + \frac{5}{3} \leq 6\)
(2'') \(\frac{1}{3}z_1 - \frac{2}{3}z_2 \leq 1\)
(3'') \(\frac{1}{3}z_1 + \frac{1}{3}z_2 \leq 4\)
(4'') \(z_1 \geq 0\)
(5'') \(z_2 \geq 0\)
και οι μετασχηματισμοί (M') που μας πήγαν από το (Π2) στο (Π3) είναι:
\(z_1 = 3 - 3y_1 + 2y_2\)
\(z_2 = y_2\)
Μην γίνεται σύγχυση του z (της τιμής της συνάρτησης στόχου) και των μεταβλητών \(z_i\) του (Π3). Εδώ παρατηρούμε ότι για κανένα θετικό \(z_1, z_2\) δεν μπορούμε να αυξήσουμε την τιμή της συνάρτησης στόχου. Άρα έχουμε τελειώσει! Η βέλτιστη τιμή της συνάρτησης στόχου είναι 22. Η τιμή που μας δίνει την βέλτιστη λύση στο (Π3) είναι φυσικά η \((0, 0)\), όμως μπορούμε να χρησιμοποιήσουμε τους μετασχηματισμούς (Μ), (Μ') για να βρούμε την λύση στο (Π1), η οποία θα είναι η \((x_1, x_2) = (1, 4)\). Η αναγνώστρια καλείται να επαληθεύσει αυτούς τους ισχυρισμούς.
Παρακάτω βλέπουμε σχηματικά την πορεία που ακολούθησε η μέθοδος Simplex στο πολύτοπο του (Π1). Όπως βλέπουμε σταματάει στην κορυφή Δ, η οποία πράγματι είναι η κορυφή που δίνει την βέλτιστη λύση, όπως μπορούμε να επαλυθεύσουμε και με την χρήση της γραφικής μεθόδου (Κεφάλαιο 1).
Τώρα πια μπορούμε να λύσουμε ένα γενικό ΓΠ, οσοδήποτε μεταβλητών. Στο επόμενο μέρος του Κεφαλαίου 3 θα δούμε την γεωμετρική ερμηνεία πίσω από τις αλγεβρικές πράξεις που είδαμε εδώ.
Σημειώσεις:
Αν δεν εμφανίζονται σωστά τα μαθηματικά σύμβολα, παρακαλώ πατήστε Ctrl+F5.
Τα σχήματα έγιναν με το GeoGebra5. Το πρόγραμμα διατίθεται για Windows, Mac και Linux
Για μαθηματικά σύμβολα στο blogger ακολούθησα αυτές εδώ τις οδηγίες.
Βιβλιογραφία:
[1] Το πρόβλημα πάρθηκε από το βιβλίο Αλγόριθμοι των Sanjoi Dasqupta, Christos Papadimitriou, Umesh Vazirani, εκδόσεις Κλειδάριθμος
Πλοήγηση
\(max\) \(z = 2x_1 + 5x_2\)
υ.π.:
(1) \(2x_1 - x_2 \leq 4\)
(2) \(x_1 + 2x_2 \leq 9\)
(3) \(-x_1 + x_2 \leq 3\)
(4) \(x_1, \geq 0\)(5) \(x_2, \geq 0\)
Ας ονομάσουμε την παραπάνω γραφή του ΓΠ (Π1). Δεν θα κάνουμε κάτι άλλο από το να υλοποιήσουμε την μέθοδο που περιγράψαμε στην Κεφάλαιο 2.0. Παρατηρούμε ότι η αρχή των αξόνων \( (x_1, x_2) = (0, 0) \) είναι μια λύση για το (Π1), με τιμή της συνάρτησης στόχου \( z = 0 \). Από γεωμετρικής άποψης για να συμβαίνει αυτό συμβαίνει επειδή η αρχή των αξόνων είναι μια κορυφή του πολυτόπου των περιορισμών.
 | |
| Σχήμα1: Το πολύτοπο του ΓΠ (Π1), ως τομή ημιεπιπέδων |
 |
| Σχήμα 2: Το πολύτοπο του ΓΠ (Π1) |
Φυσικά στόχος μας είναι να αυξήσουμε την συνάρτηση στόχο, πως μπορούμε να το κάνουμε αυτό; Θα αυξήσουμε είτε την \(x_1\), είτε την \(x_2\). Ας προσπαθήσουμε με την \(x_1\). Πόσο; Όσο περισσότερο μπορούμε, ώστε να διατηρούνται οι περιορισμοί. Κρατάμε σταθερό το \(x_2\) σταθερό, \(x_2 = 0\).
(1) \( x_1 \leq 2 + \frac{x_2}{2} \) \(\overset{x_2 = 0}{=} 2 \)
(2) \( x_1 \leq 9 - 2x_2\) \(\overset{x_2 = 0}{=} 9\)
(3) \(x_1 \leq 3 + x_2\) \(\overset{x_2 = 0}{=} 3\)
Παρατηρούμε ότι \(x_1 \leq 2, x_1 \geq 3\). Άρα δεν μπορούμε να αυξήσουμε την \(x_1\) και να πάρουμε μία εφικτή λύση. Άρα μας μένει η \(x_2\), πάλι κρατάμε την \(x_1\) σταθερή, \(x_1 = 0\) έχουμε:
(1) \(x_2 \geq -4 + 2x_1\) \(\overset{x_1 = 0}{=} -4\)
(2) \(x_2 \leq 4.5 - \frac{x_1}{2}\) \(\overset{x_1 = 0}{=} 4.5\)
(3) \(x_2 \leq 3 + x_1\) \(\overset{x_1 = 0}{=} 3\)
Άρα \(x_2 \in [-4, 3]\), άρα θέτουμε \(x_2 = 3\) και έχουμε τιμή της συνάρτησης στόχου, \(z = 15\). Θα λέμε ότι η (3) είναι σφιχτή, έχουμε μετατρέψει την ανισότητα σε ισότητα:
$$ x_2 = 3 + x_1 $$
Η κορυφή που βρισκόμαστε δίνεται από τις εξισώσεις:
\(-x_1 + x_2 = 3\), \(x_1 = 0\)
Γεωμετρικά βρισκόμαστε στην κορυφή Β στα σχήματα 1, 2.
Οι εξισώσεις είναι σε Εσσιανή Κανονική Μορφή! Άρα μπορούμε να χρησιμοποιήσουμε τα αποτελέσματα του Κεφαλαίου 2 και ξέρουμε πως να δούμε τον κόσμο από τα μάτια της κορυφής Β (σαν να ήταν η αρχή των αξόνων), ας ονομάσουμε το σύστημα αξόνων όπου το B είναι η αρχή \(S_B\), ενώ τον χώρο που είμαστε τώρα θα το λέμε \(S_E\). Για κάθε σημείο \( (x_1, x_2) \) του \(S_E\) θα το απεικονίσουμε στο σημαίο \( (y_1, y_2) \) του \( S_B \), ως εξής:
\(y_1 = x_1 \)
\(y_2 = 3 + x_1 - x_2\)
λέμε τον παραπάνω μετασχηματισμό \((Μ)\). Αρκεί τώρα να ξαναγράψουμε το (Π1), λύνοντας τους μετασχηματισμούς \((Μ)\).
\(x_1 = y_1 \)
\(x_2 = -y_2 + y_1 + 3\)
οι παραπάνω εξισώσεις συνιστούν τον αντίστροφο μετασχηματισμό \((M^{-1})\).
σ.σ.: \(z = 2y_1 + 5(-y_2 + y_1 +3)\)
(1) \(2y_1 - (-y_2 + y_1 + 3) \leq 4\)
(2) \(y_1 + 2(-y_2 + y_1 + 3) \leq 9\)
(3) \(-y_1 + (-y_2 + y_1 + 3) \leq 3\)
(4) \(y_1 \geq 0\)
(5) \(-y_2 + y_1 + 3 \geq 0\)
ή
σ.σ.: \(z = 7y_1 -5y_2 +15\)
(1) \( y_2 \leq 5 \)
(2) \( 3y_1 - 2y_2 \leq 3 \)
(3) \(y_2 \geq 0 \)
(4) \( y_1 \geq 0 \)
(5) \(-y_1 + y_2 \geq 3 \)
το φέρνουμε σε πιο οικεία μορφή:
σ.σ.: \(z = 7y_1 -5y_2 +15\)
(1') \(y_2 \leq 5\)
(2') \( 3y_1 - 2y_2 \leq 3\)
(3') \(-y_1 + y_2 \leq 3\)
(4') \(y_1 \geq 0\)
(5') \(y_2 \geq 0\)
Ονομάζουμε την μορφή αυτή του ΓΠ (Π2). Ας κάνουμε τώρα μερικές παρατηρήσεις:
- Για \((y_1, y_2) = (0, 0)\) η συνάρτηση στόχος του (Π2) μας δίνει \(z = 15\), ότι παίρναμε και στο (Π1) για \( (x_1, x_2) = (0, 2) \).
- Οι σφιχτές εξισώσεις του (Π1), (3), (4), είναι αυτές που μας έδωσαν τους περιορισμούς πρόσημου (4'), (5').
- Η \((y_1, y_2) = (0, 0)\) είναι πάλι μια εφικτή λύση του (Π2).
 |
| Σχήμα 3: Το πολύτοπο των εφικτών λύσεων του (Π2), σαν τομή ημιεπιπέδων |
 |
| Σχήμα 4: Το πολύτοπο των εφικτών λύσεων του (Π2) |
Επαναλαμβάνοντας την διαδικασία μπορούμε να πάμε από το (Π2) στο (Π3), το οποίο παραθέτουμε παρακάτω:
σ.σ.: \(z = 22 - \frac{7}{3}z_1 - \frac{1}{3}z_2\)
υ.π.
(1'') \(-\frac{1}{3}z_1 + \frac{5}{3} \leq 6\)
(2'') \(\frac{1}{3}z_1 - \frac{2}{3}z_2 \leq 1\)
(3'') \(\frac{1}{3}z_1 + \frac{1}{3}z_2 \leq 4\)
(4'') \(z_1 \geq 0\)
(5'') \(z_2 \geq 0\)
και οι μετασχηματισμοί (M') που μας πήγαν από το (Π2) στο (Π3) είναι:
\(z_1 = 3 - 3y_1 + 2y_2\)
\(z_2 = y_2\)
Μην γίνεται σύγχυση του z (της τιμής της συνάρτησης στόχου) και των μεταβλητών \(z_i\) του (Π3). Εδώ παρατηρούμε ότι για κανένα θετικό \(z_1, z_2\) δεν μπορούμε να αυξήσουμε την τιμή της συνάρτησης στόχου. Άρα έχουμε τελειώσει! Η βέλτιστη τιμή της συνάρτησης στόχου είναι 22. Η τιμή που μας δίνει την βέλτιστη λύση στο (Π3) είναι φυσικά η \((0, 0)\), όμως μπορούμε να χρησιμοποιήσουμε τους μετασχηματισμούς (Μ), (Μ') για να βρούμε την λύση στο (Π1), η οποία θα είναι η \((x_1, x_2) = (1, 4)\). Η αναγνώστρια καλείται να επαληθεύσει αυτούς τους ισχυρισμούς.
Παρακάτω βλέπουμε σχηματικά την πορεία που ακολούθησε η μέθοδος Simplex στο πολύτοπο του (Π1). Όπως βλέπουμε σταματάει στην κορυφή Δ, η οποία πράγματι είναι η κορυφή που δίνει την βέλτιστη λύση, όπως μπορούμε να επαλυθεύσουμε και με την χρήση της γραφικής μεθόδου (Κεφάλαιο 1).
 | |
| Σχήμα 5: Η πορεία την μεθόδου Simplex |
 |
| Σχήμα 6: Γραφική επίλυση του (Π1) - Επαλήθευση μεθόδου Simplex |
Τώρα πια μπορούμε να λύσουμε ένα γενικό ΓΠ, οσοδήποτε μεταβλητών. Στο επόμενο μέρος του Κεφαλαίου 3 θα δούμε την γεωμετρική ερμηνεία πίσω από τις αλγεβρικές πράξεις που είδαμε εδώ.
Σημειώσεις:
Αν δεν εμφανίζονται σωστά τα μαθηματικά σύμβολα, παρακαλώ πατήστε Ctrl+F5.
Τα σχήματα έγιναν με το GeoGebra5. Το πρόγραμμα διατίθεται για Windows, Mac και Linux
Για μαθηματικά σύμβολα στο blogger ακολούθησα αυτές εδώ τις οδηγίες.
Βιβλιογραφία:
[1] Το πρόβλημα πάρθηκε από το βιβλίο Αλγόριθμοι των Sanjoi Dasqupta, Christos Papadimitriou, Umesh Vazirani, εκδόσεις Κλειδάριθμος
Πλοήγηση
Σχόλια
Δημοσίευση σχολίου