Изменения
[[файл:ТЗПП40.JPG|thumb|300|[[Математическая модель]] ТЗПП с ограничением по транзиту]]
'''Транспортная задача с промежуточными пунктами и ограничением по транзиту''' – это транспортная задача оптимизации перевозок с использованием промежуточных (транзитных) пунктов с возможностью ограничения транзита в наиболее перегруженном промежуточном пункте.
== Постановка задачи ==
В экономической транспортной системе имеются '''n''' конечных пунктов ('''np''' поставщиков продукции и '''(n-np)''' потребителей продукции) и '''m''' промежуточных пунктов (складов). Продукция перевозится от поставщиков на склады, будем обозначать эти перевозки положительными переменными '''x<sub>ij</sub>≥0, (i=1,m,j=1,np)'''. А со складов часть продукции перевозится потребителям - их обозначим отрицательными переменными '''x<sub>ij</sub>≤0, (i=1,m,j=np+1,n)'''. Объёмы поставок поставщиков обозначим положительными числами '''b<sub>j</sub>>0, (j=1,np),''' объёмы потребностей потребителей обозначим отрицательными числами '''b<sub>j</sub><0, (j=np+1,n)'''. Если склад имеет дополнительные (внутренние) потребности продукции, то обозначим их положительными числами '''a<sub>i</sub>>0, (i=1,mp)'''. Если склад имеет излишки продукции или нулевые остатки, то обозначим их числами '''a<sub>i</sub>≤0, (i=mp+1,m)'''. Транспортные тарифы на перевозку единицы продукции от поставщика на склад выразим положительными числами '''c<sub>ij</sub>>0, (i=1,m,j=1,np),''' транспортные тарифы на перевозку со склада к потребителю выразим отрицательными числами '''c<sub>ij</sub><0, (i=1,m,j=np+1,n)'''.
где '''x<sub>ij</sub>''' — объём перевозок продукта между промежуточным пунктом '''Ai''' и конечным пунктом '''Bj'''.
== Условия разрешимости ==
Для разрешимости задачи с ограничением по транзиту необходимо выполнение условий баланса:
то есть необходимо, чтобы алгебраическая сумма поставок на склады и отрицательных поставок со складов (потребностей в продукции) равнялась алгебраической сумме дополнительных потребностей в продукции на складах.
== Постановка вспомогательной задачи ==
Для случая перегруженного пункта с дополнительной потребностью '''a<sub>t</sub>>0''', введём дополнительный склад '''A<sub>m+1</sub>''' (“двойник” склада '''A<sub>t</sub>''') с избытком '''a<sub>m+1</sub>=-T''' и пересчитаем для склада '''A<sub>t</sub>''' дополнительную потребность '''a<sub>t</sub>=a<sub>t</sub>+T'''.
[[файл:ТЗПП43.JPG]].
== Решение вспомогательной задачи ==
Очевидно, что вспомогательная задача является закрытой '''[[Транспортная задача с промежуточными пунктами|транспортной задачей с промежуточными пунктами]]''', которая разрешима по построению.
Для определения начального решения используется '''[[алгоритм северо-западного угла|метод северо-западного угла]]''', а для решения применяется '''[[Транспортная задача с промежуточными пунктами|метод потенциалов]]'''.
Очевидно, что '''M'''-множители и метод потенциалов приводят к нулевым соответствующим (сверх установленного лимита '''T''' на транзит) перевозкам в оптимальном решении. В оптимальном решении вспомогательной задачи все перевозки через конечные и промежуточные пункты без складов «двойников» являются оптимальным решением исходной задачи. А перевозки складов «двойников» объединяются (складываются) в перевозки склада '''A<sub>t</sub>'''.
== Другие задачи: ==
*[[Транспортная задача с промежуточными пунктами]];
*[[Открытая транспортная задача с промежуточными пунктами 3]];
*[[Открытая транспортная задача с промежуточными пунктами 4]].
== Ссылки ==
* [http://www.magenta-technology.com/downloads/New%20Magenta%20Papers%202013%20vol2.pdf Krivopalov V.Y., Krivopalov Y.A. The potential method for solving the transportation problem with transit points. New Magenta Papers. Magenta Technology, 2013. — Vol.2 — P.31-38.]
* Кривопалов В. Ю., Метод северо-западного угла для нахождения допустимого решения транспортной задачи с промежуточными пунктами. Сборник конференции ПИТ-2014, СГАУ, стр.369-372. http://www.ssau.ru/files/events/2014/pit_14_1_6.pdf
* Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.
