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