Page 79 - 6197

x - цілі числа, j  1,n , n  . (2.5)
n
j 1 1
Умова (2.5) означає, що n змінних можуть набувати
1
лише цілочислових значень, а на решту n n змінних вимога
1
бути цілими числами не розповсюджується.
n
При n  задача (2.2) – (2.5) називається частково
1
цілочисловою, а у тому випадку, коли n  , будемо мати
n
1
повністю цілочислову задачу.
Зустрічаються задачі, у яких змінні x  - булеві
0
j
0
n
x    1; , j  1,n , n  .
j 1 1
Математичні методи оптимізації частіше за все оперують
із задачами, які мають властивості регулярності і
характеризуються такими умовами:
- для кожної точки x X певним чином можна визначити
поняття непустого околу;
- існують необхідні і достатні умови локальної
оптимальності, які дають змогу знайти локальний оптимум
цільової функції за допомогою збіжного кінцевого (або
нескінченого) обчислювального процесу;
- локальний оптимум співпадає з глобальним оптимумом
цільової функції.
Задачі дискретного програмування не володіють
властивістю регулярності, що не дозволяє розв’язувати їх за
допомогою відомих методів математичного програмування.

2.2 Приклади задач дискретного (цілочислового)
програмування
Задача про ранець. Допустимо, що є n предметів, кожен із
яких має цінність c і вагу a , j  1,n . У наявності є ранець
j j
вантажопідйомністю Q , в який неможливо помістити всі n

79