Целочисленная оптимизация
К задачам целочисленного
программирования относят задачи, где некоторые переменные могут принимать только целые значения.
Пример.
Фирма выпускает два набора удобрений для газонов: обычный и улучшенный. В обычный набор входят 3 фунта азотных, 4 фунта фосфорных и 1 фунт калийных удобрений, а в улучшенный — 2 фунта азотных, 6 фунтов фосфорных и 2 фунта калийных удобрений. Известно, что для некоторого газона требуется по меньшей мере 10 фунтов азотных, 20 фунтов фосфорных и 7 фунтов калийных удобрений. Обычный набор стоит 3 долл., а улучшенный — 4 долл. Сколько и каких наборов удобрений надо купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?Решение
Как и в предыдущем примере, задачу нужно перевести на математический язык. Пусть х — количество обычных наборов удобрений, у — количество улучшенных наборов удобрений; x и y могут быть только целыми. Стоимость покупки = 3x+4y долл. Её надо минимизировать.
F(x,y) = Зx + 4у → min при ограничениях:
x - целое, y -целое,
Сделаем в Excel таблицу, начиная с ячейки А1. Таблица показана в режиме отображения формул.
Азотные удобрения (фунт) | Фосфорные удобрения (фунт) | Калиевые удобрения (фунт) | Цена (долл.) | Количество наборов (шт) | |
Обычный набор | 3 | 4 | 1 | 3 | 0 |
Улучшенный набор | 2 | 6 | 2 | 4 | 0 |
Стоимость | =3*x+4*y | ||||
Ограничения | |||||
=3*x+2*y-10 | >= | 0 | |||
=4*x+6*y-20 | >= | 0 | |||
=1*x+2*y-7 | >= | 0 | |||
x | >= | 0 | |||
y | >= | 0 | |||
х | цел | целое | |||
y | цел | целое |
закрашенным ячейкам присвоены имена:
- х - это имя ячейки, в которой находится количество обычных наборов удобрений. В ячейке число 0.
- y - это имя ячейки, в которой находится количество улучшенных наборов удобрений. В ячейке число 0.
- Стоимость - это имя ячейки с целевой функцией.
Имена ячеек использованы в формулах.
Выделим ячейку с целевой функцией "Стоимость". Вызовем Поиск решения (по другому его называют Решатель).
- Установим целевую
ячейку "Стоимость", равной минимальному значению, изменяя ячейки x,y.
- Ограничения (кроме х -целое и y - целое) введите самостоятельно.
- В окне "Параметры" установим флажок "Линейная модель" и
"Неотрицательные значения". Запустим Выполнение.
Вновь вызываем
Решатель, нажимаем кнопку "Добавить" и в диалоговом окне "Добавление
ограничения" указываем, что x — целое и y —целое. Запустим Выполнение.
На этот раз получим значение целевой функции 17 (естественно, оно ухудшилось), а количество наборов стало таким: х = 3, у = 2. Обратите внимание, что эти значения вовсе не являются результатом округления в большую сторону значений х и у, полученных без ограничения целочисленности. (Проверьте, что х = 2, у = 3 дают худший результат.)