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

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

Обозначения

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

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

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

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

$(i_{o},j_{o},t_{o})$ — новая (оптимизирующая) перевозка (элемент);

$u_{it}$ — потенциал ряда $(i,t),\forall (i,t)\in {N_{m}\times N_{k}}$ ;

$v_{jt}$ — потенциал ряда $(j,t),\forall (j,t)\in {N_{n}\times N_{k}}$ ;

$w_{ij}$ — потенциал ряда $(i,j),\forall (i,j)\in {N_{m}\times N_{n}}$ ;

$d_{ijt}$ — стоимость (тариф) перевозки $(i,j,t),\forall (i,j,t)\in {N_{m}\times N_{n}\times N_{k}}$ ;

$\Delta _{ijt}$ — оценка оптимальности для перевозки $(i,j,t),\forall (i,j,t)\in {N_{m}\times N_{n}\times N_{k}}$ ;

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

$G$ — вспомогательное множество базисных элементов решения $(i,j,t)$ ;

$S$ — стек-множество базисных элементов $(i,j,t)$ ;

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

$O_{m\times n\times k}$ — трёхмерная матрица оценок оптимальности $\Delta _{ijt}$ .

Алгоритм

1. $G=B_{o},S=\varnothing$ .

2. Если $\exists (i,j,t)\in G$ элемент, лежащий один хотя бы в одном ряду ( $(i,j)$ или $(i,t)$ или $(j,t)$ ), то выбираем его, иначе идти к 6.

3. Если для элемента $(i,j,t)$ по одному элементу во всех трёх рядах ( $(i,j)$ и $(i,t)$ и $(j,t)$ ), то $u_{it}=0,v_{jt}=0$ и идти к 5.

4. Если для элемента $(i,j,t)$ по одному элементу только в двух рядах, то если в ряду $(i,t)$ один элемент, то $u_{it}=0$ , иначе $v_{jt}=0$ .

5. $G=G\setminus (i,j,t),S=S\cup (i,j,t)$ . Если $G\neq \varnothing$ , то переходим к пункту 2.

6. Выбираем элемент $(i,j,t)\in S$ (в порядке обратном поряду включения в стек).

Вычисляем неизвестный потенциал по одной из формул:

$u_{it}=d_{ijt}-v_{jt}-w_{ij},v_{jt}=d_{ijt}-u_{it}-w_{ij},w_{ij}=d_{ijt}-u_{it}-v_{jt}$ .

7. $S=S\setminus (i,j,t)$ . Если $S\neq \varnothing$ , то идти к 6.

8. $\Delta _{ijt}=u_{it}+v_{jt}+w_{ij}-d_{ijt},\forall (i,j,t)\in {N_{m}\times N_{n}\times N_{k}}$ .

9. $\Delta _{o}=\max \limits _{(i,j,t)\in {N_{m}\times N_{n}\times N_{k}}}\{\Delta _{ijt}\},(i_{o},j_{o},t_{o})=\arg\{\Delta _{o}\}$ .

Выходные данные: $\Delta _{o},(i_{o},j_{o},t_{o}),O_{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 г. деп. № Д08221.
• Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи — Сборник ХI конференции «Наука. Творчество» 2015, Самара, Т. 1, стр.39.