What does sliding an objective function line toward the origin represent away from the origin?

Chapter 16  :  Linear Programming: The Graphical and Simplex Methods

INTRODUCTION

Linear programming (LP) is an application of matrix algebra used to solve a broad class of problems that can be represented by a system of linear equations. A linear equation is an algebraic equation whose variable quantity or quantities are in the first power only and whose graph is a straight line. LP problems are characterized by an objective function that is to be maximized or minimized, subject to a number of constraints. Both the objective function and the constraints must be formulated in terms of a linear equal­ity or inequality. Typically; the objective function will be to maximize profits (e.g., contribution margin) or to minimize costs (e.g., variable costs). The following assumptions must be satisfied to justify the use of linear programming:

Linearity. All functions, such as costs, prices, and technological requirements, must be linear in nature.

Certainty. All parameters are assumed to be known with certainty.

Nonnegativity. Negative values of decision variables are unacceptable.

Two approaches were commonly used to solve LP problems:

• Graphical method

• Simplex method

Now, however, MSExcel is much easier to use.

The graphical method is limited to LP problems involving two decision variables and a limited number of constraints due to the difficulty of graphing and evaluating more than two decision variables. This restriction severely limits the use of the graphical method for real-world problems. The graphical method is presented first here, however, because it is simple and easy to understand and it is a very good learning tool.

The computer-based simplex method is much more powerful than the graphical method and provides the optimal solution to LP problems containing thousands of decision variables and constraints. It uses an iter­ative algorithm to solve for the optimal solution. Moreover, the simplex method provides information on slack variables (unused resources) and shadow prices (opportunity costs) that is useful in performing sen­sitivity analysis. Excel uses a special version of the simplex method, as will be discussed later.

CONSTRUCTING LINEAR PROGRAMMING PROBLEMS AND SOLVING THEM GRAPHICALLY

We will use the following Bridgeway Company case to introduce the graphical method and illustrate how it solves LP maximization problems. Bridgeway Company manufactures a printer and keyboard. The con­tribution margins of the printer and keyboard are $30 and $20, respectively. Two types of skilled labor are required to manufacture these products: soldering and assembling. A printer requires 2 hours of soldering and 1 hour of assembling. A keyboard requires 1 hour of soldering and 1 hour of assembling. Bridgeway has 1,000 soldering hours and 800 assembling hours available per week. There are no constraints on the supply of raw materials. Demand for keyboards is unlimited, but at most 350 printers are sold each week. Bridgeway wishes to maximize its weekly total contribution margin.

Constructing the Linear Programming Problem for Maximization of the Objective Function

Constructing the LP problem requires four steps:

Step 1. Define the decision variables.

Step 2. Define the objective function.

Step 3. Determine the constraints.

Step 4. Declare sign restrictions.

STEP 1: DEFINE THE DECISION VARIABLES. In any LP problem, the decision variables should completely describe the decisions to be made. Bridgeway must decide how many printers and keyboards should be manufactured each week. With this in mind, the decision variables are defined as follows:

X = Number of printers to produce weekly

Y = Number of keyboards to produce weekly

STEP 2: DEFINE THE OBJECTIVE FUNCTION. The objective function represents the goal that management is trying to achieve. The goal in Bridgeway's case is to maximize (max) total contribution margin. For each printer that is sold, $30 in contribution margin will be realized. For each keyboard that is sold, $20 in contribution margin will be realized. Thus, the total contribution margin for Bridgeway can be expressed by the following objective function equation:

max Z = $30X + $20Y

where the variable Z denotes the objective function value of any LP problem. In the Bridgeway case, Z equals the total contribution margin that will be realized when an optimal mix of products X (printer) and Y (keyboard) is manufactured and sold.

STEP 3: DETERMINE THE CONSTRAINTS. A constraint is simply some limitation under which the enterprise must operate, such as limited production time or raw materials. In Bridgeway's case, the objec­tive function grows larger as X and Y increase. In other words, if Bridgeway were free to choose any values for X and Y, the company could make an arbitrarily large contribution margin by choosing X and Y to be very large. The values of X and Y, however, are restricted by the following three constraints:

Constraint 1. Each week, no more than 1,000 hours of soldering time may be used. Thus, constraint l may be expressed by:

2X + Y £ 1,000

because it takes 2 hours of soldering to produce one printer and 1 hour of soldering to produce one key­board. The inequality sign means that the total soldering time for both products X and Y cannot exceed the 1,000 soldering hours available, but could be less than the available hours.

Constraint 2. Each week, no more than 800 hours of assembling time may be used. Thus, constraint 2 may be expressed by:

X + Y  £ 800

Constraint 3. Due to limited demand, at most 350 printers should be produced each week. This constraint can be expressed as follows:

X £ 350

STEP 4: DECLARE SIGN RESTRICTIONS. To complete the formulation of an LP problem, the fol­lowing question must be answered for each decision variable: Can the decision variable assume only non­negative values, or is it allowed to assume both positive and negative values? In most LP problems, positive values are assumed. For example, in the Bridgeway case, production cannot be less than zero units. Therefore, the sign restrictions are:

X >= 0

Y >= 0

These four steps and the formulation of the LP problem for Bridgeway are summarized in Exhibit 16-1

 Exhibit 16 -1  Summary of the Linear Programming Problem for Bridgeway Company

Choose production levels for printers (X) and keyboards (Y) that:

max Z = $30X + $20Y      (objective function)

and satisfy the following:

2X + Y <= 1,000   (soldering time constraint)

X + Y <= 800        (assembling time constraint)

X <= 350               (demand constraint for printers)

X => 0 (sign restriction)

Y => 0 (sign restriction)

. This LP problem provides the necessary data to develop a graphical solution.

Graphical Solution to the Maximization Linear Programming Problem

The following are two of the most basic concepts associated with LP:

• Feasible region

• Optimal solution

The graphical solution involves two steps:

Step 1. Graphically determine the feasible region. Step 2. Search for the optimal solution.

STEP 1: GRAPHICALLY DETERMINE THE FEASIBLE REGION. The feasible region represents the set of all feasible solutions to an LP problem. In the Bridgeway case, the feasible region is the set of all points (X, Y) satisfying the constraints in Exhibit 16-1.

For a point (X, Y) to be in the feasible region, (X, Y) must satisfy all the above inequalities. A graph con­taining these constraint equations is shown in Exhibit 16-2

 Exhibit 16 -2  Feasible Region for the Bridgeway Problem

What does sliding an objective function line toward the origin represent away from the origin?

. Note that the only points satisfying the non­negativity constraints are the points in the first quadrant of the X, Y plane. This is indicated by the arrows pointing to the right from the y-axis and upward from the x-axis. Thus, any point that is outside the first quadrant cannot be in the feasible region.

In plotting equation 2X + Y <= 1,000 on the graph, the following questions are asked: How much of prod­uct X could be produced if all resources were allocated to it? In this equation, a total of 1,000 hours of sol­dering time is available. If all 1,000 hours are allocated to product X, 500 printers can be produced each week. On the other hand, how much of product Y could be produced if all resources were allocated to it? If all 1,000 soldering hours are allocated to produce Y, then 1,000 keyboards can be produced each week. Thus, the line on the graph expressing the soldering time constraint equation extends from the 500-unit point A on the x-axis to the 1,000-unit point B on the y-axis.

The equation associated with the assembling capacity constraint has been plotted on the graph in a similar manner. If 800 assembling hours are allocated to product X, then 800 printers can be produced. If, on the other hand, 800 assembling hours are allocated to product Y, then 800 keyboards can be produced. This analysis results in line CD.

Since equation X < 350 concerns only product X, the line expressing the equation on the graph does not touch the y-axis at all. It extends from the 350-unit point E on the x-axis and runs parallel to the y-axis, thereby signifying that regardless of the number of units of X produced, no more than 350 units of X can ever be sold.

Exhibit 16-2 shows that the set of points in the quadrant that satisfies all constraints is bounded by the five-sided polygon HDGFE. Any point on this polygon or in its interior is in the feasible region. Any other point fails to satisfy at least one of the inequalities and thus falls outside the feasible region.

STEP 2: SEARCH FOR THE OPTIMAL SOLUTION. Having identified the feasible region for the Bridgeway case, we now search for the optimal solution, which will be the point in the feasible region that maximizes the objective function. In Bridgeway's case, this is:

max Z = $30X + $20Y

To find the optimal solution, we graph lines so that all points on a particular line have the same Z-value. In a maximization problem, such lines are called isoprofit lines; in a minimization problem, they are called isocost lines. The parallel lines are created by assigning various values to Z in the objective function to provide either higher profits or lower costs.

A graph showing the isoprofit lines for Bridgeway Company appears in Exhibit 16-3

 Exhibit 16 -3  Graph Showing the Optimal Solution of the Bridgeway Problem

What does sliding an objective function line toward the origin represent away from the origin?

. The isoprofit lines are broken to differentiate them from the lines that form the feasible region. To draw an isoprofit line, any Z-value is chosen, then the x- and y-intercepts are calculated. For example, a contribution margin value of $6,000 gives a line with intercepts at 200 printers and 300 keyboards:

$6,000 = $30X + $20(0)   $6,000 = $30(0) + $20Y

X = 200   Y = 300

Since all isoprofit lines are of the form $30X + $20Y = contribution margin, they all have the same slope. Consequently, once an isoprofit line is drawn, all other isoprofit lines can be found by moving parallel to the initial line. Another isoprofit line is found by selecting a contribution margin of $9,000, which gives a line having intercepts at 300 printers and 450 keyboards:

$9,000 = $30X + $20(0)   $9,000 = $30(0) + $20Y

X = 300   Y = 450

Isoprofit lines move in a northeast direction; that is, upward and to the right. After a while, the isoprofit lines will no longer intersect the feasible region. The isoprofit line intersecting the last vertex of the feasi­ble region defines the largest Z-value of any point in the feasible region and indicates the optimal solution to the LP problem. In Exhibit 16-3, the isoprofit line passing through point G is the last isoprofit line to intersect the feasible region. Thus, point G is the point in the feasible region with the largest Z-value and is therefore the optimal solution to the Bridgeway problem. Note that point G is located at the intersection of lines 2X + Y = 1,000 and X + Y = 800. Solving these two equations simultaneously results in:

X = 200

Y = 600

The optimal value of Z (i.e., the total contribution margin) may be found by substituting these values of X and Y into the objective function. Thus, the optimal value of Z is:

max Z = $30 (200) + $20 (600) = $18,000

The five corners of the feasible region, designated by HDGFE, will yield different product mixes between X and Y. The calculations are presented in Exhibit 16-4, starting at the origin and going clockwise around the feasible region. These calculations also show that the optimal production mix is 200 printers and 600 keyboards. Any other production mix will result in a lower total contribution margin.

In some cases, an objective function may be parallel to one of the feasibility region boundaries. In such a case, the optimal solution will include any solutions that lie on the border. For example, in Exhibit 16-5 the solution is a line along the boundary of the feasible region. Therefore, any mix of E and C along this line will be optimal.  

 Exhibit 16 -4  z-Value for Each Corner in the Feasible Region

Corner of the Feasible Region

Units Produced

H

0

0

D

0

800

G

200

600

F

350

300

E

350

0

X

Y

Total Contribution Margin

H

$30 (0)

+ $20 (0)

$ 0

D

$30 (0)

+ $20 (800)

$16,000

G

$30 20(0)

+ $20 (600)

$18,000a

F

$30 (350)

+ $20 (300)

$16,500

E

$30 (350)

+ $20 (0)

$10,500

Constructing the Linear Programming Problem for Minimization of the Objective Function

We will use the following K9 Kondo Company case to demonstrate how the graphical method solves LP minimization problems. The K9 Kondo Company manufactures climate-controlled doghouses. The com­pany believes that its high-volume customers are high-income male and female dog owners who want to pamper their pets. To reach these groups, the marketing manager at K9 Kondo is considering placing one-minute commercials on the following national TV shows: “New York Dog Show” and “Man's Best Friend.”

