Алгоритмы по математике
Методическое пособие - Математика и статистика
Другие методички по предмету Математика и статистика
?гого игрока, соединяя их отрезками.
. Если первый игрок имеет две стратегии (в матрице 2 строки), то на нижней ломаной выбирают самую верхнюю точку (вершину). Если второй игрок имеет две стратегии, то на верхней ломаной выбирают нижнюю точку.
. Длина перпендикуляра, опущенного из полученной вершины на числовую ось, равна цене игры C. Причем
4. Стратегии, участвовавшие в определении данной вершины, называются активными стратегиями. С их помощью составляются системы уравнений для определения вероятностей использования игроками своих оптимальных стратегий.
Алгоритм сведения матричной игры к ЗЛП
1. По теореме о цене игры
и
Зная, что , ,
предполагают
2. Получают прямую и двойственную задачу линейного программирования
, ;
,
3. Решив ЗЛП, определить цену игры можно по формуле
а вероятности .
Решение статистической игры
Игры, в которых один противник "природа", а другой - человек или один из игроков действует не сознательно, а в соответствии с определенными законами, называются играми с "природой" или статистическими играми.
Для составления матрицы рисков определяют разности между максимальным выигрышем, который получил бы игрок, зная состояние природы, и выигрышем, который получит игрок, применяя стратегию.
Если известно распределение вероятностей состояний природы
то используют критерий Байеса
(максимум математического ожидания выигрыша) или
(минимум математического ожидания риска).
Если распределение вероятностей состояний "природы" неизвестно, то используют:
а) принцип "недостаточного основания Лапласа", где каждое состояние природы равновероятно, т.е. р1=р2=...= рn=1/n;
б) максиминный критерий Вальда: ;
в) критерий минимального риска Сэвиджа: ;
г) критерий Гурвица:
где
при =0 - крайний оптимизм, при =1 - крайний пессимизм
Решение транспортной задачи методом потенциалов\
Исходные данные
- вектор запасов поставщиков (столбец), - вектор потребностей потребителей (строка), - матрица тарифов (транспортные затраты при перевозке единицы груза из пункта в пункт).
Если
то имеем закрытую модель задачи. Если
то данную открытую модель задачи, необходимо свести к закрытой модели, введя недостающего фиктивного потребителя или поставщика с нулевыми тарифами.
Опорный план строится тремя методами: северо-западного угла, минимального элемента и аппроксимации Фогеля:
а) метод северо-западного угла: заполнение клеток таблицы начинается с левой верхней клетки ("северо-западной"), в которую ставят максимально возможное число, т.е. минимальное из чисел запасов и потребностей для этой клетки. При этом исчерпываются либо запасы, либо потребности (вычеркивается строка или столбец), выбирается следующая северо-западная клетка и т.д. Число заполненных клеток равно m+n-1. Если на каком-либо шаге вычеркиваются одновременно поставщик и потребитель, то в клетку, соответствующую данному методу, ставится 0-поставка;
б) метод минимального элемента: заполнение клеток осуществляется по принципу: "самая дешевая перевозка осуществляется первой". Выбирается клетка с минимальным тарифом и заполняется максимально возможным числом, при этом исчерпываются либо запасы, либо потребности (вычеркивается строка или столбец), выбирается следующая клетка с минимальным тарифом и т.д. Если на каком-либо шаге вычеркиваются одновременно поставщик и потребитель, то ставится 0-поставка в данной строке или столбце в клетку с минимальным тарифом;
в) метод аппроксимации Фогеля: во всех строках и столбцах найти разности между двумя минимальными тарифами, записать их, соответственно, справа и внизу таблицы. Среди найденных разностей выбирают максимальную. В строке (или столбце), которой соответствует данная разность, заполняют клетку с минимальным тарифом. Если максимальных разностей несколько одинаковых, выбирают ту, которой соответствует минимальный тариф. Если минимальный тариф одинаков для нескольких клеток в строке (столбце), то заполняют ту, которая стоит в столбце (строке), имеющем наибольшую разность между двумя минимальными тарифами.
Среди полученных опорных решений выбирают план с минимальной стоимостью перевозок и проверяют его на оптимальность:
1) вычисляют потенциалы поставщиков и потребителей из условия для всех занятых клеток (при условии );
) определяют оценки всех свободных клеток.
Если все , то план является оптимальным (наличие равных 0 оценок свидетельствует о неоднозначности оптимального плана). Если существуют , то построенный план не оптимален. Для его улучшения среди всех выбирают максимальное и для соответствующей свободной клетки строят цикл пересчета:
1) цикл изображают в таблице в виде замкнутой ломаной линии. В любой занятой клетке цикла возможен поворот линии на 900;
) отмечают вершины цикла пересчета (там, где линия поворачивает) последовательно знаками "+" и "-" , начиная с "+" в исходной клетке. Среди поставок, стоящих в "-" клетках, определяют минимальную. К значениям, стоящим в "+" клетках, прибавляют эту поставку, а из значений, стоящих в "-" клетках, ее вычитают;
) по этому циклу перераспределяются объемы перевозок. Перевозка загружается в выбранную свободную клетку и о?/p>