# 8.2: Linear Optimization

written by: Danny Hsiao, Jenny Ou, and Huey Shann Sue

## 2.1 Introduction

Linear optimization is a method applicable for the solution of problems in which the objective function and the constraints appear as linear functions of the decision variables. The constraint equations may be in the form of equalities or inequalities[1]. In other words, linear optimization determines the way to achieve the best outcome (for example, to maximize profit or to minimize cost) in a given mathematical model and given some lists of requirements represented as linear equations [2].

## 2.2 Applications

Linear optimization can be applied to numerous fields, in business or economics situations, and also in solving engineering problems. It is useful in modeling diverse types of problems in planning, routing, scheduling, assignment and design [2].

### 2.2.1 Some examples of applications in different industries

Petroleum refineries

One of the early industrial applications of linear optimization has been made in the petroleum refineries. An oil refinery has a choice of buying crude oil from different sources with different compositions at different prices. It can manufacture different products, such as diesel fuel, gasoline and aviation fuel, in varying quantities. A mix of the purchased crude oil and the manufactured products is sought that gives the maximum profit.

Manufacturing firms

The sales of a firm often fluctuate, therefore a company has various options. It can either build up an inventory of the manufactured products to carry it through the period of peak sales, or to pay overtime rates to achieve higher production during periods of high demand. Linear optimization takes into account the various cost and loss factors and arrive at the most profitable production plan.

Food-processing industry

Linear optimization has been used to determine the optimal shipping plan for the distribution of a particular product from different manufacturing plants to various warehouses.

Telecommunications

The optimal routing of messages in a communication network and the routing of aircraft and ships can also be determined by linear optimization method.

## 2.3 Characteristics of Linear Optimization

The characteristics of a linear optimization problem are:

1. The objective function is of the minimization type
2. All the constraints are of the equality type
3. All the decision variables are non-negative

Any linear optimization problem can be expressed in the standard form by using the following transformation:

1) The maximization of a function is equivalent to the minimization of the negative of the same function.

For example:

Minimize

is equivalent to

Maximize

Consequently, the objective function can be stated in the minimization form in any linear optimization problem.

2) If a constraint appears in the form of a "less than or equal to" type of inequality as

it can be converted into the equality form by adding a non-negative slack variable as follows:

Similarly, if the constraint is in the form of a "greater than or equal to" type of inequality, it can be converted into the equality form by subtracting the surplus variable .

3) In most engineering optimization problems, the decision variables represent some physical dimensions, hence the variables will be non-negative.

However, a variable may be unrestricted in sign in some problems. In such cases, an unrestricted variable (which can take a positive, negative or zero value) can be written as the difference of two non-negative variables.

Thus, if is unrestricted in sign, it can be written as , where

and

It can be seen that will be negative, zero or positive, depending on whether is greater than, equal to, or less than

## 2.4 Example 1

This example comes from Seborg, Edgar, and Mellinchamp (with some corrections).

A chemical company is mixing chemical component, A and B to produce product, E and F. The chemical reaction is listed below:

The conditions of this production is listed as below:

 Cost of Materials Maximum Available per day Fixed Cost A $0.15/lbs 40,000lbs 350 B$0.20/lbs 30,000lbs 200 Value of Products Maximum Production Rate E $0.40/lbs 30,000lbs F$0.33/lbs 30,000lbs

The profit of this production can be simply described as the function below:

Profit

 = ∑ FsVs − ∑ FrVr − C.P. − F.C. s r

Flow Rates of Products

Flow Rates of Raw Materials

Values of Products

Values of Raw Materials

Cost of Production

Fixed Cost

• :
• :
• :
• :
• :

### 2.4.2 Solution

Solution using Mathematica

INPUT:

profit = 0.25 FE + 0.28 FF - 0.15 FA - 0.2 FB - 350 - 200

sol = Maximize[ profit, {FA > 0, FB > 0, FA < 40000, FB < 30000, FE > 0, FE < 30000, FF > 0, FF < 30000, FA == (1/2) FE + (1/3) FF, FB == (1/2) FE + (2/3) FF}, {FE, FF}]

OUTPUT: {3875., {FE -> 30000., FF -> 22500.}}

Solution using "Solver" in Excel.

Result is FE = 30,000, FF = 22500.

If only process ! or process 2 were running a full capacity, the profit would be less.

### 2.4.3 Linear Optimization

The above is an example of linear optimization. It is often used in oil refinery to figure out maximal profit in response to market competition.

## 2.5 Example 2

Example of Linear Optimization Problem in Excel

Written by: Jennifer Campbell, Katherine Koterba, MaryAnn Winsemius

### 2.5.1 Part 1: Organize Given Information

As stated in the Linear Optimization section example above, there are three categories of information needed for solving an optimization problem in Excel: an objective function, constraints, and decision variables.

We will use the following example to demonstrate another application of linear optimization. We will be optimizing the profit for Company X’s trucking business.

