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

 

где Δ_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.  Решить задачу с помощью теории игр.

Отрасли А и В осуществляют капитальные вложения в 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) Составим пару взаимно двойственных задач, эквивалентную матричной игре с платежной матрицей С₂.

         q₁    q₂   q₃

         ↕     ↕    ↕

         х₁    х₂   х₃

Целевая функция 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.

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

 

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

Базис	х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.

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

Базис	х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.

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

Базис	х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% всей суммы. На остальные объекты деньги выделять не целесообразно.