Пример 5.1.Решете следната задача на линейното програмиране, като използвате симплексния метод:

Решение:

аз итерация:

x3, x4, x5, x6 x1,x2. Нека изразим основните променливи чрез свободни:

Нека редуцираме целевата функция до следния вид:

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

Таблица 5.3

Оригинална симплексна маса

Според дефиницията на основното решение свободните променливи са равни на нула, а стойностите на основните променливи са равни на съответните стойности на свободните числа, т.е.:

Етап 3: проверка на съвместимостта на системата за ограничения на PAP.

При тази итерация (в таблица 5.3) знакът за несъвместимост на системата за ограничения (знак 1) не е идентифициран (т.е. няма ред с отрицателно свободно число (с изключение на реда целева функция), в който няма да има поне един отрицателен елемент (т.е. отрицателен коефициент за свободна променлива)).

При тази итерация (в таблица 5.3) знакът за неограниченост на целевата функция (знак 2) не беше идентифициран (т.е. няма колона с отрицателен елемент в реда на целевата функция (с изключение на колоната със свободни числа). ), в който няма да има поне един положителен елемент) .

Тъй като намереното основно решение не съдържа отрицателни компоненти, то е допустимо.

Етап 6: проверка на оптималността.

Намереното основно решение не е оптимално, тъй като според критерия за оптималност (знак 4) не трябва да има отрицателни елементи в линията на целевата функция (свободният брой на тази линия не се взема предвид при разглеждането на този критерий). Следователно, според алгоритъма на симплексния метод, преминаваме към етап 8.

Тъй като намереното основно решение е допустимо, ще търсим разрешаващата колона по следната схема: определяме колоните с отрицателни елементи в реда на целевата функция (с изключение на колоната със свободни числа). Съгласно таблица 5.3 има две такива колони: колона „ x1" и колона " x2" От такива колони се избира тази, която съдържа най-малкия елемент в реда на целевата функция. Тя ще бъде разрешителната. колона " x2" съдържа най-малкия елемент (–3) в сравнение с колоната " x1

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

Таблица 5.4

Оригинална симплексна маса

В таблица 5.4 най-малката положителна оценъчна връзка съответства на реда „ x5“, следователно ще бъде разрешително.

Елементът, разположен в пресечната точка на разрешаващата колона и разрешаващия ред, се приема като разрешаващ. В нашия пример това е елементът, който се намира в пресечната точка на линията " x5" и колони " x2».

Разрешаващият елемент показва една база и една свободна променлива, които трябва да бъдат разменени в симплексната таблица, за да се премине към ново „подобрено“ базисно решение. IN в този случайтова са променливи x5И x2, в новата симплексна таблица (Таблица 5.5) ги разменяме.

9.1. Трансформация на разделящия елемент.

Резолюционният елемент от таблица 5.4 се преобразува, както следва:

Въвеждаме получения резултат в подобна клетка в таблица 5.5.

9.2. Преобразуване на низове за резолюция.

Разделяме елементите на разрешаващия ред на таблица 5.4 на разделящия елемент на тази симплексна таблица, резултатите се вписват в подобни клетки на новата симплексна таблица (таблица 5.5). Трансформациите на разделителните низови елементи са дадени в таблица 5.5.

9.3. Преобразуване на разделителната колона.

Разделяме елементите на разделителната колона на Таблица 5.4 на разделителния елемент на тази симплексна таблица и резултатът се взема с обратен знак. Получените резултати се вписват в подобни клетки на новата симплексна таблица (Таблица 5.5). Трансформациите на елементите на разделителната колона са дадени в таблица 5.5.

9.4. Трансформация на останалите елементи от симплексната таблица.

Трансформацията на останалите елементи на симплексната таблица (т.е. елементи, които не са разположени в разрешаващия ред и разрешаващата колона) се извършва съгласно правилото на "правоъгълника".

