== Определение =='''Алгоритм расчёта потенциаловсеверо-западного угла''' — это алгоритм нахождения потенциалов и оценок оптимальности допустимого решения для [[Транспортная задача с промежуточными пунктами|транспортной задачи с промежуточными пунктами]] ([[ТЗПП]]).== Обозначения ==
Введём обозначения:
'''n''' – число конечных пунктов (поставщиков и потребителей);
'''mp''' – число складов с положительными дополнительными потребностями;
'''np''' – число поставщиков;
'''ca<sub>iji</sub>''' – транспортный тариф дополнительная потребность (со знаком) на перевозку единицы продукции между '''i'''-ым промежуточным пунктом и '''j'''-ым конечным пунктом ого промежуточного пункта (тариф для перевозки '''(i,j)'''склада);
'''Bb<sub>0j</sub>''' – базис решения объём грузов (множество базисных перевозок решениясо знаком) '''j'''-ого конечного пункта (для поставщиков объём положительное число, для потребителей – отрицательное);
'''ux<sub>iij</sub>''' – потенциал объём перевозки (со знаком) между '''i'''-ого промежуточного пункта; '''v<sub>j</sub>''' – потенциал ым промежуточным пунктом и '''j'''-ого конечного пунктаым конечным пунктом; '''Δ<sub>ij</sub>''' – оценка оптимальности для перевозки '''(i,j)'''; '''Δo''' – оценка оптимальности решения; '''(i<sub>0</sub>,j<sub>0</sub>)''' – перевозка с оценкой '''Δo'''.
'''z<sub>ij</sub>''' – признак базисного элемента '''(i,j)'''.
== Алгоритм ==
Входные данные: '''m; n; mp; np; {ca<sub>111</sub>, ca<sub>122</sub>, ..., ca<sub>mnm</sub>}; B{b<sub>01</sub>, b<sub>2</sub>, ..., b<sub>n</sub>}'''.
[[файл:АРП01АСЗУ01.JPG]] Выходные данные: '''Δo; (i<sub>0</sub>,j<sub>0</sub>)'''. * Заметим, что данный алгоритм применим для [[Классическая транспортная задача|транспортной задачи]], при этом '''np=n''', а промежуточные пункты (склады) являются потребителями. Матрицы тарифов и оценок в алгоритме транспонированы (строки заменены на столбцы, а столбцы - на строки).
Выходные данные: '''{x<sub>11</sub>, x<sub>12</sub>, ..., x<sub>mn</sub>}; {z<sub>11</sub>, z<sub>12</sub>, ..., z<sub>mn</sub>}'''.
* Заметим, что при выборе новой клетки СЗУ(i,j) необходимо увеличивать индекс строки или индекс столбца.
== Другие алгоритмы: ==
*[[алгоритм северо-западного угларасчёта потенциалов]];
*[[алгоритм перераспределения перевозок]];
*[[алгоритм решения ТЗПП с запретами]];
*[[алгоритм расчёта потенциалов для ТТЗ]].;*[[алгоритм перераспределения перевозок для ТТЗ]].
== Ссылки ==
* Кривопалов В. Ю., Метод северо-западного угла для нахождения допустимого решения транспортной задачи с промежуточными пунктами. Сборник конференции ПИТ-2014, СГАУ, стр.369-372. http://www.ssau.ru/files/events/2014/pit_14_1_6.pdf
* Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.
* [[Участник:Logic-samara]]
[[Категория:Транспортная задача]][[Категория:Алгоритмы]]