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

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

Обозначения

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

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

k – число продуктов;

A_i - i-ый поставщик, 1≤i≤m;

B_j - j-ый потребитель, 1≤j≤n;

C_t - t-ый продукт, 1≤t≤k;

a_it - объём поставок продукта Сt от поставщика Ai;

b_jt - объём потребностей в продукте Сt у потребителя Bj;

c_ij - объём перевозок от поставщика Ai к потребителю Bj;

d_ijt - транспортные расходы d_ijt на перевозку единицы (тариф) продукта Ct от поставщика Ai к потребителю Bj;

x_ijt - объём перевозок продукта Ct от поставщика Ai к потребителю Bj;

B₀ – базис решения (множество базисных элементов (i,j,t));

do – минимальный тариф на множестве E;

(i₀, j₀, t₀) – элемент с тарифом do и перевозкой равной нулю (до перераспределения);

Δx – перераспределяемая часть перевозки;

(i_x, j_x, t_x) – элемент с перевозкой равной приращению Δx (до перераспределения).

Алгоритм

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

1. $q=\min\{\sum _{i=1}^{m}\min\{\sum _{t=1}^{k}a_{it},\sum _{j=1}^{n}c_{ij}\},\sum _{j=1}^{n}\min\{\sum _{t=1}^{k}b_{jt},\sum _{i=1}^{m}c_{ij}\},\sum _{t=1}^{k}\min\{\sum _{i=1}^{m}a_{it},\sum _{j=1}^{n}b_{jt}\}\}$ .

2. $x_{in+1t}=a_{it},\forall (i,t)\in N_{m}\times N_{k},x_{m+1jt}=b_{jt},\forall (j,t)\in N_{n}\times N_{k},x_{ijk+1}=c_{ij},\forall (i,j)\in N_{m}\times N_{n},x_{m+1n+1k+1}=q$ .

3. $E=N_{m}\times N_{n}\times N_{k},B_{o}=(N_{m+1}\times N_{n+1}\times N_{k+1})\setminus E$ .

4. $d_{o}=\min \limits _{(i,j,t)\in E}\{d_{ijt}\},(i_{o},j_{o},t_{o})=\arg\{d_{o}\}$ .

5. $\Delta _{x}=\min\{x_{i_{o}n+1t_{o}},x_{m+1j_{o}t_{o}},x_{i_{o}j_{o}k+1}\},(i_{x},j_{x},t_{x})=\arg\{\Delta _{x}\}$ .

6. $x_{ijt}=x_{ijt}+\Delta _{x},\forall (i,j,t)^{+}\in {\{(i_{o},j_{o},t_{o}),(i_{o},n+1,k+1),(m+1,j_{o},k+1),(m+1,n+1,t_{o})\}}$ ,

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle x_{ijt}=x_{ijt}-\Delta_x,\forall(i,j,t)^-\in{\{(i_o,n+1,t_o),(m+1,j_o,t_o),(i_o,j_o,k+1),(m+1,n+1,k+1)\}}} .

7. $B_{o}=B_{o}\setminus (i_{x},j_{x},t_{x})\cup (i_{o},j_{o},t_{o})$ .

8.Если Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle i_x={m+1}} , то Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle E=E\setminus\{(i,j_x,t_x)|i\in N_m\}} , иначе

если Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle j_x={n+1}} , то $E=E\setminus \{(i_{x},j,t_{x})|i\in N_{n}\}$ , иначе

если $t_{x}={k+1}$ , то $E=E\setminus \{(i_{x},j_{x},t)|i\in N_{k}\}$ .

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

10.Если $x_{m+1n+1k+1}=0$ , то $X_{m\times n\times k}$ является опорным, иначе нет решения.

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

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

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

Литература

• Кривопалов Ю. А. Метод минимального элемента для нахождения опорного решения для трёхиндексной транспортной задачи. М., ВИМИ, 1990г. деп. № Д08222.
• Кривопалов Ю. А. Метод минимального элемента для нахождения опорного решения для трёхиндексной транспортной задачи. Сборник ХII конференции «Наука. Творчество» 2016, Самара, Т.1.