Например, помислете за трансформиране на елемент, разположен в пресечната точка на линията " x3" и колони "", условно ще го обозначим " x3" В таблица 5.4 мислено начертаваме правоъгълник, единият връх на който се намира в клетката, чиято стойност трансформираме (т.е. в клетката „ x3"), а другият (диагонален връх) е в клетка с разрешаващ елемент. Другите два върха (от втория диагонал) са еднозначно определени. Тогава трансформираната стойност на клетката " x3" ще бъде равна на предишната стойност на тази клетка минус дробта, в чийто знаменател е разделящият елемент (от таблица 5.4), а в числителя е произведението на два други неизползвани върха, т.е.:

« x3»: .

Стойностите на други клетки се преобразуват по подобен начин:

« х3 х1»: ;

« x4»: ;

« х4 х1»: ;

« x6»: ;

« х6 х1»: ;

«»: ;

« x1»: .

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

II итерация:

Етап 1: изготвяне на симплексна таблица.

Таблица 5.5

Симплексна масаII итерации

Етап 2: определяне на основния разтвор.

В резултат на симплексните трансформации се получава ново основно решение (Таблица 5.5):

Както можете да видите, с това основно решение стойността на целевата функция = 15, което е по-голямо, отколкото с предишното основно решение.

Несъответствието на системата от ограничения в съответствие с признак 1 в таблица 5.5 не е установено.

Етап 4: проверка на ограничеността на целевата функция.

Неограничеността на целевата функция в съответствие с критерий 2 в таблица 5.5 не се разкрива.

Етап 5: проверка на допустимостта на намереното основно решение.

Намереното основно решение в съответствие с критерий 4 не е оптимално, тъй като редът на целевата функция на симплексната таблица (Таблица 5.5) съдържа отрицателен елемент: –2 (свободният номер на този ред не се взема предвид при разглеждането на това характеристика). Затова преминаваме към етап 8.

Етап 8: определяне на разрешаващия елемент.

8.1. Определение на колоната за разделителна способност.

Намереното базово решение е приемливо; определяме колоните с отрицателни елементи в реда на целевата функция (с изключение на колоната със свободни числа). Според таблица 5.5 има само една такава колона: „ x1" Затова го приемаме за позволено.

8.2. Дефиниция на разрешаващ низ.

Съгласно получените стойности на положителни оценъчни отношения в таблица 5.6, минимумът е отношението, съответстващо на линията „ x3" Затова го приемаме за позволено.

Таблица 5.6

Симплексна масаII итерации

Етап 9: трансформация на симплексната таблица.

Трансформациите на симплексната таблица (Таблица 5.6) се извършват по същия начин, както в предишната итерация. Резултатите от трансформациите на елементите на симплексната таблица са дадени в таблица 5.7.

III итерация

Въз основа на резултатите от симплексните трансформации от предишната итерация, ние съставяме нова симплексна таблица:

Таблица 5.7

Симплексна масаIII итерации

Етап 2: определяне на основния разтвор.

В резултат на симплексните трансформации се получава ново основно решение (Таблица 5.7):

Етап 3: проверка на съвместимостта на системата от ограничения.

Не е установено несъответствие на системата от ограничения в съответствие с признак 1 в таблица 5.7.

Етап 4: проверка на ограничеността на целевата функция.

Не се разкрива неограниченост на целевата функция в съответствие с критерий 2 в таблица 5.7.

Етап 5: проверка на допустимостта на намереното основно решение.

Намереното базово решение по критерий 3 е приемливо, тъй като не съдържа отрицателни компоненти.

Етап 6: проверка на оптималността на намереното базисно решение.

Намереното основно решение в съответствие с критерий 4 не е оптимално, тъй като редът на целевата функция на симплексната таблица (Таблица 5.7) съдържа отрицателен елемент: –3 (свободният номер на този ред не се взема предвид при разглеждането на това характеристика). Затова преминаваме към етап 8.

Етап 8: определяне на разрешаващия елемент.

8.1. Определение на колоната за разделителна способност.

Намереното базово решение е приемливо; определяме колоните с отрицателни елементи в реда на целевата функция (с изключение на колоната със свободни числа). Според таблица 5.7 има само една такава колона: „ x5" Затова го приемаме за позволено.

8.2. Дефиниция на разрешаващ низ.

Съгласно получените стойности на положителни оценъчни отношения в таблица 5.8, минимумът е отношението, съответстващо на линията „ x4" Затова го приемаме за позволено.

Таблица 5.8

Симплексна масаIII итерации

Етап 9: трансформация на симплексната таблица.

Трансформациите на симплексната таблица (Таблица 5.8) се извършват по същия начин, както в предишната итерация. Резултатите от трансформациите на елементите на симплексната таблица са дадени в таблица 5.9.

IV итерация

Етап 1: изграждане на нова симплексна таблица.

Въз основа на резултатите от симплексните трансформации от предишната итерация, ние съставяме нова симплексна таблица:

Таблица 5.9

Симплексна масаIV итерации

Етап 2: определяне на основния разтвор.

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

Етап 3: проверка на съвместимостта на системата от ограничения.

Несъответствието на системата от ограничения в съответствие с признак 1 в таблица 5.9 не е установено.

Етап 4: проверка на ограничеността на целевата функция.

Не се разкрива неограниченост на целевата функция в съответствие с критерий 2 в таблица 5.9.

Етап 5: проверка на допустимостта на намереното основно решение.

Намереното базово решение по критерий 3 е приемливо, тъй като не съдържа отрицателни компоненти.

Етап 6: проверка на оптималността на намереното базисно решение.

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

Етап 7: проверка на алтернативността на решението.

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

отговор: оптимална стойностцелева функция на разглеждания проблем =24, което се постига при.

Пример 5.2.Решете горния проблем с линейно програмиране, при условие че целевата функция е минимизирана:

Решение:

аз итерация:

Етап 1: формиране на началната симплексна таблица.

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

В получената система от уравнения ние приемаме като разрешени (основни) променливи x3, x4, x5, x6, тогава свободните променливи ще бъдат x1,x2. Нека изразим основните променливи чрез свободни.

Кратка теория

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

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

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

1. способността да се намери първоначален референтен план;
2. наличие на знак за оптималност на опорния план;
3. способността да преминете към не-лош референтен план.

Пример за решение на проблем

Проблемно състояние

За да продава три групи стоки, търговското предприятие разполага с три вида ограничени материални и парични ресурси в размер на , , , единици. В същото време за продажба на 1 група стоки за 1 хил. Рубли. стокооборотът изразходва ресурса от първи вид в брой единици, ресурса от втори вид в брой единици, ресурса от трети вид в брой единици. За продажба на 2 и 3 групи стоки за 1 хил. Рубли. стокооборотът се изразходва според ресурса от първи вид в размер на , единици, ресурси от втори вид в размер на , единици, ресурси от трети вид в размер на , единици. Печалба от продажбата на три групи стоки за 1 хил. Рубли. оборотът е съответно , хиляди рубли.

• Определете планирания обем и структура на търговския оборот, така че печалбата на търговското предприятие да бъде максимална.
• За директната задача за планиране на оборота, решена по симплексния метод, създайте двойна задача за линейно програмиране.
• Установете конюгирани двойки променливи на директните и двойствените задачи.
• Според конюгирани двойки променливи, от решението на директния проблем, се получава решение на двойния проблем, в който се оценяват ресурсите, изразходвани за продажба на стоки.

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

Решение на проблема

Изграждане на модел

Нека означим оборота съответно на 1-ви, 2-ри и трети вид стоки.

Тогава целевата функция, изразяваща получената печалба:

Ограничения за материални и парични ресурси:

Освен това според смисъла на задачата

Получаваме следната задача за линейно програмиране:

Свеждане до каноничната форма на ЗЛП

Нека сведем проблема до каноничен вид. За да трансформираме неравенствата в равенства, въвеждаме допълнителни променливи. Променливите са включени в ограниченията с коефициент 1. Въвеждаме всички допълнителни променливи в целевата функция с коефициент, равен на нула.

Ограничението има предпочитана форма, ако, ако дясната страна е неотрицателна лявата странаима включена променлива с коефициент равен на единица, а останалите ограничения за равенство - с коефициент равен на нула. В нашия случай 1-во, 2-ро, 3-то ограничение имат предпочитана форма със съответните базови променливи.

Решение по симплексния метод

Попълваме симплексната таблица на 0-та итерация.

Тъй като решаваме проблема до максимум, наличието на отрицателни числа в индексния ред при решаване на проблема до максимум показва, че не сме получили оптималното решение и че е необходимо да преминем от таблицата на 0-та итерация към следващият.

Продължаваме към следващата итерация, както следва:

Водещата колона съответства на .

Ключовият ред се определя от минималното съотношение на свободните членове и членовете на водещата колона (симплексни отношения):

В пресечната точка на ключовата колона и ключовия ред намираме разрешаващия елемент, т.е. 7.

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

В новата таблица на мястото на разрешаващия елемент записваме 1, всички останали елементи от ключовата колона са нули. Ключовите низови елементи са разделени на активиращия елемент. Всички останали елементи на таблицата се изчисляват по правилото на правоъгълника.

Получаваме таблицата на 1-ва итерация:

Ключовата колона за 1-ва итерация съответства на .

Намираме ключовия ред, за това дефинираме:

В пресечната точка на ключовата колона и ключовия ред намираме разрешаващия елемент, т.е. 31/7.

Векторът се извлича от основата и се въвежда векторът.

Получаваме таблицата на 2-ра итерация:

В индексния ред всички термини са неотрицателни, така че се получава следното решение на проблема с линейното програмиране (изписваме го от колоната със свободни термини):

По този начин е необходимо да се продадат 7,1 хиляди рубли. стоки от 1-ви вид и 45,2 хиляди рубли. стоки от 3-ти вид. Не е изгодно да се продава продукт от 2-ри тип. В този случай печалбата ще бъде максимална и ще възлиза на 237,4 хиляди рубли. При изпълнение на оптималния план оставащият ресурс от 3-ти тип ще бъде 701 единици.

Проблем с двойно LP

Нека напишем модел на двойствения проблем.

За да създадете двоен проблем, трябва да използвате следните правила:

1) ако пряката задача е решена максимално, тогава двойната задача е решена до минимум и обратно;

