Размещено на http://www.allbest.ru/

Аннотация

Курсовая работа на тему: «Метод Ньютона в нелинейном программировании».

Выполнила студентка первого курса, группы БЭК-11ц Кулешова Галина Николаевна

Руководитель: Протасов Дмитрий Николаевич.

Работа представлена к защите в 2013г.

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

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

Введение

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

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

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

Задача 1. Метод Ньютона в нелинейном программировании. Метод Ньютона. Сходимость метода Ньютона. Метод Ньютона в задачах на безусловный экстремум

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

f(x)=0 (1.1)

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

Пусть x_n - текущее приближение к корню x_r и ?x=x_r - x_n. Тогда можно записать следующее разложение функции f(x) в ряд Тейлора:

(1.2)

С учетом того, что f(x_r)=0, получим

(1.3)

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



Если теперь точку взять в качестве следующего за уточнения корня, то получим итерационную формулу метода Ньютона:

(1.4)

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

Геометрически интерпретируется как точка пересечения оси касательной к кривой y=f(x) в точке х_n (рис. 1.1).

Рис. 1.1 Метод Ньютона

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



Это разложение является более точным, так как в нем используется некоторая точка , про которую известно лишь то, что она расположена между х и х_n. Положив в нем x=х_r, получим:

.

Разделим теперь это равенство на и преобразуем результат к виду:

Левая часть полученного выражения, согласно итерационной формуле метода (1.4) есть . Тогда мы можем записать:

где А это равенство указывает на квадратичную сходимость итерационного процесса (1.4).

Метод Ньютона имеет квадратичную скорость сходимости в окрестности простого (однократного) корня. Если корень кратный, то метод Ньютона сходится гораздо медленнее - линейно.

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

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

f₁(x₁,x₂,…,x_n)=0,

f₂(x₁,x₂,…,x_n)=0,

…………………… (1.5)

f_n(x₁,x₂,…,x_n)=0.

В основе метода Ньютона для систем уравнений лежит представление левых частей всех уравнений системы (1.5) рядами Тейлора. Пусть - текущее приближение корня Х=(Х₁,Х₂,…,Х_n)^T и ?х=Х-х^(k). Тогда можно записать следующее покомпонентное разложение функции f(X) в ряды Тейлора:

Здесь все производные вычисляются в точке х^(k). С учетом того, что f(X)=0, получим систему уравнений, эквивалентную системе (1.5):

(1.6)

Если теперь в левых частях уравнений (1.6) оставить лишь слагаемые, содержащие нулевую и первую степени приращений ?x_i, то исходную нелинейную задачу удается свести к решению системы линейных уравнений вида:

(1.7)

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

i=1,2,…,n. (1.8)

Итерационный процесс, определяемый формулами (1.8), в которых приращение ?х_i вычисляются путем решения системы линейных уравнений (1.7), представляет собой алгоритм метода Ньютона для системы нелинейных уравнений (1.5). Когда модули всех корректирующих приращений ?х_i становятся достаточно малыми: итерации прекращаются. Если абсолютные величины корней Х₁,Х₂,…,Х_n значительно отличаются друг от друга, то для прекращения счета следует пользоваться нормированными корректирующими приращениями.

Систему уравнений (1.7) можно записать в векторно-матричной форме:

J(x^(k))?x=-f(x^(k)) (1.9)

