Трёхиндексная транспортная задача — различия между версиями
Fenikals (обсуждение | вклад) м (Снята защита с «Трёхиндексная транспортная задача»: Нарушений не было) |
|||
| (не показано 12 промежуточных версий 1 участника) | |||
| Строка 1: | Строка 1: | ||
[[файл:ТТЗ.JPG|thumb|300|[[Математическая модель]] ТТЗ]] | [[файл:ТТЗ.JPG|thumb|300|[[Математическая модель]] ТТЗ]] | ||
| + | '''Трёхиндексная транспортная задача (ТТЗ)''' – это многопродуктовая [[транспортная задача]] оптимизации перевозок, являющаяся трёхмерным обобщением транспортной задачи. | ||
== Постановка задачи ТТЗ == | == Постановка задачи ТТЗ == | ||
Пусть имеется '''m''' поставщиков '''(A1,A2,…,Am)''', '''n''' потребителей '''(B1,B2,…,Bn)''' и '''k''' различных продуктов '''(C1,C2,…,Ck)'''. Пусть заданы объёмы поставок '''a<sub>it</sub>''' продукта '''Ct''' поставщиком '''Ai''', объёмы потребностей '''b<sub>jt</sub>''' в продукте '''Ct''' у потребителя '''Bj''', объёмы перевозок '''c<sub>ij</sub>''' от поставщика '''Ai''' к потребителю '''Bj'''. Пусть известны транспортные расходы '''d<sub>ijt</sub>''' на перевозку единицы продукта '''Ct''' от поставщика '''Ai''' к потребителю '''Bj''' и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда трёхиндексная [[Транспортная задача с промежуточными пунктами|транспортная задача]] (ТТЗ) формулируется следующим образом: | Пусть имеется '''m''' поставщиков '''(A1,A2,…,Am)''', '''n''' потребителей '''(B1,B2,…,Bn)''' и '''k''' различных продуктов '''(C1,C2,…,Ck)'''. Пусть заданы объёмы поставок '''a<sub>it</sub>''' продукта '''Ct''' поставщиком '''Ai''', объёмы потребностей '''b<sub>jt</sub>''' в продукте '''Ct''' у потребителя '''Bj''', объёмы перевозок '''c<sub>ij</sub>''' от поставщика '''Ai''' к потребителю '''Bj'''. Пусть известны транспортные расходы '''d<sub>ijt</sub>''' на перевозку единицы продукта '''Ct''' от поставщика '''Ai''' к потребителю '''Bj''' и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда трёхиндексная [[Транспортная задача с промежуточными пунктами|транспортная задача]] (ТТЗ) формулируется следующим образом: | ||
| Строка 6: | Строка 7: | ||
где '''x<sub>ijt</sub>''' - объём перевозок продукта '''Ct''' от поставщика '''Ai''' к потребителю '''Bj'''. | где '''x<sub>ijt</sub>''' - объём перевозок продукта '''Ct''' от поставщика '''Ai''' к потребителю '''Bj'''. | ||
| − | |||
== Условия разрешимости == | == Условия разрешимости == | ||
Для разрешимости задачи необходимо выполнение условий баланса: | Для разрешимости задачи необходимо выполнение условий баланса: | ||
| Строка 12: | Строка 12: | ||
т.е. необходимо, чтобы объём поставок каждого продукта равнялся объёму потребностей в нём, чтобы объём поставок каждого поставщика равнялся объёму перевозок от него, чтобы объём потребностей каждого потребителя равнялся объёму перевозок к нему. | т.е. необходимо, чтобы объём поставок каждого продукта равнялся объёму потребностей в нём, чтобы объём поставок каждого поставщика равнялся объёму перевозок от него, чтобы объём потребностей каждого потребителя равнялся объёму перевозок к нему. | ||
| − | |||
== Метод решения ТТЗ == | == Метод решения ТТЗ == | ||
| − | Трёхиндексная [[транспортная задача]] решается методом потенциалов для решения транспортной задачи обобщённым на трёхмерный случай. | + | Трёхиндексная [[Классическая транспортная задача|транспортная задача]] решается методом потенциалов для решения транспортной задачи обобщённым на трёхмерный случай. |
| − | Пусть имеется допустимое опорное решение ТТЗ. Тогда метод потенциалов для ТТЗ принимает вид. | + | Пусть имеется допустимое опорное решение ТТЗ. Начальное допустимое опорное решение может быть получено с помощью '''[[Алгоритм минимального элемента для ТТЗ|алгоритма минимального элемента для ТТЗ]]'''. Тогда метод потенциалов для ТТЗ принимает вид. |
| − | + | ||
=== Метод потенциалов === | === Метод потенциалов === | ||
'''1.'''Берём допустимое опорное решение '''Xmxnxk''' и базис '''Zmxnxk'''. | '''1.'''Берём допустимое опорное решение '''Xmxnxk''' и базис '''Zmxnxk'''. | ||
| Строка 26: | Строка 24: | ||
'''4.'''Проверяем решение на оптимальность. Если '''Δo=0''', то решение '''Xmxnxk''' - оптимальное и конец работы, иначе определяем '''E<sup>+</sup>={(i,j,t)|Δ<sub>ijt</sub>>=0}'''. | '''4.'''Проверяем решение на оптимальность. Если '''Δo=0''', то решение '''Xmxnxk''' - оптимальное и конец работы, иначе определяем '''E<sup>+</sup>={(i,j,t)|Δ<sub>ijt</sub>>=0}'''. | ||
| − | '''5.'''Определяем оценку '''Δx''', элемент '''(i<sub>x</sub>,j<sub>x</sub>,t<sub>x</sub>)''' и новое опорное решение '''Xmxnxk''' с помощью '''алгоритма перераспределения перевозок для ТТЗ'''. Если нового допустимого опорного решения нет, то переходим к пункту 7. | + | '''5.'''Определяем оценку '''Δx''', элемент '''(i<sub>x</sub>,j<sub>x</sub>,t<sub>x</sub>)''' и новое опорное решение '''Xmxnxk''' с помощью '''[[Алгоритм перераспределения перевозок для ТТЗ|алгоритма перераспределения перевозок для ТТЗ]]'''. Если нового допустимого опорного решения нет, то переходим к пункту 7. |
'''6.'''Определяем новое значение целевой функции '''L=L-ΔoΔx''' и новый базис '''Bo=Bo\(i<sub>x</sub>,j<sub>x</sub>,t<sub>x</sub>)U(i<sub>o</sub>,j<sub>o</sub>,t<sub>o</sub>)'''. Переходим к пункту 3. | '''6.'''Определяем новое значение целевой функции '''L=L-ΔoΔx''' и новый базис '''Bo=Bo\(i<sub>x</sub>,j<sub>x</sub>,t<sub>x</sub>)U(i<sub>o</sub>,j<sub>o</sub>,t<sub>o</sub>)'''. Переходим к пункту 3. | ||
| Строка 32: | Строка 30: | ||
'''7.'''Переопределяем множество '''E<sup>+</sup>=E<sup>+</sup>\(i<sub>o</sub>,j<sub>o</sub>,t<sub>o</sub>)''' и определяем новую оценку '''Δo''' и элемент '''(i<sub>o</sub>,j<sub>o</sub>,t<sub>o</sub>)'''. | '''7.'''Переопределяем множество '''E<sup>+</sup>=E<sup>+</sup>\(i<sub>o</sub>,j<sub>o</sub>,t<sub>o</sub>)''' и определяем новую оценку '''Δo''' и элемент '''(i<sub>o</sub>,j<sub>o</sub>,t<sub>o</sub>)'''. | ||
Если новый элемент '''(i<sub>o</sub>,j<sub>o</sub>,t<sub>o</sub>)''' есть, то переходим к пункту 5, иначе конец работы. | Если новый элемент '''(i<sub>o</sub>,j<sub>o</sub>,t<sub>o</sub>)''' есть, то переходим к пункту 5, иначе конец работы. | ||
| − | |||
== Пример ТТЗ == | == Пример ТТЗ == | ||
[[файл:ТТЗ01.JPG]] | [[файл:ТТЗ01.JPG]] | ||
| − | |||
=== Допустимое решение === | === Допустимое решение === | ||
Допустимое решение '''X''' в транспортной таблице | Допустимое решение '''X''' в транспортной таблице | ||
| Строка 41: | Строка 37: | ||
[[файл:ТТЗ11.JPG]] | [[файл:ТТЗ11.JPG]] | ||
[[файл:ТТЗ10.JPG]] | [[файл:ТТЗ10.JPG]] | ||
| − | |||
=== Решение методом потенциалов === | === Решение методом потенциалов === | ||
[[файл:ТТЗ12.JPG]] | [[файл:ТТЗ12.JPG]] | ||
[[файл:ТТЗ13.JPG]] | [[файл:ТТЗ13.JPG]] | ||
[[файл:ТТЗ14.JPG]] | [[файл:ТТЗ14.JPG]] | ||
| − | + | == Задачи транспортного типа: == | |
| + | {{Список ЗТТ}} | ||
== Другие задачи: == | == Другие задачи: == | ||
| − | + | {{Список ЗМП}} | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
== Ссылки == | == Ссылки == | ||
* Емеличев В. А., Ковалев М. М., Кравцов М. К., Многогранники. Графы. Оптимизация. — М., 1981, стр.313 | * Емеличев В. А., Ковалев М. М., Кравцов М. К., Многогранники. Графы. Оптимизация. — М., 1981, стр.313 | ||
| − | * Кривопалов Ю.А. Метод потенциалов для решения трёхиндексной транспортной задачи. М.,ВИМИ, 1990г. деп.№Д08221. | + | * Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи. М.,ВИМИ, 1990г. деп.№Д08221. |
| + | * Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи. Сборник ХI конференции «Наука. Творчество» 2015, Самара, Т.1,стр.39. | ||
* [[Участник:Logic-samara]] | * [[Участник:Logic-samara]] | ||
[[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]] | [[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]] | ||
Текущая версия на 16:13, 7 июля 2017
Трёхиндексная транспортная задача (ТТЗ) – это многопродуктовая транспортная задача оптимизации перевозок, являющаяся трёхмерным обобщением транспортной задачи.
Содержание
Постановка задачи ТТЗ
Пусть имеется m поставщиков (A1,A2,…,Am), n потребителей (B1,B2,…,Bn) и k различных продуктов (C1,C2,…,Ck). Пусть заданы объёмы поставок ait продукта Ct поставщиком Ai, объёмы потребностей bjt в продукте Ct у потребителя Bj, объёмы перевозок cij от поставщика Ai к потребителю Bj. Пусть известны транспортные расходы dijt на перевозку единицы продукта Ct от поставщика Ai к потребителю Bj и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда трёхиндексная транспортная задача (ТТЗ) формулируется следующим образом:
,
где xijt - объём перевозок продукта Ct от поставщика Ai к потребителю Bj.
Условия разрешимости
Для разрешимости задачи необходимо выполнение условий баланса:
,
т.е. необходимо, чтобы объём поставок каждого продукта равнялся объёму потребностей в нём, чтобы объём поставок каждого поставщика равнялся объёму перевозок от него, чтобы объём потребностей каждого потребителя равнялся объёму перевозок к нему.
Метод решения ТТЗ
Трёхиндексная транспортная задача решается методом потенциалов для решения транспортной задачи обобщённым на трёхмерный случай. Пусть имеется допустимое опорное решение ТТЗ. Начальное допустимое опорное решение может быть получено с помощью алгоритма минимального элемента для ТТЗ. Тогда метод потенциалов для ТТЗ принимает вид.
Метод потенциалов
1.Берём допустимое опорное решение Xmxnxk и базис Zmxnxk.
2.Определяем значение целевой функции L=ΣΣΣdijtxijt и базис опорного решения Bo={(i,j,t)|zijt=1}.
3.Определяем оценку Δo и элемент (io,jo,to) с помощью алгоритма расчёта потенциалов для ТТЗ (также определяются оценки оптимальности Δijt).
4.Проверяем решение на оптимальность. Если Δo=0, то решение Xmxnxk - оптимальное и конец работы, иначе определяем E+={(i,j,t)|Δijt>=0}.
5.Определяем оценку Δx, элемент (ix,jx,tx) и новое опорное решение Xmxnxk с помощью алгоритма перераспределения перевозок для ТТЗ. Если нового допустимого опорного решения нет, то переходим к пункту 7.
6.Определяем новое значение целевой функции L=L-ΔoΔx и новый базис Bo=Bo\(ix,jx,tx)U(io,jo,to). Переходим к пункту 3.
7.Переопределяем множество E+=E+\(io,jo,to) и определяем новую оценку Δo и элемент (io,jo,to). Если новый элемент (io,jo,to) есть, то переходим к пункту 5, иначе конец работы.
Пример ТТЗ
Допустимое решение
Допустимое решение X в транспортной таблице
Решение методом потенциалов
Задачи транспортного типа:
- Транспортная задача;
- Распределительная задача;
- Задача о назначениях;
- Транспортная задача с промежуточными пунктами;
- Транспортная задача с промежуточными пунктами с запретами;
- Транспортная задача с промежуточными пунктами и ограничением по транзиту;
- Открытая транспортная задача с промежуточными пунктами 1;
- Открытая транспортная задача с промежуточными пунктами 2;
- Открытая транспортная задача с промежуточными пунктами 3;
- Открытая транспортная задача с промежуточными пунктами 4;
- Трёхиндексная транспортная задача.
Другие задачи:
Ссылки
- Емеличев В. А., Ковалев М. М., Кравцов М. К., Многогранники. Графы. Оптимизация. — М., 1981, стр.313
- Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи. М.,ВИМИ, 1990г. деп.№Д08221.
- Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи. Сборник ХI конференции «Наука. Творчество» 2015, Самара, Т.1,стр.39.
- Участник:Logic-samara
