# Connexions

You are here: Home » Content » Applied Finite Mathematics » Linear Programing: The Simplex Method

### Lenses

What is a lens?

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

#### Endorsed by (What does "Endorsed by" mean?)

This content has been endorsed by the organizations listed. Click each link for a list of all content endorsed by the organization.
• College Open Textbooks

This collection is included inLens: Community College Open Textbook Collaborative
By: CC Open Textbook Collaborative

"Reviewer's Comments: 'I recommend this book for undergraduates. The content is especially useful for those in finance, probability statistics, and linear programming. The course material is […]"

Click the "College Open Textbooks" link to see all content they endorse.

Click the tag icon to display tags associated with this content.

#### Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
• Bookshare

This collection is included inLens: Bookshare's Lens
By: Bookshare - A Benetech Initiative

"Accessible versions of this collection are available at Bookshare. DAISY and BRF provided."

Click the "Bookshare" link to see all content affiliated with them.

• Featured Content

This collection is included inLens: Connexions Featured Content
By: Connexions

"Applied Finite Mathematics covers topics including linear equations, matrices, linear programming, the mathematics of finance, sets and counting, probability, Markov chains, and game theory."

Click the "Featured Content" link to see all content affiliated with them.

Click the tag icon to display tags associated with this content.

### Recently Viewed

This feature requires Javascript to be enabled.

### Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.

Inside Collection:

Collection by: Rupinder Sekhon. E-mail the author

# Linear Programing: The Simplex Method

Module by: Rupinder Sekhon. E-mail the author

Summary: This chapter covers principles of the simplex method to Linear Programming. After completing this chapter students should be able to: solve linear programming maximization problems using the simplex method and solve the minimization problems using the simplex method.

## Chapter Overview

In this chapter, you will learn to:

1. Solve linear programming maximization problems using the simplex method.
2. Solve the minimization problems using the simplex method.

## Maximization By The Simplex Method

In the last chapter, we used the geometrical method to solve linear programming problems, but the geometrical approach will not work for problems that have more than two variables. In real life situations, linear programming problems consist of literally thousands of variables and are solved by computers. We can solve these problems algebraically, but that will not be very efficient. Suppose we were given a problem with, say, 5 variables and 10 constraints. By choosing all combinations of five equations with five unknowns, we could find all the corner points, test them for feasibility, and come up with the solution, if it exists. But the trouble is that even for a problem with so few variables, we will get more than 250 corner points, and testing each point will be very tedious. So we need a method that has a systematic algorithm and can be programmed for a computer. The method has to be efficient enough so we wouldn't have to evaluate the objective function at each corner point. We have just such a method, and it is called the simplex method.

The simplex method was developed during the Second World War by Dr. George Dantzig. His linear programming models helped the Allied forces with transportation and scheduling problems. In 1979, a Soviet scientist named Leonid Khachian developed a method called the ellipsoid algorithm which was supposed to be revolutionary, but as it turned out it is not any better than the simplex method. In 1984, Narendra Karmarkar, a research scientist at AT&T Bell Laboratories developed Karmarkar's algorithm which has been proven to be four times faster than the simplex method for certain problems. But the simplex method still works the best for most problems.

The simplex method uses an approach that is very efficient. It does not compute the value of the objective function at every point, instead, it begins with a corner point of the feasibility region where all the main variables are zero and then systematically moves from corner point to corner point, while improving the value of the objective function at each stage. The process continues until the optimal solution is found.

To learn the simplex method, we try a rather unconventional approach. We first list the algorithm, and then work a problem. We justify the reasoning behind each step during the process. A thorough justification is beyond the scope of this course.

We start out with an example we solved in the last chapter by the graphical method. This will provide us with some insight into the simplex method and at the same time give us the chance to compare a few of the feasible solutions we obtained previously by the graphical method.

But first, we list the algorithm for the simplex method.

### THE SIMPLEX METHOD

1. Set up the problem.

That is, write the objective function and the constraints.

2. Convert the inequalities into equations.

This is done by adding one slack variable for each inequality.

3. Construct the initial simplex tableau.

Write the objective function as the bottom row.

4. The most negative entry in the bottom row identifies a column.
5. Calculate the quotients. The smallest quotient identifies a row. The element in the intersection of the column identified in step 4 and the row identified in this step is identified as the pivot element.

The quotients are computed by dividing the far right column by the identified column in step 4. A quotient that is a zero, or a negative number, or that has a zero in the denominator, is ignored.

