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

Поток и паросочетание

Рассмотрим задачу о максимальном паросочетании: есть несколько юношей и девушек; для каждой пары известно, любят ли они друг друга. Нужно поженить максимальное число пар. Введем переменные x_ij — они соответствуют паре из i-того юноши и j-той девушки. Введем ограничения: x _ij ≥ 0, x _ij ≤ 1, , , . Можно показать, что среди оптимальных решений этой задачи найдется целочисленное. Переменные, равные 1, будут соответствовать парам, которые следует поженить.

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

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

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

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

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

Ограничениями будут и

.

Целевая функция имеет вид: , которую надо минимизировать.

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

Есть матрица A размера . Первый игрок выбирает число от 1 до n, второй — от 1 до m. Затем они сверяют числа и первый игрок получает a_ij очков, а второй ( − a_ij) очков (i — число, выбранное первым игроком, j — вторым). Нужно найти оптимальную стратегию первого игрока. Пусть в оптимальной стратегии число i нужно выбирать с вероятностью p_i. Тогда оптимальная стратегия является решением следующей задачи линейного программирования: , , , ( ), в которой нужно максимизировать функцию . c в оптимальном решении будет математическим ожиданием выигрыша первого игрока в наихудшем случае.