Алгоритм решения ТЗПП с запретами — различия между версиями
Ws (обсуждение | вклад) (Восстановление статей Logic-samara) |
м |
||
(не показано 8 промежуточных версий 2 участников) | |||
Строка 1: | Строка 1: | ||
− | |||
'''Алгоритм решения ТЗПП с запретами''' — это эвристический алгоритм решения [[Транспортная задача с промежуточными пунктами с запретами|транспортной задачи с промежуточными пунктами с запретами]]. | '''Алгоритм решения ТЗПП с запретами''' — это эвристический алгоритм решения [[Транспортная задача с промежуточными пунктами с запретами|транспортной задачи с промежуточными пунктами с запретами]]. | ||
− | + | == Обозначения == | |
− | + | ||
− | + | ||
'''m''' – число промежуточных пунктов (складов); | '''m''' – число промежуточных пунктов (складов); | ||
Строка 22: | Строка 19: | ||
'''(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>)}'''. | ||
Строка 29: | Строка 25: | ||
[[файл:ТЗПП33.JPG]] | [[файл:ТЗПП33.JPG]] | ||
− | Выходные данные: '''L; {x<sub>11</sub>,x<sub>12</sub>, …,x<sub>mn</sub>)'''. | + | Выходные данные: '''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]] | ||
− | [[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Алгоритмы]] | + | [[Категория:Математика]][[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Алгоритмы]] |
Текущая версия на 12:05, 16 января 2024
Алгоритм решения ТЗПП с запретами — это эвристический алгоритм решения транспортной задачи с промежуточными пунктами с запретами.
Содержание
Обозначения
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