Экономико-математическая модель по оптимизации маршрута движения транспортных средств

Экономические задачи, связанные с нахождением наилучшей последовательности действий для достижения цели, удобно представлять для восприятия и анализа в виде графов. Граф - совокупность двух конечных множеств: множества точек, которые называются вершинами, и множества пар вершин, которые называются ребрами.

Под сетевой моделью (сетевым графиком) понимается ориентированный граф, вершины которого отображают состояния (характеристики) некоторого объекта (например, строительного объекта, дорожной сети и т.д.), а дуги ‑ работы (процессы), связанные с этим объектом. Каждой дуге соответствует показатель (время, расстояние и т.д.), характеризующий работу (процесс).

Рисунок 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