d>
1
2
3
4
B j /A i
1
7 (10)
8 (11)
5 (7)
3 (5)
11
2
2 (3)
4 (4)
5 (8)
9 (12)
11
3
6 (9)
3 (4)
1 (1)
2 (2)
8
A i /B j
5
9
9
7
b j A i
Цифри в дужках вказують порядок заповнення елементів в матриці Х 0 (табл. 3.4).
Відповідне значення цільової функції дорівнює
3 * 8 + 1 * 5 + 3 * 7 + 5 * 2 + 6 * 4 + 8 * 1 = 92
В
Таблиця 4
Х 0
В В В
0
3
1
7
11
4
3
0
5
6
0
0
11
6
0
0
0
8
0
8
0
В
5
9
9
7
В
0
3
1
0
В
0
0
Рішення транспортної задачі при виродженому опорному плані
Опорний план називається виродженим, якщо число його ненульових перевезень k менше рангу матриці обмежень. У процесі побудови початкового плану або при його поліпшенні черговий план може виявитися виродженим.
Розглянемо два випадки.
1. Вироджений план є початковим Х 0 . Тоді вибирають деякі нульові елементи матриці Х 0 у як базисних так, щоб при цьому не порушувалося умова базисного плану. Число цих елементів дорівнює. Далі дані елементи заміняють на (де - довільне, нескінченно мале число) і розглядають їх як звичайні базисні елементи плану. Задачу вирішують як невироджених, а в останньому оптимальному плані Х k замість пишуть нулі.
2. Вироджений план виходить при побудові плану Х k +1 на базі Х k , якщо ланцюжок у плані Х k містить не менше двох мінімальних непарних елементів. У такому випадку в матриці Х k +1 думають рівним нулю тільки один з цих елементів, а решта замінюють на, і далі вирішують завдання як невироджених. Якщо на k-му кроці, то при переході від Х k до Х k +1 значення цільової функції не змінюється, а в базис вводиться елемент, для якого перевезення стане рівною.
Приклад 2. Ви...
