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

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

Обозначения

$m$ — число поставщиков;

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

$k$ — число типов транспорта;

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

$\Delta _{o}$ — оценка оптимальности решения;

$\Delta _{x}$ — перераспределяемая часть перевозки;

$(i_{o},j_{o},t_{o})$ — вводимая в базис перевозка;

$(i_{x},j_{x},t_{x})$ — выводимая из базиса перевозка;

$d_{ijt}$ — транспортный тариф на перевозку единицы груза от поставщика $i$ к потребителю $j$ транспортом типа $t,\forall (i,j,t)\in {N_{m}\times N_{n}\times N_{k}}$ ;

$x_{ijt}$ — объём перевозок груза от поставщика $i$ к потребителю $j$ транспортом типа $t,\forall (i,j,t)\in {N_{m}\times N_{n}\times N_{k}}$ ;

$z_{ijt}$ — булева переменная обозначающая принадлежность перевозки к базису: 1 — принадлежит базису, 0 — не принадлежит базису, $\forall (i,j,t)\in {N_{m}\times N_{n}\times N_{k}}$ ;

$B_{o}$ — множество базисных элементов — базис решения;

$A_{m}$ — вектор объёмов поставок поставщиков $a_{i}$ ;

$B_{n}$ — вектор объёмов потребностей потребителей $b_{j}$ ;

$C_{k}$ — вектор объёмов перевозок по типам транспорта $c_{t}$ ;

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle D_{m\times n\times k}} — трёхмерная матрица тарифов Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle d_{ijt}}  ;

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle X_{m\times n\times k}} — трёхмерная матрица перевозок Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle x_{ijt}}  ;

$Z_{m\times n\times k}$ — трёхмерная матрица базисных элементов $z_{ijt}$ .

Алгоритм

Входные данные: $m,n,k,A_{m},B_{n},C_{k},D_{m\times n\times k}$ .

1. Находим допустимое опорное решение $X_{m\times n\times k}$ и базис $Z_{m\times n\times k}$ с помощью алгоритма трёхгранного угла для ТТЗАС.

2. Определяем значение целевой функции $L=\sum _{i=1}^{m}\sum _{j=1}^{n}\sum _{t=1}^{k}d_{ijt}x_{ijt}$ и базис опорного решения $B_{o}=\{(i,j,t)|z_{ijt}=1\}$ .

3. Определяем оценку $\Delta _{o}$ и элемент $(i_{o},j_{o},t_{o})$ с помощью алгоритма расчёта потенциалов для ТТЗАС.

4. Проверяем решение $X_{m\times n\times k}$ на оптимальность. Если $\Delta _{o}=0$ , то решение $X_{m\times n\times k}$ — оптимальное и конец работы, иначе определяем $E^{+}=\{(i,j,t)|\Delta _{ijt}\geq 0\}\setminus B_{o}$ .

5. Определяем приращение $\Delta _{x}$ , элемент $(i_{x},j_{x},t_{x})$ и новое опорное решение $X_{m\times n\times k}$ с помощью алгоритма перераспределения перевозок для ТТЗАС.

Если нового допустимого опорного решения нет, то переходим к пункту 7.

6. Определяем новое значение целевой функции $L=L-\Delta _{o}\cdot \Delta _{x}$ и новый базис $B_{o}=B_{o}\setminus (i_{x},j_{x},t_{x})\cup (i_{o},j_{o},t_{o})$ . Переходим к пункту 3.

7. Определяем множество $E^{+}=E^{+}\setminus (i_{o},j_{o},t_{o})$ и новую оценку $\Delta _{o}$ и элемент $(i_{o},j_{o},t_{o})$ из множества $E^{+}$ . Если $\exists (i_{o},j_{o},t_{o})\in E^{+}$ , то переходим к пункту 5, иначе конец работы.

Выходные данные: $L,X_{m\times n\times k}$ .

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

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. Метод потенциалов для ТТЗПП.

Литература

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