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

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

 

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

 

 

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

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

Вариант № 7

 

 

Студент ___Науменко Е.И._________ ___________ ________

(Ф.И.О., группа, номер зачетной  книжки) (подпись) (дата)

 

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

(Ф.И.О.) (подпись) (дата)

 

Зарегистрировано

на кафедре _______________________ ___________ ________

(Ф.И.О.) (подпись) (дата)

 

 

 

 

 

 

Минск 2015

 

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

 

Решение:

Условным экстремумом функции  u= f (x, y, z)   называется экстремум этой функции в том случае, когда переменные x и y связаны уравнениями  li (x, y, z) = 0,  i=1…n (уравнения  связи)

Нахождение условного экстремума можно свести к исследованию на обычный экстремум функции Лагранжа:

                                    F(x, y, z) = u(x, y, z)  + Σ λi li (x, y, z),                                   

где  λi – некоторые постоянные множители.

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

                (*)

 Из этой системы трех уравнений можно найти неизвестные х, у, z и li. Вопрос о существовании и характере условного экстремума решается на основании  знака второго дифференциала функции Лагранжа:

Если в найденной точке (x0, y0)    , то функция имеет условный минимум, если же , - то условный максимум.

 

Итак, для исходной задачи:

u (x, y, z) = 2x2 + 5y2 + 3z2

l1 (x, y, z) = 2x - y + 4z – 7

l2 (x, y, z) = 3x - 2y + 6z - 8

 

Тогда функция Лагранжа будет иметь вид:

 F(x, y, z) = 2x2 + 5y2 + 3z2  + λ1 (2x - y + 4z – 7) + λ2 (3x - 2y + 6z - 8)

Запишем необходимые условия экстремума функции:

Запишем систему в виде:

(5 уравнений с пятью  неизвестными).

Будем решать методом Крамера (используем функцию «МОПРЕД» MS Excel)

Тогда:

x = 288 / 176  = 1,636

y = 880 / 176  = 5

z= 384 / 176   = 2,182

λ1 = -28704 / 176 = -163

λ1 = 18752 / 176 = 106,5

 

 Итак, в точке (1,636;  5;  2,182) возможен экстремум.

Запишем второй дифференциал функции Лангранжа:

F(x, y, z) = 2x2 + 5y2 + 3z2  + λ1 (2x - y + 4z – 7) + λ2 (3x - 2y + 6z - 8)

Как видим,

Следовательно, точка (1,636;  5;  2,182) –точка условного минимума.

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

Ответ: (1,636;  5;  2,182) –точка условного минимума,

 

 

 

Задача 2. В пятиугольнике с вершинами  O(0,0), A(0,6), B(5,8), D(0,4), E(8,0) найти экстремум функции

z = 18x1 + 16x2 - 3x12 - x1x2 - 5x22  → max

 

Решение:

 

Изобразим данную область:

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

 

Точки экстремума в некоторой область могут находиться как внутри этой области, так и на ее границе.

 

* Определим, имеет ли функция экстремумы внутри данной области:

Вычислим частные производные:

 

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

Получили стационарную точку:

A1(2,78; 1,32) – точка

Вычислим вторые производные:

Вычисляем выражение

:

Делаем вывод: в точке (2,78; 1,32) есть экстремум, максимум.

 

* Исследуем функцию на границе области:

На отрезке OA  x1=0, поэтому исследуем функцию z = 16x2 - 5x22

  0  ≤  x2  ≤ 6

Находим производную и приравниваем к нулю:  16-10x2=0.

Получили:  x2 = 1,6 ;  x1=0

A2(0; 1,6)

 

На отрезке OE:  x2=0, поэтому исследуем функцию z = 18x1 - 3x12

  0  ≤  x1  ≤ 8

Находим производную и приравниваем к нулю:  18-6x1=0.

Получили:  x1 = 3 ;  x2=0

A3(3; 0)

 

На отрезке AB: 2x1 – 5x2=30, выражаем x1: x1 = 15 + 1,5x2

