Question

The company has two grades of inspectors, 1 and 2, who are to be assigned for a quality control inspection. It is required that at least 1,800 pieces be inspected per 8-hour day. Grade 1 inspectors can check pieces at the rate of 25 per hour, with an accuracy of 98%. Grade 2 inspectors check at the rate of 15 pieces per hour, with an accuracy of 95%. The wage rate of a Grade 1 inspector is $4.00 per hour, while that of a Grade 2 inspector is $3.00 per hour. Each time an error is made by an inspector, the cost to the company is $2.00. The company has available for the inspection job eight Grade 1 inspector, and ten Grade 2 inspectors. The company wants to determine the optimal assignment of inspectors, which will minimize the total cost of the inspection.

1. Solve the problem using either the Big-M method or the Two-phase method step by step in tabular form (objective function is minimum = 40x1 + 36x2).

Answer 1

Formulation:

Let x1 and x2 be the number of grade-1 and grade-2 inspectors assigned per 8-hour shift.

Cost of labor = $4*8*x1 + $3*8*x1 = 32x1 + 24x2
Cost of quality = 25*8*(1-0.98)*$2*x1 + 15*8*(1-0.95)*$2*x2 = 8x1 + 12x2

So,

Minimize Z = total cost = (32+8)x1 + (24+12)x2 = 40x1 + 36x2

Subject to,

x1 <= 8

x2 <= 10

25*8*x1 + 15*8*x2 >= 1800 i.e. 20x1 + 12x2 >= 180

x1, x2 >= 0

Standard form to begin with the Big-M method

Minimize Z = 40x1 + 36x2 + 0s1 + 0s2 + 0s3 + M.A1
s.t.
x1 + s1 = 8
x2 + s2 = 10
20x1 + 12x2 - s3 + A1 <= 180
x1, x2, s1, s2, s3, A1 >= 0

Iteration-1		Cj	40	36	0	0	0	M
B	CB	XB	x1	x2	S1	S2	S3	A1	MinRatio XB/x1
S1	0	8	(1)	0	1	0	0	0	8/1=8→
S2	0	10	0	1	0	1	0	0	---
A1	M	180	20	12	0	0	-1	1	180/20=9
Z=180M		Zj	20M	12M	0	0	-M	M
		Zj-Cj	20M-40↑	12M-36	0	0	-M	0

Positive maximum Zj-Cj is 20M-40 and its column index is 1. So, the entering variable is x1.

The minimum ratio is 8 and its row index is 1. So, the leaving basic variable is S1.

So, the pivot element is 1.

Entering =x1, Departing =S1, Key Element =1

Row operations:

• R1(new)=R1(old)
• R2(new)=R2(old)
• R3(new)=R3(old) - 20 * R1(new)

Iteration-2		Cj	40	36	0	0	0	M
B	CB	XB	x1	x2	S1	S2	S3	A1	MinRatio XBx2
x1	40	8	1	0	1	0	0	0	---
S2	0	10	0	1	0	1	0	0	10/1=10
A1	M	20	0	(12)	-20	0	-1	1	20/12=1.667→
Z=20M+320		Zj	40	12M	-20M+40	0	-M	M
		Zj-Cj	0	12M-36↑	-20M+40	0	-M	0

Positive maximum Zj-Cj is 12M-36 and its column index is 2. So, the entering variable is x2.

The minimum ratio is 1.667 and its row index is 3. So, the leaving basic variable is A1.

So, the pivot element is 12.

Entering =x2, Departing =A1, Key Element =12

Row operations:

• R3(new)=R3(old) / 12
• R1(new)=R1(old)
• R2(new)=R2(old) - R3(new)

Iteration-3		Cj	40	36	0	0	0
B	CB	XB	x1	x2	S1	S2	S3
x1	40	8	1	0	1	0	0
S2	0	8.3333	0	0	1.667	1	0.0833
x2	36	1.6667	0	1	-1.667	0	-0.0833
Z=380		Zj	40	36	-20	0	-3
		Zj-Cj	0	0	-20	0	-3

Since all Zj-Cj ≤ 0, the optimal solution is reached and the solution is as follows:

x1 = 8
x2 = 1.67

Min Z = 380