Редактирование: Методы Оптимизации, Теормин

 

Пусть <math>\Sigma</math> — конечный алфавит, а <math>\Sigma^*</math> — множество слов в этом алфавите. Отображение e: <math>\Pi \rightarrow \Sigma^*</math> называется кодировкой задачи <math>\Pi</math>.

 

 

'''Кодировка задачи P''' — такое отображение <math>e: P \rightarrow \Sigma^* </math>, обладающее следующими свойствами:

* <math>e, e^{-1}</math> — полиномиально вычислимы

<math>\exists p(.): \forall I \in \Pi ~~ |e(I)| < p(|e_{1}(I)|)</math>

'''Язык массовой задачи''' — это множество правильных слов, то есть слов, соответствующих ИЗ, имеющим положительный ответ(подразумевается задача распознавания): <math>L(\Pi, e) = e(Y(\Pi)) = \{s \in \Sigma^*| s = e(I), I \in Y(\Pi)\}</math>

'''Язык алгоритма''' — множество слов, принимаемых <math>A</math>, то есть таких, на которых алгоритм останавливается в состоянии <math>q_Y</math>, что соответсвует "да": <math>L(A) = \{\sigma \in \Sigma^* | A(\sigma) = q_Y\}</math>

Алгоритм <math>A</math> '''решает''' массовую задачу <math>\Pi</math>, с кодировкой <math>e</math>, если <math>L(e, \Pi) = L(A)</math> и <math>\forall s \in \Sigma^*</math> А останавливается

 

 

'''Временная сложность''' <math>T_{A}(n) = max_{s \in \Sigma^*, |s| < n} \{t_{A}(s)\} </math>.

''Методичка, стр. 8-11''

* ∀А, решающего П с кодировкой e, ∀p(·) ∃I ∈ П: <math>t_A(e(I)) > p(|e(I)|)</math>

'''Класс недетерминированно полиномиальных задач (NP)''' -- это такие задачи, для которых существует алгоритм решения на недерменированной машине Тьюринга:

''Методичка, стр. 11''

''Методичка, стр. 12-14''

* <math>\text{co-NP} = NP</math> пока не удалось ни доказать, ни опровергнуть, но это вряд ли верно.

''Методичка, стр. 15''

''' Критерий NP-полноты. ''' Массовая задача <math>\Pi</math> '''NP-полна''' тогда и только тогда, когда она принадлежит классу '''NP''' и к ней полиномиально сводится какая-либо '''NP-полная''' задача.

''Методичка, стр. 17-18''

Легко показать, что <math>P \subseteq \text{NP} \cap \text{co-NP}</math>. Рабочая ''гипотеза'', что <math>P = \text{NP} \cap \text{co-NP}</math>.

Если для некоторой NP-полной задачи <math>\Pi</math> дополнительная к ней задача <math>\overline{\Pi} \in \text{NP}</math>, то <math>\text{NP} = \text{co-NP}</math>

''Гипотеза.'' <math>\text{P} \subset \text{PSPACE}</math> (то есть, не факт, что вложение строгое, но скорее всего так). При этом NP-полные, NP-трудные, NP-эквивалентные задачи <math> \subset \text{PSPACE} \setminus \text{P}</math>

