Теорема двойственности Первая теорема двойственности

Если одна из двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение. Причём экстремальные значения целевых функций совпадают Z(X*)=f(y*)

X1	Ym+1
X2	Ym+2
X3	Ym+J
X4	Ym+n
Xn+1	Y1
Xn+2	Y2
Xn+i	Yi
Xn+m	Ym

Min

Y*i=-X*n+i

Экономический смысл допустим, если задача определения оптимального плана максимизирующего выпуск продукции разрешимо, то разрешимо и задача определения оценок ресурсов (себестоимость равна цене)

Спрос	П1	П2	П3	П4	Об. Рес-ов
I	2	1	0.5	4	2400
II	1	5	3	0	1200
III	3	0	5	1	3000
Цена	75	30	60	120

75X1+30X2+60X3+120X4max

2X1+X2+0.5X3+4X4<=2400|X5

X1+5X2+3X3<=1200|X1

3X1+5X3+X4<=3000|X2

БП	С5	А0	Х1	Х2	Х3	Х4	X5	Х6	X7
X5	0	2400	75	30	60	120	0	0	0
			2	1	0.5	4	1	0	0
X6	0	1200	1	5	3	0	0	0	0
X7	0	3000	3	0	5	1	0	0	1
F		0	-75	-30	-60	-120	0	0	0
БП	С5	А0	Х1	Х2	Х3	Х4	X5	Х6	X7
X4	120	600	1/2	1/4	1/8	1	1/4	0	0
		1200	1	5	3	0	0	1	0
		2400	2.5	-1/4	4.85	0	-1/4	0	1
						0
						0
БП	С5	А0	Х1	Х2	Х3	Х4	X5	Х6	X7
X4	120	6000/13
X3	60	4800/13
X1	75	1200/13
		90000
			0	75	0	0	30	15	0

X*=(1200/13;0;4800/13;600013)

Y*=(30;15;0)

В М пунктах отправления А1..Ам сосредоточено определённое количество груза соответственно а1..ам имеющийся груз необходимо доставить потребителям- В1..Вн, спрос которых выражается величиной в1..вн. известна стоимость Сij- перевозки единицы груза из I пункта отправления в j пункт назначения требуется составить план перевозок, который полностью удовлетворяет спрос потребителей в грузе и при этом суммарные транспортные издержки минимизируются.

Поставщики	В1	Потребители В2	…	Вн	Запасы груза Ai
А1	С11 Х11	С12 Х12	…	С1н Х1н	а1
А2	С21 Х21	С22 Х22	…	С2н Х2н	а2
Ам	См1 Хм1	См2 Хм2	…	Смн Хмн	ам
Потребность вj	в1	в2	…	вн

Сумма (Хij)=аi

Сумма(Хij)=вj

--------------------------1

Хij>=0 (i=1,m;j=1,n)

--------------------------2

F= сумма(сумма(Cij*xij))

--------------------------3

Дана система ограничений 1 при условии 2 или линейная функция 3. Требуется среди множества решений системы надо найти такое неотрицательное решение, при котором линейная функция 3 принимает минимальное значение. План перевозок называется допустимым, если он удовлетворяет условиям 1 и 2. Допустимый план перевозок, доставляющий минимум целевой функции называется оптимальным.

Теорема 1:

Для того чтобы транспортная задача имела допустимые планы необходимо и достаточно выполнения равенства- сумма(ai)= сумма(вj), если сумма(ai)>/< сумма(вj), то модель называется открытой. Для разрешимости её необходимо преобразовать в закрытую. Для этого вводим либо фиктивного поставщика, либо фиктивного потребителя. Тариф при этом равен нулю и все тарифы одинаковы- целевая функция не меняется.

Теорема 2:

О ранге матрицы.

Ранг матрицы в транспортной задачи на единицу меньше числа уравнений- Z=m+n-1 (Z-число занятых клеток ). Если у нас сумма(ai)>сумма(вj),то необходимо ввести n+1 пункт назначения., т.е. в матрице задачи предусматривается дополнительный столбец и спрос фиктивного потребителя полагается равным Bn+1=сумма(aj)-сумма(вj). Если наоборот, то вводится фиктивный поставщик (am+1=сумма(вj)-сумма(ai))

Построение исходного опорного плана: