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

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

Обозначения

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

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

Невозможно разобрать выражение (Ошибка преобразования. Сервер («https://wikimedia.org/api/rest_») сообщил: «Cannot get mml. Server problem.»): {\displaystyle \Delta _{x}} — перераспределяемая часть перевозки;

Невозможно разобрать выражение (Ошибка преобразования. Сервер («https://wikimedia.org/api/rest_») сообщил: «Cannot get mml. Server problem.»): {\displaystyle (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

Входные данные: Невозможно разобрать выражение (Ошибка преобразования. Сервер («https://wikimedia.org/api/rest_») сообщил: «Cannot get mml. Server problem.»): {\displaystyle 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$), то Невозможно разобрать выражение (Ошибка преобразования. Сервер («https://wikimedia.org/api/rest_») сообщил: «Cannot get mml. Server problem.»): {\displaystyle G=G\setminus (i,j)} и переходим к пункту 2.

3. Элемент $(i_{o},j_{o})$ помечается знаком Невозможно разобрать выражение (Ошибка преобразования. Сервер («https://wikimedia.org/api/rest_») сообщил: «Cannot get mml. Server problem.»): {\displaystyle +} .

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

5. Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \Delta_x = \min \limits_{(i, j)^ - \in {N_m \times N_n}} \{x_{ij} \}, (i_x, j_x) = \arg \{ \Delta_x \}} .

6. Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle x_{ij} = x_{ij} + \Delta_x, \forall (i, j)^+ \in G; x_{ij} = x_{ij} - \Delta_x, \forall (i, j)^- \in G} .

Выходные данные: Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \Delta_x, (i_x, j_x), X_{m \times n}} .

Алгоритм 2

Входные данные: Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle m, n, B_o, (i_o, j_o), X_{m \times n}} .

Выходные данные: Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \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