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

Для решения задачи воспользуемся исходным базисным решением, полученным методом северо-западного угла (см. табл. 7).

1. Строим цикл пересчета и подсчитываем АСС для каждой свободной клетки.

 

(1,3) АСС = 9 – 7 + 13 – 22 = –7.

 

 

(1,4) АСС = 16 – 4 + 13 – 22 = 3.

 

 

 

(1.5) АСС = 13 – 8 + 12 – 4 + 13 – 22 = 4.

 

 

 

(2,1) АСС = 5 – 20 + 22 – 13 = –6.

 

 

 

(2,5) АСС = 10 – 8 + 12 – 4 = 10.

 

 

 

(3,1) АСС = 13 – 8 + 12 – 4 + 13 –22 = 4.

 

 

 

(3,2) АСС = 18 – 13 + 4 – 12 = –3.

 

(3,3)

АСС = 15 – 7 + 4 – 12 = 0.

 

 

Есть три клетки с отрицательными АСС. Решение не оптимальное.

2. Выбираем свободную неизвестную, то есть клетку с максимальной по абсолютной величине отрицательной алгебраической суммой стоимостей: (1,3).

3. В вершинах ее цикла пересчета базисные неизвестные имеют следующие значения

Минимальное значение в отрицательной вершине равно 30. В клетки со знаком + прибавляем 30, со знаком минус – отнимаем 30. Получим:

Количество базисных неизвестных не может измениться. Поэтому клетка (2.3) остается базисной со значением неизвестной равной нолю.

Новая матрица перевозок примет вид (табл. 9).

Таблица 9

	B 1	B 2	B 3	B 4	B 5	Запасы (аj)
А 1
А 2
А 3
Потребности (bj)

 

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

руб.

Подсчитаем АСС свободных клеток.

(1,2): 22 – 9 + 7 – 13 = 7;

(1,4): 16 – 4 + 7 – 9 = 10;

(1.5): 13 – 8 + 12 – 4 + 7 – 9 = 11;

(2.1): 5 – 20 + 9 – 7 = –13;

(2.5): 10 – 8 + 12 – 4 = 10;

(3.1): 30 – 20 + 9 – 7 + 4 – 12 = 4;

(3.2): 18 – 13 + 4 – 12 = –3;

(3.3): 15 – 7 + 4 – 12 = 0.

Решение не оптимальное. Надо преобразовать неизвестную (2.1). В ее цикле пересчета надо сдвигать на значение неизвестной в клетке (2.3), т.е. на ноль. Получаем новую матрицу перевозок (табл. 10).

Таблица 10

	B 1	B 2	B 3	B 4	B 5	Запасы
А 1
А 2
А 3
Потребности (bj)

 

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

руб.

Подсчитаем АСС свободных клеток:

(1.2): 22 – 13 + 5 – 20 = –6;

(1.4): 16 – 4 + 5 – 20 = –3;

(1.5): 13 – 8 + 12 – 4 + 5 – 20 = –2;

(2.3): 7 – 5 + 20 – 9 = 13;

(2.5): 10 – 8 + 12 – 4 = 10;

(3.1): 30 – 5 + 4 – 12 = 17;

(3.2): 18 – 13 + 4 – 12 = –3;

(3.3): 15 – 9 + 20 – 5 + 4 – 12 =13.

Решение не оптимальное.

Составим цикл пересчета для клетки (1.2). Получим новое решение (табл. 11).

Таблица 11

	B 1	B 2	B 3	B 4	B 5	Запасы (аj)
А 1
А 2
А 3
Потребности (bj)

 

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

руб.

Подсчитаем АСС таблицы 11:

(1.1): 20 – 22 + 13 – 5 = 6;

(1.4): 16 – 4 + 13 – 22 = 3;

(1.5): 13 – 8 + 12 – 4 + 13 – 22 = 4;

(2.3): 7 – 13 + 22 – 9 = 7;

(2.5): 10 – 8 + 12 – 4 = 10;

(3.1): 30– 5 + 4 – 12 = 17;

(3.2): 18 – 13 + 4 – 12 = –3;

(3.3): 15 – 9 + 22 – 13 + 4 – 12 = 7.

Существует одно значение АСС<0 для клетки (3.2). Составим для нее цикл пересчета. Новое решение имеет вид:

Таблица 12

	B 1	B 2	B 3	B 4	B 5	Запасы (аj)
А 1
А 2
А 3
Потребности (bj)

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

руб.

Подсчитаем АСС для таблицы 12:

(1.1): 20 – 22 + 13 – 5 = 6;

(1.4): 16 – 4 + 13 – 22 = 3;

(1.5): 13 – 8 + 18 – 22 = 1;

(2.3): 7 – 13 + 22 – 9 = 7;

(2.5): 10 – 8 + 12 – 4 = 10;

(3.1): 30 – 5 + 13 – 18 = 20;

(3.2): 15 – 18 + 22 – 9 = 10;

(3.3): 12 – 18 + 13 – 4 = 3.

АСС всех свободных клеток неотрицательны. Следовательно, получено оптимальное решение и минимальная стоимость перевозок Z_min = 1950 руб.

По сравнению с исходным планом (табл. 7), получена экономия за счет оптимизации на рублей.

Ответ: Оптимальный план дан таблицей 12. Минимальная стоимость перевозок Z_min = 1950 рублей.

Получена экономия 390 рублей.

 

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

 

Метод потенциалов является одним из наиболее часто используемых методов уточнения плана перевозок.

Каждой строке с номером i в матрице перевозок приписывается числовое значение , а каждому столбцу с номером j значение . , называются потенциалами, если для каждой заполненной клетки (i; j) выполняется условие:

, (16)

где – тариф перевозки.

Определение. Сумма потенциалов для свободных клеток называется косвенными тарифами .

. (17)

Соотношение между косвенными тарифами свободных клеток базисного решения и их истинными (заданными тарифами) служат критериями оптимальности решения.

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

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

Алгоритм решения транспортной задачи
методом потенциалов

Пусть имеется исходное базисное решение.

1. Для каждой строки и столбца матрицы перевозок необходимо задать потенциалы и для каждой базисной (заполненной) клетки записать уравнение вида (16). Получим систему уравнений для потенциалов.

2. Так как заполненных клеток , то соотношение (16) задают систему простейших уравнений с неизвестными. Дополняя ее условием: , получают единственное решение системы потенциалов. Числа удобно записать в дополнительном столбце справа от матрицы перевозок, а числа в дополнительной строке внизу таблицы.

3. Для каждой свободной строки находят косвенный тариф .

4. Если косвенный тариф больше истинного, то переходят к пункту 5. Если косвенный тариф меньше или равен истинному тарифу, то данное базисное решение является оптимальным.

5. Среди разностей между косвенным и истинным тарифами, найденных в пункте 3, выбирают наибольшую. Находят соответствующую ей свободную клетку.

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

7. Возвращаются к пункту 1 алгоритма.