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

контрольная сдана и проверена,с развернутым решением ...

контрольная сдана и проверена,с развернутым решением

контрольная сдана и проверена,с развернутым решением

∑a = 240 + 160 + 200 = 600∑b = 180 + 40 + 160 + 120 + 100 = 600Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.Занесем исходные данные в распределительную таблицу.12345Запасы15815209240287612141603161119105200Потребности18040160120100I. 1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.12345Запасы15[180]8[40]1520[20]92402876[160]1214160316111910[100]5[100]200Потребности180401601201002. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным. Строим новый план.Значение целевой функции для этого опорного плана равно:F(x) = 5*180 + 8*40 + 20*20 + 6*160 + 10*100 + 5*100 = 408012345Запасы15[180]8[40]1520[20]92402876[160]1214160316111910[100]5[100]200Потребности180401601201002. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным. Строим новый план.Значение целевой функции для этого опорного плана равно:F(x) = 5*180 + 8*40 + 20*20 + 6*160 + 10*100 + 5*100 = 408012345Запасы15[180]8[40]1520[20]92402876[160]1214160316111910[100]5[100]200Потребности180401601201002. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным. Строим новый план.Значение целевой функции для этого опорного плана равно:F(x) = 5*180 + 8*40 + 20*20 + 6*160 + 10*100 + 5*100 = 408012345Запасы15[180]815[40]20[20]9240287[40]6[120]1214160316111910[100]5[100]200Потребности180401601201002. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.Значение целевой функции для этого опорного плана равно:F(x) = 5*180 + 15*40 + 20*20 + 7*40 + 6*120 + 10*100 + 5*100 = 4400II..Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.u1 + v1 = 5; 0 + v1 = 5; v1 = 5u1 + v3 = 15; 0 + v3 = 15; v3 = 15u2 + v3 = 6; 15 + u2 = 6; u2 = -9u2 + v2 = 7; -9 + v2 = 7; v2 = 16u1 + v4 = 20; 0 + v4 = 20; v4 = 20u3 + v4 = 10; 20 + u3 = 10; u3 = -10u3 + v5 = 5; -10 + v5 = 5; v5 = 15v1=5v2=16v3=15v4=20v5=15u1=05[180]815[40]20[20]9u2=-987[40]6[120]1214u3=-1016111910[100]5[100]Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij(1;2): 0 + 16 > 8; ∆12 = 0 + 16 - 8 = 8(1;5): 0 + 15 > 9; ∆15 = 0 + 15 - 9 = 6max(8,6) = 8Выбираем максимальную оценку свободной клетки (1;2): 8Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».12345Запасы15[180]8[+]15[40][-]20[20]9240287[40][-]6[120][+]1214160316111910[100]5[100]200Потребности18040160120100Цикл приведен в таблице (1,2 → 1,3 → 2,3 → 2,2).12345Запасы15[180]8[40]15[0]20[20]92402876[160]1214160316111910[100]5[100]200Потребности18040160120100Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.u1 + v1 = 5; 0 + v1 = 5; v1 = 5u1 + v2 = 8; 0 + v2 = 8; v2 = 8u1 + v3 = 15; 0 + v3 = 15; v3 = 15u2 + v3 = 6; 15 + u2 = 6; u2 = -9u1 + v4 = 20; 0 + v4 = 20; v4 = 20u3 + v4 = 10; 20 + u3 = 10; u3 = -10u3 + v5 = 5; -10 + v5 = 5; v5 = 15v1=5v2=8v3=15v4=20v5=15u1=05[180]8[40]15[0]20[20]9u2=-9876[160]1214u3=-1016111910[100]5[100]Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij(1;5): 0 + 15 > 9; ∆15 = 0 + 15 - 9 = 6Выбираем максимальную оценку свободной клетки (1;5): 912345Запасы15[180]8[40]15[0]20[20][-]9[+]2402876[160]1214160316111910[100][+]5[100][-]200Потребности18040160120100Цикл приведен в таблице (1,5 → 1,4 → 3,4 → 3,5).12345Запасы15[180]8[40]15[0]209[20]2402876[160]1214160316111910[120]5[80]200Потребности18040160120100Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.u1 + v1 = 5; 0 + v1 = 5; v1 = 5u1 + v2 = 8; 0 + v2 = 8; v2 = 8u1 + v3 = 15; 0 + v3 = 15; v3 = 15u2 + v3 = 6; 15 + u2 = 6; u2 = -9u1 + v5 = 9; 0 + v5 = 9; v5 = 9u3 + v5 = 5; 9 + u3 = 5; u3 = -4u3 + v4 = 10; -4 + v4 = 10; v4 = 14v1=5v2=8v3=15v4=14v5=9u1=05[180]8[40]15[0]209[20]u2=-9876[160]1214u3=-416111910[120]5[80]Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.Минимальные затраты составят: F(x) = 5*180 + 8*40 + 9*20 + 6*160 + 10*120 + 5*80 = 3960 ВыводИз 1-го склада необходимо груз направить в 1-й магазин (180), в 2-й магазин (40), в 5-й магазин (20)Из 2-го склада необходимо весь груз направить в 3-й магазинИз 3-го склада необходимо груз направить в 4-й магазин (120), в 5-й магазин (80)Задача имеет множество оптимальных планов, поскольку оценка для (1;3) равна 0.Задание №3Условие.Предприниматель планирует закупку трех партий новых товаров (П1,П2, П3) вусловиях неясной рыночной конъюнктуры, относительно которой известны возможные состояния (Р1, Р2 ,Р3), а также объемы товарооборота по каждомуварианту и их условные вероятности. Определить предпочтительный план закупки товаров, решение игры провести с использованием критериев Вальда, Гурвица с параметром k=0,4, Лапласа (1-5 варианты); Вальда, Сэвиджа, Байеса (6-10 варианты)).Решение.Критерий Байеса.По критерию Байеса за оптимальные принимается та стратегия (чистая) Ai, при которой максимизируется средний выигрыш a или минимизируется средний риск r.Считаем значения ∑(aijpj)∑(a1,jpj) = 3.4•0.5 + 1.9•0.2 + 2.7•0.3 = 2.89∑(a2,jpj) = 2.4•0.5 + 2.8•0.2 + 2.3•0.3 = 2.45∑(a3,jpj) = 2.2•0.5 + 3•0.2 + 2.8•0.3 = 2.54AiП1П2П3∑(aijpj)A11.70.380.812.89A21.20.560.692.45A31.10.60.842.54pj0.50.20.3Выбираем из (2.89; 2.45; 2.54) максимальный элемент max=2.89Вывод: выбираем стратегию N=1.Критерий Вальда.По критерию Вальда за оптимальную принимается чистая стратегия, которая в наихудших условиях гарантирует максимальный выигрыш, т.е.a = max(min aij)Критерий Вальда ориентирует статистику на самые неблагоприятные состояния природы, т.е. этот критерий выражает пессимистическую оценку ситуации.AiП1П2П3min(aij)A13.41.92.71.9A22.42.82.32.3A32.232.82.2Выбираем из (1.9; 2.3; 2.2) максимальный элемент max=2.3Вывод: выбираем стратегию N=2.Критерий Сэвиджа.Критерий минимального риска Сэвиджа рекомендует выбирать в качестве оптимальной стратегии ту, при которой величина максимального риска минимизируется в наихудших условиях, т.е. обеспечивается:a = min(max rij)Критерий Сэвиджа ориентирует статистику на самые неблагоприятные состояния природы, т.е. этот критерий выражает пессимистическую оценку ситуации.Находим матрицу рисков.1. Рассчитываем 1-й столбец матрицы рисков.r11 = 3.4 - 3.4 = 0; r21 = 3.4 - 2.4 = 1; r31 = 3.4 - 2.2 = 1.2; 2. Рассчитываем 2-й столбец матрицы рисков.r12 = 3 - 1.9 = 1.1; r22 = 3 - 2.8 = 0.2; r32 = 3 - 3 = 0; 3. Рассчитываем 3-й столбец матрицы рисков.r13 = 2.8 - 2.7 = 0.1; r23 = 2.8 - 2.3 = 0.5; r33 = 2.8 - 2.8 = 0; AiП1П2П3A101.10.1A210.20.5A31.200Результаты вычислений оформим в виде таблицы.AiП1П2П3max(aij)A101.10.11.1A210.20.51A31.2001.2Выбираем из (1.1; 1; 1.2) минимальный элемент min=1Вывод: выбираем стратегию N=2.Таким образом, в результате решения статистической игры по различным критериям чаще других рекомендовалась стратегия A2.Задание №4Условие.Дана таблица структурно-временных параметров комплекса работ и сетевой граф, отражающий порядок и взаимосвязь данных работ. Необходимо рассчитать основные параметры сетевого план-графика (ранние сроки наступления событий, ранние сроки окончания работ, поздние сроки наступления событий, поздние сроки начала работ, полный и свободный резервы времени) и построить критические пути.Решение.Расчет сроков свершения событий.Для i=0 (начального события), очевидно tp(0)=0.i=1: tp(1) = tp(0) + t(0,1) = 0 + 2 = 2.i=2: tp(2) = tp(0) + t(0,2) = 0 + 3 = 3.i=3: tp(3) = tp(1) + t(1,3) = 2 + 2 = 4.i=4: max(tp(1) + t(1,4);tp(3) + t(3,4)) = max(2 + 3;4 + 1) = 5.i=5: max(tp(2) + t(2,5);tp(3) + t(3,5)) = max(3 + 8;4 + 7) = 11.i=6: max(tp(4) + t(4,6);tp(5) + t(5,6)) = max(5 + 5;11 + 4) = 15.Длина критического пути равна раннему сроку свершения завершающего события 6: tkp=tp(6)=15При определении поздних сроков свершения событий tп(i) двигаемся по сети в обратном направлении, то есть справа налево и используем формулы (3), (4).Для i=6 (завершающего события) поздний срок свершения события должен равняться его раннему сроку (иначе изменится длина критического пути): tп(6)= tр(6)=15Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 5. Просматриваются все строчки, начинающиеся с номера 5.i=5: tп(5) = tп(6) - t(5,6) = 15 - 4 = 11.Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 4. Просматриваются все строчки, начинающиеся с номера 4.