statistic assignment
whiterose2015
mgmt3100_lecture_15_chap_13.pptxChapter 13: Linear Optimization – Part 2
Lan Wang
CSU East Bay
Linear Programming (LP) Problems
MAX (or MIN): c1X1 + c2X2 + … + cnXn
Subject to: a11X1 + a12X2 + … + a1nXn <= b1
:
ak1X1 + ak2X2 + … + aknXn >=bk
:
am1X1 + am2X2 + … + amnXn = bm
Developing an Optimization Model (Formulation)
Formulation in plain business language:
1. Understand the problem.
2. Identify the decision variables.
3. Identify the objective that need to be minimized or maximized
4. Identify/list the constraints
5. Organize the data required to make decisions
Writing the model in Mathematical form:
6. Write the objective function as a linear combination of the decision variables and the data.
7. Write the constraint functions as a linear combination of the decision variables and the data.
Example: Sklenka Ski Company
Sklenka Ski Company (SSC) is a small manufacturer of two types of popular all-terrain snow skis, the Jordanelle and Deercrest models.
The manufacturing process consists of two principal departments: fabrication and finishing. The fabrication department has 12 skilled workers, each of whom works 7 hours per day. The finishing department has three workers, who also work a 7-hour shift.
Each pair of Jordanelle skis requires 3.5 labor hours in the fabricating department and one labor hour in finishing. The Deercrest model requires four labor hours in fabricating and 1.5 labor hours in finishing. The company operates five days per week.
SSC makes a net profit of $50 on the Jordanelle model, and $65 on the Deercrest model. In anticipation of the next ski sale season, SSC must plan its production of these two models. Because of the popularity of its products and limited production capacity, its products are in high demand and SSC can sell all it can produce each season. The company anticipates that the demand of Deercrest models is at least twice of the demand of Jordanelle models. The company wants to determine how many of each model should be produced on a daily basis to maximize net profit.
Optimization Model
What are the decisions that need to be made here?
How many of each model should be produced on a daily basis
What is the objective?
Maximize Total Profit = 50 Jordanelle + 65 Deercrest
What are the constraints?
Total labor used ≤ the amount of labor available
3.5 Jordanelle + 4 Deercrest ≤ 84 (fabrication)
1 Jordanelle + 1.5 Deercrest ≤ 21 (finishing)
Number of pairs of Deercrest skis must be at least twice the number of Jordanelle skis
Deercrest - 2 Jordanelle ≥ 0
Nonnegativity
Deercrest ≥ 0, Jordanelle ≥ 0
Define X1 as Jordanelle, X2 as Deercrest
The mathematical model:
Maximize Total Profit = 50 X1 + 65 X2
Subject to
3.5 X1 + 4 X2 ≤ 84 (fabrication)
1 X1 + 1.5 X2 ≤ 21 (finishing)
X2 - 2 X1 ≥ 0
X2 ≥ 0, X1 ≥ 0
Challenge question A Transportation Problem: Tropicsun
Mt. Dora
1
Eustis
2
Clermont
3
Ocala
4
Orlando
5
Leesburg
6
Distances (in miles)
Capacity
Supply
275,000
Bushels of citrus
400,000
300,000
225,000
600,000
200,000
Groves
Processing
Plants
21
50
40
35
30
22
55
25
20
7
Defining the Decision Variables
Xij = # of bushels shipped from node i to node j
Specifically, the nine decision variables are:
X14 = # of bushels shipped from Mt. Dora (node 1) to Ocala (node 4)
X15 = # of bushels shipped from Mt. Dora (node 1) to Orlando (node 5)
X16 = # of bushels shipped from Mt. Dora (node 1) to Leesburg (node 6)
X24 = # of bushels shipped from Eustis (node 2) to Ocala (node 4)
X25 = # of bushels shipped from Eustis (node 2) to Orlando (node 5)
X26 = # of bushels shipped from Eustis (node 2) to Leesburg (node 6)
X34 = # of bushels shipped from Clermont (node 3) to Ocala (node 4)
X35 = # of bushels shipped from Clermont (node 3) to Orlando (node 5)
X36 = # of bushels shipped from Clermont (node 3) to Leesburg (node 6)
8
Defining the Objective Function
Minimize the total number of bushel-miles.
MIN: 21X14 + 50X15 + 40X16 +
35X24 + 30X25 + 22X26 +
55X34 + 20X35 + 25X36
9
Defining the Constraints
Capacity constraints
X14 + X24 + X34 <= 200,000 } Ocala
X15 + X25 + X35 <= 600,000 } Orlando
X16 + X26 + X36 <= 225,000 } Leesburg
Supply constraints
X14 + X15 + X16 = 275,000 } Mt. Dora
X24 + X25 + X26 = 400,000 } Eustis
X34 + X35 + X36 = 300,000 } Clermont
Non-negativity conditions
Xij >= 0 for all i and j
10
Solver in Excel
Build-in Solvers in Excel is enough for us. Resources are provided just for your reference.
http://www.meiss.com/download/Spreadsheet-Optimization-Solver.pdf
Mac User
http://www.solver.com/welcome-mac-users-solver-now-included-excel-2011
Tool -> Addins-> Solver
Then, Solver under Data tab.
PC Users
Excel Options-> Addins->Solver
11
The Steps in Implementing an LP Model in a Spreadsheet
1. Organize the data for the model on the spreadsheet.
Maintain primary data and use formulas to calculate coefficients that are needed for LP formulation.
2. Reserve separate cells in the spreadsheet for each decision variable in the model.
3. Create a formula in a cell in the spreadsheet that corresponds to the objective function.
4. For each constraint, create a formula in a separate cell in the spreadsheet that corresponds to the left-hand side (LHS) of the constraint.
12
Spreadsheet Design Guidelines - I
Organize the data, then build the model around the data.
Do not embed numeric constants in formulas.
Things which are logically related should be physically related.
Use formulas that can be copied.
Column/rows totals should be close to the columns/rows being totaled.
13
Spreadsheet Design Guidelines - II
The English-reading eye scans left to right, top to bottom.
Use color, shading, borders and protection to distinguish changeable parameters from other model elements.
Use text boxes and cell notes to document various elements of the model.
14
Example: Sklenka Ski Company
Sklenka Ski Company (SSC) is a small manufacturer of two types of popular all-terrain snow skis, the Jordanelle and Deercrest models.
The manufacturing process consists of two principal departments: fabrication and finishing. The fabrication department has 12 skilled workers, each of whom works 7 hours per day. The finishing department has three workers, who also work a 7-hour shift.
Each pair of Jordanelle skis requires 3.5 labor hours in the fabricating department and one labor hour in finishing. The Deercrest model requires four labor hours in fabricating and 1.5 labor hours in finishing. The company operates five days per week.
SSC makes a net profit of $50 on the Jordanelle model, and $65 on the Deercrest model. In anticipation of the next ski sale season, SSC must plan its production of these two models. Because of the popularity of its products and limited production capacity, its products are in high demand and SSC can sell all it can produce each season. The company anticipates selling at least twice as many Deercrest models as Jordanelle models. The company wants to determine how many of each model should be produced on a daily basis to maximize net profit.
Optimization Model
What are the decisions that need to be made here?
How many of each model should be produced on a daily basis
What is the objective?
Maximize Total Profit = 50 Jordanelle + 65 Deercrest
What are the constraints?
Total labor used ≤ the amount of labor available
3.5 Jordanelle + 4 Deercrest ≤ 84 (fabrication)
1 Jordanelle + 1.5 Deercrest ≤ 21 (finishing)
Number of pairs of Deercrest skis must be at least twice the number of Jordanelle skis
Deercrest - 2 Jordanelle ≥ 0
Nonnegativity
Deercrest ≥ 0, Jordanelle ≥ 0
Define X1 as Jordanelle, X2 as Deercrest
The mathematical model:
Maximize Total Profit = 50 X1 + 65 X2
Subject to
3.5 X1 + 4 X2 ≤ 84 (fabrication)
1 X1 + 1.5 X2 ≤ 21 (finishing)
X2 - 2 X1 ≥ 0
X2 ≥ 0, X1 ≥ 0
Let’s Implement a Model for this Example...
Steps in Implementing an LP Model in a Spreadsheet
1. Set up a logical format and organize the data for the model on the spreadsheet.
2. Reserve separate cells in the spreadsheet for each decision variable in the model.
3. Create a formula in a cell in the spreadsheet that corresponds to the objective function.
For each constraint, create a formula in a separate cell in the spreadsheet that corresponds to the left-hand side (LHS) of the constraint.
Avoid Excel functions ABS, MIN, MAX, INT, ROUND, IF, COUNT
How Solver Views the Model
Target cell - the cell in the spreadsheet that represents the objective function
Changing cells - the cells in the spreadsheet representing the decision variables
Constraint cells - the cells in the spreadsheet representing the LHS formulas on the constraints
Spreadsheet Design Guidelines
Organize the data, then build the model around the data.
Try not to embed numeric constants in formulas.
Things which are logically related should be physically related.
Use formulas that can be copied.
Column/row totals should be close to the columns/rows being totaled.
The English-reading eye scans left to right, top to bottom.
Use color, shading, borders and protection to distinguish changeable parameters from other model elements.
Use text boxes and cell notes to document various elements of the model.
Sklenka Skis
Using Standard Solver
Add Constraint Dialog
Solver Results Dialog
Select reports to save
Solver Solution
Video demo
The following is a video link showing how to use Solver in Excel to solve the Linear Programing problem (ski example).
http://youtu.be/2tt7mPb-kgg
Definitions
Feasible solution: any solution that satisfies all constraints
A problem that has no feasible solutions is called infeasible.
Possible Outcomes
Unique optimal solution
Alternate optimal solution
Unbounded problem
“The Set Cell values do not converge”
Infeasible problem
“Solver could not find a feasible solution”
In-class practice Happy Pet Example
The Happy Pet pet food company produces dog and cat food. Each food is comprised of meat, soybeans and fillers. The company earns a profit on each product but there is a limited demand for them.
The pounds of ingredients required and available, profits and demand are summarized in the following table. The company wants to plan their product mix in order to maximize profit .
27
| Product | Profit per Bag ($) | Demand for product | Pounds of Meat per bag | Pounds of Soybeans per bag | Pounds of Filler per bag |
| Dog food | 4 | 40 | 4 | 6 | 4 |
| Cat food | 5 | 30 | 5 | 3 | 10 |
| Material available (pounds) | 100 | 120 | 160 |
28
Mathematical Problem
X1 = bags of Dog food to produce
X2 = bags of Cat food to produce
MAX: 4 X1 + 5 X2
Subject to: 4 X1 + 5 X2 ≤100 (meat)
6 X1 + 3 X2 ≤120 (soybeans)
4 X1 + 10 X2 ≤ 160 (filler)
X1 ≤ 40 (Dog food demand)
X2 ≤ 30 (Cat food demand)
X1,X2 (nonnegativity)
29
Team Project
1. please formulate this problem. Show the definition of decision variables, objective functions, and constraints.
2. please using Solver to solve this problem.
3. what is the optimal solution?
Innis Investments manages funds for a number of companies and wealthy clients. The investment strategy is tailored to each client’s needs. For a new client, Innis has been authorized to invest up to $1.2 million in two investment funds: a stock fund and a money market fund. Each unit of the stock fund costs $50 and provides an annual rate of return of 10%; each unit of the money market fund costs $100 and provides an annual rate of return of 4%.
The client wants to minimize risk subject to the requirement that the annual income from the investment be at least $60,000. According to Innis’s risk measurement system, each unit invested in the stock fund has a risk index of 8, and each unit invested in the money market fund has a risk index of 3; the higher risk index associated with the stock fund simply indicates that it is the riskier investment. Innis’s client has also specified that at least $300,000 be invested in the money market fund.
Challenging Questions LP Model Formulation & Solution Innis Investment
31
