Знайте, Intuit, лекция, а ина задача без ограничение двойственост

Анотация: Разглеждат лекции с теорията за двойственост за GP задачи без никакви ограничения. Като се има предвид формулировката на основния двойственост теорема. Той въвежда концепцията за степента на трудност на личния лекар на задачите. Има изявление на двойния проблем от гледна точка на основните променливи. За проблеми с степента на сложност на SE 0 и 1 са показани в примерите, може да се използва като двоен проблем за решаването им.

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

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

Помислете определението в "Task личния лекар без ограничения" задача GP без ограничение:

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

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

Пример 27Dokazhem използва дуалността теорема, че следния проблем GP не е оптимално решение:

Ние първо определи двойна функция pozinoma използване формула (33). Posin се състои от три едночлени, следователно, има двойна функция на три променливи. Vector pozinoma коефициенти. Ето защо, с двойна функция за pozinoma е:

Сега напиши състояние pozinoma ортогоналност за (формула (34)). Тъй Posin включва две променливи, условията на ортогоналност състоят от две уравнения. Matrix експоненциална pozinoma

където та колона се формира от експонентата на променливата Ith. С формула (34), състоянието на ортогоналност за pozinoma имат формата:

Системата на линейни уравнения (41) има уникален разтвор: ,,, които не отговарят състояние (36). Това означава, че няма осъществимо решение за двойна проблема. Следователно, не съществува и оптималното решение на този проблем. От двойственост теорема означава, че в този случай директно проблем личния лекар не е оптимално решение.

Пример 28Reshim SE следния проблем използване дуалността теорема:

Най-напред се определят двойна функция за pozinoma. Posin се състои от три едночлени, следователно, има двойна функция на три променливи. Vector pozinoma коефициенти. Ето защо, с двойна функция за pozinoma е:

Сега пиша условията на ортогоналност за pozinoma. Тъй Posin включва две променливи, условията на ортогоналност състоят от две уравнения. Matrix експоненциална pozinoma

където та колона се формира от експонентата на променливата Ith. С формула (34), състоянието на ортогоналност за pozinoma имат формата:

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

Чрез двойственост теорема

Dual променлива посочи какъв е приноса на мономен в минималната стойност на целевата функция. Следователно приносът на първия мономен в целевата функция е приносът на втората - докато приносът на третия -.

Остава да се определи оптималното решение на първичното проблема. Ние сме с помощта на формулата (39) от двойственост теорема. Задължително за решаване на нелинейни система от три уравнения с две неизвестни:

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

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