Метод Данцига. Задача транспортного типа – частный случай задачи линейного программирования

1. Какие высказывания неверны? Метод Данцига

Ответ: можно отнести к группе градиентных

2. Какие из нижеперечисленных высказываний истинны:

Ответ: Задача ЛП с несовместной системой ограничений называется открытой

3. Какие из перечисленных методов не являются активными

Ответ: золотого сечения

4. Какие из приведенных высказываний верны:

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

5. Какие из приведенных утверждений истинны: Метод наименьших квадратов

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

6. Какие из указанных методов не являются градиентными

Ответ: симплексный метод (метод Нелдера-Мида)

7. Какие из указанных методов позволяют найти глобальный экстремум полимодальной функции

Ответ: сканирования

8. Какие методы среди перечисленных являются методами покоординатного поиска

Ответ: касательный

9. Отметьте верные утверждения

Ответ: метод простого перебора нельзя использовать при отыскании экстремума согласно процедуре Гаусса-Зайделя

10. Укажите истинное высказывание

Ответ: планом называется любое допустимое решение задачи

11. Укажите неправильное высказывание

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

12. Укажите номера правильных утверждений

Ответ: задачи транспортного типа нельзя решать методом Данцига, так как они относятся к задачам дискретного программирования(1). Первоначальный план в симплексном методе получаем приравниваем нулю всех базисных переменных(3)

13. Укажите правильное утверждение?

Ответ: базисное решение задачи ЛП вырожденное, если хотя бы одна из свободных переменных равна нулю

14. Что из нижеследующего неверно:

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

15. Что истинно из высказываний ниже?

Ответ: задача о коммивояжере относится к области дискретного программирования

16. Что истинно из следующего:

Ответ: одна из основных проблем оптимизации – «проблема размерности»

17. Что неверно в приведенных высказываниях?

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

18. Что из приведенных высказываний неверно?

Ответ: задачу ЛП можно решить процедурой упорядоченного перехода от одного плана к другому.

19. Что из предлагаемого истинно

Ответ: внутри области допустимых решений задачи ЛП не может быть экстремум

20. Что ложно из нижеприведенного?

Ответ: Для отыскания экстремума линейной целевой функции симплексным методом необходимо выполнить n-m итераций, n- количество неизвестных задачи, m- число ограничений общего вида

Градиентные методы поиска оптимума целевой функции основаны на использовании двух основных свойств градиента функции.

1. Градиент функции – это вектор, который в каждой точке области определения функции
направлен по нормали к поверхности уровня, проведенной через эту точку.

Проекции градиента
на оси координат равны частным производным функции
по соответствующим переменным, т.е.

. (2.4)

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

Рассмотрим некоторые из градиентных методов.

Метод градиента

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

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

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

Формульная запись алгоритма может иметь вид:

,
. (2.5)

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

Другая формульная запись алгоритма имеет вид:

,
. (2.6)

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

В стратегии изменения шага
в этом случае используется то, что градиенты
и
отличаются по направлению. Изменение шага поиска производится в соответствии с правилом:

(2.7)

где
– угол поворота градиента наk-ом шаге, определяемый выражением

,

,
– допустимые пределы угла поворота градиента.

Характер поиска оптимума в методе градиента показан на рис. 2.1.

Момент окончания поиска можно найти проверкой на каждом шаге соотношения

,

где – заданная погрешность расчета.

Рис. 2.1. Характер движения к оптимуму в методе градиента с большой величиной шага

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

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

Метод наискорейшего спуска

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

Сокращения объема вычислений можно добиться используя метод наискорейшего спуска.

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

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

Рис. 2.2. Характер движения к оптимуму в методе наискорейшего спуска (–) и методе градиента (∙∙∙∙)

В сравнении с методом градиента метод наискорейшего спуска оказывается более выгодным из-за сокращения объема вычислений.

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

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

Кроме того, можно также принять условие окончания поиска в форме соотношения

,

