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

§ 3. Классификация методов математического программирования.

Математическое программирование предполагает построение алгоритмов решения задач оптимизации (задач оптимального планирования) . В зависимости от свойств целевой функции и ограничений математическое программирование подразделяестся на: линейное; нелинейное (нелинейное при линейных ограничениях: выпуклое; сепарабельное; квадратичное; геометрическое). Это разделение неслучайно. Оно определяется отсутствием универсальных методов решения задач нелинейного программи­рования, для которого разработаны лишь эффективные методы решения отдельных классов задач. Задачи оптимизации связаны с вопросами эффективного использования или распределения ограниченных ресурсов для достижения желаемых целей. Характерной чертой задач оптимизации является большое число реше­ний, удовлетворяющих условиям задачи. Выбор конкретного решения, как «наилучшего», зависит от функции цели (показатель качества, критерий оптимальности, функция качества, критерий эффективности и т.д. — си­нонимы). Задача, допускающая лишь одно решение_, не требует оптимиза­ции.

В общем плане, существующие методы математического программирова­ния подразделяются на аналитические и численные

Аналитические методы включают в себя классические методы дифференциального и вариационного исчисления. Эти методы за­ключаются

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

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

Решение задач оптимизации численными методами представляет собой два этапа:

Первый этап — сбор информации об объекте;

Алгоритм сбора информации должен быть

1. прост;

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

Источник

1.2. Общая задача математического программирования.

Сформулируем общую задачу математического программирования.

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

Дадим количественную, математическую постановку этой задачи.

Найти значения «n» переменныхX₁,X₂. Х_n, которые неотрицательны

X_i0,i=1,2,…,n

удовлетворяют «m» ограничениям:

Z=F(X₁,X₂,…,X_n) MAX

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

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

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

Признак первой(из двух предлагаемых)классификациизадач матема­тического программирования — вид функции цели, вид ограничений и наличие или отсутствие целочисленности переменных, описывающих про­цесс или систему.

Если функция цели и ограничения являются линейными:

Z=F(X₁,X₂,…,X_n)=C₁X₁+C₂X₂+…C_nX_n MAX;

где (Ci),(Bj),(Aij) — известные постоянные, то данная задача является задачейлинейного программирования.

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

Частным случаем задач нелинейного программирования являются задачи целочисленногопрограммирования. От задач линейного программирования они отличаются только наличием условия целочисленности переменныхX1,X2. Хn.

Если целевая функция задачи математического программирования квадратичная, но все её ограничения линейны, то такую задачу называют задачей квадратичного программирования. Линейные ограниче­ния, для данной задачи записываются так же как для задачи линейного программирования, а целевая функция имеет вид:

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

Z=F(X₁,X₂)=X₁*X₂ MAX;

Отдельным классом задач математического программирования являются задачи динамического программирования.Эти задачи характеризуются многоэтапным процессом поиска оптимального решения.

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

Например, планируется работа группы предприятий на несколько лет. Конечной целью является получение максимального объема продукции. В начале периода имеется запас средств производства (оборудование, финансы), с помощью которого можно начать производство. «Шагом» процесса планирования является хозяйственный год. Необходимо решить задачу распределения средств по предприятиям по годам плани­руемого периода.

Второй признак классификациизадач математического программирования — конкретное их содержание. Поэтому в данном случае говорят о классификации задач оптимального управления и планирования. По этому признаку, задачи математического программирования принято делить на следующие типы (рис. 1):

— задача управления запасами;

— задачи замены оборудования;

— задача выбора оптимальных режимов движения;

— задача выбора оптимальной структуры.

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

Примерами распределительных задач являются:

— транспортная задача, в которой рассматривается вопрос об оптимальном прикреплении пунктов производства и пунктам потребления;

— задача о назначении, в которой рассматривается вопрос об опти­мальном прикреплении производителя работ к объекту производст­ва;

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

— задача выбора применения ресурсов;

— задача выбора типажаи другие задачи.

Задача управления запасамиформулируется следующими образом: имеется некоторое количество запасов, хранение которых связано с расходами. Однако и отсутствие запасов иногда недопустимо или при­водит к расходам. Требуется найти такой размер запасов(или порядок их пополнения), при котором расходы будут минимальными.

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

Задача замены оборудования— состоит в решении вопроса: продолжить производить или эксплуатировать старое оборудование или же заменить его новым, более совершенным, т.е. решается вопрос построения оптимального плана технического переоснащения производ­ства.

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

Задача поискасводится к отысканию оптимального плана поиска объектов. Например: объектов противника, неисправностей, брака, полезных ископаемых и др.

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

задача управления запасами

задача замены оборудования

задача выбора режима движения

задача выбора применения ресурсов

Рис.1.: Задачи математического программирования.

Источник