М-метод

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

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

Содержание

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

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

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

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

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

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

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

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

[math]L^*(X) = \sum\limits_{j=1}^n c_jx_j - \sum\limits_{i=1}^m Mx_{n+i}\rightarrow \max[/math]
[math]\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]L(X) = c_1x_1 + c_2x_2 + \ldots + c_nx_n -[/math]
[math]-Mx_{n+1} -Mx_{n+2} - \ldots -Mx_{n+m} \rightarrow \max[/math]
[math]\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]

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

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

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

ММ03.JPG

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

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

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

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

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