М-метод — различия между версиями
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
[[файл:СМ01.JPG|thumb|300|[[Математическая модель]] КЗ]] | [[файл:СМ01.JPG|thumb|300|[[Математическая модель]] КЗ]] | ||
[[файл:ММ01.JPG|thumb|300|Математическая модель эквивалентной КЗ]] | [[файл:ММ01.JPG|thumb|300|Математическая модель эквивалентной КЗ]] | ||
| − | '''M-метод''' — метод решения задач линейного программирования канонического вида, т.е. задач с ограничениями в форме равенств. | + | '''M-метод''' — это метод решения задач линейного программирования канонического вида, т.е. задач с ограничениями в форме равенств. |
== Описание метода == | == Описание метода == | ||
Суть '''M'''-метода состоит в построении с помощью искусственных переменных эквивалентной задачи с базисом, а затем решении её [[симплекс-метод]]ом. | Суть '''M'''-метода состоит в построении с помощью искусственных переменных эквивалентной задачи с базисом, а затем решении её [[симплекс-метод]]ом. | ||
| Строка 32: | Строка 32: | ||
В случае если оптимальное значение целевой функции эквивалентной задачи содержит '''M'''-множители, то это означает несовместность системы ограничений исходной задачи канонического вида и отсутствие допустимых решений. | В случае если оптимальное значение целевой функции эквивалентной задачи содержит '''M'''-множители, то это означает несовместность системы ограничений исходной задачи канонического вида и отсутствие допустимых решений. | ||
== Другие методы: == | == Другие методы: == | ||
| − | *[[ | + | *[[симплекс-метод]]; |
| − | *[[ | + | *[[метод искусственного базиса]]; |
| + | *[[М-метод]]. | ||
== Ссылки == | == Ссылки == | ||
* Юдин Д. Б., Гольштейн Е. Г. Линейное программирование., М.,1963. | * Юдин Д. Б., Гольштейн Е. Г. Линейное программирование., М.,1963. | ||
* [[Участник:Logic-samara]] | * [[Участник:Logic-samara]] | ||
[[Категория:Линейное программирование]] | [[Категория:Линейное программирование]] | ||
Текущая версия на 18:16, 2 февраля 2016
M-метод — это метод решения задач линейного программирования канонического вида, т.е. задач с ограничениями в форме равенств.
Содержание
Описание метода
Суть M-метода состоит в построении с помощью искусственных переменных эквивалентной задачи с базисом, а затем решении её симплекс-методом.
Каноническая задача
Математическая модель канонической задачи имеет следующий вид:
или
Постановка эквивалентной задачи
Для решения задачи канонического вида необходимо составить эквивалентную задачу. Введём новые (искусственные) переменные xj – остатки ресурсов (j-n)-го ограничения, j=n+1,n+2,…,n+m. Добавим эти переменные к соответствующим ограничениям и введём их в целевую функцию с отрицательным коэффициентом -M, где M – очень большое положительное число.
Математическая модель эквивалентной задачи принимает следующий вид:
.
или
Метод решения
Эквивалентная задача решается симплекс-методом.
Начальная симплекс-таблица для эквивалентной задачи имеет вид:
Если оптимальное значение целевой функции эквивалентной задачи не содержит M-множителей, то получено оптимальное решение, которое при отбрасывании искусственных переменных совпадает с оптимальным решением исходной задачи канонического вида. В случае если оптимальное значение целевой функции эквивалентной задачи содержит M-множители, то это означает несовместность системы ограничений исходной задачи канонического вида и отсутствие допустимых решений.
Другие методы:
- симплекс-метод;
- метод искусственного базиса;
- М-метод.
Ссылки
- Юдин Д. Б., Гольштейн Е. Г. Линейное программирование., М.,1963.
- Участник:Logic-samara
