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

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

Содержание

См. также:

Условие задачи

Груз расположен в 5 складах поставщиков: . Известно количество груза , имеющееся в каждом складе . Весь груз нужно перевезти в 4 склада потребителей: . Каждый склад потребителя может принять только определенное количество груза . Известна стоимость перевозки единицы груза от склада поставщика до склада потребителя. Мощности поставщиков , потребителей и матрица издержек на перевозки указана в таблице ⇓.

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

Указание. Первый опорный план составить методом наименьшей стоимости.

Исходные данные задачи

Поставщики Потребители	B₁ 21	B₂ 15	B₃ 7	B₄ 6
A₁ 15	2	6	5	3
A₂ 9	3	2	1	4
A₃ 13	3	6	2	5
A₄ 8	3	6	5	6
A₅ 9	3	6	5	7

Решение задачи методом потенциалов

1. Приведение задачи к закрытому типу

Проверим условие баланса. Находим сумму мощностей поставщиков и потребителей. Поставщиков: 15 + 9 + 13 + 8 + 9 = 54. Потребителей: 21 + 15 + 7 + 6 = 49. Сумма мощностей поставщиков больше суммы мощностей потребителей – модель задачи открытая. Для решения транспортной задачи ее модель нужно привести к закрытому типу. Для этого вводим фиктивного потребителя Φ с мощностью 54 – 49 = 5. В результате модель задачи становится закрытой. С учетом фиктивного потребителя, сумма мощностей поставщиков равна сумме мощностей потребителей. Считаем, что стоимость перевозки единицы груза от любого поставщика к фиктивному потребителю равна нулю.

Задача, приведенная к закрытому типу

Поставщики Потребители	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Ф 5
A₁ 15	2	6	5	3	0
A₂ 9	3	2	1	4	0
A₃ 13	3	6	2	5	0
A₄ 8	3	6	5	6	0
A₅ 9	3	6	5	7	0

Решаем задачу методом потенциалов.

2. Составление первого опорного плана методом наименьшей стоимости

Составляем первый опорный план методом наименьшей стоимости. Фиктивного потребителя Φ заполняем в последнюю очередь. Наименьшая стоимость 1 в клетке (2, 3). Даем в нее наибольшую поставку 7. Потребитель B₃ получил требуемое количество груза: b₃ = 7. Вычеркиваем столбец B₃.

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2	6	5	3	0
A₂9	3	2	1 7	4	0
A₃13	3	6	2	5	0
A₄8	3	6	5	6	0
A₅9	3	6	5	7	0

Среди не зачеркнутых клеток, наименьшая стоимость 2 в клетке (1, 1). Даем в нее наибольшую поставку 15. Поставщик A₁ реализовал весь имеющийся у него груз: a₁ = 15. Вычеркиваем строку A₁.

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 15	6	5	3	0
A₂9	3	2	1 7	4	0
A₃13	3	6	2	5	0
A₄8	3	6	5	6	0
A₅9	3	6	5	7	0

Среди не зачеркнутых клеток, наименьшая стоимость 2 в клетке (2, 2). Даем в нее наибольшую поставку 2. Поставщик A₂ реализовал весь имеющийся у него груз: a₂ = 2 + 7 = 9. Вычеркиваем строку A₂.

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 15	6	5	3	0
A₂9	3	2 2	1 7	4	0
A₃13	3	6	2	5	0
A₄8	3	6	5	6	0
A₅9	3	6	5	7	0

Среди не зачеркнутых клеток, наименьшая стоимость 3 в клетке (3, 1). Даем в нее наибольшую поставку 6. Потребитель B₁ получил требуемое количество груза: b₁ = 15 + 6 = 21. Вычеркиваем столбец B₁.

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 15	6	5	3	0
A₂9	3	2 2	1 7	4	0
A₃13	3 6	6	2	5	0
A₄8	3	6	5	6	0
A₅9	3	6	5	7	0

Среди не зачеркнутых клеток, наименьшая стоимость 5 в клетке (3, 4). Даем в нее наибольшую поставку 6. Потребитель B₄ получил требуемое количество груза: b₄ = 6. Вычеркиваем столбец B₄.

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 15	6	5	3	0
A₂9	3	2 2	1 7	4	0
A₃13	3 6	6	2	5 6	0
A₄8	3	6	5	6	0
A₅9	3	6	5	7	0

Среди не зачеркнутых клеток, наименьшая стоимость 6 в клетке (3, 2). Даем в нее наибольшую поставку 1. Поставщик A₃ реализовал весь имеющийся у него груз: a₃ = 6 + 1 + 6 = 13. Вычеркиваем строку A₃.

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 15	6	5	3	0
A₂9	3	2 2	1 7	4	0
A₃13	3 6	6 1	2	5 6	0
A₄8	3	6	5	6	0
A₅9	3	6	5	7	0

Среди не зачеркнутых клеток, наименьшая стоимость 6 в клетке (4, 2). Даем в нее наибольшую поставку 8. Поставщик A₄ реализовал весь имеющийся у него груз: a₄ = 8. Вычеркиваем строку A₄.

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 15	6	5	3	0
A₂9	3	2 2	1 7	4	0
A₃13	3 6	6 1	2	5 6	0
A₄8	3	6 8	5	6	0
A₅9	3	6	5	7	0

