Эксперт

Сергей

Задать вопрос

Мы готовы помочь Вам.

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

1. Автотранспортная фирма обеспечивает доставку одних и тех же строительных  блоков с 3-х железобетонных заводов на четыре строительные площадки. Вектор заводов поставщиков  , вектор спроса строительных площадок   . Тарифы на перевозку одного блока с каждого завода на соответствующую площадку заданы матрицей

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

Решение:
Математическая модель транспортной задачи:
F = ∑∑cijxij,    (1)
при условиях:
∑xij = ai,  i = 1,2,…, m,   (2)
∑xij = bj,  j = 1,2,…, n,   (3)
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
1    2    3    4    Запасы
1    3    2    4    3    30
2    2    1    3    4    20
3    3    5    2    6    40
Потребности    10    30    30    20

Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 30 + 20 + 40 = 90
∑b = 10 + 30 + 30 + 20 = 90
Занесем исходные данные в распределительную таблицу.
1    2    3    4    Запасы
1    3    2    4    3    30
2    2    1    3    4    20
3    3    5    2    6    40
Потребности    10    30    30    20

Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
1    2    3    4    Запасы
1    3[10]    2[10]    4    3[10]    30
2    2    1[20]    3    4    20
3    3    5    2[30]    6[10]    40
Потребности    10    30    30    20
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.

2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n – 1 = 6. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
v1=3    v2=2    v3=-1    v4=3
u1=0    3[10]    2[10]    4    3[10]
u2=-1    2    1[20]    3    4
u3=3    3    5    2[30]    6[10]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (3;1): 3
Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1    2    3    4    Запасы
1    3[10][-]    2[10]    4    3[10][+]    30
2    2    1[20]    3    4    20
3    3[+]    5    2[30]    6[10][-]    40
Потребности    10    30    30    20

