Численные методы поиска стационарных точек в оптимизационных задачах: метод Ньютона

Контрольная работа.

Численные методы поиска стационарных точек в оптимизационных задачах: метод Ньютона.

1. Численные методы поиска стационарных точек в оптимизационных задачах: метод Ньютона.

Как научное направление, теория оптимизации возникла лишь в эпоху ЭВМ, так как реализация алгоритмов отыскания экстремумов чрезвычайно трудоемка, но основные методы и подходы, использующиеся в теории оптимизации, были разработаны крупнейшими математиками прошлого — Ньютоном, Эйлером, Лагранжем.

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

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

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

Задачу оптимизации мы будем записывать следующим образом:

или (1).

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

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

Заметим, что термин «оптимизация функции» не вполне точно отражает существо процесса оптимизации в форме (1). В таком процессе сама функция остается неизменной.

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

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

Обычно при максимизации используются неравенства вида, а при минимизации — неравенства вида .

Таким образом, возникают две стандартные формы постановки задач оптимизации:

(2).

Ограничения типа неравенств легко заменить ограничениями типа равенств и простыми координатными неравенствами, вводя дополнительные (вещественные) переменные. При этом ограничения вида заменятся парой ограничений, , а ограничения — парой ограничений, .

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

В результате его применения в таких условиях возникает третья стандартная форма постановки задачи оптимизации:

(3).

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

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

Рассмотрим метод Ньютона.

Предположим, что у нас определено начальное приближение х₀ к одному из корней уравнения (4).

(4).

Тогда в точке х₀ можно вычислить левую часть решаемого уравнения f (x₀).

Рассмотрение метода Ньютона начнем с его геометрического представления (рисунок 1).

Рисунок 1 — Метод Ньютона Возьмем точку х₀ отрезка [a, b] и проведем в точке P₀ с координатами (x₀, f (x₀)) касательную к кривой y= f (x) до пересечения с осью 0х. Получим значение х₁, в котором касательная пересекает ось 0x. Угловой коэффициент касательной равен значению производной от функции f (x) в точке касания.

Следовательно, уравнение касательной, проходящей через точку с координатами (x₀, f (x₀)) имеет вид:

(5).

Полагая y=0, находим точку пересечения касательной с осью 0х, которую обозначим через х₁:

(6).

Абсциссу х₁ точки пересечения можно взять в качестве приближенного значения корня.

Проведя касательную через новую точку с координатами (x₁, f (x₁)) и находя точку ее пересечения с осью 0х, получим второе приближения корня х₂.

Аналогично определяются последующие приближения.

Следующие приближения находим соответственно по формулам:

(7).

В общем случае для k-го шага итерационного процесса последнее соотношение принимает вид:

(8).

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

(9).

То есть, когда выполняется следующее условие:

(10).

Таким образом, для реализации метода Ньютона необходимо:

1) Задать в явном виде уравнение f (x), корни которого необходимо определить.

2) Определить первую производную функции f (x) в аналитическом виде.

3) Определить начальное приближение х₀, обеспечивающее быструю сходимость метода.

4) Задать точность нахождения корня уравнения f (x).

5) Реализовать в программе итерационную процедуру, реализующую формулу (8).

2. Задача линейного программирования.

Предприятие планирует выпуск двух видов продукции I и II, на производство которых расходуется три вида сырья А, В и С. Потребность a_ij i-го вида сырья на каждую единицу j-го вида продукции, запас b_i соответствующего вида сырья и прибыль c_j от реализации единицы j-го вида продукции заданы таблицей:

Таблица 1.

1. Для производства двух видов продукции I и II с планом x₁ и x₂ единиц составить математическую модель, т. е. целевую функцию прибыли F и соответствующую систему ограничений по запасам сырья, предполагая, что требуется изготовить в сумме не менее n единиц обоих видов продукции.

2. Найти оптимальный план X*=(x₁, x₂) производства продукции, обеспечивающий максимальную прибыль F_max. Определить остатки каждого вида сырья. Задачу решить симплекс-методом..

3. Построить по полученной системе ограничений многоугольник допустимых решений и найти оптимальный план производства геометрическим методом. Определить максимальную прибыль F_max.

4. Составить математическую модель двойственной задачи (систему ограничений по единичной прибыли и целевую функцию общих издержек на сырье Z); найти оптимальный набор цен на сырьё Y*=(y₁, y₂, y₃), обеспечивающий минимум общих затрат на сырье Z_min.

5. Провести анализ первоначальных и дополнительных переменных исходной и двойственной задач, сделать выводы.

