Двойният симплекс метод

Решението на проблема с директната оптимизация може да бъде определено с помощта на симплексния метод. Тя може да бъде получена чрез заместване на основата, при която всички свободни термини в отношенията на директната система стават неотрицателни, тъй като само за неотрицателни свободни термини за нулеви стойности на неосновни променливи, променливите на основата ще бъдат неотрицателни. В същото време екстремалната стойност на целевата функция се постига с такава промяна на основните променливи, за която всички коефициенти за неосновни променливи в израза за L са отрицателни.

Извиква се двойният симплекс метод метод за последователно подобряване на оценките. Значението му по същество е, че вместо директния проблем се решава дуалният проблем и след това се определят оптималните стойности на директния проблем от оптималните стойности на променливите на дуалния проблем и оптималното основно решение на един проблем се получава чрез приравняване на новите му основни променливи с коефициентите за съответните неосновни променливи в линейната форма на дуалната задача, взета със знака „-“.

Двойният симплекс метод разумно е да се прилага, когато броят на ограниченията в първоначалния проблем е много по-голям от броя на неизвестните. Ако в този случай преминем към дуалния проблем, тогава симплексната процедура ще бъде по-проста, отколкото при директния проблем. В същото време методът на двойния симплекс се използва широко в различни методи за решаване на цели числа.програмиране.

Решението на дуалния проблем често се нарича псевдо план, за да се разграничи от решаването на директен проблем, наречен просто план.

По-лесно е да илюстрирате двойния метод с пример.

Пример. Помислете за следния проблем с линейното програмиране: