Содержание
Задача 1.
В соответствии с 11 вариантом, составить обратную задачу 10-й задаче.
Найти максимум функции F=5×1+5×2→max при ограничениях:
{█(x_1-4x_(2 )≤[email protected]_1+2x_2 ≤ [email protected]@x_1-x_2 ≥ -2)┤
Решение: x_1≥ 0 , x_2≥0
Разобьем третье неравенство системы ограничений исходного уравнения на два. Получим:
{█(x_1-4x_(2 ) ≤[email protected]_1+2x_2 ≤ [email protected]_1≤[email protected]_2 ≥- 2)┤
Так как исходная задача дана на максимизацию, то приведем все неравенства системы ограничений к виду "≤", для чего обе части первого, второго и четвертого неравенства умножим на -1. Так же разобьем третье неравенство на два.
Получим следующие ограничения:
{█(〖-x〗_1+4x_2≥[email protected]_1-2x_2≥[email protected]_1≤[email protected]_2 ≥[email protected])┤
Определим условные, относительные оценки ресурсов.
Обозначим их y1, y2, y3, y4, где Yi – условная цена соответствующего i – го ресурса (i = 1, 2, 3, 4,).
Тогда на основании прямой задачи можно составить обратную ей задачу.
Требуется найти Z = 4y1 +16y2 + 2y3 →min.
При условии:
1у + 1y+1y ≥5
4y+2 y-1y≥5 у1,у2,у3,у4 ≥0
Задача 2.
Для платежной матрицы определить нижнюю и верхнюю цены игры, минимальные стратегии и оптимальные решения игры, если существует седловая точка.
6. P=(█(■(0,2&0,8&0,[email protected],6&0,3&0,[email protected],8&0,5&0,4)@))
Решение. Все расчеты удобно проводить в таблице, в которой, кроме матрицы Р, введены столбец αi и строка βj (табл. 1).
Таблица 1
Bj
Ai B1 B2 B3 αi
A1 0,2 0,8 0,5 0,2
A2 0,6 0,3 0,9 0,3
A3 0,8 0,5 0,4 0,4
βj 0,8 0,8 0,9 α ≠ β
Анализируя строки матрицы (стратегии игрока А), заполняем столбец αi:
α1= 0,2, α2=0,3, α3=0,4, — минимальные числа в строках 1, 2, 3, Аналогично, β1 =0,6 β2 =0,3, β3 =0,9 — максимальные числа в столбцах 1, 2, 3 соответственно. Нижняя цена игры α=max┬(i=1,2,3,)〖α_i=max(0,2;0,3;0,4;) 〗 =0,3(наибольшее число в столбце αi) и верхняя цена игры β=min┬(j=1,2,3)〖β_j=min〖(0,8;0,8;0,9)〗 〗=0,8 (наименьшее число в строке βj). Эти значения не равны, т.е. α≠β, следовательно игра не имеет седловую точку, цена игры находится в пределах
Задача 3.
Рассчитать резерв времени для каждой работы, найти критический путь и временные параметры событий в нижеследующем сетевом графике:
Рис.1 Схема сетевого графика
Решение.
Определим, порядок внесения параметров в сетевой график:
i
tр(i) tп(i)
R(i)
Найденные данные сведем в табл. 1.
Таблица 1
Номер
события Сроки свершения события, сутки Резерв вре-
мени R(i),
час
ранний tp(i) поздний tn(i)
1 0 0 0
2 6 6 0
3 7 7 0
4 13 14 1
5 9 9 0
6 17 12 5
7 10 10 0
8 21 19 2
9 14 14 0
10 20 20 0
11 22 22 0
При определении ранних сроков свершения работ tp(i) двигаемся по сетевому графику слева направо и используем формулу:
где tp(i) — ранний (или ожидаемый) срок свершения i –го работы.
Для i = 1 tp(1) = 0, так как работа 1 начальное событие (нулевое).
Для i =2 tp(2) = tp(1) + t(1,2) = 0+6 =6 (часа), так как для работы 2 существует только один предшествующий путь Ln1 1→6
Для i = 3 tp(3) = max{tp(1)+t(1,3); tp(2)+t(2,3)} = mах{0+5; 6+1} = max{5; 7} =7 (часов), так как для работы 3 существуют два предшествующих пути Lп3 1→3 и 1→2→3 два предшествующих события 0 и 2
Аналогично:
tp(4) = max {tp(1)+t(1,4); tp(3)+t(3,4)} = max {0+7; 7+6} = max {7; 13} = 13 (часов);
tp (5) = max {tp(2)+t(2,5); tp(3)+t(3,5)} = max {6+1; 7+2} = max {7; 9} = 9 (часов);
tp (6) = max {tp(4)+t(4,6); tp(5)+t(5,6)} = max {13+4; 9+4} = max {17; 13} = 17 (часов);
tp(7) = tp(5) + t(5,7)=9+1 = 10 (часов);
tp (8) = max {tp(4)+t(4,8); tp(6)+t(6,8)} = max {13+5;17 +4} = max {18; 21} = 21 (часа);
tp (9) = max {tp(6)+t(6,9); tp(7)+t(7,9)} = max {17+2;10 +4} = max {19; 14} = 14 (часа);
tp (10) = max {tp(5)+t(5,10); tp(9)+t(9,10)} = max {9+4;14 +6} = max {13; 20} = 20 (часов);
tp (11) = max {tp(8)+t(8,11); tp(9)+t(9,11); tp(10)+t(10,11)} = max {21+3;14+3;20+2} = max {24; 17; 22} = 22 (часа)
Длина критического пути равна раннему сроку свершения завершающей работы 11 :
tкр=tp(11)=22 (часа).
При определении поздних сроков свершения работ tп(i) двигаемся по сети в обратном направлении, т.е. справа налево, и используем формулы:
где Lci – любой путь, следующий за i –м событием, т.е. путь от i –го до завершающего события сети.
Если работа i имеет несколько последующих путей, а, следовательно, несколько последующих работ j, то поздний срок свершения работы i удобно находить по формуле:
Для i = 11 (завершающей работы) поздний срок свершения работы должен равняться его раннему сроку (иначе изменится длина критического пути): tп(11)=tp(11)=22 (часа).
Для i = 10 tп(10) = tп(11)-t(10,11) = 22-2 = 20 (часов), так как для работы 10 существует только один последующий путь Lс10: 10→11.
Для i = 9 tп (9) = min {tп (10)-t(9,10); tп (11)-t(9,11)} = min {20-6; 22-3} = min {14; 19} =14 (часа), так как для работы 9 существуют два последующих пути Lс9: 9→10→11 и 9→11 и два последующих события 10 и 11.
Аналогично:
tп(8) = tп(11) — t(8,11) =22-3 = 19 (час);
tп(7) = tп(9) — t(9,7) = 14-4 = 10 (часов);
tп(6) = min { tп(9) –t(6, 9); tп(8) – t(6,8)} = min {14-2; 19-4} = min {12; 15} = 12 (часов);
tп(5) = min { tп(6) –t(5, 6); tп(7) – t(5,7); tп(10) – t(5,10)} = min {12-4; 10-1; 20-4} = min {8; 9; 16} = 9 (часов);
tп(4) = min { tп(6) –t(4, 6); tп(8) – t(4,8)} = min {12-4; 19-5} = min {8; 14} = 14 (часов);
tп(3) = min { tп(4) –t(3,4); tп(5) – t(3,5)} = min {14-6; 9-2} = min {8; 7} = 7 (часа);
tп(2) = min { tп(3) –t(2,3); tп(5) – t(2,5)} = min {7-1; 9-6} = min {6; 2} = 6 (часа);
tп(1) = min { tп(2) –t(1,2); tп(3) – t(1,3); tп(4) – t(1,4)} = min {6-6;7-5; 14-7} = min {0; 2; 7} = 0 (часов);
По формуле определяем резервы времени i-ой работы (R(i)):
R(1) = 0;
R(2) = 6-6 = 0;
R(3) = 7-7 = 0;
R(4) = 13-14 = 1;
R(5) = 9 — 9 = 0;
R(6) = 17-12 = 5;
R(7) = 10-10 = 0;
R(8) = 21-19 = 2;
R(9) = 14-14 = 0;
R(10) = 20-20 = 0;
R(11) = 22-22 = 0.
Резерв времени, например, работы 8 — R(8) = 8 — означает, что время свершения работы 8 может быть задержано на 8 часов без увеличения общего срока выполнения проекта. Анализируя табл. 1, видим, что не имеют резервов времени работы 1, 2, 3, 5, 7, 9, 10, 11. Эти события и образуют критический путь (на рис. 1 он выделен жирным шрифтом).
Выдержка из текста
Оглавление
Задача 1. 3
Задача 2. 3
Задача 3. 4
Список использованной литературы
1