Формальная запись решения системы (1.9) имеет вид: ?х=-J(x^(k))^-1f(x^(k), где J^-1 - матрица, обратная матрице Якоби. Если воспользоваться этим выражением, то итерационные формулы (1.8) можно записать как:

x^(k+1)= =x^(k)-J(x^(k))^-1f(x^(k). (1.10)

При n=2 система (1.7) имеет простое аналитическое решение с небольшим числом арифметических операций. Весьма распространена задача о нахождении комплексных корней нелинейного уравнения F(z)=0. Действительно, если ввести в рассмотрение функции f₁(x₁,x₂)=Re(F(x₁+jx₂)) и f₂(x₁,x₂)=Im(F(x₁+jx₂)), то вещественная часть x₁ и мнимая часть x₂ комплексного корня z находятся из системы уравнений: f₁(x₁,x₂)=0, f₂(x₁,x₂)=0.

Будем предполагать, что для данной системы определитель матрицы Якоби отличен от нуля на каждой итерации:

Тогда система имеет решение:

Теперь формулы итераций (1.8) можно записать в явном виде:

(1.11)

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

При условии, что в окрестности корня вектор-функция f(x) дважды непрерывна дифференцируема по всем аргументам и матрица J невырождена, многомерный метод Ньютона сходится квадратично:

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

Процесс сходимости итераций метода Ньютона от начального приближения x⁽⁰⁾=(2,2) к корню Х=(1,1) системы уравнений:

(1.12)

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

Таблица 1.1

k
0	2.000000000	2.000000000	1.414213562	-
1	1.693548387	0.890322581	0.702167004	0.351
2	1.394511613	0.750180529	0.466957365	0.947
3	1.192344147	0.822840986	0.261498732	1.199
4	1.077447418	0.918968807	0.112089950	1.639
5	1.022252471	0.976124950	0.02637256	2.598
6	1.002942200	0.996839728	4.317853366Е-3	4.054
7	1.000065121	0.999930102	9.553233627Е-5	5.124
8	1.000000033	0.999999964	4.871185259Е-8	5.337
9	1.000000000	1.000000000	1.272646866Е-14	5.363

Как видно, итерации сходятся довольно быстро - результат с семью верными цифрами после десятичной точки получается после восьми итераций. Данные пятого столбца таблицы 1.1 подтверждают положение о квадратичной сходимости метода. Правда, зависимость справедлива в довольно малой окрестности корня, а константа С достаточно велика: С ?5,4.

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

Оптимизация означает минимизацию или максимизацию функции. В общем случае задача оптимизации формулируется как задача нахождения на множестве S n-мерного пространства таких значений аргументов функции n вещественных переменных f(x₁,x₂,…,x_n), при которых эта функция достигает минимума или максимума. Минимизация (или максимизация) функции часто называется целевой функцией. Если множество S представляет собой все n-мерное пространство, то говорят, что решается задача безусловной оптимизации (оптимизации без ограничений).

Будем говорить, что функция f(x) имеет глобальный минимум в точке , если точка допустима (принадлежит множеству S) и для всех допустимых точек. Аналогично, f(x) имеет локальный минимум в точке , если точка допустима и для всех допустимых точек из окрестности . Функция f(x) называется унимодальной на отрезки [a,b], если на этом отрезке она единственный минимум и при строго убывает, а при строго возрастает.

Применим метод Ньютона для минимизации функции f(x). Будем предполагать, что функция имеет по крайней мере три непрерывные производные и ограничена снизу. Идея метода Ньютона состоит в аппроксимации f(x) в окрестности предполагаемой точки минимума х₀ более простой функцией, для минимизации которой можно воспользоваться аналитическими выражениями. Точка минимума х₁ этой аппроксимирующей функции дает новое приближение для точки минимума исходной функции f(x). Затем процесс повторяется до тех пор, пока модуль разности межлу двумя последовательными приближениями не достигает заданной погрешности минимизации. Так как линейная функция не имеет конечного минимума, простейшей аппроксимацией является квадратичная.

Предположим, что точка х_n - текущее приближение к истинному положению минимума , и рассмотрим разложение функции f(x) в ряд Тейлора в окрестности точки х_n, ограничившись тремя членами ряда:

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

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

(1.13)

Условия сходимости итерационного процесса (1.13) можно сформулировать как следующее утверждение. Пусть и непрерывна. Тогда существует окрестность точки такая, что если начальное приближение х₀ принадлежит этой окрестности, то последовательность значений х_n , вычисляется по формуле (1.13), сходится к при n>?. Для функций не являющихся унимодальными при итерации (1.13) сходятся к локальному минимуму, а при - к локальному максимуму.

Когда метод Ньютона сходится, скорость сходимости квадратична. Это означает, что если точка х_n достаточно близка к , то то С - неотрицательная константа, зависящая от вида минимизируемой функции. Проще говоря, число верхних значений цифр приближения х_n удваивается с каждой новой итерацией. Одномерная оптимизация тесно связана с задачей решения нелинейных уравнений. Так, формула (1.13) получается, если методом Ньютона решить уравнение которое представляет собой необходимое условие экстремума функции. С другой стороны, нелинейное уравнение g(x)=0 можно решить, найдя точку нулевого минимума функции f(x)=g²(x). Метод Ньютона для решения задач минимизации функций многих аргументов является обобщением метода одномерной оптимизации. Разложение целевой функции f(x₁,x₂) в ряд Тейлора в окрестности точки текущего приближения Х^(k) имеет вид:

(1.14)

Здесь все производные вычисляются в точке Х^(k). Выражение (1.14) можно записать в векторно-матричной форме, если ввести в рассмотрение квадратичную матрицу Н (матрицу Гессе) с элементами и вектор-столбец смещений :

(1.15)

Несмотря на то, что этот результат получен для двумерного случая, его векторно-матричная форма (1.15) сохраняется и для n измерений.

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

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

и приравнивая его к нулю. В результате получаем систему линейных алгебраических уравнений относительно компонент вектора - вектора смещения из точки текущего приближения Х^(k) в точку нового приближения Х^(k+1):

(1.16)

Уравнение (1.16) называются уравнениями Ньютона. Их решение позволяет определить новое приближение как

(1.17)

Если решение уравнения Ньютона (1.16) формально записать через матрицу Н(х^(k))^-1, обратную матрице Гессе, то

и итерационная формула многомерного метода Ньютона будет выглядеть следующим образом:

(1.18)

Метод Ньютона для многих измерений обладает тем же свойством квадратичной сходимости в окрестности минимума, что и в одномерном случае.

Задача 2

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

;

.

Выполнить следующее:

а) Кратко описать сущность модели межотраслевого баланса (2 страницы);

б) Вычислить вектор-столбец конечного продукта и вектор-строку условно-чистого продукта, проверить выполнение балансового соотношения между ними, составить таблицу межотраслевого баланса;

