Econ 172A Fall 2008 Problem Set 3 Instructions Due December 2 2008 I may not cover some of this material until the last week of class If so I will reduce the assignment on November 25 2008 1 Consider the linear integer programming problem max 22x1 subject to 5x1 2x1 x1 8x2 2x2 x2 2x2 16 4 4 In addition x1 and x2 are constrained to be non negative integers Solve the linear programming problem ignoring integer constraints graphically Round this solution to the nearest integer solution and check whether it is feasible Next enumerate all of the rounded solutions by rounding the solution to the linear programming problem in all possible ways This means that there might be four possibilities If for example you find that the solution to the LP is 1 2 2 9 then the nearest integer solution is 1 3 while the four rounded possibilities are 1 2 1 3 2 2 2 3 For each rounded solution check for feasibility and if feasible calculate the value Do any of these possibilities actually solve the given integer programming problem If so explain why If not then use branch and bound techniques to find a solution to the integer programming problem 2 A machine shop makes two products Each unit of the first product requires three hours on Machine 1 and two hours on Machine 2 Each unit of the second product requires 2 hours on Machine 1 and 3 hours on Machine 2 Machine 1 is available at most 8 hours each day Machine 2 is available at most 7 hours each day The profit per unit sold is 16 for the first product and 10 for the second product The amount of each product produced per day much be an integer multiple of 25 The objective is to determine the daily mix of production quantities that will maximize profit Formulate an integer programming problem that describes this problem Solve the problem using the branch and bound technique You may solve the associated relaxed linear programming problems either by graphing or by using Excel 3 Four students from each of four grades a total of 16 students are eligible to go on a field trip Four cars are available to transport the students Two cars can carry four people each Two cars can carry three people each School rules require that no more than two people from each grade travel in the same car Use a network flow model to determine the maximum number of people than can go on the field trip You may assume that there are at least 16 students in each grade Hint Imagine a network in which the source is the school From the school are four edges each representing students from a different grade This leads to a node for each grade From each of these nodes there are four edges one of these edges represents the students from a particular grade who travel in a particular car These edges go to four nodes which can be thought of as students going in car i These edges have capacity two Finally from each of the four nodes representing students going in car i draw an edge to the sink representing students who arrive at field trip location 4 Five employees are available to perform four jobs The time it takes each person to perform each job is given in the table below Determine the assignment of employees to jobs that minimizes the total time required to perform the four jobs Dashed lines appear when it is impossible to schedule a person to a job That is Person 2 is unable to do Job 2 1 P erson P erson P erson P erson P erson 1 2 3 4 5 Job 1 Job 2 Job 3 Job 4 22 18 30 18 18 27 22 26 20 28 28 16 22 14 21 25 28 5 Suppose it costs 30 000 to purchase a new car The annual operating cost and resale value of a used car are shown in the table below The numbers in the Resale Value column indicate the amount that you can sell a car that in n years old so a three year old car can be sold for 12 000 The numbers in the Operating Cost column indicate the amount you must pay to operate a car in its nth year of service That is you pay 2 400 in the third year of service and a total of 4 800 to maintain a three year old car Assuming that you have a new car at present determine a replacement policy that minimizes your net costs of owning and operating a car for the next six years Solve this problem as a shortest route problem Hint Imagine a network in which there are seven nodes i 0 1 6 Node i represents the end of year i The cost on the edge connecting node i with node j is the cost associated with buying a new car at time i maintaining it until the end of year j a total of j i years and then reselling it So the cost associated with i 0 and j 3 is 30 000 900 1 500 2 400 12 000 22 800 You must buy the car for 30 000 you then pay annual maintenance of 900 then 1 500 then 2 400 before selling the car for 12 000 The shortest route from 0 to 6 in this network is the minimum cost Explain this and find the optimal replacement plan How would your answer change if the maintenance costs of a six year old car doubled so that it was equal to 13 200 instead of 6 600 Age of Car Resale Value 1 21000 2 18000 3 12000 4 9000 5 6000 6 3000 Operating Cost 900 1500 2400 3600 4800 6600 6 The table below gives the distances between pairs of missile silos in Utah The government is laying cables between the six silos so that any one silo can communicate with any other What connections should be made to minimize the total cable length subject to all towers being connected From Tower 1 1 2 3 4 5 6 5 14 45 32 25 2 5 2 5 22 25 2 To Tower 4 5 45 32 5 22 6 26 6 13 26 13 21 22 18 3 14 2 6 25 25 21 22 18