Assignment Problem

Balanced Assignment Problem

1. A startup company has tree expert programmers. The company wants three application programmes to be developed. The manager of the company, after carefully studying the programmes to be developed, estimates the time in minutes required by experts for developing the programmes are summarized below:

		Programmers
		A	B	C
Programmes	1	120	100	80
	2	80	90	110
	3	110	140	120

Assign the programmers to programmes in such a way that the total computer time is minimum.

LPP Formulation:

Min Z = 120*X11+100*X12+80*X13+80*X21+90*X22+110*X23+110*X31+140*X32+120*X33

Subjected to:

1*X11+1*X12+1*X13≤1

1*X21+1*X22+1*X23≤1

1*X31+1*X32+1*X33≤1

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

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

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

X11, X12, X13, X21, X22, X23, X31, X32, X33≥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

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

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

# Objective Function

Lp_prob += 120* X11 + 100*X12 + 80*X13 + 80* X21+90* X22+110* X23+110* X31+140* X32+120* X33

# Constraints:

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

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

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

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

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

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

# 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(X21), p.value(X22), p.value(X23), p.value(X31), p.value(X32), p.value(X33), p.value(Lp_prob.objective))

Solution is:

Problem:
MINIMIZE
120*X11 + 100*X12 + 80*X13 + 80*X21 + 90*X22 + 110*X23 + 110*X31 + 140*X32 + 120*X33 + 0
SUBJECT TO
_C1: X11 + X12 + X13 <= 1

_C2: X21 + X22 + X23 <= 1

_C3: X31 + X32 + X33 <= 1

_C4: X11 + X21 + X31 = 1

_C5: X12 + X22 + X32 = 1

_C6: X13 + X23 + X33 = 1

VARIABLES
X11 Continuous
X12 Continuous
X13 Continuous
X21 Continuous
X22 Continuous
X23 Continuous
X31 Continuous
X32 Continuous
X33 Continuous

Optimal
0.0 0.0 1.0 0.0 1.0 0.0 1.0 0.0 0.0 280.0

Using R 

library(lpSolve)

# Assignment Cost matrix
costs <- matrix(c(120,100,80,
80,90,110,         
110,140,120), nrow = 3, byrow = TRUE)
# Print assignment costs matrix
costs
lp.assign(costs)
lp.assign(costs)$solution

Solution

> library(lpSolve)
> # Assignment Cost matrix
> costs <- matrix(c(120,100,80,
+ 80,90,110,         
+ 110,140,120), nrow = 3, byrow = TRUE)
> # Print assignment costs matrix
> costs
     [,1] [,2] [,3]
[1,]  120  100   80
[2,]   80   90  110
[3,]  110  140  120
> lp.assign(costs)
Success: the objective function is 280 
> lp.assign(costs)$solution
     [,1] [,2] [,3]
[1,]    0    0    1
[2,]    0    1    0
[3,]    1    0    0
>

Unbalanced Assignment Problem

Five students, Akira, Bobby, Cay, Di and Ed have to submit group assignments in four subjects: Marketing, HR, Operations and Finance. The expected marks for the assignments in each subjects and that a student can score are given the below table:



 
  
  
  Akira
  
  
  Bobby
  
  
  Cay
  
  
  Di
  
  
  Ed
  
 
 
  
  Marketing
  
  
  4
  
  
  90
  
  
  64
  
  
  58
  
  
  73
  
 
 
  
  HR
  
  
  19
  
  
  88
  
  
  52
  
  
  41
  
  
  14
  
 
 
  
  Operations 
  
  
  35
  
  
  86
  
  
  68
  
  
  11
  
  
  6
  
 
 
  
  Finance
  
  
  78
  
  
  41
  
  
  88
  
  
  93
  
  
  53
  
 

Allocate the assignments to each student to maximize the marks scored. 

Balanced Assignment Problem


 
  
  
  Akira
  
  
  Bobby
  
  
  Cay
  
  
  Di
  
  
  Ed
  
 
 
  
  Marketing
  
  
  4
  
  
  90
  
  
  64
  
  
  58
  
  
  73
  
 
 
  
  HR
  
  
  19
  
  
  88
  
  
  52
  
  
  41
  
  
  14
  
 
 
  
  Operations 
  
  
  35
  
  
  86
  
  
  68
  
  
  11
  
  
  6
  
 
 
  
  Finace
  
  
  78
  
  
  41
  
  
  88
  
  
  93
  
  
  53
  
 
 
  
  Dummy 
  
  
  0
  
  
  0
  
  
  0
  
  
  0
  
  
  0
  
 


