Econ 172A, Fall 2008: Problem Set 3Instructions: Due: December 2, 2008. (I may not cover some of this material until the last weekof class. If so, I will “reduce” the assignment on November 25, 2008.)1. Consider the linear integer programming problem:max 22x1+ 8x2subject to 5x1+ 2x2≤ 162x1− x2≤ 4−x1+ 2x2≤ 4In addition, x1and x2are constrained to be non-negative integers.Solve the linear programming problem (ignoring integer constraints) graphically. Round thissolution to the nearest integer solution and check whether it is feasible. Next enumerate allof the rounded solutions by rounding the solution to the linear programming problem in allpossible ways. (This means that there might be four possibilities. If, for example, you findthat the solution to the LP is (1.2, 2.9), then the nearest integer solution is (1, 3), while thefour rounded possibilities are (1 , 2), (1, 3), (2, 2), (2, 3).) For each rounded solution, check forfeasibility and, if feasible, calculate the value. Do any of these possibilities actually solve thegiven integer programming problem? If so, explain why. If not, then use branch-and-boundtechniques 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 onMachine 1 and two hours on Machine 2. Each unit of the second product requires 2 hourson 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 thefirst product and 10 for the second product. The amount of each product produced per daymuch be an integer multiple of .25. The objective is to determine the daily mix of productionquantities that will maximize profit. Formulate an integer programming problem that describesthis problem. Solve the problem using the branch-and-bound technique. (You may solve theassociated 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. Twocars can carry three people each. School rules require that no more than two people from eachgrade travel in the same car. Use a network-flow model to determine the maximum numberof p e ople than can go on the field trip. (You may assume that there are at least 16 studentsin 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. Fromeach of these nodes there are four edges, one of these edges represents the students from aparticular grade who travel in a particular car. These edges go to four nodes, which can bethought of as “students going in car i.” These edges have capacity two. Finally, from each ofthe 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 performeach job is given in the table below. Determine the assignment of employees to jobs thatminimizes the total time required to perform the four jobs. (Dashed lines appear when it isimpossible to schedule a person to a job. That is, Person 2 is unable to do Job 2.)1Job 1 Job 2 Job 3 Job 4P erson 1 22 18 30 18P erson 2 18 −− 27 22P erson 3 26 20 28 28P erson 4 16 22 −− 14P erson 5 21 −− 25 285. Suppose it costs $30,000 to purchase a new car. The annual operating cost and resale value ofa used car are shown in the table below. The numbers in the “Resale Value” column indicatethe amount that you can sell a car that in n years old (so a three-year old car can be soldfor $12,000). The numbers in the “Operating Cost” column indicate the amount you mustpay to operate a car in its nth year of service. That is, you pay $2,400 in the third year ofservice and a total of $4,800 to maintain a three-year old car.) As suming that you have a newcar at present, determine a replacement policy that minimizes your net costs of owning andoperating 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 representsthe end of year i.) The cost on the edge connecting node i with node j is the cost associatedwith 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 networkis 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 thatit was equal to $13,200 instead of $6,600).Age of Car Resale Value Operating Cost1 $21000 $9002 $18000 $15003 $12000 $24004 $9000 $36005 $6000 $48006 $3000 $66006. The table below gives the distances between pairs of missile silos in Utah. The governmentis 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 towersbeing connected)?From Tower To Tower1 2 3 4 5 61 5 14 45 32 252 5 2 5 22 253 14 2 6 26 214 45 5 6 13 225 32 22 26 13 186 25 25 21 22