Εισαγωγή
Όλοι μας λύνουμε κάθε μέρα Προβλήματα Γραμμικού Προγραμματισμού χωρίς συχνά να το καταλαβαίνουμε. Όταν ψωνίζουμε στο Σουπερμάρκετ και υπολογίζουμε πως θα αγοράσουμε περισσότερα τρόφιμα με τα χρήματα που έχουμε μαζί μας, τότε λύνουμε ένα απλό ΠΓΠ. Όταν αποφασίζουμε ποιό συνδυασμό μέσων μεταφοράς θα χρησιμοποιήσουμε για να μην αργήσουμε (ελαχιστοποίηση του χρόνου), πάλι τότε λύνουμε ένα μικρό ΠΓΠ. Αλλά και όταν ρυθμίζουμε την εργασία μας ώστε να μείνει χρόνος και για κάτι άλλο (οικογάνεια, διακοπές, κλπ.) και τότε λύνουμε ένα πρόβλημα βελτιστοποίησης σύμφωνα με τα δεδομένα που έχουμε, την εμπειρία μας και τον σκοπό που θέλουμε να πετύχουμε.
Για να λύσουμε τα προβλήματα αυτά πιο συστηματικά, με μαθηματικές και υπολογιστικές μεθόδους πρέπει πρώτα να τους δώσουμε μια μαθηματική διατύπωση, δηλαδή να δημιουργήσουμε το μοντέλο του προβλήματος. Τα προβλήματα που διατυπώνονται με γραμμικές σχέσεις μεταξύ των μεταβλητών (περιορισμοί, αντικειμενικός στόχος, ...) λέγονται Προβλήματα Γραμμικού Προγραμματισμού.
Παραδείγματα Μοντελοποίησης Προβλημάτων Γραμμικού Προγραμματισμού (ΠΓΠ)
ΠΡΟΒΛΗΜΑ 1
Μία σπουδάστρια θέλει να στείλει, από το μέρος που σπουδάζει, 12 τουλάχιστον κάρτες σε φίλους και συγγενείς. Οι ασπρόμαυρες κάρτες κοστίζουν 1 € και οι έγχρωμες 2 € η μία, αλλά η σπουδάστρια δεν διαθέτει πάνω από 16 €. Πόσες κάρτες από κάθε είδος μπορεί να αγοράσει;
ΜΟΝΤΕΛΟΠΟΙΗΣΗ:
1. Μεταβλητές
Οι μεταβλητές θα είναι οι ζητούμενες ποσότητες:
α) ο αριθμός των ασπρόμαυρων καρτών που θα αγοραστούν, Χ.
β) ο αριθμός των έγχρωμων καρτών που θα αγοραστούν, Υ.
2. Παράμετροι
Οι παράμετροι του προβλήματος είναι οι:
α) 1 € η τιμή κάθε κάρτας Χ (ασπρόμαυρης),
β) 2 € η τιμή κάθε κάρτας Υ (έγχρωμης),
γ) 16 € τα χρήματα που διαθέτει η σπουδάστρια, και,
δ) το να αγοραστούν 12 κάρτες τουλάχιστον.
3. Περιορισμοί
α) ‘Τουλάχιστον 12 κάρτες’ σημαίνει ότι το σύνολο ασπρόμαυρων (Χ) και έγχρωμων (Υ) καρτών θα είναι 12 ή μεγαλύτερο. Σε μαθηματική διατύπωση γράφεται: Χ + Υ ≥ 12.
β) ‘Όχι πάνω από 16 €' σημαίνει ότι το συνολικό κόστος ασπρόμαυρων (X·1 €) και έγχρωμων (Υ·2 €) καρτών θα είναι 16 € ή μικρότερο. Σε μαθηματική διατύπωση γράφεται: Χ + 2·Υ ≤ 16.
γ) Οι ποσότητες των καρτών είναι θετικοί ακέραιοι αριθμοί, δηλαδή είναι: Χ ≥ 0, και, Υ ≥ 0.
4. Αντικειμενικός στόχος (ΑΣ)
Στο πρόβλημα δεν έχει δοθεί κάποιος αντικειμενικός στόχος ώστε να βρεθεί η βέλτιστη λύση που θα τον ικανοποιεί. Το πρόβλημα ζητά τους εφικτούς συνδυασμούς καρτών που μπορούν να αγοραστούν. Έχοντας βέβαια το σύνολο των δυνατών λύσεων, μπορούμε μετά να διαλέξουμε εκείνη που μας εξυπηρετεί καλύτερα (π.χ. να είναι όσο πιο πολλές οι έγχρωμες κάρτες, ή, να είναι όσο πιο πολλές συνολικά οι κάρτες, κλπ.).
ΜΟΝΤΕΛΟ:
Υπό τους περιορισμούς (ΥΤΠ):
Χ + Υ ≥ 12
Χ + 2·Υ ≤ 16
Χ ≥ 0, και, Υ ≥ 0.
ΑΣ: -
Να Βρεθούν Όλες οι Εφικτές Λύσεις
ΠΡΟΒΛΗΜΑ 2
Ένας μηχανικός πρόκειται να φέρει από το εξωτερικό τόρνους και τρυπάνια. Οι συσκευές έρχονται λυμένες και ο μηχανικός θα τις συναρμολογήσει και θα τις μεταπωλήσει. Συνολικά μπορεί να αποθηκεύσει μέχρι 50 συσκευές. Κάθε τόρνος κοστίζει 40 € και κάθε τρυπάνι 20 €. Ο μηχανικός μπορεί να διαθέσει μέχρι 1400 € για την αγορά τους. Υπολογίζει να κερδίσει 60 € από κάθε τόρνο και 40 € από κάθε τρυπάνι. Με αυτές τις συνθήκες πόσους τόρνους και τρυπάνια πρέπει να αγοράσει για να κερδίσει περισσότερα;
ΜΟΝΤΕΛΟΠΟΙΗΣΗ:
1. Μεταβλητές
Οι μεταβλητές θα είναι πάλι οι ζητούμενες ποσότητες:
α) ο αριθμός των τόρνων που θα αγοραστούν, έστω Χ.
β) ο αριθμός των τρυπανιών που θα αγοραστούν, έστω Υ.
2. Παράμετροι
Οι παράμετροι του προβλήματος είναι οι:
α) 40 € η τιμή και 60 € το κέρδος κάθε συσκευής Χ (τόρνος),
β) 20 € η τιμή και 40 € το κέρδος κάθε συσκευής Υ (τρυπάνι),
γ) 1400 € τα χρήματα που διαθέτει ο μηχανικός, και,
δ) ότι η αποθήκη χωρά 50 συσκευές.
3. Περιορισμοί
α) ‘μέχρι 50 συσκευές’ σημαίνει ότι το σύνολο τόρνων (Χ) και τρυπανιών (Υ) θα είναι 50 ή μικρότερο. Σε μαθηματική διατύπωση γράφεται: Χ + Υ ≤ 50.
β) ‘Όχι πάνω από 1400 €’ σημαίνει ότι το συνολικό κόστος τόρνων (X·40 €) και τρυπανιών (Υ·20 €) θα είναι 1400 € ή μικρότερο. Σε μαθηματική διατύπωση γράφεται: 40·Χ + 20·Υ ≤ 1400, ή, 2·Χ + Υ ≤ 70.
γ) Οι ποσότητες των συσκευών είναι θετικοί ακέραιοι αριθμοί, δηλαδή είναι: Χ ≥ 0, και, Υ ≥ 0.
4. Αντικειμενικός στόχος
‘Για να κερδίσει περισσότερα’ σημαίνει ότι το συνολικό κέρδος από τη πώληση των τόρνων (X·60 €) και των τρυπανιών (Υ·40 €) θα πρέπει να γίνει όσο το δυνατόν μεγαλύτερο. Σε μαθηματική διατύπωση γράφεται σαν: max (60·Χ + 40·Υ). Η βέλτιστη λύση θα είναι η εφικτή λύση θα που μεγιστοποιεί τη συνάρτηση.
ΜΟΝΤΕΛΟ:
Υπό τους περιορισμούς (ΥΤΠ):
Χ + Υ ≤ 50
2·Χ + Υ ≤ 70
Χ ≥ 0, και, Υ ≥ 0.
ΑΣ:
Να Μεγιστοποιηθεί το Συνολικό Κέρδος: 60·Χ + 40·Υ
