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

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

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

Определения

Гипотетический многогранник перераспределения (ГМП) - это множество узлов (элементов) целочисленной решётки N_mxN_nxN_k, содержащее в каждом ряду решётки не менее двух узлов. ГМП называется допустимым, если все его узлы можно пометить так, что в каждом ряду решётки число узлов со знаком "+" равно числу узлов со знаком "-". Очевидно, что в допустимом ГМП чётное число узлов в рядах. Все остальные ГМП будем считать недопустимыми.

Обозначения

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

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

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

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

$\Delta _{x}$ — перераспределяемая часть перевозки;

$(i_{o},j_{o},t_{o})$ — вводимая в базис перевозка;

$(i_{x},j_{x},t_{x})$ — выводимая из базиса перевозка;

$x_{ijt}$ — объём перевозок $t$ -продукта между $i$ -м промежуточным пунктом и $j$ -м конечным пунктом;

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

$G$ — вспомогательное множество для построения цикла перераспределения перевозок;

$X_{m\times n\times k}$ — трёхмерная матрица перевозок — текущее и новое решения.

Алгоритм

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

1. $G=B_{o}\cup (i_{o},j_{o},t_{o})$ .

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

3. Если $\exists$ ряд ( $(i,j)$ или $(i,t)$ или $(j,t)$ ), с нечётным числом элементов, $(i,j,t)\in G$ , то ГМП — недопустимый и конец работы (выход из алгоритма).

4. Если $j_{o}>np$ , то элемент $(i_{o},j_{o},t_{o})$ помечается знаком $-$ , иначе знаком $+$ .

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

6. Если $\exists$ ряд ( $(i,j)$ или $(i,t)$ или $(j,t)$ ), в котором разное число элементов с противоположными знаками, то ГМП — недопустимый и конец работы, иначе ГМП — допустимый.

7. $\Delta _{x1}=\min \limits _{(i,j,t)^{-}\in G,j\leq np}\{x_{ijt}\},\Delta _{x2}=-\max \limits _{(i,j,t)^{+}\in G,j>np}\{x_{ijt}\},\Delta _{x}=\min\{\Delta _{x1},\Delta _{x2}\},(i_{x},j_{x},t_{x})=\arg\{\Delta _{x}\}$ .

8. $x_{ijt}=x_{ijt}+\Delta _{x},\forall (i,j,t)^{+}\in G,x_{ijt}=x_{ijt}-\Delta _{x},\forall (i,j,t)^{-}\in G$ .

Выходные данные: $\Delta _{x},(i_{x},j_{x},t_{x}),X_{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. Перевод статьи.