26.Приведите пример двух взаимно двойственных задач лп. Сформулируйте правило построения двойственной задачи.

Пусть дана задача ЛП:

f = 74x1 + 106x2 + 20x3 → min,

− 6x1 + 10x2 − 4x3 6, (1)

− 4x1 − 2x2 + 6x3 4,

x1 0, x2 0, x3 0.

Составим задачу, двойственную (1), следуя обычному правилу:

Поскольку в исходной задаче целевая функция исследуется на минимум, двойственная задача представляет собой задачу на максимум. Количество нетривиальных ограничений исходной задачи равно количеству неизвестных двойственной задачи, так что в двойственной задаче будет фигурировать 2 неизвестных z1, z2. Коэффициенты целевой функции ϕ двойственной задачи равны правым частям ограничений исходной задачи:

ϕ = 6z₁ + 4z₂ → max

Количество неизвестных исходной задачи равно количеству нетривиальных огра ничений двойственной задачи, так что двойственная задача будет содержать 3 нетривиальных ограничения; матрица левых частей ограничений получается из соответствующей матрицы исходной задачи транспонированием, а правые части ограничений в двойственной задаче равны коэффициентам целевой функции исходной задачи:

−6z₁ − 4z₂ 74,

10z₁ − 2z₂ 106,

−4z₁ + 6z₂ 20.

Таким образом, двойственная задача имеет вид:

ϕ = 6z₁ + 4z₂ → max,

−6z₁ − 4z₂ 74,

10z₁ − 2z₂ 106,

−4z1 + 6z₂ 20,

z1 0, z2 0.

27. Сформулируйте и докажите основное неравенство для взаимно двойственных задач лп. Сформулируйте достаточный признак оптимальности.

I. II.

Пусть Х – какое–нибудь допустимое решение задачи 1, а У – какое-нибудь допустимое решение задачи 2. Тогда f(X)≤φ(Y)

Доказательство: Имеем AXB, откуда следует (AX)^TB^T. Умножив обе части этого нер-ва справа на матрицу Y0, получим (X^TA^T)YB^TY или, ввиду ассоциативности умножения матриц, X^T(A^TY)B^TY=(Y). Аналогично имеем A^TYC, умножив обе части слева на матрицу X^T, будем иметь X^T(A^TY)X^TC=f(X). Соединяя два полученных неравенства, можем записать f(X)X^TA^TY(Y). Отсюда и следует основное неравенство.

Достаточный признак оптимальности. Если для каких-то допустимых решений Х₀ Y₀ задач I и II выполняется равенство f(X₀)=(Y₀), то X₀ есть оптимальное решение задачи I, а Y₀ – оптимальное решение задачи II.

28. Сформулируйте первую и вторую теоремы двойственности. Докажите вторую теорему двойственности (теорему равновесия)

1 теорема двойственности. Критерий оптимальности. Если разрешима одна из двойственных задач I или II, то разрешима и другая, причем maxf=min.

Пусть X и Y – допустимые решения задачи I и II соответственно. Для того, чтобы X было оптимальным решением задачи II, необходимо и достаточно выполнение равенства f(X)=(Y)

2 теорема двойственности. Теорема равновесия. Оптимальные решения ^*=(х₁^*,х₂^*,…х_n^*)^Т и ŷ^*=(у₁^*,у₂^*,…,у_n^*) пары двойственных задач связаны следующим соотношением:

(1)

Доказательство: Из критерия оптимальности =>

Пусть задача 1 имеет размеры m*n

Где i[1;m], j[1;n]

x₁(

y₁(

Что и записано в системе (1). ЧТД

29. Приведите пример постановки транспортной задачи. Что такое оптимальный план перевозок? Что такое транспортная задача с правильным балансом? Сформулируйте критерий разрешимости транспортной задачи.

Пусть имеются m поставщиков A₁,A₂,...,A_m и n потребителей B₁,B₂,...,B_n некоторого однородного продукта. Для i-го поставщика задан объем производства a_i ≥ 0 (i= (1;m)), а для j-го потребителя — объем потребления b_j ≥0 (j= (1;n)) и известна стоимость доставки единицы продукта c_ij≥0 из пункта производства i в пункт потребления j. Переменные x_ij≥0 характеризуют объем первозки между i-м поставщиком и j-м потребителем. Оптимальный план транспортировки соответствует минимуму линейной целевой функции

F(X) = ^m_i=1∑ⁿ_j=1∑c_ij x_ij→min при ограничениях на потребление и поставку ^m_i=1∑x_ij=b_j , ⁿ_j=1∑x_ij=a_i . Число базисных переменных в системе ограничений равно m+n-1.

Данные обычно представляют в виде транспортной таблицы:

Поставщики	Потребители					Запасы
	B1	B2	...	Bn
A1	С11 x11	С12 x12	...	С1n x1n	a1
A2	С21 x21	С22 x22	...	С23 x23	a2
...	...	...	...	...	...
Am	Сm1 xm1	Сm2 xm2	...	Сmn xmn	an
Потребности	b1	b2	...	bn

Критерий разрешимости транспортной задачи — транспортная задача разрешима только, если она имеет правильный баланс.

Общее количество товара у поставщиков равно ^m_i=1∑a_i , a общая потребность в товаре в пунктах назначения есть ⁿ_j=1∑b_j , . Если ^m_i=1∑a_i = ⁿ_j=1∑b_j , т. е. суммарные запасы поставщиков равны суммарным запросам потребителей, то такая задача называется задачей с правильным балансом, а ее модель — закрытой.