2) в проблема с максимума ограниченията на неравенството имат значение ≤, а в проблема с минимизиране имат значение ≥;

3) всяко ограничение на директния проблем съответства на променлива на двойния проблем и обратно, всяко ограничение на двойния проблем съответства на променлива на директния проблем;

4) матрицата на системата от ограничения на двойствения проблем се получава от матрицата на системата от ограничения на първоначалния проблем чрез транспониране;

5) свободните членове на системата от ограничения на директния проблем са коефициенти на съответните променливи на целевата функция на двойния проблем и обратно;

6) ако е наложено условие за неотрицателност на променливата на директния проблем, тогава съответното ограничение на двойния проблем се записва като ограничение за неравенство, ако не, тогава като ограничение за равенство;

7) ако някое ограничение на директния проблем е записано като равенство, тогава условието за неотрицателност не се налага на съответната променлива на двойния проблем.

Транспонираме матрицата на първоначалния проблем:

Нека сведем проблема до каноничен вид. Нека въведем допълнителни променливи. Въвеждаме всички допълнителни променливи в целевата функция с коефициент, равен на нула. Добавяме допълнителни променливи към левите страни на ограниченията, които нямат предпочитана форма, и получаваме равенства.

Решение на двойната LP задача

Съответствие между променливите на първоначалния и двойния проблем:

Въз основа на симплексната таблица беше получено следното решение на проблема с двойното линейно програмиране (записваме го от долния ред):

По този начин ресурсът от първия тип е най-дефицитен. Резултатът му е максимален и равен на . Ресурсът от третия тип е излишен - неговата двойна стойност е нула. Всяка допълнителна продадена единица стоки от 2-ра група ще намали оптималната печалба с
Разгледан е графичен метод за решаване на задача с линейно програмиране (LPP) с две променливи. Дава се примерна задача подробно описаниеконструиране на чертеж и намиране на решение.

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

Вземане на решения в условията на несигурност
Разглежда се решението на статистическа матрична игра при условия на несигурност, като се използват критериите на Валд, Савидж, Хървиц, Лаплас и Байс. Използвайки примерен проблем, е показано подробно изграждането на матрица за плащане и матрица на риска.

Необходимо е да се реши задача на линейно програмиране.

Целева функция:

2x 1 +5x 2 +3x 3 +8x 4 →мин

Ограничителни условия:

3x 1 +6x 2 -4x 3 +x 4 ≤12
4x 1 -13x 2 +10x 3 +5x 4 ≥6
3x 1 +7x 2 +x 3 ≥1

Нека приведем системата от ограничения в канонична форма; за това е необходимо да преминем от неравенства към равенства, с добавяне на допълнителни променливи.

