Simplex Method - Lecture notes 17 PDF

Preview

Summary

Professor: Shashi Shahi...

Description

Simplex Method -

-

The graphical solution can be used to solve linear programming problems involving 2 decision variables only Most linear programming problems are too large to be solved graphically so an algebraic solution (simplex method) must be used Tableau form - Provides the initial basic feasible solution - Eliminates all basic infeasible solutions - Two important properties - 1. For each constraint of the equation, the coefficient of one of the basic variables must be 1, and all of the others must be 0 - 2. The values of the right-hand sides of the constraint equations must be non-negative - Setting up the initial simplex tableau - General Notation - cj  = objective function coefficient for variable j  right-hand side value for constraint i - bi  = - aij  = coefficient associated with variable j in constraint i - Initial simplex tableau c1

c2

...cn

a11

a12

...a1n

b1

a21

a22

...a2n

b2

.

.

….

.

.

.

….

.

am1

am2

...amn

bm

-

Moving to a better simplex tableau - Add two more columns x1

x2

s1

s2

s3

Basis

CB

50

40

0

0

0

s1

0

3

5

1

0

0

150

s2

0

0

1

0

1

0

20

s3

0

8

5

0

0

1

300

-

The basic column has the current basic variables Column CB is the current objective function coefficient of the basic variable

-

Add two more rows to the tableau

-

-

x1

x2

s1

s2

s3

Basis

CB

50

40

0

0

0

s1

0

3

5

1

0

0

150

s2

0

0

1

0

1

0

20

s3

0

8

5

0

0

1

300

zj

0

0

0

0

0

0

cj - xj

50

40

0

0

0

Zj represents the decrease in the value of the objective function that will result if on unit of the variable corresponding to the jth column of the A matrix is brought to the basis (Cj - Zj ) Value of the objective function is taken by multiplying CB by the last column...