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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

История[править | править вики-текст]

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

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

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

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

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

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

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

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

Задачи[править | править вики-текст]

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

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\geqslant b_i\quad (i=1,\;2,\;\ldots,\;m),
x_j\geqslant 0\quad (j=1,\;2,\;\ldots,\;n).

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

\sum_{j=1}^n a_{ij}x_j = b_i\quad (i=1,\;2,\;\ldots,\;m),

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

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

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

Примеры задач[править | править вики-текст]

Максимальное паросочетание[править | править вики-текст]

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

Введём переменные 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).

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

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

Ссылки[править | править вики-текст]