Среди не зачеркнутых клеток, наименьшая стоимость 6 в клетке (5, 2). Даем в нее наибольшую поставку 4. Потребитель B₂ получил требуемое количество груза: b₂ = 2 + 1 + 8 + 4 = 15. Вычеркиваем столбец B₂.

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 15	6	5	3	0
A₂9	3	2 2	1 7	4	0
A₃13	3 6	6 1	2	5 6	0
A₄8	3	6 8	5	6	0
A₅9	3	6 4	5	7	0

Даем наибольшую поставку 5 в оставшуюся не зачеркнутую клетку (5, 5). Получаем первый опорный план.

Таблица 1.1

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 15	6	5	3	0
A₂9	3	2 2	1 7	4	0
A₃13	3 6	6 1	2	5 6	0
A₄8	3	6 8	5	6	0
A₅9	3	6 4	5	7	0 5

Найдем значение целевой функции F₁ для первого опорного плана. Она равна сумме всех затрат на перевозки. Умножим стоимость перевозки единицы груза на количество перевезенного груза , и просуммируем по всем клеткам:

.

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

3. Построение оптимального плана

3.1. Шаг 1

Находим потенциалы u_i, v_j. Для этого нам нужно решить приведенную ниже систему уравнений, используя только заполненные клетки:
u₁ = 0;
u_i + v_j = c_ij.
Полагаем u₁ = 0.
Для клетки (1, 1): v₁ = c_1,1 – u₁ = 2 – 0 = 2;
Для клетки (3, 1): u₃ = c_3,1 – v₁ = 3 – 2 = 1;
Для клетки (3, 2): v₂ = c_3,2 – u₃ = 6 – 1 = 5;
Для клетки (2, 2): u₂ = c_2,2 – v₂ = 2 – 5 = -3;
Для клетки (2, 3): v₃ = c_2,3 – u₂ = 1 – -3 = 4;
Для клетки (3, 4): v₄ = c_3,4 – u₃ = 5 – 1 = 4;
Для клетки (4, 2): u₄ = c_4,2 – v₂ = 6 – 5 = 1;
Для клетки (5, 2): u₅ = c_5,2 – v₂ = 6 – 5 = 1;
Для клетки (5, 5): v₅ = c_5,5 – u₅ = 0 – 1 = -1.
Заносим потенциалы в таблицу 1.2.

Таблица 1.2

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5	u
A₁15	2 15	6	5	3	0	0
A₂9	3	2 2	1 7	4	0	-3
A₃13	3 6	6 1	2	5 6	0	1
A₄8	3	6 8	5	6	0	1
A₅9	3	6 4	5	7	0 5	1
v	2	5	4	4	-1

Находим оценки свободных клеток по формуле:
Δ_ij = c_ij – u_i – v_j.
Δ_1,2 = c_1,2 – u₁ – v₂ = 6 – 0 – 5 = 1;
Δ_1,3 = c_1,3 – u₁ – v₃ = 5 – 0 – 4 = 1;
Δ_1,4 = c_1,4 – u₁ – v₄ = 3 – 0 – 4 = -1;
Δ_1,5 = c_1,5 – u₁ – v₅ = 0 – 0 – (-1) = 1;
Δ_2,1 = c_2,1 – u₂ – v₁ = 3 – (-3) – 2 = 4;
Δ_2,4 = c_2,4 – u₂ – v₄ = 4 – (-3) – 4 = 3;
Δ_2,5 = c_2,5 – u₂ – v₅ = 0 – (-3) – (-1) = 4;
Δ_3,3 = c_3,3 – u₃ – v₃ = 2 – 1 – 4 = -3;
Δ_3,5 = c_3,5 – u₃ – v₅ = 0 – 1 – (-1) = 0;
Δ_4,1 = c_4,1 – u₄ – v₁ = 3 – 1 – 2 = 0;
Δ_4,3 = c_4,3 – u₄ – v₃ = 5 – 1 – 4 = 0;
Δ_4,4 = c_4,4 – u₄ – v₄ = 6 – 1 – 4 = 1;
Δ_4,5 = c_4,5 – u₄ – v₅ = 0 – 1 – (-1) = 0;
Δ_5,1 = c_5,1 – u₅ – v₁ = 3 – 1 – 2 = 0;
Δ_5,3 = c_5,3 – u₅ – v₃ = 5 – 1 – 4 = 0;
Δ_5,4 = c_5,4 – u₅ – v₄ = 7 – 1 – 4 = 2.
Поскольку есть отрицательные оценки, то план не оптимален.

Наименьшая оценка Δ_3,3 = -3 в клетке (3,3). Вводим ее в базис. Строим цикл для этой клетки. Изображаем его в таблице 1.3. Расставляем знаки ′+′ и ′–′ в вершинах цикла, чередуя их, начиная со знака ′+′ в клетке (3,3).

Таблица 1.3

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 15	6	5	3	0
A₂9	3	+ 2 2	– 1 7	4	0
A₃13	3 6	– 6 1	+ 2	5 6	0
A₄8	3	6 8	5	6	0
A₅9	3	6 4	5	7	0 5

