Разновидность задач ИО.

Все задачи ИО можно условно разбить на две категории: прямые и обратные.

Прямые задачи отвечают на вопрос “что будет, если в заданных условиях будет принято какое-то конкретное решение x*ÎX. В частности – при заданном решении x* и заданных детерминированных значениях неуправляемых факторов а чему будет равен выбранный показатель эффективности операции W(a,x*) или ряд показателей при векторном критерии эффективности

W = W(a, x*).

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

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

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

Обратные задачи отвечают на вопрос – какое необходимо выбрать решение xÎX (оптимальное или рациональное) для того, чтобы обеспечить при этом наилучшее значение показателя эффективности W.

В случае скалярного критерия эффективности W под наилучшим будем понимать максимальное значение показателя. Тогда обратная задача ИО может быть записана следующим образом:

При заданном комплексе условий а найти такое решение

x = x° (xÎX),

которое обращает показатель эффективности операции W в максимум

W° (x°) = мах W(a, x)

XÎX

(см. Рисунок)

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

Если число возможных вариантов решения, образующих множество X невелико, то для поиска оптимального решения необходимо, для каждого из возможных значений xÎX, решая прямую задачу определить значение показателя W. Сравнив их между собой, можно указать одно или несколько решений, при которых W достигает максимума. Такой способ называется простым перебором.

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

С формальной точки зрения задачи поиска оптимального решения (в случае скалярного показателя W) относятся к классу задач математического программирования. Термин программирование от английского programming – составление плана или программы действий, здесь следует понимать в смысле “поиска наилучших планов”, а не в смысле разработки программного обеспечения для ЭВМ.

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

- либо максимальное (минимальное) значение некоторого обобщенного (скалярного) показателя U, который представляет собой результат формализованной (неформализованной) свертки векторного критерия

мax U = U(W),

- либо решения (одно из решений), отвечающее условию, что нельзя найти другое решение, позволяющее улучшить любой из показателей Wi (i = 1,к) не ухудшая при этом значения других показателей Wx (x¹i) (хотя бы одно из них). Такие решения называются эффективными или паретовскими (xпÎXп ).

I i

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

0 £ a_i £1 , Sa_i = 1 ( i = 1, k)

I

Поиск решения при выбранной функции свертки U(W) аналогичен поиску оптимального решения по скалярному критерию эффективности.

Во втором случае (не свернутый векторный критерий) поиск эффективных (паретовских) решений xпÎXп может быть осуществлен путем прямого перебора всех возможных решений xÎX (если оно конечно) с процедурой сравнения показателей

W(x).

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

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

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

Остановимся несколько подробнее на их постановке и методах решения.
Постановка и классификация задач математического программирования.

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

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

найти значения переменных x₁,…x_n, доставляющие максимум (минимум) заданной скалярной функции f(x₁,…x_n; a)

при условиях g_i (x₁,…x_n) ≤ (≥, =) b_i , где i=1,…,m.

Здесь a и b_i – константы , определяемые из физических условий задачи.

Условия g_i(x₁,…x_n) ограничивают возможность выбора значений переменных x₁,…x_n из множества всех возможных значений. Множество точек Х= { x₁,…x_n }, удовлетворяющих системе ограничений g_i (i=1,…,m) есть область определенияXпоставленной задачи.

Функция f(x₁,…x_n; a) называется целевой функцией, которая может достигать экстремальных значений в одной или нескольких точках области X, которые предстоит найти (в конкретных задачах ИО в качестве целевой функции используют критерий эффективности, вычисляемый на основе модели операции).

Обычно вид функций f и g известен, константы͞a и b_i, вытекающие из параметров исследуемой системы и целей, стоящие перед ней – заданы, число переменных n и ограничений m – определено. Кроме того, при необходимости, специально оговариваются ограничения на не отрицательность и целочисленность переменных x_i (i=1,…,n) исходя из их физической природы, которые также входят в систему ограничений на переменные.

Исходя из вышесказанного формальная запись задачи математического программирования имеет вид:

Параметр a входит в вид самой целевой функции и в дальнейшем может быть опущен.

В зависимости от вида целевой функции и ограничений можно выделить следующие классы задач:

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

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

3. Задачи выпуклого программирования. Это такие задачи, когда целевая функция f и множество возможных решений X – выпуклые.

Множество X называется выпуклым, если для любых двух точек x₁,x₂ Î X оно содержит в себе весь отрезок, их соединяющий:

Функция f(x) называется выпуклой (выпуклой вниз) на интервале [x_1,x₂], если для любой точки ( внутри этого интервала выполняется условие f( ) ≤ .

Здесь

(1)

(2)

(3)

Если f( ) ≥ , то функция называется вогнутой или выпуклой вверх.

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

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

4. По ограничениям, накладываемым на переменные x_i можно выделить задачи с непрерывными и дискретными переменными. Дискретность переменных нарушает выпуклость множества X и приводит, как правило, к необходимости либо полного, либо направленного перебора всех возможных решений xÎX, что значительно увеличивает трудоемкость решения задачи. При высокой размерности множества X точное решение задачи бывает практически невозможным за приемлемое время.

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

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

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