Алгоритм расчёта потенциалов для ТЗПП

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

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

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

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

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

c_ij – транспортный тариф (со знаком) на перевозку единицы продукции между i-ым промежуточным пунктом и j-ым конечным пунктом (тариф для перевозки (i,j));

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

u_i – потенциал i-ого промежуточного пункта;

v_j – потенциал j-ого конечного пункта;

Δ_ij – оценка оптимальности для перевозки (i,j);

Δo – оценка оптимальности решения;

(i₀,j₀) – перевозка с оценкой Δo.

Входные данные: m; n; np; {c₁₁, c₁₂, ..., c_mn}; B₀.

Выходные данные: Δo; (i₀,j₀).

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

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

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