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

Математическая модель КЗ

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

Математическая модель

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle L(X) = \sum\limits_{j=1}^n c_jx_j \rightarrow \max}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\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}}

или

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle L(X) = c_1x_1 + c_2x_2 + \ldots + c_nx_n \rightarrow \max}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\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}}

Метод решения

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

Другие задачи:

1. Каноническая задача;
2. Производственная задача;
3. Общая прямая задача линейного программирования;
4. Общая двойственная задача линейного программирования;
5. Задачи транспортного типа;
6. Задача целочисленного программирования;
7. Задача о рюкзаке;
8. Задача распределения средств;
9. Задача замены оборудования.

Литература

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