Изменения

[[файл:СМ01.JPG|thumb|300|[[Математическая модель]] КЗ]]

[[файл:ММ01.JPG|thumb|300|Математическая модель эквивалентной КЗ]]

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

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

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

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

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

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

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

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

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

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

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

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

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

*[[Симплекс-метод]];

*[[Метод искусственного базиса]].

== Ссылки ==

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

* [[Участник:Logic-samara]]

[[Категория:Линейное программирование]]