Переходим к следующему опорному плану. Для этого определяем наименьшее значение поставок в вершинах цикла со знаком ′–′. Оно равно 1 в клетке (3,2). Выполняем сдвиг по циклу на величину 1: в клетках, помеченных знаком ′+′, прибавляем 1; в клетках, помеченных знаком ′–′, вычитаем 1. В результате клетка (3,3) входит в базис со значением 1, а клетка (3,2) выходит из базиса.
Получаем таблицу 2.1.

Таблица 2.1

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 15	6	5	3	0
A₂9	3	2 3	1 6	4	0
A₃13	3 6	6	2 1	5 6	0
A₄8	3	6 8	5	6	0
A₅9	3	6 4	5	7	0 5

Целевая функция:
F₂ = 2·15 + 2·3 + 1·6 + 3·6 + 2·1 + 5·6 + 6·8 + 6·4 + 0·5 = 164
Мы видим, что целевая функция стала меньше. Изменение целевой функции:
.
Оно равно произведению оценки клетки (3,3), которую мы ввели в базис, на поставку в эту клетку:
.

3.2. Шаг 2. Переход к вырожденному плану

Выясним, является ли новый план оптимальным. Для этого находим потенциалы u_i, v_j. Решаем систему уравнений, используя только заполненные клетки:
u₁ = 0;
u_i + v_j = c_ij.
Полагаем u₁ = 0.
Для клетки (1, 1): v₁ = c_1,1 – u₁ = 2 – 0 = 2;
Для клетки (3, 1): u₃ = c_3,1 – v₁ = 3 – 2 = 1;
Для клетки (3, 3): v₃ = c_3,3 – u₃ = 2 – 1 = 1;
Для клетки (2, 3): u₂ = c_2,3 – v₃ = 1 – 1 = 0;
Для клетки (2, 2): v₂ = c_2,2 – u₂ = 2 – 0 = 2;
Для клетки (3, 4): v₄ = c_3,4 – u₃ = 5 – 1 = 4;
Для клетки (4, 2): u₄ = c_4,2 – v₂ = 6 – 2 = 4;
Для клетки (5, 2): u₅ = c_5,2 – v₂ = 6 – 2 = 4;
Для клетки (5, 5): v₅ = c_5,5 – u₅ = 0 – 4 = -4.
Заносим потенциалы в таблицу 2.2.

Таблица 2.2

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5	u
A₁15	2 15	6	5	3	0	0
A₂9	3	2 3	1 6	4	0	0
A₃13	3 6	6	2 1	5 6	0	1
A₄8	3	6 8	5	6	0	4
A₅9	3	6 4	5	7	0 5	4
v	2	2	1	4	-4

Находим оценки свободных клеток по формуле:
Δ_ij = c_ij – u_i – v_j.
Δ_1,2 = c_1,2 – u₁ – v₂ = 6 – 0 – 2 = 4;
Δ_1,3 = c_1,3 – u₁ – v₃ = 5 – 0 – 1 = 4;
Δ_1,4 = c_1,4 – u₁ – v₄ = 3 – 0 – 4 = -1;
Δ_1,5 = c_1,5 – u₁ – v₅ = 0 – 0 – (-4) = 4;
Δ_2,1 = c_2,1 – u₂ – v₁ = 3 – 0 – 2 = 1;
Δ_2,4 = c_2,4 – u₂ – v₄ = 4 – 0 – 4 = 0;
Δ_2,5 = c_2,5 – u₂ – v₅ = 0 – 0 – (-4) = 4;
Δ_3,2 = c_3,2 – u₃ – v₂ = 6 – 1 – 2 = 3;
Δ_3,5 = c_3,5 – u₃ – v₅ = 0 – 1 – (-4) = 3;
Δ_4,1 = c_4,1 – u₄ – v₁ = 3 – 4 – 2 = -3;
Δ_4,3 = c_4,3 – u₄ – v₃ = 5 – 4 – 1 = 0;
Δ_4,4 = c_4,4 – u₄ – v₄ = 6 – 4 – 4 = -2;
Δ_4,5 = c_4,5 – u₄ – v₅ = 0 – 4 – (-4) = 0;
Δ_5,1 = c_5,1 – u₅ – v₁ = 3 – 4 – 2 = -3;
Δ_5,3 = c_5,3 – u₅ – v₃ = 5 – 4 – 1 = 0;
Δ_5,4 = c_5,4 – u₅ – v₄ = 7 – 4 – 4 = -1.
Поскольку есть отрицательные оценки, то план не оптимален.

Наименьшие оценки Δ_4,1 = Δ_5,1 = -3 в клетках (4,1), (5,1). Мы можем ввести в базис любую из них. Вводим в базис клетку (4,1). Строим цикл для этой клетки. Изображаем его в таблице 2.3. Расставляем знаки ′+′ и ′–′ в вершинах цикла, чередуя их, начиная со знака ′+′ в клетке (4,1).

Таблица 2.3

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 15	6	5	3	0
A₂9	3	+ 2 3	– 1 6	4	0
A₃13	– 3 6	6	+ 2 1	5 6	0
A₄8	+ 3	– 6 8	5	6	0
A₅9	3	6 4	5	7	0 5

