Задача 3а.

Найти

 

 

при условиях

 

 

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

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

Этап 1. Нахождение опорного решения х⁽⁰⁾.

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

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

Оптимальное решение находится последовательным перебором вершин многогранника (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;

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

 

 

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

 

 

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

 

В большинстве методов спуска величина 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+1 должно также, как и предыдущее 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+1:

 

 

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

 

 

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