Transportation Problem

Management Science - Applying Python and R

Pages

Transportation Problem

Unbalanced Transportation Problem

No comments:

Post a Comment

Balanced Transportation Problem

LPP formulation:

Min Z = 21* X11 + 16*X12 + 15*X13 + 3* X14+17* X21+18* X22+14* X23+ 23*X24+32* X31+27* X32+18* X33+41* X34

1*X11+1*X12+1*X13+1*X14 ≤ 11

1*X21+1*X22+1*X23+1*X24 ≤ 13

1*X31 + 1*X32 + 1*X33 + 1*X34 ≤ 19

1*X11+1*X21+1*X31 = 6

1*X12+1*X22+1*X32 = 6

1*X13+1*X23+1*X33 = 8

1*X14+1*X24+1*X34 = 23

X11, X12, X13, X14, X21, X22, X23, X24, X31, X32, X33, X34 ≥ 0

Using Python

# import the library pulp as p

import pulp as p

# Create a LP Minimization problem

Lp_prob = p.LpProblem('Problem', p.LpMinimize)

# Create problem Variables

X11 = p.LpVariable("X11", lowBound = 0) # Create a variable X11 >= 0

X12 = p.LpVariable("X12", lowBound = 0) # Create a variable X12 >= 0

X13 = p.LpVariable("X13", lowBound = 0) # Create a variable X13 >= 0

X14 = p.LpVariable("X14", lowBound = 0) # Create a variable X14 >= 0

X21 = p.LpVariable("X21", lowBound = 0) # Create a variable X21>= 0

X22 = p.LpVariable("X22", lowBound = 0) # Create a variable X22 >= 0

X23 = p.LpVariable("X23", lowBound = 0) # Create a variable X23 >= 0

X24 = p.LpVariable("X24", lowBound = 0) # Create a variable X24 >= 0

X31 = p.LpVariable("X31", lowBound = 0) # Create a variable X31 >= 0

X32 = p.LpVariable("X32", lowBound = 0) # Create a variable X32 >= 0

X33 = p.LpVariable("X33", lowBound = 0) # Create a variable X33 >= 0

X34 = p.LpVariable("X34", lowBound = 0) # Create a variable X34 >= 0

# Objective Function

Lp_prob += 21* X11 + 16*X12 + 15*X13 + 3* X14+17* X21+18* X22+14* X23+ 23*X24+32* X31+27* X32+18* X33+41* X34

# Constraints:

Lp_prob += 1*X11+1*X12+1*X13+1*X14 <= 11

Lp_prob += 1*X21+1*X22+1*X23+1*X24 <= 13

Lp_prob += 1*X31+ 1*X32 + 1*X33 + 1*X34 <= 19

Lp_prob +=1*X11+1*X21+1*X31 == 6

Lp_prob +=1*X12+1*X22+1*X32 == 6

Lp_prob += 1*X13+1*X23+1*X33== 8

Lp_prob +=1*X14+1*X24+1*X34 == 23

# Display the problem

print(Lp_prob)

status = Lp_prob.solve() # Solver

print(p.LpStatus[status]) # The solution status

# Printing the final solution

print(p.value(X11), p.value(X12), p.value(X13), p.value(X14), p.value(X21), p.value(X22), p.value(X23), p.value(X24), p.value(X31), p.value(X32), p.value(X33), p.value(X34), p.value(Lp_prob.objective))

Solution is:

Problem:
MINIMIZE
21*X11 + 16*X12 + 15*X13 + 3*X14 + 17*X21 + 18*X22 + 14*X23 + 23*X24 + 32*X31 + 27*X32 + 18*X33 + 41*X34 + 0
SUBJECT TO
_C1: X11 + X12 + X13 + X14 <= 11

_C2: X21 + X22 + X23 + X24 <= 13

_C3: X31 + X32 + X33 + X34 <= 19

_C4: X11 + X21 + X31 = 6

_C5: X12 + X22 + X32 = 6

_C6: X13 + X23 + X33 = 8

_C7: X14 + X24 + X34 = 23

