Задача на целочисленото линейно програмиране

оценена също, ако въобще няма допустимо решение.

целочислено решение и да се оцени и втората подзадача ЛП2. Като променлива на разклоняването обаче би могла да бъде избрана промен-лиивата x2, а като първа за решаване - подзадачата ЛП2, което би довело до значително по-различен изчислителен процес от разглеждания. Не-ка например най-напред да се решава задачата ЛП2 (фиг.7.3). Нейното оптимално решение е х*1 = 5, х*2 = 0,7273 и J* = 33,6364. Тъй като стойността х*2 не е целочислена, х 2 се избира като променлива на раз-клоняване и от подзадачата ЛП2 възникват двете нови подзадачи ЛПЗ и ЛП4, съответно с клони и . Техните пространства на решение са ПрЛПЗ = ПрЛП2 и ограничението

(x2 0) =
ПрЛП0 и ограничението (х1 5) и ограничението (х2 0); ПрЛП4 = ПрЛП2 и ограничението (х2 1) =
ПрЛП0 и ограничението (x1 5) и ограничението (х2 1).

Нека като първа се решава подзадачата ЛП4. Прилагането на дуалния симплекс -метод показва, че тази подзадача няма допустимо целочислено решение, т.е. тя е оценена. Да предположим, че като следваща за решаване произволно се избира подзадачата ЛПЗ. Нейното решение x*1 = 5, х*2 = 0 и J* = 30 удовлетворява изискванията за целочисленост. Това решение определя текуща долна граница J* = 30 за оптималната стойност на целевата функция на ЦЛЗ. Последна се решава подзадачата ЛП1. Както беше показано по-горе, нейното оптимално решение е х*1 = 4, х*2 = 2, J* = 34 и то определя нова, по-добра долна граница. Тъй като всички задачи са оценени, решението на началната ЦЛЗ се определя от оптималното решение, което съответствува на текущата Долна граница - решението на ЛП1.

Разгледаният изчислителен процес премина през решаването на задачите ЛПО->ЛП2->ЛП4->ЛПЗ->ЛП1 и е значително по-неефективен от първия процес ЛП0->ЛШ -»ЛП2. Той илюстрира един основен не-достатък на метода на клоните и границите - липсата на обосновани правила за избиране на променливата на разклоняване при дадена под-задача и на следващата за решаване подзадача сред останалите нереше-ни подзадачи. Според едно най-просто правило целочислените промен-ливи се номерират и подреждат в естествен ред x1,x2, ... ,хп и сред тези от тях, конто в оптималното решение на съответната подзадача имат нецелочислени стойности, се избира първата в естествения ред (тази с най- мальк номер) като променлива на разклоняването.
Съществуват евристични правила за избор на перспективни клони, конто невинаги са резултатни при решаването на общата задача на ЦЛП.
Алгоритъмът на клоните и границите се използува и за решаване на задачи на СЦП, като непрекъснатите променливи (тези, конто могат да имат дробни стойности) не се избират като променливи на разклоняване. Нека да изменим разглеждания пример така, че променливата х1 да е целочислена, x2- непрекъсната. Подзадачата ЛП1 дава допустимо решение x1 = 4 и долна граница J* = 34. В случая обаче подзадачата ЛП2 не може да бъде оценена без да се реши, тъй като целевата функция може да има нецелочислени стойности. Решението на тази подзадача е x*1= 5, x*2 = 0,7273 и J* = 33,6364. Вижда се, че решението на ЛП1 е по-добро и то е оптималното решение на разгледаната задача на СЦП.
Често оптималната стойност J*, подучена при решаването на под-задача, която е възникнала от начална задача на СЦП, се нарича граница на подзадачата. Ако началната задача е напълно целочислена, грани-цата на възникнала от нея подзадача се определя, като подучената за подзадачата стойност J* се закръгли до най-близкото по-малко цяло число.
Методът на клоните и границите е предложен от Ланд и Доиг (1960). Съвременните реализации се основават на алгоритъма на Да-кин (1965). В случая на задача за максимизация този алгоритъм може да бъде представен в

следния обобщен вид:

