Document

Report
Readings
Readings
Chapter 7
Integer Linear Programming
BA 452 Lesson B.5 Binary Indicator Variables
1
Overview
Overview
BA 452 Lesson B.5 Binary Indicator Variables
2
Overview
Machine Use Indicators are binary variables where 0 indicates no use and 1
indicates positive use. They are part of a simple linear model of the fixed cost
of machine use.
Resource Allocation Problems with Fixed Costs trade off the advantage of using
a variety of inputs to conform to fixed resources with the positive fixed cost of
using each input.
Product Mix Problems with Fixed Costs trade off the advantage of producing a
variety of goods to conform to fixed resources with the positive fixed cost of
producing each good.
Make or Buy Decisions with Fixed Costs trade off the lower unit cost of
producing a good yourself with the positive fixed cost of production.
Relational Constraints such as “either project i or project j is completed” or “both
project i and project j are completed” can be written as linear constraints in
binary indicator variables.
Capital Budgeting Problems maximize the net present value or net return from
a selection of projects that each require a fixed amount of capital. Relational
constraints are often imposed.
BA 452 Lesson B.5 Binary Indicator Variables
3
Tool Summary
Tool Summary
 Use binary variables to indicate whether an activity, such as a
production run, is undertaken.
 Write a multiple-choice constraint: The sum of two or more binary
variables equals 1, so any feasible solution choose one variable to
equal 1.
 Write a mutually-exclusive constraint: The sum of two or more binary
variables is at most 1, so any feasible solution chooses at most one
variable to equal 1. All variables could equal 0.
 Write a conditional constraint: An inequality constraint so that one
binary variable cannot equal unless certain other binary variables
also equal 1.
 Write a corequisite constraint: An equality constraint of binary
variables, so are either both 0 or both 1.
BA 452 Lesson B.5 Binary Indicator Variables
4
Machine Indicators
Machine Indicators
BA 452 Lesson B.5 Binary Indicator Variables
5
Machine Indicators
Overview
Machine Use Indicators are binary variables where 0 indicates no use
and 1 indicates positive use. They are part of a simple linear model of
the fixed cost of machine use.
For example, consider a standard Resource Allocation Problem with
Machines, where the maximum machine resource available is 20.
Suppose fixed setup costs of using a machine restrict machine use X
so “either X = 0 or 6 < X < 20”. But “either X = 0 or 6 < X < 20” is not a
linear constraint. To make “either X = 0 or 6 < X < 20” a linear
constraint, introduce binary variable Y and replace the standard
resource constraint X < 20 with “6Y < X < 20Y”. The linear constraints
“6Y < X < 20Y” can be satisfied in one of two ways. On the one hand, if
Y = 0, then the constraints read “6(0) < X < 20(0)” and so are satisfied
only by X = 0. On the one hand, if Y = 1, then the constraints read “6(1)
< X < 20(1)” and so are satisfied only by 6 < X < 20.
BA 452 Lesson B.5 Binary Indicator Variables
6
Machine Indicators
Question: Ji-Yang Plastic makes plastic parts in Taiwan
used in automobiles and computers. One of its major
contracts involves the production of plastic printer cases
for a computer company’s portable printers. The printer
cases can be produced on two injection molding machines.
The M-100 machine has a production capacity of 25 printer
cases per hour, and the M-200 machine has a production
capacity of 40 printer cases per hour. Both machines use
the same chemical to produce the printer cases; the M-100
uses 40 pounds of raw material per hour, and the M-200
uses 50 pounds per hour.
BA 452 Lesson B.5 Binary Indicator Variables
7
Machine Indicators
The computer company asked Ji-Yang to produce as many
of the cases as possible during the upcoming week; it will
pay $18 for each case. However, next week is a regularly
scheduled vacation period for most of Ji-Yang’s production
employees. During this time, annual maintenance is
performed on all equipment. Because of the downtime for
maintenance, the M-100 is only available for at most 15
hours, and the M-200 for at most 10 hours.
BA 452 Lesson B.5 Binary Indicator Variables
8
Machine Indicators
The supplier of the chemical used in the production
process informed Ji-Yang that a maximum of 1000 pounds
of the chemical material will be available for next week’s
production; the cost for this raw material is $6 per pound.
In addition to the raw material cost, Ji-Yang estimates that
the hourly cost of operating the M-100 and the M-200 are
$50 and $75, respectively.
BA 452 Lesson B.5 Binary Indicator Variables
9
Machine Indicators
However, because of the high setup cost on both
machines, management requires that, if a machine is used
at all, it must be used for at least 5 hours.
(That last constraint makes the fixed cost of producing with
a machine equal to the cost of using the machine for 5
hours.)
BA 452 Lesson B.5 Binary Indicator Variables
10
Machine Indicators
Answer:
 Define decision variables:
