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

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

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

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

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

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

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

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

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

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

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

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

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

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

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