Задача на целочисленото линейно програмиране
Изтегляне 482.95 Kb.
|
|
След заместване за хк от сьотношението по-горе тези условия приемат вида 
Ако с N+ и N- се означат множествата на индексите j, за конто съот-ветно аjк 0 и аjк < 0, от последните две неравенства се получава 
Тъй като тези две условия не могат да се изпълняват едновременно, по-долу
търсеното сечение на Гомори за частично целочислената задача и е необходимото условие за целочисленост на xк. В оптималната симплекс-таблица всички небазисни променливи zj = 0, следователно стойността на Sk не е допустима. По-нататък изчисленията трябва да продължат с използуването на дуалния симплекс-метод. Възможността за обединяване на двете условия по-горе в едно ограничение се показва по следния начин. Условията се записват в опростен 
след умножаване На двете страни по —1 и въвеждане на допълнителната променлива Sk, Може да се запише Sk - {а + b) = -fk.
откъдето
или
Вижда се, че оптималната стойност J* = 86 / се получава при х*1 = 5 и х*2 = 42/3. 
Счита се,че методите на отсичането не са подходящи за решаване-то на задачи с по-голяма размерност. Те са ефективни при решаването на някои задачи със специална структура. Напоследък, в съчетание с елементи на разклоняване, идеите за отсичащи равнини се използуват при разработването на нови алгоритми на ЦП. 7.5. ДВОИЧНИ ЦЕЛОЧИСЛЕНИ ЗАДАЧИ Целочислената променлива х с горна граница п, 0  х  п може да бъде изразена чрез п двоични променливи y1,y2, ...,yn по следния начин
x = y1 + y2 + ... + yn Друго по-икономично представяне, при което броят на двоичните про-менливи обикновено е по-малък от п, е следното х = y0 + 2y1 + 22у2 + ... + 2rуr, където r е най-малкото цяло число, което удовлетворява 2r+1 — 1  п. По такъв начин всяка целочислена задача може да бъде представена като задача на двоичното ЦП. За решаването на такива задачи може да се използува разгледаният метод на клоните и границите, като се направят следните изменения:
—
съответната отслабена задача xi приема фиксирани стойности, съ-ответно 1 или 0. Основен недостатък на този алгоритъм е решаването във всеки възел на задача на ЛП. Това е избегнато в метода, предложен от Е. Балаш за решаване на двоични целочислени задачи, известен като ади-тивен алгоритъм. Този метод може да се разглежда като модификация на по-общия метод на клоните и границите. Простотата на пресмята-нията с двоични променливи е използувана при него по такъв начин, че единствените необходими операции са събиране и изваждане. Това е определило и наименованието - адитивен алгоритъм. 7.5.1. АДИТИВЕН АЛГОРИТЪМ Разглежда се следната задача Да се минимизира 
при ограниченията 
където Si 0 са допълнителни променливи. За използуването на алго-ритъма е необходимо началната симплекс-таблица на отслабената за-дача да определи т.нар. дуално допустимо решение, т.е. оптимално, но недопустимо решение. Необходимо е с-ыцо ограниченията да са от типа 
Получаването на начално дуално допустимо решение на отслабената задача е възможно, ако Ако има някое с,- < 0, то се преобразува чрез допълването на хj, т.е. чрез заместването жу = 1 - х'j в целевата функция и ограниченията, където х'j е двоична променлива Задачата, в която всички , се нарича дуално реигима. 
Понякога, след преобразуването на отслабената задача в дуално решима, началната симплекс-таблица определя допустимо решение. В такива случаи това решение е и оптимално, тъй като оптимумът на J се постига, като всички променливи хj се положат равни на нула. Адити-вният алгоритъм се използува за решаване на задачи, когато началното решение е дуално-допустимо (оптимално и недопустимо). Основната идея се състои в изброяването (преглеждането, проби-рането) на всички 2n възможни решения на задачата, при което само в част от тях се изследват явно, а останалите се отстраняват автоматично. В началото всички променливи хj, имат нулева стойност. Тъй като задачата е за минимизация, решението е оптимално, но недопустимо -някои
Каталог: lib lib -> Преводач Елена Атанасова Коректор Ива Данева Формат 84/108/32 Печатни коли 15 дф „абагар" Велико Търново ик „сова" Варна как да се използва тази книга lib -> За медитацията ошо въведение lib -> Поредица ние обичаме животните lib -> Тайната на скорпион lib -> Разчупване на оковите Победа над: Отрицателните мисли lib -> Въведение Изтегляне 482.95 Kb. Сподели с приятели:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
в отслабените задачи на ЛП за двоичните променливи Xi се