Поиск решения EXCEL (3.2). Минимизация потерь (задача о рюкзаке)

Создадим модель для одной из модификаций классической задачи о рюкзаке: укладка как можно большего числа вещей в рюкзак при условии, что общий объём (или вес) всех предметов, способных поместиться в рюкзак, ограничен. Расчет будем проводить с помощью надстройки Поиск решения.

Существует множество разновидностей задачи о рюкзаке, отличия заключаются в условиях, наложенных на рюкзак, на предметы или их выбор. Рассмотрим Рюкзак 0-1 (англ. 0-1 Knapsack Problem): не более одного экземпляра каждого предмета (пример с сайта ]]> www.solver.com ]]> ).

Задача

Бензовоз с 4-мя цистернами разного объема должен выполнить заказ: перевезти определенное количество топлива трех разных типов. К сожалению, суммарный объем цистерн меньше, чем объем заказа. За невыполненный заказ взимается штраф, размер которого пропорционален объему невыполненного заказа. Необходимо минимизировать размер штрафа, заполнив цистерны топливом оптимальным образом.

Создание модели

На рисунке ниже приведена модель, созданная для решения задачи (см. файл примера ).

Переменные (выделено зеленым) . В качестве переменных модели следует взять загрузку цистерн разными видами топлива. Поиск решения подбирает как сам вид топлива, который нужно перевозить, так и его объем. Ограничения (выделено синим) . Объем перевозимого топлива не должен превышать объем цистерн, а также как можно ближе к требованиям заказа. Целевая функция (выделено красным) . Сумма штрафа должна быть минимальна.

Примечание : для удобства настройки Поиска решения используются именованные диапазоны .

Вводная статья про Поиск решения в MS EXCEL 2010 находится здесь .