Solve the following problem using the big M and twophase met

Solve the following problem using the big M and two-phase method:

Max Z=4x1+5x2

x1+2x2>=10

2x1+3x2<=60

x1,x2>=0

Solution

Given that Max Z=4X₁+5X₂

      subject to constraints

                  X₁+2X₂>=10

                 2X₁+3X₂<=60 and

                  X₁,X₂>=0

X₁

min

ratio=X_b/X₂

Entering =S₁,Departing=A₁, Key element=2

R₁(new)=[R₁(old)]/(2)=[R₁(old)]*(1/2)

R₂(new)=R₂(old)-3R₁(new)

Min

ratio=X_b/S₁

Entering=S₁ Departing=S₁, Key element=3/2

R₂(new)=[R2(old)]/(3/2)=[R₂(old)](2/3)

R₁(new)=[R₁(old)]+[(1/2)R₂(new)]

B

Min

Ratio=X_b/X₁

Entering=X₁ Departing=X₁, Key element=2/3

R₁(new)=[R₁(old)]/(2/3)=[R₁(old)](3/2)

R₂(new)=[R₂(old)]-[(1/3)R₁(new)]

Min

Ratio

Since all C_j-Z_j<=0

Optimum solution is arrived with value of variables as X₁=30

                                                                             X₂=0

                                              Maximize Z=120

Two Phase method

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

Max Z=4X₁+5X₂

      subject to constraints

                  X₁+2X₂>=10

                 2X₁+3X₂<=60 and

                  X₁,X₂>=0

Phase1

S₂

Min

Ratio=X_b/X₂

Entering=X₂ Departing=A₁, Key element=2

R₁(new)=[R₁(old)]/(2)=[R₁(old)](1/2)

R₂(new)=[R₂(old)]-[(3)R₁(new)]

Min

Ratio

Since all CjZj0,

Optimum Solution is arrived with value of variables as :X₁=0
                                                                              X₂=5

Maximise Z=0

Phase-2

Min

ratio

Entering=X₁ Departing=X₁, Key element=2/3

R₁(new)=[R₁(old)]/(2/3)=[R₁(old)](3/2)

R₂(new)=[R₂(old)]-[(1/3)R₁(new)]

		Cj	4	5	0	0	-M
B	Cb	Xb	X1	X2	S1	S2	A1	min ratio=Xb/X2
A1	-M	10	1	(2)	-1	0	1	10/2=5--->
S1	0	60	2	3	0	1	0	60/2=30
Z=0		Zj	-M	-2M	M	0	-M
		Cj-Zj	M+4	2M+5	-M	0	0