V4
V5
400
U1
2502
04
5
11
150 3
370
U2
12
+
808
-
2906
14
11
380
U3
10
__
120 15
+
* 7
2609
18
Т.к. n + m - 1 = 3 + 5 - 1 = 7, а в нашій задачі заповнених клітин всього 6, введемо додаткове число - нуль, на перетині U1 і V2. p> Отримуємо рішення:
X1 = - опорне рішення № 1.
Обчислюємо значення цільової функції на цьому опорному рішенні F = 250.2 + 150.3 + 80.8 + 290.6 + 120.15 + 260.9 = 500 + 450 + 640 + 1740 + 1800 + 2340 = 7470. p> Для перевірки оптимальності опорного рішення необхідно знайти потенціали та оцінки. За ознакою оптимальності в кожній зайнятої опорним рішенням клітці таблиці транспортної задачі сума потенціалів дорівнює вартості
Ui + Vj = Сij
Записуємо систему рівнянь для знаходження потенціалів:
U1 + V1 = 2,
U1 + V2 = 4,
U1 + V5 = 3,
U2 + V2 = 8,
U2 + V3 = 6,
U3 + V2 = 15,
U3 + V4 = 9
Далі одному з потенціалів задаємо значення довільно: нехай U1 = 0. Решта потенціали перебувають однозначно:
U1 = 0,
V1 = 2, V2 = 4, V5 = 3
U2 = 8 - V2 = 4
U3 = 15 - V2 = 11
V4 = 9 - U3 = -2
V3 = 6 - U2 = 2
Перевіряємо опорне рішення Х1 на оптимальність. З цією метою обчислюємо оцінки для всіх незаповнених клітин таблиці.
О”13 = U1 + V3 - С13 = 0 + 2 - 5 = - 3,
О”14 = U1 + V4 - С14 = 0 - 2 -11 = - 13,
О”21 = U2 + V1 - С21 = 4 + 2 - 12 = - 6,
О”24 = U2 + V4 - С24 = 4 - ...