М-метод
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]
Постановка эквивалентной задачи[править]
Для решения задачи канонического вида необходимо составить эквивалентную задачу. Введём новые (искусственные) переменные xj — остатки ресурсов (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.