'

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

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

А теперь перейдем к формализации стратегической цели: получение максимальной выручки. Выручка - это стоимость всей проданной продукции. Пусть цена одного пирожка – 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.


Слайд 7

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


Слайд 8

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


Слайд 9

   


Слайд 10

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


Слайд 11

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


Слайд 12

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


Слайд 13


Слайд 14

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


Слайд 15

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


Слайд 16

   


Слайд 17

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


Слайд 18

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


×

HTML:





Ссылка: