Page 86 - 4719

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

Поділ на підмножини у симплекс-методі здійснюється
шляхом введення нових обмежень x ≤ [ ] або x i ≥ [ ] 1+x 0 i .
x
i
0 i
При розв’язку задачі максимізації функції
використовують верхні оцінки.

2. Контрольні запитання

1. Поясніть суть методу Гоморі.
2. Наведіть алгоритм методу Гоморі.
3. В чому полягає суть методу віток і меж?
85