6. Решить задачу оптимизации в MS Excel в режиме «поиск решения». Провести исследование полученного решения, используя отчеты по результатам, по устойчивости, по пределам; сделать выводы. Ответы, полученные в результате решений «вручную» и с помощью Excel, должны совпадать.

Решение:.

Предположим, что будет использовано х₁ сырья, А для изготовления продукции I, х₂ сырья для изделия II. Тогда общая прибыль составит 6х₁ + 6х₂.

Так как общее количество сырья, А не может превышать 36 единиц, то должно выполняться следующее неравенство:

4х₁+2х₂? 36.

Аналогичные рассуждения относительно возможно использования остального количества сырья приведут к следующим неравенствам:

х₁ + х₂? 11;

2х₁ + 5х₂? 40.

При этом, так как количество изготовляемых изделий не может быть отрицательным, то:

х₁? 0, х₂? 0 (1).

Пусть F — прибыль предприятия, так как по условию необходимо составить план производства двух видов изделий, обеспечивающий максимальную прибыль, следовательно, функция F, при условии, что изготовлено х₁ единиц изделий I и х₂ единиц изделий II будет максимизироваться:

F = 6х₁ + 5х₂ > max.

Таким образом, мы приходим к следующей математической задаче:

Дана система:

(2).

трех линейных неравенств с двумя неизвестными х_i (i=1,2). И линейная функция относительно этих же переменных:

F = 6х₁ + 6х₂ (3).

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

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

Прямые S1 — S3, изображены на рисунке 1.

Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству, а другой — нет. Определим искомую полуплоскость через точку О (0; 0).

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

Рисунок 1 — Многоугольник решений математический переменная издержки затраты Как видно из рисунка 1, многоугольником решений является пятиугольник ОАВСD.

Таким образом, среди точек пятиугольника ОАВСD нам нужно найти такие, в которых функция F = 6х₁ + 6х₂ принимает максимальное значение. Для нахождения этих точек построим нулевую линию уровня (F₀) 6х₁ + 6х₂ = 0 и вектор N = (12; 12).

Передвигая данную прямую параллельно самой себе в направлении вектора N, видим, что ее последней точкой с многоугольником решений задачи является точка С. Следовательно, в этой точке функция F принимает максимальное значение. Так как С — точка пересечения прямых S1 и S2, то ее координаты удовлетворяют уравнениям этих прямых:

Решив эту систему уравнений мы получили:

х₁ = 7 и х₂ = 4.

Таким образом, максимальное значение функции F_max = 6*7+6*4 = 42 + 24 = 66.

3. Решение симплекс-методом.

Математическая модель задачи:

х₁, х₂? 0.

F = 6х₁ + 6х₂.

Запишем эту задачу в форме основной задачи ЛП:

Для этого перейдем от ограничений неравенств — к ограничениям равенствам.

Введем 3 дополнительные переменные, в результате чего ограничения запишутся в виде систем ограничений:

Преобразованную систему ограничений запишем в векторной форме:

Поскольку среди векторов Р₁-Р₅ имеются 3 единичных вектора, для данной задачи можно непосредственно записать опорный план.

Таковым является план Х = (0; 0; 0; 36; 11; 40), определяемый системой трехмерных единичных векторов Р₃, Р₄, Р₅, которые образуют базис трехмерного векторного пространства.

Составим симплексную таблицу для I итерации (таб. 2), подсчитав значения F₀, z_i — c_i и проверяем исходный план на оптимальность.

F₀ = (c, P₀); z₁ = (c, P₁) = 0; z₂ = (c, P₂) = 0; z₃ = (c, P₃) = 0;

z₄ = (c, P₄) = 0; z₅ = (c, P₅) = 0;

z₁ — c₁ = 0 -6= -6; z₂ — c₂ = 0 — 6 = -6.

Для векторов базиса z_i — c_i = 0.

Таблица 2.

Таким образом, по 4 строке таблицы 2 видно, что план не оптимален, т.к. значения z_i — c_i — отрицательны..

Далее определяем вектор, подлежащий исключению из базиса. Для этого находим Q_0min (b_i/a_i1) для a_i1>0 и Q_0min (b_i/a_i2) для a_i2>0..

Таким образом, Q_0min (b_i/a_i1) = min (36/4; 11/1; 40/2) = 36/4, а Q_0min (b_i/a_i2)= min (36/2; 11/1; 40/51) = 40/5..

Min (36/4; 40/5) = 40/5..

Таким образом, мы нашли разрешающий элемент, находящийся на пересечении 2-ой строки и столбца вектора Р₂..

Следовательно, вектор Р₄ подлежит исключению из базиса..

Столбец вектора Р₂ и вторая строка являются направляющими..

Далее, составляем таблицу для итерации II (таб. 3)..

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

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

