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

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ Государственное БЮДЖЕТНОЕ образовательное учреждение высшего профессионального образования «Московский государственный университет экономики, статистики и информатики (МЭСИ)»

Минский филиал

Кафедра Математики и информатики

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

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

Студент Довжная О.О.

Руководитель Лукин К.Д.

Минск 2015

Содержание

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

• Задание 1
• Задание 2
• Задание 3
• Задание 4
• Задание 5

Задача 1

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

при условии

Решение.

Применим метод исключения части переменных (т.к. система ограничений содержит только линейные уравнения, можно не применять метод множителей Лагранжа).

Выразим из условия y и z через х и подставим в выражение для функции:

Для нахождения экстремума продифференцируем полученное выражение, получим:

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

Значение функции в этой точке:

Таким образом, данная функция в точке (18/11; 5; 24/11) имеет при заданных условиях минимум, равный 1591/11.

Ответ: (18/11; 5; 24/11), 1591/11.

Задача2

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

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

2x₁+5x₂?20

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

Решение.

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

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

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

Применив теорему Куна-Такера, получим следующие условия для оптимального решения:

и условия дополняющей нежесткости

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

и условия дополняющей нежесткости

Запишем полученную систему в эквивалентном виде:

Необходимо найти допустимое базисное решение последней системы, удовлетворяющее всем условиям дополняющей нежесткости. Для этого применим метод искусственных переменных. Введем искусственные переменные y₁, y₂ в первые два ограничения, получим следующую задачу линейного программирования:

Минимизировать

f = M y₁ + My₂

При ограничениях

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

Получили следующее решение, удовлетворяющее условиям дополняющей нежесткости: х₁ = 5/2, х₂ = 3, z_max = 380.

Задача3

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

Решение.

Имеем l = 27, m = 30, коэффициент загрузки системы ш =l/m = 27/30 = 0.9.

Вероятность простоя системы вычисляется по формуле

Вероятность ожидания начала обслуживания вычисляется по формуле

Последняя характеристика позволяет решать задачу об определении оптимального числа каналов обслуживания с таким расчетом, чтобы вероятность ожидания начала обслуживания была меньше заданного числа. Для этого достаточно просчитать вероятность ожидания последовательно при s =1, s =2, s =3 и т.д.

Предположим, что имеется всего одна полоса. Найдем вероятность ожидания начала обслуживания при s = 1:

При s = 2:

При s = 3:

При s = 4:

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

Задача 4

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

Решение

а) Проверим условие существования седловой точки. Должно выполняться равенство

Следовательно, седловая точка не существует, и игра не имеет решения в чистых стратегиях.

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

Аналогично получаем для столбцов (стратегий II игрока).

в) Сведем данную матричную игру к паре двойственных задач линейного программирования. Чтобы упростить решение, вычтем из всех элементов платежной матрицы минимальное значение 4. Тогда получим эквивалентную игру

Пара двойственных задач линейного программирования запишется следующим образом:

1. Прямая задача (задача первого игрока :

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

2. Двойственная задача (задача второго игрока)

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

Решим двойственную задачу симплекс-методом: начальная таблица имеет вид

Отсюда находим решение задачи ЛП: точка максимума есть (2/87; 8/87; 25/87), w*=35/87 - максимальное значение целевой функции.

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

В исходной игре : , к полученному ранее значению игры 87/35 прибавили вычтенное число 4. Второй игрок должен в 2/35 процентов случаев выбирать первую стратегию, в 8/35 процентов случаев выбирать вторую стратегию и в 5/7 процентов случаев выбирать третью стратегию.

Оптимальная смешанная стратегия I игрока находится из последней строки последней симплексной таблицы и после преобразований равна . Таким образом, первый игрок должен в 24/35 процентов случаев выбирать первую стратегию, в 2/35 процентов случаев выбирать вторую стратегию, и в 9/35 процентов случаев выбирать четвертую стратегию.

Задача5

Построение и расчет сетевой модели.

Поданной таблице построить сетевой график и рассчитать его параметры

Решение

Построим сетевой график (введем две фиктивные работы а₁₂ и а₁₃ с нулевыми длительностями):

Характеристики событий

1. Ранний срок свершения события

t_p(0) = 0,

t_p(j) = max_i {t_p(i) + t(ij)}, j = 1N

2. Поздний срок свершения события

t_п(N) = t_p(N),

t_п(i) = min_j {t_п(j) - t(ij)}, i = 1N-1

3. Резерв времени события

R(i) = t_п(i) - t_p(i)

Табл.

Анализ таблицы и сетевого графика показывает, что критический путь (в событиях) имеет вид (0-1-2-7-8), а его длина равна t_кр=44.

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

Характеристики работы (i,j)

1. Ранний срок начала работ t_pн(i,j)=t_p(i).

2. Ранний срок окончания работы

t_po(i,j)= t_pн(i,j) + t_ij =t_p(i) + t_ij

3. Поздний срок начала работы:

t_пн(i,j)=t_п(j) - t_ij.

4. Поздний срок окончания работы: t_по(i,j) = t_п(j).

5. Резервы времени работ:

· полный резерв R_п(i,j) = t_п(j) - t_p(i) - t_ij.

· частный резерв R₁(i,j) = R_п(i,j) - R(i) = t_п(j) - t_п(i) - t_ij.

· свободный резерв R_с(i,j) = R_п(i,j) - R(j) = t_p(j) - t_p(i) - t_ij.

· независимый резерв R_н(i,j) = R_п(i,j) - R(i) - R(j) = t_p(j) - t_п(i) - t_ij.

Коэффициент напряженности работ:

К_н(i,j) = ( t(L_max)-t`_кр ) / (t_кр-t^'_кр) = 1 - R_п(i,j) / (t_кр-t^'_кр),

где t(L_max(i,j)) - продолжительность максимального пути L_max(i,j), проходящего через работу (i,j); t^'_кр - продолжительность отрезка пути L_max(i,j), совпадающего с критическим путем.

К_н(а₂) = (36-9) / (44-9) = 27 / 35 = 0,77,

К_н(а₄) = (38-14) / (44-14) = 24 / 30 = 0,8,

К_н(а₅) = (32-14) / (44-14) = 18 / 30 = 0,6,

К_н(а₆) = (26-14) / (44-14) = 12 / 30 = 0,4,

К_н(а₇) = (38-14) / (44-14) = 24 / 30 = 0,8,

К_н(а₈) = (38-5) / (44-5) = 33 / 39 = 0,85,

К_н(а₉) = (38-5) / (44-5) = 33 / 39 = 0,85,

К_н(а₁₂) = (38-14) / (44-14) = 24 / 30 = 0,8,

К_н(а₁₃) = (38-14) / (44-14) = 24 / 30 = 0,8.

Анализ таблицы и сетевого графика показывает, что критический путь (в работах) имеет вид (а₁ - а₃ - а₁₀ - а₁₁), а его длина равна t_кр=44.

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