Велика енциклопедия на нефт и газ

Двойният симплекс метод

Методът на двойния симплекс променя само реда, в който се намира разделителният елемент; следователно всички характеристики (несъвместимост на системата, неограниченост на функционалността) тук имат същите характеристики като при обикновения симплекс метод. Нека анализираме само преодоляването на дегенерацията, тъй като тя се причинява от нула сред коефициентите на z - реда, а не сред свободните членове. [един]

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

Двойният симплекс метод, подобно на симплекс метода, се използва за намиране на решение на задача за линейно програмиране, написана под формата на основен проблем, за който сред векторите P /, съставени от коефициентите на неизвестни в системата на уравненията, има са m единица единици. [3]

Удобно е да се решават задачи за цялостно програмиране чрез метода на двойния симплекс с използване на модифицирани изключения (вж. Гл. [4]

По метода на двойния симплекс той се получава не в три стъпки, а в две. [пет]

Използвайки метода на двойния симплекс, се намира решение на проблема в резултат на добавянето на допълнително ограничение. [6]

Използвайки метода на двойния симплекс, се намира решение на проблема, произтичащ от проблем (32) - (34) чрез добавяне на допълнително ограничение. [7]

Съществува и двоен симплекс метод, който е предназначен за решаване на проблеми с голям брой ограничения или проблеми, при които броят на ограниченията се увеличава. Освен това има методи за решаване на проблеми с променливи параметри, когато не са задължително добавени само редове или само колони. [8]

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

Използването на метода на двойния симплекс за решаване на линейно програмиране е еквивалентно на използването на обичайния симплекс метод за решаване на съответния двоен проблем. [десет]

Ще използваме стандартния двоен симплекс метод, за да решим задачата за максимизиране и да получим желаната система от оптимални цени. [единадесет]

При метода на двойния симплекс задачата се решава в следната последователност: първо се постига неотрицателността на коефициентите z - низове, а след това се постига неотрицателността на свободните членове. Необходимо е да се обоснове правило за избор на разрешаващ елемент за такава поръчка. [12]

Ако се използва методът на двойния симплекс, тогава, имайки двойно допустимо y, трябва да получим неравенство, което токът y не удовлетворява. По този начин изчислението се състои от две части. Втората част са спомагателните изчисления на (генерираните) неравенства, използвани в първата част. Ако използваме тока Y в графика H (G, m), y), можем да намерим най-краткия път от 0 до g0 с дължина yt Yo - Тогава неравенството yt To не е валидно. Това неравенство се добавя към неравенствата в първата част. Неравенството трябва да бъде променено, преди да бъде записано в края на двойната симплекс таблица. [13]

Проблемът се решава чрез двойния симплекс метод, последван от прилагането на метода Gomori23 за получаване на цяло число решение. [14]

След това методът на двойния симплекс се итерира, като се използва линия (10) като водеща. [петнадесет]