Редактирование: Методы Оптимизации, Теормин
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 40 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 8: | Строка 8: | ||
* список свободных параметров; | * список свободных параметров; | ||
* формулировка свойств, которым должно удовлетворять решение задачи. | * формулировка свойств, которым должно удовлетворять решение задачи. | ||
- | |||
<math>\Pi</math> есть множество индивидуальных задач <math>I \in \Pi</math>. '''Индивидуальная задача''' получается, если всем параметрам присвоить конкретные значения. | <math>\Pi</math> есть множество индивидуальных задач <math>I \in \Pi</math>. '''Индивидуальная задача''' получается, если всем параметрам присвоить конкретные значения. | ||
- | + | Пусть <math>\Sigma</math> - конечный алфавит, а <math>\Sigma^*</math> - множество слов в этом алфавите. Отображение e: <math>P \rightarrow \Sigma^*</math> называется кодировкой задачи П. | |
- | Пусть <math>\Sigma</math> | + | |
- | + | ||
'''Алгоритм <math>A</math> решает массовую задачу''' <math>\Pi</math>, если для любой индивидуальной задачи <math>I \in \Pi</math> : | '''Алгоритм <math>A</math> решает массовую задачу''' <math>\Pi</math>, если для любой индивидуальной задачи <math>I \in \Pi</math> : | ||
Строка 20: | Строка 17: | ||
* <math>A</math> дает решение <math>I</math> | * <math>A</math> дает решение <math>I</math> | ||
- | + | '''Кодировка задачи P''' -- такое отобраение <math>e: P \rightarrow \Sigma^* </math>, обладающее следующими свойствами: | |
- | '''Кодировка задачи P''' | + | |
* Возможность однозначно декодировать, то есть у двух различных ИЗ не может быть одинаковых кодировок. | * Возможность однозначно декодировать, то есть у двух различных ИЗ не может быть одинаковых кодировок. | ||
- | * <math>e, e^{-1}</math> | + | * <math>e, e^{-1}</math> -- полиномиально вычислимы |
* Кодировка не избыточна, то есть для любой другой кодировки <math>e_1</math>, удовлетворяющей 1 и 2 условиям справедливо: | * Кодировка не избыточна, то есть для любой другой кодировки <math>e_1</math>, удовлетворяющей 1 и 2 условиям справедливо: | ||
- | <math>\exists p(.): \forall I \in \Pi ~~ |e(I)| < p( | + | <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>t_{A}(s)</math> -- число шагов алгоритма <math>A</math> для входа <math>s \in \Sigma^*</math>. | |
- | + | ||
- | + | ||
- | + | ||
'''Временная сложность''' <math>T_{A}(n) = max_{s \in \Sigma^*, |s| < n} \{t_{A}(s)\} </math>. | '''Временная сложность''' <math>T_{A}(n) = max_{s \in \Sigma^*, |s| < n} \{t_{A}(s)\} </math>. | ||
Строка 55: | Строка 49: | ||
* задачи, для которых длина записи выхода превышает любой наперед заданный полином от длины входа | * задачи, для которых длина записи выхода превышает любой наперед заданный полином от длины входа | ||
** найти все маршруты в задаче коммивояжёра | ** найти все маршруты в задаче коммивояжёра | ||
- | * ∀А, решающего П с кодировкой e, ∀p(·) ∃I ∈ П: <math>t_A(e(I)) > p(|e(I)|)</math> | ||
- | |||
- | '''Класс | + | '''Класс недетерменированно полиномиальных задач (NP)''' -- это такие задачи, для которых существует алгоритм решения на недерменированной машине Тьюринга: |
* <math>\exists \hat{A}</math> для НДМТ такой, что <math>\hat{A}</math> решает массовую задачу <math>\Pi</math> с кодировкой <math>e</math> | * <math>\exists \hat{A}</math> для НДМТ такой, что <math>\hat{A}</math> решает массовую задачу <math>\Pi</math> с кодировкой <math>e</math> | ||
* <math>\exists p(\cdot)</math> -- полином такой, что <math>\hat{T}_{\hat{A}}(n) < p(n)~~,~\forall n \in Z_{+}</math> | * <math>\exists p(\cdot)</math> -- полином такой, что <math>\hat{T}_{\hat{A}}(n) < p(n)~~,~\forall n \in Z_{+}</math> | ||
Строка 96: | Строка 88: | ||
''Методичка, стр. 15'' | ''Методичка, стр. 15'' | ||
- | ''' Критерий NP-полноты. ''' Массовая задача <math>\Pi</math> '''NP-полна''' тогда и только тогда, когда она принадлежит классу '''NP''' и к ней полиномиально сводится | + | ''' Критерий NP-полноты. ''' Массовая задача <math>\Pi</math> '''NP-полна''' тогда и только тогда, когда она принадлежит классу '''NP''' и к ней полиномиально сводится хотя бы одна '''NP-полная''' задача |
=== Д-во NP-полноты задачи 3-выполнимость. NP-трудные задачи === | === Д-во NP-полноты задачи 3-выполнимость. NP-трудные задачи === | ||
Строка 110: | Строка 102: | ||
=== Взаимоотношение классов P, NP и NPC, NP и co-NP. Класс PSPACE === | === Взаимоотношение классов P, NP и NPC, NP и co-NP. Класс PSPACE === | ||
- | + | ''Гипотеза.'' <math>\Pi \subseteq \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> | + | ''Гипотеза.'' Если для некоторой NP-полной задачи <math>\Pi</math> дополнительная к ней задача <math>\overline{\Pi} \in \text{NP}</math>, то <math>\text{NP} = \text{co-NP}</math> |
Класс '''PSPACE''' массовых задач -- класс алгоритмов, требующих не более, чем полиномиальной памяти. | Класс '''PSPACE''' массовых задач -- класс алгоритмов, требующих не более, чем полиномиальной памяти. | ||
- | ''Гипотеза.'' <math>\text{P} \subset \text{PSPACE}</math> | + | ''Гипотеза.'' <math>\text{P} \subset \text{PSPACE}</math>. При этом NP-полные, NP-трудные, NP-эквивалентные задачи <math> \subset \text{PSPACE} \setminus \text{P}</math> |
=== Псевдополиномиальные алгоритмы. Пример для задачи о рюкзаке === | === Псевдополиномиальные алгоритмы. Пример для задачи о рюкзаке === | ||
Строка 123: | Строка 115: | ||
Пусть <math>M(I)</math> -- некоторая функция, задающая значение числового параметра индивидуальной задачи <math>I</math>. Если таких параметров несколько, в качестве <math>M(I)</math> можно взять или максимальное, или среднее значение, а если задача вовсе не имеет числовых параметров (например, раскраска графа, шахматы и т.п.), то <math>M(I) = 0</math>. Алгоритм называется псевдополиномиальным, если он имеет оценку трудоемкости <math>T_{max}(I) = O(p(|I|, M(I)))</math>, где <math>p(\cdot, \cdot)</math> -- некоторый полином от двух переменных. | Пусть <math>M(I)</math> -- некоторая функция, задающая значение числового параметра индивидуальной задачи <math>I</math>. Если таких параметров несколько, в качестве <math>M(I)</math> можно взять или максимальное, или среднее значение, а если задача вовсе не имеет числовых параметров (например, раскраска графа, шахматы и т.п.), то <math>M(I) = 0</math>. Алгоритм называется псевдополиномиальным, если он имеет оценку трудоемкости <math>T_{max}(I) = O(p(|I|, M(I)))</math>, где <math>p(\cdot, \cdot)</math> -- некоторый полином от двух переменных. | ||
- | |||
- | [http://en.wikipedia.org/wiki/Pseudo-polynomial_time en-wiki] | ||
=== Сильная NP-полнота. Теорема о связи сильной NP-полноты задачи с существованием псевдополиномиального алгоритма ее решения === | === Сильная NP-полнота. Теорема о связи сильной NP-полноты задачи с существованием псевдополиномиального алгоритма ее решения === | ||
Строка 130: | Строка 120: | ||
'''Полиномиальное сужение''' массовой задачи <math>\Pi</math> -- множество таких индивидуальных задач <math>I</math>, числовые параметры которых не превосходят полинома от длины входа: <math>\Pi_{p(\cdot)} = \{ I \in \Pi | M(I) \leqslant p(|I|) \}</math> | '''Полиномиальное сужение''' массовой задачи <math>\Pi</math> -- множество таких индивидуальных задач <math>I</math>, числовые параметры которых не превосходят полинома от длины входа: <math>\Pi_{p(\cdot)} = \{ I \in \Pi | M(I) \leqslant p(|I|) \}</math> | ||
- | Массовая задача <math>\Pi</math> называется '''сильно NP-полной''', если её полиномиальное сужение является NP-полным. | + | Массовая задача <math>\Pi</math> называется '''сильно NP-полной''', если её полиномиальное сужение является NP-полным. |
* задача выполнимости, задача 3-выполнимости -- совпадают со своими полиномиальными сужениями | * задача выполнимости, задача 3-выполнимости -- совпадают со своими полиномиальными сужениями | ||
- | * задача булевых линейных неравенств | + | * задача булевых линейных неравенств |
- | * задача о целочисленном решении системы линейных уравнений | + | * задача о целочисленном решении системы линейных уравнений |
- | * задача | + | * задача комивояжа |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | === Определение | + | === Определение <math>\varepsilon</math>-приближенного алгоритма и полностью полиномиальной приближенной схемы (ПППС). Связь между существованием ПППС и псевдополиномиальностью === |
'' Методичка, стр. 22-24 '' | '' Методичка, стр. 22-24 '' | ||
Строка 148: | Строка 134: | ||
* <math>\max</math> вообще говоря вполне может быть заменён на <math>\min</math> | * <math>\max</math> вообще говоря вполне может быть заменён на <math>\min</math> | ||
- | Алгоритм <math>A</math> называется '''приближённым алгоритмом''' решения массовой задачи <math>\Pi</math>, если для любой задачи <math>I \in \Pi</math> он находит точку <math>z_A(I) \in S_\Pi(I)</math>, лежащую в области допустимых значений, принимаемую за приближённое решение | + | Алгоритм <math>A</math> называется '''приближённым алгоритмом''' решения массовой задачи <math>\Pi</math>, если для любой задачи <math>I \in \Pi</math> он находит точку <math>z_A(I) \in S_\Pi(I)</math>, лежащую в области допустимых значений, принимаемую за приближённое решение |
- | ''Утверждение'' | + | ''Утверждение'' Если <math>\mathrm{P} \neq \mathrm{NP}</math>, то ни для какой константы <math>C > 0</math> не существует полиномиального приближённого алгоритма решения задачи о рюкзаке с оценкой <math>| \mathrm{Opt}(I) - A(I) | \leqslant C</math> |
- | Приближённый алгоритм <math>A</math> решения массовой задачи <math>\Pi</math> называется ''' <math>\varepsilon</math>-приближённым алгоритмом ''' решения задачи, если <math>\forall I \in \Pi : ~ \left| \frac{\mathrm{Opt}_\Pi(I) - A(I)}{\mathrm{Opt}_\Pi(I)} \right| \leqslant \varepsilon</math> | + | Приближённый алгоритм <math>A</math> решения массовой задачи <math>\Pi</math> называется ''' <math>\varepsilon</math>-приближённым алгоритмом ''' решения задачи, если <math>\forall I \in \Pi : ~ \left| \frac{\mathrm{Opt}_\Pi(I) - A(I)}{\mathrm{Opt}_\Pi(I)} \right| \leqslant \varepsilon</math> |
=== Теорема об отсутствии ПППС для задач оптимизации, соответствующих сильно NP-полным задачам распознавания === | === Теорема об отсутствии ПППС для задач оптимизации, соответствующих сильно NP-полным задачам распознавания === | ||
Строка 170: | Строка 156: | ||
- | '''Утверждение (принцип граничных решений)'''. Если озЛП имеет решение, то найдется такая подматрица <math>A_I</math> матрицы <math>A</math>, что любое решение системы уравнений <math>A_I x = b_I</math> реализует максимум <math> | + | '''Утверждение (принцип граничных решений)'''. Если озЛП имеет решение, то найдется такая подматрица <math>A_I</math> матрицы <math>A</math>, что любое решение системы уравнений <math>A_I x = b_I</math> реализует максимум <math>c(x)</math>. |
'''Алгебраическая сложность''' -- количество арифметических операций. | '''Алгебраическая сложность''' -- количество арифметических операций. | ||
Строка 182: | Строка 168: | ||
Симплекс-метод -- метод решения озЛП. | Симплекс-метод -- метод решения озЛП. | ||
- | Каждое из линейных неравенств в <math>Ax \leqslant b</math> ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным конусом. | + | Каждое из линейных неравенств в <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>W(x) = c</math>, где <math>W(x)</math> — максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость <math>L(c)</math>. Зависимость от <math>c</math> порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку — требуется найти такое наибольшее <math>c</math>, что гиперплоскость <math>L(c)</math> пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его ребрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено. | ||
Строка 188: | Строка 174: | ||
''Методичка, стр. 28-29'' | ''Методичка, стр. 28-29'' | ||
- | <math>\Delta(D) = \max | \det(D_1) | </math>, где <math>D_1</math> | + | <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>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> |
=== Теорема о мере несовместности систем линейных неравенств с целыми коэффициентами === | === Теорема о мере несовместности систем линейных неравенств с целыми коэффициентами === | ||
Строка 213: | Строка 199: | ||
Таким образом получаем, что если система совместна, то эта лемма позволяет локализовать хотбы бы 1 из ее решений | Таким образом получаем, что если система совместна, то эта лемма позволяет локализовать хотбы бы 1 из ее решений | ||
- | Введем функцию невязки в точке 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> -- решение. Если это не так, то | + | Введем функцию невязки в точке 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>. Пересечение этого полупространства с нашей сферой дают полуэлипсоид. Вокруг получившегося полуэлипсоида описываем новую сферу и повторяем алгоритм заново. |
=== Теория двойственности ЛП === | === Теория двойственности ЛП === | ||
Строка 221: | Строка 207: | ||
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой задаче. | Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой задаче. | ||
- | '''Двойственной задачей''' к задаче линейного программирования <math>Ax \leqslant b</math> на максимум <math>\langle c, x\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> |
''Утверждение'' Двойственная задача к двойственной задаче совпадает с прямой задачей линейного программирования. | ''Утверждение'' Двойственная задача к двойственной задаче совпадает с прямой задачей линейного программирования. | ||
Строка 241: | Строка 227: | ||
'''Метод Кармаркара.''' | '''Метод Кармаркара.''' | ||
- | # На основании предыдущего утверждения (см. вопрос о сведении озЛП к однородной системе), есть возможность свести задачу ЛП <math>\max_{x \in \mathbb{R}^n:~Ax \leqslant b} \langle c, x \rangle</math> к поиску решения СЛАУ <math>\hat{P}y = \hat{q | + | # На основании предыдущего утверждения (см. вопрос о сведении озЛП к однородной системе), есть возможность свести задачу ЛП <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>k(x) = \frac{\left[ (\langle p_1, x \rangle)^2 + \dots + (\langle p_K, x \rangle)^2\right]^{N/2}}{x_1 \cdot x_2 \cdot \dots \cdot x_N}</math>, где | # Введем '''функцию Кармаркара''': <math>k(x) = \frac{\left[ (\langle p_1, x \rangle)^2 + \dots + (\langle p_K, x \rangle)^2\right]^{N/2}}{x_1 \cdot x_2 \cdot \dots \cdot x_N}</math>, где | ||
#* <math>N</math> -- число столбцов в <math>P</math> | #* <math>N</math> -- число столбцов в <math>P</math> | ||
#* <math>K</math> -- число строк в <math>P</math> | #* <math>K</math> -- число строк в <math>P</math> | ||
- | #* <math>p_i, ~ i \in [1,K]</math> -- строки матрицы <math>P</math> | + | #* <math>p_i, ~ i \in [1,K]</math> -- строки матрицы <math>P</math> (не <math>\hat P</math>! описание этой матрицы - в доказательстве утверждения 5 в методичке, стр. 37) |
# применяя теорему о мере несовместимости и алгоритм округления можно показать, что для решения достаточно найти такой <math>\hat{x}</math>, для которого <math>k(\hat{x}) \leqslant \frac{1}{3 \left(\Delta(\hat{P})\right)^N}</math> | # применяя теорему о мере несовместимости и алгоритм округления можно показать, что для решения достаточно найти такой <math>\hat{x}</math>, для которого <math>k(\hat{x}) \leqslant \frac{1}{3 \left(\Delta(\hat{P})\right)^N}</math> | ||
# при этом можно так же показать полиномиальный алгоритм поиска данного приближения, который в курсе не рассматривается. | # при этом можно так же показать полиномиальный алгоритм поиска данного приближения, который в курсе не рассматривается. | ||
Строка 258: | Строка 244: | ||
'''Афинная лемма Фаракша.''' | '''Афинная лемма Фаракша.''' | ||
- | Линейное неравентсво <math>\langle c, x\rangle \leqslant d</math> является следствием разрешимой в вещественный переменных ЛН <math>Ax \leqslant b</math>, тогда и только тогда, когда | + | Линейное неравентсво <math>\langle c, x\rangle \leqslant d</math> является следствием разрешимой в вещественный переменных ЛН <math>Ax \leqslant b</math>, тогда и только тогда, когда существует <math>\lambda \in \mathbb{R}^{m}</math>: |
* <math>c = \sum_{i \in M} \lambda_i a_i</math> | * <math>c = \sum_{i \in M} \lambda_i a_i</math> | ||
* <math>d \geqslant \sum_{i \in M}\lambda_ib_i</math> | * <math>d \geqslant \sum_{i \in M}\lambda_ib_i</math> | ||
Строка 267: | Строка 253: | ||
'''Лемма'''. | '''Лемма'''. | ||
- | Система | + | Система динейный неравенсив <math>Ax \leqslant b</math> неразрешима тогда и только тогда, когда разрешима система: |
* <math>\sum_{i \in M}\lambda_i a_i = \overline{0}</math> (нулевой вектор) | * <math>\sum_{i \in M}\lambda_i a_i = \overline{0}</math> (нулевой вектор) | ||
Строка 371: | Строка 357: | ||
''Методичка. стр 60'' | ''Методичка. стр 60'' | ||
- | '''Опр.''' Функция f называется '''разделяемой''' на <math>f_1</math> и <math>f_2</math>, если она представима в виде | + | '''Опр.''' Функция f называется '''разделяемой''' на <math>f_1</math> и <math>f_2</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>f_1</math> и <math>f_2</math> | * она разделяема на <math>f_1</math> и <math>f_2</math> | ||
* <math>f_1</math> монотонно не убывает по последнему аргументу | * <math>f_1</math> монотонно не убывает по последнему аргументу | ||
- | '''Теорема оптимальности для разложимых функций''' | + | '''Теорема оптимальности для разложимых функций''' |
+ | |||
+ | <math> \min_{x,y}(f(x,y)) = \min_x(f_1(x, \min_y(f_2(y)))) </math> | ||
Указанная теорема используется для уменьшения размерности оптимизационных задач и в методе ДП. | Указанная теорема используется для уменьшения размерности оптимизационных задач и в методе ДП. |