Транспортная задача (практика) часть 2

Содержание лекции:

1. Метод Фогеля.
2. Метод потенциалов.
3. Заключение (метод максимального элемента, распределительный метод)

1. Метод Фогеля

Напомним, в чем суть метода аппроксимации Фогеля.

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

Среди разностей выбирают максимальную.

В строке (или столбце), которой данная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации.

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

Задача. Рассмотрим следующую распределительную таблицу:

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

В строке А1 два минимальных тарифа – 1 и 2, разность между ними 1 запишем в дополнительном столбце.  В строке А2 два минимальных тарифа – 4 и 5, разность между ними 1 также запишем в дополнительном столбце. В строке А3 два минимальных тарифа – 2 и 3, разность между ними 1 запишем в дополнительном столбце.

В столбце В1 два минимальных тарифа – 4 и 7, разность между ними 3 запишем в дополнительной строке.   В столбце В2 два минимальных тарифа – 2 и 5, разность между ними 3 запишем в дополнительной строке. В столбце В3 два минимальных тарифа – 1 и 3, разность между ними 2 запишем в дополнительной строке. В столбце В4 два минимальных тарифа – 2 и 6, разность между ними 4 запишем в дополнительной строке.

Максимальная разность равна 4 в столбце В4. Ставим после числа 4 в дополнительной строке знак «-». Находим в этом столбце минимальный тариф – величина 2 в клетке (1; 4). Заносим в эту клетку min(110; 160)=110. Это число соответствует потребностям, т. е. столбец В4 исключаем из дальнейшего решения.

Снова для каждой строки и каждого столбца, кроме В4, находим разности между двумя минимальными тарифами.

В строке А1 два минимальных тарифа – 1 и 7, разность между ними 6 запишем в дополнительном столбце.  В строках А2 и А3 два минимальных тарифа расположены не в столбце В4, поэтому разности между ними – 1 в строке А2 и 1 в строке А3 остаются прежними.

В столбцах В1, В2 и В3 разности между минимальными тарифами прежние – 3, 3 и 2 соответственно.

Максимальная разность равна 6 в строке А1. Ставим после числа 6 в дополнительном столбце знак «-». Находим в этой строке минимальный тариф – величина 1 в клетке (1; 3). Заносим в эту клетку min(190; 160-110=50)=50. Это число соответствует запасам, поэтому строку А1 исключаем из дальнейшего решения.

Снова для каждой строки и каждого столбца, кроме столбца В4 и строки А1, находим разности между двумя минимальными тарифами.

В строках А2 и А3 разности между минимальными тарифами остаются прежними – 1 в строке А2 и 1 в строке А3.

В столбцах В1 разность между минимальными тарифами равна 5. В столбце В2  разности между минимальными тарифами прежняя – число 3. А в столбце В3 – разность между минимальными тарифами равна 6. Эта разность является максимальной среди всех разностей.

Находим в столбце В3, кроме первой строки, минимальный тариф – величина 3 в клетке (3; 3). Заносим в эту клетку min(190-50=140; 170)=140. Это число соответствует потребностям, поэтому столбец В3 исключаем из дальнейшего решения.

Снова для каждой строки и каждого столбца, кроме столбцов В3, В4 и строки А1, находим разности между двумя минимальными тарифами.

В строке А2 эта разность равна 1 (между тарифами 4 и 5).  В строке А3 разность между минимальными тарифами 9 и 2 равна 7.

В столбце В1 разность равна 5, в столбце В2  - 3.

Разность 7 в строке А3 является максимальной среди всех разностей. Ставим после числа 7 в дополнительном столбце знак «-».

Находим в строке А3, кроме столбцов В3 и В4, минимальный тариф – величина 2 в клетке (3; 2). Заносим в эту клетку min(50; 170-140=30)=30. Это число соответствует запасам, поэтому строка А3 исключается из дальнейшего решения.

