Лабораторная работа №3 "Поиск оптимального решения средствами Microsoft Excel"
Цель работы: целью данной лабораторной работы ставится ознакомление с возможностью нахождения оптимального решения, используя опцию Поиск Решения в пакете Microsoft Excel.
Краткие сведения из теории
Термин оптимизация происходит от латинского слова optimum, что означает наилучший. Оптимизация – это процесс выбора наилучшего варианта из всех допустимых.
В общем случае имеется:
Математическая
модель объекта
,
где (х)
– варьируемые параметры или сам объект.
Имеется целевая функция ЦФ (критерий
оптимальности, критерий качества).
.
Имеются также ограничения, которые
определяют максимальный диапазон
варьирования параметров. Ограничения
на функцию бывают либо типа равенств,
либо типа неравенств.
Задача состоит в том, что из множества допустимых значений варьируемых параметров, описаных системой ограничений найти оптимальное, как правило, единственное значение совокупности варьируемых параметров, при котором достигается наибольшая (наименьшая) из допустимых значений целевой функции.
К линейным задачам оптимизации (задачам линейного программирования) относятся такие, в которых целевая функция линейна, все ограничения линейны, а все варьируемые переменные неотрицательны.
Существует несколько методов решения задач линейного программирования.
Графический метод (Хорош при 2-3 варьируемых параметрах)
Метод перебора (хорош при небольшом числе варьируемых параметрах). Суть метода перебора состоит в следующем. Все ограничения в виде неравенств преобразуются в раввенство. Образующаяся система уравнений ограничений решается и находятся все точки пересечения этих уравнений между собой. После нахождения множества вершин отбрасываются те, которые лежат вне области допустимых значений.
При большом числе варьируемых параметров и ограничений очень тяжело найти оптимальные пераметры путем перебора всех вершин. Симплекс-метод. Этот метод использует ту же идею, что и метод перебора. Разработан американским ученым Джорджем Данцигом. Но перебор идет не целенаправлено, а всоответствии с определенным планом: просмотр многогранника ограничений ведется по соседним вершинам, просмотр ведется таким образом, что значение ЦФ возрастает шаг за шагом.
Для решения задачи поиска оптимального решения используются готовые программы, разработанные на ПЭВМ. Одной из программ подобного типа является опция Поиск Решения в пакете в пакете Microsoft Excel.
Поиск решения позволяет решать задачи как линейного так и нелинейного математического программирования.
Для линейной оптимизации используются алгоритмы симплексного метода и метода «ветвей и границ» (branch-and-bound), которые разработаны Джоном Уотсоном (John Watson) и Деном Филстра (Dan Fylstra) из Frontline Systems, Inc.
Для нелинейной оптимизации используется алгоритм Generalized Reduced Gradient (GRG2) (Обобщенный Уменьшенный Градиент), разработанный Леоном Ласдоном (Leon Lasdon, University of Texas at Austin) и Аланом Уореном (Allan Waren, Cleveland State University).