Оптимальная маршрутизация

Представим как транспортную задачу с промежуточными пунктами. Будем считать, что транспортные расходы при перевозке одной единицы груза равны (в условных единицах) расстояниям между вершинами. Одна единица груза отправляется из вершины 1 (исходный пункт) и должна прибыть в вершину 7 (пункт назначения). Вершины 2, 3, 4, 5, 6 рассматриваются как промежуточные пункты, которые являются одновременно и исходными пунктами и пунктами назначения.

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

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

Буквой М обозначается случай, когда между соответствующими вершинами нет пути. В качестве М берут число, значительно большее самого большего пути. В данной задаче наибольший путь между 5-й и 7-ой вершинами, поэтому можно взять, например, М=50. Для промежуточных пунктов 2, 3, 4, 5, 6 должны быть предусмотрены буферные емкости В. Буферная емкость должна быть не меньшей, чем количество груза, которое перемещается в сети описываемой графом. В данной задаче – В=1. После введения буферных емкостей в первый столбец и нижнюю строку таблицы и замены М=50, получим транспортную задачу.

Решая задачу венгерским методом, получим новую таблицу

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

Перенеся эти результаты на исходную таблицу, получим новую таблицу

Наикратчайший путь из вершины 1 в вершину 7 определяется следующей траекторией:

1 → 2 → 6 → 7

Длина наикратчайшего пути равна: 2 + 2 + 4 = 8.
2. Оптимальное распределение ресурсов

Пусть имеется некоторое количество ресурсов х, которое необходимо распределить между п различными предприятиями, объектами, работами и т.д. так, чтобы получить максимальную суммарную эффективность от выбранного способа распределения.

Введем обозначения: xi — количество ресурсов, выделенных i-му предприятию (i =);

gi(xi) — функция полезности, в данном случае это величина дохода от использования ресурса xi, полученного i-м предприятием;

fk(x) — наибольший доход, который можно получить при использовании ресурсов х от первых k различных предприятий.

Сформулированную задачу можно записать в математической форме:

при ограничениях:

Для решения задачи необходимо получить рекуррентное соотношение, связывающее fk(x) и fk-1(x).

Обозначим через хk количество ресурса, используемого k-м способом (0 ≤ xk ≤ х), тогда для (k — 1) способов остается величина ресурсов, равная (x — xk). Наибольший доход, который получается при использовании ресурса (x — xk) от первых (k — 1) способов, составит fk-1(x — xk).

Для максимизации суммарного дохода от k-гo и первых (k — 1) способов необходимо выбрать xk таким образом, чтобы выполнялись соотношения

Поиск по сайту: