56:171 Operations Research mmmmmmm 56:171mmmmmmm

Operations Research -- Sample Homework Assignments
Fall 1997 Dennis Bricker Dept. of Industrial Engineering University of Iowa mmmmmmmmmmmmmmmmmmmm mmmmmmmmmm Homework #1 mmmmmmmmm Linear Programming Model Formulation: Formulate a Linear Programming model for each problem below, and solve it using LINDO (available on the HP-UX workstations, or you may use the software packaged with the textbook.) Be sure to state precisely the definitions of your decision variables, and explain in a few words the purpose of each type of constraint. Write a few words to state what the optimal solution is (i.e., without making use of variable names). (For instructions on LINDO, see §4.7 and the appendix of chapter 4 of the text.) mmmmmmmmmmmmmmmmmmmm

1. Exercise #4, page 113 (Walnut Orchard Farms)
"Walnut Orchard has two farms that grow wheat and corn. Because of differing soil conditions, there are differences in the yields and costs of growing crops on the two farms. The yields and costs are Farm 1 Farm 2 -------------------------------------------------------------------------------------------Corn yield/acre Cost/acre of corn Wheat yield/acre Cost/acre of wheat 500 bushels $100 400 bushels $90 650 bushels $120 350 bushels $80

Each farm has 100 acres available for cultivation; 11,000 bushels of wheat and 7000 bushels of corn must be grown. Determine a planting plan that will minimize the cost of meeting these demands. mmmmmmmmmmmmmmmmmmmm

2. Investment planning
I now have $100. The following investments are available at the beginning of each of the next five years: Investment A: Every dollar invested yields $0.10 a year from now and $1.30 three years after the original investment, a total of $1.40. Investment B: Every dollar invested yields $1.35 two years later.

Sample HW

Fall '97

page 1

56:171 Operations Research Investment C: Every dollar invested yields $0.45 at the end of each of the following three years, a total return of $1.35. During each year, uninvested cash can be placed in money market funds, which yield 6% interest per year. At most $50 may be placed in an investment in any one year. (It is permitted, for example, to invest $50 in A during two consecutive years, so that we have invested a total of more than $50 in A at some point in time-- this restriction limits only the size of each investment in A.) Formulate an LP to maximize my cash on hand five years from now. mmmmmmmmmm Homework #1 Solutions mmmmmmmmm

1. Exercise #4, page 113 (Walnut Orchard Farms)
Solution: Note: The author of this exercise was evidently ignorant of crop yields, since even prime Iowa farmland seldom yields more than 200 bushels/acre. Perhaps the original units of land were hectares rather than acres, and were changed for an American student audience? Decision variables: C1 = # of acres of Farm 1 planted in corn W1 = # of acres of Farm 1 planted in wheat C2 = # of acres of Farm 2 planted in corn W2 = # of acres of Farm 2 planted in wheat Constraints: • We must impose a constraint which restricts the number of acres of each farm which are planted in crops. Thus, we impose: C1 + W1 ≤ 100 C2 + W2 ≤ 100 Note that we are not requiring that all of the land be planted in crops! • We must also impose a constraint which restricts us to produce a minimum quantity of each crop. Thus, we impose: 500C1 + 650C2 ≥ 11000 400W1 + 350W2 ≥ 7000 For example, the left side of the first of the two above constraints states that the total production of corn, namely, (500 bushels/acre)(# acres of farm 1 planted in corn) + (650 bushels/acre)(# acres of farm 2 planted in corn) must be at least 11000 bushels. Note that we assume that all crops which are produced can be sold, i.e., we must produce at least the required amounts, but may, if doing so resulted in lower costs (unlikely here), produce an excess. • Lastly, we must impose a nonnegativity constraint on each of the four variables. Note that these nonnegativity constraints are not entered explicitly into LINDO, which assumes that all the user-defined variables are nonnegativity!

Sample HW

Fall '97

page 2

56:171 Operations Research

Objective: We wish to minimize the costs of producing the required quantities of each crop, i.e., MAX 100 C1 + 120 C2 + 90 W1 + 80 W2 The complete LP model is therefore MAX 100 C1 + 120 C2 + 90 W1 + 80 W2 subject to C1 + W1 100 C2 + W2 100 500C1 + 650C2 11000 400W1 + 350W2 7000 C10, C20, W10, W20 LINDO output:
MIN 100 C1 + 120 C2 + SUBJECT TO 2) C1 + W1 = 4

11000 7000

OBJECTIVE FUNCTION VALUE 1) VARIABLE C1 C2 W1 W2 ROW 2) 3) 4) 5) 3605.769 VALUE .000000 16.923080 17.500000 .000000 SLACK OR SURPLUS 82.500000 83.076920 -.000000 -.000000 REDUCED COST 7.692307 .000000 .000000 1.250000 DUAL PRICES .000000 .000000 -.184615 -.225000

That is, the optimal plan is to plant 17.5 acres of wheat on farm #1 and 16.923 acres of corn on farm #2. (Most of each farm is left unplanted.) mmmmmmmmmmmmmmmmmmmm

2. Investment planning
Solution: The variables may be defined as follows: At = $ invested in A at the beginning of year t, t=1,2,3 Bt = $ invested in B at the beginning of year t, t=1,2,3,4

Sample HW

Fall '97

page 3

56:171 Operations Research Ct = $ invested in C at the beginning of year t, t=1,2,3 Rt = $ invested in the money market fund at the beginning of year t, t=1,2,3,4,5 Note that I'm not considering the possibility of investing in A4, A5, B5, C4, and C5 because in these cases, not all of the returns on these investments will be received in time to be included in the objective function, which is the total accumulation at the beginning of year 6 (i.e., end of year 5). The constraints will include a restriction for each year, stating that the return obtained at the end of the previous year must equal the total amount invested at the beginning of the current year. To assist in writing the constraints, consider the following table:
Begin yr. A1 A2 1 -1 2 0.1 -1 3 0.1 4 1.3 5 1.3 6 A3 -1 0.1 1.3 B1 -1 Investment B3 B4 C1 C2 -1 -1 0.45 -1 1.35 -1 0.45 0.45 1.35 -1 0.45 0.45 1.35 0.45 1.35 B2 C3 -1 0.45 0.45 0.45 R1 R2 R3 R4 R5 -1 1.06 -1 1.06 -1 1.06 -1 1.06 -1 1.06

