Στο προηγούμενο κεφάλαιο περιγράψαμε την μέθοδο Simplex, αλγεβρικά. Σε αυτή την σειρά όμως βασικό μας μέλημα είναι η διαίσθηση που προσφέρει η γεωμετρία του προβλήματος. Εδώ θα ασχοληθούμε με την ερμηνεία των αλγεβρικών βημάτων του προηγούμενου κεφαλαίου από γεωμετρικής σκοπιάς. Ας θυμηθούμε άλλη μια φορά την κεντρική ιδέα της μεθόδου Simplex, όπως την περιγράψαμε στο Κεφάλαιο 2.0:
Κεντρική Ιδέα Μεθόδου Simplex
Το σχήμα θα μας βοηθήσει να το δούμε καλύτερα. (Όσες έχετε τα 4έδρα ζάρια του D&D, μπορείτε να δείτε εκεί το επιχείρημα πειραματιζόμενες με αυτά). Θυμόμαστε ότι μια ανισότητα αντιστοιχεί σε ένα ημιχώρο, δηλαδή τον χώρο που ορίζεται την μία πλευρά ενός υπερεπιπέδπου. Στο Κεφάλαιο 3.1 όταν αυξάναμε μία μεταβλητή, αυτό είχε ως συνέπεια μία ανισότητα να γίνει ισότητα, την ονομάσαμε σφιχτή. Αυτό που δεν επισημάναμε τότε είναι ότι, κάθε φορά θα έχουμε n σφιχτές ανισότητες, όπου n = # μεταβλητών = διάσταση του χώρου που βρισκόμαστε. Γιατί; Μα επειδή μία κορυφή στον n-διάστατο χώρο ορίζεται σαν τομή n υπερεπιπέδων.
Παρατηρήστε το Σχήμα 1, η κορυφή Α είναι η τομή των υπερεπιπέδων \(H_{ADC}, H_{ADB}, H_{ACB}\). Όταν μια ανισότητα γίνεται σφιχτή σταματάει να περιγράφει έναν ολόκληρο ημιχώρο και περιγράφει μόνο έναν υπερεπίπεδο. Έτσι ξέρουμε κάθε φορά σε ποια κορυφή του πολυτόπου βρισκόμαστε· σε εκείνη που ορίζεται από τις σφιχτές ανισότητες.
Ας πούμε το σύνολο των σφιχτών ανισοτήτων T (από το tight). Τι θα κάνουμε σε ένα βήμα της Simplex; Μία ανισότητα θα σταματήσει να είναι σφιχτή, ενώ κάποια άλλη θα γίνει. Έτσι ο πλυθάριθμος του Τ θα διατηρείται πάντα, \(|T| = n\). Τι σημαίνει όμως αυτό; Αν έχουμε n-1 ανισότητες σφιχτές έχουμε μια ευθεία στον n-διάστατο χώρο, συνεπώς κινούμαστε πάνω σε αυτή ακριβώς την ευθεία.
Έστω ότι θέλουμε να πάμε από το Α στο Β στο Σχήμα 1, θα χαλαρώσουμε την ανισότητα που αντιστοιχεί στο υπερεπίπεδο \(H_{ADC}\), έτσι μπορούμε να κινηθούμε σε όλο τον χώρο πάνω από το \(H_{ADC}\), μένοντας πάνω στην ευθεία \(\epsilon_{AB}\) αφού έχουμε κρατήσει σφιχτές τις ανισότητες των υπερεπιπέδων \(H_{ADB}, H_{ACB}\). Μέχρι που; Μέχρι να συναντήσουμε κάποια άλλη κορυφή του πολυτόπου (ξέρουμε ότι θα γίνει αφού το πολύτοπο είναι φραγμένο). Όταν συναντήσουμε κάποια άλλη κορυφή, τότε κάποια άλλη ανισότητα θα έχει γίνει σφιχτή. Έτσι πάλι το Τ θα έχει n στοιχεία. Στο συγκεκριμένο παράδειγμα θα είναι η ανισότητα που αντιστοιχεί στο υπερεπίπεδο \(Η_{BDC}\).
Έχουμε αντιστοιχήσει, λοιπόν, και πάλι την άλγεβρα με την γεωμετρία. Στο επόμενο μέρος του Κεφαλαίου 3 θα δούμε, γιατί η Simplex μας επιστρέφει πράγματι μια βέλτιστη λύση.
Σημειώσεις:
Αν δεν εμφανίζονται σωστά τα μαθηματικά σύμβολα, παρακαλώ πατήστε Ctrl+F5.
Τα σχήματα έγιναν με τον GeoGebra5. Το πρόγραμμα διατίθεται για Windows, Mac και Linux.
Για μαθηματικά σύμβολα στο blogger ακολούθησα αυτές εδώ τις οδηγίες
Πλοήγηση
Κεντρική Ιδέα Μεθόδου Simplex
- Έστω v μία κορυφή της εφικτής περιοχής
- Όσο υπάρχει ένας γείτονας της v, v' με καλύτερη τιμή της συνάρτησης στόχου:
- θέσε v' := v
 |
| Σχήμα 1: 3-διάστατο πολύτοπο |
Το σχήμα θα μας βοηθήσει να το δούμε καλύτερα. (Όσες έχετε τα 4έδρα ζάρια του D&D, μπορείτε να δείτε εκεί το επιχείρημα πειραματιζόμενες με αυτά). Θυμόμαστε ότι μια ανισότητα αντιστοιχεί σε ένα ημιχώρο, δηλαδή τον χώρο που ορίζεται την μία πλευρά ενός υπερεπιπέδπου. Στο Κεφάλαιο 3.1 όταν αυξάναμε μία μεταβλητή, αυτό είχε ως συνέπεια μία ανισότητα να γίνει ισότητα, την ονομάσαμε σφιχτή. Αυτό που δεν επισημάναμε τότε είναι ότι, κάθε φορά θα έχουμε n σφιχτές ανισότητες, όπου n = # μεταβλητών = διάσταση του χώρου που βρισκόμαστε. Γιατί; Μα επειδή μία κορυφή στον n-διάστατο χώρο ορίζεται σαν τομή n υπερεπιπέδων.
Παρατηρήστε το Σχήμα 1, η κορυφή Α είναι η τομή των υπερεπιπέδων \(H_{ADC}, H_{ADB}, H_{ACB}\). Όταν μια ανισότητα γίνεται σφιχτή σταματάει να περιγράφει έναν ολόκληρο ημιχώρο και περιγράφει μόνο έναν υπερεπίπεδο. Έτσι ξέρουμε κάθε φορά σε ποια κορυφή του πολυτόπου βρισκόμαστε· σε εκείνη που ορίζεται από τις σφιχτές ανισότητες.
Ας πούμε το σύνολο των σφιχτών ανισοτήτων T (από το tight). Τι θα κάνουμε σε ένα βήμα της Simplex; Μία ανισότητα θα σταματήσει να είναι σφιχτή, ενώ κάποια άλλη θα γίνει. Έτσι ο πλυθάριθμος του Τ θα διατηρείται πάντα, \(|T| = n\). Τι σημαίνει όμως αυτό; Αν έχουμε n-1 ανισότητες σφιχτές έχουμε μια ευθεία στον n-διάστατο χώρο, συνεπώς κινούμαστε πάνω σε αυτή ακριβώς την ευθεία.
Έστω ότι θέλουμε να πάμε από το Α στο Β στο Σχήμα 1, θα χαλαρώσουμε την ανισότητα που αντιστοιχεί στο υπερεπίπεδο \(H_{ADC}\), έτσι μπορούμε να κινηθούμε σε όλο τον χώρο πάνω από το \(H_{ADC}\), μένοντας πάνω στην ευθεία \(\epsilon_{AB}\) αφού έχουμε κρατήσει σφιχτές τις ανισότητες των υπερεπιπέδων \(H_{ADB}, H_{ACB}\). Μέχρι που; Μέχρι να συναντήσουμε κάποια άλλη κορυφή του πολυτόπου (ξέρουμε ότι θα γίνει αφού το πολύτοπο είναι φραγμένο). Όταν συναντήσουμε κάποια άλλη κορυφή, τότε κάποια άλλη ανισότητα θα έχει γίνει σφιχτή. Έτσι πάλι το Τ θα έχει n στοιχεία. Στο συγκεκριμένο παράδειγμα θα είναι η ανισότητα που αντιστοιχεί στο υπερεπίπεδο \(Η_{BDC}\).
Έχουμε αντιστοιχήσει, λοιπόν, και πάλι την άλγεβρα με την γεωμετρία. Στο επόμενο μέρος του Κεφαλαίου 3 θα δούμε, γιατί η Simplex μας επιστρέφει πράγματι μια βέλτιστη λύση.
Σημειώσεις:
Αν δεν εμφανίζονται σωστά τα μαθηματικά σύμβολα, παρακαλώ πατήστε Ctrl+F5.
Τα σχήματα έγιναν με τον GeoGebra5. Το πρόγραμμα διατίθεται για Windows, Mac και Linux.
Για μαθηματικά σύμβολα στο blogger ακολούθησα αυτές εδώ τις οδηγίες
Πλοήγηση
- Προηγούμενο
- Περιεχόμενα
- Επόμενο
Σχόλια
Δημοσίευση σχολίου