Алгоритм минимального элемента для ТТЗ
Алгоритм минимального элемента для ТТЗ — это алгоритм построения опорного решения для трёхиндексной транспортной задачи (ТТЗ).
Обозначения[править]
m – число поставщиков;
n – число потребителей;
k – число продуктов;
Ai - i-ый поставщик, 1≤i≤m;
Bj - j-ый потребитель, 1≤j≤n;
Ct - t-ый продукт, 1≤t≤k;
ait - объём поставок продукта Сt от поставщика Ai;
bjt - объём потребностей в продукте Сt у потребителя Bj;
cij - объём перевозок от поставщика Ai к потребителю Bj;
dijt - транспортные расходы dijt на перевозку единицы (тариф) продукта Ct от поставщика Ai к потребителю Bj;
xijt - объём перевозок продукта Ct от поставщика Ai к потребителю Bj;
B0 – базис решения (множество базисных элементов (i,j,t));
do – минимальный тариф на множестве E;
(i0, j0, t0) – элемент с тарифом do и перевозкой равной нулю (до перераспределения);
Δx – перераспределяемая часть перевозки;
(ix, jx, tx) – элемент с перевозкой равной приращению Δx (до перераспределения).
Алгоритм[править]
Входные данные: m; n; k; {a11, a12, …, amk}; {b11, b12, …, bnk}; {c11, c12, …, cmn}; {d111, d112, ..., dmnk}.
Выходные данные: {x111, x112, …, xmnk}.
Другие алгоритмы:[править]
- алгоритм северо-западного угла для ТЗ;
- алгоритм расчёта потенциалов для ТЗ;
- алгоритм перераспределения перевозок для ТЗ;
- алгоритм северо-западного угла для ТЗПП;
- алгоритм расчёта потенциалов для ТЗПП;
- алгоритм перераспределения перевозок для ТЗПП;
- алгоритм решения ТЗПП с запретами;
- алгоритм минимального элемента для ТТЗ;
- алгоритм расчёта потенциалов для ТТЗ;
- алгоритм перераспределения перевозок для ТТЗ.
Литература[править]
- Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи — М.: ВИМИ, 1990 г. деп. № Д08221.
- Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи — Сборник ХI конференции «Наука. Творчество» 2015, Самара, Т. 1.
Ссылки[править]
↑ [+] | |
---|---|
Транспортная задача |
Транспортная задача (классическая) • Решение симплекс-методом • Решение в Excel • Транспортная задача с промежуточными пунктами (и ограничением по транзиту, с запретами) • Трёхиндексная транспортная задача (алгоритм минимального элемента) |
Начальное решение |
Метод северо-западного угла • Метод минимальных тарифов • Метод Фогеля |
Вырожденные случаи |