Теория графов

      Транспортная  задача может быть решена методами линейного программирования. Однако благодаря особенностям переменных задачи разработаны специальные  методы ее решения. Наиболее применяемый из них метод потенциалов.

   Согласно  методу потенциалов, каждому i-му пункту отправления устанавливается потенциал U_i, который можно интерпретировать как цену продукта в пункте отправления, а каждому j-му пункту назначения устанавливается потенциал V_j, который можно условно принять как цену продукта в пункте назначения равна его цене в пункте отправления плюс транспортные расходы на его доставку, т.е. V_j= U_i+c_ij.

   Алгоритм  решения транспортной задачи методом  потенциалов включает следующие  этапы:

1. определение начального плана перевозок с помощью метода северо-западного угла, наименьших стоимостей или аппроксимации Фогеля;
2. построение системы потенциалов на основе равенства V_j= U_i+c_ij;
3. проверка начального плана на оптимальность, и в случае его на оптимальности реализация циклов перераспределения плана перевозок.

  Третий  этап повторяется до тех пор, пока план перевозок не станет оптимальным.

  Пример. Пусть имеется 3 поставщика и 4 потребителя. Запасы продукта у поставщиков, спрос потребителей и транспортные расходы на доставку единицы продукта от i-го поставщика к j-му потребителю заданы в таблице:

 

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

Решение. Обозначим x_ij – количество продукта, доставляемого от i-го поставщика к j-му потребителю. Тогда модель:

min L = 3x₁₁+5x₁₂+6x₁₃+2x₁₄+6x₂₁+4x₂₂+7x₂₃+5x₂₄+5x₃₁+4x₃₂+6x₃₃+5x₃₄

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

таблица 2

 

     Мы  должны заполнить m+n-1 клеток. Если число заполненных клеток меньше m+n-1 (случай вырождения), то недостающие клетки выбираются произвольно и заполняются нулями. Это так называемые условные поставки.

     Первоначальный  план содержит шесть перевозок: от первого  поставщика – 150 ед. к первому потребителю  и 20 ед. ко второму; от второго поставщика – 210 ед. ко второму и 40 ед. к третьему; от третьего поставщика – 120 ед. к третьему потребителю и 60 ед. к четвертому.

     Построим  систему потенциалов на основе равенства:

     V_j= U_i+c_ij.

     Присвоим  первому поставщику потенциал U₁ =0. От первого поставщика продукт направляют первому и второму потребителям, следовательно, V₁=U₁+c₁₁=0+3=3; V₂=0+5=5. Зная потенциал второго потребителя, найдем потенциал второго поставщика  U₂=V₂.-c₂₂=5-4=1. потенциал третьего потребителя V₃=1+7=8. потенциал третьего поставщика U₃= 8-6=2. Потенциал четвертого потребителя V₄= 2+5=7. Вычислить потенциалы, помещаем в ( табл.3).

     Проверим  первоначальный план на оптимальность. План считывается оптимальным, если для всех свободных ячеек выполняется  условие:

     

     Осуществляем  проверку:

     U1+с₁₃=0+6=6<8 – не выполняется, т.е. если бы продукт отправлялся от первого поставщика к третьему потребителю, то его цена у первого поставщика была бы ниже, чем в первоначальном плане.

     

     Рассчитанные  значения заносятся в свободные ячейки (табл.3). 
 
 
 
 

     таблицы 3

     Итерация 1. целевая функция=2590.

 

     Для улучшения плана (целевая функция = 2690) необходимо переместить перевозку  в ячейку, где условие оптимальности  нарушено больше всего, т.е. разность V_j-(U_i+c_ij) максимальна (ячейка 1.4).

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

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

     Последовательное  улучшение плана в таблицах 3-5. 
 
 
 

     таблицы 4

     Итерация 2. целевая функция=2570.

 

     таблицы 5

     Итерация 3. целевая функция=2550.