Тъй като нашият проблем е проблем за минимизиране, трябва да го трансформираме в проблем за максимално търсене. За да направите това, променяме знаците на коефициентите на целевата функция на противоположните. Записваме елементите на първото неравенство непроменени, като добавяме допълнителна променлива x 5 и променяме знака „≤“ на „=". Тъй като второто и третото неравенство имат знаци „≥“, е необходимо да се обърнат знаците на техните коефициенти и да се въведат допълнителни променливи x 6 и x 7 съответно в тях. В резултат на това получаваме еквивалентен проблем:

3x 1 +6x 2 -4x 3 +x 4 +x 5 =12
-4x 1 +13x 2 -10x 3 -5x 4 +x 6 =-6
-3x 1 -7x 2 -x 3 +x 7 =-1

Пристъпваме към формирането на началната симплексна таблица. Ред F на таблицата съдържа коефициентите на целевата функция с противоположен знак.

Тъй като в колоната със свободни членове няма отрицателни елементи, е намерено допустимо решение, което съдържа отрицателни елементи, което означава, че полученото решение не е оптимално. Нека дефинираме водещата колона. За да направим това, ще намерим в ред F отрицателния елемент с максимален модул - това е -1,988 Водещият ред ще бъде този, за който отношението на свободния член към съответния елемент на водещата колона е минимално. Водещият ред е X2, а водещият елемент е: 0,313.

Тъй като в низа F няма отрицателни елементи, открихме оптимално решение. Тъй като първоначалната задача беше да се намери минимумът, оптималното решение ще бъде свободният член на низа F, взет с обратен знак. F=1,924
с променливи стойности равни: x 3 =0,539, x 1 =0,153. Променливите x 2 и x 4 не са включени в основата, така че x 2 =0 x 4 =0.

Ето ръчно (не аплетно) решение на две задачи, използвайки симплексния метод (подобен на аплетното решение) с подробни обяснения, за да разберете алгоритъма за решаване на проблеми, използвайки симплексния метод. Първата задача съдържа знаци за неравенство само „≤“ (задача с начална основа), втората може да съдържа знаци „≥“, „≤“ или „=“ (задача с изкуствена основа), те се решават по различен начин.

Симплексен метод, решаване на задача с начален базис

1)Симплексен методза задача с начална база (всички признаци на неравенство ограничения " ≤ ").

Нека напишем проблема канониченформа, т.е. пренаписваме ограниченията на неравенството под формата на равенства, добавяйки счетоводен баланспроменливи:

