# Connexions

You are here: Home » Content » 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 module is included inLens: Community College Open Textbook Collaborative
By: CC Open Textbook CollaborativeAs a part of collection: "Applied Finite Mathematics"

"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 module is included inLens: Bookshare's Lens
By: Bookshare - A Benetech InitiativeAs a part of collection: "Applied Finite Mathematics"

"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 module is included inLens: Connexions Featured Content
By: ConnexionsAs a part of collection: "Applied Finite Mathematics"

"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.

# 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?

##### Solution

In solving this problem, we will follow the algorithm listed above.

1. Set up the problem. That is, write the objective function and the constraints.

Since the simplex method is used for problems that consist of many variables, it is not practical to use the variables xx size 12{x} {}, yy size 12{y} {}, zz size 12{z} {} etc. We use the symbols x1x1 size 12{x rSub { size 8{1} } } {}, x2x2 size 12{x rSub { size 8{2} } } {}, x3x3 size 12{x rSub { size 8{3} } } {}, and so on.

Let x1=The number of hours per week Niki will work at Job Ix1=The number of hours per week Niki will work at Job I size 12{x rSub { size 8{1} } ="The number of hours per week Niki will work at Job I"} {}.

and x2=The number of hours per week Niki will work at Job IIx2=The number of hours per week Niki will work at Job II size 12{x rSub { size 8{2} } ="The number of hours per week Niki will work at Job II"} {}.

It is customary to choose the variable that is to be maximized as ZZ size 12{Z} {}.

The problem is formulated the same way as we did in the (Reference).

Maximize Z = 40 x 1 + 30 x 2 Z = 40 x 1 + 30 x 2 size 12{Z="40"x rSub { size 8{1} } +"30"x rSub { size 8{2} } } {}

Subject to: x 1 + x 2 12 x 1 + x 2 12 size 12{x rSub { size 8{1} } +x rSub { size 8{2} } <≤ "12"} {}

2x1+x2162x1+x216 size 12{2x rSub { size 8{1} } +x rSub { size 8{2} } <≤ "16"} {}
(1)
x1;  x20x1;  x20 size 12{x rSub { size 8{1} } > ≥ 0;x rSub { size 8{2} } > ≥ 0} {}
(2)
2. Convert the inequalities into equations. This is done by adding one slack variable for each inequality.

For example to convert the inequality x1+x212x1+x212 size 12{x rSub { size 8{1} } +x rSub { size 8{2} } <≤ "12"} {} into an equation, we add a non-negative variable y1y1 size 12{y rSub { size 8{1} } } {}, and we get

x1+x2+y1=12x1+x2+y1=12 size 12{x rSub { size 8{1} } +x rSub { size 8{2} } +y rSub { size 8{1} } ="12"} {}
(3)

Here the variable y1y1 size 12{y rSub { size 8{1} } } {} picks up the slack, and it represents the amount by which x1+x2x1+x2 size 12{x rSub { size 8{1} } +x rSub { size 8{2} } } {} falls short of 12. In this problem, if Niki works fewer that 12 hours, say 10, then y1y1 size 12{y rSub { size 8{1} } } {} is 2. Later when we read off the final solution from the simplex table, the values of the slack variables will identify the unused amounts.

We can even rewrite the objective function Z=40x1+30x2Z=40x1+30x2 size 12{Z="40"x rSub { size 8{1} } + "30"x rSub { size 8{2} } } {} as -40x1-30x2+Z=0-40x1-30x2+Z=0 size 12{ - "40"x rSub { size 8{1} } - "30"x rSub { size 8{2} } +Z=0} {}.

Objective function: -40x1-30x2+Z=0-40x1-30x2+Z=0 size 12{ - "40"x rSub { size 8{1} } - "30"x rSub { size 8{2} } +Z=0} {}

Subject to constraints: x1+x2+y1=12x1+x2+y1=12 size 12{x rSub { size 8{1} } +x rSub { size 8{2} } +y rSub { size 8{1} } ="12"} {}

2x1+x2+y2=162x1+x2+y2=16 size 12{2x rSub { size 8{1} } +x rSub { size 8{2} } +y rSub { size 8{2} } ="16"} {}
(4)
x1;  x20x1;  x20 size 12{x rSub { size 8{1} } > ≥ 0;x rSub { size 8{2} } > ≥ 0} {}
(5)
3. Construct the initial simplex tableau. Write the objective function as the bottom row.

Now that the inequalities are converted into equations, we can represent the problem into an augmented matrix called the initial simplex tableau as follows.

Here the vertical line separates the left hand side of the equations from the right side. The horizontal line separates the constraints from the objective function. The right side of the equation is represented by the column CC size 12{C} {}.

