Линейное программирование. Симплекс метод / Big M метод
Есть ли какая-то разница между Big M методом решения задач на оптимизацию в линейном программировании и обычный симплекс методом?
Я понимаю, что Big M метод по сути основан на симплекс методе и отличается не особо сильно, однако я так и не понял зачем этот метод вообще нужен.
Везде говорят про то, что Big M метод нужен для случаев, когда ограничения со знаком >=, однако при решении обычным симплекс методом встречался и с такими задачами, где были знаки >=, в таких случаях люди обычно домножают на -1 и получают обратный знак.
Далее соответственно добавляются доп. переменные и в ход идут симплекс преобразования и т.д.
Однако если одно из ограничений уже ввиде равенства, в таком случае по логике не должно добавляться никаких доп. переменных, но при таких условиях симплекс таблица не формируется. Правильно ли я понял, что как раз таки для таких случаев нужен Big M метод или всё-таки нет?
Вот если бы ты знал, как нормально по-русски называется твой "Big M", думаю, никаких подобных вопросов бы не возникло.
Это "МЕТОД ИСКУССТВЕННОГО БАЗИСА". Применяется тогда, когда в исходной канонической задаче нет исходного опорного плана (т.е. не хватает одной или нескольких базисных переменных). Тогда вводятся недостающие, совершенно левые, искусственные базисные переменные, и для каждой из них в целевой функции вводится штраф (c коэффициентом -М, от слова "Mille" - тысяча, или, если тебе мало, "Мillion" - тысяча тысяч))). Штрафы нужны для того, чтобы, как можно скорее, исключить эти искусственные переменные из рассмотрения. В отличие от стандартного симплекс-метода, каждая искусственная переменная при исключении из базиса, сразу же выбрасывается из таблицы. Если все искусственные переменные удастся выбросить, то, получается, что найден опорный план исходной задачи, и дальше работает обычный симплекс-метод. А если оптимальное решение будет получено с искусственными переменными, значит, у исходной задачи нет опорного плана, т.е. она не имеет решений.
Для подробностей можешь загуглить "метод искусственного базиса".
В принципе, AFAIR, в сети имеется в электронном виде книжка Акулича "Математическое программирование в примерах и задачах". Там есть, в частности, и описание метода искусственного базиса с примерами его применения.
