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