Читайте также:
|
Формулировка любой оптимизационной задачи требует использования некоторой базовой системы понятий.
Любая переменная (изменяемая ячейка в ЭТ) обычно интерпретируется как некоторый ресурс (например, ресурс времени, материала, продукта, валюты), выраженный в количественном измерении (минуты, тонны, штуки, рубли). Задача оптимизации состоит в том, чтобы подобрать такие значения переменных, при которых целевая функция (целевая ячейка ЭТ) принимает максимальное, минимальное или заданное значение (оптимальное значение), при этом найденные значения переменных в совокупности составляют оптимальное решение задачи.
В классическом исследовании операций [1, 4—6] задачи математического программирования делятся на несколько различных типов в зависимости от вида целевой функции и ограничений. К основным типам относятся задачи линейного и нелинейного программирования. Для первого типа характерна целевая функция, линейно зависящая от переменных (ресурсов) исследуемой системы, и такие же линейные ограничения. Если же целевая функция или хотя бы одно из ограничений нелинейно зависит от переменной (хотя бы одной), задача относится к типу нелинейного программирования. В качестве примеров нелинейностей можно привести зависимости видов Xi*Xj, Xi/Xj, log(Xi) (вычисление логарифма от Xi), MIN(Xi,Xj,Xk), Xj2 (квадрат Xj) и т. д. Здесь Xi, Xj — переменные задачи.
Если оптимизационная задача должна решаться в целых числах, когда хотя бы одна из переменных модели должна измеряться в штуках (станках, автобусах и т. п.), говорят о целочисленном программировании. Наконец, если хотя бы одна из переменных может принимать только одно из двух значений (0 или 1), говорят о булевском программировании.
Вычислительные алгоритмы поиска решения для разных классов задач характеризуются разной степенью сложности, наиболее сложными являются задачи целочисленного программирования, к наиболее простым относятся задачи линейного программирования. Класс
задач линейного программирования весьма широк, эти задачи имеют наиболее эффективную реализацию и характеризуются наглядной
экономической интерпретацией результатов. Поэтому любую иссле-дуемую систему желательно привести к линейной модели. К сожалению, это не всегда возможно.
Любой вычислительный алгоритм решения оптимизационной задачи имеет характер итерационного процесса, постепенно (шаг за шагом) приближающегося к оптимальному решению. Такие процессы поиска решения характеризуются точностью вычислений, количеством итераций и временем поиска решения. Все эти характеристики определяются в разделе Параметры окна Поиск решения.
Итерационные процессы поиска должны обладать свойством сходимости вычислений. Это свойство заключается в том, что разность результатов, получаемых на л-ом и (л + 1)-ом шаге вычислений, должна с ростом л стремиться к нулю:
limn->~(Xn+1-Xn) = 0.
Здесь Хп+1, Хп— значения изменяемых ячеек на л-ой и (л + 1)-ой итерации. Практически л ограничивается конкретным значением N — количеством итераций. Количество итераций определяет число шагов d последовательности приближений текущего решения задачи к оптимальному, при этом время, затраченное на реализацию такой последовательности, определяет время поиска оптимального решения. По умолчанию в программе Solver: N = 100.
Точность вычислений оптимального решения задачи определяется количеством значащих цифр в представлении значений изменяемых ячеек Х„. Понятие точности тесно связано с понятием отклонения \XN+1 — Хn, которое может задаваться в процентах от абсолютной величины XN.
Итерационные процессы могут отличаться также методами реали-зации вычислений. Для линейных моделей используется главным образом так называемый симплекс-метод, для нелинейных — метод Ньютона и метод сопряженных градиентов. Они кратко комментируются в разделе «Поиск решения».
Контрольные вопросы
1. Какое предположение целесообразно сделать перед разработкой структуры
ЭТ для решения оптимизационной задачи?
2. Что такое размерность оптимизационной задай?
3. Что такое целевая ячейка?
4. Что такое изменяемые ячейки?.
5. Чем отличаются зависимые ячейки от ячеек исходных данных?
\
18
Часть 1. Поиск решений на электронных таблицах
Поиск решения
19
 | |||
 |
6. Чем отличаются изменяемые ячейки от ячеек исходных данных?
7. Перечислите и охарактеризуйте отношения в списке ограничений (ниспа
дающее меню) окна Добавить ограничение.
8. Какие ограничения относятся к естественным?
9. Чем полезна структура графа зависимостей для ЭТ, связанной с решением
оптимизационной задачи?
10. В каких ячейках ЭТ программа поиска размещает оптимальное решение
задачи?
11. В какой ячейке размещается оптимальное значение целевой функции?
12. Назовите и охарактеризуйте основные виды задач математического про
граммирования.
13. Какие задачи математического программирования имеют наиболее эффек
тивную реализацию на ЭТ?
14. Чем характеризуется итерационный процесс решения задачи?
15. Можно ли рассматривать целевую ячейку как разновидность зависимой?
Почему?
Дата добавления: 2015-07-16; просмотров: 93 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Быстрое начало | | | Поиск решения |