• M1 = number of hours spent on the M-100 machine
• M2 = number of hours spent on the M-200 machine
 Total revenue = 18(25) M1 + 18(40) M2 = 450 M1 + 720
M2
 Total cost = 6(40) M1 + 6(50) M2 + 50 M1 + 75 M2 = 290
M1 + 375 M2
BA 452 Lesson B.5 Binary Indicator Variables
11
Machine Indicators
Mixed binary formulation
 Define objective:
Maximize (profit = revenue-cost) 160 M1 + 345 M2
 Define constraints:
• M1
< 15
(M-100 maximum)
•
M2 < 10
(M-200 maximum)
• 40M1 + 50 M2 < 1000
(Raw Material)
• M1
> 5 U1
(M-100 minimum, if M1 > 0)
•
M2 > 5 U2
(M-200 minimum, if M2 > 0)
• 15U1 > M1
(so U1 = 1 if M1 > 0)
• 10U2 > M2
(so U2 = 1 if M2 > 0)
• M1, M2 > 0 and U1, U2 binary (0 or 1)
BA 452 Lesson B.5 Binary Indicator Variables
12
Machine Indicators
Mixed binary formulation
BA 452 Lesson B.5 Binary Indicator Variables
13
Machine Indicators
Mixed binary solution
Use M1 for 12.5 hours, and M2 for 10 hours.
BA 452 Lesson B.5 Binary Indicator Variables
14
Resource Allocation with Fixed Cost
Resource Allocation with Fixed
Cost
BA 452 Lesson B.5 Binary Indicator Variables
15
Resource Allocation with Fixed Cost
Overview
Resource Allocation Problems with Fixed Cost trade off the advantage of using
a variety of inputs to conform to fixed resources with the positive fixed cost of
using each input. The simplest way to model those fixed costs in a linear
program is with binary (0 or 1) variables used as indicators, where 0 values
indicate no production and 1 indicates positive production.
For example, consider a standard Resource Allocation Problem, where for one
of the inputs, the maximum resource available is 10, and the cost of using X is
3X. Now suppose there is an added fixed setup costs of 15. To model those
fixed costs in a linear program, introduce binary variable Y, replace the
resource supply constraint X < 10 with “X < 10Y”, and add the cost term 15Y so
total cost becomes 3X + 15Y. The constraint “X < 10Y” can be satisfied in one
of two ways. On the one hand, if X = 0, then the constraint reads “0 < 10Y” and
so can be satisfied by Y = 0, and so total cost = 3X. On the one hand, if X > 0,
then the constraint “X < 10Y” can only be satisfied by Y = 1, and so total cost =
3X + 15.
BA 452 Lesson B.5 Binary Indicator Variables
16
Resource Allocation with Fixed Cost
Question: A businessman is considering opening a small
specialized trucking firm. To make the firm profitable, it is
estimated that it must have a daily trucking capacity of at
least 12 tons. Two types of trucks are appropriate for the
specialized operation. Their characteristics and costs are
summarized in the table below. Note that each large truck
require 2 drivers for long-haul trips. There are 8 potential
drivers available and there are facilities for at most 4 trucks.
BA 452 Lesson B.5 Binary Indicator Variables
17
Resource Allocation with Fixed Cost
The businessman's objective is to minimize the total cost
outlay for trucks.
Truck
Small
Large
Capacity
Cost
(tons)
$10,000
2
$30,000
4
Drivers
Needed
1
2
Formulate and graphically solve a linear programming
model for this problem. How many of each type of truck
should be used?
Reformulate the problem if the trucking firm incurs a fixed
setup cost of $2 if it uses any positive quantity of small
trucks, and a fixed setup cost of $4 if it uses any positive
quantity of large trucks?
BA 452 Lesson B.5 Binary Indicator Variables
18
Resource Allocation with Fixed Cost
Answer:
Let S = the number of small trucks used
Let L = the number of large trucks used
Min
s.t.
10000S + 30000L
2S + 4L > 12 (capacity constraint)
S + 2L < 8 (driver constraint)
S + L < 4 (facility constraint)
S, L > 0
A graph of the feasible set and iso-value lines shows the
optimal solution occurs where the first and third constraints
bind (the second constraint is redundant). Solving the
binding form of those two constraints yields the optimal
solution: S = 2, L = 2.
BA 452 Lesson B.5 Binary Indicator Variables
19
Resource Allocation with Fixed Cost
Question: How would the formulation change if the trucking
firm incurs a fixed setup cost of $2 if it uses any positive
quantity of small trucks, and a fixed setup cost of $4 if it
uses any positive quantity of large trucks?
BA 452 Lesson B.5 Binary Indicator Variables
20
Resource Allocation with Fixed Cost
Answer:
Let SS = 1 if Small Trucks are used; 0 if not
Let SY = 1 if Large Trucks are used; 0 if not
Objective: Min
10000S + 30000L + 2SS + 4SY
Input Constraints:
2S + 4L > 12 (capacity constraint)
S + 2L < 8 (driver constraint)
S + L < 4 (facility constraint)
S, L > 0
Setup Constraints (given input constraints imply S < 4, L <
4):
S < 4SS
L < 4SL
BA 452 Lesson B.5 Binary Indicator Variables
21
Product Mix with Fixed Cost
Product Mix with Fixed Cost
BA 452 Lesson B.5 Binary Indicator Variables
22
Product Mix with Fixed Cost
Overview
Product Mix Problems with Fixed Cost trade off the advantage of producing a
variety of goods to conform to fixed resources with the positive fixed cost of
producing each good. The simplest way to model those fixed costs in a linear
program is with binary (0 or 1) variables used as indicators, where 0 values
indicate no production and 1 indicates positive production.
For example, consider a standard Product Mix Problem, where for one of the
outputs, the maximum production demanded is 10, and the cost of producing X
is 3X. Now suppose there is an added fixed setup costs of 15. To model those
fixed costs in a linear program, introduce binary variable Y, replace the demand
constraint X < 10 with “X < 10Y”, and add the cost term 15Y so total cost
becomes 3X + 15Y. The constraint “X < 10Y” can be satisfied in one of two
ways. On the one hand, if X = 0, then the constraint reads “0 < 10Y” and so
can be satisfied by Y = 0, and so total cost = 3X. On the one hand, if X > 0,
then the constraint “X < 10Y” can only be satisfied by Y = 1, and so total cost =
3X + 15.
BA 452 Lesson B.5 Binary Indicator Variables
23
Product Mix with Fixed Cost
Question: Iron Elegance seeks to maximize profit by
making two products from steel. It just received this
month's allocation of 19 pounds of steel. It takes 2 pounds
of steel to make a unit of product 1, and 3 pounds of steel
to make a unit of product 2. The physical plant has the
capacity to make at most 6 units of product 1, and at most
8 units of total product (product 1 plus product 2).
Product 1 sells for price 7, has marginal cost 2, and fixed
cost 3. Product 2 sells for price 8, has marginal cost 1, and
fixed cost 2.
Formulate a linear program to maximize profit.
BA 452 Lesson B.5 Binary Indicator Variables
24
Make or Buy with Fixed Cost
Answer: A mixed integer linear program can be set up to
solve this problem. Binary variables are used to indicate
whether or not we setup to produce the two products.
 Let x1 and x2 denote this month's production level of
