Симплекс метод 2
Текуща версия (не е тествана)
Не бива да се бърка с "симплексния метод" - произволен метод за оптимизиране на функцията. Вижте метода на Nelder-Mead
Симплексният метод е алгоритъм за решаване на оптимизационен проблем на линейното програмиране чрез итерация върху върховете на изпъкнал многоъгълник в многомерно пространство. Методът е разработен от американския математик Джордж Данциг през 1947г.
2 Алгоритъм на симплексния метод
2.1 Подсилено изявление на проблема
3 Двуфазен симплекс метод
3.1 Причини за употреба
3.2 Промяна на ограниченията
3.2.1 Разлики между спомагателните и спомагателните променливи
3.3 Фази на разтвора
4 Модифициран симплекс метод
5 Двоен симплекс метод
Преминаване от един връх към друг
Проблемът с линейното програмиране е, че е необходимо да се максимизират или минимизират някои линейни функционални функции в многомерно пространство при дадени линейни ограничения.
Имайте предвид, че всяко от линейните неравенства за променливи ограничава полупространство в съответното линейно пространство. В резултат на това всички неравенства ограничават определен многоъгълник (евентуално безкраен), наричан още многогранен конус. Уравнението W (x) = c, където W (x) е максимизираният (или минимизиран) линеен функционал, генерира хиперплоскостта L (c). Зависимостта от c поражда семейство паралелни хиперплани. Тогава екстремният проблем приема следната формулировка: изисква се да се намери най-голямото c, така че хиперплоскостта L (c) да пресича политопа поне в една точка. Обърнете внимание, че пресичането на оптимална хиперплоскост и многогранник ще съдържа поне един връх и ще има повече от един, ако пресечната точка съдържа ръб или k-измерно лице. Следователно, максимумът на функционала може да се търси във върховете на многогранника. Принципът на симплекс метода е, че се избира един от върховете на многогранника, след което движението по неговите ръбове от връх до връх започва в посока на увеличаване на стойността на функционала. Когато преходът по ръб от текущия връх към друг връх с по-висока функционална стойност е невъзможен, се счита, че е намерена оптималната стойност на c.
Последователността на изчисленията по симплексния метод може да бъде разделена на две основни фази:
намиране на оригиналния връх на множеството възможни решения,
последователен преход от един връх в друг, което води до оптимизиране на стойността на целевата функция.
Освен това, в някои случаи оригиналното решение е очевидно или дефиницията му не изисква сложни изчисления, например, когато всички ограничения са представени от неравенства във формата "по-малко или равно" (тогава нулевият вектор определено е осъществимо решение, въпреки че най-вероятно е далеч от най-оптималното) ... При такива проблеми изобщо не е необходимо да се провежда първата фаза на симплексния метод. Симплексният метод, съответно, се разделя на еднофазен и двуфазен.
[редактиране] Алгоритъм на симплекс метод
[редактиране] Подсилено изявление на проблема
Помислете за следния проблем с линейното програмиране:
Сега поставяме този проблем в еквивалентна засилена форма. Необходимо е да се максимизира Z, където:
Тук x са променливи от оригиналния линеен функционал, xs са нови променливи, които допълват старите по такъв начин, че неравенството се превръща в равенство, c са коефициентите на оригиналния линеен функционал, Z е променлива, която трябва да бъде максимизирана. Полупространствата и в пресечната точка образуват многоъгълник, представляващ множеството възможни решения. Разликата между броя на променливите и уравненията ни дава броя на степени на свобода. Най-просто казано, ако разгледаме върха на многоъгълник, това е броят на ребрата, по които можем да продължим да се движим. След това можем да зададем този брой променливи на 0 и да ги наречем „сложни“. Останалите променливи ще бъдат изчислени еднозначно и ще бъдат наречени „прости“. Получената точка ще бъде върхът в пресечната точка на хиперплоскостите, съответстващи на нелеките променливи. За да се намери т.нар. първоначалното осъществимо решение (върхът, от който ще започнем движението), присвояваме всички начални променливи x стойността 0 и ги считаме за непрости, а всички нови ще се считат за прости. В този случай първоначалното възможно решение се изчислява по уникален начин: .