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

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

Обозначения

$m$ — число поставщиков $(m>1)$;

$n$ — число потребителей $(n>1)$;

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

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

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

$x_{ij}$ — объём перевозки $(i,j),\forall (i,j)\in {N_{m}\times N_{n}}$;

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

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

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

Алгоритм 1

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

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

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

3. Элемент $(i_{o},j_{o})$ помечается знаком $+$.

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

5. $\Delta _{x}=\min \limits _{(i,j)^{-}\in {N_{m}\times N_{n}}}\{x_{ij}\},(i_{x},j_{x})=\arg\{\Delta _{x}\}$.

6. $x_{ij}=x_{ij}+\Delta _{x},\forall (i,j)^{+}\in G;x_{ij}=x_{ij}-\Delta _{x},\forall (i,j)^{-}\in G$.

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

Алгоритм 2

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

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

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

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

Ссылки

• Участник:Logic-samara