2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Транспортная задача с ограничениями
Сообщение14.08.2012, 09:01 
Пусть у нас есть 3 поставщика: $D_1, D_2, D_3$ и 2 склада-потребителя $W_1, W_2$
Каждый поставщик поставляет $40$ единиц товара, каждому складу требуется $60$ единиц.
Пусть также у нас есть ограничение на поставку - поставщик $D_2$ на склад $W_1$ не может поставить более $10$ единиц. Это сводится к стандартной транспортной задаче расщеплением склада $W_1$ на два: $W_{11}$ и $W_{12}$.

$\begin{tabular}{c|cc}
& W_1& W_2 \\
\hline
D_1&  & \\
D_2&  \leq10&\\
D_3&  &\\
&60&60
\end{tabular}
\Longrightarrow
\begin{tabular}{c|ccc}
& W_{11}& W_{12}&W_2 \\
\hline
D_1&  & &\\
D_2& X & &\\
D_3&  & &\\
&50&10&60
\end{tabular}
$

Вопрос, что делать в случае нескольких ограничений?
Для случая достаточно малых поставок тоже можно исхитриться. Например, для $D_2$ и $D_3$ на склад $W_1$ заданы ограничения в $10$ и $20$ единиц соответственно:

$\begin{tabular}{c|cc}
& W_1& W_2 \\
\hline
D_1&  & \\
D_2&  \leq10&\\
D_3& \leq20 &\\
&60&60
\end{tabular}
\Longrightarrow
\begin{tabular}{c|cccc}
& W_{11}& W_{12}&W_{13}&W_2 \\
\hline
D_1&  & & &\\
D_2& X & &X &\\
D_3& X & X& &\\
&30&10&20&60
\end{tabular}
$

Но что делать, если сумма ограничений превышает потребности склада (как оно обычно и бывает по факту)?

$\begin{tabular}{c|cc}
& W_1& W_2 \\
\hline
D_1&  & \\
D_2&  \leq35&\\
D_3& \leq35 &\\
&60&60
\end{tabular}
$

 
 
 
 Re: Транспортная задача с ограничениями
Сообщение14.08.2012, 13:01 
Кроме складов можно расщеплять и поставщиков. В последнем примере это решает проблему. Но можно и только складов расщеплять - $W_1$ на три $W_{11},W_{12}, W_{13}$ с суммами (25,25,10) - последний склад - избыток ограничений. И запреты в ячейках $D_2W_{11}, D_3W_{12}$. Кажется получится. Если ограничения например 35 и 40, то расщеплят на 25,20,15.

 
 
 
 Re: Транспортная задача с ограничениями
Сообщение14.08.2012, 15:41 
Shadow, большое спасибо.
Вы правы, расщеплять поставщиков тоже можно, но при двух десятках складов и полусотне поставщиков встанет та же самая проблема.
И еще раз огромное спасибо за пример, действительно все сходится. Сейчас попробую на неограниченное количество обобщить...

 
 
 
 Re: Транспортная задача с ограничениями
Сообщение15.08.2012, 11:32 
К сожалению, далеко не для всех случаев получится расщепить.
Например, возьмем 3 поставщиков с одинаковым ограничением $p \geq 0.5$ части склада. Поскольку любые $2$ поставщика могут удовлетворить потребности склада, то на одном расщепленном складе не может быть более одного запрета. Откуда количество частей - не более $4$.

$\begin{tabular}{c|cccc} 
& W_{11}& W_{12}&W_{13}&W_{14} \\ 
\hline p&1 &1 &0 &1\\ p& 1 &0 &1 &1\\ p& 0 & 1& 1&1\\ &x_1&x_2&x_3&x_4 
\end{tabular} $

$x_1+x_2+x_3+x_4=1$
$1-x_1=1-x_2=1-x_3=p$, откуда
$x_1=x_2=x_3 = 1-p$
$x_4=3p-2$, а значит $p\geq 2/3$
Получается, что для значений $p$ от $[1/2;2/3)$ невозможно подобным образом свести задачу к стандартной. И как быть? Может есть еще какие-то военные хитрости?

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group