Задача 2.1

xij – количество перевезенной продукции от i-ого в j-ый пункт

ai – количество произведенной продукции у i-ого производителя

bj – количество потребляемой продукции у j-ого потребителя

Si – себестоимость изготовления одной единицы у i-ого производителя

cij – стоимость перевозки от i-ого производителя к j-ому потребителю за единицу

Z- суммарные затраты по изготовлению и доставке продукции потребителям

Z`-суммарная выгода от изготовления и доставки продукции производителя и потребителя

Ui- оценка i-ого производителя

Vj- оценка j-ого потребителя

w-коэффициент перераспределения груза

Проверка на балансированность:

Сумм (ai)=340+341+415 =1096 ед.

Сумм (bj)= 107+226+238+126=697 ед.

Задача не балансированна. Вводим фиктивного потребителя b₀ c потреблением в 1096-697=399 ед.

	Cij				Si
a1	3	1	5	9	5
a2	9	7	8	2	3
a3	5	3	5	7	4

Матрица полных затрат:

a1	8	6	10	14
a2	12	10	11	5
a3	9	7	9	11

Математическая модель прямой задачи:

Z=8x₁₁+6x₁₂+10x₁₃+14x₁₄+12x₂₁+10x₂₂+11x₂₃+5x₂₄+9x₃₁+7x₃₂+9x₃₃+11x₃₄ –min

Система ограничений:

x₁₁+x₁₂+x₁₃+x₁₄=340 x₁₁+x₂₁+x₃₁=107

x₂₁+x₂₂+x₂₃+x₂₄=341 x₁₂+x₂₂+x₃₂=226

x₃₁+x₃₂+x₃₃+x₃₄=415 x₁₃+x₂₃+x₃₃=238

xij=>0 x₁₄+x₂₄+x₃₄=126

Математическая модель двойственной задачи:

Z`=340U1+341U2+415U3+107V1+226V2+238V3+126V4 –max

Система ограничений:

Ui+Vj<=cij

Ui,Vj – произвольное значение

Первый опорный план составлен по методу наименьшего элемента

ai bj	107		226		238		126		399		Ui
340	107	8	1 1 +w	6	2 22 -w	10		14	0		U1=0
341		12	2 15 -w	10		11	126	5	+ w		U2=4
										0
415		9		7	1 6 +w	9			399 -w		U3= -1
								11		0
Vj	V1=8		V2=6		V3=10		V4=1		V5=1		w=215

r=7 – число базисных клеток

m=3 – число строк

n=5 – число столбцов

[r=7] =[m+n-1=7] – план невырожден и задача имеет оптимальное решение. Это позволит найти потенциалы всех базисных клеток.

Метод потенциалов

Ui+Vj<=cij – критерий оптимальности плана

Для всех базисных клеток: Ui+Vj=cij

U1+V1=8 U1=0 V1=8

U1+V2=6 U2=4 V2=6

U1+V3=10 U3= -1 V3=10

U2+V2=10 V4=1

U2+V4=5 V5=1

U3+V3=9

U3+V5=0

Для всех свободных клеток: Ui+Vj<=cij

U1+V5=1>0 не выполняется на 1

U2+V3=14>11 не выполняется на 3

U2+V5=5>0 не выполняется на 5

В клетку с₂₅ ставим +w