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

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

  Лема 3.1 (основна нерівність теорії двоїстості). Якщо Неможливо розібрати вираз (невідома помилка): X=(x_1,x_2...,x_n)
та Неможливо розібрати вираз (невідома помилка): Y=(y_1,y_2,...,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 + ... + a_2n x_n \le b_2; y_2 \\ ................................ \\ a_m1 x_1 + a_m2 x_2 + ... + a_mn x_n \le b_m; y_m \\ \end{array}} \right.

Маємо:

Неможливо розібрати вираз (невідома помилка): \left\{ {\begin{array}{l} a_11 x_1 y_1+ a_12 x_2 + ... + a_1n x_n \le b_1; y_1 \\ a_21 x_1 + a_22 x_2 + ... + a_2n x_n \le b_2; y_2 \\ ................................ \\ a_m1 x_1 + a_m2 x_2 + ... + a_mn x_n \le b_m; y_m \\ \end{array}} \right.