Алгоритм расчёта потенциалов для трёхиндексной транспортной задачи с промежуточными пунктами

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

Обозначения

$m$ – число промежуточных пунктов (складов), $m>1$ ;

$n$ – число конечных пунктов (поставщиков и потребителей), $n>3$ ;

$np$ – число поставщиков (конечных пунктов c положительными значениями), $1<np<n$ ;

$k$ – число продуктов;

$\Delta _{o}$ — оценка оптимальности решения;

$(i_{o},j_{o},t_{o})$ — новая (оптимизирующая) перевозка (элемент);

$u_{it}$ — потенциал ряда $(i,t),\forall (i,t)\in {N_{m}\times N_{k}}$ ;

$v_{jt}$ — потенциал ряда $(j,t),\forall (j,t)\in {N_{n}\times N_{k}}$ ;

$w_{ij}$ — потенциал ряда $(i,j),\forall (i,j)\in {N_{m}\times N_{n}}$ ;

$d_{ijt}$ — стоимость (тариф) перевозки $(i,j,t),\forall (i,j,t)\in {N_{m}\times N_{n}\times N_{k}}$ ;

$\Delta _{ijt}$ — оценка оптимальности для перевозки $(i,j,t),\forall (i,j,t)\in {N_{m}\times N_{n}\times N_{k}}$ ;

$B_{o}$ — базис решения — множество базисных перевозок решения;

$G$ — вспомогательное множество базисных элементов решения $(i,j,t)$ ;

$S$ — стек-множество базисных элементов $(i,j,t)$ ;

$D_{m\times n\times k}$ — трёхмерная матрица тарифов $d_{ijt}$ ;

$O_{m\times n\times k}$ — трёхмерная матрица оценок оптимальности $\Delta _{ijt}$ .

Алгоритм

Входные данные: $m,n,np,k,B_{o},D_{m\times n\times k}$ .

1. $G=B_{o},S=\varnothing$ .

2. Если $\exists (i,j,t)\in G$ элемент, лежащий один хотя бы в одном ряду ( $(i,j)$ или $(i,t)$ или $(j,t)$ ), то выбираем его, иначе переходим к пункту 6.

3. Если для элемента $(i,j,t)$ по одному элементу во всех трёх рядах ( $(i,j)$ и $(i,t)$ и $(j,t)$ ), то $u_{it}=0,v_{jt}=0$ и переходим к пункту 5.

4. Если для элемента $(i,j,t)$ по одному элементу только в двух рядах, то если в ряду $(i,t)$ один элемент, то $u_{it}=0$ , иначе $v_{jt}=0$ .

5. $G=G\setminus (i,j,t),S=S\cup (i,j,t)$ . Если $G\neq \varnothing$ , то переходим к пункту 2.

6. Выбираем элемент $(i,j,t)\in S$ (в порядке обратном поряду включения в стек). Вычисляем неизвестный потенциал по одной из формул: $u_{it}=d_{ijt}-v_{jt}-w_{ij},v_{jt}=d_{ijt}-u_{it}-w_{ij},w_{ij}=d_{ijt}-u_{it}-v_{jt}$ .

7. Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S=S\setminus(i,j,t)} . Если $S\neq \varnothing$ , то переходим к пункту 6.

8. $\Delta _{ijt}=u_{it}+v_{jt}+w_{ij}-d_{ijt},\forall (i,j,t)\in {N_{m}\times N_{n}\times N_{k}}$ .

9. $\Delta _{1}=\max \limits _{(i,j,t)\in {N_{m}\times N_{np}\times N_{k}}}\{\Delta _{ijt}\},\Delta _{2}=-\min \limits _{(i,j,t)\in {N_{m}\times {(N_{n}\setminus N_{np})}\times N_{k}}}\{\Delta _{ijt}\},\Delta _{o}=\max\{\Delta _{1},\Delta _{2}\},(i_{o},j_{o},t_{o})=\arg\{\Delta _{o}\}$ .

Выходные данные: $\Delta _{o},(i_{o},j_{o},t_{o}),O_{m\times n\times k}$ .

Другие алгоритмы

1. Алгоритм метода потенциалов для ТЗ:
   1. алгоритм северо-западного угла для ТЗ;
   2. алгоритм минимального элемента для ТЗ;
   3. алгоритм расчёта потенциалов для ТЗ;
   4. алгоритм перераспределения перевозок для ТЗ;
2. Алгоритм метода потенциалов для ТЗПП:
   1. алгоритм северо-западного угла для ТЗПП;
   2. алгоритм расчёта потенциалов для ТЗПП;
   3. алгоритм перераспределения перевозок для ТЗПП;
   4. алгоритм решения ТЗПП с запретами;
3. Алгоритм метода потенциалов для ТТЗ:
   1. алгоритм минимального элемента для ТТЗ;
   2. алгоритм расчёта потенциалов для ТТЗ;
   3. алгоритм перераспределения перевозок для ТТЗ;
4. Алгоритм метода потенциалов для ТТЗАС:
   1. алгоритм трёхгранного угла для ТТЗАС;
   2. алгоритм расчёта потенциалов для ТТЗАС;
   3. алгоритм перераспределения перевозок для ТТЗАС;
5. Алгоритм метода потенциалов для ТТЗПП:
   1. алгоритм расчёта потенциалов для ТТЗПП;
   2. алгоритм перераспределения перевозок для ТТЗПП.

Литература

• Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи — М.: ВИМИ, 1990 г. деп. № Д08221.
• Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 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. Перевод статьи.