Линейное программирование - Математическая формулировка

Интернет магазин китайских планшетных компьютеров

Компьютеры - Линейное программирование - Математическая формулировка

23 января 2011

Оглавление:
1. Линейное программирование
2. Математическая формулировка
3. Алгоритмы решения
4. История

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

$f=\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 также накладывается некоторый набор ограничений в виде равенств, но от них можно избавиться, последовательно выражая одну переменную через другие и подставляя её во всех остальных равенствах и неравенствах.

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

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

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

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

Введём переменные 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\geqslant m$ , где m — величина максимального потока, и решить задачу с новой функцией f — стоимостью потока.

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

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

Имеется некий однородный груз, который нужно перевести с n складов на m заводов. Для каждого склада i известно, сколько в нём находится груза a_i, а для каждого завода известна его потребность b_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_{11}c_{11}+x_{12}c_{12}+\ldots+x_{nm}c_{nm}$ , которую надо минимизировать.

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

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

Пусть в оптимальной стратегии, например, первого игрока число 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$ ,

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

<<< Задача о принадлежности точки многоугольнику

Метод эллипсоидов >>>

Компьютерное аппаратное обеспечение
Вычислительные комплексы
Компьютерные данные
Компьютерные журналы
Классы компьютеров
Компьютеры

Программное обеспечение
Производители компьютеров
Профессии в ИТ
Системное администрирование
Компьютерный сленг
Списки компьютерных терминов

Человеко-компьютерное взаимодействие