Транспортная задача с промежуточными пунктами и ограничением по транзиту

Материал из ALL
Перейти к: навигация, поиск
Математическая модель ТЗПП с ограничением по транзиту

Транспортная задача с промежуточными пунктами и ограничением по транзиту – это транспортная задача оптимизации перевозок с использованием промежуточных (транзитных) пунктов с возможностью ограничения транзита в наиболее перегруженном промежуточном пункте.

Постановка задачи

В экономической транспортной системе имеются n конечных пунктов (np поставщиков продукции и (n-np) потребителей продукции) и m промежуточных пунктов (складов). Продукция перевозится от поставщиков на склады, будем обозначать эти перевозки положительными переменными xij≥0, (i=1,m,j=1,np). А со складов часть продукции перевозится потребителям - их обозначим отрицательными переменными xij≤0, (i=1,m,j=np+1,n). Объёмы поставок поставщиков обозначим положительными числами bj>0, (j=1,np), объёмы потребностей потребителей обозначим отрицательными числами bj<0, (j=np+1,n). Если склад имеет дополнительные (внутренние) потребности продукции, то обозначим их положительными числами ai>0, (i=1,mp). Если склад имеет излишки продукции или нулевые остатки, то обозначим их числами ai≤0, (i=mp+1,m). Транспортные тарифы на перевозку единицы продукции от поставщика на склад выразим положительными числами cij>0, (i=1,m,j=1,np), транспортные тарифы на перевозку со склада к потребителю выразим отрицательными числами cij<0, (i=1,m,j=np+1,n).

Пусть T – это лимит транзита для перегружаемого склада At.

Тогда математическая модель задачи с ограничением по транзиту принимает вид:

ТЗПП40.JPG,

где xij — объём перевозок продукта между промежуточным пунктом Ai и конечным пунктом Bj.

Условия разрешимости

Для разрешимости задачи с ограничением по транзиту необходимо выполнение условий баланса:

ТЗ02.JPG,

то есть необходимо, чтобы алгебраическая сумма поставок на склады и отрицательных поставок со складов (потребностей в продукции) равнялась алгебраической сумме дополнительных потребностей в продукции на складах.

Постановка вспомогательной задачи

Для случая перегруженного пункта с дополнительной потребностью at>0, введём дополнительный склад Am+1 (“двойник” склада At) с избытком am+1=-T и пересчитаем для склада At дополнительную потребность at=at+T.

Пусть M — это достаточно большое положительное число.

Введём обозначения:

ТЗПП41.JPG.

Для случая перегруженного пункта с избытком at≤0, введём дополнительный склад Am+1 («двойник» склада At) с дополнительной потребностью am+1=T и пересчитаем для склада At дополнительную потребность at=at-T. Введём обозначения:

ТЗПП42.JPG.

Математическая модель вспомогательной задачи (в обоих случаях) принимает следующий вид:

ТЗПП43.JPG.

Решение вспомогательной задачи

Очевидно, что вспомогательная задача является закрытой транспортной задачей с промежуточными пунктами, которая разрешима по построению. Для определения начального решения используется метод северо-западного угла, а для решения применяется метод потенциалов. Очевидно, что M-множители и метод потенциалов приводят к нулевым соответствующим (сверх установленного лимита T на транзит) перевозкам в оптимальном решении. В оптимальном решении вспомогательной задачи все перевозки через конечные и промежуточные пункты без складов «двойников» являются оптимальным решением исходной задачи. А перевозки складов «двойников» объединяются (складываются) в перевозки склада At.

Другие задачи:

Ссылки