Теорема об интегральной стоимости минимального расхода

Question

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

l_i <= c_i <= u_i 

l_i, где находится нижняя граница пропускной способности края i и u_i верхняя граница. Для того чтобы теорема об интегральности имела место, достаточно ли, чтобы l_i and u_i были целыми числами? Уверенность возникает из-за того, что это не обязательно означает, что потоки всегда являются целыми числами, например, для l_i = 0, u_i = 1, край i может иметь поток 0,5.

Answer 1

Да, это именно то, что говорит теорема об интегральности.

Если все l_i и u_i представляют собой целые числа, и любой допустимое решение существует, то должна существовать решение, при котором все потоки являются целыми числами.

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