Какие существуют методы оптимизации? Методы оптимизации управленческих решений. Классические методы безусловной оптимизации Методы многомерной оптимизации

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

где х = (х 1 ..х п) е Е п

Эта задача сводится к решению системы уравнений

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

в точках (а-|, (*2, а п) решения уравнений (7.3).

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

Пример:

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

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

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

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

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

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

можно записать в виде: А = 4ху, тогда

откуда

Задача 3. Найти при условиях:

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

Задача За.

при условиях

Она решается симплекс-методом , который с помощью аппарата линейной алгебры осуществляет целенаправленный перебор вершин многогранника, определяемого (7.13).

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

Этап 1. Нахождение опорного решения х^ 0). Опорное решение - одна из точек многогранника (7.13).

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

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

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

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

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

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

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

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

Тогда задача о перевозках формулируется как задача линейного программирования: определить величины х,у > О, удовлетворяющие ограничениям (7.14), (7.15) и доставляющие функции (7.16) минимальное значение. Ограничение (7.15) - это условие баланса; условие (7.14) можно назвать целью операции, ибо смысл операции в том и состоит, чтобы обеспечить запросы потребителей.

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

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

На первом этапе решения задачи составляют первоначальный план перевозок, удовлетворяющий ограничениям (7.14), (7.15). Если

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

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

Задача 36. В общем случае задача (7.10-7.11) называется задачей нелинейного программирования. Рассмотрим ее в виде

при условиях

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

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

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

точке х к выбирается направление спуска - S k ;
находят (к + 1)-е приближение по формуле

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

где число Х к - любое такое число, когда 0 Х к min f(x k - $ Sk).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

при условиях

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

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

