CHAPTER 22

Unconstrained Optimization.
Linear Programming

Optimization is a general term used to describe types of problems and solution techniques that are concerned with the best (“optimal”) allocation of limited resources in projects. The problems are called optimization problems and the methods optimization methods. Typical problems are concerned with planning and making decisions, such as selecting an optimal production plan. A company has to decide how many units of each product from a choice of (distinct) products it should make. The objective of the company may be to maximize overall profit when the different products have different individual profits. In addition, the company faces certain limitations (constraints). It may have a certain number of machines, it takes a certain amount of time and usage of these machines to make a product, it requires a certain number of workers to handle the machines, and other possible criteria. To solve such a problem, you assign the first variable to number of units to be produced of the first product, the second variable to the second product, up to the number of different (distinct) products the company makes. When you multiply these, for example, by the price, you obtain a linear function called the objective function. You also express the constraints in terms of these variables, thereby obtaining several inequalities, called the constraints. Because the variables in the objective function also occur in the constraints, the objective function and the constraints are tied mathematically to each other and you have set up a linear optimization problem, also called a linear programming problem.

The main focus of this chapter is to set up (Sec. 22.2) and solve (Secs. 22.3, 22.4) such linear programming problems. A famous and versatile method for doing so is the simplex method. In the simplex method, the objective function and the constraints are set up in the form of an augmented matrix as in Sec. 7.3, however, the method of solving such linear constrained optimization problems is a new approach.

The beauty of the simplex method is that it allows us to scale problems up to thousands or more constraints, thereby modeling real-world situations. We can start with a small model and gradually add more and more constraints. The most difficult part is modeling the problem correctly. The actual task of solving large optimization problems is done by software implementations for the simplex method or perhaps by other optimization methods.

Besides optimal production plans, problems in optimal shipping, optimal location of warehouses and stores, easing traffic congestion, efficiency in running power plants are all examples of applications of optimization. More recent applications are in minimizing environmental damages due to pollutants, carbon dioxide emissions, and other factors. Indeed, new fields of green logistics and green manufacturing are evolving and naturally make use of optimization methods.

Prerequisite: a modest working knowledge of linear systems of equations.

References and Answers to Problems: App. 1 Part F, App. 2.

22.1 Basic Concepts.
Unconstrained Optimization:
Method of Steepest Descent

In an optimization problem the objective is to optimize (maximize or minimize) some function f. This function f is called the objective function. It is the focal point or goal of our optimization problem.

For example, an objective function f to be maximized may be the revenue in a production of TV sets, the rate of return of a financial portfolio, the yield per minute in a chemical process, the mileage per gallon of a certain type of car, the hourly number of customers served in a bank, the hardness of steel, or the tensile strength of a rope.

Similarly, we may want to minimize f if f is the cost per unit of producing certain cameras, the operating cost of some power plant, the daily loss of heat in a heating system, CO₂ emissions from a fleet of trucks for freight transport, the idling time of some lathe, or the time needed to produce a fender.

In most optimization problems the objective function f depends on several variables

These are called control variables because we can “control” them, that is, choose their values.

For example, the yield of a chemical process may depend on pressure x₁ and temperature x₂. The efficiency of a certain air-conditioning system may depend on temperature x₁, air pressure x₂, moisture content x₃, cross-sectional area of outlet x₄, and so on.

Optimization theory develops methods for optimal choices of x₁, …, x_n, which maximize (or minimize) the objective function f, that is, methods for finding optimal values of x₁, …, x_n.

In many problems the choice of values of x₁, …, x_n is not entirely free but is subject to some constraints, that is, additional restrictions arising from the nature of the problem and the variables.

For example, if x₁ is production cost, then , and there are many other variables (time, weight, distance traveled by a salesman, etc.) that can take nonnegative values only. Constraints can also have the form of equations (instead of inequalities).

We first consider unconstrained optimization in the case of a function f(x₁, …, x_n). We also write X = (x₁, …, x_n) and f(x), for convenience.

By definition, f has a minimum at a point x = X₀ in a region R (where f is defined) if

for all x in R. Similarly, f has a maximum at X₀ in R if

for all x in R. Minima and maxima together are called extrema.

Furthermore, f is said to have a local minimum at X₀ if

for all x in a neighborhood of X₀, say, for all x satisfying

where X₀ = (X₁, …, X_n) and r > 0 is sufficiently small.

Similarly, f has a local maximum at X₀ if for all x satisfying |x − X₀| < r.

If f is differentiable and has an extremum at a point X₀ in the interior of a region R (that is, not on the boundary), then the partial derivatives ∂f/∂x₁, …, ∂f/∂x_n must be zero at X₀. These are the components of a vector that is called the gradient of f and denoted by grad f or ∇f. (For n = 3 this agrees with Sec. 9.7.) Thus

