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

Перейдем ко второму этапу решения задачи — проверке полученного решения на оптимальность.

Решение будет оптимальным только тогда, когда целе­вая функция примет минимальное значение, т. е. когда даль­нейшее уменьшение затрат путем перераспределения поста­вок будет невозможным.

Условимся называть клетки, заполненные поставками — базисными, клетки, где нет поставки — свободными.

Чтобы установить, является ли план оптимальным, надо проверить, можно ли уменьшить значение функции цели перераспределив поставки. Для этого в каждую свободную клетку попытаемся включить какую-либо поставку, но с та­ким перераспределением начального решения, чтобы оно было допустимым, т. е. чтобы соблюдался баланс спроса и предложения. Если в результате таких перестановок най­дется хотя бы одно решение, которое приведет к снижению величины функции цели, значит анализируемое решение не оптимальное.

В опорном плане, представленном в табл. 4.3., имеется шесть свободных клеток, значит необходимо проверить воз­можность единичной поставки поочередно в каждую из этих клеток. Для выполнения этого анализа принимаем именно единичную поставку, так как при этом значительно упроща­ются расчеты. В свободную клетку А₁В₁ поставим единичную поставку, т.е. приняв за основу начальное решение, проверим, будет ли уменьшена величина функции цели, если хотя бы 1 м³ (1 тыс. м³) пиловочника будет поставлен с леспромхоза А₁ на предприятие В₁.

Для того, чтобы не нарушался баланс поставщика А₁ не­обходимо уменьшить поставку от этого поставщика потре­бителю В₄ на единицу, но чтобы не нарушилась поставка по­требителю В₄, необходимо увеличить ему поставку от по­ставщика А₃ на единицу. В свою очередь, чтобы не нарушил­ся баланс поставщика А₃ необходимо уменьшить от него по­ставку потребителю В₂, а потребителю В₂ увеличить постав­ку от поставщика А₂. Теперь, чтобы не нарушался баланс поставщика А₂, необходимо уменьшить от него поставку потре­бителю В₁.

Результат этих перестановок можно изобразить схемой, приведенной на рис. 2. В результате выполненных переста­новок мы опять получили допустимое решение. Если выпол­нить эти перестановки в начальном решении, то произойдет изменение стоимости перевозок. Определим, к чему это приведет. Стоимость поставки потребите­лю В₁ от поставщика A₁ т. е. cтоимость поставки A₁В₁ увели­чится на C₁₁ = 6*1 = + 6.

 

 

 

Рис. 4.1. Перераспределение единичных поставок для клетки A₁В₁

 

Стоимость поставки A₁В₄ уменьшится на величину С₁₄ *1= -10*1 = -10.

В целом, изме­нения, которые произойдут при рассмотренной перестановке по­ставок, можно записать следую­щим образом:

ΔR= +С₁₁ *1- С₁₄ *1 +С₃₄ *1- С₃₂ *1+ С₂₂ *1- С₂₁ *1=+ 6-10+12-8+7-4=+3

То есть при попытке дать поставку в клетку A₁В₁ в целом произойдет увеличение стоимости перевозок, увеличение зна­чения функции цели.

Для каждой из свободных клеток необходимо выполнить такие же решения и определить, к какому результату при­ведет соответствующее изменение поставок.

Перераспределяя поставки (рис. 4.1.), мы прошли по неко­торым клеткам. Путь движения образовал так называемую цепь. Цепью в транспортной задаче называется замкнутый многоугольник с четным количеством вершин. Вершинами цепи являются клетки таблицы, при этом одна из вершин на­ходится в свободной клетке, остальные в базисных. Верши­ны цепи обязательно прямоугольные. Цепь может проходить через базисные клетки, не являющиеся вершинами данной цепи. Необходимо отметить, что для любой свободной клетки можно построить одну и только одну единственную цепь.

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

Вершины цепи, в которых поставка при перераспределе­нии уменьшается, отмечаются знаком минус и называются отрицательными вершинами. Вершина в свободной клетке всегда положительная. В цепи одинаковое количество поло­жительных и отрицательных вершин и они всегда череду­ются. Цепь изображается следующим образом. Вершина, на­ходящаяся в свободной клетке, изображается квадратом, остальные — кружком. Внутри квадрата записывается показатель критерия оптимальности или стоимость единичной поставки со знаком. В положительных вершинах +, в отрицательных —. Цепи для остальных свободных клеток рассматриваемого примера приведены на рис. 4.2.

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

Если характеристики цепей всех свободных клеток положительны при решении задачи на минимум, то получено оптимальное решение. Если имеется хотя бы одна отрицательная характеристика цепи — решение не оптимальное и име­ется возможность улучшить решение путем перераспределения поставок. Свободная клетка, имеющая минимальное зна­чение характеристики, называется перспективной. В нашем примере минимальную характеристику цепи — 3 имеет клет­ка A₂ В₄ (рис. 4.2).

 

 

Клетка A₁В₁ Клетка A₁В₂

∑С₁₁ =+6-10+12-8+7-4=+3 ∑С₁₂ =+8-10+12-8=+2

 

Клетка A₁В₃ Клетка A₂В₃

 

∑С₁₃ =+7-10+12-5=+4 ∑С₂₃ =+6-5+8-7=+2

 

 

Клетка A₂В₄ Клетка A₃В₁

 

∑С₂₄ =+8-12+8-7=-3 ∑С₃₁ =+9-8+7-4=+4

 

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

 

 

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.