—>Информационные технологии —>
Целочисленная оптимизация
К задачам целочисленного программирования относят задачи, где некоторые переменные могут принимать только целые значения.
Пример.
Фирма выпускает два набора удобрений для газонов: обычный и улучшенный. В обычный набор входят 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 — целое) введите са мостоятельно.
- В окне «Параметры» установим флажок «Линейная модель» и «Неотрицательные значения». Запустим Выполнение.
Поиск решения вернет результат: х=1.5, у = 2.75. Целевая функция равна 15.5. Но наборы удобрений нельзя покупать частями! Нужно наложить еще одно ограничение: х, у — целые числа.
Вновь вызываем Решатель, нажимаем кнопку «Добавить» и в диалоговом окне «Добавление ограничения» указываем, что x — целое и y —целое. Запустим Выполнение.
На этот раз получим значение целевой функции 17 (естественно, оно ухудшилось), а количество наборов стало таким: х = 3, у = 2. Обратите внимание, что эти значения вовсе не являются результатом округления в большую сторону значений х и у, полученных без ограничения целочисленности. (Проверьте, что х = 2, у = 3 дают худший результат.)
Источник