The Transportation Problem

Question 1

supply and demand

Answer 1

supply is positive allocation [X]
and demands is negative [-Y]
can make a graph that links the supplies to the demands. The edges have then an associated cost for the transport.

Question 2

Transportation problem basic formulation

Answer 2

Minimize the cost to transport the supply to eh demands
decision variables xij (from supply y to demand j) and their associated cost cij is the coefficient.
Obj: Min sum Cij*Xij
s.t.
sum xij for a supply i = its amount of supply
sum xij for a demand i = its amount of demand

=> m+n constraints (m sources + n destinations)

sum of demands = sum of supply
-> can be softened with a dummy destination

Question 3

Dummy destination

Answer 3

if we don’t have the sum demand = sum supply
we can add a dummy destination which absorb the extra fictional production difference
(if total supply is 100, and the total demand is 70, add a dummy that demands 30)

Question 4

Big M

Answer 4

In our cost table, can put M in places we want to prevent supply to be given to demand (eg: if the destination follow one another, previous ones can’t be reused)

Question 5

Transportation Problem Integral Property

Answer 5

If sources and demands are integers, there exist an optimal integer solution (all BFS will be integers)

Question 6

Infinite demand

Answer 6

if a place has an infinite demand its max can be set to the max supply we have available (check the total supply - the total minimum requirements of the other places)

Question 7

Dummy supply

Answer 7

if destinations have min and max demands, put all demands to their max values.
Then, add a dummy supply source its supply is equal to: the sum of the max demands - the sum of the supply available (the missing supply to satisfy the max demand of all destinations).
If the dummy supply gives to the destination it amounts to not receiving anything

To satisfy the minimum requirements of destination j we need to adjust the costs cij of that dummy:

• if min of j = 0 -> cost 0 (it doesn’t need supply so receiving fake supply is fine)
• if min of j = max -> cost M (it needs all its demand so it should not receive any fake supply)
• if max - dummy supply >= min demand j -> cost 0 (it is fine if it receive all the fake supply because its remainder demand of real supply will exceed its min requirements)
• ELSE : split the destination in 2 (can copy the same costs for the supplies), 1 is the minimum demand, the other is the extra demand. For the minimum, have the dummy supply cost is big M (it should not receive any fake supply), for the second the cost is 0 (it can receive only fake supply, it does not actually need it) .

Question 8

Advantages of Transportation Problem Formulation

Answer 8

Faster than normal LP formulation: gain speed in pivots

Knowledge such as integral solutions property

Question 9

Assignment Problem

Answer 9

Special case Transportation

n tasks n people, every tasks needs to be done, 1 per people
people do tasks in different times

time it takes for a task -> cij
Each task is demand 1
Each person is supply 1

-> integral property still applies. There will be an integer solution

Transportation algorithm can be used to solve it :D