в) Построить производственную матрицу , и записать систему балансовых соотношений в матричной форме (проверить её выполнение);

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

д) пусть даны:

- вектор-столбец прямых затрат по оплате труда на рубль продукции

- вектор-столбец прямых затрат(в чел/час) труда на рубль продукции

-- вычислить полную трудоемкость и зарплатоемкость продукции, по отраслям;

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

;

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

как должен быть изменен вектор валовых выпусков?

Решение

а) Модель межотраслевого баланса является классическим примером макроэкономической модели. Первые её варианты появились еще в 10-20-х годах ХХ века, и далее имело место их развитие и весьма плодотворное использование на протяжении всего последующего периода, как за рубежом, так и в СССР, и в соцстранах.

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

Планировать необходимый валовый выпуск продукции при заданном объеме конечной продукции отраслей;

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

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

Ставить и решать различные оптимизационные задачи промышленного производства.

б) Вычисляем вектор-столбец конечного продукта

вектор-строку условно-чистого продукта



проверяем выполнение балансового соотношения между ними,

Видим - баланс выполняется.

в) Строим производственную матрицу

Проверяем выполнение баланса

г) Вычисляем матрицу полных потребностей продукции отраслей В=(Е-А)^-1.

Сделаем проверку:

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

д) - Вектор полной трудоемкости:

- Вектор полной затратоемкости:

е) Рассчитываем план по валовому продукту:

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

,

то вектор валовых выпусков должен измениться на

Задача решена.

Задача 3

Привести математическую формулировку задачи. Решить ее симплекс-методом. Составить двойственную задачу. Найти ее решение. Проинтерпретировать полученное решение двойственной задачи.

Для изготовления различных изделий А, В и C предприятие использует два вида ресурсов: станочное оборудование и рабочую силу. Нормы затрат станко-часов и нормо-часов необходимые для изготовления одной тысячи изделий каждого вида, цена одной тысячи изделий каждого вида, а также общее имеющееся количество ресурсов приведены в таблице.

