Введение

Метод решения задач оптимизации, ретроним, относящийся к телевизионному вещанию. Линейное программирование (ЛП), также называемое линейной оптимизацией, – это метод достижения наилучшего результата (например, максимальной прибыли или минимальных затрат) в математической модели, требования и целевая функция которой представлены линейными соотношениями. Линейное программирование является частным случаем математического программирования (также известного как математическая оптимизация). Более формально, линейное программирование – это техника оптимизации линейной целевой функции при линейных ограничениях в виде равенств и неравенств. Область допустимых решений представляет собой выпуклый политоп, который определяется как пересечение конечного числа полупространств, каждое из которых задается линейным неравенством. Целевая функция является аффинной (линейной) функцией, принимающей действительные значения и определенной на этом политопе. Алгоритм линейного программирования находит точку в политопе, в которой эта функция достигает наибольшего (или наименьшего) значения, если такая точка существует. Линейные программы – это задачи, которые могут быть выражены в стандартной форме как:

Здесь компоненты – это переменные, которые необходимо определить, и – заданные векторы, а – заданная матрица. Функция, значение которой требуется максимизировать (в данном случае), называется целевой функцией. Ограничения и определяют выпуклый политоп, на котором необходимо оптимизировать целевую функцию. Линейное программирование может применяться в различных областях науки. Оно широко используется в математике и, в меньшей степени, в бизнесе, экономике и некоторых инженерных задачах. Отрасли, использующие модели линейного программирования, включают транспорт, энергетику, телекоммуникации и производство. Оно оказалось полезным при моделировании различных типов задач в области планирования, маршрутизации, составления расписаний, назначения и проектирования.

История

Проблема решения системы линейных неравенств уходит корнями, по крайней мере, во времена Фурье, который в 1827 году опубликовал метод их решения, и в честь которого назван метод исключения Фурье — Моцкина. В конце 1930-х годов советский математик Леонид Канторович и американский экономист Василий Леонтьев независимо занялись практическими применениями линейного программирования. Канторович сосредоточился на составлении производственных графиков, а Леонтьев исследовал экономические приложения. Их новаторская работа долгое время оставалась в значительной степени незамеченной. Переломный момент наступил во время Второй мировой войны, когда линейное программирование стало важнейшим инструментом. Оно нашло широкое применение в решении сложных задач военного времени, включая транспортную логистику, планирование и распределение ресурсов. Линейное программирование оказалось незаменимым в оптимизации этих процессов с учетом критических ограничений, таких как стоимость и доступность ресурсов. Несмотря на первоначальную малоизвестность, успехи военного времени вывели линейное программирование на передний план. После Второй мировой войны метод получил широкое признание и стал краеугольным камнем в различных областях, от исследования операций до экономики. Недооцененный вклад Канторовича и Леонтьева в конце 1930-х годов в конечном итоге заложил основу для более широкого принятия и использования линейного программирования в оптимизации процессов принятия решений. Работа Канторовича первоначально игнорировалась в СССР. Примерно в то же время, что и Канторович, голландско-американский экономист Т. К. Купманс сформулировал классические экономические проблемы в виде задач линейного программирования. Канторович и Купманс впоследствии разделили Нобелевскую премию по экономическим наукам в 1975 году. Хичкок умер в 1957 году, и Нобелевская премия не присуждается посмертно. С 1946 по 1947 год Джордж Б. Данциг самостоятельно разработал общую формулировку линейного программирования для использования при планировании задач в ВВС США. В 1947 году Данциг также изобрел симплекс-метод, который впервые эффективно решал задачу линейного программирования в большинстве случаев. Однако более значительный теоретический и практический прорыв в этой области произошел в 1984 году, когда Нарендра Кармаркар представил новый метод внутренней точки для решения задач линейного программирования.

Применение

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

Примеры

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

Дополнительная слабая работа

Можно получить оптимальное решение двойственной задачи, зная только оптимальное решение прямой задачи, используя теорему о дополнительной слабимости. Теорема утверждает:

Предположим, что x = (x1, x2, ..., xn) является допустимым решением прямой задачи, а y = (y1, y2, ..., ym) – допустимым решением двойственной задачи. Пусть (w1, w2, ..., wm) обозначают соответствующие переменные двойственности прямой задачи, а (z1, z2, ..., zn) – соответствующие переменные двойственности двойственной задачи. Тогда x и y являются оптимальными решениями своих соответствующих задач тогда и только тогда, когда
xj zj = 0 для j = 1, 2, ..., n, и
wi yi = 0 для i = 1, 2, ..., m.

Таким образом, если i-я переменная двойственности прямой задачи не равна нулю, то i-я переменная двойственной задачи равна нулю. Аналогично, если j-я переменная двойственности двойственной задачи не равна нулю, то j-я переменная прямой задачи равна нулю. Это необходимое условие оптимальности выражает довольно простой экономический принцип. В стандартной форме (при максимизации), если в ограниченном ресурсе прямой задачи есть избыток (то есть есть "остатки"), то дополнительные единицы этого ресурса не имеют ценности. Аналогично, если в ограничении неотрицательности двойственной (теневой) цены есть избыток, то есть цена не равна нулю, то предложение этого ресурса ограничено (нет "остатков").

Существование оптимальных решений

Геометрически, линейные ограничения определяют допустимую область, которая является выпуклым политопом. Линейная функция является выпуклой функцией, что означает, что любой локальный минимум является глобальным минимумом; аналогично, линейная функция является вогнутой функцией, что означает, что любой локальный максимум является глобальным максимумом. Оптимальное решение не всегда существует по двум причинам. Во-первых, если ограничения несовместны, то допустимого решения не существует: например, ограничения x ≥ 2 и x ≤ 1 не могут быть выполнены одновременно; в этом случае говорят, что задача линейного программирования не имеет решений. Во-вторых, когда политоп неограничен в направлении градиента целевой функции (где градиент целевой функции является вектором коэффициентов целевой функции), то оптимальное значение не достигается, поскольку всегда можно улучшить любое конечное значение целевой функции.

Оптимальные вершины (и лучи) полиедров

В противном случае, если существует допустимое решение и множество ограничений ограничено, то оптимальное значение всегда достигается на границе множества ограничений, согласно принципу максимума для выпуклых функций (или, альтернативно, принципу минимума для вогнутых функций), поскольку линейные функции являются одновременно выпуклыми и вогнутыми. Однако некоторые задачи имеют различные оптимальные решения; например, задача поиска допустимого решения системы линейных неравенств является задачей линейного программирования, в которой целевая функция представляет собой нулевую функцию (то есть постоянную функцию, принимающую значение ноль во всех точках). Для этой задачи на допустимость с нулевой целевой функцией, если существуют два различных решения, то любая выпуклая комбинация этих решений также является решением. Вершины политопа также называются базисными допустимыми решениями. Причина такого выбора названия заключается в следующем. Пусть d обозначает число переменных. Тогда фундаментальная теорема о линейных неравенствах утверждает (для допустимых задач), что для каждой вершины x* допустимой области LP существует набор из d (или меньше) неравенств-ограничений LP, при этом, если рассматривать эти d ограничений как равенства, то единственным решением будет x*. Таким образом, мы можем изучать эти вершины, рассматривая определенные подмножества множества всех ограничений (дискретное множество), а не континуум решений LP. Этот принцип лежит в основе симплекс-метода для решения задач линейного программирования.

Симплексный алгоритм Данцига

Симплексный алгоритм, разработанный Джорджем Данцигом в 1947 году, решает задачи линейного программирования, строя допустимое решение в вершине политопа и затем перемещаясь по пути вдоль рёбер политопа к вершинам с неубывающими значениями целевой функции, пока достоверно не будет достигнут оптимум. Во многих практических задачах наблюдается "застой": выполняется множество итераций без улучшения значения целевой функции. В редких практических задачах обычные варианты симплексного алгоритма могут фактически приходить к "циклу", что аналогично его поведению на практических задачах. Однако симплексный алгоритм демонстрирует плохие показатели в худшем случае: Кли и Минти построили семейство задач линейного программирования, для которых симплексный метод требует количества шагов, экспоненциально зависящего от размера задачи. Фактически, некоторое время было неизвестно, может ли задача линейного программирования быть решена за полиномиальное время, то есть относится к классу сложности P.

Алгоритм перекрестного счета

Как и симплексный алгоритм Данцига, алгоритм criss-cross является алгоритмом обмена базисами, переходящим от одного базиса к другому. Однако алгоритму criss-cross не требуется поддерживать допустимость, он может переходить от допустимого базиса к недопустимому. Алгоритм criss-cross не обладает полиномиальной временной сложностью для линейного программирования. В худшем случае оба алгоритма просматривают все 2D вершины (возмущенного) куба размерности D, куба Кли–Минти.

Внутренняя точка

В отличие от симплекс-алгоритма, который находит оптимальное решение, последовательно переходя от вершины к вершине на многограннике, методы внутренней точки движутся внутри допустимой области.

Эллипсоидный алгоритм, следуя Хачияну

Это первый алгоритм с наихудшим полиномиальным временем работы, когда-либо найденный для линейного программирования. Для решения задачи с n переменными, которая может быть закодирована в L входных битах, этот алгоритм выполняется за время . С момента открытия Кармаркара было предложено и проанализировано множество методов внутренних точек.

Алгоритм Вайдьи 87

В 1987 году Вайдья предложил алгоритм, работающий за время .

Алгоритм 89 Вайдьи

В 1989 году Вайдья разработал алгоритм, работающий за время. Формально, алгоритм выполняет арифметических операций в худшем случае, где — количество ограничений, — количество переменных, а — количество бит.

Алгоритмы времени сплошности ввода

В 2015 году Ли и Сидфорд показали, что линейное программирование может быть решено за время, где обозначает количество ненулевых элементов, однако в худшем случае время решения остаётся равным .

Алгоритм времени умножения текущей матрицы

В 2019 году Коэн, Ли и Сонг улучшили время работы до , где – показатель степени умножения матриц, а – двойной показатель степени умножения матриц. определяется (приблизительно) как наибольшее число, такое, что матрицу размера *n* x *n* можно умножить на матрицу размера *n* x *n* за время . В последующей работе Ли, Сон и Чжан воспроизвели тот же результат другим методом. Эти два алгоритма остаются оптимальными при и Результат, полученный Цзян, Сонг, Вайнштейном и Чжан, улучшил до .

Сравнение методов внутренней точки и алгоритмов симплекса

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