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

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

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

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

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

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

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

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

 

 

 

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

 

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

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

ΔR= +С11 *1- С14 *1 +С34 *1- С32 *1+ С22 *1- С21 *1=+ 6-10+12-8+7-4=+3

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

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

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

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

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

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

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

 

 

Клетка A1В1 Клетка A1В2

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

 

Клетка A1В3 Клетка A2В3

       
   

 


∑С13 =+7-10+12-5=+4 ∑С23 =+6-5+8-7=+2

 

 

Клетка A2В4 Клетка A3В1

       
   

 


∑С24 =+8-12+8-7=-3 ∑С31 =+9-8+7-4=+4

 

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

 

 

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

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

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

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

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

 

 

Таблица 4.4.