Учебно-методическое пособие для студентов специальности 1-36 20 02 «Упаковочное производство»

 
7.2.1. Максимальное сочетание пар 
Рассмотрим задачу о максимальном парасочетании в двудольном 
графе: есть несколько значений а и с. Нужно объединить макси-
мальное число пар. 
Введем переменные x
ij
, которые соответствуют паре из i-го зна-
чения и j-го значения и удовлетворяют ограничениям: 
0
1;
ij
x


1
2
...
1;
i
i
ni
x
x
x

 

1
2
...
1
i
i
im
x
x
x

 

с целевой функцией
11
12
...
.
nm
f
x
x
x


 
Можно показать, что среди оптимальных решений этой задачи 
найдется целочисленное. Переменные, равные 1, будут соответ-
ствовать парам, которые следует объединить. 
7.2.2. Максимальный поток 
Пусть имеется граф (с ориентированными ребрами), в котором 
для каждого ребра указана его пропускная способность и заданы 
две вершины: сток и исток. Для каждого ребра нужно указать, 
сколько через него будет протекать жидкости (не больше его про-
пускной способности), так чтобы максимизировать суммарный по-
ток из истока в сток (жидкость не может появляться или исчезать во 
всех вершинах, кроме стока и истока). 
В качестве переменных x
i
возьмем количество жидкости, проте-
кающей через i-е ребро. Тогда 
0
,
i
i
x
c


где c
i
– пропускная способность i-го ребра.

---

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