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

Определение

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

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

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

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

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

B₀ – базис решения (множество базисных перевозок решения);

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

G – множество узлов целочисленной решётки, состоящее из множества базисных перевозок решения и перевозки (i₀,j₀);

Δx – перераспределяемая часть перевозки;

(i_x,j_x) – перевозка с перераспределяемым приращением Δx.

Алгоритм

Входные данные: m; n; np; B₀; (i₀,j₀); {x₁₁, x₁₂, ..., x_mn}.

Выходные данные: Δx; (i_x,j_x); {x₁₁, x₁₂, ..., x_mn}.

• Заметим, что данный алгоритм применим для транспортной задачи, при этом np=n, а промежуточные пункты (склады) являются потребителями. Матрицы тарифов и перевозок в алгоритме транспонированы (строки заменены на столбцы, а столбцы - на строки).

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

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

Ссылки

• Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.
• Участник:Logic-samara