11.4. ДВОЙЕН СИМПЛЕКСЕН МЕТОД
От резултатите от предишните раздели следва, че за да получим решение на първоначалния проблем, можем да преминем към двойния и, използвайки оценки на неговия оптимален дизайн, да определим оптималното решение на първоначалния проблем.
Преходът към двойния проблем не е необходим, тъй като ако разгледаме първата симплексна таблица с единична допълнителна основа, тогава е лесно да се види, че колоните съдържат оригиналния проблем, а двойният проблем е написан в редовете.
Както беше показано, при решаването на директния проблем на всяка итерация разликата, т.е. величина -коефициент с променлива, е равно на разликата между дясната и лявата страна на съответното ограничение на двойствения проблем. Ако при решаването на директен проблем с максимизираща се целева функция итерацията не води до оптимално решение, тогава поне за една променлива и само в оптималното за всичкиразлика .
Като се има предвид това условие с двойствеността, взета под внимание, можем да напишем
.
По този начин, ако, тогава . Това означава, че когато решението на основния проблем не е оптимално, решението на двойния проблем е невалидно. От друга страна 
при . Това означава, че оптималното решение на първичната задача съответства на допустимо решение на двойствената задача.
Това направи възможно разработването на нов метод за решаване на проблеми с линейното програмиране, който първо води до неприемливо, но „по-добро от оптималното“ решение (в обичайния симплекс метод първо намираме допустимо, но неоптималенрешение). Нов метод, наречен двоен симплексен метод, осигурява изпълнението на условието за оптималност на решението и неговото систематично „приближаване“ до областта на възможните решения. Когато полученото решение се окаже допустимо, итеративният процес на изчисления завършва, тъй като това решение също е оптимално.
Двойният симплексен метод позволява решаване на проблеми с линейно програмиране, чиито системи с ограничения, с положителна основа, съдържат свободни термини от произволен знак. Този метод дава възможност да се намали броят на трансформациите на системата за ограничения, както и размерът на симплексната таблица. Помислете за приложението на двойния симплекс метод, като използвате пример.
Пример. Намерете минимума на функция 
под ограничения
.
Да преминем към каноничната форма:
под ограничения
Първоначалната симплексна таблица има формата
|
Основен променливи |
х 1 |
х 2 |
х 3 |
х 4 |
х 5 |
Решение |
|
х 3 х 4 х 5 |
–3 –4 |
–1 –3 |
–3 –6 |
|||
|
–2 |
–1 |
Първоначално основно решениеоптимално, но не и приемливо.
Подобно на обичайния симплекс метод, разглежданият метод на решение се основава на използването на условия за допустимост и оптималност.
Условие за допустимост. Най-голямата отрицателна основна променлива по абсолютна стойност се избира като изключена променлива (ако има алтернативи, изборът се прави произволно). Ако всички основни променливи са неотрицателни, изчислителният процес приключва, тъй като полученото решение е осъществимо и оптимално.
Състояние оптималност. Променливата, включена в основата, се избира измежду неосновните променливи, както следва. Изчисляват се съотношенията на коефициентите на лявата страна-уравнения към съответните коефициенти на уравнението, свързано с изключената променлива. Връзки с положителни или нулеви знаменатели не се вземат предвид. При задачата за минимизиране на входната променлива трябва да съответства най-малкото от посочените съотношения, а при задачата за максимизиране - отношението с най-малка абсолютна стойност (ако има алтернативи, изборът се прави произволно). Ако знаменателите на всички съотношения са нула или положителни, проблемът няма възможни решения.
След избора на променливите, които да бъдат включени в основата и да бъдат изключени, се извършва обичайната операция за трансформиране на редовете на симплексната таблица, за да се получи следващото решение.
В този пример изключената променлива е. Съотношенията, изчислени за определяне на новата базова променлива, са показани в следната таблица:
|
Променливи |
х 1 |
х 2 |
х 3 |
х 4 |
х 5 |
|
Уравнението х 4 - уравнение |
–2 –4 |
–1 –3 |
|||
|
Поведение |
Променливата, която трябва да бъде включена, е х 2. Последващото преобразуване на низ води до нова симплексна таблица:
|
Основен променливи |
х 1 |
х 2 |
х 3 |
х 4 |
х 5 |
Решение |
|
х 3 х 2 х 5 |
–1 –1 |
|||||
Ново решение също оптимално, но все пак невалидно. Като нова изключена променлива избираме (произволно) х 3 . Нека дефинираме включена променлива.
|
Променливи |
х 1 |
х 2 |
х 3 |
х 4 |
х 5 |
|
Уравнението х 4 - уравнение |
|||||
|
поведение |
Симплексен метод - това е метод за последователен преход от едно основно решение (върхът на полиедъра на решението) на системата от ограничения на задача за линейно програмиране към друго основно решение, докато целевата функция приеме оптималната стойност (максимална или минимална).
Симплексният метод е универсален метод, който може да реши всяко проблем с линейно програмиране, докато графичният метод е подходящ само за система с ограничения с две променливи.
Симплексният метод е предложен от американския математик Р. Данциг през 1947 г., оттогава за нуждите на индустрията този метод често решава проблеми с линейно програмиране с хиляди променливи и ограничения.
Преди да преминете към алгоритъма на симплексния метод, няколко дефиниции.
Всяко неотрицателно решение на система от ограничения се нарича приемливо решение .
Нека има система мограничения от нпроменливи ( мн).
Допустимо основно решение е разтвор, съдържащ мнеотрицателни майор (основен ) променливи и н - м неосновни . (неосновен, или Безплатно ) променливи. Неосновните променливи в основното решение са равни на нула, докато основните променливи по правило са различни от нула, т.е. те са положителни числа.
Всякакви мсистемни променливи млинейни уравнения с нсе наричат променливи основен , ако детерминантата на коефициентите при тях е различна от нула. След това останалите н - мсе наричат променливи неосновни (или Безплатно ).
Алгоритъм на симплексния метод
- Етап 1. Приведете проблема с линейното програмиране до канонична форма. За да направите това, преместете свободните членове в дясната страна (ако сред тези свободни членове има отрицателни, тогава умножете съответното уравнение или неравенство по - 1) и въведете допълнителни променливи във всяко ограничение (със знак плюс, ако в първоначално неравенство знакът е по-малък или равен на ", и със знак минус, ако е "по-голям или равен на").
- Стъпка 2. Ако в получената система муравнения, тогава мвземете променливите за главни, изразете главните променливи по отношение на неосновните и намерете съответното базисно решение. Ако намереното базисно решение се окаже допустимо, преминаваме към допустимото базисно решение.
- Стъпка 3. Изразете целевата функция по отношение на второстепенните променливи на изпълнимото основно решение. Ако максимумът (минимумът) на линейната форма е намерен и в израза му няма неосновни променливи с отрицателни (положителни) коефициенти, тогава критерият за оптималност е изпълнен и полученото базисно решение е оптимално - решението е край. Ако при намиране на максимума (минимума) на линейна форма нейният израз съдържа една или повече неосновни променливи с отрицателни (положителни) коефициенти, преминете към ново основно решение.
- Стъпка 4. От неосновните променливи, включени в линейната форма с отрицателни (положителни) коефициенти, изберете тази, която съответства на най-големия (модулен) коефициент, и я прехвърлете към основните. Отидете на стъпка 2.
Важни условия
Някои специални случаи са разгледани в отделни статии: кога максимална целева функция – безкрайност, кога системата няма решение, и когато оптималното решение не е единственото .
След това ще анализираме типичен пример, когато системата от ограничения е последователна и има краен оптимум и само един. Разновидност на симплексния метод е метод на разпространение за решаване на транспортния проблем .
Симплексен метод със симплексни таблици
Чрез конструиране на симплексни таблици е много по-лесно да се реши проблем с линейно програмиране, отколкото чрез алгебрични трансформации, което е показано в следващия параграф. Симплексните таблици са много визуални. Има няколко вида правила за работа със симплексни таблици. Ще анализираме правилото, което най-често се нарича правило за водеща колона и водещ ред.
Би било полезно да отворите ръководството Действия с дроби в нов прозорец: има ги достатъчно, дроби в задачите по симплексния метод, меко казано.
Пример.
Въвеждаме допълнителни неотрицателни променливи и свеждаме тази система от неравенства до еквивалентна система от уравнения
.
Това беше направено в съответствие със следното правило: ако знакът в първоначалното ограничение е „по-малко или равно на“, тогава трябва да се добави допълнителната променлива, а ако „по-голямо или равно на“, тогава допълнителната променлива трябва да бъде изваден.
Въведените допълнителни променливи се приемат като основни (основни). Тогава и са неосновни (свободни) променливи.
Изразявайки основните (основни) променливи по отношение на неосновни (свободни), получаваме
Ние също така изразяваме целевата функция по отношение на неосновни (свободни) променливи:
От коефициентите на променливи (неизвестни) конструираме първата симплексна таблица.
| маса 1 | ||||
| Основни неизвестни | Безплатни членове | Свободни неизвестни | Спомагателни коефициенти | |
| X1 | X2 | |||
| X3 | -2 | 1 | -2 | |
| X4 | -4 | -1 | -1 | |
| X5 | 2 | 1 | -1 | |
| X6 | 6 | 0 | 1 | |
| Е | 0 | -1 | -2 | |
Последният ред на таблицата, който съдържа целевата функция и коефициентите на свободните променливи в нея, ще се нарича индексен ред.
Полученото решение не е оптимално, тъй като коефициентите на свободните променливи в индексния ред са отрицателни. Тоест оптималното решение ще бъде това, при което коефициентите на свободните променливи в индексния ред ще бъдат по-големи или равни на нула.
За да преминете към следващата таблица, намерете най-голямото (по модул) от числата и . Това число е 2. Следователно водещата колона е колоната, в която е записано
За да определим водещия ред, намираме минимума от съотношенията на свободните членове към елементите на водещата колона и ако числителят има положително число, а знаменателят е отрицателен, отношението се счита за равно на безкрайност.
.
Следователно водещият ред е този, в който е написано
Следователно водещият елемент е -2.
Съставяме втората симплексна таблица.
Въвеждаме новия основен елемент в първия ред, и влизаме в колоната, в която е стоял, въвеждаме нова свободна променлива
Попълнете първия ред. За да направим това, разделяме всички числа във водещия ред на таблица 1 на водещия елемент и го записваме в съответната колона на първия ред на таблица 2, с изключение на числото във водещата колона, където реципрочната стойност на водещия елемент е написан (т.е. един разделен на водещия елемент).
Попълнете колоната за спомагателни коефициенти. За този номер на водещата колона на таблица 1, в допълнение към водещия елемент, пишем с противоположни знаци в колоната на спомагателните коефициенти на таблица 2.
| таблица 2 | ||||
| Основни неизвестни | Безплатни членове | Свободни неизвестни | Спомагателни коефициенти | |
| X1 | X3 | |||
| X2 | 1 | -1/2 | -1/2 | |
| X4 | -3 | -3/2 | -1/2 | 1 |
| X5 | 3 | 1/2 | -1/2 | 1 |
| X6 | 5 | 1/2 | 1/2 | -1 |
| Е | 2 | -2 | -1 | 2 |
Който все още не е отворил в нов прозорец ръководството Действия с дроби, може да го направи сега, защото е време.
За да получим останалите редове от таблица 2, числата, които вече са в първия ред на тази таблица, се умножават по спомагателния коефициент в реда, който се попълва, и към резултата добавяме числото от таблица 1, което е в същия ред с съответната променлива.
Например, за да получим свободния член на втория ред, умножаваме числото 1 по 1 и добавяме числото -4 от таблица 1. Получаваме -3. Намираме коефициента за във втория ред по същия начин: 
. Тъй като в предишната таблица няма колона с нова свободна променлива, коефициентът на втория ред в колоната на новата свободна променлива ще бъде 
(т.е. от таблица 1 добавяме 0, тъй като в таблица 1 няма колона c).
Индексният ред се попълва по същия начин:
Така полученото решение отново не е оптимално, тъй като коефициентите на свободните променливи в индексния ред отново са отрицателни.
За да преминем към следващата симплексна таблица, нека намерим най-голямото (по модул) от числата и , т.е. модулите на коефициентите в индексния ред. Това число е 2. Следователно водещата колона е колоната, която съдържа .
За да търсим водещия ред, нека намерим минималното съотношение на свободните членове към елементите на водещия ред. Получаваме:
.
Следователно водещият ред е този, в който е записано, а водещият елемент е -3/2.
Съставяне на третата симплексна таблица
Записваме новата базова променлива в първия ред. В колоната, в която беше, въвеждаме нова свободна променлива.
Първа линия:
Спомагателни коефициенти:
| Таблица 3 | ||||
| Основни неизвестни | Безплатни членове | Свободни неизвестни | Спомагателни коефициенти | |
| X4 | X3 | |||
| X1 | 2 | -2/3 | 1/3 | |
| X2 | 2 | -1/3 | -1/3 | 1/2 |
| X5 | 2 | 1/3 | -2/3 | -1/2 |
| X6 | 4 | 1/3 | 1/3 | -1/2 |
| Е | 6 | -4/3 | -1/3 | 2 |
Полученото решение отново не е оптимално, тъй като коефициентите на свободните неизвестни в индексния ред отново са отрицателни.
За да отидем на четвъртата симплексна таблица, нека намерим най-голямото от числата и . Това е число.
Следователно водещата колона е тази с .
Минимален модул на отношенията на свободните членове към елементите на водещата колона:
.
Следователно водещият ред е този, в който е написано, а водещият елемент е 1/3.
В четвъртата симплексна таблица записваме новата базова променлива в първия ред. В колоната, където беше, записваме нова безплатна променлива.
Първа линия:
Спомагателни коефициенти:
| Таблица 4 | ||||
| Основни неизвестни | Безплатни членове | Свободни неизвестни | Спомагателни коефициенти | |
| X5 | X3 | |||
| X4 | 6 | 3 | -2 | |
| X1 | 6 | 2 | -1 | 2/3 |
| X2 | 4 | 1 | -1 | 1/3 |
| X6 | 2 | -1 | 1 | -1/3 |
| Е | 14 | 4 | -3 | 4/3 |
Изчисляване на останалите редове по примера на втория ред:
Полученото решение също не е оптимално, но вече е по-добро от предишните, тъй като един от коефициентите за свободни променливи в индексния ред е неотрицателен.
За да подобрим плана, нека преминем към следващата симплексна таблица.
Намерете най-голямото от числата 4 и . Това число е 4. Следователно водещата колона е .
За да намерите водещия ред, намерете
.
Следователно водещата линия е тази, която съдържа . Но те вече бяха заедно сред свободните променливи. Следователно, за да прехвърлим следващата променлива от свободна в основна, избираме друга водеща колона - тази, в която е записано.
За да намерите водещия ред, намерете
.
Следователно ключовият ред е този, в който е написано, а водещият елемент е 1.
В петата симплексна таблица новата базова променлива е записана на първия ред. В колоната, където беше, записваме нова безплатна променлива.
Първа линия:
Спомагателни коефициенти:
| Таблица 5 | ||||
| Основни неизвестни | Безплатни членове | Свободни неизвестни | Спомагателни коефициенти | |
| X5 | X6 | |||
| X3 | 2 | -1 | 1 | |
| X4 | 10 | 2 | ||
| X1 | 8 | 1 | ||
| X2 | 6 | 1 | ||
| Е | 20 | 1 | 3 | 3 |
Нека се опитаме веднага да разберем дали решението не е оптимално. Следователно за останалите редове изчисляваме само свободните членове (за да разберем стойностите на основните променливи, когато свободните променливи са равни на нула) и коефициентите за свободните променливи в индексния ред.
Безплатни членове:
Във втория ред;
В третия ред;
На четвъртия ред.
Индексна линия:
Разглеждаме симплексната таблица 5. Виждаме, че е получено оптималното решение, тъй като коефициентите за свободните неизвестни в индексния ред са неотрицателни.
Симплексен метод с алгебрични трансформации
Нека решим чрез алгебрични трансформации същия пример като в предишния параграф. Трябва да се отбележи, че когато се решава този тип симплекс метод, е по-добре да не се записва целевата функция във формата , тъй като е лесно да се объркате в знаците. Но в този случай точката на алгоритъма, която определя критерия за оптималност, ще бъде модифицирана, както следва.
Ако максимумът (минимумът) на линейната форма е намерен и в израза му няма неосновни променливи с положителни (отрицателни) коефициенти, тогава критерият за оптималност е изпълнен и полученото базисно решение е оптимално - решението е край. Ако при намиране на максимума (минимума) на линейна форма нейният израз съдържа една или повече неосновни променливи с положителни (отрицателни) коефициенти, преминете към ново основно решение.
Пример.Намерете максимума на функция при ограничения
Стъпка I. Въвеждаме допълнителни неотрицателни променливи и свеждаме тази система от неравенства до еквивалентна система от уравнения
.
Въведените допълнителни променливи се приемат като основни, тъй като в този случай основното решение на системата се намира лесно. Тогава и са второстепенни променливи.
Изразявайки основните променливи чрез небазисните, получаваме
Следователно това разделение на променливите на основни и неосновни съответства на основното решение 
, което е невалидно (две променливи са отрицателни) и следователно не е оптимално. Нека преминем от това основно решение към подобрено.
За да решите коя променлива трябва да бъде преобразувана от неглавна в главна, разгледайте някое от двете налични уравнения на последната система с отрицателни свободни членове, например второто. Това показва, че и могат да бъдат преведени в главните променливи, тъй като в това уравнение те имат положителни коефициенти (следователно, когато се увеличат, а това ще се случи, ако преведем някоя от тях в основните променливи, променливата ще се увеличи).
Нека се опитаме да преведем в основната променлива. За да определим коя променлива трябва да бъде прехвърлена от основната към неосновната, намираме абсолютната стойност на най-малкото съотношение на свободните членове на системата към коефициентите при . Ние имаме . Получава се от третото уравнение, което показва, че променливата трябва да се преобразува в неосновни, което е положително в първоначалното основно решение. Следователно полученото основно решение, подобно на първоначалното, съдържа два отрицателни компонента, т.е. няма да има подобрение при прехода към такова основно решение.
Симплексен метод− това е метод за подредено изброяване на референтни планове (подреждането се осигурява чрез монотонна промяна в стойността на целевата функция по време на прехода към следващия план). В този случай е необходимо да се спазва принципът: всяка следваща стъпка трябва да подобрява или в краен случай да не влошава стойността на целевата функция.
За решаване на LLP симплексен методтя е сведена до канонична форма, т.е. от ограничения - неравенства е необходимо да се направят ограничения - равенства. За да направите това, всяко ограничение се допълва с допълнително неотрицателно балансова променливасъс знака „+“, ако знакът за неравенство е „£“, и със знака „–“, ако знакът за неравенство е „³“.
В целевата функция тези допълнителни променливи влизат с нулеви коефициенти, т.е. записът на целевата функция няма да се промени. Всяка променлива, която не е предмет на условието за неотрицателност, може да бъде представена като разлика на две неотрицателни променливи: .
Ако ограниченията на задачата отразяват наличието и потреблението на ресурси, тогава числената стойност на допълнителната променлива в плана на задачата, написана в канонична форма, е равна на количеството на неизползвания ресурс.
За да решим задачата по симплексния метод, ще използваме съкратени симплексни таблици на система от линейни уравнения и модифициран метод на елиминиране на Йордан.
1. Изготвяме първия основен план
Задачата остава същата. Нека приведем стандартната форма на системата от неравенства (1) в каноничната форма на системата от уравнения чрез въвеждане на допълнителни балансови променливи х 3 , х 4 , х 5 ,х 6 .
В икономически смисъл, стойностите на допълнителните променливи х 3 , х 4 , х 5 определя баланса на суровините след продажбата на продуктите.
Матрицата на получената система от уравнения има формата:
Вижда се, че в матрицата Абазисният минор от 4-ти ред е детерминантата, съставена от единични коефициенти за допълнителни променливи х 3 , х 4 , х 5 ,х 6, тъй като не е нула и е равна на 1. Това означава, че колонните вектори за тези променливи са линейно независими, т.е. форма база, и съответните променливи х 3 , х 4 , х 5 ,х 6 са основен(основен). Променливи х 1 , х 2 ще бъде извикан Безплатно(незначителен).
Ако свободните променливи х 1 и х 2 за задаване на различни стойности, тогава, решавайки системата по отношение на основните променливи, получаваме безкраен набор от конкретни решения. Ако са зададени само нулеви стойности за свободни променливи, тогава от безкраен набор от конкретни решения, основни решения- основни планове.
За да разберете дали променливите могат да бъдат основни, е необходимо да изчислите детерминантата, състояща се от коефициентите на тези променливи. Ако тази детерминанта не е равна на нула, тогава тези променливи могат да бъдат основни.
Броят на основните решения и съответният брой групи от основни променливи не може да бъде повече от , където не общият брой променливи, rе броят на основните променливи, r≤ м≤ н.
За нашата задача r = 4; н= 6. Тогава , т.е. Възможни са 15 групи от 4 основни променливи (или 15 основни решения).
Нека решим системата от уравнения по отношение на основните променливи х 3 , х 4 , х 5 ,х 6:
Ако приемем, че свободните променливи х 1 = 0, х 2 = 0, получаваме стойностите на основните променливи: х 3 = 312; х 4 = 15; х 5 = 24;х 6 = -10, т.е. основното решение ще бъде = (0; 0; 312; 15; 24; -10).
Това основно решение е неприемливо, защото х 6 = –10 ≤ 0 и от условието за ограничение х 6 ≥ 0. Следователно вместо променливата х 6 като основа, трябва да вземете друга променлива от свободните х 1 или х 2 .
По-нататъшното решение ще проведем с помощта на съкратени симплексни таблици, като попълним редовете на първата таблица с коефициентите на системата, както следва (Таблица 1):
маса 1
Е- низът се извиква индекс. Той е изпълнен с коефициенти на обективна функция, взети с противоположни знаци, тъй като уравнението на функцията може да бъде представено като Е = 0 – (– 4х 1 – 3х 2).
В графата свободни членове b iима отрицателен елемент b 4 = -10, т.е. решението на системата е невалидно. За да получите валидно решение (основен план), елементът b 4 трябва да бъде неотрицателно.
Избирам х 6 - ред с отрицателен свободен член. Този ред съдържа отрицателни елементи. Изберете някой от тях, например "-1" в х 1 -колона и х 1 - колона приема като колона за разрешение(ще определи, че променливата х 1 ще премине от безплатен към основен).
Споделяме безплатни членове b iвърху съответните елементи а еразрешаваща колона, получаваме оценъчни отношенияΘ аз==(24, 15, 12, 10). От тях избираме най-малкото положително (minΘ аз=10), което ще съответства на линия за разрешение. Низът за разрешение дефинира променлива xj, която на следващата стъпка излиза от основата и се освобождава. Ето защо х 6 -ред е разрешителен ред, а елементът "-1" е позволяващ елемент. Ограждаме го. Променливи х 1 и х 6 са разменени.
Прогнозни съотношения Θ азвъв всеки ред се определят от правилата:
1) Θ аз= ако b iи а еимат различни знаци;
2) Θ аз= ∞ ако b i= 0 и а е < 0;
3) Θ аз= ∞ ако а е = 0;
4) Θ аз= 0 ако b i= 0 и а е > 0;
5) Θ аз= ако b iи а еимат същите знаци.
Ние предприемаме стъпката на модифицираната йорданска елиминация (MJJI) с разрешителен елемент и компилираме нова таблица (Таблица 2) съгласно следното правило:
1) на мястото на разрешаващия елемент (RE) се задава стойност, нейната обратна, т.е. ;
2) елементите на разрешителната линия са разделени на RE;
3) елементите на разрешаващата колона се разделят на RE и знакът се променя;
4) останалите елементи се намират според правилото на правоъгълника:
От табл. 2 се вижда, че свободните членове в b i-колона са неотрицателни, следователно се получава първоначалното допустимо решение - първи базов план= (10; 0; 182; 5; 4; 0). В този случай стойността на функцията Е() = 40. Геометрично това съответства на върха Е(10; 0) полигон за решение (фиг. 1).
таблица 2
2. Проверяваме плана за оптималност.Базовият план не е оптимален, тъй като в Е-линията е с отрицателен коефициент "-4". Ние подобряваме плана.
3. Намиране на нова базова линия
Избираме разрешаващия елемент според правилото:
Избираме най-малкия отрицателен коефициент в Е-ред "-4", който определя разрешаващата колона - х 6; променлива х 6 преведете в основен;
Намираме съотношенията Θ аз, сред тях избираме най-малкия положителен, който съответства на разрешителния низ:
мин Θ аз = мин(14, 5, 2, ∞) = 2, следователно х 5 - линия - разрешителна, променлива х 5 превеждаме в свободни (променливи х 5 и х 6 са разменени).
В пресечната точка на разрешителния ред и колона е разрешителният елемент "2";
Изпълняваме стъпката SHMZhI, изграждаме масата. 3 съгласно горното правило и да получите нов референтен план = (12; 0; 156; 3; 0; 2).
Таблица 3
4. Проверка на новия базов план за оптималност
Базовият план също не е оптимален, тъй като в Е-ред има отрицателен коефициент "-1". Функционална стойност Е() = 48, което геометрично съответства на върха д(12; 0) полигон за решение (фиг. 1). Ние подобряваме плана.
5. Намиране на нова базова линия
х 2-колона е допустима, тъй като в Е-ред, в който е най-малкият отрицателен коефициент "-1". х 2-колона (Δ 2 = -1). Намиране на най-малкото Θ аз: мин Θ аз = мин(≈ 9, 6, ∞, 24) = 6, следователно х 4-ти ред - разрешителен. Разрешителен елемент "1/2". Размяна на променливи х 2 и хчетири . Изпълняваме стъпката SHMZhI, изграждаме масата. 4, получаваме нов референтен план = (9; 6; 51; 0; 0; 5).
6. Проверка на основния план за оптималност
AT Е-линия, всички коефициенти са неотрицателни, следователно референтният план е оптимален. Геометрично съответства на точка д(9; 6) (виж фиг. 1). Оптималният план дава максимална стойност на целевата функция c.u.
Основен идеята за симплексен метод за решаване на LLPсе състои в последователно подобряване на решенията за поддръжка на LLP.
Има няколко начина да напишете симплексния метод.
- Основната форма на симплексния метод;
- Симплексен метод под формата на симплексна таблица;
- Модифициран симплекс метод;
- Симплексен метод в колонна форма;
- Симплексен метод във формата на ред.
Нека дефинираме максималната стойност на целевата функция F(X) = 3x 1 +5x 2 +4x 3 при следните ограничителни условия.
0.1x 1 +0.2x 2 +0.4x 3 ≤1100
0,05x 1 +0,02x 2 +0,02x 3 ≤120
3x1 +x2 +2x3 ≤8000
За да изградим първия референтен план, свеждаме системата от неравенства до система от уравнения чрез въвеждане на допълнителни променливи (преход към каноничната форма).
0.1x1 + 0.2x2 + 0.4x3 + 1x4 + 0x5 + 0x6 = 1100
0,05x1 + 0,02x2 + 0,02x3 + 0x4 + 1x5 + 0x6 = 120
3x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 8000
Основна нотация на симплексния метод
| Решението се осъществява чрез изразяване на основните променливи чрез неосновни: x0 = 3x1 +5x2 +4x3 x 4 = 1100-0,1x 1 -0,2x 2 -0,4x 3 x 5 = 120-0,05x 1 -0,02x 2 -0,02x 3 x 6 = 8000-3x 1 -x 2 -2x 3 |
Симплексен метод под формата на симплексна таблица
Решението се извършва под формата на симплексна таблица. Формата е предназначена за изчисления на компютър. При използване на изкуствена основа се използва специално число М (обикновено 10000).| Планирайте | Основа | AT | х 1 | x2 | х 3 | x4 | x5 | x6 | мин |
| 1 | x4 | 1100 | 0.1 | 0.2 | 0.4 | 1 | 0 | 0 | 5500 |
| x5 | 120 | 0.05 | 0.02 | 0.02 | 0 | 1 | 0 | 6000 | |
| x6 | 8000 | 3 | 1 | 2 | 0 | 0 | 1 | 8000 | |
| Индексна линия | F(X1) | 0 | -3 | -5 | -4 | 0 | 0 | 0 | 0 |
| 2 | x2 | 5500 | 0.5 | 1 | 2 | 5 | 0 | 0 | 11000 |
| x5 | 10 | 0.04 | 0 | -0.02 | -0.1 | 1 | 0 | 250 | |
| x6 | 2500 | 2.5 | 0 | 0 | -5 | 0 | 1 | 1000 | |
| Индексна линия | F(X2) | 27500 | -0.5 | 0 | 6 | 25 | 0 | 0 | 0 |
| 3 | x2 | 5375 | 0 | 1 | 2.25 | 6.25 | -12.5 | 0 | 11000 |
| x1 | 250 | 1 | 0 | -0.5 | -2.5 | 25 | 0 | 250 | |
| x6 | 1875 | 0 | 0 | 1.25 | 1.25 | -62.5 | 1 | 1000 | |
| Индексна линия | F(X3) | 27625 | 0 | 0 | 5.75 | 23.75 | 12.5 | 0 | 0 |
Модифициран симплекс метод
| Матрица на коефициента A = a ij Матрица b. |
Симплексен метод в колонна форма
| Преминаваме към колонната форма на симплексния метод. Изразяваме всяка променлива по отношение на неосновните. x 0 = 0-3(-x 1)-5(-x 2)-4(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 1 = 0-1(-x 1)+0(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 2 = 0+0(-x 1)-1(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 3 = 0+0(-x 1)+0(-x 2)-1(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 4 = 1100+0,1(-x 1)+0,2(-x 2)+0,4(-x 3)+1(-x 4)+0(-x 5)+0(-x 6) x 5 = 120+0,05(-x 1)+0,02(-x 2)+0,02(-x 3)+0(-x 4)+1(-x 5)+0(-x 6) x 6 = 8000+3(-x 1)+1(-x 2)+2(-x 3)+0(-x 4)+0(-x 5)+1(-x 6) Тази система съответства на таблицата T 0 .
|
Симплексен метод в низова форма
Като начална допустима база можем да приемем B 0 =<4, 5, 6>. Тя ще съответства на следната таблица.
|
Матрицата Q, съставена от коефициентите на системата, се нарича симплексна таблицасъответстваща на база B. Симплексна таблица се нарича допустимо, или пряко допустими, ако q i0 ≥ 0. Елементите q i0 от последния ред на симплексната таблица Q се наричат относителни оценки.
Форми на решение по метода на изкуствената основа
За използването на изкуствени променливи, въведени в целевата функция, се налага така наречената санкция от М, много голямо положително число, което обикновено не се посочва.Получената основа се нарича изкуствена, а методът на решение се нарича метод на изкуствена основа.
Освен това изкуствените променливи не са свързани със съдържанието на задачата, но ви позволяват да изградите отправна точка, а процесът на оптимизация принуждава тези променливи да приемат нулеви стойности и да гарантират допустимостта на оптималното решение.
Форми на решение по метода на изкуствената основа:
- М-метод (симплексна таблица);
- двуетапен или двуфазен симплексен метод (основна нотация, модифициран симплексен метод, симплексен метод в колонна форма, симплексен метод в редова форма).
Ако в условието на задачата има ограничения със знак ≥, тогава те могат да бъдат редуцирани до вида ∑a ji b j чрез умножаване на двете части на неравенството по -1. Въвеждаме m допълнителни променливи x n+j ≥0(j =1,m) и трансформираме ограниченията във формата на равенства
(2)
Да приемем, че всички начални променливи на задачата x 1 , x 2 ,..., x n са небазисни. Тогава допълнителните променливи ще бъдат основни и определено решение на системата от ограничения има формата
x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m . (3)
Тъй като в този случай стойността на целевата функция F 0 = 0, можем да представим F(x) както следва:
F(x)=∑c i x i + F 0 =0 (4)
Първоначалната симплексна таблица (симплексна таблица 1) се съставя въз основа на уравнения (2) и (4). Ако допълнителните променливи x n+j са предшествани от знака „+“, както в (2), тогава всички коефициенти преди променливите x i и свободния член b j се въвеждат в симплексната таблица без промяна. Коефициентите на целевата функция при нейното максимизиране се въвеждат в долния ред на симплексната таблица с противоположни знаци. Свободните членове в симплексната таблица определят решението на задачата.
Алгоритъмът за решаване на проблема е следният:
1-ва стъпка. Търсят се елементите на колоната за безплатни членове. Ако всички те са положителни, значи е намерено приемливо основно решение и трябва да се премине към стъпка 5 от алгоритъма, която съответства на намирането на оптималното решение. Ако има отрицателни свободни членове в първоначалната симплексна таблица, тогава решението не е валидно и трябва да преминете към стъпка 2.
2-ра стъпка. За да се намери осъществимо решение, се извършва, докато е необходимо да се реши коя от неосновните променливи да се включи в основата и коя променлива да се оттегли от основата.
Маса 1.
| базисни променливи | Безплатни членове в ограничения | Неосновни променливи | |||||
| х 1 | x2 | ... | х л | ... | x n|||
| xn+1 | b 1 | а 11 | а 12 | ... | 1л | ... | a 1n |
| xn+2 | б 2 | а 21 | а 22 | ... | 2л | ... | a 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+r | b2 | a r1 | a r2 | ... | a rl | ... | rn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+m | b m | a m1 | м2 | ... | aml | ... | amn |
| F(x)макс | F0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
За да направите това, изберете някой от отрицателните елементи на колоната със свободни членове (нека бъде b 2 водещ или позволяващ. Ако няма отрицателни елементи в реда с отрицателен свободен член, тогава системата от ограничения е непоследователна и проблемът няма решение.
В същото време променливата, която първа променя знака с увеличаване на избрания NP x l, се изключва от BP. Това ще бъде x n+r, чийто индекс r се определя от условието
тези. променливата, която съответства на най-малкото отношение на свободния член към елемента от избраната водеща колона. Тази връзка се нарича симплексна релация. Трябва да се вземат предвид само положителни симплексни отношения.
Извиква се низът, съответстващ на променливата x n+r водещи или позволяващи. Елементът на симплексната таблица a rl , който е в пресечната точка на водещия ред и водещата колона, се нарича водещ или разрешаващ елемент.Намирането на водещия елемент завършва работата с всяка следваща симплексна таблица.
3-та стъпка. Изчислява се нова симплексна таблица, чиито елементи се преизчисляват от елементите на симплексната таблица от предходната стъпка и се отбелязват с просто число, т.е. b" j, a" ji, c" i, F" 0. Елементите се преизчисляват по следните формули:
Първо, редът и колоната, които бяха водещи в предишната симплексна таблица, ще бъдат попълнени в новата симплексна таблица. Израз (5) означава, че елементът a "rl на мястото на водещия елемент е равен на реципрочната стойност на елемента от предишната симплексна таблица. Елементите на реда a ri се разделят на водещия елемент, а елементите на колона a jl също се разделят на водещия елемент, но се вземат с обратен знак. Елементите b" r и c" l се изчисляват по същия принцип.
Останалите формули могат лесно да бъдат написани с помощта на .
Правоъгълникът е изграден според старата симплексна таблица по такъв начин, че единият му диагонал е образуван от преизчислените (a ji) и водещите (a rl) елементи (фиг. 1). Вторият диагонал е еднозначно определен. За да се намери нов елемент a "ji, произведението на елементи от противоположния диагонал, разделено на водещия елемент, се изважда от елемент a ji (това се обозначава със знака" - "в клетката). По същия начин елементите b" j, (j≠r) и c" i се преизчисляват, (i≠l).
4-та стъпка. Анализът на нова симплексна таблица започва от 1-вата стъпка на алгоритъма. Действието продължава, докато се намери изпълнимо основно решение, т.е. всички елементи на колоната за безплатни членове трябва да са положителни.
5-та стъпка. Смятаме, че е намерено приемливо основно решение. Разглеждаме коефициентите на правата на целевата функция F(x) . Признак за оптималност на симплексна таблица е неотрицателността на коефициентите за небазисни променливи в F-реда.
Ориз. 1. Правило на правоъгълника
Ако сред коефициентите на F-реда има отрицателни (с изключение на свободния член), тогава трябва да отидете на друго основно решение. При максимизиране на целевата функция базата включва тази на небазисните променливи (например x l), чиято колона съответства на максималната абсолютна стойност на отрицателния коефициент c l в долния ред на симплексната таблица. Това ви позволява да изберете променливата, чието увеличение води до подобряване на целевата функция. Колоната, съответстваща на променливата x l, се нарича водеща колона. В същото време тази променлива x n+r се изключва от основата, чийто индекс r се определя от минималното симплексно отношение:
Редът, съответстващ на x n+r, се нарича водещ ред, а елементът от симплексната таблица a rl , който е в пресечната точка на водещия ред и водещата колона, се нарича водещ елемент.
6-та стъпка. съгласно правилата, посочени в 3-та стъпка. Процедурата продължава, докато се намери оптимално решение или се заключи, че то не съществува.
Ако в процеса на оптимизиране на решението във водещата колона всички елементи са неположителни, тогава водещият ред не може да бъде избран. В този случай функцията в областта на допустимите решения на задачата не е ограничена отгоре и F max ->&∞.
Ако на следващата стъпка от търсенето на екстремум една от основните променливи стане равна на нула, тогава съответното базисно решение се нарича изродено. В този случай се получава така нареченото зацикляне, което се характеризира с това, че една и съща комбинация от BP започва да се повтаря с определена честота (стойността на функцията F се запазва в този случай) и е невъзможно да се премине към ново приемливо основно решение. Зациклянето е един от основните недостатъци на симплексния метод, но е сравнително рядко. На практика в такива случаи обикновено се отказва да се въведе в базата променливата, чиято колона съответства на максималната абсолютна стойност на отрицателния коефициент в целевата функция, и се прави произволен избор на ново базисно решение.
Пример 1. Решете задача
max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)
Симплексен метод и дайте геометрична интерпретация на процеса на решаване.
Графичната интерпретация на решението на задачата е показана на фиг. 2. Максималната стойност на целевата функция се достига на върха на ОДЗП с координати . Нека решим проблема с помощта на симплексни таблици. Умножаваме второто ограничение по (-1) и въвеждаме допълнителни променливи, за да приведем неравенствата под формата на равенства, след което
Първоначалните променливи x 1 и x 2 се приемат като неосновни, а допълнителните x 3 , x 4 и x 5 се считат за основни и съставяме симплексна таблица (симплексна таблица 2). Решението, съответстващо на симплексната таблица. 2, не е валидно; водещият елемент е очертан и избран в съответствие със стъпка 2 от горния алгоритъм. Следващият симплекс раздел. 3 определя допустимо базисно решение; 2 Водещият елемент е очертан и избран в съответствие с 5-та стъпка от алгоритъма за решаване на задачата. Раздел. 4 съответства на оптималното решение на задачата, следователно: x 1 = x 5 = 0; x 2 \u003d 4; x 3 \u003d 3; х 4 = 8; F max = 20.
Ориз. 2. Графично решение на задачата
