7.5 Solving Minimization Problems
Many LP problems involve minimizing an objective such as cost instead of maximizing a profit function. A restaurant, for example, may wish to develop a work schedule to meet staffing needs while minimizing the total number of employees. A manufacturer may seek to distribute its products from several factories to its many regional warehouses in such a way as to minimize total shipping costs. A hospital may want to provide a daily meal plan for its patients that meets certain nutritional standards while minimizing food purchase costs.
Minimization problems with only two variables can be solved graphically by first setting up the feasible solution region and then using either the corner point method or an isocost line approach (which is analogous to the isoprofit approach in maximization problems) to find the values of the decision variables (e.g., and ) that yield the minimum cost. Let’s take a look at a common LP problem referred to as the diet problem. This situation is similar to the one that the hospital faces in feeding its patients at the least cost.
Holiday Meal Turkey Ranch
The Holiday Meal Turkey Ranch is considering buying two different brands of turkey feed and blending them to provide a good, low-cost diet for its turkeys. Each feed contains, in varying proportions, some or all of the three nutritional ingredients essential for fattening turkeys. Each pound of brand 1 purchased, for example, contains 5 ounces of ingredient A, 4 ounces of ingredient B, and 0.5 ounce of ingredient C. Each pound of brand 2 contains 10 ounces of ingredient A, 3 ounces of ingredient B, but no ingredient C. The brand 1 feed costs the ranch 2 cents a pound, while the brand 2 feed costs 3 cents a pound. The owner of the ranch would like to use LP to determine the lowest-cost diet that meets the minimum monthly intake requirement for each nutritional ingredient.
Table 7.5 summarizes the relevant information. If we let
Table 7.5 Holiday Meal Turkey Ranch Data
| COMPOSITION OF EACH POUND OF FEED (OZ.) | MINIMUM MONTHLY REQUIREMENT PER TURKEY (OZ.) | ||
|---|---|---|---|
| INGREDIENT | BRAND 1 FEED | BRAND 2 FEED | |
| A | 5 | 10 | 90 |
| B | 4 | 3 | 48 |
| C | 0.5 | 0 | 1.5 |
| Cost per pound | 2 cents | 3 cents | |
then we may proceed to formulate this linear programming problem as follows:
subject to these constraints:
Before solving this problem, we want to be sure to note three features that affect its solution. First, you should be aware that the third constraint implies that the farmer must purchase enough brand 1 feed to meet the minimum standards for the C nutritional ingredient. Buying only brand 2 would not be feasible because it lacks C. Second, as the problem is formulated, we will be solving for the best blend of brands 1 and 2 to buy per turkey per month. If the ranch houses 5,000 turkeys in a given month, it need simply multiply the and quantities by 5,000 to decide how much feed to order overall. Third, we are now dealing with a series of greater-than-or-equal-to constraints. These cause the feasible solution area to be above the constraint lines in this example.
Using The Corner Point Method On A Minimization Problem
To solve the Holiday Meal Turkey Ranch problem, we first construct the feasible solution region. This is done by plotting each of the three constraint equations as in Figure 7.10. Note that the third constraint, can be rewritten and plotted as (This involves multiplying both sides of the inequality by 2 but does not change the position of the constraint line in any way.) Minimization problems are often unbounded outward (i.e., on the right side and the top), but this causes no difficulty in solving them. As long as they are bounded inward (on the left side and the bottom), corner points may be established. The optimal solution will lie at one of the corners, as it would in a maximization problem.
Figure 7.10 Feasible Region for the Holiday Meal Turkey Ranch Problem
In this case, there are three corner points: a, b, and c. For point a, we find the coordinates at the intersection of the ingredient C and B constraints—that is, where the line crosses the line If we substitute into the B constraint equation, we get
or
Thus, point a has the coordinates
To find the coordinates of point b algebraically, we solve the equations and simultaneously. This yields
The coordinates at point c are seen by inspection to be We now evaluate the objective function at each corner point, and we get
Hence, the minimum cost solution is to purchase 8.4 pounds of brand 1 feed and 4.8 pounds of brand 2 feed per turkey per month. This will yield a cost of 31.2 cents per turkey.
Isocost Line Approach
As mentioned before, the isocost line approach may also be used to solve LP minimization problems such as that of the Holiday Meal Turkey Ranch. As with isoprofit lines, we need not compute the cost at each corner point but instead draw a series of parallel cost lines. The lowest cost line (i.e., the one closest to the origin) to touch the feasible region provides us with the optimal solution corner.
For example, we start in Figure 7.11 by drawing a 54-cent cost line—namely, Obviously, there are many points in the feasible region that would yield a lower total cost. We proceed to move our isocost line toward the lower left, in a plane parallel to the 54-cent solution line. The last point we touch while still in contact with the feasible region is the same as corner point b of Figure 7.10. It has the coordinates and an associated cost of 31.2 cents.
Figure 7.11 Graphical Solution to the Holiday Meal Turkey Ranch Problem Using the Isocost Line
Figure 7.10 Feasible Region for the Holiday Meal Turkey Ranch Problem
This could be solved using QM for Windows by selecting the Linear Programming Module and selecting New problem. Specify that there are two variables and three constraints. When the input window opens, enter the data and click Solve. The output is shown in Program 7.4.
To solve this in Excel 2016, determine the cells where the solution will be, enter the coefficients from the objective function and the constraints, and write formulas for the total cost and the total of each ingredient (constraint). The input values and solution are shown in Program 7.5A, with column D containing the formulas. These formulas are shown in Program 7.5B. When the Solver Parameters window opens, the Set Objective cell is D5; the addresses in the By Changing Variable Cells box are B4:C4; the Simplex LP method is used; the box for variables to be nonnegative is checked; and Min is selected because this is a minimization problem.
Program 7.4 Solution to the Holiday Meal Turkey Ranch Problem in QM for Windows
Program 7.5A Excel 2016 Solution for Holiday Meal Turkey Ranch Problem
