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

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

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

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

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

Математическая формулировка

Нужно определить максимум линейной целевой функции (линейной формы)

$f(x)=\sum_{j=1}^n c_jx_j=c_1x_1+c_2x_2+\ldots+c_nx_n$

при условиях

$\sum_{j=1}^n a_{ij}x_j\leqslant b_i$ при $i=1,\;2,\;\ldots,\;m$.

Иногда на $x_i$ также накладывается некоторый набор ограничений в виде равенств, но от них можно избавиться, последовательно выражая одну переменную через другие и подставляя её во всех остальных равенствах и неравенствах (а также в функции $f$).

Такую задачу называют «основной» или «стандартной» в линейном программировании.

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

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

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

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

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

$x_{1i}+x_{2i}+\ldots+x_{ni}\leqslant 1,$

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

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

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

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

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

$0\leqslant x_i\leqslant c_i$,

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

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

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

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

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

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

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

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

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

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

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

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

$0\leqslant p_i\leqslant 1$,

$p_1+\ldots+p_n=1$,

$a_{1i}p_1+a_{2i}p_2+\ldots+a_{ni}p_n\geqslant c$ ($i=1,\;\ldots,\;m$),

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

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

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

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

История

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

На западе «отцом линейного программирования» считается Джордж Данциг, который разработал симплекс-метод.^{[источник не указан 1025 дней]}

Впервые метод внутренних точек был упомянут И. И. Дикиным в 1967 году.

См. также

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

Литература

• Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 5-8459-0857-4
• Акулич И.Л. Глава 1. Задачи линейного программирования, Глава 2. Специальные задачи линейного программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9
• Данциг Джордж Бернард «Воспоминания о начале линейного программирования»

Ссылки

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