Scribd
Upload
3 views6 pages

Simplex Method for Linear Programming

The document outlines the steps of the Simplex Method for solving linear programming problems, specifically maximizing a function subject to constraints. It details the introduction of slack variables, the formation of the Simplex tableau, and the process of pivoting to find the optimal solution. The example provided illustrates the method with two and three-variable scenarios, concluding with the maximum values for the objective function.

Uploaded by

bonga.zoeloe
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views6 pages

Simplex Method for Linear Programming

The document outlines the steps of the Simplex Method for solving linear programming problems, specifically maximizing a function subject to constraints. It details the introduction of slack variables, the formation of the Simplex tableau, and the process of pivoting to find the optimal solution. The example provided illustrates the method with two and three-variable scenarios, concluding with the maximum values for the objective function.

Uploaded by

bonga.zoeloe
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

1

SIMPLEX METHOD

1. Given the problem: Maximize:

P = x + 2y

Subject to:

2x + 2y ≤ 6

2x + y ≤12 x,y ≥0

A. Introduce slack variables s and t:

2x + 2y + s =6

2x + y +t =12

Rewrite P=x+2y as P-x-2y=0

B. Write down Simplex Tableau

P x y s t constant column

0 2 2 1 0 6

0 2 1 0 1 12

------------------------------------------

1 -1 -2 0 0 0

C. Look in LAST row for first negative term=pivot column=col 2


D. In Pivot column take SMALLEST POSITIVE variable= pivot
row

2x=6 so x=3 = smallest positive

2y=12 so y=6 XXXX NO

So pivot row = row 1


2

Pivot is in row 1 and column 2 * *

P x y s t constant column

* 0 2 2 1 0 6

0 2 1 0 1 12

------------------------------------------

1 -1 -2 0 0 0

E. Convert the pivot value to 1

P x y s t constant column

0 1 1 1/2 0 3

0 2 1 0 1 12

------------------------------------------

1 -1 -2 0 0 0

F. Get all entries below pivot to 0 using pivot

P x y s t constant column

0 1 1 1/2 0 3

0 0 -1 -1 1 6

------------------------------------------

1 0 -1 1/2 0 3
3

G. Next FIRST minus in last row =pivot column

Smallest variable POSITIVE= pivot row-can’t use y

H. Pivot in col 3 row 1

P x y s t constant column

* 0 1 1 1/2 0 3

0 0 -1 -1 1 6

1 0 -1 1/2 0 3

I. Use new pivot to get entries in column to 0

P x y s t constant column

0 1 1 1/2 0 3

0 1 0 -1/2 1 9
1 1 0 1 0 6

NO NEGATIVES in last row so STOP STOP

Last row states P=6-s-x, but we must max P so s=0 and x=0

Thus P=6

First row states x+y=3-s/2 =3 But s=0 so x+y=3


4

So x=?? y=??

1. Repeat doing graphical method


2. Do eg. 2 on page 240 – 3 variables=mock test 5 and test 5

Eg. 3 variables

Maximise P=x+y+z subject to

x+y+0.z=1

0.x+y+ z=2

x+0.y+z=3 x,y,z all greater or eqial to 0

simplex tableau

P x y z a b c const

0 1 1 0 1 0 0 1

0 0 1 1 0 1 0 2

0 1 0 1 0 0 1 3

1 -1 -1 -1 0 0 0 0

Pivot col=col2 row =row 1

P x y z a b c const
5

0 1 1 0 1 0 0 1

0 0 1 1 0 1 0 2

0 1 0 1 0 0 1 3

1 -1 -1 -1 0 0 0 0

P x y z a b c const

0 1 1 0 1 0 0 1

0 0 1 1 0 1 0 2

0 0 -1 1 -1 0 1 2

1 0 0 -1 1 0 0 1

Pivot colum = col 4 row =2 or 3 take 2

P x y z a b c const

0 1 1 0 1 0 0 1

0 0 1 1 0 1 0 2

0 0 -2 0 -1 -1 1 0

1 0 1 0 1 1 0 3

P=3-a-b -y so a =0 and b=0and and y=0 and P=3

X+y=1so x=1

Y+z=2so z=2
6

You might also like