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

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

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

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

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

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

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

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

Метод внутренних точек был впервые упомянут И. И. Дикиным в 1967 году.^[2]

Общей (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида^[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_{1i}+x_{2i}+\ldots +x_{ni}\leqslant 1,}$ 

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

с целевой функцией ${\displaystyle f=x_{11}+x_{12}+\ldots +x_{nm}}$ . Можно показать, что среди оптимальных решений этой задачи найдётся целочисленное. Переменные, равные 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}$  (${\displaystyle i=1,\;\ldots ,\;m}$ ),

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

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

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

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

${\displaystyle \sum _{j=1}^{n}a_{ij}x_{j}\leq c_{i},i=1,m;}$  ${\displaystyle x_{j}\geq 0,j=1,n;}$  ${\displaystyle F(x)=\sum _{j=1}^{n}b_{j}x_{j}\to \max }$ 

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

Если вектора ${\displaystyle x}$  и ${\displaystyle y}$  - допустимые решения прямой и двойственной задачи, то ${\displaystyle F(x)\leq 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=1,n;}$ 

${\displaystyle y_{i}^{*}(\sum _{j=1}^{n}a_{ij}x_{j}^{*}-c_{i})=0,i=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.

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

• Абрамов Л. М., Капустин В.Ф. Математическое программирование. — Учебное пособие. — Л.: ЛГУ, 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 с.
• Данциг Джордж Бернард «Воспоминания о начале линейного программирования»

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