Εργασία AMPL

Επιχειρησιακή Έρευνα 8ο Εξάμηνο

Στεφανίδης Ιωάννης

2021-07-27

1 Το Πρόβλημα

1.1 Σχέδιο Σωτηρία (έγγραφα)

Σημαντικά κρατικά έγγραφα/αρχεία μιας χώρας είναι αποθηκευμένα σε κεντρικό χώρο της πρωτεύουσάς της. Σε περίπτωση κρίσης κρίθηκε σκόπιμο να μεταφερθούν όλα αυτά με ειδικά μέσα μεταφοράς, που αποκτήθηκαν με ιδιαίτερα υψηλό κόστος, σε άλλες πόλεις της χώρας για να αποφευχθεί είτε η μαζική καταστροφή τους είτε η μαζική κατοχή τους απο μη εξουσιοδοτημένους φορείς. Για το λόγο αυτό η χώρα μπορεί να διαθέσει μέχρι 8 ειδικά μέσα μεταφοράς, όπου το κάθε ένα μέσο είναι δυνατόν να μεταφέρει όλο το αρχειακό υλικό που είναι αποθηκευμένο στην πρωτεύουσα. Ο περιορισμός είναι ότι το διαθέσιμο καύσιμο, που έχει το κάθε μέσο, του επιτρέπει να διανύσει το μέγιστο 400 χιλιόμετρα, ενώ στο σενάριο που εξετάζεται δεν προβλέπεται ανεφοδιασμός των παραπάνω μέσων μεταφοράς. Στον παρακάτω Πίνακα 1 δίνονται οι αποστάσεις (σε χιλιόμετρα) μεταξύ του αρχικού αποθηκευτικού χώρου Α και των 14 πόλεων (B1, B2, . . . , B14) καθώς και μεταξύ των 14 πόλεων. Σε κάθε μία από τις 14 πολεις υπάρχει σχεδιασμός να μεταφερθεί, απο την πρωτεύουσα, τουλάχιστον ένα αρχείο/έγγραφο σε περίοδο κρίσης. Ζητούμενο είναι να βρεθεί ο ελάχιστος αριθμός των ειδικών μέσων μεταφοράς που απαιτούνται για να γίνει η παραπάνω μεταφορά. Στην περίπτωση, που για την επιτυχή περάτωση του Σχεδίου 1, ειδικά μέσα μεταφοράς περισσέψουν, τότε αυτά θα μπορούσαν να υποστηρίξουν την μεταφορά υλικού (π.χ. ιατροφαρμακευτικού) όπως περιγράφεται στο παρακάτω Σχέδιο 2

Table 1.1: Distances (near=green and far=red)

Town	B1	B2	B3	B4	B5	B6	B7	B8	B9	B10	B11	B12	B13	B14
A	180	240	85	285	205	235	255	155	120	230	340	220	160	240
B1	0	255	150	125	100	175	235	25	65	95	210	55	135	215
B2	255	0	160	235	160	105	45	245	255	195	225	310	115	50
B3	150	160	0	215	125	150	170	130	110	160	260	200	75	150
B4	125	235	215	0	90	130	195	150	190	50	85	155	155	185
B5	100	160	125	90	0	70	135	110	135	40	135	155	65	120
B6	175	105	150	130	70	0	70	175	200	95	125	225	70	55
B7	235	45	170	195	135	70	0	235	250	165	180	290	110	20
B8	25	245	130	150	110	175	235	0	40	110	225	70	130	215
B9	65	255	110	190	135	200	250	40	0	145	265	100	135	230
B10	95	195	160	50	40	95	165	110	145	0	115	135	105	150
B11	210	225	260	85	135	125	180	225	265	115	0	240	185	175
B12	55	310	200	155	155	225	290	70	100	135	240	0	190	270
B13	135	115	75	155	65	70	110	130	135	105	185	190	0	90

1.2 Σχέδιο Σωτηρία (εμβόλια covid)

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

Table 1.2: Minutes (near=green and far=red)

Town	B1	B2	B3	B4	B5	B6
A	786	549	657	331	559	250
B1	0	668	979	593	224	905
B2	668	0	316	607	472	467
B3	979	316	0	890	769	400
B4	593	607	890	0	386	559
B5	224	472	769	386	0	681