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

Задача 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.

Находим гарантированный выигрыш, определяемый нижней ценой игры 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).

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

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

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

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

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

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

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

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

Итерация № 0.

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

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

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

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

…

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

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

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

Итерация № 1.

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

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

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

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

…

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

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

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

Итерация № 2.

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

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

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

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

…

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

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

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

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

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

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.