симплекс метода на линейното програмиране

Същността на метода на симплекс

Помислете стандартната проблема LP:

В случай, че множеството от възможни решения на последователност ограничения в (4.1), можем да покажем, че образува изпъкнала многоъгълна област в п-тримерното пространство. Ако тази област е ограничено, ние ще се отнасят към него като изпъкнал многоъгълник в наш тримерно пространство. Според основните теорема на линейното програмиране, ако проблемът с LP има решение, целевата функция достига оптимална стойност в поне една точка на ъгъл от разтворите на полигон. Ако целевата функция достига оптимална стойност в повече от една ъглова точка, тя достига същото решение във всяка точка на отсечката, свързваща тези точки. Ето защо, от теоретична гледна точка LP проблем не е сложно. Просто достатъчно, за да се намери определен брой върховете на многоъгълника и изчисли решения в техните обективни стойности функция. От всички тези стойности изберете най-високата и най-ниската.

От практическа гледна точка, положението е много по-сложно. На първо място, просто налучкване на решения многоъгълник може да бъде практически невъзможно, тъй като на много голям броят на върховете на многоъгълника. И на второ място, дори и с малко на брой върхове, проблемът с намирането на върха координати на сложност, сравнима с първоначалния проблем. Затова има нужда от целенасочена методи изброяване, същността на което, очевидно, е да се оправи, не всички на върха и да си отида от всеки връх на тази, в която "не по-лошо" обективна стойност функция, отколкото предишната. Един от тези методи е метод симплекс.

Основни понятия симплекс метод.

Ние вярваме, че всички неравенства в (4.1) имат формата. ако има неравенство на формата. те лесно да доведе до неравенство. умножаване на лявата и дясната страна на (-1). Тук е стандартен LP проблем (4.1), за да каноничната форма. За да направите това, ще се въведе допълнителни неотрицателни променливи. и да получите съответния каноничен LP проблема:

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

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

Определение 4.2. Основен разтвор, в който всички компоненти не са отрицателни, е допустима основен разтвор.

Определение 4.3. Допустимо основен разтвор се нарича не-дегенерат. ако това точно е съм позитивен елемент, в противен случай, това се нарича изроден.

Изграждане на първата симплекс таблица.

Предполагаме, че проблемът с LP се записва като (4.2). В решаването на проблема със симплекс метода е удобен за използване на така наречените симплекс масите. Превръщаме (4.2) следва, като изберете, като основните променливи, допълнителни променливи:

Трябва да се отбележи, че в (4.3) преди знаци "сумата" в първа и втора линии трябва да бъде "минус" се регистрирате.

Въз основа (4.3) представлява първата таблица симплекс.

Tab.1. Първият симплекс таблицата

Намирането на основния разтвор.

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

Валидиране на основни решения.

1. Основен критерий за решение да е валидно, ако масата за симплекс всички свободни позиции, с изключение може би последната, не-отрицателно.

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

Критерий 2. Проверете ограниченията за съвместимост. Ограничения са несъвместими ако поне една линия, с изключение на последната, с отрицателен свободен елемент, всички стойности са положителни.

Ако открие несъответствие, решаването на проблеми там.

Ако различието не се разкрива и основната решение е неприемливо, тогава ние преминете към стъпка 4.

Проверка на оптимално решение.

Ако основният разтвор се оставя, след това разтворът се тества за критерий оптималност използва 3.

Критерий 3. обективната функция ще има максимум (минимум) стойност, ако последните са елементи на "свободен" променливи колоните са неотрицателна (не-положителна). В този случай, максималната (минимум) стойността на обективната функция е равен на последния елемент в колоната "налични елементи" на.

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

Критерий 4. Целева е ограничена по-горе (по-долу), т.е. има максимум (минимум) стойност на обективната функция, ако при всяка итерация във всяка колона не отговаря оптималността, има най-малко един положителен, не на последно в елемент колона.

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

Ако не се яви безграничната обективна функция по-горе (по-долу), а след това преминете към стъпка 4.

Да бъдеш толерантен елемент.

1. Намиране решаване колона.

а) основен разтвор неприемливо.

Линията, съдържаща отрицателно свободен елемент (с изключение на последния ред), отрицателния селективен елемент. Колона й, който е избран елемент е приет за решаване;

б) от основния разтвор се оставя, без оптимално.

Колоната се приема за решаване всяка колона "свободен променливата", последното от които не отговарят на критерия за оптималност елемент 3.

2. Намирането на резолюция линия.

Наравно тип фракция. където има елементи, позволяващи колона й, и е без елементи, като по този начин имат същия знак. Както резолюция линия е избран, за която минималната стойност намерено фракции.

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

След намиране на елемент позволява преминете към стъпка 5.

Да предположим, че се даде възможност на елемент е. която е формулирана в таблица 1. В този случай, основната променлива трябва да бъде зададен в свободен и безплатен променлива - в база. Компонентите на новата симплекс таблица, която се попълва от следните правила.

