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

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

Пункт отправления	Пункт назначения	B₁	B₂	B₃	B₄	запасы
A₁	⁵ ₄₀	² ₂₀	⁵	⁶
A₂	³	¹ ₆₀	³ ₂₀	⁷
A₃	⁴	⁵	⁴ ₃₀	⁶ ₄₀
потребности

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

Таблица8

Пункт отправления	Пункт назначения	B₁	B₂	B₃	B₄	запасы
A₁	⁵	² ₆₀	⁵	⁶
A₂	³ ₄₀	¹ ₂₀	³ ₂₀	⁷
A₃	⁴	⁵	⁴ ₃₀	⁶ ₄₀
потребности

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

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

Ответ:

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

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

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

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

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

<4 5 6 7 8910 >

Дата добавления: 2020-02-05; просмотров: 565;