Изменения
'''Алгоритм северо-западного угларасчёта потенциалов''' — это алгоритм нахождения допустимого решения потенциалов и оценок оптимальности для [[Транспортная задача с промежуточными пунктами|транспортной задачи с промежуточными пунктами]] ([[ТЗПП]]).
== Обозначения ==
Введём обозначения:
'''n''' – число конечных пунктов (поставщиков и потребителей);
'''np''' – число поставщиков;
'''ac<sub>iij</sub>''' – дополнительная потребность транспортный тариф (со знаком) на перевозку единицы продукции между '''i'''-ым промежуточным пунктом и '''j'''-ым конечным пунктом (тариф для перевозки '''(i,j)'''); '''B<sub>0</sub>''' – базис решения (множество базисных перевозок решения); '''u<sub>i</sub>''' – потенциал '''i'''-ого промежуточного пункта (склада); '''v<sub>j</sub>''' – потенциал '''j'''-ого конечного пункта;
'''bΔ<sub>jij</sub>''' – объём грузов (со знаком) оценка оптимальности для перевозки '''(i,j)'''-ого конечного пункта (для поставщиков объём положительное число, для потребителей – отрицательное);
'''x<sub>ij</sub>Δo''' – объём перевозки (со знаком) между '''i'''-ым промежуточным пунктом и '''j'''-ым конечным пунктомоценка оптимальности решения;
'''z(i<sub>ij0</sub>, j<sub>0</sub>)''' – признак базисного элемента перевозка с оценкой '''(i,j)Δo'''.
== Алгоритм ==
Входные данные: '''m; n; mp; np; {ac<sub>111</sub>, ac<sub>212</sub>, ..., ac<sub>mmn</sub>}; {bB<sub>10</sub>, b<sub>2</sub>, ..., b<sub>n</sub>}'''.
[[файл:АСЗУ01АРП01.JPG]]
Выходные данные: '''{x<sub>11</sub>, x<sub>12</sub>, ..., x<sub>mn</sub>}Δo; {z(i<sub>110</sub>, zj<sub>120</sub>, ..., z<sub>mn</sub>})'''.* Заметим, что данный алгоритм применим для [[Классическая транспортная задача|транспортной задачи]], при выборе новой клетки СЗУэтом '''np=n''', а промежуточные пункты (iсклады) являются потребителями. Матрицы тарифов и оценок в алгоритме транспонированы (строки заменены на столбцы,j) необходимо увеличивать индекс а столбцы - на строки или индекс столбца).
== Другие алгоритмы: ==
*[[алгоритм расчёта потенциаловсеверо-западного угла]];
*[[алгоритм перераспределения перевозок]];
*[[алгоритм решения ТЗПП с запретами]];
*[[алгоритм перераспределения перевозок для ТТЗ]].
== Ссылки ==
* Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.
* [[Участник:Logic-samara]]
[[Категория:Транспортная задача]][[Категория:Алгоритмы]]
