Методы оптимальных решений

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

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

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

Методы оптимальных решений



Задача 1

Найти точки условного экстремума и экстремальные значения функции при условии .

Решение

Найдем экстремум функции F(X) = , используя функцию Лагранжа.

В качестве целевой функции, подлежащей оптимизации, в этой задаче выступает функция:

F (x, y, z) =

Перепишем ограничения задачи в неявном виде:

ц (x, y, z) = ;

Составим вспомогательную функцию Лагранжа:

L (x, y z, л₁,л₂) = + л₁() + л₂()

Необходимым условием экстремума функции Лагранжа является равенство нулю ее частных производных по переменным и неопределенным множителям л_i.



Составим систему:

?L/?x = 4x+2л₁+3л₂ = 0

?L/?y = 10y-л₁-2л₂ = 0

?L/?z = 6z+4л₁+6л₂ = 0

?L/?л =

?L/?л =

Решив данную систему, получаем:

Получили точку т.е.

<0



Д<0 в точке функция имеет условный максимум.

.

Задача 2

Решить задачи квадратичного программирования

z=32x₁+120x₂-4x₁²-15x₂²>max

2x₁+5x₂?20

2x₁-x₂?8, x_i?0

Решение

Найдем градиент функции

.

В качестве X⁽⁰⁾=(4,2).

Дf(X⁽⁰⁾)=(0,60)?0.¦f(X^(k+1))?f(X^(k)))¦?0,01.

1- итерация. Дf(X⁽⁰⁾)=(0, 60).



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

Z⁽⁰⁾=(0, 4), X⁽¹⁾ = X⁽⁰⁾ + л₀(Z⁽⁰⁾ ? X⁽⁰⁾) =

=(4, 2) + л₀((0, 4) ? (4, 2)) = (4, 2) + л₀(-4, 2).

x⁽¹⁾₁=4-4л₀, x⁽¹⁾₂=2+2л₀.

Подставляем полученные значения x⁽¹⁾₁ и x⁽¹⁾₂ в целевую функцию, получим

f(л₀) = 244+120л₀? 124л²₀>max, f^' = 120 ? 248л₀= 0, л₀=0,48.

Следовательно, X⁽¹⁾ =(2,08; 2,96), f(X⁽¹⁾)=273,03.

Проверим условие окончания ¦f(X⁽¹⁾)?f(X⁽⁰⁾))¦=¦273,03 ? 240¦= 33,03 > 0,1.

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

2-я итерация.

Дf(X⁽¹⁾)=(15,36; 31,2). F₁(X) = 15,36x₁+31,2x₂> max.

Решая графически получили

Z⁽¹⁾ =(5; 2), X⁽²⁾ = X⁽¹⁾ + л₁(Z⁽¹⁾ ? X⁽¹⁾) =

= (2,08; 2,96) + л₁((5; 2) ? (2,08; 2,96)) = (2,08; 2,96) + л₁(2,92; -0,96).

x⁽²⁾₁=2,08+2,92л₁, x⁽²⁾₂=2,96-0,96л₁.

Подставляем полученные значения x⁽²⁾₁ и x⁽²⁾₂ в целевую функцию, получим



f(л₁) = 273,0304 +14,8932л₁ - 47,9296л²₁>max,

f^' = 14,8932 - 95,8592л₁= 0, л₁=0,155.

Следовательно, X⁽²⁾ =(2,53; 2,81), f(X⁽²⁾)=274,1873.

Проверим условие окончания ¦f(X⁽²⁾)?f(X⁽¹⁾))¦=¦274,1873 - 273,03¦= 1,1573 > 0,1.

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

3-я итерация.

Дf(X⁽²⁾)=(11,76; 35,7). F₂(X) = 11,76x₁+35,7x₂> max.

Решая графически получили

Z⁽²⁾ =(0; 4), X⁽³⁾ = X⁽²⁾ + л₂(Z⁽²⁾ ? X⁽²⁾) =

=(2,53; 2,81) + л₂((0; 4) ? (2,53; 2,81)) = (2,53; 2,81) + л₂(-2,53; 1,19).

x⁽³⁾₁=2,53-2,53л₂, x⁽³⁾₂=2,81+1,19л₂.