6. Perform pivoting to make all other entries in this column zero.

This is done the same way as we did with the Gauss-Jordan method.

7. When there are no more negative entries in the bottom row, we are finished; otherwise, we start again from step 4.

Get the variables using the columns with 1 and 0s. All other variables are zero. The maximum value you are looking for appears in the bottom right hand corner.

And now, (Reference) we solved in (Reference).

### Example 2

#### Problem 1

Niki holds two part-time jobs, Job I and Job II. She never wants to work more than a total of 12 hours a week. She has determined that for every hour she works at Job I, she needs 2 hours of preparation time, and for every hour she works at Job II, she needs one hour of preparation time, and she cannot spend more than 16 hours for preparation. If she makes $40 an hour at Job I, and$30 an hour at Job II, how many hours should she work per week at each job to maximize her income?

## Minimization By The Simplex Method

In this section, we will solve the standard linear programming minimization problems using the simplex method. Once again, we remind the reader that in the standard minimization problems all constraints are of the form ax+bycax+byc size 12{ ital "ax"+ ital "by" >= c} {}. The procedure to solve these problems was developed by Dr. John Von Neuman. It involves solving an associated problem called the dual problem. To every minimization problem there corresponds a dual problem. The solution of the dual problem is used to find the solution of the original problem. The dual problem is really a maximization problem which we already learned to solve in the Section 2. We will first solve the dual problem by the simplex method and then, from the final simplex tableau, we will extract the solution to the original minimization problem.

Before we go any further, however, we first learn to convert a minimization problem into its corresponding maximization problem called its dual.

### Example 3

#### Problem 1

Convert the following minimization problem into its dual.

Minimize Z = 12 x 1 + 16 x 2 Z = 12 x 1 + 16 x 2 size 12{Z="12"x rSub { size 8{1} } +"16"x rSub { size 8{2} } } {}

Subject to: x 1 + 2x 2 40 x 1 + 2x 2 40 size 12{x rSub { size 8{1} } +2x rSub { size 8{2} } >= "40"} {}

x1+x230x1+x230 size 12{x rSub { size 8{1} } +x rSub { size 8{2} } >= "30"} {}
(14)
x10;x20x10;x20 size 12{x rSub { size 8{1} } >= 0;x rSub { size 8{2} } >= 0} {}
(15)

### Example 4

#### Problem 1

Solve graphically both the minimization problem and its dual, the maximization problem.

### Example 5

#### Problem 1

Find the solution to the minimization problem in Example 3 by solving its dual using the simplex method. We rewrite our problem.

Minimize Z = 12 x 1 + 16 x 2 Z = 12 x 1 + 16 x 2 size 12{Z="12"x rSub { size 8{1} } +"16"x rSub { size 8{2} } } {}

Subject to: x1+2x240x1+2x240

x1+x230x1+x230
(20)
x10;x20x10;x20 size 12{x rSub { size 8{1} } >= 0;x rSub { size 8{2} } >= 0} {}
(21)

We now summarize our discussion so far.

### MINIMIZATION BY THE SIMPLEX METHOD

1. Set up the problem.
2. Write a matrix whose rows represent each constraint with the objective function as its bottom row.
3. Write the transpose of this matrix by interchanging the rows and columns.
4. Now write the dual problem associated with the transpose.
5. Solve the dual problem by the simplex method learned in Example 2.
6. The optimal solution is found in the bottom row of the final matrix in the columns corresponding to the slack variables, and the minimum value of the objective function is the same as the maximum value of the dual.

## Content actions

PDF | EPUB (?)

### What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

PDF | EPUB (?)

### What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

#### Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

#### Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

### Reuse / Edit:

Reuse or edit collection (?)

#### Check out and edit

If you have permission to edit this content, using the "Reuse / Edit" action will allow you to check the content out into your Personal Workspace or a shared Workgroup and then make your edits.

#### Derive a copy

If you don't have permission to edit the content, you can still use "Reuse / Edit" to adapt the content by creating a derived copy of it and then editing and publishing the copy.

| Reuse or edit module (?)

#### Check out and edit

If you have permission to edit this content, using the "Reuse / Edit" action will allow you to check the content out into your Personal Workspace or a shared Workgroup and then make your edits.

#### Derive a copy

If you don't have permission to edit the content, you can still use "Reuse / Edit" to adapt the content by creating a derived copy of it and then editing and publishing the copy.