Таблица 3.1

Вид оборудования	Нормы затрат ресурсов на одну тысячу изделий.	Общее количество
	A	B	C	ресурсов.
Станочное оборудование	25+N=25+7=32	10+2N=10+2*7=24	20+N=20+7=27	500+5N+4N2= =500+5*7+4*0=535
Рабочая сила	15+2N=15+2*7=29	24+2N=24+2*7=38	45-N=45-7=38	440+3N+6N2= =440+3*7+6*0=461
Цена одной тысячи изделий, тыс. руб	10+N=10+7=17	12+N=12+7=19	8+N=8+7=15

Известно также, что по ранее заключенным договорам суммарный объем выпуска в денежном выражении изделий видов A и C не может быть менее 250_2N= 250-2*7=236 тыс.руб.

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

Решение.

Составим математическую модель задачи. Искомый выпуск изделий А обозначим через x₁, изделий В - через х₂, изделий C - через x₃. Переменные должны удовлетворять следующей системе неравенств:

32x₁ + 24x₂ + 27x ₃ 535,

29x₁ + 38x₂ + 38x ₃ 461,

Общая стоимость произведенной продукции составит:

С = 17x₁+19x₂+15x₃

x₁ 0 , x₂ 0, x₃ 0.

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

32x₁ + 24x₂ + 27x ₃ + x ₄ = 535

29x₁ + 38x₂ + 38x ₃ + x ₅ = 461

Для приведения к каноническому виду вводим дополнительную переменную x₆.

17x₁ + 15x₃ - x₆ = 236

Значит, матрица ограничений задачи теперь имеет вид:

и в ней нет 3-х (по количеству ограничений) единичных столбцов.

Введем искусственную переменную x₇0,

17x₁ + 15x₃ - x₆ + x₇ = 236

Имеем задачу

С = 17x₁ + 19x₂ + 15x₃ - 200*x₇ max,

при ограничениях:

32x₁ + 24x₂ + 27x ₃ + x ₄ = 535

29x₁ + 38x₂ + 38x ₃ + x ₅ = 461

17x₁ + 15x₃ - x₆ + x₇ = 236

x_i 0, (i=).

Ниже приводится последовательность симплекс-таблиц полученных при решении задачи.

Принимаем в качестве первоначального базиса х₄, х₅, х₇ и записываем данные задачи в таблицу, называемую симплекс-таблицей.

Шаг 1. Симплекс-таблица первого шага.

Таблица 3.2

Базис	х1	х2	х3	х4	х5	х6	х7	Р	С
x4	32	24	27	1	0	0	0	535	0
x5	29	38	38	0	1	0	0	461	0
х7	17	0	15	0	0	-1	1	236	-200
?	-3417	-19	-3015	0	0	200	0

где ?_i = <c,a_i>-c_i, где <c,a_i> - скалярное произведение столбца с и столбца таблицы а_i соответствующего переменной х_i, c_i - коэффициент из целевого функционала при переменной х_i. Если среди величин ?_i есть отрицательные, следовательно текущий план можно улучшить.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

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

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1 и из них выберем наименьшее:

Вводим в базис х₁. Исключаем х₇. Разрешающий коэффициент 17.

Шаг 2. Симплекс-таблица второго шага.

Таблица 3.3

Базис	х1	х2	х3	х4	х5	х6	х7	Р
x4	0	24	-1,235	1	0	1,88	-1,88	87
x5	0	38	12,41	0	1	1,71	-1,71	55
х1	1	0	15/17	0	0	-1/17	1/17	14
?	0	-19	0	0	0	-1	201

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2 и из них выберем наименьшее:

Вводим в базис х₂. Исключаем х₅. Разрешающий коэффициент 38.

Шаг 3. Симплекс-таблица третьего шага.

Таблица 3.4

Базис	х1	х2	х3	х4	х5	х6	х7	Р
x4	0	0	-9,07	1	-0,63	0,8	-0,8	52
х2	0	1	0,327	0	0,026	0,045	-0,045	1,45
х1	1	0	0,88	0	0	-0,06	0,06	14
?	0	0	6,2	0	0,5	-0,145	200,145

