2818_Основы_мат_моделирования. Задача 1 Решить задачу с помощью симплексного метода Найти максимум целевой функции при данной системе ограничений
 Скачать 46.16 Kb.
|
1 2 Задача 2Найти оптимальный план транспортной задачи: 14. Три предприятия одного экономического района могут производить некоторую продукцию в количествах, соответственно равных 180, 350 и 20 ед. Эта продукция должна быть поставлена пяти потребителям в количествах 110, 90, 120, 80 и 150 ед. Затраты, связанные с производством и доставкой единицы продукции, задаются матрицей  .Составить такой план прикрепления получателей продукции к ее поставщикам, при котором общая стоимость перевозок является минимальной, и найти оптимальное решение. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 180 + 350 + 20 = 550 ∑b = 110 + 90 + 120 + 80 + 150 = 550 Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой. Занесем исходные данные в распределительную таблицу.
Поиск первого опорного плана. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи. Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj. Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены. Искомый элемент равен c21=1. Для этого элемента запасы равны 350, потребности 110. Поскольку минимальным является 110, то вычитаем его. x21 = min(350,110) = 110.
Искомый элемент равен c25=3. Для этого элемента запасы равны 240, потребности 150. Поскольку минимальным является 150, то вычитаем его. x25 = min(240,150) = 150.
Искомый элемент равен c13=4. Для этого элемента запасы равны 180, потребности 120. Поскольку минимальным является 120, то вычитаем его. x13 = min(180,120) = 120.
Искомый элемент равен c24=5. Для этого элемента запасы равны 90, потребности 80. Поскольку минимальным является 80, то вычитаем его. x24 = min(90,80) = 80.
Искомый элемент равен c22=8. Для этого элемента запасы равны 10, потребности 90. Поскольку минимальным является 10, то вычитаем его. x22 = min(10,90) = 10.
Искомый элемент равен c12=12. Для этого элемента запасы равны 60, потребности 80. Поскольку минимальным является 60, то вычитаем его. x12 = min(60,80) = 60.
Искомый элемент равен c32=13. Для этого элемента запасы равны 20, потребности 20. Поскольку минимальным является 20, то вычитаем его. x32 = min(20,20) = 20.
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность потребительов удовлетворена, а план соответствует системе ограничений транспортной задачи. 2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 12*60 + 4*120 + 1*110 + 8*10 + 5*80 + 3*150 + 13*20 = 2500 Улучшение опорного плана. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v2 = 12; 0 + v2 = 12; v2 = 12 u2 + v2 = 8; 12 + u2 = 8; u2 = -4 u2 + v1 = 1; -4 + v1 = 1; v1 = 5 u2 + v4 = 5; -4 + v4 = 5; v4 = 9 u2 + v5 = 3; -4 + v5 = 3; v5 = 7 u3 + v2 = 13; 12 + u3 = 13; u3 = 1 u1 + v3 = 4; 0 + v3 = 4; v3 = 4
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (1;4): 0 + 9 > 8; ∆14 = 0 + 9 - 8 = 1 > 0 (1;5): 0 + 7 > 5; ∆15 = 0 + 7 - 5 = 2 > 0 (3;4): 1 + 9 > 7; ∆34 = 1 + 9 - 7 = 3 > 0 (3;5): 1 + 7 > 4; ∆35 = 1 + 7 - 4 = 4 > 0 max(1,2,3,4) = 4 Выбираем максимальную оценку свободной клетки (3;5): 4 Для этого в перспективную клетку (3;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (3,5 → 3,2 → 2,2 → 2,5). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 2) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v2 = 12; 0 + v2 = 12; v2 = 12 u2 + v2 = 8; 12 + u2 = 8; u2 = -4 u2 + v1 = 1; -4 + v1 = 1; v1 = 5 u2 + v4 = 5; -4 + v4 = 5; v4 = 9 u2 + v5 = 3; -4 + v5 = 3; v5 = 7 u3 + v5 = 4; 7 + u3 = 4; u3 = -3 u1 + v3 = 4; 0 + v3 = 4; v3 = 4
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (1;4): 0 + 9 > 8; ∆14 = 0 + 9 - 8 = 1 > 0 (1;5): 0 + 7 > 5; ∆15 = 0 + 7 - 5 = 2 > 0 max(1,2) = 2 Выбираем максимальную оценку свободной клетки (1;5): 5 Для этого в перспективную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,5 → 1,2 → 2,2 → 2,5). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 60. Прибавляем 60 к объемам грузов, стоящих в плюсовых клетках и вычитаем 60 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v3 = 4; 0 + v3 = 4; v3 = 4 u1 + v5 = 5; 0 + v5 = 5; v5 = 5 u2 + v5 = 3; 5 + u2 = 3; u2 = -2 u2 + v1 = 1; -2 + v1 = 1; v1 = 3 u2 + v2 = 8; -2 + v2 = 8; v2 = 10 u2 + v4 = 5; -2 + v4 = 5; v4 = 7 u3 + v5 = 4; 5 + u3 = 4; u3 = -1
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij. Минимальные затраты составят: F(x) = 4*120 + 5*60 + 1*110 + 8*90 + 5*80 + 3*70 + 4*20 = 2300 Анализ оптимального плана. Из 1-го склада необходимо груз направить в 3-му потребителю (120 ед.), 5-му потребителю (60 ед.) Из 2-го склада необходимо груз направить в 1-му потребителю (110 ед.), 2-му потребителю (90 ед.), 4-му потребителю (80 ед.), 5-му потребителю (70 ед.) Из 3-го склада необходимо весь груз направить 5-му потребителю. Задача 3Матричные игры. Для данных платежных матриц найти нижнюю и верхнюю цены игры; выявить активные стратегии игроков графическим методом при условии его применимости; найти решение игры (смешанные стратегии игроков и цену игры).  Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях. Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 5, которая указывает на максимальную чистую стратегию A2. Верхняя цена игры b = min(bj) = 7. Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 5 ≤ y ≤ 7. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии). Так как игроки выбирают свои чистые стратегии случайным образом, то выигрыш игрока I будет случайной величиной. В этом случае игрок I должен выбрать свои смешанные стратегии так, чтобы получить максимальный средний выигрыш. Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I. Находим решение игры в смешанных стратегиях. Решение можно найти по следующим формулам: = = = = = p1 = 1/5 (вероятность применения 1-ой стратегии). p2 = 4/5 (вероятность применения 2-ой стратегии). Оптимальная смешанная стратегия игрока I: P = (1/5; 4/5) q1 = 3/10 (вероятность применения 1-ой стратегии). q2 = 7/10 (вероятность применения 2-ой стратегии). Оптимальная смешанная стратегия игрока II: Q = (3/10; 7/10) Цена игры: y = 53/5 1 2 |