Симплекс метод 2 (страница 1 от 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 и ги считаме за непрости, а всички нови ще се считат за прости. В този случай първоначалното възможно решение се изчислява по уникален начин: .

Сега нека покажем стъпките на алгоритъма. На всяка стъпка ще променяме наборите от прости и непрости вектори (движим се по краищата) и матрицата ще изглежда така:

където cB са коефициентите на вектора c, съответстващи на прости променливи (променливите xs съответстват на 0), B са колони, съответстващи на прости променливи. Матрицата, образувана от останалите колони, обозначаваме с D. Защо матрицата ще има тази форма, ще бъде обяснено в описанието на стъпките на алгоритъма.

Избираме първоначалната допустима стойност, както е посочено по-горе. В първата стъпка B е матрицата на идентичността, тъй като xs са основни променливи. cB - нулев вектор по същите причини.

Нека покажем, че в израза само непростите променливи имат ненулев коефициент. Обърнете внимание, че от израза Ax + xs = b простите променливи се изразяват уникално по отношение на непрости такива, тъй като броят на простите променливи е равен на броя на уравненията. Нека x 'е прости и x' 'непрости променливи при дадената итерация. Уравнението Ax + xs = b може да бъде пренаписано като Bx '+ Dx' '= b. Умножете го по B - 1 отляво: x '+ B - 1Dx "= B - 1b. По този начин изразихме прости променливи по отношение на непрости такива, а в израза B - 1Ax + B - 1xs, което е еквивалентно на лявата страна на равенството, всички прости променливи имат единични коефициенти. Следователно, ако добавим равенство към равенството Z - cTx = 0, тогава в полученото равенство всички прости променливи ще имат нулев коефициент - всички прости променливи от формата x ще се отменят, а простите променливи от формата xs няма да влязат в израз .

Нека изберете ръба, по който ще се движим. Тъй като искаме да максимизираме Z, трябва да изберем променлива, която ще намали израза най-много

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

Сега трябва да разберете коя проста променлива ще бъде първата, която ще премине към нула, тъй като входната променлива се увеличава. За да направите това, достатъчно е да разгледате системата:

За фиксирани стойности на непрости променливи системата е уникално разрешима по отношение на простите, поради което можем да определим коя от простите променливи първо ще достигне нула при увеличаване на входа. Тази променлива ще се нарича изходяща. Това ще означава, че сме достигнали нов връх. Сега ще разменяме входящите и изходящите променливи - входящите и изходящите ще „влизат“ в простите, а изходящите от тях ще „излизат“ в сложните. Сега нека пренапишем матрицата B и вектора cB в съответствие с новите набори от прости и непрости променливи, след което се връщаме към втората стъпка. х ''

Тъй като броят на върховете е краен, алгоритъмът ще приключи един ден. Намереният връх ще бъде оптималното решение.

[редактиране] Двуфазен симплекс метод

[редактиране] Причини за използване

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

Процесът на намиране на оригиналния връх не се различава много от еднофазния симплекс метод, но може да се окаже по-труден от по-нататъшната оптимизация.

[редактиране] Промяна на ограниченията

Всички ограничения на задачите се променят съгласно следните правила:

ограниченията от типа "≤" се преобразуват в равенства чрез създаване на допълнителна променлива с коефициент "+1". Тази модификация се извършва в еднофазен симплекс метод, допълнителни променливи се използват допълнително като начална основа.

ограниченията от типа "≥" се допълват с една променлива с коефициент "-1". Тъй като такава променлива не може да се използва в началната база поради отрицателен коефициент, е необходимо да се създаде друга, спомагателна променлива. Помощните променливи винаги се създават с коефициент "+1".

ограничения като "=" се допълват с една спомагателна променлива.

Съответно ще бъдат създадени редица допълнителни и спомагателни променливи. Допълнителни променливи с коефициент "+1" и всички спомагателни се избират в началната база. Внимание: решението, на което съответства тази основа, не е валидно.

[редактиране] Разлики между спомагателните и спомагателните променливи

Въпреки факта, че както допълнителните, така и спомагателните променливи са изкуствено създадени и използвани за създаване на начална основа, техните стойности в решението са много различни:

допълнителни променливи показват колко съответното им ограничение е "недостатъчно използвано". Стойността на допълнителната променлива към нула съответства на равенството на стойностите на дясната и лявата страна на ограничението.

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

Тоест, ненулева стойност на допълнителна променлива може (но не трябва) да сигнализира за неоптималното решение. Ненулева стойност на спомагателната променлива сигнализира за невалидно решение.