Получен оптимальный план.

В соответствии с ним нужно произвести 14 тыс. изделий вида А, и 1,45 тыс. изделий вида С. Изделия вида В производить не нужно.

Прибыль при этом составит С=17*14+15*1,45=260 тыс. руб.

Составим двойственную задачу:

С = 535y₁ + 461*y₂ + 236*y₃ min,

при ограничениях:

32y₁ + 29y₂ + 17y₃ ? 17

24y₁ + 38y₂ ? 19

27y₁ + 38y₂ + 15у₃ ? 15

y₁?0, y₂?0, -y₃?0, y₃?-200.

Из таблицы 3.4 находим решение y₁^*=0; y₂^*=0,5; y₃^*=0,145.

Подставим в ограничения:

32*0 + 29*0,5 + 17*0,145=17 ? 17

24*0 + 38*0,5=19 ? 19

27*0 + 38*0,5 + 15*0,145=21 ? 19

Что касается величин двойственных оценок, то можно сказать, что максимальное значение С_max может быть увеличено на 0,5, если второе ограничение увеличить с 461 до 462. И - на 0,145, если третье - с 236 до 237. Это может быть использовано при принятии решения о том какой ресурс прежде всего следует увеличить.

Задача 4

Решить задачу с помощью теории игр.

Отрасли А и В осуществляют капитальные вложения в 4 объекта. С учетом особенностей вкладов и местных условий прибыль отрасли А в зависимости от объемов финансирования выражается с помощью платежной матрицы С. Убыток отрасли В равен прибыли отрасли А. Найти оптимальные стратегии отраслей.

1) Свести исходные данные в таблицу и найти решение матричной игры в чистых стратегиях (если оно существует).

2) Упростить платежную матрицу.

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

4) Найти решение игры в смешанных стратегиях.

5) Дать рекомендации по каждой отрасли.

Решение

1) Обозначим чистые стратегии отраслей А и В соответственно через А₁, А₂, А₃, А₄ и В₁, В₂, В₃, В₄. Предположим, что отрасль А располагает общей суммой а тыс. ден. ед., отпускаемой на капитальные вложения четырех объектов. Аналогично и отрасль В имеет сумму b тыс. ден. ед., отпускаемую на капитальные вложения тех же четырех объектов. Тогда общая сумма средств капитальных вложений в 4 объекта отраслью А: а₁+а₂+а₃+а₄ и отраслью В: b₁+b₂+b₃+b₄

Сведем исходные даны в табл. 4.

Таблица 4.1

В А	В1	В2	В3	В4	?=minaij
А1	15	11	5	17	5
А2	13	9	5	13	5
А3	3	7	9	15	3
А4	7	11	3	15	3
?=maxaij	15	11	9	17	?=5 ?=9

Проверим, имеет ли игра решение в чистых стратегиях.

Так как ? = 5 ? 9 = ? , то игра неразрешима в чистых стратегиях.

2)Чтобы упростить платежную матрицу, будем сначала сравнивать поэлементно 1-ю строку со всеми остальными, затем 2-ю строку со всеми остальными и т.д. Элементы 1-ой строки больше либо равны соответствующим элементам 2-ой строки. Значит, 2-ая стратегия будет доминирующей, и ей отрасли А пользоваться заведомо не выгодно. Следовательно, 2-ую строку можно исключить. Аналогично 4-ую строку тоже можно исключить. Получим следующую цепочку платежных матриц:

Теперь будем аналогично сравнивать столбцы. Получим следующую цепочку платежных матриц:

.

Платежная матрица упрощена, при этом последняя матрица эквивалентна исходной.

3) Составим пару взаимно двойственных задач, эквивалентную матричной игре с платежной матрицей С₂.

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

Z= x₁+x₂+x₃>max.

А ограничения выписываются по строкам и не превышают единицы:

Целевая функция F двойственной задачи исследуется на минимум и равна:

F=y₁+y₂>min

при ограничениях, больших либо равных единицы, которые выписываются по столбцам:



Решим прямую задачу симплекс-методом. Приведем ее к каноническому виду:

