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

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

Обозначения

$m$ — число поставщиков;

$n$ — число потребителей;

$k$ — число типов транспорта;

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

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

$u_{i}$ — потенциал поставщика $i,\forall i\in N_{m}$ ;

$v_{j}$ — потенциал потребителя $j,\forall j\in N_{n}$ ;

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle w_t} — потенциал транспорта типа Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle t,\forall t\in N_k}  ;

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

$\Delta _{ijt}$ — оценка оптимальности для перевозки Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle (i,j,t),\forall(i,j,t)\in{N_m\times N_n\times N_k}}  ;

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

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

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle D_{m\times n\times k}} — трёхмерная матрица тарифов $d_{ijt}$ ;

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

Алгоритм

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

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

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

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

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

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

6. Выбираем элемент Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle (i,j,t)\in S} (в порядке обратном поряду включения в стек). Вычисляем неизвестный потенциал по одной из формул $u_{i}=d_{ijt}-v_{j}-w_{t},v_{j}=d_{ijt}-u_{i}-w_{t},w_{t}=d_{ijt}-u_{i}-v_{j}$ .

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

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

9. $\Delta _{o}=\max \limits _{(i,j,t)\in {N_{m}\times N_{n}\times N_{k}}}\{\Delta _{ijt}\},(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.
• Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи — Сборник ХI конференции «Наука. Творчество» 2015, Самара, Т. 1, стр.39.