Тази система е система с базис (базис s 1, s 2, s 3, всеки от тях е включен само в едно уравнение на системата с коефициент 1), x 1 и x 2 са свободни променливи. Задачите, които се решават чрез симплексния метод, трябва да притежават следните две свойства: - системата от ограничения трябва да бъде система от уравнения с базис; -свободните членове на всички уравнения в системата трябва да са неотрицателни.

Получената система е система с база и нейните свободни условия са неотрицателни, така че можем да приложим симплекс метод. Нека създадем първата симплексна таблица (итерация 0), за да решим проблема симплекс метод, т.е. таблица с коефициенти на целевата функция и система от уравнения за съответните променливи. Тук „BP“ означава колоната от основни променливи, „Разтвор“ означава колоната от дясната страна на уравненията на системата. Решението не е оптимално, т.к има отрицателни коефициенти в z-реда.

симплекс метод итерация 0

За да подобрим решението, нека преминем към следващата итерация симплекс метод, получаваме следната симплексна таблица. За да направите това, трябва да изберете активиране на колона, т.е. променлива, която ще бъде включена в основата при следващата итерация на симплексния метод. Избира се по най-големия абсолютен отрицателен коефициент в z-реда (в максималния проблем) - в началната итерация на симплексния метод това е колона x 2 (коефициент -6).

След това изберете активиране на низ, т.е. променлива, която ще напусне основата при следващата итерация на симплексния метод. Избира се чрез най-малкото съотношение на колоната „Решение“ към съответните положителни елементи на колоната за разделяне (колона „Съотношение“) - в първоначалната итерация това е ред s 3 (коефициент 20).

Разрешителен елементе в пресечната точка на разделящата колона и разрешаващия ред, нейната клетка е маркирана в цвят, тя е равна на 1. Следователно, при следващата итерация на симплексния метод, променливата x 2 ще замени s 1 в основата. Обърнете внимание, че връзката не се търси в z-низ; там се поставя тире „-“. Ако има еднакви минимални отношения, тогава се избира всяка от тях. Ако всички коефициенти в разделителната колона са по-малки или равни на 0, тогава решението на проблема е безкрайно.

Нека попълним следната таблица „Итерация 1“. Ще го получим от таблицата „Итерация 0“. Целта на по-нататъшните трансформации е колоната с разделителна способност x2 да се превърне в колона с единица (с единица вместо разделителния елемент и нули вместо останалите елементи).

1) Изчислете ред x 2 от таблицата „Итерация 1“. Първо, разделяме всички членове на разрешаващия ред s 3 на таблицата „Итерация 0“ на разделящия елемент (той е равен на 1 в този случай) на тази таблица, получаваме ред x 2 в таблицата „Итерация 1“ . защото разрешаващият елемент в този случай е равен на 1, тогава ред s 3 от таблицата „Итерация 0“ ще съвпадне с ред x 2 от таблицата „Итерация 1“. Ред x 2 от таблицата от Итерация 1 получихме 0 1 0 0 1 20, останалите редове от таблицата от Итерация 1 ще бъдат получени от този ред и редовете от таблицата от Итерация 0, както следва:

2) Изчисляване на z-реда на таблицата „Итерация 1“. На мястото на -6 в първия ред (z-ред) в колоната x2 на таблицата Итерация 0 трябва да има 0 в първия ред на таблицата Итерация 1. За да направите това, умножете всички елементи на реда x 2 на таблицата "Итерация 1" 0 1 0 0 1 20 по 6, получаваме 0 6 0 0 6 120 и добавете този ред с първия ред (z - ред) на таблицата "Итерация 0" -4 -6 0 0 0 0, получаваме -4 0 0 0 6 120. В колоната x 2 се появява нула 0, целта е постигната. Елементите на колоната за разделителна способност x 2 са маркирани в червено.

