Алгоритм перераспределения перевозок для ТТЗ — различия между версиями
м |
|||
| (не показано 9 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
| − | |||
'''Алгоритм перераспределения перевозок для ТТЗ''' — это алгоритм построения трёхмерного цикла перераспределения перевозок и нахождения нового опорного решения для [[Трёхиндексная транспортная задача|трёхиндексной транспортной задачи]] ([[ТТЗ]]). | '''Алгоритм перераспределения перевозок для ТТЗ''' — это алгоритм построения трёхмерного цикла перераспределения перевозок и нахождения нового опорного решения для [[Трёхиндексная транспортная задача|трёхиндексной транспортной задачи]] ([[ТТЗ]]). | ||
| − | + | == Определения == | |
| − | + | '''[[Гипотетический многогранник перераспределения]] ([[ГМП]])''' - это множество узлов (элементов) целочисленной решётки '''N<sub>m</sub>xN<sub>n</sub>xN<sub>k</sub>''', содержащее в каждом ряду решётки не менее двух узлов. | |
| − | + | ||
| − | '''Гипотетический многогранник перераспределения (ГМП)''' - это множество узлов (элементов) целочисленной решётки '''N<sub>m</sub>xN<sub>n</sub>xN<sub>k</sub>''', содержащее в каждом ряду решётки не менее двух узлов. | + | |
ГМП называется допустимым, если все его узлы можно пометить так, что в каждом ряду решётки число узлов со знаком '''"+"''' равно числу узлов со знаком '''"-"'''. Очевидно, что в допустимом ГМП чётное число узлов в рядах. | ГМП называется допустимым, если все его узлы можно пометить так, что в каждом ряду решётки число узлов со знаком '''"+"''' равно числу узлов со знаком '''"-"'''. Очевидно, что в допустимом ГМП чётное число узлов в рядах. | ||
Все остальные ГМП будем считать недопустимыми. | Все остальные ГМП будем считать недопустимыми. | ||
| − | + | ГМП будем использовать для обозначения трёхмерных циклов перераспределения перевозок. | |
| − | + | == Обозначения == | |
| − | + | ||
'''m''' – число поставщиков; | '''m''' – число поставщиков; | ||
| Строка 29: | Строка 25: | ||
'''(i<sub>x</sub>, j<sub>x</sub>, t<sub>x</sub>)''' – элемент с перевозкой равной приращению '''Δx''' (до перераспределения). | '''(i<sub>x</sub>, j<sub>x</sub>, t<sub>x</sub>)''' – элемент с перевозкой равной приращению '''Δx''' (до перераспределения). | ||
| − | |||
== Алгоритм == | == Алгоритм == | ||
Входные данные: '''m; n; k; B<sub>0</sub>; (i<sub>0</sub>, j<sub>0</sub>, t<sub>0</sub>); {x<sub>111</sub>, x<sub>112</sub>, ..., x<sub>mnk</sub>}'''. | Входные данные: '''m; n; k; B<sub>0</sub>; (i<sub>0</sub>, j<sub>0</sub>, t<sub>0</sub>); {x<sub>111</sub>, x<sub>112</sub>, ..., x<sub>mnk</sub>}'''. | ||
| Строка 36: | Строка 31: | ||
Выходные данные: '''Δx; (i<sub>x</sub>, j<sub>x</sub>, t<sub>x</sub>); {x<sub>111</sub>, x<sub>112</sub>, ..., x<sub>mnk</sub>}'''. | Выходные данные: '''Δx; (i<sub>x</sub>, j<sub>x</sub>, t<sub>x</sub>); {x<sub>111</sub>, x<sub>112</sub>, ..., x<sub>mnk</sub>}'''. | ||
| − | + | == [[Алгоритмы решения транспортных задач|Другие алгоритмы:]] == | |
| − | == Другие алгоритмы: == | + | {{Список АТЗ}} |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
== Ссылки == | == Ссылки == | ||
| − | * Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи. М.,ВИМИ, 1990г. деп.№Д08221. | + | *Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи. М.,ВИМИ, 1990г. деп.№Д08221. |
| − | * Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи. Сборник ХI конференции «Наука. Творчество» 2015, Самара, Т.1,стр.39. | + | *Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи. Сборник ХI конференции «Наука. Творчество» 2015, Самара, Т.1,стр.39. |
| − | * [[Участник:Logic-samara]] | + | *[[Участник:Logic-samara]] |
| − | [[Категория:Транспортная задача]][[Категория:Алгоритмы]] | + | [[Категория:Математика]][[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Алгоритмы]] |
Текущая версия на 12:03, 16 января 2024
Алгоритм перераспределения перевозок для ТТЗ — это алгоритм построения трёхмерного цикла перераспределения перевозок и нахождения нового опорного решения для трёхиндексной транспортной задачи (ТТЗ).
Определения
Гипотетический многогранник перераспределения (ГМП) - это множество узлов (элементов) целочисленной решётки 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}.
Выходные данные: Δx; (ix, jx, tx); {x111, x112, ..., xmnk}.
Другие алгоритмы:
- алгоритм северо-западного угла для ТЗ;
- алгоритм расчёта потенциалов для ТЗ;
- алгоритм перераспределения перевозок для ТЗ;
- алгоритм северо-западного угла для ТЗПП;
- алгоритм расчёта потенциалов для ТЗПП;
- алгоритм перераспределения перевозок для ТЗПП;
- алгоритм решения ТЗПП с запретами;
- алгоритм минимального элемента для ТТЗ;
- алгоритм расчёта потенциалов для ТТЗ;
- алгоритм перераспределения перевозок для ТТЗ.
Ссылки
- Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи. М.,ВИМИ, 1990г. деп.№Д08221.
- Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи. Сборник ХI конференции «Наука. Творчество» 2015, Самара, Т.1,стр.39.
- Участник:Logic-samara
