М-метод

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

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

M-метод — метод решения задач линейного программирования канонического вида, то есть задач с ограничениями в форме равенств.

Описание метода

Суть M-метода состоит в построении с помощью искусственных переменных эквивалентной задачи с базисом, а затем решении её симплекс-методом.

Каноническая задача

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

[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]

Постановка эквивалентной задачи

Для решения задачи канонического вида необходимо составить эквивалентную задачу. Введём новые (искусственные) переменные x_j — остатки ресурсов (j-n)-го ограничения, j=n+1,n+2,…,n+m. Добавим эти переменные к соответствующим ограничениям и введём их в целевую функцию с отрицательным коэффициентом -M, где M — очень большое положительное число.

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

[math]\displaystyle{ L^*(X) = \sum\limits_{j=1}^n c_jx_j - \sum\limits_{i=1}^m Mx_{n+i}\rightarrow \max }[/math]

[math]\displaystyle{ \begin{cases}\sum\limits_{j=1}^n a_{ij}x_j+x_{n+i}=b_i, \ \forall i\in N_m \\ x_j \ge 0, \forall j\in N_{n+m}\end{cases} }[/math]

или

[math]\displaystyle{ L(X) = c_1x_1 + c_2x_2 + \ldots + c_nx_n - }[/math]

[math]\displaystyle{ -Mx_{n+1} -Mx_{n+2} - \ldots -Mx_{n+m} \rightarrow \max }[/math]

[math]\displaystyle{ \begin{cases}a_{11}x_1+a_{12}x_2+\ldots+a_{1n}x_n+x_{n+1}=b_1 \\ a_{21}x_1+a_{22}x_2+\ldots+a_{2n}x_n+x_{n+2}=b_2 \\ \ldots \\ a_{m1}x_1+a_{m2}x_2+\ldots+a_{mn}x_n+x_{n+m}=b_m \\ x_1 \ge 0, \ x_2 \ge 0, \ldots, \ x_{n+m} \ge 0 \end{cases} }[/math]

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

Эквивалентная задача решается симплекс-методом.

Начальная симплекс-таблица для эквивалентной задачи имеет вид:

Если оптимальное значение целевой функции эквивалентной задачи не содержит M-множителей, то получено оптимальное решение, которое при отбрасывании искусственных переменных совпадает с оптимальным решением исходной задачи канонического вида. В случае если оптимальное значение целевой функции эквивалентной задачи содержит M-множители, то это означает несовместность системы ограничений исходной задачи канонического вида и отсутствие допустимых решений.

Другие методы

• Симплекс-метод;
• Метод искусственного базиса.

Литература

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