1. Solve Exercise 2.2 of the textbook using the Simplex method. For each diction
ID: 3145589 • Letter: 1
Question
1. Solve Exercise 2.2 of the textbook using the Simplex method. For each dictionary answer the follwoing questions: Determine the basic variables Determine the set of basic indices. Determine nonbasic variables. Determine the set of nonbasic indices. e the entering and leaving variables. . Determine the BFS. Determine the objective funciton's value. Graph the feasible region and locate each BFS on the graph. (Please note that you do not need to solve it by graphical solution method. That is already done in the previous homework.) On the graph, show the path the Simplex method takes to reach to the optimal solution.Explanation / Answer
Max Z = 2 x1 + x2
subject to
2 x1 + x2 4
2 x1 + 3 x2 3
4 x1 + x2 5
x1 + 5 x2 1
and x1,x20;
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
3. As the constraint 3 is of type '' we should add slack variable S3
4. As the constraint 4 is of type '' we should add slack variable S4
After introducing slack variables
Max Z = 2 x1 + x2 + 0 S1 + 0 S2 + 0 S3 + 0 S4
subject to
2 x1 + x2 + S1 = 4
2 x1 + 3 x2 + S2 = 3
4 x1 + x2 + S3 = 5
x1 + 5 x2 + S4 = 1
and x1,x2,S1,S2,S3,S40
Iteration-1 Cj 2 1 0 0 0 0
B CB XB x1 Entering variable x2 S1 S2 S3 S4 MinRatio
XB
x1
S1 0 4 2 1 1 0 0 0
4
2
=2
S2 0 3 2 3 0 1 0 0
3
2
=
3
2
S3 0 5 4 1 0 0 1 0
5
4
=
5
4
S4 Leaving variable 0 1 (1) (pivot element) 5 0 0 0 1
1
1
=1
Z=0 0=
Zj=CBXB Zj Zj=CBxj 0 0=0×2+0×2+0×4+0×1
Zj=CBx1 0 0=0×1+0×3+0×1+0×5
Zj=CBx2 0 0=0×1+0×0+0×0+0×0
Zj=CBS1 0 0=0×0+0×1+0×0+0×0
Zj=CBS2 0 0=0×0+0×0+0×1+0×0
Zj=CBS3 0 0=0×0+0×0+0×0+0×1
Zj=CBS4
Cj-Zj 2 2=2-0 1 1=1-0 0 0=0-0 0 0=0-0 0 0=0-0 0 0=0-0
Positive maximum Cj-Zj is 2 and its column index is 1. So, the entering variable is x1.
Minimum ratio is 1 and its row index is 4. So, the leaving basis variable is S4.
The pivot element is 1.
Entering =x1, Departing =S4, Key Element =1
R4(new)=R4(old)
R1(new)=R1(old)-2R4(new)
R2(new)=R2(old)-2R4(new)
R3(new)=R3(old)-4R4(new)
Iteration-2 Cj 2 1 0 0 0 0
B CB XB x1 x2 S1 S2 S3 S4 MinRatio
S1 0 2 2=4-2×1
R1(new)=R1(old)-2R4(new) 0 0=2-2×1
R1(new)=R1(old)-2R4(new) -9 -9=1-2×5
R1(new)=R1(old)-2R4(new) 1 1=1-2×0
R1(new)=R1(old)-2R4(new) 0 0=0-2×0
R1(new)=R1(old)-2R4(new) 0 0=0-2×0
R1(new)=R1(old)-2R4(new) -2 -2=0-2×1
R1(new)=R1(old)-2R4(new)
S2 0 1 1=3-2×1
R2(new)=R2(old)-2R4(new) 0 0=2-2×1
R2(new)=R2(old)-2R4(new) -7 -7=3-2×5
R2(new)=R2(old)-2R4(new) 0 0=0-2×0
R2(new)=R2(old)-2R4(new) 1 1=1-2×0
R2(new)=R2(old)-2R4(new) 0 0=0-2×0
R2(new)=R2(old)-2R4(new) -2 -2=0-2×1
R2(new)=R2(old)-2R4(new)
S3 0 1 1=5-4×1
R3(new)=R3(old)-4R4(new) 0 0=4-4×1
R3(new)=R3(old)-4R4(new) -19 -19=1-4×5
R3(new)=R3(old)-4R4(new) 0 0=0-4×0
R3(new)=R3(old)-4R4(new) 0 0=0-4×0
R3(new)=R3(old)-4R4(new) 1 1=1-4×0
R3(new)=R3(old)-4R4(new) -4 -4=0-4×1
R3(new)=R3(old)-4R4(new)
x1 2 1 1=1
R4(new)=R4(old) 1 1=1
R4(new)=R4(old) 5 5=5
R4(new)=R4(old) 0 0=0
R4(new)=R4(old) 0 0=0
R4(new)=R4(old) 0 0=0
R4(new)=R4(old) 1 1=1
R4(new)=R4(old)
Z=2 2=2×1
Zj=CBXB Zj Zj=CBxj 2 2=0×0+0×0+0×0+2×1
Zj=CBx1 10 10=0×(-9)+0×(-7)+0×(-19)+2×5
Zj=CBx2 0 0=0×1+0×0+0×0+2×0
Zj=CBS1 0 0=0×0+0×1+0×0+2×0
Zj=CBS2 0 0=0×0+0×0+0×1+2×0
Zj=CBS3 2 2=0×(-2)+0×(-2)+0×(-4)+2×1
Zj=CBS4
Cj-Zj 0 0=2-2 -9 -9=1-10 0 0=0-0 0 0=0-0 0 0=0-0 -2 -2=0-2
Since all Cj-Zj0
Hence, optimal solution is arrived with value of variables as :
x1=1,x2=0
Max Z=2
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.