15. Принципы построения двойственных задач. Связь между ними.

1. Целевая функция исходной задачи задается на максимум, а целевая функция двойственной на минимум. Все ограничения ИД записываются в виде <=, ДЗ >=.

2. Матрица, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица в двойственной задаче получаются друг из друга транспонированием.

3. Число переменных в двойственной задаче равно числу ограничений в системе исходной задачи, а число ограничений в системе двойственной задачи – числу переменных в исходной задаче (Без учета условий неотрицательности).

4. Ограничения ИД находятся во взаимооднозначном соответствии с переменными ДЗ, и наоборот. Переменные ИЗ обозначаем через x1,x2…xn; ДЗ – y1,y2…ym.

4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе исходной задачи, а правыми частями в соотношениях системы двойственной задачи – коэффициенты при неизвестных в целевой функции исходной задачи.

5. Каждому ограничению-неравенству ИЗ соответствует условие неотрицательности ассоциированной с этим ограничением переменной ДЗ. Каждому ограничению-равенству ИЗ соответствует переменная ДЗ без ограничений на знак, и наоборот. ИЗ называется двойственной ДЗ, и наоборот.

Если Х – некоторый план исходной задачи a Y – произвольный план двойственной задачи, то значение целевой функции исходной задачи при плане Х всегда не превосходит значения целевой функции двойственной задачи при плане Y, т. е. 

Если  для некоторых планов X^* и Y^* ИЗ и ДЗ, то X^* – оптимальный план исходной задачи, а Y^* – оптимальный план двойственной задачи.

16. Симметричные двойственные задачи. Нахождение опт-решения.

{a11x1+a12x2+…+a1nxn<=b1 |y1

{a21x1+a22x2+…+a2nxn<=b2 |y2

{….. | (1)

{am1x1+am2x2+…+amnxn<=bm |ym

xi>=0, i=1,n (2)

F=C1x1+C2x2+…+Cnxn  max (3)

{a11y1+ a21y2+…+am1ym≥C1

{a12y1+a22y2+…+am2ym≥C2 (4)

{……..

{a1ny1+a2ny2+…+amnym≥Cn

yj≥0, j=1,m (5)

f=b1y1+b2y2+…+bmym min (6)

Пара задач (1)-(3) и (4)-(6) наз-ся парой симметричных двойственных задач.

Векторно-матричная запись:

{AX<=B

{X≥0 (1)

F=CX max

{A^TY≥C^T

{Y≥0 (2)

W=B^TYmin

Нахождение опт-решения. При решении задачи (1) симплекс-методом идет перебор допустимых решений задачи (2). На всех итерациях, кроме последней, векторы

уˉ=Сˉ_базВ^-1 не являются допустимыми решениями задачи (1). При этом выполняются след. условия: если xj>0 (xj – базисная переменная), то Δj=0. Это означает, что j-e ограничение двойственной задачи превращается в строгое рав-во на векторе уˉ. Можно предложить симметричный алгоритм, основанный на переборе допустимых решений ПЗ (1). Перебор осуществляется с помощью симплекс-таблиц, в каждой из которых все оценки Δj неотрицательны,Δj≥0 (обеспечение допустимости вектора yˉ). Но значения переменных xj хотя и удовлетворяют системе ограничений задачи (1),Аˉх=Аˉо, но не удовлетворяют условию xj≥0, j=1,n (среди правых частей есть отрицательные). На каждом векторе уˉ целевая ф-ия W задачи находится Wmin, что означает одновременное определение Fmax и оптимального решения xˉ (все правые части симплекс-таблицы становятся неотрицательными). Описанный алгоритм называется двойственным симплекс-методом.