Переходим к следующему опорному плану. Для этого определяем наименьшее значение поставок в вершинах цикла со знаком ′–′. Мы видим, что минимальное значение 6 сразу в двух клетках: (2,3) и (3,1). Если мы выполним сдвиг по циклу, то в обеих этих клетках будут нулевые поставки. Из базиса можно исключить любую из этих клеток. Мы исключим клетку (3,1), поскольку у нее больше значение затрат на перевозку единицы груза: . Выполняем сдвиг по циклу на величину 6: в клетках, помеченных знаком ′+′, прибавляем 6; в клетках, помеченных знаком ′–′, вычитаем 6. В результате клетка (4,1) входит в базис со значением 6, а клетка (3,1) выходит из базиса.
Получаем таблицу 3.1.

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

Таблица 3.1

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 15	6	5	3	0
A₂9	3	2 9	1 0	4	0
A₃13	3	6	2 7	5 6	0
A₄8	3 6	6 2	5	6	0
A₅9	3	6 4	5	7	0 5

Целевая функция:
F₃ = 2·15 + 2·9 + 1·0 + 2·7 + 5·6 + 3·6 + 6·2 + 6·4 + 0·5 = 146
Она стала еще меньше. Изменение целевой функции:
.
Оно равно произведению оценки клетки (4,1), которую мы ввели в базис, на поставку в эту клетку:
.

3.3. Шаг 3

Снова проверяем, является ли новый план оптимальным. Находим потенциалы u_i, v_j. Решаем систему уравнений, используя только заполненные клетки:
u₁ = 0;
u_i + v_j = c_ij.
Полагаем u₁ = 0.
Для клетки (1, 1): v₁ = c_1,1 – u₁ = 2 – 0 = 2;
Для клетки (4, 1): u₄ = c_4,1 – v₁ = 3 – 2 = 1;
Для клетки (4, 2): v₂ = c_4,2 – u₄ = 6 – 1 = 5;
Для клетки (2, 2): u₂ = c_2,2 – v₂ = 2 – 5 = -3;
Для клетки (2, 3): v₃ = c_2,3 – u₂ = 1 – -3 = 4;
Для клетки (3, 3): u₃ = c_3,3 – v₃ = 2 – 4 = -2;
Для клетки (3, 4): v₄ = c_3,4 – u₃ = 5 – -2 = 7;
Для клетки (5, 2): u₅ = c_5,2 – v₂ = 6 – 5 = 1;
Для клетки (5, 5): v₅ = c_5,5 – u₅ = 0 – 1 = -1.
Заносим потенциалы в таблицу 3.2.

Таблица 3.2

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5	u
A₁15	2 15	6	5	3	0	0
A₂9	3	2 9	1 0	4	0	-3
A₃13	3	6	2 7	5 6	0	-2
A₄8	3 6	6 2	5	6	0	1
A₅9	3	6 4	5	7	0 5	1
v	2	5	4	7	-1

Находим оценки свободных клеток:
Δ_ij = c_ij – u_i – v_j.
Δ_1,2 = c_1,2 – u₁ – v₂ = 6 – 0 – 5 = 1;
Δ_1,3 = c_1,3 – u₁ – v₃ = 5 – 0 – 4 = 1;
Δ_1,4 = c_1,4 – u₁ – v₄ = 3 – 0 – 7 = -4;
Δ_1,5 = c_1,5 – u₁ – v₅ = 0 – 0 – (-1) = 1;
Δ_2,1 = c_2,1 – u₂ – v₁ = 3 – (-3) – 2 = 4;
Δ_2,4 = c_2,4 – u₂ – v₄ = 4 – (-3) – 7 = 0;
Δ_2,5 = c_2,5 – u₂ – v₅ = 0 – (-3) – (-1) = 4;
Δ_3,1 = c_3,1 – u₃ – v₁ = 3 – (-2) – 2 = 3;
Δ_3,2 = c_3,2 – u₃ – v₂ = 6 – (-2) – 5 = 3;
Δ_3,5 = c_3,5 – u₃ – v₅ = 0 – (-2) – (-1) = 3;
Δ_4,3 = c_4,3 – u₄ – v₃ = 5 – 1 – 4 = 0;
Δ_4,4 = c_4,4 – u₄ – v₄ = 6 – 1 – 7 = -2;
Δ_4,5 = c_4,5 – u₄ – v₅ = 0 – 1 – (-1) = 0;
Δ_5,1 = c_5,1 – u₅ – v₁ = 3 – 1 – 2 = 0;
Δ_5,3 = c_5,3 – u₅ – v₃ = 5 – 1 – 4 = 0;
Δ_5,4 = c_5,4 – u₅ – v₄ = 7 – 1 – 7 = -1.
Поскольку есть отрицательные оценки, то план не оптимален.

Наименьшая оценка Δ_1,4 = -4 в клетке (1,4). Вводим ее в базис. Строим цикл для этой клетки. Изображаем его в таблице 3.3. Расставляем знаки ′+′ и ′–′ в вершинах цикла, чередуя их, начиная со знака ′+′ в клетке (1,4).

Таблица 3.3

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	– 2 15	6	5	+ 3	0
A₂9	3	+ 2 9	– 1 0	4	0
A₃13	3	6	+ 2 7	– 5 6	0
A₄8	+ 3 6	– 6 2	5	6	0
A₅9	3	6 4	5	7	0 5

