Трёхиндексная транспортная задача с промежуточными пунктами

Математическая модель ТТЗПП

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

Постановка задачи ТТЗПП

В экономической транспортной системе имеются n конечных пунктов (np поставщиков B1,B2,…,Bnp продукции и (n-np) потребителей Bnp+1,Bnp+2,…,Bn продукции), m промежуточных пунктов (складов A1,A2,…,Am) и k видов продукции (C1,C2,…,Ck). Продукция перевозится от поставщиков на склады, будем обозначать эти перевозки положительными переменными x_ijt≥0, (i=1,m,j=1,np,t=1,k). А со складов часть продукции перевозится потребителям – их обозначим отрицательными переменными x_ijt≤0, (i=1,m,j=np+1,n,t=1,k). Объёмы поставок поставщиков обозначим положительными числами b_jt>0, (j=1,np,t=1,k), объёмы потребностей потребителей обозначим отрицательными числами b_jt<0, (j=np+1,n). Если склад имеет дополнительные потребности продукции t-вида, то обозначим их положительными числами a_it>0, (i=1,mp,t=1,k). Если склад имеет излишки продукции или нулевые остатки, то обозначим их числами a_it≤0, (i=mp+1,m,t=1,k). Для упрощения метода решения задачи, будем считать, что склады имеющие дополнительные (внутренние) потребности продукции расположены вначале (в любом порядке) списка, а склады имеющие излишки продукции или нулевые остатки – в конце (в любом порядке). Транспортные тарифы на перевозку единицы продукции t-вида от i-поставщика на j-склад выразим положительными числами d_ijt>0, (i=1,m,j=1,np,t=1,k), транспортные тарифы на перевозку единицы продукции t-вида с i-склада к j-потребителю выразим отрицательными числами d_ijt<0, (i=1,m,j=np+1,n,t=1,k). Тогда ТТЗПП формулируется следующим образом:

$L(X)=\sum _{i=1}^{m}\sum _{j=1}^{n}\sum _{t=1}^{k}d_{ijt}x_{ijt}\rightarrow \min$

${\begin{cases}\sum \limits _{j=1}^{n}x_{ijt}=a_{it},\forall (i,t)\in N_{m}\times N_{k}\\\sum \limits _{i=1}^{m}x_{ijt}=b_{jt},\forall (j,t)\in N_{n}\times N_{k}\\\sum \limits _{t=1}^{k}x_{ijt}=c_{ij},\forall (i,j)\in N_{m}\times N_{n}\\x_{ijt}\geq 0,\forall (i,j,t)\in N_{m}\times N_{np}\times N_{k}\\x_{ijt}\leq 0,\forall (i,j,t)\in N_{m}\times (N_{n}\setminus N_{np})\times N_{k}\end{cases}}$,

где |x_ijt| — объём перевозок продукта Ct между промежуточным пунктом (складом) Ai и конечным пунктом (поставщиком или потребителем) Bj, знак x_ijt определяет направление перевозок.

Условия разрешимости

Для разрешимости задачи необходимо выполнение условий баланса:

$\sum _{i=1}^{m}a_{it}=\sum _{j=1}^{n}b_{jt},\forall t\in N_{k}$,

$\sum _{t=1}^{k}a_{it}=\sum _{j=1}^{n}c_{ij},\forall i\in N_{m}$,

$\sum _{t=1}^{k}b_{jt}=\sum _{i=1}^{m}c_{ij},\forall j\in N_{n}$.

Метод решения ТТЗПП

Трёхиндексная транспортная задача с промежуточными пунктами решается методом потенциалов для решения ТЗПП обобщённым на трёхмерный случай. Пусть имеется допустимое опорное решение ТТЗПП. Базис ТТЗПП содержит mn+mk+nk-m-n-k+1 базисных элементов. Тогда метод потенциалов для ТТЗПП принимает вид.

Метод потенциалов

1. Берём допустимое опорное решение Xmxnxk и базис Zmxnxk.

2. Определяем значение целевой функции L=ΣΣΣd_ijtx_ijt и базис опорного решения Bo={(i,j,t)|z_ijt=1}.

3. Определяем оценку Δo и элемент (i_o,j_o,t_o) с помощью алгоритма расчёта потенциалов для ТТЗПП (также определяются оценки оптимальности Δ_ijt).

4. Проверяем решение на оптимальность. Если Δo=0, то решение Xmxnxk – оптимальное и конец работы, иначе определяем E⁺={(i,j,t)|Δ_ijt≥0,j≤np}, E^-={(i,j,t)|Δ_ijt≤0,j>np}, E=E⁺UE^-\Bo.

5. Определяем оценку Δx, элемент (i_x,j_x,t_x) и новое опорное решение Xmxnxk с помощью алгоритма перераспределения перевозок для ТТЗПП. Если нового допустимого опорного решения нет, то переходим к пункту 7.

6. Определяем новое значение целевой функции L=L-ΔoΔx и новый базис Bo=Bo\(i_x,j_x,t_x)U(i_o,j_o,t_o). Переходим к пункту 3.

7. Переопределяем множество E=E\(i_o,j_o,t_o) и определяем новую оценку Δo и элемент (i_o,j_o,t_o) из множества E. Если новый элемент (i_o,j_o,t_o) есть, то переходим к пункту 5, иначе конец работы.

Другие задачи:

1. Транспортная задача;
2. Распределительная задача;
3. Задача о назначениях;
4. Транспортная задача с промежуточными пунктами;
5. Транспортная задача с промежуточными пунктами с запретами;
6. Транспортная задача с промежуточными пунктами и ограничением по транзиту;
7. Открытая транспортная задача с промежуточными пунктами;
8. Открытая транспортная задача с промежуточными пунктами 1;
9. Открытая транспортная задача с промежуточными пунктами 2;
10. Открытая транспортная задача с промежуточными пунктами 3;
11. Открытая транспортная задача с промежуточными пунктами 4;
12. Трёхиндексная транспортная задача;
13. Трёхиндексная транспортная задача с аксиальными суммами;
14. Трёхиндексная транспортная задача с промежуточными пунктами.

Литература

• Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи. М.,ВИМИ, 1990г. деп.№Д08221.
• Кривопалов В. Ю., Модель транспортной задачи с промежуточными пунктами в матричной постановке, «Вестник Самарского государственного аэрокосмического университета» № 3, 2012.
• Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.
• Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи. Сборник ХI конференции «Наука. Творчество» 2015, Самара, Т.1,стр.39.

Ссылки

• 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. Перевод статьи.