# 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 non-basic 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.

 a Simplex
SIMPLEX METHOD
APPLIED TO MINIMIZING
and NON-STANDARD PROBLEMS
INDEX
OF
TERMS
 PIVOT Constraint Objective Function Simplex Tableau Standard Maximizing Problem Hopping phase I Objective row Ratios (Quotients) Identity Sub-Matrix (ISM) Indicator Z-column basic solution Final Tableau pivoting,pivot operation
Definitions
 A linear programming problem (or linear program) is a set of (linear) inequalities (with a solution set S) and a (linear) function (often cost or profit) whose value (within S) is to be maximized or minimized.
A STANDARD MAXIMIZING PROBLEM is a linear programming problem
which satisfies all of the following 4 CONDITIONS (Rolf, pg.263) :
 [C1] The objective function is to be maximized. [C2] All variables are non-negative. [C3] All inequalities are of the type. [C4] All right hand constants are non-negative.
 A NON-STANDARD PROBLEM is simply a problem which is not standard, and hence fails to satisfy at least one of [C1] through [C4] above. In our text, [C2] is always true, which simplifies discussions.

Reference :An example of how to apply the following procedure to a non-standard problem is available, with abundant comments and cross-references.

Reference : Many EXERCIZES are available for each step of this method.

 Step NS-1
 Convert your problem into one satisfying conditions C1,C2, and C3 described above. How to do this is explained in Rolf 8th edition (pg 318-319).
 see example of this step? Step NS-2
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 Z-COLUMN.
Strategy
 The basic solution for a tableau with some negative right sides is a point like A or B in the figure above : it will not be a corner of the RED shaded solution set, but rather will be an intersection of extended boundaries of that set. Our first task will be to locate a corner point of the actual solution set : this task might be called PHASE I and is described here : it differs from the procedure for a standard problem only in STEPS NS-1 and NS-3. After locating some corner of the solution set (shaded above), we must set out to locate the BEST corner : this second and final stage of the solution is called PHASE II, and is identical to the procedure for a standard problem.
Note
 PHASE I, as described in Rolf 8th edition (Step 5, Pg 329), allows the freedom to choose any number as pivot. On tests, you must follow the more restrictive PHASE I procedure given below, not the unrestricted procedure in Rolf.

FINDING THE PIVOT (steps NS-3 through NS-6)

 Step NS-3
Locate the row containing the most negative right-hand number. This row will be called the INDICATOR ROW. If no right-hand number is negative, then your tableau is STANDARD.
 Step NS-4
INDICTORS will consist of all numbers in the row found in NS-3, except the right-most 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.
 Step NS-5
Form RATIOS or QUOTIENTS for all (non-objective) rows : for each row, divide the right-most number by the number in the pivot column.
 Step NS-6
The PIVOT will be in the ROW with smallest non-negative 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).
 Step NS-7
Perform a pivot transformation on the above pivot (Rolf, Pg 98). Check out the PIVOT ENGINE to speed pactice.
 Step NS-8
If all right-most (non-objective row) entries are non-negative, then phase I is ended. PHASE II now consists of applying steps 3-9 of the standard maximizing procedure to the new tableau obtained in step NS-7 above. Note:PHASE II is described as step #7 on Page 329 of our text, Rolf.
 Step NS-9
Otherwise, if some right-most (non-objective row) entry is negative, apply steps NS-3 through NS-9 to the new tableau obtained in NS-7.

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

Notice that the only difference here is that the inequality is greater-than-or-equal-to.

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 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]}[/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 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.

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.

1. 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).
2. Find the transpose of the matrix.
3. 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.
4. Build an initial simplex tableau
5. Solve by using the Simplex Method
6. 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 + x1 = 6

y1 + y2 + x2 =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 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:

x1 = # of trucks from Phoenix to Gilbert

x2 = # of trucks from Phoenix to Mesa

x3 = # of trucks from Casa Grande to Gilbert

x4 = # 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
x1 + x3 [latex]ge[/latex] 12

Further,

x2 + x4 [latex]ge[/latex] 13

x1 + x2 [latex]ge[/latex]15

x3 + x4 [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 = 44x1 + 40x2 + 62x3 + 76x4

Subject To:

x1 + x3 [latex]ge[/latex] 12

x2 + x4 [latex]ge[/latex] 13

x1 + x2 [latex]ge[/latex]15

x1 ,x2 ,x3 ,x4 [latex]ge[/latex] 0

The initial coefficient matrix is:

We must now transpose this matrix to get:

The Dual Problem is,

Maximize: N = 12y1 + 13y2 + 15y3 + 20y4

Subject To:

y1+ y3[latex]le[/latex] 44

y2 + y3 [latex]le[/latex] 40

y1 + y4 [latex]le[/latex] 62

y2+ y4[latex]le[/latex] 76

y1 ,y2 ,y3 ,y4 [latex]ge[/latex] 0

Rewriting the conctraints and incorporating slack variables gives;

1y1 + 0y2 + 1y3+ 0y4 + x1 = 44

0y1 + 1y2 + 1y3 + 0y4 + x2= 40

1y1 + 0y2 + 0y3 + 1y4 + x3= 62

0y1 + 1y2 + 0y3 + 1y4 + x4= 76

The rewritten objective function is
–12y1 – 13y2 – 15y3 – 20y4 + 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.