Алгоритм решения ТЗПП с запретами
Содержание
Определение
Алгоритм решения ТЗПП с запретами — это эвристический алгоритм решения транспортной задачи с промежуточными пунктами с запретами.
Введём обозначения:
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