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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \sum _{j=1}^{n}a_{ij}x_{j}\geqslant b_{i},\quad (i=1,\;2,\;\ldots ,\;m)}$

${\displaystyle x_{j}\geqslant 0.\quad (j=1,\;2,\;\ldots ,\;n)}$

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

${\displaystyle \sum _{j=1}^{n}a_{ij}x_{j}=b_{i}.\quad (i=1,\;2,\;\ldots ,\;m)}$

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

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

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

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

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

${\displaystyle 0\leqslant x_{ij}\leqslant 1,}$

${\displaystyle x_{1j}+x_{2j}+\ldots +x_{nj}\leqslant 1,}$

${\displaystyle x_{i1}+x_{i2}+\ldots +x_{im}\leqslant 1,}$

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

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

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

${\displaystyle 0\leqslant x_{i}\leqslant c_{i},}$

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

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

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

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

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

${\displaystyle x_{i1}+x_{i2}+\ldots +x_{im}\leqslant a_{i},}$

${\displaystyle x_{1j}+x_{2j}+\ldots +x_{nj}\geqslant b_{j}.}$

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

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

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

${\displaystyle 0\leqslant p_{i}\leqslant 1,}$

${\displaystyle p_{1}+\ldots +p_{n}=1,}$

${\displaystyle a_{1i}p_{1}+a_{2i}p_{2}+\ldots +a_{ni}p_{n}\geqslant c\quad (i=1,\;\ldots ,\;m),}$

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

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

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

Еще один метод решения ЛП - использование алгоритма Зейделя:

1. Дана ЛП в канонической форме с ${\displaystyle d}$ переменными и ${\displaystyle m}$ ограничениями, составляющими множество ${\displaystyle H}$.
2. Если ${\displaystyle d=1}$ или ${\displaystyle m=0}$, выведи оптимальное базисное решение ${\displaystyle H}$.
3. Иначе выбери случайное ограничение ${\displaystyle h\in H}$ и рекурсивно рассчитай оптимальное базисное решение для ${\displaystyle H\setminus \{h\}}$.
4. Если оптимальное базисное решение для ${\displaystyle H\setminus \{h\}}$ не нарушает ограничение ${\displaystyle h}$, верни его.
5. Иначе рассчитай пересечение полиэдра ЛП с гиперплоскостью ${\displaystyle h}$ и рекурсивно реши получившуюся ЛП с ${\displaystyle d-1}$ переменной.

Данный метод имеет асимтотическую сложность ${\displaystyle O(m\cdot d!)}$.

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

${\displaystyle \sum _{j=1}^{n}a_{ij}x_{j}\leqslant c_{i},\;i={\overline {1,\;m}};}$

${\displaystyle x_{j}\geqslant 0,\;j={\overline {1,\;n}};}$

${\displaystyle F(x)=\sum _{j=1}^{n}b_{j}x_{j}\to \max }$

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

Исходная задача	Двойственная задача
${\displaystyle \sum _{j=1}^{n}a_{ij}x_{j}\leqslant c_{i},\;i={\overline {1,\;m}}}$	${\displaystyle y_{i}\geqslant 0,\;i={\overline {1,\;m}}}$
${\displaystyle x_{j}\geqslant 0,\;j={\overline {1,\;n}}}$	${\displaystyle \sum _{i=1}^{m}a_{ij}y_{i}\geqslant b_{j},\;j={\overline {1,\;n}}}$
${\displaystyle F(x)=\sum _{j=1}^{n}b_{j}x_{j}\to \max }$	${\displaystyle T(y)=\sum _{i=1}^{m}c_{i}y_{i}\to \min }$

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

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

${\displaystyle x_{j}^{*}(\sum _{i=1}^{m}a_{ij}y_{i}^{*}-b_{j})=0,\;j={\overline {1,\;n}};}$

