Циклопедия скорбит по жертвам террористического акта в Крокус-Сити (Красногорск, МО)

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

Материал из Циклопедии
Перейти к навигации Перейти к поиску

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

Обозначения[править]

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}.

АМЭ03.JPG

Выходные данные: {x111, x112, …, xmnk}.

Другие алгоритмы:[править]


Литература[править]

  • Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи — М.: ВИМИ, 1990 г. деп. № Д08221.
  • Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи — Сборник ХI конференции «Наука. Творчество» 2015, Самара, Т. 1.

Ссылки[править]

 
Транспортная задача

Транспортная задача (классическая) • Решение симплекс-методомРешение в ExcelТранспортная задача с промежуточными пунктами (и ограничением по транзиту, с запретами) • Трёхиндексная транспортная задача (алгоритм минимального элемента)

Начальное решение

Метод северо-западного углаМетод минимальных тарифовМетод Фогеля‎

Вырожденные случаи

Вырожденность в ТЗАцикличность в ТЗ