Решение задачи линейного программирования графическим и симплексным методом. Определение минимальных затрат на производство продукции с помощью способа множителей Лагранжа. Особенность построения начального плана средством северо-западного угла.
Аннотация к работе
Подставляя данные производства, получим: 1 (работник) • D (продукция в рублях на одного работника) • L (всего работников) = 1 • 5 • 104 • 81 = Функция спроса на товар X имеет вид QDX = a b • PX c • PY, где PX - цена товара X; PY - цена товара Y. Мерой реакции спроса на данный товар при изменении цены некоторого другого товара служит перекрестная эластичность спроса по цене. Для нахождения оптимального плана будем «передвигать» линию нулевого уровня функции Z (x1, x2 ) параллельно самой себе в направлении, указанном вектором grad Z до точки ее «первой встречи» с многоугольником ABCED, которая и является оптимальным планом задачи. Строим вторую симплекс-таблицу, элементы которой пересчитываем по соответствующим формулам. а) выбор разрешающего столбца (отмечен вертикальной стрелкой): для этого в L - строке выбираем максимальный по абсолютной величине из отрицательных элементов, если задача на максимум, или, максимальный из положительных элементов, если задача на минимум.
Сравнивая транспортные издержки, видим, что план, построенный методом наименьшей стоимости, лучший.
IV) Метод потенциалов. Потенциалами называются условные числа ui и vj приписанные определенным образом каждому поставщику и потребителю.
Условие оптимальности плана: Сумма потенциалов поставщика и потребителя равна тарифной ставке для занятых клеток; сумма потенциалов поставщика и потребителя не превышает тарифную ставку для свободных клеток: ui vj = cij (здесь: cij ? dij ), xij ? 0 ui vj = cij (здесь: cij ? dij ), xij = 0
Опорный план должен быть невырожденным.
1). Рассмотрим начальный план, полученный методом наименьшей стоимости (как лучший).
2). Рассмотрим потенциалы поставщиков и потребителей, используя первое условие оптимальности плана: ui vj = cij
Используя первое условие оптимальности плана, составим систему линейных уравнений для определения потенциалов: u1 v2 = 2 u2 v1 = 1 u3 v1 = 3 u4 v2 = 8 u4 v3 = 6
Система уравнений содержит 5 уравнений и 6 неизвестных, т.е. она имеет множество решений. Так как нужно одно решение, то любой из неизвестных задаем значение и вычисляем остальные неизвестные. Пусть u1 = 0, тогда V2 = 5, v2 = 2, v1 = 0, u2 = 1, u3 = -2, u4 = 3, v3 = 3
3) Проверяем условие оптимальности для свободных клеток. При невыполнении второго условия оптимальности плана в клетку заносим нарушение ui vj - cij со знаком « ». (такие клетки называются потенциальными.). В результате проверки получили одну потенциальную клетку. Таким образом, начальный план не оптимален.
V j Поставщики 0 5 3
U i Потребители В1 В2 В3
0 А1 d11=5 d13=8
1 А2 _ d22=3 3 d23=5
-2 А3 d32=4 d33=1
3 А4 d41=4 _
4) Улучшение плана.
· среди все потенциальных клеток выбираем клетку с наибольшим нарушением;
· строим для выбранной клетки замкнутый контур, состоящий из вертикальных и горизонтальных отрезков прямой, причем вершины контура лежат в занятых клетках, за исключением той клетки, для которой строится контур.
· вершины контура поочередно помечаем знаками “ ” и “- “, начиная с клетки, для которой построен контур;
· среди клеток, помеченных знаком “-“ , выбираем наименьшую перевозку.
Здесь: q = min (100; 50) = 50.
На эту величину увеличиваем перевозки в клетках, помеченных знаком “ ”, и уменьшаем в клетках, помеченных знаком “-“.
В результате переназначения освобождается одна клетка и имеем план:.
Потребности (требуемый объем работ) b1=200 200.150.0 K b2=150 150.50.0.K b3=50 50.0.K ? ai= ? bj (условие баланса для закрытой модели)
5). Вновь полученный план проверяем на оптимальность.
Так как число неизвестных больше числа уравнений на два, то в данном случае оптимальным следует признать план, полученный методом наименьшей стоимости. Действительно, по последней таблице имеем: x12, x22, x31, x41, x43
При таком начальном плане суммарные расходы: L = 2 · 100 3 · 50 3 · 150 4 · 50 6 · 50 = 200 150 450 200 300 = 1 300
что больше суммарных расходов, полученных по методу наименьшей стоимости.
ОТВЕТ: Начальный план: x21, x31, x12, x42, x43
При таком начальном плане транспортные издержки: L = 1200 (руб.)
Задание 6
Найти решение матричных игр: a) ; b) c) a) Решение:
А=
2 4 3 5
Седловой точкой является пара чисел (i0 = 2, j0 =1), при которой . Это и есть решение игры. b) РЕШЕНИЕ:
А=
2 5 3 4
Из анализа данной матрицы выигрышей видно, что то есть данная матрица не имеет седловой точки. В игре без седловой точки игроки вынуждены применять так называемые смешанные стратегии, заключающиеся в том, что игроки применяют не одну стратегию и выбирают среди них случайным образом.
Наиболее простым методом решения игр является графический метод, но он применим только для игр, в которых хотя бы у одного из двух участников имеется не более двух стратегий. Данная платежная матрица имеет размерность 2 х 3.
На плоскости XOY введем систему координат и на оси Ox отложим отрезок единичной длины А1А2, каждой точке которого поставим в соответствие некоторую смешанную стратегию первого игрока - (x, 1?x). В частности, точке А1(0; 0) отвечает стратегия А1, точке А2(1; 0) - стратегия А2.
В точках А1 и А2 восстановим перпендикуляр и на полученных прямых будем откладывать выигрыш игроков. На первом перпендикуляре (в данном случае он совпадает с осью Oy) отложим выигрыш игрока 1 при стратегии А1, а во втором - при стратегии А2. Если игрок применит стратегию А1, то его выигрыш при стратегии второго игрока В1 составляет 1, при стратегии В2 - 4, а при стратегии В3 - 5. Числам 1, 4, 5 на оси OX соответствуют точки В1, В2 и В3.
Если же игрок 1 применит стратегию А2, то его выигрыш при стратегии второго игрока В1 равен 3, при В2 - 2, а при В3 - 1. Эти числа определяют точки В1*, В2*, В3* на перпендикуляре, восстановленном в точке А2. Соединяя между собой точки В1 и В1*, В2 и В2*, В3 и В3*, получим три прямые, расстояние до которых от оси ОХ определяет средний выигрыш при любом сочетании соответствующих стратегий. Например, расстояние от любой точки отрезка В2В2* до оси ОХ определяет средний выигрыш при любом сочетании стратегий А1, А2 (с частотами х и 1?х) и стратегий В2 игрока 2. Это расстояние равно 4 • х1 ? 2 • (1 ? х1) =
Ординаты точек, принадлежащих ломаной B1 N B1*, определяют минимальный выигрыш игрока 1 при применении любых смешанных стратегий. Эта минимальная величина является максимальной в точке N.
Следовательно, этой точке соответствует оптимальная смешанная стратегия Х = (х, 1?х), а ее ордината равна цене игры Координаты точки N находим как точку пересечения прямых В3В3* и В1В1*. Соответствующие два уравнения имеют вид:
1 • х ? 3 • (1 ? х) = (при стратегии В3)
5 • х ? 1 • (1 ? х) = ( при стратегии В1)
Следовательно,
Таким образом,
Как видно из рис., стратегия В2 не входит в оптимальную стратегию, и мы можем найти оптимальную смешанную стратегию при помощи матрицы
Оптимальную смешанную стратегию для игрока 2 можно найти из системы
1 • y ? 5 • (1 ? y) = ( при стратегии A1)
3 • y ? 1 • (1 ? y) = (п при стратегии A2)
Следовательно, Таким образом, с) Решение:
А=
7 8 7
Из анализа данной матрицы выигрышей видно, что то есть данная матрица не имеет седловой точки.
Если у каждого игрока больше двух возможных стратегий, то можно решение игры свести к решению задачи линейного программирования
Данная игра не имеет Седловой точки, поэтому решение игры представим в смешанных стратегиях: , с ценой . Здесь: ,
При оптимальной стратегии игроку 1 обеспечен выигрыш независимо от выбора стратегий 2 игроком, то есть a11 • x1 a21 • x2 am1 • xm ? (при стратегии В1) a12 • x1 a21 • x2 am2 • xm ? (при стратегии В2) a1n • x1 a2n • x2 amn • xm ? (при стратегии Bn)
Цена игры неизвестна, но можно предположить, что (Последнее условие выполняется, если элементы игровой матрицы неотрицательны (как в данном случае). Если элементы платежной матрицы имеют отрицательные числа, то, прибавляя ко всем элементам матрицы некоторое положительное число (например, 1), можно получить матрицу, все элементы которой будут неотрицательны.)
Преобразуем систему ограничений, разделив обе части неравенства на Вводим обозначения:
Первый игрок стремится цену игры максимизировать, значит, функция Z= должна принимать минимальное значение. Таким образом, получилась задача линейного программирования.
Для определения стратегии 2 игрока задача линейного программирования будет иметь после аналогичных преобразований и замены переменных следующий вид:
Таким образом, для решения игры имеем пару двойственных задач линейного программирования. Из них удобнее решать задачу на max с ограничениями ‘?’ симплексным методом.
Составим пару взаимно-двойственных задач для заданной игровой матрицы : для первого игрока
Z = p1 p2 p3 > min
5 • p1 6 • p2 7 • p3 ? 0 (при стратегии В1)
6 • p1 8 • p2 3 • p3 ? 0 (при стратегии В2) (*)
4 • p1 7 • p2 5 • p3 ? 0 (при стратегии В3) p1, p2, p3 ? 0. для второго игрока
Решаем вторую (**) из пары взаимно-двойственных задач на максимум, где ограничения имеют знак ‘?’. Решение выполняем с помощью пакета MS EXCEL и надстройки «Поиск решения». (К элементам уравнений систем (*) и (**) добавили 1):
Переменные q1 q2 q3
-0,03125 -0,687 1
Функция цели 0,2813 файл Поиск решения.xls
Решаем первую (*) из пары взаимно-двойственных задач на минимум, где ограничения имеют знак ‘?’. Решение выполняем с помощью пакета MS EXCEL и надстройки «Поиск решения». (К элементам уравнений систем (*) и (**) добавили 1):
Переменные p1 p2 p3
-9,800000001 7,4 1
Функция цели -1,4 файл Поиск решения_на максимум_зад_246_с.xls (тот же самый файл: Сервис - Поиск решения - меняем параметры с максимума на минимум и знак на ограничения)
Таким образом, получили: (p1, p2, p3) = (-9,8; 7,4; 1). Следовательно, цена игры с платежной матрицей А1 (где к элементам исходной игровой матрице прибавили по 1 и выполнили расчет с помощью функции «Поиск решения»): ,