Page 46 - 4168

що (xz ) ξ≥ (D 0 ) для всіх x ∈ D . Питання про те, як знахо-
0
)
0
диться (D , вирішується окремо для кожної задачі.
ξ
2 Розбиття на підмножини (розгалуження). Реалізація мето-
ду пов'язана з розгалуженням множини D (або деякої її пі-
дмножини) в дерево підмножин з наступним визначенням
найбільш перспективної.
Як і в методі відсікаючих площин, процес починають з
розв’язку безперервної задачі ЛП. Якщо отриманий при цьому
0
оптимальний план x не задовольняє умові цілочисельності, то
значення цільової функції ξ 0 = Z (x 0 ) дає нижню оцінку (межу)
для шуканого розв’язку.
Алгоритм методу віток та меж (Ленд-Дойг)
1 Розв'язуємо задачу ЛП без врахування умови цілочисловос-
ті змінних. Якщо її розв'язок x - цілочисловий, то він є ро-
0
0
зв'язком вихідної цілочислової задачі ЛП на множині D . У
протилежному випадку величина (D =ξ 0 ) Z (x 0 ) дає нижню
0
оцінку (межу) цільової функції ЦЗЛП на множині D .
0
1
2 Множину D розбиваємо на дві підмножини D 1 1 , D , причо-
2
1
1
0
му D = D ∪ D за умовою
1
2
D = 1 1 { :xx∈ D 0 ; x ≤ i [ ]},x 0 i
(3.27)
D = 1 2 { :xx∈ D 0 ; x ≥ i [ ] } 1 ,x 0 i +
де x - нецілочислова компонента.
i
1
3 Розв'язуємо задачу ЛП на множині D і знаходимо оптима-
1
1
льний розв’язок x , аналогічно розв'язуємо задачу ЛП на
1
множині D і знаходимо оптимальний розв’язок x .
1
1
2
2
4 Визначаємо оцінки (D =ξ 1 1 ) Z (x 1 1 ) , (D =ξ 2 1 ) Z (x 1 2 ) і перевіря-
ємо умову оптимальності.
1
Якщо x - цілочислова і (Dξ i 1 ) = min { (Dξ 1 1 ),ξ (D 2 1 } ) , то x - оп-
1
i
i
тимальний розв'язок.
5 В іншому випадку переходимо до наступної ітерації з про-
цедурою розгалуження. Найперспективнішу множину ви-
значаємо за умовою (Dξ v k ) = minξ (D v k ) .
46