Simplex Method Minimization Examples

Example: Simplex Method Solve the following problem by the simplex method: Max 12x1 + 18x2 + 10x3 s.t. 2x1 + 3x2 + 4x3 0 x2 - 1.5x3 0 x1, x2, x3 0 Example: Simplex Method Writing the Problem in Tableau Form We can avoid introducing artificial variables to the second and third constraints by multiplying each by -1. Some Simplex Method Examples Example 1: (from class) Maximize: P = 3x+4y subject to: x+y ≤ 4 2x+y ≤ 5 x ≥ 0,y ≥ 0 Our first step is to classify the problem. Clearly, we are going to maximize our objec-tive function, all are variables are nonnegative, and our constraints are written with.

4.2 The Simplex Method: Standard Minimization Problems

Learning Objectives

• Use the Simplex Method to solve standard minimization problems.

Notes

This section is an optional read. This material will not appear on the exam.

We can also use the Simplex Method to solve some minimization problems, but only in very specific circumstances. The simplest case is where we have what looks like a standard maximization problem, but instead we are asked to minimize the objective function.

We notice that minimizing $C$ is the same as maximizing $P=-C$. Thus the solution to the minimization problem can be found by solving the standard maximization problem below with the techniques learned in Section 4.1.

The solution to this example is left as an exercise. The other important class of minimization problems we encounter are called standard minimization problems.

Definition. A standard minimization problem is a linear programming problem in which we seek to minimize an objective function $C=c_1x_1+ldots+c_nx_n$ subject to the constraints$$begin{align}a_{11}x_1 + ldots + a_{1n}x_n & geq b_1& vdotsa_{m1}x_1 + ldots + a_{mn}x_n & geq b_mend{align}$$where all $x_igeq 0$.

Definition. Each maximization problem in linear programming is associated with a counterpart minimization problem, and vice versa. For the purposes of identification, the given problem will be referred to as the primal problem, and the counterpart to this problem is called the dual problem.

Example. Consider the following standard minimization problem.

We first write down the following tableau for the given primal problem:$$begin{array}{cc|c}x & y &hline5 & 1 & 55 & 3 & 10hline4 & 2end{array}$$Note that this is not a typical Simplex tableau. There are no slack variables, and we don't rewrite the objective function for the last row. Next we transpose.$$begin{array}{cc|c}u & v &hline5 & 5 & 41 & 3 & 2hline5 & 10end{array}$$Then we construct the dual problem:

Then we set up the Simplex tableau and proceed as the Section 4.1, using $x$ and $y$ as our slack variables.$$begin{array}{ccccc|c}u & v & x & y & P & text{Constant}hline5 & 5 & 1 & 0 & 0 & 41 & 3 & 0 & 1 & 0 & 2hline-5 & -10 & 0 & 0 & 1 & 0end{array}$$Solving this tableau is left to the reader as an exercise. The final tableau looks like this.$$begin{array}{ccccc|c}u & v & x & y & P & text{Constant}hline1 & 0 & 3/10 & -1/2 & 0 & 1/50 & 1 & -1/10 & 1/2 & 0 & 3/5hline0 & 0 & 1/2 & 5/2 & 1 & 7end{array}$$Interpreting this in the usual manner, the solution of the dual problem is $u=1/5$, $v=3/5$, and $P=7$. The solution to the primal problem appears under the respective slack variables in the last row of the final tableau: $x=1/2$ and $5/2$.

Learning Objectives

In this section, you will learn to solve linear programming minimization problems using the simplex method.

1. Identify and set up a linear program in standard minimization form
2. Formulate a dual problem in standard maximization form
3. Use the simplex method to solve the dual maximization problem
4. Identify the optimal solution to the original minimization problem from the optimal simplex tableau.

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

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 a maximization problem, which we learned to solve in the last section. We first solve the dual problem by the simplex method.

From the final simplex tableau, we then 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 (PageIndex{1})

Convert the following minimization problem into its dual.

[begin{array}{ll}
textbf { Minimize } & mathrm{Z}=12 mathrm{x}_{1}+16 mathrm{x}_{2}
textbf { Subject to: } & mathrm{x}_{1}+2 mathrm{x}_{2} geq 40
& mathrm{x}_{1}+mathrm{x}_2 geq 30
& mathrm{x}_{1} geq 0 ; mathrm{x}_{2} geq 0
end{array} nonumber]

Solution

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

[begin{array}{cc|c}
1 & 2 & 40
1 & 1 & 30
hline 12 & 16 & 0
end{array} nonumber]

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:

[begin{array}{cc|c}
1 & 1 & 12
2 & 1 & 16
hline 40 & 30 & 0
end{array} nonumber]

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

[begin{array}{ll}
textbf { Maximize } & mathrm{Z}=40 mathrm{y}_{1}+30 mathrm{y}_{2}
textbf { Subject to: } & mathrm{y}_{1}+mathrm{y}_{2} leq 12
& 2 mathrm{y}_1+mathrm{y}_2 leq 16
& mathrm{y}_{1} geq 0 ; mathrm{y}_{2} geq 0
end{array} nonumber]

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