Подставляем полученные значения x⁽³⁾₁ и x⁽³⁾₂ в целевую функцию, получим

f(л₂) = 274,1149 +12,7302л₂ - 46,8451л²₂>max,

f^' = 12,7302 - 93,6902л₂= 0, л₂=0,136.

Следовательно, X⁽³⁾ =(2,19; 2,97), f(X⁽³⁾)=274,9798.

Проверим условие окончания

¦f(X⁽³⁾)?f(X⁽²⁾))¦=¦274,9798 - 274,1873¦= 0,7925 >0,1.



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

4-я итерация.

Дf(X⁽³⁾)=(14,48; 30,9). F₃(X) = 14,48x₁+30,9x₂> max.

Решая графически получили

Z⁽³⁾ =(5; 2), X⁽⁴⁾ = X⁽³⁾ + л₃(Z⁽³⁾ ? X⁽³⁾) =

=(2,19; 2,97) + л₃((5; 2) ? (2,19; 2,97)) = (2,19; 2,97) + л₃(2,81; -0,97).

x⁽⁴⁾₁=2,19+2,81л₃, x⁽⁴⁾₂=2,97-0,97л₃.

Подставляем полученные значения x⁽⁴⁾₁ и x⁽⁴⁾₂ в целевую функцию, получим

f(л₃) = 274,9821 +10,7158л₃ - 45,6979л²₃>max,

f^' = 10,7158 - 91,3958л₃= 0, л₃?0,117.

Следовательно, X⁽⁴⁾ =(2,52; 2,86), f(X⁽⁴⁾)=275,61.

Проверим условие окончания

¦f(X⁽⁴⁾)?f(X⁽³⁾))¦=¦275,61 - 274,9798¦= 0,6361 >0,1.

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

5-я итерация.

Дf(X⁽⁴⁾)=(11,84; 34,2). F₄(X) = 11,84x₁+34,2x₂> max.



Решая графически получили

Z⁽⁴⁾ =(0; 4), X⁽⁵⁾ = X⁽⁴⁾ + л₄(Z⁽⁴⁾ ? X⁽⁴⁾) =

=(2,52; 2,86) + л₄((0; 4) ? (2,52; 2,86)) = (2,52; 2,86) + л₃(-2,52; 1,14).

x⁽⁵⁾₁=2,52-2,52л₄, x⁽⁵⁾₂=2,86+1,14л₄.

Подставляем полученные значения x⁽⁵⁾₁ и x⁽⁵⁾₂ в целевую функцию, получим

f(л₄) = 275,74 +9,1512л₄ - 44,8956л²₄>max,

f^' = 9,1512 - 89,7912л₄= 0, л₄?0,102.

Следовательно, X⁽⁵⁾ =(2,26; 2,98), f(X⁽⁵⁾)=276,29.

Проверим условие окончания

¦f(X⁽⁵⁾)?f(X⁽⁴⁾))¦=¦ 276,29 - 275,61 ¦= 0,68 >0,1.

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

6-я итерация.

Дf(X⁽⁵⁾)=(13,92; 30,6). F₅(X) = 13,92x₁+30,6x₂> max.

Решая графически получили

Z⁽⁵⁾ =(5; 2), X⁽⁶⁾ = X⁽⁵⁾ + л₅(Z⁽⁵⁾ ? X⁽⁵⁾) =

=(2,26; 2,98) + л₅((5; 2) ? (2,26; 2,98)) = (2,26; 2,98) + л₅(2,74; -0,98).

x⁽⁶⁾₁=2,26+2,74л₅, x⁽⁶⁾₂=2,98-0,98л₅.



Подставляем полученные значения x⁽⁴⁾₁ и x⁽⁴⁾₂ в целевую функцию, получим

f(л₅) = 275,87 +8,1528л₅ - 39,2852л²₅>max,

f^' = 8,1528 - 78,5704л₅= 0, л₅?0,1.

Следовательно, X⁽⁶⁾ =(2,54; 2,89), f(X⁽⁶⁾)=276,282.

Проверим условие окончания

¦f(X⁽⁴⁾)?f(X⁽³⁾))¦=¦276,282 - 276,29¦= 0,08 <0,1.

