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

Материал из ALL
Перейти к: навигация, поиск

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

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

Определения[править]

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

Обозначения[править]

Введём обозначения:

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

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

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

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

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

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

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

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

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

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

Алгоритм[править]

Входные данные: m; n; k; B0; (i0, j0, t0); {x111, x112, ..., xmnk}.

АПП03.JPG

Выходные данные: Δx; (ix, jx, tx); {x111, x112, ..., xmnk}.

Другие алгоритмы:[править]

Ссылки[править]

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