Στο προηγούμενο κεφάλαιο είχαμε δει πως περνάμε από το πρόβλημα σε φυσική γλώσσα σε μια αυστηρή μαθηματική διατύπωση. Είχαμε πει ότι από την στιγμή που γίνει αυτό μπορούμε ουσιαστικά να ξεχάσουμε το αρχικό πρόβλημα και να λύσουμε την μαθηματική μοντελοποίησή του, το ΓΠ. Μια λύση του ΓΠ θα είναι και μια λύση του αρχικού προβλήματος, αν έχουμε κάνει σωστά την μετάβαση.
Το ΓΠ στο οποίο καταλήξαμε την προηγούμενη φορά είναι το εξής:
Στο Σχήμα 1 έχουμε σχεδιάσει την ε1 με μπλε, την ε2 με πράσινο και την ε3 με πορτοκαλί, ενώ τους άξονες α1, α2 με μαύρο. Όμως στο ΓΠ δεν έχουμε ισότητες αλλά ανισότητες και ξέρουμε ότι μια ανισότητα στον δισδιάστατο χώρο, ορίζει ένα ημιεπίπεδο. Οι ευθείες που σχεδιάσαμε χωρίζουν (η κάθε μία) τον δισδιάστατο χώρο σε 2 ημιεπίπεδα, ποιο ημιεπίπεδο θέλουμε όπως για το κάθε περιορισμό; Ας ελέγξουμε για τον πρώτο, \(x_1 \leq 200\) θέλουμε όλα τα σημεία του επιπέδου (\(x_1, y_1)\) για τα οποία \(x_1 \leq 200\). Σε ποια μεριά της ε1 βρίσκονται αυτά τα σημεία; Έχουμε ότι η αρχή των αξόνων \((0,0)\) τηρεί τον περιορισμό, άρα θέλουμε το ημιεπίπεδο που ορίζεται από την ε1 και το \((0,0)\) (αν δεν ίσχυε αυτό, θα παίρναμε το άλλο ημιεπίπεδο).
Ομοίως ενεργούμε και στις υπόλοιπες ευθείες:
Η τομή όλων των ημιεπιδέδων των περιορισμών ορίζει την Εφικτή Περιοχή ενός ΓΠ, δηλαδή το σύνολο όλων των εφικτών λύσεων.
Έχουμε τελειώσει με τους περιορισμούς! Το κυρτό πολύγωνο ΟΠΡΤΓ περιέχει όλες τις εφικτές λύσεις του ΓΠ. Μας μένει μόνο να βρούμε την καλύτερη! Μέχρι τώρα έχουμε παραλείψει την συνάρτηση στόχο \(f(x_1, x_2) = x_1 + 6x_2\). Από την συνάρτηση στόχο, μπορούμε να πάρουμε μια οικογένεια ευθειών, η μία παράλληλη στην άλλη, π.χ. για \(f(x_1, x_2) = 100\) έχουμε \(x_1 + 6x_2 = 100\), ενώ για \(f(x_1, x_2) = 400\), έχουμε \(x_1 + 6x_2 = 400\). Γενικά \(f(x_1, x_2) = c \Leftrightarrow x_1 + 6x_2 = c\). Μπορούμε, λοιπόν, να φανταστούμε την συνάρτηση στόχο σαν μια ευθεία που σαρώνει την εφικτή περιοχή.
Που θα σταματήσει; Μπορούμε να φανταστούμε, και φαίνεται και από το σχήμα, ότι θα σταματήσει σε κάποια από τις κορυφές του πολυγώνου, συγκεκριμένα στην Π. Οπότε τελικά θα έχουμε:
\(x^* = (100, 300)\) = Π
\(f(100, 300) = 100 + 6\cdot300 = 1900\)
To \(x^*\) είναι η Βέλτιστη Λύση, ενώ το \(f(x^*) = 1900\) η τιμή της.
Η επίλυση ΓΠ στον δισδιάστατο χώρο αποδείχθηκε σχετικά απλή υπόθεση. Η γραφική μέθοδος θα λειτουργούσε και στον τριδιάστατο χώρο, αν και θα απαιτούσε πολύ μεγαλύτερη δεξιοτεχνία στην σχεδίαση. Η διάσταση του χώρου προκύπτει από το πόσες μεταβλητές έχει το ΓΠ μας και φυσικά δεν μπορούμε να σχεδιάσουμε πάνω από τρεις διαστάσεις. Στο επόμενο κεφάλαιο θα θυμηθούμε κάποια θεωρήματα της Αναλυτικής Γεωμετρίας από το σχολείο και θα τα γενικεύσουμε στις n διαστάσεις, ώστε να μπορούμε να δουλέψουμε πιο περίπλοκα ΓΠ. Τα εργαλεία αυτά θα μας χρησιμεύσουν στη μέθοδο Simplex, με την βοήθεια της οποίας μπορούμε να λύσουμε οποιοδήποτε ΓΠ.
To Κεφάλαιο 2 θα είναι προαπαιτούμενο του Κεφαλαίου 3, αλλά εκείνος/η που νιώθει σίγουρος με τις στοιχειώδεις γνώσεις στην Αναλυτική Γεωμετρία μπορεί να το παραλείψει.
Σημειώσεις:
Αν δεν εμφανίζονται σωστά τα μαθηματικά σύμβολα, παρακαλώ πατήστε Ctrl+F5.
Τα σχήματα έγιναν με το GeoGebra6, ενώ το gif με το GeoGebra4. Το πρόγραμμα διατίθεται για Windows, Mac και Linux.
Για μαθηματικά σύμβολα στο blogger ακολούθησα αυτές εδώ τις οδηγίες
Πλοήγηση
Το ΓΠ στο οποίο καταλήξαμε την προηγούμενη φορά είναι το εξής:
\(max\) \(f(x_1, x_2) = x_1 + 6x_2\)
υ.π.:
\(x_1 \leq 200\)
\(x_2 \leq 300\)
\(x_1 + x_2 \leq 400\)
\(x_1, x_2 \geq 0\)
Για την λύση αρκεί να ξέρουμε να ζωγραφίζουμε και τα μαθηματικά του Γυμνασίου, αυτό είναι ένα από τα χαρακτηριστικά που καθιστούν τον Γραμμικό Προγραμματισμό τόσο όμορφο, το ότι είναι εξαιρετικά minimal. Θα πιάσουμε και θα σχεδιάσουμε τις ευθείες που αντιστοιχούν στους περιορισμούς. Ορίζουμε τις εξής ευθείες:
ε1: \(x_1 = 200\)
ε2: \(x_2 = 300\)
ε3: \(x_1 + x_2 = 400\)
και φυσικά έχουμε και τους άξονες \(x_1 = 0\), \(x_2 = 0\).
Για την λύση αρκεί να ξέρουμε να ζωγραφίζουμε και τα μαθηματικά του Γυμνασίου, αυτό είναι ένα από τα χαρακτηριστικά που καθιστούν τον Γραμμικό Προγραμματισμό τόσο όμορφο, το ότι είναι εξαιρετικά minimal. Θα πιάσουμε και θα σχεδιάσουμε τις ευθείες που αντιστοιχούν στους περιορισμούς. Ορίζουμε τις εξής ευθείες:
ε1: \(x_1 = 200\)
ε2: \(x_2 = 300\)
ε3: \(x_1 + x_2 = 400\)
και φυσικά έχουμε και τους άξονες \(x_1 = 0\), \(x_2 = 0\).
 | ||||
