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

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

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

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

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

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

Содержание

1 Математическая формулировка задачи линейного программирования
2 Примеры задач линейного программирования
3 Алгоритмы решения общей задачи линейного программирования
4 История
5 Ссылки

[править] Математическая формулировка задачи линейного программирования

Нужно максимизировать

$f(x)= \sum_{j=1}^n c_j x_j=c_1x_1+c_2x_2+\dots+c_nx_n$

при условиях

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

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

[править] Примеры задач линейного программирования

[править] Поток и паросочетание

Рассмотрим задачу о максимальном паросочетании: есть несколько юношей и девушек; для каждой пары известно, любят ли они друг друга. Нужно поженить максимальное число пар. Введем переменные $x i j$ — они соответствуют паре из $i$ -того юноши и $j$ -той девушки. Введем ограничения: $x_{ij}\ge 0$ , $x_{ij}\le 1$ , $x_{1i}+x_{2i}+\dots+x_{ni}\le 1$ , $x_{i1}+x_{i2}+\dots+x_{im}\le 1$ , $f=x_{11}+x_{12}+\dots+x_{nm}$ . Можно показать, что среди оптимальных решений этой задачи найдется целочисленное. Переменные, равные 1, будут соответствовать парам, которые следует поженить.

Вторая важная задача — максимальный поток. Пусть имеется граф (с ориентированными ребрами), в котором для каждого ребра указана его пропускная способность. И заданы 2 вершины: сток и исток. Нужно указать для каждого ребра, сколько через него будет протекать жидкости (не больше его пропускной способности) так, чтобы максимизировать суммарный поток из стока в исток (жидкость не может появляться или исчезать во всех вершинах, кроме стока и истока). Возьмем в качестве переменных $x i$ — количество жидкости, протекающих через $i$ -тое ребро. Тогда $x_i\ge 0$ , $x_i\le c_i$ , где $c i$ — пропускная способность $i$ -того ребра. Эти неравенства надо дополнить равенством количества втекающей и вытекающей жидкости для каждой вершины, кроме стока и истока. В качестве функции $f$ естественно взять разность между количеством вытекающей и втекающей жидкости в истоке.

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

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

[править] Транспортная задача

Имеется некий однородный груз, который нужно перевести с $n$ складов на $m$ заводов. Для каждого склада $i$ известно, сколько в нем находится груза $a i$ , а для каждого завода известна его потребность $b j$ в грузе. Стоимость перевозки пропорциональна расстоянию от склада до завода (все расстояния $c i j$ от $i$ -го склада до $j$ -го завода известны). Требуется составить наиболее дешевый план перевозки. Решающими переменными в данном случае являются $x i j$ — количества груза, перевезенного из $i$ -го склада на $j$ -й завод.

Ограничениями будут $x_{i1}+x_{i2}+\dots+x_{im}\le a_i$ и

$x_{1j}+x_{2j}+\dots+x_{nj}\ge b_j$ .

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

[править] Игра с нулевой суммой

Есть матрица $A$ размера $n\times m$ . Первый игрок выбирает число от 1 до $n$ , второй — от 1 до $m$ . Затем они сверяют числа и первый игрок получает $a i j$ очков, а второй $( - a i j)$ очков ( $i$ — число, выбранное первым игроком, $j$ — вторым). Нужно найти оптимальную стратегию первого игрока. Пусть в оптимальной стратегии число $i$ нужно выбирать с вероятностью $p i$ . Тогда оптимальная стратегия является решением следующей задачи линейного программирования: $p_i\ge 0$ , $p_i\le 1$ , $p_1+\dots+p_n=1$ , $a_{1i}p_1+a_{2i}p_2+\dots+a_{ni}p_n\ge c$ ( $i=1,\dots,m$ ), в которой нужно максимизировать функцию $f(p_1,\dots,p_n,c)=c$ . $c$ в оптимальном решении будет математическим ожиданием выигрыша первого игрока в наихудшем случае.

[править] Алгоритмы решения общей задачи линейного программирования

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

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

[править] История

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

Джордж Данциг разработал симплекс-метод и считается «отцом линейного программирования» на западе.

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

Категории: Геометрические алгоритмы | Исследование операций | Оптимизация

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

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

Содержание

[править] Математическая формулировка задачи линейного программирования

[править] Примеры задач линейного программирования

[править] Поток и паросочетание

[править] Транспортная задача

[править] Игра с нулевой суммой

[править] Алгоритмы решения общей задачи линейного программирования

[править] История

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

Views

Навигация

Участие

Поиск

На других языках