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

k = ai bj . Рассчитаем k.

Тогда получим транспортную задачу с правильным балансом.

Найдем опорное решение с помощью метода северо-западного угла.

r = 3+5-1 =7

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

Проверка по столбцам:

Проверка по строкам:

Количество заполненных клеток равно r =7. Найденный план является опорным.

Постараемся улучшить план перевозок

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

Цикл1

(1;1)-(1;2)-(2;2)-(2;1)

, где цена цикла

Цикл2

(2;3)-(2;4)-(3;4)-(3;3)

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

После всех рассуждений получим следующее:

Итак, улучшаем план перевозок с помощью Цикла1. Для этого перенесем по циклу мнимальное количество груза, стоящее в отрицательной вершине.

Подсчитаем L для таблицы с изменениями.

L =

Допустим, что найдено оптимальное решение. Проверим его с помощью метода потенциалов.

Примем a1 = 0, тогда bj = cij - ai (для заполненных клеток). Если найденное решение справедливо, то во всех пустых клетках таблицы Дij = cij - (ai + bj )?0. Ясно, что Дij = 0 для заполненных клеток. Получим следующее.

Из таблицы видно, что найденное оптимальное решение верно, так как Дij ?0.