Основные этапы работ при принятии оптимальных решений.
1.Выбор задачи – это важнейший вопрос. Если задача выбрана неудачно, то она может и не решиться методами оптимизации.
Задача должна удовлетворять требованиям:
§ Должно существовать минимум два варианта ее решения. Если вариантов решения нет, значит и выбирать не из чего.
§ Надо четко знать, в каком смысле искомое решение должно быть наилучшим. Если мы четко не знаем, чего хотим, то математические методы, реализованные даже на самом лучшем компьютере не помогут.
Выбор задачи завершается ее содержательной постановкой.
2.Содержательная постановка – формулировка задачи в такой форме, на основании которой было бы ясно, каковы элементы математической модели.
§ Исходные данные: величины итерминированные или случайные.
§ Искомые переменные: непрерывные или дискретные.
§ Пределы, в которых могут находиться значения искомых величин в оптимальном решении.
§ Зависимости между переменными: линейные или нелинейные.
§ Критерии, по которым следует находить оптимальное решение.
Хорошо сформированная содержательная постановка – основа успешного составления математической модели.
3.Составление математической модели – очень ответственный этап работ.
4.Сбор исходных данных. Необходимо собрать лишь те данные, которые входят в математическую модель. Следовательно, сбор данных необходимо производить лишь после того, как будет сформулирована математическая модель.
5.Решение задачи.
6.Анализ решения.
7.Принятие оптимального решения – конечный этап работы. Решение принимает не компьютер, а тот человек, который должен ответить за результаты принятого решения.
8.Графическое представление результата – мощный фактор наглядности информации, необходимой для принятия решения.
Пример решения задач оптимизации.
Excel предлагает мощный инструмент для решения оптимизационных задач, т.е. таких задач, в которых необходимо найти экстремальное значение (min или max) некоторой функции, называемой целевой, при заданных ограничениях.
Если целевая функция и/или ограничения линейны, то такие задачи принято называть задачами линейного программирования.
Многие экономические задачи решаются в рамках линейного программирования. Целевой функцией в них является либо прибыль или объем производства, которые надо максимизировать, либо затраты (издержки), которые надо минимизировать.
Ограничения – это обычно условия, которые накладываются на используемые ресурсы для производства продукции.
Построив математическую модель и решив задачу в заданных ограничениях, можно поварьировать ограничениями, т.е. речь уже идет о математическом моделировании экономических систем с помощью Excel.
Рассмотрим задачу.
В цехе, площадью 74м2 необходимо установить станки, на приобретение которых отпущено 420 тыс.руб.
Существует два типа станков. Станок первого типа стоимостью 60 тыс.руб., требующий 12м2 производственных площадей обеспечивает изготовление 70 изделий в смену. Аналогичные характеристики станка второго типа составляют соответственно 40 тыс.руб., 6м2, 40 изделий в смену.
Найти оптимальный вариант приобретения станков, обеспечивающих max производство изделий в цехе.
Обозначим Х1 количество станков первого типа, а Х2 – количество станков второго типа, которые предполагается установить в цехе.
Тогда количество изделий, которое будет произведено на этих станках равно
Это и есть целевая функция, которую нужно максимизировать.
Теперь запишем ограничения. Их в задаче два.
Ограничения по финансам:
тыс.руб.
Ограничения по площади размещения:
м2
Кроме этих ограничений следует добавить очевидные ограничения:
- переменные задачи должны быть неотрицательные
- переменные задачи должны быть целочисленные
Итак, математическая модель сформулирована
|
Решение оптимизационных задач в Excel проводится с помощью специализированной программы Поиск решения, вызываемой из Главного меню: Сервис–Поиск решения.
Если в выпадающем меню Сервис нет пункта Поиск решения, то нужно выбрать в меню Сервис пункт Надстройки и там отметить галочкой Поиск решения.
Таким образом, теперь задача состоит в том, чтобы перенести математическую модель в Excel.
Алгоритм следующий
1.Отводим ячейки для каждой независимой переменной задачи. В нашем примере это ячейки В4 для Х1 и ячейка В5 для Х2. Их оставляют пустыми.
2.Отводим ячейку С13 для целевой функции и набираем в ней соответствующую формулу:
=В4*Е4+В5*Е5
В формуле в качестве переменных фигурируют адреса ячеек, где расположены соответствующие переменные. Константы задачи заданы не числами, а также ссылками на ячейки, в которых их необходимо разместить.
3.Отводим ячейки (А13 и В13) для создания
| A | B | C | D | E | |
| Тип | Кол-во шт. | Стоимость тыс.руб. | Площадь кв.м. | Произв. Дет/смен | |
| Стан 1 типа | |||||
| Стан 2 типа | |||||
| Ограничения | |||||
| По стоимости | По площади | ||||
| Выполнение ограничений по стоимости по площади | Производство деталей | ||||
| =В4*С4+В5*С5 | =В4*D4+B5*D5 | =В4*Е4+В5*Е5 | |||
формул, соответствующих левой части каждого ограничения:
=В4*С4+В5*С5
=В4*D4+B5*D5
4. Открываем диалоговое окно Поиск решения.
5. В поле Установить целевую ячейку указываем адрес ячейки, в которой находится формула для расчета целевой функции (С13). Ниже указываем тип оптимизации (поиск max и min).
6. В поле Изменяя ячейки отмечаем адреса ячеек, где находятся независимые переменные задачи (В4 и В5).
7. Для того, чтобы ввести ограничения, нужно нажать на кнопку Добавить. Появляется диалоговое окно Добавления ограничения.
В левое поле вводим адрес ячейки, где находятся ограничения (или диапазон адресов), в центральном поле выбираем знак операции отношения (а также задаем целочисленность переменных), в правом поле задаем адрес ячейки (или диапазон адресов), где находятся правые части ограничений.
Вместо адресов в правой части можно просто задать числовые значения.
Нажатием клавиши Добавить переходим в режим добавления следующего ограничения, нажатием клавиши ОК заканчиваем ввод ограничений.
Теперь, если необходимо, в поле Ограничения окна Поиск решения можно выбирать какие-либо ограничения и редактировать их или удалять
8. Запускаем процесс вычислений нажатием кнопки Выполнить. Решение: заданным ограничениям удовлетворяет следующий парк станков: 3 – первого типа, 6 – второго типа; при этом будет изготовлено max количество деталей – 450.
В окне Поиск решения с помощью кнопки Параметры можно вызвать диалоговое окно Параметры поиска решения.
С помощью элементов этого окна можно установить время, отпущенное на поиск решения задачи, и число промежуточных вычислений (операций) соответственно.
Задать точность, с которой ищется решение.
Установить вид зависимости модели (линейная, нелинейная) и другие параметры.
Понятие алгоритма.
Слово «Алгоритм» происходит от «algorithmi» латинского написания имени аль-Хорезми, под которым в средневековой Европе знали величайшего математика из Хорезма (город в Узбекистане) Мухаммеда бен Нусу, жившего в 783-850 г.г.
В своей книге «Об индийском счете» он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними столбиком.
Алгоритм – точное предписание, определяющее последовательность действий, обеспечивающих получение требуемого результата их исходных данных.
Алгоритм может быть предназначен для выполнения его человеком или автоматическим устройством. Создание алгоритма, пусть даже самого простого – процесс творческий. Он доступен исключительно живым существам, а долгое время считалось, что только человеку.
Другое дело – реализация уже имеющего алгоритма. Ее можно поручить субъекту или объекту, который не обязан вникать в существо дела, а возможно и не способен его понять.
Такой субъект или объект принято называть формальным исполнителем.
Пример – стиральная машина-автомат, которая неукоснительно исполняет предписанные ей действия, даже если вы забыли положить в нее порошок.
Человек тоже может выступать в роли формального исполнителя, но в 1-ю очередь формальными исполнителями являются различные автоматические устройства, и компьютер в том числе.
Каждый алгоритм создается в расчете на вполне конкретного исполнителя.
Т.е. действия, которые может совершать исполнитель, называются его допустимыми действиями.
Совокупность допустимых действий образует систему команд исполнителя.
Алгоритм должен содержать только те действия, которые допустимы для данного исполнителя.
Свойства алгоритмов.
Формулирует несколько общих свойств алгоритмов, позволяющих отличать алгоритмы от других инструкций.
1. Дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (ранее определенных) шагов.
Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.
2. Определенность – каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
3. Результативность (конечность) – алгоритм должен приводить к решению задачи за конечное число шагов.
4. Массовость – алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
Правила выполнения арифметических операций или геометрических построений представляют собой алгоритмы.
Алгоритм – искусственная конструкция, которую мы сооружаем для достижения своих целей. Чтобы алгоритм выполнил свое предназначение, его необходимо строить по определенным правилам.
1 правило – при построении алгоритма, прежде всего, необходимо задать множество объектов, с которыми будет работать алгоритм. Формализованное (закодированное) представление этих объектов носит название данных.
Алгоритм приступает к работе с некоторым набором данных, которые называются входными, и в результате своей работы выдает данные, которые называются выходными. Таким образом, алгоритм преобразует входные данные в выходные.
2 правило – для работы алгоритма требуется память. В памяти размещаются входные данные, с которыми алгоритм начинает работать, промежуточные данные и выходные данные, которые являются результатом работы алгоритма.
Память является дискретной, т.е. состоящей из отдельных ячеек. Поименованная ячейка памяти носит название переменной.
В теории алгоритмов размеры памяти не ограничиваются, т.е. считается, что мы можем предоставить алгоритму любой необходимый для работы объем памяти.
В языках программирования распределение памяти осуществляется операторами описания переменных.
3 правило – дискретность. Алгоритм строится из отдельных шагов (действий, операций, команд). Множество шагов, из которых составлен алгоритм, конечно.
4 правило – детерминированность (связан). После каждого шага необходимо указывать, какой шаг выполняется следующим, либо давать команду остановки.
5 правило – сходимость (результативность). Алгоритм должен завершить работу после конечного числа шагов. При этом необходимо указать, что считать результатом работы алгоритма.
Итак, алгоритм каждому набору входных данных ставит в соответствие некоторый набор выходных данных.
Виды алгоритмов.
1 Механические алгоритмы задают определенные действия, обозначая их в последовательности, обеспечивая однозначный требуемый результат. (например, алгоритм работы машины, двигателя и т.п.).
2 Вероятные алгоритмы дают программу решения задачи несколькими путями млм способами, приводящими к вероятному достижению результата.
3. Эвристические алгоритмы (от греческого слова «эврика») – это алгоритмы, в которых достижение конечного результата однозначно не не предопределено и не обозначена вся последовательность действий. Пример – инструкции и предписания.
В этих алгоритмах используются универсальные логические процедуры, и способы принятия решений, основанные на аналогиях, ассоциациях и прошлом опыте решения схожих задач.
4 Линейные алгоритмы – наборы команд (указаний), выполняемых последовательно во времени друг за другом.
5 Разветвляющиеся алгоритмы – алгоритмы, содержащие хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из 2-х возможных шагов.
6 Циклические алгоритмы предусматривают многократное повторение одного и того же действия над новыми исходными данными. К циклическим алгоритмам сводится большинство методов вычислений, перебора вариантов
Цикл программы – последовательность команд, которая может выполняться многократно до удовлетворения некоторого условия.