Переходим к следующему опорному плану. Для этого определяем наименьшее значение поставок в вершинах цикла со знаком ′–′. Оно равно 0 в клетке (2,3). Выполняем сдвиг по циклу на величину 0: в клетках, помеченных знаком ′+′, прибавляем 0; в клетках, помеченных знаком ′–′, вычитаем 0. В результате клетка (1,4) входит в базис со значением 0, а клетка (2,3) выходит из базиса.
Получаем таблицу 4.1.

Таблица 4.1

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 15	6	5	3 0	0
A₂9	3	2 9	1	4	0
A₃13	3	6	2 7	5 6	0
A₄8	3 6	6 2	5	6	0
A₅9	3	6 4	5	7	0 5

Целевая функция:
F₄ = 2·15 + 3·0 + 2·9 + 2·7 + 5·6 + 3·6 + 6·2 + 6·4 + 0·5 = 146
Ее значение не изменилось, поскольку при переходе к новому базису, изменений поставок не произошло. Мы только изменили состав базисных переменных, перешли от одного вырожденного плана ⇑ к другому.

Возможность зацикливания при вырожденном плане

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

К счастью, при решении задач методом потенциалов, случаи зацикливания не известны, хотя математически не доказано, что их не существует.

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

Для транспортной задачи этот метод заключается в следующем.
1. Вводим малое число ε.
2. Вводим новые значения мощностей поставщиков и потребителей по следующим формулам:
(1) ;
(2)
3. Решаем транспортную задачу методом потенциалов с мощностями и .
В результате получаем приближенное решение задачи, которое, чем меньше ε, тем ближе к истинному решению.

Доказано, (см. [3] стр. 369 ⇓) что при замене (1) – (2):
1) отсутствуют вырожденные опорные планы;
2) при , решение задачи стремится к истинному решению:
.
Здесь и – решение задачи с мощностями и .
То есть, при достаточно малом ε, мы получаем приближенное решение транспортной задачи.

См. Приближенное решение этой задачи без вырожденных опорных планов

3.4. Шаг 4

Находим потенциалы u_i, v_j. Для этого нам нужно решить приведенную ниже систему уравнений, используя только заполненные клетки:
u₁ = 0;
u_i + v_j = c_ij.
Полагаем u₁ = 0.
Для клетки (1, 1): v₁ = c_1,1 – u₁ = 2 – 0 = 2;
Для клетки (1, 4): v₄ = c_1,4 – u₁ = 3 – 0 = 3;
Для клетки (3, 4): u₃ = c_3,4 – v₄ = 5 – 3 = 2;
Для клетки (3, 3): v₃ = c_3,3 – u₃ = 2 – 2 = 0;
Для клетки (4, 1): u₄ = c_4,1 – v₁ = 3 – 2 = 1;
Для клетки (4, 2): v₂ = c_4,2 – u₄ = 6 – 1 = 5;
Для клетки (2, 2): u₂ = c_2,2 – v₂ = 2 – 5 = -3;
Для клетки (5, 2): u₅ = c_5,2 – v₂ = 6 – 5 = 1;
Для клетки (5, 5): v₅ = c_5,5 – u₅ = 0 – 1 = -1.
Заносим потенциалы в таблицу 4.2.

Таблица 4.2

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5	u
A₁15	2 15	6	5	3 0	0	0
A₂9	3	2 9	1	4	0	-3
A₃13	3	6	2 7	5 6	0	2
A₄8	3 6	6 2	5	6	0	1
A₅9	3	6 4	5	7	0 5	1
v	2	5	0	3	-1

Находим оценки свободных клеток по формуле:
Δ_ij = c_ij – u_i – v_j.
Δ_1,2 = c_1,2 – u₁ – v₂ = 6 – 0 – 5 = 1;
Δ_1,3 = c_1,3 – u₁ – v₃ = 5 – 0 – 0 = 5;
Δ_1,5 = c_1,5 – u₁ – v₅ = 0 – 0 – (-1) = 1;
Δ_2,1 = c_2,1 – u₂ – v₁ = 3 – (-3) – 2 = 4;
Δ_2,3 = c_2,3 – u₂ – v₃ = 1 – (-3) – 0 = 4;
Δ_2,4 = c_2,4 – u₂ – v₄ = 4 – (-3) – 3 = 4;
Δ_2,5 = c_2,5 – u₂ – v₅ = 0 – (-3) – (-1) = 4;
Δ_3,1 = c_3,1 – u₃ – v₁ = 3 – 2 – 2 = -1;
Δ_3,2 = c_3,2 – u₃ – v₂ = 6 – 2 – 5 = -1;
Δ_3,5 = c_3,5 – u₃ – v₅ = 0 – 2 – (-1) = -1;
Δ_4,3 = c_4,3 – u₄ – v₃ = 5 – 1 – 0 = 4;
Δ_4,4 = c_4,4 – u₄ – v₄ = 6 – 1 – 3 = 2;
Δ_4,5 = c_4,5 – u₄ – v₅ = 0 – 1 – (-1) = 0;
Δ_5,1 = c_5,1 – u₅ – v₁ = 3 – 1 – 2 = 0;
Δ_5,3 = c_5,3 – u₅ – v₃ = 5 – 1 – 0 = 4;
Δ_5,4 = c_5,4 – u₅ – v₄ = 7 – 1 – 3 = 3.
Поскольку есть отрицательные оценки, то план не оптимален.

