Каноническая задача линейного программирования

Материал из Циклопедии
(перенаправлено с «Каноническая задача»)
Перейти к навигации Перейти к поиску

Каноническая задача — это основная задача линейного программирования канонического вида, т.е. задача с ограничениями в форме равенств.

Математическая модель[править]

Математическая модель канонической задачи имеет следующий вид:

[math]\displaystyle{ L(X) = \sum\limits_{j=1}^n c_jx_j \rightarrow \max }[/math]
[math]\displaystyle{ \begin{cases}\sum\limits_{j=1}^n a_{ij}x_j=b_i, \ \forall i\in N_m \\ x_j \ge 0, \forall j\in N_n\end{cases} }[/math]

или

[math]\displaystyle{ L(X) = c_1x_1 + c_2x_2 + \ldots + c_nx_n \rightarrow \max }[/math]
[math]\displaystyle{ \begin{cases}a_{11}x_1+a_{12}x_2+\ldots+a_{1n}x_n=b_1 \\ a_{21}x_1+a_{22}x_2+\ldots+a_{2n}x_n=b_2 \\ \ldots \\ a_{m1}x_1+a_{m2}x_2+\ldots+a_{mn}x_n=b_m \\ x_1 \ge 0, \ x_2 \ge 0, \ldots, \ x_n \ge 0 \end{cases} }[/math]

Метод решения[править]

Каноническая задача решается М-методом, также для решения может применяться метод искусственного базиса и симплекс-метод.

Другие задачи:[править]

Литература[править]

  • Юдин Д. Б., Гольштейн Е. Г. Линейное программирование — М.,1963.