Начална стъпка. Полага се долната граница . Решава се
отслабената задача ЛПО. Ако ЛПО е оценена, изчисленията се прекра-тяват, в обратния случай се преминава към стъпка 1.
Стъпка 1. Разклоняване. Избира се подзадача сред оставащите не-оценени подзадачи (например последната създадена). Избира се една от целочислените променливи xj, чиято стойност х* j в оптималното решение на подзадачата не е целочислена (например първата такава в естествения ред на целочислените променливи). Построяват се две нови подзадачи чрез

включване	към	избраната	подзадача	на	едно	от	ограни-
ченията			, където [х*j] означава най-голямото цялo
число

Стъпка 2. Ограничаване. Определи се границата на всяка от двете нови подзадачи чрез решаването и с използуване на дуалния симплекс-метод. В случая на задача на чистото ЦП стойността на J се закръгля до най-близкото по-малко цяло число, а при задача на СЦП закръгление

не се извършва.
Стъпка 3. Оценяване. За всяка от новите подзадачи се проверява изпълнението на следните условия:

а) границата и е J*, където J* e текущата долна граница на началната задача;

сленост.
Ако се изпълнява кое и да е от тези условия, подзадачата е оценена. Оценените подзадачи се отстраняват от разглеждане. Ако подзадачата е оценена вследствие изпълнение на условие в) и оптималното и решение е по-добро от досегашното, то го заменя, а съответствуващата му стойност на целевата функция става нова текуща граница J*. В този случай условие а) се проверява отново за всички неоценени подзадачи с новата, по-добра стойност на J*.

границата на подзадачатаJ*.

при зададени положителни константи М и .За определяне на ква-зиоптимално решение условие а) в стъпка 3 на алгоритъма се заменя с едно

от двете условия

границата на подзадачата J* + М

или (1 —) границата на подзадачата J*, като условието се
проверява след проверката на условие в) и установя-ването евентуално на нова долна граница. Ускорението се дължи на това, че алгоритъмът оценява (отстранява от разглеждане) дадена подзадача, ако нейната граница не е "достатъчно по-добра" от текущата долна граница.

АЛГОРИТМИ, КОИТО РЕАЛИЗИРАТ МЕТОДА НА ОТСИЧАЩИТЕ РАВНИНИ

Необходимо е да се максимизира

въвеждането на две нови подходящи ограничения позволява да се получи нова екстремна точка (5,4), която е оптималното решение на началната задача. Защрихованата "отсечена" област не съдържа точки с целочислени координати.

чението

Където xi, i = l,m са базисните, a zj,j = l,n - небазисните променливи. Да предположим, че на i-тия ред е получена нецелочислена стойност bi На базисната променлива xi. Тази променлива може да бъде изразена

чрез небазисните променливи

Всеки ред на симплекс-таблицата, който поражда такова равенство, се нарича ред-източник (произвеждащ ред). Тъй като коефициентите на J са цели, J трябва също да е целочислена и първият ред на таблицата може също да се избира като произвеждащ ред. Стойностите bi и аji се представят

във вида

bi =[bi] + fi, aji = [aji] + fij

където с N = [с] е означено най-голямото цяло число, което удовлетво-рява условието Nс. Следователно fi, и fij удовлетворяват условията 0 < fi < 1 и

0 fij < 1, т.е. fi е положителна дроб, а fij - неотрицател-на дроб. Например,

ако с = 11/3, [с] = 1 и f = с - [с] = , ако с = -22/3 [c] = -3 и f = 1/3.

След заместване с новите означения в уравнението за xi, се полу-чава

или

където Si >= 0 е допьлнителна променлива, конто по определение трябва да има целочислени стойности. Последното ограничение вьв вид на равенство

определя сечението на Гомори за напълно целочислената задача.

Тъй като небазисните променливи z3 = 0, то очевидно Si = fi, т.е. тази компонента на решението не е допустима. Това означава, че полученото по-рано решение на отслабената задача на ЛП не удовлет-ворява новото ограничение. В този случай бихме могли да използува-ме дуалния симплекс-метод, с помощта на който да се отсече част от областта, която не съдържа точки с целочислени координати.
Симплекс-таблицата на отслабената задача се преобразува чрез добавяне на нов ред и нов стълб, които съответствуват на полученото уравнение на сечението на Гомори и се получава решението в табл.7.3.
Таблица 7.3.

Тъй като всички xi и zj трябва да имат цели стойкости, дясната част трябва да е целочислена. Следователно и лявата част трябва да приема цели стойности. Но fijО и z j0 за всички i,j, следователно