Линейное программирование - Linear programming
Линейное программирование ( LP , которая также называется линейной оптимизацией ) является методом для достижения наилучшего результата (например, максимальная прибыли или низкой стоимости) в математической модели , требование которой представлена линейными соотношениями . Линейное программирование - это частный случай математического программирования (также известного как математическая оптимизация ).
Более формально, линейное программирование представляет собой метод для оптимизации в виде линейной целевой функции , при условии линейного равенства и линейных неравенств ограничений . Его допустимая область представляет собой выпуклый многогранник , который представляет собой множество, определенное как пересечение конечного числа полупространств , каждое из которых определяется линейным неравенством. Его целевая функция является реальным значной аффинной (линейная) функция , определенная на этом многогранника. Алгоритм линейного программирования находит точку в многограннике, в которой эта функция имеет наименьшее (или наибольшее) значение, если такая точка существует.
Линейные программы - это задачи, которые в канонической форме можно выразить как
При этом компоненты х являются переменными, подлежащими определению, с и б приведены векторы (с указанием , что коэффициенты C используются в качестве матрицы однорядной с целью формирования матрицы продукта), а заданная матрица . Функция, значение которой должно быть максимальное или минимальное ( в данном случае) называется целевой функцией . Неравенства A x ≤ b и x ≥ 0 являются ограничениями, которые задают выпуклый многогранник, по которому должна быть оптимизирована целевая функция. В этом контексте два вектора сопоставимы, если они имеют одинаковые размеры. Если каждая запись в первом меньше или равна соответствующей записи во втором, то можно сказать, что первый вектор меньше или равен второму вектору.
Линейное программирование может применяться в различных областях обучения. Он широко используется в математике и, в меньшей степени, в бизнесе, экономике и для некоторых инженерных задач. Отрасли, в которых используются модели линейного программирования, включают транспорт, энергетику, телекоммуникации и производство. Она оказалась полезной при моделировании различных типов проблем планирования , маршрутизации , планирования , присвоения и дизайна.
История
Проблема решения системы линейных неравенств восходит, по крайней мере, к Фурье , который в 1827 г. опубликовал метод их решения и в честь которого назван метод исключения Фурье – Моцкина .
В 1939 г. постановка задачи линейного программирования, эквивалентная общей задаче линейного программирования, была дана советским математиком и экономистом Леонидом Канторовичем , который также предложил метод ее решения. Это , как он развивается, во время Второй мировой войны , к расходам план и прибыль , с тем чтобы сократить расходы на армию и увеличить потери , наложенные на противника. Первоначально в СССР творчеству Канторовича не уделялось должного внимания . Примерно в то же время, что и Канторович, американский экономист нидерландского происхождения Т.К. Купманс сформулировал классические экономические проблемы в виде линейных программ. Позднее Канторович и Купманс разделили Нобелевскую премию по экономике 1975 года . В 1941 году Фрэнк Лорен Хичкок также сформулировал транспортные задачи в виде линейных программ и дал решение, очень похожее на более поздний симплекс-метод . Хичкок умер в 1957 году, и Нобелевская премия не присуждена посмертно.
В течение 1946–1947 годов Джордж Б. Данциг независимо разработал общую формулировку линейного программирования для использования при решении задач планирования в ВВС США. В 1947 году Данциг также изобрел симплексный метод, который впервые эффективно решал проблему линейного программирования в большинстве случаев. Когда Данциг организовал встречу с Джоном фон Нейманом, чтобы обсудить свой симплекс-метод, Нойман сразу же высказал гипотезу о теории двойственности , осознав, что проблема, над которой он работал в теории игр, эквивалентна. Данциг представил формальное доказательство в неопубликованном отчете «Теорема о линейных неравенствах» 5 января 1948 года. Работа Данцига была обнародована в 1951 году. В послевоенные годы многие отрасли промышленности применяли ее в своем ежедневном планировании.
Первоначальный пример Данцига заключался в том, чтобы найти лучшее назначение из 70 человек на 70 рабочих мест. Вычислительная мощность, необходимая для тестирования всех перестановок, чтобы выбрать лучшее назначение, огромна; количество возможных конфигураций превышает количество частиц в наблюдаемой Вселенной . Однако требуется всего лишь мгновение, чтобы найти оптимальное решение, поставив задачу в виде линейной программы и применив симплексный алгоритм . Теория, лежащая в основе линейного программирования, резко сокращает количество возможных решений, которые необходимо проверить.
Впервые задача линейного программирования была решена за полиномиальное время Леонидом Хачияном в 1979 году, но более крупный теоретический и практический прорыв в этой области произошел в 1984 году, когда Нарендра Кармаркар представил новый метод внутренней точки для решения задач линейного программирования.
Использует
Линейное программирование - широко используемая область оптимизации по нескольким причинам. Многие практические проблемы исследования операций можно выразить как задачи линейного программирования. Некоторые частные случаи линейного программирования, такие как сеть поток проблемы и многопродуктовая потока проблемы , которые считаются важными достаточно породили много исследований на специализированных алгоритмах их решение. Ряд алгоритмов для других типов задач оптимизации работают, решая задачи LP как подзадачи. Исторически идеи линейного программирования вдохновляли многие из центральных концепций теории оптимизации, таких как двойственность, декомпозиция и важность выпуклости и ее обобщений. Точно так же линейное программирование активно использовалось на раннем этапе становления микроэкономики, и в настоящее время оно используется в управлении компаниями, например, в планировании, производстве, транспортировке, технологиях и других вопросах. Хотя современные проблемы управления постоянно меняются, большинство компаний хотели бы максимизировать прибыль и минимизировать затраты с ограниченными ресурсами. Google использует линейное программирование для стабилизации видео на YouTube. Поэтому многие проблемы можно охарактеризовать как задачи линейного программирования.
Стандартная форма
Стандартная форма - это обычная и наиболее интуитивно понятная форма описания задачи линейного программирования. Он состоит из следующих трех частей:
- Линейная функция , чтобы максимизировать
- например
- Ограничения задачи следующего вида
- например
- Неотрицательные переменные
- например
Проблема обычно выражается в матричной форме , а затем становится следующей:
Другие формы, такие как задачи минимизации, проблемы с ограничениями на альтернативные формы, а также проблемы с отрицательными переменными всегда можно переписать в эквивалентную задачу в стандартной форме.
Пример
Предположим, что у фермера есть участок земли, скажем, 1 км 2 , который нужно засеять пшеницей или ячменем, или их комбинацией. У фермера ограниченное количество удобрений, F килограммов, и пестицидов, P килограммов. Каждый квадратный километр пшеницы требует F 1 кг удобрений и Р 1 килограмм пестицида, в то время как каждый квадратный километр ячменя требует F 2 кг удобрений и P 2 кг пестицида. Пусть S 1 будет продажной ценой пшеницы за квадратный километр, а S 2 будет продажной ценой ячменя. Если обозначить площадь земель, засеянных пшеницей и ячменем, через x 1 и x 2 соответственно, то прибыль можно максимизировать, выбрав оптимальные значения для x 1 и x 2 . Эту проблему можно выразить следующей задачей линейного программирования в стандартной форме:
Максимизировать: | (максимизировать доход - доход - это "целевая функция") | |
При условии: | (ограничение на общую площадь) | |
(лимит удобрений) | ||
(ограничение по пестицидам) | ||
(нельзя засаживать отрицательную зону). |
В матричной форме это становится:
- максимизировать
- при условии
Расширенная форма (свободная форма)
Задачи линейного программирования могут быть преобразованы в расширенную форму для применения общей формы симплексного алгоритма . Эта форма вводит неотрицательные переменные запаса, чтобы заменить неравенства равенствами в ограничениях. Затем проблемы можно записать в следующей блочно-матричной форме:
- Максимизировать :
где являются вновь введенной переменной слабиной, являются переменным решением, и переменным будут максимальными.
Пример
Приведенный выше пример преобразуется в следующую расширенную форму:
Максимизировать: (целевая функция) при условии: (расширенное ограничение) (расширенное ограничение) (расширенное ограничение)
где - (неотрицательные) переменные резервов, представляющие в этом примере неиспользованную площадь, количество неиспользованных удобрений и количество неиспользованного пестицида.
В матричной форме это становится:
- Максимизировать :
Двойственность
Каждая задача линейного программирования, называемая основной задачей, может быть преобразована в двойную задачу , которая обеспечивает верхнюю границу оптимального значения прямой задачи. В матричной форме мы можем выразить основную проблему как:
- Максимизировать c T x при условии A x ≤ b , x ≥ 0;
- с соответствующей симметричной двойственной задачей,
- Минимизировать b T y при условии, что A T y ≥ c , y ≥ 0.
Альтернативная первичная формулировка:
- Максимизировать c T x при условии A x ≤ b ;
- с соответствующей несимметричной двойственной задачей,
- Минимизируйте b T y при условии, что A T y = c , y ≥ 0.
Есть две фундаментальные идеи теории двойственности. Во-первых, это тот факт, что (для симметричной дуальной) двойственной к дуальной линейной программе является исходная прямая линейная программа. Кроме того, каждое возможное решение для линейной программы дает оценку оптимального значения целевой функции двойственной программы. Слабая двойственность теорема утверждает , что значение целевой функции в двойственном при любом допустимом решении всегда больше или равно значение целевой функции Первичного в любом возможном решении. В сильные двойственности теорема утверждает , что если первичная имеет оптимальное решение, х * , то сопряженное также имеет оптимальное решение, у * , а с Т х * = Ь Т у * .
Линейная программа также может быть неограниченной или невыполнимой. Теория двойственности говорит нам, что если прямое не ограничено, то двойственное невозможно по слабой теореме двойственности. Точно так же, если двойственное неограничено, тогда прямое должно быть недопустимым. Тем не менее, как двойственное, так и прямое могут быть недопустимыми. См двойной линейной программы для деталей и еще несколько примеров.
Вариации
Дуальности покрытия / упаковки
Покрытие LP представляет собой линейную программу в виде:
- Свернуть: b T y ,
- при условии: A T y ≥ c , y ≥ 0 ,
таким образом, что матрица и векторы Ь и с неотрицательны.
Дуальным к покрытию ЛП является ЛП упаковки , линейная программа вида:
- Максимизировать: c T x ,
- при условии: A x ≤ b , x ≥ 0 ,
таким образом, что матрица и векторы Ь и с неотрицательны.
Примеры
Покрытие и упаковка LP обычно возникают как релаксация линейного программирования комбинаторной задачи и важны при изучении алгоритмов аппроксимации . Так , например, Л. П. релаксации поставленной задачи упаковки , в независимом множестве , и проблема согласований пакуют пластинки. ЛВ релаксаций задачи набор крышки , в задаче вершина крышки , и доминирующий поставленной задачи также покрытие грампластинки.
Нахождение дробной окраски из в графе является еще одним примером сопроводительного LP. В этом случае, есть одно ограничение для каждой вершины графа и одной переменных для каждого независимого множества графа.
Дополнительная расслабленность
Можно получить оптимальное решение двойственной, когда известно только оптимальное решение прямой, используя дополнительную теорему о нерезкости. Теорема гласит:
Предположим, что x = ( x 1 , x 2 , ..., x n ) прямолинейно допустимое, а y = ( y 1 , y 2 , ..., y m ) двойственно допустимое. Пусть ( ж 1 , ж 2 , ..., ш м ) обозначают соответствующую переменные первобытную слабину, и ( г 1 , г 2 , ..., г п ) обозначает соответствующую двойственную переменную слабину. Тогда x и y оптимальны для своих задач тогда и только тогда, когда
- x j z j = 0 для j = 1, 2, ..., n и
- w i y i = 0 для i = 1, 2, ..., m .
Таким образом, если i -я переменная резерва первичного элемента не равна нулю, то i -я переменная дуального элемента равна нулю. Точно так же, если j -я переменная резерва дуального элемента не равна нулю, то j -я переменная простого элемента равна нулю.
Это необходимое условие оптимальности выражает довольно простой экономический принцип. В стандартной форме (при максимизации), если в ограниченном основном ресурсе имеется резерв (т. Е. Есть «остатки»), то дополнительные количества этого ресурса не должны иметь ценности. Точно так же, если есть слабое место в требовании ограничения двойной (теневой) неотрицательности цены, т. Е. Цена не равна нулю, то должны быть дефицитные поставки (без «остатков»).
Теория
Наличие оптимальных решений
Геометрически линейные ограничения определяют допустимую область , которая представляет собой выпуклый многогранник . Линейная функция является выпуклой функцией , которая подразумевает , что каждый локальный минимум является глобальным минимумом ; аналогично линейная функция - это вогнутая функция , что означает, что каждый локальный максимум является глобальным максимумом .
Оптимального решения не существует по двум причинам. Во-первых, если ограничения несовместимы, то допустимого решения не существует: например, ограничения x ≥ 2 и x ≤ 1 не могут быть удовлетворены совместно; в этом случае мы говорим, что ЛП недопустима . Во-вторых, когда многогранник неограничен в направлении градиента целевой функции (где градиент целевой функции является вектором коэффициентов целевой функции), то оптимальное значение не достигается, потому что всегда можно сделать лучше любого конечного значения целевой функции.
Оптимальные вершины (и лучи) многогранников
В противном случае, если допустимое решение существует и если набор ограничений ограничен, то оптимальное значение всегда достигается на границе набора ограничений по принципу максимума для выпуклых функций (альтернативно, по принципу минимума для вогнутых функций ), поскольку линейные функции бывают как выпуклыми, так и вогнутыми. Однако у некоторых проблем есть четкие оптимальные решения; например, проблема поиска допустимого решения системы линейных неравенств представляет собой задачу линейного программирования, в которой целевая функция является нулевой функцией (то есть постоянной функцией, принимающей значение ноль всюду). Для этой проблемы выполнимости с нулевой функцией для ее целевой функции, если есть два различных решения, то каждая выпуклая комбинация решений является решением.
Вершины многогранника также называются базовыми допустимыми решениями . Причина такого выбора имени заключается в следующем. Пусть d обозначает количество переменных. Тогда из фундаментальной теоремы о линейных неравенствах следует (для возможных задач), что для каждой вершины x * допустимой области LP существует набор из d (или меньше) ограничений-неравенств из LP, таких что, когда мы рассматриваем эти d ограничений как равенства, то единственное решение х * . Таким образом, мы можем изучать эти вершины, рассматривая определенные подмножества множества всех ограничений (дискретный набор), а не континуум решений ЛП. Этот принцип лежит в основе симплекс-алгоритма решения линейных программ.
Алгоритмы
Базовые алгоритмы обмена
Симплексный алгоритм Данцига
Симплексный алгоритм , разработанный Джордж Данциг в 1947 году, решает Л.П. проблемы пути построения допустимого решения при вершине многогранника , а затем идет по пути по краям многогранника с вершинами с не не уменьшая значение целевой функции до тех пор , оптимум достигается точно. Во многих практических задачах происходит « срыв »: многие повороты выполняются без увеличения целевой функции. В редких практических задачах обычные версии симплексного алгоритма могут фактически «зацикливаться». Чтобы избежать циклов, исследователи разработали новые правила поворота.
На практике симплексный алгоритм достаточно эффективен и может гарантированно найти глобальный оптимум, если будут приняты определенные меры предосторожности против цикличности . Было доказано, что симплексный алгоритм эффективно решает "случайные" задачи, т.е. за кубическое число шагов, что аналогично его поведению на практических задачах.
Однако симплексный алгоритм имеет плохое поведение в худшем случае: Кли и Минти построили семейство задач линейного программирования, для которых симплекс-метод выполняет ряд шагов, экспоненциально зависящих от размера задачи. На самом деле, в течение некоторого времени не было известно , была ли задача линейного программирования разрешима в полиномиальное время , то есть класс сложности P .
Алгоритм крест-накрест
Подобно симплексному алгоритму Данцига, перекрестный алгоритм представляет собой алгоритм обмена базисами, который вращается между базами. Однако перекрестный алгоритм не обязательно должен поддерживать выполнимость, но может скорее перейти от допустимой основы к недопустимой. Алгоритм крест-накрест не имеет полиномиальный временной сложности для линейного программирования. Оба алгоритма посетить все- D углы (возмущенная) кубу в размерности D , в кубе Кли-Минтите , в худшем случае .
Внутренняя точка
В отличие от симплексного алгоритма, который находит оптимальное решение путем обхода ребер между вершинами на многогранном множестве, методы внутренней точки перемещаются через внутреннюю часть допустимой области.
Алгоритм эллипсоида по Хачияну
Это первый алгоритм с полиномиальным временем наихудшего случая, когда- либо найденный для линейного программирования. Чтобы решить задачу, которая имеет n переменных и может быть закодирована в L входных битов, этот алгоритм работает во времени. Леонид Хачиян решил эту давнюю проблему сложности в 1979 году, введя метод эллипсоидов . У анализа сходимости есть предшественники (действительные числа), в частности итерационные методы, разработанные Наумом З. Шором, и алгоритмы аппроксимации, разработанные Аркадием Немировским и Д. Юдиным.
Проективный алгоритм Кармаркара
Алгоритм Хачияна имел важное значение для установления разрешимости линейных программ за полиномиальное время. Алгоритм не стал прорывом в вычислениях, поскольку симплекс-метод более эффективен для всех семейств линейных программ, кроме специально построенных.
Однако алгоритм Хачияна вдохновил на новые направления исследований в области линейного программирования. В 1984 г. Н. Кармаркар предложил проективный метод линейного программирования. Алгоритм Кармаркара улучшил оценку полинома Хачияна в наихудшем случае (дает ). Кармаркар утверждал, что его алгоритм был намного быстрее в практической LP, чем симплекс-метод, и это заявление вызвало большой интерес к методам внутренней точки. С момента открытия Кармаркара было предложено и проанализировано множество методов внутренней точки.
Алгоритм Вайдьи 87
В 1987 году Вайдья предложил алгоритм, работающий во времени.
Алгоритм Вайдьи 89
В 1989 году Вайдья разработал алгоритм, работающий во времени. Формально говоря, алгоритм принимает арифметические операции в худшем случае, когда это количество ограничений, это число переменных, и это число бит.
Алгоритмы времени разреженности входных данных
В 2015 году Ли и Сидфорд показали, что ее можно решить за время, где представляет собой количество ненулевых элементов, и в худшем случае она остается принимаемой .
Алгоритм времени умножения текущей матрицы
В 2019 году Коэн, Ли и Сонг улучшили время от времени выполнение, это показатель степени умножения матриц и двойной показатель степени умножения матриц . (примерно) определяется как наибольшее число, такое, что можно умножить матрицу на матрицу во времени. В последующей работе Ли, Сон и Чжан они воспроизводят тот же результат другим методом. Эти два алгоритма остается , когда и . Результат благодаря Цзян, Сун, Вайнштейн и Чжан улучшился до .
Сравнение методов внутренней точки и симплексных алгоритмов
В настоящее время считается, что эффективность хороших реализаций симплекс-методов и методов внутренней точки одинакова для рутинных приложений линейного программирования. Однако для определенных типов задач LP может оказаться, что один тип решателя лучше, чем другой (иногда намного лучше), и что структура решений, генерируемых методами внутренней точки по сравнению с методами на основе симплексов, значительно отличается с поддержкой набор активных переменных обычно меньше для последнего.
Открытые проблемы и недавние работы
Допускает ли линейное программирование алгоритм с сильно полиномиальным временем?
В теории линейного программирования есть несколько открытых проблем, решение которых означало бы фундаментальный прорыв в математике и потенциально значительный прогресс в нашей способности решать крупномасштабные линейные программы.
- Допускает ли LP алгоритм с сильно полиномиальным временем?
- Допускает ли LP алгоритм с сильно полиномиальным временем для поиска строго дополнительного решения?
- Допускает ли LP алгоритм с полиномиальным временем в модели вычислений с вещественными числами (удельной стоимостью)?
Этот тесно связанный набор проблем был назван Стивеном Смейлом среди 18 величайших нерешенных проблем 21 века. По словам Смейла, третья версия проблемы «является основной нерешенной проблемой теории линейного программирования». В то время как алгоритмы существуют для решения линейного программирования в слабо полиномиальное время, например, в эллипсоид методов и приемов внутренних точек , никакие алгоритмы пока не было обнаружено , что позволяет производительность сильно полиномиальное время в ряде ограничений и числа переменных. Разработка таких алгоритмов представляла бы большой теоретический интерес и, возможно, также позволила бы получить практическую пользу при решении больших LP.
Хотя гипотеза Хирша была недавно опровергнута для более высоких размерностей, она все еще оставляет открытыми следующие вопросы.
- Существуют ли правила поворота, которые приводят к полиномиальным вариантам симплекса?
- Все ли многогранные графы имеют полиномиально ограниченный диаметр?
Эти вопросы касаются анализа производительности и разработки симплекс-подобных методов. Огромная эффективность симплексного алгоритма на практике, несмотря на его теоретическую производительность в экспоненциальном времени, намекает на то, что могут быть вариации симплексного алгоритма, которые работают за полиномиальное или даже сильно полиномиальное время. Было бы очень важно знать, существуют ли какие-либо такие варианты, особенно как подход к решению, можно ли решить ЛП за строго полиномиальное время.
Симплексный алгоритм и его варианты относятся к семейству алгоритмов отслеживания ребер, названных так потому, что они решают задачи линейного программирования, перемещаясь от вершины к вершине вдоль ребер многогранника. Это означает, что их теоретическая производительность ограничена максимальным числом ребер между любыми двумя вершинами многогранника LP. В результате мы заинтересованы в знании максимального теоретико-графического диаметра многогранных графов . Доказано, что все многогранники имеют субэкспоненциальный диаметр. Недавнее опровержение гипотезы Хирша - это первый шаг к доказательству того, имеет ли какой-либо многогранник суперполиномиальный диаметр. Если такие многогранники существуют, то никакой вариант следования ребрам не может выполняться за полиномиальное время. Вопросы о диаметре многогранника представляют самостоятельный математический интерес.
Симплексные методы поворота сохраняют первичную (или двойную) выполнимость. С другой стороны, методы перекрестного поворота не сохраняют (первичную или двойную) выполнимость - они могут посещать первичные допустимые, двойственно допустимые или первично-двойные недопустимые базы в любом порядке. Методы Pivot этого типа изучаются с 1970-х годов. По сути, эти методы пытаются найти кратчайший путь поворота на многограннике расположения в задаче линейного программирования. В отличие от многогранных графов, графы многогранников расположения, как известно, имеют малый диаметр, что позволяет использовать алгоритм перекрестного поворота с сильно полиномиальным временем без решения вопросов о диаметре многогранников общего вида.
Целочисленные неизвестные
Если все неизвестные переменные должны быть целыми числами, тогда проблема называется проблемой целочисленного программирования (IP) или целочисленного линейного программирования (ILP). В отличие от линейного программирования, которое может быть эффективно решено в худшем случае, задачи целочисленного программирования во многих практических ситуациях (с ограниченными переменными) являются NP-трудными . Целочисленное программирование 0–1 или двоичное целочисленное программирование (BIP) является частным случаем целочисленного программирования, когда переменные должны быть 0 или 1 (а не произвольные целые числа). Эта проблема также классифицируется как NP-трудная, и фактически версия решения была одной из 21 NP-полных задач Карпа .
Если требуется, чтобы только некоторые из неизвестных переменных были целыми числами, проблема называется проблемой смешанного целочисленного программирования (MIP). Обычно они также NP-трудны, потому что они даже более общие, чем программы ПДОДИ.
Однако есть некоторые важные подклассы задач IP и MIP, которые эффективно решаются, в первую очередь проблемы, в которых матрица ограничений полностью унимодулярна, а правые части ограничений являются целыми числами или, в более общем смысле, где система имеет полную двойную целостность (TDI) свойство.
Расширенные алгоритмы решения целочисленных линейных программ включают:
- плоскостной метод
- Ветвь и переплет
- Разделить и разрезать
- Филиал и цена
- если проблема имеет дополнительную структуру, можно применить отложенное создание столбцов .
Такие алгоритмы целочисленного программирования обсуждаются Падбергом и Бизли.
Интегральные линейные программы
Линейная программа в вещественных переменных называется интегральной, если у нее есть хотя бы одно оптимальное решение - интегральное. Точно так же многогранник называется целым, если для всех ограниченных допустимых целевых функций c линейная программа имеет оптимум с целочисленными координатами. Как наблюдали Эдмондс и Джайлз в 1977 году, можно эквивалентно сказать, что многогранник является целым, если для любой ограниченной допустимой интегральной целевой функции c оптимальное значение линейной программы является целым числом.
Интегральные линейные программы имеют центральное значение в многогранном аспекте комбинаторной оптимизации, поскольку они обеспечивают альтернативную характеристику проблемы. В частности, для любой задачи выпуклая оболочка решений представляет собой целочисленный многогранник; если этот многогранник имеет красивое / компактное описание, то мы можем эффективно найти оптимальное допустимое решение при любой линейной цели. И наоборот, если мы сможем доказать, что релаксация линейного программирования является интегральной, то это будет желаемое описание выпуклой оболочки допустимых (интегральных) решений.
Терминология не является единообразной во всей литературе, поэтому следует осторожно различать следующие два понятия:
- в целочисленной линейной программе, описанной в предыдущем разделе, переменные принудительно ограничиваются целыми числами, и эта проблема в целом NP-трудна,
- в интегральной линейной программе, описанной в этом разделе, переменные не ограничиваются целыми числами, а скорее каким-то образом доказано, что непрерывная задача всегда имеет целочисленное оптимальное значение (при условии, что c является целым), и это оптимальное значение может быть эффективно найдено, поскольку все линейные программы полиномиального размера могут быть решены за полиномиальное время.
Один из распространенных способов доказать, что многогранник целочислен, - это показать, что он полностью унимодулярен . Существуют и другие общие методы, включая свойство целочисленной декомпозиции и полную двойственную целостность . Другие конкретные хорошо известные интегральные LP включают совпадающий многогранник, решетчатые многогранники, субмодульные многогранники потока и пересечение двух обобщенных полиматроидов / g -полиматроидов - например, см. Schrijver 2003.
Решатели и языки сценариев (программирования)
Разрешающие лицензии:
Имя | Лицензия | Краткая информация |
---|---|---|
GLOP | Apache v2 | Решатель линейного программирования с открытым исходным кодом от Google |
Pyomo | BSD | Язык моделирования с открытым исходным кодом для крупномасштабной линейной, смешанной целочисленной и нелинейной оптимизации. |
СуанШу | Apache v2 | набор алгоритмов оптимизации с открытым исходным кодом для решения LP, QP , SOCP , SDP , SQP на Java |
Копилефт (взаимные) лицензии:
Имя | Лицензия | Краткая информация |
---|---|---|
Решатель ограничений казуара | LGPL | набор инструментов для постепенного решения ограничений, который эффективно решает системы линейных равенств и неравенств |
CLP | CPL | решатель LP от COIN-OR |
glpk | GPL | Комплект программирования GNU Linear, ЛП / MILP решатель с родным C API и многочисленными (15) третьих лиц обертками для других языков. Специализированная поддержка проточных сетей . Включает в себя AMPL- подобный язык моделирования и переводчик GNU MathProg . |
Qoca | GPL | библиотека для пошагового решения систем линейных уравнений с различными целевыми функциями |
R-Project | GPL | язык программирования и программная среда для статистических вычислений и графики |
MINTO (Mixed Integer Optimizer, решающая программа для целочисленного программирования , использующая алгоритм ветвления и привязки) имеет общедоступный исходный код, но не является открытым исходным кодом.
Собственные лицензии:
Имя | Краткая информация |
---|---|
ЦЕЛИ | Язык моделирования, позволяющий моделировать линейные, смешанные целочисленные и нелинейные модели оптимизации. Он также предлагает инструмент для программирования ограничений. Алгоритм в форме эвристики или точных методов, таких как Branch-and-Cut или Column Generation, также может быть реализован. Инструмент вызывает соответствующий решатель, такой как CPLEX, Gurobi или аналогичный, для решения поставленной задачи оптимизации. Академические лицензии выдаются бесплатно. |
AMPL | Популярный язык моделирования для крупномасштабной линейной, смешанной целочисленной и нелинейной оптимизации с доступной бесплатной ограниченной версией для учащихся (500 переменных и 500 ограничений). |
APMonitor | API к MATLAB и Python. Решите примеры задач линейного программирования (LP) через MATLAB, Python или веб-интерфейс. |
CPLEX | Популярный решатель с API для нескольких языков программирования, а также язык моделирования и работа с AIMMS, AMPL, GAMS , MPL, OpenOpt, OPL Development Studio и TOMLAB . Бесплатно для академического использования. |
Функция решателя Excel | Нелинейный решатель, адаптированный к электронным таблицам, в которых оценки функций основаны на пересчете ячеек. Базовая версия доступна как стандартное дополнение для Excel. |
FortMP | |
GAMS | |
Гуроби | Решатель с параллельными алгоритмами для крупномасштабных линейных программ, квадратичных программ и смешано-целочисленных программ. Бесплатно для академического использования. |
Цифровые библиотеки IMSL | Коллекции математических и статистических алгоритмов доступны на C / C ++, Fortran, Java и C # /. NET. Подпрограммы оптимизации в библиотеках IMSL включают неограниченные, линейно и нелинейно ограниченные минимизации и алгоритмы линейного программирования. |
LINDO | Решатель с API для крупномасштабной оптимизации линейных, целочисленных, квадратичных, конических и общих нелинейных программ с расширениями стохастического программирования. Он предлагает процедуру глобальной оптимизации для поиска гарантированного глобально оптимального решения общих нелинейных программ с непрерывными и дискретными переменными. Он также имеет API статистической выборки для интеграции моделирования Монте-Карло в структуру оптимизации. Он имеет язык алгебраического моделирования ( LINGO ) и позволяет моделировать в электронной таблице ( What'sBest ). |
Клен | Универсальный язык программирования для символьных и числовых вычислений. |
MATLAB | Универсальный матрично-ориентированный язык программирования для числовых вычислений. Для линейного программирования в MATLAB требуется Optimization Toolbox в дополнение к базовому продукту MATLAB; доступные процедуры включают INTLINPROG и LINPROG |
Mathcad | Математический редактор WYSIWYG. В нем есть функции для решения как линейных, так и нелинейных задач оптимизации. |
Mathematica | Универсальный язык программирования для математики, включая символьные и числовые возможности. |
МОСЕК | Решатель для крупномасштабной оптимизации с API для нескольких языков (C ++, java, .net, Matlab и python). |
Цифровая библиотека NAG | Набор математических и статистических процедур, разработанных Numerical Algorithms Group для нескольких языков программирования (C, C ++, Fortran, Visual Basic, Java и C #) и пакетов (MATLAB, Excel, R, LabVIEW). Глава Оптимизация библиотеки NAG включает процедуры для задач линейного программирования с разреженными и не разреженными матрицами линейных ограничений, а также процедуры для оптимизации квадратичных, нелинейных сумм квадратов линейных или нелинейных функций с нелинейными, ограниченными или отсутствующими ограничениями. . В библиотеке NAG есть процедуры как для локальной, так и для глобальной оптимизации, а также для непрерывных или целочисленных задач. |
OptimJ | Язык моделирования на основе Java для оптимизации с доступной бесплатной версией. |
SAS / OR | Набор решателей для линейной, целочисленной, нелинейной, без производной, сетевой, комбинаторной оптимизации и оптимизации ограничений; язык алгебраического моделирования OPTMODEL ; и различные вертикальные решения, нацеленные на конкретные проблемы / рынки, все из которых полностью интегрированы с системой SAS . |
SCIP | Решатель целочисленного программирования с ограничениями общего назначения с упором на MIP. Совместимость с языком моделирования Zimpl . Бесплатно для академического использования и доступно в исходном коде. |
XPRESS | Решатель для крупномасштабных линейных программ, квадратичных программ, общих нелинейных и смешанно-целочисленных программ. Имеет API для нескольких языков программирования, также имеет язык моделирования Mosel и работает с AMPL, GAMS . Бесплатно для академического использования. |
VisSim | Язык визуальных блок-схем для моделирования динамических систем . |
Смотрите также
- Выпуклое программирование
- Динамическое программирование
- Ожидаемый дефицит § Оптимизация ожидаемого дефицита
- Модель ввода-вывода
- Планирование работы цеха
- Линейная алгебра
- Линейная производственная игра
- Дробно-линейное программирование (LFP)
- Задача типа LP
- Математическое программирование
- Нелинейное программирование
- Ориентированный матроид
- Квадратичное программирование , надмножество линейного программирования
- Полуопределенное программирование
- Теневая цена
- Симплексный алгоритм , используемый для решения задач LP
Примечания
использованная литература
- Канторович, Л. В. (1940). "Об одном эффективном методе решения некоторых классов экстремальных проблем" [Новый метод решения некоторых классов экстремальных задач]. Доклады АН СССР . 28 : 211–214.
- Ф.Л. Хичкок: Распространение продукта из нескольких источников по многочисленным местам , Journal of Mathematics and Physics, 20, 1941, 224–230.
- Г.Б. Данциг: Максимизация линейной функции переменных с учетом линейных неравенств , 1947. Опубликовано на стр. 339–347 в TC Koopmans (ed.): Activity Analysis of Production and Allocation , New York-London 1951 (Wiley & Chapman-Hall)
- Дж. Э. Бизли, редактор. Успехи в линейном и целочисленном программировании . Oxford Science, 1996. (Сборник обзоров)
- Блэнд, Роберт Г. (1977). «Новые правила конечного поворота для симплексного метода». Математика исследования операций . 2 (2): 103–107. DOI : 10.1287 / moor.2.2.103 . JSTOR 3689647 .
- Карл-Хайнц Боргвардт, Симплексный алгоритм: вероятностный анализ , алгоритмы и комбинаторика, том 1, Springer-Verlag, 1987. (Поведение в среднем для случайных задач)
- Ричард В. Коттл, изд. Базовый Джордж Б. Данциг . Stanford Business Books, Stanford University Press, Стэнфорд, Калифорния, 2003 г. (Избранные статьи Джорджа Б. Данцига )
- Джордж Б. Данциг и Мукунд Н. Тапа. 1997. Линейное программирование 1: Введение . Springer-Verlag.
- Джордж Б. Данциг и Мукунд Н. Тапа. 2003. Линейное программирование 2: теория и расширения . Springer-Verlag. (Комплексный, охватывающий, например, алгоритмы поворота и внутренней точки, крупномасштабные задачи, декомпозицию по Данцигу – Вулфу и Бендерсу , а также введение стохастического программирования .)
- Эдмондс, Джек; Джайлз, Рик (1977). «Отношение минимум-максимум для субмодульных функций на графах». Исследования в области целочисленного программирования . Анналы дискретной математики. 1 . С. 185–204. DOI : 10.1016 / S0167-5060 (08) 70734-9 . ISBN 978-0-7204-0765-5.
- Фукуда, Комей; Терлаки, Тамаш (1997). Томас М. Либлинг; Доминик де Верра (ред.). «Перекрестные методы: свежий взгляд на алгоритмы разворота». Математическое программирование, серия B . 79 (1-3): 369-395. CiteSeerX 10.1.1.36.9373 . DOI : 10.1007 / BF02614325 . Руководство по ремонту 1464775 . S2CID 2794181 .
- Гондзио, Яцек; Терлаки, Тамаш (1996). «3 Вычислительный взгляд на методы внутренней точки» . В JE Бизли (ред.). Успехи в линейном и целочисленном программировании . Оксфордская серия лекций по математике и ее приложениям. 4 . Нью-Йорк: Издательство Оксфордского университета. С. 103–144. Руководство по ремонту 1438311 . Файл PostScript на веб-сайте Гондзио и на веб-сайте Университета Макмастера в Терлаки .
- Мурти, Катта Г. (1983). Линейное программирование . Нью-Йорк: John Wiley & Sons, Inc., стр. Xix + 482. ISBN 978-0-471-09725-9. Руководство по ремонту 0720547 . (исчерпывающая ссылка на классические подходы).
- Эвар Д. Неринг и Альберт В. Такер , 1993, Линейные программы и связанные с ними проблемы , Academic Press. (элементарный)
- М. Падберг, Линейная оптимизация и расширения , второе издание, Springer-Verlag, 1999. (тщательно написанный отчет о простых и двойственных симплексных алгоритмах и проективных алгоритмах, с введением в целочисленное линейное программирование - с задачей коммивояжера для Одиссея ).
- Христос Х. Пападимитриу и Кеннет Стейглиц, Комбинаторная оптимизация: алгоритмы и сложность , исправленное переиздание с новым предисловием, Dover. (Информатика)
- Майкл Дж. Тодд (февраль 2002 г.). «Многогранность линейного программирования». Математическое программирование . 91 (3): 417–436. DOI : 10.1007 / s101070100261 . S2CID 6464735 . (Приглашенный опрос с Международного симпозиума по математическому программированию.)
- Вандербей, Роберт Дж. (2001). Линейное программирование: основы и расширения . Springer Verlag.
- Вазирани, Виджай В. (2001). Аппроксимационные алгоритмы . Springer-Verlag. ISBN 978-3-540-65367-7. (Информатика)
дальнейшее чтение
Библиотечные ресурсы о линейном программировании |
- Дмитрис Алеврас и Манфред В. Падберг, Линейная оптимизация и расширения: проблемы и решения , Universitext, Springer-Verlag, 2001. (Проблемы Падберга с решениями).
- Марк де Берг, Марк ван Кревельд, Марк Овермарс и Отфрид Шварцкопф (2000). Вычислительная геометрия (2-е изд., Перераб.). Springer-Verlag . ISBN 978-3-540-65620-3.CS1 maint: несколько имен: список авторов ( ссылка ) Глава 4: Линейное программирование: стр. 63–94. Описывает рандомизированный алгоритм пересечения полуплоскостей для линейного программирования.
- Майкл Р. Гарей и Дэвид С. Джонсон (1979). Компьютеры и непоколебимость: руководство по теории NP-полноты . WH Freeman. ISBN 978-0-7167-1045-5.A6: MP1: ЦЕЛОЕ ПРОГРАММИРОВАНИЕ, стр. 245. (информатика, теория сложности)
- Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования . Берлин: Springer. ISBN 3-540-30697-8. (элементарное введение для математиков и информатиков)
- Корнелис Роос, Тамаш Терлаки, Жан-Филипп Виаль, Методы внутренней точки для линейной оптимизации , второе издание, Springer-Verlag, 2006. (уровень выпускника)
- Александр Шрайвер (2003). Комбинаторной оптимизации: многогранники и эффективность . Springer.
- Александр Шрайвер, Теория линейного и целочисленного программирования . John Wiley & sons, 1998, ISBN 0-471-98232-6 (математика)
- Жерар Сирксма; Йори Зволс (2015). Линейная и целочисленная оптимизация: теория и практика . CRC Press. ISBN 978-1-498-71016-9.
- Жерар Сирксма; Диптеш Гош (2010). Сети в действии; Текстовые и компьютерные упражнения по оптимизации сети . Springer. ISBN 978-1-4419-5512-8. (линейное оптимизационное моделирование)
- HP Williams, Построение моделей в математическом программировании , пятое издание, 2013 г. (моделирование)
- Стивен Дж. Райт, 1997, Первично-двойственные методы внутренней точки , SIAM. (Выпускной уровень)
- Yinyu Ye , 1997, Алгоритмы внутренней точки: теория и анализ , Wiley. (Продвинутый уровень выпускника)
- Зиглер, Гюнтер М. , главы 1–3 и 6–7 в Лекциях по многогранникам , Springer-Verlag, Нью-Йорк, 1994. (Геометрия)