A point X₀ at which (1) holds is called a stationary point of f.

Condition (1) is necessary for an extremum of f at X₀ in the interior of R, but is not sufficient. Indeed, if, n = 1, then for y = f(x), condition (1) is y′ = f′(X₀) = 0; and, for instance, y = x³ satisfies y′ = 3x² = 0 at x = X₀ = 0 where f has no extremum but a point of inflection. Similarly, for f(x) = x₁x₂ we have δf(0) = 0, and f does not have an extremum but has a saddle point at 0. Hence, after solving (1), one must still find out whether one has obtained an extremum. In the case n = 1 the conditions y′(X₀) = 0, y″(X₀) > 0 guarantee a local minimum at X₀ and the conditions y′(X₀) = 0, y″(X₀) < 0 a local maximum, as is known from calculus. For n > 1 there exist similar criteria. However, in practice, even solving (1) will often be difficult. For this reason, one generally prefers solution by iteration, that is, by a search process that starts at some point and moves stepwise to points at which f is smaller (if a minimum of f is wanted) or larger (in the case of a maximum).

The method of steepest descent or gradient method is of this type. We present it here in its standard form. (For refinements see Ref. [E25] listed in App. 1.)

The idea of this method is to find a minimum of f(x) by repeatedly computing minima of a function g(t) of a single variable t, as follows. Suppose that f has a minimum at X₀ and we start at a point x. Then we look for a minimum of f closest to x along the straight line in the direction of , which is the direction of steepest descent (= direction of maximum decrease) of f at x. That is, we determine the value of t and the corresponding point

at which the function

has a minimum. We take this z(t)as our next approximation to X₀.

Fig. 473. Method of steepest descent in Example 1

Table 22.1 Method of Steepest Descent, Computations in Example 1

22.2 Linear Programming

Linear programming or linear optimization consists of methods for solving optimization problems with constraints, that is, methods for finding a maximum (or a minimum) x = (x₁, …, x_n) of a linear objective function

satisfying the constraints. The latter are linear inequalities, such as 3x₁ + 4x₂ 36, or x₁ 0, etc. (examples below). Problems of this kind arise frequently, almost daily, for instance, in production, inventory management, bond trading, operation of power plants, routing delivery vehicles, airplane scheduling, and so on. Progress in computer technology has made it possible to solve programming problems involving hundreds or thousands or more variables. Let us explain the setting of a linear programming problem and the idea of a “geometric” solution, so that we shall see what is going on.

Fig. 474. Linear programming in Example 1

Note well that the problem in Example 1 or similar optimization problems cannot be solved by setting certain partial derivatives equal to zero, because crucial to such problems is the region in which the control variables are allowed to vary.

Furthermore, our “geometric” or graphic method illustrated in Example 1 is confined to two variables x₁, x₂. However, most practical problems involve much more than two variables, so that we need other methods of solution.

Normal Form of a Linear Programming Problem

To prepare for general solution methods, we show that constraints can be written more uniformly. Let us explain the idea in terms of (1),

This inequality implies 60 − 2x₁ − 8x₂ 0 (and conversely), that is, the quantity

is nonnegative. Hence, our original inequality can now be written as an equation

where

x₃ is a nonnegative auxiliary variable introduced for converting inequalities to equations. Such a variable is called a slack variable, because it “takes up the slack” or difference between the two sides of the inequality.

Our example suggests that a general linear optimization problem can be brought to the following normal form. Maximize

subject to the constraints

with all b_j nonnegative. (If a b_j < 0, multiply the equation by −1.) Here x₁, …, x_n include the slack variables (for which the c_j’s in f are zero). We assume that the equations in (6) are linearly independent. Then, if we choose values for n − m of the variables, the system uniquely determines the others. Of course, since we must have

this choice is not entirely free.

Our problem also includes the minimization of an objective function f since this corresponds to maximizing −f and thus needs no separate consideration.

An n-tuple (x₁, …, x_n) that satisfies all the constraints in (6) is called a feasible point or feasible solution. A feasible solution is called an optimal solution if, for it, the objective function f becomes maximum, compared with the values of f at all feasible solutions.

Finally, by a basic feasible solution we mean a feasible solution for which at least n − m of the variables x₁, …, x_n are zero. For instance, in Example 2 we have n = 4, m = 2, and the basic feasible solutions are the four vertices O, A, B, C in Fig. 474. Here B is an optimal solution (the only one in this example).

The following theorem is fundamental.

For a proof, see Ref. [F5], Chap. 3 (listed in App. 1). A problem can have many optimal solutions and not all of them may be basic feasible solutions; but the theorem guarantees that we can find an optimal solution by searching through the basic feasible solutions only. This is a great simplification; but since there are different ways of equating n − m of the n variables to zero, considering all these possibilities, dropping those which are not feasible and then searching through the rest would still involve very much work, even when n and m are relatively small. Hence a systematic search is needed. We shall explain an important method of this type in the next section.

