Изменения
[[файл:ТЗППэ.JPG|thumb|300|Математическая модель эквивалентной ТЗПП]]
[[файл:ТЗПП1.JPG|thumb|300|Математическая модель классической ТЗПП]]
'''Транспортная задача с промежуточными пунктами (ТЗПП)''' – это [[транспортная задача ]] оптимизации перевозок с использованием промежуточных (транзитных) пунктов. ТЗПП позволяет оптимизировать мультимодальные транспортные перевозки.
== Постановка задачи ТЗПП ==
Пусть имеется '''m''' поставщиков '''(A1,A2,…,Am)''', '''n''' потребителей '''(B1,B2,…,Bn)''' и '''k''' промежуточных пунктов '''(C1,C2,…,Ck)''', однородного продукта. Пусть заданы объёмы поставок '''a<sub>i</sub>''' продукта поставщиком '''Ai''', объёмы потребностей '''b<sub>j</sub>''' в продукте у потребителя '''Bj''', объёмы дополнительных потребностей '''c<sub>t</sub>''' в продукте в промежуточном пункте (на складе) '''Ct''', причём если '''c<sub>t</sub><0''', то дополнительные потребности являются избытком. Пусть известны транспортные расходы '''d<sub>ti</sub>''' на перевозку единицы продукта от поставщика '''Ai''' на склад '''Ct''', и транспортные расходы '''q<sub>tj</sub>''' на перевозку единицы продукта со склада '''Ct''' к потребителю '''Bj''' и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда [[Трёхиндексная транспортная задача|транспортная задача]] с промежуточными пунктами формулируется следующим образом:
'''3.'''Наконец, удовлетворяем потребности потребителей '''(b<sub>j</sub><0)''', т.е. назначаем соответствующие отрицательные перевозки по формулам: '''x<sub>ij</sub>=max(a<sub>i</sub>,b<sub>j</sub>), a<sub>ij</sub>=a<sub>i</sub>-x<sub>ij</sub>, b<sub>j</sub>=b<sub>j</sub>-x<sub>ij</sub>'''.
Метод северо-западного угла реализуется с помощью алгоритма северо-западного угладля ТЗПП.
=== Метод потенциалов ===
'''1.'''Берём решение '''Xmxn''' и базис '''Zmxn''', найденные с помощью '''[[алгоритм северо-западного угладля ТЗПП|алгоритма северо-западного угла]]'''.
'''2.'''Определяем значение целевой функции '''L=ΣΣc<sub>ij</sub>x<sub>ij</sub>''' и базис опорного решения '''Bo={(i,j)|z<sub>ij</sub>=1}'''.
'''3.'''Определяем оценку '''Δo''' и элемент '''(i<sub>o</sub>,j<sub>o</sub>)''' с помощью '''[[алгоритм расчёта потенциаловдля ТЗПП|алгоритма расчёта потенциалов]]''' и оценок оптимальности.
'''4.'''Проверяем решение на оптимальность. Если '''Δo=0''', то решение '''Xmxn''' - оптимальное и конец работы.
'''5.'''Определяем оценку '''Δx''', элемент '''(i<sub>x</sub>,j<sub>x</sub>)''' и новое опорное решение '''Xmxn''' с помощью '''[[алгоритм перераспределения перевозокдля ТЗПП|алгоритма перераспределения перевозок]]'''.
'''6.'''Определяем новое значение целевой функции '''L=L-ΔoΔx''' и новый базис '''Bo=Bo\(i<sub>x</sub>,j<sub>x</sub>)U(i<sub>o</sub>,j<sub>o</sub>)'''.
[[файл:МП03.JPG]]
[[файл:МП04.JPG]]
== Другие ТЗППЗадачи транспортного типа: ==*[[Транспортная задача с промежуточными пунктами с запретами]];*[[Транспортная задача с промежуточными пунктами и ограничением по транзиту]];*[[Открытая транспортная задача с промежуточными пунктами 1]];*[[Открытая транспортная задача с промежуточными пунктами 2]];*[[Открытая транспортная задача с промежуточными пунктами 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.
*[http://megapedia.wiki/wiki/Транспортная_задача_с_промежуточными_пунктами Подробное решение примера ТЗПП.]
* [[Участник:Logic-samara]]
[[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]]
