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

Основные понятия математического программирования.

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

В процессе решения задачи оптимизации обычно необходимо найти оптимальные значения некоторых переменных, определяющих данную задачу. Примерами таких переменных являются: численность исполнителей, станков, машин и др. Число переменных (обозначим их X₁, X₂,...,Х_n, где n - число переменных) характеризует степень сложности задачи оптимизации.

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

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

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

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

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

Обозначим ограничения следующим образом:

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

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

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

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

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

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

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

X_i 0, i=1,2,…,n

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

и максимизируют функцию:

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

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

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

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

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

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

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_n)=åC_iX_i+ååX_iD_ijX_j.

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

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

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

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

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

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

- распределительные задачи;

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

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

- задача поиска;

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

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

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

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

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

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

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

- задача o выборе рациона;

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

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

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

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

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

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

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

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

задача выбора типажа

задача поиска

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

1.4.Контрольные задания.

1. Приведите примеры задач линейного, целочисленного, нелинейного и динамического программирования.

2. Приведите несколько примеров практических задач и определите каким классам задач математического программирования они относятся.