Задача про рюкзак. Математична модель задачі про рюкзак

У загальному вигляді задача про рюкзак (в літературі часто зустрічається і інша її назва, а саме задача про ранець) формулюється в такий спосіб: є рюкзак певного об'єму і необмежена кількість предметів. Для кожного предмета відомий його об'єм (вага) і цінність (вартість, ефективність). У рюкзак можна покласти ціле число предметів різного типу. Мета полягає в тому, щоб сумарна цінність всіх, що знаходяться в рюкзаку, предметів була максимальна, а їх об'єм (вага) не перевищував заданої величини. До подібного формулювання може бути зведена задача максимального використання вантажопідйомності рухомого складу, вантажомісткості судна, автомобіля і тому подібне. Таке завдання часто виникає при виборі оптимального управління в економіко-фінансових областях (наприклад розподіл бюджету відділу по проектам).

Ілюстрація задачі про ранець

Запишемо математичну модель задачі такого типу. Для цього, припустимо, що розглядається скінченна множина предметів , для кожного з яких відома вартість і визначений об'єм . Також є рюкзак об'ємом . Необхідно упакувати рюкзак таким чином, щоб загальна вартість запакованих предметів була якнайбільшою, а їх загальний об'єм не перевищував величини . Традиційно вважають, що  — цілі невід'ємні числа.

Введемо двійкові змінні такі, що , якщо предмет обраний для упаковки в рюкзак і  — в протилежному випадку. Тоді задача про рюкзак зводиться до наступної задачі лінійного цілочисельного програмування з булевими змінними: знайти такі значення змінних , при яких досягається максимум суми:

і виконується обмеження:

Відмітимо, що якщо математична модель задачі містить тільки одне обмеження виду (2), то задача про ранець називається одновимірною, в протилежному випадку — багатовимірною.

Задача про рюкзак — приклад:

Знайти розв'язок задачі про рюкзак наступного вигляду: малому підприємству для прання необхідно 170 кілограм прального порошку на два тижні. Вони можуть його купити в упаковках по 35 кілограм вартістю 14 умовних одиниць або по 24 кілограми — вартістю 12 умовних одиниць. Метою малого підприємства є покупка не менше 107 кілограм прального порошку з мінімальними витратами. При цьому треба купувати або цілу упаковку, або не купувати її зовсім (частину упаковки придбати неможливо).

Для цього, на першому кроці, позначивши кількість упаковок вагою 35 і 24 кілограми змінними та відповідно, запишемо математичну модель розглядуваної задачі:

Далі, виходячи з того, що число невідомих задачі дорівнює двом і, як зазначалося вище, задача пакування рюкзака відноситься до класу задач лінійного цілочисельного програмування, то для її розв'язку скористаємося графічним методом.

Розв'язок задачі про рюкзак графічно

В результаті отримаємо оптимальний план і , тобто потрібно купити одну упаковку прального порошку вагою 35 кілограм і три упаковки — вагою по 24 кілограми. Мінімальні витрати при цьому складатимуть 50 умовних одиниць.

Матеріал був корисним, поділись в соціальних мережах:
Якщо тобі сподобалась дана тема, залиш свій коментар