М-метод

Математическая модель КЗ

Математическая модель эквивалентной КЗ

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

Описание метода

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

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

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

или

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

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

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

.

или

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

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

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

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

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

• симплекс-метод;
• метод искусственного базиса;
• М-метод.

Ссылки

• Юдин Д.Б., Гольштейн Е.Г. Линейное программирование., М.,1963.
• Участник:Logic-samara