Chapter Preview
TopIntroduction
To become problem solvers for the 21st century, analysts must be able to formulate the problem into mathematical terms, solve the problem, and then interpret the results. This chapter presents problems, their formulation, solution, and interpretations, as well as sensitivity analysis.
Consider a small company that is planning to install a central computer with cable links to five new departments. According to the floor plan, the peripheral computers for the five departments will be situated as shown in Figure 1. The company wishes to locate the central computer so that the minimal amount of cable will be used to link to the five peripheral computers. This will minimize the cost per cable and labor that is considered the biggest overall cost. Assuming that cable can be strung over the ceiling panels in a straight line from a point above any peripheral to a point above the central computer, the distance formula may be used to determine the length of cable needed to connect any peripheral to the central computer. Ignore all lengths of cable from the computer itself to a point above the ceiling panel immediately over that computer. In other words, work only with lengths of cable strung over the ceiling panels. We could add constraints later in the optimization chapter with constraints.
We keep this problem to only five data pairs as coordinates for the computers but the problem can easily be expanded. The coordinates of the locations of the five peripheral computers are listed in Table 1.
Table 1. Grid coordinates of five departments
Assume the central computer will be positioned at coordinates (m, n) where m and n are integers in the grid representing the office space. Determine the coordinates (m, n) for placement of the central computer that minimize the total amount of cable needed. Report the total number of feet of cable needed for this placement along with the coordinates (m, n).
This is a multivariable optimization problem. We want to minimize the sum of the distances from each department to the placement of the central computer system. The distances represent the cable lengths assuming that the straight line is the shortest distance between two points. Using the distance formula,
where d represents the distance (cable length in feet) between the location of the central computer (
x,y) and the location of the first peripheral computer (
X1, Y1). Since we have five departments we define
, for i = 1,2,3,4
5 We wish to minimize the sum of the distances given by
Key Terms in this Chapter
Gradient: The vector of first partial derivatives.
Decision Variables: The component variables, X , that impact the solution.
Optimal Solution: The values of the decision variables that either maximize or minimize the objective function.
Hessian Matrix: The matrix of second partial derivatives.
Numerical Search: An algorithmic procedure that allows for iterating to points that maximize or minimize an objective function.
Objective Function: A function of the decision variables that is to be maximized or minimized.
Stationary or Critical Point: The value of the decision variables that make the gradient equal to zero.
Unconstrained: The objective function is not constrained by resources surrounding the decision variables.
Optimization: The maximization or minimization of an objective function that depends on a finite number of decision variables.