Линейное программирование


Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n {displaystyle n} -мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

Линейное программирование (ЛП) является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование.

Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их.

История

Математические исследования отдельных экономических проблем, математическая формализация числового материала проводилась ещё в XIX веке. При математическом анализе процесса расширенного производства использовались алгебраические соотношения, анализ их проводился с помощью дифференциального исчисления. Это давало возможность получить общее представление о проблеме.

Развитие экономики потребовало количественных показателей, и в 1920 годы был создан межотраслевой баланс (МОБ). Он-то и послужил толчком в деле создания и исследования математических моделей. Разработка МОБ в 1924—1925 годах в СССР повлияла на работы экономиста и статистика Василия Васильевича Леонтьева. Он разработал межотраслевую модель производства и распределения продукции.

В 1938 году Леонид Витальевич Канторович в порядке научной консультации приступил к изучению чисто практической задачи по составлению наилучшего плана загрузки лущильных станков (фанерный трест). Эта задача не поддавалась обычным методам. Стало ясно, что задача не случайная.

В 1939 году Леонид Канторович опубликовал работу «Математические методы организации и планирования производства», в которой сформулировал новый класс экстремальных задач с ограничениями и разработал эффективный метод их решения, таким образом были заложены основы линейного программирования.

Изучение подобных задач привело к созданию новой научной дисциплины линейного программирования и открыло новый этап в развитии экономико-математических методов.

В 1949 году американский математик Джордж Бернард Данциг разработал эффективный метод решения задач линейного программирования (ЗЛП) — симплекс-метод.

Термин «программирование» нужно понимать в смысле «планирования» (один из переводов англ. programming). Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, ещё до того, как компьютеры были использованы для решения линейных задач оптимизации.

Метод внутренних точек был впервые упомянут И. И. Дикиным в 1967 году.. Эти исследования были продолжены в том числе и отечественными учёными. В 1970-е годы В. Г. Жадану удалось получить основные результаты и разработать общий подход к построению методов внутренней точки для решения задач линейного и нелинейного программирования, основанный на преобразовании пространств; предложить барьерно-проективные и барьерно-ньютоновские численные методы.

Задачи

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

f ( x ) = ∑ j = 1 n c j x j = c 1 x 1 + c 2 x 2 + … + c n x n . {displaystyle f(x)=sum _{j=1}^{n}c_{j}x_{j}=c_{1}x_{1}+c_{2}x_{2}+ldots +c_{n}x_{n}.}

Задача, в которой фигурируют ограничения в форме неравенств, называется основной задачей линейного программирования (ОЗЛП)

∑ j = 1 n a i j x j ⩾ b i , ( i = 1 , 2 , … , m ) {displaystyle sum _{j=1}^{n}a_{ij}x_{j}geqslant b_{i},quad (i=1,;2,;ldots ,;m)} x j ⩾ 0. ( j = 1 , 2 , … , n ) {displaystyle x_{j}geqslant 0.quad (j=1,;2,;ldots ,;n)}

Задача линейного программирования будет иметь канонический вид, если в основной задаче вместо первой системы неравенств имеет место система уравнений с ограничениями в форме равенства:

∑ j = 1 n a i j x j = b i . ( i = 1 , 2 , … , m ) {displaystyle sum _{j=1}^{n}a_{ij}x_{j}=b_{i}.quad (i=1,;2,;ldots ,;m)}

Основную задачу можно свести к канонической путём введения дополнительных переменных.

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

Легко заметить, что задачу нахождения максимума можно заменить задачей нахождения минимума, взяв коэффициенты c {displaystyle c} с обратным знаком.

Примеры задач

Максимальное паросочетание

Рассмотрим задачу о максимальном паросочетании в двудольном графе: есть несколько юношей и девушек, причём для каждых юноши и девушки известно, симпатичны ли они друг другу. Нужно поженить максимальное число пар со взаимной симпатией.

Введём переменные x i j {displaystyle x_{ij}} , которые соответствуют паре из i {displaystyle i} -го юноши и j {displaystyle j} -й девушки и удовлетворяют ограничениям:

0 ⩽ x i j ⩽ 1 , {displaystyle 0leqslant x_{ij}leqslant 1,} x 1 j + x 2 j + … + x n j ⩽ 1 , {displaystyle x_{1j}+x_{2j}+ldots +x_{nj}leqslant 1,} x i 1 + x i 2 + … + x i m ⩽ 1 , {displaystyle x_{i1}+x_{i2}+ldots +x_{im}leqslant 1,}

