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

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

Обозначения

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

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

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

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

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

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

Невозможно разобрать выражение (Ошибка преобразования. Сервер («https://wikimedia.org/api/rest_») сообщил: «Cannot get mml. Server problem.»): {\displaystyle v_{j}} — потенциал потребителя $j,\forall j\in N_{n}$ ;

Невозможно разобрать выражение (Ошибка преобразования. Сервер («https://wikimedia.org/api/rest_») сообщил: «Cannot get mml. Server problem.»): {\displaystyle c_{ij}} — транспортный тариф на перевозку $(i,j),\forall (i,j)\in {N_{m}\times N_{n}}$ ;

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

$C_{m\times n}$ — матрица транспортных тарифов Невозможно разобрать выражение (Ошибка преобразования. Сервер («https://wikimedia.org/api/rest_») сообщил: «Cannot get mml. Server problem.»): {\displaystyle c_{ij}} .

Алгоритм 1

Входные данные: Невозможно разобрать выражение (Ошибка преобразования. Сервер («https://wikimedia.org/api/rest_») сообщил: «Cannot get mml. Server problem.»): {\displaystyle m,n,B_{o},C_{m\times n}} .

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

2. Если $\exists (i,j)\in B_{o}$ с известным $u_{i}$ и неизвестным $v_{j}$ , то $v_{j}=c_{ij}-u_{i}$ и переходим к пункту 2.

3. Если $\exists (i,j)\in B_{o}$ с известным $v_{j}$ и неизвестным $u_{i}$ , то $u_{i}=c_{ij}-v_{j}$ и переходим к пункту 3.

4. Если $\exists (i,j)\in B_{o}$ с известным $u_{i}$ и неизвестным $v_{j}$ , то переходим к пункту 2.

5. $\Delta _{ij}=u_{i}+v_{j}-c_{ij},\forall (i,j)\in {N_{m}\times N_{n}}$ .

6.$\Delta _{o}=\max \limits _{(i,j)\in {N_{m}\times N_{n}}}\{\Delta _{ij}\},(i_{o},j_{o})=\arg\{\Delta _{o}\}$ .

Выходные данные: $\Delta _{o},(i_{o},j_{o})$ .

Алгоритм 2

Входные данные: Невозможно разобрать выражение (Ошибка преобразования. Сервер («https://wikimedia.org/api/rest_») сообщил: «Cannot get mml. Server problem.»): {\displaystyle m,n,B_{o},C_{m\times n}} .

Выходные данные: $\Delta _{o},(i_{o},j_{o})$.

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

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

Ссылки

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