Over. L.P. App. Sol.
Linear Programming and its Applications
Master of Business Administration
MBA 8419 – Decision Making Technology
Copyright By PowCoder代写 加微信 powcoder
1 Linear Programming and its Applications
Over. L.P. App. Sol. Overview of the presentation
What is a linear program (LP) ? Problem ⇒ optimization model General Form
Applications and the use of EXCEL’s Solver Marketing
Operations management
How are these models solved ?
Graphical solution Sensitivity analysis
Linear Programming and its Applications
Over. L.P. App. Sol.
P. ⇒ O.M. G.F.
What is a linear program ? Problem ⇒ optimization model
Here are some typical applications :
FIGURE – Taken from Anderson et. al. (2012), Chap.2
3 Linear Programming and its Applications
Over. L.P. App. Sol. P. ⇒ O.M. G.F. What is a linear program ?
Problem ⇒ optimization model
General characteristics :
A series of Decisions to be made Desire to max or min some quantity
Objective of the LP
Presence of restrictions, or Constraints
limit the values the decisions can take
implicitly limit the degree to which the objective can be pursued
Examples :
Satisfying customer demands
Limited supplies
Limited capacities (space, time, employees, etc.) etc.
Linear Programming and its Applications
Over. L.P. App. Sol.
P. ⇒ O.M. G.F.
What is a linear program ? Problem ⇒ optimization model
Define the decision variables
Definition: what decisions need to be made and how do they influence the state of the system under study.
Characteristics:
• Varying impacts on the system
• Can be grouped by category
• Can be made over multiple time periods
Formulate the objective function
Definition: what is the objective pursued in solving the problem or in modifying the system (i.e., what criteria is used to evaluate the decisions). Characteristics:
•Evaluate the quality of decisions
Express the constraints
Definition: set of obligations and limits that need to be enforced and that define admissible/feasible decisions.
Characteristics:
• Technological: • Hard
• Non-negativity
• Integrity
FIGURE – Process to formulate a problem
5 Linear Programming and its Applications
Over. L.P. App. Sol.
P. ⇒ O.M. G.F.
What is a linear program ? General form
Decision variables
x1,x2,…,xn Objective Function
Subject to
max or minz = c1x1 +c2x2 +…+cnxn ≤
a11x1 +a12x2 +…+a1nxn ≥ b1 =
≤ a21x1 +a22x2 +…+a2nxn ≥ b2
am1x1 +am2x2 +…+amnxn ≥ bm =
x1,x2,…,xn ≥ 0 and xj is integer, ∀j ∈ E and given E ⊆ {1,2,…,n}
6 Linear Programming and its Applications
Over. L.P. App. Sol. Mar. Fin. O.M. Applications and the use of EXCEL’s Solver
Types of problems
Promotional planning
Description : Choose between a set of available media options such as to maximize the promotional effort for a given set of products or services, targeted at specific segments of a given population
Sales territory coverage
Description : Assign a set of salespersons to a set of existing or potential customers such as to minimize costs, or, ensure that the workload (or value) among the salespersons are uniformly distributed
Marketing research
Description : To understand the composition and nature of a targeted mar- ket, establish the number and types of studies that need to be performed to obtain the desired information while minimizing the costs
Linear Programming and its Applications
Over. L.P. App. Sol.
Mar. Fin. O.M.
Applications and the use of EXCEL’s Solver Marketing
Marketing research
Context : Market Survey Inc. (MSI), specializes in evaluation of consumer reaction to new products, services, and adverti- sing campaigns. A client firm requested that MSI’s assistances in ascertaining consumer reaction to a recently marketed hou- sehold product.
Strategy : door-to-door personal interviews with families (i.e., households) that either have, or don’t have, children.
Contract : MSI must conduct 1 000 interviews
8 Linear Programming and its Applications
Over. L.P. App. Sol. Mar. Fin. O.M. Applications and the use of EXCEL’s Solver
Marketing research (cont’d)
Quota guidelines :
Interview at least 400 households with children
Interview at least 400 households without children
The total number of households interviewed during the evening must be at least as great as the number of households interviewed during the day
At least 40% of the interviews for households with children must be conducted during the evening
At least 60% of the interviews for households without children must be conducted during the evening
Interview cost Household Day Evening
Children 20$ 25$ No Children 18$ 20$
TABLE – Unitary costs per interview type
Linear Programming and its Applications
Over. L.P. App. Sol.
Mar. Fin. O.M.
Applications and the use of EXCEL’s Solver Marketing
Marketing research (cont’d) Model :
Decision variables :
DC = the number of daytime interviews of households with children,
EC = the number of evening interviews of households with children, DNC = the number of daytime interviews of households without children, ENC = the number of evening interviews of households without children.
Objective Function : min 20DC + 25EC + 18DNC + 20ENC Subject to :
DC + EC + DNC + ENC = 1 000
DC + EC ≥ 400
DNC + ENC ≥ 400
EC +ENC ≥ DC +DNC
EC ≥ 0, 4(DC + EC)
ENC ≥ 0, 6(DNC + ENC)
DC, EC, DNC, ENC ≥ 0 and integer.
10 Linear Programming and its Applications
Over. L.P. App. Sol. Mar. Fin. O.M. Applications and the use of EXCEL’s Solver
Solving the problem using EXCEL
Build the spreadsheet Standard Form :
Each column is associated with a specific decision variable Each line is associated to a linear function (i.e., objective and constraints)
Use of the Solver function Define the variable cells
Define the objective cell and max or min
Add the different constraints
Make Unconstrained Variables Non-Negative Select solving method :
GRG Nonlinear ⇒ for nonlinear optimization models Simplex LP ⇒ exact method for linear optimization models Evolutionary ⇒ heuristic method for optimization models
Linear Programming and its Applications
Over. L.P. App. Sol.
Mar. Fin. O.M.
Applications and the use of EXCEL’s Solver Marketing
Optimal solution to the MSI problem
Number of Interviews Household Day Evening Total
Children No Children Total
240 160 400 240 360 600 480 520 1000
TABLE – Optimal Solution
12 Linear Programming and its Applications
Over. L.P. App. Sol. Mar. Fin. O.M. Applications and the use of EXCEL’s Solver
Types of problems Portfolio theory
Description : Considering a set of available stocks and bonds, deter- mine the amount of investment that a company (or particular) should make in each financial instrument with the objective of minimizing risk, while also maximizing the returns
Valuation of financial instruments
Description : In the context of trading within financial markets, deter- mine what is the value of the assets that are being traded
Financial planning
Description : Figure out what funding decisions should be made to best raise the necessary capital from the financial markets to finance an organization’s activities
Linear Programming and its Applications
Over. L.P. App. Sol.
Mar. Fin. O.M.
Applications and the use of EXCEL’s Solver Finance
Designing Portfolio of Mutual Funds
Description : Portfolio models are used to determine the % of the investment funds that should be made in each available assets.
Goal : provide the best balance between risk and return.
Context : Services designs annuities and long term investment plans for investors with a variety of risk tolerances. Hauck would like to develop a portfolio model that can be used to determine an optimal portfolio involving a mix of six mutual funds. A variety of measures can be used to indi- cate risk, but for portfolios of financial assets all are related to variability in return.
14 Linear Programming and its Applications
Over. L.P. App. Sol.
Mar. Fin. O.M.
Applications and the use of EXCEL’s Solver Finance
Designing Portfolio of Mutual Funds (cont’d)
Managers at Services think that the returns of past years can be used to represent the possibilities (i.e., sce- narios) for the next year. Therefore, the following information will be used as planning scenarios for the next 12 months :
Mutual Fund
Foreign Stock Intermediate-Term Bond Large-Cap Growth Large-Cap Value Small-Cap Growth Small-Cap Value
10,06 17,64 32,41 32,36 33,44 24,56
13,12 3,25 18,71 20,61 19,40 25,32
13,47 7,51 33,28 12,93 3,85 -6,70
45,42 -1,33 41,46 7,06 58,68 5,43
-21,93 7,36 -23,26 -5,37 -9,02 17,31
Annual Return (%)
TABLE – Mutual fund performance in 5 selected years
15 Linear Programming and its Applications
Over. L.P. App. Sol.
Mar. Fin. O.M.
Applications and the use of EXCEL’s Solver Finance
Conservative Portfolio
Idea : Design a portfolio for a conservative client that has a strong aversion to risk. Determine the proportion of the portfolio to invest in each of the six mutual funds so that the portfolio provides the best return possible with a minimum of risk.
Decision variables
FS = proportion of portfolio invested in the Foreign Stock mutual fund IB = proportion of portfolio invested in the Intermediate-Term Bond fund LG = proportion of portfolio invested in the Large-Cap Growth fund
LV = proportion of portfolio invested in the Large-Cap Value fund
SG = proportion of portfolio invested in the Small-Cap Growth fund
SV = proportion of portfolio invested in the Small-Cap Value fund
16 Linear Programming and its Applications
Over. L.P. App. Sol.
Mar. Fin. O.M.
Applications and the use of EXCEL’s Solver Finance
Given the definition of the decision variables the following constraint needs to be imposed :
FS+IB+LG+LV +SG+SV =1
The portfolio return over the next year will depend on which scenario will
10,06FS + 17,64IB + 32,41LG + 32,36LV + 33,44SG + 24,56SV 13,12FS + 3,25IB + 18,71LG + 20,61LV + 19,40SG + 25,32SV 13,47FS + 7,51IB + 33,28LG + 12,93LV + 3,85SG − 6,70SV 45,42FS + 1,33IB + 41,46LG + 7,06LV + 58,68SG + 5,43SV −21,93FS + 7,36IB − 23,26LG − 5,37LV − 9,02SG + 17,31SV
17 Linear Programming and its Applications
Over. L.P. App. Sol.
Mar. Fin. O.M.
Applications and the use of EXCEL’s Solver Finance
Decision variables (cont’d)
M = minimum return for the portfolio
To define M, we need to add the following minimum-return constraints
R1≥M Scenario 1 minimum return R2≥M Scenario 2 minimum return R3≥M Scenario 3 minimum return R4≥M Scenario 4 minimum return R5≥M Scenario 5 minimum return
18 Linear Programming and its Applications
Over. L.P. App. Sol.
Mar. Fin. O.M.
Applications and the use of EXCEL’s Solver Finance
Substituting the values previously define for R1, R2, and so on, provides the following five minimum-return constraints :
10,06FS+17,64IB+32,41LG+32,36LV +33,44SG+24,56SV ≥M 13,12FS+3,25IB+18,71LG+20,61LV +19,40SG+25,32SV ≥M 13,47FS+7,51IB+33,28LG+12,93LV +3,85SG−6,70SV ≥M 45,42FS+1,33IB+41,46LG+7,06LV +58,68SG+5,43SV ≥M −21,93FS+7,36IB−23,26LG−5,37LV −9,02SG+17,31SV ≥M
Objective Function
Apply a maximin approach
Scenario 1 Scenario 2 Scenario 3 Scenario 4 Scenario 5
19 Linear Programming and its Applications
Over. L.P. App. Sol.
Mar. Fin. O.M.
Applications and the use of EXCEL’s Solver Finance
max M s.t.
10,06FS + 17,64IB + 32,41LG + 32,36LV + 33,44SG + 24,56SV ≥ M 13,12FS + 3,25IB + 18,71LG + 20,61LV + 19,40SG + 25,32SV ≥ M 13,47FS + 7,51IB + 33,28LG + 12,93LV + 3,85SG − 6,70SV ≥ M 45,42FS + 1,33IB + 41,46LG + 7,06LV + 58,68SG + 5,43SV ≥ M −21,93FS + 7,36IB − 23,26LG − 5,37LV − 9,02SG + 17,31SV ≥ M FS+IB+LG+LV +SG+SV =1 FS,IB,LG,LV,SG,SV ≥ 0
20 Linear Programming and its Applications
Over. L.P. App. Sol. Mar. Fin. O.M. Applications and the use of EXCEL’s Solver
Moderate Risk Portfolio
Note : certain clients are willing to accept a moderate amount of risk in order to attempt to achieve better returns.
Assumption
Clients in this category are willing to accept some risks but do not want the annual return for the portfolio to drop below 2%
Therefore, M = 2
Scenario 1 minimum return Scenario 2 minimum return Scenario 3 minimum return Scenario 4 minimum return Scenario 5 minimum return
21 Linear Programming and its Applications
Over. L.P. App. Sol. Mar. Fin. O.M. Applications and the use of EXCEL’s Solver
Objective Function
A different objective is needed here ⇒ Maximize the expected return for the portfolio
Assumption
Assuming that pi , for i = 1, . . . , 5, are the probabilities of observing the scenarios i.
Then, R = p1R1 + p2R2 + p3R3 + p4R4 + p5R5, defines an estimator of the expected value of the return
If all scenarios are equiprobable, then
max 51R1 + 15R2 + 51R3 + 15R4 + 51R5
maxp1R1 +p2R2 +p3R3 +p4R4 +p5R5
22 Linear Programming and its Applications
Over. L.P. App. Sol.
Mar. Fin. O.M.
Applications and the use of EXCEL’s Solver Finance
0.2R1 + 0.2R2 + 0.2R3 + 0.2R4 + 0.2R5
10,06FS + 17,64IB + 32,41LG + 32,36LV + 33,44SG + 24,56SV = R1,
13,12FS + 3,25IB + 18,71LG + 20,61LV + 19,40SG + 25,32SV = R2, 13,47FS + 7,51IB + 33,28LG + 12,93LV + 3,85SG − 6,70SV = R3, 45,42FS + 1,33IB + 41,46LG + 7,06LV + 58,68SG + 5,43SV = R4, −21,93FS + 7,36IB − 23,26LG − 5,37LV − 9,02SG + 17,31SV = R5, R1 ≥2,R2 ≥2,R3 ≥2,R4 ≥2,R5 ≥2,
FS+IB+LG+LV +SG+SV =1, FS,IB,LG,LV,SG,SV ≥ 0
23 Linear Programming and its Applications
Over. L.P. App. Sol. Mar. Fin. O.M. Applications and the use of EXCEL’s Solver
Operations management
Types of problems
Distribution Management
Description : Planning and executing the various distribution operations of a company to serve its clients in a timely manner, while minimizing the costs.
Production Planning
Description : Planning and scheduling the production operations of a company, which may include the procurement processes, the management of inventory, establishing the production levels through time, assigning ressources, etc., while minimizing the overall costs.
Logistics Network Design
Description : Design, manage and coordinate a logistics network such as to perform the necessary operations while minimizing costs.
Linear Programming and its Applications
Over. L.P. App. Sol.
Mar. Fin. O.M.
Applications and the use of EXCEL’s Solver Operations management
Production Scheduling
Description : Company (BEC) pro- duces two different electronic components for a major airplane engine manufacturer. The airplane engine manu- facturer notifies the Bollinger sales office each quarter of its monthly requirements for components for each of the next three months. The requirements may vary considerably, depending on the type of engine the manufacturer is producing.
1000 3000 5000 1 000 500 3 000
TABLE – Three-month demand schedule for BEC
25 Linear Programming and its Applications
Over. L.P. App. Sol. Mar. Fin. O.M. Applications and the use of EXCEL’s Solver
Operations management
Production Scheduling (cont’d)
Once the order is processed, a demand statement is sent to the produc- tion control department. The production control department then deve- lops a three-month production plan for the components. The production manager will want to identify the following :
1 Total production cost
2 Inventory holding cost
3 Change-in-production-level costs
322A costs 20$ per unit produced, while 802B costs 10$ per unit produced
Inventory holding costs are 1.5% of the cost of the product (monthly)
Cost associated with ↑ the production level for any month is 0.50$ per unit increase
Cost associated with ↓ the production level for any month is 0.20$ per unit decrease
Linear Programming and its Applications
Over. L.P. App. Sol.
Mar. Fin. O.M.
Applications and the use of EXCEL’s Solver Operations management
Production Scheduling (cont’d)
Machine Capacity (hours)
Labor Capacity (hours) 300
Storage Capacity (square feet) 10 000
TABLE – Machine, Labor and Storage Capacities for BEC
Machine Component (hours/unit)
322A 0.10 802B 0.08
Labor Storage (hours/unit) (square feet/unit)
0.05 2 0.07 3
TABLE – Machine, Labor and Storage requirements for components 322A and 802B
27 Linear Programming and its Applications
Over. L.P. App. Sol. Mar. Fin. O.M. Applications and the use of EXCEL’s Solver
Operations management
Decision Variables
xim = production volume in units for product i in month m sim = inventory level for product i at the end of month m
Im = increase in the total production level necessary during month m
Dm = decrease in the total production level necessary during month m
i =1⇒322Aandi =2⇒802B
m = 1 ⇒ April, m = 2 ⇒ May and m = 3 ⇒ June
28 Linear Programming and its Applications
Over. L.P. App. Sol.
Mar. Fin. O.M.
Applications and the use of EXCEL’s Solver Operations management
Objective function :
min Total Cost = Total production cost + Inventory holding cost + Change-in-production-level costs
Total production cost = 20×11 + 20×12 + 20×13 + 10×21 + 10×22 + 10×23
Inventory holding cost = (0.015×20)s11+s12+s13+(0.015×10)s21+s22+s23 Change-in-production-level costs = 0.50(I1 +I2 +I3)+0.20(D1 +D2 +D3) Therefore,
min 20×11 + 20×12 + 20×13 + 10×21 + 10×22 + 10×23 + 0.30s11 + 0.30s12 + 0.30s13 +0.15s21 +0.15s22 +0.15s23 +0.50I1 +0.50I2 +0.50I3 +0.20D1 + 0.20D2 + 0.20D3
29 Linear Programming and its Applications
Over. L.P. App. Sol.
Mar. Fin. O.M.
Applications and the use of EXCEL’s Solver Operations management
Subject to :
Inventories at the beginning of the three-month scheduling period were 500 units for component 322A and 200 units for component 802B. The company would like to have 400 and 200 units, respectively for each product, in the inventory at the end of the planning.
Month1: Month2: Month3:
500+x11 −s11 =1000 200+x21 −s21 = 1000
s11 +x12 −s12 =3000 s21 +x22 −s22 =500
s12 +x13 −s13 =5000 s22 +x23 −s23 = 3000
Ending inventory : s13 ≥ 400
30 Linear Programming and its Applications
Over. L.P. App. Sol.
Mar. Fin. O.M.
Applications and the use of EXCEL’s Solver Operations management
Subject to (cont’d) :
Capacities :
Machines :
Month 1 : 0.10×11 + 0.08×21 ≤ 400 Month 2 : 0.10×12 + 0.08×22 ≤ 500 Month 3 : 0.10×13 + 0.08×23 ≤ 600
Month 1 : 0.05×11 + 0.07×21 ≤ 300 Month 2 : 0.05×12 + 0.07×22 ≤ 300 Month 3 : 0.05×13 + 0.07×23 ≤ 300
Month1:2s11 +3s21 ≤10000 Month2:2s12 +3s22 ≤10000 Month3:2s13 +3s23 ≤10000
31 Linear Programming and its Applications
Over. L.P. App. Sol. Mar. Fin. O.M. Applications and the use of EXCEL’s Solver
Operations management
Subject to (cont’d) :
∆ production volumes :
Production levels during the month of March were 1 500 units of 322A
and 1 000 units of 802B
Month1:(x11 +x21)−2500=I1 −D1
There are three possible cases :
If(x11 +x21)−2500>0thenI1 >0andD1 =0 If(x11 +x21)−2500<0thenI1 =0andD1 >0 If(x11 +x21)−2500=0thenI1 =0andD1 =0
Month2:(x12 +x22)−(x11 +x21)=I2 −D2 Month3:(x13 +x23)−(x12 +x22)=I3 −D3
Non-negativity and integrality : xim,sim,Im,Dm ≥0andinteger,∀i,m.
32 Linear Programming and its Applications
Over. L.P. App. Sol. Gra. Sol. Sen. Ana. How are these models solved ?
Graphical solution
Consider the optimization problem (P) :
max z = 1000×1 + 1200×2 subject to
(C1) 10×1 + 5×2 ≤ 200 (C2) 2×1 + 3×2 ≤ 60
(C3) x1 ≤ 34 (C4) x2 ≤ 14 (C5)x1,x2 ≥0
Dimensions of the model :
2 decision variables
4 technological constraints 2 non-negativity constraints
The feasible region of the model can be graphically represented
33 Linear Programming and its Applications
Over. L.P. App. Sol.
Gra. Sol. Sen. Ana.
How are these models solved
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com