· планирование перевозок— минимизация затрат на транспортировку товаров;
· составление смеси — достижение заданного качества смеси при наименьших расходах;
· прочие разнообразные задачи оптимального распределения ресурсов и оптимального проектирования и т.д.
При постановке задачи оптимизации определяют:
1) целевую функцию (критерий оптимизации) F = (xj) → max (min, const), которая показывает, в каком смысле решение должно быть оптимальным, т.е. наилучшим. Возможны три вида целевой функции: максимизация, минимизация, назначение заданного значения.
2) ограничения gi (xj) ≤ (=; ≥) bi, которые устанавливают зависимости между переменными; могут быть односторонними и многосторонними.
3) граничные условияdj≤ xj≤ Dj, которые показывают, в каких пределах могут быть значения искомых переменных в оптимальном решении.
Решение задачи, удовлетворяющее всем ограничениям и граничным условиям, называется допустимым.
Важная xaрактеристика задачи оптимизации — ее размерность, которая определяется числом переменных п и числом ограничений т.
Прип < тзадачи решения не имеют. Необходимымтребованием задач оптимизации является условие п > т.
Систему уравнений, для которых п = трассматривают как задачу оптимизации, имеющую одно допустимое решение (ее можно решать как обычную задачу оптимизации, назначая в качестве целевой функции любую переменную).
Итак, задача имеет оптимальное решение, если она удовлетворяет двум требованиям:
· имеет более одного решения, т.е. существуют допустимые решения;
· имеется критерий, показывающий, в каком смысле принимаемое решение должно быть оптимальным, т.е. наилучшим из допустимых.
В Ехсе1 для оптимизации могут быть применен ряд надстроек и средств, таких как «Поиск решения», «Таблицы подстановки», «Подбор параметра».
Вопрос 2. Использование средства Ехсе1 «Подбор параметра» и «Таблицы подстановки» для улучшения характеристик модели.
«Таблицы подстановки» служат для решения задач, когда значение одной или двух исходных величин требуется изменить с целью определения наилучшего итога в случае использования их конкретных значений. Необходимым условием для выполнения подобных задач является ввод формулы, связывающей рассчитываемые параметры с исходными.
Формула в таблицах подстановки с одной исходной величиной должна находиться на одну строку выше и на один столбец правее первого значения изменяемой величины, при этом значения должны быть организованы в столбец ниже первого.
В задачах, включающих две исходные величины, формула и исходные величины, значение одной из которых организованы в столбец, а другой – в строку, должны образовывать прямоугольник (формула, таким образом, может занимать его левый верхний угол).
Средство Excel «Подбор параметра» используется в случае необходимости нахождения точки равновесия, т.е. оптимального параметра. Таким образом, например, может быть найдено количество выпускаемых товаров, уравновешивающее затраты и прибыль предприятий по их выпуску и реализации.
Диалоговое окно «Подбор параметра» предлагает установить в ячейке, содержащей формулу разности между уравновешиваемыми параметрами, значение 0, изменяя значение ячейки, оказывающей непосредственное влияние на решение поставленной задачи. Задача будет решена, если каждый из параметров задать формулой, в которой будет ссылка на влияющую ячейку.
Для решения поставленной задачи графическим способом следует использовать «Мастер диаграмм», однако прежде следует произвести расчет, используя «Таблицу подстановки» с одной исходной величиной.
Вопрос 3. Оптимизация модели процедурой Поиск решения.
В MSExcel существует возможность с помощью надстройки Поиск решения найти решение, оптимальное в некотором смысле при нескольких входных значениях и наборе ограничений на решение.
Диспетчер сценариев способен запомнить несколько решений, найденных данным средством и сгенерировать на этой основе отчет.
С помощью надстройки Поиск решенияможно решать как линейные задачи (задачи линейного, целочисленного и стохастического программирования), так и нелинейные (задачи нелинейного программирования).
Работа по решению некоторой оптимизационной задачи всегда
начинается с построения математической модели, для чего необходимо ответить на следующие вопросы:
- каковы переменные модели (для определения каких величин строится модель)?
- в чем состоит цель, для достижения которой из множества всех допустимых значений переменных выбираются оптимальные?
- каким ограничениям должны удовлетворять неизвестные?
Стоит также учесть, что при конструировании модели формулировка ограничений является самой ответственной частью конструкции. В некоторых случаях ограничения очевидны, например ограничение на количество сырья. Другие же ограничения могут быть менее очевидны и могут быть указаны неверно.
Например:
- в модели с несколькими периодами времени величина материального ресурса на начало следующего периода должна равняться величине этого ресурса на конец предыдущего периода;
- в модели поставок величина запаса на начало периода плюс количество полученного должна равняться величине запаса на конец периода плюс количество отправленного;
- многие величины в модели по своему физическому смыслу не могут быть отрицательными, например, количество полученных единиц товара.
Таким образом, на данном этапе делаются выводы об исходных данных (детерминированные или случайные), искомых переменных (непрерывные или дискретные), о пределах, в которых могут находиться значения искомых величин, о зависимостях между переменными (линейные или нелинейные), о критериях, по которым необходимо находить оптимальное решение.
Сюда же входит преодоление несовместности, а также неограниченности целевой функции: при максимизации целевой функции область допустимых решений должна быть ограничена сверху, при минимизации — ограничена снизу.
Для решения задачи с помощью надстройки Поиск решения прежде всего следует подготовить рабочий лист MSExcel, корректно разместить на нем все исходные данные, грамотно ввести необходимые формулы для целевой функции и для других зависимостей, выбрать место для значений переменных. Правильно ввести все ограничения, переменные, целевую функцию и другие значения в окно Поиск решения.
Поскольку большую часть задач оптимизации представляют собой задачи линейного программирования, т.е. такие, у которых критерий оптимизации и ограничения — линейные функции, в окне Параметры поиска решения следует установить флажок Линейная модель. Это обеспечит применение симплекс-метода. В противном случае даже для решения линейной задачи будут использоваться более общие (т.е. более медленные) методы.
Решая задачи с нелинейными зависимостями, следует:
- ввести предварительно предположительные значения искомых переменных (иногда легко получить графическое представление решения и сделать приблизительные выводы о решении);
- в окне Параметры поиска решения снять (если установлен) флажок Линейная модель.
Решая задачи целочисленного программирования, не следует забывать также о требованиях целочисленности.
Приведем описание диалоговых окон надстройки Поиск решения.
Опции настройки диалогового окна Поиск решения.
| Опция | Описание |
| Установить целевую ячейку | Указывается ячейка, содержащая целевую функцию (критерий оптимизации) рассматриваемой задачи |
| Равной | Следует выбрать из трех переключателей (максимальному значению, минимальному значению) тот, который определяет тип взаимосвязи между решением и целевой ячейкой |
| Изменяя ячейки | Указываются ячейки, которые должны изменяться в процессе поиска решения задачи (т.е. ячейки, которые являются переменными задачи) |
| Ограничения | Отображаются ограничения, налагаемые на переменные задачи. Допускаются ограничения в виде равенств, неравенств, а также – требование целочисленности переменных. Ограничения добавляются по одному с помощью кнопки Добавить |
| кнопка Параметры | Позволяет изменять условия и варианты поиска решений исследуемой задачи, а также загружать и сохранять оптимизируемые модели. Значения и состояния элементов управления, используемые по умолчанию, подходят для решения большинства задач. |
При нажатии кнопки Параметры в окне Поиск решения открывается окно Параметры поиска решения.
Опции настройки диалогового окна Параметры поиска
| Опция | Описание |
| Максимальное время | Ограничивает время, отпускаемое на поиск решения задачи |
| Предельное число операций | Ограничивает число промежуточных вычислений |
| Относительная погрешность | Определяют точность, с которой ищется решениеРекомендация. После нахождения решения с величинами данных параметров, заданными по умолчанию, повторите вычисления с большей точностью и меньшим допустимым отклонением и сравните с первоначальным решением. |
| Допустимое отклонение | |
| Линейная модель | Служит для поиска решения линейной задачи оптимизации или нелинейной аппроксимации нелинейной задачи. В случае нелинейной задачи флажок Линейная модель должен быть сброшен, в случае линейной задачи – установлен, т.к. иначе возможно получение неверного результата. |
| Показывать результаты итераций | Для приостановки поиска решений и просмотров отдельных итераций |
| Автоматическое масштабирование | Предназначен для включения автоматической нормализации входных и выходных значений, качественно различающихся по величине |
| Оценки | Служит для выбора метода экстраполяции |
| Разности | Группа предназначена для выбора метода численного дифференцирования |
| Метод поиска | Служит для выбора алгоритма оптимизации |
При необходимости может быть проведен анализ решениязадачи оптимизации: добавляют представление решения в виде графиков или диаграмм, а также можно получить и отчет о поиске решения.