Question

In: Operations Management

Answer the following questions for the linear programming problem given below: Write the Phase-One LP model...

Answer the following questions for the linear programming problem given below:

  1. Write the Phase-One LP model
  2. Conduct one iteration of the Simplex method.
  3. Describe how the optimal solution to the original problem will be determined from this point on.

maxz=2x1+3x2+x3maxz=2x1+3x2+x3

Subject to:Subject to:

x1+x2+x3≤40x1+x2+x3≤40

2x1+x2−x3≥102x1+x2−x3≥10

−x1+x3≥10−x1+x3≥10

x1,x2,x3≥0

Solutions

Expert Solution

PHASE ONE

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 subtract surplus variable S2 and add artificial variable A1
3. As the constraint-3 is of type '≥' we should subtract surplus variable S3 and add artificial variable A2

After introducing slack,surplus,artificial variables

Max Z = - A1 - A2
subject to
x1 + x2 + x3 + S1 = 400
2 x1 + x2 - x3 - S2 + A1 = 102
- x1 + x3 - S3 + A2 = 10
and x1,x2,x3,S1,S2,S3,A1,A2≥0
Iteration-1 Cj 0 0 0 0 0 0 -1 -1
B CB XB x1 x2 x3 S1 S2 S3 A1 A2 MinRatio
XBx1
S1 0 400 1 1 1 1 0 0 0 0 4001=400
A1 -1 102 (2) 1 -1 0 -1 0 1 0 1022=51→
A2 -1 10 -1 0 1 0 0 -1 0 1 ---
Z=-112 Zj -1 -1 0 0 1 1 -1 -1
Zj-Cj -1↑ -1 0 0 1 1 0 0

Negative minimum Zj-Cj is -1 and its column index is 1. So, the entering variable is x1.
Minimum ratio is 51 and its row index is 2. So, the leaving basis variable is A1.
∴ The pivot element is 2.
Entering =x1, Departing =A1, Key Element =2

R2(new)=R2(old)÷2

R2(old) = 102 2 1 -1 0 -1 0 0
R2(new)=R2(old)÷2 51 1 0.5 -0.5 0 -0.5 0 0

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

R1(old) = 400 1 1 1 1 0 0 0
R2(new) = 51 1 0.5 -0.5 0 -0.5 0 0
R1(new)=R1(old) - R2(new) 349 0 0.5 1.5 1 0.5 0 0

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

R3(old) = 10 -1 0 1 0 0 -1 1
R2(new) = 51 1 0.5 -0.5 0 -0.5 0 0
R3(new)=R3(old) + R2(new) 61 0 0.5 0.5 0 -0.5 -1 1
Iteration-2 Cj 0 0 0 0 0 0 -1
B CB XB x1 x2 x3 S1 S2 S3 A2 MinRatio
XBx2
S1 0 349 0 0.5 1.5 1 0.5 0 0 3490.5=698
x1 0 51 1 (0.5) -0.5 0 -0.5 0 0 510.5=102→
A2 -1 61 0 0.5 0.5 0 -0.5 -1 1 610.5=122
Z=-61 Zj 0 -0.5 -0.5 0 0.5 1 -1
Zj-Cj 0 -0.5↑ -0.5 0 0.5 1 0

Negative minimum Zj-Cj is -0.5 and its column index is 2. So, the entering variable is x2.
Minimum ratio is 102 and its row index is 2. So, the leaving basis variable is x1.
∴ The pivot element is 0.5.
Entering =x2, Departing =x1, Key Element =0.5

R2(new)=R2(old)÷0.5

R2(old) = 51 1 0.5 -0.5 0 -0.5 0 0
R2(new)=R2(old)÷0.5 102 2 1 -1 0 -1 0 0

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

R1(old) = 349 0 0.5 1.5 1 0.5 0 0
R2(new) = 102 2 1 -1 0 -1 0 0
0.5×R2(new) = 51 1 0.5 -0.5 0 -0.5 0 0
R1(new)=R1(old) - 0.5R2(new) 298 -1 0 2 1 1 0 0

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

R3(old) = 61 0 0.5 0.5 0 -0.5 -1 1
R2(new) = 102 2 1 -1 0 -1 0 0
0.5×R2(new) = 51 1 0.5 -0.5 0 -0.5 0 0
R3(new)=R3(old) - 0.5R2(new) 10 -1 0 1 0 0 -1 1
Iteration-3 Cj 0 0 0 0 0 0 -1
B CB XB x1 x2 x3 S1 S2 S3 A2 MinRatio
XBx3
S1 0 298 -1 0 2 1 1 0 0 2982=149
x2 0 102 2 1 -1 0 -1 0 0 ---
A2 -1 10 -1 0 (1) 0 0 -1 1 101=10→
Z=-10 Zj 1 0 -1 0 0 1 -1
Zj-Cj 1 0 -1↑ 0 0 1 0