product 1 and product 2.
 y1 = 1 if x1 > 0; y1 = 0 if not
 y2 = 1 if x2 > 0; y2 = 0 if not
BA 452 Lesson B.5 Binary Indicator Variables
25
Product Mix with Fixed Cost


The total monthly profit =
(profit per unit of product 1) x (monthly production of
product 1)
+ (profit per unit of product 2) x (monthly production of
product 2)
= (7-2)x1 + (8-1)x2 - 3y1 - 2y2
Maximize total monthly profit: Max 5x1 + 7x2 - 3y1 - 2y2
BA 452 Lesson B.5 Binary Indicator Variables
26
Product Mix with Fixed Cost
Here is a mathematical formulation of constraints.
 The total amount of steel used during monthly production =
(steel used per unit of product 1) x (monthly production of product 1)
+ (steel used per unit of product 2) x (monthly production of product 2)
= 2x1 + 3x2
 That quantity must be less than or equal to the allocated 19 pounds
of steel (the inequality < in the constraint below assumes excess
steel can be freely disposed; if disposal is impossible, then use
equality =) :
2x1 + 3x2 < 19
 The constraint that the physical plant has the capacity to make at
most 6 units of product 1 is formulated
x1 < 6
 The constraint that the physical plant has the capacity to make at
most 8 units of total product (product 1 plus product 2) is
x1 + x2 < 8
BA 452 Lesson B.5 Binary Indicator Variables
27
Product Mix with Fixed Cost

