Здравствуйте, Aleksandrkib!

Так как 100 + 140 + 60 = 80 + 80 + 60 + 80 = 300, то запасы равны потребностям и условие баланса соблюдается. Построим первый опорный план, используя метод наименьшей стоимости:



Всего должно быть занято 3+4-1=6 клеток таблицы, в первом опорном плане занято 6 клеток, следовательно, опорный план является невырожденным. Проверим его оптимальность. Для этого найдем потенциалы u[sub]i[/sub], v[sub]j[/sub], исходя из того, что для занятых клеток таблицы u[sub]i[/sub] + v[sub]j[/sub] = c[sub]ij[/sub] и полагая u[sub]1[/sub] = 0:



Опорный план оптимален, если для всех свободных клеток u[sub]i[/sub] + v[sub]j[/sub] <= c[sub]ij[/sub]. В данном случае это условие не выполняется для клетки (3;4). Выберем максимальную оценку этой клетки. Для этого помечаем клетки - вершины многоугольника (3;4) (2;4) (2;1) (3;1) чередующимися знаками + и -, начиная со знака + для выбранной клетки (3;4):



Теперь изменяем объемы грузов в помеченных клетках с учетом расставленных знаков на максимально возможную величину (то есть прибавлем к плюсовым клеткам и отнимаем от минусовых). Очевидно, она равна 40 = min(40,60) (так как значения не могут быть отрицательными). Получаем новый опорный план:



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



Условие u[sub]i[/sub] + v[sub]j[/sub] <= c[sub]ij[/sub] выполняется для всех свободных клеток, поэтому новый опорный план оптимален.

Итак, решением явлется следующая схема:

A[sub]1[/sub] → B[sub]3[/sub]: 60; A[sub]1[/sub] → B[sub]4[/sub]: 40;
A[sub]2[/sub] → B[sub]1[/sub]: 60; A[sub]2[/sub] → B[sub]2[/sub]: 80;
A[sub]3[/sub] → B[sub]1[/sub]: 20; A[sub]3[/sub] → B[sub]4[/sub]: 40.

Минимальные затраты составят F(x) = 3*60 + 4*40 + 3*60 + 2*80 + 1*20 + 2*40 = 780.