| Σχήμα 1: Οι περιορισμοί του ΓΠ σχεδιασμένοι στο επίπεδο. |
 | |
| Σχήμα 2: το ημιεπίπεδο η1 |
 | ||
| Σχήμα 3: Τα ημιεπίπεδα των περιορισμών |
 | |||
| Σχήμα 4: Εφικτή Περιοχή ΓΠ |
 |
| Σχήμα 5: Η συνάρτηση στόχος, σαρώνει την Εφικτή Περιοχή |
\(x^* = (100, 300)\) = Π
\(f(100, 300) = 100 + 6\cdot300 = 1900\)
To \(x^*\) είναι η Βέλτιστη Λύση, ενώ το \(f(x^*) = 1900\) η τιμή της.
Η επίλυση ΓΠ στον δισδιάστατο χώρο αποδείχθηκε σχετικά απλή υπόθεση. Η γραφική μέθοδος θα λειτουργούσε και στον τριδιάστατο χώρο, αν και θα απαιτούσε πολύ μεγαλύτερη δεξιοτεχνία στην σχεδίαση. Η διάσταση του χώρου προκύπτει από το πόσες μεταβλητές έχει το ΓΠ μας και φυσικά δεν μπορούμε να σχεδιάσουμε πάνω από τρεις διαστάσεις. Στο επόμενο κεφάλαιο θα θυμηθούμε κάποια θεωρήματα της Αναλυτικής Γεωμετρίας από το σχολείο και θα τα γενικεύσουμε στις n διαστάσεις, ώστε να μπορούμε να δουλέψουμε πιο περίπλοκα ΓΠ. Τα εργαλεία αυτά θα μας χρησιμεύσουν στη μέθοδο Simplex, με την βοήθεια της οποίας μπορούμε να λύσουμε οποιοδήποτε ΓΠ.
To Κεφάλαιο 2 θα είναι προαπαιτούμενο του Κεφαλαίου 3, αλλά εκείνος/η που νιώθει σίγουρος με τις στοιχειώδεις γνώσεις στην Αναλυτική Γεωμετρία μπορεί να το παραλείψει.
Σημειώσεις:
Αν δεν εμφανίζονται σωστά τα μαθηματικά σύμβολα, παρακαλώ πατήστε Ctrl+F5.
Τα σχήματα έγιναν με το GeoGebra6, ενώ το gif με το GeoGebra4. Το πρόγραμμα διατίθεται για Windows, Mac και Linux.
Για μαθηματικά σύμβολα στο blogger ακολούθησα αυτές εδώ τις οδηγίες
Πλοήγηση
Σχόλια
Δημοσίευση σχολίου