Στο προηγούμενο κεφάλαιο περιγράψαμε την μέθοδο Simplex, αλγεβρικά. Σε αυτή την σειρά όμως βασικό μας μέλημα είναι η διαίσθηση που προσφέρει η γεωμετρία του προβλήματος. Εδώ θα ασχοληθούμε με την ερμηνεία των αλγεβρικών βημάτων του προηγούμενου κεφαλαίου από γεωμετρικής σκοπιάς. Ας θυμηθούμε άλλη μια φορά την κεντρική ιδέα της μεθόδου Simplex, όπως την περιγράψαμε στο Κεφάλαιο 2.0 : Κεντρική Ιδέα Μεθόδου Simplex Έστω v μία κορυφή της εφικτής περιοχής Όσο υπάρχει ένας γείτονας της v, v' με καλύτερη τιμή της συνάρτησης στόχου:         θέσε v' := v Αυτή ακριβώς την κεντρική ιδέα υλοποιήσαμε και στο Κεφάλαιο 3.1 . Έστω ότι έχουμε ένα ΓΠ με n μεταβλητές (άρα θα "ζούμε" στον n-διάστατο χώρο), ουσιαστικά κινούμαστε κάθε φορά πάνω σε μία ακμή του πολυτόπου των λύσεων (η μία ακμή ορίζεται από n-1 υπερεπίπεδα, οι n-1 μεταβλητές που παραμένουν σταθερές) και θα σταματήσουμε στην άλλη άκρη της ακμής. Η γειτονιά συνεπώς που αναφέρουμε στην Κεντρική Ιδέα δεν είναι άλλη απ

Τώρα έχουμε επιτέλους τα κατάλληλα εργαλεία (συγκεκριμένα την εξίσωση (4) ), ώστε να λύσουμε ένα ΓΠ. Συγκεκριμένα ας θεωρήσουμε το ακόλουθο ΓΠ.:                 \(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) Φυσικά στόχος μας είναι να αυξήσουμε την συνάρτηση στόχο, πως μπορούμε να

Στο προηγούμενο μέρος του κεφαλαίου δείξαμε πως μπορούμε να γράφουμε τα υπερεπίπεδα και τις ευθείες σε άλγεβρα και αποδείξαμε τις εξισώσεις:   \(\vec{x} \cdot \vec{a} = -c \hspace{5mm} (1)\) \(H_{\vec{a}, c} = \{ \vec{x} \in \mathbb{R}^n | \vec{a} \cdot  \vec{x} = - c\} \hspace{5mm}(2)\)  Την (1) την ονομάσαμε Εσσιανή Κανονική Μορφή . Θα δούμε ότι είναι πολύ εύκολο να βρούμε την απόσταση ενός σημείου από ένα υπερεπίπεδο, αν μας δίνεται το υπερεπίπεδο στην μορφή της (2). Θυμόμαστε ότι το \(\vec{a} \perp Η_{\vec{a}, c}\) και \(\|a\| = 1\). Επίσης, ότι το υπερεπίπεδο απέχει \(|c|\) από την αρχή των αξόνων. Έστω Χ το σημείο του οποίου θέλουμε να βρούμε την απόσταση από το \(H_{\vec{a}, c}\), τότε, ξέρουμε  ήδη από το σχολείο, ότι όταν λέμε απόσταση σημείου από υπερεπίπεδο εννοούμε κάθετη απόσταση. Σχήμα 1: Κάθετη απόσταση σημείου από υπερεπίπεδο Ας προσπαθήσουμε να "πιάσουμε" το σημείο Χ. Θεωρούμε ένα σημείο \(X_0\) πάνω στο υπερεπίπεδο, τότε παρατηρούμε ότι το

Είδαμε στα προηγούμενα κεφάλαια την σημασία της γεωμετρίας των ευθειών και των υπερεπιπέδων για τον Γραμμικό Προγραμματισμό. Σε αυτό το κεφάλαιο θα πάμε πιο βαθιά σε αυτή την έννοια και θα δείξουμε πως να την "κωδικοποιούμε" στην γλώσσα της άλγεβρας. Ευθείες, Επίπεδα και Υπερεπίπεδα Τι ακριβώς είναι μια ευθεία ή ένα υπερεπίπεδο; Πως γράφουμε μια ευθεία σε αλγεβρική μορφή; Θα πρέπει να σκεφτόμαστε την αναλυτική γεωμετρία σαν ένα υπολογιστικό σύστημα, σαν μια γλώσσα προγραμματισμού. Στην ευκλείδια γεωμετρία που κάναμε στο σχολείο η ευθεία και το επίπεδο είναι κάτι τελείως χειροπιαστό, στην άλγεβρα όμως έχουμε μόνο πράξεις, μεταβλητές και εξισώσεις, τι άλλο θα μπορούσε να είναι λοιπόν μια ευθεία από μια εξίσωση, η εξίσωση θα ισχύει μόνο για τα σημεία εκείνα τα οποία ανήκουν στην ευθεία . Στο σχολείο γράφαμε το εξής: \(y = \frac{-a}{b}x + \frac{-c}{b}\) ή \(y = \lambda x+\beta\) θα δούμε πως η πρώτη μορφή είναι πολύ πιο χρήσιμη από την δεύτερη: $$  y = \frac{-a}{b}

Ως εδώ είχαμε προχωρήσει χωρίς να εισάγουμε βαρύ μαθηματικό συμβολισμό. Δυστυχώς όμως για να περάσουμε από τις 2 διαστάσεις στις n δεν μπορούμε να το κάνουμε χωρίς να βασιστούμε σε στοιχειώδη γραμμική άλγεβρα και αναλυτική γεωμετρία . Η αναγνώστρια/ης που δεν διαθέτει αυτές τις γνώσεις παραπέμπεται στη σειρά βίντεο του 3blue1brown (στα αγγλικά). Ας σταθούμε λίγο στην παρατήρηση που είχαμε κάνει στο προηγούμενο κεφάλαιο : Καθώς η συνάρτηση στόχος σαρώνει την εφικτή περιοχή, θα σταματήσει σε κάποια από τις κορυφές του πολυγώνου. Αυτό το βασικό θεώρημα του γραμμικού προγραμματισμού, μας επιτρέπει να ψάχνουμε μόνο στις κορυφές του πολυτόπου, για την βέλτιστη του ΓΠ. Η κεντρική ιδέα της μέθοδου Simplex είναι η ακόλουθη: Έστω v μια κορυφή της εφικτής περιοχής   Όσο υπάρχει ένα γείτονας v' του v με καλύτερη τιμή της συνάρτησης στόχου:       Θέσε v := v' Το παραπάνω απαιτεί κάθε φορά να βλέπουμε το πολύτοπο από την οπτική γωνία μιας κορυφής . Θα δούμε στο επόμενο

Στο προηγούμενο κεφάλαιο είχαμε δει πως περνάμε από το πρόβλημα σε φυσική γλώσσα σε μια αυστηρή μαθηματική διατύπωση. Είχαμε πει ότι από την στιγμή που γίνει αυτό μπορούμε ουσιαστικά να ξεχάσουμε το αρχικό πρόβλημα και να λύσουμε την μαθηματική μοντελοποίησή του, το ΓΠ. Μια λύση του ΓΠ θα είναι και μια λύση του αρχικού προβλήματος, αν έχουμε κάνει σωστά την μετάβαση. Το ΓΠ στο οποίο καταλήξαμε την προηγούμενη φορά είναι το εξής:                 \(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\) ε