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

Мы получили задачу о назначениях, но ограничения не определяют однозначно маршрут и могут появиться несколько циклов. Чтобы цикл был единственным, используем подход Таккера, введя дополнительно (n-1) переменную u₂,u₃,…,u_n и (n-1)×(n-2) ограничения (3): u_i– u_j+ x_ij·(n-1) ≤ n–2, где 2 ≤ i≠ j≤ n. Тогда

a)  если $ допустимое решение (X,u) задачи (1)-(3), то матрица X имеет единственный цикл (т.е. маршрут коммивояжера);

b)  если $ маршрут коммивояжера (допустимая матрица Х с одним циклом), то $ и вектор u=(u₂,u₃,…,u_n), удовлетворяющий ограничениям (3).

Доказательство: Докажем a): предположим противное, т.е. что цикл не единственный Þ существует цикл, не проходящий через точку 1. Пусть вершины этого цикла имеют номера , т.е. все . Имеем:

,                          …

,                          ,

…                                                                    .

Складывая все эти неравенства, получим  n–1 ≤ n–2, т.е. - противоречие.

Докажем b). Пусть u_i - номер шага, на котором мы попадем в точку i, начиная движение с точки 1. Такие u_i удовлетворяют ограничениям (3):

1)  Пусть пара (i,j) – звено маршрута (i¹1) Þ u_i– u_j= –1 по определению u. Кроме того, x_ij= 1, Þ получим: -1+1·(n-1) ≤ n-2, т.е. верно.

2)  Пара (i,j) Ï маршруту Þx_ij= 0, и u_i– u_j≤ n–2 по определению u.

Но для этой задачи матрица ограничений не вполне унимодулярна. Поэтому, если отбросить условие целочисленности, можно получить дробные решения. Þ Такой подход вообще не позволяет корректно решать задачу коммивояжера.

Метод динамического программирования для ЗК.

Принцип оптимальности Беллмана: любая часть оптимального решения оптимальна.

Пусть S Ì{2,3,…, n}, kÎS, а C (S, k) – длина кратчайшего пути из 1 в k, проходящего по всем пунктам множества S. Тогда C ({k}, k) = d_1k , а при | S | > 1 C (S, k) = min [C (S \ {k}, m) + d_mk], где минимум берется по всем mÎS \ {k}. Нужно хранить argmin, чтобы восстанавливать оптимальный путь. Придется вычислять и сохранять C (S, k) для всех множеств S  и всех mÎS . Для этого требуется память объемом V_n и T_n операций сравнения и сложения.  

Метод ветвей и границ для ЦЛП.

Пусть Z есть задача ЦЛП (x-целое). Рассмотрим функционалы F _ЛП и F _ЦЛП

D_ЛП - область определения ЛП, D_ЦЛП   - область определения ЦЛП

D_ЛП É D_ЦЛПÞ F_ЛП  ³ F_ЦЛП ,           Это соотношение задает границу для F_ЦЛП

Описание  МВиГ:     Вход: описание задачи Z.

Оценка (Z)     /* решение вспомогательной ЛП, т.е. нахождение x_ЛП и F_ЛП*/

If x_ЛП – целое Then Return(x_ЛП)  Else  { r =-¥;  OPEN ={Z};

/* OPEN - упорядоченное по значениям F_ЛП AVL-дерево.*/ }

While (OPEN¹Æ) do                          /* основной цикл */

s= pop(OPEN); OPEN-={s};     /*выбор вершины списка OPEN как */

/* текущей задачи s и удаление ее из списка*/

СПИСОК1= список_дочерей_s;  /* СПИСОК1-очередь на оценку*/ выбор для ветвления нецелочисленной координаты x_i0;

s1=sÈ{ x_i0<[ x_i0опт]}; s2=sÈ{ x_i0<[ x_i0опт]+1};

While (СПИСОК1¹Æ) do

s1=pop(СПИСОК1);        СПИСОК1-=s1;

оценка(s1)                                     /* для ЦЛП: решение ЛП для s1 */

Анализ:          If оценка(s1)> r Then                         /* оценка лучше рекорда */

If x^лп_s1-целое

Then    {r = оценка(s1); x_r= x^лп_s1; установка флага очистки списка OPEN }

Else     OPEN+=s1; /* с учетом оценки s1*/

End_While_ СПИСОК1

If  флаг очистки установлен

Then  удаляем из списка OPEN все вершины, оценка которых < r

End_While_OPEN;

Return(r,x_r);

End.

№9. Пример:         2x₁+5x₂àmax

x₁+3x₂ £ 9

3x₁+2x₂ £ 12               x₁,x₂ ³ 0

для ЛП z=(¹⁸/₇, ¹⁵/₇)     f_опт^лп=15⁶/₇

f_опт^злп =?                         Z  (¹⁸/₇,¹⁵/₇)

Z₁=Z È {x₂ £ 2}              Z₂=Z È {x₂ ³ 3}

(⁸/₃,2), f_опт=15¹/₃                     (0,3), f_опт^злп=15

получили целочисленное решение стоимостью 15. Это уже точно одно из решений целочисленной задачи => (0,3) записываем в рекорд (R).

На следующих шагах (если f_опт^лп > f_опт^цлп  или нужно найти все решения):