Алгоритм минимального элемента для ТТЗ — различия между версиями

Текущая версия на 12:04, 16 января 2024

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

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

@@ Строка 1: / Строка 1: @@
 '''Алгоритм минимального элемента для ТТЗ''' — это алгоритм построения опорного решения для [[Трёхиндексная транспортная задача|трёхиндексной транспортной задачи]] ([[ТТЗ]]).
 == Обозначения ==
-Введём обозначения:
 '''m''' – число поставщиков;
@@ Строка 43: / Строка 41: @@
 ''' {x<sub>111</sub>, x<sub>112</sub>, …, x<sub>m+1 n+1 k+1</sub>}'''.
 *Заметим, что при отсутствии опорного решения исходной задачи (после завершения работы алгоритма), возможно использование опорного решения вспомогательной задачи. Для этого нужно решить вспомогательную задачу [[Трёхиндексная транспортная задача|методом потенциалов]].
-== [[Алгоритм|Другие алгоритмы:]] ==
+== [[Алгоритмы решения транспортных задач|Другие алгоритмы:]] ==
 {{Список АТЗ}}
 == Ссылки ==