Редактирование: Методы Оптимизации, Теормин
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 41 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 25: | Строка 25: | ||
* <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> |
Строка 190: | Строка 190: | ||
<math>\Delta(D) = \max | \det(D_1) | </math>, где <math>D_1</math> — квадратная подматрица <math>D</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> |
=== Теорема о мере несовместности систем линейных неравенств с целыми коэффициентами === | === Теорема о мере несовместности систем линейных неравенств с целыми коэффициентами === | ||
Строка 258: | Строка 258: | ||
'''Афинная лемма Фаракша.''' | '''Афинная лемма Фаракша.''' | ||
- | Линейное неравентсво <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> |