где
и
– координаты начальной и конечной точек последнего отрезка спуска. Этот же критерий может использоваться в сочетании с контролем значений целевой функции в точках
и

.

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

Рис. 2.3. К определению окончания поиска в методе наискорейшего спуска

В качестве стратегии изменения шага спуска можно использовать методы изложенные выше (2.7).

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

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

1. Метод наискорейшего спуска.

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

Этот метод, предложенный в 1845 г. О. Коши, принято теперь называть методом наискорейшего спуска.

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

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

Применим метод наискорейшего спуска для минимизации квадратичной функции

с симметричной положительно определенной матрицей А.

Согласно формуле (10.8), в этом случае Поэтому формула (10.22) выглядит здесь так:

Заметим, что

Эта функция является квадратичной функцией параметра а и достигает минимума при таком значении для которого

Таким образом, применительно к минимизации квадратичной

функции (10.24) метод наискорейшего спуска эквивалентен расчету по формуле (10.25), где

Замечание 1. Поскольку точка минимума функции (10.24) совпадает с решением системы метод наискорейшего спуска (10.25), (10.26) может применяться и как итерационный метод решения систем линейных алгебраических уравнений с симметричными положительно определенными матрицами.

Замечание 2. Отметим, что где отношение Рэлея (см. § 8.1).

Пример 10.1. Применим метод наискорейшего спуска для минимизации квадратичной функции

Заметим, что Поэтому точное значение точки минимума нам заранее известно. Запишем данную функцию в виде (10.24), где матрица и вектор Как нетрудно видеть,

Возьмем начальное приближение и будем вести вычисления по формулам (10.25), (10.26).

I итерация.

II итерация.

Можно показать, что для всех на итерации будут получены значения

Заметим, что при Таким образом,

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

На рис. 10.5 изображена именно та траектория спуска, которая была получена в данном примере.

Для случая минимизации квадратичной функции справедлив следующий общий результат .

Теорема 10.1. Пусть А - симметричная положительно определенная матрица и минимизируется квадратичная функция (10.24). Тогда при любом выборе начальною приближения метод наискорейшею спуска (10.25), (10.26) сходится и верна следующая оценка погрешности:

Здесь и Ладо - минимальное и максимальное собственные значения матрицы А.

Отметим, что этот метод сходится со скоростью геометрической прогрессии, знаменатель которой причем если их близки, то мало и метод сходится достаточно быстро. Например, в примере 10.1 имеем и поэтому Если же Ащах, то и 1 и следует ожидать медленной сходимости метода наискорейшего спуска.

Пример 10.2. Применение метода наискорейшего спуска для минимизации квадратичной функции при начальном приближении дает последовательность приближений где Траектория спуска изображена на рис. 10.6.

Последовательность сходится здесь со скоростью геометрической прогрессии, знаменатель которой равен т. е. существенно медленнее,

чем в предыдущем примерю. Так как здесь и полученный результат вполне согласуется с оценкой (10.27).

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

Замечание 2. Для квадратичной целевой функции (10.24) решение задачи одномерной минимизации (10.23) удается найти в виде простой явной формулы (10.26). Однако для большинства других нелинейных функций этого сделать нельзя и для вычисления методом наискорейшего спуска приходится применять численные методы одномерной минимизации типа тех, которые были рассмотрены в предыдущей главе.

2. Проблема "оврагов".

Из проведенного выше обсуждения следует, что градиентный метод сходится достаточно быстро, если для минимизируемой функции поверхности уровня близки к сферам (при линии уровня близки к окружностям). Для таких функций и 1. Теорема 10.1, замечание 1, а также результат примера 10.2 указывают на то, что скорость сходимости резко падает при увеличении величины Действительно, известно, что градиентный метод сходится очень медленно, если поверхности уровня минимизируемой функции сильно вытянуты в некоторых направлениях. В двумерном случае рельеф соответствующей поверхности напоминает рельеф местности с оврагом (рис. 10.7). Поэтому такие функции принято называть овражными. Вдоль направлений, характеризующих "дно оврага", овражная функция меняется незначительно, а в других направлениях, характеризующих "склон оврага", происходит резкое изменение функции.

