Задача на целочисленото линейно програмиране
Изтегляне 482.95 Kb.
|
|
и  звършва в съответствие с тестове.
Елементите на алгоритъма се разглеждат най-напред с пример. Пример 7.4. Да се максимизира W = 4х'1 + Зх'2 - 6х'3 - Зх'4 + 4х'5 при ограниченията 
Най-напред задачата се формулира като задача за минимизация на 
 =- 4х'1 + Зх'2 - 6х'3 - Зх'4 + 4х'5
и всички коефициенти се преобразуват в неотрицателни стойности, като се използува субституцията х'j= 1 - хj, J = 1,2,5 и x'j = хj, j = 3,4. Целевата функция на преобразуваната задача е J = 4x1 + 3x2 + 6x3 + 3x4 + 4x5 Тя е получена след субституцията и пренебрегване на константата в дя-сната част на , тъй като тя не влияе на избора на хi. След записване на 
третото ограничение във вида и въвеждане на допълнителните про-менливи S1, S2 и S3, преобразуваната задача се представя във формата, представена в таблица 7.11.
В началото всички хj = 0 и стойностите на допълнителните променливи Si0 и на целевата функция J0 са [S10,S20,S3°] = [2,-3,-2] и J0 = 0. Тъй като S20 и S30 са отрицателни, началното решение [0,0,0,0,0] е недо-пустимо и поне една променлива хj трябва да приеме стойност 1, така, че решението да се измести по-близо до допустимата област. От табли-цата се вижда, че всички коефициенти при променливата х3 в ограниченията с отрицателни стойности на Si са неотрицателни. Полагането х3 = 1 само би увеличило степента на недопустимост (например S2 би получила стойността S'2 = -7), поради което х 3 трябва да запази началната си нулева стойност. Вижда се също, че всяка от променливите x1,x2 и х4 по отделно не може да осигури допустимост, но комбинация от тях при стойности 1 може да доведе до допустими Si. Затова тези променливи не се изключват от по -нататъшно разглеждане. Ако пък се положи х5 = 1, може да се постигне допустимо решение. Поради това процедурата ще осигури полагането на х5 = 1, което ще доведе до решението [ х 1 , x2, x3, x4, x5] - [0,0,0,0,1]. [S11,S21,S31] = [S10 - (-1),S20 - (-4),S30 - (-4)] = [3,1,2] И J1 — 4. Тъй като товае първото допустимо решение, то се запазва и определи горна граница J за всяко бъдещо допустимо решение, J — J1 = 4. Както при метода на клоните и границите, от бъдещите допустими Фиг. 7.5
Тъй като всички коефициенти сj > 0 и се решава задача за мини-мизация, нито един клон с хj = 1, j = 1,4 не може да подобри стойност-та на целевата функция. Следователно възелът (1) е оценен. Остава да се анализира решението във възела (2), който съответствува на един-ствения останал клон x5 = 0. Решението в този възел е [х1,х2,х3,х4,х5} = [ 0 ,0 ,0 ,0 ,0] , [S12,S22,S32]= [2,-3,-2], J2 = 0. Разликата между решенията във възлите (0) и (2) не е в стойностите на променливите и на функцията J, а в това, че във възела (0) всяка от променливите хj, j = 1,5 е свободна променлива, т.е. може да приема стоиности 0 или 1 и да генерира разклоняване, докато във възела (2) свободни са само променливите хj, j = 1,4, а х5 е фиксирана на нулева стойност. Изборът на променлива на разклоняването във възела (2) се из-вършва по същия начин както във възела (0), като се използува и ин- формацията за горната граница 
намалява още повече). Променливата х1 също може да бъде устранена, тъй като c1 = 4 не води до по-добра стойност на J от Следователно, изборът трябва да бъде направен между х2 и х 4. Тъй като нито една от тези променливи не отстранява недопустимостта (ко-гато стойността й нарастне на 1), като променлива на разклоняване ще се избере тази от тях, на която съответствува най-голямото намаление на недопустимостта. За целта за всяка свободна променлива хj се дефи-нира "мяра на недопустимостта на решението", което се получава след полагането х3 = 1. Тази мяра е емпирична и се въвежда по следния начин: Като променлива на разклоняване се избира променливата, за която абсолютната стойност на vj e най-малка. В случая v2 = min{0,2 - (-1)} + min{0, -3 - 0} + min{0, -2 - (-7)} = 0+(-3) + 0 = -3 v4 = min{0,2-3} + min{0,-3- (-5)} + min{0, -2 - (-4)} = -1+0 + 0= -1 като променлива на разклоняване се избира х4. На фиг.7.5 х4 = 1 е клонът, който води до възела (3), дефиниран от х5 = 0 и x4 = 1, където [x1,x2,x3,x4,x5] = [0.0,0,1,0], [S13,S23,S33] = [-1,2,2], J3=3. Свободни променливи в този възел са x1,x2 и x3. Тъй като с1 = 4, с2 = 3 с3 = 6, полагането на x1,x2 или x3 равно на единица би довело съответно до стойностите J = 3 + 4, З + ЗиЗ + 6, които са по-лоши от J. Следователно x1,x2 х3 се изключват от разглеждане и тъй като това са всички свободни променливи във възела (3), по-нататъшното разклоняване от този възел не е възможно и той е оценен. Остава единствено възелът (4), дефиниран от х5 = 0 и x4 = 0. Тук
Свободни променливи са x1,x2 и x3. Неперспективността на х3 вече бе-Ше показана, a х1 и х2 не могат да направят решението в (4) допустимо. Следователно не съществуват променливи на разклоняване и възелът (4) е оценен. Всички възли са оценени и решението се определя от възела (1) [x1,x2,x3,x4,x5] = [0,0,0,0,1] и J = 4. Решението на началната задача се получава след преминаване към на-чалните променливи
При формализирането на процедурата се използуват понятията свободна променлива и частично решение. Една двоична променлива е
Частичните решения могат да бъдат генерирани последователно едно от друго. Общото правило за получаване на следващото частично решение от едно оценено решение (възел) е следното. Ако всички елементи на оце-неното частично решение Rs са отрицателни, изброяването е напълно завършено. В обратния случай се избира най-десният положителен еле-мент, изменя се знакът му и се отстраняват отрицателните елементи вдясно от него. Например, ако решението Rs = {2,6,5,-4,3,7,-8,-9} е оценено, Rs+1 = {2,6,5,-4,3,-7}. Смисълът на правилото се изясня-ва, като се вземе предвид, че адитивният алгоритъм добавя новите променливи със стойност единица. Отрицателният елемент в такъв случай означава, че предшествуващото частично решение, в което този елемент е бил положителен, е било оценено. А когато всички елементи на оце-неното частично решение Rs ca отрицателни, съответните променливи са били разгледани със стойкости 0 и 1 и не съществуват повече клони за разглеждане (т.е. изброяването е завършено). Да предположим, че в общата двоична задача за минимизация, разгледана в началото на раздела, всички коефициенти сj  0 (след евентуална субституция на някои променливи). Разглежданият пример позволява да се представят в обобщен вид тестовете, използувани за оценяване на частичните решения и за избор на нови променливи, чиито стойности ще се фиксират равни на единица.
Тест 1, Нека xS e свободна променлива. Ако aiS  0 за всички г, съответствуващи на Sik< 0, xS се отстранява като неперспективна, тъй като не може да приближи решението до допустимата област.
Тест 2. Ако xS е свободна променлива и cS + Jk , xS се от-странява като неперспективнах тъй като не може да подобри съществу-ващото решение, определило J. Тест 3. Нека на ограничението аi1x1 + ai2x2 + ... + ainxn + Si = bi съответствува Sik< 0. Ако с Mk се означи множеството от свободни про-менливи, конто не са отстранени чрез тестовете 1 и 2, нито една от тези променливи не е перспективна, ако поне за една Sik < 0 се изпълнява условието 
Това означава, че променливите от Mk съвместно, когато стойностите им станат равни на 1, не могат да направят решението допустимо и трябва да бъдат отстранени. В такъв случай частичното решение Rk e оценено. Тест 4. Ако множеството Mk след прилагането на теста 3 не е празно, като променлива на разклоняването хr се избира тази, на която съответствува 
където
Ако vrk = 0, стойноетта хr = 1 заедно с частичното решение Rk води до подобрено допустимо решение. В този случай Rk+1 = {Rk,,r} e оценено. Ако обаче vrk < 0, описаните тестове се прилагат към Rk+1 дотогава, Докато изброяването се извърши напълно, т.е. докато всички елементи на оцененото частично решение станат отрицателни.
. [S10,S20,S30] = [2,-3,-2], J0 = 0. Чрез теста 1 се изключва х3. Променливите от множеството М0 {1,2,4,5} не се отстраняват чрез теста 3, защото i = 2: - 8 - 5 - 4 = -17 <-3 i = 3: - 7 - 4 - 4 = -15 < -2. За прилагането на теста 4 се определят: v10 = 0 + 0 + (-2- 12) = -14 v20 = 0 + (-3 - 0) + 0 = -3 v40 = ( 2 - 3 ) + 0 + 0 = -1 v50 = 0 + 0 + 0 = 0, следователно r = 5. Възел (итерация) 1 Полага се R1 = {5}. Определят се
Възел (итерация) 2 Полагат се R2 = {-5}, Възел (итерация) 3 Полага се R3 = {-5,4} и се определя
Полага се R4 = {-5,—4}. Определя се [S12,S24,S34] = [2,-3,-2], J4 = 0. Чрез теста 1 се изключва х3. Чрез теста 2 се отстраняват x1 и х3. Про-менливата от множеството М4 = {2} се отстранява чрез теста 3. Следо-вателно R4 e оценено. Тъй като всички елементи на R4 са отрицателни, изброяването е пълно. Оптималното решение е Rj, при което J1 = 4. ВЪЗМОЖНОСТИ ЗА ПОВИШАВАНЕ НА ЕФЕКТИВНОСТТА НА АЛГОРИТМИТЕ Най-съществени резултати са постигнати при разработването на алгоритми за решаване на двоични задачи на ЦП. Предложен е алго-ритмичен подход, чрез който са решени двоични задачи на ЦП - чисто и смесено, в които броят на променливите е няколко хиляди. Решените задачи имат обаче разредени матрици А, т.е. броят на ненулевите кое-фициенти във функционалните ограничения е твърде малък - около 5 %. В общия случай се счита, че все още само задачи с няколко десетки двоични променливи (до могат да бъдат решавани за приемливо време. съвременните алгоритмични реализации се използува комбинация от три вида методи: 1) усъвършенствувани алгоритми на клоните и границите; 2) генериране на отсичащи равнини и 3) автоматична предварителна обработка на задачата. Последната се основава на компютъ-рен анализ на началната формулировка, в резултат на който задачата се преформулира във вид, който се решава по-бързо, без да се отстраняват допустими решения. Някои от използуваните идеи са твърде прости. Например някои променливи се отстраняват от модела, като се фик-сират на 0 или 1, което пък е възможно поради наличието на някои специфични ограничения, например 5х1 + Зх2 < 3, ==> x1 = 0 5х3 - Зх4 < 2 ==> х3 = 0 и х4 = 1. Някои ограничения се отстраняват от модела, тъй като са излишни при двоични променливи, например 5х1 + 3х2 < 9. Двоичните променливи позволяват понякога стесняването на функци-онално ограничение чрез намаляване на някои от коефициентите му, например 6x1 + 8х2 + х3 > 3 ==> Зх1 + Зх2 + х3 > 3. . По този начин се стеснява отслабената задача на ЛП, т.е. отстраняват се някои нейни допустими решения, без да се елиминират допустими целочислени решения. Когато има група от променливи, които представят взаимно из-ключващи се алтернативи, често се използува "тригер", който задава стойност на една или повече променливи, след като на друга променли ва от групата е присвоена определена стойност от алгоритъма. Изложените идеи се използуват при създаването на евристични алгоритмы за решаване на задачи с голяма размерност. Тези алгори-тми определят бързо добри допустими решения, които не винаги са оптимални, но обикновено са по -добри от тези, които биха се получили чрез закръгляне на непрекъснатото решение на отслабената задача до допустимо целочислено решение. След бурно развитие през последните три десетилетия, създаването на алгоритми за решаване на целочислени задачи продължава да бъде област на активни изследвания. 7.7. ЗАКЛЮЧЕНИЕ Много задачи за управление, проектиране и избор на решение мо-гат да бъдат формулирани като задачи на ЦП. Те са по-трудни от зада-чите, в които отсъствуват изисквания за целочисленост на променли-вите, вследствие на което достъпните алгоритми за решаването им са значително по-малко ефективни от симплекс-метода. Най-важен фактор за времето на изчисление при ЦП е броят на променливите и струк-турата на задачата. Двоичните ЦЛЗ се решават по-лесно от задачите с общи целочислени променливи. Добавянето на нови непрекъснати променливи (СЦП) не влияе съществено върху времето на решение. За някои задачи със специална структура са разработени специализирани алгоритми, които решават големи задачи, с няколко хиляди двоични променливи. В общия случай обаче решението може да бъде определено ако броят на променливите е много по-малък. Съществуващите програми за задачи на ЦП се основават на метода на клоните и границите. Предполага се участие на човека в процеса на решение, при което последователно се уточнява начинът на решение на задачата чрез избиране между няколко възможни начина на решение. В новия алгоритмичен подход се комбинира използуването на метода на клоните и границите, генерирането на отсичащи равнини и автоматичната предварителна обработка на задачата. Разработват се евристични алгоритми за задачи с голяма размерност. Създадените алгоритми и програмни продукти все още не съот-ветствуват на значимостта на задачите на ЦП, които възникват в упра-влението и проектирането. Може да се очаква, че изследванията в тази облает и особено тези, свързани с приложенията на паралелни компю- търни системи, ще доведат до нови мощни алгоритми, с които решава-нето на задачи с голям брой променливи ще стане възможно. Каталог: lib lib -> Преводач Елена Атанасова Коректор Ива Данева Формат 84/108/32 Печатни коли 15 дф „абагар" Велико Търново ик „сова" Варна как да се използва тази книга lib -> За медитацията ошо въведение lib -> Поредица ние обичаме животните lib -> Тайната на скорпион lib -> Разчупване на оковите Победа над: Отрицателните мисли lib -> Въведение Изтегляне 482.95 Kb. Сподели с приятели:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
. Променливата х3 се изключва от разглеждане, тъй като условието х3 = 1 влошава както оптималността (J = 6 > ), така и допустимостта на решението (отрицателната про-менлива S2
. Определят се
= J1 = 4 и R1 e оцене-но.
. = 4 и се определя