f(x), строя линейную функцию f(x) = f(x k) + {у"(х к), х-х к), и затем, минимизируя f(x) на множестве х, находят точку у к. После этого полагают S k = у к - х к и далее вдоль этого направления осуществляют спуск х к+ 1 = х к - $ к (х к -у к), так, чтобы g X.

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

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

Направление s в точке х е X называется возможным,_если существует такое число (3 > О, что х - (3s е х для всех (3 g . Для нахождения возможного направления необходимо решить задачу линейного программирования либо простейшую задачу квадратичного программирования: а?=> min при условиях

Пусть д к и s k - решение этой задачи. Условие (7.25) гарантирует, что направление s k возможное. Условие (7.26) обеспечивает максимальность величины (/"(х k),s), т.е. среди всех возможных направлений s, направление s k обеспечивает самое быстрое убывание функции f{x). Условие (7.27) избавляет от неограниченности решения задачи. Метод возможных направлений устойчив к возможным вычислительным ошибкам. Однако скорость его сходимости оценить в общем случае сложно, и эта задача пока остается нерешенной.

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

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

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

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

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

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

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

Метод Розенброка является улучшенным вариантом покоординатного спуска.

Метод покоординатного спуска характеризуется выбором направлений поиска поочередно вдоль всех координатных осей, шаг рассчитывается на основе одномерной оптимизации, критерий окончания поиска , где — заданная точность определения локального экстремума, — размерность пространства управляемых параметров. Траектория покоординатного спуска для примера двумерного пространства управляемых параметров показана на рис. 1, где — точки на траектории поиска, — управляемые параметры. Целевая функция представлена своими линиями равного уровня, около каждой линии записано соответствующее ей значение . Очевидно, что есть точка минимума.

Рис. 1. Траектория покоординатного спуска

При использовании метода покоординатного спуска велика вероятность "застревания" поиска на дне оврага вдали от точки экстремума. На рис. 2 видно, что после попадания в точку , расположенную на дне оврага, дальнейшие шаги возможны лишь в направлениях или , но они приводят к ухудшению целевой функции. Следовательно, поиск прекращается в точке .

Примечание 1

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

Рис. 3. Траектория покоординатного спуска при благоприятной ориентации координатных осей

Метод Розенброка заключается в таком повороте координатных осей, чтобы одна из них оказалась квазипараллельной дну оврага. Такой поворот осуществляют на основе данных, полученных после серии из шагов покоординатного спуска. Положение новых осей может быть получено линейным преобразованием прежних осей : ось совпадает по направлению с вектором ; остальные оси выбирают из условия ортогональности к и друг к другу.

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

Рис. 4. Иллюстрация метода конфигураций

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

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

шаг выбирается оптимальным с помощью одномерной оптимизации.

При использовании метода наискорейшего спуска, как и большинства других методов, эффективность поиска существенно снижается в овражных ситуациях. Траектория поиска приобретает зигзагообразный вид с медленным продвижением вдоль дна оврага в сторону экстремума. Чтобы повысить эффективность градиентных методов, используют несколько приемов.

Один из приемов, использованный в методе сопряженных градиентов (называемом также методом Флетчера-Ривса), основан на понятии сопряженности векторов. Векторы и называют -сопряженными, если , где — положительно определенная квадратная матрица того же порядка, что и размер векторов и (частный случай сопряженности — ортогональность векторов, когда является единичной матрицей порядка ), — вектор-строка, — вектор-столбец.

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

Примечание 2

Матрицей Гессе называют матрицу вторых частных производных целевой функции по управляемым параметрам.

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

Поиск экстремума выполняют в соответствии с формулой

где — коэффициент. Кроме того, учитывают условие сопряженности

Поскольку шаг рассчитывается исходя из условия одномерной оптимизации, то, во-первых, справедливо соотношение

Алгоритм поиска сводится к применению формулы (3), пока не будет выполнено условие окончания вычислений

Чтобы определить коэффициент , решают систему уравнений (2)-(7) путем подстановки в (4) величин из (3) и из (2):

или

откуда

и с учетом (6) и (7)

Выражение (10) — это система линейных алгебраических уравнений. Ее корень есть очередное приближение к решению

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

Поэтому

Можно показать, что стремится к , — к при , где — размерность пространства управляемых параметров. Спустя шагов, нужно снова начинать с .

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

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

Задача условной оптимизации заключается в поиске минимального или максимального значения скалярной функции f(x) n-мерного векторного аргументах. Решение задачи основывается на линейной или квадратичной аппроксимации целевой функции для определения приращений x1, …,xn на каждой итерации. Существуют также приближенные методы решения нелинейных задач. Это методы основанные на методе кусочно-линейной аппроксимации. Точность нахождения решений зависит от количества интервалов, на которых мы находим решение линейной задачи, максимально приближенной к нелинейной. Такой метод позволяет производить расчеты с помощью симплекс-метода. Обычно в линейных моделях коэффициенты целевой функции постоянны и не зависят от значения переменных. Однако существует ряд задач, где затраты зависят от объема нелинейно.

Алгоритм решения:

1. Работа начинается с построения регулярного симплекса в пространстве независимых переменных и оценивая значения целевой функции в каждой из вершин симплекса.
2. Определяется вершина - наибольшее значение функции.
3. Вершина проецируется через центр тяжести остальных вершин в новую точку, которая используется в качестве вершины нового симплекса.
4. Если функция убывает достаточно плавно, итерации продолжаются до тех пор, пока либо не будет накрыта точка min, либо не начнется циклическое движение по 2 или более симплексам.
5. Поиск завершается, когда или размеры симплекса, или разности между значениями функции в вершинах останутся достаточно малыми.

Задача: оптимизация емкостей. Добиться минимальных затрат на изготовление емкости объёмом 2750 литров для хранения песка.

Z = C1X1 + C2X2 + C3X3 + C4X4 + C5X5 min;

где: X1 - количество необходимого металла, кг;

C1 - стоимость металла, руб/кг;

X2 - масса требующихся электродов, кг;

C2 - стоимость электродов, руб/кг;

X3 - количество затраченной электроэнергии, кВт ч;

C3 - стоимость электроэнергии, руб/кВт ч;

X4 - время работы сварщика, ч;

C4 - тарифная ставка сварщика, руб/ч;

X5 - время работы подъемника, ч;

C5 - оплата подъемника, руб/ч.

1. Найдем оптимальную поверхностную площадь емкости:

F = 2ab+2bh+2ah min (1)

где V=2750 литров.

x1=16,331; x2=10,99

Минимум функции получен в процессе оптимизации по методу Бокса- 1196,065 дм2

В соответствие с ГОСТ 19903 - 74, примем:

h=16,50 дм, b=10,00 дм.

Выразим a из (1) и получим:

Рассчитаем оптимальную толщину листа металла

Выберем углеродистую обыкновенную сталь Ст2сп

Для этой стали 320 МПа, ;

Масса песка.

Нагрузка на стенку емкости наибольшей площади:

Высчитаем нагрузку на 1 погонный сантиметр листа шириной 100 см:

Определим толщину стенки, исходя из условия:

где: l - длина листа (желательно наибольшая, чтобы оставить дополнительный запас прочности);

q - нагрузка на 1 погонный сантиметр, кг/см;

Толщина листа металла, м

Максимально допустимое напряжение металла, Н/мм2.

Выразим из (2) толщину стенки:

Учитывая, что 320 МПа = 3263 кг/см2,

Масса металла

где: F - площадь поверхности емкости, м2 ;

Толщина стенки металла, м;

Плотность металла, кг/м3.

Цена на сталь Ст2сп составляет около 38 руб/кг.

2. Длина сварного шва:

Воспользуемся электродами для нержавеющей стали «УОНИ-13/45»

Цена 88,66 руб/кг;

где: Sшва - поперечная площадь сечения сварного шва, м2;

l - длина сварного шва, м;

Плотность наплавленного металла, кг/м3.

3. Время сварки:

где l - длина сварного шва, м;

v - скорость сварки, м/ч.

Суммарная потребляемая мощность:

Рсум = 5 17 = 85 кВт ч;

Стоимость электроэнергии 5,7 руб/ кВт ч.

4. Для ручной дуговой сварки затраты вспомогательного, подготовительно-заключительного времени и времени на обслуживание рабочего места составляют в среднем 40 - 60%. Воспользуемся средним значением в 50%.

Общее время:

Оплата сварщика VI разряда - 270 руб/час.

Плюс тарифный коэффициент 17% за работу в замкнутом плохо проветриваемом пространстве:

Оплата помощника составит 60% от оплаты сварщика:

8055 0,6 = 4833 руб.

Итого: 8055+4833 = 12888 рублей.

5. Кран понадобиться для того, чтобы держать листы металла во время сварки, погрузки и выгрузки листов металла и непосредственно готовой емкости.

Чтобы «прихватить» всю конструкцию, сварщику необходимо наложить около 30% швов.

Оплата крана - 1000 руб/час.

Общая стоимость емкости.

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

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

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

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

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

Пример:

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

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

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

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

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

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

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

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

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

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

Задача 3 а.

при условиях

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

при условиях

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

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

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

Точке x k выбирается направление спуска – s k ;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Метод случайного спуска. 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 (выпуклость и замкнутость).