ожна поліпшити, ввівши в план перевезення. З цією метою складемо цикл, що має початок у вільній клітці (4, 1), а інші вершини - у зайнятих клітинах, послідовно збільшуючи і зменшуючи перевезення, що потрапили в цикл, на величину. Цикл і послідовність збільшення та зменшення перевезень зображено на рисунку 5. p> Важливо відзначити, що при складанні циклу слід рухатися тільки по горизонталі або вертикалі, так що б у кожен рядок і кожен стовпець плану перевезень, охоплених циклом, потрапили тільки дві перевезення.
Вибираємо, тобто в якості вибирається найменша з перевезень, з яких віднімається. При включенні в план перевезення = 12 сумарна вартість перевезень зміниться на, тобто зменшиться на 48 од. і для нового плану складе:
В
В
Малюнок 6 - План Х2 (План)
За умовою для зайнятих клітин:
В В
За умовою для вільних клітин:
В В
Підставами потенціали в нерівності, отримаємо:
; -1 <3; 4 = 4; -4> 0
; 3> 2 ; 8> 7 ; 9> 6
Ми бачимо, що не виконуються три нерівність причому
;
;
.
Отже, план можна поліпшити, ввівши в план перевезення, для якої різниця виявилася менше різниць. З цією метою складемо цикл, що має початок у вільній клітці (3, 3), а інші вершини - у зайнятих клітинах, послідовно збільшуючи і зменшуючи перевезення, що потрапили в цикл, на величину. Цикл і послідовність збільшення та зменшення перевезень зображено на малюнку 6. p> Вибираємо, тобто в якості вибирається найменша з перевезень, з яких віднімається. При включенні в план перевезення = 4 сумарна вартість перевезень зміниться на, тобто зменшиться на 12 од. і для нового плану складе:
В
В
Малюнок 7 - План Х3 (План)
За умовою для зайнятих клітин:
В В
За умовою для вільних клітин:
В В
Підставами потенціали в нерівності, отримаємо:
; 6 = 6; 2 <3; 7> 4
; -1 <0; 3> 2 ; 8> 7
Ми бачимо, що не виконуються три нерівність причому
;
;
.
Отже, план можна поліпшити, ввівши в план перевезення, для якої різниця виявилася менше різниць. З цією метою складемо цикл, що має початок у вільній клітці (2, 2), а інші вершини - у зайнятих клітинах, послідовно збільшуючи і зменшуючи перевезення, що потрапили в цикл, на величину. Цикл і послідовність збільшення та зменшення перевезень зображено на рисунку 7. p> Вибираємо, тобто в якості вибирається найменша з перевезень, з яких віднімається. При включенні в план перевезення = 8 сумарна вартість перевезень зміниться на, тобто зменшиться на 24 од. і для нового плану складе:
В
В
Рисунок 8 - План Х4
За умовою для зайнятих клітин:
В В
За умовою для вільних клітин:
В В
Підставами потенціали в нерівності, отримаємо:
...