That is, each column of the Investment section of the table gives the cash flow for that investment. For example, A2 has a cash flow of -1 at the beginning of year 2 (representing the cash going into that investment, a 0.1 at the beginning of year 3 (i.e., the end of year 2), and 1.3 at the beginning of year 5 (end of year 4). The cash flow balance equation for the beginning of each year may easily be written by using the coefficients in the corresponding row of the table. The LP model, as displayed by LINDO, is as follows.
MAX 1.3 SUBJECT TO 2) 3) 4) C3 - R3 = 5) C3 + 1.06 6) END A3 + 1.35 B4 + 1.06 R5 + 0.45 C3 A1 + B1 + C1 + R1 = 100 0.1 A1 + 0.45 C1 + 1.06 R1 - A2 - B2 - C2 - R2 = 0 A3 + 1.35 B1 + 0.45 C1 + 0.1 A2 + 0.45 C2 + 1.06 R2 - B3 0 0.1 A3 - B4 + 1.3 A1 + 0.45 C1 + 1.35 B2 + 0.45 C2 + 0.45 R3 - R4 = 0 R5 + 1.3 A2 + 0.45 C2 + 1.35 B3 + 0.45 C3 + 1.06 R4 = 0

The $50 upper limits on the investments have not been specified yet. For curiosity's sake, let's first find the solution of this less restrictive LP, so that we may compare to the more restrictive LP. LINDO's solution of this less restricted problem is as follows:
LP OPTIMUM FOUND AT STEP 4

OBJECTIVE FUNCTION VALUE 1) VARIABLE A3 B4 R5 A1 211.8150 VALUE .000000 126.000000 20.250000 .000000 REDUCED COST .099500 .000000 .000000 .180900

Sample HW

Fall '97

page 4

56:171 Operations Research
B1 C1 R1 A2 B2 C2 R2 B3 C3 R3 R4 .000000 100.000000 .000000 .000000 45.000000 .000000 .000000 .000000 45.000000 .000000 .000000 .046575 .000000 .186300 .291050 .000000 .047475 .195930 .103500 .000000 .103500 .226400

That is, at the beginning of year 6 (i.e. end of year 5), $211.815 will have been accumulated. Notice that all $100 is initially invested in C1, which will return $45 at the beginning of each of the years 2, 3, and 4. At the beginning of year 2, this $45 is invested in B2, while at the beginning of year 3, the $45 received from C1 is reinvested in C3. At the beginning of year 4, cash returns will be received from C1, B2, and C3. This ($126) is all invested in B4. At the beginning of year 5, only C3 returns any cash, and this cash ($20.25) is put into the money-market fund for that year. At the beginning of year 6, then, cash is received from both B4 and the money market fund (R5), a total of $211.815. Next we add the simple upper bound (SUB) command for each of the variables A1, A2, A3, B1, B2, B3, B4, C1, C2, and C3 (but not R1 through R5!). The revised LP model as displayed by LINDO appears below:
MAX 1.3 A3 + 1.35 B4 + 1.06 R5 + 0.45 C3 SUBJECT TO 2) A1 + B1 + C1 + R1 = 100 3) 0.1 A1 + 0.45 C1 + 1.06 R1 - A2 - B2 - C2 - R2 = 0 4) - A3 + 1.35 B1 + 0.45 C1 + 0.1 A2 + 0.45 C2 + 1.06 R2 - B3 C3 - R3 = 0 5) 0.1 A3 - B4 + 1.3 A1 + 0.45 C1 + 1.35 B2 + 0.45 C2 + 0.45 C3 + 1.06 R3 - R4 = 0 6) - R5 + 1.3 A2 + 0.45 C2 + 1.35 B3 + 0.45 C3 + 1.06 R4 = 0 END SUB A3 50.00000 SUB B4 50.00000 SUB A1 50.00000 SUB B1 50.00000 SUB C1 50.00000 SUB A2 50.00000 SUB B2 50.00000 SUB C2 50.00000 SUB B3 50.00000 SUB C3 50.00000

The solution of this problem with the upper limits on amounts to be invested is as follows:
LP OPTIMUM FOUND AT STEP 5

OBJECTIVE FUNCTION VALUE

Sample HW

Fall '97

page 5

56:171 Operations Research
1) VARIABLE A3 B4 R5 A1 B1 C1 R1 A2 B2 C2 R2 B3 C3 R3 R4 202.0675 VALUE .125000 50.000000 105.570740 .000000 50.000000 50.000000 .000000 .000000 .000000 22.500000 .000000 50.000000 50.000000 .000000 5.137498 REDUCED COST .000000 -.226400 .000000 .246866 -.037322 .000000 .154091 .098946 .101322 .000000 .121080 -.018640 -.020260 .221344 .000000

The solution may be stated as follows: 1. The original $100 is evenly divided between investments B1 and C1 in the first year. 2. The $22.50 (= [0.45][50]) return from C1 at the end of the first year is re-invested in C2. 3. At the end of the second year, the investor receives $67.50 (= [1.35][50]) return from his investment in B1, another $22.50 from C1, plus $10.125 (= [0.45][22.50]) from the investment C2, a total of $100.125. Of this total, $50 of this money is invested in each of B3 and C3, leaving $0.125 which is invested in A3. 4. At the end of the third year, the investment C1 returns $22.50, C2 return another $10.125, C3 returns another $22.50, and A3 returns $0.0125 (= [0.1][0.125]), a total of $55.1375. Of this total, $50 is invested in B4, and the remaining $5.1375 is invested in the money-market fund R4. 5. At the end of the fourth year, B3 returns $67.50, C2 returns $10.125, C3 returns $22.50, and the money-market fund R4 returns $5.44575 (= [1.06][5.1375]), a total of $105.57075. The only possible investment for this money is the moneymarket fund, so all $105.57075 is invested in R5. 6. At the end of the fifth year, the money-market fund R5 yields $111.904995 (= [1.06][105.57075]). Also, A3 returns $0.1625 (= [1.3][0.125]), B4 returns $67.50, and C3 returns $22.50. Thus, a total of $111.904995 + $0.1625 + $67.50 + $22.50 = $202.067495 has been accumulated, more than double the original holdings of $100.

Sample HW

Fall '97

page 6

56:171 Operations Research Notice that placing the SUB restrictions reduced the final accumulated cash from $211.815 to $202.0675, a reduction of $9.7475 (approximately 4.6% reduction). mmmmmmmmmm Homework #2 mmmmmmmmm Linear Programming Model Formulation: Formulate a Linear Programming model for each problem below, and solve it using LINDO (available on the HP-UX workstations, or you may use the software packaged with the textbook.) Be sure to state precisely the definitions of your decision variables, and explain in a few words the purpose of each type of constraint. Write a few words to state what the optimal solution is (i.e., without making use of variable names). (For instructions on LINDO, see §4.7 and the appendix of chapter 4 of the text.) 1. Two alloys, A and B, are made from four metals, labelled I, II, III, and IV, according to the following specifications:
Alloy Specifications Selling price ($/ton) ___________________________________________________________ At most 80% of I A At most 30% of II 200 At least 50% of IV ___________________________________________________________ Between 40 and 60% of II B At least 30% of III 300 At most 70% of IV ___________________________________________________________

