Транспортная задача с промежуточными пунктами

Математическая модель ТЗПП

Математическая модель эквивалентной ТЗПП

Математическая модель классической ТЗПП

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

ТЗПП позволяет оптимизировать мультимодальные транспортные перевозки.

Постановка задачи ТЗПП

Пусть имеется m поставщиков (A₁, A₂, …, A_m), n потребителей (B₁, B₂, …, B_n) и k промежуточных пунктов (C₁, C₂, …, C_k) однородного продукта. Пусть заданы объёмы поставок a_i>0 продукта поставщиком A_i, объёмы потребностей b_j>0 в продукте у потребителя B_j, объёмы дополнительных потребностей c_t>0 в продукте в промежуточном пункте (на складе) C_t, причём если c_t<0, то дополнительные потребности являются избытком. Пусть известны транспортные расходы d_ti на перевозку единицы продукта от поставщика A_i на склад C_t, и транспортные расходы q_tj на перевозку единицы продукта со склада C_t к потребителю B_j и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда транспортная задача с промежуточными пунктами формулируется следующим образом:

$L(X,Y)=\sum \limits _{t=1}^{k}\sum \limits _{i=1}^{m}d_{ti}x_{ti}+\sum \limits _{t=1}^{k}\sum \limits _{j=1}^{n}q_{tj}y_{tj}\rightarrow \min$

${\begin{cases}\sum \limits _{t=1}^{k}x_{ti}=a_{i},\ \forall i\in N_{m}\\\sum \limits _{t=1}^{k}y_{tj}=b_{j},\ \forall j\in N_{n}\\\sum \limits _{i=1}^{m}x_{ti}-\sum \limits _{j=1}^{n}y_{tj}=c_{t},\ \forall t\in N_{k}\\x_{ti}\geq 0,\forall (t,i)\in N_{k}\times N_{m}\\y_{tj}\geq 0,\forall (t,j)\in N_{k}\times N_{n}\end{cases}}$,

где x_ti — объём перевозок продукта от поставщика A_i на склад C_t,

y_tj — объём перевозок продукта со склада C_t к потребителю B_j.

Условия разрешимости

Для разрешимости задачи необходимо выполнение условий баланса:

$\sum \limits _{i=1}^{m}a_{i}-\sum \limits _{j=1}^{n}b_{j}=\sum \limits _{t=1}^{k}c_{t}$,

то есть необходимо, чтобы объём поставок продукта поставщиками минус объём потребностей в нём у потребителей равнялся объёму дополнительных потребностей продукта на складе. В этом случае транспортная задача с промежуточными пунктами называется закрытой. Базис ТЗПП в данной постановке содержит m+n+k-1 базисных элементов.

Постановка эквивалентной задачи

Введём новые обозначения:

$x_{tm+j}=-y_{tj},\forall (t,j)\in N_{k}\times N_{n}$,

$d_{tm+j}=-q_{tj},\forall (t,j)\in N_{k}\times N_{n}$,

$a_{m+j}=-b_{j},\forall j\in N_{n}$.

Математическая модель эквивалентной задачи принимает следующий вид:

$L^{*}(X)=\sum \limits _{t=1}^{k}\sum \limits _{i=1}^{m+n}d_{ti}x_{ti}\rightarrow \min$

${\begin{cases}\sum \limits _{t=1}^{k}x_{ti}=a_{i},\ \forall i\in N_{m+n}\\\sum \limits _{i=1}^{m+n}x_{ti}=c_{t},\ \forall t\in N_{k}\\x_{ti}\geq 0,\forall (t,i)\in N_{k}\times N_{m}\\x_{tm+j}\leq 0,\forall (t,j)\in N_{k}\times N_{n}\end{cases}}$,

Условия разрешимости эквивалентной задачи

Для разрешимости эквивалентной задачи необходимо выполнение условий баланса:

$\sum \limits _{i=1}^{m+n}a_{i}=\sum \limits _{t=1}^{k}c_{t}$,

то есть необходимо, чтобы объём поставок продукта на склады и объём отрицательных поставок со складов (потребностей в продукте) равнялся объёму дополнительных потребностей в продукте на складах. В этом случае транспортная задача с промежуточными пунктами называется закрытой. Базис эквивалентной ТЗПП содержит m+n+k-1 базисных элементов.

Постановка классической задачи

