Page 85 - 4719

стає базовою, то виключаються з подальшого розгляду
відповідні їй рядок та стовпець.

Метод віток і меж

Для розв'язання задач дискретного лінійного
програмування широко використовується метод віток та меж.
Цей метод належить до класу комбінаторних методів і
зводиться до направленого перебору варіантів розв'язків
оптимізаційної задачі, шляхом відбору лише тих, які
виявляються за певними ознаками перспективними, і
відкидаються відразу цілі множини безперспективних
варіантів.
Розглянемо загальну схему методу на прикладі
оптимізаційної задачі
Z (x 1 , x 2 ,....x n ) ⇒ min, (14.1)
x∈ , D
де D — скінченна множина.
Основу методу складають такі процедури.
1 Обчислення нижньої оцінки (границі) для значень
0
цільової функції Z(х) на допустимій множині D = D (або на
деякій її підмножині), тобто, знаходження числа ξ (D 0 ),
такого, що (xz ) ξ≥ (D 0 ) для всіх x ∈ D . Питання про те, як
0
знаходиться (Dξ 0 ), вирішується окремо для кожної задачі.
2 Розбиття на підмножини (розгалуження). Реалізація
методу пов'язана з розгалуженням множини D (або деякої її
підмножини) в дерево підмножин з наступним визначенням
найбільш перспективної.
Як і в методі відсікаючих площин, процес починають з
розв’язку безперервної задачі ЛП. Якщо отриманий при цьому
0
оптимальний план x не задовольняє умову цілочисельності,
то значення цільової функції ξ 0 = Z (x 0 ) дає нижню оцінку
(межу) для шуканого розв’язку.

Алгоритм методу віток та меж (Ленд-Дойг)
84