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

Пересечение конечного числа гиперплоскостей в Âⁿ есть выпуклое множество M ÎÂⁿ. Экстремум линейной функции на M достигается на его границе G_M. Разложим Âⁿ в прямую сумму линейной оболочки L, натянутой на вектор c, задающий линейный функционал, и ортогонального L подпространства Â^n-1. Границу G_M можно рассматривать как объединение графиков двух функций – выпуклой f_- и вогнутой f₊ ³ f_-, заданных на M¢ - проекции M на Â^n-1. Заключим M¢ в любой эллипс E и проведем в его центре a вычисления: находим значения f и Ñf= субградиент = направляющий вектор опорной к графику гиперплоскости. Из условия выпуклости  f(x) ³ f(a) + Ñf(a)∙ (x-a) следует, что не надо искать минимум в полупространстве Ñf(a)∙ (x-a) > 0, т.к. f(x) > f(a). Оставшуюся половину эллипса заключим в новый эллипс E₁ и повторим вычисления в его центре и т.д. Юдин и Немировский (Москва,1976) показали, что отношение объемов
V(E_k) / V(E_k-1) < ²⁽ⁿ⁺¹⁾√¯e^-1 <1. Þ V(E_k) ® 0 в Â^n-1. С ростом размерности пространства стремление к 0 замедляется, но место имеет. Хуже, что линейные расстояния при этом совсем необязательно стремятся к 0 (эффект оврага).

Однако вскоре было доказано, что полиномиальную трудоемкость имеет и алгоритм А.Левина (Воронеж,1965), названный методом центров тяжести. Б.Митягин (Воронеж,1969) доказал, что при рассечении любого выпуклого тела любой размерности любой гиперплоскостью, проходящей через его центр тяжести, объем любой его части составляет от  е^-1 » 36,8%   до  1-е^-1 » 63,2%  объема тела.

С 1971 по 2004 год А.Ю.Левин работал в ЯрГУ, заведовал основанной им кафедрой теоретической кибернетики, из которой впоследствии вырос факультет ИВТ. На матфаке ЯрГУ ее преемницей является кафедра КБиММОИ.

Приводимый ниже алгоритм основан на близкой идее – уточняя на очередном шаге решение задачи мы уменьшаем объем не только локализатора (длину интервала), но и всей входной информации (часть ограничений отбрасываем).

№8. ЛИНЕЙНЫЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ ЛП В Â² (Megiddo,1983).

Пусть b>0. Введя обозначения X=x, Y=ax+by, получим более простую задачу:

Разобьем множество ограничений на 4 части: I⁺ ={i | b_i>0 },   I^-={i | b_i<0 }, I⁰⁺={i | b_i=0 и a_i>0},  I^0-={i | b_i=0 и a_i<0} и построим интервал [u₁, u₂], где u₂=+¥ при I⁰⁺=Æ, иначе , и u₁=-¥ при I^0-=Æ, иначе . Если u₁>u₂, то исходная задача ЛП недопустима. Пусть . Построив нижнюю огибающую семейства прямых I⁺ и верхнюю огибающую семейства I^-, мы свели исходную задачу к виду:

F₊(x)®maxпри ограничениях   xÎ[u₁, u₂]   и   F₊ (x) ³F_- (x).

Алгоритм Меджиддо для задачи ЛП в ² имеет линейную трудоемкость, т.к. рекуррентное неравенство для трудоемкости имеет вид   .

1)  Элементы множеств I⁺, I^- разбиваем на пары и для каждой пары прямых ищем точку пересечения z_k. Если она Ï(u₁, u₂), то удаляем одну из прямых: лежащую выше (т.е. y¢(z_k) больше), если (пара из I⁺ и z_k.£u₁ ) или (пара из I^- и z_k³u₂).

2)  В множестве Z оставшихся точек пересечения ищем медиану m по координате x.

3)  В точке m проводим вычисления (чтобы определить направление поиска):

a.  Сначала допустимость! D= F₊(m)-F_-(m) вогнута и д.б. ³0, иначе анализ производной D¢

b.  Определяем множество I^+m прямых из I⁺, на которых в mдостигается min. Ищем в этой точке левую и правую производную функции F₊(x).
      .                              .

c.  Если обе производные > 0, то max следует искать справа (т.е. u₁=m). Если обе производные < 0, то max следует искать слева (т.е. u₂=m).

d.  Если переход с + на -, то m есть точка max. В противном случае надо смотреть на знак  производной от разности F₊(m)-F_-(m).

4)  Повторяем вычисления с пункта 1 на новом интервале, причем половина точек z_k окажется вне интервала, и для них отбрасываем одно ограничение из пары. В результате не менее четверти ограничений будет отброшено!