Chapter 14 Applications of Linear Optimization Lecturer: Nguyen Van Dung Ph. Slides are based on slides accompanied the book “Business Analytics: Methods, Models, and Decisions”, with improvement from the lecturer Applications of Linear Optimization Building Linear Optimization Models 🞂Building optimization models is more of an art than a science. ◦ Learning how to build models requires logical thought facilitated by studying examples and observing their characteristics. 🞂Key issues: ◦ Formulation ◦ Spreadsheet implementation ◦ Interpreting results ◦ Scenario and sensitivity analysis ◦ Gaining insight for making good decisions Types of Constraints in Optimization Models 🞂 Simple Bounds (giới hạn) ◦ Constraints on values of a single variable 🞂 Limitations ◦ Allocation of scarce resources 🞂 Requirements ◦ Minimum levels of performance 🞂 Proportional (tỷ lệ) Relationships ◦ Requirements for mixtures or blends (pha trộn) of materials or strategies 🞂 Balance Constraints ◦ Ensure the flow of material or money is accounted for at locations or between time periods: input = output Process Selection Models 🞂Process selection models generally involve choosing among different types of processes to produce a good.
◦ Example: make or buy decisions Example 14.1: Camm Textiles 🞂 A mill that operates on a 24/7 basis produces three types of fabric (vải) on a make-to-order basis. 🞂 The key decision is which type of loom (khung cửi dệt vải) to use for each fabric (vải) type over the next 13 weeks. 🞂 The mill has 3 dobbie looms and 15 regular looms. 🞂 If demand cannot be met, the fabric is outsourced.1 Continued 🞂Model Formulation 🞂Di = yards fabric i to produce on dobbie loom 🞂Ri = yards fabric i to produce on regular loom 🞂Pi = yards fabric i to outsource 🞂Objective 🞂 Minimize total cost of milling (sự xay, sự nghiền, sự cán) and outsourcing 🞂Constraints 🞂 Requirements: Total production and outsourcing of each fabric = demand 🞂 Limitations: Production on each type of loom cannot exceed the available production time 🞂 Nonnegativity Example 14.1 Continued 🞂Demand constraints 🞂Production + outsourcing = demand ◦ Fabric 1: D1 + P1 = 45,000 ◦ Fabric 2: D2 + R2 + P2 = 76,500 ◦ Fabric 3: D3 + R3 + P3 = 10,000 Example 14.1: Continued 🞂Loom capacity limitation constraints 🞂 First convert yards/hour into hours/yard., for fabric 1 on the dobbie loom: hours/yard = 1/(4.213 hours/yard 🞂 Capacity of the three dobbie looms: (24 hours/day)(7 days/week)(13 weeks)(3 looms) = 6,552 hours 🞂 Constraint on available production time on dobbie looms: 0.227D3 ≤ 6,552 🞂 Constraint for regular looms: 0.1 Continued 🞂Full Model Spreadsheet Design 🞂 Camm Textiles model 🞂 Decision variables 🞂 Objective Solver Model Set cell C14 to zero as a constraint because fabric 1 cannot be produced on a regular loom.
Whenever you restrict a single decision variable to equal a value or set it as a ≤ or ≥ type of constraint, Solver considers it as a simple bound.2: Interpreting Solver Reports for the Camm Textiles Problem 🞂Answer Report Example 14.2: Interpreting Solver Reports for the Camm Textiles Problem 🞂Sensitivity Report Solver Output and Data Visualization 🞂Solver requires some technical knowledge of linear optimization concepts and terminology, such as reduced costs and shadow prices (giá mờ-see note). 🞂Data visualization can help analysts present optimization results in forms that are more understandable and can be easily explained to managers and clients in a report or presentation. Answer Report Visualization 🞂Camm Textiles Sensitivity Report Visualization 🞂 Reduced costs: how much the unit production or purchasing cost must be changed to force the value of a variable to become positive in the solution. Visualizing Allowable Ranges 🞂 Unit cost coefficients: use an Excel Stock Chart (see text for details).
◦ A stock chart typically shows the “high-low-close” values of daily stock prices; here we can compute the maximum-minimum- current values of the unit cost coefficients. For those lines that have no maximum limit (the blue dash) such as with Fabric 1 Purchased, the unit costs can increase to infinity; for those that have no lower limit (the red triangle) such as Fabric 1 on Dobbie, the unit costs can decrease indefinitely. Visualizing Shadow Prices 🞂 Shadow prices show the impact of changing the right-hand side of a binding constraint. Because the plant operates on a 24/7 schedule, changes in loom capacity would require in “chunks” (i., purchasing an additional loom) rather than incrementally (gia tăng, tăng thêm).
🞂 However, changes in the demand can easily be assessed using the shadow price information. Visualizing Allowable Ranges for Shadow Prices 🞂Stock Chart Blending Models 🞂Blending problems involve mixing several raw materials that have different characteristics to make a product that meets certain specifications. ◦ Dietary planning, gasoline and oil refining, coal and fertilizer production, and the production of many other types of bulk commodities involve blending. 🞂We typically see proportional constraints in blending models.3: BG Seed Company 🞂BG Seed Company is developing a new birdseed (hạt dùng cho chim ăn) mix.
◦ Nutritional requirements specify that the mixture contain at least 13% protein, at least 15% fat, and no more than 14% fiber. ◦ BG’s objective is to determine the minimum cost mixture that meets nutritional requirements.3 Continued 🞂Formulating the model 🞂Define Xi = pounds of ingredient i in 1 pound of mix 🞂Objective function 🞂 minimize 0.3 Continued 🞂 Protein constraint 🞂 Total pounds of protein provided/total pounds of mix ≥ 0.13 🞂Add constraint X1 + X2 + X3 + X4 + X5 + X6 + X7 + X8 = 1 ◦ Protein constraint simplifies to ◦ 0.13 Formulate other nutritional constraints in a similar way.3 Continued 🞂Complete model Spreadsheet Implementation of BG Seed Company Solver Model for BG Seed Company Dealing with Infeasibility 🞂 Solver solution shows the model is infeasible! 🞂 Solver Feasibility Report A conflict exists in trying to meet both fat and fiber constraints. Only sunflower seeds and safflower contain enough fat but they also have a lot of fiber. What-If Scenarios 🞂Lower the fat requirement or raise the fiber limitation 1st Scenario: Fat requirement is lowered from 15% to 14.
2nd Scenario: Fiber limitation is raised from 14% to 14. Optimal Cost per pound: $0.148 if fat requirement lowered $0.152 if fiber limitation raised Portfolio Investment Models 🞂Many types of financial investment problems are modeled and solved using linear optimization. 🞂Such portfolio investment models problems have the basic characteristics of blending models.4: Innis Investments 🞂 Innis Investments manages 6 mutual funds. A client wants to invest a $500,000 inheritance.
The objective is to minimize risk. 🞂Constraints: 🞂 Invest no more than $200,000 in any one fund. 🞂 Invest at least $50,000 each in the multinational and balanced funds. 🞂 Invest at least 40% combined in the income equity and balanced funds.
🞂 Achieve an average return of at least 5%.4 Continued 🞂Model Formulation 🞂 Define Xi = dollar amount invested in fund i ◦ The total risk would be measured by the weighted risk of the portfolio, where the weights are the proportion of the total investment in any fund (Xj/500,000) Example 14.4 Continued 🞂Constraints ◦ Invest all money: ◦ Achieve required return: ◦ Have at least 40% in income equity and balanced funds: ◦ At least $50,000 in each of multinational and balanced funds: ◦ Restrict each investment to $200,000, and include nonnegativity: Spreadsheet Implementation for Innis Investments Solver Model for Innis Investments Example 14.5: Risk versus Reward 🞂Innis Investments ◦ Allowable Increase and Allowable Decrease values for the weighted return are very small, 0.00111, respectively; so any changes in the target return will require re- solving the model. Scaling Issues in Using Solver 🞂 A poorly scaled model is one that computes values of the objective, constraints, or intermediate results that differ by several orders of magnitude. 🞂 Poor scaling can cause Solver engines to return messages such as “Solver could not find a feasible solution,” “Solver could not improve the current solution,” or even “The linearity conditions required by this Solver engine are not satisfied,” or it may return results that are suboptimal. ◦ In the Solver options, you can check the box Use Automatic Scaling.
◦ The best way to avoid scaling problems is to carefully choose the “units” implicitly used in your model so that all computed results are within a few orders of magnitude of each other.6: Little Investment Advisors 🞂 Little Investment Advisors is working with a client on determining an optimal portfolio of bond funds. The client has $350,000 to invest and wants to achieve the largest weighted percentage return and keep the weighted risk measure no greater than 5.6 Continued 🞂 Model ◦ Define X1 through X6 be the amount invested in each of the six funds.6 Continued 🞂 Premium Solver solution without scaling, resulting in an incorrect solution! Example 14.6 Continued 🞂 Solver solution after scaling the variables Transportation Models 🞂The transportation problem involves determining how much to ship from a set of sources of supply (factories, warehouses, etc.) to a set of demand locations (warehouses, customers, etc.) at minimum cost.7: General Appliance Corporation 🞂 GAC produces refrigerants at 2 plants and ships to 5 distribution centers. 🞂 Define the decision variables as: Xij = amount shipped from plant i to distribution center j 🞂 The objective is to minimize the total cost of shipping between plants and distribution centers.7 Continued 🞂Constraints ◦ The amount shipped from each plant cannot exceed its capacity. ◦ Demand at each distribution center is met.
◦ Nonnegativity GAC Spreadsheet Implementation and Solver Model Formatting the Sensitivity Report 🞂 Depending on how cells in your spreadsheet model are formatted, the Sensitivity report produced by Solver may not reflect the accurate values of reduced costs or shadow prices because an insufficient number of decimal places may be displayed. 🞂 We highly recommend that after you save the Sensitivity report to your workbook, you select the reduced cost and shadow price ranges and format them to have at least two or three decimal places. Example: GAC Sensitivity Report Original Sensitivity Report Reformatted Sensitivity Report Example 14.8: Interpreting Sensitivity Information for the GAC Model 🞂 Reduced costs tell how much the unit shipping cost would have to be reduced to make it attractive to ship along a route. 🞂 We cannot increase the demand at any distribution center without creating an infeasible problem.
The shadow prices reflect the cost savings that would occur for a unit decrease in demand at one of the distribution centers. Degeneracy 🞂 The GAC solution exhibits a phenomenon called degeneracy (sự thoái hoá). A solution is degenerate if the right-hand-side value of any constraint has a zero Allowable Increase or Allowable Decrease. ◦ Degeneracy can impact the interpretation of sensitivity analysis information.
For example, reduced costs and shadow prices may not be unique, and you may have to change objective function coefficients beyond their allowable increases or decreases before the optimal solution will change. Multiperiod Production Planning Models 🞂 The basic decisions are how much to produce in each time period to meet anticipated demand over each period. 🞂 Although it might seem obvious to simply produce to the anticipated level of sales, it may be advantageous to produce more than needed in earlier time periods when production costs may be lower and store the excess production as inventory for use in later time periods, thereby letting lower production costs offset the costs of holding the inventory.