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

Версия 11:26, 22 февраля 2023

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

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

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

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

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

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

B₀ – базис решения (множество базисных перевозок решения (i_k, j_k));

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

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

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

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

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

Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения

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

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

Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.
Участник:Logic-samara

@@ Строка 3: / Строка 3: @@
 Введём обозначения:
-'''m''' – число промежуточных пунктов (складов);
+'''m''' – число промежуточных пунктов (складов)'''(m>1)''';
-'''n''' – число конечных пунктов (поставщиков и потребителей);
+'''n''' – число конечных пунктов (поставщиков и потребителей)'''(n>3)''';
-'''np''' – число поставщиков;
+'''mp''' – число складов с положительными дополнительными потребностями '''(0≤mp≤m)''';
-'''B<sub>0</sub>''' – базис решения (множество базисных перевозок решения);
+'''np''' – число поставщиков (конечных пунктов c положительными значениями) '''(1<np<n)''';
+'''B<sub>0</sub>''' – базис решения (множество базисных перевозок решения '''(i<sub>k</sub>, j<sub>k</sub>)''');
 '''x<sub>ij</sub>''' – объём (со знаком) перевозки продукции между '''i'''-ым промежуточным пунктом и '''j'''-ым конечным пунктом (объём перевозки '''(i,j)''');