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

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

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

Содержание

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

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

[math]L(X) = \sum\limits_{j=1}^n c_jx_j \rightarrow \max[/math]
[math]\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]L(X) = c_1x_1 + c_2x_2 + \ldots + c_nx_n \rightarrow \max[/math]
[math]\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.
Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты