matan
4.Оценка свободной клетки, ее экономический смысл, критерий оптимальности базисного распределения поставок.
Z(x)↑ - плохо; ∆ij>0. Z(x)↓ - хорошо – наша цель∆ij<0.
Оценка клетки (i, j), ∆ij:
X = {xij} – оптимальное, если оценки всех свободных клеток не отрицательны. Если хотя бы одна оценка отрицательна, то решение не оптимально. Для пересчета таблицы составляется цикл. Цикл пересчета: начинается в свободной клетке и заканчивается в ней же, все остальные базисные. Все повороты в базисных клетках под 90 градусов. Ломанная цикла замкнута. Оценка свободной клетки равна приращению суммарных затрат на перевозку, если дать в эту клетку единичную поставку.
Yandex.RTB R-A-252273-3Содержание
- 1.Экономико-математическая модель транспортных задач
- 2.Общая формулировка тз
- 3.Теор. (о ранге сис-мы ограниченной закр. Тз) и следствие из нее. Открытая тз
- 4.Оценка свободной клетки, ее экономический смысл, критерий оптимальности базисного распределения поставок.
- 5.Теорема о потенциалах свободных клеток. Вычисление оценок свободных клеток методом потенциалов.
- 6.Понятие об игровых моделях
- 7.Классификация игр.
- 8.Формальное представление игр
- 10.Фундаментальное неравенство для цен антагонистических игр
- 11.Седловая точка. Теорема о седловой точке
- 12.Понятие смешанной стратегии, чистой стратегии, активной стратегии
- 13.Теорема об активной стратегии. Решение игры 2×2 (формулы)
- 14.Графический метод решения игры 2×2
- 15.Доминирующие стратегии, заведомо невыгодные стратегии, упрощение игр.
- 16.Сведение игры m×n к двойственным задачам лп
- 17.Игры с природой: постановка задачи, матрица рисков.
- 18.Критерий принятия решений в условиях риска (Байеса I и II). Лемма (показатели эффективности и неэффективности стратегии). Теорема об эквивалентности критериев Байеса.
- 19.Критерий принятия решений в условиях неопределенности: критерий Лапласа и Сэвиджа
- 20.Критерий принятия решений в условиях неопределенности: критерий Вальда и Гурвица. Показатель оптимизма.
- 21.Общая постановка задачи динамического программирования (дп). Особенности задачи дп
- 22.Принцип оптимальности и уравнения Беллмана
- 23. Задача о распределении средств между n предприятиями (основные уравнения).
- 25. Понятие маршрута, цепи, простой цепи, цикла для графа. Связные, несвязные графы. Дерево, лес.
- 2 6. Планарные и плоские графы. Изоморфные графы. Полные графы.
- 27. Эйлеровы графы. Крит. Сущ-я эйлерова цикла в графе. Полуэйлеров граф. Задача о Кенигсбергских мостах.
- 28. Гамильтонов граф. Достаточные признаки существования гамильтонова цикла (связь с полнотой цикла, теоремы Оре и Дирака). Полугамильтонов граф.
- 29.Орграфы, турниры. Предки и потомки вершин. Алгоритм Фалкерсона разбиения орграфа на слои.
- 30.Комбинаторная постановка задачи коммивояжера.
- 31. Постан-ка зад. Коммивояжера в виде задачи целочисленного программирования. Условие наличия одного цикла.
- 32. Постановка задачи коммивояжера на языке теории графов.
- 33. Теорема о приведения матрицы расстояний в зк. Оценка маршрута снизу (нижняя граница).
- 34. Ветвление, оценки нулевых переходов, уточнение нижней границы маршрута.
- 35. Метод ближайшего соседа: эвристический алгоритм. Верхняя граница маршрута.