Переход к новому опорному решению ТЗ

В ТЗ переход от одного опорного решения к другому осуществляется с помощью цикла. Для некоторой свободной клетки таблицы строится цикл, содержащий часть клеток, занятых опорным решением. По этому циклу перераспределяются объемы перевозок. Для определения количества единиц груза, подлежащих распределению, отмечаем знаком + клетку, которую надо загрузить. Это означает, что клетка присоединяется к занятым клеткам. В таблице занятых клеток стало p+q, поэтому появляется цикл, все вершины которого, за исключением клетки, отмеченной знаком +, находятся в занятых клетках, причем этот цикл единственный. Отыскиваем цикл и, начиная движения от клетки, отмеченной знаком +, поочередно проставляем знаки + и -. Затем находим ג=minxij, где xij – перевозки, стоящие в вершинах цикла, отмеченных знаком -. Величина ג определяет, сколько единиц груза можно перераспределить по найденному циклу. Значение ג записываем в незанятую клетку, отмеченную знаком +, двигаясь по циклу, вычитаем ג из объемов перевозок, находящихся в клетках, отмеченных знаком +. Если ג соответствуют несколько минимальных перевозок, то при вычитании оставляем в соответствующих клетках нулевые перевозки в таком количестве, чтобы во вновь полученном опорном плане занятых клеток было p+q-1.

Проверяем полученный план на оптимальность. Ищем потенциалы последней матрицы. Так как отрицательных оценок нет, построенный план является оптимальным. Если полученный план окажется неоптимальным, то следует выполнить перечисленные вычисления еще раз. Процесс выполняют до тех пор, пока все незанятые клетки не будут удовлетворять условию оптимальности.

Циклы

Циклом называется набор клеток, вида: (L1;K1);(L1;K2);(L2;K2)…(Ls;K1) или (L1;K1);(L2;K1);(L2;K2)…(L1;Kl), в которых две и только две соседние клетки расположены в распределительной таблице, причем последняя клетка находится в том же столбце или той же строке, что и первая. Графически циклу соответствует замкнутая ломанная линия с прямыми углами. Допустимые решения ТЗ являются опорными, лишь в том случае, если из занятых этим решением клеток нельзя образовать ни одного цикла. Если в распределительной таблице содержится опорное решение, то для каждой свободной клетки можно образовать один цикл, содержащий данную свободную и некоторую часть занятых клеток.

Все вершины цикла кроме одной находятся в занятых клетках; углы прямые, число вершин четное. никакие 3 соседние клетки не могут быть в одной строке или в одном столбце. Около свободной клетки цикла ставится знак (+), затем поочередно проставляются знаки(-)и (+). У вершин со знаком (-) выбирают минимальный груз, его прибавляют к грузам, стоящих у вершин со знаком (+), и отнимают от грузов у вершин со знаком (-).В результате перераспределения груза получается новое опорное решение

Поиск по сайту: