Γραμμικός Προγραμματισμός: Κεφάλαιο 2.0 - λίγη γραμμική άλγεβρα & αναλυτική γεωμετρία - η γεωμετρική φύση του προβλήματος

Ως εδώ είχαμε προχωρήσει χωρίς να εισάγουμε βαρύ μαθηματικό συμβολισμό. Δυστυχώς όμως για να περάσουμε από τις 2 διαστάσεις στις n δεν μπορούμε να το κάνουμε χωρίς να βασιστούμε σε στοιχειώδη γραμμική άλγεβρα και αναλυτική γεωμετρία. Η αναγνώστρια/ης που δεν διαθέτει αυτές τις γνώσεις παραπέμπεται στη σειρά βίντεο του 3blue1brown (στα αγγλικά).

Ας σταθούμε λίγο στην παρατήρηση που είχαμε κάνει στο προηγούμενο κεφάλαιο:

Καθώς η συνάρτηση στόχος σαρώνει την εφικτή περιοχή, θα σταματήσει σε κάποια από τις κορυφές του πολυγώνου.

Αυτό το βασικό θεώρημα του γραμμικού προγραμματισμού, μας επιτρέπει να ψάχνουμε μόνο στις κορυφές του πολυτόπου, για την βέλτιστη του ΓΠ. Η κεντρική ιδέα της μέθοδου Simplex είναι η ακόλουθη:

1. Έστω v μια κορυφή της εφικτής περιοχής 
2. Όσο υπάρχει ένα γείτονας v' του v με καλύτερη τιμή της συνάρτησης στόχου: 
3.     Θέσε v := v'

Το παραπάνω απαιτεί κάθε φορά να βλέπουμε το πολύτοπο από την οπτική γωνία μιας κορυφής. Θα δούμε στο επόμενο κεφάλαιο, πως αυτό είναι εύκολο να το κάνουμε για την αρχή των αξόνων. Αυτό που θα κάνουμε είναι να μετασχήματίζουμε τον χώρο, ώστε κάθε φορά η κορυφή του πολυτόπου που βρισκόμαστε να είναι η αρχή των αξόνων. Με αυτό το τελευταίο πρόβλημα θα καταπιαστούμε σε αυτό το κεφάλαιο. Δεδομένου ενός συστήματος αξόνων S και ενός σημείου \(\vec{y}\) πως μπορούμε να πάμε σε ένα σύστημα S' ώστε το \(\vec{y}\) να είναι το \(\vec{0}\).

Το πρόβλημα θα ήταν τετρημένο, αν μας δίνεται το σημείο \(\vec{y}\) (απλά \(\forall \vec{x} \in \mathbb{R}^n\) στον χώρο S, θέτουμε \( \vec{x'} := \vec{x} - \vec{y}\) στον S'), κάτι τέτοιο όμως δεν θα συμβαίνει σε ένα ΓΠ. Στο ΓΠ αυτό που μας δίνεται είναι οι περιορισμοί· και όπως είδαμε μπορούμε να τους αντιστοιχήσουμε σε ευθείες στον δισδιάστατο χώρο, σε επίπεδα στον τρισδιάστατο χώρο ή υπερεπίπεδα στον n-διάστατο χώρο. Και όπως στον δισδιάστατο χώρο μπορούμε να ορίσουμε ένα σημείο ως τομή δύο ευθειών, έτσι και στον n-διάστατο χώρο μπορούμε να ορίσουμε ένα σημείο ως τομή n υπερεπιπέδων.

Πως μπορούμε να κάνουμε την μετάβαση που θέλουμε δεδομένων των υπερεπιπέδων που σχηματίζουν το σημείο \(\vec{y}\);. Αρκεί να εκφράσουμε τις συντεταγμένες κάθε σημείου \(\vec{x} \in \mathbb{R}^n\) ως αποστάσεις, όχι πια από τους άξονες, αλλά από τα υπερεπίπεδα που ορίζουν το \(\vec{y}\).

Στον S θα έχουμε:

Σχήμα 1(α): Οι συντεταγμένες ενός σημείου, ως αποστάσεις από τους άξονες (στο S)

Ενώ στο S' θα έχουμε:

Σχήμα 1(β): Οι συντεταγμένες ενός σημείου, ως αποστάσεις από τις ευθείες που ορίζουν το Υ (στο S')

Το Σχήμα 1(β) φαίνεται περίεργο, αλλά δεν έχει τίποτα λάθος. Θυμόμαστε από στην γραμμική άλγερβρα ότι οι άξονες ενός συστήματος αναφοράς δεν χρειάζεται να είναι κάθετοι (ορθοκανονικοί), αρκεί, τα διανύσματα που τους ορίζουν να είναι γραμμικός ανεξάρτητα.

Τέλος παρατηρούμε ότι εφόσον έχουμε καταφέρει την μετάβαση από το S στο S', δεν απαιτείται κάτι το διαφορετικό για να πάμε από το S' στο S''. Επαναλαμβάνουμε το ίδιο βήμα με διαφορετικό σημείο \(\vec{y'}\), αφού το \(\vec{y}\) θα είναι πια στο S' το \(\vec{0}\).

Στο Κεφάλαιο 2.1 θα μιλήσουμε για ευθείες και υπερεπίπεδα και την σύνδεση μεταξύ την γλώσσας της άλγεβρας (που θα χρησιμοποιήσουμε για τους υπολογισμούς μας) και της γεωμετρικής εποπτείας (η οποία μας δίνει καλύτερη διαίσθηση). Ενώ στο Κεφάλαιο 2.2 θα δούμε την απόσταση σημείου από υπερεπίπεδο, όπου και θα ολοκληρώσουμε την απόδειξη του τύπου, που υλοποιεί τον μετασχηματισμό, που περιγράψαμε πιο πάνω με λόγια.

Σημειώσεις:
Αν δεν εμφανίζονται σωστά τα μαθηματικά σύμβολα, παρακαλώ πατήστε Ctrl+F5. 
Τα σχήματα έγιναν με τον GeoGebra5. Το πρόγραμμα διατίθεται για Windows, Mac και Linux.
Για μαθηματικά σύμβολα στο blogger ακολούθησα αυτές εδώ τις οδηγίες

Πλοήγηση

• Προηγούμενο
• Περιεχόμενα
• Επόμενο