Экономические задачи, связанные с нахождением наилучшей последовательности действий для достижения цели, удобно представлять для восприятия и анализа в виде графов. Граф - совокупность двух конечных множеств: множества точек, которые называются вершинами, и множества пар вершин, которые называются ребрами.
Под сетевой моделью (сетевым графиком) понимается ориентированный граф, вершины которого отображают состояния (характеристики) некоторого объекта (например, строительного объекта, дорожной сети и т.д.), а дуги ‑ работы (процессы), связанные с этим объектом. Каждой дуге соответствует показатель (время, расстояние и т.д.), характеризующий работу (процесс).
Рисунок 30. Пример ориентированного сетевого графика
Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.
В зависимости от задач управления применяют различные типы сетевых моделей, отличающиеся составом информации о комплексе работ (процессов). Среди них можно выделить два основных типа: модели с учетом только временных характеристик (ограничения на ресурсы не накладываются) и модели с учетом временных и ресурсных характеристик.
Модели первого типа не являются оптимизационными. Их применение позволяет найти минимальное время, в течение которого может быть выполнен весь комплекс работ, и определить календарные сроки начала и окончания каждой работы.
Модели второго типа относятся к задачам распределения ресурсов. Эти задачи являются оптимизационными и встречаются в разных постановках. В зависимости от принятого критерия оптимальности и характера ограничений их можно разбить на две основные группы:
задачи минимизации сроков наступления завершающего события при соблюдении заданных ограничений на использование ресурсов;
задачи оптимизации некоторого показателя качества использования ресурсов при заданных сроках выполнения комплекса. К этой группе относится, в частности, задача минимизации ресурсов при заданном времени выполнения комплекса работ.
Частным случаем сетевых моделей являются модели определения оптимального маршрута при различных условиях его формирования.
Постановка задачи и подготовка входной информации
Необходимо найти наиболее короткий маршрут доставки продукции из сельскохозяйственного предприятия (Пункт 1) на перерабатывающее (Пункт 15). Пунктами 2‑14 отмечены все развилки и перекрестки дорог.
Расстояния между пунктами известны и представлены в виде матрицы в таблице 35 (Сi-j, где i – номер пункта отправления, а j – номер пункта прибытия).
Рисунок 31. Карта автодорожной сети
Таблица 20. Расстояния между пунктами дорожной сети, км
№ | |||||||||||||||
9,0 | 16,1 | 7,0 | |||||||||||||
9,0 | 6,5 | 8,1 | |||||||||||||
16,1 | 9,4 | 16,3 | 16,0 | ||||||||||||
7,0 | 6,5 | 9,4 | 6,9 | 10,0 | |||||||||||
8,1 | 16,3 | 7,0 | 14,2 | ||||||||||||
16,0 | 6,9 | 9,0 | 4,2 | ||||||||||||
10,0 | 7,0 | 9,0 | 11,5 | 7,8 | |||||||||||
14,2 | 4,2 | 11,5 | 18,4 | 5,0 | 12,9 | ||||||||||
7,8 | 18,4 | 18,5 | 12,1 | ||||||||||||
5,0 | 18,5 | 18,5 | 13,7 | ||||||||||||
12,9 | 18,5 | 18,8 | 13,5 | ||||||||||||
12,1 | 18,8 | 11,5 | 15,2 | 6,7 | |||||||||||
13,7 | 13,5 | 11,5 | 7,0 | 16,0 | |||||||||||
15,2 | 7,0 | 16,0 | |||||||||||||
6,7 | 16,0 | 16,0 |