Assignment LP Model The Shang-ho Project Development and Construction Company ha
ID: 419806 • Letter: A
Question
Assignment LP Model The Shang-ho Project Development and Construction Company has just been awarded a chemical plant construction contract. The contract terms require that at least five (5) other smaller companies be awarded subcontracts for portions of the total work. Shang-ho therefore requested bids from five (5) shortlisted small companies to do subcontract work in five (5) areas. Because of the production capacity, each company can work only in one area. The bids submitted by the companies, in thousands of dollars, are as follows: WORK AREA COMPANY $10$6 $4 $8 $3 9 9 9 9 Required a. Use the Hungarian (manual) method, to determine which bid Shang-ho should accept in order to minimize overall costs [12 marks] Write an LP formulation that could be used to solve this problem with the relevant LP software packages like excel "solver". [13 marks]Explanation / Answer
1.
1.
COMPANY
WORK AREA
1
2
3
4
5
A
10
6
4
8
3
B
2
9
7
8
6
C
6
11
12
5
9
D
5
4
2
1
4
E
5
9
8
5
9
Try to keep one zero in each row
COMPANY
WORK AREA
1
2
3
4
5
A
7
3
1
5
0
B
0
7
5
6
4
COMPANY
1
6
7
0
4
D
4
3
1
0
3
E
0
4
3
0
4
Try to keep one zero in each columncolumn
COMPANY
WORK AREA
1
2
3
4
5
A
7
0
0
5
0
B
0
4
4
6
4
C
1
3
6
0
4
D
4
0
0
0
3
E
0
1
2
0
4
Chek for non degeneracy by cutting lines
COMPANY
WORK AREA
1
2
3
4
5
A
7
0
0
5
0
B
0
4
4
6
4
C
1
3
6
0
4
D
4
0
0
0
3
E
0
1
2
0
4
since matrix size (5) > L (4) so non de generacy
Add ad substract the non cutting minimum value from the rest: as per the condition and check the non-degeneracy
COMPANY
WORK AREA
1
2
3
4
5
A
8
0
0
6
0
B
0
4
4
6
3
C
1
3
6
0
3
D
5
0
0
1
3
E
0
0
1
0
3
since matrix size (5) = L (5) so degeneracy obtained
Solution:
COMPANY
WORK AREA
1
2
3
4
5
A
8
0
0
6
0
B
0
4
4
6
3
C
1
3
6
0
3
D
5
0
0
1
3
E
0
0
1
0
3
Company
A
B
C
D
E
Work area
5
1
4
3
2
2.
Objective function:
MINIMIZE Z = 10*A1 + 6*A2 + 4*A3 + 8*A4 + 5*A5 + 2*B1 + 9*B2 + 7*B3 + 7*B4 + 6*B5 + 6*C1 + 11 *C2 + 12*C3 + 5*C4 + 9*C5 + 5*D1 + 4*D2 + 2*D3 + 1*D4 + 4*D5 + 5*E1 + 9*E2 + 8*E3 + 5*E4 + 9*E5
Constraints:
A1 + A2 + A3 + A4 + A5 = 1
B1 + B2 + B3 + B4 + B5 = 1
C1 + C2 + C3 + C4 + C5 = 1
D1 + D2 + D3 + D4 + D5 = 1
E1 + E2 + E3 + E4 + E5 = 1
A1 + B1 + C1 + D1 + E1 = 1
A2 + B2 + C2 + D2 + E2 = 1
A3 + B3 + C3 + D3 + E3 = 1
A4 + B4 + C4 + D4 + E4 = 1
A5 + B5 + C5 + D5 + E5 = 1
All the variables are greater than zero
1.
COMPANY
WORK AREA
1
2
3
4
5
A
10
6
4
8
3
B
2
9
7
8
6
C
6
11
12
5
9
D
5
4
2
1
4
E
5
9
8
5
9
Try to keep one zero in each row
COMPANY
WORK AREA
1
2
3
4
5
A
7
3
1
5
0
B
0
7
5
6
4
COMPANY
1
6
7
0
4
D
4
3
1
0
3
E
0
4
3
0
4
Try to keep one zero in each columncolumn
COMPANY
WORK AREA
1
2
3
4
5
A
7
0
0
5
0
B
0
4
4
6
4
C
1
3
6
0
4
D
4
0
0
0
3
E
0
1
2
0
4
Chek for non degeneracy by cutting lines
COMPANY
WORK AREA
1
2
3
4
5
A
7
0
0
5
0
B
0
4
4
6
4
C
1
3
6
0
4
D
4
0
0
0
3
E
0
1
2
0
4
since matrix size (5) > L (4) so non de generacy
Add ad substract the non cutting minimum value from the rest: as per the condition and check the non-degeneracy
COMPANY
WORK AREA
1
2
3
4
5
A
8
0
0
6
0
B
0
4
4
6
3
C
1
3
6
0
3
D
5
0
0
1
3
E
0
0
1
0
3
since matrix size (5) = L (5) so degeneracy obtained
Solution:
COMPANY
WORK AREA
1
2
3
4
5
A
8
0
0
6
0
B
0
4
4
6
3
C
1
3
6
0
3
D
5
0
0
1
3
E
0
0
1
0
3
Company
A
B
C
D
E
Work area
5
1
4
3
2
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.