3
$\begingroup$

I know that an unbalanced transportation problem could be made a balanced transportation problem by adding a dummy node which equals the difference between demand and supply.

In literature, dummy nodes are inserted with a cost of 0. Wouldn't this lead to the problem that the algorithm will always fulfill this dummy amount first? So it can't be insured that we get a realistic result, can it?

$\endgroup$
1
  • $\begingroup$ Use the simplex method to get the optimum $\endgroup$ Jun 21 at 2:05
4
$\begingroup$

The "goods" going to or coming from the dummy node are not really moved; hence the cost of zero, no matter the quantity.

If the problem is solved to optimality, using Network Simplex, or whatever, there is no "first" which can't be changed later as the algorithm proceeds. The algorithm ensures the total cost for moving everything is minimized. Do not think in terms of a "greedy" algorithm which initially makes an irrevocable assignment of what appears to be an attractive first assignment to make, and never reconsiders that first greedy assignment which winds up not being optimal in the grand scheme of things. Network Simplex may make some initial assignment which is not truly optimal, but then iterates until criteria ensuring optimality are reached.

$\endgroup$
7
  • $\begingroup$ Thanks for your answer! I think I still haven't got it... so if we do have an unbalanced transporation problem... adding a dummy node to fullfill the demand = supply requirement doesn't affect the distribution of goods in between our real nodes? I've tried out some examples with python NetworkX and the distribution in between the nodes seems to stay the same...with or without dummyNodes.. I still don't really understand why though... In my head adding dummyNodes must somehow change the distribution.. $\endgroup$
    – learnPyt
    Jun 3 at 20:31
  • $\begingroup$ You can always write it as a Linear Program without dummy node, in which the formulation allows unused supply (or demand, as the case may be). It will have the same optimal objective value as adding a dummy with zero cost arcs to (from). If there is extra supply, the optimal solution using dummy shows supply from one or more supply nodes going to the dummy demand node; but the material on the dummy arcs has zero cos;t the reality of that situation is that the unused supply never traveled anywhere, despite the solution showing it going to a dummy node. $\endgroup$ Jun 3 at 21:56
  • $\begingroup$ I can solve my problem by writing it as a LP with simplex algorithm. When solving with network simplex I get exactly the trouble which I was afraid of. Following case: totalSupply < totalDemand thus adding a supplyDummy. In the network simplex solution many consumers trade with the added supplyDummy. So I end up with many consumers getting effectively no goods at all, as dummyAmounts are just virtual. I want to solve with network simplex as this algorithm is really efficient for the transportation problem. Is there any way to insure that every consumer actually gets $\endgroup$
    – learnPyt
    Jun 4 at 8:33
  • $\begingroup$ a fair share of the available amount? Adding dummy nodes might not change the objectives value, but the reached result doesn't make sense for a real life problem.. $\endgroup$
    – learnPyt
    Jun 4 at 8:35
  • 1
    $\begingroup$ Sorry, I am not. $\endgroup$ Jun 5 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.