Solve the following linear program using the bounded simplex method (Algorithm 8

Question

Solve the following linear program using the bounded simplex method (Algorithm 8.3)

Max 4x + 5y

s.t.

x - y <= 4

2x - y => -1

0 <= x <= 6

0 <= y <= 2

For Algorithm 8.3 (bounded simplex method) see the link below on pg 306:

https://books.google.com/books?id=0Hv4QGvsbpQC&pg=PA305&dq=algorithm+8.3+bounded+simplex+(maximization+problem)&hl=en&sa=X&ved=0ahUKEwiHs4m_qb_ZAhXSl-AKHRxfDB0Q6AEIKTAA#v=onepage&q=algorithm%208.3%20bounded%20simplex%20(maximization%20problem)&f=false

Explanation / Answer

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

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

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

The pivot element is 1.

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

R2(new)=R2(old)

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

R3(new)=R3(old)

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

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

Minimum ratio is 0.5 and its row index is 4. So, the leaving basis variable is S4.

The pivot element is 2.

Entering =x1, Departing =S4, Key Element =2

R4(new)=R4(old)÷2

R1(new)=R1(old)+R4(new)

R2(new)=R2(old)+2R4(new)

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

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

Minimum ratio is 11 and its row index is 3. So, the leaving basis variable is S3.

The pivot element is 12.

Entering =S2, Departing =S3, Key Element =12

R3(new)=R3(old)×2

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

R2(new)=R2(old)

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

Since all Cj-Zj0

Hence, optimal solution is arrived with value of variables as :
x1=6,x2=2

Max Z=34

Max Z = 4 x1 + 5 x2 subject to x1 - x2 4 2 x1 - x2 -1 Here b2 = -1 < 0,
so multiply this constraint by -1 to make b2 > 0. - 2 x1 + x2 1 x1 6 x2 2 and x1,x20;

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.