Question

Maximization by the simplex method

Solve the following linear programming problems using the simplex method.

1>.

Maximize z = x₁ + 2x₂ + 3x₃

subject to x₁ + x₂ + x₃ ≤ 12

2x₁ + x₂ + 3x3 ≤ 18

x₁, x_2, x₃ ≥ 0

2>.

A farmer has 100 acres of land on which she plans to grow wheat and corn. Each acre of wheat requires 4 hours of labor and $20 of capital, and each acre of corn requires 16 hours of labor and $40 of capital. The farmer has at most 800 hours of labor and $2400 of capital available. If the profit from an acre of wheat is $80 and from an acre of corn is $100, how many acres of each crop should she plant to maximize her profit?

Answer 1

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 = x1 + 2 x2 + 3 x3 + 0 S1 + 0 S2

subject to

x1 + x2 + x3 + S1 = 12 2 x1 + x2 + 3 x3 + S2 = 18

and x1,x2,x3,S1,S2≥0 Negative minimum Zj-Cj is -3 and its column index is 3. So, the entering variable is x3. Minimum ratio is 6 and its row index is 2. So, the leaving basis variable is S2. ∴ The pivot element is 3. Entering =x3, Departing =S2, Key Element =3 Negative minimum Zj-Cj is -1 and its column index is 2. So, the entering variable is x2. Minimum ratio is 9 and its row index is 1. So, the leaving basis variable is S1. ∴ The pivot element is 2/3. Entering =x2, Departing =S1, Key Element =2/3 Since all Zj-Cj≥0 Hence, optimal solution is arrived with value of variables as : x1=0,x2=9,x3=3 Max Z=27