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