Математическая модель эквивалентной КЗ
M-метод — метод решения задач линейного программирования канонического вида, то есть задач с ограничениями в форме равенств.
Описание метода[править]
Суть M-метода состоит в построении с помощью искусственных переменных эквивалентной задачи с базисом, а затем решении её симплекс-методом.
Математическая модель канонической задачи имеет следующий вид:
или
Постановка эквивалентной задачи[править]
Для решения задачи канонического вида необходимо составить эквивалентную задачу. Введём новые (искусственные) переменные xj — остатки ресурсов (j-n)-го ограничения, j=n+1,n+2,…,n+m. Добавим эти переменные к соответствующим ограничениям и введём их в целевую функцию с отрицательным коэффициентом -M, где M — очень большое положительное число.
Математическая модель эквивалентной задачи принимает следующий вид:
или
Метод решения[править]
Эквивалентная задача решается симплекс-методом.
Начальная симплекс-таблица для эквивалентной задачи имеет вид:
Если оптимальное значение целевой функции эквивалентной задачи не содержит M-множителей, то получено оптимальное решение, которое при отбрасывании искусственных переменных совпадает с оптимальным решением исходной задачи канонического вида.
В случае если оптимальное значение целевой функции эквивалентной задачи содержит M-множители, то это означает несовместность системы ограничений исходной задачи канонического вида и отсутствие допустимых решений.
Другие методы[править]
- Юдин Д. Б., Гольштейн Е. Г. Линейное программирование. — М., 1963.