В экономической транспортной системе имеются n конечных пунктов (np поставщиков продукции и n-np потребителей продукции) и m промежуточных пунктов (складов). Продукция перевозится от поставщиков на склады, будем обозначать эти перевозки положительными переменными x_ij≥0, (i=1,m, j=1,np). А со складов часть продукции перевозится потребителям — их обозначим отрицательными переменными x_ij≤0, (i=1,m, j=np+1,n). Объёмы поставок поставщиков обозначим положительными числами b_j>0, (j=1,np), объёмы потребностей потребителей обозначим отрицательными числами b_j<0, (j=np+1,n). Если склад имеет дополнительные (внутренние) потребности продукции, то обозначим их положительными числами a_i>0, (i=1,mp). Если склад имеет излишки продукции или нулевые остатки, то обозначим их числами a_i≤0, (i=mp+1,m). Транспортные тарифы на перевозку единицы продукции от поставщика на склад выразим положительными числами c_ij>0, (i=1,m, j=1,np), транспортные тарифы на перевозку со склада к потребителю выразим отрицательными числами c_ij<0, (i=1,m, j=np+1,n). Тогда математическая модель задачи принимает вид:

$L(X)=\sum \limits _{i=1}^{m}\sum \limits _{j=1}^{n}c_{ij}x_{ij}\rightarrow \min$

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{cases}\sum\limits_{j=1}^n x_{ij}=a_i, \ \forall i\in N_m \\ \sum\limits_{i=1}^m x_{ij}=b_j, \ \forall j\in N_n \\ x_{ij} \ge 0, \forall (i,j)\in N_m\times N_{np} \\ x_{inp+j} \le 0, \forall (i,j)\in N_m\times N_{n-np} \end{cases}} ,

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

.

Условия разрешимости классической задачи

Для разрешимости классической задачи необходимо выполнение условий баланса:

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \sum\limits_{i=1}^m a_i=\sum\limits_{j=1}^n b_j} ,

то есть необходимо, чтобы алгебраическая сумма объёмов продукта промежуточных пунктов равнялась алгебраической сумме объёмов продукта конечных пунктов. В этом случае транспортная задача с промежуточными пунктами называется закрытой.

Метод решения ТЗПП

Необходимо найти начальное опорное решение, например, методом северо-западного угла.

Затем транспортная задача с промежуточными пунктами решается обобщённым методом потенциалов для решения транспортной задачи модифицированным с учётом отрицательных перевозок. Базис классической ТЗПП содержит m+n-1 базисных элементов.

Метод северо-западного угла

 → Метод северо-западного угла для ТЗПП

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

1.Сначала удовлетворяем дополнительные потребности складов (a_i>0) за счёт поставщиков (b_j>0), то есть назначаем соответствующие положительные перевозки по формулам: x_ij=min(ai, bj), ai=ai-x_ij, b_j=b_j-x_ij.

2.Затем распределяем остатки грузов от поставщиков (b_j>0) на последний используемый склад, то есть начиная с последней заполненной строки по формулам: x_ij=b_j, a_i=a_i-x_ij, b_j=0.

3.Наконец, удовлетворяем потребности потребителей (b_j<0), то есть назначаем соответствующие отрицательные перевозки по формулам: x_ij=max(a_i,b_j), a_ij=a_i-x_ij, b_j=b_j-x_ij.

Метод северо-западного угла реализуется с помощью алгоритма северо-западного угла.

Метод потенциалов

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

1.Берём решение Xmxn и базис Zmxn, найденные с помощью алгоритма северо-западного угла для ТЗПП.

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

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

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

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

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

Другие задачи

1. Транспортная задача;
2. Распределительная задача;
3. Задача о назначениях;
4. Транспортная задача с промежуточными пунктами;
5. Транспортная задача с промежуточными пунктами с запретами;
6. Транспортная задача с промежуточными пунктами и ограничением по транзиту;
7. Открытая транспортная задача с промежуточными пунктами;
8. Открытая транспортная задача с промежуточными пунктами 1;
9. Открытая транспортная задача с промежуточными пунктами 2;
10. Открытая транспортная задача с промежуточными пунктами 3;
11. Открытая транспортная задача с промежуточными пунктами 4;
12. Трёхиндексная транспортная задача;
13. Трёхиндексная транспортная задача с аксиальными суммами;
14. Трёхиндексная транспортная задача с промежуточными пунктами.

Литература

• Кривопалов В. Ю., Модель транспортной задачи с промежуточными пунктами в матричной постановке, «Вестник Самарского государственного аэрокосмического университета» № 3, 2012.
• Кривопалов В. Ю., Метод северо-западного угла для нахождения допустимого решения транспортной задачи с промежуточными пунктами. Сборник конференции ПИТ-2014, СГАУ, стр.369-372
• Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 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. Перевод статьи.
• http://www.ssau.ru/files/events/2014/pit_14_1_6.pdf стр.369-372.