Структура оптимизационных задач

Все оптимизационные задачи имеют общую структуру. Оптимизационные задачи есть задачи минимизации (максимизации) M -векторного векторного показателя эффективности E_m(x), m =1,2,..., M, N -мерного векторного аргумента x=(x₁,x₂,...,x_N), компоненты которого удовлетворяют системе ограничений-равенств q_k(x)= 0, k=1,2...K, ограничений-неравенств g_j(x)>0, j=1,2,...J, областных ограничений x_li<x_i<x_ui, i=1,2...N.

Задачи принятия оптимальных решений можно классифицировать в соответствии с видом функций и размерностью E_m(x), q_k(x), g_j(x) и размерностью и содержанием вектора x:

· одноцелевое принятие решений - E_m(x) - скаляр;

· многоцелевое принятие решений - E_m(x) - вектор;

· принятие решений в условиях определенности - исходные данные - детерминированные;

· принятие решений в условиях неопределенности - исходные данные - случайные.

Задачи оптимизации независимо от рассматриваемого направления исследовались в математике Л.С. Понтрягиным (принцип максимума Понтрягина [2]), Р.Л. Стратоновичем [2], применительно к теории управления - В.Г. Болтянским [2]. В результате сформировалась теория оптимальных процессов.

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

 

В настоящее время для решения оптимальных задач применяют в основном следующие методы:

• методы исследования функций классического анализа;
• методы, основанные на использовании неопределенных множителей Лагранжа;
• принцип максимума;
• вариационное исчисление;
• математическое программирование.

Наиболее разработан и широко используется на практике аппарат одноцелевого принятия решений в условиях определенности, который получил название математического программирования: задачи линейного программирования (E(x), q_k(x), g_j(x) - линейны); нелинейного программирования (E(x), q_k(x), g_j(x) - нелинейны); дискретного (в том числе целочисленного) программирования (x – дискретны, в том числе целочисленны); динамического программирования (x – вычисляются на каждом шаге решения задачи).

Математический аппарат одноцелевого принятия решений в условиях неопределенности представляет собой стохастическое программирование (известны законы распределения случайных величин), теории игр и статистических решений (закон распределения случайных величин неизвестен).

Методы принятия многоцелевых решений – метод анализа иерархий, метод Парето и др.

Математическое программирование - это раздел теории оптимизации (теории экстремальных задач), занимающийся изучением и решением задач минимизации (максимизации) функции нескольких переменных на подмножестве конечномерного векторного пространства, которое задано в виде системы уравнений и/или системы неравенств.

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

 

Подобного рода задачи решаются в различных отраслях деятельности: в экономике, при разработке проектов, составлении расписаний, планировании военных операций и т.п. Модели математического программирования относятся к категории детерминированных моделей. Термин программирование в применении к рассматриваемому типу задач понимается как поиск наилучших планов (от английского слова programming - составление плана, программы действий). Когда говорят о задачах математического программирования, имеют в виду задачи, цель которых состоит в повышении эффективности промышленных, транспортных систем, систем управления деятельностью учебных, проектных, научных организаций.

Математическое программирование подразделяется на линейное, целочисленное, нелинейное, динамическое программирование. Рассмотрим некоторые постановки задач, методы и алгоритмы их решения.

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

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

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

Широкий класс нелинейных и дискретных задач может решаться с использованием идеи рекуррентного подхода (методов типа математической индукции), являющихся основой динамического программирования, идея которого первоначально была предложена Р. Беллманом[1].

Для решения задач оптимизации со случайными параметрами разработано стохастическое программирование.

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

Развиты также методы решения задач оптимизации, в которых переменная принимает только два значения «истинно» - «ложно» или «да» — «нет». Такие методы относят к булевому программированию.

Методы математического программирования находят свое применение в самых различных областях техники и экономики.

В настоящее время экономическую теорию невозможно представить без экономико-математических методов, основанных на результатах математического программирования. Здесь достаточно упомянуть модели календарного планирования или упорядочения во времени, расписания, потоковые или транспортные модели; модели распределения и назначения; модели износа и замены оборудования (см. [1-4] и др.).

Экстремальные задачи независимо от рассматриваемого направления исследовались в математике Л.С. Понтрягиным (принцип максимума Понтрягина [2]), Р.Л. Стратоновичем [2], применительно к теории управления - В.Г. Болтянским [2]. В результате сформировалась теория оптимальных процессов.

Анализ постановки и решения задачи математического программирования позволяет выявить следующие особенности:

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

· при использовании методов математического программирования появляется возможность объединения в единой модели разнородных критериев (разных размерностей, предельных значений), что очень важно при отображении реальных проектных и производственных ситуаций;

· модель математического программирования допускает (и даже ориентирует на это) выход на границу области определения переменных (в то время как методы классической математики в основном приспособлены для поиска точек экстремумов во внутренней части области изменения переменных);

· изучение методов решения задач математического программирования позволяет получить представление о пошаговом приближении к решению, т. е. о пошаговом алгоитме получения результата моделирования.

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