Reading: Standard Minimization with the Dual
Using the simplex method directly does not allow us to minimize. If you think about it, the regions for maximization and minimization are "flipped" since the inequalities point in different directions (we use "flipped" loosely here and without explicitly defining it). Intuitively, we might figure that to use the simplex method, we would somehow "flip" the problem at hand. That is, in fact, exactly what takes place. In order to be able to carry out the procedure that will soon follow, we must meet the following requirements for a standard minimization problem.Standard Minimization Problem
Mathematically speaking, in order to use the "flipped" simplex method to solve a linear programming problem, we need the standard minimization problem:- an objective function, and
- one or more constraints of the form,
a1x1 + a2x2 + a3x3 + ... anxn ge V
- All of the anumber represent real-numbered coefficients and
- the xnumber represent the corresponding variables.
- V is a non-negative (0 or larger) real number
Transpose of a Matrix
The transpose of matrix A, denoted AT, is the matrix that switches the rows and columns of matrix A. Example: [latex]\displaystyle{A}={\left[\matrix{{1}&{2}\\{3}&{4}\\{5}&{6}}\right] \gt{A}^{{T}}={\left[\matrix{{1}&{3}&{5}\\{2}&{4}&{6}}\right][/latex] Notice that laying down the first column produces the first row of At and that laying down the second column produces the second row of AT. The mathematics behind this gets even more hideous than that of the standard maximization problem. Though we could formally present the mathematics taking place, it is not intuitive and only leads to a rote, procedural learning experience. We will make use of our technology. Needless to say, we still do have to follow a process in order to perform standard minimization. We will describe the procedure below.Dual Problem for Standard Minimization
In a nutshell, we will reconstruct the minimization problem into a maximization problem by converting it into what we call a Dual Problem. This is just a method that allows us to rewrite the problem and use the Simplex Method, as we have done with maximization problems. Once it's set-up, the rest is fairly simple.- Build a matrix out of the constraints and objective function without slack variables, letting the first column contain coefficients of the first variable, second column the coefficients of the second variable, etc. Let the final column represent the constant for each of the constraints. For the objective function (last row), place a 1 to represent the coefficient of the name of the objective function (e.g. 1P = 2x + 3y).
- Find the transpose of the matrix.
- Rewrite the constraints and objective function using the new matrix – this is called the Dual Problem. Treat each new column as if it represented coefficients of all original variables.
- Build an initial simplex tableau
- Solve by using the Simplex Method
- The solution will appear in the last row of the slack variable columns for x, y, z, ... respectively, and the minimized objective function value will appear in the last row, last column of the final tableau.
Example 1
Minimize: [latex-display]\displaystyle{P}={6}{x}+{5}{y}[/latex-display] Subject to: $latex f(n) = \begin{cases}{x}+{y}\ge{2} \\{2}{x}+{y}\ge{3}\\{x}\ge{0}\\{y}\ge{0} \end{cases} $Solution
We begin by creating the initial matrix. Notice that the final row is of the form 6x + 5y = 1P. We do not rewrite the coefficients with negative values.
The transpose of this matrix is thus,
We write the Dual Problem:
Maximize:
[latex-display]\displaystyle{P}={2}{x}+{3}{y}[/latex-display]
Subject to:
$latex f(n) = \begin{cases}{x}+{2}{y}\le{6} \\{x}+{y}\le{5}\\{x}\ge{0}\\{y}\ge{0} \end{cases} $
Notice that the dual problem has the word "Maximize" and that the inequality signs reverse direction. Justify this to yourself by noting that we have essentially "inverted" the problem, so we must invert from minimize to maximize and from $latex \ge $ to $latex \le $. (We will illustrate this further below.)
Writing the equations with slack variables gives:
x + 2y + s1 = 6
x + y + s2 =5
–2x – 3y + P =0
The initial simplex tableau is:
Using the SIMPLEX program in our calculator, we get:
We notice that the columns from left-to-right are x, y, $latex {s}_{1}$, and $latex {s}_{2}$. We know that$latex {s}_{1}$ corresponds to x and$latex {s}_{2}$ corresponds toy. The last row of the slack variable columns display the results for x andy. In this case, we see that those values are both 1. The corresponding minimized value is 11:
Thus we have that (1,1) minimizes the objective function with an objective output value of 11.
To justify at least some of the process that has taken place, observe that the original objective value with constraints would produce the following graph:
Now, consider a graph of the dual problem:
Interesting! It appears that the feasible region has indeed been inverted. Note, however, that our values for x and y and come from the slack variable columns of the final tableau. The reason for this is not obvious. Then again, the whole process is somewhat mystical! Because it is an obnoxious process to go through, we again leave the in-betweens up to the mathematicians.
We provide one more example:
Example 2
A truck company is hired by a retailer to transport goods from its warehouses in Phoenix, AZ, and Casa Grande, AZ, to its outlets stores in Gilbert, AZ, and Mesa, AZ. The truck company is contracted to dispatch 30 trucks each month to deliver goods. The truck company determines that it will need to send at least 12 of the trucks to the Gilbert location and at least 13 trucks to the Mesa location. At least 15 trucks can come from the Phoenix warehouse and at least 20 trucks can come from the Casa Grande warehouse. The truck company wants to minimize the number of miles placed on its trucks. How many trucks should the send out from each location and to which outlets should they send them?| Phoenix | Casa Grande | |
| Gilbert | 22 mi | 31 mi |
| Mesa | 20 mi | 38 mi |
Solution
We first note that there are four shipping possibilities: Phoenix to Gilbert, Phoenix to Mesa, Casa Grande to Gilbert, and Casa Grande to Mesa. Since we want to determine the number of trucks coming from Phoenix and Casa Grande to each of the other two locations, we let: Pg = # of trucks from Phoenix to Gilbert Pm = # of trucks from Phoenix to Mesa Cg = # of trucks from Casa Grande to Gilbert Cm = # of trucks from Casa Grande to Mesa The constraints rest with the number of trucks that must travel to/from each of the locations. Summarizing by using the table:
These arrows correspond to the sum of the values in each row or column. For example, we know that the total number of trucks going to Gilbert is at least 12. That is
Pg + Cg $latex \ge$ 12
Further,
Pm + Cm $latex \ge$ 13
Pg + Pm $latex \ge$15
Cg + Cm $latex \ge$ 20
Our goal is to minimize total mileage. Since the mileage is provided for one way only, we need to double the distances. That is, the number of times the truck goes from one location to another, multiplied by the miles per roundtrip gives us the total miles traveled for that orientation. That is:
[latex-display]\displaystyle\frac{{\text{miles}}}{{\text{trip}}}\cdot\text{trips}=\text{miles}[/latex-display]
For all trips, Total Mileage =
M = 44Pg + 40Pm + 62Cg + 76Cm
Or,
–44Pg – 40Pm – 62Cg – 76Cm + M = 0
The initial tableau is:
We must now transpose this matrix to get:
Rewriting these gives and incorporating slack variables:
1Pg + 0Pm + 1Cg + 0Cm + s1 = 44
0Pg + 1Pm + 1Cg + 0Cm + s2= 40
1Pg + 0Pm + 0Cg + 1Cm + s3= 62
0Pg + 1Pm + 0Cg + 1Cm + s4= 76
The objective function is M = 12Pg + 13Pm + 15Cg + 20Cm
So,
–12Pg – 13Pm – 15Cg – 20Cm + M = 0
The initial simplex tableau is:
After going through the SIMPLEX program,
Reading Pg, Pm, Cg, and Cm from the columns corresponding to s1, s2, s3, and s4respectively, we have that
Pg = 0
Pm = 15
Cg = 20
Cm = 0
And the minimum mileage would 1,840 miles. Why does it seem to make sense that we would get an answer like this? We see that Phoenix to Mesa and Casa Grande to Gilbert both have shorter distances than the other two.Practice Problems
- Solve each of the following linear programming problems by using the dual problem.
a) Minimize: P = x + y + 2z, subject to
$latex f(n) = \begin{cases}{x}+{2}{y}-{z}\ge{100}\\{-x}-{y}+{10}{z}\ge{30}\\{3}{x}+{4}{y}+{5}{z}\ge{200}\end{cases} $
b) Minimize: .5x + 1.2y + .9z, subject to
$latex f(n) = \begin{cases}{1.1}{x}+{2.1}{y}+{.4z}\ge{9}\\{0.7x}+{0.99}+{z}\ge{12}\\{-x}-{4}{y}+{30}{z}\ge{400}\end{cases} $
2. Manufacturing parts for a technological device can be time-consuming. Suppose that a particular device requires nuts, bolts, plastic washers, and plastic tabs. A nut can be manufactured in 20 seconds, a bolt can be manufactured in 23 seconds, a plastic washer can be manufactured in 10 seconds, and plastic tabs can be manufactured in 12 seconds. It is necessary that there are at least 12,000 nuts and 12,000 bolts. The minimum number of plastic parts that can be produced (due to costs and machinery maintenance) is 14,000. For metal parts (nuts and bolts) this number must be at least 11,000. How many of each item should be produced so that the manufacturing time is minimized.
3. A law firm hopes to hire new individuals, due to unforeseeable growth in the company. It will hire for three different positions: clerk, administrative secretary, and attorney's assistant. The positions pay $25,950, $36,500, and $45,800, respectively, and are part-time, 30 hours . The law firm would like to hire at least 15 new individuals, overall. There must be at least as many clerks as there are administrative secretaries, and at least 7 of these positions must be devoted to attorneys assistants and administrative secretaries. How many of each position should they fill in an effort to minimize cost (assume that benefits are already included and are the same across the three positions)?
- A new city bus schedule is to be created. The following table displays the distance (miles) from station to station for each of four different routes. One route starts at Congress, proceeds to Jefferson St., and returns back to Congress. Another route starts at Congress, proceeds to Washington St., and then returns to Congress. A similar story holds for the two additional routs, originating at Agrinome.
After following through with some research as to the popular routes, the city planners have found that there have always been at least twice as many trips required for the Congress-Jefferson route as the Agrinome-Washington route. It is also determined that at least 45 routes need to originate on Agrinome each day. The number of buses going through Jefferson St. needs to be no less than 60. Additionally, the number of buses originating at Congress should be at least as many as those originating at Agrinome. How many buses should be assigned to each route each day, to minimize the difference between the number of buses starting at Congress and the number of buses starting at Agrinome?Congress Blvd. Agrinome Ave Jefferson St. 4 6 Washington St. 9 7
Licenses & Attributions
CC licensed content, Shared previously
- By the Numbers, Standard Minimization with the Dual. Authored by: Milos Podmanik. License: CC BY: Attribution.
