Все формулы РФ

Математика / Численная оптимизация

Симплекс-метод: правило минимального отношения

Симплекс-метод: правило минимального отношения даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.

Опубликовано: Обновлено:

Оптимизация и исследование операцийСтраницы с задачами и решениямиЕсть историческая справкаДиагностика условий

Формула

$$\theta^*=\min_{i:a_{ij}>0}\frac{b_i}{a_{ij}}$$
Схема Сохранение допустимости базиса
Сохранение допустимости базисаСохранение допустимости базиса8−2θ9−3θ0-41-0.7522.535.7549θбазисные x

При θ=3 вторая базисная переменная достигает нуля; дальнейший рост нарушает неотрицательность.

Обозначения

$x$
аргумент, состояние или вектор данных конкретной задачи, единицы исходной модели
$n,k,i,j$
целые индексы узла, шага либо компоненты, безразмерные
$ε / err$
допуск или оценка вычислительной ошибки, если она используется, единицы результата

Условия применения

Правило относится к конкретной знаковой конвенции симплекс-таблицы и столбцу входящей переменной. Делите b_i только для строк с a_ij>0 и допустимым b_i; если таких строк нет, задача не ограничена в выбранном направлении, а не имеет нулевого отношения.

Ограничения

Результат нельзя переносить на похожую по словам, но другую модель. Оценка ошибки может быть локальной, а сходимость — зависеть от гладкости, обусловленности или начальных данных. Округление, вырождение матрицы и нарушения ограничений меняют смысл вычисления. Число после знака равенства не заменяет проверку: следует показать, какая именно формула применена, в каких единицах получен ответ и почему условия выполнены. Для информационных величин особенно важно не смешивать биты и натуральные единицы.

Подробное объяснение

Когда входящая переменная увеличивается, базисные переменные меняются по строкам таблицы. Только положительный коэффициент в опорном столбце ограничивает рост и может довести запас b_i до нуля.

Минимальное отношение выбирает первую строку, которая достигнет нуля. Благодаря этому следующий базис остаётся допустимым: ни одна переменная не становится отрицательной.

Если в подходящих строках нет положительных коэффициентов, направления не ограничены и задача может быть неограниченной по цели. Нельзя подменять это случаем большого, но конечного отношения.

Правило говорит, какая строка выходит после выбора входящей переменной. Оно не заменяет правило выбора самого столбца и требует отдельной обработки равных отношений и вырождения.

В первой таблице увеличение входящей переменной на θ уменьшает первую базисную переменную до 8−2θ и вторую до 9−3θ. При θ=3 вторая становится нулём, а первая остаётся 2; при θ=4 вторая уже была бы отрицательной. Именно это подтверждает выбор отношения 9/3.

Как пользоваться формулой

  1. Выпишите \theta^*=\min_{i:a_{ij}>0}\frac{b_i}{a_{ij}} и отметьте искомую величину; не заменяйте её одноимённым параметром из другой модели.
  2. Подготовьте данные в требуемой форме: проверьте индексы, знак, область аргумента, нормировку либо размерность.
  3. Выполните первое задание по действиям и сохраните промежуточные значения каждого коэффициента, отношения или суммы.
  4. Проверьте результат естественным способом: симметрией, точным частным случаем, невязкой или исходным ограничением.
  5. Разберите второе задание: изменённые данные показывают границу применимости и предупреждают типичную ошибку метода.

Историческая справка

Джордж Данциг разработал симплекс-метод в 1947 году для задач линейного программирования, возникших в военном планировании и логистике. Табличная форма позволила вручную переходить между базисными допустимыми решениями. Правило минимального отношения сохраняет неотрицательность базисных переменных при увеличении входящей переменной. Позднее теория показала, что у метода бывают экспоненциально длинные худшие случаи, однако на множестве практических задач он остаётся важным ориентиром и компонентом оптимизационных систем.

Данциг представил симплекс-метод в 1947 году в RAND Corporation; его книга «Linear Programming and Extensions» 1963 года стала подробным источником табличной техники. Метод возник из плановых задач, где переменные естественно имели ограничения неотрицательности.

Историческая линия формулы

Симплекс-метод обоснованно связывают с Джорджем Данцигом и 1947 годом. Правило отношения — часть табличного алгоритма и применимо лишь после правильного выбора направления и при положительных коэффициентах в соответствующем столбце. Источник в карточке указан для различения исторического имени, публикации и современной вычислительной формы; эти уровни не следует смешивать.

Пример

В столбце входящей переменной коэффициенты равны 2 и 3, правые части — 8 и 9. Отношения 8/2=4 и 9/3=3; минимум 3, значит выходит вторая базисная переменная. В первой таблице увеличение входящей переменной на θ уменьшает первую базисную переменную до 8−2θ и вторую до 9−3θ. При θ=3 вторая становится нулём, а первая остаётся 2; при θ=4 вторая уже была бы отрицательной. Именно это подтверждает выбор отношения 9/3. Когда входящая переменная увеличивается, базисные переменные меняются по строкам таблицы. Только положительный коэффициент в опорном столбце ограничивает рост и может довести запас b_i до нуля.

Частая ошибка

Нельзя делить b_i на отрицательный коэффициент входящего столбца. Нельзя выбирать максимальное, а не минимальное положительное отношение. При равенстве отношений возможен вырожденный шаг, который требует антициклического правила. И отсутствие положительных коэффициентов означает неограниченность, а не «ошибку деления». В разборе «Симплекс-метод: правило минимального отношения» проверяют именно обозначения и условия данной записи.

Практика

Задачи с решением

Минимальное отношение в двух строках

Условие. Для b=(10;12), a=(5;2) примените правило отношений.

Решение. 10/5=2 и 12/2=6. Минимум 2 достигается в первой строке.

Ответ. Выходит первая строка; θ*=2.

Строка с неположительным коэффициентом

Условие. Объясните строку с a_ij=−1.

Решение. Минимум берут только по a_ij>0: при увеличении входящей переменной эта строка не ограничивает допустимое θ в принятой табличной записи.

Ответ. Строка не участвует в минимуме.

Дополнительные источники

  • https://math.mit.edu/~shor/18.310/lpnotes310.pdf
  • https://mat.tepper.cmu.edu/classes/QUANT/notes/node62.html

Связанные формулы

Математика

Отражение в методе Нелдера—Мида

$x_r=\bar x+\alpha(\bar x-x_w),\quad\alpha=1$

Отражение в методе Нелдера—Мида даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.

Математика

Обновление BFGS для обратной матрицы Гессе

$H_{k+1}=(I-\rho sy^T)H_k(I-\rho ys^T)+\rho ss^T,\quad\rho=(y^Ts)^{-1}$

Обновление BFGS для обратной матрицы Гессе даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.

Математика

Условия Каруша—Куна—Таккера: комплементарная нежёсткость

$\lambda_i g_i(x)=0,\quad\lambda_i\ge0,\quad g_i(x)\le0$

Условия Каруша—Куна—Таккера: дополнительная нежёсткость даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.