с целевой функцией f = c 11 x 11 + c 12 x 12 + … + c n m x n m {displaystyle f=c_{11}x_{11}+c_{12}x_{12}+ldots +c_{nm}x_{nm}} , где c i j {displaystyle c_{ij}} равны 1 или 0 в зависимости от того, симпатичны ли i {displaystyle i} -й юноша и j {displaystyle j} -я девушка друг другу. Можно показать, что среди оптимальных решений этой задачи найдётся целочисленное. Переменные, равные 1, будут соответствовать парам, которые следует поженить.

Максимальный поток

Пусть имеется граф (с ориентированными рёбрами), в котором для каждого ребра указана его пропускная способность. И заданы две вершины: сток и исток. Нужно указать для каждого ребра, сколько через него будет протекать жидкости (не больше его пропускной способности) так, чтобы максимизировать суммарный поток из истока в сток (жидкость не может появляться или исчезать во всех вершинах, кроме истока и стока, соответственно).

Возьмём в качестве переменных x i {displaystyle x_{i}} — количество жидкости, протекающей через i {displaystyle i} -е ребро. Тогда

0 ⩽ x i ⩽ c i , {displaystyle 0leqslant x_{i}leqslant c_{i},}

где c i {displaystyle c_{i}} — пропускная способность i {displaystyle i} -го ребра. Эти неравенства надо дополнить равенством количества втекающей и вытекающей жидкости для каждой вершины, кроме стока и истока. В качестве функции f {displaystyle f} естественно взять разность между количеством вытекающей и втекающей жидкости в истоке.

Обобщение предыдущей задачи — максимальный поток минимальной стоимости. В этой задаче даны стоимости для каждого ребра и нужно среди максимальных потоков выбрать поток с минимальной стоимостью. Эта задача сводится к двум задачам линейного программирования: сначала нужно решить задачу о максимальном потоке, а потом добавить к этой задаче ограничение f ( x ) ⩾ m {displaystyle f(x)geqslant m} , где m {displaystyle m} — величина максимального потока, и решить задачу с новой функцией f ( x ) {displaystyle f(x)} — стоимостью потока.

Эти задачи могут быть решены быстрее, чем общими алгоритмами решения задач линейного программирования, за счёт особой структуры уравнений и неравенств.

Транспортная задача

Имеется некий однородный груз, который нужно перевезти с n {displaystyle n} складов на m {displaystyle m} заводов. Для каждого склада i {displaystyle i} известно, сколько в нём находится груза a i {displaystyle a_{i}} , а для каждого завода известна его потребность b j {displaystyle b_{j}} в грузе. Стоимость перевозки пропорциональна расстоянию от склада до завода (все расстояния c i j {displaystyle c_{ij}} от i {displaystyle i} -го склада до j {displaystyle j} -го завода известны). Требуется составить наиболее дешёвый план перевозки.

Решающими переменными в данном случае являются x i j {displaystyle x_{ij}} — количества груза, перевезённого из i {displaystyle i} -го склада на j {displaystyle j} -й завод. Они удовлетворяют ограничениям:

x i 1 + x i 2 + … + x i m ⩽ a i , {displaystyle x_{i1}+x_{i2}+ldots +x_{im}leqslant a_{i},} x 1 j + x 2 j + … + x n j ⩾ b j . {displaystyle x_{1j}+x_{2j}+ldots +x_{nj}geqslant b_{j}.}

Целевая функция имеет вид: f ( x ) = x 11 c 11 + x 12 c 12 + … + x n m c n m {displaystyle f(x)=x_{11}c_{11}+x_{12}c_{12}+ldots +x_{nm}c_{nm}} , которую надо минимизировать.

Игра с нулевой суммой

Есть матрица A {displaystyle A} размера n × m {displaystyle n imes m} . Первый игрок выбирает число от 1 до n {displaystyle n} , второй — от 1 до m {displaystyle m} . Затем они сверяют числа и первый игрок получает a i j {displaystyle a_{ij}} очков, а второй ( − a i j ) {displaystyle (-a_{ij})} очков ( i {displaystyle i} — число, выбранное первым игроком, j {displaystyle j} — вторым). Нужно найти оптимальную стратегию первого игрока.

Пусть в оптимальной стратегии, например, первого игрока число i {displaystyle i} нужно выбирать с вероятностью p i {displaystyle p_{i}} . Тогда оптимальная стратегия является решением следующей задачи линейного программирования:

0 ⩽ p i ⩽ 1 , {displaystyle 0leqslant p_{i}leqslant 1,} p 1 + … + p n = 1 , {displaystyle p_{1}+ldots +p_{n}=1,} a 1 i p 1 + a 2 i p 2 + … + a n i p n ⩾ c ( i = 1 , … , m ) , {displaystyle a_{1i}p_{1}+a_{2i}p_{2}+ldots +a_{ni}p_{n}geqslant cquad (i=1,;ldots ,;m),}

