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

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

Обозначения

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

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

$c_{o}$ — минимальный элемент для не просмотренных клеток;

$a_{i}$ — объём поставок (продукции) поставщика $i,\forall i\in N_{m}$ ;

$b_{j}$ — объём потребностей (в продукции) потребителя $j,\forall j\in N_{n}$ ;

$c_{ij}$ — транспортный тариф на перевозку $(i,j),\forall (i,j)\in {N_{m}\times N_{n}}$ ;

$x_{ij}$ — объём перевозок $(i,j),\forall (i,j)\in {N_{m}\times N_{n}}$ ;

$z_{ij}$ — булева переменная обозначающая принадлежность перевозки к базису: $1$ — принадлежит базису, $0$ — не принадлежит базису, $\forall (i,j)\in {N_{m}\times N_{n}}$ ;

$E$ — множество не просмотренных клеток;

$A_{m}$ — вектор поставок $a_{i}$ ;

$B_{n}$ — вектор потребностей $b_{j}$ ;

$C_{m\times n}$ — матрица транспортных тарифов $c_{ij}$ ;

$X_{m\times n}$ — матрица перевозок $x_{ij}$ ;

$Z_{m\times n}$ — матрица базисных элементов $z_{ij}$ .

Алгоритм

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

1. $x_{ij}=0,z_{ij}=0,\forall (i,j)\in {N_{m}\times N_{n}},E=N_{m}\times N_{n}$ .

2. $c_{o}=\min \limits _{(i,j)\in E}\{c_{ij}\},(i,j)=\arg\{c_{o}\}$ .

3. $x_{ij}=\min\{a_{i},b_{j}\},a_{i}=a_{i}-x_{ij},b_{j}=b_{j}-x_{ij},z_{ij}=1$ .

4. Если $b_{j}>0$ , то $E=E\setminus \{(i,j)|\forall j\in N_{n}\}$ , иначе $E=E\setminus \{(i,j)|\forall i\in N_{m}\}$ .

5. Если $E\neq \varnothing$ , то переходим к пункту 2.

Выходные данные: $X_{m\times n},Z_{m\times n}$ .

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

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