Краткий экскурс в теорию

Формулировка любой оптимизационной задачи требует использо­вания некоторой базовой системы понятий.

Любая переменная (изменяемая ячейка в ЭТ) обычно интерпре­тируется как некоторый ресурс (например, ресурс времени, материа­ла, продукта, валюты), выраженный в количественном измерении (минуты, тонны, штуки, рубли). Задача оптимизации состоит в том, чтобы подобрать такие значения переменных, при которых целевая функция (целевая ячейка ЭТ) принимает максимальное, минималь­ное или заданное значение (оптимальное значение), при этом най­денные значения переменных в совокупности составляют оптималь­ное решение задачи.

В классическом исследовании операций [1, 4—6] задачи матема­тического программирования делятся на несколько различных типов в зависимости от вида целевой функции и ограничений. К основным типам относятся задачи линейного и нелинейного программирования. Для первого типа характерна целевая функция, линейно зависящая от пе­ременных (ресурсов) исследуемой системы, и такие же линейные ограничения. Если же целевая функция или хотя бы одно из ограни­чений нелинейно зависит от переменной (хотя бы одной), задача от­носится к типу нелинейного программирования. В качестве примеров нелинейностей можно привести зависимости видов Xi*Xj, Xi/Xj, log(Xi) (вычисление логарифма от Xi), MIN(Xi,Xj,Xk), Xj² (квадрат Xj) и т. д. Здесь Xi, Xj — переменные задачи.

Если оптимизационная задача должна решаться в целых числах, когда хотя бы одна из переменных модели должна измеряться в шту­ках (станках, автобусах и т. п.), говорят о целочисленном программиро­вании. Наконец, если хотя бы одна из переменных может принимать только одно из двух значений (0 или 1), говорят о булевском програм­мировании.

Вычислительные алгоритмы поиска решения для разных классов задач характеризуются разной степенью сложности, наиболее слож­ными являются задачи целочисленного программирования, к наибо­лее простым относятся задачи линейного программирования. Класс

задач линейного программирования весьма широк, эти задачи имеют наиболее эффективную реализацию и характеризуются наглядной

экономической интерпретацией результатов. Поэтому любую иссле-дуемую систему желательно привести к линейной модели. К сожале­нию, это не всегда возможно.

Любой вычислительный алгоритм решения оптимизационной за­дачи имеет характер итерационного процесса, постепенно (шаг за ша­гом) приближающегося к оптимальному решению. Такие процессы поиска решения характеризуются точностью вычислений, количест­вом итераций и временем поиска решения. Все эти характеристики определяются в разделе Параметры окна Поиск решения.

Итерационные процессы поиска должны обладать свойством схо­димости вычислений. Это свойство заключается в том, что разность результатов, получаемых на л-ом и (л + 1)-ом шаге вычислений, дол­жна с ростом л стремиться к нулю:

lim_n->~(X_n+1-X_n) = 0.

Здесь Х_п+1, Х_п— значения изменяемых ячеек на л-ой и (л + 1)-ой итерации. Практически л ограничивается конкретным значением N — количеством итераций. Количество итераций определяет число шагов d последовательности приближений текущего решения задачи к опти­мальному, при этом время, затраченное на реализацию такой после­довательности, определяет время поиска оптимального решения. По умолчанию в программе Solver: N = 100.

Точность вычислений оптимального решения задачи определяет­ся количеством значащих цифр в представлении значений изменяе­мых ячеек Х„. Понятие точности тесно связано с понятием отклоне­ния \X_N+1 — Хn, которое может задаваться в процентах от абсолютной величины X_N.

Итерационные процессы могут отличаться также методами реали-зации вычислений. Для линейных моделей используется главным об­разом так называемый симплекс-метод, для нелинейных — метод Ньютона и метод сопряженных градиентов. Они кратко комментиру­ются в разделе «Поиск решения».

Контрольные вопросы

1. Какое предположение целесообразно сделать перед разработкой структуры

ЭТ для решения оптимизационной задачи?

2. Что такое размерность оптимизационной задай?

3. Что такое целевая ячейка?

4. Что такое изменяемые ячейки?.

5. Чем отличаются зависимые ячейки от ячеек исходных данных?

\

18

Часть 1. Поиск решений на электронных таблицах

Поиск решения

19

6. Чем отличаются изменяемые ячейки от ячеек исходных данных?

7. Перечислите и охарактеризуйте отношения в списке ограничений (ниспа­
дающее меню) окна Добавить ограничение.

8. Какие ограничения относятся к естественным?

9. Чем полезна структура графа зависимостей для ЭТ, связанной с решением
оптимизационной задачи?

10. В каких ячейках ЭТ программа поиска размещает оптимальное решение
задачи?

11. В какой ячейке размещается оптимальное значение целевой функции?

12. Назовите и охарактеризуйте основные виды задач математического про­
граммирования.

13. Какие задачи математического программирования имеют наиболее эффек­
тивную реализацию на ЭТ?

14. Чем характеризуется итерационный процесс решения задачи?

15. Можно ли рассматривать целевую ячейку как разновидность зависимой?
Почему?