3) Изчисляване на ред s 1 от таблицата „Итерация 1“. На мястото на 1 в s 1 ред на таблицата „Итерация 0“ трябва да има 0 в таблицата „Итерация 1“. За да направите това, умножете всички елементи на ред x 2 от таблицата "Итерация 1" 0 1 0 0 1 20 по -1, получете 0 -1 0 0 -1 -20 и добавете този ред с s 1 - ред на таблица "Iteration 0" 2 1 1 0 0 64, получаваме реда 2 0 1 0 -1 44. В колоната x 2 получаваме необходимата 0.

4) Изчислете ред s 2 от таблицата „Итерация 1“. На място 3 в s 2 ред на таблицата "Итерация 0" трябва да има 0 в таблицата "Итерация 1". За да направите това, умножете всички елементи на ред x 2 от таблицата "Итерация 1" 0 1 0 0 1 20 по -3, получаваме 0 -3 0 0 -3 -60 и добавете този ред с s 1 - ред от таблицата "Iteration 0" 1 3 0 1 0 72, получаваме реда 1 0 0 1 -3 12. В колоната x 2 се получава необходимата колона 0 в таблицата "Iteration 1". единица, тя съдържа една 1, а останалите 0.

Редовете на таблицата „Итерация 1” се получават по следното правило:

Нов ред = Стар ред – (Коефициент на разделителна способност на стария ред)*(Нов ред на разделителна способност).

Например за z-низ имаме:

Стар z-низ (-4 -6 0 0 0 0) -(-6)*Нов разрешаващ низ -(0 -6 0 0 -6 -120) =Нов z-низ (-4 0 0 0 6 120).

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

симплекс метод итерация 1

Резолвираща колона x 1, разрешаващ ред s 2, s 2 излиза от основата, x 1 влиза в основата. По абсолютно същия начин получаваме останалите симплексни таблици, докато получим таблица с всички положителни коефициенти в z-реда. Това е знак за оптимална маса.

симплекс метод итерация 2

Резолвираща колона s 3, разрешаваща ред s 1, s 1 напуска основата, s 3 влиза в основата.

симплекс метод итерация 3

В z-реда всички коефициенти са неотрицателни, следователно се получава оптималното решение x 1 = 24, x 2 = 16, z max = 192.

11.4. ДВОЙЕН СИМПЛЕКСЕН МЕТОД

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

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

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

Като се има предвид това условие, като се вземе предвид двойствеността, можем да напишем

.

По този начин, ако, това . Това означава, че когато решението на прекия проблем е неоптимално, решението на двойния проблем не е възможно. От другата страна при . От това следва, че оптималното решение на пряката задача съответства на допустимо решение на двойствената задача.

Това направи възможно разработването на нов метод за решаване на проблеми с линейното програмиране, който първо произвежда неприемливо, но „по-добро от оптималното“ решение (в обичайния симплексен метод първо се намира приемливо, Но неоптималенрешение). Нов метод, наречена двоен симплексен метод, осигурява изпълнението на условията за оптималност на решението и неговото систематично „приближаване” до областта на допустимите решения. Когато полученото решение се окаже осъществимо, итеративният процес на изчисления завършва, тъй като това решение също е оптимално.

Двойният симплексен метод дава възможност за решаване на проблеми с линейно програмиране, чиито системи с ограничения, с положителна основа, съдържат свободни членове с произволен знак. Този метод ви позволява да намалите броя на трансформациите на системата за ограничения, както и размера на симплексната таблица. Нека разгледаме приложението на двойния симплекс метод, използвайки пример.

Пример. Намерете минимума на функция

под ограничения

.

Да преминем към каноничната форма:

под ограничения

Първоначалната симплексна таблица има формата

Първоначален основен разтвороптимално, но не и приемливо.

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

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

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

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

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

Включената променлива е избрана х 2. Последващото преобразуване на низ води до нова симплексна таблица:

Ново решение също оптимално, но все пак неприемливо. Като нова изключена променлива избираме (произволно) х 3. Нека дефинираме променливата, която да бъде включена.