A one-minute commercial on “New York Dog Show” costs $200,000, and a one-minute commercial on “Man's Best Friend” costs $50,000. The marketing manager would like the commercials to be seen by at least 60 million high-income women and at least 36 million high-income men. Marketing studies show the following:

• Each one-minute commercial on “New York Dog Show” is seen by six million high-income women and two million high-income men.

• Each one-minute commercial on “Man's Best Friend” is seen by three million high-income women and three million high-income men.

Constructing the LP problem for minimization of the objective function follows the same steps used in constructing the LP problem for maximization of the objective function:    

 Exhibit 16 -5  Multiple Optimal Solutions Graphic Example

What does sliding an objective function line toward the origin represent away from the origin?

Step 1. Define the decision variables.

Step 2. Define the objective function.

Step 3. Determine the constraints.

Step 4. Declare sign restrictions.

STEP 1: DEFINE THE DECISION VARIABLES. The marketing manager at K9 Kondo must decide how many “New York Dog Show” and “Man's Best Friend” one-minute commercials to purchase. There­fore, the decision variables are:

X = Number of one-minute “New York Dog Show” commercials purchased

Y = Number of one-minute “Man's Best Friend” commercials purchased

STEP 2: DEFINE THE OBJECTIVE FUNCTION. The marketing manager is trying to minimize total advertising cost. Thus, the objective function (in thousands of dollars) is:

min Z = $200X + $50Y

STEP 3: DETERMINE THE CONSTRAINTS. The values of X and Y are restricted by the following constraints:

Constraint 1. The commercials must reach at least 60 million high-income women. Thus, constraint 1 may be expressed by:

6X + 3Y => 60

Constraint 2. The commercials must reach at least 36 million high-income men. Thus, constraint 2 may be expressed by:

2X+3Y => 36

STEP 4: DECLARE SIGN RESTRICTIONS. The sign restrictions are expressed by:

X => 0

Y => 0

These four steps and the formulation of the LP problem for K9 Kondo are summarized in Exhibit 16-6

 Exhibit 16 -6  Summary of the Linear Programming Problem for K9 Kondo Company

Choose the number of commercials on “New York Dog Show” (X) and “Man’s Best Friend” (Y) that:

min Z = $200X + $50Y    (objective function)

and satisfy the following:

6X + 3Y => 60

2X+3Y => 36

X => 0

Y => 0

. This LP problem provides the necessary data to develop a graphical solution.

Graphical Solution to the Minimization Linear Programming Problem

Like the Bridgeway problem, the K9 Kondo problem has a feasible region, but K9 Kondo's feasible region, unlike Bridgeway's, contains points for which the value of at least one variable can assume arbi­trarily large values. Such a feasible region is sometimes called an unbounded feasible region, but it is referred to here as simply the feasible region.

The graphical solution includes two steps:

Step 1. Graphically determine the feasible region.

Step 2. Search for the optimal solution.

STEP 1: GRAPHICALLY DETERMINE THE FEASIBLE REGION. The feasible region for K9 Kondo's advertising campaign is shown in Exhibit 16-7

 Exhibit 16 -7  Feasible Region for the K9 Kondo Problem

What does sliding an objective function line toward the origin represent away from the origin?

. Note that 6X + 3Y => 60 is satisfied by points on or above the line AB and that 2X + 3 Y => 36 is satisfied by the points on or above the line CD. The only points satisfying all of the constraints are in the shaded region bounded by the x-axis, CEB, and the y-axis. This is the feasible region.

Line AB, which represents the plot of constraint 6X + 3 Y => 60, is determined by first plotting the end points of the line 6X + 3Y = 60. Setting first Y and then X equal to 0, we have:

6X = 60   3Y = 60

X = 10   Y = 20

Therefore, end point A is X = 10 and Y = 0, and end point B is X = 0 and Y = 20.

Next, the constraint 2X + 3Y => 36 is plotted by first plotting the end points of the line 2X + 3Y = 36. Again, setting first Y and then X equal to 0, we have:

2X = 36   3Y= 36

X=18   Y=12

Therefore, end point C is X = 18 and Y = 0, and end point D is X = 0 and Y = 12.

STEP 2: SEARCH FOR THE OPTIMAL SOLUTION. Note that instead of isoprofit lines these are isocost lines. The objective function is

min Z = $200X + $50Y

and the marketing manager's goal is to minimize total advertising costs. Consequently, feasible values for X and Y that minimize Z must be chosen. Thus, the optimal solution to the K9 Kondo LP problem is the point in the feasible region with the smallest Z-value.

Consider an arbitrary cost of $1,800,000. That is, Z = $1,800 and the isocost line is

$1,800 = $200X + $50Y

as shown in Exhibit 16-8

 Exhibit 16 -8  Graph Showing The Optimal Solution for the K9 Kondo Problem

What does sliding an objective function line toward the origin represent away from the origin?

. Another parallel isocost line $1,400 = $200X + $50Yis also shown in Exhibit 16-8. Thus, the direction of minimum cost (i.e., decreasing Z) is toward the southwest; that is, downward and to the left. At a cost of $800,000 (Z = $800), the isocost line is beyond the feasible region and there­fore does not represent a feasible solution. The optimum isocost line is the one that intersects point B, because this is the farthest southwest point in the feasible region. Thus, point B is the optimal solution to the K9 Kondo problem. Or stating it another way, point B has the smallest Z-value of any point in the fea­sible region.

Notice that the set of feasible solutions has three corner points B E, and C.

B = (0, 20)

C = (18, 0)

Notice that point E is at the intersection of lines 6X + 3 Y = 60 and 2X + 3 Y = 36. Point E is obtained by finding the simultaneous solution to these two equations:

6X + 3 Y

= 60

-2X - 3Y

= -36

4X

=  24

X

=  6

Substituting X = 6 into 2X + 3Y = 36 yields:

2(6) + 3Y = 36

3Y= 24

Y= 8

Thus, point E = (X = 6, Y = 8).

Now, the corner points of BEC are tested. The three corners will yield different mixes of one-minute com­mercials on “New York Dog Show,” represented by X, and on “Man's Best Friend,” represented by Y. The calculations are presented in Exhibit 16-9

 Exhibit 16 -9  Z-Value for Each Corner in the Feasible Region

One-Minute Commercials Purchased

Corner of Feasible Region

X

Y

B

0

20

E

6

8

C

18

0

X

Y

Total Advertising Cost

B: $200 (0)

+ $50 (20) =

$1,000,000 (optimal solution)

E: $200 (6)

+ $50 (8)    =

$1,600,000

C: $200 (18)

+ $50 (0)    =

$3,600,000

. The optimal advertising plan is to purchase 20 one-minute commercials on “Man's Best Friend” and zero one-minute commercials on “New York Dog Show.” The total optimal advertising cost is $1,000,000.

USING THE SIMPLEX METHOD TO SOLVE MAXIMIZATION PROBLEMS

Solving LP problems graphically is only practical when there are two decision variables. Moreover, the graphical method becomes cumbersome when there are many constraints. Real-world LP problems typi­cally have thousands of corner points.

The reigning champ for handling such problems is the simplex method, devised in 1947 by George B. Dantzig of Stanford University1. The simplex method provides an iterative algorithm that systematically locates feasible corner points that will improve the objective function value until the optimal solution is reached. Regardless of the number of decision variables and constraints, the simplex algorithm applies the key characteristic of any LP problem: An optimal solution always occurs at a corner point of the feasible region. The simplex algorithm finds corner-point solutions, tests them for optimality, and stops once an optimal solution is found.

Before discussing the simplex steps required to maximize an objective function, a few concepts from linear algebra must be introduced2. These concepts are relatively basic and can be explored further in any intro­ductory linear algebra text.

Scalars, Matrices, and Vectors

The numbers used in daily life are called scalars. Scalars are simply single numbers, or variables used to identify single numbers. A number such as 8 is a scalar.

People who have used a spreadsheet such as Excel or who have done any computer programming already have a good understanding of the concept of a matrix. A matrix is a rectangular array of numbers having m rows and n columns; it is typically contained in brackets. For instance, one can refer to the 2 X 4 matrix [A] and identify the individual numbers with a subscripted lower-case a, such as ay. In the following matrix, the subscripts i and j identify the row and column, respectively, of each matrix entry:

What does sliding an objective function line toward the origin represent away from the origin?
 

A vector is a type of matrix having either an m dimension of 1 (row vector) or an n dimension of 1 (col­umn vector). Here, a column vector [b] and a row vector [c] are shown below:

What does sliding an objective function line toward the origin represent away from the origin?
 

What does sliding an objective function line toward the origin represent away from the origin?
 

Arithmetic Operations with Matrices and Vectors

Solving an LP problem by the simplex method requires three linear algebra operations: multiplying a vec­tor by a matrix (which results in a vector), multiplying a vector by a vector (which results in a scalar), and subtracting a vector from a vector (which results in a vector).

To multiply a row vector by a matrix, the vector must have the same number of columns as the matrix has rows; otherwise, the operation is impossible. The following illustration shows how this multiplication is performed:

What does sliding an objective function line toward the origin represent away from the origin?
 

= [(cla11 + c2a21 + c3a31) (cla12 + c2a22 + c3a32) (c1a13 + c2a23 + c3a33) (c1a14 + c2a24 + c3a34)]

The entries in each column of the matrix are multiplied by the entries in the vector, then summed to pro­duce the entries in the resulting row vector.

The next illustration demonstrates how a row vector may be multiplied by a column vector. The result is a scalar. This operation is just a special case of the preceding operation, as vectors are just special types of matrices. Again, the number of columns in the row vector is equal to the number of rows in the column vector:

What does sliding an objective function line toward the origin represent away from the origin?
 

= c1b1 + c2b2 + c3b3

Finally, to subtract a row vector from a row vector, the first entry of the second vector is subtracted from the first entry of the first vector, which yields the first entry of the resulting row vector. The second entries of the vectors are then subtracted, yielding the second entry of the result, and so on until all entries have been subtracted:

[c] - [d]    = [c1 c2 c3] - [d1 d2 d3]

   = [(c1 - dl) (c2 - d2) (c3 - d3)]

Additionally, matrices are added and subtracted in a similar manner.

Row-Reduced Matrix Form

The number of nonzero rows in a matrix is known as its rank. A matrix column containing a single one (1) in any position, with the remaining column entries being zeros, is known as an elementary column. A matrix is said to be in row-reduced form if the number of elementary columns is equal to the rank of the matrix. The following matrices [B], [C], and [D] serve as examples:

What does sliding an objective function line toward the origin represent away from the origin?
      
What does sliding an objective function line toward the origin represent away from the origin?
       
What does sliding an objective function line toward the origin represent away from the origin?

Which of these are row-reduced matrices? [B] is a row-reduced matrix, because its rank is 2 (only the top two rows are nonzero) and it has two elementary columns (3 and 4). [D] is also row-reduced, since its rank is 3 and columns 2, 3, and 5 are elementary. However, [C] is not row-reduced, since its rank is 3 but only columns 2 and 4 are elementary. One more elementary column is needed.

How might matrix [C] be put into row-reduced form? That is, how can one more elementary column be created? Since each row of a matrix represents the coefficients of an equation, all the numbers in any row of a matrix can be multiplied by an appropriate constant without disrupting the meaning of the matrix. Thus, a particular value can be changed to a 1. Also, since the matrix represents a system of simultaneous linear equations, rows can legally be added or subtracted from each other. Consequently, the other values can be changed to zeros in the column where the I is. Multiplying the first row of matrix [C] by 0.5 gives:

What does sliding an objective function line toward the origin represent away from the origin?
 