The reader needs to observe that the last four columns of this matrix look like the final matrix for the solution of a system of equations. If we arbitrarily choose x1=0x1=0 size 12{x rSub { size 8{1} } =0} {} and x2=0x2=0 size 12{x rSub { size 8{2} } =0} {}, we get

y1y2Z|C100|12010|16001|0y1y2Z|C100|12010|16001|0 size 12{ left [ matrix { y rSub { size 8{1} } {} # y rSub { size 8{2} } {} # Z {} # \lline {} # C {} ## 1 {} # 0 {} # 0 {} # \lline {} # "12" {} ## 0 {} # 1 {} # 0 {} # \lline {} # "16" {} ## 0 {} # 0 {} # 1 {} # \lline {} # 0{} } right ]} {}
(6)

y1=12y1=12 size 12{y rSub { size 8{1} } ="12"} {}
(7)
y2=16y2=16 size 12{y rSub { size 8{2} } ="16"} {}
(8)
Z=0Z=0 size 12{Z=0} {}
(9)

The solution obtained by arbitrarily assigning values to some variables and then solving for the remaining variables is called the basic solution associated with the tableau. So the above solution is the basic solution associated with the initial simplex tableau. We can label the basic solution variable in the right of the last column as shown in the table below.

4. The most negative entry in the bottom row identifies a column.

The most negative entry in the bottom row is –40, therefore the column 1 is identified.

###### Problem 2

Why do we choose the most negative entry in the bottom row?

###### Solution

The most negative entry in the bottom row represents the largest coefficient in the objective function – the coefficient whose entry will increase the value of the objective function the quickest.

The simplex method begins at a corner point where all the main variables, the variables that have symbols such as x1x1 size 12{x rSub { size 8{1} } } {}, x2x2 size 12{x rSub { size 8{2} } } {}, x3x3 size 12{x rSub { size 8{3} } } {} etc., are zero. It then moves from a corner point to the adjacent corner point always increasing the value of the objective function. In the case of the objective function Z=40x1+30x2Z=40x1+30x2 size 12{Z="40"x rSub { size 8{1} } +"30"x rSub { size 8{2} } } {}, it will make more sense to increase the value of x1x1 size 12{x rSub { size 8{1} } } {} rather than x2x2 size 12{x rSub { size 8{2} } } {}. The variable x1x1 size 12{x rSub { size 8{1} } } {} represents the number of hours per week Niki works at Job I. Since Job I pays $40 per hour as opposed to Job II which pays only$30, the variable x1x1 size 12{x rSub { size 8{1} } } {} will increase the objective function by $40 for a unit of increase in the variable x1x1 size 12{x rSub { size 8{1} } } {}. 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. As mentioned in the algorithm, in order to calculate the quotient, we divide the entries in the far right column by the entries in column 1, excluding the entry in the bottom row. The smallest of the two quotients, 12 and 8, is 8. Therefore row 2 is identified. The intersection of column 1 and row 2 is the entry 2, which has been highlighted. This is our pivot element. ###### Problem 3 Why do we find quotients, and why does the smallest quotient identify a row? ###### Solution When we choose the most negative entry in the bottom row, we are trying to increase the value of the objective function by bringing in the variable x1x1 size 12{x rSub { size 8{1} } } {}. But we cannot choose any value for x1x1 size 12{x rSub { size 8{1} } } {}. Can we let x1=100x1=100 size 12{x rSub { size 8{1} } ="100"} {}? Definitely not! That is because Niki never wants to work for more than 12 hours at both jobs combined. In other words, x1+x212x1+x212 size 12{x rSub { size 8{1} } +x rSub { size 8{2} } <= "12"} {}. Now can we let x1=12x1=12 size 12{x rSub { size 8{1} } ="12"} {}? Again, the answer is no because the preparation time for Job I is two times the time spent on the job. Since Niki never wants to spend more than 16 hours for preparation, the maximum time she can work is 16÷2=816÷2=8 size 12{"16" div 2=8} {}. Now you see the purpose of computing the quotients. ###### Problem 4 Why do we identify the pivot element? ###### Solution As we have mentioned earlier, the simplex method begins with a corner point and then moves to the next corner point always improving the value of the objective function. The value of the objective function is improved by changing the number of units of the variables. We may add the number of units of one variable, while throwing away the units of another. Pivoting allows us to do just that. The variable whose units are being added is called the entering variable, and the variable whose units are being replaced is called the departing variable. The entering variable in the above table is x1x1 size 12{x rSub { size 8{1} } } {}, and it was identified by the most negative entry in the bottom row. The departing variable y2y2 size 12{y rSub { size 8{2} } } {} was identified by the lowest of all quotients. 6. Perform pivoting to make all other entries in this column zero. In (Reference), we used pivoting to obtain the row echelon form of an augmented matrix. Pivoting is a process of obtaining a 1 in the location of the pivot element, and then making all other entries zeros in that column. So now our job is to make our pivot element a 1 by dividing the entire second row by 2. The result follows. To obtain a zero in the entry first above the pivot element, we multiply the second row by –1 and add it to row 1. We get To obtain a zero in the element below the pivot, we multiply the second row by 40 and add it to the last row. We now determine the basic solution associated with this tableau. By arbitrarily choosing x2=0x2=0 size 12{x rSub { size 8{2} } =0} {} and y2=0y2=0 size 12{y rSub { size 8{2} } =0} {}, we obtain x1=8x1=8 size 12{x rSub { size 8{1} } =8} {}, y1=4y1=4 size 12{y rSub { size 8{1} } =4} {}, and z=320z=320 size 12{z="320"} {}. If we write the augmented matrix, whose left side is a matrix with columns that have one 1 and all other entries zeros, we get the following matrix stating the same thing. x1y1ZC01041008001320x1y1ZC01041008001320 size 12{ left [ matrix { x rSub { size 8{1} } {} # y rSub { size 8{1} } {} # Z {} # \lline {} # C {} ## 0 {} # 1 {} # 0 {} # \lline {} # 4 {} ## 1 {} # 0 {} # 0 {} # \lline {} # 8 {} ## 0 {} # 0 {} # 1 {} # \lline {} # "320"{} } right ]} {} (10) We can restate the solution associated with this matrix as x1=8x1=8 size 12{x rSub { size 8{1} } =8} {}, x2=0x2=0 size 12{x rSub { size 8{2} } =0} {}, y1=4y1=4 size 12{y rSub { size 8{1} } =4} {}, y2=0y2=0 size 12{y rSub { size 8{2} } =0} {} and z=320z=320 size 12{z="320"} {}. At this stage of the game, it reads that if Niki works 8 hours at Job I, and no hours at Job II, her profit ZZ size 12{Z} {} will be$320. Recall from (Reference) in (Reference) that (8, 0) was one of our corner points. Here y1=4y1=4 size 12{y rSub { size 8{1} } =4} {} and y2=0y2=0 size 12{y rSub { size 8{2} } =0} {} mean that she will be left with 4 hours of working time and no preparation time.

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

Since there is still a negative entry, –10 , in the bottom row, we need to begin, again, from step 4. This time we will not repeat the details of every step, instead, we will identify the column and row that give us the pivot element, and highlight the pivot element. The result is as follows.

We make the pivot element 1 by multiplying row 1 by 2, and we get

Now to make all other entries as zeros in this column, we first multiply row 1 by 1/21/2 size 12{ - 1/2} {} and add it to row 2, and then multiply row 1 by 10 and add it to the bottom row.

We no longer have negative entries in the bottom row, therefore we are finished.

###### Problem 5

Why are we finished when there are no negative entries in the bottom row?

###### Solution

The answer lies in the bottom row. The bottom row corresponds to the following equation.

0x1+0x2+20y1+10y2+Z=400    or0x1+0x2+20y1+10y2+Z=400 size 12{0x rSub { size 8{1} } +0x rSub { size 8{2} } +"20"y rSub { size 8{1} } +"10"y rSub { size 8{2} } +Z="400"} {}    or
(11)
Z=40020y110y2Z=40020y110y2 size 12{Z="400" - "20"y rSub { size 8{1} } - "10"y rSub { size 8{2} } } {}
(12)

Since all variables are non-negative, the highest value ZZ size 12{Z} {} can ever achieve is 400, and that will happen only when y1y1 size 12{y rSub { size 8{1} } } {} and y2y2 size 12{y rSub { size 8{2} } } {} are zero.

We now read off our answers, that is, we determine the basic solution associated with the final simplex tableau. Again, we look at the columns that have a 1 and all other entries zeros. Since the columns labeled y1y1 size 12{y rSub { size 8{1} } } {} and y2y2 size 12{y rSub { size 8{2} } } {} are not such columns, we arbitrarily choose y1=0y1=0 size 12{y rSub { size 8{1} } =0} {}, and y2=0y2=0 size 12{y rSub { size 8{2} } =0} {}, and we get

x1x2ZC01081004001400x1x2ZC01081004001400 size 12{ left [ matrix { x rSub { size 8{1} } {} # x rSub { size 8{2} } {} # Z {} # \lline {} # C {} ## 0 {} # 1 {} # 0 {} # \lline {} # 8 {} ## 1 {} # 0 {} # 0 {} # \lline {} # 4 {} ## 0 {} # 0 {} # 1 {} # \lline {} # "400"{} } right ]} {}
(13)

The matrix reads x1=4x1=4 size 12{x rSub { size 8{1} } =4} {}, x2=8x2=8 size 12{x rSub { size 8{2} } =8} {} and z=400z=400 size 12{z="400"} {}.

The final solution says that if Niki works 4 hours at Job I and 8 hours at Job II, she will maximize her income to \$400. Since both slack variables are zero, it means that she would have used up all the working time, as well as the preparation time, and none will be left.

## 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)
##### Solution

To achieve our goal, we first express our problem as the following matrix.

Observe that this table looks like an initial simplex tableau without the slack variables. Next, we write a matrix whose columns are the rows of this matrix, and the rows are the columns. Such a matrix is called a transpose of the original matrix. We get

The following maximization problem associated with the above matrix is called its dual.

Maximize Z = 40 y 1 + 30 y 2 Z = 40 y 1 + 30 y 2 size 12{Z="40"y rSub { size 8{1} } +"30"y rSub { size 8{2} } } {}

Subject to: y 1 + y 2 12 y 1 + y 2 12 size 12{y rSub { size 8{1} } +y rSub { size 8{2} } <= "12"} {}

2y1+y2162y1+y216 size 12{2y rSub { size 8{1} } +y rSub { size 8{2} } <= "16"} {}
(16)
y10;y20y10;y20 size 12{y rSub { size 8{1} } >= 0;y rSub { size 8{2} } >= 0} {}
(17)

We have chosen the variables as y's, instead of x's, to distinguish the two problems.

### Example 4

#### Problem 1

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

##### Solution

Our minimization problem is as follows.

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

Subject to: x1+2x240x1+2x240 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"} {}
(18)
x10;x20x10;x20 size 12{x rSub { size 8{1} } >= 0;x rSub { size 8{2} } >= 0} {}
(19)

We now graph the inequalities.

We have plotted the graph, shaded the feasibility region, and labeled the corner points. The corner point (20, 10) gives the lowest value for the objective function and that value is 400.

Now its dual.

Maximize Z = 40 y 1 + 30 y 2 Z = 40 y 1 + 30 y 2 size 12{Z="40"y rSub { size 8{1} } +"30"y rSub { size 8{2} } } {}

Subject to: y 1 + y 2 12 y 1 + y 2 12 size 12{y rSub { size 8{1} } +y rSub { size 8{2} } <= "12"} {}

2y1+y2162y1+y216 size 12{2y rSub { size 8{1} } +y rSub { size 8{2} } <= "16"} {}

y10;y20y10;y20 size 12{y rSub { size 8{1} } >= 0;y rSub { size 8{2} } >= 0} {}

We graph the inequalities.

Again, we have plotted the graph, shaded the feasibility region, and labeled the corner points. The corner point (4, 8) gives the highest value for the objective function, with a value of 400.

The reader may recognize that this problem is the same as (Reference), in (Reference). This is also the same problem as Section 2 in Example 2, where we solved it by the simplex method.

We observe that the minimum value of the minimization problem is the same as the maximum value of the maximization problem; they are both 400. This is not a coincident. We state the duality principle.

Definition 1: The Duality Principle:
The objective function of the minimization problem reaches its minimum if and only if the objective function of its dual reaches its maximum. And when they do, they are equal.

Our next goal is to extract the solution for our minimization problem from the corresponding dual. To do this, we solve the dual by the simplex method.

### 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)
##### Solution

The dual is as follows:

Maximize Z = 40 y 1 + 30 y 2 Z = 40 y 1 + 30 y 2 size 12{Z="40"y rSub { size 8{1} } +"30"y rSub { size 8{2} } } {}

Subject to: y 1 + y 2 12 y 1 + y 2 12 size 12{y rSub { size 8{1} } +y rSub { size 8{2} } <= "12"} {}

2y1+y2162y1+y216 size 12{2y rSub { size 8{1} } +y rSub { size 8{2} } <= "16"} {}
(22)
y10;y20y10;y20 size 12{y rSub { size 8{1} } >= 0;y rSub { size 8{2} } >= 0} {}
(23)

Once again, we remind the reader that we solved the above problem by the simplex method in Section 2, in Example 2. Therefore, we will only show the initial and final simplex tableau.

The initial simplex tableau is

Observe an important change. Here our main variables are y1y1 size 12{y rSub { size 8{1} } } {} and y2y2 size 12{y rSub { size 8{2} } } {} and the slack variables are x1x1 size 12{x rSub { size 8{1} } } {} and x2x2 size 12{x rSub { size 8{2} } } {}.

The final simplex tableau reads as follows:

A closer look at this table reveals that the x1x1 size 12{x rSub { size 8{1} } } {} and x2x2 size 12{x rSub { size 8{2} } } {} values along with the minimum value for the minimization problem can be obtained from the last row of the final tableau. We have highlighted these values by the arrows.

We restate the solution as follows:

The minimization problem has a minimum value of 400 at the corner point (20, 10).

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.

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