М-метод

Материал из Циклопедии
Перейти к навигации Перейти к поиску
Математическая модель эквивалентной КЗ

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

Описание метода[править]

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

Каноническая задача[править]

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

Невозможно разобрать выражение (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}}

Постановка эквивалентной задачи[править]

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

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

Невозможно разобрать выражение (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-\sum\limits_{i=1}^m Mx_{n+i}\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+x_{n+i}=b_i,\ \forall i\in N_m\\ x_j\ge 0,\forall j\in N_{n+m}\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-Mx_{n+1}-Mx_{n+2}-\ldots-Mx_{n+m}\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+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}}

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

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

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

ММ03.JPG

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

Другие методы[править]

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

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