Пять предприятий данного акционерного общества производят четыре вида продукции

Проверим условие разрешимости транспортной задачи:
i=13ai=14+20+12+18+16=80
j=15bj=25+13+20+17=75
Т.к. ai≠bj, то имеем ТЗ открытого типа.
Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равную 5 (80-75). Тарифы перевозки единицы груза к этому предприятию полагаем равны нулю.
Поскольку в матрице присутствуют запрещенные к размещению клетки, то для отыскания оптимального плана достаточно заменить их на максимальные тарифы (6 умноженное на 3).
Найдем исходный опорный план методом наименьшей стоимости.
Поставщики Потребители Ui
25 13 20 17 5
14
2
3
5 14 1
0 0
20
18 13 4 7 4
3
0 -13
12 9 2
5 3 6
18
0 -11
18
3
4 10 18 3 2 5 0 1
16 16 1
2
5
3
0 -12
Vj
13 17 17 1 -1
Проверим число базисных клеток. В общем случае их должно быть: m+n-1=9 шт., т.е. заполненных клеток должно быть 9 штук. В таблице это выполняется, значит, исходный опорный план найден верно. Найдем значение целевой функции
F(x) = 1*14 + 4*13 + 4*7 + 2*9 + 6*3 + 18*10 + 2*3 + 0*5 + 1*16 = 332
Проверим полученный план на оптимальность. Для этого найдем значение потенциалов поставщиков и потребителей Ui и Vj соответственно (потенциалы находим только для базисных клеток) по формуле Ui Vj Cij, полагая, что U1=0 .
Найдем оценки свободных клеток по формуле: ij Ui Vj Cij:
11=0+13-2=1112=0+17-3=1413=0+1-1=0
15=0-1-0=-121=-13+13-18=-1824=-13+1-3=-15
25=-13-1-0=-1432=-11+17-5=134=-11+1-18=-28
35=-11-1-0=-1241=1+13-3=1142=1+17-4=14
52=-12+17-2=353=-12+17-5=054=-12+1-3=-14
55=-12-1-0=-13
Т.к. среди оценок есть положительные, то план не оптимальный. Строим цикл пересчета для свободной клетки (1;2): 1;2 1;4 4;4 4;3 (2;3) (2;2). Определим значение Q; Q min14;13;10 10
Q – это минимум из значений со знаком «[-]».
Поставщики Потребители Ui
25 13 20 17 5
14
2 303254148010 3
5 14 1
0 0
[+Q]
[-Q]
20
18 13 4 7 4
3
0 -13
[-Q]
[+Q]
12 9 2
5 3 6
18
0 -11
18
3
4 10 18 3 2 5 0 1
[-Q]
[+Q]
16 16 1
2
5
3
0 -12
Vj
13 17 17 1 -1
Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках, и вычитаем 10 из xij, стоящих в минусовых клетках. В результате получим новый опорный план:
Поставщики Потребители Ui
25 13 20 17 5
14
2 10 3
5 4 1
0 0
20
18 3 4 17 4
3
0 1
12 9 2
5 3 6
18
0 3
18
3
4
18 13 2 5 0 1
16 16 1
2
5
3
0 2
Vj
-1 3 3 1 -1
Найдем оценки свободных клеток:
11=0-1-2=-313=0+3-5=-215=0-1-0=-1
21=1-1-18=-1824=1+1-3=-225=1-1-0=0
32=3+3-5=134=3+1-18=-1435=3-1-0=2
41=1-1-3=-342=1+3-4=043=1+3-18=-14
52=2+3-2=353=2+3-5=054=2+1-3=0
55=2-1-0=1
Т.к