Z= x₁+x₂+x₃+0х₄+0х₅>max

Выпишем начальный опорный план задачи: Х₀= (0;0;0;1;1), z(Х₀)=0.

Составим исходную симплекс-таблицу:

Таблица 4.2 Симплекс-таблица 1

Базис	х1	х2	х3	х4	х5	Р
х4	15	11	5	1	0	1
х5	3	7	9	0	1	1
z	-1	-1	-1	0	0	0

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

Вводим в базис х₃. Исключаем х₅. Разрешающий коэффициент 9.

Таблица 4.3 Симплекс-таблица 2

Базис	х1	х2	х3	х4	х5	Р
х4	13,33	7,1	0	1	-0,55	0,45
х3	0,33	0,78	1	0	0,11	0,11
z	-0,67	-0,22	0	0	0,11	0,11

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

Вводим в базис х₁. Исключаем х₄. Разрешающий коэффициент 13,33.

Таблица 4.4 Симплекс-таблица 3

Базис	х1	х2	х3	х4	х5	Р
х1	1	0,532	0	0,075	-0,041	0,034
х3	0	0,602	1	-0,025	0,125	0,1
z	0	0,134	0	0,05	0,084	0,134

Так как в z-строке последней симплексной таблицы все элементы больше или равны нулю, та найден оптимальный план. Он единственный, поскольку нули z-строки соответствуют только базисным переменным:

Х_opt=(0,034; 0; 0,1; 0), а значение целевой функции Z_max=0,134.

Так как у нас симметричная пара двойственных задач, то в строке оценок (z-строке) найдем элементы, соответствующие переменным, которые входили в исходный базис, х₄, х₅, и присвоим им значения двойственным неизвестным у₁, у₂, т.е.

у₁^*=0,05; у₂^*=0,084. Следовательно, Y_opt=(0,05; 0,084).

При этом F_min=z_max=0,134.

4) Используя соотношения между оптимальными решениями пары двойственных задач Х_opt и Y_opt , оптимальными стратегиями и и ценой игры ?, найдем решение игры в смешанных стратегиях.

Цена игры:

Тогда оптимальные стратегии отрасли А будут равны:



Для отрасли В соответственно получим:

5) Таким образом из общей суммы средств а тыс. ден. ед., выделяемых отраслью А капитальных вложений в четыре объекта, на долю 1-го объекта следует выделить 37,3%, на долю 3-го - 62,7% этой суммы. На остальные объекты деньги выделять не целесообразно.

Так же получим, что из общей суммы средств b тыс. ден. ед., выделяемых отраслью В капитальных вложений в четыре объекта, на долю 1-го объекта следует выделить 25,4%, на долю 3-го - 74,6% всей суммы. На остальные объекты деньги выделять не целесообразно.

ньютон экстремум сходимость оптимальный

Заключение

Метод, предложенный Ньютоном в 1669 году, получил название метод Ньютона. Основная идея метода Ньютона очень проста - это идея линеаризации.

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

Список использованных источников

Экономико-математические методы и прикладные модели/ Под ред. В.В. Федосеева. - М.: ЮНИТИ, 1999.

Акулич И.Л. Математическое программирование в примерах и задачах. - М.:Высшая школа,1993.

Исследование операций в экономике: Учебное пособие для вузов/ Н.Ш. Кремер, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. - М.: Банки и биржи, ЮНИТИ, 1997.-407 с.

Эддоус М., Стэнсфилд Р. Методы принятия решений. - М.: Юнити,1997.

Шелобаев С.И. Математические методы и модели в экономике, финансах и бизнесе: Учебник для вузов. - М: ЮНИТИ, 2000. - 367 с.

Б.Т. Поляк. Метод Ньютона и его роль в оптимизации и вычислительной математике. - Труды ИСА РАН 2006. Т.28

Численные методы для физиков. Нелинейные уравнения и оптимизация: учебное пособие / В.В. Зайцев, В.М. Трещев. - Самара, 2005. - 86с.: ил.

Лекции по дисциплине «Методы оптимизации».

Размещено на Allbest.ru