Распределительный метод решения ТЗ

1. Проверяем, является ли ТЗ задачей с правильным балансом.

2. Находим исходное допустимое базисное решение ТЗ методом СЗУ или МНС.

3. Рассматриваем все свободные клетки таблицы перевозок,составляем для них циклы пересчета и находим оценки свободных клеток . Выбираем ту клетку, которая имеет наибольшую по моду-
лю отрицательную оценку .

4. Производим сдвиг по циклу пересчета этой свободной клетки. Получаем новую таблицу перевозок.

5. Операции 3, 4 повторяем до тех пор, пока для всех свободных клеток не будет выполняться .

Пример. Построить оптимальное решение ТЗ. исходное допустимое решение которой, построенное методом СЗУ, задано в таблице 5.

Решение. Проверяем выполнение критерия оптимальности, начиная с первой строки:

Единственная свободная клетка с номером (2,1) имеет отрицательную оценку. Проводим сдвиг по циклу на число e, где e =min(40,60) = 40. После сдвига по циклу базисная клетка (1, 1) станет свободной (х₁₁ = О), свободная клетка (2,1) станет базисной со значением х₂₁ = 40. В соответствии с определением операции сдвига по циклу на число e = 40: х₁₂ = 60. х₂₂ = 20 (табл. 7).

Таблица 7

В результате получаем новую таблицу перевозок (табл. 8)

Таблица8

Проверяем справедливость критерия оптимальности для данного распределения поставок:

Итак, для всех свободных клеток имеем. Следовательно, распределение поставок оптимально.

Ответ:

.

f_min=2*60 + 3*40 + 1*20 + 3*20 + 4*30 + 6*40 = 680.

Замечания о выборе числа e, на которое производится
сдвиг по циклу пересчета свободной клетки

1. По определению e= min(из значений х_ij в отрицательных вершинах цикла пересчета данной свободной клетки).

2. Может оказаться, что e = О. В этом случае значения поставок в вершинах цикла не изменяются, значение целевой Функции при переходе к новому решению не изменяется, но бывшая свободная
клетка станет базисной с нулевой поставкой.

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