Редактирование: Методы Оптимизации, Теормин
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 41 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 241: | Строка 241: | ||
'''Метод Кармаркара.''' | '''Метод Кармаркара.''' | ||
- | # На основании предыдущего утверждения (см. вопрос о сведении озЛП к однородной системе), есть возможность свести задачу ЛП <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> | ||
# при этом можно так же показать полиномиальный алгоритм поиска данного приближения, который в курсе не рассматривается. | # при этом можно так же показать полиномиальный алгоритм поиска данного приближения, который в курсе не рассматривается. |