Question

Maximize 4x + 6y subject to the following constraints (using the simplex method)

x + 4y <= 4

3x + 2y <= 6

x>= 0, y>= 0

Answer 1

Print This Solution Close This Solution

Find solution using Simplex(BigM) method
MAX Z = 4x1 + 6x2
subject to
x1 + 4x2 <= 4
3x1 + 2x2 <= 6
and x1,x2 >= 0

Solution:
Problem is

Max Z = 4 x1 + 6 x2

subject to

x1 + 4 x2 ≤ 4 3 x1 + 2 x2 ≤ 6

and x1,x2≥0;

The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate

1. As the constraint 1 is of type '≤' we should add slack variable S1

2. As the constraint 2 is of type '≤' we should add slack variable S2

After introducing slack variables

Max Z = 4 x1 + 6 x2 + 0 S1 + 0 S2

subject to

x1 + 4 x2 + S1 = 4 3 x1 + 2 x2 + S2 = 6

and x1,x2,S1,S2≥0

Iteration-1		Cj	4	6	0	0
B	CB	XB	x1	x2 Entering variable	S1	S2	MinRatio XBx2
S1 Leaving variable	0	4	1	(4) (pivot element)	1	0	44=1→
S2	0	6	3	2	0	1	62=3
Z=0 0= Zj=∑CBXB		Zj Zj=∑CBxj	0 0=0×1+0×3 Zj=∑CBx1	0 0=0×4+0×2 Zj=∑CBx2	0 0=0×1+0×0 Zj=∑CBS1	0 0=0×0+0×1 Zj=∑CBS2
		Cj-Zj	4 4=4-0	6 6=6-0↑	0 0=0-0	0 0=0-0

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

Minimum ratio is 1 and its row index is 1. So, the leaving basis variable is S1.

∴ The pivot element is 4.

Entering =x2, Departing =S1, Key Element =4

R1(new)=R1(old)÷4

R2(new)=R2(old)-2R1(new)

Iteration-2		Cj	4	6	0	0
B	CB	XB	x1 Entering variable	x2	S1	S2	MinRatio XBx1
x2	6	1 1=4÷4 R1(new)=R1(old)÷4	0.25 0.25=1÷4 R1(new)=R1(old)÷4	1 1=4÷4 R1(new)=R1(old)÷4	0.25 0.25=1÷4 R1(new)=R1(old)÷4	0 0=0÷4 R1(new)=R1(old)÷4	10.25=4
S2 Leaving variable	0	4 4=6-2×1 R2(new)=R2(old)-2R1(new)	(2.5) 2.5=3-2×0.25 (pivot element) R2(new)=R2(old)-2R1(new)	0 0=2-2×1 R2(new)=R2(old)-2R1(new)	-0.5 -0.5=0-2×0.25 R2(new)=R2(old)-2R1(new)	1 1=1-2×0 R2(new)=R2(old)-2R1(new)	42.5=1.6→
Z=6 6=6×1 Zj=∑CBXB		Zj Zj=∑CBxj	1.5 1.5=6×0.25+0×2.5 Zj=∑CBx1	6 6=6×1+0×0 Zj=∑CBx2	1.5 1.5=6×0.25+0×(-0.5) Zj=∑CBS1	0 0=6×0+0×1 Zj=∑CBS2
		Cj-Zj	2.5 2.5=4-1.5↑	0 0=6-6	-1.5 -1.5=0-1.5	0 0=0-0

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

Minimum ratio is 1.6 and its row index is 2. So, the leaving basis variable is S2.

∴ The pivot element is 2.5.

Entering =x1, Departing =S2, Key Element =2.5

R2(new)=R2(old)×0.4

R1(new)=R1(old)-0.25R2(new)

Iteration-3		Cj	4	6	0	0
B	CB	XB	x1	x2	S1	S2	MinRatio
x2	6	0.6 0.6=1-0.25×1.6 R1(new)=R1(old)-0.25R2(new)	0 0=0.25-0.25×1 R1(new)=R1(old)-0.25R2(new)	1 1=1-0.25×0 R1(new)=R1(old)-0.25R2(new)	0.3 0.3=0.25-0.25×(-0.2) R1(new)=R1(old)-0.25R2(new)	-0.1 -0.1=0-0.25×0.4 R1(new)=R1(old)-0.25R2(new)
x1	4	1.6 1.6=4×0.4 R2(new)=R2(old)×0.4	1 1=2.5×0.4 R2(new)=R2(old)×0.4	0 0=0×0.4 R2(new)=R2(old)×0.4	-0.2 -0.2=(-0.5)×0.4 R2(new)=R2(old)×0.4	0.4 0.4=1×0.4 R2(new)=R2(old)×0.4
Z=10 10=6×0.6+4×1.6 Zj=∑CBXB		Zj Zj=∑CBxj	4 4=6×0+4×1 Zj=∑CBx1	6 6=6×1+4×0 Zj=∑CBx2	1 1=6×0.3+4×(-0.2) Zj=∑CBS1	1 1=6×(-0.1)+4×0.4 Zj=∑CBS2
		Cj-Zj	0 0=4-4	0 0=6-6	-1 -1=0-1	-1 -1=0-1

Since all Cj-Zj≤0

Hence, optimal solution is arrived with value of variables as :
x1=1.6,x2=0.6

Max Z=10