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

Каждому поставщику поставим в соответствие некоторый потенциал α_i, а каждому потребителю – потенциал β_j (таблица 3.2.5.).

Таблица 3.2.5 – Оптимизация плана перевозок методом потенциалов

Присвоим любому потенциалу произвольное значение, например α₃ = 0. Остальные потенциалы легко определяются из условия, что для любой занятой клетки α_i + β_j = Z_ij.

Для каждой свободной клетки вычислим псевдостоимость P_ij = α_i + β_j и разность между стоимостью и псевдостоимостью Δ_ij = Z_ij – P_ij.

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

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

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

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

Процедура повторяется до тех пор, пока есть отрицательные циклы.

3.2.4 Транспортные задачи с дополнительными ограничениями

3.2.4.1 Задачи с обязательными поставками

В качестве примера решения такой задачи рассмотрим исходные данные, приведенные в таблице 3.2.6.

Таблица 3.2.6 – Исходная транспортная таблица задачи с обязательными поставками

Запасы  поставщиков	Потребности потребителей
	B1 = 100	B2 = 200	B3 = 50	B4 = 250	B5 = 150
	Распределение перевозок
A1 = 200	40	15	22	66	20
A2 = 150	7	25	52	25	40
A3 = 225	55	40	40	52	52
A4 = 175	55	25	52	14	33

Пусть в силу определенных обстоятельств (например, госзаказ) поставщик А₃, несмотря на фактические затраты, обязан поставить потребителю В₄ не менее 100 единиц продукции. Исключим эту обязательную поставку из транспортной задачи (таблица 3.2.7).

Таблица 3.2.7 – Транспортная таблица с исключенными обязательными поставками

Запасы  поставщиков	Потребности потребителей
	B1 = 100	B2 = 200	B3 = 50	B4 = 150	B5 = 150
	Распределение перевозок
A1 = 200	40	15	22	66	20
A2 = 150	7	25	52	25	40
A3 = 125	55	40	40	52	52
A4 = 175	55	25	52	14	33

Затем решается обычная транспортная задача, но при определении суммарных затрат на перевозки необходимо учесть и затраты на обязательные поставки: 100 × 52 = 5200.