СЕТЕВАЯ ЗАДАЧА НЕОДНОРОДНАЯ

— модель математическая оптимального планирования перевозок неоднородных грузов по транспортной сети. Пусть из одних пунктов в другие необходимо осуществить перевозки неоднородных грузов по транспортной сети, связывающей эти пункты. Суммарные объемы перевозок на отдельных участках сети ограничены их пропускными способностями. Необходимо спланировать перевозки грузов так, чтобы минимизировать суммарные транспортные издержки. Задача планирования перевозок неоднородных грузов математически формулируется как спец. задача программирования нелинейного, называемая С. з. н.

Пусть пункту отнесено число , причем для . Если то пункт является поставщиком груза вида и в нем находится единиц этого груза. Если то пункт i является потребителем груза вида и ему нужно единиц этого груза. Если то пункт i является промежуточным для перевозок груза вида. Один и тот же пункт может быть поставщиком одного груза, потребителем другого и промежуточным пунктом для третьего груза. Пропускная способность участка, связывающего непосредственно пункт i с пунктом равна Пусть суммарные транспортные издержки по перевозке единиц груза 1-го зида, единиц груза 2-го вида, единиц груза вида. Числа определяют поток в сети неоднородный. Здесь сеть определяется графом где мн-во вершин, мн-во дуг, соответствующих участкам транспортной сети. Тогда С. з. н. заключается в отыскании неоднородного потока минимизирующего функционал

Этот поток наз. оптимальным. Следовательно, С. з. н. состоит в отыскании оптим. неоднородного потока. Если ф-ции непрерывно дифференцируемы и выпуклы вниз, то справедливы следующие условия оптимальности: неоднородный поток оптимален тогда и только тогда, когда для каждой вершины существуют числа р, называемые потенциалами, а для каждой насыщенной дуги которой неотрицательное, называемое дуговым, число , т. е. существуют такие числа, что для них справедливы соотношения:

где через обозначена частная производная ф-ции по .

На приведенных условиях оптимальности основан спец. итерационный метод решения С. з. н. - метод потенциалов. Сущность этого метода заключается в построении системы потенциалов и дуговых чисел для неоднородного потока, полученного на предыдущей итерации, и в последующем преобразовании его таким образом, что в результате получается новый неоднородный поток, связанный с меньшими суммарными транспортными издержками. Преобразование неоднородного потока производится путем его перераспределения вдоль одного цикла (если не выполняются условия типа ) или вдоль двух циклов (если не выполняются условия типа ). Начальный неоднородный поток выбирается произвольным. Если все ф-ции линейны, то С. з. н. наз. линейной многопродуктовой транспортной задачей на сети. В этом случае С. з. н. является спец. задачей программирования линейного с блочной структурой, и для ее решения могут быть применены декомпозиции методы.

Лит. см. к ст. Сетевая задача. И. М. Мельник.