Алгоритм расчёта потенциалов для ТТЗ

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

Обозначения

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

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

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

d_ijt – транспортные расходы на перевозку единицы t-продукта от i-поставщика к j-потребителю.

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

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

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

u_it – потенциал it;

v_jt – потенциал jt;

w_ij – потенциал ij;

Δ_ijt – оценка оптимальности для перевозки (i,j,t);

Δo – оценка оптимальности решения;

(i₀, j₀, t₀) – перевозка (элемент) с оценкой Δo.

Алгоритм

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

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},i=1,2,...,m,j=1,2,...,n,t=1,2,...,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}$.

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

• алгоритм северо-западного угла для ТЗ;
• алгоритм расчёта потенциалов для ТЗ;
• алгоритм перераспределения перевозок для ТЗ;
• алгоритм северо-западного угла для ТЗПП;
• алгоритм расчёта потенциалов для ТЗПП;
• алгоритм перераспределения перевозок для ТЗПП;
• алгоритм решения ТЗПП с запретами;
• алгоритм минимального элемента для ТТЗ;
• алгоритм расчёта потенциалов для ТТЗ;
• алгоритм перераспределения перевозок для ТТЗ.

Литература

• Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи — М.: ВИМИ, 1990 г. деп. № Д08221.
• Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи — Сборник ХI конференции «Наука. Творчество» 2015, Самара, Т. 1, стр.39.