Given resource constraint 2x1 + 3x2 < 19 implies x1 <
19/2 and x2 < 19/3, setup indicators
x1 < (19/2) y1
x2 < (19/3) y2
BA 452 Lesson B.5 Binary Indicator Variables
28
Product Mix with Fixed Cost
Adding the non-negativity and binary constraints
complete the formulation.
Max
5x1 + 7x2 - 3y1 - 2y2
s.t. x1
< 6
2x1 + 3x2 < 19
x1 + x2 < 8
x1 < (19/2) y1
x2 < (19/3) y2
x1 > 0 and x2 > 0
y1 = 0 or 1
y2 = 0 or 1
Objective
function
Standard
constraints
Setup
constraints
Non-negativity
Binary
BA 452 Lesson B.5 Binary Indicator Variables
29
Product Mix with Fixed Cost
The Management Scientist can solve this mixed integer
linear program of 2 binary variables Yi and 2 continuous
variables Xi.
BA 452 Lesson B.5 Binary Indicator Variables
30
Make or Buy with Fixed Cost
Make or Buy with Fixed Cost
BA 452 Lesson B.5 Binary Indicator Variables
31
Make or Buy with Fixed Cost
Overview
Make or Buy Decisions with Fixed Cost trade off the lower unit cost of
producing a good yourself with the positive fixed cost of production.
The simplest way to model those fixed costs in a linear program is with
binary (0 or 1) variables used as indicators, where 0 values indicate no
production and 1 indicates positive production.
For example, consider a standard Make or Buy Decision, where the
maximum production demanded is 10, and the cost of producing X is
3X. Now suppose there is an added fixed setup costs of 15. To model
those fixed costs in a linear program, introduce binary variable Y,
replace the demand constraint X < 10 with “X < 10Y”, and add the cost
term 15Y so total cost becomes 3X + 15Y. The constraint “X < 10Y”
can be satisfied in one of two ways. On the one hand, if X = 0, then the
constraint reads “0 < 10Y” and so can be satisfied by Y = 0, and so total
cost = 3X. On the one hand, if X > 0, then the constraint “X < 10Y” can
only be satisfied by Y = 1, and so total cost = 3X + 15.
BA 452 Lesson B.5 Binary Indicator Variables
32
Make or Buy with Fixed Cost
Question: Sony produces remote controllers for both
televisions and DVD players. Each controller consists of
three subassemblies that are made by Sony --- a base, a
cartridge, and a keypad. Both controllers use the same
base subassembly, but different cartridge and keypad
subassemblies.
Sony’s sales forecast is that 7000 TV controllers and 5000
DVD controllers will be needed to satisfy demand during
the upcoming Christmas season. Because only 500 hours
of in-house manufacturing time is available, Sony considers
buying some, or all, of the subassemblies from outside
suppliers.
BA 452 Lesson B.5 Binary Indicator Variables
33
Make or Buy with Fixed Cost
If Sony makes a subassembly, it incurs a fixed setup cost
as well as a variable manufacturing cost. For each
subassembly, the following are the fixed setup costs, the
manufacturing time, the manufacturing costs, and the
purchase costs:
Subassembly
Setup Cost ($)
Manufacturing
Time per Unit
(min.)
Manufacturing
Cost per Unit
($)
Purchase Cost
per Unit ($)
Base
1000
0.9
0.40
0.65
TV cartridge
1200
2.2
2.90
3.45
DVD cartridge
1900
3.0
3.15
3.70
TV keypad
1500
0.8
0.30
0.50
DVD keypad
1500
1.0
0.55
0.70
BA 452 Lesson B.5 Binary Indicator Variables
34
Make or Buy with Fixed Cost
Formulate a linear program to determine the optimal
production and purchase of each subassembly.
BA 452 Lesson B.5 Binary Indicator Variables
35
Make or Buy with Fixed Cost
Answer: A mixed integer linear program can be set up to
solve this problem. Binary variables are used to indicate
whether or not we setup to produce the subassemblies.
 SB = 1 if bases are produced; 0 if not
 STVC = 1 if TV cartridges are produced; 0 if not
 SVCRC = 1 if VCR cartridges are produced; 0 if not
 STVP = 1 if TV keypads are produced; 0 if not
 SVCRP = 1 if VCR keypads are produced; 0 if not
