<< Chapter < Page Chapter >> Page >

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 + by c 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 [link] . 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.

Convert the following minimization problem into its dual.

Minimize 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 size 12{x rSub { size 8{1} } +2x rSub { size 8{2} }>= "40"} {}

x 1 + x 2 30 size 12{x rSub { size 8{1} } +x rSub { size 8{2} }>= "30"} {}
x 1 0 ; x 2 0 size 12{x rSub { size 8{1} }>= 0;x rSub { size 8{2} }>= 0} {}

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

A matrix that represents the problem.

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

A transposition of the original matrix.

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

Maximize 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 size 12{y rSub { size 8{1} } +y rSub { size 8{2} }<= "12"} {}

2y 1 + y 2 16 size 12{2y rSub { size 8{1} } +y rSub { size 8{2} }<= "16"} {}
y 1 0 ; y 2 0 size 12{y rSub { size 8{1} }>= 0;y rSub { size 8{2} }>= 0} {}

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

Got questions? Get instant answers now!
Got questions? Get instant answers now!

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

Our minimization problem is as follows.

Minimize 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 size 12{x rSub { size 8{1} } +2x rSub { size 8{2} }>= "40"} {}

x 1 + x 2 30 size 12{x rSub { size 8{1} } +x rSub { size 8{2} }>= "30"} {}
x 1 0 ; x 2 0 size 12{x rSub { size 8{1} }>= 0;x rSub { size 8{2} }>= 0} {}

We now graph the inequalities.

The graph shows that the lines x_1+x_2=30 and x_1+2x_2=40 intersect at the point (20,10). The shaded region represents the area of the graph that meets the required conditions.

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 size 12{Z="40"y rSub { size 8{1} } +"30"y rSub { size 8{2} } } {}

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

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

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

We graph the inequalities.

 Two lines intersecting at the point (4,8) on a graph. The shaded region represents the area of the graph that meets the required conditions.

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 [link] , in [link] . This is also the same problem as [link] in [link] , 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.

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.

Got questions? Get instant answers now!
Got questions? Get instant answers now!

Find the solution to the minimization problem in [link] by solving its dual using the simplex method. We rewrite our problem.

Minimize 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 + 2 x 2 40

x 1 + x 2 30
x 1 0 ; x 2 0 size 12{x rSub { size 8{1} }>= 0;x rSub { size 8{2} }>= 0} {}

The dual is as follows:

Maximize 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 size 12{y rSub { size 8{1} } +y rSub { size 8{2} }<= "12"} {}

2y 1 + y 2 16 size 12{2y rSub { size 8{1} } +y rSub { size 8{2} }<= "16"} {}
y 1 0 ; y 2 0 size 12{y rSub { size 8{1} }>= 0;y rSub { size 8{2} }>= 0} {}

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

The initial simplex tableau is

The initial simplex tableau for the example.

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

The final simplex tableau reads as follows:

The final simplex tableau for the example.

A closer look at this table reveals that the x 1 size 12{x rSub { size 8{1} } } {} and x 2 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).

Got questions? Get instant answers now!
Got questions? Get instant answers now!

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 [link] .
  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.
Got questions? Get instant answers now!

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Applied finite mathematics. OpenStax CNX. Jul 16, 2011 Download for free at http://cnx.org/content/col10613/1.5
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Applied finite mathematics' conversation and receive update notifications?

Ask