Відмінності між версіями «Дві леми двоїстості»

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
(→‎Дві леми двоїстості)
(→‎Лема 3.2(достатня умова оптимальності).)
 
(не показано 46 проміжних версій цього учасника)
Рядок 1: Рядок 1:
−
==Дві леми двоїстості==
+
===Дві леми двоїстості===
−
  '''Лема 3.1''' (основна нерівність теорії двоїстості). Якщо <math>X=(x_1,x_2...,x_n)</math> та <math>Y=(y_1,y_2,...,y_m)</math>— допустимі розв’язки <br>  відповідно прямої та двоїстої задач, то виконується нерівність: <br>
+
=='''Лема 3.1'''(основна нерівність теорії двоїстості).==
−
<center> <math>F(X)  \le  Z(Y)</math> або <math>\sum_{j=1}^n c_j x_j \le \sum_{i=1}^m b_i y_i  .</math> (3.7)</center>
+
Якщо <math>X=(x_1,x_2,\ldots,x_n)</math> та <math>Y=(y_1,y_2,\ldots,y_m)</math>— допустимі розв’язки <br>  відповідно прямої та двоїстої задач, то виконується нерівність:  
 +
<center> <math>F(X)  \le  Z(Y)</math> або <math>\sum_{j=1}^n c_j x_j \le \sum_{i=1}^m b_i y_i  .</math> (3.7)</center>
 +
 
 +
''Доведення.''Помножимо кожне рівняння системи (3.2) на відповідну змінну двоїстої задачі:
 +
