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

Открытая транспортная задача с промежуточными пунктами (ТЗПП открытая) — транспортная задача с промежуточными пунктами, в которой нарушен баланс ресурсов и потребностей (дисбаланс).

Открытая ТЗПП

Обозначения

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

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

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

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

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

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

$b_{j}>0,j=1,2,...,np$ — объём поставок продукции поставщиков;

$b_{np+j}<0,j=1,2,...,{n-np}$ — объём потребностей (в продукции) потребителей;

$a_{i}>0,i=1,2,...,m$ — дополнительные (внутренние) потребности продукции (на складе);

$a_{i}\leq 0,i=1,2,...,{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}$ — объём перевозок продукции со склада к потребителю.

Условие дисбаланса

Условие нарушения баланса ресурсов и потребностей

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

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

В зависимости от вида неравенств различают следующие виды открытых ТЗПП.

Открытая ТЗПП 1

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

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

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

$\sum _{j=1}^{n}x_{ij}=a_{i},i=1,2,...,m$

$\sum _{i=1}^{m}x_{ij}\leq b_{j},j=1,2,...,{np}$

$\sum _{i=1}^{m}x_{inp+j}=b_{j},j=1,2,...,{n-np}$

$x_{ij}\geq 0,i=1,2,...,m,j=1,2,...,n$

$x_{inp+j}\leq 0,i=1,2,...,m,j=1,2,...,{n-np}$

Условие дисбаланса

Избыток продукта у поставщиков.

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

Открытая ТЗПП 2

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

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

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

$\sum _{j=1}^{n}x_{ij}=a_{i},i=1,2,...,{mp}$

$\sum _{j=1}^{n}x_{mp+ij}\geq a_{mp+i},i=1,2,...,{m-mp}$

$\sum _{i=1}^{m}x_{ij}=b_{j},j=1,2,...,n$

$x_{ij}\geq 0,i=1,2,...,m,j=1,2,...,n$

$x_{inp+j}\leq 0,i=1,2,...,m,j=1,2,...,{n-np}$

Условие дисбаланса

Избыточные запасы на складах.

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

Открытая ТЗПП 3

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

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

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

$\sum _{j=1}^{n}x_{ij}=a_{i},i=1,2,...,m$

$\sum _{i=1}^{m}x_{ij}=b_{j},j=1,2,...,{np}$

$\sum _{i=1}^{m}x_{inp+j}\geq b_{j},j=1,2,...,{n-np}$

$x_{ij}\geq 0,i=1,2,...,m,j=1,2,...,n$

$x_{inp+j}\leq 0,i=1,2,...,m,j=1,2,...,{n-np}$

Условие дисбаланса

Избыточные потребности у потребителей.

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

Открытая ТЗПП 4

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

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

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

$\sum _{j=1}^{n}x_{ij}\leq a_{i},i=1,2,...,{mp}$

$\sum _{j=1}^{n}x_{mp+ij}=a_{mp+i},i=1,2,...,{m-mp}$

$\sum _{i=1}^{m}x_{ij}=b_{j},j=1,2,...,n$

$x_{ij}\geq 0,i=1,2,...,m,j=1,2,...,n$

$x_{inp+j}\leq 0,i=1,2,...,m,j=1,2,...,{n-np}$

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

Условие дисбаланса

Избыточные дополнительные потребности на складах.

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

См.также

• Открытая транспортная задача

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

• Транспортная задача;
• Распределительная задача;
• Задача о назначениях;
• Транспортная задача с промежуточными пунктами;
• Транспортная задача с промежуточными пунктами с запретами;
• Транспортная задача с промежуточными пунктами и ограничением по транзиту;
• Открытая транспортная задача с промежуточными пунктами;
• Открытая транспортная задача с промежуточными пунктами 1;
• Открытая транспортная задача с промежуточными пунктами 2;
• Открытая транспортная задача с промежуточными пунктами 3;
• Открытая транспортная задача с промежуточными пунктами 4;
• Трёхиндексная транспортная задача.

Литература

• Кривопалов В. Ю., Решение открытой транспортной задачи с промежуточными пунктами. Сборник научных трудов конференции ПИТ-2015, СГАУ, Т.2, стр.86-91.

Ссылки

• 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.
• http://www.ssau.ru/files/events/2015/pit_2015_2.pdf стр.86-91.

Одним из источников, использованных при создании данной статьи, является статья из википроекта «Рувики» («ruwiki.ru») под названием «Открытая транспортная задача с промежуточными пунктами», расположенная по адресу: — «https://ru.ruwiki.ru/wiki/Открытая_транспортная_задача_с_промежуточными_пунктами» Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC-BY-SA 4.0 и более поздних версий. Всем участникам Рувики предлагается прочитать материал «Почему Циклопедия?».