Алгоритм перераспределения перевозок для ТТЗ

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

Для обозначения трёхмерных циклов перераспределения перевозок будем использовать название гипотетический многогранник перераспределения.

Определения

Гипотетический многогранник перераспределения (ГМП) - это множество узлов (элементов) целочисленной решётки N_mxN_nxN_k, содержащее в каждом ряду решётки не менее двух узлов. ГМП называется допустимым, если все его узлы можно пометить так, что в каждом ряду решётки число узлов со знаком "+" равно числу узлов со знаком "-". Очевидно, что в допустимом ГМП чётное число узлов в рядах. Все остальные ГМП будем считать недопустимыми.

Обозначения

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

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

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

x_ijt - объём перевозок t-продукта от i-поставщика к j-потребителю.

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

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

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

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

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

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

Алгоритм

Входные данные: m; n; k; B₀; (i₀, j₀, t₀); {x₁₁₁, x₁₁₂, ..., x_mnk}.

Выходные данные: Δx; (i_x, j_x, t_x); {x₁₁₁, x₁₁₂, ..., x_mnk}.

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

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

Литература

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

Ссылки

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