logo
УЧЕБНИКИ 1 Экономика / Исследование систем управления / Мыльник В

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

Задача 1. Найти

где

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

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

в точках решения уравнений (8.3).

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

Пример:

Система уравнений имеет решения:

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

Задача 2. Найти

при условиях:

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

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

откуда

Задача 3. Найти:

при условиях:

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

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

Задача 3а.

Найти

при условиях

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

Симплекс-метод (состоит из двух этапов):

Этап 1. Нахождение опорного решения х(0).

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

Этап 2. Нахождение оптимального решения.

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

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

Транспортная задача. Пусть в пунктах находятся склады, в которых хранятся товары в количествесоответственно. В пунктахнаходятся потребители, которым необходимо поставить эти товары в количествахсоответственно. Обозначимcij стоимость перевозки единицы груза между пунктами

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

Для того, чтобы удовлетворять запросы потребителя, необходимо, чтобы величины х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) различаются либо выбором направления спуска, либо способом движения вдоль направления спуска. Методы спуска состоят в следующей процедуре построения последовательности {xk}.

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

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

• находят (к + 1) – е приближение по формуле:

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

где число – любое такое число, когда

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

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

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

Схема метода:

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

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

Схема метода:

где координатный вектор

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

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

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

Схема метода:

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

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

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

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

при условиях

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

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

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

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

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

При условиях:

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

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

Схема метода:

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

В качестве начального приближения выбирается . По вычисленной на каждой итерации точкеxk строится (k + 1)-я точка xk+1:

В качествевыбирается любое число из=, удовлетворяющее неравенству:

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