Линейное программирование: симплекс-метод и двойственность

Линейное программирование максимизирует (c^T x) при (Ax leq b), (x geq 0), используя матрицы пятой статьи и симплекс-алгоритм.

Двойственность связывает прямую и двойственную задачи.

Стандартная форма и симплекс-таблица

Задача (max c^T x), (Ax = b), (x geq 0) с базисом (B), не базисными переменными. Симплекс-шаг: выбор ведущего столбца по (c_B^T B^{-1} A_j - c_j > 0), строки по минимальному ( heta = min frac{b_i}{a_{i,sigma}}). Циклы устраняются искусственными переменными.

Переход от одной базисной вершины к соседней в симплекс-таблице Симплекс-таблица и поворот . Схема показывает алгоритм.

Двойственная задача и комплементарная слагаемость

Двойственная (min b^T y), (A^T y geq c), (y geq 0). Сильная двойственность: оптимальные (x^*, y^*) удовлетворяют (x^T A^T y^* = b^T y^* = c^T x^*). Комплементарность (x_i^* y_i^{*'} = 0) для KKT-условий нелинейной оптимизации.

Алгоритмы содержатся в пособиях по матрицам https://joker150491.narod.ru/Kryakvin_V.D._Lineynaya_algebra._Posobie_k_resheniyu_zadach.pdf. Лекции https://intuit.ru/studies/courses/1173/305/lecture/7575.

Применения: транспортная задача, планирование

Транспортная задача: минимизация перевозок с ограничениями мощностей. Метод потенциалов, разбиение циклов. Линейная регрессия, портфельные оптимизации.

Многогранник (Ax leq b), (x geq 0) с оптимальной вершиной Многогранник линейного программирования . График показывает симплекс.