ADM2302 A, B, C, D, E Fall 2015 Assignment # 3 Assignment #3 Transportation Problems, Integer and Binary Programming and Goal programming, ADM2302 students are reminded that submitted assignments must be neat, readable, and well-organized. Assignment marks will be adjusted for sloppiness, poor grammar and spelling, as well as for technical errors. Please note that: While working together is encouraged, plagiarism on assignments will not be accepted. Each student must sign the individual statement of integrity to be included with the submission. Each student must provide an individual original submission of completed Assignment #3. Students should submit a PDF of their type-written (i.e., not handwritten) assignment via blackboard learn by the due-date. Assignments must be stapled or they will not be marked. Problem1: This problem is a combination of binary integer programming and transportation problem A company has 6 sales centers in Ontario and has decided to open new depots to deliver its products from the depots to the sales centers. There are two types of costs associated with the delivery: set-up costs (fixed costs) are capital costs which may usually be written off over several years, and transportation costs which depend on the distance covered. We assume that they have been put on some comparable basis, by taking the costs over a year. There are 6 sites available for the construction of new depots to deliver products to the sales centers. The following table (Table 1) gives the transportation costs (in thousand dollars) of delivering the entire demand of each sales center from a depot (not the unit costs). Certain deliveries that are impossible are marked with the infinity symbol (). Sales Centers Depot 1 2 3 4 5 6 1 100 80 50 50 60 100 2 120 90 60 70 65 100 3 140 110 80 80 75 130 4 160 125 100 100 80 150 5 190 150 130 6 200 180 150 Table 1: Transportation costs for satisfying entire demand of each sales center The construction costs (fixed cost) for each depot as well as the capacity of each depot are listed in Table 2. Fall 2015 Page 1 ADM2302 A, B, C, D, E Fall 2015 Assignment # 3 Depot 1 2 3 4 5 6 Cost(1000$) 3500 9000 10000 4000 3000 9000 Capacity(tons) 300 250 100 180 275 300 Table 2: Fixed costs and capacity limits of the depot locations There are estimations for demand of each sales center which are shown in the following table. Sales center Demand (tons) 1 2 3 4 120 80 75 100 Table 3: Demand data 5 110 6 100 Considering that the demand of a sales center needs to be satisfied and a sales center may be delivered to from several depots, which depots should be opened to minimize the total cost of construction and of delivery, while satisfying all demands? Formulate algebraically the corresponding model for this problem, but Do NOT solve the problem. Problem2: A car rental company has decided to provide roadside services for 6 zones in a large city. The company wants to determine where (zone) to locate the roadside services. To reduce the company's costs the manager wants to locate a minimum number of roadside services and ensure that at least one service is within 15 minutes of each zone. The times (in minutes) required to drive between zones are: To From 1 2 3 4 5 6 1 0 10 20 30 20 20 2 10 0 25 35 20 10 3 20 25 0 15 30 20 4 30 35 15 0 15 25 5 20 20 30 15 0 14 6 20 10 20 25 14 0 Formulate an integer/binary programming model that will select the minimum number of roadside services that the company will need to achieve its policy objective. Do NOT solve the problem. Fall 2015 Page 2 ADM2302 A, B, C, D, E Fall 2015 Assignment # 3 Problem3: Capital budgeting A firm has 6 projects that it would like to undertake over the next 5 years but because of budget limitations not all can be selected. The total budget that the firm has considered to invest in the projects is $12,400,000. The following table displays the expected revenue (NPV) of each project after 5 years and the required yearly capital for each investment. Table 1: Investment Details Capital (in $000) required per year Investment/ Project 1 2 3 4 5 6 Expected NPV ($000) $2700 $3330 $7010 $5770 $2900 $4870 Year 1 $ 975 $1200 $2500 $1550 $1400 $1900 Year 2 $ 350 $ 200 $1200 $1350 $ 350 $1900 Year 3 $ 200 $ 200 $ 850 $ 675 $87.5 $ 350 Year 4 $ 100 $ 200 $ 400 $ 337.5 $ 21.875 $ 350 Year 5 $ 50 $ 200 $ 400 $168.75 $ 0 $ 350 The capital available for the time period of each year is shown in the following table: (The $12,400,000 in investment capital is spread over the 5 years) Year 1 $ 5800 Capital (in $000) allocated per year Year 2 Year 3 Year 4 $ 3500 $ 1300 $ 900 Year 5 $ 900 In addition, the firm must follow a few federal and state laws regarding these projects: 1. 2. 3. Surplus capital funds in any year cannot be carried over from year to year. If the firm decides to invest in the second investment/project, it must also invest in the fourth. If the firm decides to invest in the first investment/project, it cannot invest in the third investment/project. Considering the budget limitations and the laws, which of the investments/projects should be chosen to maximize potential NPV? Formulate the Integer Linear Programming model in algebraic form, and using Excel's Solver to find a solution. Provide a printout of your answer report (Attach the excel file to your submission) Fall 2015 Page 3 ADM2302 A, B, C, D, E Fall 2015 Assignment # 3 Problem4: Goal Programming A large bookstore in Ottawa operates 7 days per week. This bookstore needs the following number of fulltime employees working each day of the week: Day Number of employees Sunday 47 Monday 22 Tuesday 28 Wednesday 35 Thursday 34 Friday 43 Saturday 53 Each employee must work 5 consecutive days each week and then have 2 days off. For example, any employee who works Sunday through Thursday has Friday and Saturday off. This bookstore currently has a total of 60 employees available to work. The director of the department has developed the following set of prioritized goals for employee scheduling: (1) The store wants to avoid hiring any additional employees. Weight=40 (2) The most important days for the department to be fully staffed are Saturday and Sunday. Weight=31 (3) The next most important day to be fully staffed is Friday. Weight=25 (4) The department would like to be fully staffed the remaining 4 days in the week. Weight=20 Formulate a goal programming model to determine the number of employees who should begin their 5-day workweek each day of the week to achieve the department's objectives. Do NOT solve the problem. Fall 2015 Page 4 Problem 4 Let P1 denote the number of employees working on Sunday. P2 denote the number of employees working on Monday. P3 denote the number of employees working on Tuesday. P4 denote the number of employees working on Wednesday. P5 denote the number of employees working on Thursday. P6 denote the number of employees working on Friday. P6 denote the number of employees working on Saturday. Let the bookstore have E number of additional employees. Then, the total number of employee is 60+E 1) As the store wants to avoid hiring any additional employees we have to minimize the value of E. Goal 1 : Min E 2) The most important days for the department to be fully staffed are Saturdays and Sundays. So, we have to minimize 53-P7 and 47-P1. Goal 2: Min (53-P7)+(47-P1) 3) The next most important day to be fully staffed is Friday. So, we have to minimize 43-P6. Goal 3: Min (43-P6) 4) The department would like to be fully staffed for the remaining 4 days in a week. So we have to minimize (22-P2), (28-P3), (35-P4) and (34-P5) Goal 4: Min (22-P2)+(28-P3)+(35-P4)+(34-P5) The total number of employees is 60+E. Let the employees be numbered from 1,2,3,...,59,60,...,59+E,60+E. For each employee numbered i, let the variable cij denote that the employee i has to work on the jth day of the week. So, cij can be either 0 or 1 depending on whether ith employee has the jth day of the week as free or is working on that day. C50 1=1 denotes 50th employee has work on Sunday. C19 7=0 denotes 19th employee is free on Saturday. Thus, 60 E P1= c i 1 i1 60 E P2= c i 1 i2 60 E P3= c i 1 i3 60 E P4= c i 1 i4 60 E P5= c i 1 i5 60 E P6= c i 1 i6 60 E P7= c i 1 i7 Now, as there is a constraint that a person can work for 5 consecutive days and then take a 2 day leave. Therefore, for any employee i, ci j and ci j+1 need to have value 0 and ci j+2=ci j+3=ci j+4=ci j+5=ci j+6=1 (signifying they work for 5 consecutive days), for some j belonging to {1,2,3,4,5,6,7}. Please note that the number j denoting day of work is to be considered as congruence modulo 7 (i.e, 8 1 (mod 7)). (As after Saturday again comes Sunday). Constraints: Pj 60 E c i 1 ij for j 1,2,3,,7 and cij cij 1 0, cij 2 cij 3 cij 4 cij 5 cij 6 1 for some x j (mod 7) where x {1,2,3,} and cij 0 or 1 for i 1, 2,3, ,60 E and j 1,2,3,,7 As the goal programming problem requires using weights. The objective function is Minimize 40(Goal 1)+31(Goal 2)+25(Goal 3)+20(Goal 4) Minimize 40E+31((53-P7)+(47-P1))+25(43-P6)+20((22-P2)+(28-P3)+(35-P4)+(34-P5)) Minimize 6555+40E-31(P1+P7)-25P6-20(P2+P3+P4+P5) satisfying Pj 60 E c i 1 ij for j 1,2,3,,7 and cij cij 1 0, cij 2 cij 3 cij 4 cij 5 cij 6 1 for some x j (mod 7) where x {1,2,3,} and cij 0 or 1 for i 1, 2,3, ,60 E and j 1,2,3,,7 Solving this would provide us the value of E, P1, P2,..., P7 and all cij's which would enable us to find E thereby, providing total number of employees required and cij would provide the days on which the employees should start working. Problem 4 Let P1 denote the number of employees working on Sunday. P2 denote the number of employees working on Monday. P3 denote the number of employees working on Tuesday. P4 denote the number of employees working on Wednesday. P5 denote the number of employees working on Thursday. P6 denote the number of employees working on Friday. P6 denote the number of employees working on Saturday. Let the bookstore have E number of additional employees. Then, the total number of employee is 60+E 1) As the store wants to avoid hiring any additional employees we have to minimize the value of E. Goal 1 : Min E 2) The most important days for the department to be fully staffed are Saturdays and Sundays. So, we have to minimize 53-P7 and 47-P1. Goal 2: Min (53-P7)+(47-P1) 3) The next most important day to be fully staffed is Friday. So, we have to minimize 43-P6. Goal 3: Min (43-P6) 4) The department would like to be fully staffed for the remaining 4 days in a week. So we have to minimize (22-P2), (28-P3), (35-P4) and (34-P5) Goal 4: Min (22-P2)+(28-P3)+(35-P4)+(34-P5) The total number of employees is 60+E. Let the employees be numbered from 1,2,3,...,59,60,...,59+E,60+E. For each employee numbered i, let the variable c ij denote that the employee i has to work on the jth day of the week. So, cij can be either 0 or 1 depending on whether ith employee has the jth day of the week as free or is working on that day. C50 1=1 denotes 50th employee has work on Sunday. C19 7=0 denotes 19th employee is free on Saturday. Thus, 60 E P1= c i 1 i1 60 E P2= c i 1 i2 60 E P3= c i 1 i3 60 E P4= c i 1 i4 60 E P5= c i 1 i5 60 E P6= c i 1 i6 60 E P7= c i 1 i7 Now, as there is a constraint that a person can work for 5 consecutive days and then take a 2 day leave. Therefore, for any employee i, ci j and ci j+1 need to have value 0 and ci j+2=ci j+3=ci j+4=ci j+5=ci j+6=1 (signifying they work for 5 consecutive days), for some j belonging to {1,2,3,4,5,6,7}. Please note that the number j denoting day of work is to be considered as congruence modulo 7 (i.e, 8 1 (mod 7)). (As after Saturday again comes Sunday). Constraints: Pj 60 E c i 1 ij for j 1, 2,3,K ,7 and cij cij 1 0, cij 2 cij 3 cij 4 cij 5 cij 6 1 for some x j (mod 7) where x {1, 2,3,K } and cij 0 or 1 for i 1, 2,3,K ,60 E and j 1, 2,3,K ,7 As the goal programming problem requires using weights. The objective function is Minimize 40(Goal 1)+31(Goal 2)+25(Goal 3)+20(Goal 4) Minimize 40E+31((53-P7)+(47-P1))+25(43-P6)+20((22-P2)+(28-P3)+(35-P4)+(34-P5)) Minimize 6555+40E-31(P1+P7)-25P6-20(P2+P3+P4+P5) satisfying Pj 60 E c i 1 ij for j 1, 2,3,K ,7 and cij cij 1 0, cij 2 cij 3 cij 4 cij 5 cij 6 1 for some x j (mod 7) where x {1, 2,3,K } and cij 0 or 1 for i 1, 2,3,K ,60 E and j 1, 2,3,K ,7 Solving this would provide us the value of E, P1, P2,..., P7 and all c ij's which would enable us to find E thereby, providing total number of employees required and c ij would provide the days on which the employees should start working