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

Распределительным методом

При решении задачи «распределительным методом» используется следующая последовательность процедур.

1. Согласно данным на задание строится исходная распределительная таблица, в которую заносятся значения ресурсов и потребностей (табл. 10.2. 1).

Исходные данные Таблица 10.2.1

2. Рассчитываем опорное решение «методом северо-западногоугла» (табл. 0.2.2).

Опорное решение №1 Таблица 10.2.2

Z₀ = 1130

3. Строится схема «цикла однократного замещения» с одной изсвободных, то есть «пустых», клеток опорного решения.

Вариант построения цикла Таблица 10.2.3.

4. Вычисляется оценка свободной (пустой) клетки, выбранной для преобразования однократного замещения, ведущего к новому опорному решению, с уменьшенным значением целевой функции (табл.10.2.4).

5. В случае если оценка клетки в начальном, или в очередном шаге, является положительной, то есть со знаком «+», то такой вариант отбрасывается. Это происходит до тех пор, пока не будет найдена клетка с отрицательной оценкой. Если же все свободные клетки будут иметь положительные оценки, то это будет означать, что достигнуто оптимальное решение – то есть решение с наименьшим значением целевой функции.

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

Таблица №10.2.4

Итерация №1 Z₀= 1130; λ₁=20; О₁= -6; λ₁ · О₁= -120

Таблица №10.2.5.

Итерация №2 Z₁= 1010; λ₂=10; О₂= -3; λ₂ · О₂= -30

......................................................................

Таблица №..10. N

Итерация №... Z_мин = 860; Оптимальное решение

Контролем правильности решения по обоим вариантам расчёта служит равенство значений целевых функций в обоих решениях

Дата добавления: 2014-01-05