Page 226 - 4685

[x *] – ціла частина нецілочисельного значення змінної x * в оптимальному
j
j
рішенні. Потім вирішуються ще дві задачі лінійного програмування, до кожної
з яких увійшли всі вихідні обмеження і одне із додаткових.
Отримане вирішення нових задач перевіряють на цілочисельність змінних.
Якщо рішення не задовольняє вимогу цілочисельності, на основі кожної із
задач складають дві нові аналогічно попереднім і так далі.
Якщо одне з рішень задовольняє вимогу цілочисельності, значення
цільової функції береться за граничне L . При цьому розгляд інших задач
гр
продовжується до тих пір, поки не буде отримано:
на одній із гілок недопустиме рішення;
на одній з гілок цілочисельне рішення; тоді значення цільової
функції порівнюється з L (верхнім – при mах, нижнім – при min);
гр
якщо набуте значення гірше, воно відкидається; якщо краще, то
береться за граничне;
на одній з гілок нецілочисельне рішення, проте при цьому значення
цільової функції гірше граничного, тоді подальший розгляд також
припиняється.
На першому циклі розрахунку
 ¥- max L ;
гр 
L =
 + ¥min L .
Приклад. Визначити значення змінних для наступної оптимізаційної
задачі:
mах L = 7х + Зх ;
2
1
5х + 2х ≤ 20;
1
2
8х + 4х ≤ 38;
2
1
x , х ≥ 0 – цілі.
1
2
Рішення. В результаті рішення задачі симплекс-методом знайдемо
! ∗ ! ∗
оптимальне рішення: 4 ! = 1; 4 [ = 7,5; : = 29,5, де верхній індекс змінних –
!
номер задачі.
В отриманому рішенні х = 7,5 – нецілочисельне. Тому для подальшого
2
рішення складаємо дві нові задачі з різними граничними умовами.
Задача 2
max : = 74 + 34 ;
! [
5x + 2x £ 20;
1 2
84 + 44 ≤ 38;
!
[
4 ≥ 0;
!
0 ≤ 4 ≤ 7.
[
Задача 3
max : = 74 + 34
!
[
5x + 2x £ 20;
1 2
84 + 44 ≤ 38;
[
!
4 ≥ 0;
!
4 ≥ 8.
[
Результати рішення задачі 2 симплекс-методом:
222