The four metals, in turn, are extracted from three ores according to the following data:
Ore 1 2 3 Max Quantity (tons) 1000 2000 3000 I 20 10 5 II 10 20 5 III 30 30 70 IV 30 30 20 Others 10 10 0 Price ($/ton) 30 40 50

a. How much of each type of alloy should be produced? b. How much of each ore should be allocated to the production of each alloy? (Hint: Let xij be tons of ore i allocated to alloy j, and define wj as tons of alloy j to be produced.) mmmmmmmmmmmmmmmmmmmm 2. Consider the LP Minimize z= x1 + 2x2 - 3x3 + x4 subject to x1 + 2x2 - 3x3 + x4 = 4 x1 + 2x2 + x3 + 2x4 = 4 x1, x2, x3, x4 0

Sample HW

Fall '97

page 7

56:171 Operations Research a. A basic solution of the constraint equations of this problem has how many basic variables, in addition to -z? _____ b. What is the maximum number of basic solutions (either feasible or infeasible) which might exist? (That is, how many ways might you select a set of basic variables from the four variables x1 through x4?) _____ c. Find and list all of the basic solutions of the constraint equations. d. Is the number of basic solutions in (c) equal to the maximum possible number which you specified in (b)? ______ e. How many of the basic solutions in (c) are feasible (i.e. nonnegative)? f. By evaluating the objective function at each basic solution, find the optimal solution. mmmmmmmmmmmmmmmmmmmm 3. Consider the LP Maximize z= 2x1 - 4x2 + 5x3 - 6x4 subject to x1 + 4x2 - 2x3 + 8x4 2 -x1 + 2x2 + 3x3 + x4 1 x1, x2, x3, x4 0 a. Introduce slack variables to convert the inequality constraints to equations. b. Form the simplex tableau for this LP. c. What is the beginning basic solution? Is it feasible? What is its objective function value? d. Perform as many iterations of the simplex algorithm as required to find an optimum solution. mmmmmmmmmm Homework #2 Solutions mmmmmmmmm 1. Solution: This problem (which I obtained from a recent edition of the O.R. text by Hamdy Taha) is rather ambiguous and not well stated. The hint above suggests what might be an unlikely interpretation of the problem, which is that this is a traditional "blending" problem in which the ores are blended together to produce the alloy. If this is the case, is each alloy the sum of the ores which are allocated to it? (What about the impurities, i.e., the "other"? Can they be "skimmed" off when the ores are smelted?) Must all of the metals contained in the ores allocated to an alloy also appear in the alloy, or do the metals first get extracted from the ore and then selected for the alloy mix (but only the alloy to which the ore was allocated)? A more likely situation in reality is that the metals are extracted from the ores, and then the metals are blended together to obtain the alloys. (This second interpretation gives the manager more flexibility and the possibility of a higher profit.) I will give a formulation for each interpretation below. I. Ores are allocated directly to the alloys. Sample HW Fall '97 page 8

56:171 Operations Research

Defining the decision variables as in the hint above, the objective function becomes
Maximize 200WA + 300WB - 30(X1A + X1B) - 40(X2A + X2B) - 50(X3A + X3B)

i.e., the difference between the revenue obtained from sales of the alloys and the cost of the ores. The constraints are: Availability of ores: X1A+X1B 1000 X2A+X2B 2000 X3A+X3B 3000 Composition of alloys: 0.2X1A + 0.10X2A + 0.05X3A 0.8WA (At most 80% of alloy A is metal I) 0.10X1A + 0.20X2A + 0.05X3A 0.3WA (At most 30% of alloy A is metal II) 0.30X1A + 0.30X2A + 0.20X3A 0.5WA (At least 50% of alloy A is metal IV) 0.10X1B + 0.20X2B + 0.05X3B 0.4WB 0.10X1B + 0.20X2B + 0.05X3B 0.6WB 0.30X1B + 0.30X2B + 0.70X3B 0.3 WB 0.30X1B + 0.30X2B + 0.20X3B 0.7 WB (At least 40% of alloy B is metal I) (At most 60% of alloy B is metal I) (At least 30% of alloy B is metal III) (At most 70% of alloy B is metal IV)

Ia. Assuming that the impurities ("other") and all metals in the ores remain present in the alloys, we get the constraint: WA = X1A + X2A + X3A WB = X1B + X2B + X3B LINDO solution:
MAX X3A 200 WA + 300 WB - 30 X1A - 30 X1B - 40 X2A - 40 X2B - 50 - 50 X3B SUBJECT TO 2) X1A + X1B 0, C24=0-(30)>0, C31=420-400>0, and C32=415-4500, C13=440-435>0, C21=425-400>0, C24=0-50, and C33=410-440 3 ?Y5 + Y6 > 1 ?Y2 + Y4 + Y5 < 2 ?END : INTE 8

Sample HW

Fall '97

page 58

56:171 Operations Research The LINDO output is:
: look all MAX Y1 SUBJECT TO 2) 14 3) 16 4) 5) 6) 7) END INTE 8

4 Y1 + 5 Y2 + 3 Y3 + 2 Y4 + 4 Y5 + 3 Y6 + 5 Y7 + 4 Y8 >= 4 Y1 + 5 Y2 + 3 Y3 + 2 Y4 + 4 Y5 + 3 Y6 + 5 Y7 + 4 Y8 = + Y5 + Y8 = + Y8 >= 1 NEW INTEGER SOLUTION OF 13

.000000 AT BRANCH 0 PIVOT

1.00000000

OBJECTIVE FUNCTION VALUE 1) VARIABLE Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 ROW 2) 3) 4) 5) 6) 7) 8) 1.000000 VALUE 1.000000 1.000000 .000000 .000000 .000000 1.000000 .000000 1.000000 SLACK OR SURPLUS 2.000000 .000000 .000000 -.000000 -.000000 1.000000 .000000 REDUCED COST -1.000000 .000000 .000000 .000000 .000000 .000000 .000000 .000000 DUAL PRICES .000000 .000000 .000000 .000000 .000000 .000000 .000000 0 0 PIVOTS= 13

NO. ITERATIONS= 13 BRANCHES= 0 DETERM.= 1.000E BOUND ON OPTIMUM: 1.000000 ENUMERATION COMPLETE. BRANCHES=

LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION...

That is, the feasible solution found above is to place songs #1, 2, 6, & 8 on side #1 (and therefore the remaining songs, namely 3, 4, 5, & 7, on side #2. Note that a

Sample HW

Fall '97

page 59

56:171 Operations Research different objective might result in LINDO finding a different solution, but it would be feasible as well!

Sample HW

Fall '97

page 60

