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

Алгоритм перераспределения перевозок для ТЗПП

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

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

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

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

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

mp – число складов с положительными дополнительными потребностями (0≤mp≤m);

np – число поставщиков (конечных пунктов c положительными значениями) (1<np<n);

B0 – базис решения (множество базисных перевозок решения (ik, jk), 0<k<m+n);

xij – объём (со знаком) перевозки продукции между i-ым промежуточным пунктом и j-ым конечным пунктом (объём перевозки (i,j));

G – множество узлов целочисленной решётки, состоящее из множества базисных перевозок решения и перевозки (i0, j0);

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

(ix, jx) – перевозка с перераспределяемым приращением Δx.

Алгоритм 1[править]

Входные данные:

BX002.png

Алгоритм

РПР010.png

Выходные данные:

DX001.png

Алгоритм 2[править]

Входные данные:

BX002.png

Алгоритм

РПР011.png

Выходные данные:

DX001.png

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

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


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

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

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

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

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

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

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

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

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