Метод динамического программирования. Запишем дифференциальные уравнения Беллмана для данной задачи, рассуждения будем проводить начиная с последней стадии
Запишем дифференциальные уравнения Беллмана для данной задачи, рассуждения будем проводить начиная с последней стадии, в качестве критерия будем использовать время, обозначим через ti,j время передвижения узла I к узлу g.
Через fij-обозначим наименьшее время передвижения от узла i к узлу 6 по допустимому пути.
Тогда функциональное уравнение будут записаны в виде
F1=min(ti,j+fj)
При этом начиная с 6 узла и заканчивая 1.
Для последней стадии имеем
F6=0
F5=min(t5.6+f6)=min(2+0)=2
F4=min(t4,6+f6);(t4,5+f5)=5;5
F3=min(t4,5+f4);(t3,5+f5)=12;5
F2=min(t3+f3);(t2,4+f4);(t3,5+f5)=7;12;6
F1=min(t2f2); ( t3+f3)=7;7
Целочисленное программирование
Рассмотрим полностью целочисленную задачу вида:
R(x1,x2)=5x1+1x2=>max
При ограничении
2x1+1x2=3
X1=>0
X2=>0
X1,x2-целое
Решим вначале задачу линейного программирования
По сколько имеется одно ограничение типа 2 можно выразить одну переменную через другую и свести задачу к одномерной.
X2=3-x1
5x1+(3-x1)=3x1+3
Таким образом свели задачу с двумя переменными , с одним переменной.
X1>R(x1) но х2=3-х1=>0, x1<=3/2
X1*=3/2
X2=3-2x*=0
Решением (1-3) является x1*=3/2, x2*=0, R*=7,5
Согласно методу отсечения далее надо рассмотреть расширенную задачу линейного программирования. Мы должны добавить еще одно линейное ограничение которое отсечет не целое численно решение однако все целочисленные значения не затронет.
Проиллюстрируем задачу графически
2x1+x2=3
X1=0
X2=0
Из условия 2 видно, что х1 может быть больше или равен 1, 0 или 1.
Получили из 2 условие 5 и нанесли его на рисунок, эта линий отсекла не целое численное решение. Далее надо решать задачу (1-5), ее можно решить графически.
Вычислим значения критерия в точках А,С и Д.
т.А(0,3)=3
т.С(1,1)=9
т.Д(1,0)=5
точка С оптимальная точка задачи линейного программирования (1-3,5), Цпр(1-5).
Основные понятия орграфа
Задача о 7 мостах
Калининград располагается на обеих берегах реки Прегиль, и на двух островах. Которые соединияются 7 мостами
График
Можно ли во время прогулки пройти каждый мост по одному разу и вернуться в исходную точку.
Заменив план на схему где земля сжаты в точку. Ввел следующее определение.
Граф это фигура состоящая из точек (вершин) и соединяющих их линии ребер.
Маршрут, путь соединяющий А и Б график это такая последовательность, который каждый два ядра имеют общую консевую точку. При чем первое ребро выходит из вершины А, входят в вершину В.
Вершины А и В называются связанные. Граф называется связным если любая его пара вершин связана.
Цепь это такой маршрут или путь, где каждое ребро графа встречается в нем не более одного раза. При чем вершины цепи могут повторяться несколько раз.
При чем вершины цепи могут повторяться несколько раз.
Цикл это цепь в которой начальные и конечные вершины совпадают. Цикл это цепь в которой начальные и конечные вершины совпадают.
Вершина в графе называется четной если в ней исходятся четное число ребер. Если все сходящиеся в ней ребра нечетное.
Конечный граф – граф, в котором множество его ребер конечно.
Теорема Эйлера
В любом конечном связном графе все вершины которого четные существует цикл в котором каждая ребро графа участвует один раз.
Таким образом задача о семи мостах не имеет решения, по сколько все вершины нечетные. Граф удовлетворяющий теореме Эйлера называется Эйлерова граф.
Существует алгоритмы построения Эйлерова цикла в Эйлеровом графе. По сколько число входящих и выходящих вершин в графе четно, то выйдя из вершины уже принадлежащий циклу мы можем получить новый цикл которые далее объединяется с уже ранее существующем, определенным нами циклом, то есть можно построить Эйлеровый цикл за конечное число шагов.
Эйлеров цикл характерен тем что, идя по нему, мы в точности один раз проходим через каждое ребро.
Гомментонольф цикл, это такой цикл который проходит через каждую вершину ровно по одному разу.
Рисунок
Нет общего критерия, который позволил бы установить является ли заданный граф Гомментоновым. Нет также универсального алгоритма, эффективного построения Гомментонового цикла.
Как устроить художественную выставку, то есть организовать осмотр чтобы за отведенное время ознакомиться со всей экспозицией, наибольшему числу желающих.
Пример:
Указатели надо раставить так, чтобы перемещаясь любой посетитель мог побывать у каждой картины один раз.
Будем считать, что вход и выход совпадают.
Экспонаты следует разместить так, чтобы схема экспозиции была Эйлеровым графом, указатели должны быть снабжены порядковыми номерами.
Рисунок
Оптимизация на сетях
Сетевые модели оптимизационные являются обычно задачами частными случаями, задачами линейного программирования, они имеют такие математические особенности, которые позволяют разработать эффективные алгоритмы, лучше чем симплексный метод.
Обычно реальные сетевые задачи содержат сотни и тысячи переменных, а также ограничении по этому эффективность алгоритма важна.
Изучение сетей позволяет выявить тот факт, что разные или не похожие модели в конечном итоге решаются одинаково.
Важным классом сети является дерево.
Дерево – это связная сеть содержащая Р узлов и Р-1 дугу.
Рисунок
Дерево которое не содержит контуров. Дерево – ориентированный граф без циклов с выделенной вершиной (корнем) из которой существует путь в любую другую вершину или узел.
Наиболее эффективные методы решения задач в частности транспортные задачи являются метод потенциалов разработанный на основе симплекс метода и Венгерский метод использующий последовательное сокращение невязок.
Рассмотрим несколько задач:
Использующие дерево решений; о соединение городов; о максимальном потоке; о кратчайшем расстоянии.
1)дерево принятия решений, представляет собой схематическое описание проблемы принятия решения, например, выпускник хочет продолжить учебу и желает оценить возможность получения диплома экономиста в Москве или Тамбове. В одном из 2 университетов.
Рисунок
2)задача о соединения городов. Имеются n городов a1,a2,…an которые надо соединить между собой сетью дорог. Стоимость соединения городов C(Аi-Ak). Какой должна быть сеть дорог соединяющая все города чтобы ее суммарная стоимость была минимальной.
Очевидно что сеть должна быть деревом. Действительно если в графе найдется хоть один цикл, то при удалении из него любого звена города по прежнему в этом цикле останутся соединенными. Однако стоимость цикла уменьшится, то есть число ребер в графе должно быть n-1.
Алгоритм
1)связывают два города самым дешевым связующем звеном e1.
На каждом следующем шаге добавляют самое дешевое из звеньев (любое из них если они одинаковые, несколько), которое удлиняет сеть еще на одно звено, но никакого цикла не образуется. Последний шаг алгоритма имеет номер n-1.
Стоимость строительства сети минимально и имеет величину.
Соединим города сетью дорог
| A | B | C | D | |
| A | - | |||
| B | - | |||
| C | - | |||
| D | - |
Так как n=4, то число ребер должно быть n-1=4-1=3.
Рисунок
C(ei)=6+9+11=26
Рисунок
В этой задачи есть прямой и обратный ход.
1)Рассмотрим узел 6 которому присвоен метку (45,3).
2)Таким образом на втором шаге, метки 1,2,3 имеют постоянные метки. Метки 4 и 6 временные метки, а метки 5 и 7 не помечены.
3)3 шаг рассмотрим узел 2 и выберем все узлы с которыми он соединяется одним ребром, и которые не имеют постоянных меток. Маршрут 1, 3, 4 соединяющий узлы 1 и 4 являются кратчайшем, поэтому ему присваивают постоянную метку. Таким образом на этапе 3 узлы 1,2,3,4 имеют постоянную метку, а узлы 5,6,7 временные.
Рисунок
Рассмотрим 4 узел и выберем все узлы, соединенные одним ребром с узлом 4, которые не имеют постоянных меток. В этот узел можно придти по маршруту 1,3,6 (45) и по маршруту 1,3,4,6,(43).
Присваиваем узлу 6 постоянную метку, таким образом после 4 шага узлы 1,2,3,4,6 имеют постоянные метки.
Рисунок
5 этап, рассмотрим узел 2 и выделим связанные с ним одним ребром и имеющимся постоянных меток. Таким образом после 5 шага узлы 1,2,3,4,5,6 имеют постоянную метку, а узел 7 временную метку. Из узла 1 в узел 7 можно попасть по маршруту 1,2,5,7(49) и по маршруту 1,2,7 (60).
Наличие в метках второго числа позволяет определить последовательность вершин в каждом кратчайшем маршруте. В результате составляется табличка.
| Узел | маршрут | Длина |
| 1-2 1-3 1-3-4 1-2-5 1-3-4-6 1-2-5-7 |
Задачи о принятии решения использующие деревья решения
Как поступить в университет. Москва и экономист 0,6, Москва и инженер 0,7,
Тамбов и экономист 0,9, Тамбов и инженер 0,95.
Средняя зарплата в течение 5 лет – 35000
Инженер в Москве -30000
Экономист Тамбов-24000
Если выпускник школы никуда не поступил, то его средняя зарплата за 5 лет, выпускника не поступившего не куда 18000. Критерием при принятия решения является велечина среднего дохода за первые 5 лет трудовой деятельности. Используя дерево решений решим проблему выпускника.
Рисунок
С1 окончил университет в Москве экономист.
С2 не смог поступить или не окончил в Москве экономистом
С3 и С4 окончил университет в Москве инженером
С4 не смог поступить и окончить инженером
С5 и С6 окончил экономистом в Тамбове экономистом
Д3, Д4 выбор экономиста и инженера
Разные узлы рассчитываются по разному, в частности узлы 4,7
Методы принятия решения в условиях неопределенности
Неопределенность это понятие более широкое чем случайность.
Для случайных событий, величин и процессов характерны вероятные закономерности.
Для условий неопределенности характерна значительное число влияющих на события факторов и то, каким образом они влияют не известно.
Методы прогнозирования
Прогнозирование – по своему характеру не разрывно связаны со временем.
Через настоящее пытаются разглядеть будущее. Выбор метода прогнозирования зависит от, наличия данных, планируемый в момент времени, желаемая точность, а также стоимостные затраты и время на его составление.
По моменту времени, выделяют краткосрочный прогноз обычно на квартал, среднесрочный один три года, долгосрочный больше 3 лет.
Рисунок
Методы прогнозирования
Рисунок
количественные
1)
2)Экзопоненциального сглажевания
3)проицируевомого тренда (тенденция)
4)многомерные дипрессионные модели
5)эконометрические модели
6)компьютерная имитация
Качественные
1)дельфийские методы
2)изучение рынка
3)метод консенсуса
4)совокупное мнение сбытовиков
5)историческая аналогия
Теория игр
Это раздел математики, в котором изучаются математические модели, принятия решения в условиях конфликта.
Конфликт – всякое явление, в котором участвуют различные стороны, которые называются множеством игроков и которые наделены не совпадающими интересами.
(спортивные состязания).
Применяются теория в военном деле, экономике, социологии, в праве и т.д.
Игрок это индивидуально действующее и заинтересованное начало в игре. В условиях конфликта, стороны стремятся скрыть свои замыслы и действия, и это порождает неопределенность. С другой стороны неопределенность связанная с незнанием можно интерпретировать как конфликт принимающего решения с природой (с/х).
Теория игр связана с математикой, теория вероятностей с исследованием операций и теорией информации.
Классификация игр
В основе классификации игр лежит бескоалиционная игра с выигрышем.
Г=<I,{X1},{H1}>
Г-игра
{Xi}-множество стратегий I игрока
{Hi}-выигрыш I игрока
Точное описание конфликта, в виде игры состоит в том что указывается, кто и как участвует в игре.
Каковы его возможные исходы, а также кто и как заинтересован в этих исходах.
Существуют обобщения и ограничения данной игры. Бескоалиционной игры с выигрышем.
А)Иногда допускают, что игроки выбирают свои стратегии объединяясь в некоторые группы.
Б)существуют игры с бесконечным множеством игроков
В)бескоалиционная игра когда задаются не выигрыши, а отношения предпочтения.
Г)Игры с запрещенными ситуациями, то есть рассматриваются не все возможные ситуации Х=x1*x2*…*xn (множество всех ситуаций).
Х разрешенное э Х.
Ограничение
1)конечная игра, в ней все множества стратегий Xi конечны.
2)антагонистическая игра – это игра, в которой 2 игрока при чем Н1=-Н2=Н. (игра с нулевой суммой-игра 2 лиц с прямо противоположными интересами и нулевой суммой).
3)матричная игра – это конечная антагонистическая игра, то есть в ней множество стратегий каждого игрока, игра на единичном квадрате. Игра в которой n=2, H1=-H2, а множество стратегий X1=[0,1],X2=[0,1].
Позиционные игры
Это бескоалиционная игра, моделирующая процессы последовательного принятия решений, игроками в условиях как правило не полное и меняющейся со временем информация.
Различают позиционные игры с полной, и не полной информацией. Состояние игры называется позициями а множество позиций можно представить в виде дерева.
Динамическая игра
Это бескоалиционная игра, n-ниц в виде развивающегося во времени процесса, в котором игроки последовательно принимают частичные решения и объект переходит из одного состояния к другому (игры на выживание, где человек обладает некоторым капиталом, игроки разыгрывают игру от начала до разорения.)
Дифференциальные игры
Это разновидность динамических игр, изучаемых в теории управления, и стратегиями в них являются допустимые управления.
Кооперативные игры
Это модель конфликтной ситуации в которой рассматриваются результат конфликта, в зависимости от того, как объединяются игроки в те или иные союзы, коалиции. Это модель рынка, схемы голосования, распределение прибыли и другие.
Выделяют классические кооперативные игры, игры без побочных платежей, игры в форме функции разбиения, не атомические игры (бескоалиционные и коалиционные).
Классическая кооперативная игра – определяется как пара, в которой имеется конечное множество игроков и функция платежей, которая определена на множестве всех коалиций.
Речь идет о суммарном выигрыше, который получат игроки если они объединятся в коалицию.
Игры без побочных платежей – в которых, выигрыш от отдельного игрока не могут передаваться другому.
Игры в форме функции разбиения – в них результат выигрыша зависит от того как группируются не вошедшие в эту коалицию игроки.
Не атомическая игра – игра, в которой игроков на столько много, что можно считать бесконечной, а роль любого конечного множества игроков пренебрежимо мала (явление массового характера, пользование общественного транспорта в мегаполисе).
Принципы оптимальности
В бескоалиционных играх, принцип оптимальности базируется на понятие приемлемости.
Ситуации х в игре называется приемлемой для коалиции, если одновременное отклонение игроков из нее не улучшит ситуацию.
При этом существуют различные понимая того что понимается под ухудшением ситуации.
Для антагонистических игр характерен принцип Максимина (принцип гарантированного результата).
Он состоит в том, чтобы игроку выбирать такую стратегию, чтобы максимизировать свой выигрыш в самых неблагоприятных ситуациях. Какую бы стратегию не принял бы противник.
Метод прогнозирования