Для связи в whatsapp +905441085890

Специальный класс целочисленных задач о многопродуктовом потоке

Специальный класс целочисленных задач о многопродуктовом потоке

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

Для многопродуктовой транспортной задачи известен следующий результат. Матрица ограничений в многопродуктовой транспортной задаче является унимодулярной в том и только в том случае, когда число источников Специальный класс целочисленных задач о многопродуктовом потоке или число стоков Специальный класс целочисленных задач о многопродуктовом потоке не превосходит 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) могут быть найдены величины Специальный класс целочисленных задач о многопродуктовом потоке/

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

Эта теория взята со страницы лекций по предмету «математическое программирование»:

Предмет математическое программирование

Возможно эти страницы вам будут полезны:

Понятие о параметрическом программировании
Многопродуктовые потоки в сетях
Приближенное решение многопродуктовой транспортной задачи методом агрегирования
Приложения задач о многопродуктовом потоке