Задача 3а.

Найти z=p₁x₁+…+p_nx_nmax, (8.12)

При условиях , (8.13)

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

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

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

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

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

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

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

Транспортная задача. Пусть в пунктах а₁,а₂,…,а_n находятся склады, в которых хранятся товары в количестве x₁,x₂,…,x_n соответственно. В пунктах b₁,b₂,…,b_m находятся потребители, которым необходимо поставить эти товары в количествах y₁,y₂,…,y_m соответственно. Обозначим с_ij стоимость перевозки единицы груза между пунктами a_i и b_j.

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

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

, (8.14)

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

, (8.15)

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

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

, (8.16)

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

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

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

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

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

f(x)=f(x₁,…,x_n)min, (8.17)

при условиях

Х:, (8.18)

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

x_kX и

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

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

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

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

, (8.19)

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

, (8.20)

где число _k - любое число такое, 0<_k 1, а _к = min f(x_k-s_k).

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

Метод градиентного спуска. Поскольку антиградиент -f’(x_k) указывает направление наискорейшего убывания функции f(x), то естественным является перемещение из точки x_k по этому направлению. Метод спуска, в котором s_k=f’(x_k) называется методом градиентного спуска. Если _к=1, то релаксационный процесс называется методом скорейшего спуска.

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

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

, (8.21)

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

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

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

, где s_k=e_j- j-й координатный вектор

, (8.22)

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

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

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

Схема метода

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

, (8.23)

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

, (8.24)

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

Релаксационные методы математического программирования. Вернёмся к задаче 3в: ((8.17)-(8.18)): f(x₁,x₂,…,x_n)min

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

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

Метод условного градиента. В этом методе идея выбора направления спуска состоит в следующем: в точке х_к линеаризуют функцию f(х), строя линейную функцию f(x)= f(x_k)+(’(x_k),x-x_k) и затем, минимизируя f(x) на множестве х, находят точку y_k . После этого полагают –s_k= y_k-x_k и далее вдоль этого направления осуществляют спуск x_k+1= x_k-_k(x_k-y_k), так, чтобы x_k+1 X

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

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

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

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

, (8.25)

, (8.26)

, (8.27)

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

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

Схема метода

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

если r_k возможное направление в точке х_к

в противном случае.

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

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

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