Условие выполняется, следовательно, целевая функция достигает своего максимального значения в точке X^*=X⁽⁶⁾=(2.54; 2.89) и равна f^*=f(X⁽⁶⁾)276.3.

Задача 3

Определить число взлетно-посадочных полос для самолетов с учетом требования, что вероятность ожидания должна быть меньше, чем 0.05. При этом интенсивность входного потока 27 самолетов в сутки, а интенсивность их обслуживания - 30 самолетов в сутки.

Решение

Имеем СМО с неограниченной очередью.

Исчисляем показатели обслуживания многоканальной СМО:

Интенсивность потока обслуживания:

30 самолетов / сут.;

интенсивность поступления заказов 27 самолетов / сут.

Интенсивность нагрузки



Интенсивность нагрузки с=0,9 показывает степень согласованности входного и выходного потоков заявок канала обслуживания и определяет устойчивость системы массового обслуживания.

Поскольку 0,9<1, то процесс обслуживания будет стабилен.

Время обслуживания изделия

Пусть число линий n=1, тогда

вероятность, что полоса свободна (доля времени простоя полосы):

Следовательно, 10% в течение часа полоса будет не занята, время простоя равно t_пр = 6 мин.

Вероятность того, что полоса занята обслуживанием:

p₁ = с¹/1! p₀ = .



Вероятность образования очереди:

=> 0.05

Пусть число полос n=2, тогда

вероятность, что полоса свободна (доля времени простоя полос):

Вероятность того, что обслуживанием занята 1 полоса:

p₁ = с¹/1! p₀ = ;

заняты 2 полосы:

p₂ = с²/2! p₀ =

Вероятность образования очереди:

=> 0.05

Пусть число полос n=3, тогда

вероятность, что полоса свободна (доля времени простоя полосы):



Вероятность того, что обслуживанием занята 1 полоса:

p₁ = с¹/1! p₀ = ;

заняты 2 полосы:

p₂ = с²/2! p₀ =

заняты 3 полосы:

p₃ = с³/3! p₀ =

Вероятность образования очереди:

=< 0.05.

Выполняется требование задачи. Поэтому необходимо иметь 3 независимые полосы.

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

n_з = с = 0.9 канала.



Среднее число простаивающих каналов.

n_пр = n - n_з = 3 - 0.9 = 2.1 канала.

Коэффициент занятости каналов обслуживанием.

Следовательно, система на 30% занята обслуживанием.

Среднее число заявок, находящихся в очереди.

Среднее время простоя СМО (среднее время ожидания обслуживания заявки в очереди).

час.

Среднее число заявок в системе.

L_CMO = p + L_ож = 0.9 + 0.03 = 0.93 ед.

Среднее время пребывания заявки в СМО.

0.00+0.03 = 0.03 час.



Задача 4

программирование матричный квадратичный экстремум

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

Решение

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

Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Игроки	B1	B2	B3	a = min(Ai)
A1	6	5	7	5
A2	10	4	7	4
A3	13	10	4	4
A4	7	11	5	5
b = max(Bi)	13	11	7

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a_i) = 5, которая указывает на максимальную чистую стратегию A₁.

Верхняя цена игры b = min(b_j) = 7.

Что свидетельствует об отсутствии седловой точки, так как a ? b, тогда цена игры находится в пределах 5 ? y ? 7. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).

2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы.

В платежной матрице отсутствуют доминирующие строки.

В платежной матрице отсутствуют доминирующие столбцы.

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

Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.

3. Находим решение игры в смешанных стратегиях.

Математические модели пары двойственных задач линейного программирования можно записать так:

найти минимум функции F(x) при ограничениях:

6x₁+10x₂+13x₃+7x₄ ? 1

5x₁+4x₂+10x₃+11x₄ ? 1

7x₁+7x₂+4x₃+5x₄ ? 1

F(x) = x₁+x₂+x₃+x₄> min

найти максимум функции Ф(y) при ограничениях:

6y₁+5y₂+7y₃ ? 1

10y₁+4y₂+7y₃ ? 1

13y₁+10y₂+4y₃ ? 1

7y₁+11y₂+5y₃ ? 1

Ф(y) = y₁+y₂+y₃ > max



Решаем эти системы симплексным методом.

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

