Двойното проблема за стандартни задачи - studopediya

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

Да разгледаме проблема с избора на оптимална производствена програма. Нека броят на фирмата 1 има запаси от материални ресурси и суровини в дву на обеми (), където m - брой видове ресурси. Както и преди, ние приемаме, че Aij - е количеството материал и суровини на формата и. необходими за производството на една единица продукция тип J, CJ - печалба от емитиране и продажба на дялове на продуктов тип J на ​​().

Освен това, ние приемаме, че номерът на дружеството 2 решили да си купите всички съществени и суровинни ресурси в номера на предприятието 1 по някои от най-добрите цени на тези ресурси, които са обозначени с y1. ¼, YM. Естествено, номер 2, компанията се интересува от факта, че разходите за закупуване на материали и суровини материални ресурси са минимални, т.е.

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

За да се произведе единица продукция на тип 1 А11, консумирани ресурси от първия вид, a21 ресурс от втори тип, ¼, AI1 -тата вид ресурс. Ето защо, за да се отговори на изискванията на продавача (фирма номер 1), цената на ресурсите, използвани за производство на единица продукция от първия тип, не трябва да бъде по-малко от цената му С1. С други думи, необходимо е да се задоволи неравенството в следния вид:

По същия начин, може да се въведе ограничения за всички други видове продукти, 2, 3, ¼, п. Икономическо-математически модел и смислено тълкуване на начина, по който проблемът е представен в дясната част на таблицата. 6.1.

Baseline (пряко) на проблема (I)

Двойното проблема (II)

(6.1) в ограниченията (6.2) и състоянието на не-негативизъм (6.3), за да изход план. , на което приходите (приходи) от продажби на продукция е максимумът, при условие, че консумацията на ресурсите на всеки продукт трябва да надвишава наличните резерви

(6.4) при ограниченията (6.5) и състоянието на не-негативност (6.6), за да намерите набор от цените ресурси. където общата стойност на средствата ще бъде минимално, при условие че стойността на ресурсите при производството на всеки продукт ще бъде не по-малко от печалбата (приходи) от продажби на продукция

цени y1 ресурс. ¼, YM в икономическата литература сме получили различни имена: регистрация, имплицитно, сянка. Значението на имената им е, че за разлика от цената на получения продукт, който може да се прогнозира доста точно, цените y1 ресурси. ¼, YM са вътрешни, тъй като те не са дефинирани от външната страна, но се определят от решаването на проблема, така че те често се наричат ​​разчети на средствата.

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

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

2. коефициентите на променливите на целевата функция в първата задача са правилните части в системата от ограничения във втория проблема.

3. Всяка една от задачите, определени в стандартната форма, проблема за максимизиране на всички неравенства от вида "е по-малка или равна на", както и на проблема с минимизиране на всички видове неравенство "е по-голяма или равна на."

4. Матрицата коефициентите на променливите в ограниченията на двете задачи системи са транспонирани един до друг.

5. Броят на неравенството по отношение на ограниченията на системата за проблем съвпада с броя на променливите в различна задача.

6. Състояние без негативизъм от наличните в двете проблеми променливи.

Задачи (I и II) на линейното програмиране, като посочените по-горе характеристики, nazyvayutsyasimmetrichnymi vzaimodvoystvennymi задачи. На следващо място, ние ще ги наричаме двоен проблем. Проблемът (I) се нарича още оригинала или насочи чифт двойни проблеми. Въз основа на характеристиките, описани двойна задачи могат да бъдат формулирани обикновено след образуването на двойна проблема.

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

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

3. Форма матрица А1 ¢, транспозицията на матрица А1.

4. За да се образува двойна проблема въз основа на получената матрица А1 ¢ nonnegativeness условия и променливи.

Пример за образуването на двойна проблема. Нека оригинал или директно проблем на линейното програмиране (PZLP) е да се определи максимума на целевата функция

1. Тъй като първоначалният проблем при максимална, а след това двете страни на първи и четвърти неравенство, с което се умножава по (-1). получаваме:

2. Ние се образува разширената матрица на системата:

3. Намерете матрица A1 ¢, транспозицията на матрица А1: