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

[[файл:ТЗПП.JPG|thumb|300|[[Математическая модель]] ТЗПП]]
[[файл:ТЗППэ.JPG|thumb|300|Математическая модель эквивалентной ТЗПП]]
[[файл:ТЗППк.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''' и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда [[Трёхиндексная транспортная задача|транспортная задача]] с промежуточными пунктами формулируется следующим образом:

[[файл:ТЗПП.JPG]],

где '''x<sub>ti</sub>''' — объём перевозок продукта от поставщика '''Ai''' на склад '''Ct''',

'''y<sub>tj</sub>''' — объём перевозок продукта со склада '''Ct''' к потребителю '''Bj'''.
== Условия разрешимости ==
Для разрешимости задачи необходимо выполнение условий баланса:

[[файл:ТЗПП02.JPG]],

то есть необходимо, чтобы объём поставок продукта поставщиками минус объём потребностей в нём у потребителей равнялся объёму дополнительных потребностей продукта на складе. В этом случае транспортная задача с промежуточными пунктами называется закрытой.
== Постановка эквивалентной задачи ==
Введём новые обозначения:

[[файл:ТЗПП2.JPG]].

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

[[файл:ТЗППэ.JPG]].
== Условия разрешимости эквивалентной задачи ==
Для разрешимости эквивалентной задачи необходимо выполнение условий баланса:

[[файл:ТЗПП03.JPG]],

то есть необходимо, чтобы объём поставок продукта на склады и объём отрицательных поставок со складов (потребностей в продукте) равнялся объёму дополнительных потребностей в продукте на складах. В этом случае транспортная задача с промежуточными пунктами называется закрытой.
== Постановка классической задачи ==
В экономической транспортной системе имеются '''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)'''. 
Тогда математическая модель задачи принимает вид:

[[файл:ТЗППк.JPG]].

Классическая [[транспортная задача]] с промежуточными пунктами может быть представлена в виде таблицы 

[[файл:ТЗПП0.png]].
== Условия разрешимости классической задачи ==
Для разрешимости классической задачи необходимо выполнение условий баланса:

[[файл:ТЗ02.JPG]],

то есть необходимо, чтобы алгебраическая сумма объёмов продукта промежуточных пунктов равнялась алгебраической сумме объёмов продукта конечных пунктов. В этом случае транспортная задача с промежуточными пунктами называется закрытой.
== Метод решения ТЗПП ==
Необходимо найти начальное опорное решение, например, методом северо-западного угла для ТЗПП.

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

'''1.'''Сначала удовлетворяем дополнительные потребности складов '''(a<sub>i</sub>>0)''' за счёт поставщиков '''(b<sub>j</sub>>0)''', т.е. назначаем соответствующие положительные перевозки по формулам: '''x<sub>ij</sub>=min(a<sub>i</sub>,b<sub>j</sub>), a<sub>i</sub>=a<sub>i</sub>-x<sub>ij</sub>, b<sub>j</sub>=b<sub>j</sub>-x<sub>ij</sub>'''.

'''2.'''Затем распределяем остатки грузов от поставщиков '''(b<sub>j</sub>>0)''' на последний используемый склад, т.е. начиная с последней заполненной строки по формулам: '''x<sub>ij</sub>=b<sub>j</sub>, a<sub>i</sub>=a<sub>i</sub>-x<sub>ij</sub>, b<sub>j</sub>=0'''.

'''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>)'''.
Переходим к пункту 3.
== Примеры ТЗПП: ==
=== Пример 1 ===
[[файл:ТЗПП001.png]]
==== Транспортная таблица ====
[[файл:ТЗПП011.png]]
==== Допустимое решение ====
[[файл:МП000.png]]

[[файл:МП010.png]]
==== Решение методом потенциалов ====
[[файл:МП001.png]]

[[файл:МП011.png]]

[[файл:МП002.png]]

[[файл:МП012.png]]

[[файл:МП003.png]]

[[файл:МП013.png]]
=== Пример 2 ===
[[файл:ТЗПП002.png]]
==== Транспортная таблица ====
[[файл:ТЗПП012.png]]
==== Допустимое решение ====
[[файл:МП200.png]]
[[файл:МП210.png]]
==== Решение методом потенциалов ====
[[файл:МП201.png]]

[[файл:МП211.png]]

[[файл:МП202.png]]

[[файл:МП212.png]]

[[файл:МП203.png]]

[[файл:МП213.png]]

[[файл:МП204.png]]

[[файл:МП214.png]]
=== Пример 3 ===
[[файл:ТЗПП01.png]]
==== Транспортная таблица ====
[[файл:СЗУ00.png]]
==== Нахождение допустимого решения ====
[[файл:СЗУ11.png]][[файл:СЗУ01.png]]

[[файл:СЗУ12.png]][[файл:СЗУ02.png]]

[[файл:СЗУ13.png]][[файл:СЗУ03.png]]

[[файл:СЗУ14.png]][[файл:СЗУ04.png]]

[[файл:СЗУ15.png]][[файл:СЗУ05.png]]

[[файл:СЗУ16.png]][[файл:СЗУ06.png]]

[[файл:СЗУ17.png]][[файл:СЗУ07.png]]

[[файл:СЗУ18.png]][[файл:СЗУ08.png]]

[[файл:СЗУ19.png]][[файл:СЗУ09.png]]

[[файл:СЗУ20.png]][[файл:СЗУ10.png]]

[[файл:СЗУ21.png]][[файл:СЗУ22.png]]

==== Допустимое решение ====
[[файл:МП00.png]]
[[файл:МП10.png]]
==== Решение методом потенциалов ====
[[файл:МП01.png]]

[[файл:МП11.png]]

[[файл:МП02.png]]

[[файл:МП12.png]]

[[файл:МП03.png]]

[[файл:МП13.png]]

[[файл:МП04.png]]

[[файл:МП14.png]]

[[файл:МП05.png]]

[[файл:МП15.png]]

[[файл:МП06.png]]

[[файл:МП16.png]]

[[файл:МП07.png]]

[[файл:МП17.png]]

[[файл:МП08.png]]

[[файл:МП18.png]]

[[файл:МП09.png]]

[[файл:МП19.png]]
== [[Транспортные задачи|Другие задачи:]] ==
{{Список ЗТТ}}
== Ссылки ==
*[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.
*[[Участник:Logic-samara]]
[[Категория:Математика]][[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]]