Example (PageIndex{2})

Solve graphically both the minimization problem and its dual maximization problem. Turbov evo download.

Linear Programming Simplex Method Minimization

Solution

Our minimization problem is as follows.

Simplex Method Minimization Examples Using

[begin{array}{ll}
textbf { Minimize } & mathrm{Z}=12 mathrm{x}_1+16 mathrm{x}_2
textbf { Subject to: } & mathrm{x}_{1}+2 mathrm{x}_{2} geq 40
& mathrm{x}_{1}+mathrm{x}_{2} geq 30
& mathrm{x}_{1} geq 0 ; mathrm{x}_{2} geq 0
end{array} nonumber]

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 is:

[begin{array}{ll}
textbf { Maximize } & mathrm{Z}=40 mathrm{y}_1+30 mathrm{y}_{2}
textbf { Subject to: } & mathrm{y}_{1}+mathrm{y}_{2} leq 12
& 2 mathrm{y}_1+mathrm{y} 2 leq 16
& mathrm{y}_{1} geq 0 ; mathrm{y}_{2} geq 0
end{array}nonumber]

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 Example (PageIndex{2}) above is the same as Example 3.1.1, in section 3.1. It is also the same problem as Example 4.1.1 in section 4.1, 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; in Example (PageIndex{2}) the minimum and maximum are both 400. This is not a coincident. We state the duality principle.

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.

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 is:

[begin{array}{ll}
textbf { Maximize } & mathrm{Z}=40 mathrm{y}_1+30 mathrm{y}_{2}
textbf { Subject to: } & mathrm{y}_{1}+mathrm{y}_{2} leq 12
& 2 mathrm{y}_1+mathrm{y} 2 leq 16
& mathrm{y}_{1} geq 0 ; mathrm{y}_{2} geq 0
end{array}nonumber]

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 Example (PageIndex{2}) above is the same as Example 3.1.1, in section 3.1. It is also the same problem as Example 4.1.1 in section 4.1, 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; in Example (PageIndex{2}) the minimum and maximum are both 400. This is not a coincident. We state the duality principle.

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.

Example (PageIndex{3})

Find the solution to the minimization problem in Example (PageIndex{1}) by solving its dual using the simplex method. We rewrite our problem.

[begin{array}{ll}
textbf { Minimize } & mathrm{Z}=12 mathrm{x}_{1}+16 mathrm{x}_{2}
textbf { Subject to: } & mathrm{x}_{1}+2 mathrm{x}_{2} geq 40
& mathrm{x}_{1}+mathrm{x}_{2} geq 30
& mathrm{x}_{1} geq 0 ; mathrm{x}_{2} geq 0
end{array} nonumber]

Solution

[begin{array}{ll}
textbf { Maximize } & mathrm{Z}=40 mathrm{y}_{1}+30 mathrm{y}_{2}
textbf { Subject to: } & mathrm{y}_{1}+mathrm{y}_{2} leq 12
& 2 mathrm{y}_{1}+mathrm{y}_{2} leq 16
& mathrm{y}_{1} geq 0 ; mathrm{y}_{2} geq 0
end{array} nonumber]

Pokemon omega ruby decrypted rom fr. Recall that we solved the above problem by the simplex method in Example 4.1.1, section 4.1. Therefore, we only show the initial and final simplex tableau.

The initial simplex tableau is

[begin{array}{ccccc|c}
mathrm{y}_1 & mathrm{y}_2 & mathrm{x}_{1} & mathrm{x}_{2} & mathrm{Z} & mathrm{C}
1 & 1 & 1 & 0 & 0 & 12
2 & 1 & 0 & 1 & 0 & 16
hline-40 & -30 & 0 & 0 & 1 & 0
end{array}nonumber]

Observe an important change. Here our main variables are (mathrm{y}_1) and (mathrm{y}_2) and the slack variables are (mathrm{x}_1 and mathrm{x}_2).

The final simplex tableau reads as follows:

[begin{array}{ccccc|c}
mathrm{y}_1 & mathrm{y}_2 & mathrm{x}_{1} & mathrm{x}_{2} & mathrm{Z} &
0 & 1 & 2 & -1 & 0 & 8
1 & 0 & -1 & 1 & 0 & 4
hline 0 & 0 & 20 & 10 & 1 & 400
end{array} nonumber]

A closer look at this table reveals that the (mathrm{x}_1) and (mathrm{x}_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.

[begin{array}{ccccc|c}
mathrm{y}_1 & mathrm{y}_2 & mathrm{x}_{1} & mathrm{x}_{2} & mathrm{Z} &
0 & 1 & 2 & -1 & 0 & 8
1 & 0 & -1 & 1 & 0 & 4
hline 0 & 0 & 20 & 10 & 1 & 400
& & uparrow & uparrow & & uparrow
end{array} nonumber]

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.

Gta iv 1.0.7.0 crack. 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 section 4.1.
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.