Формирование схемы движения
Условие оптимальности не выполняется, поэтому производим перераспределение объема перевозок.
Перераспределение ресурсов
а) Строим в исходной матрице контур перераспределения ресурсов. Начало контура - клетка с максимальным нарушением условия оптимальности (клетка Х15). В новом плане эта клетка из незаполненной становится заполненной. Далее строим замкнутый многоугольник с вершинами в загруженных клетках, за исключением начала контура. Число вершин контура должно быть четным. Половина из них загружается и помечается знаком «+», другая половина- разгружается и помечается знаком « -.». в каждой строке и в каждом столбце имеется две вершины.
В контуре допускаются только вертикальные и горизонтальные линии.
В процессе перераспределения ресурсов по контуру в соответствии с условием неотрицательности переменных Хij ни одно из этих значений не должно превращаться в отрицательное число. Поэтому, с точки зрения переноса ресурсов по контуру анализируются только клетки, помеченные знаком « -.», из них выбирается клетка с минимальным объемом перевозок, и этот объем переносится по контуру.
Таблица5
П. наз П. отпр |
В1 |
В2 |
В3 |
В4 |
В5 |
Gi |
ai |
А1 |
270 150 |
190 80 |
290 20 - |
190 |
180 + |
250 |
0 |
А2 |
175 |
350 |
200 240 + |
185 120 |
200 90 - |
450 |
-90 |
А3 |
230 |
310 |
295 |
200 |
325 100 |
100 |
35 |
Vj |
150 |
80 |
260 |
120 |
190 | ||
bj |
270 |
190 |
290 |
275 |
290 |
Таблица6
П. наз П. отпр |
В1 |
В2 |
В3 |
В4 |
В5 |
Gi |
ai |
А1 |
270 150 |
190 80 |
290 |
190 |
180 20 |
250 |
0 |
А2 |
175 |
350 |
200 260 |
185 120 |
200 70 |
450 |
20 |
А3 |
230 |
310 |
295 |
200 |
325 100 |
100 |
145 |
Vj |
150 |
80 |
260 |
120 |
190 | ||
bj |
270 |
190 |
180 |
165 |
180 |