Question

A computer company manufactures 3 types of computers which are personal computers, workbooks and gamebooks. Each personal computer is produced in 0.2 hours, assembled in 0.1 hours, and inspected in 0.05 hours. Each workbook is produced in 0.2 hours, assembled in 0.3 hours, and inspected in 0.075 hours. Each gamebook is produced in 0.4 hours, assembled in 0.4 hours, and inspected in 0.15 hours. At most 600 hours of production, 480 hours of assembly and 160 hours of inspection can be done. The company profits 60$ from a personal computer, 90$ from a workbook, 100$ from a gamebook. Besides, due to the lack of demand, at least 60 personal computer should be ready in the inventory. Formulate an LP that can be used to maximize the profit of computer company. Explain each decision variable, objective function, and constraint with at least one sentence. Write down the standard form and add artificial variables if needed. Find a basic feasible solution to start simplex. Solve the LP by using simplex method step by step. Write down the optimal solution.

Answer 1

Let

x1 = no. of personal computers
x2 = no. of workbooks
x3 = no. of gamebooks to be products

Maximize Z = 60 x1 + 90 x2 + 100 x3 (this is the objective function which is the total profit that's to be maximized)

0.20 x1 + 0.20 x2 + 0.40 x3 <= 600 (This constraint is for the available production hours)
0.10 x1 + 0.30 x2 + 0.40 x3 <= 480 (This constraint is for the available assembly hours)
0.05 x2 + 0.075 x2 + 0.15 x3 <= 160 (This constraint is for the available inspection hours)

x1 >= 60 (This is for the minimum PC required in the inventory)

x1, x2, x3 >= 0 (this is the non-negativity constraint)

-------------------------

Standard form:

Max Z   =       60   x1   +   90   x2   +   100   x3   +   0   S1   +   0   S2   +   0   S3   +   0   S4   -   M   A1
subject to
0.2   x1   +   0.2   x2   +   0.4   x3   +       S1                                                   =   600
0.1   x1   +   0.3   x2   +   0.4   x3               +       S2                                       =   480
0.05   x1   +   0.075   x2   +   0.15   x3                           +       S3                           =   160
x1                                                               -       S4   +       A1   =   60
and x1,x2,x3,S1,S2,S3,S4,A1 ≥ 0

Iteration-1		Cj	60	90	100	0	0	0	0	-M
B	CB	XB	x1	x2	x3	S1	S2	S3	S4	A1	MinRatio XB / x1
S1	0	600	0.2	0.2	0.4	1	0	0	0	0	600/0.2=3000
S2	0	480	0.1	0.3	0.4	0	1	0	0	0	480/0.1=4800
S3	0	160	0.05	0.075	0.15	0	0	1	0	0	160/0.05=3200
A1	-M	60	(1)	0	0	0	0	0	-1	1	60/1=60→
Z=-60M		Zj	-M	0	0	0	0	0	M	-M
		Zj-Cj	-M-60↑	-90	-100	0	0	0	M	0

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

Row operations:

R4(new)=R4(old)

R1(new)=R1(old) - 0.2 * R4(new)

R2(new)=R2(old) - 0.1 * R4(new)

R3(new)=R3(old) - 0.05 * R4(new)

Iteration-2		Cj	60	90	100	0	0	0	0
B	CB	XB	x1	x2	x3	S1	S2	S3	S4	MinRatio XB / x3
S1	0	588	0	0.2	0.4	1	0	0	0.2	588/0.4=1470
S2	0	474	0	0.3	0.4	0	1	0	0.1	474/0.4=1185
S3	0	157	0	0.075	(0.15)	0	0	1	0.05	157/0.15=1046.667→
x1	60	60	1	0	0	0	0	0	-1	---
Z=3600		Zj	60	0	0	0	0	0	-60
		Zj-Cj	0	-90	-100↑	0	0	0	-60

Entering =x3, Departing =S3, Key Element =0.15

Row operations:

R3(new)=R3(old) / 0.15

R1(new)=R1(old) - 0.4 * R3(new)

R2(new)=R2(old) - 0.4 * R3(new)

R4(new)=R4(old)

Iteration-3		Cj	60	90	100	0	0	0	0
B	CB	XB	x1	x2	x3	S1	S2	S3	S4	MinRatio XB / x2
S1	0	169.333	0	0	0	1	0	-2.667	0.0667	---
S2	0	55.333	0	(0.1)	0	0	1	-2.667	-0.033	55.333/0.1=553.333→
x3	100	1046.667	0	0.5	1	0	0	6.667	0.333	1046.667/0.5=2093.333
x1	60	60	1	0	0	0	0	0	-1	---
Z=108266.667		Zj	60	50	100	0	0	666.667	-26.667
		Zj-Cj	0	-40↑	0	0	0	666.667	-26.667

Entering =x2, Departing =S2, Key Element =0.1

Row operations:

R2(new)=R2(old) / 0.1

R1(new)=R1(old)

R3(new)=R3(old) - 0.5 * R2(new)

R4(new)=R4(old)

Iteration-4		Cj	60	90	100	0	0	0	0
B	CB	XB	x1	x2	x3	S1	S2	S3	S4	MinRatio XB / S3
S1	0	169.333	0	0	0	1	0	-2.667	0.0667	---
x2	90	553.333	0	1	0	0	10	-26.667	-0.333	---
x3	100	770	0	0	1	0	-5	(20)	0.5	770/20=38.5→
x1	60	60	1	0	0	0	0	0	-1	---
Z=130400		Zj	60	90	100	0	400	-400	-40
		Zj-Cj	0	0	0	0	400	-400↑	-40

Entering =S3, Departing =x3, Key Element =20

Row operations:

R3(new)=R3(old) / 20

R1(new)=R1(old) + 2.667 * R3(new)

R2(new)=R2(old) + 26.667 * R3(new)

R4(new)=R4(old)

Iteration-5		Cj	60	90	100	0	0	0	0
B	CB	XB	x1	x2	x3	S1	S2	S3	S4	MinRatio XB / S4
S1	0	272	0	0	0.133	1	-0.667	0	0.333	272/0.1333=2040
x2	90	1580	0	1	1.333	0	3.333	0	0.333	1580/0.3333=4740
S3	0	38.5	0	0	0.05	0	-0.25	1	(0.025)	38.5/0.025=1540→
x1	60	60	1	0	0	0	0	0	-1	---
Z=145800		Zj	60	90	120	0	300	0	-30
		Zj-Cj	0	0	20	0	300	0	-30↑

Entering =S4, Departing =S3, Key Element =0.025

Row operations:

R3(new)=R3(old) / 0.025

R1(new)=R1(old) - 0.133 * R3(new)

R2(new)=R2(old) - 0.333 * R3(new)

R4(new)=R4(old) + R3(new)

Iteration-6		Cj	60	90	100	0	0	0	0
B	CB	XB	x1	x2	x3	S1	S2	S3	S4
S1	0	66.667	0	0	-0.133	1	0.667	-5.333	0
x2	90	1066.667	0	1	0.667	0	6.667	-13.333	0
S4	0	1540	0	0	2	0	-10	40	1
x1	60	1600	1	0	2	0	-10	40	0
Z=192000		Zj	60	90	180	0	0	1200	0
		Zj-Cj	0	0	80	0	0	1200	0

Since all the Zj-Cj ≥ 0, we have reached the optimality condition and the optimal solution is as follows:

x1 = 1600
x2 = 1066.67
x3 = 0
max. Z = 192,000