Відмінності між версіями «Задача про рюкзак.»
(→Приклад) |
(→Приклад) |
||
| Рядок 18: | Рядок 18: | ||
<center> <math>35 x_1 + 24 x_2 \ge 107</math> ; </center> | <center> <math>35 x_1 + 24 x_2 \ge 107</math> ; </center> | ||
| + | |||
| + | <center> <math>x_1 \ge 0 , x_2 \ge 0 , x_1,x_2 </math> — цілі числа. </center> | ||
Версія за 21:59, 4 травня 2012
Задача про рюкзак.
Найпростішою задачею цілочислового програмування, а саме задачею лише з одним обмеженням, є задача про рю-кзак (або ранець). Така задача має багато прикладів прак-тичного застосування. Назва «задача про рюкзак» пов’язана з інтерпретацією задачі вибору найкращого складу предметів, що задовольняють певні умови гіпотетичної проблеми туриста щодо вибору для походу оптимальної кількості речей.
Турист може вибирати потрібні речі із списку з Неможливо розібрати вираз (невідома помилка): n
предметів. Відома вага кожного Неможливо розібрати вираз (невідома помилка): j
-го предмета Неможливо розібрати вираз (невідома помилка): m_j(j=\overline{1,n})
.Визначена також цінність кожного виду предметів Неможливо розібрати вираз (невідома помилка): w_j
.Максимальна вага всього вантажу в рюкзаку не може перевищувати зазначеного обсягу М. Необхідно визначити, скільки предметів кожного виду турист має покласти в рюкзак, щоб загальна цінність спорядження була максимальною за умови виконання обмеження на вагу рюкзака.
Позначимо через Неможливо розібрати вираз (невідома помилка): x_j
– кількість предметів Неможливо розібрати вираз (невідома помилка): j
-го виду в рюкзаку. Тоді математична модель задачі матиме вигляд:
— цілі числа, Неможливо розібрати вираз (невідома помилка): (j=\overline{1,n})
. Приклад
Фермеру для удобрення земельної ділянки необхідно придбати 107 кг добрив. Він може купити добрива в упаковках по 35 кг вартістю 14 ум. од. або по 24 кг вартістю 12 ум. од. Метою фермера є закупівля не менше, ніж 107 кг добрив з мінімальними витратами. Причому потрібно купувати або цілу упаковку, або не купувати її зовсім, бо частину упаковки придбати неможливо.
Розв’язання.Позначимо кількість упаковок вагою 35 кг та вагою 24 кг відповідно змінними Неможливо розібрати вираз (невідома помилка): x_1
та Неможливо розібрати вираз (невідома помилка): x_2 . Маємо модель цієї задачі:
