- •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. Метод ближайшего соседа: эвристический алгоритм. Верхняя граница маршрута.
35. Метод ближайшего соседа: эвристический алгоритм. Верхняя граница маршрута.
Алгоритм ближайшего соседа — один из простейших эвристических методов решения задачи коммивояжёра. Относится к категории «жадных» алгоритмов.
Формулируется следующим образом:
Пункты обхода плана последовательно включаются в маршрут, причем, каждый очередной включаемый пункт должен быть ближайшим к последнему выбранному пункту среди всех остальных, ещё не включенных в состав маршрута.
Алгоритм прост в реализации, быстро выполняется, но, как и другие «жадные» алгоритмы, может выдавать неоптимальные решения. Одним из эвристических критериев оценки решения является правило: если путь, пройденный на последних шагах алгоритма, сравним с путём, пройденным на начальных шагах, то можно условно считать найденный маршрут приемлемым, иначе, вероятно, существуют более оптимальные решения. Другой вариант оценки решения заключается в использовании алгоритма нижней граничной оценки.
Для любого количества городов большего трех в задаче коммивояжёра можно подобрать такое расположение городов (значение расстояний между вершинами графа и указание начальной вершины), что алгоритм ближайшего соседа будет выдавать наихудшее решение.