LPP Formulation:
Max Z = 4*X11+90*X12+64*X13+58*X14+73*X15+19*X21+88*X22+52*X23+41*X24+14*X25+35*X31+86*X32+68*X33+11*X34+6*X35+78*X41+41*X42+88*X43+93*X44+53*X45+0*X51+0*X52+0*X53+0*X54+0*X55          
Subjected to:
1*X11+1*X12+1*X13+1*X14+1*X15≤1
1*X21+1*X22+1*X23+1*X24+1*X25≤1
1*X31+1*X32+1*X33+1*X34+1*X35≤1
1*X41+1*X42+1*X43+1*X44+1*X45≤1
1*X51+1*X52+1*X53+1*X54+1*X55≤1
1*X11+1*X21+1*X31+1*X41+1*X51=1
1*X12+1*X22+1*X32+1*X42+1*X52=1
1*X13+1*X23+1*X33+1*X43+1*X53=1
1*X14+1*X24+1*X34+1*X44+1*X54=1
1*X15+1*X25+1*X35+1*X45+1*X55=1
X11, X12, X13, X14, X15, X21, X22, X23, X24, X25, X31, X32, X33, X34, X35, X41, X42, X43, X44, X45, X51, X52, X53, X54, X55 ≥0


Using Python 
# import the library pulp as p
import pulp as p
# Create a LP Maximization problem
Lp_prob = p.LpProblem('Problem', p.LpMaximize)  
# 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
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
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
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
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

# Objective Function
Lp_prob+=4*X11+90*X12+64*X13+58*X14+73*X15+19*X21+88*X22+52*X23+41*X24+14*X25+35*X31+86*X32+68*X33+11*X34+6*X35+78*X41+41*X42+88*X43+93*X44+53*X45+0*X51+0*X52+0*X53+0*X54+0*X55

 # Constraints:

Lp_prob += 1*X11+1*X12+1*X13+1*X14+1*X15 <= 1
Lp_prob += 1*X21+1*X22+1*X23+1*X24+1*X25 <= 1
Lp_prob += 1*X31+1*X32+1*X33+1*X34+1*X35 <= 1
Lp_prob += 1*X41+1*X42+1*X43+1*X44+1*X45 <= 1
Lp_prob += 1*X51+1*X52+1*X53+1*X54+1*X55 <= 1
Lp_prob += 1*X11+1*X21+1*X31+1*X41+1*X51 == 1 
Lp_prob += 1*X12+1*X22+1*X32+1*X42+1*X52 == 1 
Lp_prob += 1*X13+1*X23+1*X33+1*X43+1*X53 == 1
Lp_prob += 1*X14+1*X24+1*X34+1*X44+1*X54 == 1
Lp_prob += 1*X15+1*X25+1*X35+1*X45+1*X55 == 1

# 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(X21), p.value(X22), p.value(X23), p.value(X24), p.value(X25), p.value(X31), p.value(X32), p.value(X33), p.value(X34), p.value(X35), p.value(X41), p.value(X42), p.value(X43), p.value(X44), p.value(X45), p.value(X51), p.value(X52), p.value(X53), p.value(X54), p.value(X55),p.value(Lp_prob.objective))

Solution is:

Problem:
MAXIMIZE
4*X11 + 90*X12 + 64*X13 + 58*X14 + 73*X15 + 19*X21 + 88*X22 + 52*X23 + 41*X24 + 14*X25 + 35*X31 + 86*X32 + 68*X33 + 11*X34 + 6*X35 + 78*X41 + 41*X42 + 88*X43 + 93*X44 + 53*X45 + 0
SUBJECT TO
_C1: X11 + X12 + X13 + X14 + X15 <= 1

_C2: X21 + X22 + X23 + X24 + X25 <= 1

_C3: X31 + X32 + X33 + X34 + X35 <= 1

_C4: X41 + X42 + X43 + X44 + X45 <= 1

_C5: X51 + X52 + X53 + X54 + X55 <= 1

_C6: X11 + X21 + X31 + X41 + X51 = 1

_C7: X12 + X22 + X32 + X42 + X52 = 1

_C8: X13 + X23 + X33 + X43 + X53 = 1

_C9: X14 + X24 + X34 + X44 + X54 = 1

_C10: X15 + X25 + X35 + X45 + X55 = 1

VARIABLES
X11 Continuous
X12 Continuous
X13 Continuous
X14 Continuous
X15 Continuous
X21 Continuous
X22 Continuous
X23 Continuous
X24 Continuous
X25 Continuous
X31 Continuous
X32 Continuous
X33 Continuous
X34 Continuous
X35 Continuous
X41 Continuous
X42 Continuous
X43 Continuous
X44 Continuous
X45 Continuous
X51 Continuous
X52 Continuous
X53 Continuous
X54 Continuous
X55 Continuous

Optimal
0.0 0.0 0.0 1.0000889e-12 1.0 0.0 1.0 0.0 1.0000889e-12 0.0 1.0000889e-12 0.0 1.0 0.0 0.0 2.9998226e-12 0.0 0.0 1.0 0.0 1.0 0.0 0.0 0.0 0.0 322.000000000368

Management Science - Applying Python and R

Pages

Assignment Problem

No comments:

Post a Comment

	Akira	Bobby	Cay	Di	Ed
Marketing	4	90	64	58	73
HR	19	88	52	41	14
Operations	35	86	68	11	6
Finance	78	41	88	93	53