Работа с таблицата за симплекс - studopediya

Първият симплекс таблицата претърпява трансформация, същността на което е да се премести в нов разтвор подкрепа.

за достъп до алгоритъма следващата таблица е:

• видите таблицата последния ред (индекс), а сред този низ от коефициенти (с изключение на колоната на постоянни условия) се избира най-малкото отрицателно число в намирането на макс. или най-голям положителен, когато задачата при мин. Ако има не е, тогава първоначалната основен решение е оптимално и тази таблица е късно;
• видима колона на таблицата. съответстваща на избрания отрицателен (положителен) фактор в последния stroke- ключ колоната и тази колона са избрани положителни коефициенти. Ако няма такива, целевата функция е неограничено върху стойностите на толеранс на променливите и проблемът няма решение;
• между избраната колона изберете коефициентите за която абсолютната стойност на съотношението на съответната свободна елемент (разположен в колона на членове) на елемента е минимална. Това съотношение се нарича толерантен. и линията, в която е ключов;
• допълнително основната променлива. съответстващ толерантен клетъчна линия, за да се прехвърли в изпълнението без. и свободното променлива съответната колона решен елемент се въвежда в редица основа. Изгражда нова таблица, съдържаща новите имена на основни променливи:
• разделят всеки ключов елемент низ (с изключение на свободен членове колона), за да се даде възможност на елемент и получените стойности написани на реда с основна променлива нова симплекс таблицата променения.
• Онлайн позволява разделена на елемент елемент и получената низ е писано в новата таблица на същото място.
• нова таблица на всички елементи на ключовия колоната = 0. освен напред. той vsegdaraven 1.
• колона. който има ключова линия 0, в новата таблица budettakim същото.
• линия. в които в колона на ключ е 0, новата таблица няма да бъде същият.
• Останалите в новите клетки от таблица, съхранявани резултат конверсия елементи старата таблица:

Резултатът е нова симплекс таблица, съответстваща на новия основен решение.

Ако просто обсъден първия проблем се получава, без никакво затруднение основен разтвор се оказа валиден, а след това на редица проблеми оригинален основен разтвор може да има една, две и така нататък. Д. Отрицателните компоненти, т.е.. Д. било неприемливо. В такива проблеми, първо трябва да се прилага на първия етап на симплекс метода, т. Е. го използвате, за да намери приемливо решение (или набор несъответствието на системата от ограничения), а след това се търси най-доброто решение (да се направи заключение относно противоречието на проблем). В същото време не трябва да забравяме, че при първото задействане на сцената на симплекс метода, т. Е. Докато ние търсим действащ основен разтвор, линейната форма, не се счита, както и всички промени, които се отнасят само за системата на ограничения.
Нека задачата на линейното програмиране е дадена в канонична форма, състояща се от м уравнения с п независими променливи (или е дадено във форма след прилагане на допълнителни не-отрицателни променливи).
Изберете група от м основния променливи, които ни позволяват да се намери оригиналния основен разтвор (без ограничение на общността, можем да предположим, че първите м променливи са основните променливи). Изразяване на тези основни променливи по отношение на второстепенни, получаваме следните ограничения на системата:

Този метод на разделяне на променливите в основния и неосновният съответства основния разтвор (k1. К2. Км. 0, 0. 0). Помислете за най-общия случай, когато решението е невалиден. От получената основна решение, първо трябва да отидете и да е допустимо основен разтвор. И не е задължително, че този преход се извършва едновременно, в една стъпка.
При поемане на първоначалния основен разтвор е неприемливо. Следователно, сред система елемент свободен ограничение (2,16) има най-малко един отрицателен (броят на отрицателните свободни членове на системата съвпада с броя на отрицателни първоначалните базови компоненти на разтвора). Нека свободен ки член аз ти уравнение. т. е. основната променлива XI в съответния основен разтвор е отрицателен.
За да преминете към новия базов разтвор е необходимо: да се избере на променливата, която искате да конвертирате от второстепенни да ядро; за да се установи каква е основната променлива в този случай ще отиде в редица второстепенни променливи. При прехвърляне неосновни променлива в основната си стойност обикновено увеличава вместо нула в първоначалния основен разтвор, той ще бъде положително в нов основен разтвор (с изключение на случая на дегенеративен). Ние се върнете в-тото уравнение на системата (2.16), съдържащ отрицателно k1 свободен член. Тя показва, че стойността на XI се увеличава с увеличаване стойностите на второстепенни променливи, които в това уравнение са положителни коефициенти. От това следва, че в по-голямата може да превежда тези nonbasic променливи в системата на уравнение (2.16) с отрицателен постоянен мандат са положителни коефициенти.

Не може да има три изхода:

1. в уравнение система и-ти (2.16) имат основни променливи с положителни коефициенти R. е. всички коефициенти Bi, М + й (като свободна Терминът Ki) са отрицателни. В този случай, системата е в противоречие ограничения, няма възможно разтвор и следователно оптимална;
2. в уравнение I-ти, има една променлива х + J. при което коефициентът В е положителен. В този случай, това е тази променлива се прехвърля към основната;
3. в уравнение I-ти, има няколко променливи с положителни коефициенти Bi, М + J. В този случай, в по-голямата можете да преведете някоя от тях.

След това трябва да се установи каква е основната променлива, за да бъдат превърнати в броя на второстепенни до мястото на прехвърлените в главната. Не-сърцевина превежда е основната променлива, че за първи път става нула при нулево увеличение на не-първичната променлива, преведен на основните. С други думи, ние използваме същото правило, че е създадена по-рано. Има връзки на безплатно членство за коефициентите на променливата, преведени в по-голямата от всички уравнения, където знаците на свободните членове и тези коефициенти са противоположни, отнема абсолютната стойност на тези отношения и са избрали най-малко (ако някои уравнения знаци свободни членове и тези фактори съвпадат Or някои уравнения, които могат да бъдат трансформирани в основната променлива липсва, тогава съотношението се приема за равен).
Уравнението, което се получава от съотношението на най-малката, е избрана. Посветен уравнение и да се покаже някои от ключовите променливи следва да бъдат прехвърлени без ядро. Изразяване на нови основни променливи по отношение на второстепенни, преминете към следващата основна решение.
Ако избраният уравнението ще бъде отрицателен със свободен мандат, новият основен разтвор на броя на отрицателните елементи ще бъде една по-малко от оригинала. Ако избраният уравнението ще бъде положителен (или нула) свободното елемент, нов основен разтвор броят на отрицателните компоненти остават същите, както беше в първоначалния основен разтвор.
Така преминаването към нов основния разтвор е изгодно за избрания уравнението оказа с отрицателен константа, и ако има избор, с предпочитание трябва да се прилага такъв обмен на променливи, в които избрани уравнение е отрицателна константа.
Така че, ние получи нов, подобрен основен разтвор, който е по-близо до зоната на възможно системни решения ограничения. Ако тя е невалидна, тогава за него да се приложи същата схема отново. В резултат на това след краен брой стъпки, ние се получи действителен основен разтвор. Веднага след като допустима основния разтвор е намерена, се преминава към втория етап на метода за симплекс, същността на което се счита в решаване на проблема с Пример 2.4.1.
След като най-добрият начин за намиране на приемливо алкални разтвори, който и да е линейното програмиране проблем може да се затрудни само изчислителни природата.