Структура оптимизационных задач. Математическое программирование

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

Все оптимизационные задачи имеют общую структуру.

Оптимизационные задачи есть задачи минимизации (максимизации) 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 _il<x_i<_iu, i=1,2...I, x_il – нижняя, x_{iu –} верхняя границы значения признака x_i.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

2.3. Линейное программирование. Содержательные постановки задач линейного программирования.

 

Общая постановка задачи линейного программирования показана в таблице 2.2

 

Таблица 2.2.

Краткая форма записи задачи линейного программирования

Матричная форма записи

Задача линейного программирования формулируется так: Определить максимум линейной формы F(x1,…,xn)=max(c1x1+…+cnxn) (2.1) при условии, что точка (х1, х2,..., хn) принадлежит некоторому множеству D, которое определяется системой линейных неравенств (2.2) x 1≥0, …, x n≥0. Любое множество значений (х1*, х2*,..., хn*), которое удовлетворяет системе неравенств (2.2) задачи линейного программирования, является допустимым решением данной задачи. Если при этом выполняется неравенство c1х1o+ c2 х2o+..+ cn хno ≥ c1х1+ c2 х2+..+ cn хn для всего множества значений x1, х2,..., хn, то значение х1o..хno является оптимальным решением задачи линейного программирования.

F=CX →max при ограничениях   .