Алгоритм решения ТЗПП с запретами

Алгоритм решения ТЗПП с запретами — это эвристический алгоритм решения транспортной задачи с промежуточными пунктами с запретами.

Обозначения

Введём обозначения:

m – число промежуточных пунктов (складов);

n – число конечных пунктов (поставщиков и потребителей);

mp – число складов с положительными дополнительными потребностями;

np – число поставщиков;

k – число запретов;

a_i – дополнительная потребность (со знаком) i-ого промежуточного пункта (склада);

b_j – объём грузов (со знаком) j-ого конечного пункта (для поставщиков объём положительное число, для потребителей – отрицательное);

x_ij – объём перевозки (со знаком) между i-ым промежуточным пунктом и j-ым конечным пунктом;

(i_t, j_t) – t-ая запрещённая коммуникация (перевозка).

D – это множество запрещённых коммуникаций, D={(i_t, j_t), t=1,k}.

Алгоритм

Входные данные: m; n; mp; np; k; {a₁, a₂, ..., a_m}; {b₁, b₂, ..., b_n}; {c₁₁, c₁₂, ..., c_mn}; {(i₁, j₁), (i₂, j₂), ..., (i_k, j_k)}.

Выходные данные: L; {x₁₁, x₁₂, …, x_mn).

Другие алгоритмы:

• алгоритм северо-западного угла для ТЗ;
• алгоритм северо-западного угла для ТЗПП;
• алгоритм расчёта потенциалов для ТЗ;
• алгоритм расчёта потенциалов для ТЗПП;
• алгоритм перераспределения перевозок для ТЗ;
• алгоритм перераспределения перевозок для ТЗПП;
• алгоритм решения ТЗПП с запретами;
• алгоритм минимального элемента для ТТЗ;
• алгоритм расчёта потенциалов для ТТЗ;
• алгоритм перераспределения перевозок для ТТЗ.

Ссылки

• Кривопалов В. Ю., Решение транспортной задачи с промежуточными пунктами с запретами. Сборник ХI конференции «Наука. Творчество» 2015, Самара, Т.1,стр.22-27.
• Участник:Logic-samara