Відмінності між версіями «Дві леми двоїстості»
(→Лема 3.2(достатня умова оптимальності).) |
(→Лема 3.2(достатня умова оптимальності).) |
||
| Рядок 54: | Рядок 54: | ||
<math>F(X_1) \le Z(Y^{*}).</math> За умовою задачі <math>F(X^{*})=Z(Y^{*})</math>, отже | <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></center> | + | <center><math>F(X_1) \le Z(Y^{*})= F(X^{*}).</math>(3.11)</center> |
Версія за 10:07, 4 травня 2012
Дві леми двоїстості
Лема 3.1(основна нерівність теорії двоїстості).
Якщо Неможливо розібрати вираз (невідома помилка): X=(x_1,x_2,\ldots,x_n)
та Неможливо розібрати вираз (невідома помилка): Y=(y_1,y_2,\ldots,y_m)
— допустимі розв’язки
відповідно прямої та двоїстої задач, то виконується нерівність:
або Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n c_j x_j \le \sum_{i=1}^m b_i y_i .
(3.7)Доведення.Помножимо кожне рівняння системи (3.2) на відповідну змінну двоїстої задачі:
Маємо:
Підсумувавши праві і ліві частини нерівностей, отримаємо:
Аналогічно перетворимо систему обмежень (3.5) двоїстої за-дачі:
Підсумувавши після множення тут також ліві та праві части-ни, отримаємо нерівність:
Ліві частини нерівностей (3.8) та (3.9) збігаються, отже:
Нерівність (3.7) доведено.
Лема 3.2(достатня умова оптимальності).
Якщо Неможливо розібрати вираз (невідома помилка): X^{*}=(x_1^*,x_2^*,\ldots,x_n^*)
та Неможливо розібрати вираз (невідома помилка): Y^{*}=(y_1^*,y_2^*,\ldots,y_m^*)
— допустимі розв’язки
відповідно прямої та двоїстої задач, то виконується нерівність:
то Неможливо розібрати вираз (невідома помилка): X^{*},Y^{*}
— оптимальні розв’язки відповідних задач.
Доведення. Нехай Неможливо розібрати вираз (невідома помилка): X_1
— допустимий план прямої задачі (3.1)—(3.3). Тоді на підставі нерівності (3.7) маємо:
Неможливо розібрати вираз (невідома помилка): F(X_1) \le Z(Y^{*}).
За умовою задачі Неможливо розібрати вираз (невідома помилка): F(X^{*})=Z(Y^{*})
, отже
