Прямые и обратные задачи исследования операций. Детерминированные задачи

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

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

Обратные задачи отвечают на вопрос: как выбрать решение х для того, чтобы показатель эффективности W обратился в максимум?

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

Остановимся несколько подробнее на обратных задачах. Если число возможных вариантов решения, образующих множество X. невелико, то можно попросту вычислить величину W для каждого из них, сравнить между собой полученные значения и непосредственно указать один или несколько оптимальных вариантов, для которых W достигает максимума. Такой способ нахождения оптимального решения называется «простым перебором». Однако, когда число возможных вариантов решения, образующих множество X, велико, поиск среди них оптимального «вслепую», простым перебором, затруднителен, а зачастую практически невозможен. В этих случаях применяются методы «направленного перебора», обладающие той общей особенностью, что оптимальное решение находится рядом последовательных «попыток» или «приближений», из которых каждое последующее приближает нас к искомому оптимальному. С некоторыми из таких методов мы познакомимся в главах 3 и 4.

Сейчас мы ограничимся постановкой задачи оптимизации решения (обратной задачи исследования операций) в самой общей форме.

Пусть имеется некоторая операция Ơ, на успех которой мы можем в какой-то мере влиять, выбирая тем или другим способом решение х (напомним, что х — не число, а целая группа параметров). Пусть эффективность операции характеризуется одним показателем W => max.

Возьмем самый простой, так называемый «детерминированный» случай, когда все условия операции полностью известны заранее, т. е. не содержат неопределенности. Тогда все факторы, от которых зависит успех операции, делятся на две группы:

1) заданные, заранее известные факторы (условия выполнения операции), которые мы для краткости обозначим одной буквой а;

2) зависящие от нас элементы решения, образующие в своей совокупности решение х.

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

Показатель эффективности W зависит от обеих групп факторов. Это мы запишем в виде формулы:

 

 

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

Будем считать, что вид зависимости (4.1) нам известен, т. е. прямая задача решена. Тогда обратная задача формулируется следующим образом.

При заданном комплексе условий найти такое решение х = х*, которое обращает показатель эффективности W в максимум.

Этот максимум мы обозначим:

 

(4.1)

 

Формула (4.2) читается так: W* есть максимальное значение W (,x), взятое по всем решениям, входящим в множество возможных решений X.

К формулам такого типа надо привыкать. Они понадобятся в дальнейшем (см. гл. 4).

Итак, перед нами — типичная Математическая Задача нахождения максимума функции или функционала.

Эта задача принадлежит к классу так называемых «вариационных задач», хорошо разработанных в математике. Самые простые из таких задач («задачи на максимум и минимум») знакомы каждому инженеру. Чтобы найти максимум или минимум (короче, «экстремум») функции многих аргументов, надо продифференцировать ее по всем аргументам (в данном случае — элементам решения), приравнять производные нулю и решить полученную систему уравнений. Казалось бы, чего проще? А вот этот классический метод как раз в исследовании операций имеет весьма ограниченное применение. Во-первых, когда аргументов много, задача решения системы уравнений зачастую оказывается не проще, а сложнее, чем непосредственный поиск экстремума. Во-вторых, когда на элементы решения наложены ограничения, экстремум часто достигается не в точке, где производные равны нулю (такой точки может вообще не быть), а где-то на границе области X. Возникают все специфические трудности так называемой «многомерной вариационной задачи при ограничениях», иной раз непосильной по своей сложности даже для современных ЭВМ. Кроме того, в некоторых задачах функция W вообще не имеет производных (например, задана только для целочисленных значений аргументов). Все это делает задачу поиска экстремума далеко не такой простои, как она кажется с первого взгляда.

Метод поиска экстремума и связанного с ним оптимального решения х* должен всегда выбираться исходя из особенностей функции W и вида ограничений, накладываемых на решение. Например, если функция W линейно зависит от элементов решения x ₁, x₂,..., а ограничения, налагаемые на x ₁, x ₂,..., имеют вид линейных равенств или неравенств, возникает ставшая классической задача линейного программирования, которая решается сравнительно простыми, а главное, стандартными методами (см. главу 3). Если функция W выпукла, применяются специальные методы выпуклого программирования с их разновидностью:

«квадратичным программированием» (см. [8]). Для оптимизации управления многоэтапными операциями применяется метод динамического программирования (см. главу 4). Наконец, существует целый набор численных методов отыскания экстремумов, специально приспособленных для реализации на ЭВМ; некоторые из них включают элемент «случайного поиска», который для многомерных задач нередко оказывается эффективнее упорядоченного перебора.

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