Γραμμικός Προγραμματισμός: Κεφάλαιο 2.1 - λίγη γραμμική άλγεβρα & αναλυτική γεωμετρία - ευθείες και υπερεπίπεδα
Είδαμε στα προηγούμενα κεφάλαια την σημασία της γεωμετρίας των ευθειών και των υπερεπιπέδων για τον Γραμμικό Προγραμματισμό. Σε αυτό το κεφάλαιο θα πάμε πιο βαθιά σε αυτή την έννοια και θα δείξουμε πως να την "κωδικοποιούμε" στην γλώσσα της άλγεβρας.
Ευθείες, Επίπεδα και Υπερεπίπεδα
Τι ακριβώς είναι μια ευθεία ή ένα υπερεπίπεδο; Πως γράφουμε μια ευθεία σε αλγεβρική μορφή; Θα πρέπει να σκεφτόμαστε την αναλυτική γεωμετρία σαν ένα υπολογιστικό σύστημα, σαν μια γλώσσα προγραμματισμού. Στην ευκλείδια γεωμετρία που κάναμε στο σχολείο η ευθεία και το επίπεδο είναι κάτι τελείως χειροπιαστό, στην άλγεβρα όμως έχουμε μόνο πράξεις, μεταβλητές και εξισώσεις, τι άλλο θα μπορούσε να είναι λοιπόν μια ευθεία από μια εξίσωση, η εξίσωση θα ισχύει μόνο για τα σημεία εκείνα τα οποία ανήκουν στην ευθεία. Στο σχολείο γράφαμε το εξής: \(y = \frac{-a}{b}x + \frac{-c}{b}\) ή \(y = \lambda x+\beta\) θα δούμε πως η πρώτη μορφή είναι πολύ πιο χρήσιμη από την δεύτερη:
$$ y = \frac{-a}{b}x + \frac{-c}{b} \\ ax + by = -c \\ \vec{x} \cdot \vec{a} = -c \hspace{5mm} (1)$$
όπου \(\vec{x} = (x, y)\), \(\vec{a} = (a, b)\) και \(\vec{a} \perp\) ε, ε η ευθεία. Έτσι ορίζουμε και το υπερεπίπεδο στον n-διάστατο χώρο. Δεδομένουνου ενός \(\vec{a} \in \mathbb{R}^n\), \(c \in \mathbb{R}\) ορίζουμε το υπερεπίπεδο \(Η_{\vec{a}, c}\), που είναι κάθετο στο \(\vec{a}\) και \(\forall \vec{x} \in \mathbb{R}^n\) αν \(\vec{a} \cdot \vec{x} = -c\), τότε το \(\vec{x}\) ανήκει στο υπερεπίπεδο \(Η_{\vec{a}, c}\).
$$ H_{\vec{a}, c} = \{ \vec{x} \in \mathbb{R}^n | \vec{a} \cdot \vec{x} = - c\} \hspace{5mm}(2) $$
Χ.β.γ. θεωρούμε ότι \(\vec{a}\) είναι μοναδιαίο, δηλαδή \(\|\vec{a}\| = 1\). Τότε η (1) λέγεται Εσσιανή Κανονική Μορφή (Hessian Normal Form). Αν \(\|\vec{a}\| \neq 1 \) τότε απλά διαιρούμε την (1) με το \( \|\vec{a}\|\). Το c είναι η απόσταση του υπερεπιπέδου από την αρχή των αξόνων. Aν \( c > 0 \), τότε η αρχή των αξόνων βρίσκεται από την πλευρά που δείχνει το \(\vec{a}\), ενώ αν \(c < 0\) από την αντίθετη.
Γεωμετρική Ερμηνία
Καταφέραμε να συμμαζέψουμε την αφηρημένη έννοια του υπερεπιπέδου στις (1), (2)· αλλά αν σταματήσουμε εδώ θα έχουμε χάσει μια μεγάλη ευκαιρία να κατάνοήσουμε πραγματικά την (1). Τι σημαίνει γεωμετρικά; Αρχίζουμε με λίγο "μασάζ"..
$$(1) \hspace{5mm}\vec{x} \cdot \vec{a} = -c \\ \vec{x} \cdot \vec{a} + c = 0 \\ \vec{x} \cdot \vec{a} + (\vec{a} \cdot \vec{a}) c = 0 \\ \vec{a}\cdot(\vec{x} + c\vec{a}) = 0 \hspace{5mm} (3)$$
H (3) μας βολεύει πάρα πολύ γιατί μεταφράζεται άμεσα σε γεωμετρία, αφού για δύο διανύσματα \(\vec{x}, \vec{y}, \vec{x} \cdot \vec{y} = 0 \Leftrightarrow \vec{x} \perp \vec{y} \). Η (3), λοιπόν μας λέει ότι ένα σημείο \(\vec{x}\) ανήκει στο υπερεπίπεδο \(H_{\vec{a}, c}\) αν και μόνον εάν προσθέσουμε στο \(\vec{x}\) το \(c\vec{a}\) και το αποτέλεσμα είναι κάθετο στο \(\vec{a}\). (θυμίζουμε ότι \(\|\vec{a}\| = 1\))
Έστω, λοιπόν ένα σημείο P \(\in \mathbb{R}^n\) θέλουμε να ελέγξουμε αν το P ανήκει στο \(H_{\vec{a}, c}\), οπότε προσθέτουμε το \(c\vec{a}\) στο \(\vec{OP}\) και θα ελέγξουμε αν το \((\vec{OP} + c\vec{a}) \perp \vec{a}\)
Έχουμε εξαντλήσει το θέμα των υπερεπιπέδων στον \(\mathbb{R}^n\) στο επόμενο μέρος του Κεφαλαίου 2, θα ασχοληθούμε με το πρόβλημα της απόστασης σημείου από υπερεπίπεδο. Έτσι θα έχουμε τα απαραίτητα μαθηματικά εργαλεία, ώστε να μεταβαίνουμε σε κάθε κορυφή του πολυτόπου στην μέθοδο Simplex και θα μπορούμε να βλέπουμε κάθε φορά το πολύτοπο από την τρέχουσα κορυφή.
Σημειώσεις:
Αν δεν εμφανίζονται σωστά τα μαθηματικά σύμβολα, παρακαλώ πατήστε Ctrl+F5.
Τα σχήματα έγιναν με τον GeoGebra5. Το πρόγραμμα διατίθεται για Windows, Mac και Linux.
Για μαθηματικά σύμβολα στο blogger ακολούθησα αυτές εδώ τις οδηγίες
Πλοήγηση
Ευθείες, Επίπεδα και Υπερεπίπεδα
Τι ακριβώς είναι μια ευθεία ή ένα υπερεπίπεδο; Πως γράφουμε μια ευθεία σε αλγεβρική μορφή; Θα πρέπει να σκεφτόμαστε την αναλυτική γεωμετρία σαν ένα υπολογιστικό σύστημα, σαν μια γλώσσα προγραμματισμού. Στην ευκλείδια γεωμετρία που κάναμε στο σχολείο η ευθεία και το επίπεδο είναι κάτι τελείως χειροπιαστό, στην άλγεβρα όμως έχουμε μόνο πράξεις, μεταβλητές και εξισώσεις, τι άλλο θα μπορούσε να είναι λοιπόν μια ευθεία από μια εξίσωση, η εξίσωση θα ισχύει μόνο για τα σημεία εκείνα τα οποία ανήκουν στην ευθεία. Στο σχολείο γράφαμε το εξής: \(y = \frac{-a}{b}x + \frac{-c}{b}\) ή \(y = \lambda x+\beta\) θα δούμε πως η πρώτη μορφή είναι πολύ πιο χρήσιμη από την δεύτερη:
$$ y = \frac{-a}{b}x + \frac{-c}{b} \\ ax + by = -c \\ \vec{x} \cdot \vec{a} = -c \hspace{5mm} (1)$$
όπου \(\vec{x} = (x, y)\), \(\vec{a} = (a, b)\) και \(\vec{a} \perp\) ε, ε η ευθεία. Έτσι ορίζουμε και το υπερεπίπεδο στον n-διάστατο χώρο. Δεδομένουνου ενός \(\vec{a} \in \mathbb{R}^n\), \(c \in \mathbb{R}\) ορίζουμε το υπερεπίπεδο \(Η_{\vec{a}, c}\), που είναι κάθετο στο \(\vec{a}\) και \(\forall \vec{x} \in \mathbb{R}^n\) αν \(\vec{a} \cdot \vec{x} = -c\), τότε το \(\vec{x}\) ανήκει στο υπερεπίπεδο \(Η_{\vec{a}, c}\).
$$ H_{\vec{a}, c} = \{ \vec{x} \in \mathbb{R}^n | \vec{a} \cdot \vec{x} = - c\} \hspace{5mm}(2) $$
Χ.β.γ. θεωρούμε ότι \(\vec{a}\) είναι μοναδιαίο, δηλαδή \(\|\vec{a}\| = 1\). Τότε η (1) λέγεται Εσσιανή Κανονική Μορφή (Hessian Normal Form). Αν \(\|\vec{a}\| \neq 1 \) τότε απλά διαιρούμε την (1) με το \( \|\vec{a}\|\). Το c είναι η απόσταση του υπερεπιπέδου από την αρχή των αξόνων. Aν \( c > 0 \), τότε η αρχή των αξόνων βρίσκεται από την πλευρά που δείχνει το \(\vec{a}\), ενώ αν \(c < 0\) από την αντίθετη.
 |
