Линейное программирование
Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах -мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
Линейное программирование (ЛП) является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование.
Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их.
История
[править | править код]Математические исследования отдельных экономических проблем, математическая формализация числового материала проводилась ещё в XIX веке. При математическом анализе процесса расширенного производства использовались алгебраические соотношения, анализ их проводился с помощью дифференциального исчисления. Это давало возможность получить общее представление о проблеме.
Развитие экономики потребовало количественных показателей, и в 1920 годы был создан межотраслевой баланс (МОБ). Он-то и послужил толчком в деле создания и исследования математических моделей. Разработка МОБ в 1924—1925 годах в СССР повлияла на работы экономиста и статистика Василия Васильевича Леонтьева. Он разработал межотраслевую модель производства и распределения продукции.
В 1938 году Леонид Витальевич Канторович в порядке научной консультации приступил к изучению чисто практической задачи по составлению наилучшего плана загрузки лущильных станков (фанерный трест). Эта задача не поддавалась обычным методам. Стало ясно, что задача не случайная.[1]
В 1939 году Леонид Канторович опубликовал работу «Математические методы организации и планирования производства», в которой сформулировал новый класс экстремальных задач с ограничениями и разработал эффективный метод их решения, таким образом были заложены основы линейного программирования.
Изучение подобных задач привело к созданию новой научной дисциплины линейного программирования и открыло новый этап в развитии экономико-математических методов.
В 1949 году американский математик Джордж Бернард Данциг разработал эффективный метод решения задач линейного программирования (ЗЛП) — симплекс-метод.[1]
Термин «программирование» нужно понимать в смысле «планирования» (один из переводов англ. programming). Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, ещё до того, как компьютеры были использованы для решения линейных задач оптимизации.
Метод внутренних точек был впервые упомянут И. И. Дикиным в 1967 году.[2]. Эти исследования были продолжены в том числе и отечественными учёными. В 1970-е годы В. Г. Жадану удалось получить основные результаты и разработать общий подход к построению методов внутренней точки для решения задач линейного и нелинейного программирования, основанный на преобразовании пространств; предложить барьерно-проективные и барьерно-ньютоновские численные методы.
Задачи
[править | править код]Общей (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида[3]:
Задача, в которой фигурируют ограничения в форме неравенств, называется основной задачей линейного программирования (ОЗЛП)
Задача линейного программирования будет иметь канонический вид, если в основной задаче вместо первой системы неравенств имеет место система уравнений с ограничениями в форме равенства[4]:
Основную задачу можно свести к канонической путём введения дополнительных переменных.
Задачи линейного программирования наиболее общего вида (задачи со смешанными ограничениями: равенствами и неравенствами, наличием переменных, свободных от ограничений) могут быть приведены к эквивалентным (имеющим то же множество решений) заменами переменных и заменой равенств на пару неравенств[5].
Легко заметить, что задачу нахождения максимума можно заменить задачей нахождения минимума, взяв коэффициенты с обратным знаком.
Примеры задач
[править | править код]Максимальное паросочетание
[править | править код]Рассмотрим задачу о максимальном паросочетании в двудольном графе: есть несколько юношей и девушек, причём для каждых юноши и девушки известно, симпатичны ли они друг другу. Нужно поженить максимальное число пар со взаимной симпатией.
Введём переменные , которые соответствуют паре из -го юноши и -й девушки и удовлетворяют ограничениям:
с целевой функцией, где равны 1 или 0 в зависимости от того, симпатичны ли -й юноша и -я девушка друг другу. Можно показать, что среди оптимальных решений этой задачи найдётся целочисленное. Переменные, равные 1, будут соответствовать парам, которые следует поженить.
Максимальный поток
[править | править код]Пусть имеется граф (с ориентированными рёбрами), в котором для каждого ребра указана его пропускная способность. И заданы две вершины: сток и исток. Нужно указать для каждого ребра, сколько через него будет протекать жидкости (не больше его пропускной способности) так, чтобы максимизировать суммарный поток из истока в сток (жидкость не может появляться или исчезать во всех вершинах, кроме истока и стока, соответственно).
Возьмём в качестве переменных — количество жидкости, протекающей через -е ребро. Тогда
где — пропускная способность -го ребра. Эти неравенства надо дополнить равенством количества втекающей и вытекающей жидкости для каждой вершины, кроме стока и истока. В качестве функции естественно взять разность между количеством вытекающей и втекающей жидкости в истоке.
Обобщение предыдущей задачи — максимальный поток минимальной стоимости. В этой задаче даны стоимости для каждого ребра и нужно среди максимальных потоков выбрать поток с минимальной стоимостью. Эта задача сводится к двум задачам линейного программирования: сначала нужно решить задачу о максимальном потоке, а потом добавить к этой задаче ограничение , где — величина максимального потока, и решить задачу с новой функцией — стоимостью потока.
Эти задачи могут быть решены быстрее, чем общими алгоритмами решения задач линейного программирования, за счёт особой структуры уравнений и неравенств.
Транспортная задача
[править | править код]Имеется некий однородный груз, который нужно перевезти с складов на заводов. Для каждого склада известно, сколько в нём находится груза , а для каждого завода известна его потребность в грузе. Стоимость перевозки пропорциональна расстоянию от склада до завода (все расстояния от -го склада до -го завода известны). Требуется составить наиболее дешёвый план перевозки.
Решающими переменными в данном случае являются — количества груза, перевезённого из -го склада на -й завод. Они удовлетворяют ограничениям:
Целевая функция имеет вид: , которую надо минимизировать.
Игра с нулевой суммой
[править | править код]Есть матрица размера . Первый игрок выбирает число от 1 до , второй — от 1 до . Затем они сверяют числа и первый игрок получает очков, а второй очков ( — число, выбранное первым игроком, — вторым). Нужно найти оптимальную стратегию первого игрока.
Пусть в оптимальной стратегии, например, первого игрока число нужно выбирать с вероятностью . Тогда оптимальная стратегия является решением следующей задачи линейного программирования:
в которой нужно максимизировать функцию . Значение в оптимальном решении будет математическим ожиданием выигрыша первого игрока в наихудшем случае.
Алгоритмы решения
[править | править код]Наиболее известным и широко применяемым на практике для решения общей задачи линейного программирования (ЛП) является симплекс-метод. Несмотря на то, что симплекс-метод является достаточно эффективным алгоритмом, показавшим хорошие результаты при решении прикладных задач ЛП, он является алгоритмом с экспоненциальной сложностью. Причина этого состоит в комбинаторном характере симплекс-метода, последовательно перебирающего вершины многогранника допустимых решений при поиске оптимального решения.
Первый полиномиальный алгоритм, метод эллипсоидов, был предложен в 1979 году советским математиком Л. Хачияном, разрешившим таким образом проблему, долгое время остававшуюся нерешённой. Метод эллипсоидов имеет совершенно другую, нежели симплекс-метод, некомбинаторную природу. Однако в вычислительном плане этот метод оказался неперспективным. Тем не менее, сам факт полиномиальной сложности задач привёл к созданию целого класса эффективных алгоритмов ЛП — методов внутренней точки, первым из которых был алгоритм Н. Кармаркара, предложенный в 1984 году. Алгоритмы этого типа используют непрерывную трактовку задачи ЛП, когда вместо перебора вершин многогранника решений задачи ЛП осуществляется поиск вдоль траекторий в пространстве переменных задачи, не проходящих через вершины многогранника. Метод внутренних точек, который, в отличие от симплекс-метода, обходит точки из внутренней части области допустимых значений, использует методы логарифмических барьерных функций нелинейного программирования, разработанные в 1960-х годах Фиако (Fiacco) и МакКормиком (McCormick).
Еще один метод решения ЛП - использование алгоритма Зейделя:
- Дана ЛП в канонической форме с переменными и ограничениями, составляющими множество .
- Если или , выведи оптимальное базисное решение .
- Иначе выбери случайное ограничение и рекурсивно рассчитай оптимальное базисное решение для .
- Если оптимальное базисное решение для не нарушает ограничение , верни его.
- Иначе рассчитай пересечение полиэдра ЛП с гиперплоскостью и рекурсивно реши получившуюся ЛП с переменной.
Данный метод имеет асимтотическую сложность .
Двойственные задачи линейного программирования
[править | править код]Каждой задаче линейного программирования[6] вида
можно определённым образом сопоставить некоторую другую задачу линейного программирования, называемую двойственной или сопряжённой по отношению к исходной или прямой. Связь исходной и двойственной задач заключается главным образом в том, что решение одной из них может быть получено непосредственно из решения другой. Дадим определение двойственной задачи по отношению к исходной задаче линейного программирования
Исходная задача | Двойственная задача |
---|---|
Если векторы и — допустимые решения прямой и двойственной задачи, то , причём равенство достигается тогда и только тогда, когда и — оптимальные решения. Если же целевая функция одной из пары двойственных задач не ограничена (для исходной — сверху, для двойственной — снизу), то область допустимых решений другой задачи — пустая.
Если векторы и — оптимальные решения прямой и двойственной задачи, соответственно, то верны следующие равенства
То есть для оптимальных решений прямой и двойственной задачи ненапряженным (выполняется строгое неравенство) ограничениям соответствуют нулевые переменные, а ненулевым переменным (входящим в опорный план) соответствуют напряжённые (нестрогое неравенство реализуется, как равенство) ограничения. Но могут быть и нулевые переменные, соответствующие напряжённым ограничениям.
Эти свойства двойственных решений позволяют существенно сократить время решения, если приходится решать задачу, с числом ограничений много большим количества переменных. Тогда можно, решив двойственную задачу, найти её опорный план, после чего, отобрав в прямой задаче только ограничения, соответствующие опорному плану (все эти ограничения должны быть напряжены), решить для них обычную систему линейных уравнений.
Теорема. Двойственная двойственной задачи ЛП является прямая задача ЛП.
Доказательство. Рассмотрим прямую ЛП вида при условии . Сопоставим ей двойственную ЛП и получим при условии . Приведем ее к другой форме, эквивалентной по смыслу: при условии . Вновь сопоставим ей двойственную ЛП и получим при условии . Приведем ее в эквивалентную форму и получим ЛП идентичную исходной: при условии .
Программное обеспечение
[править | править код]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 Источник: Алтайская краевая универсальная научная библиотека им. В. Я. Шишкова (АКУНБ) Архивная копия от 5 марта 2022 на Wayback Machine. Методы оптимизации: Учеб. пособие. Бразовская Н. В.; Алтайский государственный технический университет им. И. И. Ползунова, [Центр дистанц. обучения]. — Барнаул: Изд-во АлтГТУ, 2000. — 120 с. — ISBN 5-БНВ-МОр.9.00 — УДК/ББК 22.183.4 Б871.
- ↑ Дикин И. И. Итеративное решение задач линейного и квадратичного программирования // Докл. АН СССР. — 1967. — Т. 174, № 4. — С. 747—748.
- ↑ Карманов, 1986, с. 63.
- ↑ Карманов, 1986, с. 80.
- ↑ Карманов, 1986, с. 77.
- ↑ Электронный учебник «Экономико-математические методы». Двойственность в линейном программировании Архивная копия от 17 июня 2016 на Wayback Machine
Литература
[править | править код]- Абрамов Л. М., Капустин В. Ф. Математическое программирование. — Учебное пособие. — Л.: ЛГУ, 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 [4232 дня])
- Барсов А. С. Что такое линейное программирование // Популярные лекции по математике, Гостехиздат, 1959.
- Вялый М. Н. Линейные неравенства и комбинаторика. — МЦНМО, 2003.