22.3 Simplex Method

From the last section we recall the following. A linear optimization problem (linear programming problem) can be written in normal form; that is:

For finding an optimal solution of this problem, we need to consider only the basic feasible solutions (defined in Sec. 22.2), but there are still so many that we have to follow a systematic search procedure. In 1948 G. B. Dantzig¹ published an iterative method, called the simplex method, for that purpose. In this method, one proceeds stepwise from one basic feasible solution to another in such a way that the objective function f always increases its value. Let us explain this method in terms of the example in the last section.

In its original form the problem concerned the maximization of the objective function

Converting the first two inequalities to equations by introducing two slack variables x₃, x₄, we obtained the normal form of the problem in Example 2. Together with the objective function (written as an equation z − 40x₁ − 88x₂ = 0) this normal form is

where x₁ 0, …, x₄ 0. This is a linear system of equations. To find an optimal solution of it, we may consider its augmented matrix (see Sec. 7.3)

This matrix is called a simplex tableau or simplex table (the initial simplex table). These are standard names. The dashed lines and the letters

are for ease in further manipulation.

Every simplex table contains two kinds of variables x_j. By basic variables we mean those whose columns have only one nonzero entry. Thus x₃, x₄ in (4) are basic variables and x₁, x₂ are nonbasic variables.

Every simplex table gives a basic feasible solution. It is obtained by setting the nonbasic variables to zero. Thus (4) gives the basic feasible solution

with x₃ obtained from the second row and x₄ from the third.

The optimal solution (its location and value) is now obtained stepwise by pivoting, designed to take us to basic feasible solutions with higher and higher values of z until the maximum of z is reached. Here, the choice of the pivot equation and pivot are quite different from that in the Gauss elimination. The reason is that x₁, x₂, x₃, x₄ are restricted to nonnegative values.

Step 1. Operation O₁: Selection of the Column of the Pivot

Select as the column of the pivot the first column with a negative entry in Row 1. In (4) this is Column 2 (because of the −40).

Operation O₂: Selection of the Row of the Pivot. Divide the right sides [60 and 60 in (4)] by the corresponding entries of the column just selected (60/2 = 30, 60/5 = 12). Take as the pivot equation the equation that gives the smallest quotient. Thus the pivot is 5 because 60/5 is smallest.

Operation O₃: Elimination by Row Operations. This gives zeros above and below the pivot (as in Gauss–Jordan, Sec. 7.8).

With the notation for row operations as introduced in Sec. 7.3, the calculations in Step 1 give from the simplex table T₀ in (4) the following simplex table (augmented matrix), with the blue letters referring to the previous table.

We see that basic variables are now x₁, x₃ and nonbasic variables are x₂, x₄. Setting the latter to zero, we obtain the basic feasible solution given by T₁,

This is A in Fig. 474 (Sec. 22.2). We thus have moved from o: (0, 0) with z = 0 to A: (12, 0) with the greater z = 480. The reason for this increase is our elimination of a term (−40x₁) with a negative coefficient. Hence elimination is applied only to negative entries in Row 1 but to no others. This motivates the selection of the column of the pivot.

We now motivate the selection of the row of the pivot. Had we taken the second row of T₀ instead (thus 2 as the pivot), we would have obtained z = 1200 (verify!), but this line of constant revenue z = 1200 lies entirely outside the feasibility region in Fig. 474. This motivates our cautious choice of the entry 5 as our pivot because it gave the smallest quotient (60/5 = 12).

Step 2. The basic feasible solution given by (5) is not yet optimal because of the negative entry −72 in Row 1. Accordingly, we perform the operations O₁ to O₃ again, choosing a pivot in the column of −72.

Operation O₁. Select Column 3 of T₁ in (5) as the column of the pivot (because −72 < 0).

Operation O₂. We have 36/7.2 = 5 and 60/2 = 30. Select 7.2 as the pivot (because 5 < 30).

Operation O₃. Elimination by row operations gives

We see that now x₁, x₂ are basic and x₃, x₄ nonbasic. Setting the latter to zero, we obtain from T₂ the basic feasible solution

This is B in Fig. 474 (Sec. 22.2). In this step, z has increased from 480 to 840, due to the elimination of −72 in T₁. Since T₂ contains no more negative entries in Row 1, we conclude that z = f(10, 5) = 40 · 10 + 88 · 5 = 840 is the maximum possible revenue. It is obtained if we produce twice as many S heaters as L heaters. This is the solution of our problem by the simplex method of linear programming.

