Transcription
56:171Fall 2002Operations ResearchHomework SolutionsInstructor: D. L. BrickerUniversity of IowaDept. of Mechanical & Industrial Engineering
56:171 Operations ResearchHomework #1 Solutions –Fall 20021. The Keyesport Quarry has two different pits from which it obtains rock. The rock is run through acrusher to produce two products: concrete grade stone and road surface chat. Each ton of rock fromthe South pit converts into 0.75 tons of stone and 0.25 tons of chat when crushed. Rock from theNorth pit is of different quality. When it is crushed it produces a “50-50” split of stone and chat. TheQuarry has contracts for 60 tons of stone and 40 tons of chat this planning period. The cost per ton ofextracting and crushing rock from the South pit is 1.6 times as costly as from the North pit.a. What are the decision variables in the problem? Be sure to give their definitions, not just theirnames!Answer: S ROCK # of tons of rocks from the South pit.N ROCK # of tons of rocks from the North pit.b. There are two constraints for this problem. State them in words.Answer:1. # of tons of concrete grade stone which is the sum of concrete grade stone from South pit andconcrete grade stone from North pit is bigger than 60.2. # of tons of road surface chat which is the sum of road surface chat from South pit and roadsurface chat from North pit is bigger than 40. State them in equation or inequality form.Answer:0.75 S ROCK 0.5 N ROCK 600.25 S ROCK 0.5 N ROCK 40c. State the objective function.Answer:Total cost of the processing rocks which is the sum of the cost of processing rocks fromSouth pit and North pit in the unit of the cost of processing 1 ton’s processing North pit(to be minimized):Min 1.6 S ROCK N ROCKd. Graph the feasible region (in 2 dimensions) for this problem.56:171 O.R. -- HW #1 SolutionFall 2001page 1 of 5
Answer:e. Draw an appropriate objective function line on the graph and indicate graphically and numericallythe optimal solution.Answer:f. Use LINDO (or other appropriate LP solver) to compute the optimal solution.56:171 O.R. -- HW #1 SolutionFall 2001page 2 of 5
Answer:LP OPTIMUM FOUND AT STEP1OBJECTIVE FUNCTION VALUE1)120.0000VARIABLES ROCKN ROCKROW2)3)VALUE0.000000120.000000SLACK OR SURPLUS0.00000020.000000REDUCED COST0.1000000.000000DUAL PRICES-2.0000000.000000 2. a. Draw the feasible region of the following LP:Maximizesubject toAnswer:5X1 2X24X1 3X2 24X1 X2 83X1 X2 9X1 0, X2 0Note that the point (0,8) is the intersection of three boundary lines, indicating a degeneracy!56:171 O.R. -- HW #1 SolutionFall 2001page 3 of 5
b. Indicate on the graph the optimal solution.Answer: 3. a. Compute the inverse of the matrix (showing your computational steps): 1 0 1 A 1 2 0 2 1 1 Answer: 1 0 1 1 0 0 R2 R2 R1 1 0 1 1 0 0 R2 R2 / 2 1 2 0 0 1 0 R R 2 R 0 2 1 1 1 0 R R R / 231 32 3 3 2 1 0 0 0 1 0 1 1 2 0 1 R R1 2 R310 0 1 1 0 1 1 0 0 2 1 2 0 1 1/ 2 1/ 2 1/ 2 0 R2 R2 R3 0 1 0 1 1 1 R 2 R 3 0 0 1/ 2 3/ 2 1/ 2 1 3 0 0 1 3 1 2 56:171 O.R. -- HW #1 SolutionFall 2001page 4 of 5
2 1 2 Hence A 11 1 3 1 2 1b. Find a solution (if one exists) of the equations: X1 2 X 2 X 3 4 2 X 1 X 2 2 X 3 15 3 X 2 X 523 Answer:Using Gauss elimination, we reduce the augmented coefficient matrix to echelon form:4 1 2 1 4 1 2 1 4 1 2 1 2 1 2 15 0 5 4 7 0 1 4 / 5 7 / 5 0 3 2 5 0 3 2 5 0 01 2 X1 4 2 X 2 X 3 8 By back substitution X 2 7 / 5 (4 / 5) X 3 3 X 3 2 Note that this could also have been done by Gauss-Jordan elimination.56:171 O.R. -- HW #1 SolutionFall 2001page 5 of 5
56:171 Operations ResearchHomework #2 Solutions – Fall 20021. (Exercise 3.4-18, page 98, of Hillier&Lieberman text, 7th edition)“Oxbridge University maintains a powerful mainframe computer for research useby its faculty, Ph.D. students, and research associates. During all working hours, anoperator must be able to operate and maintain the computer, as well as to performsome programming services. Beryl Ingram, the director of the computer facility,oversees the operation.It is now the beginning of the fall semester, and Beryl is confronted with theproblem of assigning different working hours to her operators. Because all theoperators are currently enrolled in the university, they are available to work only alimited number of hours each day, as shown in the following table.NameK.C.D.H.H.B.S.C.K.S.N.K.Wage /hr10.0010.109.909.8010.8011.30Maximum # hours availableMon Tues Wed ThurFri606060606048404555053038000062There are six operators (four undergraduate students and two graduate students).They all have different wage rates because of differences in their experience withcomputers and in their programming ability. The above table shows their wage rates,along with the maximum number of hours that each can work each day.Each operator is guaranteed a certain minimum number of hours per week that willmaintain an adequate knowledge of the operation. This level is set arbitrarily at 8hours per week for the undergraduate students (K.C,, D.H, H.B, and S.C.) and 7 hoursper week for the graduate students (K.S. and N.K.).The computer facility is to be open for operation from 8 a.m. to 10 p.m. Mondaythrough Friday with exactly one operator on duty during these hours. On Saturdaysand Sundays, the computer is to be operated by other staff.Because of a tight budget, Beryl has to minimize cost. She wishes to determine thenumber of hours she should assign to each operator on each day.”a. Formulate a linear programming model for this problem. Be sure to define yourvariables!Answer:Define decision variablesXij # hours operater i is assigned to work on day jfor all i 1 6 (where 1 KC, 2 DH, 6 NK); j 1, 5 (where 1 MON,2 TUE, 5 FRI)56:171 O.R. -- HW #2 SolutionFall 2001page 1
Minimize z 10(X11 X13 X15) 10.1(X22 X24) 9.9(X31 X32 X33 X35) 9.8(X41 X42 X43 X45) 10.8(X51 X53 X54) 11.3(X64 X65)subject tomaximum number hours available each day:X11 6X22 6X31 4X41 5X51 3X64 6X13 6X24 6X32 8X42 5X53 3X65 2X15 6X33 4X43 5X54 8X35 4X45 5number of hours guaranteed for each operator:X11 X13 X15 8X41 X42 X43 X45 8X22 X24 8X51 X53 X54 7X31 X32 X33 X35 8X64 X65 7total number hours worked each day is 14:X11 X31 X41 X51 14X22 X23 X42 14X13 X33 X43 X53 14X24 X44 X54 X64 14X15 X35 X45 X65 14nonnegativity:Xij 0 for all i & jb. Use an LP solver (e.g. LINDO or LINGO) to find the optimal solution.The LINGO model is as follows:MODEL:! Oxbridge University Computer Center;SETS:OPERATOR / KC, DH, HB, SC, KS, NK/: MINIMUM, PAYRATE;DAY /MON, TUE, WED, THU, FRI/: REQUIRED;ASSIGN(OPERATOR,DAY): AVAILABLE, X;ENDSETSDATA:MINIMUM 8 8 8 8 7 7;PAYRATE 10.00 10.10 9.90REQUIRED 14 14 14 14 14;AVAILABLE 6 0 6 0 60 6 0 6 04 8 4 0 45 5 5 0 53 0 3 8 00 0 0 6 2;9.8010.8011.30;ENDDATAMIN TOTALPAY;!total weekly payroll cost;TOTALPAY @SUM(ASSIGN(I,J) AVAILABLE(I,J) #NE# 0:PAYRATE(I)*X(I,J) );56:171 O.R. -- HW #2 SolutionFall 2001page 2
!must schedule required hours each day;@FOR(DAY(J):@SUM(OPERATOR(I) AVAILABLE(I,J) #NE# 0:REQUIRED(J) );!X(I,J) ) must schedule each operator at least minimum number of hours;@FOR(OPERATOR(I):@SUM(DAY(J) AVAILABLE(I,J) #NE# 0: X(I,J) ) MINIMUM(I));!upper (& lower) bounds on variables;@FOR(ASSIGN(I,J) AVAILABLE(I,J) #NE# 0:@BND(0, X(I,J), AVAILABLE(I,J) ); );ENDNote the use of the logical expression “AVAILABLE(I,J) #NE# 0” in order to avoid definingand referencing assignments in which the operator is not available.Note also the use of @BND to impose the upper bounds instead of@FOR(ASSIGN(I,J) AVAILABLE(I,J) #NE# 0:X(I,J) AVAILABLE(I,J));The syntax is @BND( lower bound, variable name, upper bound);Global optimal solution found at step:Objective value:X(X(X(X(X(X(X(X(X(X(X(X(X(X(X(X(X(X(56:171 O.R. -- HW #2 SolutionVariableTOTALPAYKC, MON)KC, WED)KC, FRI)DH, TUE)DH, THU)HB, MON)HB, TUE)HB, WED)HB, FRI)SC, MON)SC, TUE)SC, WED)SC, FRI)KS, MON)KS, WED)KS, THU)NK, THU)NK, 000006.0000001.000000Fall 2001Reduced 0000000.00000000.00000000.0000000page 3
2. (Exercise 4.4-9, page 176, of Hillier&Lieberman text, 7th edition)Work through the simplex method step by step (in tabular form) to solve the followingproblem:Maximize Z 2X1 – X2 X3subject to3X1 X2 X3 6X1 – X2 2X3 1X1 X2 – X3 2andX1 0, X2 0, X3 0Solution: Include a slack variable in each of the three inequality constraints, S1, S2, & S3. Set upthe initial tableau, and use (-Z) and the three slack variables for the initial basis. ZX1X2X3S1S2S3RHS10002311 11 11112 10100001000010612We are maximizing, and so increasing either X1 or X3 (both of which have positive “relativeprofits”) would improve, i.e., increase, the objective. We will arbitrarily choose X1. ZX1X2X3S1S2S3RHSratio10002311 11 11112 101000010000106126/3 21/1 12/1 2As X1 increases each of the basic variables S1, S2, & S3 decrease (because of the positivesubstitution rates). The minimum ratio test indicates that the first to reach its lower bound ofzero as X1 increases is S2, and hence X1 replaces S2 in the basis, and the pivot is to be done in therow in which the minimum ratio was computed.The resulting tableau is: ZX1X2X3S1S2S3RHS1000001014 12 3 52 30100 2 31 10001 2311ratio¾ 0.75½ 0.5The tableau is not optimal, since there is a positive relative profit in the X2 column, which istherefore selected as the pivot column. As X2 increases, S1 and S3 decrease (because of thepositive substitution rates 4 & 2), and the minimum ratio test indicates that S3 is the first to reachzero. Hence the pivot is performed with the bottom row as the pivot row. The resulting tableauis:56:171 O.R. -- HW #2 SolutionFall 2001page 4
ZX1X2X3S1S2S3RHS100000100001 1.510.5 1.50100 1.5 10.50 0.5 20.5 0.5 2.511.50.5There is now no positive relative profit in the objective row, and therefore the current basis isoptimal and the optimal solution is X 1 1.5 , X 2 0.5 and X 3 0 with slack 1, 0, & 0,respectively, in the three constraints. The optimal objective value Z 2.5 .56:171 O.R. -- HW #2 SolutionFall 2001page 5
Solutions56:171 Operations ResearchHomework #3 Solutions – Fall 20021. Revised Simplex Method Consider the LP problemMaximizesubject toz 3 x1 x2 2 x3x1 x2 x3 152 x1 x2 x3 2 x1 x2 x3 4x j 0, j 1, 2,3a. Let x4 , x5 , &, x6 denote the slack variables for the three constraints, and write the LP withequality constraints.Answer:Maximize z 3 x1 x2 2 x3subject tox1 x2 x3 x4 152 x1 x2 x3 x5 2 x1 x2 x3 x6 4x j 0, j 1, 2,3, 4,5, 6After several iterations of the revised simplex method, 10 the basis B {4,3,2} and the basis inverse matrix is ( AB ) 1 0 12 0 1 2 1 1 .2 1 2 b. Proceed with one iteration of the revised simplex method, byi. Computing the simplex multiplier vector πAnswer: 10 1 π CB ( AB ) 1 [0 2 1] 0 1 2 1 2 0, 3 2 , 1 2 0 11 22 [ 0, 1.5, 0.5]ii. “pricing”, i.e., computing the “relative profits”, of the non-basic columns.Answer:56:171 O.R. -- HW #3 SolutionsFall 2002page 1 of 8
Solutions 1 0 0 C [3 0 0] , A 2 1 0 1 0 1 3 1 C N C N π AN 122 2The relative profits for non-basic variables are C1 0.5 , C5 1.5 , C6 0.5 .iii. Selecting the column to enter the basis.Answer: Only the relative profit of X 1 is positive and the problem is Max problem, andso X 1 should enter the basic.iv. Computing the substitution rates of the entering column.Answer: The substitution rates of the entering variable X 1 isNN 10 1 1 2 α ( AB ) 1 A1 0 1 2 1 2 2 1 2 0 11 1 3 22 2 v. Select the variable to leave the basis.Answer: 11 The current right-hand-side is β X B ( A ) b 3 and the ratios (right-hand-side over 1 B 1 5.5 positive substitution rates) are 6 . (Note that the ratio is not computed for the last row.) " So by the minimum ratio test, X 1 enters the basis, replacing the basic variable in the first row(the row in which the minimum ratio is found), namely X 4 .vi. Update the basis inverse matrix.Answer: The new basis is B {1, 3, 2}. The basis inverse can be updated by writing α, thecolumn of substitution rates, alongside inverse matrix and pivoting in the first row, as shown:1 10 1 0 1 2 22 1 0 13 0 .1 1 11222424 0 1 13311 0 22 2 4 2 4 c. Write the dual of the above LP (i.e. with equality constraints & slack variables) in (a).Answer: Minimizez 15 y1 2 y2 4 y3subject toy1 2 y2 y3 356:171 O.R. -- HW #3 SolutionsFall 2002page 2 of 8
Solutionsy1 y2 y3 1y1 y2 y3 2y j 0, j 1, 2,3d. Substitute the vector π which you computed above in step (i) above to test whether it isfeasible in the dual LP. Which constraint(s) if any are violated? How does this relate to theresults in step (ii) above?Answer: If we substitute π [ 0, 1.5, 0.5] for the dual variables y, the first constrainty1 2 y2 y3 3 is violated.Note: The simplex multipler vector π satisfies all the constraints in the dual problem if &only if the relative profits in (ii) are all non-positive (which implies that the solution isoptimal).2. LP formulation: Staffing a Call Center (Case 3.3, pages 106-108, Intro. to O.R. by Hillier &Lieberman) Answer parts (a), (b), & (c) on page 108, using LINGO with sets to ente
56:171 Operations Research Homework #2 Solutions – Fall 2002 1. (Exercise 3.4-18, page 98, of Hillier&Lieberman text, 7th edition) “Oxbridge University maintains a powerful mainframe computer for research use by its faculty, Ph.D. students, and research associates. During all working hours, an operator must be able to operate and maintain the computer, as well as to perform some .