Если начальная точка попадает на "склон оврага", то направление градиентного спуска оказывается почти перпендикулярным "дну оврага" и очередное приближение попадает на противоположный "склон оврага". Следующий шаг в направлении ко "дну оврага" возвращает приближение на первоначальный "склон оврага". В результате вместо того чтобы двигаться вдоль "дна оврага" в направлении к точке минимума, траектория спуска совершает зигзагообразные скачки поперек "оврага", почти не приближаясь к цели (рис. 10.7).

Для ускорения сходимости градиентного метода при минимизации овражных функций разработан ряд специальных "овражных" методов. Дадим представление об одном из простейших приемов. Из двух близких начальных точек совершают градиентный спуск на "дно оврага". Через найденные точки проводят прямую, вдоль которой совершают большой "овражный" шаг (рис. 10.8). Из найденной таким образом точки снова делают один шаг градиентного спуска в точку Затем совершают второй "овражный" шаг вдоль прямой, проходящей через точки . В результате движение вдоль "дна оврага" к точке минимума существенно ускоряется.

Более подробную информацию о проблеме "оврагов" и "овражных" методах можно найти, например, в , .

3. Другие подходы к определению шага спуска.

Как нетрудно понять, на каждой итерации было бы желательно выбирать направление спуска близкое к тому направлению, перемещение вдоль которого приводит из точки в точку х. К сожалению, антиградиент (является, как правило, неудачным направлением спуска. Особенно ярко это проявляется для овражных функций. Поэтому возникает сомнение в целесообразности тщательного поиска решения задачи одномерной минимизации (10.23) и появляется желание сделать в направлении лишь такой шаг, который бы обеспечил "существенное убывание" функции Более того, на практике иногда довольствуются определением значения которое просто обеспечивает уменьшение значения целевой функции.

Метод Гаусса-Зейделя

Метод заключается в поочерёдном нахождении частных экстремумов целевой функции по каждому фактору. При этом на каждом этапе стабилизируют (k-1) факторов и варьируют только один i-ый фактор

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

Этот способ наиболее прост, нагляден, но движение к оптимуму длительно и метод редко приводит в оптимальную точку. В настоящее время он иногда применяется при машинном эксперименте.

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

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

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

Метод градиента (обычный) осуществляется по следующей схеме:

а) выбирают базовую точку;

б) выбирают шаги движения по каждому фактору;

в) определяют координаты пробных точек;

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

д) по результатам опытов вычисляют оценки составляющих вектор-градиента в т. М для каждого i-го фактора:

где H i -шаг движения по X i .

X i – координаты предыдущей рабочей точки.

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

Достоинства метода: простота, более высокая скорость движения к оптимуму.

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

а) Метод крутого восхождения (Бокса - Уилсона).

б) Принятие решений после крутого восхождения.

в) Симплексный метод оптимизации.

г) Достоинства и недостатки методов.

5.7.3 Метод крутого восхождения (Бокса- Уилсона)

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

Метод крутого восхождения предполагает движение к оптимуму по градиенту.

Где i,j,k-единичные векторы в направлении соответствующих координатных осей.

Порядок расчёта .

Исходными данными является математическая модель процесса, полученная любым способом (ПФЭ, ДФЭ и т.д.).

Расчеты проводят в следующем порядке:

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

где x i -кодированное значение переменной x i ;

X i - натуральное значение переменной x i ;

X i Ц -центральный уровень фактора в натуральном виде;

l i -интервал варьирования фактора x i в натуральном виде.

б) вычисляют шаги движения к оптимуму по каждому фактору.

Для этого вычисляют произведения коэффициентов уравнения регрессии в натуральном виде на соответствующие интервалы варьирования

B i *.l I ,

