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

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

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

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

В экономической транспортной системе имеются 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).

Пусть D — это множество запрещённых перевозок (коммуникаций), оно содержит k элементов (запретов), D={(i_t, j_t), t=1,k}.

Тогда математическая модель задачи с запретами принимает вид:

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

${\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}\geq 0,\forall (i,j)\in N_{m}\times N_{np}\\x_{inp+j}\leq 0,\forall (i,j)\in N_{m}\times N_{n-np}\\x_{ij}=0,\forall (i,j)\in D\end{cases}}$,

где x_ij — объём перевозок продукта между промежуточным пунктом Ai и конечным пунктом Bj.

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

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

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

то есть необходимо, чтобы алгебраическая сумма поставок на склады и отрицательных поставок со складов (потребностей в продукции) равнялась алгебраической сумме дополнительных потребностей в продукции на складах. Но для задачи с запретами решение может отсутствовать, например, если запретов слишком много. Следовательно, условия баланса не являются достаточными.

Постановка вспомогательной задачи

Для построения вспомогательной задачи введём новые обозначения:

M — это достаточно большое положительное число.

${c_{ij}}^{*}=c_{ij},\forall (i,j)\in {(N_{m}\times N_{n})\setminus D}$,

${c_{ij}}^{*}=M,\forall (i,j)\in {(N_{m}\times N_{np})\cap D}$,

${c_{inp+j}}^{*}=-M,\forall (i,np+j)\in {(N_{m}\times N_{n})\cap D}$.

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

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

${\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}\geq 0,\forall (i,j)\in N_{m}\times N_{np}\\x_{inp+j}\leq 0,\forall (i,j)\in N_{m}\times N_{n-np}\end{cases}}$.

Решение вспомогательной задачи

Очевидно, что вспомогательная задача является закрытой транспортной задачей с промежуточными пунктами, которая разрешима по построению. Для определения начального решения используется метод северо-западного угла, а для решения применяется метод потенциалов. M-множители и метод потенциалов приводят к нулевым запретным перевозкам в оптимальном решении. Если все запретные перевозки в оптимальном решении вспомогательной задачи равны нулю, то исходная задача с запретами решена, если нет, то исходная задача с запретами не имеет решения.

Для более эффективного решения ТЗПП с запретами, предлагается эвристический алгоритм решения ТЗПП с запретами, в котором M-множители заменяются на конкретные числа.

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

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

Литература

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

Ссылки

• 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. Перевод статьи.