VARIABLES
X11 Continuous
X12 Continuous
X13 Continuous
X14 Continuous
X21 Continuous
X22 Continuous
X23 Continuous
X24 Continuous
X31 Continuous
X32 Continuous
X33 Continuous
X34 Continuous

Optimal
0.0 0.0 0.0 11.0 1.0 0.0 0.0 12.0 5.0 6.0 8.0 0.0 792.0

Using R 

library(lpSolve)
# Transportation costs matrix
costs <- matrix(c(21,16,15,3,        
17,18,14,23,         
32,27,18,41), nrow = 3, byrow = TRUE)
# Sources and Destinations
colnames(costs) <- c("D1", "D2","D3", "D4")
rownames(costs) <- c("S1", "S2","S3")
# Set unequality/equality signs for suppliers
row.signs <- rep("<=", 3)
# Set right hand side coefficients for suppliers
row.rhs <- c(11,13,19)
# Set unequality/equality signs for customers
col.signs <- rep("==", 4)
# Set right hand side coefficients for Destinations
col.rhs <- c(6, 6, 8, 23)
lp.transport(costs, "min", row.signs,
row.rhs, col.signs, col.rhs)
lp.transport(costs, "min", row.signs,
row.rhs, col.signs, col.rhs)$solution

Solution

Success: the objective function is 792

> lp.transport(costs, "min", row.signs, row.rhs, col.signs, col.rhs)$solution
     [,1] [,2] [,3] [,4]
[1,]    0    0    0   11
[2,]    1    0    0   12
[3,]    5    6    8    0
> 

Unbalanced Transportation Problem


 
  
  
  To
  
  
 
 
  
  D1
  
  
  D2
  
  
  D3
  
  
  D4
  
  
  D5
  
  
  D6
  
  
  Supply
  
 
 
  
  From
  
  
  S1
  
  
  50
  
  
  50
  
  
  45
  
  
  29
  
  
  44
  
  
  20
  
  
  721
  
 
 
  
  S2
  
  
  29
  
  
  26
  
  
  47
  
  
  45
  
  
  37
  
  
  23
  
  
  620
  
 
 
  
  S3
  
  
  44
  
  
  31
  
  
  50
  
  
  26
  
  
  28
  
  
  30
  
  
  450
  
 
 
  
  S4
  
  
  46
  
  
  21
  
  
  49
  
  
  25
  
  
  41
  
  
  40
  
  
  587
  
 
 
  
  S5
  
  
  48
  
  
  47
  
  
  43
  
  
  40
  
  
  39
  
  
  30
  
  
  690
  
 
 
  
  
  Demand
  
  
  560
  
  
  580
  
  
  459
  
  
  700
  
  
  668
  
  
  416
  
  
 

Convert above unbalanced transportation problem into balanced transportation problem
 

 
  
  
  To
  
  
 
 
  
  From
  
  
  
  D1
  
  
  D2
  
  
  D3
  
  
  D4
  
  
  D5
  
  
  D6
  
  
  Supply
  
 
 
  
  S1
  
  
  50
  
  
  50
  
  
  45
  
  
  29
  
  
  44
  
  
  20
  
  
  721
  
 
 
  
  S2
  
  
  29
  
  
  26
  
  
  47
  
  
  45
  
  
  37
  
  
  23
  
  
  620
  
 
 
  
  S3
  
  
  44
  
  
  31
  
  
  50
  
  
  26
  
  
  28
  
  
  30
  
  
  450
  
 
 
  
  S4
  
  
  46
  
  
  21
  
  
  49
  
  
  25
  
  
  41
  
  
  40
  
  
  587
  
 
 
  
  S5
  
  
  48
  
  
  47
  
  
  43
  
  
  40
  
  
  39
  
  
  30
  
  
  690
  
 
 
  
  S6
  
  
  0
  
  
  0
  
  
  0
  
  
  0
  
  
  0
  
  
  0
  
  
  315
  
 
 
  
  Demand
  
  
  560
  
  
  580
  
  
  459
  
  
  700
  
  
  668
  
  
  416
  
  
 

