Поиск решения EXCEL (3.3). Минимизация оставшегося места на диске (задача о сумме подмножеств)

history

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


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

Задача1

Необходимо заполнить DVD диск файлами, так чтобы оставшееся пустое место было минимальным. В наличии имеется достаточно большое количество файлов (общий размер примерно соответствует 3-м DVD).

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



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

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

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

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

При большом избытке файлов, подобрать нужные, как правило, для Поиска решения не составляет труда. Если поиск затягивается, то в Параметрах Поиска решения установите целочисленное ограничение 5%. Ниже рассмотрим задачу, в которой требуется записать по дискам все имеющиеся файлы.

Задача 2

Необходимо записать файлы на минимальное количество DVD дисков (см. файл примера лист Задача (3 диска) ).

Решение . Определив требуемое количество дисков (в нашем случае 3), создадим модель для записи на 3 диска. Если процент заполнения дисков будет близок к 100% (на всех дисках практически не останется свободного места), то Поиску решения будет сложно найти решение (поиск может затянуться на несколько минут или больше, в зависимости от количества дисков и файлов). Решения вообще может не существовать (т.к. модель линейная, то можно быть уверенным, что если Поиску решения не удалось найти решения, то его действительно нет).


Комментарии

Только для авторизованных пользователей

(только для авторизованных пользователей)

© Copyright 2013 - 2024 Excel2.ru. All Rights Reserved