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

Материал из ALL
Перейти к: навигация, поиск
(Восстановление статей Logic-samara)
 
м
 
(не показано 8 промежуточных версий 2 участников)
Строка 1: Строка 1:
−
== Определение ==
 
 
'''Алгоритм перераспределения перевозок''' — это алгоритм построения цикла перераспределения и нахождения нового опорного решения для [[Транспортная задача с промежуточными пунктами|транспортной задачи с промежуточными пунктами]] ([[ТЗПП]]).
 
'''Алгоритм перераспределения перевозок''' — это алгоритм построения цикла перераспределения и нахождения нового опорного решения для [[Транспортная задача с промежуточными пунктами|транспортной задачи с промежуточными пунктами]] ([[ТЗПП]]).
 +
== Обозначения ==
 +
'''m''' – число промежуточных пунктов (складов)'''(m>1)''';
  
−
Введём обозначения:
+
'''n''' – число конечных пунктов (поставщиков и потребителей)'''(n>3)''';
  
−
'''m''' – число промежуточных пунктов (складов);
+
'''mp''' – число складов с положительными дополнительными потребностями '''(0≤mp≤m)''';
  
−
'''n''' – число конечных пунктов (поставщиков и потребителей);
+
'''np''' – число поставщиков (конечных пунктов c положительными значениями) '''(1<np<n)''';
  
−
'''np''' – число поставщиков;
+
'''B<sub>0</sub>''' – базис решения (множество базисных перевозок решения '''(i<sub>k</sub>, j<sub>k</sub>), 0<k<m+n''');
−
 
+
−
'''B<sub>0</sub>''' – базис решения (множество базисных перевозок решения);
+
  
 
'''x<sub>ij</sub>''' – объём (со знаком) перевозки продукции между '''i'''-ым промежуточным пунктом и '''j'''-ым конечным пунктом (объём перевозки '''(i,j)''');
 
'''x<sub>ij</sub>''' – объём (со знаком) перевозки продукции между '''i'''-ым промежуточным пунктом и '''j'''-ым конечным пунктом (объём перевозки '''(i,j)''');
  
−
'''G''' – множество узлов целочисленной решётки, состоящее из множества базисных перевозок решения и перевозки '''(i<sub>0</sub>,j<sub>0</sub>)''';
+
'''G''' – множество узлов целочисленной решётки, состоящее из множества базисных перевозок решения и перевозки '''(i<sub>0</sub>, j<sub>0</sub>)''';
  
 
'''Δx''' – перераспределяемая часть перевозки;
 
'''Δx''' – перераспределяемая часть перевозки;
  
−
'''(i<sub>x</sub>,j<sub>x</sub>)''' – перевозка с перераспределяемым приращением '''Δx'''.
+
'''(i<sub>x</sub>, j<sub>x</sub>)''' – перевозка с перераспределяемым приращением '''Δx'''.
 +
== Алгоритм 1 ==
 +
'''Входные данные:'''
 +
 
 +
[[файл:BX002.png]]
 +
 
 +
'''Алгоритм'''
 +
 
 +
[[файл:РПР010.png]]
 +
 
 +
'''Выходные данные:'''
  
−
== Алгоритм ==
+
[[файл:DX001.png]]
−
Входные данные: '''m; n; np; B<sub>0</sub>; (i<sub>0</sub>,j<sub>0</sub>); {x<sub>11</sub>, x<sub>12</sub>, ..., x<sub>mn</sub>}'''.
+
== Алгоритм 2 ==
 +
'''Входные данные:'''
  
−
[[файл:АПП01.JPG]]
+
[[файл:BX002.png]]
  
−
Выходные данные: '''Δx; (i<sub>x</sub>,j<sub>x</sub>); {x<sub>11</sub>, x<sub>12</sub>, ..., x<sub>mn</sub>}'''.
+
'''Алгоритм'''
  
−
* Заметим, что данный алгоритм применим для [[Классическая транспортная задача|транспортной задачи]], при этом '''np=n''', а промежуточные пункты (склады) являются потребителями. Матрицы тарифов и перевозок в алгоритме транспонированы (строки заменены на столбцы, а столбцы - на строки).
+
[[файл:РПР011.png]]
  
−
== Другие алгоритмы: ==
+
'''Выходные данные:'''
−
*[[алгоритм северо-западного угла]];
+
−
*[[алгоритм расчёта потенциалов]];
+
−
*[[алгоритм решения ТЗПП с запретами]];
+
−
*[[алгоритм расчёта потенциалов для ТТЗ]].
+
  
 +
[[файл:DX001.png]]
 +
*Заметим, что данный алгоритм применим для [[Транспортная задача|транспортной задачи]], при этом '''np=n''', а промежуточные пункты (склады) являются потребителями. Матрицы тарифов и перевозок в алгоритме транспонированы (строки заменены на столбцы, а столбцы – на строки).
 +
== [[Алгоритмы решения транспортных задач|Другие алгоритмы:]] ==
 +
{{Список АТЗ}}
 
== Ссылки ==
 
== Ссылки ==
−
* Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.
+
*Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.
−
* [[Участник:Logic-samara]]
+
*[[Участник:Logic-samara]]
−
[[Категория:Транспортная задача]][[Категория:Алгоритмы]]
+
[[Категория:Математика]][[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Алгоритмы]]

Текущая версия на 12:05, 16 января 2024

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

Обозначения

m – число промежуточных пунктов (складов)(m>1);

n – число конечных пунктов (поставщиков и потребителей)(n>3);

mp – число складов с положительными дополнительными потребностями (0≤mp≤m);

np – число поставщиков (конечных пунктов c положительными значениями) (1<np<n);

B0 – базис решения (множество базисных перевозок решения (ik, jk), 0<k<m+n);

xij – объём (со знаком) перевозки продукции между i-ым промежуточным пунктом и j-ым конечным пунктом (объём перевозки (i,j));

G – множество узлов целочисленной решётки, состоящее из множества базисных перевозок решения и перевозки (i0, j0);

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

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

Алгоритм 1

Входные данные:

Файл:BX002.png

Алгоритм

Файл:РПР010.png

Выходные данные:

Файл:DX001.png

Алгоритм 2

Входные данные:

Файл:BX002.png

Алгоритм

Файл:РПР011.png

Выходные данные:

Файл:DX001.png

  • Заметим, что данный алгоритм применим для транспортной задачи, при этом np=n, а промежуточные пункты (склады) являются потребителями. Матрицы тарифов и перевозок в алгоритме транспонированы (строки заменены на столбцы, а столбцы – на строки).

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

Ссылки

  • Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.
  • Участник:Logic-samara
Источник — «https://allll.net/w/index.php?title=Алгоритм_перераспределения_перевозок_для_ТЗПП&oldid=122888»