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

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

Обозначения

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

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

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

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

$\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

Алгоритм 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