Решить транспортные задачи методом потенциалов
Задача 1.
| Поставщики | Потребители | Запасы | ||||
| В1 | В2 | В3 | В4 | |||
| А1 | 7 | 3 | 5 | 2 | 80 | |
| А2 | 3 | 4 | 2 | 3 | 40 | |
| А3 | 1 | 5 | 8 | 4 | 40 | |
| Потребности | 30 | 50 | 30 | 50 | | |
Проверим выполнение условия:
ТЗ закрыта.С помощью метода наименьшей стоимости, построим первый опорный план транспортной задачи.
Составляем первый опорный план методом наименьшей стоимости. Наименьшая стоимость 1 в клетке (3, 1). Даем в нее наибольшую поставку 30. Потребитель B1 получил требуемое количество груза: b1 = 30. Вычеркиваем столбец B1.
| | B1 30 | B2 50 | B3 30 | B4 50 |
| A1 80 | 7 | 3 | 5 | 2 |
| A2 40 | 3 | 4 | 2 | 3 |
| A3 40 | 1 30 | 5 | 8 | 4 |
Среди не зачеркнутых клеток, наименьшая стоимость 2 в клетке (1, 4). Даем в нее наибольшую поставку 50. Потребитель B4 получил требуемое количество груза: b4 = 50. Вычеркиваем столбец B4.
| | B1 30 | B2 50 | B3 30 | B4 50 |
| A1 80 | 7 | 3 | 5 | 2 50 |
| A2 40 | 3 | 4 | 2 | 3 |
| A3 40 | 1 30 | 5 | 8 | 4 |
Среди не зачеркнутых клеток, наименьшая стоимость 2 в клетке (2, 3). Даем в нее наибольшую поставку 30. Потребитель B3 получил требуемое количество груза: b3 = 30. Вычеркиваем столбец B3.
| | B1 30 | B2 50 | B3 30 | B4 50 |
| A1 80 | 7 | 3 | 5 | 2 50 |
| A2 40 | 3 | 4 | 2 30 | 3 |
| A3 40 | 1 30 | 5 | 8 | 4 |
Среди не зачеркнутых клеток, наименьшая стоимость 3 в клетке (1, 2). Даем в нее наибольшую поставку 30. Поставщик A1 реализовал весь имеющийся у него груз: a1 = 30 + 50 = 80. Вычеркиваем строку A1.
| | B1 30 | B2 50 | B3 30 | B4 50 |
| A1 80 | 7 | 3 30 | 5 | 2 50 |
| A2 40 | 3 | 4 | 2 30 | 3 |
| A3 40 | 1 30 | 5 | 8 | 4 |
Среди не зачеркнутых клеток, наименьшая стоимость 4 в клетке (2, 2). Даем в нее наибольшую поставку 10. Поставщик A2 реализовал весь имеющийся у него груз: a2 = 10 + 30 = 40. Вычеркиваем строку A2.
| | B1 30 | B2 50 | B3 30 | B4 50 |
| A1 80 | 7 | 3 30 | 5 | 2 50 |
| A2 40 | 3 | 4 10 | 2 30 | 3 |
| A3 40 | 1 30 | 5 | 8 | 4 |
Даем наибольшую поставку 10 в оставшуюся не зачеркнутую клетку (3, 2). Получаем первый опорный план.
| | B1 30 | B2 50 | B3 30 | B4 50 |
| A1 80 | 7 | 3 30 | 5 | 2 50 |
| A2 40 | 3 | 4 10 | 2 30 | 3 |
| A3 40 | 1 30 | 5 10 | 8 | 4 |
Стоимость перевозок по первоначальному плану:
Проверим оптимальность опорного плана.
Находим потенциалы ui, vj. Для этого нам нужно решить приведенную ниже систему уравнений, используя только заполненные клетки:
u1 = 0;
ui + vj = cij.
Полагаем u1 = 0.
Для клетки (1, 2): v2 = c1,2 – u1 = 3 – 0 = 3;
Для клетки (1, 4): v4 = c1,4 – u1 = 2 – 0 = 2;
Для клетки (2, 2): u2 = c2,2 – v2 = 4 – 3 = 1;
Для клетки (2, 3): v3 = c2,3 – u2 = 2 – 1 = 1;
Для клетки (3, 2): u3 = c3,2 – v2 = 5 – 3 = 2;
Для клетки (3, 1): v1 = c3,1 – u3 = 1 – 2 = -1.
Заносим потенциалы в таблицу:
| | B1 30 | B2 50 | B3 30 | B4 50 | u |
| A1 80 | 7 | 3 30 | 5 | 2 50 | 0 |
| A2 40 | 3 | 4 10 | 2 30 | 3 | 1 |
| A3 40 | 1 30 | 5 10 | 8 | 4 | 2 |
| v | -1 | 3 | 1 | 2 | |
Находим оценки свободных клеток по формуле:
Δij = cij – ui – vj.
Δ1,1 = c1,1 – u1 – v1 = 7 – 0 – (-1) = 8; Δ1,3 = c1,3 – u1 – v3 = 5 – 0 – 1 = 4;
Δ2,1 = c2,1 – u2 – v1 = 3 – 1 – (-1) = 3; Δ2,4 = c2,4 – u2 – v4 = 3 – 1 – 2 = 0;
Δ3,3 = c3,3 – u3 – v3 = 8 – 2 – 1 = 5; Δ3,4 = c3,4 – u3 – v4 = 4 – 2 – 2 = 0.
Поскольку отрицательных оценок нет, то план оптимален. Поскольку есть оценки, равные нулю, то решение не единственное.
Оптимальный опорный план 1
| | B1 30 | B2 50 | B3 30 | B4 50 |
| A1 80 | 7 | 3 30 | 5 | 2 50 |
| A2 40 | 3 | 4 10 | 2 30 | 3 |
| A3 40 | 1 30 | 5 10 | 8 | 4 |
Поскольку есть оценки, равные нулю, то оптимальный план не единственный. Нулевые оценки имеют следующие клетки: (2, 4), (3, 4). Число альтернативных оптимальных опорных планов может быть велико. Мы построим только некоторые из них, в которых клетки с нулевыми оценками входят в базис.
Цикл для клетки (2, 4)
| | B1 30 | B2 50 | B3 30 | B4 50 |
| A1 80 | 7 | + 3 30 | 5 | – 2 50 |
| A2 40 | 3 | – 4 10 | 2 30 | + 3 |
| A3 40 | 1 30 | 5 10 | 8 | 4 |
Оптимальный опорный план 2
| | B1 30 | B2 50 | B3 30 | B4 50 |
| A1 80 | 7 | 3 40 | 5 | 2 40 |
| A2 40 | 3 | 4 | 2 30 | 3 10 |
| A3 40 | 1 30 | 5 10 | 8 | 4 |
Цикл для клетки (3, 4)
| | B1 30 | B2 50 | B3 30 | B4 50 |
| A1 80 | 7 | + 3 40 | 5 | – 2 40 |
| A2 40 | 3 | 4 | 2 30 | 3 10 |
| A3 40 | 1 30 | – 5 10 | 8 | + 4 |
На этом процесс отыскания альтернативных оптимальных опорных планов завершаем, поскольку их число может быть велико.
Задача 2.
| Поставщики | Потребители | Запасы | ||
| В1 | В2 | В3 | ||
| А1 | 3 | 1 | 4 | 40 |
| А2 | 5 | 6 | 8 | 80 |
| А3 | 3 | 4 | 2 | 120 |
| Потребности | 70 | 90 | 100 | |
Сумма мощностей поставщиков: 40 + 80 + 120 = 240 меньше суммы мощностей потребителей: 70 + 90 + 100 = 260. Модель задачи открытая. Чтобы привести ее к закрытому типу, вводим фиктивного поставщика Φ с мощностью 260 – 240 = 20. В результате модель задачи становится закрытой. Решаем ее методом потенциалов.4
Составляем первый опорный план методом наименьшей стоимости. Фиктивного поставщика Φ заполняем в последнюю очередь. Наименьшая стоимость 1 в клетке (1, 2). Даем в нее наибольшую поставку 40. Поставщик A1 реализовал весь имеющийся у него груз: a1 = 40. Вычеркиваем строку A1.
| | B1 70 | B2 90 | B3 100 |
| A1 40 | 3 | 1 40 | 4 |
| A2 80 | 5 | 6 | 8 |
| A3 120 | 3 | 4 | 2 |
| Φ 20 | 0 | 0 | 0 |
Среди не зачеркнутых клеток, наименьшая стоимость 2 в клетке (3, 3). Даем в нее наибольшую поставку 100. Потребитель B3 получил требуемое количество груза: b3 = 100. Вычеркиваем столбец B3.
| | B1 70 | B2 90 | B3 100 |
| A1 40 | 3 | 1 40 | 4 |
| A2 80 | 5 | 6 | 8 |
| A3 120 | 3 | 4 | 2 100 |
| Φ 20 | 0 | 0 | 0 |
Среди не зачеркнутых клеток, наименьшая стоимость 3 в клетке (3, 1). Даем в нее наибольшую поставку 20. Поставщик A3 реализовал весь имеющийся у него груз: a3 = 20 + 100 = 120. Вычеркиваем строку A3.
| | B1 70 | B2 90 | B3 100 |
| A1 40 | 3 | 1 40 | 4 |
| A2 80 | 5 | 6 | 8 |
| A3 120 | 3 20 | 4 | 2 100 |
| Φ 20 | 0 | 0 | 0 |
Среди не зачеркнутых клеток, наименьшая стоимость 5 в клетке (2, 1). Даем в нее наибольшую поставку 50. Потребитель B1 получил требуемое количество груза: b1 = 50 + 20 = 70. Вычеркиваем столбец B1.
| | B1 70 | B2 90 | B3 100 |
| A1 40 | 3 | 1 40 | 4 |
| A2 80 | 5 50 | 6 | 8 |
| A3 120 | 3 20 | 4 | 2 100 |
| Φ 20 | 0 | 0 | 0 |
Среди не зачеркнутых клеток, наименьшая стоимость 6 в клетке (2, 2). Даем в нее наибольшую поставку 30. Поставщик A2 реализовал весь имеющийся у него груз: a2 = 50 + 30 = 80. Вычеркиваем строку A2.
| | B1 70 | B2 90 | B3 100 |
| A1 40 | 3 | 1 40 | 4 |
| A2 80 | 5 50 | 6 30 | 8 |
| A3 120 | 3 20 | 4 | 2 100 |
| Φ 20 | 0 | 0 | 0 |
Даем наибольшую поставку 20 в оставшуюся не зачеркнутую клетку (4, 2). Получаем первый опорный план.
| | B1 70 | B2 90 | B3 100 |
| A1 40 | 3 | 1 40 | 4 |
| A2 80 | 5 50 | 6 30 | 8 |
| A3 120 | 3 20 | 4 | 2 100 |
| Φ 20 | 0 | 0 20 | 0 |
Целевая функция:
F = 1·40 + 5·50 + 6·30 + 3·20 + 2·100 + 0·20 = 730
Построение оптимального плана
Находим потенциалы ui, vj. Для этого нам нужно решить приведенную ниже систему уравнений, используя только заполненные клетки:
u1 = 0;
ui + vj = cij.
Полагаем u1 = 0.
Для клетки (1, 2): v2 = c1,2 – u1 = 1 – 0 = 1;
Для клетки (2, 2): u2 = c2,2 – v2 = 6 – 1 = 5;
Для клетки (2, 1): v1 = c2,1 – u2 = 5 – 5 = 0;
Для клетки (3, 1): u3 = c3,1 – v1 = 3 – 0 = 3;
Для клетки (3, 3): v3 = c3,3 – u3 = 2 – 3 = -1;
Для клетки (4, 2): u4 = c4,2 – v2 = 0 – 1 = -1.
Заносим потенциалы в таблицу 1.2.
| | B1 70 | B2 90 | B3 100 | u |
| A1 40 | 3 | 1 40 | 4 | 0 |
| A2 80 | 5 50 | 6 30 | 8 | 5 |
| A3 120 | 3 20 | 4 | 2 100 | 3 |
| Φ 20 | 0 | 0 20 | 0 | -1 |
| v | 0 | 1 | -1 | |
Находим оценки свободных клеток по формуле:
Δij = cij – ui – vj.
Δ1,1 = c1,1 – u1 – v1 = 3 – 0 – 0 = 3;
Δ1,3 = c1,3 – u1 – v3 = 4 – 0 – (-1) = 5;
Δ2,3 = c2,3 – u2 – v3 = 8 – 5 – (-1) = 4;
Δ3,2 = c3,2 – u3 – v2 = 4 – 3 – 1 = 0;
Δ4,1 = c4,1 – u4 – v1 = 0 – (-1) – 0 = 1;
Δ4,3 = c4,3 – u4 – v3 = 0 – (-1) – (-1) = 2.
Поскольку отрицательных оценок нет, то план оптимален. Поскольку есть оценка, равная нулю, то решение не единственное.
Наименьшее значение целевой функции:
Fmin = 730.
Оптимальный опорный план указан в следующей таблице.
Оптимальный опорный план 1
| | B1 70 | B2 90 | B3 100 |
| A1 40 | 3 | 1 40 | 4 |
| A2 80 | 5 50 | 6 30 | 8 |
| A3 120 | 3 20 | 4 | 2 100 |
| Φ20 | 0 | 0 20 | 0 |
Поскольку есть оценка, равная нулю, то оптимальный план не единственный. Нулевую оценку имеет клетка (3, 2). Строим альтернативный оптимальный опорный план, в котором эта клетка входит в базис.
Цикл для клетки (3, 2)
| | B1 70 | B2 90 | B3 100 |
| A1 40 | 3 | 1 40 | 4 |
| A2 80 | + 5 50 | – 6 30 | 8 |
| A3 120 | – 3 20 | + 4 | 2 100 |
| Φ 20 | 0 | 0 20 | 0 |
Оптимальный опорный план 2
| | B1 70 | B2 90 | B3 100 |
| A1 40 | 3 | 1 40 | 4 |
| A2 80 | 5 70 | 6 10 | 8 |
| A3 120 | 3 | 4 20 | 2 100 |
| Φ 20 | 0 | 0 20 | 0 |