ΔΠΜΣ: ΕΠΙΣΤΗΜΗ ΚΑΙ ΤΕΧΝΟΛΟΓΙΑ ΥΔΑΤΙΚΩΝ ΠΟΡΩΝ
ΜΑΘΗΜΑ: ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ ΣΥΣΤΗΜΑΤΩΝ ΥΔΑΤΙΚΩΝ ΠΟΡΩΝ
Εργασία 3: Γραμμικός
προγραμματισμός
Α. Βελτιστοποίηση αξιοποίησης υδατικών
πόρων για ύδρευση με θεώρηση οικονομικών, ποιοτικών και υδραυλικών παραμέτρων
Α1. Η πόλη Α υδρεύεται από τρεις πηγές: (α) τον ποταμό Π μέσω έργου υδροληψίας, (β) τον υπόγειο υδροφορέα Υ μέσω γεωτρήσεων και (γ) τη φυσική λίμνη Λ μέσω υδροληψίας και στη συνέχεια άντλησης. Το κόστος μεταφοράς νερού είναι αμελητέο για την πηγή Π, και 0.05 και 0.03 €/m3 για τις πηγές Υ και Λ, αντίστοιχα. Στον Πίνακα 1 δίνονται οι τιμές για τρεις χαρακτηριστικούς δείκτες της ποιότητας του νερού για καθεμιά από τις τρεις πηγές και για τους μήνες Ιανουάριο και Ιούλιο. Να βρεθούν τα ποσοστά (%) που θα πρέπει να αποληφθούν από καθεμιά απ’ τις τρεις πηγές σε τρόπο ώστε να ελαχιστοποιηθεί το μέσο (σταθμισμένο) κόστος μεταφοράς του m3 νερού στην πόλη, παίρνοντας υπόψη ότι τα ποιοτικά χαρακτηριστικά μετά την ανάμιξη του νερού δεν θα πρέπει να ξεπερνούν τα όρια που φαίνονται στο Πίνακα 1 (σύμφωνα με τις οδηγίες επεξεργασίας επιφανειακών νερών που προορίζονται για πόση, για επεξεργασία κατηγορίας Α1).
Υποδείξεις / διευκρινίσεις: Θεωρήστε ως μεταβλητές ελέγχου τα ποσοστά πΠ και πΛ απολήψεων από τις πηγές Π και Λ, αντίστοιχα. Καταστρώστε την αντικειμενική συνάρτηση και τους περιορισμούς συναρτήσει των μεταβλητών ελέγχου. Στη συνέχεια απεικονίστε γραφικά (σε λογιστικό φύλλο Excel) τους περιορισμούς και προσδιορίστε την εφικτή (ή επιτρεπτή) περιοχή. Επαληθεύστε την κυρτότητά της και προσδιορίστε τα ακραία επιτρεπτά σημεία. Τέλος απεικονίστε γραφικά την αντικειμενική συνάρτηση και βρείτε τη βέλτιστη λύση από τη γραφική παράσταση.
Πίνακας 1: Ποιοτικά χαρακτηριστικά νερού.
|
Ποιοτικός δείκτης |
Ποταμός Π |
Υδροφορέας Υ |
Λίμνη Λ |
Απαίτηση στην πόλη Α |
|||
|
Ιαν. |
Ιούλ. |
Ιαν. |
Ιούλ. |
Ιαν. |
Ιούλ. |
||
|
Θολότητα (μονάδες NTU) |
20 |
20 |
5 |
5 |
30 |
30 |
15 |
|
Συγκέντρωση νιτρικού αζώτου (mg/L) |
5 |
30 |
30 |
20 |
10 |
10 |
25 |
|
Συγκέντρωση χλωριόντων (mg/L) |
20 |
20 |
330 |
330 |
40 |
40 |
250 |
Α2. Στο παραπάνω πρόβλημα δε λάβαμε καθόλου υπόψη περιορισμούς που αναφέρονται στις απολήψιμες ποσότητες νερού. Τέτοιοι περιορισμοί ασφαλώς υπάρχουν. Να λυθεί, λοιπόν, το πρόβλημα Α1 με τα επιπλέον δεδομένα ότι η υδρευτική κατανάλωση στην πόλη και οι μέγιστες (ασφαλείς) απολήψιμες ποσότητες νερού από καθεμιά από τις τρεις πηγές είναι όπως στον Πίνακα 2.
Υποδείξεις / διευκρινίσεις: Θεωρήστε ως μεταβλητές ελέγχου τους όγκους απόληψης από τις τρεις πηγές. Καταστρώστε την αναλυτική έκφραση του προβλήματος. Τυποποιήστε την έκφραση εισάγοντας τις αναγκαίες χαλαρές (slack) μεταβλητές. Επίσης, εκφράστε το δυαδικό πρόβλημα. Στη συνέχεια καταστρώστε το πρόβλημα υπό μορφή λογιστικού φύλλου Excel και επιλύστε το με τον επιλυτή simplex. Επί πλέον, καταρτίστε εκθέσεις αποτελεσμάτων και ανάλυσης ευαισθησίας στο Excel και ερμηνεύστε τις.
Πίνακας 2: Ποσοτικά χαρακτηριστικά προσφοράς και ζήτησης νερού.
|
|
Ασφαλής απόληψη από τον ποταμό Π |
Ασφαλής απόληψη από τον υδροφορέα Υ |
Ασφαλής απόληψη από τη λίμνη Λ |
Απαίτηση στην πόλη Α |
||||
|
Ιαν. |
Ιούλ. |
Ιαν. |
Ιούλ. |
Ιαν. |
Ιούλ. |
Ιαν. |
Ιούλ. |
|
|
Ποσότητα νερού (hm3) |
8 |
4 |
7 |
7 |
10 |
10 |
10 |
14 |
Α3. Στα προηγούμενα προβλήματα κάναμε προσεγγιστικές θεωρήσεις σχετικά με το κόστος μεταφοράς νερού, ενώ δε λάβαμε υπόψη τα υδραυλικά χαρακτηριστικά του δικτύου μεταφοράς και συγκεκριμένα την παροχετευτικότητα κάθε αγωγού. Να βρεθεί ο ακριβής και λεπτομερής τρόπος μεταφοράς των ποσοτήτων νερού που προσδιορίστηκαν στο πρόβλημα Α2, σε τρόπο ώστε να ελαχιστοποιηθεί το κόστος μεταφοράς, αν το δίκτυο μεταφοράς έχει την τοπολογία του Σχήματος 1, με τις αντίστοιχες παροχετευτικότητες και τα αντίστοιχα κόστη που σημειώνονται στο σχήμα.
Υποδείξεις / διευκρινίσεις: Παραστήστε το πρόβλημα υπό μορφή διγραφήματος (digraph). Οργανώστε το και επιλύστε το με τη δικτυακή μέθοδο simplex (network simplex method) καθώς και με τον τυπικό επιλυτή simplex του Excel. Αναφέρατε τα πλεονεκτήματα και μειονεκτήματα της δικτυακής μεθόδου σε σχέση με την τυπική. Μεταβάλλετε κατά βούληση τις τιμές της παροχετευτικότητας και κόστους και παρατηρήστε πώς επηρεάζονται τα αποτελέσματα. Εφαρμόζοντας το θεώρημα ελάχιστης τομής – μέγιστης ροής (min-cut, max-flow) βρείτε τη μέγιστη παροχή που μπορεί να φτάσει στην πόλη.
Σχήμα 1: Δίκτυο μεταφοράς. Ο πρώτος αριθμός σε κάθε αγωγό εκφράζει την παροχετευτικότητα σε hm3/μήνα και ο δεύτερος το αντίστοιχο κόστος σε λεπτά του €/m3. Ο αγωγός που συνδέει τους ενδιάμεσους κόμβους 1-2 επιτρέπει ροή και προς τις δύο κατευθύνσεις (είναι κλειστός αγωγός εφοδιασμένος με αντλιοστάσιο).
Α4. Στην πραγματικότητα, το κόστος νερού, και επομένως και η βέλτιστη λύση απολήψεων, εξαρτάται από τον ακριβή τρόπο μεταφοράς του. Ωστόσο, στο πρόβλημα Α3 για απλοποίηση θεωρήσαμε ως δεδομένες τις απολήψεις ανά πηγή. Να ξανακαταστρωθεί και να επιλυθεί σε πλήρη μορφή το συνολικό πρόβλημα με τους ποιοτικούς περιορισμούς του προβλήματος Α1, τους ποσοτικούς περιορισμούς του προβλήματος Α2 και τις τιμές της παροχετευτικότητας και του κόστους του προβλήματος Α3. Ποιος είναι ο κατάλληλος αλγόριθμος επίλυσης;
Α5. Σε περίπτωση που, παράλληλα με την υδρευτική
χρήση των προηγούμενων προβλημάτων, είχαμε και αρδευτική και βιομηχανική χρήση,
εξυπηρετούμενες από τους ίδιους υδατικούς πόρους, αλλά με ένα πιο πολύπλοκο
δίκτυο μεταφοράς, το οποίο κατέληγε σε τρεις τελικούς κόμβους με διαφορετικές
ποιοτικές και ποσοτικές απαιτήσεις, πώς θα διατυπωνόταν το πρόβλημα Α4; Θα ήταν
πρόβλημα γραμμικού προγραμματισμού ή όχι;
B. Βελτιστοποίηση προγραμματισμού
κατασκευής υδραυλικού έργου
Β1. Υδροηλεκτρικό έργο αποτελείται από 9 συνιστώσες, οι οποίες φαίνονται στον Πίνακα 3 μαζί με τα βασικά στοιχεία τους που αφορούν στον προγραμματισμό της κατασκευής του έργου. Να καταστρωθεί το χρονοδιάγραμμα κατασκευής του έργου υπό μορφή διαγράμματος Gantt.
Υποδείξεις / διευκρινίσεις: Χρησιμοποιήστε το μοντέλο κρίσιμης διαδρομής (critical path model – CPM). Καταστρώστε το δίκτυο κατασκευής του έργου, επιλύστε το και βρείτε τις κρίσιμες δραστηριότητες και την κρίσιμη διαδρομή. Στη συνέχεια μεταφράστε τα αποτελέσματα σε μορφή διαγράμματος Gantt.
Πίνακας 3: Συνιστώσες υδροηλεκτρικού έργου και βασικά στοιχεία προγραμματισμού της κατασκευής του.
|
Α/Α |
Δραστηριότητα |
Προαπαιτούμενες δραστηριότητες |
Διάρκεια (μήνες) |
Κόστος επιτάχυνσης (k€/μήνα) |
|
Α |
Σήραγγα εκτροπής |
|
8 |
|
|
Β |
Πρόφραγμα |
Α |
5 |
290 |
|
Γ |
Σιμεντενέσεις |
Β |
5 |
230 |
|
Δ |
Θεμελίωση φράγματος |
Γ |
7 |
350 |
|
Ε |
Φράγμα |
Δ |
24 |
440 |
|
Ζ |
Υπερχειλιστής |
|
28 |
300 |
|
Η |
Υδροληψία |
|
16 |
220 |
|
Θ |
Σταθμός παραγωγής |
Η |
24 |
210 |
|
Ι |
Τελικές εργασίες |
Δ, Ε, Ζ, Θ |
8 |
730 |
B2. Μετά την ολοκλήρωση του προφράγματος αποφασίστηκε η επιτάχυνση του έργου κατά 5 μήνες. Να αναθεωρηθεί το χρονοδιάγραμμα του έργου ώστε να επιτευχθεί αυτός ο στόχος με το ελάχιστο δυνατό προσθετικό κόστος, παίρνοντας υπόψη ότι καμιά δραστηριότητα δεν μπορεί να συμπιεστεί περισσότερο από 30% της διάρκειας που φαίνεται στον Πίνακα 2. Το κόστος επιτάχυνσης για κάθε συνιστώσα του έργου δίνεται επίσης στον Πίνακα 2.
Αναγνωρίσεις: Η τοποθέτηση των ποιοτικών όρων και δεδομένων του προβλήματος Α1 (Πίνακας 1) έγινε σε συνεργασία με τον Α. Ανδρεαδάκη. Η τοποθέτηση των δεδομένων του προβλήματος Β1 (Πίνακας 3) έγινε σε συνεργασία με τον Μ. Αφτιά.
© Δ. Κουτσογιάννης, 2000-04