Алгоритм расчёта потенциалов для ТЗПП — различия между версиями
Материал из ALL
| Строка 1: | Строка 1: | ||
| − | '''Алгоритм | + | '''Алгоритм расчёта потенциалов''' — это алгоритм нахождения потенциалов и оценок оптимальности для [[Транспортная задача с промежуточными пунктами|транспортной задачи с промежуточными пунктами]] ([[ТЗПП]]). |
== Обозначения == | == Обозначения == | ||
Введём обозначения: | Введём обозначения: | ||
| Строка 6: | Строка 6: | ||
'''n''' – число конечных пунктов (поставщиков и потребителей); | '''n''' – число конечных пунктов (поставщиков и потребителей); | ||
| − | |||
| − | |||
'''np''' – число поставщиков; | '''np''' – число поставщиков; | ||
| − | ''' | + | '''c<sub>ij</sub>''' – транспортный тариф (со знаком) на перевозку единицы продукции между '''i'''-ым промежуточным пунктом и '''j'''-ым конечным пунктом (тариф для перевозки '''(i,j)'''); |
| + | |||
| + | '''B<sub>0</sub>''' – базис решения (множество базисных перевозок решения); | ||
| + | |||
| + | '''u<sub>i</sub>''' – потенциал '''i'''-ого промежуточного пункта; | ||
| + | |||
| + | '''v<sub>j</sub>''' – потенциал '''j'''-ого конечного пункта; | ||
| − | ''' | + | '''Δ<sub>ij</sub>''' – оценка оптимальности для перевозки '''(i,j)'''; |
| − | ''' | + | '''Δo''' – оценка оптимальности решения; |
| − | ''' | + | '''(i<sub>0</sub>, j<sub>0</sub>)''' – перевозка с оценкой '''Δo'''. |
== Алгоритм == | == Алгоритм == | ||
| − | Входные данные: '''m; n | + | Входные данные: '''m; n; np; {c<sub>11</sub>, c<sub>12</sub>, ..., c<sub>mn</sub>}; B<sub>0</sub>'''. |
| − | [[файл: | + | [[файл:АРП01.JPG]] |
| − | Выходные данные: ''' | + | Выходные данные: '''Δo; (i<sub>0</sub>, j<sub>0</sub>)'''. |
| − | * Заметим, что при | + | * Заметим, что данный алгоритм применим для [[Классическая транспортная задача|транспортной задачи]], при этом '''np=n''', а промежуточные пункты (склады) являются потребителями. Матрицы тарифов и оценок в алгоритме транспонированы (строки заменены на столбцы, а столбцы - на строки). |
== Другие алгоритмы: == | == Другие алгоритмы: == | ||
| − | *[[алгоритм | + | *[[алгоритм северо-западного угла]]; |
*[[алгоритм перераспределения перевозок]]; | *[[алгоритм перераспределения перевозок]]; | ||
*[[алгоритм решения ТЗПП с запретами]]; | *[[алгоритм решения ТЗПП с запретами]]; | ||
| Строка 32: | Строка 36: | ||
*[[алгоритм перераспределения перевозок для ТТЗ]]. | *[[алгоритм перераспределения перевозок для ТТЗ]]. | ||
== Ссылки == | == Ссылки == | ||
| − | |||
* Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29. | * Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29. | ||
* [[Участник:Logic-samara]] | * [[Участник:Logic-samara]] | ||
[[Категория:Транспортная задача]][[Категория:Алгоритмы]] | [[Категория:Транспортная задача]][[Категория:Алгоритмы]] | ||
Версия 19:14, 13 января 2016
Алгоритм расчёта потенциалов — это алгоритм нахождения потенциалов и оценок оптимальности для транспортной задачи с промежуточными пунктами (ТЗПП).
Содержание
Обозначения
Введём обозначения:
m – число промежуточных пунктов (складов);
n – число конечных пунктов (поставщиков и потребителей);
np – число поставщиков;
cij – транспортный тариф (со знаком) на перевозку единицы продукции между i-ым промежуточным пунктом и j-ым конечным пунктом (тариф для перевозки (i,j));
B0 – базис решения (множество базисных перевозок решения);
ui – потенциал i-ого промежуточного пункта;
vj – потенциал j-ого конечного пункта;
Δij – оценка оптимальности для перевозки (i,j);
Δo – оценка оптимальности решения;
(i0, j0) – перевозка с оценкой Δo.
Алгоритм
Входные данные: m; n; np; {c11, c12, ..., cmn}; B0.
Выходные данные: Δo; (i0, j0).
- Заметим, что данный алгоритм применим для транспортной задачи, при этом np=n, а промежуточные пункты (склады) являются потребителями. Матрицы тарифов и оценок в алгоритме транспонированы (строки заменены на столбцы, а столбцы - на строки).
Другие алгоритмы:
- алгоритм северо-западного угла;
- алгоритм перераспределения перевозок;
- алгоритм решения ТЗПП с запретами;
- алгоритм расчёта потенциалов для ТТЗ;
- алгоритм перераспределения перевозок для ТТЗ.
Ссылки
- Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.
- Участник:Logic-samara
