Introduction to Management Science, 11e (Taylor) Chapter 2Linear Programming: Model Formulation and Graphical Solution 1) Linear programming is a model consisting of linear relationships representing a firm's decisions given an objective and resource constraints. Answer:TR! "iff: # $age Ref: %1 &ection 'eading:(odel )ormulation *e+words:model formulation AA,&-:Anal+tic s.ills #) The objective function alwa+s consists of either ma/imi0ing or minimi0ing some value. Answer:TR! "iff: # $age Ref: %1 &ection 'eading:(odel )ormulation *e+words:objective function AA,&-:Anal+tic s.ills %) The objective function is a linear relationship reflecting the objective of an operation. Answer:TR! "iff: 1 $age Ref: %1 &ection 'eading:(odel )ormulation *e+words:model formulation AA,&-:Anal+tic s.ills 1) A constraint is a linear relationship representing a restriction on decision ma.ing. Answer:TR! "iff: 1 $age Ref: %1 &ection 'eading:(odel )ormulation *e+words:model formulation AA,&-:Anal+tic s.ills 2) A linear programming model consists of onl+ decision variables and constraints. Answer:)AL&! "iff: 1 $age Ref: 23 &ection 'eading:,haracteristics of Linear $rogramming $roblems *e+words:model formulation AA,&-:Anal+tic s.ills 3) A parameter is a numerical value in the objective function and constraints. Answer:TR! "iff: 1 $age Ref: %1 &ection 'eading:(odel )ormulation *e+words:parameter AA,&-:Anal+tic s.ills 1 ,op+right 4 #51% $earson 'igher !ducation6 7nc. $ublishing as $rentice 'all 8) A feasible solution violates at least one of the constraints. Answer:)AL&! "iff: # $age Ref: %1 &ection 'eading:(odel )ormulation *e+words:model formulation AA,&-:Anal+tic s.ills 9) $roportionalit+ means the slope of a constraint is proportional to the slope of the objective function. Answer:)AL&! "iff: # $age Ref: 23 &ection 'eading:,haracteristics of Linear $rogramming $roblems *e+words:properties of linear programming models6 proportionalit+ AA,&-:Anal+tic s.ills :) The terms in the objective function or constraints are additive. Answer:TR! "iff: # $age Ref: 23 &ection 'eading:,haracteristics of Linear $rogramming $roblems *e+words:properties of linear programming models6 additive AA,&-:Anal+tic s.ills 15) The terms in the objective function or constraints are multiplicative. Answer:)AL&! "iff: # $age Ref: 23 &ection 'eading:,haracteristics of Linear $rogramming $roblems *e+words:properties of linear programming models6 additive AA,&-:Anal+tic s.ills 11) The values of decision variables are continuous or divisible. Answer:TR! "iff: # $age Ref: 23 &ection 'eading:,haracteristics of Linear $rogramming $roblems *e+words:properties of linear programming models6 divisible AA,&-:Anal+tic s.ills 1#) All model parameters are assumed to be .nown with certaint+. Answer:TR! "iff: # $age Ref: 23 &ection 'eading:,haracteristics of Linear $rogramming $roblems *e+words:properties of linear programming models AA,&-:Anal+tic s.ills 1%) 7n linear programming models 6 objective functions can onl+ be ma/imi0ed. Answer:)AL&! "iff: 1 $age Ref: %1 &ection 'eading:(odel )ormulation *e+words:properties of linear programming models6 objective function AA,&-:Anal+tic s.ills # ,op+right 4 #51% $earson 'igher !ducation6 7nc. $ublishing as $rentice 'all 11) All linear programming models e/hibit a set of constraints. Answer:TR! "iff: 1 $age Ref: %5 &ection 'eading:(odel )ormulation *e+words:properties of linear programming models6 constraints AA,&-:Anal+tic s.ills 12) ;hen using the graphical method6 onl+ one of the four raphical &olutions of Linear $rogramming (odels *e+words:properties of linear programming models6 feasible solution area AA,&-:Anal+tic s.ills % ,op+right 4 #51% $earson 'igher !ducation6 7nc. $ublishing as $rentice 'all #1) There is e/actl+ one optimal solution point to a linear program. Answer:)AL&! "iff: # $age Ref: 2% &ection 'eading:7rregular T+pes of Linear $rogramming $roblems *e+words:properties of linear programming models6 optimal solution pt AA,&-:Anal+tic s.ills ##) The following eraphical &olutions of Linear $rogramming (odels *e+words:graphical solution6 objective function line AA,&-:Anal+tic s.ills %1) The first step in formulating a linear programming model is to define the objective function Answer:)AL&! "iff: # $age Ref: %# &ection 'eading:7ntroduction *e+words:linear programming problems6 formulation AA,&-:Anal+tic s.ills %#) EEEEEEEE are mathematical s+mbols representing levels of activit+. Answer:"ecision variables "iff: 1 $age Ref: %1 &ection 'eading:(odel )ormulation *e+words:decision variables6 model formulation AA,&-:Anal+tic s.ills %%) The EEEEEEEE is a linear relationship reflecting the objective of an operation. Answer:objective function "iff: 1 $age Ref: %1 &ection 'eading:(odel )ormulation *e+words:objective function6 model formulation AA,&-:Anal+tic s.ills 2 ,op+right 4 #51% $earson 'igher !ducation6 7nc. $ublishing as $rentice 'all %1) A EEEEEEEE is a linear relationship representing a restriction on decision ma.ing. Answer:constraint "iff: 1 $age Ref: %1 &ection 'eading:(odel )ormulation *e+words:constraint6 model formulation AA,&-:Anal+tic s.ills %2) A manufacturer using linear programming to decide the best product mi/ to ma/imi0e profit t+picall+ has aFn) EEEEEEEE constraint included in the model. Answer:nonnegativit+ "iff: 1 $age Ref: %1 &ection 'eading:A (a/imi0ation (odel !/ample *e+words:nonnegativit+ AA,&-:Anal+tic s.ills %3) 7f at least one constraint in a linear programming model is violated6 the solution is said to be EEEEEEEE. Answer:infeasible "iff: 1 $age Ref: 21 &ection 'eading:7rregular T+pes of Linear $rogramming $roblems *e+words:constraint6 infeasible solution AA,&-:Anal+tic s.ills %8) A graphical solution is limited to solving linear programming problems with EEEEEEEE decision variables Answer:two "iff: 1 $age Ref: %2 &ection 'eading:>raphical &olutions of Linear $rogramming (odels *e+words:graphical solution AA,&-:Anal+tic s.ills %9) The EEEEEEEE solution area is an area bounded b+ the constraint eraphical &olutions of Linear $rogramming (odels *e+words:graphical solution6 surplus variable AA,&-:Anal+tic s.ills 11) EEEEEEEE is the difference between the left= and right=hand sides of a greater than or eraphical &olutions of Linear $rogramming (odels *e+words:feasibilit+6 constraints AA,&-:Anal+tic s.ills 18) EEEEEEEE are at the endpoints of the constraint line segment that the objective function parallels. Answer:Alternate optimal solutions "iff: % $age Ref: 21 &ection 'eading:7rregular T+pes of Linear $rogramming $roblems *e+words:alternative optimal solutions6 multiple optimal solutions AA,&-:Anal+tic s.ills 19) The EEEEEEEE step in formulating a linear programming model is to define the decision variables. Answer:first "iff: 1 $age Ref: %% &ection 'eading:A (a/imi0ation (odel !/ample *e+words:linear programming6 formulation AA,&-:Anal+tic s.ills 1:) The management scientist constructed a linear program to help the alchemist ma/imi0e his gold production process. The computer model chugged awa+ for a few minutes and returned an answer of infinite profit.6 which is what might be e/pected from aFn) EEEEEEEE problem. Answer:unbounded "iff: 1 $age Ref: 22 &ection 'eading:7rregular T+pes of Linear $rogramming $roblems *e+words:unbounded AA,&-:Anal+tic s.ills 25) The EEEEEEEE propert+ of linear programming models indicates that the values of all the model parameters are .nown and are assumed to be constant. Answer:certaint+ "iff: # $age Ref: 23 &ection 'eading:,haracteristics of Linear $rogramming $roblems *e+words:properties of linear programming models6 certaint+ AA,&-:Anal+tic s.ills 21) The EEEEEEEE propert+ of linear programming models indicates that the rate of change6 or slope6 of the objective function or a constraint is constant. Answer:proportionalit+ or linearit+ "iff: # $age Ref: 23 &ection 'eading:,haracteristics of Linear $rogramming $roblems *e+words:properties of linear programming models6 certaint+ AA,&-:Anal+tic s.ills 9 ,op+right 4 #51% $earson 'igher !ducation6 7nc. $ublishing as $rentice 'all 2#) The EEEEEEEE propert+ of linear programming models indicates that the decision variables cannot be restricted to integer values and can ta.e on an+ fractional value. Answer:divisibilit+ "iff: # $age Ref: 23 &ection 'eading:,haracteristics of Linear $rogramming $roblems *e+words:properties of linear programming models6 divisibilit+ AA,&-:Anal+tic s.ills 2%) The constraint #A BAC violates the EEEEEEEE propert+ of linear programming. Answer:proportionalit+ or linear "iff: 1 $age Ref: 23 &ection 'eading:,haracteristics of Linear $rogramming $roblems *e+words:properties of linear programming models AA,&-:Anal+tic s.ills 21) ,onsider the following minimi0ation problem: (in 0 ?x 1 B #x # s.t.x 1 B x # D %55 #x 1 B x # D 155 #x 1 B 2x # G 825 x 1 6 x # D 5 ;hat is the optimal solutionH Answer:/ 1 ? #256 / # ? 256 0 ? %25 "iff: % $age Ref: 18=2% &ection 'eading:A (inimi0ation (odel !/ample *e+words:>raphical solution6 simultaneous solution AA,&-:Anal+tic s.ills 22) ,onsider the following minimi0ation problem: (in 0 ?x 1 B #x # s.t.x 1 B x # D %55 #x 1 B x # D 155 #x 1 B 2x # G 825 x 1 6 x # D 5 ;hich constraints are binding at the optimal solutionH Fx 1 ?#256 x # ? 25) Answer:constraints 1 and % "iff: 1 $age Ref: 18=2% &ection 'eading:A (inimi0ation (odel !/ample *e+words:>raphical solution6 simultaneous solution AA,&-:Anal+tic s.ills : ,op+right 4 #51% $earson 'igher !ducation6 7nc. $ublishing as $rentice 'all 23) &olve the following graphicall+: (a/ z ?%x 1 B 1x # s.t.x 1 B #x # G 13 #x 1 B %x # G 19 x 1 D # x # G 15 x 1 6 x # D 5 ;hat are the optimal values of x 1 6 x # 6 and zH Answer:x 1 ? :6 x # ? 56 z ? #8 "iff: % $age Ref: %2=13 &ection 'eading:>raphical &olutions of Linear $rogramming (odels *e+words:graphical solution6 simultaneous solution AA,&-:Anal+tic s.ills 15 ,op+right 4 #51% $earson 'igher !ducation6 7nc. $ublishing as $rentice 'all 28) ,onsider the following linear program: (AAI ? 35A B 25- s.t.15A B #5- G #55 9A B 2- G 95 A D # - D 2 &olve this linear program graphicall+ and determine the optimal raphical &olutions of Linear $rogramming (odels *e+words:graphical solution6 e/treme points6 feasible region AA,&-:Anal+tic s.ills 35) A graphical representation of a linear program is shown below. The shaded area represents the feasible region6 and the dashed line in the middle is the slope of the objective function. 7f this is a minimi0ation6 which e/treme point is the optimal solutionH Answer:A "iff: # $age Ref: 11 &ection 'eading:>raphical &olutions of Linear $rogramming (odels *e+words:graphical solution6 e/treme points6 feasible region AA,&-:Anal+tic s.ills 1% ,op+right 4 #51% $earson 'igher !ducation6 7nc. $ublishing as $rentice 'all 31) A graphical representation of a linear program is shown below. The shaded area represents the feasible region6 and the dashed line in the middle is the slope of the objective function. ;hat would the be the new slope of the objective function if multiple optimal solutions occurred along line segment A-H Answer:=%K# "iff: # $age Ref: 11 &ection 'eading:7rregular T+pes of Linear $rogramming $roblems *e+words:graphical solution6 multiple optimal solutions AA,&-:Anal+tic s.ills 3#) ,onsider the following linear programming problem: (a/ I ?L12x B L#5y &ubject to:9x B 2y G 15 5.1x B y D 1 x6 y D 5 "etermine the values for / and + that will ma/imi0e revenue. >iven this optimal revenue6 what is the amount of slac. associated with the first constraintH Answer:x ? 56 y ? 96 revenue ? L1356 s 1 ? 5 "iff: # $age Ref: 11 &ection 'eading:>raphical &olutions of Linear $rogramming (odels *e+words:graphical solution6 slac. variables AA,&-:Anal+tic s.ills 11 ,op+right 4 #51% $earson 'igher !ducation6 7nc. $ublishing as $rentice 'all 3%) ,onsider the following linear programming problem: (a/ I ?L%x B L:y &ubject to:#5x B %#y G 1355 1x B #y G #15 y G 15 x6 y D 5 &olve for the raphical &olutions of Linear $rogramming (odels *e+words:minimi0ation problem AA,&-:Anal+tic s.ills 13 ,op+right 4 #51% $earson 'igher !ducation6 7nc. $ublishing as $rentice 'all 3:) ,onsider the following linear programming problem: (7J I ?%x 1 B #x # &ubject to:#x 1 B %x # D 1# 2x 1 B 9x # D %8 x 1 6 x # D 5 At the optimal solution point6 the objective function value is 19. 7f the constraints are changed from greater than to less than constraints and the objective function is changed from minimi0e to ma/imi0e6 what happens to the optimal solutionH "emonstrate whether it falls at the same optimal point. Answer:Jo6 reversing the signs for the constraints and the objective function does not t+picall+ retain the same optimal solution. 7n this case6 at x # ? 1.3#2 the new objective function value is :.#2. 7n the original formulation the optimal value was at x 1 ? 3. "iff: % $age Ref: 1# &ection 'eading:A (inimi0ation (odel !/ample *e+words:optimal solutions AA,&-:Anal+tic s.ills 85) ,onsider the following linear programming problem: (7J I ?15x 1 B #5x # &ubject to:x 1 B x # D 1# #x 1 B 2x # D 15 x # G 1% x 1 6 x # D 5 At the optimal solution6 what is the value of surplus associated with constraint 1 and constraint %6 respectivel+H Answer:constraint 1: F5 surplus)6 constraint #: F8.338 surplus) "iff: # $age Ref: 18=2% &ection 'eading:A (inimi0ation (odel !/ample *e+words:graphical solution AA,&-:Anal+tic s.ills 81) >iven this set of constraints6 for what objective function is the point /?26 +?% in the feasible regionH s.t%x B 3y G %5 15x B 15y G 35 15x B 12y G :5 Answer:Jo objective function can move that point into the feasible region. "iff: # $age Ref: 15 &ection 'eading:>raphical &olutions of Linear $rogramming (odels *e+words:feasibilit+6 constraints AA,&-:Anal+tic s.ills 18 ,op+right 4 #51% $earson 'igher !ducation6 7nc. $ublishing as $rentice 'all 8#) ,onsider the following linear programming problem: (7J I ?#x 1 B %x # &ubject to:x 1 B #x # G #5 2x 1 B x # G 15 1x 1 B3x # G 35 x 1 6 x # D 5 ;hat is the optimal solutionH Answer:(ultiple optimal solutions e/ist between the e/treme point F5615) and F3.:#62.%9) along the line with a slope of =#K%. "iff: # $age Ref: 18=2% &ection 'eading:A (inimi0ation (odel !/ample *e+words:graphical solution6 multiple optimal solutions AA,&-:Anal+tic s.ills 8%) A compan+ producing a standard line and a delu/e line of dishwashers has the following time reraphical &olutions of Linear $rogramming (odels *e+words:optimal solution6 solution interpretation6 slope AA,&-:Anal+tic s.ills 83) "ecision variables A) measure the objective function. -) measure how much or how man+ items to produce6 purchase6 hire6 etc. ,) alwa+s e/ist for each constraint. ") measure the values of each constraint. Answer:- "iff: # $age Ref: %1 &ection 'eading:(odel )ormulation *e+words:decision variables AA,&-:Anal+tic s.ills 88) 7n a linear programming problem6 a valid objective function can be represented as: A) (a/ I ? 2/+ -) (a/ I 2x # B #y # ,) (a/ %x B %y B 1K% z ") (in Fx 1 B x # ) K x % Answer:, "iff: % $age Ref: 23 &ection 'eading:,haracteristics of Linear $rogramming $roblems *e+words:objective function AA,&-:Anal+tic s.ills 1: ,op+right 4 #51% $earson 'igher !ducation6 7nc. $ublishing as $rentice 'all 89) ;hich of the following could not be a linear programming problem constraintH A) 1A B #- M % -) 1A B #- ? % ,) 1A B #- G % ") 1A B #- D % Answer:A "iff: # $age Ref: %% &ection 'eading:A (a/imi0ation (odel !/ample *e+words:formulation6 constraints AA,&-:Anal+tic s.ills 8:) A linear programming model consists of A) decision variables. -) an objective function. ,) constraints. ") all of the above Answer:" "iff: 1 $age Ref: %1 &ection 'eading:(odel )ormulation *e+words:components of linear programming AA,&-:Anal+tic s.ills 95) The minimi0ation of cost or ma/imi0ation of profit is the A) constraint of operations management. -) goal of management science. ,) objective of linear programming. ") assumption of financialit+. Answer:, "iff: 1 $age Ref: %1 &ection 'eading:(odel )ormulation *e+words:objective6 cost minimi0ation6 profit ma/imi0ation AA,&-:Anal+tic s.ills 91) ;hich of the following could be a linear programming objective functionH A) I ? 1A B #-, B %" -) I ? 1A B #- B %, B 1" ,) I ? 1A B #- K , B %" ") I ? 1A B #- # B %" Answer:- "iff: # $age Ref: 23 &ection 'eading:,haracteristics of Linear $rogramming $roblems *e+words:objective function AA,&-:Anal+tic s.ills #5 ,op+right 4 #51% $earson 'igher !ducation6 7nc. $ublishing as $rentice 'all 9#) The production manager for the ,oor+ soft drin. compan+ is considering the production of two .inds of soft drin.s: regular FR) and diet F"). Two of her limited resources are production time F9 hours ? 195 minutes per da+) and s+rup F1 of the ingredients)6 limited to 382 gallons per da+. To produce a regular case reraphical &olutions of Linear $rogramming (odels *e+words:graphical solution6 e/treme points6 feasible region AA,&-:Anal+tic s.ills #9 ,op+right 4 #51% $earson 'igher !ducation6 7nc. $ublishing as $rentice 'all The following is a graph of a linear programming problem. The feasible solution space is shaded6 and the optimal solution is at the point labeled Z*. 158) This linear programming problem is aFn) A) ma/imi0ation problem. -) minimi0ation problem. ,) irregular problem. ") cannot tell from the information given Answer:- "iff: 1 $age Ref: 25 &ection 'eading:A (inimi0ation (odel !/ample *e+words:graphical solution AA,&-:Anal+tic s.ills 159) The e Answer:" "iff: 1 $age Ref: %9 &ection 'eading:>raphical &olutions of Linear $rogramming (odels *e+words:graphical solution6 feasible point AA,&-:Anal+tic s.ills 115) ;hich line is represented b+ the e ,) "' ") AN Answer:A "iff: # $age Ref: %3 &ection 'eading:>raphical &olutions of Linear $rogramming (odels *e+words:graphical solution6 constraints AA,&-:Anal+tic s.ills 111) ;hich of the following constraints has a surplus greater than 5H A) -) -) ,> ,) "' ") AN Answer:, "iff: # $age Ref: %3 &ection 'eading:>raphical &olutions of Linear $rogramming (odels *e+words:graphical solution6 constraints AA,&-:Anal+tic s.ills 11#) The constraint AN A) is a binding constraint. -) has no surplus. ,) does not contain feasible points. ") contains the optimal solution. Answer:- "iff: % $age Ref: %3 &ection 'eading:>raphical &olutions of Linear $rogramming (odels *e+words:graphical solution6 constraints AA,&-:Anal+tic s.ills %5 ,op+right 4 #51% $earson 'igher !ducation6 7nc. $ublishing as $rentice 'all 11%) (ultiple optimal solutions can occur when the objective function is EEEEEEEE a constraint line. A) uneraphical &olutions of Linear $rogramming (odels *e+words:graphic solution6 steps for solving a graphical linear prog model AA,&-:Anal+tic s.ills %# ,op+right 4 #51% $earson 'igher !ducation6 7nc. $ublishing as $rentice 'all 11:) The optimal solution of a minimi0ation problem is at the e/treme point EEEEEEEE the origin. A) farthest from -) closest to ,) e/actl+ at ") parallel to Answer:- "iff: # $age Ref: 25 &ection 'eading:A (inimi0ation (odel !/ample *e+words:minimi0ation problem AA,&-:Anal+tic s.ills 1#5) (ultiple optimal solutions provide EEEEEEEE fle/ibilit+ to the decision ma.er. A) greater -) less ,) greater or e