Распределить план перевозок однотипного груза от трёх поставщиков к четырём потребителям

Математическая модель задачи:
L=7x11+4x12+9x13+3x14+2x21+11x22+8x23+4x24+3x31+8x32+6x33+5x34-> min
x11+x12 +x13 +x14 ≤400 x21+x22 +x23 +x24 ≤550 x31+ x32 + x33 + x34 ≤ 300x11+x21 +x31 =450x12+x22 +x32 =250x13+x23 +x33 =200x14+ x24 + x34 = 350xij ≥ 0
Поставщики
Потребители B1 B2 B3 B4 Запасы
A1 7 4 9 3 400
A2 2 11 8 4 550
A3 3 8 6 5 300
Потребности 450 250 200 350
Определим тип задачи. ∑A= 400+550+300=1250; ∑B =450+250+200+350=1250.
Условие баланса соблюдается. Запасы равны потребностям=> закрытый тип.
Метод наименьшей стоимости.
Поставщики
Потребители B1 B2 B3 B4 Запасы
A1 - 7 50 4 - 9 350 3 400
A2 450 2 100 11 - 8 - 4 550
A3 - 3 100 8 200 6 - 5 300
Потребности 450 250 200 350
Находим клетку с наименьшей стоимостью и постепенно заполняем таблицу.
m + n - 1 = 6
При таком плане транспортные издержки равны
L=50*4+350*3+450*2+100*11+100*8+200*6=5250
Метод потенциалов .
1. Рассмотрим начальный план, полученный при наименьшей стоимости.
2. Находим потенциалы поставщиков и потребителей, используя первое условие оптимальности плана ui+vj=cij
vj
ui -5 4 2 3 Запасы
B1 B2 B3 B4
0 A1 7 50 4 9 350 3 400
7 A2 450 2 100 11 8 4 550
4 A3 3 100 8 200 6 5 300
Потребности 450 250 200 350
Используя первое условие оптимальности плана и полагая, что u1=0, составим систему линейных уравнений для определения потенциалов и решим ее:
u1 + v2 = 4; v2 = 4 u2 + v2 = 11; u2 = 7 u2 + v1 = 2; v1 = -5 u3 + v2 = 8; u3 = 4 u3 + v3 = 6; v3 = 2 u1 + v4 = 3; v4 = 3
3. Проверяем условие оптимальности для свободных клеток. Есть ли есть нарушения, заносим их со знаком + .Таким образом, начальный план не оптимален
vj
ui -5 4 2 3 Запасы
B1 B2 B3 B4
0 A1 7 476249838204762507429500+50 4 9 16192583820-350 3 400
7 A2 450 2 476250128905-100 11 8 + 4 550
4 A3 3 100 8 200 6 5 300
Потребности 450 250 200 350
4