More Applications of Linear and Non-linear Programming

More Linear and Non-linear Programming Models z Announcements: – Lecture check problems = practice for quiz – Can everyone attend office hours? • 3-5 Monday and Wednesdays – Should I post lectures on web before class? – Homework cover sheets 1 Overview of Lecture z Goals – get practice in recognizing and modeling linear constraints and objectives – and non-linear objectives – to see a broader use of models in practice z Models – Postal Worker Problem – Portfolio Optimization – Conjoint Analysis 2 Overview z Scheduling Postal Workers (5 in 7) – The model – Practical enhancements or modifications – Two non-linear objectives that can be made linear – A non-linear constraint that can be made linear 3 Scheduling Postal Workers z Each postal worker works for 5 consecutive days, followed by 2 days off, repeated weekly. Day Demand z Mon Tues Wed Thurs Fri 17 13 15 19 14 Sat Sun 16 11 Minimize the number of postal workers (for the time being, we will permit fractional workers on each day.) 4 Formulating as an LP z Select the decision variables – Let x1 be the number of workers who start working on Monday, and work till Friday – Let x2 be the number of workers who start on Tuesday … – Let x3, x4, …, x7 be defined similarly. 5 The linear program Day Demand Minimize subject to Mon Tues Wed Thurs Fri 17 13 15 19 14 Sat Sun 16 11 z = x1 + x2 + x3 + x4 + x5 + x6 + x7 x1 + x4 + x5 + x6 + x7 ≥ 17 x1 + x2 + x5 + x6 + x7 ≥ 13 x1 + x2 + x3 + x6 + x7 ≥ 15 x1 + x2 + x3 + x4 + x7 ≥ 19 x1 + x2 + x3 + x4 + x5 ≥ 14 x2 + x3 + x4 + x5 + x6 ≥ 16 x3 + x4 + x5 + x6 + x7 ≥ 11 Mon. Tues. Wed. Thurs. Fri. Sat. Sun. xj ≥ 0 for j = 1 to 7 6 A Closer Look at the Constraint Matrix x1 x2 x3 x4 x5 x6 x7 1 0 0 1 1 1 1 ≥ 17 Mon 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 ≥ ≥ ≥ ≥ ≥ ≥ 13 15 19 14 16 11 Tues Wed Thurs Fri Sat Sun It is cyclically repeating in both rows and columns. 7 On the selection of decision variables z A choice of decision variables that doesn’t work – Let yj be the number of workers on day j. – No. of Workers on day j is at least dj. (easy to formulate) – Each worker works 5 days on followed by 2 days off (hard). z Conclusion: sometimes the decision variables incorporate constraints of the problem. – Hard to do this well, but worth keeping in mind – We will see more of this in integer programming. 8 Some Modifications of the Model z Suppose that there was a pay differential. The cost of workers who start work on day j is cj per worker. z Suppose that one can hire part time workers (one day at a time), and that the cost of a part time worker on day j is pj. Work with your partner to modify the model taking into account the new information. What are the new decision variables? What are the changes to the model? 9 What are the new decision variables? Minimize subject to z= x1 + x4 + x5 + x6 + x7 x1 + x2 + x5 + x6 + x7 x1 + x2 + x3 + x6 + x7 x1 + x2 + x3 + x4 + x7 x1 + x2 + x3 + x4 + x5 x2 + x3 + x4 + x5 + x6 x3 + x4 + x5 + x6 + x7 ≥ ≥ ≥ ≥ ≥ ≥ ≥ 17 13 15 19 14 16 11 xj ≥ 0 for j = 1 to 7 10 Another Enhancement z Suppose that the desirable number of workers on day j is dj, but it is not required. Let sj be the “excess” number of workers day j. sj > 0 if there are more workers on day j than dj; otherwise sj ≤ 0. z What is the minimum cost schedule, where the “cost” of having too many workers on day j is fj(sj), which is a non-linear function? 11 What are the new decision variables? What is the resulting non-linear model? Minimize z = subject to x1 + x4 + x5 + x6 + x7 x1 + x2 + x5 + x6 + x7 x1 + x2 + x3 + x6 + x7 x1 + x2 + x3 + x4 + x7 x1 + x2 + x3 + x4 + x5 x2 + x3 + x4 + x5 + x6 x3 + x4 + x5 + x6 + x7 xj ≥ 0 for j = 1 to 7 d1 d2 d3 d4 d5 d6 d7 12 A non-linear function that can be made linear. Suppose we want to minimize |x – 4| + |y – 7| subject to other constraints. This is equivalent to minimize s.t. z1 + z2 z1 ≥ x – 4 z1 ≥ 4 – x z2 ≥ y – 7 z2 ≥ 7 – y + other constraints Suppose the objective is minimize |s1| + … + |s7|. Take a minute and modify the last NLP to make it a linear program. 13 Minimize subject to x1 + x4 + x5 + x6 + x7 x1 + x2 + x5 + x6 + x7 x1 + x2 + x3 + x6 + x7 x1 + x2 + x3 + x4 + x7 x1 + x2 + x3 + x4 + x5 x2 + x3 + x4 + x5 + x6 x3 + x4 + x5 + x6 + x7 xj ≥ 0 for j = 1 to 7 d1 d2 d3 d4 d5 d6 d7 14 A 2nd non-linear objective that can be made linear. Minimize y = max[ (x - 1) , (.5x + 1) ] s.t. other constraints. 5 min s.t. y y≥ x - 1 y ≥ .5x + 1 + other constraints 4 3 2 1 1 2 3 4 5 6 15 Exercise: minimize the maximum number of excess workers needed on any day: that is Minimize max (s1, …, s7), where sj ≥ 0 for each j. Minimize subject to x1 + x4 + x5 + x6 + x7 - s1 x1 + x2 + x5 + x6 + x7 - s2 x1 + x2 + x3 + x6 + x7 - s3 x1 + x2 + x3 + x4 + x7 - s4 x1 + x2 + x3 + x4 + x5 - s5 - s6 x2 + x3 + x4 + x5 + x6 x3 + x4 + x5 + x6 + x7 - s7 xj ≥ 0 , sj ≥ 0 for j = 1 to 7 = 17 = 13 = 15 = 19 = 14 = 16 = 11 16 A ratio constraint: Suppose that we need to ensure that at least 30% of the workers have Sunday off. How do we model this? (x1 + x2 )/(x1 + x2 + x3 + x4 + x5 + x6 + x7) ≥ .3 Note: the denominator is always positive. If we multiply both sides of the inequality by the denominator, we get a linear constraint. (x1 + x2 ) ≥ .3 (x1 + x2 + x3 + x4 + x5 + x6 + x7) .7x1 + .7x2 - .3x3 - .3x4 - .3x5 - .3x6 - .3x7 ≥ 0 17 Other enhancements z z z z Require that each shift has an integral number of workers – integer program Consider longer term scheduling – model 6 weeks at a time Consider shorter term scheduling – model lunch breaks Model individual workers – permit worker preferences 18 Towards a Portfolio Model z an investment model over multiple time periods z maximize return and minimize risk NEOS Portfolio Problem 19 Returns of a portfolio Example: Stock A has a return of 10% Stock B has a return of 20% Return on Investment 0.2 Return 0.18 0.16 0.14 0.12 0.1 0 0.2 0.4 0.6 0.8 1 Proportion of Stock A 20 Evaluating Risk Stock B has a s.d. of .223 Cov(A, B) = 0 SD of Return of Portfolio Stock A has a s.d. of .223 0.230 0.220 0.210 0.200 0.190 0.180 0.170 0.160 0.150 0 0.2 0.4 0.6 0.8 1 Proportion of Stock A Varying the Covariance 21 Portfolio Selection Example z There are 3 candidate assets for out portfolio, X, Y and Z. The expected returns are 30%, 20% and 8% respectively (if possible we would like at least a 12% return). Suppose the covariance matrix is: X z What are the variables? Y Z X Y Z 3 1 1 2 −0.5 −0.4 −0.5 −0.4 1 Let X,Y,Z be percentage of portfolio of each asset. 22 Portfolio Optimization Minimize Variance of Portfolio subject to Expected Return >= Required return investments sum to 100% investments are non-negative Variance of portfolio = variance due to individual investments + 2 * sum of covariances. 23 Portfolio Selection Example Min 3 X 2 + 2Y 2 + Z 2 + 2 XY − XZ − 0.8YZ st 1.3 X + 1.2Y + 1.08 Z ≥ 1.12 X +Y + Z = 1 X ≥ 0, Y ≥ 0, Z ≥ 0 The quadratic programs (non-linear programs) arising from portfolio problems are easy to solve. Portfolio Example 24 Risk Risk vs. vs. Return Return Variance of Portfolio 3.5 3 2.5 2 1.5 1 0.5 0 0.12 0.17 0.22 0.27 Expected Return 25 Portfolio Optimization in Practice z Problems arising in practice often have additional constraints. z Using linear programming one can handle: – upper bounds on each investment – lower bound (or upper bound) on the proportion of assets held in high tech firms, or whatever. z Other constraints and costs can be handled using integer programming – transaction costs – lower bounds on investments that are chosen 26 What is Conjoint Analysis? z Conjoint analysis is a data analysis for estimating how much respondents value different features. z Illustration: Consider a PDA that has 6 attributes – Size – Cell phone – Hands free operation – Extended battery – Wireless internet – Price z How much does the respondent value each attribute? 27 Why Use Conjoint Analysis? z Possibility: Ask the respondent to estimate the partworths. z Alternative: Use stated preferences on final products to backward infer partworth values. 28 Conjoint Analysis z Widely used in product designs and pricing z Lots of research over the past 25 years. 29 Simplified PDA Example ∅ B T BT T = Titanium Case; B = Big Size Four PDA Models: • Model ∅ – Small / Leather Case • Model B – Big / Leather Case • Model T – Small / Titanium Case • Model BT – Big / Titanium Case 30 Simplified PDA Example ∅ B T BT T = Titanium Case; B = Big Size Utilities given partworths v(B) and v(T): U∅ = 0 UT = v(T) UB = v(B) UBT = v(B) + v(T) 31 v(T) ∅ T BT B B v(B) T BT ∅ B Which PDA is preferred? 32 ∅ B BT T T = Titanium Case; B = Big Size A consumer then rank orders the products (or cards), and we infer information about the values. Example: The customer prefers BT, B, T, and ∅, in order Then u(BT) > u(B) > u(T) > u(∅). Î v(B) + v(T) > v(B) > v(T) > 0 Consider a graph in 2 dimensions. 33 v(T) T > BT > ∅ > B ∅ T B B T BT BT > T > B > ∅ BT T > ∅ > BT > B BT > B > T > ∅ ∅ > T > B > BT B > BT > ∅ > T ∅ ∅ > B > T > BT v(B) B B > ∅ > BT > T Example: Suppose 0 < v(T) < v(B) ≤ $50. 34 35 Conjoint Analysis. Let v(j) be the value of aspect j. For each product i, U i = ∑ v( j) j ∈Aspect ( i ) Min s.t . 2 ( y ) ∑ i , j ij U i = ∑ j∈Aspect ( i ) v ( j ) U i + y ij ≥ U ( j ) yi j ≥ 0 whenever product i is preferred to product j. for all i and j 36 Conjoint analysis z There are lots of bells and whistles one can add z Important part of marketing profession z presented in a lecture in May: a recent improvement that may yield better results due to – Dahan – Hauser – Orlin – Yee 37 Summary z Postal worker problem – illustration of different types of constraints and objectives that can arise and how to deal with them z Portfolio Optimization z Conjoint Analysis 38 Lecture check problems** z z z z z Section 3.7 Section 3.8 Section 3.9 Section 3.10 Section 3.11 #2 #1 #1 #1 #1 ** Lecture check problems are practice problems for the quizzes. They are intended to be at about the same level of difficulty. 39