Network model (operations research) — Δικτυακά μοντέλα
Δικτυακά μοντέλα (στην έρευνα επιχειρήσεων· αγγλ. Network models) — είναι μια κατηγορία μαθηματικών μοντέλων που αναπαριστούν ένα πρόβλημα υπό μορφή γράφου (δικτύου), όπου οι κορυφές (κόμβοι) συμβολίζουν αντικείμενα ή καταστάσεις, και οι ακμές (τόξα) — συνδέσεις ή διεργασίες μεταξύ τους[1]. Στο πλαίσιο της βελτιστοποίησης, με τον όρο «δίκτυο» νοείται συχνά ένας κατευθυνόμενος γράφος, ο οποίος στην επιχειρησιακή ανάλυση αποκαλείται απευθείας «δίκτυο»· οι κορυφές του δικτύου αυτού ονομάζονται κόμβοι και οι ακμές — τόξα[2].
Τα δικτυακά μοντέλα αποτελούν ισχυρό εργαλείο για την ανάλυση και βελτιστοποίηση σύνθετων συστημάτων σε τομείς όπως η εφοδιαστική αλυσίδα, οι τηλεπικοινωνίες, η διαχείριση έργων και τα χρηματοοικονομικά. Η δύναμή τους έγκειται στο υψηλό επίπεδο αφαίρεσης: ένας κόμβος μπορεί να αναπαριστά μια πόλη, έναν δρομολογητή δικτύου υπολογιστών ή ένα στάδιο έργου, ενώ ένα τόξο — έναν δρόμο, ένα κανάλι επικοινωνίας ή μια τεχνολογική λειτουργία.
Ορισμός και ορολογία
Η θεωρία γράφων αποτελεί τη βάση των δικτυακών μοντέλων. Οι βασικές έννοιες είναι:
- Δίκτυο ροής (αγγλ. flow network): κατευθυνόμενος γράφος στον οποίο κάθε ακμή διαθέτει χωρητικότητα (capacity) και ροή (flow). Στον γράφο διακρίνονται δύο ειδικές κορυφές: η πηγή (source), από την οποία εκκινεί η ροή, και η καταβόθρα (sink), στην οποία καταλήγει[1].
- Νόμος διατήρησης ροής: Για οποιαδήποτε κορυφή που δεν είναι πηγή ή καταβόθρα, το συνολικό εισερχόμενο ρεύμα πρέπει να είναι ίσο με το συνολικό εξερχόμενο. Η συνθήκη αυτή αποτελεί διακριτό ανάλογο των φυσικών νόμων διατήρησης[3].
- Δικτυακός προγραμματισμός: Μοντέλο που αναπαριστά ένα έργο ως σύνολο αλληλοεξαρτώμενων εργασιών (τόξα) και γεγονότων (κόμβοι). Τα δίκτυα αυτά είναι κατευθυνόμενοι ακυκλικοί γράφοι, γεγονός που αντικατοπτρίζει τη σειρά εκτέλεσης των εργασιών[4].
Κύριες ιδιότητες και θεωρήματα
Τα δικτυακά μοντέλα διαθέτουν σειρά ειδικών ιδιοτήτων που επιτρέπουν την εφαρμογή εξαιρετικά αποδοτικών αλγορίθμων για την επίλυσή τους.
- Ακεραιότητα λύσεων: Πολλά προβλήματα δικτυακής βελτιστοποίησης (π.χ. μέγιστης ροής ή συντομότερης διαδρομής) διαθέτουν την ιδιότητα ολικής μονομοδικότητας του πίνακα περιορισμών. Χάρη σε αυτό, εφόσον οι παράμετροι του προβλήματος (χωρητικότητες, μήκη) είναι ακέραιοι, η βέλτιστη λύση που βρίσκεται με μεθόδους γραμμικού προγραμματισμού θα είναι επίσης ακέραια χωρίς ανάγκη εισαγωγής πρόσθετων περιορισμών[5][6].
- Θεώρημα μέγιστης ροής – ελάχιστης τομής: Κεντρικό αποτέλεσμα της θεωρίας ροών. Δηλώνει ότι η μέγιστη τιμή ροής από την πηγή στην καταβόθρα ισούται με την ελάχιστη χωρητικότητα μεταξύ όλων των τομών που διαχωρίζουν πηγή και καταβόθρα. Το θεώρημα αυτό καθιερώνει κριτήριο βελτιστότητας για τη ροή και αποτελεί τη βάση πολλών αλγορίθμων[6][7].
- Αρχή βελτιστότητας για συντομότερες διαδρομές: Εάν η διαδρομή από το σημείο Α έως το σημείο Γ είναι η συντομότερη, τότε κάθε τμήμα της (π.χ. από ένα ενδιάμεσο σημείο Β έως το Γ) αποτελεί επίσης τη συντομότερη διαδρομή μεταξύ των αντίστοιχων κορυφών. Η ιδιότητα αυτή, που βρίσκεται στη βάση του δυναμικού προγραμματισμού, εξηγεί την ορθότητα αλγορίθμων όπως ο αλγόριθμος Dijkstra[8].
- Ιδιότητες ελάχιστου εκτείνοντος δένδρου (ΕΕΔ):
- Ιδιότητα τομής: Για οποιαδήποτε τομή του γράφου, η ακμή ελάχιστου βάρους που διασχίζει την τομή ανήκει σε τουλάχιστον ένα ΕΕΔ.
- Ιδιότητα κύκλου: Σε οποιονδήποτε κύκλο του γράφου, η ακμή μέγιστου βάρους δεν ανήκει σε κανένα ΕΕΔ.
Στις ιδιότητες αυτές στηρίζεται η ορθότητα των «άπληστων» αλγορίθμων Prim και Kruskal[9].
Βασικά προβλήματα δικτυακής βελτιστοποίησης
- Πρόβλημα συντομότερης διαδρομής: Εύρεση διαδρομής ελάχιστου συνολικού μήκους (βάρους) μεταξύ δύο δεδομένων κόμβων. Επιλύεται με τον αλγόριθμο Dijkstra (για μη αρνητικά βάρη) ή τον αλγόριθμο Bellman-Ford (για αυθαίρετα βάρη)[8].
- Πρόβλημα μέγιστης ροής: Προσδιορισμός της μέγιστης δυνατής ροής από την πηγή στην καταβόθρα υπό δεδομένες χωρητικότητες τόξων. Κλασική μέθοδος επίλυσης — ο αλγόριθμος Ford–Fulkerson[6].
- Πρόβλημα ελάχιστου εκτείνοντος δένδρου: Εύρεση υπογράφου που συνδέει όλες τις κορυφές του δικτύου με ελάχιστο συνολικό κόστος ακμών.
- Μέθοδος κρίσιμης διαδρομής (CPM): Στα δικτυακά μοντέλα σχεδιασμού, προσδιορισμός της μακρύτερης ακολουθίας εργασιών που καθορίζει τον ελάχιστο δυνατό χρόνο ολοκλήρωσης ολόκληρου του έργου. Οι εργασίες σε αυτή τη διαδρομή έχουν μηδενικό χρονικό απόθεμα[10].
Παραδείγματα
- Συντομότερη διαδρομή: Εύρεση της βέλτιστης διαδρομής από ένα σύστημα πλοήγησης μεταξύ δύο σημείων στον χάρτη μιας πόλης, όπου οι πόλεις αποτελούν κόμβους και οι δρόμοι τόξα με βάρη ίσα με το μήκος ή τον χρόνο διαδρομής.
- Μέγιστη ροή: Προσδιορισμός της μέγιστης χωρητικότητας ενός δικτύου αγωγών, όπου οι αντλιοστάσια αποτελούν κόμβους και οι σωλήνες τόξα με περιορισμένη χωρητικότητα.
- Ελάχιστο εκτείνον δένδρο: Σχεδιασμός δικτύου επικοινωνιών (π.χ. τοποθέτηση οπτικής ίνας) για τη σύνδεση πολλών πόλεων με ελάχιστο συνολικό μήκος καλωδίου.
- Κρίσιμη διαδρομή: Σε ένα έργο κατασκευής κατοικίας, όπου οι εργασίες (εκσκαφή θεμελίων, ανέγερση τοίχων, τοποθέτηση στέγης) έχουν καθορισμένη διάρκεια και τεχνολογικές εξαρτήσεις, η κρίσιμη διαδρομή καθορίζει την ελάχιστη προθεσμία ολοκλήρωσης της κατασκευής. Οποιαδήποτε καθυστέρηση εργασίας σε αυτή τη διαδρομή θα οδηγήσει σε καθυστέρηση ολόκληρου του έργου[10].
Δείτε επίσης
- Έρευνα επιχειρήσεων
- Θεωρία γράφων
- Πρόβλημα μεταφοράς
- Μέθοδος κρίσιμης διαδρομής
- PERT
Παραπομπές
- ↑ 1.0 1.1 "Flow network". Wikipedia. [1]
- ↑ "Тема 10: Сетевые модели". Учебное пособие. Гомель: БелГУТ. [2]
- ↑ "Транспортная сеть". Википедия. [3]
- ↑ "Сетевое планирование". Википедия. [4]
- ↑ Bradley S. P., Hax A. C., Magnanti T. L. (1977). Applied Mathematical Programming. Addison-Wesley. Ch.8: Network Models. [5]
- ↑ 6.0 6.1 6.2 "Задача о максимальном потоке". Википедия. [6]
- ↑ Goldberg A. V., Tardos É., Tarjan R. E. (1990). "Network Flow Algorithms". In: Paths, Flows, and VLSI-Layout. Springer. [7]
- ↑ 8.0 8.1 "Задача о кратчайшем пути". Википедия. [8]
- ↑ "Минимальное остовное дерево". Википедия.
- ↑ 10.0 10.1 "Метод критического пути". Википедия. [9]