Для определения остальных элементов таб. 3 применяем правило прямоугольника..

Данный цикл продолжается до тех пор, пока все значения z_i — c_i — не станут положительными..

Таким образом, в таб. 3 мы запишем все итерации вычислительного процесса..

Таблица 3.

Итак, среди значений z_i — c_i нет отрицательных, следовательно, опорный план оптимален и F_max = 66..

4. Двойственная задача.

Прямая задача имеет вид:

х₁, х₂? 0.

F = 6х₁ + 6х₂.

Хопт. = (7; 6).

Max F = 66.

Составим двойственную модель и с помощью теорем двойственности найдем оптимальное решение двойственной модели:

Двойственная модель:

Z = 36y₁ + 11y₂ + 40y₃> min.

Так как мы уже нашли решение исходной задачи (таб. 3), следовательно, мы нашли и решение двойственной задачи:

y₁ = 0; y₂ = 6; y₃ = 0. (итерация III в симплекс-таблице 3).

Таким образом оптимальное решение двойственной задачи = y_опт(0; 6; 0).

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

Z = 36*0+11*6+40*0 = 0+66+0 = 66.

Итак, Z = F = 66.

5. Транспортная задача.

На трех складах А₁, А₂ и А₃ хранится а₁=100, а₂=200, а₃=60+10n единиц одного и того же груза, соответственно. Этот груз требуется доставить трем потребителям В₁, В₂ и В₃, заказы которых b₁=190, b₂=120, b₃=10m единиц груза, соответственно. Стоимости перевозок c_ij единицы груза с i-го склада j-му потребителю указаны в соответствующих клетках транспортной таблицы:

Таблица 4.

1. Сравнивая суммарный запас и суммарную потребность в грузе, установить, является ли модель транспортной задачи открытой или закрытой. Если модель открытая, то ее необходимо закрыть, добавив фиктивный склад А₄ с запасом а₄=b-а в случае а₄ с потребностью b₄=a-b в случае а>b и положив соответствующие им тарифы перевозок нулевыми..

2. Составить первоначальный план перевозок методом северо-западного угла и методом наименьшей стоимости..

3. Методом потенциалов проверить первоначальный план перевозок на оптимальность в смысле суммарной стоимости перевозок, и если это не так, то составить оптимальный план.

,.

обеспечивающий минимальную стоимость перевозок. Найти эту стоимость..

4. Решить задачу в MS Excel в режиме «поиск решения». Ответы, полученные в результате решений «вручную» и с помощью Excel, должны совпадать..

Решение:

Потребность = 190+120+400 = 710.

Возможности = 100+200+100 = 400.

Таким образом, данная транспортная задача (ТЗ) — открытая.

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

Таблица 5.

Таблица 6.

n+m -1 =4+3−1 = 6 — соответствует числу заполненных клеток Общие транспортные издержки равны:

Z₁ = 100*4+90*4+110*5+10*5+90*6+310*0 = 400+360+550+50+540+0 = 1900.

Проверим составленный план на оптимальность методом потенциалов.

Рассчитаем потенциалы, исходя из того, что потенциал строки А1 = 0 (таблица 7).

Таблица 7.

Далее, рассчитаем теневые цены (таблица 8 — теневые цены выделены серым цветом).

Таблица 8.

Наличие теневых цен означает не оптимальность имеющегося плана, следовательно, для улучшения плана намечаем маршрут с наименьшей отрицательной теневой ценой и для этого маршрута определяем цикл перераспределения. Объем перевозимого груза численно равен минимальному значению из тех объемов груза, которые указаны в клетках со знаком минус. Таким образом, min (90; 10) = 10.

Итак, составляем новый план (таблица 9).

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

Таблица 9.

n+m -1 =4+3−1 = 6 — соответствует числу заполненных клеток Общие транспортные издержки равны:

Z₂ = 100*4+80*4+10*1+120*5+90*6+310*0 = 400+320+10+600+540+0 = 1870.

Таблица 10.

n+m -1 =4+3−1 = 6 — соответствует числу заполненных клеток Общие транспортные издержки равны:

Z₃ = 100*4+90*1+120*5+80*3+10*6+310*0 = 400+90+600+240+60+0 = 1390.

Таблица 11.

n+m -1 =4+3−1 = 6 — соответствует числу заполненных клеток Общие транспортные издержки равны:

Z₄ = 90*4+100*1+10*2+110*5+90*3+310*0 = 360+100+20+550+270+0 = 1300.

Таблица 12.

n+m -1 =4+3−1 = 6 — соответствует числу заполненных клеток Общие транспортные издержки равны:

