Оптималност състояние програма за подкрепа - studopediya
Таблица оглед ZLP. Симплекс - маса.
ZLP метод симплекс РЕШЕНИЯ
3.1. Обща характеристика и основни етапи на симплекс метод -
Основателите на симплекс метода е съветски математик LV Канторович и американският математик Джон. Данциг.
симплекс метода може да се използва за решаване на всеки ZLP или откриване го нерешим. Много специални ZLP класове могат да бъдат решени от други, по-ефективни методи за тези класове. Въпреки това, в полза на симплекс метода - неговата универсалност. Почти всички компютърни програми са предназначени за стандартни решения ZLP симплекс - метод.
Ние описваме обща представа за симплекс метода.
Ние вярваме, че ZLP записано в канонична форма и целевата функция да бъдат сведени до минимум. Както вече знаете, трябва да се потърси сред ZLP на програми за подпомагане на оптималния план. Методът на симплекс не поддържа през всички планове (което би често не е възможно поради големия им брой), а като се започне от някои първоначални програма за подкрепа, той постоянно се прехвърлят към други програми за подпомагане с намаление на целевата функция. Симплекс метод спира да работи, ако някой е установено, че оптималната програма за подкрепа или да зададете неразтворимост на проблема.
По метода на решение ZLP симплекс следните етапи:
1) привеждане ZLP в канонична форма;
2) привеждане на системата за линейни уравнения до Йордания форма с неотрицателни дясната страна с едновременна проверка на ZLP неразрешимост, поради несъответствие на системата от линейни ограничения;
3) изучаване на програмата за подкрепа за оптималност;
4) Изследване на ZLP неразрешим поради безграничност дъното на SDT на обективната функция;
5) Преходът към нов, "по-добре", програма за подкрепа.
С цел намаляване и рационализиране на записите на метода на решение ZLP симплекс използва т.нар симплекс таблица. За да използвате таблицата на симплекс ZLP трябва да се въвеждат, за да изгледа на маса. Ето как.
Нека ZLP написани на каноничната форма (2.3-2.5). За да събере ZLP, отнасящи се до системата на маса (2.4), трябва първо да предизвика Йордания форма с неотрицателни правилните страни. Да предположим, че формата Jordan има формата (2.6). Ние изразяваме (2.6) чрез безплатни основни променливи:
Заместването в обективната функция (2.3), вместо на основните променливи, експресията чрез свободни променливи от формули (3.1), като по този начин изключва от обективната функция основни променливи. Обективната функция под формата:
В табличен вид целевата функция е написано, както следва:
Обърнете внимание на следното функции ZLP табличен вид:
а) системата на линейни уравнения се дава на Jordan форма с неотрицателни дясната страна;
б) от целевата функция на основните променливи са изключени и е писано във формата (3.3).
Сега е ред на описанието на масата за симплекс. Нека ZLP записано в табличен вид:
Тогава попълнено симплекс таблица изглежда така.
Референтен ZPL план :. Тя се нарича програма за подкрепа, съответстваща на тази таблица симплекс. Както се вижда от формула (3.2), стойността на обективната функция с референтната равнина е равен на # 947; 0.
Помислете за пример. Довежда се до масата да кажа следното и попълнете таблица ZLP симплекс:
Първоначално ZLP трябва да бъдат доведени до канонична форма. За тази функция fnuzhno заменя със - е:
Системата от уравнения трябва да бъде написана под формата Йордания с неотрицателни правилните страни. Като цяло рецепция, чрез които се постига това ще се счита за по-късно (виж точка 3.7). В нашия пример, тази форма Йордания вече е променлива и основно. Ние премахване на основните променливи на целевата функция - ф. За тази цел, ние ги изразят чрез свободни и да замени тези изрази в обективната функция.
вижте Таблица ZLP следва:
Напълнете симплекс таблица (за записи намаляване първата колона е със заглавие "В", последната колона - "Q").
Стойността на целевата функция на базовата равнина и съответната таблица симплекс е 6. Пишем целевата функция в таблична форма, къде. Тъй като за всяко допустимо решение ZLP променливи са само неотрицателни стойности на последния запис на целевата функция може да се види, че нейната стойност във всяка точка на тунела за вторично разреждане не е по-малко от 6. Следователно, минималната стойност на целевата функция на SDT е 6, а това се постига при референтната равнина, съответстваща симплекс таблица.
3.4. Състояние unsolvability ZLP поради безграничност дъното на тунела за вторично разреждане на целевата функция.
Ако маса ZLP симплекс е пълен, тунела за вторично разреждане не е празна задача, така че програмата за подкрепа, съответстваща на масата за симплекс принадлежи SDT. Въпреки ZLP може да бъде неразтворим поради SDT е неограничена долу целевата функция.
Условието е формулиран като undecidability.
Ако масата за симплекс съдържа поне една колона, която е различна от крайната десница, чието дъно линия е на стойност положително число, както и всички други линии на колоната - неположителна номер, ZLP нерешим дължи на SDT е неограничено под целевата функция.
За да използвате отново Например проучването.
Колоната в най-долния ред съдържа положително число, а в останалите редове - nonpositive номер. Нека докажем undecidability ZLP.
Пишем Йордания форма, съответстваща симплекс маса и прехвърляне на условията, съдържащи, от дясната страна. получаваме
Нека един - всяко положително число. Очевидно е, че ZLP има следната осъществимо решение :. Ние се изчисли стойността на целевата функция в осъществимо решение същото време. От таблица 3.4, ние имаме:
. Когато е посочено възможно решение е = 4 - 2а. От това, което виждаме, че стойността на целевата функция може да бъде произволно малък за достатъчно голям. С други думи, целта функция не е ограничена по-долу на S & DT. Следователно ZLP неразрешим.
3.5. Преходът към новата програма за подкрепа.
Да предположим, че условията за оптималност и undecidability не са изпълнени. Тогава симплекс метода се премества в нова програма за подкрепа. Този преход се дължи на отстраняване от основата на един от основните променливи и въвеждането в основата на един от най-свободните променливи. трябва да бъдат изпълнени следните две условия:
1) нова база все още трябва да бъдат валидни, т.е. прав отговаря на формата Йордания все още трябва да бъде не-отрицателни;
2), когато една нова референтна стойност на целевата функция на условията на не трябва да надвишава предишната си стойност при базовата равнина.
маса Колона симплекс, в която има променлива въвежда в основата, наречен обща колона. Низ, в която има променлива изход от основата, която се нарича обща линия. Елементът в пресечната точка на обща линия и обща колона, наречена Обща елемент.
Общо правило за избор на елемент.
Положителното число обозначава като общо колона изберете някоя колона на таблицата с симплекс е различна от крайната десница, която има по-долния ред. само редовете на таблица симплекс след това се счита за важно от дъното, в която в пресечната точка с обща колона са положителни числа. Стоейки в господар за всяка колона на тези линии се изчислява постоянно термин, свързан с елемента. String, което е съотношението на минималната е избран като общото. Елемент в пресечната точка на общия ред и общото колоната и ще общ елемент.
Нека илюстрираме това правило, като например.
Както можете да изберете една колона или колона като общо колона. Ние избираме (най-често избират колоната, в която на дъното на голям положително число). Сега ние се пристъпи към избора на обща линия. За това ние считаме, две линии - и. Е съотношение 4: 2 и 8: 3. Също толкова важно е съотношението на 4: 2, така че ние да избере първия ред като цяло. Следователно, общото елемент е 2 - е в пресечната точка на колона и ред.
След като изберете General елемента, който трябва да отидете на нова програма за подкрепа, в което променливата е основното и променлива X1 - безплатно. Коефициентът на новата форма Jordan трябва да бъде равно на 1. Следователно, първият ред на Таблица 3.5 е разделена от две и след това се умножава получената първия ред в (3) и добавяне на втора линия, изключат от второто уравнение. По подобен начин, като се използва Jordan правило процедура и от третата уравнението на обективната функция (последното изисква табличен изглед ZLP).
В резултат на това, ние получаваме следната таблица.