56:171 Operations Research mmmmmmmmmm Homework #9 mmmmmmmmm 1. Consider an inventory system in which the number of items on the shelf is checked at the end of each day. The maximum number on the shelf is 8. If 3 or fewer units are on the shelf, the shelf is refilled overnight. The demand distribution is as follows: x 0 1 2 3 4 5 6 P{D=x} .1 .15 .25 .25 .15 .05 .05 The system is modeled as a Markov chain, with the state defined as the number of units on the shelf at the end of each day. The probability transition matrix is:

a. Explain the derivation of the values P19, P35, P51, P83 above. (Note that state 1=inventory level 0, etc.) The steady-state distribution of the above Markov chain is:

b. Write two of the equations which define this steady-state distribution. How many equations must be solved to yield the solution above? c. What is the average number on the shelf at the end of each day? The mean first passage matrix is:

Sample HW

Fall '97

page 61

56:171 Operations Research

d. If the shelf is full Monday morning, what is the expected number of days until the shelf is first emptied ("stockout")? _____________ e. What is the expected time between stockouts? _____________ f. How frequently will the shelf be restocked? (i.e. what is the average number of days between restocking?) _____________ 2. Consider a manufacturing process in which raw parts (blanks) are machined on three machines, and inspected after each machining operation. The relevant data is as follows:

For example, machine #1 requires 0.5 hrs, at $20/hr., and has a 10% scrap rate. Those parts completing this operation are inspected, requiring 0.1 hr. at $15/hr. The inspector scraps 10%, and sends 5% back to machine #1 for rework (after which it is again inspected, etc.) The Markov chain model of a part moving through this system has transition probability matrix:

Sample HW

Fall '97

page 62

56:171 Operations Research

a. Draw the diagram for this Markov chain and describe each state. b. Which states are transient?____________ which are absorbing? ____________ The absorption probabilities are:

The matrix E is as follows:

c. Explain how E was computed. Explain how A was computed, given E. d. What percent of the parts which are started are successfully completed? ____________ e. What is the expected number of blanks which should be required to fill an order for 100 completed parts? ____________

Sample HW

Fall '97

page 63

56:171 Operations Research f. What percent of the parts arriving at machine #2 will be successfully completed? ____________ g. What is the expected total number of inspections which entering parts will undergo? ____________ h. Explain the meaning of the number appearing in row 3, column 2 of the A matrix. i. Explain the meaning of the number appearing in row 3, column 3 of the E matrix. j. To fill the order for 100 completed parts, what is the expected man-hour requirement for each machine? for each inspection station? ____________ k. What are the expected direct costs (row materials + operating costs - scrap value of rejected parts) per completed part? ____________ mmmmmmmmmm Homework #9 Solutions mmmmmmmmm 1. Solution: a. Explain the derivation of the values P19, P35, P51, P83 above. (Note that state 1=inventory level 0, etc.) Solution: • A transition from today's state 1 (0 on shelf at end of day, below the reorder point s) to tomorrow's state 9 (8 on shelf at end of day) occurs only when the shelf is restocked to its maximum level of 8 overnight, but no units are sold the following day. Hence P19 = P{tomorrow's demand D = 0} = 0.1 • A transition from today's state 3 (2 on shelf at end of day, at the reorder point s) to tomorrow's state 5 (4 on shelf at end of day) occurs only when the shelf is restocked to its capacity (8) overnight, and the store sells 4 of these 8 units. Hence, P35 = P{tomorrow's demand D = 4} = 0.15 • A transition from today's state 5 (4 on shelf at end of day, so the shelf will not be restocked) to tomorrow's state 1 (none on shelf at end of day) occurs only when tomorrow the store sells all four of its stock, i.e., the demand was at least 4. This happens with probability P{D4} = P{D=4} + P{D=5} + P{D=6} = 0.15 + 0.05 + 0.05 = 0.25 • Similarly, P83 is the probability that tomorrow's demand is 5, i.e., 0.05.

Sample HW

Fall '97

page 64

56:171 Operations Research b. Write two of the equations which define this steady-state distribution. How many equations must be solved to yield the solution above? Solution: The equations which define the steadystate probability distribution ð are of two types. First is the constraint that says that the probabilities must sum to 1.00, i.e., π1 + π2 + π 3 + π4 + π5 + π6 + π 7 + π8 + π9 = 1 The other constraints are obtained from the system of equations written (in matrix form) as πΛ = 0 where is the matrix of transition rates (not probabilities!) That is, the inner product of vector ð and each of the nine columns of Λ must equal 0, i.e., 0.25 π 5 + 0.1 π 6 + 0.05 π 7 = 0 0.25 π 5 + 0.15 π 6 + 0.05 π 7 + 0.05 π 8= 0 0.05 π 1 + 0.05 π 2 + 0.05 π 3 + 0.05 π 4 + 0.25 π 5 + 0.25 π 6 + 0.15 π 7 + 0.05 π 8 + 0.05 π 9= 0 0.05 π 1 + 0.05 π 2 + 0.05 π 3 + 0.05 π 4 + 0.15 π 5 + 0.25 π 6 + 0.25 π 7 + 0.15 π 8 + 0.05 π 9= 0 0.15 π 1 + 0.15 π 2 + 0.15 π 3 + 0.15 π 4 + 0.1 π 5 + 0.15 π 6 + 0.25 π 7 + 0.25 π 8 + 0.15 π 9= 0 0.25 π 1 + 0.25 π 2 + 0.25 π 3 + 0.25 π 4 + 0.1 π 6 + 0.15 π 7 + 0.25 π 8 + 0.25 π 9= 0 0.25 π 1 + 0.25 π 2 + 0.25 π 3 + 0.25 π 4 + 0.1 π 7 + 0.15 π 8 + 0.25 π 9= 0 0.15 π 1 + 0.15 π 2 + 0.15 π 3 + 0.15 π 4 + 0.1 π 8 + 0.15 π 9= 0 0.1 π 1 + 0.1 π 2 + 0.1 π 3 + 0.1 π 4 + 0.1 π 9= 0 There are nine variables to compute, and so we need nine equations, including the equation which restricts the sum of the variables to the value 1.00. (The nine equations obtained from π Λ = 0 include one redundant equation.) c. What is the average number on the shelf at the end of each day? Solution: 0π 1 + π 2 + 2π 3 + 3π 4 + 4π 5 + 5π 6 + 6π 7 + 7π 8 +8π 9 ≈ 3.968 d. If the shelf is full Monday morning, what is the expected number of days until the shelf is first emptied ("stockout")? Solution: If the shelf is full Monday morning, then the state of the system when last observed was either 1,2,3, or 9 (i.e., either the shelf was full Sunday evening or else it was restocked that night.) The rows of M (the mean first passage time matrix) corresponding to these four states are identical, so it does not matter which row is used. The quantity sought here is the mean first passage time from one of these four states to state 1 (stockout), e.g., m91 = 15.4523 (days) e. What is the expected time between stockouts? 1 Solution: m11 = π 1 = 15.4523 (days) f. How frequently will the shelf be restocked? (i.e. what is the average number of days between restocking?) Solution: The probability that the shelf is restocked on any given day in steady state is the probability that the inventory level at the end of the day is s=3, i.e., sum of the probabilities π1, π2, π3and π4, namely 0.4076. The reciprocal of