| Σχήμα 1(α): Σχετική θέση αρχής των αξόνων - ευθείας, c < 0 |
 |
| Σχήμα 1(β): Σχετική θέση αρχής των αξόνων - ευθείας, c > 0 |
Γεωμετρική Ερμηνία
Καταφέραμε να συμμαζέψουμε την αφηρημένη έννοια του υπερεπιπέδου στις (1), (2)· αλλά αν σταματήσουμε εδώ θα έχουμε χάσει μια μεγάλη ευκαιρία να κατάνοήσουμε πραγματικά την (1). Τι σημαίνει γεωμετρικά; Αρχίζουμε με λίγο "μασάζ"..
$$(1) \hspace{5mm}\vec{x} \cdot \vec{a} = -c \\ \vec{x} \cdot \vec{a} + c = 0 \\ \vec{x} \cdot \vec{a} + (\vec{a} \cdot \vec{a}) c = 0 \\ \vec{a}\cdot(\vec{x} + c\vec{a}) = 0 \hspace{5mm} (3)$$
H (3) μας βολεύει πάρα πολύ γιατί μεταφράζεται άμεσα σε γεωμετρία, αφού για δύο διανύσματα \(\vec{x}, \vec{y}, \vec{x} \cdot \vec{y} = 0 \Leftrightarrow \vec{x} \perp \vec{y} \). Η (3), λοιπόν μας λέει ότι ένα σημείο \(\vec{x}\) ανήκει στο υπερεπίπεδο \(H_{\vec{a}, c}\) αν και μόνον εάν προσθέσουμε στο \(\vec{x}\) το \(c\vec{a}\) και το αποτέλεσμα είναι κάθετο στο \(\vec{a}\). (θυμίζουμε ότι \(\|\vec{a}\| = 1\))
Έστω, λοιπόν ένα σημείο P \(\in \mathbb{R}^n\) θέλουμε να ελέγξουμε αν το P ανήκει στο \(H_{\vec{a}, c}\), οπότε προσθέτουμε το \(c\vec{a}\) στο \(\vec{OP}\) και θα ελέγξουμε αν το \((\vec{OP} + c\vec{a}) \perp \vec{a}\)
 | |
| Σχήμα 2: Έλεγχος αν το P ανήκει στην ευθεία |
Έχουμε εξαντλήσει το θέμα των υπερεπιπέδων στον \(\mathbb{R}^n\) στο επόμενο μέρος του Κεφαλαίου 2, θα ασχοληθούμε με το πρόβλημα της απόστασης σημείου από υπερεπίπεδο. Έτσι θα έχουμε τα απαραίτητα μαθηματικά εργαλεία, ώστε να μεταβαίνουμε σε κάθε κορυφή του πολυτόπου στην μέθοδο Simplex και θα μπορούμε να βλέπουμε κάθε φορά το πολύτοπο από την τρέχουσα κορυφή.
Σημειώσεις:
Αν δεν εμφανίζονται σωστά τα μαθηματικά σύμβολα, παρακαλώ πατήστε Ctrl+F5.
Τα σχήματα έγιναν με τον GeoGebra5. Το πρόγραμμα διατίθεται για Windows, Mac και Linux.
Για μαθηματικά σύμβολα στο blogger ακολούθησα αυτές εδώ τις οδηγίες
Πλοήγηση
Σχόλια
Δημοσίευση σχολίου