Наименьшие оценки Δ_3,5 = Δ_3,1 = Δ_3,2 = -1 в клетках (3,5), (3,1), (3,2). Мы можем ввести в базис любую из них. Вводим в базис клетку (3,5) с наименьшим значением издержек на перевозки (c_3,5 = 0) среди клеток с минимальными оценками. Строим цикл для этой клетки. Изображаем его в таблице 4.3. Расставляем знаки ′+′ и ′–′ в вершинах цикла, чередуя их, начиная со знака ′+′ в клетке (3,5).

Таблица 4.3

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	– 2 15	6	5	+ 3 0	0
A₂9	3	2 9	1	4	0
A₃13	3	6	2 7	– 5 6	+ 0
A₄8	+ 3 6	– 6 2	5	6	0
A₅9	3	+ 6 4	5	7	– 0 5

Переходим к следующему опорному плану. Для этого определяем наименьшее значение поставок в вершинах цикла со знаком ′–′. Оно равно 2 в клетке (4,2). Выполняем сдвиг по циклу на величину 2: в клетках, помеченных знаком ′+′, прибавляем 2; в клетках, помеченных знаком ′–′, вычитаем 2. В результате клетка (3,5) входит в базис со значением 2, а клетка (4,2) выходит из базиса.
Получаем таблицу 5.1.

Таблица 5.1

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 13	6	5	3 2	0
A₂9	3	2 9	1	4	0
A₃13	3	6	2 7	5 4	0 2
A₄8	3 8	6	5	6	0
A₅9	3	6 6	5	7	0 3

Целевая функция:
F₅ = 2·13 + 3·2 + 2·9 + 2·7 + 5·4 + 0·2 + 3·8 + 6·6 + 0·3 = 144
Она стала меньше. Зацикливания не произошло.

3.5. Шаг 5

Как и ранее, находим потенциалы u_i, v_j, используя только заполненные клетки.
u₁ = 0;
u_i + v_j = c_ij.
Полагаем u₁ = 0.
Для клетки (1, 1): v₁ = c_1,1 – u₁ = 2 – 0 = 2;
Для клетки (1, 4): v₄ = c_1,4 – u₁ = 3 – 0 = 3;
Для клетки (3, 4): u₃ = c_3,4 – v₄ = 5 – 3 = 2;
Для клетки (3, 3): v₃ = c_3,3 – u₃ = 2 – 2 = 0;
Для клетки (3, 5): v₅ = c_3,5 – u₃ = 0 – 2 = -2;
Для клетки (4, 1): u₄ = c_4,1 – v₁ = 3 – 2 = 1;
Для клетки (5, 5): u₅ = c_5,5 – v₅ = 0 – (-2) = 2;
Для клетки (5, 2): v₂ = c_5,2 – u₅ = 6 – 2 = 4;
Для клетки (2, 2): u₂ = c_2,2 – v₂ = 2 – 4 = -2.
Заносим потенциалы в таблицу 5.2.

Таблица 5.2

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5	u
A₁15	2 13	6	5	3 2	0	0
A₂9	3	2 9	1	4	0	-2
A₃13	3	6	2 7	5 4	0 2	2
A₄8	3 8	6	5	6	0	1
A₅9	3	6 6	5	7	0 3	2
v	2	4	0	3	-2

Находим оценки свободных клеток по формуле:
Δ_ij = c_ij – u_i – v_j.
Δ_1,2 = c_1,2 – u₁ – v₂ = 6 – 0 – 4 = 2;
Δ_1,3 = c_1,3 – u₁ – v₃ = 5 – 0 – 0 = 5;
Δ_1,5 = c_1,5 – u₁ – v₅ = 0 – 0 – (-2) = 2;
Δ_2,1 = c_2,1 – u₂ – v₁ = 3 – (-2) – 2 = 3;
Δ_2,3 = c_2,3 – u₂ – v₃ = 1 – (-2) – 0 = 3;
Δ_2,4 = c_2,4 – u₂ – v₄ = 4 – (-2) – 3 = 3;
Δ_2,5 = c_2,5 – u₂ – v₅ = 0 – (-2) – (-2) = 4;
Δ_3,1 = c_3,1 – u₃ – v₁ = 3 – 2 – 2 = -1;
Δ_3,2 = c_3,2 – u₃ – v₂ = 6 – 2 – 4 = 0;
Δ_4,2 = c_4,2 – u₄ – v₂ = 6 – 1 – 4 = 1;
Δ_4,3 = c_4,3 – u₄ – v₃ = 5 – 1 – 0 = 4;
Δ_4,4 = c_4,4 – u₄ – v₄ = 6 – 1 – 3 = 2;
Δ_4,5 = c_4,5 – u₄ – v₅ = 0 – 1 – (-2) = 1;
Δ_5,1 = c_5,1 – u₅ – v₁ = 3 – 2 – 2 = -1;
Δ_5,3 = c_5,3 – u₅ – v₃ = 5 – 2 – 0 = 3;
Δ_5,4 = c_5,4 – u₅ – v₄ = 7 – 2 – 3 = 2.
Поскольку есть отрицательные оценки, то план не оптимален.