1. На мястото на стойността на разделяне елемент се записва.

2. елементи резолюция линии са разделени на позволи елемент, т.е.

3. елементи, позволяващи колоната разделени на разрешаване елементи и са взети с обратен знак, т.е.

4. Останалите елементи. , попълва съгласно принципите на правоъгълника. Първоначално конструирана правоъгълник, един от върховете на които е елемент, който изисква промени и срещу върха винаги фиксиран към елементите. След това клетката изисква промени извадена фракция знаменател от които е равна на разделяне елемент и числителя е продукт на другите два върха на правоъгълника, т. Е:

В резултат на това, ние получаваме нова симплекс таблица за преобразуване (таблица 2).

Таблица 2. Преобразен симплекс таблица

След Стъпка 5, трябва да отидете на втората итерация от стъпка 1, но като се използва вече трансформира маса.

Пример. Намерете максималната стойност на целевата функция F при дадените ограничения:

Ние изготвяме условията на проблема за симплекс метода. За да направите това, първо ние даваме всичко от неравенството на формата. За да направите това, умножете лявата и дясната страна на третото неравенство (-1) и да получите:

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

Като основни променливи е удобно да изберете допълнителни променливи и напишете системата под формата (4.3):

Част от първата симплекс таблица.

1 етап. Ние считаме, алкален разтвор. Основното решение всички свободни променливи са равни на 0, а основните променливи са равни на техните съответни свободни позиции:

Етап 2. Ние проверява допустимостта на получената основна решение. Недопустимо е, защото има отрицателен елемент (3).

Етап 3. Ние проверяваме съвместимостта на ограниченията. Ограничения са съвместими, тъй като в съответствие с отрицателен свободен елемент (3) има по-отрицателен елемент (1).

Тъй като различието не е идентифициран, ние се движат към стъпка 4.

Етап 4. Необходимо е да се намери позволява елемент.

Нека намерим разрешаване колона. Ние имаме една точка). Ние избираме най-малката отрицателна елемент в реда с отрицателен свободен елемент (3). Такъв един елемент, е (-1). Колоната, който съдържа елемент (колона) се приема като разделителната колона.

За да намерят резолюция линии определят минималната положителен съотношението на свободни елементи елементи, позволяващи на колоната. Тъй като. След това ние се резолюция на линията.

Елемент намира в пресечната точка на колона и ред толерантен е толерантен елемент (осветеното квадратче). Той посочва, че основната променлива превърне в свободен и безплатен променлива - в база.

Трансформирайте масата за симплекс с помощта на правилата за преобразуване:

1. На мястото на стойността на разделяне елемент се записва.

2. елементи резолюция линии са разделени на позволи елемент (1).

3. елементи, позволяващи колона разделени в позволяващ елемент (1) и се взема с обратен знак.

4. Останалите елементи са изпълнени от правоъгълника правило. Например, елементът намират в пресечната точка на колона и ред. Тя ще бъде равен.

В резултат на това, превръщането на масата за симплекс получаваме:

1 етап. Ние считаме, алкален разтвор.

Етап 2. Ние проверява допустимостта на получената основна решение. Допустимо е, т.е.. A. Всяка от неговите компоненти, които не са отрицателни.

Тъй като основното решение е възможно, тогава ние преминете към стъпка 3.

Етап 3. Всички елементи на последните "безплатно променливи" колоните са положителни (2 и 5), и следователно са намерени действителен основен разтвор осигурява максимално на обективната функция и максималната цел стойност функция равен на последния елемент в колоната "налични елементи":

Сега се намери минимума на целевата функция. Тъй като ние имаме действащ основен разтвор, но не предоставя минимум на целевата функция, трябва да се провери ограничена функция в съответствие с критерий 4, в който целевата функция е ограничена по-долу, ако всяка колона, които не отговарят на оптималността, има поне един положителен елемент. Ние двете колони "свободни променливи" не отговарят на критерия за оптималност най-малко, т. За да. Както на последния елемент (2 и 5) са положителни. Тези колони са положителни елементи (1 и 4), следователно, не неограничено определени по-долу и преминете към стъпка 4.

Етап 4. Необходимо е да се намери позволява елемент.

Нека намерим разрешаване колона. Имаме б). Изберете всяка графа "свободни променливи", последната от които не отговарят на критерия за оптималност за минимален елемент. Тъй като ние имаме две колони не отговарят на критерия за оптималност, някои от положителните елементи избираме най-големите, така и сред 2 и 5 имат най-висок 5 и, следователно, на колоната ще бъде разрешено.

За да намерят резолюция линии определят минималната положителен съотношението на свободни елементи елементи, позволяващи на колоната. ние намираме:

. След това ние се резолюция на линията.

Етап 5. Превръщаме масата за симплекс и да получите:

1 етап. Ние считаме, алкален разтвор.

Тъй като основното решение е възможно, тогава ние преминете към стъпка 3.

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

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