Sample HW

Fall '97

page 65

56:171 Operations Research 1 this probability of restocking, namely 0.4076 = 2.45 (days) , gives us the frequency, i.e., the expected time between visits to this set of states {1,2,3,4}. 2. Solution a. Draw the diagram for this Markov chain and describe each state. Solution:

b. Which states are transient?Solution: 1,2,3,4,5, & 6 which are absorbing? Solution: 7 & 8___ c. Explain how E was computed. -1 Solution: E = I - Q , where Q is the submatrix of P whose rows and columns both correspond to transient states, i.e.,

Sample HW

Fall '97

page 66

56:171 Operations Research

Explain how A was computed, given E. Solution: A = E R, where the matrix E was computed as in (c) and R is a submatrix of P, as shown above. d. What percent of the parts which are started are successfully completed? Solution: The value a17 in the A matrix above is the probability that the system, beginning in state 1 (i.e., the part is at Machine #1), is eventually absorbed by state 7 (i.e., the part has reached the packing & shipping area). This should give us the desired probability, 63.35% e. What is the expected number of blanks which should be required to fill an order for 100 completed parts? 1 Solution: We expect to need 0.6335 =1.579 entering blanks per successfully completed parts, or 157.9 blanks total, i.e., one entering blank 157.9 entering blanks = 0.6335 finished part 100 finished parts f. What percent of the parts arriving at machine #2 will be successfully completed? Solution: This value is given in the absorption probability matrix A: a37 = 79.09% g. What is the expected total number of inspections which entering parts will undergo? Solution: The expected number of visits to states 2, 4, and 6 (where the part is in an inspection station), given that a part begins in state 1, is e12 + e14 + e16 = 2.4069, where the elements eij are found in the E matrix above. h. Explain the meaning of the number appearing in row 3, column 2 of the A matrix. Solution: Row 3 of the A matrix corresponds to the transient state 3 (part on machine #2), while column 2 of the matrix corresponds to the second absorbing state (#8, "scrap"). Thus, 0.2091 is the probability that a part which has arrived at the second machine will eventually be scrapped.

Sample HW

Fall '97

page 67

56:171 Operations Research i. Explain the meaning of the number appearing in row 3, column 3 of the E matrix. Solution: Row 3 and column 3 of the E matrix both correspond to the 3rd transient state, i.e., the machine has arrived at Machine #2. Therefore, e33 = 1.029 is the expected number of times (including the initial visit) that the part visits this machine, given that it begins at this machine. j. To fill the order for 100 completed parts, what is the expected man-hour requirement for each machine? Solution: Since e1j, for j=1,3, and 5, are the expected number of visits to the three machines (starting at machine 1), and Tj is the time requirement per visit, T1 e11 + T3 e13 + T5 e15 = 1.31575 (hrs) is the total expected machine time requirements per entering blank. Multiplying this by 157.9 entering blank per 100 successfully completed part yields 207.757 machine hours to complete the order for 100 parts. ... for each inspection station? Solution: Since e1j, for j=2,4, and 6, are the expected number of visits to the three inspection stations (starting at machine 1), and Tj is the time requirement per visit, T2 e12 + T4 e14 + T6 e16 = 0.421207 (hrs) is the total inspection time requirements per entering blank. Multiplying this by 157.9 entering blank per 100 successfully completed part yields 66.5086 inspection hours to complete the order for 100 parts. k. What are the expected direct costs (raw materials + operating costs - scrap value of rejected parts) per completed part? Solution:
Operation Machine 1 Inspection 1 Machine 2 Inspection 2 Machine 3 Inspection 3 Pack & Ship Cost per hour $20 $15 $20 $15 $20 $15 $10 Hours Expected x per visit x # visits x 0.5 x 1.0471 x 0.1 x 0.9424 x 0.75 x 0.8246 x 0.2 x 0.7833 x 0.25 x 0.6951 x 0.25 x 0.6812 x 0.1 x 0.6335 Total expected labor cost/entering part = = = = = = = = = Cost $10.47 1.41 12.36 2.35 3.48 2.55 0.63 $33.27

Raw material cost per entering part = $50 Scrap value retrieved per entering part = $10 x 0.3665 parts scrapped/entering part = $3.66 Total expected cost per entering part: $50 + $33.27 - $3.66 = $79.61

To successfully complete 1 part, the expected number of entering parts required is 1.579, and so Total expected cost per completed part is $79.61 x 1.579 = $125.70 mmmmmmmmmm Homework #10 mmmmmmmmm

Sample HW

Fall '97

page 68

56:171 Operations Research 1. Model the following situation using a Discrete-time Markov chain, and use the MARKOV workspace of APL code to analyze the model and answer the questions below. (The MARKOV workspace is available on ICAEN's Courseware fileserver, in the I.E. program's folder. To use it, however, you must have the APL 68000 Level II interpreter. See the "Software" link on the course web page for more instructions.) The Green Valley Christmas Tree Farm owns a plot of land with 5000 evergreen trees. Each year they allow individuals to select and cut their own Christmas trees. However, they protect small trees (usually less than 4 feet tall) so that they will grow and be available for sale in future years. Currently 1500 trees are classified as protected trees, while the remaining 3500 are available for cutting. However, even though a tree is available for cutting in a given year, it possibly might not be selected for cutting until future years. While most trees not cut in a given year live until the next year(protected or unprotected), approximately 15% are lost to disease. Each year, approximately 60% of the unprotected trees are cut, and 30% of the protected trees surviving from the previous year have matured sufficiently to be made available for cutting. (a.) Define a (discrete-time) Markov chain model of the system consisting of a single tree. • List the states, with a definition of each state. • Sketch the transition diagram and write down the probability matrix. (b.) Which are the absorbing states of this model? (c.) What is the probability that a tree which is now protected is eventually sold? ________ ...that it eventually dies of disease? ________ (d.) How many of the farm's 5000 trees are expected to be sold eventually? ________ How many will be lost to disease? ________ (e.) If a tree is now protected, what is the expected number of years until it is either sold or dies? ________ 2. Continuous-time Markov chain. A certain machine has occasional breakdowns. After the first breakdown, it can be repaired at a cost of $1000. However, such a repair can only be done once, and consequently, the machine has to be replaced by a new one after the second breakdown. The replacement cost of the machine is $5000. The time until the first breakdown follows an exponential distribution with an expected value of 5 years, and the time between the first breakdown (repair) and the second breakdown (replacement) is also exponentially distributed, but with an expected value of 4 years. The time to perform the repairs is negligible.

Sample HW

Fall '97

page 69

56:171 Operations Research (a.) Formulate the problem as a continuous-time Markov chain, and draw its transition diagram. (Only 2 states are necessary. Let state 1 represent the condition before the first repair is made, and state 2 the condition after the first repair but before the second breakdown.) (b.) Write the balance equations and find the steady-state distribution of the state of the system, ð1 = ________ and ð2= ________. (c.) We want to find the average cost per year of repairs and replacements. To do this, first find: (i.) (Conditional) rate at which repairs are made when in state 1 (ii.) Rate at which repairs are made (value from (i) times ð1) ________ (iii.) (Conditional) rate at which replacements are made when in state 2. ________ (iv.) Rate at which replacements are made (value from (iii) times ð2) ________ (v.) Average cost per year (sum of the rates of repairs (ii) and replacements (iv) times the appropriate costs). ________ mmmmmmmmmm Homework #10 Solutions mmmmmmmmm 1. Discrete-Time Markov Chains. Define a Markov chain in which the state of the tree is observed each year immediately before the Christmas season begins. a. The four states of the system, and transition probabilities, are indicated below:

Sample HW

Fall '97

page 70

56:171 Operations Research

b. The absorbing states are #3: "dead" and #4: "cut ". Using the MARKOV workspace, and selecting "Absorption Analysis" on the menu produces the following output:

This computation could also be done manually as follows: Q = .595 .255 , E= I-Q -1 = .405 -.255 0 .34 0 .66 A = ER = 2.66667 .90909 0 1.51515 .15 .06 0 .6
-1

= 2.66667 .90909 0 1.51515 49 19 59 89

=

Sample HW

Fall '97

page 71

56:171 Operations Research c. According to the A matrix above, a protected tree has probability 54.54% (=a14) of eventually being cut & sold, and probability 45.45% (=a13) of eventually being lost to disease. d. The number which is expected to be eventually sold is 1500×a14+ 3500×a24 =1500(0.5454) + 3500(0.90909) = 818.1 + 3181.815 = 3999.9. That is, 54.54% of the protected trees (namely, 818.1) and 90.9% of the unprotected trees (namely, 3181.8) will be cut & sold, a total of about 4000 trees. The remaining 1000 (=3500+1500-4000) are expected to be lost to disease. e. If the tree is initially protected, the expected number of visits to the transient state #1 is e11=2.66667 and to transient state #3 is e12=0.90909. Note, however, that e11 counts the initial visit to state #1 (i.e., the initial harvest season), so that the number of additional visits to this state is 1.66667 (the expected number of years that it will be protected), i.e., the expected lifetime of the tree will be 1.6667 + 0.90909 = 2.5757 years. 2. Continuous-Time Markov Chains. Solution: (a.) Formulate the problem as a continuous-time Markov process, and draw its transition diagram. (Only 2 states are necessary. Let state 1 represent the condition before the first repair is made, and state 2 the condition after the first repair but before the second breakdown.)

(b.) Write the balance equations and find the steady-state distribution of the state of the system, ð1 and ð2. The balance equation for this C-T Markov Chain is 1 π =1 π 5 1 4 2 That is, the rate of transitions from state 1 in steady state should equal the rate of transitions into state 1, where the left side above is the rate of transitions from state 1 and the right side is the rate of transitions into state 1. (In this case, we get the identical balance equation for state 2.) As an alternative, we could write down the transition rate matrix Λ: - 15 15 Λ= 14 - 14 and then write the system of equations represented by πΛ = 0, namely - 1 5 π 1 + 1 4 π2 = 0 1 5 π1 - 1 4 π2 = 0 of which one may be discarded as redundant.

Sample HW

Fall '97

page 72

56:171 Operations Research The remaining equation, together with the restriction on the sum of the probabilities, gives us a system of 2 equations with 2 unknowns: 1π =1 π 5 1 4 2 π1 + π2 = 1 The optimal solution is π1 = 5 9 π2 = 4 9 (c.) We want to find the average cost per year of repairs and replacements. To do this, first find: (i.) (Conditional) rate at which repairs are made when in state 1 = 1/5 (ii.) Rate at which repairs are made (value from (i) times ð1) = (1/5) π1 = 1/9 (iii.) (Conditional) rate at which replacements are made when in state 2 = 1/4 (iv.) Rate at which replacements are made (value from (iii) times ð2) = (1/4)π2= 1/9 (v.) Average cost per year (sum of the rates of repairs (ii) and replacements (iv) times the appropriate costs). (1/9)($1000)+(1/9)($5000) = $666.67/year

Sample HW

Fall '97

page 73

56:171 Operations Research mmmmmmmmmm Homework #11 mmmmmmmmm 1. The college is trying to decide whether to rent a slow or fast copy machine. It is believed that an employee's time is worth $15/hour. The slow copier rents for $4 per hour, and it takes an employee an average of 10 minutes to complete a copy job (exponentially distributed). The fast copier rents for $15 per hour, and it takes an employee an average of 6 minutes to complete a copy job (also exponentially distributed). An average of 4 employees per hour need to use the copying machines (interarrival times are exponentially distributed). a. For each choice of machine, sketch the birth/death process model, showing the "birth" and "death" rates.

b. Which standard queueing model applies to this situation? (e.g., M/M/1, M/M/2, M/M/1/N, etc.) c. For each machine, what is: Utilization of the machine Average number of employees at the copy center: ______ Total cost (rental + employee time) ______ d. Which machine should the college rent? 2. (Exercise 6, page 1083-1084 of text by Winston) Bectol, Inc. is building a dam. A total of 10,000,000 cu ft of dirt is needed to construct the dam. A bulldozer is used to collect dirt for the dam. Then the dirt is moved via dumpers to the dam site. Only one bulldozer is available, and it rents for $100 per hour. Bectol can rent, at $40 per hour, as many dumpers as desired. Each dumper can hold 1000 cu ft of dirt. It takes an average of 12 minutes for the bulldozer to load a dumper with dirt, and it takes each dumper an average of five minutes to deliver the dirt to the dam and return to the bulldozer. Making appropriate assumptions about exponentiality so as to obtain a birth/death model, determine the optimal number of dumpers and the minimum total expected cost of moving the dirt needed to build the dam. a. What is the optimal number of dumpers? ______ b. What is the minimum expected cost of moving the dirt to build the dam? ______ Slow ______% Fast ______% ______ ______

Sample HW

Fall '97

page 74

56:171 Operations Research 3. A neighborhood grocery store has only one check-out counter. Customers arrive at the check-out at a rate of one per 2 minutes. The grocery store clerk requires an average of one minute and 30 seconds to serve each customer. However, as soon as the waiting line exceeds 2 customers, including the customer being served, the manager helps by packing the groceries, which reduces the average service time to one minute. Assume a Poisson arrival process and exponentially-distributed service times. a. Draw the flow diagram for a birth-death model of this system.

(b.) Either manually or using the Birth/Death workspace, compute the steady-state distribution of the number of customers at the check-out. (c.) What fraction of the time will the check-out clerk be idle? _________% (d.) What is the expected number of customers in the check-out area? __________ (e.) What is the expected length of time that a customer spends in the check-out area? ___________ minutes (f.) Suppose that the store is being remodeled, and space is being planned so that the waiting line does not overflow the space allocated to it more than 1 percent of the time, and that 4 feet must be allocated per customer (with cart). How much space should be allocated for the waiting line? ___________ feet (g.) What fraction of the time will the manager spend at the check-out area? _________% mmmmmmmmmm Homework #11 Solutions mmmmmmmmm 1. Solution: Slow copy machine : (M/M/1 model) λ=2, µ=4 W=1/(µ−λ)=0.5 (hr/job) = total time of employee per visit to copy machine Average cost per hour=(# jobs/hr)($15/hr)(hr/job)+($4/hr)=4(15)(0.5)+4= $34. Fast copy machine : (M/M/1 model) λ=4, µ=10 W=1/(µ−λ)=1/6hr/job) = total time of employee per visit to copy machine Average cost per hour=(# jobs/hr)($15/hr)(hr/job)+($15/hr)=4(15)(1/6)+15= $25. Therefore, we should choose the fast copy machine. 2. Solution:

Sample HW

Fall '97

page 75

56:171 Operations Research We have to use 10,000,000/1000=10,000 loads to deliver all the dirt. If the loader were to have 100% utilization , it would require 10000 loads / 5 loads/hr. = 2000 hours to complete the job. As the number of dumpers is increased, the utilization of the loader will increase (and the time required to complete the job will decrease ), so that the cost will decrease. We use "trial & error" below to find the optimal number of dumpers. Case 1 : One dumper : Define state 0 : no dumper in the system, state 1 : one dumper in the system. Steady-state Distribution 12/hr -----------------------------i Pi CDF 1 0 - ------------ ----------5/hr 0 0.294118 0.294118 1 0.705882 1.000000 Utilization of loader is 1−π0 = 70.5882%, so that the total time to complete the job will be 10000 loads = 2833.33 hours. .705882 × 5 loads/hr. The hourly cost of renting the bulldozer and 1 dumper is $100/hr + $40/hr = $140/hr, and so the total cost of completing the job will be 2833.33 hrs. (100$/hr. + 40 $/hr.) = $396,666 Case 2 : Two dumpers. Define state 0 : no dumper in the system, state 1 : one dumper in the system, state 2 : two dumpers in the system, one is being served and another is waiting. Steady-state Distribution -----------------------------2(12)/hr 12/hr i Pi CDF 1 2 0 1 - ------------ ----------0 0.057737 0.057737 5/hr 5/hr 1 0.277136 0.334873 2 0.665127 1.000000 Utilization of loader is 1−π0 = 94.2263%, so that the total time to complete 10000 loads = 2122.55 hours. .942263 × 5 loads/hr. the job will be The hourly cost of renting the bulldozer and 2 dumpers is $100/hr + 2($40/hr) = $180/hr, and so the total cost of completing the job will be 2122.55 hrs. × 180 $/hr. = $382,059 Case 3 : Three dumpers : Define state 0 : no dumper in the system, state 1 : one dumper in the system, state 2 : two dumpers in the system, one is being served and another is waiting.

Sample HW

Fall '97

page 76

56:171 Operations Research state 3 : three dumpers in the system, one is being served, and the other two are waiting.

Steady-state Distribution -----------------------------i Pi CDF 3(12)/hr 2(12)/hr 12/hr - ------------ ----------3 0 0.007955 0.007955 1 21 0 1 1 1 0.057277 0.065233 5/hr 5/hr 5/hr 2 0.659836 0.340164 3 0.659836 1.000000 Utilization of loader is 1−π0 = 99.2045%, so that the total time to complete the job will be 10000 loads = 2016.04 hours. .992045 × 5 loads/hr. The hourly cost of renting the bulldozer and 3 dumpers is $100/hr + 3($40/hr) = $220/hr, and so the total cost of completing the job will be 2016.04 hrs. × 220 $/hr. = $443,529 The system cost when there are two dumpers is less than that obtained when the number of dumpers is either increased to 3 or decreased to 1. Therefore, it is reasonable to conclude that the optimal number of dumpers is 2. 3. Solution: (a.) Draw the flow diagram for a birth-death model of this system.

The "birth" rate is 1/2 per minute for all states, while the "death" rate is 2/3 per minute in states 1 and 2, and 1/minute for higher-numbered states. (b.) Either manually or using the Birth/Death workspace, compute the steady-state distribution of the number of customers at the check-out. Manual computation: 12 2 12 2 12 12 2 12 2 12 2 12 3 1 = 1 + 12 π0 23 23 23 1 23 1 23 1 12 2 1 1 2 1 3 1 = 1 + 12 1+ 2 + 2 + 2 + π0 23 23 1 1 1 The infinite series within the braces is a geometric series with sum

+ +

+

+

+

+

Sample HW

Fall '97

page 77

56:171 Operations Research 1 =2 1-1 2 and so 12 2 2 1 = 1 + 12 2 = 1 +3 + 3 × 2 = 1 + 0.75 + 2(0.5625) = 2.875 23 23 4 4 π0 Therefore, π0 = 1/2.875 = 0.347826 and π2 = 0.75π0, π2=0.5625π0, etc.

+

Use of Birth/Death workspace: Entering the birth & death rates, and asking for computation of the steadystate probabilities up to π10, we get:

The computation of π0 is done by truncating the series after the 11th term, so that the probabilities above are approximations. However, from the CDF (cumulative distribution function), we see that p{# of customers 10} > 99.9%, so that the approximated probabilities should be very near to the actual probabilities. (c.) What fraction of the time will the check-out clerk be idle? π0 = 34.78% of the time, the check-out clerk will be idle. (d.) What is the expected number of customers in the check-out area?
∞

L = • iπ i = 0 + 0.608696 + 2×0.804348 + 3×0.902174 + i=0 According to the Birth/Death workspace, we get L=1.4267 customers (including the one being served, if any). (e.) What is the expected length of time that a customer spends in the check-out area? To compute the average time in the system, W, we use Little's Law: L = λW, where λ is the average arrival rate, in this case 1/2. Therefore, W = L/λ = 1.4267/(0.5/minute) = 2.8534 minutes. (f.) Suppose that the store is being remodeled, and space is being planned so that the waiting line does not overflow the space allocated to it more than 1 percent

Sample HW

Fall '97

page 78

56:171 Operations Research of the time, and that 4 feet must be allocated per customer (with cart). How much space should be allocated for the waiting line? By examining the cumulative probabilities (CDF) in the table above, we see that P{# in system 7} = 0.993886, i.e., P{# in system exceeds 7} = 0.6114%. Therefore, if we allocate enough space for 7 customers (6 waiting plus one being served), i.e., 24 feet plus space for the customer being served, the customers will overflow the space less than 1% of the time. (g.) What fraction of the time will the manager spend at the check-out area? 1−π0 − π1 − π2 = 1 - 0.804348 = 19.5652%. mmmmmmmmmm Homework #12 mmmmmmmmm 1. A system consists of 4 devices, each subject to possible failure, all of which must function in order for the system to function. In order to increase the reliability of the system, redundant units may be included, so that the system continues to function if at least one of the redundant units remains functional. The data are:
Device 1 2 3 4 Reliability (%) 80 90 75 85 Weight (kg.) 1 3 1 2

If we include a single unit of each device, then the system reliability will be only 45.9%. a. Explain how it is determined that the reliability is only 45.9%. However, by including redundant units of one or more devices, we can substantially increase the reliability. Suppose that the system may weigh no more than 12 kg. (Since at least one of each device must be included, a total of 7 kg, this leaves 5 kg available for redundant units.) Assume that no more than 3 units of any type need be considered. We wish to compute the number of units of each device type to be installed in order to maximize the system reliability, subject to the maximum weight restriction. The dynamic programming model arbitrarily assumes that the devices are considered in the order: #4, #3, #2, and finally, #1. The optimal value function is defined to be: Fn(S) = maximum reliability which can be achieved for devices #n, n-1, ... 1, given that the weight used by these devices cannot exceed S (the state variable) Note that the computation is done in the backward order, i.e., first the optimal value function F1(S) is computed for each value of the available weight S, then F2(S), etc., until finally F4(S) has been computed.

Sample HW

Fall '97

page 79

56:171 Operations Research

b. Explain the computation of the 97.75% reliability for 2 units of device #4 above.

Sample HW

Fall '97

page 80

56:171 Operations Research

c. What is the maximum reliability that can be achieved allowing 12 kg. total weight? d. How many units of each device should be included in the system? e. Four values have been blanked out in the output. What are they? i. the optimal value f2(9) ____________

ii. the optimal decision x2*(9) ____________ iii. the state which results from the optimal decision x2*(9) ____________ iv. the value associated with the decision to include 2 units of device #3, given that 10 kg. is still available ____________

Sample HW

Fall '97

page 81

56:171 Operations Research

f. Suppose that only 11 kg. of capacity were available. What is the achievable system reliability? How many units of each device should be included? 2. We wish to plan production of an expensive, low-demand item for the next three months (January, February, & March). • the cost of production is $15 for setup, plus $5 per unit produced, up to a maximum of 4 units. • the storage cost for inventory is $2 per unit, based upon the level at the beginning of the month. • a maximum of 3 units may be kept in inventory at the end of each month; any excess inventory is simply discarded. • the demand each month is random, with the same probability distribution: d 0 1 2 P{D=d} 0.3 0.4 0.3 • there is a penalty of $25 per unit for any demand which cannot be satisfied. Backorders are not allowed. • the inventory at the end of December is 1. • a salvage value of $4 per unit is received for any inventory remaining at the end of the last month (March) Consult the computer output which follows to answer the following questions: Note that in the computer output, stage 3 = January, stage 2 = February, etc. (i.e., n = # months remaining in planning period.) a. What is the optimal production quantity for January? _______ b. What is the total expected cost for the three months? __________ c. If, during January, the demand is 1 unit, what should be produced in February? ______ d. Three values have been blanked out in the computer output, What are they? i. the optimal value f2(1) ___________ ii. the optimal decision x2*(1) ___________ iii. the cost associated with the decision to produce 1 unit in February when the inventory is 0 at the end of January. ____________ The table of costs for each combination of state & decision at stage 2 is:

The tables of the optimal value function fn(Sn) at each stage are:

Sample HW

Fall '97

page 82

56:171 Operations Research

mmmmmmmmmm Homework #12 Solutions mmmmmmmmm 1. Solution: a. Explain how it is determined that the reliability is only 45.9%. Solution. (0.8)(0.9)(0.75)(0.85)=0.459. b. Explain the computation of the 97.75% reliability for 2 units of device #4 above. Solution. 1- (1- 0.85)(1- 0.85)=0.9775 or 97.75%.

Sample HW

Fall '97

page 83

56:171 Operations Research

0.89

0.98

2

3

Sample HW

Fall '97

page 84

56:171 Operations Research

c. What is the maximum reliability that can be achieved allowing 12 kg. total weight? Solution. 0.83. d. How many units of each device should be included in the system? Solution. Device # 1 2 3 4 # of units 1 1 3 2

e. Four values have been blanked out in the output. What are they? i. the optimal value f2(9) ___0.98_____

ii. the optimal decision x2*(9) ____2_____ iii. the state which results from the optimal decision x2*(9) _____3_____ iv. the value associated with the decision to include 2 units of device #3, given that 10 kg. is still available ______0.98____ f. Suppose that only 11 kg. of capacity were available. What is the achievable system reliability? How many units of each device should be included? Solution. Reliability=0.79.

Sample HW

Fall '97

page 85

56:171 Operations Research Device # 1 2 3 4 # of units 1 1 2 2

2. Solution a. What is the optimal production quantity for January? ___0____ b. What is the total expected cost for the three months? ___39.83____ c. If, during January, the demand is 1 unit, what should be produced in February? ___3__ d. Three values have been blanked out in the computer output, What are they? i. the optimal value f2(1) ____26.69____ ii. the optimal decision x2*(1) ___0_____ iii. the cost associated with the decision to produce 1 unit in February when the inventory is 0 at the end of January. ____44.69____ Solution. inventory production * f1 +penalty cost cost P(d) d 0.3 0.4 0.3 0 1 2 0 0 0 15+5 15+5 15+5 8.3 21 21+25

(0.3)(15+5+8.3)+(0.4)(15+5+21)+(0.3)(15+5+25+21)=44.69. The table of costs for each combination of state & decision at stage 2 is:

44.69

The tables of the optimal value function fn(Sn) at each stage are:

Sample HW

Fall '97

page 86

56:171 Operations Research

26.69

0

Sample HW

Fall '97

page 87