4.6. Переход от неоптимального решения к лучшему.

Для перехода к лучшему решению в перспективную клет­ку, т. е. клетку, имеющую минимальную характеристику цепи, необходимо занести возможно большую поставку. Для этого в цепи перспективной клетки определяются вершины с отрицательными знаками. Среди этих вершин находят такую, которая имеет наименьшую по величине, поставку. Эту поставку прибавляют к поставкам положительных вершин и вычитают из поставок отрицательных вершин, получая таким образом новое распределение поставок или новое ре­шение. Поскольку в нашем примере перспективной явля­ется клетка А₂В₄, находим среди отрицательных вершин этой цепи наименьшую по величине поставку - 50. Вычитаем эту поставку из отрицательных вершин, прибавляем к положительным и переписываем поставки остальных клеток без изменений. В результате получим новое решение, представ­ленное в табл. 4.4.

Величина функции цели равна:

R = 10*300 + 4*450 +7*100 +8*50 + 8*300 +5*200 = 9300 тыс. руб.

Это решение лучше начального на 150 тыс. руб. Это мож­но было установить, умножив характеристику цепи на по­ставку, внесенную в перспективную клетку -3*50 = -150 тыс. руб.

Таблица 4.4.

Результат решения после первой итерации.

Поставщики и их мощности, тыс.куб. м.		Потребители и их спрос, тыс.куб.м.
		В1	В2	В3	В4
		450	400	200	350
А1	300	6	8	7	10 300
А2	600	4 450	7 100	6	8 50
А3	500	9	8 300	5 200	12

Хотя полученное решение лучше начального, это не зна­чит, что оно оптимальное. Для решения задачи необходимо вернуться к предыдущему этапу — проверить является ли план распределения поставок оптимальным.

А₁В₁ А₁В₂ А₁В₂

∑С₁₁ =0 ∑С₁₂ =-1

∑С₁₃ =+1

А₂В₃ А₃В₁ А₃В₄

∑С₂₃ =+2 ∑С₃₁ =+4 ∑С₃₄ =+3

Рис. 4.3.Цепи свободных клеток и их характеристики на второй итерации.

Не повторяя полностью приведенные выше рассуждения, приведем цепи и характеристики цепей свободных клеток на рис. 4.3. Перспективной на втором этапе решения задачи ока­залась клетка А₁В₂ с характеристикой - 1. Выполнив перераспределение поставок по методу, описанному выше, полу­чим новое решение, приведенное в табл. 4.5. Величина функ­ции цели при этом распределении поставок равна 9200 тыс. руб.

∑С₁₁ =0 ∑С₁₃ =+2 ∑С₂₂ =+1

∑С₂₃ =+3 ∑С₃₁ =+3 ∑С₃₃ =+2

Рис. 4.4.Цепи свободных клеток и их характеристики на третьей

итерации

Для того, чтобы определить является ли полученное ре­шение оптимальным, строим цепи для свободных клеток (рис. 4.4.) полученного решения и вычисляем их характеристи­ки. Как видно из рис. 4.4. все характеристики цепей положи­тельны, т. е. решение является оптимальным.

Таблица 4.5.