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

[Cash]

Пусть у нас есть 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} $

[Shadow]

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

[Cash]

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

[Cash]

К сожалению, далеко не для всех случаев получится расщепить.
Например, возьмем 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)$ невозможно подобным образом свести задачу к стандартной. И как быть? Может есть еще какие-то военные хитрости?