z = 18·15+18·1,5x2 + 16x2 – 3(15 + 1,5x2 )2 – x2(15 + 1,5x2) - 5x22  = -13,25 x22 -107 x2 - 405

Находим производную и приравниваем к нулю:  -26,5x2-107=0.

Получили:  x2= -4,03;   x1 = 15 – 1,5·4,03=8,95  - точка (8,95;  -4,03) не принадлежит области.

 

На отрезке BE: 8x1 +3x2=64, выражаем x1: x1 = 64 - 0,38 x2

z = 18·64 -18·0,38 x2 + 16x2 – 3(64 - 0,38x2 )2 – x2(64 - 0,38x2) - 5x22  = -5,05 x22 -24,5 x2 - 11136

Находим производную и приравниваем к нулю:  -10,1x2-24,5=0.

Получили:  x2= -2,43;   x1 = 64 +0,38·2,43=64,92,1  - точка (64,92;  -2,43) не принадлежит области.

 

Итак, находим значения функции в найденных стационарных точках A1, A2, A3, а также в вершинах многоугольника:

z (x1, x2) = 18x1 + 16x2 - 3x12 - x1x2 - 5x22  =

z (A1) = z (2,78; 1,32) =35, 59

z (A2) = z (0; 1,6) = 12,8

z (A3) = z (3; 0) = 27

z (O) = z (0; 0) = 0

z (A) = z (0; 6) = -84

z (B) = z (5; 8) = -217

z (E) = z (8; 0) = -48

Итак, функция достигает максимум в точке (2,78; 1,32), находящейся внутри области.

Ответ: z max(2,78; 1,32) =35, 59

 

 

 

Задача 3.  Среднее число заказов такси, поступающих на диспетчерский пункт по двум телефонам в течение часа – 120. Среднее время оформления одного заказа – 4 минуты. Определить и дать оценку показателям эффективности системы массового обслуживания. 

 

Решение:

Запишем исходные данные задач :

n=2  – количество телефонов (каналов системы массового обслуживания);

            т.к. n=2, то данная система массового обслуживания является двухканальной.

t=4 мин – среднее время оформления одного заказа. 

λ=120  – интенсивность потока заказов (заказов/час) – среднее кол-во заказов, поступающих в час.

 

Определим основные характеристики СМО:

μ=60/t=60/4=15 – интенсивность потока обслуживания (заявок/час) – среднее кол-во заявок, которое может быть обслужено за час.

ρ= λ· t/60=120· 4/60 = 8 – интенсивность нагрузки - степень согласованности входного и выходного потоков заявок канала обслуживания.

 

Пронумеруем состояния СМО по числу заказов, находящихся в системе:

 S0 — оба телефона свободны;

 S1 — один телефон занят(оформляет заявку);

 S2 — два телефона занято(оформляют заявки)

.

Вероятность того, что система находится в состоянии S0 и  Sk соответственно:

        

- вероятность того, что  система будет свободна

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

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

 

A= λ ·(1 – pn) = 120·(1 – 0,64) = 43,2  - абсолютная пропускная способность

 

Q=  (1 – pn) =  (1 – 0,64) = 0,36  - относительная пропускная способность

 

Pотк = pn  = 0,64  -  вероятность отказа

 

 

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

  

 

Решение:

Итак, запишем платежную матрицу игры:

Игроки	B1	B2	a=min(Ai)
A1	2	-1	-1
A2	1	3	1
b=max(Bj)	2	3

 

Находим гарантированный выигрыш игрока А, определяемый нижней ценой игры a = max(ai) = 1, которая указывает на максимальную чистую стратегию A2. 
Верхняя цена игры b = min(bj) = 2. Так как a ≠ b, то седловая точка отсутствует, цена игры находится в пределах 1 <= y <= 2. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).

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

 
Решим задачу геометрическим методом:

