Просмотр исходного текста страницы М-метод

[[файл:СМ01.JPG|thumb|300|[[Математическая модель]] КЗ]]
[[файл:ММ01.JPG|thumb|300|Математическая модель эквивалентной КЗ]]
'''M-метод''' — это метод решения задач линейного программирования канонического вида, т.е. задач с ограничениями в форме равенств.
== Описание метода ==
Суть '''M'''-метода состоит в построении с помощью искусственных переменных эквивалентной задачи с базисом, а затем решении её [[симплекс-метод]]ом. 
== [[Каноническая задача]] ==
Математическая модель канонической задачи имеет следующий вид:

[[файл:СМ01.JPG]]

или 

[[файл:СМ02.JPG]]
== Постановка эквивалентной задачи ==
Для решения задачи канонического вида необходимо составить эквивалентную задачу. Введём новые (искусственные) переменные '''x<sub>j</sub>''' – остатки ресурсов '''(j-n)'''-го ограничения, '''j=n+1,n+2,…,n+m'''. Добавим эти переменные к соответствующим ограничениям и введём их в целевую функцию с отрицательным коэффициентом '''-M''', где '''M''' – очень большое положительное число. 

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

[[файл: ММ01.JPG]].

или 

[[файл:ММ02.JPG]]
== Метод решения ==
Эквивалентная задача решается [[симплекс-метод]]ом.

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

[[файл:ММ03.JPG]]

Если оптимальное значение целевой функции эквивалентной задачи не содержит '''M'''-множителей, то получено оптимальное решение, которое при отбрасывании искусственных переменных совпадает с оптимальным решением исходной задачи канонического вида.
В случае если оптимальное значение целевой функции эквивалентной задачи содержит '''M'''-множители, то это означает несовместность системы ограничений исходной задачи канонического вида и отсутствие допустимых решений.
== Другие методы: ==
*[[симплекс-метод]];
*[[метод искусственного базиса]];
*[[М-метод]].
== Ссылки ==
* Юдин Д. Б., Гольштейн Е. Г. Линейное программирование., М.,1963.
* [[Участник:Logic-samara]]
[[Категория:Линейное программирование]]