[go: up one dir, main page]
Scribd
Upload
629 views18 pages

Simplex Method

The document provides information about solving linear programming problems using the simplex method. It begins with an introduction to the simplex method and how it examines corner points in a systematic, iterative manner to find an optimal solution. It then sets up an example problem from Flair Furniture Company to demonstrate converting constraints to equations by adding slack variables. The document shows the steps to find an initial basic feasible solution and formulate the first simplex tableau. It continues walking through the iterative process of finding the pivot column and updating the tableau at each step until an optimal solution is identified where no negative entries remain in the last row.

Uploaded by

Afzal Khan
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
629 views18 pages

Simplex Method

The document provides information about solving linear programming problems using the simplex method. It begins with an introduction to the simplex method and how it examines corner points in a systematic, iterative manner to find an optimal solution. It then sets up an example problem from Flair Furniture Company to demonstrate converting constraints to equations by adding slack variables. The document shows the steps to find an initial basic feasible solution and formulate the first simplex tableau. It continues walking through the iterative process of finding the pivot column and updating the tableau at each step until an optimal solution is identified where no negative entries remain in the last row.

Uploaded by

Afzal Khan
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 18

Linear Programming

Simplex Method
Dr. Md. Nusrate Aziz Graduate School of Management Multimedia University

October 2013

Reference
Quantitative Analysis for Management, by Barry Render and Ralph M. Stair, JR. - Pearson International Edition. Chapter 9. Fundamental Methods of Mathematical Economics, by Alpha C. Chiang (3rd Edition), McGraw-Hill International Editions. Chapter 19.

Introduction
With only two decision variables it is possible to use graphical methods to solve LP problems. But most real life LP problems are too complex for simple graphical procedures. We need a more powerful procedure called the simplex method. The simplex method examines the corner points in a systematic fashion using basic algebraic concepts. It does this in an iterative manner until an optimal solution is found. Each iteration moves us closer to the optimal solution.

Setting-up Initial Simplex Model


Lets look at the Flair Furniture Company. This time well use the simplex method to solve the problem You may recall,

X1 = number of tables produced. X2 = number of chairs produced.


(painting hours constraint) (carpentry hours constraint) (non-negativity constraints)

Converting the Constraints to Equations


The inequality constraints must be converted into equations. Less-than-or-equal-to constraints () are converted to equations by

adding a slack variable (surplus for min) to each. Slack variables represent unused resources. For the Flair Furniture problem, the slacks are S1 = slack variable representing unused hours in the painting department S2 = slack variable representing unused hours in the carpentry department The constraints may now be written as 4X1 + 3X2+ S1 = 240 2X1 + 1X2 + S2 = 100

Slack Variable
If the optimal solution uses less than the available amount of a

resource, the unused resource is slack. For example, if Flair produces X1 = 40 tables and X2 = 10 chairs, the painting constraint will be 2 X1 + 1 X2 + S2 = 100 2(40) + 1(10) + S2 = 100 S2 = 10 So, there will be 10 hours of slack, or unused painting capacity.

Finding an Initial Solution Algebraically


There are now two equations and four variables. When there are more unknowns than equations, you have to set some of

the variables equal to 0 and solve for the others. In this example, two variables must be set to 0 so we can solve for the other two. A solution found in this manner is called a basic feasible solution.

Re-write Equations
We now re-write the constraints and objective functions including two slack variables. 4X1 + 3X2 + S1 = 240 2X1 + 1X2 + S2 = 100 -7X1 - 5X2 + =0 Lets formulate the first tableau in the next slide.

It simplifies handling the LP equations if we put them in tabular form. These are two constraint equations for the Flair Furniture problem. Since there are two constraints, there would be two slack variables (say, S1 and S2).

Maximization Problem

The First Simplex Tableau


The tableau 1 is as follows:
X1
4 2

X2
3 1

S1
1 0

S2
0 1

0 0

QUANTITY 240 100

-7

-5

We now need to find the most negative indicator in the last row to find the pivot column. Then divide the values of constraints in the quantity column by the respective values in the selected column. Then use the smallest non-negative entry to find the pivot column.
X1 X2
3 1

S1
1 0

S2
0 1

0 0

QUANTITY 240/4 = 60 100/2 = 50

2
-7

-5

Simplex Tableau
Now make the pivot element 1 and others in the pivot column, zero. R2 => R2 -4R2+R1 => R1 7R2+R3 => R3 After calculation we should get the following tableau:
X1
0 1

X2
1 1/2

S1
1 0

S2
-2 1/2

0 0

QUANTITY 40 50

-3/2

7/2

350

We still have negative value in the last row. So we follow the same rule.

Simplex Tableau
Find the smallest non-negative entry.
X1
0 1 0

X2
1 1/2 -3/2

S1
1 0 0

S2
-2 1/2 7/2

0 0 1

QUANTITY
40/1 = 40 50/(1/2) = 100 350

1 R1 => R1 -1/2 R1+R2 => R2 3/2 R1+R3 =>R3


X1
0 1 0

X2

S1
1 -1/2 3/2

S2
-2 3/2 1/2

0 0 1

QUANTITY 40 30 410

1
0 0

Notice that there is no negative entry in the last row. It suggest they are OPTIMAL!

Simplex Solution
S1 and S2 are not unique column so they are non basics, which means, they are zero. Therefore, X1 = 30; X2 = 40; S1 = 0; S2 = 0 and = 410. These can be obtained from the following matrix.
1 0 0 1 0 0 0 2 40 0 1 = 30 1 410

So, Maximum profit is $410 when we produce 30 tables and 40 chairs.

Minimization Problem

Minimization Problem (by using the DUAL)


Minimize, Subject to, w = 29 y1 + 10 y2 3y1 + 2y2 2 5y1+y2 3 y1, y2 0
2 1 10 2 3 0

Write a Matrix:
3 = 5 29

3 = 2 2

5 29 1 10 3 0

Re-write the dual as a standard maximization problem: Maximization, Z = 2x2 + 3x3 Subject to, 3x1 + 5x2 29 2x1 + 1x2 10 x1, x2 0

Minimization Problem (by using the DUAL)


Dual 5
29 4 =5 5 5 10 = 10 1

Most negative

1/5R1 => R1 -R1+R2 => R2 3R1+R3 => R3


29 5 29 2 . = =9 5 8 3 3 21 5 . =3 5 7

Most negative

Minimization Problem (by using the DUAL)


5/7 R2 => R2 -3/5 R2+ R1 => R1 1/5 R2 + R3 => R3

Use DUAL to obtain values. y1 = 4/7, y2 = 1/7 So, Minimum value of 18 at (4/7, 1/7).

What is Next?

You might also like