Z₅ = 100*1+90*0+100*2+20*5+180*3+220*0 = 100+0+200+100+540+0 = 940.

Таблица 13.

n+m -1 =4+3−1 = 6 — соответствует числу заполненных клеток Общие транспортные издержки равны:

Z₆ = 100*1+90*0+100*2+20*0+200*3+200*0 = 100+0+200+0+600+0 = 900.

В таблице 13 все теневые цены — положительные, следовательно, план оптимален.

Решение задачи в MS Excel.

Исходными данными для решения транспортной задачи являются:

— матрица транспортных расходов;

— предложение поставщиков;

— спрос потребителей.

Рабочий лист EXCEL с введенными исходными данными для решения транспортной задачи показан на рисунке 2.

Рисунок 2 — Рабочий лист EXCEL с введенными исходными данными для решения транспортной задачи Рабочий лист EXCEL с размеченными блоками ячеек показан на рисунке 3.

Рисунок 3 — Рабочий лист EXCEL с размеченными блоками ячеек Формирование элементов математической модели.

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

фактически реализовано;

фактически получено.

Для нашей задачи m=4, n=3.

Рассмотрим процесс формирования этих сумм на рабочем листе EXCEL.

Вначале сформируем, в блоке «Фактически реализовано».

1. Заполняем ячейки блока «Матрица перевозок» числом 0,01.

2. Селектируем первую ячейку блока «Фактически реализовано»;

3. Наводим курсор на кнопку автосуммирование и щелкаем левой клавишей мыши;

4. Нажимаем клавишу Delete;

5. Селектируем первую строку блока «Матрица перевозок»;

6. Нажимаем клавишу Enter;

7. Копируем формулу из первой ячейки блока «Фактически реализовано» на все остальные ячейки этого блока.

Сформируем теперь — в блоке «Фактически получено».

Для этого выполните следующие действия:

1. Селектируем первую ячейку блока «Фактически получено»;

2. Наводим курсор на кнопку автосуммирование и щелкаем левой клавишей мыши;

3. Нажимаем клавишу Delete;

4. Селектируем первый столбец блока «Матрица перевозок»;

5. Нажимаем клавишу Enter;

6. Копируем формулу из первой ячейки блока «Фактически получено» на остальные ячейки этого блока.

Для формирования целевой функции введем вначале формулы, отражающие транспортные расходы по каждому потребителю, т. е. формулы в ячейки блока «Транспортные расходы по потребителям».

Для ввода этих формул выполняем следующие действия:

1. Селектируем первую ячейку блока «Транспортные расходы»;

2. Наводим курсор на кнопку автосуммирование и щелкаем левой клавишей мыши;

3. Нажимаем клавишу Delete;

4. Селектируем первый столбец блока «Матрица Транспортных расходов»;

5. Нажимаем клавишу *;

6. Селектируем первый столбец блока «Матрица перевозок»;

7. Активируем строку формул, наведя на нее курсор и щелкнув затем левой клавишей мыши;

8. Нажимаем одновременно три клавиши: «CTRL» + «SHIFT» + «ENTER»;

9. Копируем формулу в остальные ячейки блока «Транспортные расходы»;

Сформируем теперь целевую функцию транспортной задачи, в ячейку «Итого расходы». Для этого:

Селектируем ячейку «Итого расходы»;

1. Наводим курсор на кнопку автосуммирование и щелкаем левой клавишей мыши;

2. Нажимаем клавишу Delete;

3. Селектируем блок ячеек «Транспортные расходы»;

4. Нажимаем клавишу Enter;

После формирования элементов математической модели и целевой функции транспортной задачи рабочий лист EXСEL примет вид, показанный на рисунке 4.

Рисунок 4 — Формирования элементов математической модели и целевой функции транспортной задачи Далее, приступаем к решению задачи с помощью программы «Поиск решения».

Параметры программы «Поиск решения» представлены на рисунке 5.

Рисунок 5 — Параметры программы «Поиск решения».

Результаты решения представлены на рисунке 6.

Рисунок 6 — Результаты решения транспортной задачи.

1) Агальцов В. П. Математические методы в программировании. Учебник — 2 изд. Издательство: Форум, 2010.

2) Математическое программирование. Учебник (издание 2-е). Балдин К. В., Брызгалов Н. А., Рукосуев А., Издательство: Дашков и К, 2012.

3) Стариков А. В. Экономико-математическое и компьютерное моделирование: учеб. пособие / А. В. Стариков, И. С. Кущева; Фед. агентство по образованию, ГОУ ВПО «ВГЛТА». — Воронеж, 2008.

4) Excel для экономистов и менеджеров / А. Г. Дубина и др. — СПб.: Питер, 2004.