Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

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

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

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

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

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

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

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

Вариант № 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

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

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

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

Решение:

Далее изобразим события 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;

tрн(F) = tрн(7,8) = tp(7) = 14;

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

tрo(С) = tрн(1,2) + t (1,2) =0+4=4

tрo(I) = tрн(1,3) + t (1,3) =0+3=3

tрo(G) = tрн(1,4) + t (1,4) = 0+5=5

tрo(E) = tрн(2,5) + t (2,5) = 4+7=11

tрo(A) = tрн(2,6) + t (2,6) =4+10=14

tрo(H) = tрн(3,6) + t (3,6) =3+8=11

tрo(D) = tрн(4,6) + t (4,6) =5+12=17

tрo(J) = tрн(4,7) + t (4,7) =5+9=14

tрo(B) = tрн(5,8) + t (5,8) =11+8=19

tрo(K) = tрн(6,8) + t (6,8) =17+10=27

tрo(F) = tрн(7,8) + t (7,8) =14+11=25

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

tпо(С) = tпо(1,2) = tп(2) = 7;

tпо(I) = tпо(1,3) = tп(3) = 9;

tпо(G) = tпо(1,4) = tп(4) = 5;

tпо(E) = tпо(2,5) = tп(5) = 19;

tпо(A) = tпо(2,6) = tп(6) = 17;

tпо(H) = tпо(3,6) = tп(6) = 17;

tпо(D) = tпо(4,6) = tп(6) = 17;

tпо(J) = tпо(4,7) = tп(7) = 16;

tпо(B) = tпо(5,8) = tп(8) = 27;

tпо(K) = tпо(6,8) = tп(8) = 27;

tпо(F) = tпо(7,8) = tп(8) = 27;

Резерв времени работы равен разности между поздним и ранним сроками ее окончания:

R(С) = tпо(1,2) - tpо(1,2) = 7-4=3

R(I) = tпо(1,3) – tpо(1,3) = 9-3=6

R(G) = tпо(1,4) – tpо(1,4) = 5-5=0

R(E) = tпо(2,5) – tpо(2,5) = 19-11=8

R(A) = tпо(2,6) – tpо(2,6) = 17-14=3

R(H) = tпо(3,6) – tpо(3,6) = 17-11=6

R(D) = tпо(4,6) – tpо(4,6) = 17-17=0

R(J) = tпо(4,7) – tpо(4,7) = 16-14=2

R(B) = tпо(5,8) – tpо(5,8) = 27-19=8

R(K) = tпо(6,8) – tpо(6,8) = 27-27=0

R(F) = tпо(7,8) – tpо(7,8) = 27-25=2

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

Определение критического пути на основании временных параметров событий и работ. Как известно, критические события и работы не имеют резерва времени. Поэтому критический путь пройдет по событиям 1, 4, 6, 8 будет состоять из работ G, D, K и иметь длину 27.

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

Работы	Какие работы следуют за Аi	время
А1	A2,A3	2
А2	A8	3
А3	A6,A7	4
А4	A6,A7	5
А5	A9	4
А6	A8	6
А7	-	4
А8	-	2
А9	-	7

Решение:

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

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

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

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

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

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

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

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

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

R(1) = 0;

R(2) = 2-2 = 0

R (3) = 6-6 = 0

R (4) = 12-12 = 0

R (5) = 14-14 = 0

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

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

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

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

tрн(1,5) = tp(1) = 0;

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

tрн(2,3) = tp(2) = 2;

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

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

tрн(4,5) = tp(4) = 12;

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

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

tро(1,3) = tpн(1) + t(1,3) = 0+5=5;

tро(1,5) = tpн(1) + t(1,5) = 0+7=7;

tро(2,4) = tpн(2) + t(2,4) = 2+3=5;

tро(2,3) = tpн(2) + t(2,3) = 2+4=6;

tро(3,4) = tpн(3) + t(3,4) = 6+6=12;

tро(3,5) = tpн(3) + t(3,5) = 6+4=10;

tро(4,5) = tpн(4) + t(4,5) = 12+2=14;

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

tпо(1,2) = tn(2) =2;

tпо(1,3) = tn(3) =6;

tпо(1,5) = tn(5) =14;

tпо(2,4) = tn(4) =12;

tпо(2,3) = tn(3) =6;

tпо(3,4) = tn(4) =14;

tпо(3,5) = tn(5) =14;

tпо(4,5) = tn(5) =14.

Резерв времени работы равен разности между поздним и ранним сроками ее окончания:

R(1,2) = tno(1,2) – tpo(1,2) = 2 – 2=0

R(1,3) = tno(1,3) – tpo(1,3) = 6 – 5=1

R(1,5) = tno(1,5) – tpo(1,5) = 14 – 7=7

R(2,4) = tno(2,4) – tpo(2,4) = 12 – 5=7

R(2,3) = tno(2,3) – tpo(2,3) =6 – 6=0

R(3,4) = tno(3,4) – tpo(3,4) = 14 – 12-2

R(3,5) = tno(3,5) – tpo(3,5) = 14 -10 =4

R(4,5) = tno(4,5) – tpo(4,5) = 14 -14-=0

Определение критического пути на основании временных параметров событий и работ. Как известно, критические события и работы не имеют резерва времени. Поэтому критический путь пройдет по событиям 1, 2, 3, 4, 5 будет состоять из работ (1,2), (2,3), (3,4) и (4,5) , критическое время – 14 дней.

Контрольная работа по Методам оптимальных решений. 4 📙 Контрольная → 🆔 62819