BA 452 Lesson B.5 Binary Indicator Variables
36
Make or Buy with Fixed Cost
Continuous variables are used for the number of units
made or purchased.










BM = Number of bases made
BP = Number of bases purchased
TVCM = Number of TV cartridges made
TVCP = Number of TV cartridges purchased
VCRCM = Number of VCR cartridges made
VCRCP = Number of VCR cartridges purchased
TVPM = Number of TV keypads made
TVPP = Number of TV keypads purchased
VCRPM = Number of VCR keypads made
VCRPP = Number of VCR keypads purchased
BA 452 Lesson B.5 Binary Indicator Variables
37
Make or Buy with Fixed Cost
Minimize cost
(manufacturing cost)
0.4BM+2.9TVCM+3.15VCRCM+0.3TVPM+0.55VCRPM
(purchase cost)
+0.65BP+3.45TVCP+3.7VCRCP+0.5TVPP+0.7VCRPP
(setup cost)
+1000SB+1200STVC+1900SVCRC+1500STVP+1500SVC
RP
BA 452 Lesson B.5 Binary Indicator Variables
38
Make or Buy with Fixed Cost
Demand constraints
1) BM+BP=12000
2) TVCM+TVCP=7000
3) VCRCM+VCRCP=5000
4) TVPM+TVPP=7000
5) VCRPM+VCRPP=5000
BA 452 Lesson B.5 Binary Indicator Variables
39
Make or Buy with Fixed Cost
Manufacturing time constraint (in minutes)
6) 0.9BM+2.2TVCM+3VCRCM+0.8TVPM+1VCRPM <
30000
Setup indicators (given demand constraints)
7) BM-12000SB < 0
8) TVCM-7000STVC < 0
9) VCRCM-5000SVCRC < 0
10) TVPM-7000STVP < 0
11) VCRPM-5000SVCRP < 0
BA 452 Lesson B.5 Binary Indicator Variables
40
Make or Buy with Fixed Cost
The Management Scientist can solve this mixed integer
linear program of 5 binary variables and 10 continuous
variables.
BA 452 Lesson B.5 Binary Indicator Variables
41
Relational Constraints
Relational Constraints
BA 452 Lesson B.5 Binary Indicator Variables
42
Relational Constraints
Overview
Relational Constraints such as “either project i or project j is
completed” or “both project i and project j are completed”
can be written as linear constraints in binary indicator
variables.
BA 452 Lesson B.5 Binary Indicator Variables
43
Relational Constraints