Наименьшие оценки Δ_3,1 = Δ_5,1 = -1 в клетках (3,1), (5,1). Мы можем ввести в базис любую из них. Вводим в базис клетку (3,1). Строим цикл для этой клетки. Изображаем его в таблице 5.3. Расставляем знаки ′+′ и ′–′ в вершинах цикла, чередуя их, начиная со знака ′+′ в клетке (3,1).

Таблица 5.3

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	– 2 13	6	5	+ 3 2	0
A₂9	3	2 9	1	4	0
A₃13	+ 3	6	2 7	– 5 4	0 2
A₄8	3 8	6	5	6	0
A₅9	3	6 6	5	7	0 3

Переходим к следующему опорному плану. Для этого определяем наименьшее значение поставок в вершинах цикла со знаком ′–′. Оно равно 4 в клетке (3,4). Выполняем сдвиг по циклу на величину 4: в клетках, помеченных знаком ′+′, прибавляем 4; в клетках, помеченных знаком ′–′, вычитаем 4. В результате клетка (3,1) входит в базис со значением 4, а клетка (3,4) выходит из базиса.
Получаем таблицу 6.1.

Таблица 6.1

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 9	6	5	3 6	0
A₂9	3	2 9	1	4	0
A₃13	3 4	6	2 7	5	0 2
A₄8	3 8	6	5	6	0
A₅9	3	6 6	5	7	0 3

Целевая функция:
F₆ = 2·9 + 3·6 + 2·9 + 3·4 + 2·7 + 0·2 + 3·8 + 6·6 + 0·3 = 140

3.6. Шаг 6

Находим потенциалы u_i, v_j:
u₁ = 0;
u_i + v_j = c_ij.
Полагаем u₁ = 0.
Для клетки (1, 1): v₁ = c_1,1 – u₁ = 2 – 0 = 2;
Для клетки (1, 4): v₄ = c_1,4 – u₁ = 3 – 0 = 3;
Для клетки (3, 1): u₃ = c_3,1 – v₁ = 3 – 2 = 1;
Для клетки (3, 3): v₃ = c_3,3 – u₃ = 2 – 1 = 1;
Для клетки (3, 5): v₅ = c_3,5 – u₃ = 0 – 1 = -1;
Для клетки (4, 1): u₄ = c_4,1 – v₁ = 3 – 2 = 1;
Для клетки (5, 5): u₅ = c_5,5 – v₅ = 0 – (-1) = 1;
Для клетки (5, 2): v₂ = c_5,2 – u₅ = 6 – 1 = 5;
Для клетки (2, 2): u₂ = c_2,2 – v₂ = 2 – 5 = -3.
Заносим потенциалы в таблицу 6.2.

Таблица 6.2

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5	u
A₁15	2 9	6	5	3 6	0	0
A₂9	3	2 9	1	4	0	-3
A₃13	3 4	6	2 7	5	0 2	1
A₄8	3 8	6	5	6	0	1
A₅9	3	6 6	5	7	0 3	1
v	2	5	1	3	-1

Находим оценки свободных клеток:
Δ_ij = c_ij – u_i – v_j.
Δ_1,2 = c_1,2 – u₁ – v₂ = 6 – 0 – 5 = 1;
Δ_1,3 = c_1,3 – u₁ – v₃ = 5 – 0 – 1 = 4;
Δ_1,5 = c_1,5 – u₁ – v₅ = 0 – 0 – (-1) = 1;
Δ_2,1 = c_2,1 – u₂ – v₁ = 3 – (-3) – 2 = 4;
Δ_2,3 = c_2,3 – u₂ – v₃ = 1 – (-3) – 1 = 3;
Δ_2,4 = c_2,4 – u₂ – v₄ = 4 – (-3) – 3 = 4;
Δ_2,5 = c_2,5 – u₂ – v₅ = 0 – (-3) – (-1) = 4;
Δ_3,2 = c_3,2 – u₃ – v₂ = 6 – 1 – 5 = 0;
Δ_3,4 = c_3,4 – u₃ – v₄ = 5 – 1 – 3 = 1;
Δ_4,2 = c_4,2 – u₄ – v₂ = 6 – 1 – 5 = 0;
Δ_4,3 = c_4,3 – u₄ – v₃ = 5 – 1 – 1 = 3;
Δ_4,4 = c_4,4 – u₄ – v₄ = 6 – 1 – 3 = 2;
Δ_4,5 = c_4,5 – u₄ – v₅ = 0 – 1 – (-1) = 0;
Δ_5,1 = c_5,1 – u₅ – v₁ = 3 – 1 – 2 = 0;
Δ_5,3 = c_5,3 – u₅ – v₃ = 5 – 1 – 1 = 3;
Δ_5,4 = c_5,4 – u₅ – v₄ = 7 – 1 – 3 = 3;
Поскольку отрицательных оценок нет, то план оптимален. Поскольку есть оценки, равные нулю, то решение не единственное.

Ответ

Наименьшее значение целевой функции:
F_min = 140.
Оптимальный опорный план указан в следующей таблице.