Objective Function
Min Z =  50*X11+50*X12+45*X13+29*X14+44*X15+20*X16+29*X21+26*X22+47*X23+45*X24+37*X25+23*X26+44*X31+31*X32+50*X33+26*X34+28*X35+30*X36+46*X41+21*X42+49*X43+25*X44+41*X45+40*X46+48*X51+47*X52+43*X53+40*X54+39*X55+30*X56+0*X61+0*X62+0*X63+0*X64+0*X65+0*X66
Subjected to: 
X11+X12+X13+X14+X15+X16
≤ 721
X21+X22+X23+X24+X25+X26
≤ 620
X31+X32+X33+X34+X35+X36≤450
X41+X42+X43+X44+X45+X46≤587
X51+X52+X53+X54+X55+X56≤690
X61+X62+X63+X64+X65+X66≤315
X11+X21+X31+X41+X51+X61=560
X12+X22+X32+X42+X52+X62=580
X13+X23+X33+X43+X53+X63=459
X14+X24+X34+X44+X54+X64=700
X15+X25+X35+X45+X55+X65=668
X16+X26+X36+X46+X56+X66=416                                                                                                                       
























X11, X12, X13, X14, X15, X16, X21, X22, X23, X24, X25, X26, X31, X32, X33, X34, X35, X36, X41, X42, X43, X44,
X45, X46, X51, X52, X53, X54, X55, X56, X61, X62, X63, X64, X65, X66 ≥ 0
Using Python 


#
import the library pulp as p 

import
pulp as p 

#
Create a LP Minimization problem 

Lp_prob
= p.LpProblem('Problem', p.LpMinimize)  

  

#
Create problem Variables  

X11
= p.LpVariable("X11", lowBound = 0)   # Create a variable
X11 >= 0 

X12
= p.LpVariable("X12", lowBound = 0)   # Create a variable
X12 >= 0 

X13
= p.LpVariable("X13", lowBound = 0)   # Create a variable
X13 >= 0 

X14
= p.LpVariable("X14", lowBound = 0)   # Create a variable
X14 >= 0 

X15
= p.LpVariable("X15", lowBound = 0)   # Create a variable
X15 >= 0 

X16
= p.LpVariable("X16", lowBound = 0)   # Create a variable
X16 >= 0 

X21
= p.LpVariable("X21", lowBound = 0)   # Create a variable
X21>= 0 

X22
= p.LpVariable("X22", lowBound = 0)   # Create a variable
X22 >= 0 

X23
= p.LpVariable("X23", lowBound = 0)   # Create a variable
X23 >= 0 

X24
= p.LpVariable("X24", lowBound = 0)   # Create a variable
X24 >= 0 

X25
= p.LpVariable("X25", lowBound = 0)   # Create a variable
X25 >= 0 

X26
= p.LpVariable("X26", lowBound = 0)   # Create a variable
X26 >= 0 

X31
= p.LpVariable("X31", lowBound = 0)   # Create a variable
X31 >= 0

X32
= p.LpVariable("X32", lowBound = 0)   # Create a variable
X32 >= 0

X33
= p.LpVariable("X33", lowBound = 0)   # Create a variable
X33 >= 0

X34
= p.LpVariable("X34", lowBound = 0)   # Create a variable
X34 >= 0

X35
= p.LpVariable("X35", lowBound = 0)   # Create a variable
X35 >= 0

X36
= p.LpVariable("X36", lowBound = 0)   # Create a variable
X36 >= 0

X41
= p.LpVariable("X41", lowBound = 0)   # Create a variable X41
>= 0

X42
= p.LpVariable("X42", lowBound = 0)   # Create a variable X42
>= 0

X43
= p.LpVariable("X43", lowBound = 0)   # Create a variable X43
>= 0

X44
= p.LpVariable("X44", lowBound = 0)   # Create a variable X44
>= 0

X45
= p.LpVariable("X45", lowBound = 0)   # Create a variable X45
>= 0

X46
= p.LpVariable("X46", lowBound = 0)   # Create a variable X46
>= 0