Binary variables can allow mathematical formulations of
some intricate verbal descriptions.
Let xi and xj represent binary variables designating
whether projects i and j have been completed (1 means
completed, 0 means not completed).
The constraint “either project i or project j is completed”
is formulated xi + xj > 1. In particular, xi + xj > 1 if both
projects are completed (both variables equal 1)
That is the standard use of “or” in quantitative or
mathematical work. It is the inclusive “or”.
For another example, if you are told “your friend is either
at the snack bar or on the tennis court”, then you are told
the truth if your friend is on the tennis court.
BA 452 Lesson B.5 Binary Indicator Variables
44
Relational Constraints





The constraint “either project i or project j is completed,
but not both” is formulated xi + xj = 1. In particular, xi + xj
= 1 is false if both projects are completed (both variables
equal 1).
The relation “xi + xj = 1” is sometimes called the
exclusive “or”.
There is debate over whether the English word “or” is
inclusive or exclusive.
Some say “you may have coffee or tea” is an example of
an exclusive “or”. But it turns out that “or” is not a logical
or at all because “you may have coffee or tea” is not
considered true if you can only have coffee.
In this class, “or” will only mean the inclusive “or”.
BA 452 Lesson B.5 Binary Indicator Variables
45
Relational Constraints
Summary
Let xi be a binary variables that is 1 if project i is done; xj likewise.
 xi + xj = 1 means “either project i or project j is done, but not both”
 xi + xj < 1 means “project i and project j are not both done”
 xi + xj < 1 means “project i and project j will not both be done”
 xi + xj > 1 means “at least one of project i or project j is done”
 xi < xj means “if project i is done, then project j is done”
 xi > xj means “project i is done if project j is done”
 xi < xj means “project i is done only if project j is done”
 xi = xj means “project i is done if, and only if, project j is done”
 xi < xj means “project i will not be done unless project j is done”
 xi < xj means “project i will not be done unless project i and project j
are done”
BA 452 Lesson B.5 Binary Indicator Variables
46
Relational Constraints
Question: Springer Verlag, a publisher of college textbooks,
must decide which new books to adopt and publish next
year. The books under consideration are described in the
first column below, along with their expected three-year
sales in the second column:
Book
Sales
Business Math
20
Finite Math
32
General Statistics
17
Mathematical Statistics 10
Business Statistics
25
Finance
18
John
12
9
16
7
8
X
Susan
40
24
X
X
X
X
BA 452 Lesson B.5 Binary Indicator Variables
Monica
X
X
30
24
16
14
47
Relational Constraints
Three individuals in the company can be assigned to these
projects, all of whom have varying amounts of time
available. John has 60 days, Susan has 52 days, and
Monica has 43 days. The days required by each person to
complete each project are showing in the third, fourth, and
fifth columns above. For example, if the business calculus
book is published, it will require 30 days of John’s time and
40 days of Susan’s time. (X means 0 time.)
BA 452 Lesson B.5 Binary Indicator Variables
48
Relational Constraints
Springer Verlag will not publish more than two statistics
books in a single year. And one of the math books must be
published, but not both. And the business math will be
published only if the finance is published. And the general
statistics will be published if the finite math is published.
And the mathematical statistics and the finance will not
both be published.
Formulate a model to decide which books should be
published to maximize sales.
BA 452 Lesson B.5 Binary Indicator Variables
49
Relational Constraints
Answer:
where 1 is the business calculus book, 2 is the finite math
book, … .
Here is a binary programming model for maximizing
projected sales (thousands of units) subject to the
restrictions mentioned.
BA 452 Lesson B.5 Binary Indicator Variables
50
Relational Constraints
Max
20x1
+ 32x2 + 17x3 + 10x4
+
25x5
+
8x5
+
18x6
s.t.
12x1 +
9x2 + 16x3 +
7x4
40x1 + 24x2
30x3 + 24x4
x3 +
x1 +
x4
+
16x5
+
x5
+
14x6
x2
x1
x2
-
x6
x3
x4
+
x6
<
60 John
<
40 Susan
<
40 Monica
<
2 No. of Stat Books
=
1 Math Book
<
0 Only if
<
0 If
<
1 Not both
BA 452 Lesson B.5 Binary Indicator Variables
51
Capital Budgeting
Capital Budgeting
BA 452 Lesson B.5 Binary Indicator Variables
52
Capital Budgeting
Overview
Capital Budgeting Problems maximize the net present
value or net return from a selection of projects that each
require a fixed amount of capital. Relational constraints are
often imposed.
BA 452 Lesson B.5 Binary Indicator Variables
53
Capital Budgeting
Question: Fry’s Electronics is planning to expand its sales
operation by offering new electronic appliances. The
company has identified seven new product lines it can
carry.
Initial Floor Space Exp. Rate
1.
2.
3.
4.
5.
6.
7.
Product Line
Invest.
(Sq.Ft.)
TV/VCRs
TVs
Projection TVs
VCRs
DVD Players
Video Games
Home Computers
$ 6,000
12,000
20,000
14,000
15,000
2,000
32,000
125
150
200
40
40
20
100
of Return
8.1%
9.0
11.0
10.2
10.5
14.1
13.2
BA 452 Lesson B.5 Binary Indicator Variables
54
Capital Budgeting
Fry's has decided that they should not stock projection
TVs unless they stock either TV/VCRs or TVs. Also,
they will not stock both VCRs and DVD players, and
they will stock video games if they stock TVs. Finally,
the company wishes to introduce at least three new
product lines.
If the company has $45,000 to invest and 420 sq. ft. of
floor space available, formulate an integer linear
program for Fry's to maximize its overall expected
return.
BA 452 Lesson B.5 Binary Indicator Variables
55
Capital Budgeting

