Основы теории

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

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

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

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

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

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

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

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

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

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