X51
= p.LpVariable("X51", lowBound = 0)   # Create a variable X51
>= 0

X52
= p.LpVariable("X52", lowBound = 0)   # Create a variable X52
>= 0

X53
= p.LpVariable("X53", lowBound = 0)   # Create a variable X53
>= 0

X54
= p.LpVariable("X54", lowBound = 0)   # Create a variable X54
>= 0

X55
= p.LpVariable("X55", lowBound = 0)   # Create a variable X55
>= 0

X56
= p.LpVariable("X56", lowBound = 0)   # Create a variable X56
>= 0

X61
= p.LpVariable("X61", lowBound = 0)   # Create a variable X61
>= 0

X62
= p.LpVariable("X62", lowBound = 0)   # Create a variable X62
>= 0

X63
= p.LpVariable("X63", lowBound = 0)   # Create a variable X63
>= 0

X64
= p.LpVariable("X64", lowBound = 0)   # Create a variable X64
>= 0

X65
= p.LpVariable("X65", lowBound = 0)   # Create a variable X65
>= 0

X66
= p.LpVariable("X66", lowBound = 0)   # Create a variable X66
>= 0

#
Objective Function 

Lp_prob
+=50*X11+50*X12+45*X13+29*X14+44*X15+20*X16+29*X21+26*X22+47*X23+45*X24+37*X25+23*X26+44*X31+31*X32+50*X33+26*X34+28*X35+30*X36+46*X41+21*X42+49*X43+25*X44+41*X45+40*X46+48*X51+47*X52+43*X53+40*X54+39*X55+30*X56+0*X61+0*X62+0*X63+0*X64+0*X65+0*X66

 

#
Constraints: 

Lp_prob
+= 1*X11+1*X12+1*X13+1*X14+1*X15+1*X16<=
721

Lp_prob
+= 1*X21+1*X22+1*X23+1*X24+1*X25+1*X26
<= 620

Lp_prob
+= 1*X31+1*X32+1*X33+1*X34+1*X35+1*X36<=450

Lp_prob
+= 1*X41+1*X42+1*X43+1*X44+1*X45+1*X46<=587

Lp_prob
+= 1*X51+1*X52+1*X53+1*X54+1*X55+1*X56<=690


Lp_prob
+= 1*X61+1*X62+1*X63+1*X64+1*X65+1*X66<=315

Lp_prob
+=1*X11+1*X21+1*X31+1*X41+1*X51+1*X61==560

Lp_prob
+=1*X12+1*X22+1*X32+1*X42+1*X52+1*X62==580

Lp_prob
+= 1*X13+1*X23+1*X33+1*X43+1*X53+1*X63==459

Lp_prob
+= 1*X14+1*X24+1*X34+1*X44+1*X54+1*X64==700

Lp_prob
+= 1*X15+1*X25+1*X35+1*X45+1*X55+1*X65==668

Lp_prob
+= 1*X16+1*X26+1*X36+1*X46+1*X56+1*X66==416

  

#
Display the problem 

print(Lp_prob) 

status
= Lp_prob.solve()   # Solver 

print(p.LpStatus[status]) 
 # The solution status 

  

#
Printing the final solution 

print(p.value(X11),
p.value(X12), p.value(X13), p.value(X14), p.value(X15), p.value(X16), p.value(X21),
p.value(X22), p.value(X23), p.value(X24), p.value(X25), p.value(X26),  p.value(X31), p.value(X32), p.value(X33),
p.value(X34), p.value(X35), p.value(X36), p.value(X41), p.value(X42),
p.value(X43), p.value(X44), p.value(X45), p.value(X46), p.value(X51), p.value(X52),
p.value(X53), p.value(X54), p.value(X55), p.value(X56), p.value(X61),
p.value(X62), p.value(X63), p.value(X64), p.value(X65), p.value(X66), p.value(Lp_prob.objective))


