3134 байта добавлено,
15:05, 15 ноября 2015 == Определение ==
'''Алгоритм расчёта потенциалов''' — это алгоритм нахождения потенциалов и оценок оптимальности для [[Транспортная задача с промежуточными пунктами|транспортной задачи с промежуточными пунктами]] ([[ТЗПП]]).
Введём обозначения:
'''m''' – число промежуточных пунктов (складов);
'''n''' – число конечных пунктов (поставщиков и потребителей);
'''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; 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''', а промежуточные пункты (склады) являются потребителями. Матрицы тарифов и оценок в алгоритме транспонированы (строки заменены на столбцы, а столбцы - на строки).
== Другие алгоритмы: ==
*[[алгоритм северо-западного угла]];
*[[алгоритм перераспределения перевозок]];
*[[алгоритм решения ТЗПП с запретами]];
*[[алгоритм расчёта потенциалов для ТТЗ]].
== Ссылки ==
* Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.
* [[Участник:Logic-samara]]
[[Категория:Транспортная задача]][[Категория:Алгоритмы]]