Page 229 - 4685

де останнє обмеження (*) може враховувати найрізноманітніші умови:
якщо накладається вимога "повинен", то в обмеженні (*) ставиться знак
рівності;
якщо вимога "може", то — знак нерівності, зокрема: якщо накладається
s
вимога "І", то умова (*): ∑ d j ³1, наприклад ухвалення і першого і третього
j =1
варіантів запишеться так: δ + δ ≥1; якщо для варіантів накладається вимога
3
1
s
"АБО", то умова (*) запишеться так: ∑ d j =1.
j =1

ДИСКРЕТНЕ ПРОГРАМУВАННЯ

У цих задачах результатом рішення мають бути цілі, але не будь-які цілі.
Приклад. Меблева фабрика випускає дивани, крісла і стільці. Потрібно
визначити, скільки можна виготовити спинок диванів, підлокітників крісел і
ніжок стільців при відомій питомій витраті ресурсів, щоб дохід був
максимальним. Випуск спинок дивана може набувати будь-якого значення,
підлокітники виготовляються парами, тобто вони мають бути кратні двом, а
ніжки стільців — чотирьом:
Показники Вироби Наявність

Спинка дивану Підлокітники Ніжка ресурсу
крісла стільця
Ціна, гр. од./од. 20 6 8 -
Деревина 10 5 3 206
Затрати праці 2 7 4 100
Попит 10 8 12 -
х х х b
і
3
1
2

Рішення. Математична модель задачі запишеться у вигляді:
max : = 204 + 64 + 84 ;
!
[
`
104 + 54 + 44 ≤ 206;
!
[
`
2x + 7x + 4x £ 100;
1 2 3
0 ≤ 4 ≤ 10;
!
0 ≤ 4 ≤ 8;
[
0 ≤ 4 ≤ 12;
`
4 = 2_ [! + 4_ [[ + 6_ [` + 8_ ;
[a
[
4 = 4_ + 8_ + 12_ ;
` `! `[ ``
_ [! + _ [[ + _ [` + _ [a = 1;
_ `! + _ `[ + _ `` = 1.
де δ , δ – варіанти кількостей підлокітників і ніжок (k=1,….,k ).
3k
i
2k
Введення булевих змінних дає можливість забезпечити випуск виробів в
кратній заданій кількості. Так, для підлокітників х може набувати наступних
2
значень: якщо в результаті рішення буде отримано _ = 1, а останні _ = _ =
21
22
23
_ = 0, то x = 2; якщо _ = 1, а останні _ = _ = _ = 0, то x = 4 і так далі.
2
22
2
24
23
24
21
225