” 辅导EBS2043设计、 写作Software编程AssignmentsEBS2043Introduction to Software in Econometrics and OperationsResearchOperations Research PartAcademic Year: 2020/2021Period: 3School of Business and EconomicsBachelorAcademic year 20192020 Maastricht University School of Business and EconomicsNothing in this Publication may be reproduced and/or made public by means of printing, offset, photocopyor microfilm or in any digital, electronic, optical or any other form without the prior written permissionof the owner of the copyright.Introduction to Software in OR / EBS2043 20192020 Page 2Contents1 General Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.1 Assignments Deliverables . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Grading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1 Part A: Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . 62.2 Part B: Integer Linear Programming in Logistics . . . . . . . . . . . . . 102.3 Part C: Combinatorial Optimization . . . . . . . . . . . . . . . . . . . 152.4 Part D: Discrete Network Location Models . . . . . . . . . . . . . . . . 172.5 Part E: Logic Puzzles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22Introduction to Software in OR / EBS2043 20192020 Page 31 General Information1.1 Assignments DeliverablesFor this course you have to model, implement, and solve four optimization problems fromdifferent domains. Part A: non-integer Linear Programming and economic interpretations Part B: Integer Linear Programming in logistic context Part C: Combinatorial Optimization problems Part D: Discrete Network Location models Part E: Logic PuzzlesParts A-D each contain four different problems. The problems you have to solve dependon your student ID. Here is how you find out which problems you have to solve: Consider the last Four digits of your student ID. Replace each digit by the remainder when it is divided by four. The obtained Sequence of four numbers shows you which problem you have to solvefrom Parts A-D.Here is an example: your student ID is i6214235. The last four digits are 4235. Wheneach digit is divided by four, the remainders are 0231. Hence youd have to solve problemsA0, B2, C3, and D1. If you are not sure which problems you have to solve, please let meknow.If you like logic puzzles, you can replace your assigned problem from part A or B by apuzzle problem of your choice from Part E (be aware: they may be harder than they looklike).For each problem you have to submit:1. a written report containing(a) the description of your LP/ILP model and the answers to the questions of theassignment (if any),(b) the solutions and the objective values to the problems with the given data,2. the source files of your implementation.Introduction to Software in OR / EBS2043 20192020 Page 4Important: Please adhere to the following conventions: name all files that you submit beginning with FirstNameLastName,e.g. AndreBerger Solutions.pdf, AndreBerger Submission.zip. All your written ILP formulations as well as their explanation and the solutionsto the given instances should be written into one pdf document (one section perassignment). the source files should be organized in folders, one for each problem that you submit each source file should contain your name and the number of the assignment at thetop as a comment At the end, compress all your files in a single .zip folder (no tar, rar or othercompressing formats!).As a conclusion, you should have a .zip folder containing one pdf document and foursubfolders, each holding the source files of one problem.The deadline to submit your solutions in Canvas is Thursday, January 21st, 2021, at23:59pm.In addition to your submission an individual meeting will be scheduled on Friday, January22nd, 2021, or on MondayJanuary 25th, 2021, where you briefly have to explain one ofyour solutions.1.2 GradingFor each of the Four assignments that you submit you can get a maximum number of 25points (13 points for the report including the model and solutions, and 12 points for thesource code of your implementation).You need at least 55 points in total to pass this skills course. If you have at least 55 points, then your overall grade is the total number of pointsdivided by 10, rounded to the nearest half integer. If you do not have at least 55 points, then you will take the resit: another set ofproblems will then be provided to you, and will have to model, implement, and solvefour new problems, as well as comment your results and draw some conclusions.Introduction to Software in OR / EBS2043 20192020 Page 51.2.1 Report assessmentThe report should be clearly written and structured. More precisely, please be sure that the (I)LP is understandable: describe your parameters, variables, objective function,and constraints in a clear way (check the summation indices if any, etc.); explainbriefly the objective function and the constraints as done in academic papers, you answer the questions regarding the interpretation (if any), you can also make some comments about your choice for the models or about yourresults.1.2.2 Implementation assessmentHere are some remarks to help you to assess your implementation.A sufficient implementation compiles and Runs without errors, implements the correct LP or ILP model, returns the correct solution, and has a human readable source code.A nice implementation earning more points has a clearly readable and understandable source code, i.e. the source code is well structured (makes appropriate use of methods andclasses) is well commented, has reasonable and understandable variable names and method names, and avoids unnecessary overhead (unused variables, other warnings, etc.), separates the model and the data, i.e. it can also easily be used for the same problemif some of the data change (preferably by reading the data from a file or through auser interface), and is as memory and run time efficient as possible, and outputs the Solution in a nice way, preferably it writes the solution to a file if thereare many information.Introduction to Software in OR / EBS2043 20192020 Page 62 Assignments2.1 Part A: Linear ProgrammingDeliverables: a written report with your LP formulation of the problem and the answersto the questions, an optimal solution to the given instance, and your source codes.2.1.1 Assignment A0: Investment Plan IFox Enterprises is considering six projects for possible construction over the next fouryears. The expected returns and cash outlays for the projects are given below. Fox canundertake any of the projects partially or completely, during the whole 4-year period. Apartial undertaking of a project will prorate both the return and cash outlays proportionally.Cash outlay ($1000)Project Year 1 Year 2 Year 3 Year 4 Return ($1000)1 10.5 14.4 2.2 2.4 32.402 8.3 12.6 9.5 3.1 39.803 10.2 14.2 5.6 4.2 37.754 7.2 10.5 7.5 5.0 34.805 12.3 10.1 8.3 6.3 38.206 9.2 7.8 6.9 5.1 27.35Available funds ($1000) 60 70 35 201. Formulate the problem as a linear problem, and determine the optimal project mixthat maximizes the total return. Ignore the time value of money.2. Use CPLEX to get the information needed to answer the following questions. Foreach question, explain which piece of information enables you to answer.(a) What are the binding constraints?(b) What would you gain if the RHS of one of those binding constraints increasedof one unit?(c) To what extend Could the return of project 6 be increased without changingthe optimal solution?3. How would you modify your linear formulation to take into account the followingadditional features:Suppose that if a portion of project 2 is undertaken then at least an equal portion ofproject 6 must be undertaken. Suppose that any funds left at the end of a year areused in the next year.What is the impact of those two new characteristics on your first optimal solution?Introduction to Software in OR / EBS2043 20192020 Page 72.1.2 Assignment A1: Investment Plan IIInvestor Doe has $10 000 to invest in four projects. The following table gives the cashflow for the four investments.Cash flow ($1000) at the start ofProject Year 1 Year 2 Year 3 Year 4 Year 51 -1.00 0.50 0.30 1.80 1.202 -1.00 0.60 0.20 1.50 1.303 0.00 -1.00 0.80 1.90 0.804 -1.00 0.40 0.60 1.80 0.95The information in the table can be interpreted as follows. For project 1, $1.00 investedat the start of year 1 will yield $0.50 at the start of year 2, $0.30 at the start of year 3,$1.80 at the start of year 4, and $1.20 at the start of year 5. The remaining entries can beinterpreted similarly. The entry 0.00 indicates that no transaction is taking place. Eachyear, Doe has the additional option of investing in a bank account that earns 6.5% annualprofit. All funds accumulated at the end of one year can be reinvested in the followingyear. Doe can invest in projects 1, 2, and 4 only at the start of year 1. He can invest inproject 3 only at the start of year 2. However, investing in the bank account is possibleat the start of years 1, 2, 3, and 4.1. Formulate the problem as a linear program to maximize the total earned moneyat the start of year 5. Implement your mathematical program to get the optimalsolution and optimal value.2. Use CPLEX to get the information needed to answer the following questions. Foreach question, Explain which piece of information enables you to answer.(a) What are the binding constraints?(b) What would you gain if the RHS of one of those binding constraints increasedof one unit (without re-running the model)?3. How would you modify your linear formulation to take into account the followingadditional feature:Suppose that if an investment is made in project 2, then an amount at least as largeshould be invested in project 4.What is the impact of this new characteristic on your first optimal solution?Introduction to Software in OR / EBS2043 20192020 Page 82.1.3 Assignment A2: ErstvilleThe city of Erstville is faced with severe budget shortage. Seeking a long-term solution, thecity council votes to improve the tax base by condemning an inner-city housing area andreplacing it with a modern development. The project involves two phases: (1) demolishingsubstandard houses to provide land for the new development, and (2) building the newdevelopment. The following is a summary of the situation.1. As many as 300 substandard houses can be demolished. Each house occupies a0.25-acre lot. The cost of demolishing a condemned house is $2000.2. Lot sizes for new single-, double-, triple-, and quadruple-family homes (units) are0.18, 0.28, 0.4 and 0.5 acre, respectively. Streets, open space, and utility easementsaccount for 15 % of available acreage.3. In the new Development the triple and quadruple units together account for at least25 % of the total. Single units must be at least 20 % of all units and double unitsat least 10 %.4. The tax levied per unit for single, double, triple, and quadruple units is $1000,$1900, $2700 and $3400, respectively.5. The construction cost per unit for single-, double-, triple-, and quadruple- familyhomes is $50000, $70000, $130000, $160000, respectively. Financing through a localbank can amount to a maximum of $15 million.Assume that if you get a fractional number of units you can round it up to the closestinteger. How many units of each type should be constructed to maximize tax collection?1. Formulate the problem as a linear program to maximize the tax collection. Implementyour mathematical program in CPLEX to get the optimal solution andoptimal value.2. Use CPLEX to get the information needed to answer the following questions. Foreach question, explain which piece of information enables you to answer.(a) What are the binding constraints?(b) What should be the minimum tax levied per unit for the quadruple houses tobecome profitable enough?(c) What would you gain if the loan can be extended until $15.5 million (withoutre-running the model)?Introduction to Software in OR / EBS2043 20192020 Page 92.1.4 Assignment A3: Urban RenewalA city will undertake four urban renewal housing projects over the next five years. Eachproject has a different Starting year and a different duration. The following table providesthe basic data of the situation.Year 1 Year 2 Year 3 Year 4 Year 5 Cost Annual income(million $) (million $)Project 1 Start End 5 0.05Project 2 Start End 8 0.07Project 3 Start End 15 0.15Project 4 Start End 1.2 0.02Budget(million $)3 6 7 7 7Projects 1 and 4 must be finished completely within their durations. The remaining twoprojects can be finished partially within their durations, if necessary. Each project mustbe at least 25% completed within its duration. At the end of each year, the completedsection of a project is immediately occupied by tenants and a proportional amount ofincome is realized. For example, if 40% of project 1 is completed in year 1 and 60% inyear 3, the associated income over the five-year planning horizon is:0.4 $50000(for year 2) + 0.4 $50000(for year 3) + (0.4 + 0.6) $50000(for year 4)+(0.4 + 0.6) $50000((for year 5) = (4 0.4 + 2 0.6) $50000.What is the optimal schedule for the projects that will maximize the total income overthe five-year horizon?For simplicity, disregard the time value of money.1. Formulate the problem as a linear program to maximize the total income over thefive-year horizon. Implement your mathematical program in CPLEX to get theoptimal solution and optimal value.2. Use CPLEX to get the information needed to answer the following questions. Foreach question, explain which piece of information enables you to answer.(a) What are the binding constraints?(b) What would you loose if the budget of year 2 was reduced of 1 million $(withoutre-running the model)?Introduction to Software in OR / EBS2043 20192020 Page 102.2 Part B: Integer Linear Programming in LogisticsDeliverables: a written report with your ILP formulation of the problem an optimalsolution to the given instance, and your source codes.2.2.1 Assignment B0: capacitated facility location ITrendCoats is a manufacturer of jeans and sells its products on the North America market.Actually, the firm has a Plant in Denver with a capacity of 1500 thousands of units, twowarehouses: one in Chicago and one in Salt Lake City, each with a capacity of 1000thousands of units, and serves markets in Seattle, Sacramento, Houston, Toronto, Miamiand Detroit. The market demand and the transportation costs are shown below:Transportation Cost Seattle Sacramento Houston Toronto Miami Detroitper thousand units ($)Chicago 165 183 124 86 132 67Salt Lake City 110 75 132 210 153 195Demand 190 150 90 200 240 130(thousand units)The transportation cost of one thousand units between the plant in Denver and thewarehouse in Chicago is $105 and from the plant in Denver to the warehouse in Salt LakeCity is $68. Assume that the jeans are packed in boxes of one thousand units and thatthey cannot be split.The demand is growing dramatically. In order to satisfy this demand, the managers ofTrendCoats have decided to change their network design, several options are studied: A new plant can be opened in Wichita (in addition to the low capacity plant alreadyexisting in Denver) or the capacity of the plant in Denver can be increased (a highcapacity plant would take the place of the low capacity one). The capacity of the warehouse in Chicago and/or Salt Lake City can be increasedto 2000 thousands of units if needed.Introduction to Software in OR / EBS2043 20192020 Page 11Plant capacities, market demand, fixed costs incurred by the transformations and transportationcosts are shown below:Transportation Cost Chicago Salt Lake City Capacity Fixed Costper thousand units ($) (thousand Units) (thousand $)Wichita 87 75 1500 2000Denver (low capacity) 105 68 1500 0Denver (high capacity) 105 68 2500 1500Transportation Cost Seattle Sacramento Houston Toronto Miami Detroit Fixed Costper thousand units ($) (thousand $)Chicago 165 183 124 86 132 67 0(low cap.)Chicago 165 183 124 86 132 67 250(high cap.)Salt Lake City 110 75 132 210 153 195 0(low cap.)Salt Lake City 110 75 132 210 153 195 200(high cap.)Demand 480 420 220 500 450 320(thousand units)1. Write down the mixed integer linear programming formulation that would minimizethe total transportation and fixed cost of TrendCoats (taking the best decisionsamong the propositions above).2. Solve the formulation with CPLEX. Describe the optimal solution and interpretthe value of the variables in the context. Give the optimal value associated to thissolution.Introduction to Software in OR / EBS2043 20192020 Page 122.2.2 Assignment B1: capacitated facility location IISC Consulting, a supply chain consulting firm, must decide on the location of its homeoffices. Its clients are located primarily in the 16 states listed in the table below. Thereare four potential sites for Home offices : Los Angeles, Tulsa, Denver and Seattle. Theannual fixed cost of locating an office in Los Angeles is $165428, in Tulsa it is $131 230,in Denver it is $140 000, and in Seattle it is $145 000. The expected number of trips toeach state and the travel costs per trip from each potential site to each state are shownin the table below.State Los Angeles Tulsa Denver Seattle Number of tripsWashington 150 250 200 25 40Oregon 150 250 200 75 35California 75 200 150 125 100Idaho 150 200 125 125 25Nevada 100 200 125 150 40Montana 175 175 125 125 25Wyoming 150 175 100 150 50Utah 150 150 100 200 30Arizona 75 200 100 250 50Colorado 150 125 25 250 65New Mexico 125 125 75 300 40North Dakota 300 200 150 200 30South Dakota 300 175 125 200 20Nebraska 250 100 125 250 30Kansas 250 75 75 300 40Oklahoma 250 25 125 300 55Each consultant is expected to take at most 25 trips each year. If there are no restrictionson the number of consultants at a site and the goal is to minimize costs, where shouldthe home offices be located and how many consultants should be assigned to each office ?What is the annual cost in terms of facility and travel?1. Write down an integer linear programming formulation for this problem.2. Solve it using CPLEX. Describe the optimal solution and interpret it in the context.What is the optimal value of this solution?3. If, at most, 10 consultants are to be assigned to a home office, where should theoffices be set up? How many consultants should be assigned to each office? Whatis the annual cost of this network?Introduction to Software in OR / EBS2043 20192020 Page 132.2.3 Assignment B2: Production planning IA vacuum cleaner manufacturer tries to plan ahead in order to effectively address theseasonal variation appearing in the Annual demand of its products. A planning horizonof 6 months is used. The demand forecast for the next six months along the number ofworking days are as in Table 1.Month Demand Forecast No. of Working DaysJan. 1800 22Feb. 1500 19March 1100 21April 900 21May 1100 22June 1600 20Table 1: Demand forecast and number of working days per monthThe associated cost break-down is as described in Table 2.Item CostMaterial $50 per unitInventory Holding $5 per unit per monthCost of Subcontracting $120 per unitHiring and Training $1000 per workerLayoff $1500 per workerRegular Labor cost per hour $15 per employee per hourOvertime labor cost per hour $20 per employee per hourTable 2: CostsAt the end of December, the company has an inventory of 400 units and 38 workers, eachof whom works 8 hours of non-overtime per day. In order to produce one vacuum cleaner,5 hours of labor work are required. At the end of each month, the company wants to havea minimum inventory level of a quarter of the corresponding demand.1. Write the linear programming model of this problem that would determine theoptimal production planning.2. Solve it using CPLEX. Describe the optimal solution and interpret it in the context.What is the optimal value of this solution?3. Currently, backorders are allowed. All stock-outs are backlogged and supplied fromthe following months production. The backorder cost is $7 per unit and per month.However, assume that at the end of the sixth months, all the demands are satisfied.Adapt the Previous model to consider the possible backorders and determine theoptimal production planning. What are the costs over the 6 months in this case?Introduction to Software in OR / EBS2043 20192020 Page 142.2.4 Assignment B3: Production Planning IIA local canning company sells canned vegetables to a supermarket chain in the Minneapolisarea. A typical case of canned vegetables requires an average of 0.2 day of labor toproduce. The aggregate inventory on hand at the end of June is 800 cases. The demandfor the vegetables can be accurately predicted for about 18 months based on orders receivedby the firm. The predicted demands (in hundreds of cases) for the next 18 monthsare as follows :Month Demands workdays Month Demands workdaysJuly 23 21 April 29 20August 28 14 May 33 22September 42 20 June 31 21October 26 23 July 20 18November 29 18 August 16 14December 58 10 September 33 20January 19 20 October 35 23February 17 14 November 28 18March 25 20 December 50 10The firm currently has 25 workers. The cost of hiring and training a new worker is $1000 and the cost to lay off one worker is $1 500. An employee works 8 hours per day andis paid $10 per hour. The firm estimates a cost of $2.8 to store a case of vegetables for amonth. The material to built one case of vegetables costs $0.5. The firm can also chooseto subcontract the production for $24 per case. They would like to have 1 500 cases ininventory at the end of the 18-month planning horizon.1. Write the problem as a linear program.2. Determine the strategy that the firm must apply in order to minimize its costs usingCPLEX.3. Analyze how the number of units subcontracted changes when the price of subcontractingincreases or decreases. Show this relation on a chart in the writtenreport. Determine the limit price above which it is not interesting to subcontractthe production and the limit for which it is more interesting to subcontract only.Introduction to Software in OR / EBS2043 20192020 Page 152.3 Part C: Combinatorial OptimizationFor your assignment, you are provided with five instances that you have to solve. You aresupposed to:1. Develop an integer linear program for the given problem. Then, implement it usingCPLEX.2. For each of the five instances, find the optimal integer solution.3. For each of the five instances, find the optimal solution to the corresponding linearprogramming relaxation, i.e. when all integer/binary variables are relaxed to takenonnegative real values.4. For each of the five instances, measure the running times needed to solve bothversions.5. For each of the five instances, determine the GAP of the solution of the relaxationcompared to the optimal integer solution. The GAP is defined as the ratio betweenthe difference of the best bound (provided by the relaxation in this case) and the bestinteger solution value over the best integer solution value. The GAP is expressed inpercentages and Measures how good a solution is (the closer to 0, the better):|best relaxation value best integer value||best integer value|6. For one of the five instance, describe the optimal solution in the context (= inwords).Deliverables: a written ILP formulation of the problem, the following table (filled withvalues), a brief description of the results in the table, the description of one optimalsolution in the context of the assignment, and your source codes.Instance Optimal Run time Optimal Run time GAPvalue (ILP) ILP (ms) value (LP) LP (ms)12345Introduction to Software in OR / EBS2043 20192020 Page 162.3.1 Assignment C0 – The Bin Packing ProblemGiven a set of items I = {1, . . . , n}, each having a size si [0, 1] for i I, determine anallocation of items to bins of size 1, that minimizes the number of bins used.2.3.2 Assignment C1 – The Knapsack problemGiven a set of items I = {1, . . . , n}, each having a required space siin cm2, a durationdiin minutes, and a value vi R+ for i I. The plant Has an available space of 300cm2 and a workforce working 8 hours. Select the items such that the value of the selecteditems is maximized.2.3.3 Assignment C2 – Minimizing weighted completion timesGiven a set J = {1, . . . , n} of jobs, each having a processing time pj R+ and a weightwj R+, determine an allocation of the jobs to a single machine that minimizes theweighted sum of completions times of the jobs, i.e. PjJ wjCj, where Cjis the time thatjob j is finished.Hint: you have to declare as a decision whether a job precedes another one.2.3.4 Assignment C3 – The Scheduling Parallel Machines ProblemGiven a number m of machines, and a set J = {1, . . . , n} of jobs, each having a processingtime pj R+, determine an allocation of the jobs to the machines that minimizes themakespan of the schedule, i.e. the finish time of the last machine.Introduction to Software in OR / EBS2043 20192020 Page 172.4 Part D: Discrete Network Location ModelsFor the assignment, you need first to be able to solve the shortest path problem:Given an undirected graph G = (V, A), arc weights w : A R+, a source s V anda destination t V , determine the shortest path in G between s and t. Then, use thisalgorithm to determine the shortest distance between any pair of vertices in V . Presentyour results as a distance matrix.Using this as a tool to Compute a distance matrix, four location problems are then presented.For your assignment, you are provided with five instances that you have to solve. You aresupposed to:1. Present your ILP or algorithm to solve the shortest path.2. For your specific assignment, find the name of this type of problem in the literature.Provide the reference(s) you used.3. Develop an integer linear program for the given assignment. Then, implement itusing CPLEX.4. For each of the five instances, find the optimal integer solution and provide therunning time (without the time to compute the distance matrix).5. For one of the five instances, interpret the solutions in the actual context.Deliverables: a written report with all the above elements, and your source codes.Introduction to Software in OR / EBS2043 20192020 Page 182.4.1 Assignment D0 – Facility locationThe customers and the potential facilities of a country have been aggregated in n regions.Some of the regions are connected to each others through a set of m arcs.A company would like to open p facilities among these regions to supply all the customersin minimizing the total distance to travel.We assume that all the facilities have the same fixed cost to get opened and that theyhave an infinite capacity. A customer can be supplied by only one facility.Write down a linear model for this problem. Solve it with p = 2, 3, 4. Include the followingtable filled in in your report. Comment the results.Optimal value Run time (ms)Introduction to Software in OR / EBS2043 20192020 Page 192.4.2 Assignment D1 – Hospital locationInhabitants have been grouped in n regions. Some of the regions are connected to eachothers through a set of m arcs. We want to locate new hospitals in some regions suchthat each person in each Region can reach at least one of them in less than a maximumdistance M. Determine the minimum number of hospitals to build.Write down a linear model for this problem. Solve it with M = 3, 5, 10. Include thefollowing table filled in in your report. Comment the results.Optimal value Run time (ms)Introduction to Software in OR / EBS2043 20192020 Page 202.4.3 Assignment D2CareFor is a well-known supermarket chain. The managing director is aware that mo”
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
