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

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

Подібні завдання легко вирішуються за допомогою надбудови Пошук рішення За аналогією з розглянутими раніше завданнями підготовлені вихідні дані (рис 438) Завдання полягає в тому, щоб за рахунок підбору значень осередків B16: B19 домогтися максимального значення цільової функції (значення комірки D20)

Рис 438 Вихідні дані до задачі про рюкзаку

На рис 439 показані обмеження на значення змінюваних клітинок

На рис 440 наводиться результат розрахунку

У багатьох практичних випадках дана постановка задачі є занадто спрощеною Далі будуть розглянуті різні варіанти ускладнення постановки завдання

Рис 439 Обмеження на значення змінюваних клітинок

Рис 440 Рішення задачі про рюкзаку

Одним з додаткових обмежень, що виникають при практичному використанні даної задачі, можуть бути обмеження на необхідну кількість предметів певних видів, які можна покласти в рюкзак При цьому можуть виникати варіанти завдання, коли потрібно строго певну кількість предметів або потрібно не менше (не більше) заданої кількості предметів

На рис 441 показані вихідні дані модифікованого варіанту завдання У цьому випадку передбачається, що в рюкзак може бути покладено не менш деякої кількості предметів

. Транспортна логістика

Рис 441 Вихідні дані до модифікованої задачі про рюкзаку

Рис 442 Обмеження на значення змінюваних клітинок для модифікованої задачі про рюкзаку

На рис 442 показані обмеження на значення змінюваних клітинок B16: B19 В даному випадку до обмежень додано умова $ B $ 16: $ B $ 19> = $ D $ 8: $ D $ 11, тобто задано мінімальну необхідну кількість предметів різних видів

Рис 443 Рішення модифікованої задачі про рюкзаку

Рішення завдання представлено на рис 443

При необхідності додаткову умову $ B $ 16: $ B $ 19> = $ D $ 8: $ D $ 11 може бути змінено Наприклад, можна встановити окремі обмеження для всіх предметів, призначивши для деяких з них точну кількість предметів, у той час як для інших – умова «не менше» або «не більше»

Джерело: Трусов А Ф Excel 2007 для менеджерів та економістів: логістичні, виробничі та оптимізаційні розрахунки (+ CD) – СПб: Питер, 2009 – 256 с: Ил

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*