Solution is:
Problem:
MINIMIZE
50*X11 + 50*X12 + 45*X13 + 29*X14 + 44*X15 + 20*X16 + 29*X21 + 26*X22 + 47*X23 + 45*X24 + 37*X25 + 23*X26 + 44*X31 + 31*X32 + 50*X33 + 26*X34 + 28*X35 + 30*X36 + 46*X41 + 21*X42 + 49*X43 + 25*X44 + 41*X45 + 40*X46 + 48*X51 + 47*X52 + 43*X53 + 40*X54 + 39*X55 + 30*X56 + 0
SUBJECT TO
_C1: X11 + X12 + X13 + X14 + X15 + X16 <= 721

_C2: X21 + X22 + X23 + X24 + X25 + X26 <= 620

_C3: X31 + X32 + X33 + X34 + X35 + X36 <= 450

_C4: X41 + X42 + X43 + X44 + X45 + X46 <= 587

_C5: X51 + X52 + X53 + X54 + X55 + X56 <= 690

_C6: X61 + X62 + X63 + X64 + X65 + X66 <= 315

_C7: X11 + X21 + X31 + X41 + X51 + X61 = 560

_C8: X12 + X22 + X32 + X42 + X52 + X62 = 580

_C9: X13 + X23 + X33 + X43 + X53 + X63 = 459

_C10: X14 + X24 + X34 + X44 + X54 + X64 = 700

_C11: X15 + X25 + X35 + X45 + X55 + X65 = 668

_C12: X16 + X26 + X36 + X46 + X56 + X66 = 416

VARIABLES
X11 Continuous
X12 Continuous
X13 Continuous
X14 Continuous
X15 Continuous
X16 Continuous
X21 Continuous
X22 Continuous
X23 Continuous
X24 Continuous
X25 Continuous
X26 Continuous
X31 Continuous
X32 Continuous
X33 Continuous
X34 Continuous
X35 Continuous
X36 Continuous
X41 Continuous
X42 Continuous
X43 Continuous
X44 Continuous
X45 Continuous
X46 Continuous
X51 Continuous
X52 Continuous
X53 Continuous
X54 Continuous
X55 Continuous
X56 Continuous
X61 Continuous
X62 Continuous
X63 Continuous
X64 Continuous
X65 Continuous
X66 Continuous

Optimal
0.0 0.0 0.0 305.0 0.0 416.0 560.0 60.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 328.0 122.0 0.0 0.0 520.0 0.0 67.0 0.0 0.0 0.0 0.0 144.0 0.0 546.0 0.0 0.0 0.0 315.0 0.0 0.0 0.0 86990.0


Using R

library(lpSolve)

# Transportation costs matrix

costs <- matrix(c(50,50,45,29,44,20,

29,26,47,45,37,23,

44,31,50,26,28,30,

46,21,49,25,41,40,

48,47,43,40,39,30,

0,0,0,0,0,0), nrow = 6, byrow = TRUE)

# Sources and Destinations

colnames(costs) <- c("D1", "D2","D3", "D4", "D5", "D6")

rownames(costs) <- c("S1", "S2","S3","S4","S5","S6")

# Set unequality/equality signs for suppliers

row.signs <- rep("<=", 6)

# Set right hand side coefficients for suppliers

row.rhs <- c(721,620,450,587,690, 315)

# Set unequality/equality signs for customers

col.signs <- rep("==", 6)

# Set right hand side coefficients for Destinations

col.rhs <- c(560,580,459,700,668,416)

lp.transport(costs, "min", row.signs, row.rhs, col.signs, col.rhs)

lp.transport(costs, "min", row.signs, row.rhs, col.signs, col.rhs)$solution

Solution

Success: the objective function is 86990

     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    0    0    0  305    0  416
[2,]  560   60    0    0    0    0
[3,]    0    0    0  328  122    0
[4,]    0  520    0   67    0    0
[5,]    0    0  144    0  546    0
[6,]    0    0  315    0    0    0
>

Destination

		To
		D1	D2	D3	D4	D5	D6	Supply
From	S1	50	50	45	29	44	20	721
	S2	29	26	47	45	37	23	620
	S3	44	31	50	26	28	30	450
	S4	46	21	49	25	41	40	587
	S5	48	47	43	40	39	30	690
	Demand	560	580	459	700	668	416