Специальный класс целочисленных задач о многопродуктовом потоке
Как отмечалось выше, общая задача о многопродуктовом потоке может не иметь целочисленного оптимального решения. Однако существует несколько классов этих задач, в которых матрицы ограничений являются унимодулярными, и, следовательно, целочисленные оптимальные решения существуют. Интересно отметить, что многие из этих задач могут быть сведены к эквивалентным задачам об однопродуктовом потоке, которые несложно решаются с помощью любого алгоритма для задачи о потоке минимальной стоимости.
Для многопродуктовой транспортной задачи известен следующий результат. Матрица ограничений в многопродуктовой транспортной задаче является унимодулярной в том и только в том случае, когда число источников 
или число стоков 
не превосходит 2. Этот результат гарантирует существование целочисленного оптимального решения в случае, если 
или 
независимо от числа продуктов. Очевидно, что если или равно 1, то решение тривиально. Однако, когда и , и превосходят 1, то возникает более общая задача линейного программирования. Покажем, что при этом существует более простой метод решения.
Введя слабые переменные 
в ограничения на пропускные способности дуг, переформулируем многопродуктовую транспортную задачу (5.2) следующим образом:
минимизировать
при условии,что
При = 2 данная задача сводится к следующей задаче линейного программирования:
минимизировать
при условии, что
Нетрудно заметить, что в равенствах (5.4)—(5.6) каждая из переменных 
появляется дважды: один раз со знаком плюс и один раз со знаком минус. Отметим также, что переменные 
входят только в равенства (5.7) и (5.8) (со знаком плюс). Поэтому можно рассматривать эти переменные как слабые и исключить их, записав (5.7) и (5.8) в виде
Величины, стоящие в правых частях равенств (5.4)—(5.6), представляют собой предложение (если они положительные) и спрос (если отрицательные). Равенства (5.4)—(5.6) описывают транспортную модель, сетевая структура которой показана на рис. 5.4.
Правые части равенств (5.7) и (5.8) представляют собой пропускные способности дуг, соответствующих неременным 
Для решения указанной задачи определяют оптимальные потоки . Затем из (5.7) и (5.8) могут быть найдены величины /
Интересно отметить, что исходная задача линейного программирования не имела форму сетевой задачи. Однако с помощью преобразования ограничений удалось свести ее к сетевой и тем самым существенно упростить решение.
Эта теория взята со страницы лекций по предмету «математическое программирование»:
Предмет математическое программирование
Возможно эти страницы вам будут полезны:
| Понятие о параметрическом программировании |
| Многопродуктовые потоки в сетях |
| Приближенное решение многопродуктовой транспортной задачи методом агрегирования |
| Приложения задач о многопродуктовом потоке |
