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

Алгоритм «Разделяй и властвуй».

Разделим точки пополам произвольным образом. Для двух множеств решим задачу рекурсивно, и соединим построенные оболочки. Как соединять? Берем внутреннюю точку (центр тяжести) одной оболочки. Построим полярные углы из нее на точки обоих оболочек. Если выбранная точка лежит вне выпуклой оболочки второго множества, граница второго множества разбивается на два участка, на одном из которых углы при обходе границы против часовой стрелки убывают, а на втором - возрастают. Удалим внутренние точки участка убывания. Теперь все углы в обоих оболочках возрастают. Сольем их в одно упорядоченное множество углов и выполним шаг 3 алгоритма Грехема за линейное время. Из уравнения  следует трудоемкостьO(n·log n).

НАХОЖДЕНИЕ ДИАМЕТРА КОНЕЧНОГО МНОЖЕСТВА ТОЧЕК

Две точки a и b назовем противоположными в Х, если существуют две параллельные опорные (охватывающие все множество Х) прямые, проходящие через a и b.

Вращая две такие прямые вокруг выпуклой оболочки множества Х и сравнивая углы между ними и границей оболочки, получим все n пар противоположных точек, перебрав которые найдем наиболее удаленную пару – диаметр множества. В примере это пара (1,4).

Кстати, минимальная описанная окружность опирается или на диаметр или на 3 точки и ее центр – вершина ДВ дальней точки (строится аналогично обычной ДВ).

ПОСТРОЕНИЕ ОГИБАЮЩЕЙ СЕМЕЙСТВА ПРЯМЫХ.

Дано n прямых. Требуется построить верхнюю/нижнюю огибающую. Используя метод “разделяй и властвуй”, делим все прямые на два множества, строим огибающие для каждого из них и сливаем их в общую огибающую. Алгоритм напоминает построение выпуклой оболочки, только точка наблюдения находится на бесконечности. Трудоемкость – O(n·log n)

1.3. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ (ЛП) В Âⁿ.

Дадим экономическую интерпретацию параметров прямой задачи ЛП.

Планирование по валу. Пусть A = {a_ij³ 0} - технологическая матрица, где a_ij - расход i-го ресурса для производства единицы j-го товара,

x = (x₁,…,x_n) ³ 0 - план выпуска товара, где x_j - количество единиц j-го товара,
b = (b₁,…,b_m) ³ 0 - вектор имеющихся ресурсов, c = (c₁,…,c_n) - вектор цен на товары. Тогда Ax – расход ресурсов (который не может быть больше b) , а c’x– подлежащая максимизации прибыль от продажи товара x. ‘ = знак транспонирования.

Планирование по номенклатуре. Если мы хотим, чтобы произведенного товара хватило на l комплектов (вектор  показывает, сколько единиц каждого из товаров входит в 1 комплект), то , и требуется максимизировать .

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

Th1: Если x,y – допустимы в задачах П и Д, то  y¢b³c¢x.

Доказательство: y¢b³y¢(Ax)= (y¢A)x³c¢x.

Следствие: Если x, y допустимы и  y¢b=c¢x, то x, y – оптимальны.

Th2: Если задача П допустима (т.е. существует допустимый x), а задача Д  - недопустима, то задача П - неограничена.

Th3: Если задачи П и Д допустимы, то обе имеют решения, и  y¢b= c¢x.

Th4 (о дополняющей нежесткости, ТДН). Предварительные обсуждения.

Пусть задачи П и Д допустимы, и (x, y) – оптимальные решения Þ (b–Ax)³0,  (c’–y’A)£0, x³0, y³0, и по Th3 верно равенство y¢b= c¢x. Вычитая  y’Ax  из обеих частей равенства, получим c¢x- y¢Ax =y¢b - y¢Ax, или 0£y’(b–Ax)=(c’-y’A)x£0. Т.е. имеем  y’(b – Ax)= 0  и  (c’-y’A)x= 0, но в силу знакопостоянства компонент всех векторов получаем покомпонентные равенства  y_j’(b–Ax)_j=0  и  (c’-y’A)_ix_i=0

Формулировка ТДН.:         Если задачи П и Д допустимы, то

(x, y) оптимальны  Ûy_j’(b–Ax)_j=0  и  (c’-y’A)_ix_i=0 для всех индексов i,j.