двойна Задачата на линейното програмиране

Тези задачи са следните свойства:

1. Директното проблема стреми максимума на обективната функция (линейна форма) и двоен проблем - най-малко.
2. Коефициентите на променливите в целевата функция на първичен проблем са свободни членове на двойна проблемни ограничения на системата. От друга страна, постоянните условия на границите на системата на пряка проблема - коефициентите на променливите в целевата функция на двойната проблема.
3. Във всяка задача системата на ограничения се дава под формата на неравенства, с всички от един и същи смисъл на думата, а именно, когато максимумът на целевата функция (пряко проблем) тези неравенства са написани с "по-малка или равна на", а когато минимума (двойна задача) - знакът "по-голямо или равно".
4. Коефициентите на променливите в системите на ограниченията, описани матрици
   
   и
   
   които са транспонирани една спрямо друга.
5. Броят на неравенството в системата ограничава прякото проблема съвпада с броя на променливите на двойна проблема.
6. Условия за не-негативност от променливите се съхраняват в права линия. и двойният проблема.

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

Водени сме да ги наричаме просто взаимно двойна проблеми.

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

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

1. Доведете всички неравенството в системата от ограничения на първоначалния проблем за неравенството в същия смисъл (тоест, с един и същ знак): Ако ви търсят за максимум целевата функция в оригиналната проблема (линейна форма) - те са написани с "по-малка или равна на", и ако най-малко - с "по-голямо или равно на" знак. За това неравенство, в които това изискване не е спазено, умножена по минус едно.
2. Изтощеният матричните коефициенти на променливите на първоначалния проблем, получен след трансформации, описани в предходния параграф, както и да представлява матрицата ", транспозицията на матрицата А.
3. Съставляват системни ограничения двоен проблем, като като коефициентите на променливите на елементите на матрицата ", а като свободни членове - коефициентите на променливите в целевата функция на първоначалния проблем и пишат противоположния смисъл на неравенството (т.е. знак на климата), в сравнение с неравенството, получена в етап 1.
4. Съставляват целевата функция (линейна форма) на двойния проблем чрез приемане на коефициентите на променливите на ограничение система оригиналната безпроблемна членове, получени в стъпка 1.
5. Посочва се, че е необходимо да се намери в разтвора на двойния проблем, а именно минимум на целевата функция, ако първоначалният проблем се търси максимално и максимално ако се търси минимума в оригиналната проблема.
6. Запишете състоянието на не-негативност от променливите на двойна проблема.

Пример 1: Създаване на задача, двойна, както следва: намери максималната функция под ограничения

Решение. На трето място, на оригиналния проблем неравенството на системата не отговаря на параграф 1 от изготвянето на двойното проблема. Ето защо, умножете го по отрицателен:

За да се улесни получаването на двойната Проблемът е добре да се използва разширена матрица Б. който заедно с коефициентите на променливите на оригиналните проблемни ограниченията на системата запише свободните условията и коефициентите на променливите в обективната функция, избор за тази цел допълнително колона (разделени линия) и линия (подчертано в червено) , Транспонира матрица B и с помощта на транспонирана матрица B ", е задачата на двоен източник. Матрици Б и В "имат формата

Така двойна задачата на линейното програмиране намалява намиране минимум на функция при ограничения

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

1. Безплатни членове в директен проблем - коефициентите на целевата функция в двойна проблема.
2. Коефициентите на целевата функция в директен проблем - свободни членове в двойна проблема.
3. Augmented матрица в директен проблем - транспонирана матрица удължен до двоен проблем.
4. к-ти непозната в проблема с директен дизайн за неотрицателно - к-ти неравенство в двойна проблема с "по-голямо или равно".
5. к-ти непозната в директен проблема без ограничение марка - к-ти ограничение в двойна проблема под формата на уравнение.
6. к-ти непозната в не-положителен директен проблем - к-ти неравенство в двойна проблема с "по-малко или равно на".
7. Аз ия неравенство в директен проблема с "по-малка или равна" - аз ия неизвестен в двойна проблемът не е отрицателен.
8. Аз ия ограничаване на пряката проблема под формата на уравнението - аз ия неизвестен в двойна проблема без ограничение знак.
9. Аз ия неравенство в директен проблема с "по-голямо или равно" - аз ия неизвестен в двойна проблемът с липсата на положителна.

Пример 2: Създаване на задача, двойна, както следва: намери минимум на функцията при ограничения

Решение. Както можете да видите, прякото Проблемът е написано в общи линии. Тя ще бъде взето предвид при поставянето на знаци по отношение на двойното проблема. И все пак, както в предишния пример, proizvedom универсален ефект - формира матрица B на пряката проблема и транспонирана матрица B "на двойния проблем:

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

Теорията на двойственост в линейното програмиране е изграден върху два основни теореми.

