Алгоритм расчёта потенциалов для ТЗПП — различия между версиями
Материал из ALL
Ws (обсуждение | вклад) (Восстановление статей Logic-samara) |
|||
| Строка 1: | Строка 1: | ||
| − | + | '''Алгоритм северо-западного угла''' — это алгоритм нахождения допустимого решения для [[Транспортная задача с промежуточными пунктами|транспортной задачи с промежуточными пунктами]] ([[ТЗПП]]). | |
| − | '''Алгоритм | + | == Обозначения == |
| − | + | ||
Введём обозначения: | Введём обозначения: | ||
| Строка 7: | Строка 6: | ||
'''n''' – число конечных пунктов (поставщиков и потребителей); | '''n''' – число конечных пунктов (поставщиков и потребителей); | ||
| + | |||
| + | '''mp''' – число складов с положительными дополнительными потребностями; | ||
'''np''' – число поставщиков; | '''np''' – число поставщиков; | ||
| − | ''' | + | '''a<sub>i</sub>''' – дополнительная потребность (со знаком) '''i'''-ого промежуточного пункта (склада); |
| − | ''' | + | '''b<sub>j</sub>''' – объём грузов (со знаком) '''j'''-ого конечного пункта (для поставщиков объём положительное число, для потребителей – отрицательное); |
| − | ''' | + | '''x<sub>ij</sub>''' – объём перевозки (со знаком) между '''i'''-ым промежуточным пунктом и '''j'''-ым конечным пунктом; |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| + | '''z<sub>ij</sub>''' – признак базисного элемента '''(i,j)'''. | ||
== Алгоритм == | == Алгоритм == | ||
| − | Входные данные: '''m; n; np; { | + | Входные данные: '''m; n; mp; np; {a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>m</sub>}; {b<sub>1</sub>, b<sub>2</sub>, ..., b<sub>n</sub>}'''. |
| − | [[файл: | + | [[файл:АСЗУ01.JPG]] |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| + | Выходные данные: '''{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. | * Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29. | ||
* [[Участник:Logic-samara]] | * [[Участник:Logic-samara]] | ||
[[Категория:Транспортная задача]][[Категория:Алгоритмы]] | [[Категория:Транспортная задача]][[Категория:Алгоритмы]] | ||
Версия 19:12, 13 января 2016
Алгоритм северо-западного угла — это алгоритм нахождения допустимого решения для транспортной задачи с промежуточными пунктами (ТЗПП).
Содержание
Обозначения
Введём обозначения:
m – число промежуточных пунктов (складов);
n – число конечных пунктов (поставщиков и потребителей);
mp – число складов с положительными дополнительными потребностями;
np – число поставщиков;
ai – дополнительная потребность (со знаком) i-ого промежуточного пункта (склада);
bj – объём грузов (со знаком) j-ого конечного пункта (для поставщиков объём положительное число, для потребителей – отрицательное);
xij – объём перевозки (со знаком) между i-ым промежуточным пунктом и j-ым конечным пунктом;
zij – признак базисного элемента (i,j).
Алгоритм
Входные данные: m; n; mp; np; {a1, a2, ..., am}; {b1, b2, ..., bn}.
Выходные данные: {x11, x12, ..., xmn}; {z11, z12, ..., zmn}.
- Заметим, что при выборе новой клетки СЗУ(i,j) необходимо увеличивать индекс строки или индекс столбца.
Другие алгоритмы:
- алгоритм расчёта потенциалов;
- алгоритм перераспределения перевозок;
- алгоритм решения ТЗПП с запретами;
- алгоритм расчёта потенциалов для ТТЗ;
- алгоритм перераспределения перевозок для ТТЗ.
Ссылки
- Кривопалов В. Ю., Метод северо-западного угла для нахождения допустимого решения транспортной задачи с промежуточными пунктами. Сборник конференции ПИТ-2014, СГАУ, стр.369-372. http://www.ssau.ru/files/events/2014/pit_14_1_6.pdf
- Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.
- Участник:Logic-samara
