Skip to content
Textbook Guides

Solution Manual for Optimization in Operations Research, 2nd Edition

Solution Manual for Optimization in Operations Research, 2nd Edition is your ultimate textbook solutions guide, providing answers to the most difficult questions.

Preview 16 of 186 pages

See the first 16 pages exactly as they appear in the document.

  1. Page 1
    Read page 1 as text

    1 Chapter 1 Solutions 1 2 1 Supplement to the 2nd edition of Optimization in Operations Research , by Ronald L. Rardin, Pearson Higher Education, Hoboken NJ, ○ c 2017. 2 As of June 4, 2015 1-1 . (a) The only unsettled quantity is decision variable s . (b) Given quantities or parameters are d , p and b . (c) Minimize the maximum error, i.e. objective min ( d/s ) 2 (d) We must have an integer number of sensors and not exceed the available budget, i.e. constraints ps ≤ b , s nonnegative and integer. 1-2 . (a) Feasible because 3 . 5(4) 14 ≤ , and optimal because any larger s would not be feasible. (b) Infeasible and thus not optimal because 3 . 5(6) / ≤ 14 . (c) Feasible because 3 . 5(2) ≤ 14 , but not optimal because feasible solution s = 4 yields a better objective value. 1-3 . (a) The only quantities to be determined are x 1 and x 2 , the numbers of lots on the 2 lines. (b) Given quantities or parameters are t 1 , t 2 , c 1 , c 2 , b and T . (c) Minimize total production cost or objective min c 1 x 1 + c 2 x 2 . (d) t 1 x 1 + t 2 x 2 ≤ T (at most T hours of production), x 1 + x 2 = b (produce b lots), x 1 , x 2 ≥ 0 and integer (numbers nonnegative integers). 1-4 . (a) Infeasible and thus not optimal because 10(0) + 20(3) / ≤ 40 . (b) Feasible because 10(2) + 20(1) ≤ 40 and 2 + 1 = 3 . Also optimal because no more or less expensive x 2 can be used if b = 3 lots are to run. (c) Feasible because 10(3) + 20(0) ≤ 40 and 3 + 0 = 3, but not optimal because x 1 = 2, x 2 = 1 yields a lower cost. 1-5 . (a) Exact numerical optimization because it is the maximum feasible choice for the given set of parameter values. (b) Descriptive modeling because we have merely evaluated the consequences of a given choice of decision variables and parameters. (c) Closed-form optimization because an optimal solution is specified for each choice of decision variables. (d) Heuristic optimization because a good feasible solution is identified for the given choice of parameter values, but a non-usual layout might yield superior results. 1-6 . (a) Provides optimum for all choices of input parameters, not just one. (b) Provides a provably best solution, not just a good feasible one. (c) Systematically searches for a good feasible solution, rather than just evaluating the consequences of one. 1-7 . Higher tractability usually means loss of validity, so results from the model might not be useful in the application. 1-8 . (a) (3 for the first) · (3 for the second) · . . . · (3 for the n th) = 3 n combinations. (b) One run per second is 3,600 per hour, 86,400 per day, 31,536,000 per year. The 3 10 = 59 , 049 requires 59 , 049 / 3 , 600 = 16 . 4 hours; 3 15 = 14 , 348 , 907 requires 166.1 days; 3 20 ≈ 3 . 49 × 10 9 requires 110.6 years; and 3 30 ≈ 2 . 06 × 10 14 requires 6.5 million years. (c) Practical computation would be limited to a few days which could accommodate no more than 10 − 11 decision variables. 1-9 . (a) Random variable because short term rainfall is unpredictable. (b) Deterministic quantity because annual rainfall averages are fairly stable. (c) Deterministic quantity be- cause history can be known with certainty. (d) Random variable because future stock market behavior is highly uncertain. (e) Deterministic quantity because the seating capacity is fairly fixed. (f ) Random variable because night to night arrivals are usually variable. (g) Ran- dom variable because breakdowns make the ef- fective production rate uncertain. (h) Deter- ministic quantity because a reliable robot has a predictable rate of production. (i) Determin- istic quantity because short term demand for such an expensive product would be fairly well known for the next few days. (j) Random vari- able because long term demand for a product is usually uncertain.

  2. Page 2
  3. Page 3
    Read page 3 as text

    1 Chapter 2 Solutions 1 2 1 Supplement to the 2nd edition of Optimization in Operations Research , by Ronald L. Rardin, Pearson Higher Education, Hoboken NJ, ○ c 2017. 2 As of September 24, 2015 2-1 . (a) max 200 x 1 + 350 x 2 (max total profit), s.t. 5 x 1 + 5 x 2 ≤ 300 (legs), 0 . 6 x 1 + 1 . 5 x 2 ≤ 63 (assembly hours), x 1 ≤ 50 (wood tops), x 2 ≤ 35 (glass tops), x 1 ≥ 0 , x 2 ≥ 0 (b) x ∗ 1 =basic=30, x ∗ 2 =deluxe=30 (c) x 1 x 1 ≤ 50 x 2 x 2 ≤ 35 ≥ 0 x 2 ≥ 0 x 1 5 +5 x 2 x 1 ≤ 300 ≤ .6 +1.5 x 2 x 1 63 10 20 30 40 10 20 30 40 x 2 x 1 ( *, *) = (30,30) 50 50 max (d) x 1 x 1 ≤ 50 x 2 x 2 ≤ 35 ≥ 0 x 2 ≥ 0 x 1 5 +5 x 2 x 1 ≤ 300 ≤ .6 +1.5 x 2 x 1 63 10 20 30 40 10 20 30 40 50 50 max alternative optima All optimal from x = (30 , 30) to x = (17 . 5 , 35). 2-2 . (a) max . 11 x 1 + . 17 x 2 (max total return), s.t. x 1 + x 2 ≤ 12 ($12 million investment), x 1 ≤ 10 (max $10 million domestic), x 2 ≤ 7 (max $7 million foreign), x 1 ≥ . 5 x 2 (domestic at least half foreign), x 2 ≥ . 5 x 1 (foreign at least half domestic), x 1 ≥ 0, x 2 ≥ 0 (b) x ∗ 1 =domestic=$5 million , x ∗ 2 = foreign=$7 million (c) x 1 x 2 4 8 12 4 8 12 x ≥ 0 1 x ≥ 0 2 1 x ≤ 10 2 x ≤ 7 1 2 x + x ≤ 12 2 1 x ≥ .5 x x ≥ .5 x 2 1 optimal solution ( x * , x * )=(5,7) 1 2 max (d) x 1 2 4 8 12 4 8 12 x ≥ 0 1 x ≥ 0 2 1 x ≤ 10 2 x ≤ 7 1 2 x + x ≤ 12 2 1 x ≥ .5 x x ≥ .5 x 2 1 max alternative optima x All optimal from x = (5 , 7) to x = (8 , 4). 2-3 . (a) min 3 x 1 + 5 x 2 (min total cost), s.t. x 1 + x 2 ≥ 50 (at least 50 thousand acres), x 1 ≤ 40 (at most 40 thousand from Squawking Eagle), x 2 ≤ 30 (at most 30 thousand from Crooked Creek), x 1 ≥ 0 , x 2 ≥ 0 (b) x ∗ 1 =Squawking Eagle=40 thousand, x ∗ 2 =Crooked Creek=10 thousand

  4. Page 4
    Read page 4 as text

    2 (c) x 1 x 2 25 50 75 25 50 75 100 x + x ≤ 95 1 2 1 2 x + x ≥ 50 x ≤ 30 2 x ≥ 0 1 x ≥ 0 2 x ≤ 40 1 ( x * , x * ) = (40,10) 1 2 optimal solution min (d) x 1 x 2 25 50 75 25 50 75 100 x + x ≤ 95 1 2 1 2 x + x ≥ 50 x ≤ 30 2 min Improves forever in direction Δ x 1 = 1 , Δ x 2 = 1 − . (e) x 1 x 2 25 50 75 25 50 75 100 x + x ≤ 95 1 2 1 2 x + x ≥ 50 x ≤ 30 2 x ≥ 0 1 x ≥ 0 2 x ≤ 0 2 x ≤ 40 1 x 2 = 0 leaves no feasible. 2-4 . (a) max x 1 (max beef content), s.t. x 1 + x 2 ≥ 125 (weight at least 125), 2 . 5 x 1 + 1 . 8 x 2 ≤ 350 (calories at most 350), 0 . 2 x 1 + 0 . 1 x 2 ≤ 15 (fat at most 15), 3 . 5 x 1 + 2 . 5 x 2 ≤ 360 (sodium at most 360), x 1 ≥ 0, x 2 ≥ 0 (b) x ∗ 1 =beef=25g , x ∗ 2 =chicken=100g (c) x 1 x 2 25 50 75 100 125 150 175 10 20 30 40 50 x + x ≥ 125 1 2 2.5 x +1.8 x ≤ 350 1 2 x ≥ 0 1 x ≥ 0 2 0.2 x + 0.1 x ≤ 15 1 2 3.5 x + 2.5 x ≤ 360 1 2 max optimal solution ( x * , x * ) = (25,100) 1 2 (d) x 1 x 2 25 50 75 100 125 150 175 10 20 30 40 50 2.5 x +1.8 x ≤ 350 1 2 x ≥ 0 1 x ≥ 0 2 0.2 x + 0.1 x ≤ 15 1 2 3.5 x + 2.5 x ≤ 360 1 2 1 2 x + x ≥ 200 x 1 + x 2 ≥ 200 leaves no feasible.

  5. Page 5
    Read page 5 as text

    3 (e) x 1 x 2 25 50 75 100 125 150 175 10 20 30 40 50 2.5 x +1.8 x ≤ 350 1 2 0.2 x + 0.1 x ≤ 15 1 2 3.5 x + 2.5 x ≤ 360 1 2 max Improve forever in direction Δ x 1 = 1 , Δ x 2 = − 2 . 2-5 . (a) max 450 v + 200 c (max total profit), s.t. 10 v + 7 c ≤ 70000 (water at most 70000 units), v + c ≤ 10000 (total acreage 10000), v ≤ 7000 (at most 70% vegetables), c ≤ 7000 (at most 70% cotton), v ≥ 0, c ≥ 0 (b) v ∗ = 7000, c ∗ = 0 (c) v c 2000 4000 6000 8000 2000 4000 6000 8000 10000 10 v + 7 c ≤ 70000 v + c ≤ 10000 v ≥ 0 c ≥ 0 v ≤ 7000 c ≤ 7000 optimal solution ( v *, c *) = (7000,0) max (d) v c 2000 4000 6000 8000 2000 4000 6000 8000 10000 10 v + 7 c ≤ 70000 v + c ≤ 10000 max Improves forever in direction Δ v = 10 , Δ c = − 7 . (e) c 2000 4000 6000 8000 2000 4000 6000 8000 10000 10 v + 7 c ≤ 70000 v + c ≤ 10000 v ≥ 0 c ≥ 0 v ≤ 7000 c ≤ 7000 v + c ≥ 10000 No solution with v + c = 10000. 2-6 . (a) min x 1 + x 2 (min used stock), s.t. 5 x 1 + 3 x 2 ≥ 15 (cut at least 15 long rolls), 2 x 1 + 5 x 2 ≥ 10 (cut at least 10 short rolls), x 1 ≤ 4 (at most 4 times on pattern 1), x 2 ≤ 4 (at most 4 times on pattern 2), x 1 , x 2 ≥ 0 and integer. (b) Partial cuts make no physical sense because all unused material is scrap. (c) Either x ∗ 1 = x ∗ 2 = 2 , or x ∗ 1 = 3, x ∗ 2 = 1

  6. Page 6
    Read page 6 as text

    4 (d) x 1 2 x ≤ 4 1 x ≥ 0 1 5 x + 3 x ≥ 15 1 2 2 x + 5 x ≥ 10 1 2 x ≤ 4 2 2 x ≥ 0 alternative optima min 1 2 3 4 5 1 2 3 4 5 x (e) Both (2 , 2) and (3 , 1) are feasible and lie on the best contour of the objective. 2-7 . (a) min 16 x 1 + 16 x 2 (min total wall area), s.t. x 1 x 2 = 500 (500 sqft pool), x 1 ≥ 2 x 2 (length at least twice width), x 2 ≤ 15 (width at most 15 ft), x 1 ≥ 0, x 2 ≥ 0 (b) x ∗ =length=33 1 feet 1 3 , x ∗ =width 2 =15 feet (c) x 1 2 10 20 30 40 10 20 30 40 x ≥ 0 1 x ≥ 2 x 2 1 x x = 500 1 2 2 x ≥ 0 x ≤ 15 2 50 optimal solution ( x * , x * ) = (33.33,15) 1 2 min x (d) x 1 x 2 10 20 30 40 10 20 30 40 x ≥ 0 1 x ≥ 2 x 2 1 x x = 500 1 2 2 x ≥ 0 x ≤ 15 2 50 x ≤ 25 1 x 1 ≤ 25 leaves no feasible. 2-8 . (a) max x 2 (max number of floors), s.t. π/ 4( x 1 ) 2 x 2 = 150000 (150000 sqft floor space), 10 x 2 ≤ 4 x 1 (height at most 4 times diameter), x 1 0, x 2 0 ≥ ≥ (b) x ∗ 1 = diameter = 78 . 16 feet, x ∗ 2 = floors = 31.26 (c) x 1 2 x ≥ 0 1 2 x ≥ 0 20 40 60 80 100 20 40 60 80 10 x ≤ 4 x 1 2 π ( x ) x = 150000 1 2 2 1 4 _ optimal solution ( x * , x * ) = (78.16,31.26) 1 2 max x (d) x 1 x 2 x ≥ 0 1 2 x ≥ 0 20 40 60 80 100 20 40 60 80 10 x ≤ 4 x 1 2 π ( x ) x = 150000 1 2 2 1 4 _ x ≤ 50 1 x 1 ≤ 50 leaves no feasible. 2-9 . (a) (b) min x 2 (c) min x 1 + x 2 (d) max x 2 (e) x 2 ≤ 1 / 2 2-10 .

  7. Page 7
    Read page 7 as text

    5 (a) (b) min x 1 + x 2 (c) min x 1 (d) max x 1 (e) x 1 + x 2 1 ≤ 2-11 . (a) min 4 i =3 i 2 j =1 y i,j ∑ ∑ (b) max ∑ 4 i =1 iy i, 3 (c) max ∑ p i =1 α i y i, 4 (d) min ∑ t i =1 δ i y i (e) ∑ 4 j =1 y i,j = s i , i = 1 , . . . , 3 (f ) ∑ 4 j =1 a j,i y j = c i , i = 1 , . . . , 3 2-12 . (a) ∑ 17 i =1 x i,j,t ≤ 200 , j = 1 , . . . , 5; t = . . . , 7; 35 constraints (b) ∑ 5 j =1 ∑ 7 t =1 x 5 ,j,t ≤ 4000 ; 1 constraint (c) ∑ 5 j =1 x i,j,t ≥ 100 , i = 1 , . . . , 17; t = 1 , . . . , 7; 119 constraints 2-13 . model; param m; param n; param p; set products := 1 .. m; set lines := 1 .. n; set weeks := 1 .. p; var x { i in products, j in lines, t in weeks } >= 0; subject to # part (a) linecap { j in lines, t in weeks } : sum { i in products } x[i,j,t] <= 200; # part (b) prod5lim: sum { j in lines, t in weeks } x[5,j,t] <= 4000; # part (c) minprodn { i in products, t in weeks } : sum { j in lines } x[i,j,t] >= 100; # data; param m := 17; param n := 5; param p := 7; 2-14 . (a) ∑ 9 j =1 x i,j,t ≤ p i , i = 1 , . . . , 47; t = 1 , . . . , 10 ; 470 constraints (b) 0 . 25 ∑ 47 i =1 ∑ 9 j =1 x i,j,t ≤ ∑ 47 i =1 x i, 4 ,t ; t = 1 , . . . , 5; 5 constraints (c) x i, 1 ,t ≥ x i,j,t i = 1 , . . . , 47; j = 1 , . . . , 9; t = 1 , . . . , 10; 4230 constraints 2-15 . model; param m; param n; param q; set plots := 1 .. m; set crops := 1 .. n; set years := 1 .. q; param p { i in plots } ; var x { i in plots, j crops, t in years } >= 0 ; subject to # part (a) acrelims { i in plots, t in years } : sum { j in crops } x[i,j,t] <= p[i]; # part (b) crop4min { t in years: t <= 5 } : 0.25* sum { i in plots, j in crops } x[i,j,t] <= sum { i in plots } x[i,4,t]; # part (c) beam1st { i in plots, j in crops, t in years } : x[i,1,t] >= x[i,j,t]; # data; param m := 47; param n := 9; param q := 10; 2-16 . (a) f ( y 1 , y 2 , y 3 ) Δ = ( y 1 ) 2 y 2 /y 3 , g 1 ( y 1 , y 2 , y 3 ) Δ = y 1 + y 2 + y 3 , b 1 = 13 , g 2 ( y 1 , y 2 , y 3 ) Δ = 2 y 1 − y 2 + 9 y 3 , b 2 = 0 , g 3 ( y 1 , y 2 , y 3 ) Δ = y 1 , b 3 = 0, g 4 ( y 1 , y 2 , y 3 ) Δ = y 3 , b 4 = 0 (b) f ( y 1 , y 2 , y 3 ) Δ = 13 y 1 + 22 y 2 + 10 y 2 y 3 + 100 , g 1 ( y 1 , y Δ 2 , y 3 ) = y 1 − y 2 + 9 y 3 , b 1 = − 5 , g 2 ( y 1 , y 2 , y 3 ) Δ = 8 y 2 − 4 y 3 , b 2 = 0, g 3 ( y 1 , y 2 , y 3 ) Δ = y 1 , b 3 = 0, g 4 ( y Δ 1 , y 2 , y 3 ) = y 2 , b 4 = 0 , g ( y Δ 5 1 , y 2 , y 3 = y 3 , b 5 = 0 , 2-17 . (a) Linear because LHS is a weighted sum of the decision variables. (b) Linear because both LHS and RHS are weighted sums of the decision variables. (c) Nonlinear because LHS has reciprocal 1 /x 9 . (d) Linear because LHS is a weighted sum of the decision variables. (e) Nonlinear because LHS has ( x j ) 2 terms . (f ) Nonlinear because LHS has log( x 1 ) term, and RHS has a product of

  8. Page 8
    Read page 8 as text

    6 variables. (g) Nonlinear because LHS has max operator. (h) Linear because LHS is a weighted sum of the decision variables. 2-18 . (a) LP because the objective and all constraints are linear. (b) NLP because of the nonlinear objective function with reciprocal of w 2 . (c) NLP because of the nonlinear first constraint. (d) LP because the objective and all constraints are linear. 2-19 . (a) Continuous because fractions make sense. (b) Discrete because they either closed or not. (c) Discrete because a specific process must be used. (d) Continuous because fractions can probably be ignored. 2-20 . (a) 8 ∑ j =1 x j = 3 (b) x 1 + x 2 + x 4 + x 5 ≥ 2 (c) x 3 + x 8 ≤ 1 (d) x 4 x 1 ≥ 2-21 . (a) max 85 x 1 + 70 x 2 + 62 x 3 + 93 x 4 (max total score), s.t. 700 x 1 + 400 x 2 + 300 x 3 + 600 x 4 ≤ 1000 ($1 million available), x j = 0 or 1 , j = 1 , . . . , 4 (b) Fund 2 and 4, i.e. x ∗ 1 = x ∗ 3 = 0 , x ∗ 2 = x ∗ 4 = 1 2-22 . (a) min 43 y 1 + 175 y 2 + 60 y 3 + 35 y 4 (min total land cost), s.t. y 2 + y 4 ≥ 1 (service NW), y 1 + y 2 + y 4 ≥ 1 (service SW), y 2 + y 3 ≥ 1 (service capital), y 1 + y 4 ≥ 1 (service NE), y 1 + y 2 + y 3 ≥ 1 (service SE), y j = 0 or 1 , j = 1 , . . . , 4 (b) Build 3 and 4, i.e. y 1 ∗ = y 2 ∗ = 0, y 3 ∗ = y 4 ∗ = 1 2-23 . (a) ILP because the objective and all constraints are linear, but variables are discrete. (b) NLP because the objective is nonlinear and all variables are continuous. (c) INLP because the objective is nonlinear and variables are discrete. (d) LP because the objective and all constraints are linear, and all variables are continuous. (e) INLP because the one constraint is nonlinear, and z 3 are discrete. (f ) ILP because the objective and all constraints are linear, but variables z 1 and z 3 are discrete. (g) LP because the objective and all constraints are linear, and all variables are continuous. (h) INLP because the objective is nonlinear and z 3 is discrete. 2-24 . (a) Model (d) because LP’s are generally more tractable than ILP’s. (b) Model (d) because LP’s are generally more tractable than NLP’s. (c) Model (d) because LP’s are generally more tractable than INLP’s. (d) Model (f) because ILP’s are generally more tractable than INLP’s. (e) Model (g) because LP’s are generatlly more tranctable than ILP’s. 2-25 . (a) x 1 x 2 4 12 16 4 8 12 16 x ≤ 8 1 x ≥ 0 2 x ≥ 0 1 - x + x ≤ 4 1 2 max alternative optimal solutions Alternative optima from x ∗ 1 = 8 , x ∗ 2 = 0 to x ∗ 1 = 8, x ∗ 2 = 12 (b) x 1 x 2 4 12 16 4 8 12 16 x ≤ 8 1 x ≥ 0 2 x ≥ 0 1 - x + x ≤ 4 1 2 max optimal solution ( x * , x * ) = (0,4) 1 2 Unique optimum x ∗ 1 = 0, x ∗ 2 = 4 (c) Helping one can hurt the other. 2-26 .

  9. Page 9
    Read page 9 as text

    7 (a) Unique optimum x ∗ 1 = 4, x ∗ 2 = 0 (b) Unique optimum x ∗ 1 = 0, x ∗ 2 = 4 (c) Helping one can hurt the other. 2-27 . (a) min . 092 x 4 + . 112 x 5 + . 141 x 6 + . 420 x 9 + . 719 x 12 (min total cost), s.t. x 4 + x 5 + x 6 + x 9 + x 12 = 16000 (16000m line), . 279 x 4 + . 160 x 5 + . 120 x 6 + . 065 x 9 + . 039 x 12 ≤ 1600 (at most 1600 Ohms resistance), . 00175 x 4 + . 00130 x 5 + . 00161 x 6 + . 00095 x 9 + . 00048 x 12 ≤ 8 . 5 (at most 8.5 dBell attenuation), x 4 , x 5 , x 6 , x 9 , x 12 ≥ 0 (b) Nonzeros: x ∗ 5 = 1000 , x ∗ 12 = 15000 2-28 . (a) Pump rates are the decisions to be made. (b) u Δ j = the capacity of pump j , c Δ j = the pumping cost of pump j (c) min ∑ 10 j =1 c j x j (d) x 1 + x 4 + x 7 ≤ 3000 (well 1), x 2 + x 5 + x 8 ≤ 2500 (well 2), x 3 + x 6 + x 9 + x 10 ≤ 7000 (well 3) (e) x j ≤ u j , j = 1 , . . . , 10 (f ) ∑ 10 j =1 x j ≥ 10000 (g) x j ≥ 0, j = 1 , . . . , 10 (h) A single objective LP because the one objective and all constraints are linear, and all variables are continuous. (i) x ∗ 1 = x ∗ 2 = x ∗ 3 = 1100, x ∗ 4 = x ∗ 6 = 1500 , x ∗ 5 = 1400, x ∗ 7 = 400¡ x ∗ 8 = x ∗ 10 = 0, x ∗ 9 = 1900 2-29 . (a) The decisions to be made are which projects to undertake. (b) p Δ j = the profit for project j , m Δ j = the man-days required on project j , and t Δ j = the CPU time required on project j . (c) max ∑ 8 j =1 p j x j (d) 7 ≤ ( ∑ 8 j =1 m j x j ) / 240 ≤ 10 (e) ∑ 8 j =1 t j x j ≤ 1000 (computer time), ∑ 8 j =1 x j ≥ 3 (select at least 3); x 3 + x 4 + x 5 + x 8 ≥ 1 (include at least 1 of director’s favorites) (f ) x j = 0 or 1 , j = 1 , . . . , 8 (g) A single objective ILP because the one objective and all constraints are linear, but variables are discrete. (h) x ∗ 1 = x ∗ 3 = x ∗ 6 = x ∗ 7 = 1 , others = 0 2-30 . (a) We must decide what quantities to move from surplus sites to fulfill each need. (b) s Δ i = the supply available at i , r Δ j = the quantity needed at j , d Δ i,j = the distance from i to j . (c) min ∑ 4 i =1 ∑ 7 j =1 d i,j x i,j (d) 7 ∑ j =1 x i,j = s i , i = 1 , . . . , 4 (e) ∑ 4 i =1 x i,j = r j , j = 1 , . . . , 7 (f ) x i,j ≥ 0, i = 1 , . . . , 4, j = 1 , . . . , 7 (g) A single objective LP because the one objective and all constraints are linear, and all variables are continuous. (h) Nonzeros: x ∗ 1 , 1 = 81, x ∗ 1 , 2 = 93 , x ∗ 1 , 3 = 166, x ∗ 1 , 5 = 90, x ∗ 1 , 6 = 85, x ∗ 1 , 7 = 145 , x ∗ 2 , 2 = 301, x ∗ 3 , 1 = 166, x ∗ 3 , 4 = 105, x ∗ 4 , 3 = 99 2-31 . (a) The values to be chosen are the

  10. Page 10
    Read page 10 as text

    8 coefficients in the estimating relationship. (b) min n j =1 ( c j − k/ (1 + e a + bf j ) ) 2 ∑ (min total squared error) (c) Single objective NLP because the objective is quadratic, there are no constraints, and all variables are continuous. 2-32 . (a) The decisions to be m ade are where to assign each teacher. (b) min 22 ∑ i =1 ∑ 22 j =1 c i,j x i,j (min total cost), max ∑ 22 22 i =1 ∑ j =1 t i,j x i,j (max total teacher preference), max ∑ 22 i =1 ∑ 22 j =1 s i,j x i,j (max total supervisor preference), max ∑ 22 i =1 ∑ 22 j =1 p i,j x i,j (max total principal preference) (c) ∑ 22 j =1 x i,j = 1 , i = 1 , . . . , 22 (each teacher i ) (d) ∑ 22 i =1 x i,j = 1, j = 1 , . . . , 22 (each school j ) (e) x i,j = 0 or 1, i, j = 1 , . . . , 22 (f ) A multiobjective ILP because the 4 objectives and all constraints are linear, but variables are discrete. 2-33 . (a) Each task must go to Assistant 0 or Assistant 1. (b) max 100(1 − x 1 ) + 80 x 1 + 85(1 − x 2 ) + 70 x 2 + 40(1 − x 3 ) + 90 x 3 + 45(1 − x 4 ) + 85 x 4 + 70(1 − x 5 ) + 80 x 5 + 82(1 − x 6 ) + 65 x 6 6 j =1 x j = 3 ∑ (c) (d) x 5 = x 6 (e) x j = 0 or 1, j = 1 , . . . , 6 (f ) A single objective ILP because the one objective and all constraints are linear, but variables are discrete. (g) x ∗ 2 = x ∗ 3 = x ∗ 4 = 1 , others = 0 2-34 . (a) Batch sizes are the decisions to be made. (b) min x j /d j , j = 1 , . . . , 4 (each burger j ) (c) ∑ 4 j =1 t j d j /x j ≤ 60 (d) 0 ≤ x j ≤ u j , j = 1 , . . . , 4 (e) Multiobjective NLP because the first constraint is nonlinear and all variables are continuous. 2-35 . (a) The issue is how many cars to move from where to where. (b) Relatively large values can be rounded if fractional without much loss, and continuous is more tractable. (c) c Δ i,j = the cost of moving a car from i to j , p Δ j = the number of cars presently at j , n Δ j = the number of cars required at j (d) min ∑ 5 i =1 ∑ 5 j =1 ,j = i c i,j x i,j (e) ∑ 5 i =1 ,i = k x i,k − 5 j =1 ,j = k x k,j = n k − p k ∑ , k = 1 , . . . , 5 (each region k ) (f ) x i,j ≥ 0, i, j = 1 , . . . , 5, i = j (g) A single objective LP because the one objective and all constraints are linear, and all variables are continuous. (h) Nonzero values: x ∗ 4 , 2 = 115 , x ∗ 4 , 3 = 165 , x ∗ 5 , 1 = 85, x ∗ 5 , 3 = 225 / / / / 2-36 . (a) We must decide how much of what fuel to burn at each plant. (b) min ∑ 4 f =1 ∑ 23 p =1 c f,p x f,p (c) min ∑ 4 f =1 s f ∑ 23 p =1 x f,p (d) 4 ∑ f =1 e f x f,p ≥ r p , p = 1 , . . . , 23 (each plant p ); 23 constraints (e) x f,p ≥ 0 , f = 1 , . . . , 4, p = 1 , . . . , 23; 92 constraints (f ) A multiobjective LP because the 2 objectives and all constraints are linear, and all variables are continuous. 2-37 . (a) The available options are to buy whole logs or green lumber. (b) Relatively large magnitudes can be rounded without much loss, and continuous is more tractable. (c) min 70 x 10 + 200 x 15 + 620 x 20 + 1 . 55 y 1 + 1 . 30 y 2 (d) 100( . 09) x 10 + 240( . 09) x 15 + 400( . 09) x 20 + . 10 y 1 + . 08 y 2 ≥ 2350 (e) x 10 + x 15 + x 20 ≤ 1500 (sawing capacity), 100 x 10 + 240 x 15 + 400 x 20 + y 1 + y 2 ≤ 26500 (drying capacity) (f ) x 10 ≤ 50 (size 10 log availability), x 15 ≤ 25 (size 15 log availability), x 20 ≤ 10 (size 20 log availability), y 1 ≤ 5000 (grade 1 green lumber availability) (g) x 10 , x 15 , x 20 , y 1 , y 2 ≥ 0 (h) A single objective LP because the one

  11. Page 11
    Read page 11 as text

    9 objective and all constraints are linear, and all variables are continuous. (i) x ∗ 10 = 50, x ∗ 15 = 25, x ∗ 20 = 5, y 1 ∗ = 5000 , y 2 ∗ = 8500 2-38 . (a) Decisions to be made are when to schedule each film. (b) m − 1 m n min j =1 j ′ = j +1 a j,j ′ t =1 x j,t x j ′ ,t ∑ ∑ ∑ (c) ∑ n t =1 x j,t = 1 , j = 1 , . . . , m (each film j ) (d) m j =1 x j,t ≤ 4 ∑ , t = 1 , . . . , n (each time t ) (e) x j,t = 0 or 1, j = 1 , . . . , m ; t = 1 , . . . , n (f ) A single objective INLP because the one objective is nonlinear, and variables are discrete. (g) model; param m; param n; set films := 1 .. m; set slots := 1 .. n; var x { j in films, t in slots } binary; param a { j in films, jp in films } ; minimize totconflict: sum { j in films, jp in films: j < m and jp > j } a[j,jp]*sum { t in slots } x[j,t]*x[jp,t]; subject to allin { j in films } : sum { t in slots } x[j,t] = 1; max4 { t in slots } :sum { j in films } x[j,t] <= 4; 2-39 . (a) We need to decide both which offices to open and how to service customers from them. (b) Offices must either be opened or not. (c) f Δ i = fixed cost of site i , c Δ i,j = unit cost of audits at j from i , r Δ j = required number of audits in state j (d) 5 5 5 min i =1 j =1 c i,j r j x i,j + i =1 f i y i ∑ ∑ ∑ (e) ∑ 5 i =1 x i,j = 1 , j = 1 , . . . , 5 (each location j ) (f ) x i,j ≤ y i , i, j = 1 , . . . , 5 (each site i , location j combination) (g) x i,j ≥ 0 , i, j = 1 , . . . , 5, y i = 0 or 1, i = 1 , . . . , 5 (h) A single objective ILP because the one objective and all constraints are linear, but the y i variables are discrete. (i) Nonzeros: x ∗ 2 , 2 = x ∗ 2 , 4 = x ∗ 3 , 1 = x ∗ 3 , 3 = x ∗ 5 , 5 = 1 , y 2 ∗ = y 3 ∗ = y 5 ∗ = 1 (j) model; param m; param n; set sites := 1 .. m; set states := 1 .. n; var x { i in sites, j in states } >= 0; var y { i in sites } binary; param c { i in sites, j in states } ; param f { i in sites } binary; param r { j in states } ; minimize totcost: sum { i in sites, j in states } c[i,j]*r[j]*x[i,j] + sum { i in sites } f[i]*y[i]; x[j,t]*x[jp,t]; subject to doeach { j in states } : sum { i in sites } x[i,j] = 1; switch { i in sites, j in states } : x[i,j] <= y[i]; data; param m := 5; param n := 5; param f := 1 160 2 49 3 246 4 86 4 100; param r := 1 200 2 100 3 300 4 100 5 200; param c: 1 2 3 4 5 := 1 0.0 0.4 0.8 0.4 0.8 2 0.7 0.0 0.8 0.4 0.4 3 0.6 0.4 0.0 0.5 0.4 4 0.6 0.4 0.9 0.0 0.4 5 0.9 0.4 0.7 0.4 0.0 ; 2-40 . (a) 8 max ∑ j =1 r j x j , subject to, ∑ 8 j =1 x j ≤ 4, x 1 + x 2 + x 3 ≥ 2 , x 4 + x 5 + x 6 + x 7 + x 8 ≥ 1 , x 2 + x 3 + x 4 + x 8 ≥ 2, x 1 . . . x 8 = 0 or 1 (b) model; param n ; set games := 1 .. n ; #ratings param r { j in games } ; #home? param h { j in games } ; #state? param s { j in games } ; #cover? var x { j in games } binary; maximize totrat: sum { j in games } r[j]*x[j]; subject to capacity: sum { j in games } x[j] <= 4; home: sum { j in games } h[j]*x[j] >= 2; away: sum { j in games } (1-h[j])* x[j] >= 1; state: sum { j in games } s[j]*x[j] >= 2; data; param n := 8; param r :=1 3.0 2 3.7 3 2.6 4 1.8 5 1.5 6 1.3 7 1.6 8 2.0; param h:=1 1 2 1 3 1 4 0 5 0 6 0 7 0 8 0; param s:=1 0 2 1 3 1 4 1 5 0 6 0 7 0 8 1; (c) The model is an ILP because all constraints and the objective are linear, but decision variables are binary. 2-41 . (a) How to divide funds is the issue. (b) max ∑ n j =1 v j x j (c) min ∑ n j =1 r j x j (d) ∑ n j =1 x j = 1 (e) x j ≥ ℓ j , j = 1 , . . . , n (each category j )

  12. Page 12
    Read page 12 as text

    10 (f ) x j ≤ u j , j = 1 , . . . , n (each category j ) (g) A multiobjective LP because the 2 objectives and all constraints are linear, and all variables are continuous. 2-42 . (a) The issue is which module goes to which site. (b) If x i,j x i ′ ,j ′ = 1 the i is at j and i ′ is at j ′ , so wire d j,j ′ will be required. Summing over all possible location pairs captures the wire requirements for i and i ′ . (c) min ∑ m − 1 i =1 ∑ m n n i = i +1 a d ′ i,i ′ ∑ j =1 ∑ j ′ =1 j,j ′ x i,j x i ′ ,j ′ (d) n ∑ j =1 x i,j = 1 , i = 1 , . . . , m (each module i ) (e) ∑ m i =1 x i,j ≤ 1 , j = 1 , . . . , n (each site j ) (f ) x i,j = 0 or 1, i = 1 , . . . , m , j = 1 , . . . , n (g) Single objective INLP because the one objective is nonlinear and variables are discrete. (h) model; param m; param n; set modules := 1 .. m; set sites := 1 .. n; var x { i in modules, j in sites } binary; param a { i in modules, ip in modules } ; param d { j in sites, jp in sites } ; minimize totdist: sum { i in modules, ip in modules: i < m and ip > i } a[i,ip] sum { j in sites, jp in sites : j < n and jp > j } d[j,jp]*x[i,j]*x[ip,jp]; subject to alli { i in modules } : sum { j in sites } x[i,j] = 1; allj { j in sites } : sum { i in modules } x[i,j] <= 1; 2-43 . max 199 x 1 + 229 x 2 + 188 x 3 + 205 x 4 − 180 y 1 − 224 y 2 − 497 y 3 , subject to, 23 x 3 + 41 x 4 ≤ 2877 y 1 , 14 x 1 + 29 x 2 ≤ 2333 y 2 , 11 x 3 + 27 x 4 ≤ 3011 y 3 , x 1 + x 2 + x 3 + x 4 ≥ 205, y 1 + y 2 + y 3 ≤ 2, x 1 , . . . , x 4 ≥ 0, y 1 , . . . , y 3 = 0 or 1 2-44 . max 11 x 1 , 1 + 15 x 1 , 2 + 19 x 1 , 3 + 10 x 1 , 4 + 19 x 2 , 1 + 23 x 2 , 2 + 44 x 2 , 3 + 67 x 2 , 4 + 17 x 3 , 1 + 18 x 3 , 2 + 24 x 3 , 3 + 55 x 3 , 4 , subject to, 15 x 1 , 1 + 24 x 2 , 1 + 17 x 3 , 1 ≤ 7600, 19 x 1 , 2 + 26 x 2 , 2 + 13 x 3 , 2 ≤ 8200, 23 x 1 , 3 + 18 x 2 , 3 + 16 x 3 , 3 ≤ 6015, 14 x 1 , 4 +33 x 2 , 4 +14 x 3 , 4 ≤ 5000, 31 x 1 , 1 +26 x 2 , 1 + 21 x 3 , 1 ≤ 6600, 25 x 1 , 2 + 28 x 2 , 2 + 17 x 3 , 2 ≤ 7900, 39 x 1 , 3 + 22 x 2 , 3 + 20 x 3 , 2 ≤ 5055, 29 x 1 , 4 + 31 x 2 , 4 + 18 x 3 , 4 ≤ 7777, x 1 , 1 + x 2 , 1 + x 3 , 1 ≥ 200, x 1 , 2 + x 2 , 2 + x 3 , 2 ≥ 300, x 1 , 3 + x 2 , 3 + x 3 , 3 ≥ 250, x 1 , 4 + x 2 , 4 + x 3 , 4 ≥ 500, x j,t ≥ 0 , j = 1 , . . . 3 , t = 1 , . . . 4.

  13. Page 13
    Read page 13 as text

    1 Chapter 3 Solutions 1 2 1 S upplement to the 2nd edition of Optimization in Operations Research , by Ronald L. Rardin, Pearson Higher Education, Hoboken NJ, c 2017. ○ 2 As of October 1, 2015 3-1 . (a) x (1) is feasible and only a local max because all constraints are satisfied and no nearby point has better objective value, but there are better such as (1 , 3). x (2) is infeasible and thus no sort of optimum because it violates constraint x 2 ≥ 0 . x (3) is feasible because it satisfies all constraints, but no sort of optimum because it can be improved in the neighborhood. x (4) is feasible and both a local and a global max because it satisfies all constraints and has better objective value than any other point in the feasible region. (b) x (1) is infeasible and thus no sort of optimum because it violates constraint x 1 + x 2 ≤ 4 . x (2) is feasible because it satisfies all constraints, but no kind of optimum because it can be improved in a variety of directions. x (3) is feasible and a local minimum because it cannot be improved in the neighborhood, but not global because other feasible points such as x (4) have better objective values. x (4) is feasible and both a local and a global minimum because it satisfies all constraints and has better objective value than any other point in the feasible region. 3-2 . (a) y (1) = (2 , 0 , 5) + 2(3 , 1 , 0) = (8 , 2 , 5), − − y (2) = (8 , − 2 , 5) + 5( − 1 , 2 , 1) = (3 , 8 , 10), (3) y = (3 , 8 , 10) + 1 / 2(0 , 6 , 0) = (3 , 11 , 10) (b) y (1) = (2 , 0 , 5) + 2(1 , 3 , − 2) = (4 , 6 , 1), y (2) = (4 , 6 , 1) + 1 / 2(1 , 0 , 2) = (4 1 / 2 , 6 , 2), y (3) = (4 1 / 2 , 6 , 2) + 12(4 , 3 , 2) = (52 1 / 2 , 42 , 26) 3-3 . (a) Δw (1) = (4 , − 1 , 7) − (0 , 1 , 1) = (4 , − 2 , 6), Δw (2) = (4 , − 3 , 19) − (4 , − 1 , 7) = (0 , − 2 , 8), (3) Δw = (3 , − 3 , 22) − (4 , − 3 , 19) = ( − 1 , 0 , 3) (b) Δw (1) = (4 , 2 , 10) − (4 , 0 , 7) = (0 , 2 , 3), Δw (2) = ( 2 , 4 , 5) (4 , 2 , 10) = ( 6 , 2 , 5), − − − Δw (3) = (5 , 5 , 5) ( 2 , 4 , 5) = (7 , 1 , 0) − − 3-4 . (a) Nonimproving because the objective value worsens in the neighborhood along this direction. (b) Nonimproving because the objective decreases in the neighborhood along this direction. (c) Improving because the objective improves in the neighborhood along this direction. (d) Improving because the objective improves in the neighborhood along this direction. (e) Nonimproving because x (3) is a local minimum. (f ) Improving because the objective value improves in the neighborhood along this direction. 3-5 . (a) Feasible because movement along this direction retains feasibility in the neighborhood. (b) Infeasible because any movement along this direction produces infeasibility. (c) Feasible because movement along this direction retains feasibility in the neighborhood. (d) Feasible because movement along this direction retains equality of the only active constraint. (e) Feasible because any movement along this direction violates no constraints immediately. (f ) Infeasible because movement along this direction immediately violates x 2 ≥ 0 . 3-6 . (a) (4 − 1 λ ) − 2(0 + 3 λ ) + 3(6 − 2 λ ) ≤ 25 is satisfied for all positive λ ; (4 − 1 λ ) ≥ 0 is satisfied for λ ≤ 4 ; (0 + 3 λ ) ≥ 0 is satisfied for all positive λ ; (6 − 3 λ ) ≥ 0 is satisfied for λ ≤ 3 . Thus the proper step is λ = m in 4 , 3 = 3 { } . The model is not unbounded because this λ is finite. (b) (8 − 2 λ ) − 2(5 + 1 λ ) + 3(3 − 1 λ ) ≤ 25 is satisfied for all positive λ ; (8 − 2 λ ) ≥ 0 is satisfied for λ ≤ 4 ; (5 + 1 λ ) ≥ 0 is satisfied for all positive λ ; (3 − 1 λ ) ≥ 0 is satisfied for λ ≤ 3. Thus the proper step is λ = min { 4 , 3 } = 3. The model is not unbounded because this λ is finite. (c) (0 + 1 λ ) − 2(0 + 3 λ ) + 3(4 + 1 λ ) ≤ 25 is satisfied for all positive λ ; (0 + 1 λ ) ≥ 0 is satisfied for all positive λ ; (0 + 3 λ ) ≥ 0 is

  14. Page 14
    Read page 14 as text

    2 satisfied for all positive λ ; (4 + 1 λ ) ≥ 0 is satisfied for all positive λ . Thus λ = + ∞ , and the model is unbounded. (d) (20 + 2 λ ) − 2(4 + 7 λ ) + 3(3 + 4 λ ) ≤ 25 is satisfied for all positive λ ; (20 + 2 λ ) ≥ 0 is satisfied for all positive λ ; (4 + 7 λ ) ≥ 0 is satisfied for all positive λ ; (3 + 4 λ ) ≥ 0 is satisfied for all positive λ . Thus the model is unbounded because steps in this direction can be arbitrarily large without losing feasibility. 3-7 . (a) ∇ f (2 , − 3 , 4 , 0 , 6) = (4 , 0 , − 2 , 0 , 1) and ∇ f · Δy = (4 , 0 , − 2 , 0 , 1) · (2 , − 3 , 4 , 0 , 6) = 6, so improving for a maximize. (b) ∇ f (1 , 0 , 9 , 0 , 0) = (1 , 0 , 7 , 0 , 2) and ∇ f · Δy = (1 , 0 , 7 , 0 , 2) · ( − 1 − , − 20 , 2 , 0 , 4) = 7 > 0 , so improving for a maximize. (c) ∇ f (3 , − 1) = ( − 1 + 2(3) , 3 + 4) and ∇ f · Δy = (5 , 7) · ( − 7 , 5) = 0, so more information is needed. (d) ∇ f (2 , 1) = (2(2) + 1 , 2 + 4) and ∇ f · Δy = (5 , 6) · ( − 1 , 3) = 13 < 0, so nonimproving for a minimize. (e) ∇ f (4 , 1) = (2(4 − 5) , 2(1 + 1)) and ∇ f · Δy = ( − 2 , 4) · ( − 1 , 2) = 12 > 0, so improving for a maximize. (f ) ∇ f (1 , 1) = (2(1 − 2) + 1 , 1 + 2(1 − 3)) and ∇ f · Δy = ( − 1 , − 3) · (3 , − 1) = 0, so more information is needed. 3-8 . (a) Δw = ∇ f (2 , 0 , 5 , 1) = (3 , − 2 , 0 , 1) (b) Δw = − ∇ f (2 , 2 , 1 , 0) = (0 , 4 , − 5 , 1) (c) Δw = − ∇ f (3 , 2) = − (2(3 + 2) − 2 , − 3) = ( − 8 , 3) (d) Δw = ∇ f (11 , 2) = ( − 4 , 9 + 4(2)) = ( − 4 , 17) 3-9 . (a) 2 (4 − 2) + (0 − 1) 2 = 5 < 10 so [i] is inactive; 2(4) − (0) = 8 so [ii] is active; (4) > 0 so [iii] is inactive; (0) = 0 so [iv] is active. (b) (6 − 2) 2 + (4 − 1) 2 = 25 so [i] is active; 2(6) − (4) = 8 so [ii] is active; (6) > 0 so [iii] inactive; (4) > 0 so [iv] inactive. 3-10 . (a) Active constraints are 3 y 1 2 y 2 + 8 y 3 = 14 and y 2 0. − ≥ For these a (1) · Δy = 3 , − 2 , 8) · (0 , 4 , 1) = 0 and a (4) · Δy = 0 , 1 , 0) · (0 , 4 , 1) = 4 ≥ 0 as / required for feasibility. (b) Active constraints are 3 y 1 − 2 y 2 + 8 y 3 = 14 and y 2 ≥ 0. For these ) a (1 · Δy = (3 , − 2 , 8) · (0 , − 4 , 1) = 16 , infeasible for an = constraint. a (4) · Δy = (0 , 1 , 0) · (0 , − 4 , 1) = − 4 ≥ 0 infeasible for a ≥ constraint. (c) Active constraints are 3 y 1 − 2 y 2 + 8 y 3 = , 14 and y 1 ≥ 0 . In the first a (1) · Δy = (3 , − 2 , 8) · (2 , 0 , 1) = 14 = 0 as required so infeasible. (d) Active constraints are 3 y 1 − 2 y 2 + 8 y 3 = 14 and y 1 ≥ 0. For these a (1) · Δy = (3 , − 2 , 8) · ( − 2 , 1 , 1) = 0 as required for feasibility of an = constraint. a (3) · Δy = (1 , 0 , 0) · ( − 2 , 1 , 1) = − 2 infeasible fore a ≥ 0 constraint. / 3-11 . (a) Active constraints are 2 w 1 + 3 w 3 = 18, 1 w 1 + 1 w 2 + 2 w 3 = 14, and w 1 ≥ 0. Thus conditions are 2 Δ w 1 + 3 Δ w 3 = 0 , 1 Δ w 1 + 1 Δ w 2 + 2 Δ w 3 = 0, Δ w 1 ≥ 0 (b) Active constraints are 2 w 1 + 3 w 3 = 18 ,and 1 w 1 + 1 w 2 + 2 w 3 = 14. Thus conditions are 2 Δ w 1 + 3 Δ w 3 = 0, 1 Δ w 1 + 1 Δ w 2 + 2 Δ w 3 = 0, (c) Active constraints are 1 w 1 + 1 w 2 = 10 and 2 w 1 − 1 w 2 ≥ 8. Thus conditions are 1 Δ w 1 + 1 Δ w 2 = 0, 2 Δ w 1 − 1 Δ w 2 ≥ 0 (d) Only active constraint is 1 w 1 + 1 w 2 = 10. Thus conditions are 1 Δ w 1 + 1 Δ w 2 = 0, 3-12 . (a) − 1 Δ y 1 + 5 Δ y 2 < 0 (b) Direct substitution (c) Active constraints are y 1 ≥ 0 and − y 1 + y 2 ≤ 3. (d) Active constraints yield conditions 1 Δ y 1 + 0 Δ y 2 ≥ 0, − 1 Δ y 1 + 1 Δ y 2 ≤ 0. (e) Direct supstitution shows direction is feasible. Maximum step is λ = 1 where constraint y 2 ≥ 0 is encountered.

  15. Page 15
    Read page 15 as text

    3 (f ) 3-13 . (a) 3 Δ x 1 − 13 Δ x 3 < 0 (b) 3( − 1) − 13(2) = − 16 < 0 as required. (c) Only first constraint with 11(3) + 4(9) = 69, and fourth constraint x 2 = 0 are active at (3 , 0 , 9). (d) 11 Δ x 1 + 3 Δ x 2 + 4 Δ x 3 = 0 and Δ x 2 ≥ 0. (e) Direct substitution; Checking limits on λ , (3 − 1 λ ) + (0 + 1 λ ) + (9 + 2 λ ) ≤ 16 gives λ ≤ 2, 3 − 1 λ ≥ 0 gives λ ≤ 3. Combining λ ← min { 2 , 3 } = 2. Then x (2) ← (3 − 2 , 0 + 2 , 9 + 4) = (1 , 2 , 13) 3-14 . (a) ∇ f · Δz (1) = (4 , 7) · (2 , 0) = 8 > 0 and ∇ f · Δz (2) = (4 , 7) · ( − 2 , 4) = 20 > 0 as required for improving directions in a maximize. (b) With both directions improving at all z , the only considerations are when directions are feasible. At z (0) = (0 , 0) , only Δz (1) is feasible because Δz (2) has a · Δz (2) = (1 , 0) · ( − 2 , 4) = − 2 / ≥ 0 for active z 1 ≥ 0. A maximum feasible step follows ( Δz 1) for λ = 2 to z (1) = (4 , 0) . At z (1) = (4 , 0) , further pursuit of Δz (1) is infeasible, but Δz (2) = ( − 2 , 4) is feasible. A maximum feasible step follows Δz (2) for λ = 3 / 4 to z (2) = (5 / 2 , 3) . At z (2) = (5 / 2 , 3) , further pursuit of Δz (2) is infeasible, but Δz (1) = (2 , 0) is again feasible. A maximum feasible step follows Δz (1) for λ = 1 / 4 to z (3) = (3 , 3). At z (3) , both directions are infeasible, and the search terminates. (c) z 1 z 2 1 2 3 1 2 3 2 z ≥ 0 1 z ≥ 0 2 z ≤ 4 1 2 2 z + z ≤ 9 z = (0,0) (0) z = (4,0) (1) z = (5/2,3) (2) z = (3,3) (3) 1 z ≤ 4 max 3-15 . (a) ∇ f · Δz (1) = (1 , 1) (0 , − 5) = − 5 < 0 · and ( ∇ f · Δz 2) = (1 , 1) · ( 2 , 1) = − 2 < − 0 as required for a minimize. (b) With both directions improving at all z , the only considerations are when directions are feasible. At z (0) = (5 , 3) , only Δz (1) is feasible because Δz (2) has a · Δz (2) = (0 , 1) · ( − 2 , 1) = 1 / ≤ 0 for active z 2 ≤ 3 . A maximum feasible step follows Δz (1) for λ = 3 / 5 to z (1) = (5 , 0) . At z (1) = (5 , 0) , further pursuit of Δz (1) is infeasible, but Δz (2) = ( − 2 , 1) is now feasible. A maximum feasible step follows Δz (2) for λ = 5 / 2 to z (2) = (0 , 5 / 2) . At z (2) = (0 , 5 / 2) , further pursuit of Δz (2) is infeasible, but Δz (1) = (0 , − 5 is again feasible. A maximum feasible step follows Δz (1) for λ = 1 / 10 to z (3) = (0 , 2) . At z (3) , both directions are infeasible, and the search terminates. (c) 1 2 3 1 2 3 4 5 z 2 1 z 1 2 z + z ≥ 4 2 z ≥ 0 1 z ≥ 0 1 z ≤ 5 2 z ≤ 3 z = (5,0) (1) z = (0,5/2) (2) z = (0,2) (3) z = (5,3) (0) min 3-16 . (a) (3 , 1 , 0) + λ ( − 3 , 3 , 9), λ ∈ [0 , 1] . Setting λ = 1 / 3 in this expression yields z (3) ; no λ gives z (4) . (b) (6 , 4 , 4) + λ (4 , − 4 , 3) , λ ∈ [0 , 1] . Setting λ = 3 / 4 in this expression yields z (3) ; no λ gives z (4) . 3-17 .

  16. Page 16
    Read page 16 as text

    4 (a) x 1 x 2 2 4 2 4 1 x ≥ 0 2 x ≥ 0 6 8 10 6 8 violation x + x ≤ 10 1 2 1 2 ( x ) + ( x ) ≥ 9 2 2 From the graph, the set is not convex because part of the line segment from x (1) = (0 , 3) to x (2) = (3 , 0) lies outside the feasible region. (b) From the graph, the set is convex because the line segment between every pair of feasible solutions lies entirely within the feasible region. (c) Convex because all constraints are linear. (d) Convex because all constraints are linear. (e) Not convex because fractional solutions between say x (1) = (0 , 0 , 0 , 4) and x (2) = (0 , 0 , 0 , 5) are infeasible. (f ) Not convex because fractional solutions between the all x j = 1 and all x j = 0 solutions are infeasible. 3-18 . (a) Only the first and third constraints are violated at w = 0 . Adding nonnegative artificial variables w 4 in the first and w 5 in the third, and minimizing their sum, produces Phase I model: min w 4 + w 5 , s.t. 40 w 1 + 30 w 2 + 10 w 3 + w 4 = 150 , w 1 − w 2 ≤ 0, 4 w 2 + w 3 + w 5 ≥ 10 , w 1 , w 2 , w 3 , w 4 , w 5 ≥ 0 . Setting w 4 = 150 − 40(0) − 30(0) − 10(0) = 150 and w 5 = 10 − 4(0) − (0) = 10 (or any higher value) completes a starting (artificially) feasible solution. (b) Only the second and third constraints are violated at w = 0 . Adding nonnegative artificial variable w 3 in the second, and w 4 in the third, then minimizing their sum, produces Phase I model: min w 3 + w 4 , s.t. − w 1 + w 2 ≤ 3, w 2 + w 3 ≥ 2, w 2 + w 4 ≥ w 1 + 1 , w 1 , w 2 , w 3 , w 4 ≥ 0 . Setting w 3 = 2 and w 4 = 1 (or any higher values), completes a starting (artificially) feasible solution.

170 more pages in the full document

Unlock it once and it stays in your library, ready to chat with or turn into flashcards.

Unlock the full document

More Mathematics study materials

See all

Study this document with CramX

Once it is in your library, every tool can work from it.