Метод потенциалов для транспортной задачи

Метод потенциалов для ТЗ — это метод решения транспортной задачи. Метод позволяет с помощью потенциалов определить оценки оптимальности, определить новую (оптимизирующую) перевозку, построить для неё цикл перераспределения перевозок и перейти к более оптимальному решению.

Обозначения

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

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

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

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

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

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

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

$a_{i}$ — объём поставок (продукции) поставщика $i,\forall i\in N_{m}$ ;

$b_{j}$ — объём потребностей (в продукции) потребителя $j,\forall j\in N_{n}$ ;

$c_{ij}$ — транспортный тариф на перевозку $(i,j),\forall (i,j)\in {N_{m}\times N_{n}}$ ;

$x_{ij}$ — объём перевозок $(i,j),\forall (i,j)\in {N_{m}\times N_{n}}$ ;

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

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

$E$ — множество не просмотренных клеток;

$A_{m}$ — вектор поставок $a_{i}$ ;

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

$C_{m\times n}$ — матрица транспортных тарифов $c_{ij}$ ;

$X_{m\times n}$ — матрица перевозок $x_{ij}$ ;

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

Алгоритм

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

1. Находим допустимое опорное решение $X_{m\times n}$ и базис $Z_{m\times n}$ с помощью алгоритма северо-западного угла или алгоритма минимального элемента.

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

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

4. Проверяем решение $X_{m\times n}$ на оптимальность. Если $\Delta _{o}=0$ , то решение $X_{m\times n}$ — оптимальное и конец работы.

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

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

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

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

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

Литература

• Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа, М.,1969.

Ссылки

• Пример решения ТЗ.