Алгоритм решения ТЗПП с запретами — различия между версиями
Строка 1: | Строка 1: | ||
− | |||
'''Алгоритм решения ТЗПП с запретами''' — это эвристический алгоритм решения [[Транспортная задача с промежуточными пунктами с запретами|транспортной задачи с промежуточными пунктами с запретами]]. | '''Алгоритм решения ТЗПП с запретами''' — это эвристический алгоритм решения [[Транспортная задача с промежуточными пунктами с запретами|транспортной задачи с промежуточными пунктами с запретами]]. | ||
− | + | == Обозначения == | |
Введём обозначения: | Введём обозначения: | ||
Строка 22: | Строка 21: | ||
'''(i<sub>t</sub>, j<sub>t</sub>)''' – '''t'''-ая запрещённая коммуникация (перевозка). | '''(i<sub>t</sub>, j<sub>t</sub>)''' – '''t'''-ая запрещённая коммуникация (перевозка). | ||
− | '''D''' – это множество запрещённых коммуникаций, '''D={(i<sub>t</sub>, j<sub>t</sub>),t=1,k}'''. | + | '''D''' – это множество запрещённых коммуникаций, '''D={(i<sub>t</sub>, j<sub>t</sub>), t=1,k}'''. |
− | + | ||
== Алгоритм == | == Алгоритм == | ||
Входные данные: '''m; n; mp; np; k; {a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>m</sub>}; {b<sub>1</sub>, b<sub>2</sub>, ..., b<sub>n</sub>}; {c<sub>11</sub>, c<sub>12</sub>, ..., c<sub>mn</sub>}; {(i<sub>1</sub>, j<sub>1</sub>), (i<sub>2</sub>, j<sub>2</sub>), ..., (i<sub>k</sub>, j<sub>k</sub>)}'''. | Входные данные: '''m; n; mp; np; k; {a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>m</sub>}; {b<sub>1</sub>, b<sub>2</sub>, ..., b<sub>n</sub>}; {c<sub>11</sub>, c<sub>12</sub>, ..., c<sub>mn</sub>}; {(i<sub>1</sub>, j<sub>1</sub>), (i<sub>2</sub>, j<sub>2</sub>), ..., (i<sub>k</sub>, j<sub>k</sub>)}'''. | ||
− | [[файл: | + | [[файл:ТЗПП33.JPG]] |
− | + | ||
− | + | ||
+ | Выходные данные: '''L; {x<sub>11</sub>, x<sub>12</sub>, …, x<sub>mn</sub>)'''. | ||
== Другие алгоритмы: == | == Другие алгоритмы: == | ||
*[[алгоритм северо-западного угла]]; | *[[алгоритм северо-западного угла]]; | ||
*[[алгоритм расчёта потенциалов]]; | *[[алгоритм расчёта потенциалов]]; | ||
*[[алгоритм перераспределения перевозок]]; | *[[алгоритм перераспределения перевозок]]; | ||
− | *[[алгоритм расчёта потенциалов для ТТЗ]] | + | *[[алгоритм расчёта потенциалов для ТТЗ]]; |
− | + | *[[алгоритм перераспределения перевозок для ТТЗ]]. | |
== Ссылки == | == Ссылки == | ||
* Кривопалов В. Ю., Решение транспортной задачи с промежуточными пунктами с запретами. Сборник ХI конференции «Наука. Творчество» 2015, Самара, Т.1,стр.22-27. | * Кривопалов В. Ю., Решение транспортной задачи с промежуточными пунктами с запретами. Сборник ХI конференции «Наука. Творчество» 2015, Самара, Т.1,стр.22-27. | ||
* [[Участник:Logic-samara]] | * [[Участник:Logic-samara]] | ||
[[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Алгоритмы]] | [[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Алгоритмы]] |
Версия 19:03, 13 января 2016
Алгоритм решения ТЗПП с запретами — это эвристический алгоритм решения транспортной задачи с промежуточными пунктами с запретами.
Содержание
Обозначения
Введём обозначения:
m – число промежуточных пунктов (складов);
n – число конечных пунктов (поставщиков и потребителей);
mp – число складов с положительными дополнительными потребностями;
np – число поставщиков;
k – число запретов;
ai – дополнительная потребность (со знаком) i-ого промежуточного пункта (склада);
bj – объём грузов (со знаком) j-ого конечного пункта (для поставщиков объём положительное число, для потребителей – отрицательное);
xij – объём перевозки (со знаком) между i-ым промежуточным пунктом и j-ым конечным пунктом;
(it, jt) – t-ая запрещённая коммуникация (перевозка).
D – это множество запрещённых коммуникаций, D={(it, jt), t=1,k}.
Алгоритм
Входные данные: m; n; mp; np; k; {a1, a2, ..., am}; {b1, b2, ..., bn}; {c11, c12, ..., cmn}; {(i1, j1), (i2, j2), ..., (ik, jk)}.
Выходные данные: L; {x11, x12, …, xmn).
Другие алгоритмы:
- алгоритм северо-западного угла;
- алгоритм расчёта потенциалов;
- алгоритм перераспределения перевозок;
- алгоритм расчёта потенциалов для ТТЗ;
- алгоритм перераспределения перевозок для ТТЗ.
Ссылки
- Кривопалов В. Ю., Решение транспортной задачи с промежуточными пунктами с запретами. Сборник ХI конференции «Наука. Творчество» 2015, Самара, Т.1,стр.22-27.
- Участник:Logic-samara