which produces a 1 in the first position of row 1. Next, row 1 is subtracted from row 2 to obtain:

What does sliding an objective function line toward the origin represent away from the origin?
 

Finally, row 1 is subtracted from row 3 three times to get:

What does sliding an objective function line toward the origin represent away from the origin?
 

which produces the needed zeros in the first column. Matrix [C] is now in row-reduced form.

Pivoting a Matrix

The key to iteration in the simplex algorithm is a matrix procedure called pivoting. This is merely the row-reduction technique just presented; the goal is to obtain a one (1) in a particular position in the matrix, with all other column entries becoming zero. Once the pivot entry is chosen (which is a location in the matrix), the row and column containing the pivot entry are called the pivot row and pivot column, respec­tively. All the values in the pivot row are then divided by the value in the pivot entry position to obtain a one (1) in the pivot entry position. Then, the pivot row is used to obtain zeros in the rest of the pivot col­umn by subtracting the pivot row the required number of times from the other rows. The matrix has now been “pivoted about” the pivot entry.

A Simplex Maximization Example

The simplex algorithm can be used to solve LP problems in which the goal is to maximize the objective function. The following example is necessarily simple to illustrate the mechanics of the algorithm; it could easily be solved graphically. The method is the same for more complex problems. The simplex solution of a minimization LP problem is described in a later section.

The Heartache machine shop has time available on three machines, and the shop's owner wishes to sched­ule production of two types of fastening pins. The owner's objective is to maximize the profit resulting from the proposed production run.

Lathe A is used for rough turn of the pin stock and has 50 hours of time available. Lathe B is used to finish turn the fastening pins and has 36 hours available. The third machine, grinder G, is used to finish grind each pin, thereby completing the production process. The grinder has 81 hours available. Manufacturing times for pin lots, in hours, are summarized as follows:

Machine Lot Times

A

B

G

Pin Type 1

10

6

4.5

Pin Type 2

5

6

18.0

Heartache’s profit on these pins is $9 per lot for Type 1 and $7 per lot for Type 2.

Before the simplex algorithm can be applied, the LP problem must be set up using the four steps intro­duced in the graphical method section.

STEP 1: DEFINE THE DECISION VARIABLES. In this example, the produce-thin mix of Types 1 and 2 must be “programmed” for maximum profitability. Hence, the unknown number of lots of each pin type can be represented as follows:

XI = Number of lots of pin Type 1

X2 = Number of lots of pin Type 2

STEP 2: DEFINE THE OBJECTIVE FUNCTION. The machine shop owner's goal can be expressed by the following objective function equation:

max Z = $9X1 + $7X2

This equation has one term for the profit generated by producing pin Type 1 and another term for the profit generated by producing pin Type 2. Together, they equal AeroTech's profit, Z, which is to be maximized.

STEP 3: DETERMINE THE CONSTRAINTS. This simplified example is limited only by the machine times available for the production of fastening pins. Using these times, along with the lot manufacturing times for each pin type, the following constraints can be formulated:  

 10X1 + 5X2 <=

50

(lathe A)

6X1 + 6X2 <=

36

(lathe B)

4.5X1 + 18X2 <=

81

(grinder G)

STEP 4: DECLARE SIGN RESTRICTIONS. Of course, the machine shop can-not produce a negative number of fastening pins of either type. Therefore:

X1 >= 0

X2 >= 0

Exhibit 16-10 summarizes the complete LP problem for AeroTech machine shop. So far, the procedure has been the same as for the graphical method described at the beginning of this chapter. Now, six additional steps, known as the simplex algorithm, are performed to arrive at an optimal solution. .

 Exhibit 16 -10  Summary of the Linear Programming Problem for AeroTech Machine Shop

Choose production levels for Type 1 pins (X1) and Type 2 pins (X2)

max Z = $9X1 + $7X2

Objective function

and satisfy the following

10X1 + 5X2 <=

50

(lathe A time constraint)

6X1 + 6X2 <=

36

(lathe B time constraint)

4.5X1 + 18X2 <=

81

(grinder G time constraint)

X1 >=

0

(sign restriction)

X2 >=

0

(sign restriction)

STEP 5: CONVERT THE LP TO STANDARD MATRIX FORM. Before solving a problem using the simplex algorithm, the objective function and constraints must be placed in standard matrix notation, and inequalities must be removed through the use of slack variables. To eliminate the inequalities present in the three time constraints of Exhibit 16-10, the slack variables X3, X4, and X5 are introduced. They replace each inequality with an equals sign  

10X1

+

5X2 

+ X3

=

50

(lathe A)

6X1 

+

6X2

+ X4

=

36

(lathe B)

4.5X1 

+

18X2

+ X5    =

81

(grinder G)

The physical meaning of the slack variables in the AeroTech problem is the remaining spare machine time given a particular solution for X, and X2. Ideally, given an optimum solution, X3, X4, and X5 would all be zero, but this is seldom the case. For our purposes here, however, the slack variables merely provide a con­venient way of converting inequalities to equalities.

This standard matrix notation for an LP objective function is:

max Z = [c][x]

where [c] contains the coefficients in the objective function (all slack variable coefficients are zero). The objective function must satisfy:

[A][x] = [b]

[x] >= 0

[b] >= 0

where [x] is the variable vector, [A] is the matrix of constraint coefficients for the variables, and [b] is the right-hand side vector from the constraint equation.

To complete step 5, the AeroTech LP problem is presented in its standard matrix form:

max Z = [c][x]

=

What does sliding an objective function line toward the origin represent away from the origin?

and satisfy:

[A][x] = [b]

What does sliding an objective function line toward the origin represent away from the origin?
 

One should make certain that the original objective function and constraints from these matrices can be recreated. Also, notice that matrix [A] is row-reduced, a necessary condition of the standard form for the simplex method.

STEP 6: PREPARE THE FIRST TABLEAU. The following matrix, called a tableau, is associated with the solution:

[A]

[b]

[c*][A]-[c]

[c*][b]

> value of the objective function

Simplex indicators

Simplex Indicators

The matrix [A] and the vectors [b] and [c] were defined in step 5. The vector [c*] is a subset of [c] contain­ing the coefficients of the variables that are currently defined by elementary columns in matrix [A]. For the initial tableau, the initial slack variables' coefficients are in [c*]. This will become clearer as the simplex tableau of Exhibit 16-11 is filled in.

Two columns have been added to the left-hand side of the tableau in the exhibit. The leftmost column sim­ply indicates which decision variables are currently elementary. Across the table from each of these vari­ables, one finds the value of 1 in an elementary column in [A]. The same variable appears at the top of that elementary column.

