3 Use the Big M method and the two-phase method to nd the optimal solution to the following LP: max z 5x1 x2 s.t. 2x1 x2 6 s.t. x1 x2 4 s.t. x1 2x2 5 x1, x2 0 4 Use the simplex algorithm to nd the optimal solution to the following LP: max z 5x1 x2 s.t. x1 3x2 1 s.t. x1 4x2 3 s.t. x1, x2 0 5 Use the simplex algorithm to nd the optimal solution to the following LP: min z x1 2x2 s.t. 2x1 x2 5 s.t. x1 x2 3 x1, x2 0 6 Use the Big M method and the two-phase method to nd the optimal solution to the following LP: max z x1 x2 s.t. 2x1 x2 3.5 s.t. 3x1 x2 3.5 s.t. x1 x2 1 x1, x2 0 7 Use the simplex algorithm to nd two optimal solutions to the following LP. How many optimal solutions does this LP have? Find a third optimal solution. max z 4x1 x2 s.t. 2x1 3x2 4 s.t. x1 x2 1 s.t. 4x1 x2 2 x1, x2 0 8 Use the simplex method to nd the optimal solution to the following LP: max z 5x1 x2 s.t. 2x1 x2 6 s.t. x1 x2 0 x1, x2 0 9 Use the Big M method and the two-phase method to nd the optimal solution to the following LP: min z 3x1 x2 s.t. x1 2x2 2 s.t. x1 x2 3 x1, x2 0 10 Suppose that in the Dakota Furniture problem, 10 types of furniture could be manufactured. To obtain an optimal solution, how many types of furniture (at the most) would have to be manufactured? 11 Consider the following LP: max z 10x1 x2 s.t. x1 x2 1 s.t. 20x1 x2 100 x1, x2 0 a Find all the basic feasible solutions for this LP. b Show that when the simplex is used to solve this LP, every basic feasible solution must be examined before the optimal solution is found. By generalizing this example, Klee and Minty (1972) constructed (for n 2, 3, . . .) an LP with n decision variables and n constraints for which the simplex algorithm examines 2n 1 basic feasible solutions before the optimal solution is found. Thus, there exists an LP with 10 variables and 10 constraints for which the simplex requires 210 1 1,023 pivots to nd the optimal solution. Fortunately, such \"pathological\" LPs rarely occur in practical applications. 12 Productco produces three products. Each product requires labor, lumber, and paint. The resource requirements, unit price, and variable cost (exclusive of raw materials) for each product are given in Table 70. Currently, 900 labor hours, 1,550 gallons of paint, and 1,600 board feet of lumber are available. Additional labor can be purchased at $6 per hour, additional paint at $2 per gallon, and additional lumber at $3 per board foot. For the following two sets of priorities, use preemptive goal programming to determine an optimal production schedule. For set 1: Priority Priority Priority Priority 1 2 3 4 Obtain prot of at least $10,500. Purchase no additional labor. Purchase no additional paint. Purchase no additional lumber. For set 2: Priority Priority Priority Priority 13 1 2 3 4 Purchase no additional labor. Obtain prot of at least $10,500. Purchase no additional paint. Purchase no additional lumber. Jobs at Indiana University are rated on three factors: Factor 1 Factor 2 Factor 3 Complexity of duties Education required Mental and or visual demands For each job at IU, the requirement for each factor has been rated on a scale of 1-4, with a 4 in factor 1 representing high complexity of duty, a 4 in factor 2 representing high educational requirement, and a 4 in factor 3 representing high mental and/or visual demands. TA B L E 70 Product Labor 1 2 3 1.5 3 2 Lumber Paint 2 3 4 3 2 2 4 . 17 Review Problems Price ($) Variable Cost ($) 26 28 31 10 6 7 213 IU wants to determine a formula for grading each job. To do this, it will assign a point value to the score for each factor that a job requires. For example, suppose level 2 of factor 1 yields a point total of 10, level 3 of factor 2 yields a point total of 20, and level 3 of factor 3 yields a point value of 30. Then a job with these requirements would have a point total of 10 20 30. A job's hourly salary equals half its point total. IU has two goals (listed in order of priority) in setting up the points given to each level of each job factor. Goal 1 When increasing the level of a factor by one, the points should increase by at least 10. For example, level 2 of factor 1 should earn at least 10 more points than level 1 of factor 1. Goal 1 is to minimize the sum of deviations from this requirement. Goal 2 For the benchmark jobs in Table 71, the actual point total for each job should come as close as possible to the point total listed in the table. Goal 2 is to minimize the sum of the absolute deviations of the point totals from the desired scores. Use preemptive goal programming to come up with appropriate point totals. What salary should a job with skill levels of 3 for each factor be paid? 14 A hospital outpatient clinic performs four types of operations. The prot per operation, as well as the minutes of X-ray time and laboratory time used are given in Table 72. The clinic has 500 private rooms and 500 intensive care rooms. Type 1 and Type 2 operations require a patient to stay in an intensive care room for one day while Type 3 and Type 4 operations require a patient to stay in a private room for one day. Each day the hospital is required to perform at least 100 operations of each type. The hospital has set the following goals: Goal 1 Earn a daily prot of at least $100,000. Goal 2 Use at most 50 hours daily of X-ray time. Goal 3 Use at most 40 hours daily of laboratory time. TA B L E 1 2 3 Desired Score 1 2 3 4 4 3 2 1 4 3 2 1 4 2 2 2 105 93 75 68 TA B L E Goal 1 Cost of $1 for each dollar by which prot goal is unmet Goal 2 Cost of $10 for each hour by which X-ray goal is unmet Goal 3 Cost of $8 for each hour by which laboratory goal is unmet Formulate a goal programming model to minimize the daily cost incurred due to failing to meet the hospital's goals. Group B 15 Consider a maximization problem with the optimal tableau in Table 73. The optimal solution to this LP is z 10, x3 3, x4 5, x1 x2 0. Determine the second-best bfs to this LP. (Hint: Show that the second-best solution must be a bfs that is one pivot away from the optimal solution.) 16 A camper is considering taking two types of items on a camping trip. Item 1 weighs a1 lb, and item 2 weighs a2 lb. Each type 1 item earns the camper a benet of c1 units, and each type 2 item earns the camper c2 units. The knapsack can hold items weighing at most b lb. a Assuming that the camper can carry a fractional number of items along on the trip, formulate an LP to maximize benet. b Show that if c2 c1 a2 a1 then the camper can maximize benet by lling a knapsack with b type 2 items. a2 C Which of the linear programming assumptions are violated by this formulation of the camper's problem? 17 You are given the tableau shown in Table 74 for a maximization problem. Give conditions on the unknowns a1, a2, a3, b, and c that make the following statements true: a The current solution is optimal. b The current solution is optimal, and there are alternative optimal solutions. c The LP is unbounded (in this part, assume that b 0). 71 Job The cost per unit deviation from each goal is as follows: 72 Factor Level 18 Suppose we have obtained the tableau in Table 75 for a maximization problem. State conditions on a1, a2, a3, b, c1, and c2 that are required to make the following statements true: a The current solution is optimal, and there are alternative optimal solutions. b The current basic solution is not a basic feasible solution. TA B L E Type of Operation 73 1 Prot ($) X-ray time (minutes) Laboratory time (minutes) 214 2 3 4 z x1 x2 x3 x4 rhs 200 206 205 150 155 154 100 154 153 80 3 2 1 0 0 2 3 4 1 2 3 0 1 0 0 0 1 10 3 5 CHAPTER 4 The Simplex Algorithm and Goal Programming TA B L E 74 z x1 x2 x3 x4 x5 rhs 1 0 0 0 c 1 a2 a3 2 a1 4 3 0 1 0 0 0 0 1 0 0 0 0 1 meeting (on time) the demands of the next six months. At the beginning of month 1, Shoemakers has 13 workers. 10 4 1 b TA B L E 75 z x1 x2 x3 x4 x5 x6 rhs 1 0 0 0 c1 4 1 a3 c2 a1 5 3 0 1 0 0 0 0 1 0 0 a2 1 4 0 0 0 1 10 b 2 3 c The current basic solution is a degenerate bfs. d The current basic solution is feasible, but the LP is unbounded. e The current basic solution is feasible, but the objective function value can be improved by replacing x6 as a basic variable with x1. 19 Suppose we are solving a maximization problem and the variable xr is about to leave the basis. a What is the coefcient of xr in the current row 0? b Show that after the current pivot is performed, the coefcient of xr in row 0 cannot be less than zero. c Explain why a variable that has left the basis on a given pivot cannot re-enter the basis on the next pivot. 20 A bus company believes that it will need the following number of bus drivers during each of the next ve years: year 160 drivers; year 270 drivers; year 350 drivers; year 465 drivers; year 575 drivers. At the beginning of each year, the bus company must decide how many drivers should be hired or red. It costs $4,000 to hire a driver and $2,000 to re a driver. A driver's salary is $10,000 per year. At the beginning of year 1, the company has 50 drivers. A driver hired at the beginning of a year may be used to meet the current year's requirements and is paid full salary for the current year. Formulate an LP to minimize the bus company's salary, hiring, and ring costs over the next ve years. 21 Shoemakers of America forecasts the following demand for each of the next six months: month 15,000 pairs; month 26,000 pairs; month 35,000 pairs; month 4 9,000 pairs; month 56,000 pairs; month 65,000 pairs. It takes a shoemaker 15 minutes to produce a pair of shoes. Each shoemaker works 150 hours per month plus up to 40 hours per month of overtime. A shoemaker is paid a regular salary of $2,000 per month plus $50 per hour for overtime. At the beginning of each month, Shoemakers can either hire or re workers. It costs the company $1,500 to hire a worker and $1,900 to re a worker. The monthly holding cost per pair of shoes is 3% of the cost of producing a pair of shoes with regular-time labor. (The raw materials in a pair of shoes cost $10.) Formulate an LP that minimizes the cost of 22 Monroe County is trying to determine where to place the county re station. The locations of the county's four major towns are given in Figure 31. Town 1 is at (10, 20); town 2 is at (60, 20); town 3 is at (40, 30); town 4 is at (80, 60). Town 1 averages 20 res per year; town 2, 30 res; town 3, 40 res; and town 4, 25 res. The county wants to build the re station in a location that minimizes the average distance that a re engine must travel to respond to a re. Since most roads run in either an east-west or a north-south direction, we assume that the re engine can only do the same. Thus, if the re station were located at (30, 40) and a re occurred at town 4, the re engine would have to travel (80 30) (60 40) 70 miles to the re. Use linear programming to determine where the re station should be located. (Hint: If the re station is to be located at the point (x, y) and there is a town at the point (a, b), dene variables e, w, n, s (east, west, north, south) that satisfy the equations x a w e and y b n s. It should now be easy to obtain the correct LP formulation.) 23 During the 1972 football season, the games shown in Table 76 were played by the Miami Dolphins, the Buffalo Bills, and the New York Jets. Suppose that on the basis of these games, we want to rate these three teams. Let M Miami rating, J Jets rating, and B Bills rating. Given values of M, J, and B, you would predict that when, for example, the Bills play Miami, Miami is expected to win by M B points. Thus, for the rst Miami-Bills game, your prediction would have been in error by |M B 1| points. Show how linear programming can be used to determine ratings for each team that minimize the sum of the prediction errors for all games. 31 FIGURE 4 3 1 2 TA B L E 76 Miami Bills Jets 27 28 24 30 23 16 24 3 17 24 41 41 Based on Wagner (1954). 4 . 17 Review Problems 215 At the conclusion of the season, this method has been used to determine ratings for college football and college basketball. What problems could be foreseen if this method were used to rate teams early in the season? 28 Suppose the bfs for an optimal tableau is degenerate, and a nonbasic variable in row 0 has a zero coefcient. Show by example that either of the following cases may hold: 24 During the next four quarters, Dorian Auto must meet (on time) the following demands for cars: quarter 14,000; quarter 22,000; quarter 35,000; quarter 41,000. At the beginning of quarter 1, there are 300 autos in stock, and the company has the capacity to produce at most 3,000 cars per quarter. At the beginning of each quarter, the company can change production capacity by one car. It costs $100 to increase quarterly production capacity. It costs $50 per quarter to maintain one car of production capacity (even if it is unused during the current quarter). The variable cost of producing a car is $2,000. A holding cost of $150 per car is assessed against each quarter's ending inventory. It is required that at the end of quarter 4, plant capacity must be at least 4,000 cars. Formulate an LP to minimize the total cost incurred during the next four quarters. Case 1 Case 2 25 Ghostbusters, Inc., exorcises (gets rid of) ghosts. During each of the next three months, the company will receive the following number of calls from people who want their ghosts exorcised: January, 100 calls; February, 300 calls; March, 200 calls. Ghostbusters is paid $800 for each ghost exorcised during the month in which the customer calls. Calls need not be responded to during the month they are made, but if a call is responded to one month after it is made, then Ghostbusters loses $100 in future goodwill, and if a call is responded to two months after it is made, Ghostbusters loses $200 in goodwill. Each employee of Ghostbusters can exorcise 10 ghosts during a month. Each employee is paid a salary of $4,000 per month. At the beginning of January, the company has 8 workers. Workers can be hired and trained (in 0 time) at a cost of $5,000 per worker. Workers can be red at a cost of $4,000 per worker. Formulate an LP to maximize Ghostbusters' prot (revenue less costs) over the next three months. Assume that all calls must be handled by the end of March. 26 Carco uses robots to manufacture cars. The following demands for cars must be met (not necessarily on time, but all demands must be met by end of quarter 4): quarter 1 600; quarter 2800; quarter 3500; quarter 4400. At the beginning of the quarter, Carco has two robots. Robots can be purchased at the beginning of each quarter, but a maximum of two per quarter can be purchased. Each robot can build as many as 200 cars per quarter. It costs $5,000 to purchase a robot. Each quarter, a robot incurs $500 in maintenance costs (even if it is not used to build any cars). Robots can also be sold at the beginning of each quarter for $3,000. At the end of each quarter, a holding cost of $200 per car is incurred. If any demand is backlogged, then a cost of $300 per car is incurred for each quarter the demand is backlogged. At the end of quarter 4, Carco must have at least two robots. Formulate an LP to minimize the total cost incurred in meeting the next four quarters' demands for cars. 27 Suppose we have found an optimal tableau for an LP, and the bfs for that tableau is nondegenerate. Also suppose that there is a nonbasic variable in row 0 with a zero coefcient. Prove that the LP has more than one optimal solution. 216 CHAPTER The LP has more than one optimal solution. The LP has a unique optimal solution. 29 You are the mayor of Gotham City, and you must determine a tax policy for the city. Five types of taxes are used to raise money: a Property taxes. Let p property tax percentage rate. b A sales tax on all items except food, drugs, and durable goods. Let s sales tax percentage rate. c A sales tax on durable goods. Let d durable goods sales tax percentage rate. d A gasoline sales tax. Let g gasoline tax sales percentage rate. e A sales tax on food and drugs. Let f sales tax on food and drugs. The city consists of three groups of people: low-income (LI), middle-income (MI), and high-income (HI). The amount of revenue (in millions of dollars) raised from each group by setting a particular tax at a 1% level is given in Table 77. For example, a 3% tax on durable good sales will raise $360 million from low-income people. Your tax policy must satisfy the following: Restriction 1 The tax burden on MI people cannot exceed $2.8 billion. Restriction 2 The tax burden on HI people cannot exceed $2.4 billion. Restriction 3 The total revenue raised must exceed the current level of $6.5 billion. Restriction 4 s must be between 1% and 3%. Given these restrictions, the mayor has set the following three goals: Goal P Keep the property tax rate less than 3%. Goal LI Limit the tax burden on LI people to $2 billion. Goal Suburbs If their tax burden becomes too high, 20% of the LI people, 20% of the MI people, and 40% of the HI people may consider moving to the suburbs. Suppose that this will happen if their total tax burden exceeds $1.5 billion. To discourage this exodus, the suburb goal is to keep the total tax burden on these people below $1.5 billion. Use goal programming to determine an optimal tax policy if the mayor's goals follow the following set of priorities: LI P Suburbs TA B L E 77 p LI MI HI s d g f 1,900 1,200 1,000 300 400 250 120 100 60 30 20 10 90 60 40 Based on Chrisman, Fry, Reeves, Lewis, and Weinstein (1989). 4 The Simplex Algorithm and Goal Programming