Задача про рюкзак.

Задача про рюкзак.

Найпростішою задачею цілочислового програмування, а саме задачею лише з одним обмеженням, є задача про рю-кзак (або ранець). Така задача має багато прикладів прак-тичного застосування. Назва «задача про рюкзак» пов’язана з інтерпретацією задачі вибору найкращого складу предметів, що задовольняють певні умови гіпотетичної проблеми туриста щодо вибору для походу оптимальної кількості речей.
Турист може вибирати потрібні речі із списку з Неможливо розібрати вираз (невідома помилка): n

предметів. Відома вага кожного Неможливо розібрати вираз (невідома помилка): j

-го предмета Неможливо розібрати вираз (невідома помилка): m_j(j=\overline{1,n}) .Визначена також цінність кожного виду предметів Неможливо розібрати вираз (невідома помилка): w_j .Максимальна вага всього вантажу в рюкзаку не може перевищувати зазначеного обсягу М. Необхідно визначити, скільки предметів кожного виду турист має покласти в рюкзак, щоб загальна цінність спорядження була максимальною за умови виконання обмеження на вагу рюкзака.
Позначимо через Неможливо розібрати вираз (невідома помилка): x_j – кількість предметів Неможливо розібрати вираз (невідома помилка): j -го виду в рюкзаку. Тоді математична модель задачі матиме вигляд:

Неможливо розібрати вираз (невідома помилка): \max F=\sum_{j=1}^n w_j x_j Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n m_j x_j \le M ; Неможливо розібрати вираз (невідома помилка): x_j \ge 0 , x_j

— цілі числа, Неможливо розібрати вираз (невідома помилка): (j=\overline{1,n})

.

Приклад

Фермеру для удобрення земельної ділянки необхідно придбати 107 кг добрив. Він може купити добрива в упаковках по 35 кг вартістю 14 ум. од. або по 24 кг вартістю 12 ум. од. Метою фермера є закупівля не менше, ніж 107 кг добрив з мінімальними витратами. Причому потрібно купувати або цілу упаковку, або не купувати її зовсім, бо частину упаковки придбати неможливо.

Розв’язання.Позначимо кількість упаковок вагою 35 кг та вагою 24 кг відповідно змінними Неможливо розібрати вираз (невідома помилка): x_1

та Неможливо розібрати вираз (невідома помилка): x_2
. Маємо модель цієї задачі:

Неможливо розібрати вираз (невідома помилка): \min F= 14 x_1 + 12 x_2 Неможливо розібрати вираз (невідома помилка): 35 x_1 + 24 x_2 \ge 107 ; Неможливо розібрати вираз (невідома помилка): x_1 \ge 0 , x_2 \ge 0 , x_1,x_2 — цілі числа.

У результаті розв’язування задачі будь-яким з вищена-ведених методів отримаємо оптимальний план: Неможливо розібрати вираз (невідома помилка): X^{*}(x_1=1,x_2=3), F_\min =50 .Отже, за оптимальним планом найменші витрати, що дорівнюють 50 ум. од., можливі у разі закупівлі однієї упаковки добрив вагою 35 кг та трьох вагою по 24 кг.