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

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

Обозначения

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

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

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

$n-np$ — число потребителей;

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

$(i_{o},j_{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}}$ ;

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

$C_{m\times n}$ — матрица тарифов $c_{ij}$ .

Алгоритм 1

Алгоритм 2

• Заметим, что данный алгоритм применим для транспортной задачи, при этом np=n, а промежуточные пункты (склады) являются потребителями. Матрицы тарифов и оценок в алгоритме транспонированы (строки заменены на столбцы, а столбцы - на строки).

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

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

Литература

• Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.

Ссылки

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