Смешанные двойственные задачи

Математическая модель исходной задачи имеет условия симметричных и несимметричных задач. При составлении двойственной задачи необходимо выполнять правила симметричных и несимметричных задач.

 

Критерий оптимальности (доказательство для симметричных задач)

Критерий оптимальности (критерий оптимизации) — характерный показатель решения задачи, по значению которого оценивается оптимальность найденного решения, то есть максимальное удовлетворение поставленным требованиям. В одной задаче может быть установлено несколько критериев оптимальности.

 

Вторая теорема двойственности для несимметричных двойственных задач

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

Система ограничений исходной задачи в несимметричных двойственных задачах определяется как равенство. Двойственная же задача задается, как неравенство, причем переменные могут быть и отрицательными. Что бы проще понимать постановку задачи будем интерпретировать ее в матричной форме.

Сформулируем двойственную задачу. Необходимо определить матрицу-строку Y=(y₁, y₂, …, y_m), которая максимизирует линейную функцию f=YA₀и удовлетворяет ограничениям

YA> С (1.1)

Сформулируем исходную задачу. Определить матрицу-столбец X=(x₁, x₂, …, x_n), которая минимизирует линейную функцию Z=СХ и. удовлетворяет ограничениям

AX=A0, Х> 0 (1.2)

Как в исходной так и в двойственной задачах А=(a_ij) - матрица коэффициентов системы ограничений, A₀=(b₁, b₂, …, b_m) - матрица-столбец, C=(c₁, c₂, …, c_n) - матрица-строка. Теорема двойственности устанавливает связь между оптимальными планами пары двойственных задач.

Теорема двойственности гласит: если из пары двойственных задач одна обладает оптимальным планом, то и другая имеет решение, причем для экстремальных значений линейных функций выполняется соотношение minZ =maxf. Если линейная функция одной из задач не ограничена, то другая не имеет решения

Доказательство.

Будем считать, что исходная задача имеет оптимальный план. План определен симплексным методом. Можно считать, что конечный базис состоит из т первых векторов A₁, A₂, …, A_m.

Будем считать, что D является матрицей, составленной из компонент векторов конечного базиса A₁, A₂., A_m Приведенная выше таблица состоит из коэффициентов разложения векторов A₁, A₂, …, A_n исходной системы по векторам базиса. В этой таблице каждому вектору A _j соответствует вектор X_j.

Используя соотношения (1.3) и (1.4), получаем:

(1.5) A=D, D^-1A=

(1.6) A₀ =DX*; D^-1A₀ =X

(1.7) min Z= C*X*,

(1.8) = C* - C > 0,

где С=(C₁, C₂, …, C_m), С=(C₁, C₂, …, C_m, C_{m +1}, …, C_n), a=(CX₁-C₁; СХ₂ - С_2, …, CX_n-C_n)=(Z₁-С; Z₂-C₂; …, Z_n-C_n) - вектор, компоненты которого неположительны, так как они совпадают с Z_j-C_j> 0, соответствующими оптимальному плану.

Оптимальный план исходной задачи имеет вид X=D^-1А₀, поэтому оптимальный план двойственной задачи ищем в виде

(1.9) Y = C*D^-1

Покажем, что Y* действительно план двойственной задачи. Для этого ограничения (1.2) запишем в виде неравенства YA-С> 0, в левую часть которого подставим Y*. Тогда на основании (1.9), (1.5) и (1.8) получим

YА-С=С*D^-1А-С=С-С> 0, откуда находим Y*A> С

Так как Y* удовлетворяет ограничениям (1.2), то это и есть план двойственной задачи. При этом плане значение линейной функции двойственной задачи f(Y)=Y*A_0.Учитывая соотношения (1.9), (1.6) и (1.7), имеем

(1.10) f (Y) = Y*A₀=C * D^-1A₀= C*X = minZ(X)

Таким образом, значение линейной функции двойственной задачи от Y численно равно минимальному значению линейной функции исходной задачи

Докажем теперь, что Y* является оптимальным планом. Умножим (1.1) на любой план Y двойственной задачи, а (1.2) - на любой план X исходной задачи: YAX=YA₀=f(Y), YAX> СХ=Z(X), отсюда следует, что для любых планов Х и Y выполняется неравенство

(1.11) f(Y)> Z(X)

Этим же соотношением связаны и экстремальные значения maxf(Y)> minZ(Х). Из последнего неравенства заключаем, что максимальное значение линейной функции достигается только в случае, если maxf(Y)=minZ(X), но это значение f(Y) достигает при плане Y, следовательно, план Y - оптимальный план двойственной задачи.

Аналогично можно доказать, что если двойственная задача имеет решение, то исходная также обладает решением и имеет место соотношение maxf(Y)=minZ(X)

Для доказательства второй части теоремы допустим, что линейная функция исходной задачи не ограничена снизу. Тогда из (1.11) следует, что f(Y) - Y. Это выражение лишено смысла, следовательно, двойственная задача не имеет решений.

Аналогично предположим, что линейная функция двойственной задачи не ограничена сверху. Тогда из (1.11) получаем, что Z(X)+Y. Это выражение также лишено смысла, поэтому исходная задача не имеет решений.

Доказанная теорема позволяет при решении одной из двойственных задач находить оптимальный план другой. Здесь матрица-строка С = (0; 1; 0; -1; - 3, 0), матрица-столбец

1 1 2 0 -1 1 0

A ₀ = 2 A = 0 -4 1 2 -1 0

3 0 3 0 0 1 1

1 0 0

2 -4 3

A «' = 0 1 0

-1 2 0

1 -1 0

0 0 1

Двойственная задача. Найти максимальное значение линейной функции f=y₁+2y₂+5y₃ при ограничениях

y₁> 0

2y₁ - 4y₂ + 3y₃ > 1,

y₂ > 0,

(-y₁) + 2y₂ > (-1),

y₁ - y₂ + y₃ = -3, y₃ > 0

Оптимальный план исходной задачи X = (0; 1/3; 0; 11/3; 4; 0), при котором получим Z_min= -46/3. Используя эту итерацию, найдем оптимальный план двойственной задачи. Согласно теореме двойственности оптимальный план двойственной задачи находится из соотношения Y= C*D^-1, где матрица D^-1 - матрица, обратная матрице, составленной из компонент векторов, входящих в последний базис, при котором получен оптимальный план исходной задачи. В последний базис входят векторы A_5, A_4, A_2; значит,

1 -1 2

D = (A _5, A _4, A ₂₎ = -1 2 -4

1 0 3

Обратная матрица D ^-1 образована из коэффициентов, стоящих в столбцах A₁, A₃, A₆ четвертой итерации:

2 1 0

D ^{-1 =} -1/3 1/3 2/3

-2/3 -1/3 1/3

Из этой же итерации следует С = (-3; -1; 1). Таким образом

2 1 0

Y=С*D^-1 =(-3; - 1; 1) -1/3 1/3 2/3

-2/3 1/3 1/3

Y=(-19/3; - 11/3; - 1/3),

т.е. y_i =С*Х_i, где Х_i - коэффициенты разложения последней итерации, стоящие в столбцах векторов первоначального единичного базиса.

Итак, i-ю двойственную переменную можно получить из значения оценки (m+1) - й строки, стоящей против соответствующего вектора, входившего в первоначальный единичный базис, если к ней прибавить соответствующее значение коэффициента линейной функции:

у₁ =-19/3+0=-19/3; y₂ =-11/3+0=-11/3; у₃ =-1/3+0=-1/3

При этом плане maxf=-46/3

 

⇐ Предыдущая234567891011Следующая ⇒

Поделиться: