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

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

Обозначения

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

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

$k$ — число типов транспорта;

$x_{ijt}$ — объём перевозок груза от поставщика $i$ к потребителю $j$ на транспорте типа $t,\forall (i,j,t)\in {N_{m}\times N_{n}\times N_{k}}$;

$z_{ijt}$ — булева переменная обозначающая принадлежность перевозки к базису: Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 1} — принадлежит базису, Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 0} — не принадлежит базису, $\forall (i,j,t)\in {N_{m}\times N_{n}\times N_{k}}$;

$A_{m}$ — вектор объёмов поставок поставщиков Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle a_i} ;

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle B_n} — вектор объёмов потребностей потребителей $b_{j}$;

$C_{k}$ — вектор объёмов перевозок по типам транспорта $c_{t}$;

$D_{m\times n\times k}$ — трёхмерная матрица тарифов $d_{ijt}$;

$X_{m\times n\times k}$ — трёхмерная матрица перевозок $x_{ijt}$;

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

Алгоритм

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

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

2. $x_{ijt}=\min\{a_{i},b_{j},c_{t}\},a_{i}=a_{i}-x_{ijt},b_{j}=b_{j}-x_{ijt},c_{t}=c_{t}-x_{ijt},z_{ijt}=1$.

3. Если $a_{i}=0$, то $i=i+1$, иначе если $b_{j}=0$, то $j=j+1$, иначе $t=t+1$.

4. Если $i\leq m$, то переходим к пункту 2.

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

• Заметим, что при выборе новой клетки $(i,j,t)$ необходимо увеличивать на единицу или индекс $i$, или индекс $j$, или индекс Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle t} .

Пример

Транспортная задача

Нахождение допустимого решения

Допустимое решение

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

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

Ссылки

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