Negative minimum Zj-Cj is -1 and its column index is 3. So, the entering variable is x3.
Minimum ratio is 10 and its row index is 3. So, the leaving basis variable is A2.
∴ The pivot element is 1.
Entering =x3, Departing =A2, Key Element =1

R3(new)=R3(old)

R3(old) = 10 -1 0 1 0 0 -1
R3(new)=R3(old) 10 -1 0 1 0 0 -1

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

R1(old) = 298 -1 0 2 1 1 0
R3(new) = 10 -1 0 1 0 0 -1
2×R3(new) = 20 -2 0 2 0 0 -2
R1(new)=R1(old) - 2R3(new) 278 1 0 0 1 1 2

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

R2(old) = 102 2 1 -1 0 -1 0
R3(new) = 10 -1 0 1 0 0 -1
R2(new)=R2(old) + R3(new) 112 1 1 0 0 -1 -1
Iteration-4 Cj 0 0 0 0 0 0
B CB XB x1 x2 x3 S1 S2 S3 MinRatio
S1 0 278 1 0 0 1 1 2
x2 0 112 1 1 0 0 -1 -1
x3 0 10 -1 0 1 0 0 -1
Z=0 Zj 0 0 0 0 0 0
Zj-Cj 0 0 0 0 0 0

Since all Zj-Cj≥0
Hence, optimal solution is arrived with value of variables as :
x1=0,x2=112,x3=10
Max Z=0

SIMPLEX METHOD

Max Z = 2 x1 + 3 x2 + x3
subject to
x1 + x2 + x3 ≤ 400
2 x1 + x2 - x3 ≥ 102
- x1 + x3 ≥ 10
and x1,x2,x3≥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 subtract surplus variable S2 and add artificial variable A1
3. As the constraint-3 is of type '≥' we should subtract surplus variable S3 and add artificial variable A2

After introducing slack,surplus,artificial variables

Max Z = 2 x1 + 3 x2 + x3 + 0 S1 + 0 S2 + 0 S3 - M A1 - M A2
subject to
x1 + x2 + x3 + S1 = 400
2 x1 + x2 - x3 - S2 + A1 = 102
- x1 + x3 - S3 + A2 = 10
and x1,x2,x3,S1,S2,S3,A1,A2≥0
Iteration-1 Cj 2 3 1 0 0 0 -M -M
B CB XB x1 x2 x3 S1 S2 S3 A1 A2 MinRatio
XBx2
S1 0 400 1 1 1 1 0 0 0 0 4001=400
A1 -M 102 2 (1) -1 0 -1 0 1 0 1021=102→
A2 -M 10 -1 0 1 0 0 -1 0 1 ---
Z=-112M Zj -M -M 0 0 M M -M -M
Zj-Cj -M-2 -M-3↑ -1 0 M M 0 0

Negative minimum Zj-Cj is -M-3 and its column index is 2. So, the entering variable is x2.
Minimum ratio is 102 and its row index is 2. So, the leaving basis variable is A1.
∴ The pivot element is 1.
Entering =x2, Departing =A1, Key Element =1

R2(new)=R2(old)

R2(old) = 102 2 1 -1 0 -1 0 0
R2(new)=R2(old) 102 2 1 -1 0 -1 0 0

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

R1(old) = 400 1 1 1 1 0 0 0
R2(new) = 102 2 1 -1 0 -1 0 0
R1(new)=R1(old) - R2(new) 298 -1 0 2 1 1 0 0

R3(new)=R3(old)

R3(old) = 10 -1 0 1 0 0 -1 1
R3(new)=R3(old) 10 -1 0 1 0 0 -1 1
Iteration-2 Cj 2 3 1 0 0 0 -M
B CB XB x1 x2 x3 S1 S2 S3 A2 MinRatio
XBx3
S1 0 298 -1 0 2 1 1 0 0 2982=149
x2 3 102 2 1 -1 0 -1 0 0 ---
A2 -M 10 -1 0 (1) 0 0 -1 1 101=10→
Z=-10M+306 Zj M+6 3 -M-3 0 -3 M -M
Zj-Cj M+4 0 -M-4↑ 0 -3 M 0

Negative minimum Zj-Cj is -M-4 and its column index is 3. So, the entering variable is x3.
Minimum ratio is 10 and its row index is 3. So, the leaving basis variable is A2.
∴ The pivot element is 1.
Entering =x3, Departing =A2, Key Element =1

R3(new)=R3(old)

R3(old) = 10 -1 0 1 0 0 -1
R3(new)=R3(old) 10 -1 0 1 0 0 -1

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

