Алгоритм минимального элемента для ТТЗ

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

Содержание

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

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

n – число потребителей;

k – число продуктов;

A_i - i-ый поставщик, 1≤i≤m;

B_j - j-ый потребитель, 1≤j≤n;

C_t - t-ый продукт, 1≤t≤k;

a_it - объём поставок продукта Сt от поставщика Ai;

b_jt - объём потребностей в продукте Сt у потребителя Bj;

c_ij - объём перевозок от поставщика Ai к потребителю Bj;

d_ijt - транспортные расходы d_ijt на перевозку единицы (тариф) продукта Ct от поставщика Ai к потребителю Bj;

x_ijt - объём перевозок продукта Ct от поставщика Ai к потребителю Bj;

B₀ – базис решения (множество базисных элементов (i,j,t));

do – минимальный тариф на множестве E;

(i₀, j₀, t₀) – элемент с тарифом do и перевозкой равной нулю (до перераспределения);

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

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

Входные данные: m; n; k; {a₁₁, a₁₂, …, a_mk}; {b₁₁, b₁₂, …, b_nk}; {c₁₁, c₁₂, …, c_mn}; {d₁₁₁, d₁₁₂, ..., d_mnk}.

Выходные данные: {x₁₁₁, x₁₁₂, …, x_mnk}; {x₁₁₁, x₁₁₂, …, x_{m+1 n+1 k+1}}.

Заметим, что при отсутствии опорного решения исходной задачи (после завершения работы алгоритма), возможно использование опорного решения вспомогательной задачи. Для этого нужно решить вспомогательную задачу методом потенциалов.

Кривопалов Ю. А. Метод минимального элемента для нахождения опорного решения для трёхиндексной транспортной задачи. М., ВИМИ, 1990г. деп. № Д08222.
Кривопалов Ю. А. Метод минимального элемента для нахождения опорного решения для трёхиндексной транспортной задачи. Сборник ХII конференции «Наука. Творчество» 2016, Самара, Т.1.
Участник:Logic-samara