Найти эйлеров цикл в графе. Вершина 5 отсутствует.
Найти кратчайшие пути из вершины 1 во все остальные вершины графа. Граф приведен в задаче 7. Дуги и их веса заданы в таблице.
Вес дуги (2,8) равен сумме дуг (2,5) и (5,8), а вес дуги (3,7) равен сумме весов дуг (3,5) и (5,7).
|
Дуги |
1,2 |
1,3 |
2,4 |
2,7 |
2,5 |
3,5 |
3,8 |
|
Веса |
3 |
1 |
4 |
2 |
5 |
3 |
2 |
|
Дуги |
3,6 |
4,7 |
5,7 |
5,8 |
6,8 |
7,9 |
8,9 |
|
Веса |
4 |
5 |
1 |
3 |
2 |
4 |
2 |
Решить задачу коммивояжера для 5 городов. Матрица расстояний (стоимостей переезда) представлена в виде\
|
|
1 |
2 |
3 |
4 |
5 |
|
1 |
2 |
4 |
10 |
4 |
|
|
2 |
1 |
15 |
6 |
4 |
|
|
3 |
6 |
3 |
14 |
2 |
|
|
4 |
5 |
21 |
10 |
5 |
|
|
5 |
14 |
3 |
4 |
7 |
Найти длину критического пути (длительность выполнения проекта) в сети, где дуги представляют собой работы проекта, начало и конец дуги - начало и конец работы, вес дуги - длительность работы.
Вычислить наиболее ранние и наиболее поздние моменты начала работ. Вершины s и t сопоставлены началу и завершению проекта соответственно.
Длительности выполнения работ (веса дуг) (2,7), (3,8), (8,5) равны 1, дуги (5,7) равна целой части от деления номера набора задач (N) на 15 (=), остальные равны 2.
Решить антагонистическую матричную игру.
Выигрыш 1 игрока в зависимости от выбранных стратегий игроков 1 и 2 задан следующей матрицей.
|
Ai \ Πj |
1 |
2 |
3 |
4 |
5 |
|
1 |
5 |
10 |
12 |
7 |
13 |
|
2 |
4 |
3 |
7 |
11 |
2 |
Найти оптимальные смешанные стратегии и цену игры в антагонистической матричной игре 2 х n.
|
Игрок 1 \ Игрок 2 |
1 |
2 |
3 |
|
1 |
5 |
4 |
6 |
|
2 |
2 |
-3 |
1 |
В эксперименте 7 человек независимо друг от друга будут случайным образом выбирать одну из клеток шахматной доски 8х8. При этом выбранная клетка и граничащие с ней клетки (граничащих клеток не более 8), закрашиваются.
С помощью метода Монте-Карло определить предполагаемое значение количества закрашенных клеток.
Использовать механизм случайного выбора типа "рулетка".
Число испытаний N = 10.
Описать процесс получения решения.
Решить с помощью динамического программирования:
при ограничениях
Построить расписание обслуживания n = 10 требований m = 3 приборами, минимизирующее момент завершения обслуживания последнего требования
Требования готовы к обслуживанию в момент времени 0.
Прерывания обслуживания любого требования разрешены.
Требование не может обслуживаться 2 и более приборами одновременно. Длительности обслуживания pj заданы в таблице
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
|
40 |
12 |
30 |
50 |
7 |
4 |
10 |
21 |
9 |
14 |
В эксперименте 7 человек независимо друг от друга будут случайным образом выбирать одну из клеток шахматной доски 8х8. При этом выбранная клетка и граничащие с ней клетки (граничащих клеток не более 8), закрашиваются.
С помощью метода Монте-Карло определить предполагаемое значение количества закрашенных клеток.
Использовать механизм случайного выбора типа "рулетка".
Число испытаний N = 10.
Описать процесс получения решения.
Решение
Идея метода Монте-Карло состоит в следующем. Вместо того, чтобы описывать случайное явление с помощью аналитических зависимостей, производится эксперимент, называемый розыгрышем, дающий случайный результат. В результате розыгрыша получаем одну реализацию случайного явления. Проведя эксперимент достаточно большое количество раз, получим статистический материал, который можно обрабатывать методами математической статистики. Для сложных операций, в которых участвует много элементов (машин, систем, людей, коллективов) и в которых случайные факторы сложным образом взаимодействуют друг с другом, метод Монте-Карло как правило оказывается проще и адекватнее аналитического. Рассмотрим пример, типичный для применения метода Монте-Карло.
На плоскости нарисована некоторая фигура. Команда из n человек (участников операции) должна выполнить следующее. Каждый человек, не видя фигуры и не зная действий других участников, должен нарисовать на плоскости круг заданного радиуса r. Операция считается успешной, если круги покрыли не менее 50% площади фигуры. Требуется определить вероятность того, что операция будет успешной.
Решение этой задачи аналитически с помощью методов теории вероятностей чрезвычайно сложно. Значительно проще решить эту задачу методом Монте-Карло.
Для этого проведем следующий эксперимент. Разыграем координаты n точек на плоскости с помощью какого-либо механизма случайного выбора. Например, пусть m - количество точек на плоскости. Разобьем интервал [0,1] на m последовательных непересекающихся частей одинаковой длины (события выбора центра круга независимы и равновероятны). С помощью ЭВМ или по таблице выберем n (псевдо)случайных чисел из [0,1]. Интервалы, в которые попали эти числа, указывают координаты n точек на плоскости. Нарисуем соответствующие круги и определим площадь покрытия фигуры. Если эта площадь не менее 50%, то будем считать эксперимент успешным.
При большом количестве экспериментов N вероятность W успеха операции может быть приближенно оценена как частота успешных экспериментов:
, где M - число успешных экспериментов.
С помощью метода Монте-Карло можно получать не только вероятности событий, но и математические ожидания случайных величин. Например, если в рассматриваемом примере требуется найти не вероятность успеха операции, а математическое ожидание M[S] площади S покрытия фигуры кругами, то можно воспользоваться следующим.
В соответствии с законом больших чисел (теорема Чебышева) при большом количестве независимых опытов среднее арифметическое полученных значений случайной величины почти наверняка мало отличается от ее математического ожидания. Пусть Si - площадь покрытия фигуры в эксперименте i. Тогда
Применительно, к условиям исходной задачи:
Таким образом, предполагаемое значение количества закрашенных клеток –....
Список использованной литературы:
Балашевич В.А. Основы математического программирования. - Мн.: Выш. шк., 2002. Карасев А.Н., Кремер Н.Ш., Савельева Т.Н. Математические методы в экономике. - М., 1996. Лященко И.Н. Линейное и нелинейное программирования: И.Н.Лященко, Е.А.Карагодова, Н.В.Черникова. - К.: Высшая школа, 1992. - 372 с. Общий курс высшей математики для экономистов / под ред В.И. Ермакова.- М.: ИНФА - М., 1997. Федосеев В.В. и др. Экономико-математические методы и прикладные модели: учебное пособие для ВУЗов. - М.: Юнити, 2002.