Определим минимальное значение целевой функции F(X) = x₁ + x₂ + x₃+x₄ при следующих условиях-ограничениях.

6x₁+10x₂+13x₃+7x₄ ? 1

5x₁+4x₂+10x₃+11x₄ ? 1

7x₁+7x₂+4x₃+5x₄ ? 1

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

6x₁+10x₂+13x₃+7x₄ - х₅= 1

5x₁+4x₂+10x₃+11x₄ - х₆ = 1

7x₁+7x₂+4x₃+5x₄ - х₇ = 1

Умножим все строки на (-1) и будем искать первоначальный опорный план.

-6x₁-10x₂-13x₃-7x₄ +х₅= -1

-5x₁-4x₂-10x₃-11x₄ +х₆ = -1

-7x₁-7x₂-4x₃-5x₄ +х₇ = -1

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Решим систему уравнений относительно базисных переменных:

x₄, x₅, x₆,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0, - 1, - 1, - 1)

Базис	B	x1	x2	x3	x4	x5	x6	x7
x4	-1	-6	-10	-13	-7	1	0	0
x6	-1	-5	-4	-10	-11	0	1	0
x7	-1	-7	-7	-4	-5	0	0	1
F(X0)	0	1	1	1	1	0	0	0

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7
x4	-1	-6	-10	-13	-7	1	0	0
x6	-1	-5	-4	-10	-11	0	1	0
x7	-1	-7	-7	-4	-5	0	0	1
F(X0)	0	1	1	1	1	0	0	0
и	0	-1/6	-1/10	-1/13	-1/7	-	-	-

Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис	B	x1	x2	x3	x4	x5	x6	x7
x3	1/3	6/13	10/13	1	7/13	-1/13	0	0
x6	-3/13	-5/13	48/13	0	-73/13	-10/13	1	0
x7	-9/13	-67/13	-51/13	0	-37/13	-4/13	0	1
F(X0)	-1/13	7/13	3/13	0	6/13	1/13	0	0

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

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (^-4/₁₃).

Базис	B	x1	x2	x3	x4	x5	x6	x7
x3	1/3	6/13	10/13	1	7/13	-1/13	0	0
x6	-3/13	-5/13	48/13	0	-73/13	-10/13	1	0
x7	-9/13	-67/13	-51/13	0	-37/13	-4/13	0	1
F(X0)	-1/13	7/13	3/13	0	6/13	1/13	0	0
и		-7/67	-3/51	-	-6/37	-1/4

Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис	B	x1	x2	x3	x4	x5	x6	x7
x3	1/4	7/4	7/4	1	5/4	0	0	-1/4
x6	3/2	25/2	27/2	0	3/2	0	1	-5/2
x5	9/4	67/4	51/4	0	37/4	1	0	-13/4
F(X1)	-1/4	-3/4	-3/4	0	-1/4	0	0	1/4

В базисном столбце все элементы положительные.

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

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

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

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

и из них выберем наименьшее:

………………………

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (²⁵/₂) и находится на пересечении ведущего столбца и ведущей строки.



Базис	B	x1	x2	x3	x4	x5	x6	x7	min
x3	1/4	7/4	7/4	1	5/4	0	0	-1/4	1/7
x6	3/2	25/2	27/2	0	3/2	0	1	-5/2	3/25
x5	9/4	67/4	51/4	0	37/4	1	0	-13/4	9/67
F(X1)	-1/4	-3/4	-3/4	0	-1/4	0	0	1/4

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7
x3	1/25	0	-7/50	1	26/25	0	-7/50	1/10
x1	3/25	1	27/25	0	3/25	0	2/25	-1/5
x5	6/25	0	-267/50	0	181/25	1	-67/50	1/10
F(X2)	-4/25	0	3/50	0	-4/25	0	3/50	1/10

Итерация №1.

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

В качестве ведущего выберем столбец, соответствующий переменной x₄.

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

и из них выберем наименьшее:

………………………

Следовательно, 3-я строка является ведущей.

