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

Разделы:

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

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

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

Содержание

1 История
2 Задачи
3 Примеры задач
4 Алгоритмы решения
5 Двойственные задачи линейного программирования
6 Программное обеспечение
7 См. также
8 Примечания
9 Литература
10 Ссылки

История

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

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

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

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

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

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

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

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

Задачи

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

f(x)=∑j=1ncjxj=c1x1+c2x2+…+cnxn{displaystyle f(x)=sum _{j=1}^{n}c_{j}x_{j}=c_{1}x_{1}+c_{2}x_{2}+ldots +c_{n}x_{n}}

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

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

∑j=1naijxj⩾bi(i=1,2,…,m){displaystyle sum _{j=1}^{n}a_{ij}x_{j}geqslant b_{i}quad (i=1,;2,;ldots ,;m)}

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

xj⩾0(j=1,2,…,n){displaystyle x_{j}geqslant 0quad (j=1,;2,;ldots ,;n)}

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

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

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

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

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

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

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

$c$ с обратным знаком.

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

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

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

Введём переменные xij{displaystyle x_{ij}}

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

0⩽xij⩽1,{displaystyle 0leqslant x_{ij}leqslant 1,}

0leqslant x_{{ij}}leqslant 1,

x1i+x2i+…+xni⩽1,{displaystyle x_{1i}+x_{2i}+ldots +x_{ni}leqslant 1,}

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

xi1+xi2+…+xim⩽1,{displaystyle x_{i1}+x_{i2}+ldots +x_{im}leqslant 1,}

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

с целевой функцией f=x11+x12+…+xnm{displaystyle f=x_{11}+x_{12}+ldots +x_{nm}}

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

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

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

Возьмём в качестве переменных xi{displaystyle x_{i}}

$x_{i}$ — количество жидкости, протекающей через i{displaystyle i} $i$ -е ребро. Тогда

0⩽xi⩽ci,{displaystyle 0leqslant x_{i}leqslant c_{i},}

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

где ci{displaystyle c_{i}}

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

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

$f(x)geqslant m$ , где m{displaystyle m} $m$ — величина максимального потока, и решить задачу с новой функцией f(x){displaystyle f(x)} $f(x)$ — стоимостью потока.

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

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

Имеется некий однородный груз, который нужно перевезти с n{displaystyle n}

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

Решающими переменными в данном случае являются xij{displaystyle x_{ij}}

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

xi1+xi2+…+xim⩽ai,{displaystyle x_{i1}+x_{i2}+ldots +x_{im}leqslant a_{i},}

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

x1j+x2j+…+xnj⩾bj.{displaystyle x_{1j}+x_{2j}+ldots +x_{nj}geqslant b_{j}.}

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

Целевая функция имеет вид: f(x)=x11c11+x12c12+…+xnmcnm{displaystyle f(x)=x_{11}c_{11}+x_{12}c_{12}+ldots +x_{nm}c_{nm}}

$f(x)=x_{{11}}c_{{11}}+x_{{12}}c_{{12}}+ldots +x_{{nm}}c_{{nm}}$ , которую надо минимизировать.

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

Есть матрица A{displaystyle A}

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

Пусть в оптимальной стратегии, например, первого игрока число i{displaystyle i}

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

0⩽pi⩽1{displaystyle 0leqslant p_{i}leqslant 1}

0leqslant p_{i}leqslant 1

p1+…+pn=1{displaystyle p_{1}+ldots +p_{n}=1}

p_{1}+ldots +p_{n}=1

a1ip1+a2ip2+…+anipn⩾c{displaystyle a_{1i}p_{1}+a_{2i}p_{2}+ldots +a_{ni}p_{n}geqslant c}

a_{{1i}}p_{1}+a_{{2i}}p_{2}+ldots +a_{{ni}}p_{n}geqslant c

(i=1,…,m{displaystyle i=1,;ldots ,;m}

i=1,;ldots ,;m

в которой нужно максимизировать функцию f(p1,…,pn,c)=c{displaystyle f(p_{1},;ldots ,;p_{n},;c)=c}

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

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

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

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

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

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

∑j=1naijxj≤ci,i=1,m;{displaystyle sum _{j=1}^{n}a_{ij}x_{j}leq c_{i},i=1,m;}

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

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

Исходная задача	Двойственная задача
∑j=1naijxj≤ci,i=1,m{displaystyle sum _{j=1}^{n}a_{ij}x_{j}leq c_{i},i=1,m} ${displaystyle sum _{j=1}^{n}a_{ij}x_{j}leq c_{i},i=1,m}$	yi≥0,i=1,m{displaystyle y_{i}geq 0,i=1,m} ${displaystyle y_{i}geq 0,i=1,m}$
xj≥0,j=1,n{displaystyle x_{j}geq 0,j=1,n} ${displaystyle x_{j}geq 0,j=1,n}$	∑i=1maijyi≥bj,j=1,n{displaystyle sum _{i=1}^{m}a_{ij}y_{i}geq b_{j},j=1,n} ${displaystyle sum _{i=1}^{m}a_{ij}y_{i}geq b_{j},j=1,n}$
F(x)=∑j=1nbjxj→max{displaystyle F(x)=sum _{j=1}^{n}b_{j}x_{j}to max } ${displaystyle F(x)=sum _{j=1}^{n}b_{j}x_{j}to max }$	T(y)=∑i=1mciyi→min{displaystyle T(y)=sum _{i=1}^{m}c_{i}y_{i}to min } ${displaystyle T(y)=sum _{i=1}^{m}c_{i}y_{i}to min }$

Если вектора x{displaystyle x}

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

Если вектора x∗{displaystyle x^{*}}

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

xj∗(∑i=1maijyi∗−bj)=0,j=1,n;{displaystyle x_{j}^{*}(sum _{i=1}^{m}a_{ij}y_{i}^{*}-b_{j})=0,j=1,n;}

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

yi∗(∑j=1naijxj∗−ci)=0,i=1,m.{displaystyle y_{i}^{*}(sum _{j=1}^{n}a_{ij}x_{j}^{*}-c_{i})=0,i=1,m.}

${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.

См. также

Примечания

↑ 1 2 Источник: Алтайская краевая универсальная научная библиотека им. В. Я. Шишкова (АКУНБ). Методы оптимизации: Учеб. пособие. Бразовская Н. В.; Алтайский государственный технический университет им. И. И. Ползунова, [Центр дистанц. обучения]. — Барнаул: Изд-во АлтГТУ, 2000. — 120 с. — ISBN 5-БНВ-МОр.9.00 — УДК/ББК 22.183.4 Б871.
↑ Дикин И. И. Итеративное решение задач линейного и квадратичного программирования // Докл. АН СССР. — 1967. — Т. 174, № 4. — С. 747-748.
↑ Карманов, 1986, с. 63.
↑ Карманов, 1986, с. 80.
↑ Карманов, 1986, с. 77.
↑ Электронный учебник «Экономико-математические методы». Двойственность в линейном программировании

Литература

Абрамов Л. М., Капустин В.Ф. Математическое программирование. — Учебное пособие. — Л.: ЛГУ, 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.