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

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

Обозначения

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

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

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

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

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

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

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

$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}$ — матрица транспортных тарифов $c_{ij}$ .

Алгоритм 1

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

1. $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

Входные данные: $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