Задача на целочисленото линейно програмиране
Изтегляне 482.95 Kb.
|
и се изпълнява неравенството Тъй като fi < 1, то и . Както беше показано, лявата част на това неравенство трябва да има цели стойности. От последното неравенство следва, че необходимото условие за нейната целочисленост е 
Това ограничение се записва във вида 
Ако решението, получено по дуалния симплекс-метод, е целочи-слено, процесът на решаване приключва. В обратния случай се въве-жда ново сечение на Гомори въз основата на симплекс-таблицата на оптималното решение, определено по дуалния симплекс-метод и отно-во се прилага този метод. Тази процедура се повтаря до получаването на целочислено решение. Ако на някоя итерация се разкрие отсъствие на допустимо решение (при прилагането на дуалния симплекс-метод), Началната задача на ЦП няма допустимо целочислено решение. Алгоритъмът се нарича дробен, защото всички ненулеви коефици-енти на сечението на Гомори са по-малки от единица. Общият брой на ограниченията на породената задача не е по-го-лям от (rn + п). Ако породената задача има повече от m+n ограничения, една или няколко от допълнителните променливи Si стават базисни, съответните уравнения стават излишни и се изключват от таблицата. Основните недостатъци на този алгоритъм са възможността за определяне на неоптимално целочислено решение вследствие на грешки при закръгленията и отсъствието на допустимо решение до последна-та итерация на процеса на решение. Има алгоритми, конто избягват тези недостатъци, но в изчислително отношение те не са достатъчно ефективни. Пример 7.2. За разглежданата по-горе задача на ЦП, чието реше-ние е показано на фиг.7.4., симплекс-таблицата на оптималното решение на отслабената задача е
Като произвеждащ може да се избере кой да е от редовете. Оби-кновено се избира редът, на който съответствува mах{fi}. В случая това е редът на х2 (4/5 > 2/5). За този ред може да се запише 
или 
откъдето уравнението на сечението на Гомори е 
Новата симлекс-таблица е
Тъй като S1 има недопустима стойност (< 0), прилага се дузл-ният симплекс-метод. В съответствие с правилата за определяне на изключваната и включваната променлива, изключва се променлива S1 и се включва променливата х3. Преобразуваната таблица, чиито еле-менти са получени по съответните правила за дуалния симплекс-метод. е
Вижда се, че новата стойност на х2 е целочислена, но решение-то за х1 е нецелочислено, затова въвеждането на сечения продължава. Уравнението на х1 се представя във вида 
и новото пораждащо сечение се описва с уравнението 
Това сечение се добавя към последната таблица и се получава табл.7.7.
След прилагането на дуалния симплекс-метод се получава таблица 7.8. Оптималното решение на началната задача е х*1 = 5, х*2 = 4 и J* = 80. Вижда се, че стойността на J намалява с последователното въвеждане на нови ограничения. Да проверим как сеченията отсичат части от допустимото про-странство на отслабената задача. От последната таблица се вижда, че x2 + S1 = 4, откъдето x2 <= 4 е едното ново допълнително ограничение. От същата таблица може да се запише х1 - S1 + S2 = 5.
в повечето случаи по-добре представя "силата" на дробното сечение, измервана с големината на отрязваната област от пространството на решенията. АЛГОРИТЪМ ЗА РЕШАВАНЕ НА ЧАСТИЧНО ЦЕЛОЧИСЛЕНИ ЗАДАЧИ Нека xк е целочислена променлива в задача на СЦП. Съответни-ят й ред в симплекс-таблицата на оптималното решение на отслабената задача поражда съотношението 
или
Тъй като някои от променливите zj не са целочислени, трябва да се построи процедура на отсичане по-различна от използуваната при напъл-но целочислени задачи. Това може да бъде направено като се използува фактът, че за целочислената променлива хк трябва да се изпълнява едно от двете условия 
Каталог: lib lib -> Преводач Елена Атанасова Коректор Ива Данева Формат 84/108/32 Печатни коли 15 дф „абагар" Велико Търново ик „сова" Варна как да се използва тази книга lib -> За медитацията ошо въведение lib -> Поредица ние обичаме животните lib -> Тайната на скорпион lib -> Разчупване на оковите Победа над: Отрицателните мисли lib -> Въведение Изтегляне 482.95 Kb. Сподели с приятели:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||