- •1. Экономико-математическая модель транспортной задачи.
- •2. Обща формулировка тз
- •3. Теорема (о ранге системы ограничений закрытой тз) и следствие из неё. Открытая тз.
- •4. Оценка свободной клетки, ее экономический смысл, критерий оптимальности базисного распределения поставок.
- •5. Теорема о потенциалах свободных клеток. Вычисление оценок свободных клеток методом потенциалов.
- •6. Понятие об игровых моделях.
- •7. Классификация игр.
- •8. Формальное представление игр.
- •9 .Принцип минимакса для антагонистических игр.
- •10.Фунд-ое нер-во для цен антагонистических игр.
- •11. Седловая точка. Теорема о седловой точке.
- •12. Понятие смешанной стратегии, чистой стратегии, активной стратегии.
- •14.Граф.Метод реш-ия игры 2х2 (формулы).
- •15.Доминирущие стратегии, заведомо невыгодные стратегии, упрощение игр.
- •16. Сведение игры mxn к двойственной задаче лп
- •17.Игры с природой: постановка задачи, матрица рисков.
- •18. Критерий принятия решений в условиях риска (Байеса 1 и 2). Лемма (показатели эффективности и неэффективности стратегии). Теорема об эквивалентности критериев Байеса.
- •19. Критерий принятия решений в условиях неопределенности: критерий Лапласа и Сэвиджа
- •20. Критерий принятия решений в условиях неопределенности: критерий Вальда и Гурвица
- •21.Общая постановка задачи динамического программирования (дп). Особенности задачи дп
- •22. Принцип оптимальности и уравнение Бэллмана
- •23. Задача о распределении средств между n предприятиями (основные уравнения)
- •25. Понятие маршрута, цепи, простой цепи, цикла для графа. Связные, несвязные графы. Дерево, лес.
- •26. Планарные и плоские графы. Изоморфные графы. Полные графы.
- •27. Эйлеровы графы. Критерий существования эйлерова цикла в графе. Полуэйлеров граф. Задача о Кенигсбергских мостах.
- •28. Гамильтонов граф. Достаточные признаки существования гамильтонова цикла (связь с полнотой цикла, теоремы Оре и Дирака). Полугамильтонов граф.
- •29.Орграфы, турниры. Предки и потомки вершин. Алгоритм Фалкерсона разбиения орграфа на слои.
- •30.Комбинаторная постановка задачи коммивояжера.
- •31. Постановка задачи коммивояжера в виде задачи целочисленного программирования. Условие наличия одного цикла.
- •32. Постановка задачи коммивояжера на языке теории графов.
- •33. Теорема о приведения матрицы расстояний в зк. Оценка маршрута снизу (нижняя граница).
- •34. Ветвление, оценки нулевых переходов, уточнение нижней границы маршрута.
- •35. Метод ближайшего соседа: эвристический алгоритм. Верхняя граница маршрута.
29.Орграфы, турниры. Предки и потомки вершин. Алгоритм Фалкерсона разбиения орграфа на слои.
Орграфом называется пара , где непустое конечное множество элементов, называемых вершинами, а — конечное семейство упорядоченных пар элементов из , называемых дугами (илиориентированными ребрами ). Дуга, у которой вершина является первым элементом, а вершина — вторым, называетсядугой из в . Заметим, что дуги и различны. Хотя графы и орграфы — различные объекты, в определенных случаях графы можно рассматривать как орграфы, в которых каждому ребру соответствуют две противоположно ориентированные дуги. и называются соответственно множеством вершин и семейством дуг орграфа .
Турниром называется орграф, в котором любые две вершины соединены ровно одной дугой.
Алгоритм Форда–Фалкерсона решает задачу нахождения максимального потока в транспортной сети.
Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: f(u,v) = 0 для всех . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.
30.Комбинаторная постановка задачи коммивояжера.
Задача коммивояжёра (коммивояжёр — разъездной сбытовой посредник) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов.
31. Постановка задачи коммивояжера в виде задачи целочисленного программирования. Условие наличия одного цикла.
При решении многих задач нецелочисленное решение не имеет смысла. Раздел математического программирования, в котором на экстремальные задачи налагается условие дискретности переменных при конечной области допустимых решений, называется дискретным программированием. При наличии условия целочисленности имеется в виду подраздел дискретного программирования - целочисленное программирование.
Коммивояжер должен посетить один, и только один, раз каждый из n городов и вернуться в исходный пункт. Его маршрут должен минимизировать суммарную длину пройденного пути.
Математическая модель задачи: , ,
Условия неотрицательности и целочисленности: , .
Добавляется условие прохождение маршрута через все города, т.е. так называемое условие цикличности. Иначе, маршрут должен представлять собой замкнутую ломаную, без пересечений в городах-точках
32. Постановка задачи коммивояжера на языке теории графов.
Задача коммивояжера может быть сформулирована как задача на графе в следующей постановке: построить граф G(X, A), вершины которого соответствуют городам в зоне коммивояжера, а дуги отображают коммуникации, соединяющие пары городов. Пусть длина a(х, у) > 0 каждой дуги (х, у) є А равна расстоянию, стоимости или времени. Контур, включающий каждую вершину графа G хотя бы один раз, называется маршрутом коммивояжера. Контур, включающий каждую вершину графа G ровно один раз, называется гамильтоновым контуром (по имени ирландского математика Вильяма Роуана Гамильтона, который в 1859 г. первым начал изучение этих задач).
Города — это вершины графа.
Дороги между городами — это ориентированные ребра графа.
Длина соответствующей дороги — это вес ребра.
Граф должен быть полным, т.е. в нем имеются все возможные ребра. Если граф не является полным, то его можно дополнить недостающими ребрами с весом =
Путь, который требуется найти, - это ориентированный оставный, простой цикл, минимального веса в графе. Такие циклы называются гамильтоновыми.
Оставным циклом называется такой цикл, который проходит через все вершины. Вес цикла — это сумма веса всех ребер.