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

Матричная алгебра применяется не только для поиска точных решений уравнений, но и для поиска наилучших решений в условиях жестких ограничений. Этот раздел прикладной математики называется линейным программированием (ЛП). Разработанная советским математиком Леонидом Канторовичем (лауреатом Нобелевской премии по экономике) и американцем Джорджем Данцигом, теория ЛП стала революционным инструментом логистики, производственного планирования и распределения ресурсов. Математически задача ЛП заключается в максимизации или минимизации линейной целевой функции при условии, что переменные удовлетворяют системе линейных неравенств. Геометрия этой задачи и алгоритм ее решения (симплекс-метод) опираются на фундаментальные концепции выпуклого анализа и линейных подпространств.

Выпуклые многогранники и область допустимых решений

Каждое линейное неравенство в задаче (например, ограничение на количество доступного сырья) геометрически отсекает ровно половину n-мерного пространства (полупространство). Пересечение всех этих полупространств формирует область допустимых решений. С точки зрения геометрии, эта область всегда представляет собой выпуклый многогранник (политоп). Целевая функция, которую мы хотим максимизировать (например, общая прибыль), задает семейство параллельных гиперплоскостей (линий уровня). Фундаментальная теорема линейного программирования гласит: если задача имеет оптимальное решение, то оно гарантированно находится как минимум в одной из вершин (крайних точек) этого многогранника. Нам не нужно исследовать бесконечное множество точек внутри многогранника; достаточно перебрать лишь его вершины.

Каноническая форма и базисные решения

Для применения алгоритмов линейной алгебры система неравенств должна быть преобразована в систему строгих уравнений. Это достигается введением фиктивных (балансовых) неотрицательных переменных, которые превращают неравенства типа «меньше или равно» в строгие равенства. В результате мы получаем недоопределенную систему линейных уравнений AX = B, где матрица A имеет размер m на n (широкая матрица, уравнений меньше, чем переменных). Вершины многогранника алгебраически соответствуют так называемым базисным допустимым решениям. Чтобы получить такое решение, мы приравниваем n - m свободных переменных к нулю, а оставшиеся m базисных переменных вычисляем путем решения квадратной системы, где матрицей выступает невырожденный минор матрицы A. Если полученные значения неотрицательны, мы нашли настоящую вершину политопа.

Алгоритм симплекс-метода: скольжение по ребрам

Симплекс-метод Джорджа Данцига не перебирает все вершины многогранника вслепую (их число может расти экспоненциально). Алгоритм стартует из любой допустимой вершины и оценивает так называемые приведенные стоимости соседних вершин. Используя аппарат элементарных преобразований строк (подобно методу Гаусса или Жордана-Гаусса), алгоритм алгебраически переходит (делает шаг пивотирования) в ту соседнюю вершину, которая улучшает значение целевой функции. Геометрически симплекс-метод представляет собой скольжение по ребрам многогранника от одной вершины к другой в направлении градиента целевой функции. Как только алгоритм попадает в вершину, из которой ни одно ребро не ведет к улучшению, теорема гарантирует, что мы достигли глобального оптимума.

Теория двойственности в линейном программировании

Одной из самых красивых алгебраических структур ЛП является теория двойственности. Каждой прямой задаче максимизации жестко соответствует двойственная (сопряженная) задача минимизации. При построении двойственной задачи столбцы исходной матрицы A становятся строками (используется транспонированная матрица A^T), коэффициенты целевой функции меняются местами с вектором свободных членов B, а знаки неравенств разворачиваются. Сильная теорема двойственности утверждает потрясающий факт: если обе задачи имеют допустимые решения, то их оптимальные значения (максимум прямой и минимум двойственной) в точности равны друг другу. Двойственные переменные имеют огромный экономический смысл — они показывают теневые цены (скрытую ценность) каждого ограничивающего ресурса на производстве.

Оценить