## 2.7 Solving Linear Optimization Problems Using The Primal Simplex Algorithm

Written by: Tejas Kapadia and Dan Hassing

[Note: needs specific reference, and also solution to the preceding problem by this method would be good -- R.Z.]

Instead of solving linear optimization problems using graphical or computer methods, we can also solve these problems using a process called the Primal Simplex Algorithm. The Primal Simplex Algorithm starts at a Basic Feasible Solution (BFS), which is a solution that lies on a vertex of the subspace contained by the constraints of the problem. In the Graph in Example 1, this subspace refers to the shaded region of the plot. Essentially, after determining an initial BFS, the Primal Simplex Algorithm moves through the boundaries from vertex to vertex until an optimal point is determined.

The basic procedure is the following:

1. Find a unit basis.
2. Set-up the problem in standard form using a canonical tableau.
3. Check optimality criterion.
1. If criterion passes, then stop, solution has been found.
1. Select an entering variable among the eligible variables.
2. Perform pivot step.
3. Go back to 1.

For simplicity, we will make the following assumptions:

1. The optimum lies on a vertex and is not unbounded on an extreme half-line.
2. The constraints are equations and not also inequalities.
1. In the case that the constraints are inequalities, slack variables will need to be introduced. Although the process is not very different in this case, we will ignore this to make the algorithm slightly less confusing.
1. Decision variables are required to be nonnegative.
2. The problem is a minimization problem. To turn a maximization problem into a minimization problem, multiply the objective function by -1 and follow the process to solve a minimization problem.

We will begin with the following example:

Objective Function: Minimize

Subject to the constraints:

First we begin by finding a unit basis:

A shortcut method to finding this unit basis is putting numbers in for each variable so that every constraint equation is satisfied.

In this case, setting , , and will satisfy the final equation and also set the values for , , and to 2, 1, and 5, respectively. Remember, these decision variables must be nonnegative.

Set up the canonical tableau in the following form:

As you can see, the first four rows correspond to the constraints, while the final row corresponds to the objective function. The “b” column corresponds to the right hand side (RHS) of the constraints. As you can see, the “-z” column is on the left hand side (LHS) of the equation, rather than the RHS.

First, we should perform pivot steps so that the tableau corresponds to the unit basis we found earlier. By performing pivot steps on , , , and , we will reach the feasible point where (, , , , , and ) = . Because , , and all equal zero, the pivot step on can actually be done on or , but in this example, we used . These pivot steps can be performed on any row as long as they are all different rows. In this example, we performed pivot steps on , , , using the Pivot and Gauss-Jordan Tool at people.hofstra.edu/Stefan_Waner/RealWorld/tutorialsf1/scriptpivot2.html. To use this tool, place the cursor on the cell that you wish to pivot on, and press “pivot”.

After four pivot steps, the tableau will look like this:

As you can see, this is identical to the initial tableau, as , , , and were set up such that an initial feasible point was already chosen.

The optimality criterion states that if the vector in the bottom left of the tableau is all positive, then an optimal solution exists in the “b” column vector, with the value at the bottom of the “b” column vector as the negative of the value of the objective function at that optimal solution. If this is not true, then a pivot step must be performed. In this example, clearly, a pivot step must be performed.

Next, we need to choose an entering variable. We want to choose an entering variable that has a negative element in the bottom row, meaning that the objective value could be improved if that variable was nonzero in the solution. So, we will choose in this example. Now, we must calculate ratios of each RHS coefficient divided by the coefficient of the entering variable in that row. In this case, the vector corresponding to this calculation would equal . We cannot pivot on a zero element, so we cannot pivot on the fourth row. We want to keep the RHS positive, so we cannot pivot on the first row. We must choose the minimum nonnegative ratio to remain at a feasible solution, so we choose the second row in the column, which has a ratio of 1/1.

After the pivot step:

As we can see, has a negative coefficient in the bottom row, indicating the same step must be repeated on that column. We calculate ratios for that column, and get: . Consequently, we choose to pivot on the fourth row because it corresponds to the minimum nonnegative ratio of 0.

After another pivot step:

Because the bottom row is all positive, we are now at an optimal solution. To understand this final tableau, we look at each column for variables that only have one “1” in the column. If the column has only one “1”, the RHS value in that row is the value of that variable. In this case, , , and . Any variable that does not have just a single “1” in the column is equal to zero. So, the optimal solution is (, , , , , and ) = , and the optimal value is (z was on the LHS in the tableau).

Now, we have successfully solved a linear optimization problem using the Primal Simplex Algorithm. Verification of the solution can be easily performed in Microsoft Excel.

## References

1. D. E. Seborg, T. F. Edgar, D. A. Mellichamp: Process Dynamics and Control, 2nd Edition, John Wiley & Sons.
2. Rao, Singiresu S. Engineering Optimization - Theory and Practice, 3rd Edition, 129-135, John Wiley & Sons.
3. www.wikipedia.org
4. http://www.math.ualberta.ca/~devries...erTutorial.pdf