Цикл приведен в таблице (3,1; 3,4; 1,4; 1,1; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1    2    3    4    Запасы
1    3    2[10]    4    3[20]    30
2    2    1[20]    3    4    20
3    3[10]    5    2[30]    6[0]    40
Потребности    10    30    30    20

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
v1=0    v2=2    v3=-1    v4=3
u1=0    3    2[10]    4    3[20]
u2=-1    2    1[20]    3    4
u3=3    3[10]    5    2[30]    6[0]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.
Минимальные затраты составят:
F(x) = 2*10 + 3*20 + 1*20 + 3*10 + 2*30  = 190

2. Полагая матрицу  А  во второй задаче матрицей игры с природой найти решение игры используя критерии Вальда, Сэвиджа и Гурвица (коэффициент  к  для критерия Гурвица положить равным 0,7).

Решение:
Критерий Вальда.
По критерию Вальда за оптимальную принимается чистая стратегия, которая в наихудших условиях гарантирует максимальный выигрыш, т.е.
a = max(min aij)
Критерий Вальда ориентирует статистику на самые неблагоприятные состояния природы, т.е. этот критерий выражает пессимистическую оценку ситуации.
Ai    П1    П2    П3    П4    min(aij)
A1    3    5    2    2    2
A2    0    6    8    9    0
A3    4    1    3    3    1
A4    -4    4    0    1    -4

Выбираем из (2; 0; 1; -4) максимальный элемент max=2
Вывод: выбираем стратегию N=1.
Критерий Севиджа.
Критерий минимального риска Севиджа рекомендует выбирать в качестве оптимальной стратегии ту, при которой величина максимального риска минимизируется в наихудших условиях, т.е. обеспечивается:
a = min(max rij)
Критерий Сэвиджа ориентирует статистику на самые неблагоприятные состояния природы, т.е. этот критерий выражает пессимистическую оценку ситуации.
Находим матрицу рисков.
Риск – мера несоответствия между разными возможными результатами принятия определенных стратегий. Максимальный выигрыш в j-м столбце bj = max(aij) характеризует благоприятность состояния природы.
1. Расчитываем 1-й столбец матрицы рисков.
r11 = 4 – 3 = 1; r21 = 4 – 0 = 4; r31 = 4 – 4 = 0; r41 = 4 – (-4) = 8;
2. Расчитываем 2-й столбец матрицы рисков.
r12 = 6 – 5 = 1; r22 = 6 – 6 = 0; r32 = 6 – 1 = 5; r42 = 6 – 4 = 2;
3. Расчитываем 3-й столбец матрицы рисков.
r13 = 8 – 2 = 6; r23 = 8 – 8 = 0; r33 = 8 – 3 = 5; r43 = 8 – 0 = 8;
4. Расчитываем 4-й столбец матрицы рисков.
r14 = 9 – 2 = 7; r24 = 9 – 9 = 0; r34 = 9 – 3 = 6; r44 = 9 – 1 = 8;
Ai    П1    П2    П3    П4
A1    1    1    6    7
A2    4    0    0    0
A3    0    5    5    6
A4    8    2    8    8

Результаты вычислений оформим в виде таблицы.
Ai    П1    П2    П3    П4    max(aij)
A1    1    1    6    7    7
A2    4    0    0    0    4
A3    0    5    5    6    6
A4    8    2    8    8    8

Выбираем из (7; 4; 6; 8) минимальный элемент min=4
Вывод: выбираем стратегию N=2.
Критерий Гурвица.
Критерий Гурвица является критерием пессимизма – оптимизма. За (оптимальную принимается та стратегия, для которой выполняется соотношение:
max(si)
где si = y min(aij) + (1-y)max(aij)
При y = 1 получим критерий Вальде, при y = 0 получим – оптимистический критерий (максимакс).
Критерий Гурвица учитывает возможность как наихудшего, так и наилучшего для человека поведения природы. Как выбирается y? Чем хуже последствия ошибочных решений, тем больше желание застраховаться от ошибок, тем y ближе к 1.
Расчитываем si.
s1 = 0.7•2+(1-0.7)•5 = 2.9
s2 = 0.7•0+(1-0.7)•9 = 2.7
s3 = 0.7•1+(1-0.7)•4 = 1.9
s4 = 0.7•(-4)+(1-0.7)•4 = -1.6
Ai    П1    П2    П3    П4    min(aij)    max(aij)    y min(aij) + (1-y)max(aij)
A1    3    5    2    2    2    5    2.9
A2    0    6    8    9    0    9    2.7
A3    4    1    3    3    1    4    1.9
A4    -4    4    0    1    -4    4    -1.6

Выбираем из (2.9; 2.7; 1.9; -1.6) максимальный элемент max=2.9
Вывод: выбираем стратегию N=1.
Таким образом, в результате решения статистической игры по различным критериям чаще других рекомендовалась стратегия A1.

3. Анализируется работа междугородного переговорного пункта в небольшом городке. Пункт имеет один телефонный аппарат для переговоров. В среднем за сутки поступает 240 заявок на переговоры. Средняя длительность переговоров (с учетом вызова абонентов в другом городе) составляет 5 мин. Никаких ограничений на длину очереди нет. Потоки заявок и обслуживаний простейшие. Определить предельные вероятности состояний и характеристики обслуживания переговорного пункта в стационарном режиме.

Решение:
Исчисляем показатели обслуживания для одноканальной СМО:
Интенсивность потока обслуживания:
μ = 15 = 0.2
1. Интенсивность нагрузки.
ρ = λ • tобс = 0.16666 • 5 = 0.83
Интенсивность нагрузки ρ=0.83 показывает степень согласованности входного и выходного потоков заявок канала обслуживания и определяет устойчивость системы массового обслуживания.
Поскольку ρ < 1, то очередь не будет расти бесконечно, следовательно, предельные вероятности существуют.
3. Вероятность, что канал свободен (доля времени простоя канала).
p0 = 1 – ρ = 1 – 0.83 = 0.17
Следовательно, 17% в течение часа канал будет не занят, время простоя равно tпр = 10 мин.
Вероятность того, что в очереди:
1 заявка:
p1  = ρ(1 – ρ) = 0.831(1 – 0.83) = 0.14
2 заявка:
p2  = ρ(1 – ρ) = 0.832(1 – 0.83) = 0.12
3 заявка:
p3  = ρ(1 – ρ) = 0.833(1 – 0.83) = 0.0965
4 заявка:
p4  = ρ(1 – ρ) = 0.834(1 – 0.83) = 0.0804
5 заявка:
p5  = ρ(1 – ρ) = 0.835(1 – 0.83) = 0.067
4. Доля заявок, получивших отказ.
p1  = 1 – p0 = 1 – 0.17 = 0.83
Значит, 83% из числа поступивших заявок не принимаются к обслуживанию.
5. Относительная пропускная способность.
Поскольку в рассматриваемой СМО ограничение на длину очереди отсутствует, то любая заявка может быть обслужена, поэтому Q = pобс = 1.
6. Абсолютная пропускная способность.
A = Q • λ = 1 • 0.16666 = 0.167 заявок/мин.
8. Среднее число заявок в очереди (средняя длина очереди).
Lоч = ρ21 – ρ = 0.8321 – 0.83 = 4.17
9. Среднее время простоя СМО (среднее время ожидания обслуживания заявки в очереди).
Tоч = LочA = 4.170.167 = 24.99 мин.
10. Среднее число обслуживаемых заявок.
Lоб = ρ = 0.83
12. Среднее число заявок в системе.
LCMO = Lоч + Lобс = 4.17 + 0.83 = 5 ед.
13. Среднее время пребывания заявки в СМО.
TCMO = LCMOA = 50.167 = 29.99 мин