Page 45 - 4168

4 Знаходимо I, що відповідає максимальні дробовій частині
коефіцієнта { β }, по всіх таких i, що β - дріб, і формуємо
i
i
додаткове обмеження, у якому коефіцієнти будуть дробо-
вими частинами {g} коефіцієнтів попередніх обмежень
n
x n + 1 ∑ {a Ij } = { − β I },
x
−
j
j =m + 1 (3.25)
x n + 1 ≥ , 0
де x n + 1 - додаткова змінна.
5 Розширюємо симплекс-таблицю за рахунок (m+1)-го рядка
(додаткове обмеження) та ( n +1) - го стовпця, що відпові-
дає додатковій змінній x n + 1 .
6 Розв'язуємо розширену таким чином ЗЛП двоїстим симп-
лекс-методом і переходимо до пункту 2, змінюючи s на
s+1. Якщо при цьому на якій-небудь ітерації двоїстого
симплекс-методу одна з додаткових змінних задачі (тобто,
тих, що з'явилися при побудові правильних відсіків) повто-
рно стає базовою, то виключаються з подальшого розгляду
відповідні їй рядок та стовпець.
Метод віток і меж
Для розв'язання задач дискретного лінійного програму-
вання широко використовується метод віток та меж. Цей метод
належить до класу комбінаторних методів і зводиться до на-
правленого перебору варіантів розв'язків оптимізаційної зада-
чі, шляхом відбору лише тих, які виявляються за певними
ознаками перспективними, і відкидаються відразу цілі множи-
ни безперспективних варіантів.
Розглянемо загальну схему методу на прикладі оптиміза-
ційної задачі
Z (x , x ,....x ) ⇒ min,
1 2 n (3.26)
x∈ , D
де D — скінченна множина.
Основу методу складають такі процедури.
1 Обчислення нижньої оцінки (границі) для значень цільової
0
функції Z(х) на допустимій множині D = D (або на деякій
її підмножині), тобто, знаходження числа (Dξ 0 ), такого,

45