[http://en.wikipedia.org/wiki/Pseudo-polynomial_time en-wiki]

Массовая задача <math>\Pi</math> называется '''сильно NP-полной''', если её полиномиальное сужение является NP-полным. Примеры:

* задача булевых линейных неравенств -- ВЫП сводится к её полиномиальноу сужению, где числовые параметры (правая часть неравенств) линейны.

* задача о целочисленном решении системы линейных уравнений -- , т.к. БЛН сводится к ней

* задача коммивояжёра (TSL) -- совпадает со своим сужением

 

 

=== Определение ε-приближенного алгоритма и полностью полиномиальной приближенной схемы (ПППС). Связь между существованием ПППС и псевдополиномиальностью ===

 

 

 

 

''Методичка, стр. 24''

'''Теорема''' Если для <math>\Pi</math> оптимизации

* соответствующая ей задача распознавания свойств является сильно NP-полной

* существует полином <math>\exists p'(\cdot) : \mathrm{Opt}_\Pi(I) < p'(M(I)) ~~ \forall I \in \Pi</math>

то при условии, что <math>\mathrm{P} \neq \mathrm{NP}</math> для <math>\Pi</math> не существует ПППС

'''Утверждение (принцип граничных решений)'''. Если озЛП имеет решение, то найдется такая подматрица <math>A_I</math> матрицы <math>A</math>, что любое решение системы уравнений <math>A_I x = b_I</math> реализует максимум <math>\langle c,x \rangle</math>.

=== Геометрическое описание симплекс-метода ===

(Копипаста из [[http://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BC%D0%BF%D0%BB%D0%B5%D0%BA%D1%81-%D0%BC%D0%B5%D1%82%D0%BE%D0%B4 ru.wiki]], там-же есть хорошая иллюстрация.)<br>

Симплекс-метод -- метод решения озЛП.

Каждое из линейных неравенств в <math>Ax \leqslant b</math> ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным конусом.

Уравнение <math>W(x) = c</math>, где <math>W(x)</math> — максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость <math>L(c)</math>. Зависимость от <math>c</math> порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку — требуется найти такое наибольшее <math>c</math>, что гиперплоскость <math>L(c)</math> пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его ребрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.

<math>\Delta(D) = \max | \det(D_1) | </math>, где <math>D_1</math> — квадратная подматрица <math>D</math>.

'''Теорема (о границах решений).''' Если задача озЛП <math>d^{*} = \max\langle c, x\rangle, x \in \mathbb{R}^{n}, Ax \leqslant b</math> размерности (n, m) с целыми коэффициентами разрешима, то у нее существует рациональное решение <math>x^{*}</math> в шаре: <math>\| x^{*}\| \leqslant \sqrt{n} \Delta([A|b])</math> и <math>d^{*} = \frac{t}{s}~,~~ t,s \in Z,~~|s| \leqslant \Delta(A)</math>

Введем функцию невязки в точке x -- <math>t(x) = \max_i((Ax)_i - b_i)</math>. Точка <math>x^{0}=\overline{0}</math> -- это центр шара <math>E_0</math>. Если <math> t(x^{0}) \leqslant 0</math>, то <math>x^{0}</math> -- решение. Если это не так, то возьмем s: <math>t(x) = \langle a_{s},x^{0}\rangle - b_s</math>, значит <math>x^{0}</math> не удовлетворяет s-ому неравенству системы. Всякий вектор <math>x</math>, удовлетворяющий неравенству s, должен лежать в полупространстве <math>\leqslant \langle a_s, x^{0}\rangle</math>. Пересечение этого полупространства с нашей сферой дают полуэлипсоид. Вокруг получившегося полуэлипсоида описываем новую сферу и повторяем алгоритм заново.

'''Двойственной задачей''' к задаче линейного программирования <math>Ax \leqslant b</math> на максимум <math>\langle c, x\rangle</math> (в форме ОЗЛП можно записать: <math>\max_{x \in \mathbb{R}^n:~Ax \leqslant b} \langle c, x \rangle</math>) называется задача линейного программирования на минимум: <math>\min_{\lambda \in \mathbb{R}^n:~\lambda A = c,~\lambda \geqslant \overline{0}} \langle \lambda, b \rangle</math>

# На основании предыдущего утверждения (см. вопрос о сведении озЛП к однородной системе), есть возможность свести задачу ЛП <math>\max_{x \in \mathbb{R}^n:~Ax \leqslant b} \langle c, x \rangle</math> к поиску решения СЛАУ <math>\hat{P}y = \hat{q},~ y \geqslant \overline{0}</math>, которая, в свою очередь, сводится к однородной СЛАУ: <math>Py = \overline{0},~ y \geqslant \overline{0}</math>

#* <math>p_i, ~ i \in [1,K]</math> -- строки матрицы <math>P</math>

Линейное неравентсво <math>\langle c, x\rangle \leqslant d</math> является следствием разрешимой в вещественный переменных ЛН <math>Ax \leqslant b</math>, тогда и только тогда, когда существуют <math>\lambda _i \in \mathbb{R}</math>:

Система линейных неравенств <math>Ax \leqslant b</math> неразрешима тогда и только тогда, когда разрешима система:

'''Опр.''' Функция f называется '''разделяемой''' на <math>f_1</math> и <math>f_2</math>, если она представима в виде <math>f(x, y) = f_1(x, f_2(y))</math>.

'''Опр.''' Функция f называется '''разложимой''' на <math>f_1</math> и <math>f_2</math>, если:

'''Теорема оптимальности для разложимых функций''': <math> \min_{x,y}(f(x,y)) = \min_x(f_1(x, \min_y(f_2(y)))) </math>.

# Полиномиальный алгоритм округления <math>\epsilon_{1}</math>-приближенного решения системы линейных неравенств

# Оценка сложности метода эллипсоидов <math>\epsilon_{2}</math>-приближенного решения озЛП