Линейное программирование — Оптимизация линейных целевых функций при линейных ограничениях
- Автор метода
- George B. Dantzig
- Год
- 1947
- Тип
- Mathematical programming / continuous optimization
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Линейное программирование (ЛП), пионером которого был Джордж Б. Данциг в 1947 году, представляет собой математический метод нахождения наилучшего значения линейной целевой функции — например, минимальной стоимости или максимальной прибыли — при заданном наборе линейных неравенств и равенств.
Это фундаментальный метод исследования операций, лежащий в основе планирования производства, распределения ресурсов, логистики, задач о диете и бесчисленного множества других сценариев принятия решений в инженерии, экономике и естественных науках.
Интуиция метода
Представьте, что вы управляете небольшой фабрикой, производящей два продукта. Каждый продукт приносит определенную прибыль, но его производство потребляет ограниченные сырьевые материалы и машинное время. Линейное программирование находит точное соотношение продуктов, которое позволяет извлечь максимальную прибыль из ваших фиксированных ресурсов — не нарушая никаких физических или контрактных ограничений. 'Линейная' часть означает, что прибыль и потребление ресурсов масштабируются прямо пропорционально количеству производимой продукции. Допустимые варианты образуют многоугольник (в двух измерениях) или многогранник (в более высоких измерениях), и оптимальное решение всегда находится в одной из его вершин.
История
Систематическое развитие линейного программирования началось в 1947 году, когда Джордж Б. Данциг, работавший в ВВС США, изобрел симплекс-алгоритм для автоматизации планирования военной логистики. Данциг опубликовал основополагающую теорию в своей монографии 1963 года, которая остается каноническим источником. Независимая и параллельная работа Леонида Канторовича в Советском Союзе (1939) касалась планирования производства с использованием схожих математических идей, и Канторович был удостоен Нобелевской премии по экономике в 1975 году отчасти за этот вклад. Теоретический вопрос о полиномиальной разрешимости был решен методом эллипсоидов Хачияна (1979), а затем методом внутренней точки Кармаркара (1984), который оказался практически быстрым для крупномасштабных задач. Сегодня коммерческие и открытые решатели ЛП встроены в системы планирования ресурсов предприятия, составления расписаний авиакомпаний и энергетические системы по всему миру.
Когда применять
Линейное программирование уместно всякий раз, когда вам нужно оптимизировать величину, которая линейно зависит от набора переменных решения, и все ограничения также линейны. Оно не требует предположений о распределении и минимального размера выборки — это детерминированная математическая модель, а не статистический оценщик. Метод применим, когда переменные решения являются непрерывными (дробные значения имеют смысл); если переменные должны быть целыми числами или бинарными, вместо этого требуется целочисленное программирование. ЛП широко используется в планировании производства, логистике цепочек поставок, задачах о диете и смешивании, оптимизации финансовых портфелей, транспортных задачах и задачах назначения, а также в диспетчеризации энергетики.
Ограничения и замечания
- Требование линейности: если целевая функция или какое-либо ограничение нелинейны, модель ЛП сформулирована некорректно, и решение может быть неверным или недопустимым.
- Только непрерывные переменные: когда переменные решения должны принимать целочисленные или бинарные значения, релаксация ЛП дает нижнюю границу, но не допустимое решение; вместо этого следует использовать целочисленное программирование.
- Детерминированность: ЛП не моделирует неопределенность параметров; стохастическое программирование или робастная оптимизация необходимы, когда данные неопределенны.
- Вырожденность и цикличность: в редких случаях симплекс-метод может зацикливаться на вырожденных базисах без сходимости, хотя правила предотвращения цикличности (например, правило Блэнда) решают эту проблему.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Гарантированный глобальный оптимум: поскольку допустимая область является выпуклым многогранником, любой локальный оптимум также является глобальным оптимумом, без риска застрять в субоптимальном решении.
- Высокая масштабируемость: современные решатели (HiGHS, Gurobi, CPLEX) обрабатывают модели с миллионами переменных и ограничений за секунды.
- Богатая информация после решения: теневые цены и диапазоны чувствительности предоставляют действенные сведения о ценности ресурсов и устойчивости решения без дополнительных запусков.
- Отсутствие предположений о распределении: ЛП — это чисто алгебраическая модель, поэтому она не требует нормальности или каких-либо статистических свойств данных.
Применение
- Планирование производства: нахождение оптимального производственного плана, максимизирующего прибыль при соблюдении ограничений по мощности оборудования и сырью.
- Логистика цепочек поставок и транспортировка: минимизация транспортных расходов по сети складов и клиентов.
- Задачи о диете и смешивании: выбор количеств ингредиентов, удовлетворяющих требованиям к питательности при минимальной стоимости.
- Оптимизация финансовых портфелей: распределение капитала между активами для максимизации ожидаемой доходности при соблюдении ограничений по риску и нормативных требований.
- Диспетчеризация энергетики и планирование энергосистем: минимизация затрат на топливо при удовлетворении спроса на электроэнергию и ограничений мощности генераторов.
- Планирование персонала и рабочей силы: назначение смен работникам для покрытия спроса при минимальных затратах на рабочую силу.
Как это работает
Как это работает
Реальная задача принятия решений переводится в математические символы. Вы определяете переменные решения (величины, которые вы можете контролировать), записываете целевую функцию (что вы хотите максимизировать или минимизировать) как линейную комбинацию этих переменных, и записываете каждое ограничение — лимиты ресурсов, пределы мощностей, требования к спросу — как линейное неравенство или равенство. Корректно сформулированная задача ЛП имеет четкую цель, явные границы переменных и все структурные ограничения, выраженные линейно.
Модель приводится к канонической или стандартной форме, которую может обработать решатель. Неравенства преобразуются в равенства путем введения неотрицательных переменных дополнения (slack) или избытка (surplus), а любая неограниченная переменная заменяется разностью двух неотрицательных переменных. Этот механический шаг создает таблицу или матричное представление, на котором работает алгоритм, и не изменяет задачу — он лишь преобразует ее для вычислений.
Решатель ищет оптимальную вершину в допустимом многограннике. Классический симплекс-метод перемещается от вершины к вершине вдоль ребер многогранника, всегда улучшая (или сохраняя) целевую функцию, пока не существует соседней вершины с лучшим значением. Методы внутренней точки (барьерные) вместо этого проходят через внутреннюю часть допустимой области вдоль центрального пути, что особенно эффективно для очень больших моделей. Обе группы методов гарантированно находят глобальный оптимум, когда он существует, поскольку допустимая область является выпуклой.
Решатель возвращает оптимальные значения переменных решения и оптимальное значение целевой функции, а также двойственные переменные (теневые цены) и диапазоны чувствительности. Теневые цены количественно определяют, насколько улучшится целевая функция, если бы связывающее ограничение было ослаблено на единицу — напрямую указывая лицу, принимающему решение, где дополнительные ресурсы были бы наиболее ценными. Анализ чувствительности определяет, насколько может измениться коэффициент затрат или значение правой части, прежде чем текущий базис перестанет быть оптимальным.
Частые ошибки
- Применение ЛП, когда ограничения или целевая функция нелинейны — решение будет неверным, или решатель отклонит модель.
- Игнорирование требований целочисленности: округление непрерывного решения ЛП до целых чисел в общем случае не дает допустимого или оптимального целочисленного решения; вместо этого используйте целочисленное программирование.
- Недопустимые или неограниченные модели: если допустимая область пуста (противоречивые ограничения) или целевая функция неограничена (отсутствуют ограничивающие ограничения), решатель сообщит об ошибке — всегда проверяйте структуру модели перед запуском.
- Рассмотрение результатов ЛП как рекомендации без анализа чувствительности: решение, которое технически является оптимальным, может находиться на очень тонкой грани, где небольшое изменение данных меняет рекомендацию — диапазоны чувствительности всегда следует проверять.
Часто задаваемые вопросы
Что делает задачу 'линейной' для целей ЛП?
И целевая функция, и каждое ограничение должны быть линейными — это означает, что каждый член представляет собой константу, умноженную на одну переменную решения, без произведений переменных, без степеней и без нелинейных функций. Если хотя бы одно ограничение или целевая функция включает, скажем, x, умноженное на y, или x в квадрате, стандартное ЛП больше не применимо, и требуется решатель нелинейного или квадратичного программирования.
Почему оптимальное решение всегда находится в углу допустимой области?
Допустимая область, определяемая линейными ограничениями, является выпуклым многогранником (или политопом). Линейная целевая функция сама по себе является линейной, поэтому ее нельзя 'притянуть' к внутренней части выпуклого множества — она всегда достигает своего экстремального значения на границе, и в частности в вершине (угловой точке). Это геометрическое понимание лежит в основе стратегии симплекс-метода, основанной на перемещении от вершины к вершине.
Когда следует использовать целочисленное программирование вместо ЛП?
Всякий раз, когда одна или несколько переменных решения должны принимать целочисленные или бинарные (0/1) значения — например, открывать ли предприятие (да/нет), сколько грузовиков отправлять (целые числа) или какие элементы включить в выборку. Простое решение задачи ЛП и округление непрерывного решения не является надежным: округленные решения могут быть недопустимыми или далекими от оптимальных. Целочисленное программирование корректно обрабатывает целочисленность, но требует больших вычислительных затрат.
Что означают теневые цены?
Теневая цена (двойственная переменная) для связывающего ограничения указывает, насколько улучшится оптимальное значение целевой функции, если бы правая часть этого ограничения была ослаблена на единицу, при условии, что все остальное остается неизменным. Например, теневая цена 3 для ограничения по рабочим часам означает, что добавление одного дополнительного часа работы улучшит целевую функцию на 3 единицы. Ограничения, которые не являются связывающими, имеют теневую цену ноль — они не ограничивают текущий оптимум.
Похожие методы
Источники
Dantzig, G.B. (1963). Linear Programming and Extensions. Princeton University Press.
ISBN: 9780691059136Скопировано.Vanderbei, R.J. (2014). Linear Programming: Foundations and Extensions. Springer.
Открыть ссылку DOIСкопировано.