Мрежови модел (изследване на операциите)
Jump to navigation
Jump to search
Мрежови модели (в изследването на операциите; англ. Network models) — това е клас математически модели, представящи задача във вид на граф (мрежа), където върховете (възлите) означават обекти или състояния, а ребрата (дъгите) — връзки или процеси между тях[1]. В контекста на оптимизацията под мрежа често се разбира ориентиран граф, който в операционния анализ директно се нарича „мрежа"; върховете на такава мрежа се наричат възли, а ребрата — дъги[2].
Мрежовите модели са мощен инструмент за анализ и оптимизация на сложни системи в области като логистика, телекомуникации, управление на проекти и финанси. Тяхната сила се заключава в високото ниво на абстракция: даден възел може да представлява град, компютърен маршрутизатор или етап от проект, а дъга — път, комуникационен канал или технологична операция.
Определение и терминология
Основа на мрежовите модели е теорията на графите. Ключовите понятия са:
- Мрежа от потоци (англ. flow network): ориентиран граф, в който всяко ребро има пропускателна способност (capacity) и поток (flow). В графа се отделят два специални върха: извор (source), от който потокът произхожда, и приемник (sink), в който той постъпва[1].
- Закон за запазване на потока: За всеки връх, който не е извор или приемник, сумарният входящ поток трябва да е равен на сумарния изходящ поток. Това условие е дискретен аналог на физическите закони за запазване[3].
- Мрежово планиране: Модел, представящ проект като съвкупност от взаимосвързани операции (дъги) и събития (възли). Такива мрежи са ориентирани ацикличен графи, което отразява реда на изпълнение на дейностите[4].
Ключови свойства и теореми
Мрежовите модели притежават редица особени свойства, които позволяват прилагането на високоефективни алгоритми за тяхното решаване.
- Целочисленост на решенията: Много задачи от мрежовата оптимизация (например за максимален поток или за най-кратък път) притежават свойството на пълна унимодулярност на матрицата на ограниченията. Благодарение на това, ако параметрите на задачата (пропускателни способности, дължини) са целочислени, то оптималното решение, намерено чрез методите на линейното програмиране, също ще бъде целочислено без необходимост от въвеждане на допълнителни ограничения[5][6].
- Теорема за максималния поток и минималния разрез: Централен резултат от теорията на потоците. Твърди, че максималната стойност на потока от извора към приемника е равна на минималната пропускателна способност сред всички разрези, разделящи извора и приемника. Тази теорема установява критерий за оптималност на потока и стои в основата на много алгоритми[6][7].
- Принцип на оптималността за най-кратките пътища: Ако пътят от точка А до точка С е най-кратък, то всеки негов участък (например от междинна точка В до С) също е най-краткият път между съответните върхове. Това свойство, което стои в основата на динамичното програмиране, обуславя коректността на алгоритми като алгоритъма на Дейкстра[8].
- Свойства на минималното покриващо дърво (МПД):
- Свойство на разреза: За всеки разрез на графа реброто с минимално тегло, пресичащо разреза, принадлежи на поне едно МПД.
- Свойство на цикъла: В произволен цикъл на графа реброто с максимално тегло не принадлежи на нито едно МПД.
На тези свойства се основава коректността на „алчните" алгоритми на Прим и Крускал[9].
Основни задачи на мрежовата оптимизация
- Задача за най-краткия път: Намиране на път с минимална обща дължина (тегло) между два зададени възла. Решава се с алгоритъма на Дейкстра (за неотрицателни тегла) или алгоритъма на Белман-Форд (за произволни тегла)[8].
- Задача за максималния поток: Определяне на максимално възможния поток от извора към приемника при зададени пропускателни способности на дъгите. Класическият метод за решаване е алгоритъмът на Форд — Фълкерсън[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]