Решение возникающей оптимизационной задачи.

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

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

Методы безусловной и условной оптимизации

Задача 1 сводится к решению системы уравнений:

и исследованию значения второго дифференциала:

Если квадратичная форма (8.4) отрицательно определена в точке, то она достигает в ней максимальное значение, а если положительно определена, то минимальное значение.

Точка (– 1/3,0) является точкой максимума, а точка (1/3,2) –точкой минимума.

Задача 2 решается методом множителей Лагранжа. Для этого находится решение системы (т + п) уравнений:

Пример. Найти стороны прямоугольника максимальной площади, вписанного в круг:

. Площадь А прямоугольника можно записать в виде: А = 4ху, тогда

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

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

Она решается симплекс-методом [3,7], который с помощью аппарата линейной алгебры производит целенаправленный перебор вершин многогранника, определяемого (8.13).

Опорное решение – одна из точек многогранника (8.13).

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

Частный случай задачи линейного программирования – так называемая транспортная задача [3].

Транспортная задача. Пусть в пунктах

находятся склады, в которых хранятся товары в количестве

соответственно. В пунктах

находятся потребители, которым необходимо поставить эти товары в количествах

соответственно. Обозначим c_ij стоимость перевозки единицы груза между пунктами

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

количество товара, перевозимого из пункта а_i в пункт b_j.

Для того, чтобы удовлетворять запросы потребителя, необходимо, чтобы величины х_ij удовлетворяли условиям:

В то же время со склада а; нельзя вывезти продуктов в большем количестве, чем там имеется. Это означает, что искомые величины должны удовлетворять системе неравенств:

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

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

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

, удовлетворяющие ограничениям (8.14), (8.15) и доставляющие функции (8.16) минимальное значение. Ограничение (8.15) – это условие баланса; условие (8.14) можно назвать целью операции, ибо смысл операции в том и состоит, чтобы обеспечить запросы потребителей.

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

Одним из известных методов решения транспортной задачи является метод потенциалов [3].

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

ограничениям (8.14), (8.15). Если

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

или фиктивный склад

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

Задача 3б. В общем случае задача (8.10 – 8.11) называется задачей нелинейного программирования. Рассмотрим ее в более принятом виде:

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

называется релаксационным, если:

Методы спуска (общая схема) [3]. Все методы спуска решения задачи безусловной оптимизации (8.17) различаются либо выбором направления спуска, либо способом движения вдоль направления спуска. Методы спуска состоят в следующей процедуре построения последовательности {x_k}.

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

• точке x_k выбирается направление спуска – s_k;

где в качестве величины

выбирают любое число, удовлетворяющее неравенству

В большинстве методов спуска величина l_к выбирается равной единице. Таким образом, для определения b_к приходится решать задачу одномерной минимизации.

Метод градиентного спуска. Поскольку антиградиент –

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

называется методом градиентного спуска. Если

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

Метод сопряженных направлений. В линейной алгебре этот метод известен как метод сопряженных градиентов решения систем линейных алгебраических уравнений АХ=b, а следовательно, как метод минимизации квадратичной функции

Если

= 0, то эта схема превращается в схему метода скорейшего спуска. Соответствующий выбор величины t_k гарантирует сходимость метода сопряженных направлений со скоростью того же порядка, что и в методах градиентного спуска и обеспечивает конечность числа итераций в квадратичном спуске [3] (например

Покоординатный спуск. На каждой итерации в качестве направления спуска – s _k выбирается направление вдоль одной из координатных осей. Метод имеет скорость сходимости процесса минимизации порядка 0(1/m). Причем она существенно зависит от размерности пространства.

Если в точке x_k имеется информация о поведении градиента функции f(x), например:

то в качестве направления спуска s_k можно взять координатный вектор е_j. В этом случае скорость сходимости метода в n раз меньше, чем при градиентном спуске.

На начальном этапе процесса минимизации можно использовать метод циклического покоординатного спуска, когда сначала спуск осуществляется по направлению е₁, затем по е₂ и т. д. вплоть до е_п, после чего весь цикл повторяется снова. Более перспективным по сравнению с предыдущим является покоординатный спуск, в котором направления спуска выбираются случайным образом. При таком подходе к выбору направления существуют априорные оценки, гарантирующие для функции f(x) свероятностью, стремящейся к единице при

, сходимость процесса со скоростью порядка 0(1/m).

На каждом шаге процесса из n чисел {1, 2,..., n} случайным образом выбирается номер j(k) и в качестве s _k выбирается единичный координатный вектор е_j₍_k₎, после чего осуществляется спуск:

Метод случайного спуска. На n-мерной единичной сфере с центром в начале координат выбирается случайная точка s_k, подчиняющаяся на этой сфере равномерному распределению, и затем по вычисленному на k-м шаге процесса элементу х_к определяется

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

Релаксационные методы математического программирования. Вернемся к задаче 36 ((8.17) – (8.18)):

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

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

и затем, минимизируя f(x) на множестве х, находят точку y_k. После этого полагают

и далее вдоль этого направления осуществляют спуск

, так, чтобы

Таким образом, для отыскания направления – s_k следует решить задачу минимизации линейной функции на множестве X. Если X в свою очередь задается линейными ограничениями, то она становится задачей линейного программирования.

Метод возможных направлений. Идея метода: среди всех возможных направлений в точке х_к выбирают то, вдоль которого функция f(x) убывает быстрее всего, и затем осуществляют спуск вдоль этого направления.

Направление – s в точке х Î X называется возможным, если существует такое число

, что

для всех

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

Пусть

– решение этой задачи. Условие (8.25) гарантирует, что направление –

– возможное. Условие (8.26) обеспечивает максимальность величины (

, то есть среди всех возможных направлений – s, направление –

обеспечивает самое быстрое убывание функции f(x). Условие (8.27) избавляет от неограниченности решения задачи. Метод возможных направлений устойчив к возможным вычислительным ошибкам. Однако скорость его сходимости оценить в общем случае сложно и эта задача пока остается нерешенной.

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

На n-мерной единичной сфере с центром в начале координат выбирается случайная точка r_k, подчиняющаяся на этой сфере равномерному распределению, и затем направление спуска – s_k из условий

В качестве начального приближения выбирается

. По вычисленной на каждой итерации точке x_k строится (k + 1)-я точка x_k₊₁:

В качестве

выбирается любое число из

, удовлетворяющее неравенству:

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

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: