4
$\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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Use the simplex method to get the optimum $\endgroup$
    – themmy boscoh
    Jun 21, 2021 at 2:05

1 Answer 1

Reset to default
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.

Improve this answer
$\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, 2021 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$
    – Mark L. Stone
    Jun 3, 2021 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, 2021 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, 2021 at 8:35
  • 1
    $\begingroup$ Sorry, I am not. $\endgroup$
    – Mark L. Stone
    Jun 5, 2021 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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