## Linear Optimization Models: A Comprehensive Guide This guide explores linear optimization models, also known as linear programs, a powerful problem-solving approach for managerial decision-making. We'll cover key concepts, examples, and special cases, using the versatile tool of Excel Solver. ### 1. Introduction to Linear Optimization Linear optimization models help managers make better decisions by maximizing or minimizing an **objective function** subject to a set of **constraints**. Both the objective function and constraints are linear functions of the decision variables. Think of the objective function as what you want to achieve (maximize profit, minimize cost), and the constraints as the limitations you face (available resources, production capacity). **Typical Applications:** * **Production Planning:** Minimizing production and inventory costs while meeting demand. * **Investment Portfolio:** Maximizing return on investment given various investment options. * **Marketing Budget Allocation:** Maximizing advertising effectiveness with a fixed budget. * **Transportation:** Minimizing shipping costs from warehouses to customers. A furniture manufacturer wants to determine the optimal number of chairs and tables to produce to maximize profit, given limited wood and labor resources. This is a linear optimization problem. ### 2. A Simple Maximization Problem: Par, Inc. **Par, Inc.** manufactures golf bags. They want to determine the optimal number of standard (S) and deluxe (D) bags to produce to maximize profit. **Data:** * **Profit:** $10/standard bag, $9/deluxe bag * **Resources (hours):** * Cutting & Dyeing: 630 hours total * Sewing: 600 hours total * Finishing: 708 hours total * Inspection & Packaging: 135 hours total * **Resource Usage (hours/bag):** (See Table 12.1 in original content for detailed resource usage per bag type) **Mathematical Model:** **Objective Function:** Maximize $Z = 10S + 9D$ **Constraints:** * Cutting & Dyeing: $7S + D \le 630$ * Sewing: $S + 5D/2 \le 600$ * Finishing: $2S + D \le 708$ * Inspection & Packaging: $S + 4D/10 \le 135$ * Non-negativity: $S \ge 0$, $D \ge 0$ Always clearly define your decision variables (S and D in this case) and express the objective and constraints in terms of these variables. This is a linear program because the objective function and all constraints are linear. ### 3. Solving Linear Programs: Graphical Method and Excel Solver For two-variable problems, the graphical method can be used. The **feasible region** is the area satisfying all constraints. The optimal solution lies at an **extreme point** of this region. For problems with more than two variables, the graphical method is impractical. We use the simplex method, implemented in software like Excel Solver. **Excel Solver:** 1. **What-if Model:** Create a spreadsheet with cells for decision variables, calculations for resource usage and profit, and cells representing constraints. 2. **Solver Parameters:** Set the objective cell (total profit), changing variable cells (S and D), and constraints. 3. **Solve:** Solver finds the optimal solution using the simplex method. Incorrectly defining the objective cell or constraints in Excel Solver can lead to incorrect results. The Solver Answer Report provides the optimal solution, objective function value, and information on binding constraints (constraints holding as equalities at the optimum) and slack (unused resources). ### 4. A Simple Minimization Problem: M&D Chemicals M&D Chemicals produces products A and B. They want to minimize production cost while meeting demand and capacity constraints. **Data:** * **Cost:** $2/gallon of A, $3/gallon of B * **Demand:** At least 350 gallons total, at least 125 gallons of A. * **Capacity:** 600 hours of processing time. * **Processing Time:** 2 hours/gallon of A, 1 hour/gallon of B **Mathematical Model:** **Objective Function:** Minimize $Z = 2A + 3B$ **Constraints:** * Total Production: $A + B \ge 350$ * Product A Demand: $A \ge 125$ * Processing Time: $2A + B \le 600$ * Non-negativity: $A \ge 0$, $B \ge 0$ This problem is solved similarly using Excel Solver. The Solver Answer Report will show the optimal production quantities and minimum cost. It will also indicate which constraints are binding and the surplus (excess production) for any greater-than-or-equal-to constraints. ### 5. Special Cases * **Alternative Optimal Solutions:** The objective function contour line coincides with a constraint line, resulting in multiple optimal solutions. * **Infeasibility:** No solution satisfies all constraints. This often indicates unrealistic expectations or too many restrictions. * **Unbounded:** The objective function can be infinitely increased (maximization) or decreased (minimization) without violating constraints. This usually indicates a modeling error, often a missing constraint. ### 6. Sensitivity Analysis **Sensitivity analysis** examines how changes in input parameters (objective function coefficients, constraint right-hand sides) affect the optimal solution. Excel Solver's Sensitivity Report provides this information. * **Shadow Price:** The change in the optimal objective function value for a one-unit increase in a constraint's right-hand side. Zero for non-binding constraints. * **Reduced Cost:** The shadow price of the non-negativity constraint for a decision variable. * **Allowable Increase/Decrease:** The range of change in an objective function coefficient that keeps the current optimal solution optimal. Sensitivity analysis helps understand the robustness of the optimal solution and the impact of uncertainties in input data. ### 7. General Linear Programming Notation and More Examples Using general notation ($x_1, x_2, ...$) simplifies modeling large problems. We explored applications in: * **Investment Portfolio Selection:** Maximizing expected return subject to investment constraints. * **Transportation Planning:** Minimizing transportation costs from multiple origins to multiple destinations. * **Maximizing Banner Ad Revenue:** Optimizing ad placement on a website to maximize revenue. These examples demonstrate the broad applicability of linear programming across various business domains. ### 8. Generating Alternative Optimal Solutions Sometimes, multiple optimal solutions exist with the same objective function value. A method to find an alternative optimal solution is presented, involving creating a new objective function that maximizes the sum of variables that were zero in the original optimal solution, while keeping the original objective function value fixed. This can lead to solutions that are more desirable from a managerial perspective, even if the objective function value remains unchanged. This comprehensive guide provides a solid foundation in linear optimization models. Remember to practice solving problems using Excel Solver to solidify your understanding.