НЕФИНАЛНА ВЕРСИЯ - PDF безплатно изтегляне
Най-важният от всички проблеми е изборът на променливи. Сега ще присвоим нашите променливи на храните и стойността на променливата ще бъде количеството храна, което трябва да се консумира (на части). Отбележете x 1 броя порции овесени ядки за ядене, x 2 пилешкото, x 3 яйцата, x 4 млякото, x 5 черешовия пай, x 6 броя порции със свински боб! Диетата трябва да отговаря на следните условия: Доза/ден по лимит Дневно изискване 0 x 1 4 0 x 2 3 0 x 3 2 0 x 4 8 0 x 5 2 0 x 6 2 110x 1 + 205x 2 + 160x 3 + 160x 4 + 420x 5 + 260x 6 2000 4x 1 + 32x 2 + 13x 3 + 8x 4 + 4x 5 + 14x 6 55 2x 1 + 12x 2 + 54x 3 + 285x 4 + 22x 5 + 80x 6 800 Тук взехме предвид, че не трябва да консумираме отрицателно количество или твърде много храна, или сме обобщили хранителната стойност в тях. И накрая, цената на диетата може да бъде изразена чрез въведените променливи и дадени константи: 3x 1 + 24x 2 + 13x 3 + 9x 4 + 20x 5 + 19x 6 След това математическото описание на диетичния проблем е както следва: min 3x 1 + 24x 2 + 13x 3 + 9x 4 + 20x 5 + 19x 6 110x 1 + 205x 2 + 160x 3 + 160x 4 + 420x 5 + 260x 6 2000 4x 1 + 32x 2 + 13x 3 + 8x 4 + 4x 5 + 14x 6 55 2x 1 + 12x 2 + 54x 3 + 285x 4 + 22x 5 + 80x 6 800 x 1 4 x 2 3 x 3 2 x 4 8 x 5 2 x 6 2 x 1, x 2, x 3, x 4, x 5, x 6 0 3
2.2. Двойственост Обмислете следния стандартен LP! макс. 4x 1 + x 2 + 5x 3 + 3x 4 x 1 x 2 x 3 + 3x 4 1 (1) 5x 1 + x 2 + 3x 3 + 8x 4 55 (2) x 1 + 2x 2 + 3x 3 5x 4 3 (3) x 1, x 2, x 3, x 4 0 Вместо да решавате задачата, дайте горна оценка за стойността на z на целевата функция. Умножавайки неравенството (2) по 5/3, се получава горна граница на z. 5 3 (5x 1 + x 2 + 3x 3 + 8x 4 55) 4x 1 + x 2 + 5x 3 + 3x 4 25 3 x 1 + 5 3 x 2 + 5x 3 + 40 3 x 4 275 3 z 275 3 A (2) + (3) дава дясна горна граница: 5x 1 + x 2 + 3x 3 + 8x 4 55 x 1 + 2x 2 + 3x 3 5x 4 3 4x 1 + 3x 2 + 6x 3 + 3x 4 58 4x 1 + x 2 + 5x 3 + 3x 4 4x 1 + 3x 2 + 6x 3 + 3x 4 58 z 58 Продължавайки идеята, вземете неотрицателната линейна комбинация от неравенства, т.е. умножете първата по y 1, а втората по y 2, третият с y 3, след което ги съберете! (Очевидно е, че крайното неравенство е вярно, ако y 1, y 2, y 3 е неотрицателно.) (Y 1 + 5y 2 y 3) x 1 + (y 1 + y 2 + 2y 3) x 2 + (y 1 + 3y 2 + 3y 3) x 3 + + (3y 1 + 8y 2 5y 3) x 4 y 1 + 55y 2 + 3y 3 4
Ако са изпълнени следните условия, тогава y 1 + 55y 2 + 3y 3 дава горна граница на стойността на целевата функция: Ако горното е изпълнено, получаваме: y 1 + 5y 2 y 3 4 y 1 + y 2 + 2y 3 1 y 1 + 3y 2 3y 3 5 3y 1 + 8y 2 5y 3 3 4x 1 + x 2 + 5x 3 + 3x 4 y 1 + 55y 2 + 3y 3 zy 1 + 55y 2 + 3y 3: min y 1 + 55y 2 + y 3 y 1 + 5y 2 y 3 4 y 1 + y 2 + 2y 3 1 y 1 + 3y 2 3y 3 5 3y 1 + 8y 2 5y 3 3 y 1, y 2, y 3 0 The оригиналният проблем е първичен и полученият по-горе се нарича двойна или двойна задача. LP в стандартна форма и нейния дуал като цяло: Primary Dual max c j x j j = 1 min m b i y i a ij x j b i i = 1. m j = 1 m a ij y i c j j = 1. n x j 0 j = 1. n y i 0 i = 1. m 1. Теорема. (Слаба двойственост) Ако (x 1. x n) е възможно решение на основния проблем и (y 1. y m) е възможно решение на дуалния проблем, тогава m c j x j b i y i j = 1 5
Доказателство. Очевидно е от конструкцията на дуалния проблем. Формално: (m) mmcjxja ij yixj = a ij xjyibiyi, j = 1 j = 1 j = 1, тъй като днес ij yicj, xj 0 (j = 1. n) и nj = 1 е ij xjbi, yi 0 (i = 1 м). Преди да заявим и докажем т.нар. силна теорема за двойствеността, помислете за последния речник на LP задача. Може да се забележи следната много изненадваща характеристика: Решението на дуалния проблем може да се прочете от последния речник на оригиналния проблем. Ако първоначалното решение беше оптимално, така да бъде. Например, ако последният речник на основния проблем е: x 2 = 14 2x 1 4x 3 5x 5 3x 7 x 4 = 5 x 1 x 3 2x 5 x 7 x 6 = 1 + 5x 1 + 9x 3 + 21x 5 + 11x 7 z = 29 x 1 2x 3-11 x 5 + 0 x 6-6 x 7 x 5 y 1 y 1 = 11 x 6 y 2 y 2 = 0 x 7 y 3 y 3 = 6 Съответствието: двойно променливи в някакъв смисъл могат да бъдат присвоени на изкуствените променливи на оригиналния LP. Стойността на двойните променливи е точно 1 пъти коефициентите на моментната целева функция на изкуствените променливи. Това скоро доказано свойство е изключително полезно както за доказване на теоремата за двойствеността, така и за решаване на практически задачи. Теорема 2. (Силна двойственост) Ако основният проблем има оптимално решение (x 1. x n), тогава двойният проблем има оптимално решение (y 1. y m), за което m c j x j = b i yi j = 1 6
Доказателство. Поради видяната по-рано теорема за слабата двойственост е достатъчно да се намери възможно решение (y1, y 2. y n) за двойствената задача, за която се изпълнява уравнението nj = 1 c j x j = m b i yi. При решаването на основния проблем въвеждаме изкуствените променливи x n + i = b i a ij x j (i = 1. m) j = 1. Да предположим, че сме достигнали последния речник: n + mz = z + ckxkk = 1 ck 0, (k = 1. n + m), z = cjxjj = 1 Както споменахме, опитайте yi = c n + i (i = 1. m ) заместване! Ние твърдим, че това е възможно решение на дуала, въпрос е само на други точки. x n + i < >> < m z = c j x j = z + c j x j yi b i a ij x j j=1 j=1 j=1 ( ) ( ) m m c j x j = z b i yi + c j + a ij yi x j j=1 j=1 Ezt az egyenlőséget egyszerű algebrai manipulációval kaptuk az előzőből, azaz minden x 1, x 2. x n értékre igaznak kell lennie. Ebből adódnak a m z = b i yi, m c j = c j + a ij yi egyenlőségek. Mivel c k 0 minden k = 1. n + m esetén, így m a ij yi c j (j = 1. n) yi 0 (i = 1. m) 7