Оптимальный опорный план 1

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 9	6	5	3 6	0
A₂9	3	2 9	1	4	0
A₃13	3 4	6	2 7	5	0 2
A₄8	3 8	6	5	6	0
A₅9	3	6 6	5	7	0 3

Поскольку последний потребитель фиктивный, и имеет отличные от нуля поставки в клетках (3, 5) и (5, 5), то это означает, что третий и пятый поставщики реализуют запасы груза в неполном объеме. Третий поставщик отправит только 11 единиц груза из имеющихся 13-ти. Две единицы останутся на складе. Пятый поставщик отправит 6 единиц из 9-ти. Три единицы останутся не реализованными.

Альтернативные оптимальные опорные планы

Так как есть оценки равные нулю, то оптимальный план не единственный. Существуют другие, альтернативные опорные планы с тем же самым значением целевой функции. То есть решение задачи не единственное. Число альтернативных опорных планов равно числу опорных планов, которые можно составить из клеток с нулевыми оценками. Это заполненные клетки приведенной выше таблицы и пустые клетки (4, 5), (5, 1), (3, 2), (4, 2) с нулевыми оценками. Число альтернативных опорных планов может быть велико. Поэтому мы найдем только некоторые из них, используя за отравную точку, оптимальный опорный план 1.

Нулевые оценки имеют следующие клетки: (4, 5), (5, 1), (3, 2), (4, 2). Строим опорные планы, в которых эти клетки входят в базис.

Цикл для клетки (4, 5)

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 9	6	5	3 6	0
A₂9	3	2 9	1	4	0
A₃13	+ 3 4	6	2 7	5	– 0 2
A₄8	– 3 8	6	5	6	+ 0
A₅9	3	6 6	5	7	0 3

Оптимальный опорный план 2

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 9	6	5	3 6	0
A₂9	3	2 9	1	4	0
A₃13	3 6	6	2 7	5	0
A₄8	3 6	6	5	6	0 2
A₅9	3	6 6	5	7	0 3

Цикл для клетки (5, 1)

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 9	6	5	3 6	0
A₂9	3	2 9	1	4	0
A₃13	3 6	6	2 7	5	0
A₄8	– 3 6	6	5	6	+ 0 2
A₅9	+ 3	6 6	5	7	– 0 3

Оптимальный опорный план 3

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 9	6	5	3 6	0
A₂9	3	2 9	1	4	0
A₃13	3 6	6	2 7	5	0
A₄8	3 3	6	5	6	0 5
A₅9	3 3	6 6	5	7	0

Цикл для клетки (3, 2)

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 9	6	5	3 6	0
A₂9	3	2 9	1	4	0
A₃13	– 3 6	+ 6	2 7	5	0
A₄8	3 3	6	5	6	0 5
A₅9	+ 3 3	– 6 6	5	7	0

Оптимальный опорный план 4

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 9	6	5	3 6	0
A₂9	3	2 9	1	4	0
A₃13	3 0	6 6	2 7	5	0
A₄8	3 3	6	5	6	0 5
A₅9	3 9	6	5	7	0

Цикл для клетки (4, 2)

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 9	6	5	3 6	0
A₂9	3	2 9	1	4	0
A₃13	+ 3 0	– 6 6	2 7	5	0
A₄8	– 3 3	+ 6	5	6	0 5
A₅9	3 9	6	5	7	0

Оптимальный опорный план 5

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 9	6	5	3 6	0
A₂9	3	2 9	1	4	0
A₃13	3 3	6 3	2 7	5	0
A₄8	3	6 3	5	6	0 5
A₅9	3 9	6	5	7	0

Альтернативные оптимальные не опорные планы

Если существует хотя бы два различных оптимальных опорных плана, то задача имеет бесконечно много решений. В пространстве размерности , оптимальные опорные планы являются вершинами выпуклого многогранника, все точки которого являются решением задачи. Здесь μ – номер плана. То есть решением задачи также является план
,
где – произвольные числа, удовлетворяющие условию:
.

В качестве примера, найдем не опорный план, используя только полученные нами первый ⇑ и второй ⇑ планы. Положим . Тем самым мы найдем середину отрезка между точками и в -мерном пространстве.

Компоненты, имеющие равные значения в обоих опорных планах не изменятся. Например, для клеток (1, 1) и (1, 2) имеем:
;
.

Найдем компоненты для клеток с различающимися значениями.
;
;
;
.
В результате получаем следующий не опорный план, который также является решением задачи.

Оптимальный не опорный план

	B₁ 21	B₂ 15	B₃ 7	B₄ 6	Φ 5
A₁15	2 9	6	5	3 6	0
A₂9	3	2 9	1	4	0
A₃13	3 5	6	2 7	5	0 1
A₄8	3 7	6	5	6	0 1
A₅9	3	6 6	5	7	0 3

Использованная литература:
1. Общий курс высшей математики для экономистов. Под общей редакцией В. И. Ермакова. Москва, «ИНФРА-М», 2007.
2. К. Н. Лунгу. Линейное программирование. Руководство к решению задач. Москва, «ФИЗМАТЛИТ», 2005.
3. Д. Б. Юдин, Е. Г. Гольштейн. Задачи и методы линейного программирования. Москва, «Советское радио», 1961.

Автор: Олег Одинцов. Опубликовано: 29-10-2021

См. также: