Μετάβαση στο κύριο περιεχόμενο

Γραμμικός Προγραμματισμός: Περιεχόμενα

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

Αυτή η μίνι σειρά μαθημάτων αποσκοπεί να εξοικειώσει τον αναγνώστη με τις βασικές έννοιες του γραμμικού προγραμματισμού. Δεν απαιτούνται προηγούμενες γνώσεις· μόνο κάποια εξοικείωση κυρίως με τα διανύσματα και τις πράξεις τους. Μία μαθήτρια λυκείου που έχει εμπεδώσει την ύλη της αναλυτικής γεωμετρίας που διδάσκεται στην Β' Λυκείου, δεν θα πρέπει να έχει πρόβλημα να διαβάσει τα κεφάλαια 0 - 3.

Περιεχόμενα
Ετικέτες

Σχόλια

Δημοσίευση σχολίου

Δημοφιλείς αναρτήσεις από αυτό το ιστολόγιο

Γραμμικός Προργαμματισμός: Κεφάλαιο 3.1 - Η Μέθοδος Simplex

Τώρα έχουμε επιτέλους τα κατάλληλα εργαλεία (συγκεκριμένα την εξίσωση (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.2 - λίγη γραμμική άλγεβρα & αναλυτική γεωμετρία - απόσταση σημείου - υπερεπιπέδπου

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

Γραμμικός Προγραμματισμός: Κεφάλαιο 1 - Γραφική Μέθοδος Επίλυσης ΓΠ

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