Алгоритм решения оптимизационной задачи с использованием табличного процессора 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 ввести целевую функцию.

ABCD 1Оптимальное планирование 2 3Основные показатели 4 X (пирожков) Y (пирожных) 5 6 7Ограничения 8 9 Левая частьЗнакПравая часть 10Время производства=B5+4*C5= Целевая функция=B5+2*C5 18

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

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

В появившемся диалоговом окне «Добавление ограничения» ввести ссылку на ячейку В10, выбрать из меню знак неравенства

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

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

A BBBB C D 1 Оптимальное планирование 2 3 Плановые показатели 4 X(пирожки) У (пирожные) Ограничения 8 9 Левая часть Знак Правая часть 10 Время производства: 1000 = Целевая функция

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

Полученная электронная таблица и настроенная на нее сервисная функция «Поиск решения» являются средством, с помощью которого можно решать задачу оптимального планирования при меняющихся условиях. Например, может измениться длина рабочего дня. Тогда надо внести новое значение в ячейку D10 и оптимальный план автоматически пересчитается. Так же может измениться допустимое суммарное число изделий в ячейке D11. Следует иметь в виду, что при решении подобных задач искомого оптимального решения может и не быть – тогда программа об этом сообщит.