Krajewski TIF Supplement E

Supplement E Linear Programming
Supplement
E
Linear Programming
TRUE/FALSE
1. Linear programming is useful for allocating scarce resources among competing demands.
Answer: True
Reference: Introduction
Difficulty: Easy
Keywords: linear, programming, product, mix
2. A constraint is a limitation that restricts the permissible choices.
Answer: True
Reference: Basic oncepts
Difficulty: !oderate
Keywords: constraint, limit
". #ecision $ariables are represented in both the ob%ecti$e function and the constraints &hile
formulating a linear program.
Answer: True
Keywords: constraint, decision, $ariable, ob%ecti$e
'. A parameter is a region that represents all permissible combinations of the decision $ariables in a
linear programming model.
Answer: (alse
Keywords: parameter, decision, $ariable, feasible, region
). In linear programming, each parameter is assumed to be *no&n &ith certainty.
Answer: True
Keywords: certainty, assumption
196
+. The ob%ecti$e function
2
Maximize Z = 3x +4y is appropriate.
Answer: (alse
Keywords: linearity, assumption, proportionality
,. -ne assumption of linear programming is that a decision ma*er cannot use negati$e .uantities of the
decision $ariables.
Answer: True
Keywords: nonnegati$ity, decision, $ariable
/. -nly corner points should be considered for the optimal solution to a linear programming problem.
Answer: True
Reference: 0raphic Analysis
Keywords: corner, point, optimal
1. The graphical method is a practical method for sol$ing product mix problems of any si2e, pro$ided
the decision ma*er has sufficient .uantities of graph paper.
Answer: (alse
Keywords: graphical, method
13. A binding constraint is the amount by &hich the left4hand side falls short of the right4hand side.
Answer: (alse
Keywords: binding, constraint
11. A binding constraint has slac* but does not ha$e surplus.
Answer: (alse
Keywords: binding, slac*, surplus
12. The simplex method is an interacti$e algebraic procedure for sol$ing linear programming problems.
Answer: True
Reference: omputer 5olutions
Keywords: simplex, method
197
MULTIPLE CHICE
1". A manager is interested in using linear programming to analy2e production for the ensuing &ee*. 5he
*no&s that it &ill ta*e exactly 1.) hours to run a batch of product A and that this batch &ill consume
t&o tons of sugar. This is an example of the linear programming assumption of6
a. linearity.
b. certainty.
c. continuous $ariables.
d. &hole numbers.
Answer: b
Keywords: certainty, assumption
1'. 7hich of the follo&ing statements regarding linear programming is 8-T true9
a. A parameter is also *no&n as a decision $ariable.
b. Linearity assumes proportionality and additi$ity.
c. The product4mix problem is a one4period type of aggregate planning problem.
d. -ne reasonable se.uence for formulating a model is defining the decision $ariables, &riting out the
ob%ecti$e function, and &riting out the constraints.
Answer: a
Keywords: parameter, decision, $ariable
1). 7hich of the follo&ing statements regarding linear programming is 8-T true9
a. A linear programming problem can ha$e more than one optimal solution.
b. !ost real4&orld linear programming problems are sol$ed on a computer.
c. If a binding constraint &ere relaxed, the optimal solution &ouldn:t change.
d. A surplus $ariable is added to a ; constraint to con$ert it to an e.uality.
Answer: c
Keywords: solution, surplus, $ariable
1+. (or the line that has the e.uation 'X1 < /X2 = //, an axis intercept is6
a. >3, 22?.
b. >+, 3?.
c. >+, 22?.
d. >3, 11?.
Answer: d
Keywords: axis, intercept
19!
1,. onsider a corner point to a linear programming problem, &hich lies at the intersection of the
follo&ing t&o constraints6
+X1 < 1)X2 @ "13
2X1 < X2 @ )3
7hich of the follo&ing statements about the corner point is true9
a. X1 @ 21
b. X1 ; 2)
c. X1 @ 13
d. X1 ; 1,
Answer: a
Keywords: corner, point
1/. A manager is interested in deciding production .uantities for products A, B, and . Ae has an
in$entory of 23 tons each of ra& materials 1, 2, ", and ' that are used in the production of products A,
B, and . Ae can further assume that he can sell all of &hat he ma*es. 7hich of the follo&ing
statements is correct9
a. The manager has four decision $ariables.
b. The manager has three constraints.
c. The manager has three decision $ariables.
d. The manager can sol$e this problem graphically.
Answer: c
Keywords: decision, $ariable
11. A site manager has three day laborers a$ailable for eight hours each and a burning desire to maximi2e
his return on their &ages. The site manager uses linear programming to assign them to t&o tas*s and
notes that he has enough &or* to occupy 21 labor hours. The linear program that the site manager has
constructed has6
a. slac*.
b. surplus.
c. a positi$e shado& price for labor.
d. no feasible solution.
Answer: d
Keywords: shado&, price
199
23. 5uppose that the optimal $alues of the decision $ariables to a t&o4$ariable linear programming
problem remain the same as long as the slope of the ob%ecti$e function lies bet&een the slopes of the
follo&ing t&o constraints6
2X1 < "X2 @ 2+
2X1 < 2X2 @ 23
The current ob%ecti$e function is6
/X1 < 1X2 = Z
7hich of the follo&ing statements about the range of optimality on c1 is TBCE9
a. 3 @ c1 @ 2
b. 2 @ c1 @ +
c. + @ c1 @ 1
d. 1 @ c1 @ 12
Answer: c
Reference: 5ensiti$ity Analysis
Difficulty: Aard
Keywords: range, optimality
21. Dou are faced &ith a linear programming ob%ecti$e function of6
!ax E = F23G < F"3D
and constraints of6
"G < 'D = 2' >onstraint A?
)G H D = 1/ >onstraint B?
Dou disco$er that the shado& price for onstraint A is ,.) and the shado& price for onstraint B is 3.
7hich of these statements is TBCE9
a. Dou can change .uantities of G and D at no cost for onstraint B.
b. (or e$ery additional unit of the ob%ecti$e function you create, you lose 3 units of B.
c. (or e$ery additional unit of the ob%ecti$e function you create, the price of A rises by F,.)3.
d. The most you &ould &ant to pay for an additional unit of A &ould be F,.)3.
Answer: d
Difficulty: Aard
22. 7hile glancing o$er the sensiti$ity report, you note that the stitching labor has a shado& price of F13
and a lo&er limit of 2' hours &ith an upper limit of "+ hours. If your original right hand $alue for
stitching labor &as "3 hours, you *no& that6
a. the next &or*er that offers to &or* an extra / hours should recei$e at least F/3.
b. you can send someone home + hours early and still pay them the F+3 they &ould ha$e earned &hile
on the cloc*.
c. you &ould be &illing pay up to F+3 for someone to &or* another + hours.
d. you &ould lose F/3 if one of your &or*ers missed an entire / hour shift.
Answer: c
"##
FILL I$ THE %LA$&
2". IIIIIIIIIIII is useful for allocating scarce resources among competing demands.
Answer: Linear programming
Reference: Introduction
Difficulty: Easy
Keywords: linear, programming
2'. The IIIIIIIIIIII is an expression in linear programming models that states mathematically &hat is
being maximi2ed or minimi2ed.
Answer: ob%ecti$e function
Keywords: ob%ecti$e, function
2). IIIIIIIIIIII represent choices the decision ma*er can control.
Answer: #ecision $ariables
Keywords: decision, $ariables
2+. IIIIIIIIIIII are the limitations that restrict the permissible choices for the decision $ariables.
Answer: onstraints
Keywords: constraint
2,. The IIIIIIIIIIII represents all permissible combinations of the decision $ariables in a linear
programming model.
Answer: feasible region
Keywords: feasible, region
2/. A>n? IIIIIIIIIIII is a $alue that the decision ma*er cannot control and that does not change &hen
the solution is implemented.
Answer: parameter
Keywords: parameter, $alue
21. Each coefficient or gi$en constant is *no&n by the decision ma*er &ith IIIIIIIIIIII.
Answer: certainty
Difficulty: Easy
Keywords: parameter, certainty, assumption
"#1
"3. If merely rounding up or rounding do&n a result for a decision $ariable is not sufficient &hen they
must be expressed in &hole units, then a decision ma*er might instead use IIIIIIIIIIII to analy2e
the situation.
Answer: integer programming
Keywords: integer, programming
"1. IIIIIIIIIIII is an assumption that the decision $ariables must be either positi$e or 2ero.
Answer: 8onnegati$ity
Difficulty: Easy
Keywords: nonnegati$ity, assumption
"2. The assumption of IIIIIIIIIIII allo&s a decision ma*er to combine the profit from one product
&ith the profit from another to reali2e the total profit from a feasible solution.
Answer: additi$ity
Difficulty: Easy
Keywords: additi$ity, assumption
"". The IIIIIIIIIIII problem is a one4period type of aggregate planning problem, the solution of
&hich yields optimal output .uantities of a group of products or ser$ices, sub%ect to resource capacity
and mar*et demand conditions.
Answer: product4mix
Keywords: product4mix, product, mix
"'. In linear programming, a IIIIIIIIIIII is a point that lies at the intersection of t&o >or possibly
more? constraint lines on the boundary of the feasible region.
Answer: corner point
Keywords: corner, point, solution
"). A>n? IIIIIIIIIIII forms the optimal corner and limits the ability to impro$e the ob%ecti$e function.
Answer: binding constraint
Keywords: binding, constraint, corner
"+. IIIIIIIIIIII is the amount by &hich the left4hand side falls short of the right4hand side in a linear
programming model.
Answer: 5lac*
Keywords: slac*, left4hand, side, right4hand
"#"
",. IIIIIIIIIIII is the amount by &hich the left4hand side exceeds the right4hand side in a linear
programming model.
Answer: 5urplus
Keywords: surplus, left4hand, side, right4hand
"/. A modeler is limited to t&o or fe&er decision $ariables &hen using the IIIIIIIIIIII.
Answer: graphical method
Difficulty: Easy
Keywords: decision, $ariables, graphical, method
"1. The IIIIIIIIIIII is the upper and lo&er limit o$er &hich the optimal $alues of the decision
$ariables remain unchanged.
Answer: range of optimality
Keywords: range, optimality
'3. (or an = constraint, only points IIIIIIIIIIII are feasible solutions.
Answer: on the line
Difficulty: Easy
Keywords: e.ual, than, line, feasible, region
'1. A>n? IIIIIIIIIIII is the marginal impro$ement in the ob%ecti$e function $alue caused by relaxing a
constraint by one unit.
Answer: shado& price
Keywords: shado&, price, sensiti$ity, relax, constraint
'2. The inter$al o$er &hich the right4hand4side parameter can $ary &hile its shado& price remains $alid
is the IIIIIIIIIIII.
Answer: range of feasibility
Keywords: range, feasibility
'". IIIIIIIIIIII occurs in a linear programming problem &hen the number of non2ero $ariables in the
optimal solution is fe&er than the number of constraints.
Answer: #egeneracy
Reference: omputer 5olution
Keywords: degeneracy
"#'
SHRT A$S(ER
''. 7hat are the assumptions of linear programming9 Ero$ide examples of each.
Answer: The assumptions are certainty, linearity, and nonnegati$ity. The assumption of certainty
is that a fact is *no&n &ithout doubt, such as an ob%ecti$e function coefficient, or the parameters
in the right4 and left4hand sides of the constraints. The assumption of linearity implies
proportionality and additi$ity, that is, that there are no cross products or s.uared or higher po&ers
of the decision $ariables. The assumption of nonnegati$ity is that decision $ariables must either
be positi$e or 2ero. Examples &ill $ary.
Keywords: assumption, linearity, certainty, nonnegati$ity
'). 7hat is the meaning of a slac* or surplus $ariable9
Answer: The amount by &hich the left4hand side falls short of the right4hand side is the slac*
$ariable. The amount by &hich the left4hand side exceeds the right4hand side is the surplus
$ariable.
Keywords: slac*, surplus
'+. Briefly describe the meaning of a shado& price. Ero$ide an example of ho& a manager could use
information about shado& prices to impro$e operations9
Answer: The shado& price is the marginal impro$ement in Z caused by relaxing a constraint by
one unit. Examples &ill $ary.
',. Ero$ide three examples of operations management decision problems for &hich linear programming
can be useful, and &hy.
Answer: Ans&ers and %ustifications &ill $ary. Eossible ans&ers include aggregate planning,
distribution, in$entory, location, process management, and scheduling.
Reference: Applications
Keywords: linear, programming, application
'/. 7hat are some potential abuses or misuses of linear programming >beyond $iolation of basic
assumptions?9
Answer: Ans&ers &ill $ary, but may include a discussion of the inability of modeling techni.ues
to capture all of the rele$ant factors that may be as important as &hat can be .uantified in an LE
formulation. (actors such as aesthetics, ethics, ci$ility, character, etc., may be difficult to capture
in an LE. 5la$ish adhesion to the output from a linear programming formulation robs a manager
of the freedom to in%ect reality or personality into a model. The rush to use a tool &ithout
understanding fully the &or*ings of it may render the output meaningless.
Reference: Applications
Difficulty: Basic oncepts
Keywords: linear, programming, application
"#)
PR%LEMS
'1. Cse the graphical techni.ue to find the optimal solution for this ob%ecti$e function and associated
constraints.
!aximi2e6 J=/A < )B
5ub%ect To6
onstraint 1 'A < )B @ /3
onstraint 2 ,A < 'B @ 123
A, B ; 3
a. 0raph the problem fully in the follo&ing space. Label the axes carefully, plot the constraints, shade
the feasibility region, identify all candidate corner points, and indicate &hich one yields the
optimal ans&er.
A
B
"#*
Answer:
>3, 3? / 3 ) 3 3 Z = + =
>3,1+? / 3 ) 1+ 13 Z = + =
>3,1,.1'? / 1,.1' ) 3 1",.1' Z = + =
>1'.,", '.21? / 1'.," ) '.21 1"/./1 Z = + = optimal
Keywords: graphic, analysis
"#6
Intersection of onstraint 1 K 2
>, ' 123? )
>' ) /3? '
11 2/3
1'.,", '.21
A B
A B
A
A B
+ =
+ =
=
= =
)3. A producer has three products, A, B, and , &hich are composed from many of the same ra&
materials and subassemblies by the same s*illed &or*force. Each unit of product A uses 1) units of
ra& material G, a single purge system subassembly, a case, a po&er cord, three labor hours in the
assembly department, and one labor hour in the finishing department. Each unit of product B uses 13
units of ra& material G, fi$e units of ra& material D, t&o purge system subassemblies, a case, a po&er
cord, fi$e labor hours in the assembly department, and 13 minutes in the finishing department. Each
unit of product uses fi$e units of ra& material G, 2) units of ra& material D, t&o purge system
subassemblies, a case, a po&er cord, se$en labor hours in the assembly department, and three labor
hours in the finishing department. Labor bet&een the assembly and finishing departments is not
transferable, but &or*ers &ithin each department &or* on any of the three products. There are three
full4time >'3 hoursL&ee*? &or*ers in the assembly department and one full4time and one half4time
>23 hoursL&ee*? &or*er in the finishing department. At the start of this &ee*, the company has "33
units of ra& material G, '33 units of ra& material D, +3 purge system subassemblies, '3 cases, and )3
po&er cords in in$entory. 8o additional deli$eries of ra& materials are expected this &ee*. There is a
F13 profit on product A, a F123 profit on product B, and a F1)3 profit on product . The operations
manager doesn:t ha$e any firm orders, but &ould li*e to ma*e at least fi$e of each product so he can
ha$e the products on the shelf in case a customer &anders in off the street.
(ormulate the ob%ecti$e function and all constraints, and clearly identify each constraint by the name
of the resource or condition it represents.
Answer:
-b%ecti$e (unction6 F13 F123 F1)3 Max P A B C = + +
Ba& !aterial G6 1) 13 ) "33 A B C + +
Ba& !aterial D6 3 ) 2) '33 A B C + +
Eurge 5ystem 5ubassembly6 1 2 2 +3 A B C + +
ase6 1 1 1 '3 A B C + +
ord6 1 1 1 )3 A B C + +
Assembly #epartment Labor6 " ) , 123 A B C + +
(inish #epartment Labor6 1 1.) " +3 A B C + +
!inimum Eroduction for A6 1 3 3 ) A B C + +
!inimum Eroduction for B6 3 1 3 ) A B C + +
!inimum Eroduction for 6 3 3 1 ) A B C + +
Reference: !ultiple sections
Difficulty: Easy
Keywords: linear, programming, ob%ecti$e, function, constraint
"#7
)1. A $ery confused manager is reading a t&o4page report gi$en to him by his student intern. M5he told
me that she had my problem sol$ed, ga$e me this, and then said she &as off to her production
management course,N he &hined. MI ga$e her my best estimates of my on4hand in$entories and
re.uirements to produce, but &hat if my numbers are slightly off9 I recogni2e the names of our four
models 7, G, D, and J, but that:s about it. an you figure out &hat I:m supposed to do and &hy9N
Dou ta*e the report from his hands and note that it is the ans&er report and the sensiti$ity report from
Excel:s sol$er routine.
Explain each of the highlighted cells in layman:s terms and tell the manager &hat they mean in
relation to his problem.
Microsoft Excel 10.0 Answer Report
Worksheet: Supplement D
Report Create: 1!"#!"00$ 11:"#:%0 AM
&ar'et Cell (Max)
Cell Name Original Value Final Value
*A+*1" ,00 -----.----,
A.usta/le Cells
Cell Name Original Value Final Value
*0*1" W 0 111.1111111
*1*1" 0 0 0
*2*1" 1 1.% 0
*AA*1" 2 0 0
Constraints
Cell Name Cell Value Formula Status Slack
*A+*1% 10000*A+*1%34*AC*1% +inin' 0
*A+*1$ 1111.111111*A+*1$34*AC*1$ 5ot +inin' 6---.-----,
*A+*1# %000*A+*1#34*AC*1# 5ot +inin' "%000
"#!
Microsoft Excel 10.0 Sensiti7it8 Report
Worksheet: Supplement D
Report Create: 1!"#!"00$ 11:"#:%0 AM
A.usta/le Cells
Final Reduced Objective Alloable Alloable
Cell Name Value Cost Coe!!icient "ncrease #ecrease
*0*1" W 111.1111111 0 -00 1E960 -0
*1*1" 0 0 :,66.6666666 $00 ,66.6666666 1E960
*2*1" 1 0 :##.#######; #00 ##.#######; 1E960
*AA*1" 2 0 :10%%.%%%%%# %00 10%%.%%%%%# 1E960
Constraints
Final S$ado Constraint Alloable Alloable
Cell Name Value Price R%&% Side "ncrease #ecrease
*A+*1% 10000 -.--------, 10000 6%000 10000
*A+*1$ 1111.111111 0 %000 1E960 6---.-----,
*A+*1# %000 0 60000 1E960 "%000
Answer:
Ans&er Beport
Target ell !ax6 The target cell should be maximi2ed, so the manager must ha$e pro$ided the
intern &ith profit information.
(inal Oalue6 The final $alue is the greatest amount possible for the situation. If &e are
&or*ing &ith profit figures, this is the best return possible gi$en &hat &e estimate is on hand and
ho& it is to be produced. This may change if our in$entory or recipes are slightly off. The highest
profit identified is F//,///./1
Ad%ustable ells6 The ad%ustable cells sho& that &e considered any positi$e .uantity of models
7HJ as possible outputs for the &ee*.
8ame6 The names are those of the models &e produce.
(inal Oalue6 These are the exact amounts of each of our four models to produce to earn the
final $alue. In this case &e &ould ma*e 111.1 units of model 7 and none of the other four
models.
5tatus6 This sho&s &hat is limiting our ability to produce the models. A binding constraint
directly limits our output although a nonbinding constraint means that factor does not limit us. In
this case, the second and third constraints are nonbinding, so producing 111.1 units of model 7
lea$es us &ith lefto$ers of &hate$er scarce resource they represent. The first constraint is binding,
so &e are using up e$ery bit of that resource.
5lac*6 5lac* sho&s us ho& much of each resource &e ha$e left. -ur first constraint is
binding, so &e ha$e none left o$er and therefore ha$e 3 slac*. -ur second and third constraints
are not binding, so &e ha$e plenty >",/// and 2),333 units respecti$ely? of these scarce resources
left o$er.
5ensiti$ity Beport
Ad%ustable ells
Beduced ost6 This is the change in the optimum objective per unit change in the upper or
lower bounds of the variable. The objective function will increase by 0.-66, and so on, per unit
increase.
"#9
Allo&able Increase6 These t&o >Allo&able Increase and Allo&able #ecrease? pro$ide a
range for our current ans&er and the recipe &e used to arri$e at it. (or model 7, &e ha$e
assumed that each unit gi$es us F/33 profit. If our estimate &as too high, and the return &as up to
F/3 less per unit, &e &ould still arri$e at the same ans&er. If it &ere more than F/3 too high, our
ans&er &ould change. The same holds true for the models &e are not ma*ing. If model D made
more than F+++.++ profit per unit, then our final product mix &ould change.
Allo&able #ecrease6 5ee analysis for Allo&able Increase.
onstraints
5hado& Erice6 This is the marginal return for ha$ing one more unit of each resource. Aere
&e ha$e a shado& price of F/.//, so if &e had one more unit of resource in the first constraint, &e
could ma*e an additional F/.//. This gi$es us an idea of the maximum &e &ould be &illing to
pay for more of that resource.
Allo&able Increase6 These &or* the same as the allo&able increases and decreases for the
ad%ustable cells except they focus on the shado& prices. They indicate ho& far the BA5 of the
constraint can change before the shado& price &ill change.
Allo&able #ecrease6 5ee discussion immediately preceding.
Keywords: sensiti$ity, analysis
)2. The J Pe&elry ompany produces t&o products6 >1? engagement rings and >2? %e&eled &atches. The
production process for each is similar in that both re.uire a certain number of hours of diamond &or*
and a certain number of labor hours in the gold department. Each ring ta*es four hours of diamond
&or* and t&o hours in the gold shop. Each &atch re.uires three hours in diamonds and one hour in
the gold department. There are 2'3 hours of diamond labor a$ailable and 133 hours of gold
department time a$ailable for the next month. Each engagement ring sold yields a profit of F1Q each
&atch produced may be sold for a F13 profit.
a. 0i$e a complete formulation of this problem, including a careful definition of your decision
$ariables. Let the first decision $ariable, >X1?, deal &ith rings, the second decision $ariable, >X2?,
&ith &atches, the first constraint &ith diamonds, and the second constraint &ith gold.
b. 0raph the problem fully in the follo&ing space. Label the axes carefully, plot the constraints, shade
the feasibility region, plot at least one isoprofit line that re$eals the optimal solution, circle the
corner points and highlight the optimal optimal corner point so found, and sol$e for it
algebraically. >5ho& all your &or* to get credit.?
"1#
X1
X2
Answer:
a. !ax6 1X1 < 13X2
s.t. 'X1 < "X2 @ 2'3 hours of diamond &or*
2X1 < X2 @ 133 hours of gold &or*
X1, X2 ; 3
b.
Keywords: ob%ecti$e, function, constraint, graphical
"11
X1
)". 8D8EG must schedule round4the4cloc* co$erage for its telephone operators. To *eep the number of
different shifts do&n to a manageable le$el, it has only four different shifts. -perators &or* eight4
hour shifts and can begin &or* at either midnight, / a.m., noon, or ' p.m. -perators are needed
according to the follo&ing demand pattern, gi$en in four4hour time bloc*s.
Time Eeriod -perators 8eeded
midnight to ' a.m. '
' a.m. to / a.m. +
/ a.m. to noon 13
8oon to ' p.m. /)
' p.m. to / p.m. ))
/ p.m. to midnight 23
(ormulate this scheduling decision as a linear programming problem, defining fully your decision
$ariables and then gi$ing the ob%ecti$e function and constraints.
Answer:
Let X1 = the number of telephone operators starting their shift at midnight.
X2 = the number of telephone operators starting their shift at / a.m.
X" = the number of telephone operators starting their shift at noon.
X' = the number of telephone operators starting their shift at ' p.m.
!in6 X1 < X2 < X" < X'
sub%ect to X1 ; ' !idnight to ' a.m.
X1 ; + ' a.m. to / a.m.
X2 ; 13 / a.m. to noon
X2 < X" ; /) noon to ' p.m.
X" < X' ; )) ' p.m. to / p.m.
X' ; 23 / p.m. to midnight
X1, X2, X", X' ; 3
Keywords: ob%ecti$e function, constraint
"1"
)'. The Beally Big 5hoe ompany is a manufacturer of bas*etball shoes and football shoes. Ed 5ulli$an,
the manager of mar*eting, must decide the best &ay to spend ad$ertising resources. Each football
team sponsored re.uires 123 pairs of shoes. Each bas*etball team re.uires "2 pairs of shoes. (ootball
coaches recei$e F"33,333 for shoe sponsorship and bas*etball coaches recei$e F1,333,333. EdRs
promotional budget is F"3,333,333. The Beally Big 5hoe ompany has a $ery limited supply >'
liters or ',333cc? of flubber, a rare and costly ra& material used only in promotional athletic shoes.
Each pair of bas*etball shoes re.uires "cc of flubber, and each pair of football shoes re.uires 1cc of
flubber. Ed desires to sponsor as many bas*etball and football teams as resources allo&. Ao&e$er, he
has already committed to sponsoring 11 football teams and &ants to *eep his promises.
a. 0i$e a linear programming formulation for Ed. !a*e the $ariable definitions and constraints line
up &ith the computer output appended to this exam.
b. 5ol$e the problem graphically, sho&ing constraints, feasible region, and isoprofit lines. ircle the
optimal solution, ma*ing sure that the isoprofit lines dra&n ma*e clear &hy you chose this point.
>5ho& all your calculations for plotting the constraints and isoprofit line on the left to get credit.?
c. 5ol$e algebraically for the corner point on the feasible region.
d. Eart of EdRs computer output is sho&n follo&ing. 0i$e a full explanation of the meaning of the
three numbers listed at the end. Based on your graphical and algebraic analysis, explain &hy
these numbers ma*e sense. >Aint6 Ae formulated the budget constraint in terms of F333.?
5ee the computer printout that follo&s.
"1'
X
1
X
2

Solver'Linear Programming
Solution
<aria/le <aria/le =ri'inal Coefficient
>a/el <alue Coefficient Sensiti7it8
<ar1 1,.0000 1.0000 0
<ar" 1;.,1#; 1.0000 0
Constraint =ri'inal Slack or Shaow
>a/el R?< Surplus @rice
Const1 1, 0
Const" 60000 #6-6 0
Const6 $000 0 0.010$
=/.ecti7e Aunction <alue: 6#.,1#####;
Sensitivit( Anal(sis and Ranges
=/.ecti7e Aunction Coefficients
<aria/le >ower =ri'inal Bpper
>a/el >imit Coefficient >imit
<ar1 5o >imit 1 1."%
<ar" 0.- 1 5o >imit
Ri'ht:?an:Sie <alues
Constraint >ower =ri'inal Bpper
>a/el >imit <alue >imit
Const1 1"."-0; 1, 66.66666666
Const" "6#1#.#; 60000 5o >imit
Const6 ""-0 $000 $#1".-
(irst 8umber6 The shado& price of 3.313' for the Sonst"S constraint.
5econd 8umber6 The slac* or surplus of +"/" for the Sonst1S constraint.
Third 8umber6 The lo&er limit of 12.2/3,for the Sonst1S constraint.
Answer:
a. Let X1 = the number of football teams sponsored
X2 = the number of bas*etball teams sponsored
!ax X1 < X2
s.t. X1 ; 11 ommitments
"33X1 < 1333G2 @ "3333 Budget
123X1 < 1+G2 @ '333 (lubber
"1)
G1, X2 ; 3
"1*
b.
"16
1 1
6 11 11 Commitments X X > =
1 2
1 2
2 1
6 "33 1333 "3333
"3333
3, "3
1333
"3333
3Q 133
"33
Budget X X
if X X
if X X
+ <
= = =
= = =
1 2
1 2
2 1
(lubber 6123 1+ '333
'333
3Q '1.+
1+
'333
3Q ""."
123
X X
if X X
if X X
+ <
= = =
= = =
c.
Therefore, X1 = 11
d.
(irst 8umber6 The shado& price of 3.313' for the Sonst"S constraint.
5econd 8umber6 The slac* or surplus of +"33 for the Sonst1S constraint.
Third 8umber6 The lo&er limit of 12."+/' for the Sonst1S constraint.
The first number is the amount >.313'? by &hich the ob%ecti$e function &ill impro$e &ith a one4unit
decrease in the right4hand4side $alue. The second number means that +,"33,333 remains in the promised
commitment. The third $alue is the amount by &hich the constraint can change and still *eep the current
$alues of the shado& price.
Keywords: constraint, ob%ecti$e, function
)). A portfolio manager is trying to balance in$estments bet&een bonds, stoc*s and cash. The return on
stoc*s is 12 percent, 1 percent on bonds, and " percent on cash. The total portfolio is F1 billion, and
he or she must *eep 13 percent in cash in accordance &ith company policy. The fundRs prospectus
promises that stoc*s cannot exceed ,) percent of the portfolio, and the ratio of stoc*s to bonds must
e.ual t&o. (ormulate this in$estment decision as a linear programming problem, defining fully your
decision $ariables and then gi$ing the ob%ecti$e function and constraints.
Answer:
Let X1 = the amount in$ested in bonds
X2 = the amount in$ested in stoc*s
X" = the amount in$ested in cash
!ax6 z = .31X1 < .12X2 <.3"X"
s.t. X1 < X2 < G" 1,333,333,333 Eortfolio $alue
G1 = 133,333,333 13T minimum stoc*
X2 ,)3,333,333 ,)T maximum cash
2X1 H X2 = 3 261 ratio stoc*s to bonds
X1, X2, X" ; 3
Keywords: ob%ecti$e, function, constraint
"17
1 2
1
2
2
corner point
123 1+ '333
> 11? 123
1+ 1,23
1,.11+
X X
X
X
X
+ =
=
=
=
)+. A small oil company has a refining budget of F233,333 and &ould li*e to determine the optimal
production plan for profitability. The follo&ing table lists the costs associated &ith its three products.
!ar*eting has a budget of F)3,333, and the company has ,)3,333 gallons of crude oil a$ailable.
Each gallon of gasoline contributes 1' cents of profits, heating oil pro$ides 13 cents, and plastic
resin "3 cents per unit. The refining process results in a ratio of t&o units of heating oil for each
unit of gasoline produced. This problem has been modeled as a linear programming problem and
sol$ed on the computer. The output follo&s6
Solution
<aria/le <aria/le =ri'inal Coefficient
>a/el <alue Coefficient Sensiti7it8
<ar1 0.0000 0.1$00 0
<ar" 1%0000.0000 0.1000 0
<ar6 0.0000 0.6000 0
Constraint =ri'inal Slack or Shaow
>a/el R?< Surplus @rice
Const1 "00000 1-%000 0
Const" %0000 $"%00 0
Const6 ;%0000 0 0.0"00
=/.ecti7e Aunction <alue: 1%000
Sensitivit( Anal(sis and Ranges
=/.ecti7e Aunction Coefficients
<aria/le >ower =ri'inal Bpper
>a/el >imit Coefficient >imit
<ar1 5o >imit 0.1$ 0."
<ar" 0.0;% 0.1 5o >imit
<ar6 5o >imit 0.6 0.$
Ri'ht:?an:Sie <alues
Constraint >ower =ri'inal Bpper
>a/el >imit <alue >imit
Const1 1%000 "00000 5o >imit
Const" ;%00 %0000 5o >imit
Const6 0 ;%0000 %000000
"1!
a. 0i$e a linear programming formulation for this problem. !a*e the $ariable definitions and
constraints line up &ith the computer output.
b. 7hat product mix maximi2es the profit for the company using its limited resources9
c. Ao& much gasoline is produced if profits are maximi2ed9
d. 0i$e a full explanation of the meaning of the three numbers listed follo&ing.
(irst 8umber6 5lac* or surplus of '2)33 for constraint 2.
5econd 8umber6 5hado& price of 3 for constraint 1.
Third 8umber6 An upper limit of Sno limitS for the right4hand4side $alue constraint 1.
Answer:
a. Let X1 = gallons of gasoline refined
X2 = gallons of heating oil refined
X" = gallons of plastic resin refined
!ax6 .1'X1 < .13X2 < ."3X"
s.t. .'3X1 < .13X2 < .+3X" @ 233,333 Befining budget
.13X1 < .3)X2 < .3,X" @ )3,333 !ar*eting budget
13X1 < )X2 < 23X" @ ,)3,333 rude oil a$ailable
X2 H 2X1 = 3 Batio
X1, X2, X" ; 3
b. X1 = 3 gallons, X2 = 1)3,333 gallons, and X" = 3 gallons
c. 8o gasoline is produced if profits are maximi2ed.
d. F'2,)33 remains in the mar*eting budget. A 2ero implies that increasing the refining budget &ill not
impro$e the $alue of the ob%ecti$e function. A no4limit implies that the right4hand side can be increased
by any amount and the shado& price &ill remain the same.
),. A snac* food producer runs four different plants that supply product to four different regional
distribution centers. The di$ision operations manager is focused on one product, so he creates a table
sho&ing each plant:s monthly capacity and each distribution center:s monthly demand >both amounts
in cases? for the product. The di$ision manager supplements this table &ith the cost data to ship one
case from each plant to each distribution center. (ormulate an ob%ecti$e function and constraints that
&ill sol$e this problem using linear programming.
enter 1 enter 2 enter " enter ' !onthly
apacity
Elant A F2 F, F) F' /333
Elant B F1 F' F, F+ 12333
Elant F, F+ F' F" ,)33
Elant # F' F/ F" F) )333
!onthly
#emand
1333 /)33 /333 ,333
Answer:
This is a cost minimi2ation problem &ith 1+ decision $ariables, one for each combination of plant
and centerQ there are / constraints, one for each plant:s capacity and one for each center:s
demand.
1 2 " ' 1 2 " ' 1
2 " ' 1 2 " '
F2 F, F) F' F1 F' F, F+ F,
F+ F' F" F' F/ F" F)
A A A A B B B B C
C C C D D D D
O!ecti"e Min Z x x x x x x x x x
x x x x x x x
= + + + + + + + +
+ + + + + + +
"19
1 2 " '
1 2 " '
1 2 " '
1 2 " '
1 1 1 1
2 2 2 2
" "

6 /333
6 12333
6 ,)33
6 )333
16 1333
2 6 /)33
"6
A A A A
B B B B
C C C C
D D D D
A B C D
A B C D
A B C
#u!ect to
P$ant A x x x x
P$ant B x x x x
P$ant C x x x x
P$ant D x x x x
Cente% x x x x
Cente% x x x x
Cente% x x x
+ + + =
+ + + =
+ + + =
+ + + =
+ + + =
+ + + =
+ +
" "
' ' ' '
/333
' 6 ,333
D
A B C D
x
Cente% x x x x
+ =
+ + + =
(or those of you *eeping score at home, the optimal solution is6
Center 1 Center 2 Center 3 Center 4 Monthly
Capacity
Plant A 8,000 8,000
Plant B 8,500 3,500 12,000
Plant C 500 7,000 7,500
Plant D 1,000 4,000 5,000
Monthly
Demand
9,000 8,500 8,000 7,000 $113,500
""#

Krajewski TIF Supplement E

Uploaded by

Copyright:

Available Formats

Krajewski TIF Supplement E

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Krajewski TIF Supplement E

Uploaded by

Copyright:

Available Formats

Supplement E Linear Programming

You might also like