ТПР_шпоры
.doc
|
Для любой матричной игры имеет место равенство , т. е. любая матричная игра разрешима в смешанных стратегиях.
|
Смешанной стратегией (с.с.) игрока в матричной игре называется вероятностное распределение на множестве его ч.с. . .
|
|
|
6. Задача линейного программирования для II игрока в смешанных стратегиях.
|
7. Математическая модель задачи о назначениях. . , , , , , , |
В неотрицательной матрице Aij>=0 (квадратной матрице) необходимо выбрать в каждой строчке и в каждом столбце ровно по 1 максимальному элементу, чтобы их сумма была максимальна. Если матрица Х=х1..xn допустима то в каждой строчке и в каждом столбце ровно по 1 единице. В целевой функции это означает что в каждой строчке и столбце из матрице С берется по 1 элементу.
|
Две матрицы и назовем эквивалентными , если, . Задачи о назначениях, определяемые эквивалентными матрицами, называются эквивалентными. |
Нулевые элементы матрицы называются независимыми нулями, если для любого нуля , , строка и столбец, на пересечении которых лежит этот нуль, не содержат других нулевых элементов |
Как только количество независимых нулей становится равным , задача о назначениях решена: оптимальный вариант определяется позициями независимых нулей в последней из матриц, эквивалентных исходн. матрице .
|
а) в первом столбце помечаем произвольный нуль; б) во втором столбце помечаем (если найдется) тот нуль, в строке которого нет нуля, помеченного "*"; в) аналогично просматриваем один за другим все столбцы матрицы . |
Выделенные элементы матрицы - это элементы строк или столбцов, помеченных знаком +. Все остальные элементы матрицы - невыделенные элементы. |
14. Содержательная постановка задачи Коммивояжера. Имеется городов, занумерованных числами от 1 до . Расстояния между любой парой городов известны и составляют . Если между городами и нет дороги, то . По тем же соображениям . Вообще говоря, (путь в одну сторону не обязательно совпадает с путем, пройденным в обратную сторону). Коммивояжер (бродячий торговец), выезжая из какого-либо города, должен посетить все города, побывав в каждом ровно один раз, и вернуться в исходный город. Объезд городов, удовлетворяющий этим требованиям, называется маршрутом коммивояжера. Под длиной маршрута понимается сумма длин всех входящих в него переездов из города в город. Необходимо определить маршрут минимальной длины. |
|
16. Выбор множества для ветвления. На первом шаге это множество . Его нижняя оценка . На остальных шагах из числа кандидатов на ветвление (из множества висячих вершин дерева ветвления) выбирается множество с наименьшей оценкой.
|
17. Критерий выбора дуги для ветвления.
|
|
|
f1,…fm – выпуклые функции
|
f (x1,x2,…,xn) max(min) gi(x1,x2,…,xn) bi (i=1…m) xi 0 (i=1…n), где f и gi - некоторые линейные функции переменных x1…xn.
|
1)F0(хк+1)<F0(xk) 2),D- допустимая область. 3)Существует х*=
|
Последовательность хк называется релаксац, в которой выполняются св-ва из 22.
|
|
1)Выделение (уточнение) отрезка на котором содержится минимум 1)Деление отрезка пополам 2)Метод золотого сечения 3)Метод Фибоначчи
|
Пусть дан вектор и квадратичная матрица P=ux, тогда задача нахождения вектора z (удовлет. 1-3) наз задачей ЛЗД.
|
Если матрица P положительная определена, то линейная задача дополнительная, имеет единственное решение z при любом векторе q.
|
Прямые используют информацию о значениях функции при реализациях v, имеют схему графического метода. Непрямые: если удается выписать явные функции то задачи стохастического программирования становятся нелинейными задачами.
|
|
|
|
Направление Sk называется дополнительным, если выполняется условие
|
|
|
Это направление, которое с градиентом функции образует тупой угол, вдоль которого функция убывает.
|
Это направление, которое одновременно допустимо (сохраняет допустимость) и прогрессивно (сохраняет убывание) 1) 2)
|
|
|
|
Ипсилон активные ограничения – это такие номера i, для которых .
|
|
|
Оптимальное решение КЗВП, если оно существует, достигается на границе области. Для найденного направления Sk допустимо xk<=xk+αSk, величину шага αk вычисляем из условия в данном направлении границы допустимой области. |
|
45. Принцип оптимальности динамического программирования а) задача разбивается на подзадачи имеющие общую структуру. б) Оптимальное управление обладает таким свойством, что каково бы ни было начальное состояние на любом шаге и управление, выбранное на этом шаге, последующие управления должны выбираться оптимальными относительно состояния, к которому придет процесс в конце данного шага.
|
46. Общее уравнение Беллмана , , |
47. Уравнение Беллмана для задачи распределения ресурсов , ,
|
48. Уравнение Беллмана для задачи о замене оборудования |
49. Уравнение Беллмана для задачи о рюкзаке |
50. Уравнение Беллмана для задачи о пожаре |