Алгоритм решения транспортной задачи с промежуточными пунктами с запретами

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

Обозначения

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).

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

1. Алгоритм метода потенциалов для ТЗ:
   1. алгоритм северо-западного угла для ТЗ;
   2. алгоритм минимального элемента для ТЗ;
   3. алгоритм расчёта потенциалов для ТЗ;
   4. алгоритм перераспределения перевозок для ТЗ;
2. Алгоритм метода потенциалов для ТЗПП:
   1. алгоритм северо-западного угла для ТЗПП;
   2. алгоритм расчёта потенциалов для ТЗПП;
   3. алгоритм перераспределения перевозок для ТЗПП;
   4. алгоритм решения ТЗПП с запретами;
3. Алгоритм метода потенциалов для ТТЗ:
   1. алгоритм минимального элемента для ТТЗ;
   2. алгоритм расчёта потенциалов для ТТЗ;
   3. алгоритм перераспределения перевозок для ТТЗ;
4. Алгоритм метода потенциалов для ТТЗАС:
   1. алгоритм трёхгранного угла для ТТЗАС;
   2. алгоритм расчёта потенциалов для ТТЗАС;
   3. алгоритм перераспределения перевозок для ТТЗАС;
5. Алгоритм метода потенциалов для ТТЗПП:
   1. алгоритм расчёта потенциалов для ТТЗПП;
   2. алгоритм перераспределения перевозок для ТТЗПП.

Литература

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

Ссылки

• Участник:Logic-samara