Транспортная задача с промежуточными пунктами — различия между версиями
Строка 2: | Строка 2: | ||
[[файл:ТЗППэ.JPG|thumb|300|Математическая модель эквивалентной ТЗПП]] | [[файл:ТЗППэ.JPG|thumb|300|Математическая модель эквивалентной ТЗПП]] | ||
[[файл:ТЗПП1.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''' и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда [[Трёхиндексная транспортная задача|транспортная задача]] с промежуточными пунктами формулируется следующим образом: | Пусть имеется '''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''' и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда [[Трёхиндексная транспортная задача|транспортная задача]] с промежуточными пунктами формулируется следующим образом: | ||
Строка 10: | Строка 11: | ||
'''y<sub>tj</sub>''' — объём перевозок продукта со склада '''Ct''' к потребителю '''Bj'''. | '''y<sub>tj</sub>''' — объём перевозок продукта со склада '''Ct''' к потребителю '''Bj'''. | ||
− | |||
== Условия разрешимости == | == Условия разрешимости == | ||
Для разрешимости задачи необходимо выполнение условий баланса: | Для разрешимости задачи необходимо выполнение условий баланса: | ||
Строка 17: | Строка 17: | ||
то есть необходимо, чтобы объём поставок продукта поставщиками минус объём потребностей в нём у потребителей равнялся объёму дополнительных потребностей продукта на складе. В этом случае транспортная задача с промежуточными пунктами называется закрытой. | то есть необходимо, чтобы объём поставок продукта поставщиками минус объём потребностей в нём у потребителей равнялся объёму дополнительных потребностей продукта на складе. В этом случае транспортная задача с промежуточными пунктами называется закрытой. | ||
− | |||
== Постановка эквивалентной задачи == | == Постановка эквивалентной задачи == | ||
Введём новые обозначения: | Введём новые обозначения: | ||
Строка 26: | Строка 25: | ||
[[файл:ТЗППэ.JPG]]. | [[файл:ТЗППэ.JPG]]. | ||
− | |||
== Условия разрешимости эквивалентной задачи == | == Условия разрешимости эквивалентной задачи == | ||
Для разрешимости эквивалентной задачи необходимо выполнение условий баланса: | Для разрешимости эквивалентной задачи необходимо выполнение условий баланса: | ||
Строка 33: | Строка 31: | ||
то есть необходимо, чтобы объём поставок продукта на склады и объём отрицательных поставок со складов (потребностей в продукте) равнялся объёму дополнительных потребностей в продукте на складах. В этом случае транспортная задача с промежуточными пунктами называется закрытой. | то есть необходимо, чтобы объём поставок продукта на склады и объём отрицательных поставок со складов (потребностей в продукте) равнялся объёму дополнительных потребностей в продукте на складах. В этом случае транспортная задача с промежуточными пунктами называется закрытой. | ||
− | |||
== Постановка классической задачи == | == Постановка классической задачи == | ||
В экономической транспортной системе имеются '''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)'''. | В экономической транспортной системе имеются '''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)'''. | ||
Строка 40: | Строка 37: | ||
[[файл:ТЗПП1.JPG]]. | [[файл:ТЗПП1.JPG]]. | ||
− | + | [[Классическая транспортная задача]] с промежуточными пунктами может быть представлена в виде таблицы | |
[[файл:ТТ.JPG]]. | [[файл:ТТ.JPG]]. | ||
− | |||
== Условия разрешимости классической задачи == | == Условия разрешимости классической задачи == | ||
Для разрешимости классической задачи необходимо выполнение условий баланса: | Для разрешимости классической задачи необходимо выполнение условий баланса: | ||
Строка 50: | Строка 46: | ||
то есть необходимо, чтобы алгебраическая сумма объёмов продукта промежуточных пунктов равнялась алгебраической сумме объёмов продукта конечных пунктов. В этом случае транспортная задача с промежуточными пунктами называется закрытой. | то есть необходимо, чтобы алгебраическая сумма объёмов продукта промежуточных пунктов равнялась алгебраической сумме объёмов продукта конечных пунктов. В этом случае транспортная задача с промежуточными пунктами называется закрытой. | ||
− | |||
== Метод решения ТЗПП == | == Метод решения ТЗПП == | ||
Необходимо найти начальное опорное решение, например, методом северо-западного угла. | Необходимо найти начальное опорное решение, например, методом северо-западного угла. | ||
Затем транспортная задача с промежуточными пунктами решается обобщённым методом потенциалов для решения транспортной задачи модифицированным с учётом отрицательных перевозок. | Затем транспортная задача с промежуточными пунктами решается обобщённым методом потенциалов для решения транспортной задачи модифицированным с учётом отрицательных перевозок. | ||
− | |||
=== Метод северо-западного угла === | === Метод северо-западного угла === | ||
Метод северо-западного угла для нахождения допустимого решения транспортной задачи с промежуточными пунктами аналогичен одноимённому методу для транспортной задачи и состоит в последовательном назначении перевозок для клеток транспортной таблицы, находящихся в верхних (северных) строках и в левых (западных) столбцах. Процесс заполнения клеток (распределения перевозок) для ТЗПП осуществляется в три этапа и продолжается до тех пор пока у поставщиков имеются нераспределённые положительные остатки или у потребителей имеются неудовлетворённые отрицательные потребности. | Метод северо-западного угла для нахождения допустимого решения транспортной задачи с промежуточными пунктами аналогичен одноимённому методу для транспортной задачи и состоит в последовательном назначении перевозок для клеток транспортной таблицы, находящихся в верхних (северных) строках и в левых (западных) столбцах. Процесс заполнения клеток (распределения перевозок) для ТЗПП осуществляется в три этапа и продолжается до тех пор пока у поставщиков имеются нераспределённые положительные остатки или у потребителей имеются неудовлетворённые отрицательные потребности. | ||
Строка 66: | Строка 60: | ||
Метод северо-западного угла реализуется с помощью алгоритма северо-западного угла. | Метод северо-западного угла реализуется с помощью алгоритма северо-западного угла. | ||
− | |||
=== Метод потенциалов === | === Метод потенциалов === | ||
'''1.'''Берём решение '''Xmxn''' и базис '''Zmxn''', найденные с помощью '''[[алгоритм северо-западного угла|алгоритма северо-западного угла]]'''. | '''1.'''Берём решение '''Xmxn''' и базис '''Zmxn''', найденные с помощью '''[[алгоритм северо-западного угла|алгоритма северо-западного угла]]'''. | ||
Строка 80: | Строка 73: | ||
'''6.'''Определяем новое значение целевой функции '''L=L-ΔoΔx''' и новый базис '''Bo=Bo\(i<sub>x</sub>,j<sub>x</sub>)U(i<sub>o</sub>,j<sub>o</sub>)'''. | '''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. | Переходим к пункту 3. | ||
− | |||
== Пример ТЗПП == | == Пример ТЗПП == | ||
[[файл:СЗУ10.JPG]] | [[файл:СЗУ10.JPG]] | ||
− | |||
=== Нахождение допустимого решения === | === Нахождение допустимого решения === | ||
[[файл:СЗУ11.JPG]] | [[файл:СЗУ11.JPG]] | ||
Строка 89: | Строка 80: | ||
[[файл:СЗУ13.JPG]] | [[файл:СЗУ13.JPG]] | ||
[[файл:СЗУ04.JPG]] | [[файл:СЗУ04.JPG]] | ||
− | |||
=== Решение методом потенциалов === | === Решение методом потенциалов === | ||
[[файл:МП01.JPG]] | [[файл:МП01.JPG]] | ||
Строка 95: | Строка 85: | ||
[[файл:МП03.JPG]] | [[файл:МП03.JPG]] | ||
[[файл:МП04.JPG]] | [[файл:МП04.JPG]] | ||
− | |||
== Другие ТЗПП: == | == Другие ТЗПП: == | ||
*[[Транспортная задача с промежуточными пунктами с запретами]]; | *[[Транспортная задача с промежуточными пунктами с запретами]]; | ||
Строка 103: | Строка 92: | ||
*[[Открытая транспортная задача с промежуточными пунктами 3]]; | *[[Открытая транспортная задача с промежуточными пунктами 3]]; | ||
*[[Открытая транспортная задача с промежуточными пунктами 4]]. | *[[Открытая транспортная задача с промежуточными пунктами 4]]. | ||
− | |||
== Другие задачи: == | == Другие задачи: == | ||
*[[Каноническая задача]]; | *[[Каноническая задача]]; | ||
Строка 115: | Строка 103: | ||
*[[Задача целочисленного программирования]]; | *[[Задача целочисленного программирования]]; | ||
*[[Задача о рюкзаке]]. | *[[Задача о рюкзаке]]. | ||
− | |||
== Ссылки == | == Ссылки == | ||
− | * [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.] | + | * [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, СГАУ, стр.369-372. http://www.ssau.ru/files/events/2014/pit_14_1_6.pdf | ||
* Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29. | * Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29. | ||
* [[Участник:Logic-samara]] | * [[Участник:Logic-samara]] | ||
[[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]] | [[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]] |
Версия 18:44, 13 января 2016
Транспортная задача с промежуточными пунктами (ТЗПП) – это транспортная задача оптимизации перевозок с использованием промежуточных (транзитных) пунктов. ТЗПП позволяет оптимизировать мультимодальные транспортные перевозки.
Содержание
Постановка задачи ТЗПП
Пусть имеется m поставщиков (A1,A2,…,Am), n потребителей (B1,B2,…,Bn) и k промежуточных пунктов (C1,C2,…,Ck), однородного продукта. Пусть заданы объёмы поставок ai продукта поставщиком Ai, объёмы потребностей bj в продукте у потребителя Bj, объёмы дополнительных потребностей ct в продукте в промежуточном пункте (на складе) Ct, причём если ct<0, то дополнительные потребности являются избытком. Пусть известны транспортные расходы dti на перевозку единицы продукта от поставщика Ai на склад Ct, и транспортные расходы qtj на перевозку единицы продукта со склада Ct к потребителю Bj и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда транспортная задача с промежуточными пунктами формулируется следующим образом:
где xti — объём перевозок продукта от поставщика Ai на склад Ct,
ytj — объём перевозок продукта со склада Ct к потребителю Bj.
Условия разрешимости
Для разрешимости задачи необходимо выполнение условий баланса:
то есть необходимо, чтобы объём поставок продукта поставщиками минус объём потребностей в нём у потребителей равнялся объёму дополнительных потребностей продукта на складе. В этом случае транспортная задача с промежуточными пунктами называется закрытой.
Постановка эквивалентной задачи
Введём новые обозначения:
Математическая модель эквивалентной задачи принимает следующий вид:
Условия разрешимости эквивалентной задачи
Для разрешимости эквивалентной задачи необходимо выполнение условий баланса:
то есть необходимо, чтобы объём поставок продукта на склады и объём отрицательных поставок со складов (потребностей в продукте) равнялся объёму дополнительных потребностей в продукте на складах. В этом случае транспортная задача с промежуточными пунктами называется закрытой.
Постановка классической задачи
В экономической транспортной системе имеются 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). Тогда математическая модель задачи принимает вид:
Классическая транспортная задача с промежуточными пунктами может быть представлена в виде таблицы
Условия разрешимости классической задачи
Для разрешимости классической задачи необходимо выполнение условий баланса:
то есть необходимо, чтобы алгебраическая сумма объёмов продукта промежуточных пунктов равнялась алгебраической сумме объёмов продукта конечных пунктов. В этом случае транспортная задача с промежуточными пунктами называется закрытой.
Метод решения ТЗПП
Необходимо найти начальное опорное решение, например, методом северо-западного угла.
Затем транспортная задача с промежуточными пунктами решается обобщённым методом потенциалов для решения транспортной задачи модифицированным с учётом отрицательных перевозок.
Метод северо-западного угла
Метод северо-западного угла для нахождения допустимого решения транспортной задачи с промежуточными пунктами аналогичен одноимённому методу для транспортной задачи и состоит в последовательном назначении перевозок для клеток транспортной таблицы, находящихся в верхних (северных) строках и в левых (западных) столбцах. Процесс заполнения клеток (распределения перевозок) для ТЗПП осуществляется в три этапа и продолжается до тех пор пока у поставщиков имеются нераспределённые положительные остатки или у потребителей имеются неудовлетворённые отрицательные потребности.
1.Сначала удовлетворяем дополнительные потребности складов (ai>0) за счёт поставщиков (bj>0), т.е. назначаем соответствующие положительные перевозки по формулам: xij=min(ai,bj), ai=ai-xij, bj=bj-xij.
2.Затем распределяем остатки грузов от поставщиков (bj>0) на последний используемый склад, т.е. начиная с последней заполненной строки по формулам: xij=bj, ai=ai-xij, bj=0.
3.Наконец, удовлетворяем потребности потребителей (bj<0), т.е. назначаем соответствующие отрицательные перевозки по формулам: xij=max(ai,bj), aij=ai-xij, bj=bj-xij.
Метод северо-западного угла реализуется с помощью алгоритма северо-западного угла.
Метод потенциалов
1.Берём решение Xmxn и базис Zmxn, найденные с помощью алгоритма северо-западного угла.
2.Определяем значение целевой функции L=ΣΣcijxij и базис опорного решения Bo={(i,j)|zij=1}.
3.Определяем оценку Δo и элемент (io,jo) с помощью алгоритма расчёта потенциалов и оценок оптимальности.
4.Проверяем решение на оптимальность. Если Δo=0, то решение Xmxn - оптимальное и конец работы.
5.Определяем оценку Δx, элемент (ix,jx) и новое опорное решение Xmxn с помощью алгоритма перераспределения перевозок.
6.Определяем новое значение целевой функции L=L-ΔoΔx и новый базис Bo=Bo\(ix,jx)U(io,jo). Переходим к пункту 3.
Пример ТЗПП
Нахождение допустимого решения
Решение методом потенциалов
Другие ТЗПП:
- Транспортная задача с промежуточными пунктами с запретами;
- Транспортная задача с промежуточными пунктами и ограничением по транзиту;
- Открытая транспортная задача с промежуточными пунктами 1;
- Открытая транспортная задача с промежуточными пунктами 2;
- Открытая транспортная задача с промежуточными пунктами 3;
- Открытая транспортная задача с промежуточными пунктами 4.
Другие задачи:
- Каноническая задача;
- Производственная задача;
- Общая прямая задача линейного программирования;
- Общая двойственная задача линейного программирования;
- Транспортная задача;
- Распределительная задача;
- Задача о назначениях;
- Трёхиндексная транспортная задача;
- Задача целочисленного программирования;
- Задача о рюкзаке.
Ссылки
- 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