Теория игр и исследование операций. Модели, алгоритмы, сложность: Конспект лекций, страница 35

Прореживаем его так же, как в предыдущем алгоритме: 1 2 3 6 4 5 7 8 1.

Докажем, что его длина превышает оптимум не более, чем на.50%.

Пусть {i₁, i₂,…,i_2m}- множество вершин из V’, выписанных в порядке появления их на оптимальном маршруте коммивояжера. Тогда по неравенству треугольника имеем для паросочетаний 

S₁ = {(i₁, i₂), (i₃, i₄),…} и  S₂ = {(i₂, i₃), (i₄, i₅),…}:

D_постр £ D_МОД + D_МПС < D_опт + D_МПС , и D_опт ³ D(S₁) + D(S₂) ³ 2×D_МПС  Þ.

Приведем пример того, что эта оценка неулучшаема. МОД – k треугольников.

при  

3.7. ТОЧНЫЕ МЕТОДЫ РЕШЕНИЯ NP-ПОЛНЫХ ЗАДАЧ.

№29 Решение задачи коммивояжера методом ветвей и границ.

На основе чего делать ветвление? Фиксируем любую часть пути – цепочку длины D.

На вершинах, не вошедших в цепочку, построим МОД.

D_опт  – оптимальная длина при фиксированной цепочке,

-длина перемычки,  D_опт ≥ D + D_МОД + D_перем.= D_постр

Если D_постр ³ R , то цепочку можно отбросить (R – сам цикл). R – рекорд, т.е. если R - D £ D_МОД + D_перем, то цепочка не улучшает рекорд, Þ отсечение.

Некоторые ребра можно выкидывать. Если из гамильтонова цикла выкинем любое ребро, то останется цепочка, для которой D_опт ³ D_МОД (v), Þ
R ³ D_опт ³ D_МОД (v) + r (на множестве всех вершин графа, r-длина любого ребра, вошедшего в оптимальный цикл). Получаем  r £ R – D_МОД (v).

Если r > R – D_МОД (v), то это ребро в улучшающий цикл не войдет.

Чтобы улучшить рекорд, необходимо r < R – D_МОД (v).                            Решаем:

1.  Сначала строим текущий рекордный цикл R:

f_R=14

2.  Строим МОД алгоритмом Тарьяна: 1 – 2 – 5 – 3 – 4 – 6,  D_МОД  =7

3.  Отбросим ребра (1,4) и (1,6), длина которых.³ f_R - D_МОД = 14-17 = 7. Вершина 1 имеет степень 2 Þ ребра (1,2) и (1,5) участвуют в цепи,  хорда (2,5) не участвует (иначе возникнет цикл). Начнем построение с вершины 5, ее степень больше, чем у 2.

Для вершины 1?: f_R-D=14-8=6         Для вершины 2: f_R-D=14-7=7

Þ Ветвим и делаем перепроверку, т.к. получен новый рекорд: f_R=12

f_R-D=12-7=5=5= улучшения нет, Þ отсечение.

Для вершины 6: ,

Для нижней вершины 3:      D=10,              f_R-D=14-10=4

,

Для нижней вершины 4:      D=9,                f_R-D=14-9=5

Þ ветвим, но мы получили цикл, Þ   (r<12-7=5, оставляем. Стоп.)

Все висячие вершины раскрыты Þ R – оптимален,   f_R=12.

Этот метод работает, если граф неориентированный ( для построения МОД).

№30. Задача оптимального распределения ограниченного ресурса.

Пусть задан ресурс R ³ 0 и n потребителей со своими функциями прибыли j _i(x). Требуется распределить ресурс между потребителями: R = S_i r_i , r_i ³ 0, максимизируя суммарную прибыль S_i j _i(r_i). Заметим, что любая часть оптимального распределения сама является оптимальным распределением (принцип Беллмана).

Пусть F_k(y) ={ j _k(x_k) + F_k+1(y-x_k)} - максимальная прибыль потребителей с номерами от k до n-1 при распределении между ними ресурса y и F_n(y) = j _n(y). ЕслиR и r_i – целые, то, меняя k от n-1 до 1 (метод динамического программирования), мы найдем максимальную прибыль F₁(R). Трудоемкость = O(n×R²).

Пример: 3 экзамена за 8 дней. j _i – оценка на экзамене, x - время на подготовку.