Simplex Method Problem

The simplex method is a method which goes from one BFS or extreme point of the feasible region of an Linear programming problem expressed in tableau form to another BFS, in such a way as to continually increase or decrease the value of the objective function until optimality is reached. The simplex method moves from one extreme point to one of its neighboring extreme point.

Let us see simplex method problems with solutions.

Simplex method problems :

Simplex method Problem 1:

Consider

x1 + x2  - x3 + x4                  = 5

2x1 – 3x2 + x3        + x5         = 3

-x1 + 2x2  - x3                 + x6 = 1

Solution:

The initial tableau is given by

Tableau 1:

x1       x2      x3      x4      x5      x6      b                             B1

x4   1         1       -1        1       0         0       5                      1     0     0

x5   2        -3         1       0       1         0       3                      0      1     0

x6   -1        2        -1       0       0          1      1                      0      0      1

The current basic solution is [ 0, 0 , 0, 5, 3, 1]T which is feasible. Suppose we choose a1,1 as our pivot element. Then after one pivot operation, we have

Tableau 2:

x1       x2      x3      x4      x5      x6      b                             B1

x1   1         1       -1        1       0         0       5                      1     0     0

x5   0        -5         3       -2       1         0    -7                      2      1     0

x6   0         3        -2        1        0         1      6                     -1      0      1

We note that the current basic solution is [ 5, 0, 0, 0, -7, 6]T which is infeasible. Using the new (2, 2) entry as pivot, we have

Tableau 3:

x1       x2      x3      x4      x5      x6      b                             B1

x1   1         0       -2/5    3/5    1/5     0   18/5                   1     0     0

x2   0         1        -3/5    2/5   -1/5    0   7/5                     2     -3     0

x6   0        0        -1/5   -1/5  -3/5     1    9/5                    -1     2      1

The current basic solution is [ 18/5 , 7/5, 0, 0, 0, 9/5]T and is feasible. Finally, let us eliminate the last slack variable x6 by replacing it by x3.

Tableau 4:

x1       x2      x3      x4      x5      x6      b                             B1

x1   1          0      0        1       -1         -2     0                      1      1     -1

x2   0         1        0       1        -2         -3     -4                    2      -3     1

x3   0        0        1      1       -2         -5     -9                      -1       2      -1

The current basic solution is [ 0, -4, -9, 0, 0, 0]T which is infeasible and degenerate.

I am planning to write more post on An even Number and neet medical pg entrance exam 2013. Keep checking my blog.

Simplex method Problem 2:

Problem 2:

A contractor is planning to build a new housing development consisting of colonial, split-level, and ranch-style houses. A colonial house requires one-half acre of land, $60,000 capital and 4,000 labor-hours to construct, and returns a profit of $20,000. A split-level house requires one-half acre of land $60,000 capital, and 3000 labor-hours to construct and returns a profit of $18,000. A ranch house requires 1 acre of land, $80,000 capital, and 4,000 labor-hours to construct, and returns a profit of $24,000. The contractor has available 30 acres of land, $3,200,000 capital, and 180,000 labor-hours. (Barnett 10e)*

How many houses of each type should be constructed to maximize the contactor’s profit? What is the maximum profit.

Solution:

1/2        1/2       1        1         0         0       0              30

2            2         0       -8         1         0      0              80

2            1         0       -4         0         1      0               60

-8000      -6000     0     24000    0          0      1           72000



0          1/4       1        2         0        -1/4   0              15

0            1         0       -4         1        -1      0              20

1           1/2       0       -2         0        1/2    0              30

0      -2000     0      8000    0       4000   1            960000



0            0         1        3       -1/4      0       0             10

0            1         0       -4         1        -1      0              20

1            0         0        0         1/2       1      0              20

0          0         0       0         2000    2000   1         1000000