Θέματα Προόδου του μαθήματος “Γραμμικός και μη- Προγραμματισμός”-Μάϊος 2005

Ν. Γ. Χρηστάκης

1. Ένας κατασκευαστής επίπλων κατασκευάζει δύο τύπους τραπεζιών. Οι δύο αυτοί τύποι διαφέρουν τόσο στον τρόπο κατασκευής τους, όσο και στο κέρδος που αποφέρουν. Ο κατασκευαστής έχει διαθέσιμες κάθε μέρα 12 εργατοώρες, 6 μονάδες ξύλου και 10 μονάδες μετάλου. Για την κατασκευή ενός τραπεζιού τύπου 1 χρειάζονται 1 ώρα εργασίας, 1 μονάδα ξύλου και 2 μονάδες μετάλου. Για την κατασκευή ενός τραπεζιού τύπου 2 χρειάζονται 3 ώρες εργασίας, 1 μονάδα ξύλου και 1 μονάδα μετάλου. Τα κέρδη που αποφέρουν κάθε τραπέζι τύπου 1 και 2 είναι 2 και 5 ευρώ αντίστοιχα. Ο κατασκευαστής επιζητά να βρει πόσα τραπέζια από κάθε τύπο πρέπει να κατασκευάζει ημερησίως ώστε το κέρδος του να μεγιστοποιη0εί. Εκφράστε το πρόβλημα ως πρόβλημα Γραμμικού Προγραμματισμού με κατάλληλες ανισώσεις-περιορισμούς και στη συνέχεια βρείτε τη βέλτιστη λύση του αφού πρώτα βρείτε όλες τις βασικές του λύσεις. ΜΗΝ χρησιμοποιήσετε για την επίλυσή του μέθοδο Simplex.

(1,5 μονάδα)

2. Μία εταιρεία ανακαλύπτει ότι για τους επόμενους 3 μήνες παρουσίαζει έλλειψη χώρου αποθήκευσης. Οι επιπλέον ανάγκες της για τους επόμενους 3 μήνες θα είναι:

Μήνας	Ιούνιος	Ιούλιος	Αύγουστος
Χώρος που απαιτείται (χιλιάδες m^2)	25	10	20

Για να ανταπεξέλθει στις ανάγκες της αυτές η εταιρεία σκοπεύει να ενοικιάσει επιπλέον χώρο για μικρό χρονικό διάστημα. Στην αρχή κάθε μήνα η εταιρεία μπορεί να ενοικιάσει όσο χώρο θέλει για όσο καιρό θέλει. Ξεχωριστές ενοικιάσεις είναι δυνατόν να γίνουν για διαφορετικά τετραγωνικά χώρου και διαφορετική χρονική διάρκεια. Έτσι για παράδειγμα τον πρώτο μήνα θα μπορούσε να ενοικιάσει 20,000 m² για 2 μήνες και 5,000 m² για ένα μήνα. Επίσης, καινούργιες ενοικιάσεις μπορούν να γίνουν πριν λήξουν οι παλιές. Το κόστος ανά 1000 m² για διάφορες χρονικές διάρκειες δίδεται από τον πίνακα:

Διάρκεια μίσθωσης	1 μήνας	2 μήνες	3 μήνες
Κόστος (ευρώ ανά 1000 m^2)	1000	1800	2500

Εκφράστε το παραπάνω πρόβλημα με κατάλληλες ανισώσεις-περιορισμούς ως πρόβλημα Γραμμικού Προγραμματισμού (ΧΩΡΙΣ ΝΑ ΤΟ ΛΥΣΕΤΕ), του οποίου η λύση θα ικανοποιεί τις ανάγκες της εταιρείας με το ελάχιστο δυνατό κόστος. Αιτιολογήστε με σαφήνεια την απάντησή σας.

(1,5 μονάδα)

3. Να λυθεί με τη μέθοδο του μεγάλου-Μ το πρόβλημα Γραμμικού Προγραμματισμού:

με περιορισμούς:

Να εξηγείτε με σαφήνεια τι κάνετε σε κάθε βήμα.

(3 μονάδες)

4. Να λυθεί με την αναθεωρημένη μέθοδο Simplex το πρόβλημα Γραμμικού Προγραμματισμού:

με περιορισμούς:

Εξετάστε εάν η βέλτιστη λύση που βρήκατε είναι και η μοναδική ή υπάρχουν και εναλλακτικές βέλτιστες λύσεις. Εάν ναι, ποιές είναι αυτές;

Να εξηγείτε με σαφήνεια τι κάνετε σε κάθε βήμα.

(4 μονάδες)