Алгоритм решения ТЗ,

1) находим начальное базисное допустимое (опорное) решение, состоящее из (n+m+1) заполненных клеток таблицы поставок методом северо-западного угла или методом минимальной стоимости. Убеждаемся в его «опорности» методом вычёркивания рядов с одной заполненной клеткой из матрицы поставок.

2) проверяем оптимальность найденного решения (используя различные критерии оптимальности)

3) если найденное решение не оптимально, изменяемего, используя «сдвиг по циклу»: увеличиваем объём перевозок во всех нечётных клетках цикла и уменьшаем во всех чётных на величину ( равен наименьшему из объёмов перевозок в чётных клетках цикла). Переходим к пункту 2).

Построение начального решения:

В клетку (i,j) таблицы поставок вносим максимально возможный объём перевозки, равный оставшимся запасам i-го поставщика или неудовлетворённым потребностям j-го потребителя. Затем вычёркиваем из таблицы поставщика или потребителя, потребности которого полностью удовлетворены. (одна заполненная клетка таблицы – один вычеркнутый ряд матрицы).

Метод северо-западного угла: последовательнозаполняем правую верхнюю клетку таблицы поставок.

Метод минимальной стоимости – в первую очередь заполняем клетки с наименьшей стоимостью первозки.

Критерий оптимальности найденного решения распределительного метода.

Вычисляем оценку цикла для каждой свободной клетки таблицы поставок (складываем стоимости перевозок в нечётных клетках цикла и вычитаем стоимости в чётных клетках).

Если оценки циклов всех свободных клеток неотрицательны, найденное решение оптимально.