в которой нужно максимизировать функцию f ( p 1 , … , p n , c ) = c {displaystyle f(p_{1},;ldots ,;p_{n},;c)=c} . Значение c {displaystyle c} в оптимальном решении будет математическим ожиданием выигрыша первого игрока в наихудшем случае.

Алгоритмы решения

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

Первый полиномиальный алгоритм, метод эллипсоидов, был предложен в 1979 году советским математиком Л. Хачияном, разрешившим таким образом проблему, долгое время остававшуюся нерешённой. Метод эллипсоидов имеет совершенно другую, нежели симплекс-метод, некомбинаторную природу. Однако в вычислительном плане этот метод оказался неперспективным. Тем не менее, сам факт полиномиальной сложности задач привёл к созданию целого класса эффективных алгоритмов ЛП — методов внутренней точки, первым из которых был алгоритм Н. Кармаркара, предложенный в 1984 году. Алгоритмы этого типа используют непрерывную трактовку задачи ЛП, когда вместо перебора вершин многогранника решений задачи ЛП осуществляется поиск вдоль траекторий в пространстве переменных задачи, не проходящих через вершины многогранника. Метод внутренних точек, который, в отличие от симплекс-метода, обходит точки из внутренней части области допустимых значений, использует методы логарифмических барьерных функций нелинейного программирования, разработанные в 1960-х годах Фиако (Fiacco) и МакКормиком (McCormick).

Двойственные задачи линейного программирования

Каждой задаче линейного программирования вида

∑ j = 1 n a i j x j ⩽ c i , i = 1 , m ¯ ; {displaystyle sum _{j=1}^{n}a_{ij}x_{j}leqslant c_{i},;i={overline {1,;m}};} x j ⩾ 0 , j = 1 , n ¯ ; {displaystyle x_{j}geqslant 0,;j={overline {1,;n}};} F ( x ) = ∑ j = 1 n b j x j → max {displaystyle F(x)=sum _{j=1}^{n}b_{j}x_{j} o max }

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

Если вектора x {displaystyle x} и y {displaystyle y} — допустимые решения прямой и двойственной задачи, то F ( x ) ⩽ T ( y ) {displaystyle F(x)leqslant T(y)} , причём равенство достигается тогда и только тогда, когда x {displaystyle x} и y {displaystyle y} — оптимальные решения. Если же целевая функция одной из пары двойственных задач не ограничена (для исходной — сверху, для двойственной — снизу), то область допустимых решений другой задачи — пустая.

Если вектора x ∗ {displaystyle x^{*}} и y ∗ {displaystyle y^{*}} — оптимальные решения прямой и двойственной задачи, соответственно, то верны следующие равенства

x j ∗ ( ∑ i = 1 m a i j y i ∗ − b j ) = 0 , j = 1 , n ¯ ; {displaystyle x_{j}^{*}(sum _{i=1}^{m}a_{ij}y_{i}^{*}-b_{j})=0,;j={overline {1,;n}};} y i ∗ ( ∑ j = 1 n a i j x j ∗ − c i ) = 0 , i = 1 , m ¯ . {displaystyle y_{i}^{*}(sum _{j=1}^{n}a_{ij}x_{j}^{*}-c_{i})=0,;i={overline {1,;m}}.}

То есть, для оптимальных решений прямой и двойственной задачи, ненапряженным (выполняется строгое неравенство) ограничениям соответствуют нулевые переменные, а ненулевым переменным (входящим в опорный план) соответствуют напряжённые (нестрогое неравенство реализуется, как равенство) ограничения. Но могут быть и нулевые переменные, соответствующие напряжённым ограничениям.

Эти свойства двойственных решений позволяют существенно сократить время решения, если приходится решать задачу, с числом ограничений много большим количества переменных. Тогда можно, решив двойственную задачу, найти её опорный план, после чего, отобрав в прямой задаче только ограничения, соответствующие опорному плану (все эти ограничения должны быть напряжены), решить для них обычную систему линейных уравнений.

Программное обеспечение

lp_solve — открытое программное обеспечение (лицензия LGPL GNU Стандартная общественная лицензия GNU для библиотек) для решения линейных уравнений. LpSolve имеет IDE, собственный C API, и множество других программных интерфейсов для Java, AMPL, MATLAB, Wolfram Mathematica, O-Matrix, Sysquake, Scilab, Octave, FreeMat, Euler, Python, Sage, PHP, R и Microsoft Solver Foundation.