Линейное программирование (LP, также называемое линейной оптимизацией ), является методом достижения наилучшего результата (например, максимальная прибыль или наименьшая стоимость) в математической модели, которой представлены требования линейными отношениями. Линейное программирование - это частный случай математического программирования (также известное как математическая оптимизация ).
Более формально, линейное программирование - это метод оптимизации линейной функции функции при условии линейного равенства и линейное неравенство ограничения. Его допустимая область является выпуклым многогранником, который представляет собой множество, определенное как пересечение конечного числа полупространств, каждое из которых определяется линейным неравенством. Его целевая функция представляет собой действительную -значную аффинную (линейную) функцию, определенную на этом многограннике. Алгоритм линейного программирования находит точку в многограннике , где эта функция имеет наименьшее (или наибольшее) значение, если такая точка существует.
Линейные программы - это проблемы, которые могут быть выражены в канонической форме как
где x представляет векторную (чтобы быть определено), c и b - это (известных) коэффициентов, A - (известная) матрица коэффициентов, и - транспонированная матрица. Выражение, которое нужно максимизировать или минимизировать, в этом случае называется функция функции (cx). Неравенства A x≤ bи x≥ 0являются ограничителями, которые задают выпуклый многогранник , по которому должна быть оптимизирована целевая функция. В этом контексте два изображения сравнимы, если они имеют одинаковые размеры. Если каждая запись в первом меньше или используется записи во втором, то можно сказать, что первый вектор меньше или равен второму вектору.
Линейное программирование может использовать различные области обучения. Он широко используется в математике и в меньшей степени, в бизнесе, экономике и для некоторых инженерных задач. Отрасли, в которых используются модели линейного программирования, включая транспорт, энергетику, телекоммуникации и производство. Он оказался полезным при планировании различных типов проблем в , маршрутизации, планировании, назначении и проектировании.
Проблема решения линейных неравенств восходит как минимум к Фурье, который в 1827 году опубликовал метод их решения и в честь которого назван метод исключение Фурье - Моцкина.
В 1939 г. формулировка задачи линейного программирования, которая эквивалентна общей задаче линейного программирования, была дана советским математиком и экономистом Леонид Канторович, который также использует способ ее решения. Это способ, который он разработал во время Второй мировой войны, чтобы планировать расходы и доходы, чтобы сократить расходы армии и увеличить потери, нанесенные противнику. Работа Канторовича изначально игнорировалась в СССР. Примерно в то же время, что и Канторович, американский экономист голландско-американского происхождения Т. К. Купманс сформулировал классические экономические задачи как линейные программы. Позднее Канторович и Купманс разделили Нобелевскую премию 1975 года по экономике . В 1941 году Фрэнк Лорен Хичкок также сформулировал транспортные задачи в виде линейных программ и дал решение, очень похожее на более поздний симплекс-метод. Хичкок умер в 1957 году, и Нобелевская премия не присуждена посмертно.
В течение 1946–1947 гг. Джордж Б. Данциг независимо разработал общую формулировку линейного программирования для использования в задачах планирования в ВВС США. В 1947 году Данциг также изобрел симплекс-метод, который впервые эффективно решал проблему линейного программирования в большинстве случаев. Когда Данциг устроил встречу с Джоном фон Нейманом, чтобы обсудить свой симплексный метод, Нойман сразу же высказал гипотезу о теории двойственности, осознал, что проблема, над которой он работал, теории игр был эквивалентен. Данциг представил формальное доказательство в неопубликованном отчете «Теорема о линейных неравенствах» от 5 января 1948 года. Работа Данцига была обнародована в 1951 году. В послевоенные годы многих отраслей промышленности применяли ее в своем ежедневном планировании.
Первоначальный пример Данцига заключался в том, чтобы найти лучшее назначение из 70 человек на 70 рабочих мест. Вычислительная мощность, необходимая для тестирования всех перестановок для выбора наилучшего назначения, огромна; количество активных количеств частиц в наблюдаемой вселенной. Однако требуется всего лишь мгновение, чтобы найти оптимальное решение, поставив задачу в виде линейной программы и применив симплексный алгоритм . Теория линейного резко сокращает количество средств, которые необходимо проверить.
Решение задачи линейного программирования для полиномиального времени было введено Леонидом Хачияном в 1979 году, но более крупный теоретический и практический прорыв в этой области произошел в 1984 году, когда Нарендра Кармаркар представил новый метод внутренней точки для решения задач линейного программирования.
Линейное программирование является широко используемой областью оптимизации по нескольким причинам. Многие практические проблемы в исследовании операций могут быть выражены как задачи линейного программирования. Определенные частные случаи линейного программирования, такие как проблемы сетевого потока и проблемы многопродуктового потока, считаются достаточно важными для того, чтобы создать исследование системы алгоритмов для их решения. Ряд алгоритмов для других типов задач работают, решая задачи LP как подзадачи. Исторически идеи линейного программирования рассматривали многие из центральных концепций теории оптимизации, такой как двойственность, декомпозиция и выпуклости ее обобщений. Точно так же линейное программирование активно использовалось на начальном этапе формирования микроэкономики, например, в планировании, производстве, транспортировке, технологиях и других вопросах. Хотя современные проблемы управления постоянно меняются, большинство ограничителей хотят максимизировать прибыль и минимизировать затраты на имеющиеся ресурсы. Поэтому многие проблемы можно охарактеризовать как задачи линейного программирования.
Стандартная форма - это обычная и наиболее интуитивно понятная форма задачи линейного программирования. Он состоит из следующих трех частей:
Обычно проблема выражается в форме матрицы, а становится:
Другие формы, такие как задачи минимизации, проблемы с ограничениями на альтернативные формы, а также проблемы с отрицательными переменными всегда можно переписать в эквивалентную стандартную форму.
Предположим, что у фермера есть участок сельскохозяйственной земли, скажем, L км, который нужно засеять либо пшеницей, либо ячменем, либо некоторой их комбинацией. У фермера есть ограниченное количество удобрений, F килограммов, и пестицидов, P килограммов. На каждый квадратный километр пшеницы требуется F 1 килограммов удобрений и P 1 килограмм пестицидов, в то время как на каждый квадратный километр ячменя требуется F 2 килограммов удобрений и P 2 килограмма пестицида. Пусть S 1 будет продажной ценой пшеницы за квадратный километр, а S 2 будет продажной ценой ячменя. Если обозначить площадь земель, засеянных пшеницей и ячменем, как x 1 и x 2 соответственно, то прибыль можно максимизировать, выбрав оптимальные значения для x 1 и x 2. Эта проблема может быть выражена в следующей линейного программирования в стандартной форме:
Развернуть: | (максимизировать доход - доход является «функцией функции») | |
При условии: | (ограничение на общую площадь) | |
(ограничение на удобрения) | ||
(ограничение на пестицид) | ||
(нельзя засаживать отрицательную область). |
В матричной форме это выглядит следующим образом:
Задачи линейного программирования могут быть преобразованы в расширенную форму для применения общей формулы симплекс-алгоритма. Эта форма вводит неотрицательные переменные запаса, чтобы заменить равенство равенствам в ограничениях. Затем могут быть записаны в следующей форме блочной матрицы :
, где - недавно представленные слабые переменные, - переменные решения, а - переменная, которую нужно максимизировать.
Приведенный выше пример преобразован в расширенную формулу:
Развернуть: | (целевая функция) | |
при условии: | (расширенное ограничение) | |
(расширенное ограничение) | ||
(расширенное ограничение) | ||
где - это (неотрицательные) переменные запаса хода, представляющие в этом примере неиспользованную площадь, количество неиспользованных удобрений., и количество неиспользованного пестицида.
В матричной форме это выглядит следующим образом:
Любую задачу линейного программирования, называемую основную проблему, можно преобразовать в двойную задачу, что дает оценку сверху оптимального значения прямые задачи. В матричной форме мы можем выразить основную проблему как:
Альтернативная простая формулировка:
Есть две фундаментальные идеи теории теории. Один из них заключается в том, что (для симметричной дуальной) двойная линейная программа является исходной прямой линейной программой. Кроме того, допустимое решение линейной программы дает оценку оптимального значения функции двойной программы. Теорема слабой двойственности утверждает, что значение функции двойного элемента в любом допустимом решении всегда больше или равно значении функции прямого элемента в любом допустимом решении. Теорема сильной двойственности утверждает, что если прямое число имеет оптимальное решение, x, то двойственное также имеет оптимальное решение, y и cx=by.
A линейная программа также может быть неограниченной или невыполнимой. Теория двойственности говорит нам, что если прямое не ограничено, то двойственное невозможно по слабой теореме двойственности. Точно так же, если двойственное неограничено, тогда прямое должно быть недопустимым. Однако, как двойное, так и прямое может быть недопустимыми. См. двойная линейная программа для подробностей и еще нескольких примеров.
A покрывающие LP заменить собой линейную программу вида:
таким образом, что матрица A и состояние b и c неотрицательны.
Дуал покрывающей LP - это упаковочная LP, линейная программа вида:
такой что матрица A и структура b и c неотрицательны.
Покрытие и упаковка LP обычно возникают как релаксация линейного программирования комбинаторной задачи и важны при изучении алгоритмов аппроксимации. Например, ослабления LP для упаковки набора, проблемы независимого набора и проблемы сопоставления являются упаковкой LP. LP-релаксация проблемы проблемы покрытия, покрытия вершины и проблемы доминирующего числа также покрывают LP.
Нахождение дробной раскраски графа - еще один пример покрывающей LP. В этом случае существует одно ограничение для каждой вершины графа и одна переменная для каждого независимого набора графа.
Возможно получить оптимальное решение двойственного, если только оптимальное решение для первичного, используя теорему о дополнительном провисании. Теорема утверждает:
Предположим, что x = (x1, x2,..., xn) является первично допустимым и что y = (y1, y2,..., ym) двойственно допустима. Пусть (w1, w2,..., wm) обозначают соответствующие первичные переменные резерва, а (z1, z2,..., zn) обозначают соответствующие двойные переменные резерва. Тогда x и y оптимальны для своих соответствующих задач тогда и только тогда, когда
Итак, если i-я переменная резерва первичного элемента не равна нулю, то i-я переменная дуального элемента равна нулю. Точно так же, если j-я переменная резерва дуального элемента не равна нулю, то j-я переменная простого элемента равна нулю.
Это необходимое условие оптимальности выражает довольно простой экономический принцип. В стандартной форме (при максимизации), если есть резерв в ограниченном основном ресурсе (т.е. есть «остатки»), то дополнительные количества этого ресурса не должны иметь ценности. Аналогичным образом, если есть слабое место в требовании двойного (теневого) ограничения неотрицательности цены, то есть цена не равна нулю, то должны быть дефицитные запасы (без «остатков»).
Геометрически линейные ограничения определяют допустимую область, которая является выпуклой точных методов, таких как Генерация ветвей и разрезов или столбцов. Инструмент вызывает соответствующий решатель, такой как CPLEX, Gurobi или аналогичный, для решения поставленной задачи оптимизации. Академические лицензии выдаются бесплатно.AMPL Популярный язык моделирования для крупномасштабной линейной, смешанной целочисленной и нелинейной оптимизации с доступной ограниченной версией для учащихся (500 переменных и 500 ограничений). APMonitor API для MATLAB и Python. Решите пример задачи линейного программирования (LP) через MATLAB, Python или веб-интерфейс. CPLEX Популярный решатель с API для нескольких языков программирования, а также язык моделирования и работы с AIMMS, AMPL, GAMS, MPL, OpenOpt, OPL Development Studio и ТОМЛАБ. Бесплатно для академического использования. Excel Функция решателя Нелинейный решатель, адаптированный к электронным таблицам, в которых оценки функций основаны на пересчете ячеек. Базовая версия как стандартное дополнение для Excel. FortMP GAMS Гуроби Решатель с параллельными алгоритмами для крупномасштабных линейных программ, квадратичных программ и смешанных целочисленных программ. Бесплатно для академического использования. Числовые библиотеки IMSL Наборы математических и статистических алгоритмов, доступных на C / C ++, Fortran, Java и C # /. СЕТЬ. Процедуры оптимизации в библиотеке IMSL включают неограниченные, линейно и нелинейно ограниченные минимизации, а также алгоритмы линейного программирования. LINDO Решатель с API для крупномасштабной оптимизации линейных, целочисленных, квадратичных, конических и общих нелинейных программ с расширениями стохастического программирования. Он предлагает глобальную оптимизацию для поиска гарантированного глобально оптимального решения общих программ с непрерывными и дискретными переменными. Он также имеет API статистической выборки для интеграции моделирования Монте-Карло в оптимизацию. Он язык алгебраического моделирования (LINGO ) и позволяет моделировать в таблице (). Maple Универсальный язык программирования для символьных и числовых вычислений. MATLAB Универсальный матрично-ориентированный язык программирования для численных вычислений. Для линейного программирования в MATLAB требуется Optimization Toolbox в дополнение к базовому продукту MATLAB; Доступные подпрограммы включают INTLINPROG и LINPROG Mathcad Математический редактор WYSIWYG. В нем есть функции для решений как линейных, так и нелинейных задач оптимизации. Mathematica Универсальный язык программирования для математики, включая символьные и числовые возможности. MOSEK Решатель для крупномасштабной оптимизации с API для нескольких языков (C ++, java,.net, Matlab и python). NAG Numerical Library Набор математических и статистических процедур, разработанных Numerical Algorithms Group для нескольких языков программирования (C, C ++, Fortran, Visual Basic, Java и C #) и пакетов (MATLAB, Excel, R, LabVIEW). Глава Оптимизация библиотеки NAG включает процедуры для задач линейного программирования как с разреженными, так и с неразрушенными матрицами линейных ограничений, а также процедуры для оптимизации квадратичных, нелинейных сумм квадратов линейных или нелинейных функций с нелинейными, ограниченными или отсутствующими ограничениями.. В библиотеке NAG есть процедуры как для локальных, так и для глобальной оптимизации, а также для непрерывных или целочисленных задач. NMath Stats Универсальная статистическая библиотека .NET, содержащая симплексный решатель. OptimJ Язык моделирования на основе Java для оптимизации с доступной бесплатной версией. SAS / OR Набор решателей для линейной, целочисленной, нелинейной, без производной, сетевой, комбинаторной оптимизации и оптимизации ограничений; язык алгебраического моделирования OPTMODEL ; и различные вертикальные решения, нацеленные на определенные проблемы / рынки, все из которых полностью интегрированы с Система SAS. SCIP Решатель целочисленного программирования с ограничениями общего назначения с упором на MIP. Совместимость с языком моделирования Zimpl. Бесплатно для академического использования и доступно в исходном коде. XPRESS Решатель для крупномасштабных линейных программ, квадратичных программ, общих и смешанно-целочисленных программ. Имеет API для нескольких языков программирования, имеет язык моделирования Mosel и работает с AMPL, GAMS. Бесплатно для академического использования. VisSim Визуальная блок-схема язык для моделирования динамических систем.
Викискладе есть материалы, связанные с линейным программированием. |