${\displaystyle y_{i}^{*}(\sum _{j=1}^{n}a_{ij}x_{j}^{*}-c_{i})=0,\;i={\overline {1,\;m}}.}$

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

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

Теорема. Двойственная двойственной задачи ЛП является прямая задача ЛП.

Доказательство. Рассмотрим прямую ЛП вида ${\displaystyle \max c^{T}}$ при условии ${\displaystyle Ax\leqslant b,x\geqslant 0}$. Сопоставим ей двойственную ЛП и получим ${\displaystyle \min b^{T}y}$ при условии ${\displaystyle A^{T}y\geqslant c,y\geqslant 0}$. Приведем ее к другой форме, эквивалентной по смыслу: ${\displaystyle \max -b^{T}y}$ при условии ${\displaystyle -A^{T}y\leqslant -c,y\geqslant 0}$. Вновь сопоставим ей двойственную ЛП и получим ${\displaystyle \min -c^{T}x}$ при условии ${\displaystyle -Ax\geqslant -b,x\geqslant 0}$. Приведем ее в эквивалентную форму и получим ЛП идентичную исходной: ${\displaystyle \max c^{T}}$ при условии ${\displaystyle Ax\leqslant b,x\geqslant 0}$.

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.

• Нелинейное программирование
• Алгоритм Данцига
• Графический метод решения задачи линейного программирования
• Дробно-линейное программирование
• Модель «затраты — выпуск»

• Абрамов Л. М., Капустин В. Ф. Математическое программирование. — Учебное пособие. — Л.: ЛГУ, 1981. — 328 с.
• Акоф Р., Сасиени М. Основы исследования операций. — Пер. с англ. В. Я. Алтаева., под ред. И. А. Ушакова. — М.: Мир, 1971. — 551 с.
• Акулич И. Л. Глава 1. Задачи линейного программирования, Глава 2. Специальные задачи линейного программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9.
• Астафьев Н. Н. Бесконечные системы линейных неравенств в математическом программировании. — М.: Наука, 1991. — 134 с.
• Ашманов С. А., Тимохов А. В. Теория оптимизации в задачах и упражнениях. — М.: Наука, 1991. — 446 с.
• Гасс С. Линейное программирование. — М.: Физико-математическая литература, 1961. — 300 с.
• Давыдов Э. Г. Исследование операций. — М.: Высшая школа, 1990. — 382 с.
• Дегтярёв Ю. И. Исследование операций. — Учебник для вузов. — М.: Высшая школа, 1986. — 320 с.
• Зуховицкий С. И., Авдеева Л. И. Линейное и выпуклое программирование. — М.: Наука, 1966. — 348 с.
• Карманов В. Г. Математическое программирование. — 3-е издание. — М.: Наука, 1986. — 288 с.
• Кузнецов А. В., Сакович В. А., Холод Н. И. Высшая математика. Математическое программирование. — Минск.: Вышейшая школа, 1994. — 286 с.
• Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 5-8459-0857-4.
• Юдин Д. Б., Гольштейн Е. Г. Линейное программирование. — М.: Наука, 1969. — 424 с.
• Данциг Дж. Б. Воспоминания о начале линейного программирования.
• Габасов Р., Кириллова Ф. М. Методы линейного программирования. — Минск: БГУ, 1977. — 176 с.

• Linear Program Solver (LiPS) — Бесплатный оптимизационный пакет, предназначенный для решения задач линейного, целочисленного и целевого программирования.
• Вершик А. М. O Л. В. Канторовиче и линейном программировании
• Слайды по линейному программированию
• Большакова И. В., Кураленко М. В. Линейное программирование. Учебно-методическое пособие к контрольной работе.  (недоступная ссылка с 13-05-2013 [4197 дней])
• Барсов А. С. Что такое линейное программирование // Популярные лекции по математике, Гостехиздат, 1959.
• Вялый М. Н. Линейные неравенства и комбинаторика. — МЦНМО, 2003.