R1(old) = 298 -1 0 2 1 1 0
R3(new) = 10 -1 0 1 0 0 -1
2×R3(new) = 20 -2 0 2 0 0 -2
R1(new)=R1(old) - 2R3(new) 278 1 0 0 1 1 2

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

R2(old) = 102 2 1 -1 0 -1 0
R3(new) = 10 -1 0 1 0 0 -1
R2(new)=R2(old) + R3(new) 112 1 1 0 0 -1 -1
Iteration-3 Cj 2 3 1 0 0 0
B CB XB x1 x2 x3 S1 S2 S3 MinRatio
XBS3
S1 0 278 1 0 0 1 1 (2) 2782=139→
x2 3 112 1 1 0 0 -1 -1 ---
x3 1 10 -1 0 1 0 0 -1 ---
Z=346 Zj 2 3 1 0 -3 -4
Zj-Cj 0 0 0 0 -3 -4↑

Negative minimum Zj-Cj is -4 and its column index is 6. So, the entering variable is S3.
Minimum ratio is 139 and its row index is 1. So, the leaving basis variable is S1.
∴ The pivot element is 2.
Entering =S3, Departing =S1, Key Element =2

R1(new)=R1(old)÷2

R1(old) = 278 1 0 0 1 1 2
R1(new)=R1(old)÷2 139 0.5 0 0 0.5 0.5 1

R2(new)=R2(old) + R1(new)

R2(old) = 112 1 1 0 0 -1 -1
R1(new) = 139 0.5 0 0 0.5 0.5 1
R2(new)=R2(old) + R1(new) 251 1.5 1 0 0.5 -0.5 0

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

R3(old) = 10 -1 0 1 0 0 -1
R1(new) = 139 0.5 0 0 0.5 0.5 1
R3(new)=R3(old) + R1(new) 149 -0.5 0 1 0.5 0.5 0
Iteration-4 Cj 2 3 1 0 0 0
B CB XB x1 x2 x3 S1 S2 S3 MinRatio
XBS2
S3 0 139 0.5 0 0 0.5 (0.5) 1 1390.5=278→
x2 3 251 1.5 1 0 0.5 -0.5 0 ---
x3 1 149 -0.5 0 1 0.5 0.5 0 1490.5=298
Z=902 Zj 4 3 1 2 -1 0
Zj-Cj 2 0 0 2 -1↑ 0

Negative minimum Zj-Cj is -1 and its column index is 5. So, the entering variable is S2.
Minimum ratio is 278 and its row index is 1. So, the leaving basis variable is S3.
∴ The pivot element is 0.5.
Entering =S2, Departing =S3, Key Element =0.5

R1(new)=R1(old)÷0.5

R1(old) = 139 0.5 0 0 0.5 0.5 1
R1(new)=R1(old)÷0.5 278 1 0 0 1 1 2

R2(new)=R2(old) + 0.5R1(new)

R2(old) = 251 1.5 1 0 0.5 -0.5 0
R1(new) = 278 1 0 0 1 1 2
0.5×R1(new) = 139 0.5 0 0 0.5 0.5 1
R2(new)=R2(old) + 0.5R1(new) 390 2 1 0 1 0 1

R3(new)=R3(old) - 0.5R1(new)

R3(old) = 149 -0.5 0 1 0.5 0.5 0
R1(new) = 278 1 0 0 1 1 2
0.5×R1(new) = 139 0.5 0 0 0.5 0.5 1
R3(new)=R3(old) - 0.5R1(new) 10 -1 0 1 0 0 -1
Iteration-5 Cj 2 3 1 0 0 0
B CB XB x1 x2 x3 S1 S2 S3 MinRatio
S2 0 278 1 0 0 1 1 2
x2 3 390 2 1 0 1 0 1
x3 1 10 -1 0 1 0 0 -1
Z=1180 Zj 5 3 1 3 0 2
Zj-Cj 3 0 0 3 0 2

Since all Zj-Cj≥0
Hence, optimal solution is arrived with value of variables as :
x1=0,x2=390,x3=10
Max Z=1180

keosha answered 2 hours ago
< Previous

Related Solutions

