Перегляд вихідного коду сторінки Дві леми двоїстості

===Дві леми двоїстості===
   '''Лема 3.1''' (основна нерівність теорії двоїстості). Якщо <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>