<center><math>\left\{ {\begin{array}{l}
 +
a_{11} x_1 + a_{12} x_2 + \ldots + a_{1n} x_n \le b_1; y_1 \\
 +
a_{21} x_1 + a_{22} x_2 + \ldots+ a_{2n} x_n \le b_2; y_2 \\
 +
................................ \\
 +
a_{m1} x_1 + a_{m2} x_2 + \ldots + a_{mn} x_n \le b_m; y_m \\
 +
\end{array}} \right.</math></center>
 +
 
 +
Маємо:
 +
 
 +
<center><math>\left\{ {\begin{array}{l}
 +
a_{11} x_1 y_1 + a_{21} x_2 y_1 + \ldots + a_{1n} x_n y_1 \le b_1 y_1 \\
 +
a_{21} x_1 y_2 + a_{22} x_2 y_2 + \ldots+ a_{2n} x_n y_2 \le b_2 y_2 \\
 +
................................ \\
 +
a_{m1} x_1 y_m + a_{m2} x_2 y_m + \ldots + a_{mn} x_n y_m \le b_m y_m \\
 +
\end{array}} \right.</math></center>
 +
 
 +
Підсумувавши праві і ліві частини нерівностей, отримаємо:
 +
 
 +
<center> <math>\sum_{i=1}^m y_i (\sum_{j=1}^n a_{ij} x_j) \le \sum_{i=1}^m b_i y_i  </math> (3.8) </center>
 +
 
 +
Аналогічно перетворимо систему обмежень (3.5) двоїстої задачі:
 +
 
 +
<center><math>\left\{ {\begin{array}{l}
 +
a_{11} y_1 + a_{21} y_2 + \ldots + a_{m1} y_m \ge c_1; x_1 \\
 +
a_{12} y_1 + a_{22} y_2 + \ldots + a_{m2} y_m \ge c_2; x_2 \\
 +
................................ \\
 +
a_{1n} y_1 + a_{2n} y_2 + \ldots + a_{mn} y_m \ge c_n; x_n \\
 +
\end{array}} \right.</math></center>
 +
 
 +
Підсумувавши після множення тут також ліві та праві части-ни, отримаємо нерівність:
 +
 
 +
<center> <math>\sum_{j=1}^n x_j (\sum_{i=1}^m a_{ij} y_i) \ge \sum_{j=1}^n c_j x_j  </math>  (3.9)</center>
 +
 
 +
Ліві частини нерівностей (3.8) та (3.9) збігаються, отже:
 +
 
 +
<center> <math> \sum_{j=1}^n c_j x_j \le \sum_{j=1}^n x_j (\sum_{i=1}^m a_{ij} y_i) = \sum_{i=1}^m y_i (\sum_{j=1}^n a_{ij} x_j) \le \sum_{i=1}^m b_i y_i . </math> </center>
 +
Нерівність (3.7) доведено.
 +
 
 +
=='''Лема 3.2'''(достатня умова оптимальності). ==
 +
Якщо <math>X^{*}=(x_1^*,x_2^*,\ldots,x_n^*)</math> та <math>Y^{*}=(y_1^*,y_2^*,\ldots,y_m^*)</math>— допустимі розв’язки <br>  відповідно прямої та двоїстої задач, то виконується нерівність:
 +
 
 +
<center><math>F(X^{*}) = Z(Y^{*})</math>(3.10)</center>
 +
 
 +
то <math>X^{*},Y^{*}</math> — оптимальні розв’язки відповідних задач.
 +
 
 +
''Доведення.'' Нехай <math>X_1</math> — допустимий план прямої задачі (3.1)—(3.3). Тоді на підставі нерівності (3.7) маємо:
 +
 
 +
<math>F(X_1) \le Z(Y^{*}).</math> За умовою задачі <math>F(X^{*})=Z(Y^{*})</math>, отже
 +
 
 +
<center><math>F(X_1) \le Z(Y^{*}) = F(X^{*}).</math>(3.11)</center>
 +
 +
 
 +
Оскільки за допущенням <math>X_1</math> — довільний допустимий план прямої задачі, то нерівність (3.11) виконується для будь-якого з можливих розв’язків. Отже, маємо, що при <math>X^{*}</math>цільова функція (3.1) набирає найбільшого значення, тобто є оптимальним розв’язком початкової задачі.<br>
 +
В аналогічний спосіб доводиться, що <math>Y^{*}</math> — оптимальний план двоїстої задачі.
 +
 
 +
== '''Література'''  ==
 +
 
 +
[http://fingal.com.ua/content/view/454/76/1/2/ Математичне програмування -Третя теорема двоїстості.Економічний зміст третьої теореми двоїстості.- Наконечний С.І.]

Поточна версія на 22:12, 4 травня 2012

Дві леми двоїстості

Лема 3.1(основна нерівність теорії двоїстості).

Якщо Неможливо розібрати вираз (невідома помилка): X=(x_1,x_2,\ldots,x_n) 

та Неможливо розібрати вираз (невідома помилка): Y=(y_1,y_2,\ldots,y_m)

— допустимі розв’язки
відповідно прямої та двоїстої задач, то виконується нерівність:

Неможливо розібрати вираз (невідома помилка): F(X) \le Z(Y) 
або Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n c_j x_j \le \sum_{i=1}^m b_i y_i  .
(3.7)

Доведення.Помножимо кожне рівняння системи (3.2) на відповідну змінну двоїстої задачі:

Неможливо розібрати вираз (невідома помилка): \left\{ {\begin{array}{l} a_{11} x_1 + a_{12} x_2 + \ldots + a_{1n} x_n \le b_1; y_1 \\ a_{21} x_1 + a_{22} x_2 + \ldots+ a_{2n} x_n \le b_2; y_2 \\ ................................ \\ a_{m1} x_1 + a_{m2} x_2 + \ldots + a_{mn} x_n \le b_m; y_m \\ \end{array}} \right.

Маємо:

Неможливо розібрати вираз (невідома помилка): \left\{ {\begin{array}{l} a_{11} x_1 y_1 + a_{21} x_2 y_1 + \ldots + a_{1n} x_n y_1 \le b_1 y_1 \\ a_{21} x_1 y_2 + a_{22} x_2 y_2 + \ldots+ a_{2n} x_n y_2 \le b_2 y_2 \\ ................................ \\ a_{m1} x_1 y_m + a_{m2} x_2 y_m + \ldots + a_{mn} x_n y_m \le b_m y_m \\ \end{array}} \right.

Підсумувавши праві і ліві частини нерівностей, отримаємо:

Неможливо розібрати вираз (невідома помилка): \sum_{i=1}^m y_i (\sum_{j=1}^n a_{ij} x_j) \le \sum_{i=1}^m b_i y_i (3.8)

Аналогічно перетворимо систему обмежень (3.5) двоїстої задачі:

Неможливо розібрати вираз (невідома помилка): \left\{ {\begin{array}{l} a_{11} y_1 + a_{21} y_2 + \ldots + a_{m1} y_m \ge c_1; x_1 \\ a_{12} y_1 + a_{22} y_2 + \ldots + a_{m2} y_m \ge c_2; x_2 \\ ................................ \\ a_{1n} y_1 + a_{2n} y_2 + \ldots + a_{mn} y_m \ge c_n; x_n \\ \end{array}} \right.

Підсумувавши після множення тут також ліві та праві части-ни, отримаємо нерівність:

Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n x_j (\sum_{i=1}^m a_{ij} y_i) \ge \sum_{j=1}^n c_j x_j (3.9)

Ліві частини нерівностей (3.8) та (3.9) збігаються, отже:

Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n c_j x_j \le \sum_{j=1}^n x_j (\sum_{i=1}^m a_{ij} y_i) = \sum_{i=1}^m y_i (\sum_{j=1}^n a_{ij} x_j) \le \sum_{i=1}^m b_i y_i .

Нерівність (3.7) доведено.

Лема 3.2(достатня умова оптимальності).

Якщо Неможливо розібрати вираз (невідома помилка): X^{*}=(x_1^*,x_2^*,\ldots,x_n^*) 

та Неможливо розібрати вираз (невідома помилка): Y^{*}=(y_1^*,y_2^*,\ldots,y_m^*)

— допустимі розв’язки
відповідно прямої та двоїстої задач, то виконується нерівність:

Неможливо розібрати вираз (невідома помилка): F(X^{*}) = Z(Y^{*}) (3.10)

то Неможливо розібрати вираз (невідома помилка): X^{*},Y^{*} 

— оптимальні розв’язки відповідних задач.

Доведення. Нехай Неможливо розібрати вираз (невідома помилка): X_1 

— допустимий план прямої задачі (3.1)—(3.3). Тоді на підставі нерівності (3.7) маємо:

Неможливо розібрати вираз (невідома помилка): F(X_1) \le Z(Y^{*}). 

За умовою задачі Неможливо розібрати вираз (невідома помилка): F(X^{*})=Z(Y^{*})

, отже

Неможливо розібрати вираз (невідома помилка): F(X_1) \le Z(Y^{*}) = F(X^{*}). (3.11)


Оскільки за допущенням Неможливо розібрати вираз (невідома помилка): X_1 

— довільний допустимий план прямої задачі, то нерівність (3.11) виконується для будь-якого з можливих розв’язків. Отже, маємо, що при Неможливо розібрати вираз (невідома помилка): X^{*}

цільова функція (3.1) набирає найбільшого значення, тобто є оптимальним розв’язком початкової задачі.
В аналогічний спосіб доводиться, що Неможливо розібрати вираз (невідома помилка): Y^{*} 

— оптимальний план двоїстої задачі.

Література

Математичне програмування -Третя теорема двоїстості.Економічний зміст третьої теореми двоїстості.- Наконечний С.І.

Отримано з https://wiki.cusu.edu.ua/index.php?title=Дві_леми_двоїстості&oldid=66892