Метод потенциалов для ТЗПП

Метод потенциалов для ТЗПП — метод решения ТЗПП.

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

Обозначения

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

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

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

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

$mp$ — число складов с дополнительными (внутренними) потребностями;

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

$c_{ij}>0,i=1,2,...,m,j=1,2,...,{np}$ — транспортные тарифы на перевозку единицы продукции от поставщика на склад;

$c_{inp+j}<0,i=1,2,...,m,j=1,2,...,{n-np}$ — транспортные тарифы на перевозку единицы продукции со склада к потребителю;

$x_{ij}\geq 0,i=1,2,...,m,j=1,2,...,{np}$ — объём перевозок продукции от поставщика на склад;

$x_{inp+j}\leq 0,i=1,2,...,m,j=1,2,...,{n-np}$ — объём перевозок продукции со склада к потребителю;

$z_{ij},i=1,2,...,m,j=1,2,...,n$ — булевы переменные обозначающие принадлежность перевозок к базису: 1 — принадлежит базису, 0 — не принадлежит базису;

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

$X_{m\times n}$ — матрица перевозок — текущее решение;

$Z_{m\times n}$ — матрица базисных и не базисных переменных;

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

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

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

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

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

Алгоритм

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

Литература

• Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 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 и более поздних версий. Всем участникам Рувики предлагается прочитать материал «Почему Циклопедия?».