Разрешающий элемент равен (¹⁸¹/₂₅) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	x7	min
x3	1/25	0	-7/50	1	26/25	0	-7/50	1/10	1/26
x1	3/25	1	27/25	0	3/25	0	2/25	-1/5	1
x5	6/25	0	-267/50	0	181/25	1	-67/50	1/10	6/181
F(X2)	-4/25	0	3/50	0	-4/25	0	3/50	1/10



Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7
x3	1/181	0	227/362	1	0	-26/181	19/362	31/362
x1	21/181	1	423/362	0	0	-3/181	37/362	-73/362
x4	6/181	0	-267/362	0	1	25/181	-67/362	5/362
F(X3)	-28/181	0	-21/362	0	0	4/181	11/362	37/362

Итерация №2.

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

В качестве ведущего выберем столбец, соответствующий переменной x₂.

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

и из них выберем наименьшее:

………………………

Следовательно, 1-я строка является ведущей.

Разрешающий элемент равен (¹⁸¹/₂₅) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	x7	min
x3	1/181	0	227/362	1	0	-26/181	19/362	31/362	2/227
x1	21/181	1	423/362	0	0	-3/181	37/362	-73/362	42/423
x4	6/181	0	-267/362	0	1	25/181	-67/362	5/362
F(X3)	-28/181	0	-21/362	0	0	4/181	11/362	37/362

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7
x2	2/227	0	1	362/227	0	-52/227	19/227	31/227
x1	24/227	1	0	-429/227	0	57/227	1/227	-82/227
x4	9/227	0	0	267/227	1	-7/227	-28/227	26/227
F(X4)	-35/227	0	0	21/227	0	2/227	8/227	25/227



Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план

Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5	x6	x7
x2	2/227	0	1	362/227	0	-52/227	19/227	31/227
x1	24/227	1	0	-429/227	0	57/227	1/227	-82/227
x4	9/227	0	0	267/227	1	-7/227	-28/227	26/227
F(X4)	-35/227	0	0	21/227	0	2/227	8/227	25/227

Оптимальный план можно записать так:

x₂ = ²/₂₂₇

x₁ = ²⁴/₂₂₇

x₄ = ⁹/₂₂₇

F(X) = = ³⁵/₂₂₇

Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:

p_i = g*x_i; q_i = g*y_i.

Цена игры: g = ²²⁷/₃₅

p₁ = ²²⁷/₃₅ * ²⁴/₂₂₇ = ²⁴/₃₅

p₂ = ²²⁷/₃₅ * ²/₂₂₇ = ²/₃₅

p₃ = 0

p₄ = ²²⁷/₃₅ * ⁹/₂₂₇ = ⁹/₃₅

Оптимальная смешанная стратегия игрока I:

P = (²⁴/₃₅; ²/₃₅; 0; ⁹/₃₅)

q₁ = ²²⁷/₃₅ * ²/₂₂₇ = ²/₃₅

q₂ = ²²⁷/₃₅ * ⁸/₂₂₇ = ⁸/₃₅

q₃ = ²²⁷/₃₅ * ²⁵/₂₂₇ = ⁵/₇

Оптимальная смешанная стратегия игрока II:

Q = (²/₃₅; ⁸/₃₅; ⁵/₇)

Цена игры: v=²²⁷/₃₅

4. Проверим правильность решения игры с помощью критерия оптимальности стратегии.

?a_ijq_j ? v

?a_ijp_i ? v

M(P₁; Q) = (6*²⁴/₃₅) + (10*²/₃₅) + (13*0) + (7*⁹/₃₅) = ²²⁷/₃₅ v

M(P₂; Q) = (5*²⁴/₃₅) + (4*²/₃₅) + (10*0) + (11*⁹/₃₅) = ²²⁷/₃₅ v

M(P₃; Q) = (7*²⁴/₃₅) + (7*²/₃₅) + (4*0) + (5*⁹/₃₅) = ²²⁷/₃₅ v

M (P; Q₁) = (6*²/₃₅) + (5*⁸/₃₅) + (7*⁵/₇) = ²²⁷/₃₅? v

M (P; Q₂) = (10*²/₃₅) + (4*⁸/₃₅) + (7*⁵/₇) = ²²⁷/₃₅? v

M (P; Q₃) = (13*²/₃₅) + (10*⁸/₃₅) + (4*⁵/₇)= ²²⁷/₃₅? v

M (P; Q₃) = (7*²/₃₅) + (11*⁸/₃₅) + (5*⁵/₇) = ²²⁷/₃₅? v

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

...