Given the following linear programming model, answer the questions that follow. You are given the result...
Given the following linear programming model, answer the questions that follow. You are given the result of a computer program. The results are Maximize 9 X1 + 12 X2 + 10 X3 Subject to: Machine Constraint:   3 X1 + 4 X2 + 3 X3 < 160 Labor Constraint:        6 X1 + 10 X2 + 4 X3 < 288 Materials Constraint: 2 X1 + 2 X2 + 7 X3 < 200 Product 2 Constraint: X1 < 16 OPTIMAL SOLUTION Objective Function Value...
Given the following linear programming model, answer the questions that follow. You are given the result...
Given the following linear programming model, answer the questions that follow. You are given the result of a computer program. The results are Maximize 9 X1 + 12 X2 + 10 X3 Subject to: Machine Constraint:   3 X1 + 4 X2 + 3 X3 < 160 Labor Constraint:        6 X1 + 10 X2 + 4 X3 < 288 Materials Constraint: 2 X1 + 2 X2 + 7 X3 < 200 Product 2 Constraint: X1 < 16 OPTIMAL SOLUTION Objective Function Value...
QUESTION 1: Solve the linear programming model given below using the simplex method. Write the primal...
QUESTION 1: Solve the linear programming model given below using the simplex method. Write the primal and dual results from the optimal table you obtained. MAX Z = 10?1 + 20?2 + 5?3 6?1 + 7?2 + 12?3 ≥ 560 5?1 − 3?2 +   x3 ≤ 100 2000?1 + 1000?2 + 1000?3 ≤ 62298 ?1,?2,?3 ≥ 0 IMPORTANT REMINDER ABOUT THE QUESTION SOLUTION: NEW ORDER CALCULATIONS SHOULD BE WRITTEN DETAILED WHEN CREATING THE SYMPLEX TABLES. WHEN THE CALCULATIONS ARE SHOWED AND...
Below given is the linear programming model at a manufacturing firm which produces and sells for...
Below given is the linear programming model at a manufacturing firm which produces and sells for different bags: small bags, medium bags, standard bags, and deluxe bags. DECISION VARIABLES: xi- Number of bags for group i to produce, i=1(small bag), 2(medium bag), 3(standard bag), 4(deluxe bag). OBJECTIVE FUNCTION: Maximize profit, z = 6.5x1 + 7.5x 2 +10x3 + 9x4 CONSTRAINTS: 0.55x1 + 0.6x 2 + 0.7x3 + x4 ≤ 630 (Cutting and dyeing) 0.425x1 + 0.45x 2 + 0.5x3 +...
Consider the following transportation problem. Formulate this problem as a linear programming model and solve it...
Consider the following transportation problem. Formulate this problem as a linear programming model and solve it using the MS Excel Solver tool. Shipment Costs ($), Supply, and Demand: Destinations Sources 1 2 3 Supply A 6 9 100 130 B 12 3 5 70 C 4 8 11 100 Demand 80 110 60 (4 points) Volume Shipped from Source A __________ (4 points) Volume Shipped from Source B __________ (4 points) Volume Shipped from Source C __________ (3 points) Minimum...
Solve this linear programming (LP) problem using the transportation method. Find the optimal transportation plan and...
Solve this linear programming (LP) problem using the transportation method. Find the optimal transportation plan and the minimum cost. (Leave no cells blank - be certain to enter "0" wherever required. Omit the "$" sign in your response.) Minimize 8x11 + 2x12 + 5x13 + 2x21 + x22 + 3x23 + 7x31 + 2x32 + 6x33 Subject to x11 + x12 + x13 = 90 x21 + x22 + x23 = 105 x31 + x32 + x33 = 105 x11...
Linear programming. Solve the following two (2) Linear programming problems (#1 and #2) and then answer...
Linear programming. Solve the following two (2) Linear programming problems (#1 and #2) and then answer question 3: 1.. Solve the following LP problem graphically: Maximize profit =            X + 10Y Subject to:                        4X + 3Y < /= 36                                            2X +4Y < / = 40                                            Y > / = 3                                            X, Y > / = 0 2. Considering the following LP problem and answer the questions, Part a and Part b: Maximize profit =            30X1...
Partial of the Solver Sensitivity Report for the LP model in Problem (3) is provided below....
Partial of the Solver Sensitivity Report for the LP model in Problem (3) is provided below. Microsoft Excel 16.0 Sensitivity Report Constraints Final Shadow Constraint Allowable Allowable Cell Name Value Price R.H. Side Increase Decrease $I$9 Component A 4000 11.33 4000 1250 4000 $I$10 Component B 2667 0 3500 1E+30 833 Answer the following questions based this report. (a) If 1,000 additional units of component A are available at a unit cost of $10, should the company take it? Why...
Every linear programming problem involves optimizing a: Select one: a. linear function subject to several linear...
Every linear programming problem involves optimizing a: Select one: a. linear function subject to several linear constraints b. linear regression model subject to several linear constraints c. linear function subject to several non-linear constraints d. non-linear function subject to several linear constraints
Below is the linear programming for the Shortest Path Problem. Considering the second contraint in the...
Below is the linear programming for the Shortest Path Problem. Considering the second contraint in the mathematical model : ∑ixji−∑ixij=0∀j≠s,j≠t What is the logic behind this contraint? To make sure there is only one solution To make sure that the path is connected between the nodes To make sure the variable stays binary This contraint is redundant and not necessary Which of the following statements are true? (select all that apply) The shape of a student t-distribution curve depends on...
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT