Типовой расчет №1 «Линейное программирование» (стр. 5 )

вj ai	в1	в2	в3	в4	в5	Запасы
а1	4 10	8	3	1 30	0	40
а2	5 10	9 30	2 20	2	0	70
а3	2 50	5	8	7	0	50
Потребности	70	30	20	30	10	160 160

В рассмотрении остались только пятый потребитель (фиктивный) и второй поставщик: в ячейку (2;5) распределим перевозку 10=min(70-10-30-20;10), получаем:

вj ai	в1	в2	в3	в4	в5	Запасы
а1	4 10	8	3	1 30	0	40
а2	5 10	9 30	2 20	2	0 10	70
а3	2 50	5	8	7	0	50
Потребности	70	30	20	30	10	160 160

Таким образом, все поставки распределены, получено начальное решение транспортной задачи:

Значение целевой функции:

L(X0)=10*4+30*1+10*5+30*9+20*2+10*0+50*2=530 ден. ед.

Базисное решение методом минимального элемента найдено.

Продолжим решение транспортной задачи и найдем оптимальное решение методом потенциалов. Возьмем первоначальный план, составленный методом минимального элемента. Число базисных (заполненных) клеток равно 5+3-1=7. Найдем потенциалы заполненных клеток. Считаем потенциалы складов ui и потребителей vj по правилу: ui+vj=сij. Поскольку в этой системе уравнений на одно больше, чем неизвестных, то один из потенциалов можно выбрать произвольно, положим u1=0 →v4=1 и v1=4;

v1=4→u2=1 и u3=-2;

u2=1→v2=8 и v3=1 и v5=-1.

вj ai	в1	в2	в3	в4	в5	Запасы	ui
а1	4 10	8	3	1 30	0	40	0
а2	5 10	9 30	2 20	2	0 10	70	1
а3	2 50	5	8	7	0	50	-2
Потребности	70	30	20	30	10
vj	4	8	1	1	-1

Вычислим оценки свободных клеток. Находим разности потенциалов в небазисных клетках по формулам:  ∆ij = сij - ui-vj.

∆12=8-0-8=0; ∆13=3-0-1=2; ∆15=0-0-(-1)=1; ∆24=2-1-1=0; ∆32=5-(-2)-8=-1; ∆33=8-(-2)-1=9; ∆34=7-(-2)-1=8; ∆35=0-(-2)-(-1)=3. Среди оценок есть отрицательные: ∆32=-1, значит, опорный план не оптимален и его можно улучшить. В клетке (3;2) построим цикл пересчета, выделен цветом на min(50;30)=30

вj ai	в1	в2	в3	в4	в5	Запасы
а1	4 10	8	3	1 30	0	40
а2	5 10+	9 30-	2 20	2	0 10	70
а3	2 50-	5 0+	8	7	0	50
Потребности	70	30	20	30	10

Получаем новый опорный план:

вj ai	в1	в2	в3	в4	в5	Запасы
а1	4 10	8	3	1 30	0	40
а2	5 40	9	2 20	2	0 10	70
а3	2 20	5 30	8	7	0	50
Потребности	70	30	20	30	10

Получен план

Стоимость перевозок равна:

L(X0)=10*4+30*1+40*5+20*2+10*0+20*2+30*5=500 ден. ед.< 530 де. ед., т. е. этот план ближе к оптимальному. Число базисных (заполненных) клеток равно 5+3-1=7. Найдем потенциалы заполненных клеток. Считаем потенциалы складов ui и потребителей vj по правилу: ui+vj=сij. Поскольку в этой системе уравнений на одно больше, чем неизвестных, то один из потенциалов можно выбрать произвольно, положим u1=0 →v4=1 и v1=4;

v1=4→ u2=2 и u3=-1;

u3=-1→ v2=6;

u2=2→ v3=0 и v5=-2;

вj ai	в1	в2	в3	в4	в5	Запасы	ui
а1	4 10	8	3	1 30	0	40	0
а2	5 40	9	2 20	2	0 10	70	2
а3	2 20	5 30	8	7	0	50	-1
Потребности	70	30	20	30	10
vj	3	6	0	0	-2

Вычислим оценки свободных клеток. Находим разности потенциалов в небазисных клетках по формулам:  ∆ij = сij - ui-vj.

∆12=8-0-6=2; ∆13=3-0-0=3; ∆15=0-0-(-2)=2; ∆22=9-2-6=1; ∆24=2-2-0=0; ∆33=8-(-1)-0=9; ∆34=7-(-1)-0=8; ∆35=0-(-1)-(-2)=3. Среди оценок нет отрицательных, значит план X1 оптимальный. Поскольку в таблице есть базисные клетки с нулевыми поставками, то это означает, что задача имеет не единственное решение. Таким образом, решение транспортной задачи:

L(X*)=500 ден. ед.