1. В декартовой  системе координат по оси абсцисс  откладывается отрезок, длина которого  равна 1. Левый конец отрезка (точка  х = 0) соответствует стратегии A1, правый - стратегии A2 (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S1 = (p1,p2).

2. На левой оси  ординат откладываются выигрыши  стратегии A1. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии A2.

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

Максиминной оптимальной стратегии игрока A соответствует точка N, лежащая на пересечении прямых B1B1 и B2B2, для которых можно записать следующую систему уравнений:

y = 2 + (1 - 2)p2

y = -1 + (3 - (-1))p2

 

Откуда

p1 = 2/5

p2 = 3/5

Цена игры, y = 7/5

Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений

2q1-q2 = y

q1+3q2 = y

q1+q2 = 1

откуда:

q1 = 4/5

q2 = 1/5

 

Цена игры: y = 7/5, векторы стратегии игроков: Q(4/5, 1/5), P(2/5, 3/5)

Ответ: Цена игры: y = 7/5, векторы стратегии игроков: Q(4/5, 1/5), P(2/5, 3/5)

 

 

 

 

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

В таблице даны названия и продолжительность работ

Работы	A	B	C	D	E	F	G	H	JI	J	K
Продолж.	10	8	4	12	7	11	5	8	3	9	10

 

Упорядочение работ:

1. Работы C, I, G являются исходными работами проекта, которые могут выполняться одновременно.
2. Работы E и A следуют за работой C.
3. Работа H следует за работой I.
4. Работы D и J следуют за работой G.
5. Работа B следует за работой E.
6. Работа K следует за работами A и D, но не может начаться прежде, чем не завершится работа H.
7. Работа F следует за работой J.

Требуется составить сетевую модель и рассчитать ее параметры.

   

Решение:

 

1. Построение сетевого графика. Будем называть событиями моменты, возникающие в начале или конце работы. Считаем  событие 1 началом всего проекта (исходное событие). Изобразим в виде дуг графа (стрелочек) работы C, I, G, исходящие из события 1.

 

Далее изобразим события 2, 3, 4 и отмечаем работы E и A, которые следуют за работой C (исходят из события 2), работу H, которая следует за работой I (исходят из события 3) и работы D  и J, исходящие из события 4 соответственно:

Добавляем события 5, 6, 7 и изображаем завершающие работы B, K, F.

 

 

Итак, на графике построены все работы, перечисленные в исходной таблице. Вершина 1 представляет собой факт начало всего проекта,  вершина 8 представляет собой факт завершения всего проекта.

 

Рассчитаем основные параметры сетевого графика:

 

Определение параметров событий:

Определение ранних сроков свершения событий.

Ранний срок наступления события j – это самый ранний момент времени, к которому завершаются все работы, предшествующие этому событию:

В нашем случае:

 

Определение поздних сроков свершения событий.

Поздний срок наступления события j – такой предельный момент времени, после которого остается столько времени, сколько необходимо для завершения всех работ, следующих за этим событием:

В нашем случае:

Итак, минимальное время, за которое может быть выполнен весь комплекс работ составляет 27 дней.

 

Определение резервов времени событий. Резерв времени события определяется как разность между поздним и ранним сроками свершения этого события:

R(1) =  0;

R(2) = 7-4 = 3

R (3) = 9-3 = 6

R (4) = 5-5 = 0

R (5) = 19-11 = 8

R (6) = 17-17 = 0

R (7) = 16-14 = 2

R (5) = 27-27 = 0

 

 

 Определение параметров работ.

Ранний срок начала работы совпадает с ранним сроком свершения  начального события работы:

tрн(С) = tрн(1,2) = tp(1) = 0;

tрн(I) = tрн(1,3) = tp(1) = 0;

tрн(G) = tрн(1,4) = tp(1) = 0;

tрн(E) = tрн(2,5) = tp(2) = 4;

tрн(A) = tрн(2,6) = tp(2) = 4;

tрн(H) = tрн(3,6) = tp(3) = 3;

tрн(D) = tрн(4,6) = tp(4) = 5;

tрн(J) = tрн(4,7) = tp(4) = 5;

tрн(B) = tрн(5,8) = tp(5) = 11;

tрн(K) = tрн(6,8) = tp(6) = 17;