Снова для каждой строки и каждого столбца, кроме столбцов В3, В4 и строк А1 и А3, находим разности между двумя минимальными тарифами.

В строке А2 эта разность равна 1 (между тарифами 4 и 5). 

В столбцах В1 и В2 разность равна 0, так как в этих столбцах осталась одна неисключенная строка – А2.

Разность 1 в строке А2 является максимальной среди всех разностей. Ставим после числа 1 в дополнительном столбце знак «-».

Находим в строке А2, кроме столбцов В3 и В4, минимальный тариф – величина 4 в клетке (2; 1). Заносим в эту клетку min(120; 140)=120. Это число соответствует потребностям, поэтому столбец В1 исключается из дальнейшего решения.

Для оставшегося столбца В2 разность равна 0. Разность 0 в столбцах В1 и В2 является максимальной. Ставим после числа 0 в дополнительном строке в этих столбцах знак «-».

В последней доступной для заполнения клетке (2; 2) в столбце В2 заносим   min(50-30=20; 140-120=20)=20. Это число соответствует запасам и потребностям одновременно, поэтому строка А2 и столбец В2 исключается из дальнейшего решения. Таким образом, все строки и все столбцы исключены из решения. Это означает, что все запасы исчерпаны и все потребности удовлетворены.

Таким образом, матрица решения имеет вид

Общая стоимость перевозок (целевая функция) равна

2. Метод потенциалов

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

Улучшим опорный план распределительным методом, или методом потенциалов.

Для каждой строки и каждого  столбца последней таблицы найдем потенциалы   и    соответственно. Для этого составим систему уравнений относительно каждой заполненной клетки по формуле

,

где  - стоимость перевозки из пункта А_i  в  пункт  В_j.

   Þ 

Проверим критерий оптимальности для незаполненных клеток:

 ,

где  - стоимость перевозки из пункта А_i  в  пункт  В_j в  незаполненной клетке.

В клетках (1; 3), (1; 4) и (2; 4) критерий оптимальности нарушается, значит, опорный план не оптимальный. Построим цикл перераспределения перевозок для клетки с максимальной оценкой, т. е. для клетки  (1; 4):

В клетке (1; 4) поставим знак  «+», в остальных клетках цикла знаки чередуются. В клетках со знаком «-» найдем минимальный объем перевозки:

Min(40; 130; 110)=40,

т. е. перераспределим по циклу 40 ед. груза: в клетках со знаком «+» прибавим 40, в клетках со знаком «-» вычтем 40. Получим новый план перевозок:

Проверим полученный план на оптимальность методом потенциалов:

   Þ 

Проверим критерий оптимальности для незаполненных клеток:

В клетках (2; 1), (2; 4) и (3; 1) критерий оптимальности нарушается, значит, опорный план не оптимальный. Построим цикл перераспределения перевозок для клетки с максимальной оценкой, т. е. для клетки  (2; 1):

В клетках со знаком «-» найдем минимальный объем перевозки:

Min(120; 70; 90)=70,

т. е. перераспределим по циклу 70 ед. груза.

Получим новый план перевозок:

Проверим полученный план на оптимальность методом потенциалов:

   Þ 

Проверим критерий оптимальности для незаполненных клеток:

В клетке (1; 3) критерий оптимальности нарушается, значит, опорный план не оптимальный. Построим цикл перераспределения перевозок для этой клетки:

В клетках со знаком «-» найдем минимальный объем перевозки:

Min(50; 20)=20,

т. е. перераспределим по циклу 20 ед. груза.

Получим новый план перевозок:

Проверим полученный план на оптимальность методом потенциалов:

   Þ 

Проверим критерий оптимальности для незаполненных клеток:

В клетке (3; 2) критерий оптимальности нарушается, значит, опорный план не оптимальный. Построим цикл перераспределения перевозок для этой клетки:

В клетках со знаком «-» найдем минимальный объем перевозки:

