CS 170 AlgorithmsSpring 2009 David Wagner HW 11Due Apr 24, 2:45pmInstructions: You may work in groups of up to 4 people (but make sure to list your study partnerson your homework). You do not need to provide pseudocode on this homework if you explain youralgorithm clearly, in enough detail to enable someone else to implement your algorithm, givenyour written solution. Unless stated otherwise, you do not need to provide a proof of correctnessfor your algorithms on this homework. You may assume that linear programming problems can besolved in polynomial time, i.e., in time polynomial in the number of variables and the number ofconstraints.1. (25 pts.) Learn linear programmingYou are the manager of a large post office, and you need to ensure that on each day you haveenough employees to handle the demand. You’ve noticed that there is a very strong weekly patternto the demand, so that the number of employees needed on any particular day depends only uponwhich day of the week it is (e.g., Mon, Tue, etc.). In particular, the minimum number of employeeswho will be needed on each day of the week is as follows:Mon Tue Wed Thu Fri Sat Sun21 17 16 19 22 15 8You need to hire enough employees to ensure that you will meet these minimums on each day ofthe week. Due to federal regulations, each employee must work 5 days in a row, then take twodays off; each employee’s 5-day work segment can start on any day of the week you choose, butthey must strictly alternate 5 days on duty, followed by 2 days off duty. For instance, if you hirean employee whose work week starts on Wednesday, they will be working on Wed, Thu, Fri, Sat,Sun, and will be off-duty on Mon and Tue. Due to the recession, there’s an effectively unlimitedsupply of potential workers willing to start on any particular day of the week. Due to federal payscales, every employee is paid the same amount, so your total costs are proportional to the numberof employees you hire.Your goal is to hire the minimum number of employees sufficient to ensure that you meet theminimums shown above on each of the 7 days of the week. How many employees do you need?How to solve it. Solve this problem with linear programming. You should write down a linearprogramming problem instance. Then, solve it with a linear programming solver. I’ve included atutorial on how to use one linear programming solver, below. This problem will give you practicewith translating a problem statement into a linear programming problem, and it will give youpractice with using a linear programming solver.CS 170, Spring 2009, HW 11 1How to use lp solve. The instructional staff have installed a linear solver named lp solveon the instructional Unix machines. It is easy to use. Here is a brief tutorial.Suppose we had the following simple linear program:maximize x2+ 2x3subject to:0 ≤ x1≤ 75 ≤ x2≤ 100 ≤ x3≤ 6x1+ x2≤ x3We can translate this into the lp solve input format by storing the following into a file calledinput.lp:maximize: x2 + 2*x3;0 <= x1 <= 7;5 <= x2 <= 10;0 <= x3 <= 6;x1 + x2 <= x3;(Any other filename would be fine, too, as long as it ends with the .lp extension.) Then weexecute the commandlp_solve input.lpand the solver gives us the following output:Value of objective function: 18.00000000Actual values of the variables:x2 6x3 6x1 0which tells us that the maximum attainable value of the objective function is 18, and one way toachieve this is by setting x1= 0, x2= 6, and x3= 6. Pretty easy, right?A few extensions are also supported. If you want to find the minimum possible value of the objec-tive function, rather than the maximum, use minimize: on the first line rather than maximize:.If you want to force a variable x2 to be an integer, add the lineint x2;CS 170, Spring 2009, HW 11 2to the input file.The lp solve solver is installed on the Unix instructional machines, so you may want to log intoyour Unix instructional account and use it there. (It is an open source package, so in principle youcould download it and run it on your own machine, but it will probably be easier to just use theinstallation that the instructional staff have already kindly prepared for you.)What you should turn in. Please turn in: (1) a description of the main idea of your solution,including a specification of the variables and what each variable intuitively corresponds to; (2) aprint-out of the lp solve input file that you used; (3) the final answer (the minimum number ofemployees needed to meet these constraints—we’re looking for a number).2. (30 pts.) HenronYou’ve been hired by Henron, a new startup with this great idea to make a killing by creatinga market for chicken futures. Henron has relationships with a set of n suppliers and a set of mpurchasers. The i-th supplier can supply up to s[i] chickens this year, and the j-th purchaser wouldlike to buy up to b[ j] chickens this year. Henron is the middleman and makes $1 off each chickenthat is sold. Thus, the more chickens that are sold, the more money you make!However, there’s a complication. Due to federal restrictions on interstate trafficking in avian lifeforms, supplier i can only sell chickens to a purchaser j if they are situated at most 100 milesapart. Assume that you’re given a list L of all the pairs (i, j) such that supplier i is within 100 milesof purchaser j. You will be given n, m,s[1..n],b[1..m],L as input. Your job will be to computethe maximum number of chickens that can be sold this year. The running time of your algorithmshould be polynomial in n and m.(a) Formulate this as a network flow problem. In other words, show how to solve this problem,using a network flow algorithm as a subroutine. Show or describe the graph you have inmind, and explain why the output from the network flow algorithm gives a valid solution tothis problem.(b) Formulate this as a linear programming problem. In other words, show how to solve thisproblem, using a linear programming solver as a subroutine. Explain why this correctlysolves the problem.(c) Let’s assume you don’t care about the running time of your algorithm. Which formulationwould be better, network flow or linear programming? Explain your answer.HINT: You can’t sell fractional chickens. (Can you imagine the mess?)3. (25 pts.) Optimal gerrymanderingIt will soon be election time in Upper Moldavia, and things don’t look good for the Republicratparty: the majority of Upper Moldavians plan to vote Democan next year. However, the Republi-crat party has a secret