Затем выбирают из полученных произведений максимальное по модулю,а соответствующий этому произведению фактор принимают за базовый фактор(B a l a). Для базового фактора следует установить шаг движения, который рекомендуется задавать меньшим или равным интервалу варьирования базового фактоpa

Знак шага движения l a ’ должен совпадать со знаком коэффициента уравнения регрессии, соответствующего базовому фактору (B a). Величина шагов для других факторов вычисляется пропорционально базовому по формуле:

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

в) вычисляют функцию отклика в центре плана, т. е. при значениях факторов равных центральному уровню факторов, т. к. движение к оптимуму начинают из центра плана.

Далее производят вычисление параметра оптимизации, увеличивая значения факторов на величину соответствующего шага движения, если хотят получить Y max . В противном случае, если необходимо получить Y min , значения факторов уменьшают на величину шага движения.

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

Если Y® max X i =X i ц +gl i ` ’

если Y® min .X i =X i ц -gl i ` . (5.36)

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

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

Рис. 4.11.

Рис. 4.12.

(двумерный случай)

Вначале выбирают начальную точку Если в одномерном случае (см. подпараграф 4.2.6) из нее можно было

сдвинуться только влево или вправо (см. рис. 4.9), то в многомерном случае число возможных направлений перемещения бесконечно велико. На рис. 4.11, иллюстрирующем случай двух переменных, стрелками, выходящими из начальной точки А, показаны различные возможные направления. При этом движение по некоторым из них дает увеличение значения целевой функции по отношению к точке А (например, направления 1-3), а по другим направлениям приводит к его уменьшению (направления 5-8). Учитывая, что положение точки оптимума неизвестно, считается наилучшим то направление, в котором целевая функция возрастает быстрее всего. Это направление называется градиентом функции. Отметим, что в каждой точке координатной плоскости направление градиента перпендикулярно касательной к линии уровня, проведенной через ту же точку.

В математическом анализе доказано, что составляющие вектора градиента функции у =/(*, х 2 , ..., х п) являются ее частными производными по аргументам, т.е.

&ад/(х 1 ,х 2 ,.= {ду/дху,ду/дх 2 , ...,ду/дх п }. (4.20)

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

У" с координатами:

1§гас1/(х (0)),

или в векторной форме

где X - постоянный или переменный параметр, определяющий длину рабочего шага, ?і>0. На второй итерации снова вычисляют

вектор градиента уже для новой точки.У, после чего по анало-

гичной формуле переходят в точку х^ > и т.д. (рис. 4.12). Для произвольной к- й итерации имеем

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

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

длина рабочего шага - расстояние между соседними точками х^

их 1 " - окажется пропорциональном модулю вектора градиента. Можно, наоборот, на каждой итерации выбирать X таким, чтобы длина рабочего шага оставалась постоянной.

Пример. Требуется найти максимум функции

у = 110-2(лг, -4) 2 -3(* 2 -5) 2 .

Разумеется, воспользовавшись необходимым условием экстремума, сразу получим искомое решение: х ] - 4; х 2 = 5. Однако на этом простом примере удобно продемонстрировать алгоритм градиентного метода. Вычислим градиент целевой функции:

grad у = {ду/дх-,ду/дх 2 } = {4(4 - *,); 6(5 - х 2)} и выбираем начальную точку

Л*» = {х}°> = 0; 4°> = О}.

Значение целевой функции для этой точки, как легко подсчитать, равно у[х^ j = 3. Положим, X = const = 0,1. Величина градиента в точке

Зс (0) равна grad y|x^j = {16; 30}. Тогда на первой итерации получим согласно формулам (4.21) координаты точки

х 1) = 0 + 0,1 16 = 1,6; х^ = 0 + 0,1 30 = 3.

у(х (1)) = 110 - 2(1,6 - 4) 2 - 3(3 - 5) 2 = 86,48.

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

• 1,6 + 0,1 4(4 - 1,6) = 2,56;