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. Simplex Method  Exercises So the minimum is attained for ariablev x 5 and x 5 exits the basis. The pivot row is thus the row 2 of the tableau and the pivot element is that at the intersection of row 2 and column 1. In order to get the new tableau corresponding to the new basis: B= A 4 A 1 = 1 4 0 2. 5.1 The Simplex Algorithm: The path around the feasible region is shown in the gure. Each exchange of a basic and nonbasic variable moves us along an edge of the polygon in a direction that increases the value of the objective function.78 5.2 Unbounded Linear Program: The existence of a negative column a j in the simplex tableau for entering.

INDEX OF TERMS 

 
A STANDARD MAXIMIZING PROBLEM is a linear programming problem which satisfies all of the following 4 CONDITIONS (Rolf, pg.263) :  


Reference :An example of how to apply the following procedure to a nonstandard problem is available, with abundant comments and crossreferences.
Reference : Many EXERCIZES are available for each step of this method.


Convert all constraints to equations with slack variables, and then write the problem as a tableau with some negative right sides, with or without a ZCOLUMN. 


FINDING THE PIVOT (steps
Locate the row containing the most negative righthand number. This row will be called the INDICATOR ROW. If no righthand number is negative, then your tableau is STANDARD. 
INDICTORS will consist of all numbers in the row found in NS3, except the rightmost number; the PIVOT COLUMN will contain the most negative of these indicators. If no indicator is negative, then there is no pivot column, and the problem is unsolvable. 
Form RATIOS or QUOTIENTS for all (nonobjective) rows : for each row, divide the rightmost number by the number in the pivot column. 
The PIVOT will be in the ROW with smallest nonnegative ratio. Note that 0(+1) and 0(1) are both numerically zero, but in calculating RATIOS, consider 0(+1) as positive (OK), and 0(1) as negative (not OK). 
Perform a pivot transformation on the above pivot (Rolf, Pg 98). Check out the PIVOT ENGINE to speed pactice. 
If all rightmost (nonobjective row) entries are nonnegative, then phase I is ended. PHASE II now consists of applying steps 39 of the standard maximizing procedure to the new tableau obtained in step NS7 above. Note:PHASE II is described as step #7 on Page 329 of our text, Rolf. 
Otherwise, if some rightmost (nonobjective row) entry is negative, apply steps NS3 through NS9 to the new tableau obtained in NS7. 
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,
a_{1}x_{1} + a_{2}x_{2} + a_{3}x_{3} + … a_{n}x_{n} ge V All of the a_{number} represent realnumbered coefficients and
 the x_{number} represent the corresponding variables.
 V is a nonnegative (0 or larger) real number
Notice that the only difference here is that the inequality is greaterthanorequalto.
There is one very important term that we need to consider: the transpose of a matrix.
Transpose of a Matrix
The transpose of matrix A, denoted A^{T}, 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]}[/latex] [latex]{A}^{{T}}={left[matrix{{1}&{3}&{5}{2}&{4}&{6}}right]}[/latex]
Notice that laying down the first column produces the first row of A^{t} and that laying down the second column produces the second row of A^{T}.
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.
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 setup, 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 column and the minimized objective function value will appear in the last row, last column of the final tableau.
Example 1
Minimize:
[latex]displaystyle{P}={6}{x1}+{5}{x2}[/latex]
Subject to:
[latex]f(n) = begin{cases}{x1}+{x2}ge{2}{2}{x1}+{x2}ge{3}{x1}ge{0}{x2}ge{0} end{cases} [/latex]
Solution
We begin by creating the initial matrix.
Notice that the final row is of the form
6x1 + 5x2 = 1P. We do not rewrite the coefficients with negative values.
The transpose of this matrix is thus,
We write the Dual Problem: (It is best to use different variables in the Dual)
Maximize:
[latex]displaystyle{P}={2}{y1}+{3}{y2}[/latex]
Subject to:
[latex]f(n) = begin{cases}{y1}+{2}{y2}le{6} {y1}+{y2}le{5}{y1}ge{0}{y2}ge{0} end{cases} [/latex]
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 [/latex] to [latex]le [/latex]. (We will illustrate this further below.)
Writing the equations with slack variables gives:
y1 + 2y2 + x_{1} = 6
y1 + y2 + x_{2} =5
–2y1 – 3y2 + P =0
The initial simplex tableau is:
Solve using simplex Method:
[latex]displaystyle{left[matrix{{y1}&{y2}&{x1}&{x2}&{P}{1/2}&{1}&{1/2}&{0}&{0}{ }&{3}{1/2}&{0}&{1/2}&{1}&{0}{ }&{2}{1/2}&{0}&{3/2}&{0}&{1}{ }&{9}}right]}[/latex]
[latex]displaystyle{left[matrix{{y1}&{y2}&{x1}&{x2}&{P}{0}&{1}&{1}&{1}&{0}{ }&{1}{1}&{0}&{1}&{2}&{0}{ }&{4}{0}&{0}&{1}&{1}&{1}{ }&{11}}right]}[/latex]
REMEMBER: LOOK AT THE BOTTOM OF THE X1 AND X2 COLUMNS TO GET THEIR VALUES.
x1=1, x2=1 and C=P=11.
{edited by Kevin Pinegar}
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 inbetweens 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:
x_{1} = # of trucks from Phoenix to Gilbert
x_{2} = # of trucks from Phoenix to Mesa
x_{3} = # of trucks from Casa Grande to Gilbert
x_{4} = # 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
x_{1} + x_{3} [latex]ge[/latex] 12
Further,
x_{2} + x_{4 }[latex]ge[/latex] 13
x_{1} + x_{2} [latex]ge[/latex]15
x_{3} + x_{4} [latex]ge[/latex] 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]displaystylefrac{{text{miles}}}{{text{trip}}}cdottext{trips}=text{miles}[/latex]
For all trips, Total Mileage = M
Minimize: M = 44x_{1} + 40x_{2} + 62x_{3} + 76x_{4}
Subject To:
x_{1} + x_{3} [latex]ge[/latex] 12
x_{2} + x_{4 }[latex]ge[/latex] 13
x_{1} + x_{2} [latex]ge[/latex]15
Omnisphere keygen download free. x_{3} + x_{4} [latex]ge[/latex] 20
x_{1} ,x_{2} ,x_{3} ,x_{4} [latex]ge[/latex] 0
The initial coefficient matrix is:
We must now transpose this matrix to get:
The Dual Problem is,
Maximize: N = 12y_{1} + 13y_{2} + 15y_{3} + 20y_{4}
Subject To:
y_{1}+ y_{3}[latex]le[/latex] 44
y_{2} + y_{3} [latex]le[/latex] 40
y_{1} + y_{4} [latex]le[/latex] 62
y_{2}+ y_{4}[latex]le[/latex] 76
y_{1} ,y_{2} ,y_{3} ,y_{4 }[latex]ge[/latex] 0
Rewriting the conctraints and incorporating slack variables gives;
1y_{1} + 0y_{2} + 1y_{3}+ 0y_{4} + x_{1 }= 44
0y_{1} + 1y_{2} + 1y_{3} + 0y_{4} + x_{2}= 40
1y_{1} + 0y_{2} + 0y_{3} + 1y_{4} + x_{3}= 62
0y_{1} + 1y_{2} + 0y_{3} + 1y_{4} + x_{4}= 76
The rewritten objective function is
–12y_{1} – 13y_{2} – 15y_{3} – 20y_{4} + N = 0
The initial simplex tableau is:
After going through the SIMPLEX method you should get;
[latex]displaystyle{left[matrix{{y1}&{y2}&{y3}&{y4}&{x1}&{x2}&{x3}&{x4}&{N}{1}&{0}&{1}&{0}&{1}&{0}&{0}&{0}&{0}{ }&{44}{0}&{1}&{1}&{0}&{0}&{1}&{0}&{0}&{0}{ }&{40}{1}&{0}&{0}&{1}&{0}&{0}&{1}&{0}&{0}{ }&{62}{1}&{1}&{0}&{0}&{0}&{0}&{1}&{1}&{0}{ }&{14}{8}&{13}&{15}&{0}&{0}&{0}&{20}&{0}&{1}{ }&{1240}}right]}[/latex]
[latex]displaystyle{left[matrix{{y1}&{y2}&{y3}&{y4}&{x1}&{x2}&{x3}&{x4}&{M}{1}&{1}&{0}&{0}&{1}&{1}&{0}&{0}&{0}{ }&{4}{0}&{1}&{1}&{0}&{0}&{1}&{0}&{0}&{0}{ }&{40}{1}&{0}&{0}&{1}&{0}&{0}&{1}&{0}&{0}{ }&{62}{1}&{1}&{0}&{0}&{0}&{0}&{1}&{1}&{0}{ }&{14}{8}&{2}&{0}&{0}&{0}&{15}&{20}&{0}&{1}{ }&{1840}}right]}[/latex]
Reading the bottom row we get,
x1 = 0, x2 = 15, x3= 20, x4 = 0
And the minimum mileage would M=N=1,840 miles.
Simplex Method Optimization Example
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.