Теорема 1. За преките и двойни проблеми в силата на един и само един от следните твърдения. 1. Ако една от задачите на линейното програмиране има ограничен оптимално, след това си двойна задача също има ограничен оптимално, с оптимални стойности на линейни форми на двата проблема са еднакви, т.е.. ФЕ макс = Z мин iliF мин = Z макс. 2. Ако линейна форма на едната от проблемите не се ограничават до, условията на другите цели са противоречиви. 3. И двата проблема имат не е решение, тъй като ограниченията на системата са противоречиви.

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

При решаването метод симплекс на първоначалния проблем за информационната система на неравенство еквивалентна система от уравнения трябва да въведете допълнителна м неотрицателни променливи (броят на неравенство в системата на ограничения) х N + 1. х п + 2. х п + т. х п + m. където I = 1, 2. m е броят на неравенство, в която п + и е въведена допълнителна променлива х.

Системни ограничения двоен проблем се състои от неравенства н съдържащи м променливи. Ако се реши този проблем, като симплекс метода, е необходимо да се въведе н г м + 1 допълнителни неотрицателни променливи. г м + 2. г м + J. г м + н. където к = 1, 2. п е броя на системата на неравенство ограничения на двойната проблема, който беше въведен в допълнителна променлива г м + J.

Всички по-горе е дадена, за да се установи следното съответствие между променливите в оригиналните и двойни проблеми на линейното програмиране:

Това означава, че основните променливи на първоначалния проблем, по реда им, съответстват на допълнителна променлива на двойния проблем, също в реда, в който се появи. На свой ред, допълнителни променливи на първоначалния проблем, по реда им, съответстват на основните променливи на двойното проблема, в реда, в който се появи.

С други думи, всяка първоначална променлива х й първоначалната задача (к = 1, 2. п) е свързан допълнителен променлива г м + J. въведена в к ти неравенство двойна проблем, и всеки от допълнителна променлива х п + и на оригиналния проблема (I = 1, 2. т), въведена в неравенството I тата на оригиналния проблема, - оригиналния променливата у, двойна проблема.

Всички по-горе, както е отбелязано, ще бъде по-добре разбрано от Пример 2, който ще бъде малко след Теореми 2.

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

Теореми 1 и 2, че ако за решаване на един от най-взаимно двойно линейни програмни проблеми, т.е., за да намери своето оптимално решение и оптималното целевата функция, можем да пишем най-доброто решение и оптимални обективна функция други задачи. Сега, един пример, който ще постави всички по-горе по рафтовете на магазините.

Пример 3. Въз основа на преките решения и двойни проблеми на линейното програмиране на пример 1, за да се провери валидността на теореми 1 и 2.

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

Ние го направи двойна задача: да се намери минимума на функцията при ограничения

За решаването на проблема симплекс метод системата на ограничения-неравенства директно намалява до система от уравнения чрез въвеждане на допълнителни не-отрицателни променливи х 3. х 4. х 5. х 6:

Читателят може да се провери, решаване на проблема чрез симплекс метода. че тя има следните решения:

и максимума на обективната функция F макс = 13,

докато се обективната функция се изразява като

двойна система за проблем ограничение се свежда до система от уравнения чрез въвеждане на допълнителни променливи у 5. у 6:

Решението на метода на двойна проблем симплекс дава следния отговор:

и минимум на обективната функция Z = 13 мин

докато се обективната функция се изразява като

Определяне на два проблема, ние виждаме, че първата част на теорема 1: двойната проблема, също има ограничен оптимално, с Z мин = F макс = 13.

Нека да се уверите, че е така и Теорема 2. За да направите това, пишем на променливите на първичната и двоен проблем, спазвайки тяхната кореспонденция:

Както можете да видите, основните променливи на първоначалния проблем, по реда им, съответстват на допълнителна променлива на двойния проблем, също в реда, в който се появи. На свой ред, допълнителни променливи на първоначалния проблем, по реда им, съответстват на основните променливи на двойното проблема, в реда, в който се появи.

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

Като се има предвид коефициентите на променливите у J в целевата функция и като се вземе предвид тяхното съответствие с коефициентите на променливите х аз. Ние се получи разтвор (4; 1; 0; 5; 4; 0). съвпада с решаването на прякото проблема.

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

От Теорема 2, като се има предвид кореспонденция между променливите в първичните и двойни проблеми и предприемане на абсолютната стойност на коефициентите на променливите, намираме оптималното решение за двоен проблем (2/3, 0, 0, 7/3, 0, 0). Където Z мин = F макс = 13.

Пример 4. Уверете се, че системата ограничава директно проблема

и двоен проблем

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

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

Нека да погледнем отново на прав Задачата на линейното програмиране и двойния проблем там.

Директен проблем.
максимизиране функция