Алгоритм расчёта потенциалов для ТЗПП — различия между версиями
м |
|||
(не показано 8 промежуточных версий 2 участников) | |||
Строка 1: | Строка 1: | ||
'''Алгоритм расчёта потенциалов''' — это алгоритм нахождения потенциалов и оценок оптимальности для [[Транспортная задача с промежуточными пунктами|транспортной задачи с промежуточными пунктами]] ([[ТЗПП]]). | '''Алгоритм расчёта потенциалов''' — это алгоритм нахождения потенциалов и оценок оптимальности для [[Транспортная задача с промежуточными пунктами|транспортной задачи с промежуточными пунктами]] ([[ТЗПП]]). | ||
== Обозначения == | == Обозначения == | ||
− | + | '''m''' – число промежуточных пунктов (складов)'''(m>1)'''; | |
− | ''' | + | '''n''' – число конечных пунктов (поставщиков и потребителей)'''(n>3)'''; |
− | ''' | + | '''np''' – число поставщиков (конечных пунктов c положительными значениями) '''(1<np<n)'''; |
− | + | ||
− | '''np''' | + | |
'''c<sub>ij</sub>''' – транспортный тариф (со знаком) на перевозку единицы продукции между '''i'''-ым промежуточным пунктом и '''j'''-ым конечным пунктом (тариф для перевозки '''(i,j)'''); | '''c<sub>ij</sub>''' – транспортный тариф (со знаком) на перевозку единицы продукции между '''i'''-ым промежуточным пунктом и '''j'''-ым конечным пунктом (тариф для перевозки '''(i,j)'''); | ||
Строка 22: | Строка 20: | ||
'''(i<sub>0</sub>, j<sub>0</sub>)''' – перевозка с оценкой '''Δo'''. | '''(i<sub>0</sub>, j<sub>0</sub>)''' – перевозка с оценкой '''Δo'''. | ||
− | == Алгоритм == | + | == Алгоритм 1 == |
− | Входные данные: ''' | + | '''Входные данные:''' |
+ | |||
+ | [[файл:BС011.png]] | ||
+ | |||
+ | '''Алгоритм:''' | ||
+ | |||
+ | [[файл:РПО010.png]] | ||
+ | |||
+ | '''Выходные данные:''' | ||
+ | |||
+ | [[файл:UVD001.png]] | ||
+ | == Алгоритм 2 == | ||
+ | '''Входные данные:''' | ||
+ | |||
+ | [[файл:BС011.png]] | ||
+ | |||
+ | '''Алгоритм:''' | ||
+ | |||
+ | [[файл:РПО011.png]] | ||
− | + | '''Выходные данные:''' | |
− | + | [[файл:UVD001.png]] | |
− | * Заметим, что данный алгоритм применим для [[ | + | *Заметим, что данный алгоритм применим для [[Транспортная задача|транспортной задачи]], при этом '''np=n''', а промежуточные пункты (склады) являются потребителями. Матрицы тарифов и оценок в алгоритме транспонированы (строки заменены на столбцы, а столбцы - на строки). |
− | == Другие алгоритмы: == | + | == [[Алгоритмы решения транспортных задач|Другие алгоритмы:]] == |
− | + | {{Список АТЗ}} | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
== Ссылки == | == Ссылки == | ||
− | * Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29. | + | *Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29. |
− | * [[Участник:Logic-samara]] | + | *[[Участник:Logic-samara]] |
− | [[Категория:Транспортная задача]][[Категория:Алгоритмы]] | + | [[Категория:Математика]][[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Алгоритмы]] |
Текущая версия на 12:06, 16 января 2024
Алгоритм расчёта потенциалов — это алгоритм нахождения потенциалов и оценок оптимальности для транспортной задачи с промежуточными пунктами (ТЗПП).
Обозначения
m – число промежуточных пунктов (складов)(m>1);
n – число конечных пунктов (поставщиков и потребителей)(n>3);
np – число поставщиков (конечных пунктов c положительными значениями) (1<np<n);
cij – транспортный тариф (со знаком) на перевозку единицы продукции между i-ым промежуточным пунктом и j-ым конечным пунктом (тариф для перевозки (i,j));
B0 – базис решения (множество базисных перевозок решения);
ui – потенциал i-ого промежуточного пункта;
vj – потенциал j-ого конечного пункта;
Δij – оценка оптимальности для перевозки (i,j);
Δo – оценка оптимальности решения;
(i0, j0) – перевозка с оценкой Δo.
Алгоритм 1
Входные данные:
Алгоритм:
Выходные данные:
Алгоритм 2
Входные данные:
Алгоритм:
Выходные данные:
- Заметим, что данный алгоритм применим для транспортной задачи, при этом np=n, а промежуточные пункты (склады) являются потребителями. Матрицы тарифов и оценок в алгоритме транспонированы (строки заменены на столбцы, а столбцы - на строки).
Другие алгоритмы:
- алгоритм северо-западного угла для ТЗ;
- алгоритм расчёта потенциалов для ТЗ;
- алгоритм перераспределения перевозок для ТЗ;
- алгоритм северо-западного угла для ТЗПП;
- алгоритм расчёта потенциалов для ТЗПП;
- алгоритм перераспределения перевозок для ТЗПП;
- алгоритм решения ТЗПП с запретами;
- алгоритм минимального элемента для ТТЗ;
- алгоритм расчёта потенциалов для ТТЗ;
- алгоритм перераспределения перевозок для ТТЗ.
Ссылки
- Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.
- Участник:Logic-samara