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

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

Содержание

1 Определения
2 Обозначения
3 Алгоритм
4 Другие алгоритмы:
5 Ссылки

Определения

Гипотетический многогранник перераспределения (ГМП) - это множество узлов (элементов) целочисленной решётки 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 (до перераспределения).