Изменения
Новая страница: «[[файл:ТЗПП.JPG|thumb|300|[[Математическая модель]] ТЗПП]] файл:ТЗППэ.JPG|thumb|300|Математическая мод…»
[[файл:ТЗПП.JPG|thumb|300|[[Математическая модель]] ТЗПП]]
[[файл:ТЗППэ.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''' и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда [[Трёхиндексная транспортная задача|транспортная задача]] с промежуточными пунктами формулируется следующим образом:
[[файл:ТЗПП.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)'''.
Тогда математическая модель задачи принимает вид:
[[файл:ТЗПП1.JPG]].
[[Классическая транспортная задача]] с промежуточными пунктами может быть представлена в виде таблицы
[[файл:ТТ.JPG]].
== Условия разрешимости классической задачи ==
Для разрешимости классической задачи необходимо выполнение условий баланса:
[[файл:ТЗ02.JPG]],
то есть необходимо, чтобы алгебраическая сумма объёмов продукта промежуточных пунктов равнялась алгебраической сумме объёмов продукта конечных пунктов. В этом случае транспортная задача с промежуточными пунктами называется закрытой.
== Метод решения ТЗПП ==
Необходимо найти начальное опорное решение, например, методом северо-западного угла.
Затем транспортная задача с промежуточными пунктами решается обобщённым методом потенциалов для решения транспортной задачи модифицированным с учётом отрицательных перевозок.
=== Метод северо-западного угла ===
Метод северо-западного угла для нахождения допустимого решения транспортной задачи с промежуточными пунктами аналогичен одноимённому методу для транспортной задачи и состоит в последовательном назначении перевозок для клеток транспортной таблицы, находящихся в верхних (северных) строках и в левых (западных) столбцах. Процесс заполнения клеток (распределения перевозок) для ТЗПП осуществляется в три этапа и продолжается до тех пор пока у поставщиков имеются нераспределённые положительные остатки или у потребителей имеются неудовлетворённые отрицательные потребности.
'''1.'''Сначала удовлетворяем дополнительные потребности складов '''(a<sub>i</sub>>0)''' за счёт поставщиков '''(b<sub>j</sub>>0)''', т.е. назначаем соответствующие положительные перевозки по формулам: '''x<sub>ij</sub>=min(ai,bj), ai=ai-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.
== Пример ТЗПП ==
[[файл:СЗУ10.JPG]]
=== Нахождение допустимого решения ===
[[файл:СЗУ11.JPG]]
[[файл:СЗУ12.JPG]]
[[файл:СЗУ13.JPG]]
[[файл:СЗУ04.JPG]]
=== Решение методом потенциалов ===
[[файл:МП01.JPG]]
[[файл:МП02.JPG]]
[[файл:МП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.
* [[Участник:Logic-samara]]
[[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]]
[[файл:ТЗППэ.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''' и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда [[Трёхиндексная транспортная задача|транспортная задача]] с промежуточными пунктами формулируется следующим образом:
[[файл:ТЗПП.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)'''.
Тогда математическая модель задачи принимает вид:
[[файл:ТЗПП1.JPG]].
[[Классическая транспортная задача]] с промежуточными пунктами может быть представлена в виде таблицы
[[файл:ТТ.JPG]].
== Условия разрешимости классической задачи ==
Для разрешимости классической задачи необходимо выполнение условий баланса:
[[файл:ТЗ02.JPG]],
то есть необходимо, чтобы алгебраическая сумма объёмов продукта промежуточных пунктов равнялась алгебраической сумме объёмов продукта конечных пунктов. В этом случае транспортная задача с промежуточными пунктами называется закрытой.
== Метод решения ТЗПП ==
Необходимо найти начальное опорное решение, например, методом северо-западного угла.
Затем транспортная задача с промежуточными пунктами решается обобщённым методом потенциалов для решения транспортной задачи модифицированным с учётом отрицательных перевозок.
=== Метод северо-западного угла ===
Метод северо-западного угла для нахождения допустимого решения транспортной задачи с промежуточными пунктами аналогичен одноимённому методу для транспортной задачи и состоит в последовательном назначении перевозок для клеток транспортной таблицы, находящихся в верхних (северных) строках и в левых (западных) столбцах. Процесс заполнения клеток (распределения перевозок) для ТЗПП осуществляется в три этапа и продолжается до тех пор пока у поставщиков имеются нераспределённые положительные остатки или у потребителей имеются неудовлетворённые отрицательные потребности.
'''1.'''Сначала удовлетворяем дополнительные потребности складов '''(a<sub>i</sub>>0)''' за счёт поставщиков '''(b<sub>j</sub>>0)''', т.е. назначаем соответствующие положительные перевозки по формулам: '''x<sub>ij</sub>=min(ai,bj), ai=ai-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.
== Пример ТЗПП ==
[[файл:СЗУ10.JPG]]
=== Нахождение допустимого решения ===
[[файл:СЗУ11.JPG]]
[[файл:СЗУ12.JPG]]
[[файл:СЗУ13.JPG]]
[[файл:СЗУ04.JPG]]
=== Решение методом потенциалов ===
[[файл:МП01.JPG]]
[[файл:МП02.JPG]]
[[файл:МП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.
* [[Участник:Logic-samara]]
[[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]]
