Алгоритм перераспределения перевозок для ТЗПП — различия между версиями
| Строка 22: | Строка 22: | ||
== Алгоритм == | == Алгоритм == | ||
Входные данные: '''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>}'''. | Входные данные: '''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>}'''. | ||
| + | |||
| + | [[файл:BX001.png]] | ||
[[файл:РПР010.png]] | [[файл:РПР010.png]] | ||
Выходные данные: '''Δx; (i<sub>x</sub>, j<sub>x</sub>); {x<sub>11</sub>, x<sub>12</sub>, ..., x<sub>mn</sub>}'''. | Выходные данные: '''Δx; (i<sub>x</sub>, j<sub>x</sub>); {x<sub>11</sub>, x<sub>12</sub>, ..., x<sub>mn</sub>}'''. | ||
| + | |||
| + | [[файл:DX001.png]] | ||
*Заметим, что данный алгоритм применим для [[Транспортная задача|транспортной задачи]], при этом '''np=n''', а промежуточные пункты (склады) являются потребителями. Матрицы тарифов и перевозок в алгоритме транспонированы (строки заменены на столбцы, а столбцы - на строки). | *Заметим, что данный алгоритм применим для [[Транспортная задача|транспортной задачи]], при этом '''np=n''', а промежуточные пункты (склады) являются потребителями. Матрицы тарифов и перевозок в алгоритме транспонированы (строки заменены на столбцы, а столбцы - на строки). | ||
== [[Алгоритм|Другие алгоритмы:]] == | == [[Алгоритм|Другие алгоритмы:]] == | ||
Версия 16:31, 23 февраля 2023
Алгоритм перераспределения перевозок — это алгоритм построения цикла перераспределения и нахождения нового опорного решения для транспортной задачи с промежуточными пунктами (ТЗПП).
Содержание
Обозначения
Введём обозначения:
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.
Алгоритм
Входные данные: m; n; np; B0; (i0, j0); {x11, x12, ..., xmn}.
Выходные данные: Δx; (ix, jx); {x11, x12, ..., xmn}.
- Заметим, что данный алгоритм применим для транспортной задачи, при этом np=n, а промежуточные пункты (склады) являются потребителями. Матрицы тарифов и перевозок в алгоритме транспонированы (строки заменены на столбцы, а столбцы - на строки).
Другие алгоритмы:
- алгоритм северо-западного угла для ТЗ;
- алгоритм северо-западного угла для ТЗПП;
- алгоритм расчёта потенциалов для ТЗ;
- алгоритм расчёта потенциалов для ТЗПП;
- алгоритм перераспределения перевозок для ТЗ;
- алгоритм перераспределения перевозок для ТЗПП;
- алгоритм решения ТЗПП с запретами;
- алгоритм минимального элемента для ТТЗ;
- алгоритм расчёта потенциалов для ТТЗ;
- алгоритм перераспределения перевозок для ТТЗ.
Ссылки
- Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.
- Участник:Logic-samara