Minimization. If we want to minimize z = f(x) (instead of maximize), we take as the columns of the pivots those whose entry in Row 1 is positive (instead of negative). In such a Column k we consider only positive entries t_jk and take as pivot a t_jk for which b_j/t_jk is smallest (as before). For examples, see the problem set.

22.4 Simplex Method: Difficulties

In solving a linear optimization problem by the simplex method, we proceed stepwise from one basic feasible solution to another. By so doing, we increase the value of the objective function f. We continue this stepwise procedure, until we reach an optimal solution. This was all explained in Sec. 22.3. However, the method does not always proceed so smoothly. Occasionally, but rather infrequently in practice, we encounter two kinds of difficulties. The first one is the degeneracy and the second one concerns difficulties in starting.

Degeneracy

A degenerate feasible solution is a feasible solution at which more than the usual number n − m of variables are zero. Here n is the number of variables (slack and others) and m the number of constraints (not counting the x_j 0 conditions). In the last section, n = 4 and m = 2, and the occurring basic feasible solutions were nondegenerate; n − m = 2 variables were zero in each such solution.

In the case of a degenerate feasible solution we do an extra elimination step in which a basic variable that is zero for that solution becomes nonbasic (and a nonbasic variable becomes basic instead). We explain this in a typical case. For more complicated cases and techniques (rarely needed in practice) see Ref. [F5] in App. 1.

Difficulties in Starting

As a second kind of difficulty, it may sometimes be hard to find a basic feasible solution to start from. In such a case the idea of an artificial variable (or several such variables) is helpful. We explain this method in terms of a typical example.

We have reached the end of our discussion on linear programming. We have presented the simplex method in great detail as this method has many beautiful applications and works well on most practical problems. Indeed, problems of optimization appear in civil engineering, chemical engineering, environmental engineering, management science, logistics, strategic planning, operations management, industrial engineering, finance, and other areas. Furthermore, the simplex method allows your problem to be scaled up from a small modeling attempt to a larger modeling attempt, by adding more constraints and variables, thereby making your model more realistic. The area of optimization is an active field of development and research and optimization methods, besides the simplex method, are being explored and experimented with.

CHAPTER 22 REVIEW QUESTIONS AND PROBLEMS

1. What is unconstrained optimization? Constraint optimization? To which one do methods of calculus apply?
2. State the idea and the formulas of the method of steepest descent.
3. Write down an algorithm for the method of steepest descent.
4. Design a “method of steepest ascent” for determining maxima.
5. What is the method of steepest descent for a function of a single variable?
6. What is the basic idea of linear programming?
7. What is an objective function? A feasible solution?
8. What are slack variables? Why did we introduce them?
9. What happens in Example 1 of Sec. 22.1 if you replace with ? Start from x₀ = [6 3]^T. Do 5 steps. Is the convergence faster or slower?
10. Apply the method of steepest descent to , 5 steps. Start from x₀ = [2 4]^T.
11. In Prob. 10, could you start from [0 0]^T and do 5 steps?
12. Show that the gradients in Prob. 11 are orthogonal. Give a reason.

13–16 Graph or sketch the region in the first quadrant of the x₁x₂-plane determined by the following inequalities.

• 13.
• 14.
• 15.
• 16.

17–20 Maximize or minimize as indicated.

• 17. Maximize f = 10x₁ + 20x₂ subject to x₁ 5, x₁ + x₂ 6, x₂ 4.
• 18. Maximize f = x₁ + x₂ subject to x₁ + 2x₂ 10, 2x₂ + x₂ 10, x₂ 4.
• 19. Minimize f = 2x₁ − 10x₂ subject to x₁ − x₂ 4, 2x₁ + x₂ 14, x₁ + x₂ 9, −x₁ + 3x₂ 15.
• 20. A factory produces two kinds of gaskets, G₁, G₂, with net profit of $60 and $30, respectively, Maximize the total daily profit subject to the constraints (x_j = number of gaskets G_j produced per day):

  

SUMMARY OF CHAPTER 22

Unconstrained Optimization. Linear Programming

In optimization problems we maximize or minimize an objective function z = f(x) depending on control variables x₁, …, x_m whose domain is either unrestricted (“unconstrained optimization,” Sec. 22.1) or restricted by constraints in the form of inequalities or equations or both (“constrained optimization,” Sec. 22.2).

If the objective function is linear and the constraints are linear inequalities in x₁, …, x_m, then by introducing slack variables x_m+1, …, x_n we can write the optimization problem in normal form with the objective function given by

(where c_m+1 = … = c_n = 0) and the constraints given by

In this case we can then apply the widely used simplex method (Sec. 22.3), a systematic stepwise search through a very much reduced subset of all feasible solutions. Section 22.4 shows how to overcome difficulties with this method.