Алгоритм решения оптимизационной задачи с использованием табличного процессора Excel

Кондитерский цех техникума готовит пирожки и пирожные. В силу ограниченности складских помещений за день можно приготовить в совокупности не более 700 изделий. Рабочий день в кондитерском цехе длится 8 часов. Если выпускать только пирожные, за день можно произвести не более 250 штук, пирожков же можно произвести 1000, если при этом не выпускать пирожных. Стоимость пирожного вдвое выше чем пирожка. Требуется составить дневной план производства, обеспечивающий кондитерскому цеху наибольшую выручку.

Выработаем математическую модель задачи.
Плановыми показателями являются:
x - дневной план выпуска пирожков;
y - дневной план выпуска пирожных.
Ресурсы производства:
длительность рабочего дня - 8 часов;
вместимость складских помещений – 700 мест.
Предполагается для простоты, что другие ресурсы неограничены (сырье, электроэнергия и пр.)

Если обозначить время изготовления пирожка – t мин, то время изготовления пирожного будет – 4t мин. Значит суммарное время на изготовление x пирожков и y пирожных равно
tx+4ty=(x+4y)t.
Но это время не может быть больше длительности рабочего дня. Отсюда следует неравенство:

Легко вычислить t – время изготовления одного пирожка. Поскольку за рабочий день их может быть изготовлено 1000 штук, то на один пирожок затрачивается 480/1000=0,48 мин. Подставляя это значение в неравенство, получим:
или
Ограничение на общее число изделий дает совершенно очевидное неравенство
.

К двум полученным неравенствам следует добавить условия положительности значений величин x и y (не может быть отрицательного числа пирожков и пирожных). В итоге мы получаем систему неравенств:

А теперь перейдем к формализации стратегической цели: получение максимальной выручки. Выручка - это стоимость всей проданной продукции. Пусть цена одного пирожка – r рублей. По условию задачи, цена пирожного в два раза больше, то есть 2r рублей. Отсюда стоимость всей произведенной за день продукции равна
rx+2ry=r(x+2y).
Будем рассматривать записанное выражение как функцию от x,y:
f(x,y)=r(x+2y).
Она называется целевой функцией.
Поскольку значение r – константа, то максимальное значение f(x,y) будет достигнуто при максимальной величине выражения (x+2y).Поэтому в качестве целевой функции можно принять
f(x,y)=x+2y.

Следовательно, получение оптимального плана свелось к следующей математической задаче: найти значения плановых показателей x и y, удовлетворяющей системе неравенств, полученных выше, при которых указанная целевая функция принимает максимальное значение.
Компьютерная модель. Будем искать решение задачи путем создания и исследования компьютерной модели в электронных таблицах Excel.

Оптимизационное моделирование
Ячейки В5 и С5 выделить для хранения значений параметров x и y.
Ниже этих ячеек представить систему неравенств, определяющую ограничения на искомые решения
В ячейку В15 ввести целевую функцию.

Исследование модели. Для поиска оптимального решения задачи использовать надстройку электронных таблиц Поиск решения. Для этого выполнить команду Сервис => Поиск решения. На экране появится соответствующая форма.

Далее нужно выполнить следующий алгоритм:
1. Ввести координату ячейки с целевой функцией. В нашем примере это В15.
2. Поставить отметку «максимальному значению», то есть сообщить программе, что нас интересует нахождение максимума целевой функции.
3. В поле «Изменяя ячейки» ввести В5:С5, то есть сообщить, какое место отведено под значения переменных – плановых показателей.
4. В поле «Ограничения» надо ввести информацию о неравенствах - ограничениях, которые имеют вид В10<=D10; B11<=D11; B12>=D12; B13>=D13. Ограничения вводятся следующим образом:
=> щелкнуть по кнопке «Добавить»;

=> щелкнуть по кнопке «Добавить»;
В появившемся диалоговом окне «Добавление ограничения» ввести ссылку на ячейку В10, выбрать из меню знак неравенства <= и ввести ссылку на ячейку D10; снова щелкнуть по кнопке «добавить» и аналогично ввести второе ограничение B11<=D11 и так далее. В конце надо щелкнуть по кнопке ОК.
Закрыть диалоговое окно «Добавление ограничения».
Снова появится форма «Поиск решения»

Теперь надо дать последние указания: задача является линейной. Для этого следует щелкнуть по кнопке «Параметры» - появится форма «Параметры поиска решения».

1. Надо выставить флажки на переключателях «Линейная модель», «Прямые разности», «Метод поиска Ньютона» и щелкнуть по кнопке ОК, что возвратит нас в форму «Поиск решения».
2. Вся информация введена. Далее надо щелкнуть по кнопке «Выполнить» - мгновенно в ячейках В5 и С5 появится оптимальное решение (числа 600 и 100), а также число 800 в ячейке В15 – максимальное значение целевой функции.

Результаты решения задачи.
Кроме того, на экране появится еще одна форма – «Результаты поиска решения»