Математика \ Теория игр и исследование операций

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

y à max

Пример:

Решение:

  

-x +y - 3£0

x +y-11£0

2x – y -7£0

-2x-3y +6£0

- x+2y - 7£0

4x + y-27£0

-x            £0

-y      £0

y £ y1 = x + 3

y £ y2 = 11 - x

y ³ y3 = 2x -7

y ³ y4 = 2-⅔x

y £ y5 = ½(x+7)

y £ y6 = 27-4x

x ³ x7 = 0

y ³ y8 = 0

I+={1,2,5,6}

I-={3,4,8}      

F+(x)=min{x+3; -x+11; ½(x+7); -4x+27}

F-(x) = max{2x-7; - 2/3x+2; 0 }

I0-={7}

I0+=Æ

u1=max{0/(-1)} =0

u2=+∞

U=[u1,u2]=[0,+∞)

Точки пересечения пар прямых (i, j) из I+ и  I-:

  

(1,2):  x + 3 = 11 – x  Þ 2x=  8 Þ x=4    ÎU

(5,6):  ½(x+7)=27-4x Þ 9x=47 Þ x=52/9 ÎU

(3,4): 2x - 7 = 2 - 2/3x Þ 8x=27 Þ x=33/8 ÎU

X={4,52/9,3⅜}

медиана(X)=4
 

F-(4) =max{1; <0; 0}=1 < 5½ =min{7; 7; 5½; 11}= F+(4) Þ m1=4 допустима. Минимум был один Þ F+(x) в окрестности точки m1 совпадает с прямой y5 = ½(x+7) и возрастает (y¢5>0) Þ максимум находится  справа от m1 Þ корректируем интервал: U=[m1=4, +∞).

Анализируем пары прямых, точки пересечения которых оказались слева от интервала. Пара 1,2ÎI+ Þ можно отбросить прямую y1, лежащую выше, т.к. y¢1 =1 > -1= y¢2;
пара 3,4ÎI- Þ можно отбросить прямую y4, лежащую ниже, т.к. y¢4 = -2/3 < 2= y¢3.

    I-={3, 8}. Ищем точку пересечения новой пары: 2x-7 = 0 Þ x=3½ лежит слева от U Þ сразу отбрасываем прямую y8 , лежащую ниже, т.к. y¢8 = 0 < 2= y¢3. Теперь I-={3}.

    I+={2,5,6}. Здесь оставляем пару (5,6), для которой  x=52/9 є U. Она же медиана m2.
F-(52/9) =2*52/9-7=34/9 < 57/9 =min{57/9; 61/9; 61/9}= F+(52/9) Þ x=52/9  допустима. Минимум был один Þ F+ в окрестности точки m2 совпадает с y2=11-x; y2¢ =-1<0 Þ F+ убывает Þ ее максимум находится  слева от m2 Þ переходим к интервалу: U=[4, m2 =52/9]. Пара 5,6ÎI+ Þ отбрасываем  прямую y6, лежащую выше, т.к. y¢5 =½ > -4= y¢6.

    I+={2,5}. Ищем точку пересечения новой пары: 11-x = ½(x+7) Þ x=5 ÎU=[4, 52/9].

Других пар нет Þ m3 =5. F+(5)= min{y2=11-5=6;y5=½(5+7)=6}>3=F-(5) Þ m3 допустима.

Т.к. F+(5) есть минимум пересекающихся прямых y2 и y5, то F¢+лев =max{y2¢=-1; y5¢=½}>0, F¢+прав =min{y2¢=-1; y5¢=½}<0. Производная меняет знак с + на - Þ m3 - точка максимума.


1.4. ПОНЯТИЕ О NР-ПОЛНОТЕ.

Алгоритм, решающий задачу Z, строит по входной информации выходную. Трудоемкость алгоритма будем оценивать как функцию от объема входа.

 Пример: возведем 2 в степень n. Длина входа = log(n). Трудоемкость алгоритма равна n = 2log n, т.е. зависит от объема входной информации экспоненциально.

Будем различать 3 типа задач поиска:

1.  оптимизационный: найти вектор x оптÎD, такой что ¦(xопт) = extr ¦(x).

2.  вычислительный: найти число ¦опт такое, что ¦опт = extr ¦(x).

3.  распознавания: существует ли (да или нет =1 бит) xÎD  такой, что ¦(x) > L?

Все типы задач можно свести к варианту распознавания свойств.

НЕФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ NP-ПОЛНОТЫ.

Говорят, что массовая задача распознавания Z принадлежит классу NP, если существуют такие полином Pz и алгоритм Az, что для каждой индивидуальной задачи (Z,I) с ответом “да” существует краткое удостоверение xответа, быстро проверяемого алгоритмом Az (т.е.  и ).Краткого удостоверения ответа “нет” при этом может и не существовать.

Скачать файл