Построение экономико-математической модели

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

Карта, приведенная на рисунке 25, по своей сути сама является сетью, но сеть удобнее представлять в упрощенном виде, не соблюдая масштабов и пропорций, а указывая только связи между вершинами:

Рисунок 32. Сеть поставленной задачи по оптимизации маршрута

Пункты пронумерованы в порядке «слева-направо, сверху-вниз». Стрелки на концах дуг указывают направления, в которых может происходить перемещение транспорта из одного пункта в другой. В целях упрощения расчетов будем считать, что перемещение обратно в пункт 1 из пунктов 2, 3 и 4 невозможно (так как не соответствует требованиям задачи); также невозможен выезд из пункта 15 (так как цель уже достигнута). Рядом с каждой дугой указана ее характеристика (в данном случае – расстояние между пунктами в километрах).

Для решения задач оптимизации маршрута разработаны несколько методов: метод полного перебора вариантов, метод ветвей и границ, метод Дейкстры и т.д. Но для выполнения вручную они требуют значительных затрат времени, а для автоматизированного решения – специальных программных средств.

Практически любую сетевую задачу оптимизации маршрута движения можно решить с помощью методов линейного программирования. В качестве переменных в данной задаче принимаются передвижения по дугам.

Например, передвижение из пункта 2 в пункт 4 будет обозначено переменной X_2-4, а переезд из пункта 4 в пункт 2 – переменной X_2-4. Таким образом, дуге с двумя стрелками на концах будут соответствовать две переменные, дуге с одной стрелкой – одна переменная. Переменные в этой задаче – булевого (двоичного) типа, они принимают значение 0, если перемещение по дуге состоялось, и значение 1, если перемещения не было.

Выезд транспортного средства из пункта 1 может быть описан в следующем виде:

.

Так как переменная булева, то лишь одна из трех переменных примет значение 1. Например, если X_1-3 = 1, то транспортное средство переместится из пункта 1 в пункт 3.

Проезд через остальные пункты будет обеспечен уравнениями следующего вида (пример ‑ уравнение для пятого пункта):

.

По этому условию количество выездов из 5 пункта (во 2, 3, 7 или 8 пункт) равно количеству въездов в него (из 2, 3, 7 или 8 пункта). В левой, как и в правой части уравнения, лишь одна переменная может принять значение 1. Например, X_5-8 = 1 и X_3-5 = 1, таким образом, в пятый пункт транспорт прибыл из третьего, а уедет – в восьмой. Для простоты реализации этих уравнений в «Поиске решения» перенесем переменные из правой части в левую:

.

Достижение конечного (пятнадцатого) пункта будет реализовано следующим уравнением:

.

Целевая функция данной задачи представляет собой пройденное расстояние, находимое как сумма произведений расстояний между пунктами на количество переездов между ними (0 или 1):

.

В структурном виде данная задача записывается следующим образом:

где n – количество вершин сети (или номер конечного пункта назначения), С_i-j – вес дуги i-j (расстояние от i-го пункта до j-го пункта).

Сетевая модель в матричной форме приведена в таблице 36.

Таблица 21. Модель по оптимизации маршрута движения в табличной (матричной форме)

Продолжение таблицы 21