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

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

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

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

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

Пусть T — это лимит транзита для перегружаемого склада At.

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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 \\ \sum\limits_{j=1}^{np}x_{tj}=\max\{a_t, 0\} +T \\ \sum\limits_{j=1}^{n-np}x_{tnp+j}=\min\{a_t, 0\} -T \\ 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}} ,

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

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

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

Невозможно разобрать выражение (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} ,

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

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

Для случая перегруженного пункта с дополнительной потребностью a_t>0, введём дополнительный склад A_m+1 («двойник» склада A_t) с избытком a_m+1=-T и пересчитаем для склада A_t дополнительную потребность a_t=a_t+T.

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

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle {c_{ij}}^*=c_{ij}, \forall (i,j)\in (N_m \setminus \{t\})\times N_n} ,

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle {c_{tj}}^*=c_{tj}, \forall j\in N_{np}} ,

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle {c_{tnp+j}}^*=-M, \forall j\in N_{n-np}} ,

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

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

Для случая перегруженного пункта с избытком a_t≤0, введём дополнительный склад A_m+1 («двойник» склада A_t) с дополнительной потребностью a_m+1=T и пересчитаем для склада A_t дополнительную потребность a_t=a_t-T. Введём обозначения:

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle {c_{ij}}^*=c_{ij}, \forall (i,j)\in (N_m \setminus \{t\})\times N_n} ,

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle {c_{tj}}^*=M, \forall j\in N_{np}} ,

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle {c_{tnp+j}}^*= c_{tnp+j}, \forall j\in N_{n-np}} ,

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

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

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

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

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

Очевидно, что вспомогательная задача является закрытой транспортной задачей с промежуточными пунктами, которая разрешима по построению. Для определения начального решения используется метод северо-западного угла, а для решения применяется метод потенциалов. Очевидно, что M-множители и метод потенциалов приводят к нулевым соответствующим (сверх установленного лимита T на транзит) перевозкам в оптимальном решении. В оптимальном решении вспомогательной задачи все перевозки через конечные и промежуточные пункты без складов «двойников» являются оптимальным решением исходной задачи. А перевозки складов «двойников» объединяются (складываются) в перевозки склада A_t.

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

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.
• Кривопалов В. Ю., Решение транспортной задачи с промежуточными пунктами и ограничением по транзиту. Сборник ХI конференции «Наука. Творчество» 2015, Самара, Т.1,стр.28-32.

Ссылки

• 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