The next column from the left contains the values of [c*]. In this first tableau, the variables in the leftmost column are just the slack variables. In [c], the slack variables all have coefficients of zero, so in this first tableau, the subset vector [c*J is:

[c*] = [0 0 0]

The operations [c*] [A] - [c] and [c*] [b] can now be carried out, as shown in the exhibit, and the rest of the tableau completed. The portion of the tableau corresponding to [c*] [b] contains the value of the objective function (the profit, or Z, in this case) for the current solution.

The portion of the tableau corresponding to [c*] [A] - [c] contains the simplex indicators for the current solution. Simplex indicators show in each column how much Z will decrease per unit increase of the vari­able. These indicator numbers are vital for the next four steps of the simplex algorithm.

STEP 7: CHECK TO SEE IF THE CURRENT SOLUTION IS MAXIMAL. If no simplex indicator is negative, the solution is maximal, and the algorithm terminates. The values of the decision variables and the objective function can be read directly from the table. The optimization is complete.

 Exhibit 16 -11  Preparation of the First Simplex Tableau for the AeroTech Problem

[c*]

X1

X2

X3

X4

X5

[b]

X3

0

10

5

1

0

0

50

X4

0

6

6

0

1

0

36

X5

0

4.5

18

0

0

1

81

[c] = [9 7 0 0 0]         [c*] = [0 0 0]

[c*] [A] - [c] = [0 0 0]

What does sliding an objective function line toward the origin represent away from the origin?
- [9 7 0 0 0]

= [0 0 0 0 0] - [9 7 0 0 0]

= [-9 -7 0 0 0]

[c*][b] = [0 0 0]

What does sliding an objective function line toward the origin represent away from the origin?
  = 0

[C*]

X1

X2

X3

X4

X5

[b]

Quotients

X3

10

10 pivot entry

5

1

0

0

50

50/10 = 5

Minimum quo­tient (pivot row)

X4

0

6

6

0

1

0

36

36/6 = 6

X5

0

4.5

18

0

0

1

81

81/4.5 = 18

-9

-7

0

0

0

0

Pivot column

STEP 8: CHECK TO SEE IF NO MAXIMAL SOLUTION EXISTS. If some simplex indicators are negative, and no entry in that column is positive, there is no maximal solution, and the algorithm termi­nates. Either there is an inconsistency in the constraints of the LP problem, or the feasible region is unbounded. In either case, the LP problem cannot be optimized as formulated.

STEP 9: CREATE A NEW TABLEAU TO FIND A BETTER SOLUTION. Another tableau will be created that proceeds from the basic solution of the first tableau to another solution that might satisfy steps 7 or 8. This iteration is performed by pivoting matrices in the current tableau and reevaluating the simplex indicators.

STEP 10: REPEAT STEP 9 UNTIL EITHER STEP 7 OR STEP 8 IS SATISFIED. The simplex algo­rithm is iterative. Recalling the graphical approach to optimizing an LP problem, the simplex algorithm simply proceeds around the perimeter of the feasible region, stopping at corner points along the way to test for optimality. A new tableau is associated with each corner point.

To continue with the AeroTech problem, the bottom of Exhibit 16-11 should be revisited. Two of the sim­plex indicators are negative; therefore, step 7 is not satisfied. There is at least one positive value in the col­umns above these negative indicators, so step 8 is not satisfied. Therefore, we must proceed to step 9 and generate a new tableau.

To create the new tableau, an entry in the current tableau is selected about which to pivot. First, the most negative simplex indicator having a positive value above it in [A} is selected (-9 in the exhibit). In essence, the greatest negative value indicates which variable will increase Z by the greatest rate. The col­umn above this indicator is the pivot column.

Second, for each positive entry in the pivot column in [A], the entry in [b] on that row is divided by the entry in the pivot column of [A], and the resulting quotient is noted (three such quotients are shown in the exhibit, one for each row of [A]). Each of these quotients is the largest value the pivot column variable can be without exceeding the constraint of that row.

Finally, the smallest of these quotients is determined. It indicates the largest value of the pivot column variable that is assured of not violating any constraints. The row corresponding to this quotient is the pivot row. The pivot entry is at the intersection of the pivot row and the pivot column (the circled 10 is the pivot entry in the exhibit).

Exhibit 16-12 shows the second tableau for AeroTech. Since [c*] is not needed beyond the first tableau, the leftmost columns are omitted. To create this second tableau, the entire first tableau is transformed by the pivoting process described earlier. This pivoting also affects the entire last row of the tableau, and the right-hand column. All values in the pivot row are divided by the pivot entry, which leaves a 1 in the pivot position. Then, multiples of the resulting pivot row are subtracted from the tableau's other rows to leave zeros in the pivot column.

Once again, the second tableau does not satisfy steps 7 and 8, so a third tableau must be generated, starting with the selection of a pivot entry. The only negative simplex indicator in the exhibit is -2.5, so that col­umn becomes the pivot column. Recomputing the three quotients and finding their minimum results in the second row being chosen as the pivot row. The pivot entry (3) is circled.

Exhibit 16-13 shows the third tableau produced by pivoting the second tableau around its pivot entry. Note that in the third tableau, none of the simplex indicators are negative, satisfying step 7 of the algorithm. Therefore, this tableau represents an optimal solution to the AeroTech problem, and no further iterations are necessary.

The solution values in the tableau in Exhibit 16-13 are read as follows. First, the objective function (Z) value from the lower right corner of the tableau is read, in this case, 50. AeroTech can expect to make a profit of $50 from the optimal production run. But what is this optimal production run? How many fasten­ing pins of Types 1 and 2 should be produced? This question is answered in the rightmost [b] column of the tableau.

 Exhibit 16 -12  The Second Simplex Tableau for the AeroTech Problem

X1

X2

X3

X4

X5

[b]

1

0.5

0.1

0

0

5

0

3

-0.6

1

0

6

0

15.75

-0.45

0

1

58.5

0

-2.5

0.9

0

0

45

X1

X2

X3

X4

X5

[b]

Quotients

1

0.5

0.1

0

0

5

5/0.5 = 10

0

3 Pivot entry

-0.6

1

0

6

6/3 = 2

Minimum quotient (pivot row)

0

15.75

-0.45

0

1

58.5

58.5/15.75 = 3.7

0

-2.5

0.9

0

0

45

Pivot column

First, find the elementary columns in [A] of the third tableau. Then, note the decision variables to which these columns correspond and the row on which each column's 1 is located. For instance, the first column of the tableau is elementary and corresponds to the variable X1. This column has a 1 in the first row. It is now possible to read across this row to the far right. The value of 4 appears in the first row of [b], meaning that four lots of pin Type 1 should be produced.

Similarly, the value of 2 appears in the second row of [b], meaning that two lots of pin Type 2 should be produced. The value of 27 in row three of [b] means that 27 hours of unused (slack) time remain on grinder G because the third elementary column corresponds to X5. Having completed the LP problem, AeroTech's owner can now run the machines to this optimal schedule.

Sensitivity Analysis

When an optimal solution is reached, management would often like to know how the optimal values would react to a change in the initial formulation of the LP problem, but it is not practical to rework the entire problem for each possible change. Fortunately, the information can be obtained directly through an analyti­cal approach called sensitivity analysis (also referred to as postoptimality analysis). Sensitivity analysis basically looks at the question of “what if” a variable is different from that originally estimated. The wide­spread use of computers has made sensitivity analysis a common extension of linear programming. Most linear programming computer packages include the results of sensitivity analysis as a part of the normal printout.

 Exhibit 16 -13  The Third and Final Simplex Tableau for the AeroTech Problem

X1

X2

X3

X4

X5

[b]

1

0

0.2

-0.167

0

4

0

1

-0.2

0.33

0

2

0

0

2.7

-5.2

1

27

0

0

0.4

0.833

0

50

No simplex indicator is negative. Therefore, Maximal.

X1

X2

X3

X4

X5

[b]

1

0

0.2

-0.167

0

4

Solution for Xt (4 lots)

0

1

-0.2

0.33

0

2

Solution for X2 (2 lots)

0

0

2.7

-5.2

1

27

Solution for X5 (27 hours)

0

0

0.4

0.833

0

50\

Profit ($50)

Optimal solution

Shadow Prices

A shadow price represents the change in the objective function that would result from the addition or reduction of one unit of a resource, such as machine time or labor time. Shadow pricing, a form of sensi­tivity analysis, shows how sensitive the optimal value of the objective function would be to adding or reducing resources. For example, is it worthwhile to pay workers an overtime rate? If the increase in over­time pay is $1,000 and results in an increase of $800 in the optimal objective function, the addition of overtime work is not worthwhile.

The shadow price “value” of adding one additional unit of a resource can be readily determined by exam­ining the last row of the final tableau. Each value is the shadow price for that variable. For example, as shown in Exhibit 16-13, the shadow price of slack variable X, is 0.4. Since slack variable X3 is directly associated with constraint 1, this means that a one-hour increase in Lathe A's time would result in an increase in Z of $0.40.

USING THE SIMPLEX METHOD TO SOLVE MINIMIZATION PROBLEMS

In the preceding discussion of maximization problems using the simplex algorithm, the constraints were of the following form:

[E][x] <= [b]

[x] >= 0

[b] > = 0

where [E] contains the constraint coefficients for the variables, not including slack variables.

The first simplex tableau could be formed around the subset vector [e*] = 0, which relates to starting at the origin in a graphical plot of the feasible region. Most maximization problems will fit this form nicely, but the majority of minimization problems will not contain the origin as a feasible point. They often have con­straints of the following form:

[E][xl  >= [b]

A quick review of Exhibit 16-2 (a maximization problem) shows that the origin (0, 0) is a corner point of the feasible region, but in Exhibit 16-7 (a minimization problem) the origin is outside the feasible region. Thus, such a simplex minimization problem cannot be started from the origin because it is not a feasible point.

To overcome this difficulty, a modification of simplex called the two-phase procedure is employed. The first phase of this procedure uses subtracted slack variables plus additional artificial variables to find a corner point of the feasible region and to produce a tableau based on that point. The second phase then drops the artificial variables and uses the feasible point to optimize the LP problem similar to the way described for the LP maximization problem.

An additional concern with all minimization problems is the evaluation of the simplex indicators. Whereas negative indicators were sought in the maximization problem for AeroTech machine shop, positive indica­tors are looked for in a minimization problem. The maximum simplex indicator in a minimization problem indicates the variable that will reduce Z at the greatest rate. The pivot column will contain a positive indi­cator, but the pivot row will be determined exactly as before.

A Simplex Minimization Example

Consider the following LP problem, which was solved graphically as the K9 Kondo Company problem earlier in this chapter:

min Z = $200X + $50Y

subject to the following:

6X+ 3Y >= 60

2X+ 3Y >= 36

X >= 0

Y >= 0

Phase One of the Two-Phase Procedure

First, the problem is converted to standard matrix form by subtracting the slack variables J and K from the constraints. Then, the artificial variables M and N are added to produce the following equality constraints:

What does sliding an objective function line toward the origin represent away from the origin?
 

For phase one, a “rigged” objective function is used, which contains only the artificial variables. The use of these artificial variables and the rigged objective function may seem strange and, for the purposes here, will have to be taken on faith. In matrix form, the rigged objective function is:

min Z = [a] [x]

= [0 0 0 0 1 1]

What does sliding an objective function line toward the origin represent away from the origin?

The first tableau is at the top of Exhibit 16-14. The vector [a*] contains the coefficients of the artificial variables from the rigged objective function since the artificial variables are defined by the elementary col­umns in matrix [A]. The simplex indicators are then computed, and the value of the objective function is determined as shown.

Because this is a minimization problem, the highest value positive simplex indicator is selected to deter­mine the pivot column; in this case, 8 is chosen. As before, the quotients for this tableau are computed, and the minimum quotient is chosen as the pivot row. Again, the minimum quotient value indicates the largest value the pivot column variable can be without violating any of the constraints. The pivot entry, in this case 6, is circled.

Pivoting twice yields the tableau at the bottom of Exhibit 16-14. Because there are now no positive sim­plex indicators, phase one is completed. The value of the objective function in the lower right corner of the tableau gives valuable information. In the tableau, this value is zero, indicating that there is a solution to the problem if one wishes to proceed with phase two. If the value were nonzero, no solution to the LP problem would exist, and the process would not be continued.

Phase Two of the Two-Phase Procedure

Phase one found a corner point in the feasible region that permits the simplex method to optimize the mini­mization LP problem. Exhibit 16-15 shows the first tableau of phase two. The columns of [A] correspond­ing to the artificial variables M and N are simply deleted and the rows are reordered, if necessary, so the l's of the elementary columns are in the same order as the objective function coefficients. The original objec­tive function is, of course, restored to read in matrix form.

 Exhibit 16 -14  Tableau Associated with Phase One of the Two-Phase Simplex Minimization Problem

Artificial Slack Variables

[a*]

X

Y

J

K

M

N

[b]

M

1

6

3

-1

0

1

0

60

N

1

2

3

0

-1

0

1

36

[a]=[0 0 0 0 1 1]   [a*]=[1 1]

[a*] [A]-[a] = [1 1]

What does sliding an objective function line toward the origin represent away from the origin?
-[0 0 0 0 1 1]

= [8 6 -1 -1 1 1] - [0 0 0 0 1 1]

= [8 6 -1 -1 0 0]

 [a*] [b] = [1 1]

What does sliding an objective function line toward the origin represent away from the origin?
= 96

[a*]

X

Y

J

K

M

N

[b]

Quotients

M

1

6 (pivot entry)

3

-1

0

1

0

60

60/6 = 10

Minimum Quo­tient (pivot row)

N

1

2

3

0

-1

0

1

36

36/2 = 18

8

6

-1

-1

0

0

96

Pivot col­umn

X

Y

J

K

M

N

[b]

Quotients

1

0.5

-0.167

0

0.167

0

10

10/0.5 = 20

0

2 (Pivot entry)

0.333

-1

-0.333

1

16

16/2 = 8

Minimum Quotient (pivot row)

0

2

0.333

-1

-1.333

0

16

Pivot column

X

Y

J

K

M

N

[b]

1

0

-0.25

0.25

0.25

-0.25

6

0

1

0.167

-0.5

-0.167

0.5

8

0

0

0

0

-1

-1

0

< The Value is zero, therefore a solution to the LP exists.

 Exhibit 16 -15  Creation of the First Tableau in Phase Two of the Simplex Minimization Problem

[c*]

X

Y

J

K

M

N

[b]

X

200

1

0

-0.25

0.25

0.25

-0.25

6

V

50

0

1

0.167

-0.5

-0.167

0.5

8

[c] = [200 50 0 0]    [c*] = [200 50]

[c*] [A] - [c] =[200 50]

What does sliding an objective function line toward the origin represent away from the origin?
  - [200 50 0  0]

= [200 50 -41.65 25] - [200 50 0 0]

= [0 0 -41.65 25]

[c*] [b] = [200 50]

What does sliding an objective function line toward the origin represent away from the origin?
= 1,600

[c*]

X

Y

J

K

[b]

X

200

1

0

-0.25

0.25 Pivot entry

6

YI

50

0

1

0.167

-0.5

8

0

0

-41.67

25

1 600

Pivot column

min Z = [c] [x]

= [200 50 0 0]

What does sliding an objective function line toward the origin represent away from the origin?

Noting that the elementary columns in [A] correspond to the variables X and Y, the subset vector [c*] can be determined and the simplex indicators recalculated as shown in the exhibit. This leaves the complete first tableau of phase two shown at the bottom. Note that the leftmost Z columns have been eliminated from the tableau including the [a*] column. Also, note that no row ordering was necessary since the i's of the elementary column were in the same order as the objective function coefficients.

There is one positive simplex indicator in the tableau, which is 25. In the [A] column above this indicator, there is only one positive value, 0.25, which automatically becomes the pivot value. In this case, it is not necessary to compute quotients to determine the pivot row because there is only one positive pivot column value to choose from. Exhibit 16-16 shows the second tableau obtained by pivoting the first.

 Exhibit 16 -16  The Second and Final Tableau in Phase Two of the Simplex Minimization Problem

X

Y

J

K

[b]

4

0

-1

1

24 (Solution for K)

2

1

-0.333

0

20 (Solution for Y)

-100

0

-16.67

0

1000   Z

No simplex indicator is positive. Minimal

Use the second constraint:

2X + 3Y + 0J = 36

to obtain a solution for X:

2X + 3 (20) + 0 - 1 (24) = 36

X = 0

All simplex indicators are nonpositive so the solution is now minimized and the simplex algorithm termi­nates. The location of the elementary columns in this tableau should be studied. The number 24 in [b] is the optimal value of the slack variable K. The number 20 in [b] is the optimal value of the decision variable Y. The tableau provides no value for the decision variable X, so its optimal value is zero. Finally, the value of the objective function is 1,000 (or $1,000,000). Note that the simplex solution is the same as that found graphically earlier in the chapter for the K9 Kondo Company problem.

THE LINDO COMPUTER PACKAGE

If the use of linear programming in industry has been restricted, it has been because of two difficulties: (1) the cost of collecting the necessary input data and (2) the cost of solving large LP problems. The first of these roadblocks is being removed as many firms develop integrated information and database systems. Since the solution of LP problems is purely mechanical, these problems are best assigned to the computer. Therefore, rapid reductions in the cost of computer hardware are removing the second roadblock.

Of course, computers require software to solve problems. Probably the most common specialized linear programming software package used in the early days was LINDO3, an acronym for Linear INteractive Discrete Optimizer. LINDO is most at home running on a mainframe or minicomputer. Ultimately, how­ever, LINDO was superceded by Excel and Lotus 123 when they adopted the Karmarker method in about 1998. The Solver in Excel uses the Karmarker method even though the Excel documentation does not refer to the Solver as a LP tool.

SOLVING LINEAR PROGRAMMING PROBLEMS WITH KARMARKAR'S METHOD

Prior to 1984, most scientists and mathematicians thought that the simplex method was as far as they could go. A number of relatively easy-to-use decision support packages based on the simplex method have been available for years. Even when LP problems are not terribly complex, however, solving them can chew up so much computer time that the answer is useless before it is found.

In November 1984, a 28-year-old mathematician named Narendra Karmarkar announced he had discov­ered a quick way to solve problems so hideously complicated that they often defied even the most power­ful supercomputers. Fittingly, Karmarkar worked at Bell Laboratories, the home of the first transistors, the devices that made computerization possible in the first place. Karmarkar's discovery is loaded with signif­icance.

Testing has shown that Karmarkar's method is many times faster than the classic simplex method. An implementation of Karmarkar's method outperformed one implementation of the simplex method by a fac­tor of over 50 on medium-scale problems of 5,000 variables. AT&T (Bell Labs' parent) sold the first soft­ware product based on Karmarkar's method to the US Air Force's Military Airlift Command (MAC).

On a typical day, thousands of Air Force planes ferry cargo and passengers among airfields scattered around the world. Determining how to fly various routes, deciding which aircraft should be used, and scheduling pilots and ground personnel are the primary functions of the MAC. Getting all the pieces to play together is a classic challenge in linear programming. In fact, the MAC's LP problem contains upward of 150,000 variables and 12,000 constraints. If a computer could wring out just a couple of per­centage points of added efficiency, it would be worth millions of dollars. Karmarkar's method has enabled the MAC to do just that. In fact, the most common software for scheduling classes at colleges and universi­ties uses this method to develop schedules which match rooms, teachers and students.

Improving on the Simplex Method

How does Karmarkar's method work? A common analogy compares an LP problem to a geodesic dome. In the graphical problems of this chapter, two-dimensional feasible regions were plotted on the x and y axes. The simplex examples had two variables and therefore had two-dimensional feasible regions. Since the addition of each new variable adds another dimension to the feasible region, LP problems with three vari­ables are difficult, and problems with four or more variables are impossible to visualize graphically. There­fore, it helps to think of the feasible region of an LP problem as a geodesic dome in multiple dimensions.

Each of the dome's corners is a possible solution. The task is to find which one holds the best solution. With the simplex method, the program “lands” on one corner and inspects it. Then it scouts the adjacent corners to see if there is a better answer; if so, it heads off in that direction. The procedure is repeated at every corner until the program finds itself boxed in by worse solutions.

Karmarkar's method employs a radically different tactic. It starts from a point within the multidimensional feasible region and finds the optimal solution by taking a shortcut that avoids the tedious surface route. From this interior point, the region is “projected” to reconfigure its shape. Then, the method determines in which direction the solution lies. Finally, the problem structure is allowed to return to its original shape, and the program jumps toward the solution, pausing at intervals to repeat the exercise and hone in on the answer4.

New Solutions to Old Problems

Karmarkar's method applies to a variety of commercial problems5. An airline trying to coordinate schedul­ing efficiently is one example. An energy producer managing the movement of oil among ships, storage tanks, and refineries is another. Yet another example is the classic LP problem of locating distribution cen­ters geographically for a manufacturing firm. In truth, answering most of what are termed “what-if” ques­tions involves simulation, backed up by linear programming.

Perhaps the greatest benefits will be in the use of simulation for everyday operations6. Problems that used to take hours of expensive time on the corporate mainframe can now be performed in minutes, or possibly even performed on a desktop PC in a short time. These benefits can only be a boon to productivity and cost management.

SUMMARY OF LEARNING OBJECTIVES

The major goals of this chapter were to enable you to achieve four learning objectives:

Learning objective 1. Explain linear programming and its components and assump­tions.

Linear programming consists of a sequence of steps that lead to an optimal solution to a class of problems dealing with the allocation of scarce resources. There are three popular linear programming methods:

• Graphical method

• Simplex method

• Karmarkar's method

All LP problems are composed of four components:

• Objective function

• Decision variables

• Constraints

• Feasible region

The objective function deals with two types of objectives:

Maximization of such things as profits, revenue, or productivity

Minimization of such things as cost, time, or scrap

Decision variables are simply choices available to management in terms of the amount of input or output. Constraints are limitations that restrict alternatives available to management. Together, the constraints define the set of all feasible combinations of decision variables, which is called the feasible region. LP methods (graphical, simplex, or Karmarkar) systematically search the feasible region for the combination of decision variables that will yield an optimal solution in terms of the objective function.

To use linear programming effectively, certain assumptions must be satisfied:

Linearity. All functions, such as costs, prices, and technological requirements, must be linear in nature.

Certainty. All parameters are assumed to be known with certainty.

Nonnegativity. Negative values of decision variables are unacceptable.

Learning objective 2. Describe the graphical method, and apply it in solving both maximization and minimization linear programming problems.

The graphical method is used to find optimal solutions for two-variable LP problems. This method involves plotting the constraints on a graph and identifying the feasible region.

The optimal solution for a maximization problem is found by moving the objective function, which is an isoprofit line, away from the origin until it intersects the extreme corner point of the feasible region, which is a polygon. The optimal solution occurs where the isoprofit line intersects the extreme corner point, or where the isoprofit line overlays one of the boundaries.

Graphical minimization problems are similar to maximization problems except for two differences. One is that the constraints are usually of the “greater than or equal to” kind rather than “less than or equal to.” This difference causes the feasible region to be outside the polygon instead of inside. The other difference is that the objective is to minimize something, such as cost. The optimum corner point is found by moving the objective function, which is an isocost line, toward the origin rather than away from it.

Learning objective 3. Describe the simplex method, and use it in solving both maxi­mization and minimization linear programming problems.

Most real-world LP problems have more than two variables and are therefore too complex for the graphi­cal method. The simplex method is a general-purpose algorithm that is widely used to solve multivariable and multiconstraint LP problems.

With the simplex method, a series of iterations is conducted until an optimal solution is found. Often, the iterations and computations can become overwhelming and thus call for the use of computer software packages, such as LINDO. Still, some familiarity with manual calculations is useful in understanding how the simplex algorithm works.

Learning objective 4. Discuss Karmarkar's method of solving linear programming problems.

The most significant change in linear programming solution methods is Karmarkar's method. This rela­tively new method often takes considerably less computer time to solve very large LP problems.

The simplex method's algorithm discovers a solution by moving from one adjacent corner point to the next, following the outside edges of the feasible region. Alternatively, Karmarkar's method takes a short­cut by following a path of points on the inside of the feasible region. Although the simplex method will likely continue to be used for many LP problems, software that supports Karmarkar's method is already being used by a number of companies as well as federal government agencies.

IMPORTANT TERMS

Constraint A limit to the degree to which an objective can be pursued.

Decision variables Represent choices available to decision makers in terms of amounts of either inputs or outputs.

Elementary column A matrix column containing a single one (1) in any position, with the remaining col­umn entries being zeros.

Feasible region A feasible solution space that contains the set of all possible combinations of decision variables.

Graphical method An approach to optimally solving LP problems involving two decision variables and a limited number of constraints.

Isocost lines A set of parallel lines that represent the objective function of an LP problem. They indicate constant amounts of cost at various solution values. They are used to solve an LP minimization problem graphically.

Isoprofit lines A set of parallel lines that represent the objective function of an LP problem. They indicate constant amounts of profit at various solution values. They are used to solve an LP maximization problem graphically.

Karmarkar's method An approach to optimally solving large-scale LP problems efficiently. It starts from a point within the multidimensional feasible region and finds the optimal solution by taking a shortcut that avoids the tedious surface route of the simplex method.

Linear equation An algebraic equation whose variable quantity or quantities are in the first power only and whose graph is a straight line.

Linear programming (LP) An application of matrix algebra used to solve a broad class of problems that can be represented by a system of linear equations. It is used to determine the best allocation of multiple scarce resources to achieve an optimal solution. Matrix A rectangular array of numbers having m rows and n columns; it is typically contained in brackets.

Objective function The linear mathematical equation that states the objective of an LP problem. The major objective of a typical enterprise is to maximize profits or minimize costs.

Optimal solution The solution to an LP problem that provides the best answer to the objective function.

Pivoting The key iterating process of the simplex algorithm.

Rank The number of nonzero rows in a matrix.

Row-reduced form A matrix in which the number of elementary columns is equal to the rank of the matrix.

Scalars Single numbers or variables used to identify single numbers. It is a quantity that has magnitude but no direction in space.

Sensitivity analysis (postoptimality analysis) An analysis that projects how much a solution might change, given changes in the variables.

Shadow price The value of one additional unit of a resource in the form of one more hour of machine time or labor time or other scarce resource in linear programming.

Simplex method An approach to optimally solving multivariable, multiconstraint LP problems. The sim­plex method applies an algorithm iteratively to locate feasible corner points in a systematic fash­ion until it arrives at the best solution (i.e., the highest profit or lowest cost).

Slack variables Represent the amount of each resource that will not be used if the solution is imple­mented. Under the simplex method, constraints (inequalities) are converted to equations (equali­ties) by adding slack variables. Slack variables are always nonnegative.

Tableau A table or matrix of the coefficients used in the problem equations. It represents a solution of the simplex algorithm in tabular form. By inspecting the bottom row of each tableau in a series of tab­leaus, one can immediately tell if it represents the optimal solution. Each tableau corresponds to a corner point of the feasible region. The initial tableau corresponds to the origin. Subsequent tab­leaus are developed by shifting to an adjacent corner point in the direction that yields an optimal solution.

Vector A type of matrix having either an m dimension of 1 (row vector) or an n dimension of 1 (column vector).

DEMONSTRATION PROBLEMS

DEMONSTRATION PROBLEM 1 Developing a linear programming problem.

The Marlowe Company manufactures and sells two products, A and B. Demand for the two products has grown to such a level that Marlowe can no longer meet the demand with its present resources. The com­pany can work a total of 800,000 direct labor hours (DLhr) annually using three shifts. A total of 250,000 hours of machine time is available annually. The unit sales price for product A is $49.90. The unit sales price for product B is $84.50. The company plans to use linear programming to determine a master produc­tion schedule that maximizes its contribution margin. Overhead is assigned on a machine hour (Mhr) basis. The unit production requirements and unit cost data follow:

Product A

Product B

Raw materials

$ 4

$ 8

Direct labor

1 DLhr @ $6

6

2 DLhr @ $6

12

Variable overhead

0.5 Mhr @ $16

8

2 Mhr @ $8

16

Fixed overhead

1.5 Mhr @ $10

15

3 Mhr @ $10

30

Required:

a. Develop the objective function that will maximize Marlowe's contribution margin (CM).

b. Develop the constraint function for the direct labor.

c. Develop the constraint function for the machine capacity.

SOLUTION TO DEMONSTRATION PROBLEM I

a. The objective function that will maximize Marlowe's total contribution margin (CM):

max CM = 31.90A + 48.50B

The total variable unit cost of product A is $18 ($4 raw materials + $6 direct labor + $8 variable over­head). The CM is $31.90 ($49.90 unit sales price - $18 variable cost). Similarly, the total variable unit cost of product B is $36 ($8 raw materials + $12 direct labor + $16 variable overhead), and the CM is $48.50 ($84.50 unit sales price - $36 variable cost). Thus, the objective function should maximize the total CM from both products.

b. The constraint function for the direct labor is:

A + 2B <= 800,000

Because 800,000 direct labor hours are available, the function must be equal to or less than 800,000. Every unit of product A requires 1 hour of direct labor, and every unit of product B requires 2 direct labor hours.

c. The constraint function for the machine capacity is:

0.5A + 2B  <= 250,000

Because 250,000 hours of machine time are available, the function must be equal to or less than 250,000 machine hours. Every unit of product A requires 0.5 hours, and every unit of product B requires 2 hours.

DEMONSTRATION PROBLEM 2 Using the graphical method to solve a maximization LP problem.

Office Designs manufactures and sells two kinds of desktop pen and pencil sets. The Executive (E) is a high-quality set, while the Clerical (C) is of somewhat lower quality. The contribution margin (CM) is $8 for each Executive set. sold and $2 for each Clerical set sold. Each Executive set requires twice as much manufacturing time as is required

for a Clerical set. If only Clerical sets are made, the company has the capacity to manufacture 1,200 sets daily. Enough pen and pencil components are available to make 800 sets daily of Executive and Clerical combined. Executive requires a special marble pedestal, of which only 500 per day are available. Clerical requires a metal pedestal, of which 700 per day are available. The company can sell all the Executive and Clerical sets that it produces.

Required:

a. Formulate the problem.

b. Use the graphical method to find the optimal solution.

c. Management wants to know what the optimal solution will be if the number of available marble pedes­tals is reduced to 400 Prepare a graph showing this postoptimal solution.

SOLUTION TO DEMONSTRATION PROBLEM 2

a. The objective function maximizes the total contribution margin (CM), where the CM is $8 for each Executive (E) set and $2 for each Clerical (C) set. Therefore, the objective function for Office Designs is:

max CM = 8E + 2C

Certain constraints exist. First, only enough manufacturing time is available to produce 1,200 sets of C, if only C is made. It takes twice as much manufacturing time to produce E. The company does not have to use all its manufacturing capacity. The first constraint is stated as:

2E + C <= 1,200

Second, enough pen and pencil components are available to produce 800 desktop sets of any combination daily. This constraint is stated as:

E + C <= 800

Third, the pedestals for each set are also limited in supply. Only 500 marble pedestals are available daily to make E, and only 700 metal pedestals are available daily for C. Mathematically, these two constraints become:

E <= 500

C <= 700

Finally, although it's common sense, for mathematical completeness, the following nonnegativity con­straints are necessary:

E >= 0

C >= 0

Putting all the preceding material together, the LP problem is formulated as:

max CM = 8E + 2C where

2E + C <= 1,200

E + C <= 800

       E <= 500

       C <= 700

         E >= 0

         C >= 0

b. Because there are only two variables, this LP problem lends itself to the graphical method. The con­straints are graphed first because they will determine what solutions to the problem are possible. The feasi­ble solution boundaries are obtained by graphing the inequalities as if they were equalities and then noting where the solution must lie relative to the equation. For example, the first constraint, 2E + C 1,200 is graphed as 2E + C = 1,200. If C = 0, 2E = 1,200, and E = 600. If E = 0, C = 1,200. Thus, the end points that are used to draw the 2E + C < 1,200 constraint line are E = 600 and C = 1,200. This constraint line as well as all the others are shown in the following graph. When all constraints are simultaneously enforced, the shaded area results. This area is the feasible region. It represents the set of all feasible solutions to Office Designs' LP problem.

The CM equation can now be graphed. To do this, various levels of CM may be assumed; for example, $2,400 and $3,200. As the CM level is increased, the isoprofit lines (the dashed lines in the graph) will shift away from the origin. As the graph makes clear, the maximum CM level will occur at a corner point of the feasible region. This will always be the case. It is possible, however, that the maximum isoprofit line could be parallel to a constraint line. In such a case, both corners of the constraint as well as all the points on the constraint line would represent optimum solutions. Normally, a unique optimum occurs at a single point (vertex), as is the case with Office Designs.

Graphical Solution to Office Designs' LP Problem:

What does sliding an objective function line toward the origin represent away from the origin?

To confirm the preceding discussion, the optimal solution is determined by evaluating all corner points of the feasible region, as numbered in the graph. This evaluation is presented as follows:

CORNER­POINT

E, C Coordinates

CM = 8E + 2C

1

0,0

$8(0) +

$2(0) =

$-0-

2

500, 0

$8(500) +

$2(0) =

$4,000

3

500, 200

$8(500) +

$2(200) =

$4,400

4

400,400

$8(400) +

$2(400) =

$4,000

5

100, 700

$8(100) +

$2(700) =

$2,200

6

0, 700

$8(0) +

$2(700) =

$1,400

The total CM is maximized at $4,400, with 500 Executive and 200 Clerical desktop pen and pencil sets being produced. This maximum profit is represented by the isoprofit line that intersects corner point 3.

c. Once the optimal solution is reached, it is important to know how the solution will change based on a change in the initial formulation. This is achieved by employing sensitivity or postoptimality analysis. In the case of Office Designs, management wants to know what the optimal solution will be if the number of marble pedestals is reduced to 400. Such a change causes the original constraint line E ~ 500 to shift left­ward, reducing the feasible region, as shown in the following graph. The revised optimal solution occurs at corner point 4, where 400 sets of E and 400 sets of C are the optimum number of sets to produce. The total CM at this corner point is $8(400) + $2(400) = $4,000. The total CM is less than could be made before, but it is still the best possible solution when the supply of marble pedestals is reduced to 400.

What does sliding an objective function line toward the origin represent away from the origin?

DEMONSTRATION PROBLEM 3 Using the graphical method to solve a minimization LP problem.

Moran Chemicals produces two types of chemicals:

• Insecticide A

• Herbicide B

Chemical A costs Moran $3,000 per ton; B costs $3,500 per ton. Moran's production superintendent has specified that at least 30 tons of A and at least 20 tons of B must be produced during the next month. More­over, the superintendent observes that an existing inventory of a highly perishable raw material needed in both chemicals must be used within 30 days. In order to prevent the loss of this expensive raw material, Moran must produce a total of at least 70 tons of chemicals next month.

Required:

a. Formulate the LP problem

b. Solve the LP problem graphically.

SOLUTION TO DEMONSTRATION PROBLEM 3

 a. Total cost (TC) = 3,000A + 3,500B

where

   A >= 30

   B >= 20

   A+B >= 70

   A >= 0

   B >= 0

b. To solve Moran's LP problem graphically, the following feasible region is constructed.Graph Showing Moran Chemicals' Feasible Region

What does sliding an objective function line toward the origin represent away from the origin?

The minimization LP problem is unbounded on the right side and on the top. As long as it is bounded inward, corner points can be determined. The optimal solution will always occur at one of the corner points, or along one of the boundary lines. In the case of Moran's LP problem, there are only two corner points, 1 and 2. At point 1, A = 50 and B = 20. At point 2, A = 30 and B = 40. The optimal solution is found at the point yielding the lowest total cost:

TC at point 1 = 3,000A + 3,500B

= 3,000(50) + 3,500(20) = 150,000 + 70,000 = $220,000

TC at point 2 = 3,000A + 3,500B

= 3,000(30) + 3,500(40) = 90,000 + 140,000 = $230,000

The lowest cost to Moran is at point 1, Thus, Moran should produce 50 tons of A and 20 tons of B.

DEMONSTRATION PROBLEM 4 Using the simplex method to solve a maximization LP problem.

Rock Fellow Oil Refinery refines crude oil into gasoline and diesel. Crude oil inputs to the refinery can be a maximum of 100 million barrels per quarter, and the maximum energy usage per quarter is 42 million BTUs. Historical statistics show that the maximum uptime for the refinery is 75 days per quarter. The die­sel process uses 2 million BTUs, which is twice as much energy as the gasoline process, and a diesel batch process takes only 3 days compared to 4 days for a gasoline batch. Each diesel and gasoline batch uses 4 million barrels and 10 million barrels, respectively. Each gasoline batch nets $50,000 and each diesel batch nets $60,000.

Required:

a. Formulate this maximization problem.

b. Use the simplex method to find the optimal solution.

SOLUTION TO DEMONSTRATION PROBLEM 4

a. The objective function maximizes the total net contribution (NC) where the net is

$60,000 for each diesel (D) batch and $50,000 for each gasoline (G) batch. Therefore, the objective func­tion for Rock Fellow is:

max NC = 60D + 50G

Three stated constraints exist. First, only 100 million barrels of crude oil can be input to the refinery. Since D uses 4 million barrels per batch and G uses 10 million barrels per batch, the first constraint can be stated as:

4D + 10G <= 100

Second, energy consumption is limited to 42 million BTUs. It takes twice as much energy to produce D as G. Thus, the constraint is:

2D + G <= 42

Third, crude oil can be refined only 75 days per quarter. Each D batch takes 3 days, and each G batch takes 4 days. Mathematically, this constraint is:

3D + 4G <= 75

Putting all this together, the LP problem is formulated as:

max NC = 60D + 50G

where

4D + 10G <= 100

2D +  G <= 42

3D + 4G <= 75

b. Setting up the first tableau, with the formulated problem from above, we have:

D

G

X1

X2

X3

[]b

4

10

1

0

0

100

2

1

0

1

0

42

3

4

0

0

1

75

-60

-50

0

0

0

0

where the bottom row is obtained by:

[c*] [A] - [c]

or

[0 0 0]

What does sliding an objective function line toward the origin represent away from the origin?
 - [60 50 0 0 0]

The bottom right corner is calculated as:

[c*] [b]

and since [e*] is all zeros, the resulting scalar is 0.

Now, since the bottom row has negative values, we need to find the pivot entry. Choosing the first column (D) as the pivot column since its simplex indicator is the most negative, we calculate the quotients (b/D) to determine the pivot row, as follows:

D

G

X1

X2

X3

[b]

b/D

4

10

1

0

0

100

100/4 = 25

2

1

0

1

0

42

42/2 = 21 (pivot row)

3

4

0

0

1

75

75/3 = 25

-60

-50

0

0

0

0

Pivot Column

Thus, the pivot value is the 2.

Pivoting around the 2, we generate the second tableau:

D

G

X1

X2

X3

[b]

0

8

1

-2

0

16

1

0.5

0

0.5

0

21

0

2.5

0

-1.5

1

12

0

-20

0

30

0

1,260

Note that as a result of the pivot, all values in the pivot column (D) are now 0, except for the 1 where the pivot value was.

Since the last row still has negative values, another pivot value must be determined, as shown:  

D

G

X1

X2

X3

[b]

b/D

0

8-

1

- 2

0

16

16/8 = 2 (pivot Row)

1

0.5

0

0.5

0

21

21/0.5 = 42

0

2.5

0

-1_5

1

12

12/2.5 = 4.8

0

-20

0

30

0

1,260

Pivot Column

Thus, the pivot value is the 8.

Pivoting around the 8, we generate the third tableau:  

D

G

X,

X2

X3

[b]

0

1

0.125

-0.25

0

2

1

0

-0.0625

0.625

0

20

0

0

-0.3125

-0.875

1

7

0

0

2.5

25

0

1,300

Note that as a result of the pivot, all values in the pivot column (G) are now 0, except for the 1 where the pivot value was. Also, note that the first pivot column (D) did not change.

Since there are no negative values in the last row, we have converged to a solution. The value in the bot­tom right corner is the maximum. In this case, the maximum net is $1,300,000. (Recall that the objective function used thousands of dollars.)

What is the product mix? We look to the D column for the lone value of 1, then look at the value in the rightmost column of that row-in this case, 20. This means that Rock Fellow should make 20 batches of diesel (D). Doing the same for G, we see a value of 2. Thus, Rock Fellow should make only 2 batches of gasoline (G).

In summary, the optimal solution is:

• $1,300,000 net per quarter

• 2020 diesel batches per quarter

• 2 gasoline batches per quarter

­ DEMONSTRATION PROBLEM 5 Using the simplex method to solve a minimization LP problem.

Given the following minimization problem:

min Z=21X+18Y

subject to:

5X + 10Y >= 100

2X + Y >= 20

Required:

Use the simplex method to find the optimal solution.

SOLUTION TO DEMONSTRATION PROBLEM 5 PHASE 1:

First, the tableau is generated by subtracting the slack variables and then adding artificial variables:

X

Y

S1

S2

A1

A2

[b]

5

10

-1

0

1

0

100

2

1

0

-1

0

1

20

7

11

-1

-1

0

0

120

The bottom row is calculated as follows:

[a*] [A] - [a]

where [a] is a vector of length [A] with only 1s for each of the artificial columns and [a*] has only is for the number of artificial columns of [A]. Thus, we have:

[1 1]

What does sliding an objective function line toward the origin represent away from the origin?
- [0 0 0 0 1 1]

which is essentially a summation of all the columns except the artificial columns. For the bottom right, the following is used:

[a*] [b]

which results in 120, again just the summation of the values of [b].

Now we pivot until all positive values are eliminated along the bottom row (except for the far right “opti­mization” value). If the far right value is not zero, a solution does not exist, and we would stop. The pivot­ing process for our problem is as follows: After the first pivot:  

X

Y

S1

S2

A1

A2

[b]

0.5

1

-0.1

0

0.1

0

10

1.5

0

0.1

-1

-0.1

1

10

1.5

0

0.1

-1

-1.1

0

10

After the second pivot:

X

Y

S1

S2

A1

A2

[b]

0

1

-0.133

0.333

0.133

-0.33

6.67

1

0

0.067

-0.667

-0.067

0.67

6 67

0

0

0

0

-1

-1

0

Now that the bottom row is nonpositive and the bottom right value is zero, a solution is assured, and we can proceed to phase 2.

PHASE 2:

Now a new first tableau is constructed, using the non-artificial values in the last phase 1 tableau and sort­ing the rows. The bottom row is calculated from scratch with now familiar maximization equations:

[c*] [A] - [c]

or

[21 18]

What does sliding an objective function line toward the origin represent away from the origin?
- [21 18 0 01

The bottom right corner is calculated as:

[c*][b]

or

[21 18]

What does sliding an objective function line toward the origin represent away from the origin?

The resulting first tableau is thus:

X

Y

S1

S2

[b]

1

0

0.067

-0.667

6.67

0

1

-0.133

0.33

6.67

0

0

-1.0

-8

260

if the bottom row contained any positive values, it would be necessary to pivot until all the values in the bottom row (excluding the bottom right value) were nonpositive, but that is not the case here.

Since all the bottom row values are nonpositive, the values are optimized. This tableau is read in the same way as the maximization case-the bottom right value is the minimized Z-value; the X column reveals a single value in the first row; the Y column has a single value in the second row.

In summary, the optimum solution is:

Z = 260

when

X = 6.67

Y = 6.67

DEMONSTRATION PROBLEM 6 Using linear programming for sensitivity analysis.

Fugi Disk Company cannot meet the demand for its preformatted 3.5-inch floppy disks . Fugi markets two types of disks: HD (high density) for newer computers and DD (double density) for older ones. Fugi can realize a profit of $0.32 for each DD disk and $0.30 for each HD disk. Unfortunately, Fugi is limited to 2,500 plastic DD disk cases and 400 disk boxes each day due to manufacturing limitations. Each box holds either 10 HD or 10 DD disks. The supply of box and disk labels is unlimited. The bulk formatting machine operates 420 minutes per day and can format two disks at a time; it has auto-feed and auto-eject mechanisms and can format an HD disk in 18 seconds and a DD disk in 15 seconds, including the loading and ejection times.

Required:

Use sensitivity analysis to find the optimal solution.

SOLUTION TO DEMONSTRATION PROBLEM 6

Formulating the linear programming problem, the objective function is:

0.30H + 0.32D = Maximize profit

The constraints are:

1.00D <= 2,500 (disk cases)

0.30H + 0.25D <= 840 (minutes)

0.1 OH + 0.10D <= 400 (boxes)

Using Excel to calculate the solution, we input the objective function and constraints as: (click Tools Options Formulas, to show the formulas as seen below)

What does sliding an objective function line toward the origin represent away from the origin?

When the formulas are not shown it looks like:   

What does sliding an objective function line toward the origin represent away from the origin?

After running Solver, the output screens show:

What does sliding an objective function line toward the origin represent away from the origin?

(with formulas shown)

What does sliding an objective function line toward the origin represent away from the origin?

Evaluating these output screens, Fugi management found that the optimal solution would he 2,500 DD disks and 716 HD disks (rounded down to whole disks). The shadow price (Lagrange multiplier) of 1 indi­cates that adding 1 minute would add $1 to profit. Therefore if the floor supervisor can add blocks of min­utes for less than $1/minute, profit will increase. After examining the shadow prices, (Lagrange Multiplier) the floor supervisor suggested adding 2.25 hours to the operation of the formatting machine by shuffling schedules and assigning some over-time. The extra cost would be $200 per day.

When the total format machine minutes were changed from 840 to 1,110 and the computer program was rerun, the following output screens resulted:

What does sliding an objective function line toward the origin represent away from the origin?

Since the new profit of $1,250 per day is greater than the old profit plus the extra cost ($200), it would be advantageous for Fugi to implement the increase in formatting machine hours.

REVIEW QUESTIONS

16.1 What does the feasible region represent?

16.2 Give two reasons why the graphical method is only practical for small LP problems.

16.3 What does moving an objective function line toward the origin represent? Moving the line away from the origin?

16.4 Which values are used to construct the objective function and the constraints?

a. LINDO parameters.

b. Decision variables.

c. Pricing policy.

d. Sensitivity constraints.

e. Shadow prices.

16.5 Which of the following do almost all practical applications of linear programming require?

a. Graphs.

b. Matrices.

c. Objective functions.

d. Computers.

e. Market surveys.

16.6 What are the four steps for constructing an LP problem?

16.7 Which of the following procedures is employed to solve simplex linear programming problems?

a. Shadow prices.

b. Graphs.

c. Integral calculus.

d. Expected value.

e. Matrix algebra.

16.8 In linear programming, shadow prices measure the:

a. Cost of the optimum solution.

b. Contribution margins hidden from production.

c. Addition or reduction of one unit of each of the resources.

d. Contribution of a product.

e. Volume price discounts.

16.9 In linear programming, the increase in profit when one more unit of a limited resource is made avail­able is indicated by:

a. The feasible region.

b. The objective function.

c. Nonnegativity constraints.

d. Shadow prices.

e. Incremental decision variables.

16.10 Which points do the simplex method “land on”?

16.11 What steps are required in solving a maximization problem using the simplex method?

16.12 What is the purpose of the first phase in using the simplex method for a minimization problem?

16.13 What is the primary difference between the simplex method and Karmarkar's method?

CHAPTER-SPECIFIC PROBLEMS

These problems require responses based directly on concepts and techniques presented in the text.

16.14 Graphical solution to LP minimization problem. Given the following LP problem:

min Z = 33X + 10Y

subject to:

X + Y >= 15

X >= 2

3X + Y >= 33

X + 2Y >= 18

Required:

Use the graphical method to find the optimal solution.

16.15 Graphical solution to LP maximization problem. Given the following LP problem: max Z = 3X + 2Y subject to:

5X + Y <= 100

X + 2Y <=  50

Y <=  15

Required.

Use the graphical method to find the optimal solution.

16.16 Determining the objective function and constraint. The Teaque Company makes

three products: A, B, and C. Management wants to maximize profits on these products. The contribution margin for each product follows:

PRODUCT

CONTRIBUTION MARGIN

A

$3

B

8

C

6

 The production requirements and departmental capacities, by departments, are as follows:  

Production Requirements

By Product (Hours)

Department

A

B

C

Assembling

Painting

Finishing

2

1

2

4

2

3

2

3

1

Department

Departmental Capacity (Total Hours)

Assembling

40,000

Painting

27,000

Finishing

42,000

Required:

a. Determine the objective function formula.

b. Specify the constraint for the Finishing Department.

16.17 Developing the objective function, constraint function, and nonnegativity constraints. The Galloway Company manufactures and sells shirts and dresses in its two-department factory. Galloway uses linear programming to determine its optimum product mix. Data related to the two products follow:

SHIRTS

DRESSES

Selling price per unit

$25

$40

Cost data per unit: Variable manufacturing cost

8

10

Variable selling cost

3

5

Fixed manufacturing cost

4

8

Fixed selling cost

1

2

MACHINE HOUR DATA

CUTTING

FINISHING

Shirts

10 minutes

15 minutes

Dresses

6 minutes

30 minutes

Monthly capacity

1,000 hours

2,000 hours

Required:

a. Develop the objective function that will maximize the contribution margin.

b. Develop the monthly machine hour constraints.

c. Develop the monthly nonnegativity constraints.

16.18 Graphical solution to LP problem. Neil and Neil book publishers are getting ready to print covers for their latest mass-market novel. (The current trend is to produce different covers for the same book, ide­ally to generate interest in the book and increase sales.) For this book, the publisher has decided to use pre­dominantly green and predominantly blue covers. Based on a marketing department request, at least 144 covers need to be produced each day, 32 of which should be blue.

Due to idiosyncrasies of the color printing process, blue covers take 2 minutes and green covers take 4.5 minutes each to print. Daily deliveries of raw blue pigment are at least 90 ounces due to vendor contracts. All other raw pigments (e.g., yellow pigment) are not a constraint. Blue covers use one ounce each whereas green covers use half an ounce each of the raw blue pigment. Raw materials costs are predicted to be $0.10 for each green cover and $0.17 for each blue cover. Efficiency goals require the printing press to be run at least 420 minutes each day.

Required:

Use the graphical method to find the optimal solution.

16.19 Graphical solution to LP problem. SpatulaCity Industries has only two products, Thick and Thin spatulas. The company nets $200 on a batch of Thin spatulas and $300 on each Thick spatula batch. Spat­ulaCity has only 100 tons of plastic available each day, with Thick spatula batches using 4 tons each and Thin spatula batches using 2 tons each. The finishing process takes 2 hours and 3 hours for each Thick and Thin batch, respectively, with a finishing process daily capacity of 90 hours. A contract with a large department store requires SpatulaCity to make at least 3 Thick batches per day.

Required:

a. Use the graphical method to find the feasible region.

b. Can 25 batches of Thin spatulas be optimally made each day?

16.20 Developing the objective function and constraints. The Harrington Corporation manufactures and sells three products: anchor bolts (A), bearings (B), and casters (C). There are 150 direct labor hours avail­able. Machine hour capacity allows 100 anchor bolts only; 50 bearings only; 40 casters only; or any com­bination of the three that does not exceed the capacity. Data associated with the products follow:

Product

Selling price

Variable Cost per Unit

Fixed Cost per Unit

Direct Labor Hours Per Unit

A

$4.00

$1.00

$2.00

2

B

3.50

0.50

2.00

2

C

6.00

2.00

3.00

3

Required:

a. Develop the objective function to maximize the total contribution margin from Harrington's three prod­ucts.

b. Develop the direct labor hour constraint.

c. Develop the machine hour constraint.

[CMA adapted]

16: 21 Simplex solution to LP maximization problem. Given the following LP problem: max Z = 15X + 13Y subject to:

Required:

Use the simplex method to find the optimal solution.

16.22 Simplex solution to LP minimization problem. Given the following LP problem: min Z = 12X + 5 Y

X + Y >= 25

X + 3.5Y >= 30

6X + 5Y >= 50

Required:

Use the simplex method to find the optimal solution.

16.23 Simplex solution to LP problem. Bear Chemical Company is planning to introduce two types of pain reliever products. The first, an aspirin and decongestant combination, will be marketed as a cold pill. The second will be just a plain aspirin pill. Due to spoilage of material, only 100 kilograms of raw decon­gestant can be used each week. Every 100 batches of cold pills require a half kilogram of decongestant and one-quarter kilogram of raw aspirin compound. Every 100 batches of plain pills use only one-third kilo­gram of raw aspirin compound. Bear can only use 540 kilograms of raw aspirin compound each week due to purchase contract requirements. Marketing has determined that no more than 300 batches of plain pills need to be manufactured each week. The pill press machine takes 10 minutes to make each cold pill batch and 9 minutes to make each plain pill batch.

Required:

Use the simplex method to find the optimal solution to maximize the use of the pill press machine.

16.24 Simplex solution to LP problem. A large food manufacturer is attempting to minimize the cost of the raisins that are included in one of its cereal products. It has a choice between two types of raisins-Best Quality and Good Quality. Best Quality raisins cost $0.023 and Good Quality raisins cost $0.010 each. Advertising claims of “2 scoops” in each box create the necessity to have at least 500 raisins in each box. Customer taste tests have proven that at least 250 of the raisins in each box have to be Best Quality to meet quality requirements. Due to damage during the mixing and packaging processes and the fact that the Best Quality raisins are more fragile, tests have shown that the Good Quality raisins are more visually appeal­ing in the box. Therefore, marketing requires a minimum of 100 Good Quality raisins in each box.

Required: Use the simplex method to find the optimal solution_

THINK-TANK PROBLEMS

Although these problems are based on chapter material, reading extra material, reviewing previous chap­ters, and using creativity may be required to develop workable solutions.

16.25 Comprehensive linear programming problem using the graphical method. [CMA adapted] Home Cooking Company offers monthly service plans providing prepared meals that are delivered to the cus­tomers' homes and that need only be heated in a micro-wave or conventional oven. The target market for these meal plans includes double-income families with no children and retired couples in the upper-income brackets.

Home Cooking offers two monthly plans-Premier Cuisine and Haute Cuisine. The Premier Cuisine plan provides frozen meals that are delivered twice each month: this plan generates a profit of $120 for each monthly plan sold. The Haute Cuisine plan provides freshly prepared meals delivered on a daily basis and generates a profit of $90 for each monthly plan sold. Home Cooking's reputation provides the company with a market that will purchase all the meals that can be prepared.

All meals go through food preparation and cooking steps in the company's kitchens. After these steps, the Premier Cuisine meals are flash frozen. The time requirements per monthly meal plan and hours available per month are as follows:

PREPARATION

COOKING

FREEZING

Hours required: Premier Cuisine

2

2

1

Haute Cuisine

1

3

0

Hours available

60

120

45

For planning purposes, Home Cooking uses linear programming to determine the most profitable number of Premier Cuisine and Haute Cuisine monthly meal plans to produce.

Required:

a. Using the notations P = Premier Cuisine and H = Haute Cuisine, state the objective function and the constraints that Home Cooking should use to maximize profits generated by the monthly meal plans.

b. Graph the constraints on Home Cooking's meal preparation process. Be sure to clearly label your graph.

c. By using the graph prepared in Requirement (b) or by making the necessary calculations, determine the optimal solution to Home Cooking's objective function in terms of the number of:

1. Premier Cuisine meal plans to produce.

2. Haute Cuisine meal plans to produce.

d. Calculate the optimal value of Home Cooking's objective function.

e. If the constraint on preparation time could be eliminated, determine the revised optimal solution in terms of the:

1. Number of Premier Cuisine meal plans to produce.

2. Number of Haute Cuisine meal plans to produce.

3. Resulting profit.

16.26 Determining the objective function, constraints, and assumptions of an LP problem. [CMA adapted] The Tripro Company produces and sells three products, hereafter referred to as products A, B, and C. The company is currently changing its short-range planning approach in an attempt to incorporate some of the newer planning techniques. The controller and some of his staff have been conferring with a consultant on the feasibility of using a linear programming model for determining the optimum product mix.

Information for short-range planning has been developed in the same format as in prior years. This infor­mation includes expected sales prices and expected direct labor and material costs for each product. In addition, variable and fixed overhead costs were assumed to be the same for each product because approx­imately equal quantities of the products were produced and sold.

PRICE AND COST INFORMATION (PER UNIT}  

A

B

C

Selling price

$25.00

$30.00

$40.00

Direct labor

7.50

10.00

12.50

Direct materials

9.00

6.00

10.50

Variable overhead

6.00

6.00

6.00

Fixed overhead

6.00

6.00

6.00

All three products use the same type of direct material, which costs $1.50 per pound of material. Direct labor is paid at the rate of $5.00 per direct labor hour. There are 2,000 direct labor hours and 20,000 pounds of direct materials available each month.

Required:

a. Formulate and label the linear programming objective function and constraint functions necessary to maximize Tripro's contribution margin. Use QA, QB, and Qc to represent units of the three prod­ucts.

b. What underlying assumptions must be satisfied to justify the use of linear programming?

c. The controller, upon reviewing the data presented and the linear programming functions developed, per­formed further analysis of overhead costs. He used a multiple linear regression model to analyze the overhead cost behavior. The regression model incorporated observations from the past 48 months of total overhead cost and the direct labor hours for each product. The following equation was the result:

Y = $5,000 + 2XA + 4XB + 3XC

where:

Y= Monthly total overhead in dollars

XA = Monthly direct labor hours for product A

XB = Monthly direct labor hours for product B

XC = Monthly direct labor hours for product C

The total regression has been determined to be statistically significant as has each of the individual regres­sion coefficients. Reformulate the objective function for Tripro Company using the results of this analysis.

16.27 Determining product mix and shadow price. [CMA adapted] The Frey Company manufactures and sells two products-a toddler bike and a toy highchair. Linear programming is employed to determine the best production and sales mix of bikes and chairs. This approach also allows Frey to speculate on eco­nomic changes. For example, management is often interested in knowing how variations in selling prices, resource costs, resource availabilities, and marketing strategies would affect the company's performance.

The demand for bikes and chairs is relatively constant throughout the year. The following economic data pertain to the two products:

BIKE (B)

CHAIR (C)

Selling price per unit

$12

$10

Variable cost per unit

  8

  7

Contribution margin per unit

$ 4

$ 3

Raw materials required:

Wood

1 board foot

2 board feet

Plastic

2 pounds

1 pound

Direct labor required

2 hours

2 hours

Estimates of the resource quantities available in a nonvacation month during the year are as follows:

Wood

10,000 board feet

Plastic

10,000 pounds

Direct labor

12,000 hours

 The graphic formulation of the constraints of the linear programming model that Frey Company has developed for nonvacation months accompanies the problem. The algebraic formulation of the model for the nonvacation months is as follows:

Objective function: max Z = 4B + 3C

The constraints are:

B + 2C <= 10,000 hoard feet

2B +  C <= 10,000 pounds

2B + 2C <= 12,000 direct labor hours

B, C >= 0

What does sliding an objective function line toward the origin represent away from the origin?

The results from the linear programming model indicate that Frey Company can maximize its contribution margin (and thus profits) for a nonvacation month by producing and selling 4,000 toddler hikes and 2,000 toy highchairs. This sales mix will yield a total contribution margin of $22,000 for a nonvacation month.

Required:

a. During the months of June, July, and August, the total direct labor hours available are reduced from 12,000 to 10,000 hours per month due to vacations.

1. What would be the best product mix and maximum total contribution margin when only 10,000 direct labor hours are available during a month?

2. The “shadow price” of a resource is defined as the marginal contribution of a resource or the rate at which profit would increase (decrease) if the amount of the resource were increased (decreased). Based on your solution to Requirement (a)1, what is the shadow price on direct labor hours in the original model for a vacation month?

b. Competition in the toy market is very strong. Consequently, the prices of the two products tend to fluc­tuate. Can analysis of data from the linear programming model provide information to management that will indicate when price changes to meet market conditions will alter the optimum product mix? Explain your answer.

16.28 Identifying and discussing the application of linear programming. [CMA adapted] The firm of Miller, Lombardi, and York was recently formed by the merger of two companies providing accounting services. York's business was providing personal financial planning, while Miller and Lombardi con­ducted audits of small governmental units and provided tax planning and preparation for several commer­cial firms. The combined firm has leased new offices and acquired several microcomputers that are used by the professional staff in each area of service. In the short run, however, the firm does not have the financial resources to acquire computers for all of the professional staff.

The expertise of the professional staff can be divided into three distinct areas that match the services pro­vided by the firm (i.e., tax preparation and planning, insurance and investments, and auditing). Since the merger, however, the new firm has had to turn away business in all three areas of service. One of the prob­lems is that although the total number of staff seems adequate, the staff members are not completely inter­changeable. Limited financial resources do not permit hiring any new staff in the near future, and, therefore, the supply of staff is restricted in each area.

Rich Oliva has been assigned the responsibility of allocating staff and computers to the various engage­ments. The management has given Oliva the objective of maximizing revenues in a manner consistent with maintaining a high level of professional service in each of the areas of service. Management's time is billed at $100 per hour, and the staff's time is billed at $70 per hour for those with experience, and $50 per hour for the inexperienced staff. Pam Wren, a member of the staff, recently completed a course in quantitative methods at the local university. She suggested to Oliva that he use linear programming to assign the appro­priate staff and computers to the various engagements.

Required:

a. Identify and discuss the assumptions underlying the linear programming model.

b. Explain the reasons why linear programming would be appropriate for Miller, Lombardi, and York in making staff assignments.

c. Identify and discuss the data that would be needed to develop a linear programming model for Miller, Lombardi, and York.

d. Discuss objectives, other than revenue maximization, that Rich Oliva should consider before making staff allocations.

16.29 Graphical solution to LP minimization problem. Modern Air is planning to add jet service to Chat­tanooga. Before purchasing the plane, Modern needs to determine the seat split between first and coach class. Modern's marketing department has already stated that the new plane should have at least 8 first-class seats. Modern's flight attendants have stated that to maintain adequate customer service, there should be, on average, one attendant for each 20 first-class seats or 50 coach seats. Modern's cabin designers have found that the average first-class seat takes the equivalent cabin space of one and one-half coach seats. Modern's marketing department also found that the average first-class passenger is on a short business trip with a combined person and luggage weight of 210 pounds. On the other hand, the average coach-class passenger is on an extended trip with a combined person and luggage weight of 230 pounds.

Required:

a. Modern is considering purchasing a model G-535, which is designed to lift 50,000 pounds of passenger (people + baggage) weight, can accommodate four attendants, and has the equivalent cabin room for 210 coach-class seats. With this plane, Modern's cost accountants have calculated a contribution of $110 for each first-class passenger and, due to severe competition from other airlines, only $50 for each coach pas­senger. What should be the cabin seat split?

b. Modern is also considering the purchase of a model G-535e-the efficiency version of the model G-535. With the G-535e, due to lower jet fuel costs, the contribution for each passenger would increase by 10%. Part of the decrease in operating costs is due to the passenger weight capacity being reduced by 10,000 pounds. What should the cabin seat split be for the model G-535e?

c. Based on the results from Requirements (a) and (b), briefly comment on the following:

1. What is the importance of each constraint?

2. Should Modern Air consider a smaller cabin size (and thus less expensive) jet?