Метод потенциалов для транспортной задачи с промежуточными пунктами

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

Обозначения

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

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

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

m-mp — число складов с излишками продукции или нулевыми остатками;

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

n-np — число потребителей;

L — целевая функция — стоимость затрат на перевозки;

Δ_o — оценка оптимальности решения;

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

(i_o,j_o) — вводимая в базис перевозка;

(i_x,j_x) — выводимая из базиса перевозка;

a_i>0 — дополнительные потребности продукции на складе i, ⱯiϵN_mp;

a_mp+i≤0 — излишки продукции или нулевые остатки на складе mp+i, ⱯiϵN_m-mp;

b_j>0 — объём поставок продукции поставщика j, ⱯjϵN_np;

b_np+j<0 — объём потребностей (в продукции) потребителя np+j, ⱯjϵN_n-np;

c_ij>0 — транспортный тариф на перевозку единицы продукции от поставщика j на склад i, Ɐ(i,j)ϵN_mxN_np;

c_inp+j<0 — транспортный тариф на перевозку единицы продукции со склада i к потребителю np+j, Ɐ(i,j)ϵN_mxN_n-np;

x_ij≥0 — объём перевозок продукции от поставщика j на склад i, Ɐ(i,j)ϵN_mxN_np;

x_inp+j≤0 — объём перевозок продукции со склада i к потребителю np+j, Ɐ(i,j)ϵN_mxN_n-np;

z_ij — булева переменная обозначающая принадлежность перевозки к базису: 1 — принадлежит базису, 0 — не принадлежит базису, Ɐ(i,j)ϵN_mxN_n;

B_o — базис решения — множество базисных перевозок (элементов) решения;

G — вспомогательное множество для построения цикла перераспределения перевозок;

X_mxn — матрица перевозок — текущее и новое решения.

A_m — вектор объёмов перевозок промежуточных пунктов (складов) a_i;

B_n — вектор объёмов перевозок конечных пунктов (поставщиков и потребителей) b_j;

C_mxn — матрица тарифов с_ij;

X_mxn — матрица перевозок x_mxn;

Z_mxn — матрица базисных элементов z_mxn.

Алгоритм

Входные данные: m, mp, n, np, A_m, B_n, C_mxn.

1. Находим допустимое опорное решение X_mxn и базис Z_mxn с помощью алгоритма северо-западного угла для ТЗПП.

2. Определяем значение целевой функции L=∑_i=1,m∑_j=1,n c_ijx_ij и базис опорного решения B_o={(i,j)|z_ij=1}.

3. Определяем оценку Δ_o и элемент (i_o,j_o) с помощью алгоритма расчёта потенциалов и оценок оптимальности для ТЗПП.

4. Проверяем решение X_mxn на оптимальность. Если Δ_o=0, то решение X_mxn — оптимальное и конец работы.

5. Определяем приращение Δ_x, элемент (i_x,j_x) и новое опорное решение X_mxn с помощью алгоритма перераспределения перевозок для ТЗПП.

6. Определяем новое значение целевой функции L=L-Δ_oΔ_x и новый базис B_o=B_o/(i_x,j_x)U(i_o,j_o). Переходим к пункту 3.

Выходные данные: L, X_mxn.

Другие алгоритмы

1. Алгоритм метода потенциалов для ТЗ:
   1. алгоритм северо-западного угла для ТЗ;
   2. алгоритм минимального элемента для ТЗ;
   3. алгоритм расчёта потенциалов для ТЗ;
   4. алгоритм перераспределения перевозок для ТЗ;
2. Алгоритм метода потенциалов для ТЗПП:
   1. алгоритм северо-западного угла для ТЗПП;
   2. алгоритм расчёта потенциалов для ТЗПП;
   3. алгоритм перераспределения перевозок для ТЗПП;
   4. алгоритм решения ТЗПП с запретами;
3. Алгоритм метода потенциалов для ТТЗ:
   1. алгоритм минимального элемента для ТТЗ;
   2. алгоритм расчёта потенциалов для ТТЗ;
   3. алгоритм перераспределения перевозок для ТТЗ;
4. Алгоритм метода потенциалов для ТТЗАС:
   1. алгоритм трёхгранного угла для ТТЗАС;
   2. алгоритм расчёта потенциалов для ТТЗАС;
   3. алгоритм перераспределения перевозок для ТТЗАС;
5. Алгоритм метода потенциалов для ТТЗПП:
   1. алгоритм расчёта потенциалов для ТТЗПП;
   2. алгоритм перераспределения перевозок для ТТЗПП.

Другие методы

1. Метод потенциалов для ТЗ;
2. Метод минимального элемента для ТЗ;
3. Метод северо-западного угла для ТЗ;
4. Метод потенциалов для ТЗПП;
5. Метод северо-западного угла для ТЗПП;
6. Метод потенциалов для ТТЗ;
7. Метод минимального элемента для ТТЗ;
8. Метод потенциалов для ТТЗАС;
9. Метод трёхгранного угла для ТТЗАС;
10. Метод потенциалов для ТТЗПП.

Литература

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

Ссылки

• Krivopalov V. Y., Krivopalov Y. A. The potential method for solving the transportation problem with transit points. New Magenta Papers. Magenta Technology, 2013. — Vol.2 — P.31-38. Перевод статьи.

Одним из источников, использованных при создании данной статьи, является статья из википроекта «Рувики» («ruwiki.ru») под названием «Метод потенциалов для транспортной задачи с промежуточными пунктами», расположенная по адресу: — «https://ru.ruwiki.ru/wiki/Метод_потенциалов_для_транспортной_задачи_с_промежуточными_пунктами» Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC-BY-SA 4.0 и более поздних версий. Всем участникам Рувики предлагается прочитать материал «Почему Циклопедия?».