Min(170; 30; 50)=30,

т. е. перераспределим по циклу 30 ед. груза.

Получим новый план перевозок:

Проверим полученный план на оптимальность методом потенциалов:

   Þ 

Проверим критерий оптимальности для незаполненных клеток:

Во всех клетках критерий оптимальности выполняется, следовательно, получен оптимальный план, который совпадает с планом, полученным методом Фогеля.

Целевая функция (суммарные транспортные расходы):

Заключение

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

Метод максимального элемента

Решение транспортной задачи для нахождения максимального значения функции цели:

• проверить задачу на сбалансированность;
• составить план базисным способом северо-западного угла, рассчитать значение функции цели базисного плана;
• составить базисный план методом наилучшего элемента (максимального элемента) на максимальное значение функции цели. Рассчитать функцию цели (F);
• сравнить результат решения двух базисных планов;
• проверить базисный план методом наилучшего элемента на максимальном значении функции цели на оптимальном потенциале и проверить улучшение плана до оптимального результата.

Пример ТЗ на максимум целевой функции

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

Распределительный метод

Один из наиболее простых методов решения транспортных задач - распределительный метод. 

Пусть для транспортной задачи найдено начальное опорное решение Х₁ и вычислено значение целевой функции на этом решении F(Х₁). По доказанной выше теореме для каждой свободной клетки таблицы задачи можно построить единственный цикл, который содержит эту клетку и часть клеток, занятых опорным решением. Обозначив этот цикл и осуществив сдвиг (перераспределение груза) по циклу на величину Q=min{x_ij}, можно получить новое опорное решение Х₂. 

Определим, как изменится целевая функция при переходе к новому опорному решению. При сдвиге на единицу груза по циклу, соответствующему клетке (l,m), приращение целевой функции Δ_lm равно разности двух сумм:

где - сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком “+” ; - сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком “-”. 

В клетках, отмеченных знаком “+”, величины груза прибавляются, что приводит к увеличению значения целевой функции F(X), а в клетках, отмеченных знаком “-”, величины груза уменьшаются, что приводит к уменьшению значения целевой функции. 
Если разность сумм для свободной клетки (l, m) меньше нуля, т.е. Δ _lm< 0, то перераспределение величины θ по соответствующему циклу приведет к уменьшению значения F(X) на величину θ•Δ_lm, т.е. опорное решение можно улучшить. Если же величины Δ_lm, называемые оценками, для всех свободных клеток таблицы транспортной задачи неотрицательны, то значение целевой функции нельзя уменьшить и опорное решение оптимально. Следовательно, признаком оптимальности распределительного метода является условие

Для решения транспортной задачи распределительным методом необходимо найти начальное опорное решение. Затем для очередной опорной клетки (l, m) построить цикл и вычислить оценку Δ_lm. Если оценка неотрицательная, переходят к следующей свободной клетке. Если же оценка отрицательная, следует осуществить сдвиг по циклу на величину Q=min{x_ij}. В результате получится новое опорное решение.

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

Основной алгоритм распределительного метода является не лучшим методом решения транспортных задач, так как на каждой итерации для проверки опорного плана на оптимальность приходилось строить [mп—(m+n—1)] циклов пересчета, что при больших размерах матрицы оказывается очень громоздким и трудоемким делом. Так, для расчетов по матрице 10х10 на каждой итерации надо строить 81 цикл, а по матрице 20x20 — 361 цикл.

Список литературы

1. Интрилигатор М. Математические методы оптимизации и экономическая теория. М.: Изд. Айрис-Пресс, 2002.

2. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. М.: Высшая школа, 2001.

3. Глухов В.В., Медников М.Д., Коробко С.Б. Математические методы и модели для менеджмента. СПб.: Лань, 2000.

4. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании. М.: Изд. ДЕЛО, 2003.

5. Ларичев О.И. Теория и методы принятия решений. М.: Логос, 2000.