Целочисленная оптимизация

К задачам целочисленного программирования относят задачи, где некоторые переменные могут принимать только целые значения.

Пример.

Фирма выпускает два набора удобрений для газонов: обычный и улучшенный. В обычный набор входят 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
целцелое


закрашенным ячейкам присвоены имена:

  1. х - это имя ячейки, в которой находится количество обычных наборов удобрений. В ячейке число 0.
  2. y - это имя ячейки, в которой находится количество улучшенных наборов удобрений. В ячейке число 0.
  3. Стоимость - это имя ячейки с целевой функцией.

Имена ячеек использованы в формулах.

Выделим ячейку с целевой функцией "Стоимость". Вызовем Поиск решения (по другому его называют Решатель).

  1. Установим целевую ячейку "Стоимость", равной минимальному значению, изменяя ячейки x,y.
  2. Ограничения (кроме х -целое и y - целое) введите самостоятельно.
  3. В окне "Параметры" установим флажок "Линейная модель" и "Неотрицательные значения". Запустим Выполнение.
Поиск решения вернет результат: х=1.5, у = 2.75. Целевая функция равна 15.5. Но наборы удобрений нельзя покупать частями! Нужно наложить еще одно ограничение: х, у — целые числа.

Вновь вызываем Решатель, нажимаем кнопку "Добавить" и в диалоговом окне "Добавление ограничения" указываем, что x — целое и y —целое. Запустим Выполнение.

На этот раз получим значение целевой функции 17 (естественно, оно ухудшилось), а количество наборов стало таким: х = 3, у = 2. Обратите внимание, что эти значения вовсе не являются результатом округления в большую сторону значений х и у, полученных без ограничения целочисленности. (Проверьте, что х = 2, у = 3 дают худший результат.)