Page 80 - 6197

n
предметів, тобто  a  Q . У ранці необхідно розмістити
j
j 1 
певну кількість предметів таким чином, щоб їх загальна
цінність була б максимальною.
Введемо змінні x , j  1,n ,які можуть приймати лише два
j
значення x  1, якщо j -тий предмет поміщений у ранець і
j
x  0, якщо j -тий предмет не кладуть у ранець.
j
Таким чином, сумарна цінність всіх предметів, які
покладені у ранець, буде такою:
n
R   x   c x . (2.6)
j
j
j 1 
Крім того повинні виконуватись обмеження на загальну
вагу предметів, що знаходяться у ранці
n
 a x  Q . (2.7)
j
j
j 1 
Очевидно, що у задачі про ранець, необхідно
максимізувати цільову функцію (2.6) за умови наявності
обмежень (2.7) з врахуванням тієї обставини, що змінні x
j
повинні належати бінарній множині

0
x    1; , j  1,n . (2.8)
j
Задача про випуск продукції. Деяка фірма випускає n
різних типів приладів. На виготовлення кожного типу
0
приладів є ресурс b  , i  1,m . Фірма планує випустити x
i j
приладів типу j . Прибуток від реалізації одного приладу
типу j становить c . Позначимо через a - кількість i
j ij
одиниць ресурсу b  необхідних для випуску одного
0
i
приладу типу j . Необхідно скласти такий план випуску

80