Define the Decision Variables
= 1 if product line j is introduced;
xj
= 0 otherwise.
Product line 1 = TV/VCRs
Product line 2 = TVs
Product line 3 = Projection TVs
Product line 4 = VCRs
Product line 5 = DVD Players
Product line 6 = Video Games
Product line 7 = Home Computers
BA 452 Lesson B.5 Binary Indicator Variables
56
Capital Budgeting

Define the Objective Function
Maximize total expected return:
Max .081(6000)x1 + .09(12000)x2 +
.11(20000)x3 + .102(14000)x4
+
.105(15000)x5 + .141(2000)x6
+
.132(32000)x7
1.
2.
3.
4.
5.
6.
7.
Invest. Space Return
$ 6,000 125
8.1%
12,000 150
9.0
20,000 200 11.0
14,000 40
10.2
15,000 40
10.5
2,000 20
14.1
32,000 100
13.2
BA 452 Lesson B.5 Binary Indicator Variables
57
Capital Budgeting
1.
2.
3.
4.
5.
6.
Constrain total investment by $45,000:
6x1 + 12x2 + 20x3 + 14x4 + 15x5 + 2x6 + 32x7 < 45
Constrain space by 420 square feet: 125x1 +150x2
1.
+200x3 +40x4 + 40x5 + 20x6 + 100x7 < 420
2.
Stock projection TVs only if stock TV/VCRs or TVs:3.
x1 + x2 > x3 or x1 + x2 - x3 > 0
4.
5.
Do not stock both VCRs and DVD players:
6.
x4 + x 5 < 1
7.
Stock video games if they stock TV's: x2 - x6 < 0
Introduce at least 3 new lines:
x1 + x2 + x3 + x4 + x5 + x6 + x7 > 3
Invest. Space Return
$ 6,000 125
8.1%
12,000 150
9.0
20,000 200 11.0
14,000 40
10.2
15,000 40
10.5
2,000 20
14.1
32,000 100
13.2
BA 452 Lesson B.5 Binary Indicator Variables
58
Capital Budgeting

Interpretation:
Introduce:
TV/VCRs, Projection TVs, and
DVD Players
Do Not Introduce:
TVs, VCRs, Video Games, and
Home Computers
Total Expected Return:
$4,261
Surplus:
$4,000 Investment
55 square feet of space
BA 452 Lesson B.5 Binary Indicator Variables
59
BA 452
Quantitative Analysis
End of Lesson B.5
BA 452 Lesson B.5 Binary Indicator Variables
60

similar documents