Μια από τις πιο όμορφες ιδέες που αναδεικνύουν όλα τα όμορφα χαρακτηριστικά της τομής των μαθηματικών με την επιστήμη υπολογιστών, είναι ο Γραμμικός Προγραμματισμός (ΓΠ) και η μέθοδος, επίλυσης Γραμμικών Προγραμμάτων, Simplex. Όπως και με τα γραφήματα, έτσι και μέσω του ΓΠ μπορούμε να εκφράζουμε τυπικά και κομψά μια πληθώρα προβλημάτων και να τα επιλύουμε αποτελεσματικά*. Ας ξεκινήσουμε σιγά σιγά..
Ας θεωρήσουμε το εξής πρόβλημα. Έστω ότι έχουμε μια σοκολατοποιία και παρασκευάζουμε δύο προϊόντα: το κύριο προϊόν το οποίο είναι τριγωνικές σοκολάτες, με την ονομασία Pyramid, και το πιο παλαιό και πολυτελές με την ονομασία Pyramid Nuit. Οι Pyramid πωλούνται 1€, ενώ οι Pyramid Nuit 6€. Επίσης έχουμε κάνει έρευνα της αγοράς και έχουμε διαπιστώσει πως αποκλείεται να πουλήσουμε πάνω από 200 κουτιά Pyramid και 300 κουτιά Pyramid Nuit. Ακόμη βάση του εξοπλισμού και του εργασιακού δυναμικού γνωρίζουμε ότι δεν μπορούμε να παράγουμε πάνω από 400 κουτιά σοκολάτας την ημέρα. Πόσα κουτιά από το κάθε είδος πρέπει να παράξουμε ώστε να μεγιστοποιήσουμε το κέρδος μας;[1]
Το πρόβλημα φαίνεται καθημερινό και ίσως να έχει ερωτηθεί πολλές φορές σε βιομηχανίες και βιοτεχνίες. Πως το λύνουμε όμως; Το πρώτο πράγμα που πρέπει να κάνουμε είναι να περάσουμε από τον χώρο της φυσικής γλώσσας στα μαθηματικά.
Παρατηρούμε ότι θέλουμε να μεγιστοποιήσουμε την συνάρτηση:
Η μετάβασή μας έχει ολοκληρωθεί! Πλέον μπορούμε να "πετάξουμε στα σκουπίδια" το αρχικό πρόβλημα και να επικεντρώσουμε την μελέτη μας στο τυπικά διατυπωμένο πρόβλημα, το οποίο το γράφουμε μαζεμένα παρακάτω:
Την παραπάνω γραφή θα την ονομάζουμε Γραμμικό Πρόγραμμα (ΓΠ, χωρίς σύγχηση με το Γραμμικό Προγραμματισμό). Την συνάρτηση \(f(x_1, x_2)\) που θέλουμε να μεγιστοποιήσουμε θα την λέμε Συνάρτηση Στόχο (από το αγγλικό Objective Function, στην ελληνική βιβλιογραφία θα την συναντήσετε και ως "αντικειμενική συνάρτηση"). Για να δικαιολογήσουμε το όνομα που δώσαμε (Γραμμικό Πρόγραμμα) αρκεί να παρατηρήσουμε ότι τόσο η συνάρτηση στόχος, όσο και οι περιορισμοί είναι γραμμικές συναρτήσεις.
Στο επόμενο κεφάλαιο θα δούμε πως να επιλύουμε ένα ΓΠ.
Σημειώσεις:
Αν δεν εμφανίζονται σωστά τα μαθηματικά σύμβολα, παρακαλώ πατήστε Ctrl+F5.
(*) Σε επόμενα κεφάλαια θα δούμε πόσο "αποτελεσματικά" μπορούμε να λύσουμε ένα ΓΠ.
Για μαθηματικά σύμβολα στο blogger ακολούθησα αυτές εδώ τις οδηγίες
Βιβλιογραφία:
[1] Το πρόβλημα πάρθηκε από το βιβλίο Αλγόριθμοι των Sanjoi Dasqupta, Christos Papadimitriou, Umesh Vazirani, εκδόσεις Κλειδάριθμος
Πλοήγηση
Ας θεωρήσουμε το εξής πρόβλημα. Έστω ότι έχουμε μια σοκολατοποιία και παρασκευάζουμε δύο προϊόντα: το κύριο προϊόν το οποίο είναι τριγωνικές σοκολάτες, με την ονομασία Pyramid, και το πιο παλαιό και πολυτελές με την ονομασία Pyramid Nuit. Οι Pyramid πωλούνται 1€, ενώ οι Pyramid Nuit 6€. Επίσης έχουμε κάνει έρευνα της αγοράς και έχουμε διαπιστώσει πως αποκλείεται να πουλήσουμε πάνω από 200 κουτιά Pyramid και 300 κουτιά Pyramid Nuit. Ακόμη βάση του εξοπλισμού και του εργασιακού δυναμικού γνωρίζουμε ότι δεν μπορούμε να παράγουμε πάνω από 400 κουτιά σοκολάτας την ημέρα. Πόσα κουτιά από το κάθε είδος πρέπει να παράξουμε ώστε να μεγιστοποιήσουμε το κέρδος μας;[1]
Το πρόβλημα φαίνεται καθημερινό και ίσως να έχει ερωτηθεί πολλές φορές σε βιομηχανίες και βιοτεχνίες. Πως το λύνουμε όμως; Το πρώτο πράγμα που πρέπει να κάνουμε είναι να περάσουμε από τον χώρο της φυσικής γλώσσας στα μαθηματικά.
Παρατηρούμε ότι θέλουμε να μεγιστοποιήσουμε την συνάρτηση:
\(f(x_1, x_2) = x_1 + 6x_2\)
όπου,
\(x_1\) = #σοκολατών Pyramid,
\(x_2\) = #σοκολατών Pyramid Nuit
επίσης έχουμε τους εξής περιορισμούς:
\(x_1 \leq 200\)
\(x_2 \leq 300\)
\(x_1 + x_2 \leq 400\)
και φυσικά θέλουμε οι ποσότητες από σοκολάτες που παράγουμε να είναι μη αρνητικός αριθμός, επομένως:
\(x_1, x_2 \geq 0\)
Η μετάβασή μας έχει ολοκληρωθεί! Πλέον μπορούμε να "πετάξουμε στα σκουπίδια" το αρχικό πρόβλημα και να επικεντρώσουμε την μελέτη μας στο τυπικά διατυπωμένο πρόβλημα, το οποίο το γράφουμε μαζεμένα παρακάτω:
\(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\)
Στο επόμενο κεφάλαιο θα δούμε πως να επιλύουμε ένα ΓΠ.
Σημειώσεις:
Αν δεν εμφανίζονται σωστά τα μαθηματικά σύμβολα, παρακαλώ πατήστε Ctrl+F5.
(*) Σε επόμενα κεφάλαια θα δούμε πόσο "αποτελεσματικά" μπορούμε να λύσουμε ένα ΓΠ.
Για μαθηματικά σύμβολα στο blogger ακολούθησα αυτές εδώ τις οδηγίες
Βιβλιογραφία:
[1] Το πρόβλημα πάρθηκε από το βιβλίο Αλγόριθμοι των Sanjoi Dasqupta, Christos Papadimitriou, Umesh Vazirani, εκδόσεις Κλειδάριθμος
Πλοήγηση
Σχόλια
Δημοσίευση σχολίου