.

Lecture 1 Linear programming formulations

Reddy Mikks produces both and paints from two raw mate ext int eri ria erior ls
n
r
d
o
a
,
Problem Statement
A B nd a .

A B

Tons of raw material per ton of paint
Basic data


Maximumdaily


( )
,

Exterior paint Interi paint
Raw materi
or
al

Maximum daily
availabilit tons y
6 A 24 4
,
( )
Raw material
Profit per ton
1 B 6
$1000


2
5 4
A market survey indicates that the daily demand for paint cannot
exceed that of paint by more than
interio
exter o
r
i r

ton
Al th i d il d d f i t i t i t i 2
. 1
optimum
Also, the maximum daily demand of paint is tons.
Reddy wants to determine the (b
exteri
est) product mix of and
paints that maximizes the
i
t
nterior
interior
otal daily prof or it
2

. exteri paints that maximizes the total daily prof or it
Tons of raw material per ton of paint
B asic data
Equation Form
Tons of raw material per ton of paint
( )
,
paint paint tons
Raw material
Max d Exterior
6
Interi
A
a

ily

availabil

i

or y
4
t

,
( )

1 Raw material
24
B 6
$1000

P fit t
2
5 4 ( ) $1000 Profit per ton
* : To determine the amounts to be produced of and
paints. interio
exterio
r
r Decision variables
5 4
tonsproduceddailyof paint exterior x
p
tons produced daily of paint
interior tons produced daily of paint
* ( ) : The company wa
exterio
nts to in
r
Objective aims optimize to
2
1
x

goal
x =
=
crease its profit as ( ) p y j p g p
much as possible.
represents the total daily profit in thousands of dollars

1 2
5x Maximize x z
z
4 = +
* : Restr Constraints ict raw materials usage and demand
Usage of a raw material by both paints Maximum available raw material
(R t i l )
s
s 4 6 A 24 (Raw material )

s
1 2
4 6x A x 24 +
(Raw material )
- (Demand Limit)
s
s
1 2
2 1
x
x
6 B
1
2x
x
+
+ ( )

2 1
(Demand Limit)
: , .
s
> Nonnegativity restrictions
2
2 1

x


2
0 x
x
. Two variables problem 1
tons per day
tons per day,
Let
1
2

x 1
x 3

=
=
,
p y
then ( ) is a feasible solution, at which the
hasvalue
objective
function
1
2
2
x x = x
has value

function
2 1
4x 4 x 1 5 z 5 3 = + = + (thousand dollars) 19 =
( , ) an optimal solution ?
the feasiblesolutionthat yieldsthemaximum optimum
Is
Find
1 x 3 =
the feasible solution that yields the maximum
total profit while satisfying all the constrai
optimum
nts

.
Find
G h ll i i l di i i i i
Graphical Method
Solu space consists of infinity of poin feasible ti ts on
Graph all constraints, including nonnegativity restrictions


Identify corner points of feasib the so l lution space e
optimumsolut Candidates for the are given by a finite
number of corner poin
io
ts
n
de y co e po s o e s b e so u o sp ce e


number of corner points
U e s optimu the function to determine the corner objecti e m v U e s optimu the function to determine the corner
point from among all the
objec
candi
ti
d
e m v
ates
: determinate Graphical procedure includes steps to
Graphical Solutio LP n
2

:
) The solution space that defines all feasible s
optim
olutions of the model
) The solution um from amon
determinate Graphical procedure includes steps to
1
2
2
g all the feasible points in the solution space p )

and for nonnegativity restrictions
g p p
: Determination of the Solution Spac Feasibl e e
2 1
0 x 0 x
Step 1
> > g y
Replace each inequality( ) with equations( )
2 1
s =
( )
2 2 1 1

6x 6x 4x 4x 24 24 1 + s + =

6 2
fi d
x

- -
(
( )
(
)
)
2 2
2 2
2 2
1 1
1 1
x x
x
2x 2x
x x
x 2 x 2
x

6

6
4
2

3 1 1

+ s + =
+ s + =
s =

5
4
first quadrant
points

Determine 2

, and , Let
1
1 1
2
2 2
6x
x x 4
4x
x 6 x
24
0 0
+ =
= = = =
4
3

, and ,
points: ( , ) and ( , ).
Let
Graph of eq ations
1 1 2 2
x x 4
2 4
x 6 x
6
0 0
0

0
2
1
Graph of equations
1
0
1 2 3 4 5 6

1
x
Reference point
Feasible Space

: ( , ). Convenient computationally

0 0
: select another point if the line passes
throughtheorigin ( )
Note
cannot use

0 0
Ex: 6x
1
+ 4x
2
24
Feasible half-space
through the origin, ( , ). cannot use 0 0
first quadrant
2
x

(0,0) 6 x 0 + 4 x 0 = 0 (0 24)
Not a feasible side
(6,0) 6 x 6 + 4 x 0 = 36 (36 24)
first quadrant
6
5
Constraints:
4
3
1
2
3
6x
1
+ 4x
2
24
x
1
+ 2x
2
6
1
l
3
2
3
4
5
-x
1
+ x
2
1
x
2
2
x
1
0
Solution
space

1
x
1 2 3 4 5 6
1
0
6
1
x
2
0
Feasible space of the Reddy Mikks model
1 2 3 4 5 6
Optimum Solution
Step 2: Determination of the Optimum Solution Step 2: Determination of the Optimum Solution
The feasible space consists of an infinite number of points
Optimum solution: identify the direction in which the profit function z =5x
1
+ 4x
2
increases (maximize z) Assign arbitrary increasing values to z increases (maximize z). Assign arbitrary increasing values to z.
Arbitrary increasing z values
z = 10 and z = 15
z = 5x
1
+ 4x 5x
1
+ 4x = 10 z = 5x
1
+ 4x
2
5x
1
+ 4x
2
= 10
5x
1
+ 4x
2
= 15
Values of x
1
and x
2
associated with the
optimum point
3
x
2
optimum point
6x
1
+ 4x
2
= 24 solve
x
1
+ 2x
2
= 6
simultaneously
x 3 nd x 1 5
2
3
x
1
= 3 and x
2
= 1.5
z = 21
Optimum:
x
1
+ 2x
2
6
x
1
= 3 tons
x
2
= 1.5 tons
1
x
1
6x
1
+ 4x
2
24
2
.5 tons
z = $21,000
0 1 2 3 4
x
1
Overview of the Steps
Develop equation form
*Decision variables
Determine the optimum
solution
Identify the direction Decision variables
*Objective function
*Constraints
Identify the direction
in which the profit
Function increases Fu
(maximize z)
Convert the
constraints () into
Determine the
solution space
equation forms (=)
Graph them including
th ti it
solution space
(the intersection areas
of the constraints +
the nonnegativity
constraints
the corner points)
Terminology for Solutions of the Model
Afeasible solution: asolutionfor whichall theconstraintsaresatisfied A feasible solution: a solution for which all the constraints are satisfied.
An infeasible solution: a solution for which at least one constraint is violated.
The feasible region: the collection of all feasible solutions.
It is possible for a problem to have no feasible solutions.
Maximize z = 3x
1
+ 5x
2
,
10
8
Maximize z 3x
1
5x
2
,
subject to x
1
4
2x
2
12
3x
1
+ 2x
2
18
3x
1
+ 5x
2
50
This problem would have
no feasible solutions if the
constraint 3x
1
+5x
2
50
were added to the problem
6
3x
1
+ 2x
2
18
3x
1
+ 5x
2
50
and x
1
0, x
2
0
2x
2
12
were added to the problem.
4
2
2x
2
12
3x
1
+ 2x
2
18
4
x
1
0
2
0 2 4 6 8 10
x
1
4
x
2
0
Introduction to Cases of Optimal Solution
that there are feasible solutions, the goal of linear
programming is to find a best feasible solution, as measured
Given
p g g ,
by the value of the objective function in the model.
: a feasible solution that has the
value of the objective function.
most
favorable
optimal An solution
: the largest value if the objective
functionisto
most f The avorab ue le val
be whereasitisthesmallest valueif maximized function is tobe , whereas it is the smallest value if
the objective function is to be
maximized
minimized.
Multiple Optimal Solutions
Mostproblemswillhavejustoneoptimalsolution.However,itispossibletohavemorethanone. Mostproblemswillhavejustoneoptimalsolution.However,itispossibletohavemorethanone.
Any problemhavingmultipleoptimalsolutionswillhaveaninfinite numberofthem,eachwith
thesameoptimalvalueoftheobjectivefunction.
z = 18 = 3x
1
+ 2x
2
Maximize z = 3x
1
+ 2x
2
,
subject to x
1
4
2x
2
12
3 2 18
z 18 3x
1
2x
2
This problem would have
multiple optimal solutions
if the objective function
(2 6)
3x
1
+ 2x
2
18
and x
1
0, x
2
0
if the objective function
were changed to
z = 3x
1
+ 2x
2
(2, 6)
(4 3)
Every point on this darker line segment
is optimal, each with z = 18.
(4, 3)
No Optimal Solutions
Another possibility is that a problem has no optimal solutions. This occurs only if (1) it Another possibilityisthataproblemhasnooptimalsolutions. This occursonlyif(1) it
hasnofeasiblesolutionsor(2) theconstraintsdonotpreventimprovingthevalueof
theobjectivefunctionz indefinitelyinthefavorabledirection(positiveornegative).
The latter case is referred to as having an unbounded z or an unbounded objective The lattercaseisreferredtoashavinganunbounded z oranunboundedobjective.
(4, ), z =
(4, 10), z = 62
Maximize z = 3x
1
+ 5x
2
,
subject to x
1
4
and x
1
0, x
2
0
The problem would have no
optimal solutions if the
only functional constraint
(4, 8), z = 52
(4, 6), z = 42
F ibl
were x
1
4, because x
2
then could be increased
indefinitely in the feasible
re i n ith ut ever
(4, 4), z = 32
Feasible
region
region without ever
reaching the maximum
value of z = 3x
1
+ 5x
2
(4, 2), z = 22
CPF & A Thought Question
Acornerpointfeasible(CPF)solution: asolutionthatliesatacornerofthefeasibleregion.
Example: Thepoints(0,0),(0,6),(2,6),(4,3),and(4,0)inthefollowingfigureareCPFsolutions.
Relationshipbetween optimalsolutions and CPFsolutions: Consideranylinearprogramming
problemwithfeasiblesolutionsandaboundedfeasibleregion.
The problemmustpossessCPFsolutions andatleastoneoptimalsolution.
Furthermore,thebestCPFsolution must beanoptimalsolution.Thus,ifaproblemhasexactly
oneoptimalsolution,itmust beaCPFsolution.
If h bl h l i l i l l i l b CPF l i If theproblemhasmultipleoptimalsolutions,atleasttwomust beCPFsolution.
Athoughtquestion: thinkabout howthegraphicalmethodleadstotheoneoptimalsolution
beingaCPFsolution.
The five dots are the
five CPF solutions
Feasible
region region
Some thoughts
of the Reddy Mikks model: , and
:a daily product mix of tons of exterior paint


Conclusion
Optimal solution
1 2
x 3 x 1.5 z 21
3
= = =
yp p
and tons of interior paint .
p
The
1.5
associateddailyprofitis$21 000 The associated daily profit is
the Reddy Mikks model : change the slope of the profit
f i ( ) h i l i l
, .

h i ffi i
In
$21 000
function ( ) the optimum solution always
occurs at one of these corner points
change its coefficients ,
.
z
is the key to the development of the general simplex algorithm
programming( )appliestooptimizationmodels
. This
Linear LP
.
programming( )applies to optimization models
in which the objective and constraint functions are strictly linear
Linear LP
ProblemStatement Bank Loan Policy
2. Multiple variables problem
bank is in the process of formulating a loan policy involving
atotal of million afull -servicefacility theban

Problem Statement Bank Loan Policy
The ABC
Being $12 kisobliged a total of million a full -service facility, the ban . Being $12 k is obliged
to grant loans to different clientele
following table provides the types of loans, the interest rate charged
.
The g p yp , g
by the bank, and the probability of bad debt from past experience:
Basic data
Type of loan Interest rate Probability of Bad Debt
Personal
Car
H


0.140 0.10
0.130 0.07
0 120 0 03 Home 0.120
Farm
Commercial
0.03
0.125 0.05
0 100 0 02 Commercial 0.100 0.02
d bt d bl dh i t t B d
Bank Loan Policy - Con.
debts are assumed unrecoverable and hence no interest
revenue

.
Bad
with other financial institutions requires that
the bank allocate at least of the total funds to


Competition
40% farm and
i l l commercial loans.
assist the housing industry in the region, home loans must To
equal at least of the personal, car and home loans.
bank also has a stated policy specifyingthat the

The
50%
overall p y p y g
ratio for bad debts on all loans may not exceed . 0.04
Mathematical Model
should funds be allocated to these typesof loans
to maximize the net rate of return?
How
Solving procedure includes steps
th i bl f d l f ll D fi i

S
. LP 3
t 1 the variables of model as follo : ws Defining S tep 1
personal loan ( ) in million dollars
1
x = p ( )
car loan
homeloan
1
2
x
x
=
= home loan
farm loan
3
4
x
x
=
=
commercial loan
5
x =
theobjectivefunction : Writing
Mathematical Model
Step 2 the objective function
net returns for the types of loans can be written as
:

Writing
The


Step 2
:
:
Personal
Car
1 1 1
0.14 0.9 0.1 0.026

x x x =

2 2 2
x x x 0.13 0.93 0.07 0.0509 =
:
:
Home
Farm

3 3 3
4 4 4
x x x 0.12 0.97 0.03 0.0864
x x x 0.125 0.95 0.05 0.06875


=
=
: Commercial
4 4 4
5
0.1 0 x .98
b dd bt d bl b th i i l Si
5 5
x x 0.02 0.078 =
bad debts are assumed unrecoverable, both as principal
and interest, the objective function can be written as
Since
M i

14 9 13 93 12 97 125 95 i
1 2 3 4
Maxi z x x .14 .9 .13 .93 .12 .97 .125 . x x 95 mize + + +

=
5 1 2 3 4 5
.1 .98 .1 .07 .03 .05 .02 x x x x x x +
1 2 3 4 5
.026 .0509 .0864 .06875 .078 . x x x x x + + + + =
problemhasfiveConstraintsasfollow : s The
Mathematical Model
Ste 3 p problem has five Constraints as follow : s The
Total funds
1 2 3 4 5

1. 12 x x x
Ste
x x
3 p
+ + + + s
Farm and Commercial loans
Home loans
4 5
2. .4 12 4.8
3
x x + > =
( ) 5 x x x x > Home loans 3.

( )
Limit on bad debts

3 1 2 3
.5
4.
x x x x + + >

1 2 3 4 5
1 2 3 4 5
.1 .07 .03 .05 .02
.04
x x x x x
x x x x x
+ + + +
+ + + +
s
, Nonnegativity
1

5. 0 x > , , ,
2 3 4 5
0 0 0 x x x x 0. > > > > , Nonnegativity
1
5. 0 x > , , ,
2 3 4 5
0 0 0 x x x x 0. > > > >
The LP Formulation
M i i 026 0509 0864 06875 078

1 2 3 4 5
Maximize
Subj
x x x x x .026 .0509 .0864 .06875 .078
ect to
+ + + +

1 2 3 4 5
x x x x x
x x
12
4 8
+ + + + s
s

4 5
1 2 3
x x
x x x
- - - 4.8
.5 .5 -.5 0 +
s
s
.06
, , , ,
1 2 3 4 5
1 2 3 4 5
.03 - .01 .01 - .02 0
0 0 0
x x x x x
0 0 x x x x x
+ + s
> > > > > , , , ,
1 2 3 4 5

personal loan
Optimal Solution
x 0 0

personal loan
car loan
1
2
x

0.0
x 0.0
=
=
home loan
3
x =
farm loan
4
x
7.2
0.0 =
( ) Max ObjectiveValue
commercial loan
Optimal Value
5
4.8 x
0 9965
=
( ) Max Objective Value Optimal Value 0.9965
Two Variables Problem
3 5
Maximize
Subject to
.0864 .078 x x +


3 5
5
12
- - 4.8
x x
x
+ s
s
,
5
3 5
x 0 x 0 > >
Bus Scheduling Problem Example 1.1
Cit i t d i th f ibilit f i t d i

P
Problem Statement
City is studying the feasibility of introducing
a mass transit bus systemthat will alleviate the smog
Progress
problemby reducing in-city driving.
initial studyseeksthedeterminationof theminimum The initial study seeks the determinationof the minimum
number of buses that can handle the transportation needs.
The
city engineer found that the requirednumber of
bus
The
es can be assumed constant over successive intervals
of hours each. 4
wasdecidedthat tocarryout therequireddailymaintenance
summarizes the engineer's findings.
It
Figure 1
.
was decided that to carry out the required daily maintenance,
each bus could operate only successive hours a day
It
8
Figure
10
12
10
12
14
s
e
s
4
8
7
4
6
8
10
b
e
r

o
f

b
u
s
4 4
0
2
4
N
u
m
0
0
12:00 4:00 8:00 12:00 4:00 8:00 12:00
A.M. Hour of the day Midnight
Mathematical Representation
aim of this study is to minimize the total number
of daily buses in operation (objective) by determining
The
y p ( j ) y g
the number of buses to operate during different shifts
(variables) that meet the minimum demand (constraints). ( ) ( )
solving bus scheduling problem by : Additional LP 3 steps
decision variables (What are you choosing?)
objective function
Define
Write j
const Write raints
ashiftisallowedtostartevery hours( variables) and If 4 6 a shift is allowed to start every hours ( variables) and
continues for consecutive hours, we mayget a better solution.
illustratesthisconcept where(overlapping)shifts
If 4 6
8
Figure 2 illustrates this concept where (overlapping) shifts
may star
Figure 2
t at
: 12 01 a m :
:
12 01 a.m.
4 01 a.m.
8 01 :
:
8 01 a.m.
12 01 p.m.
4 01 :
:
4 01 p.m.
8 01 p.m.
with each shift continuing
for consecutivehours. 8 for consecutive hours. 8
Mathematical Representation
can now define the variables as follows: We
p
6
number of buses starting at
number of busesstartingat
:
:
1
12 01 a.m.
4 01 a
x
x m
=
= number of buses starting at
number of buses starti


:
2
3
4 01 a x .m.
x
=
= ng at : 8 01 a.m.
number of buses starting at
number of busesstartingat
:
:
4
12 01 p.m.
4 01 p m
x
x
=
= number of buses starting at
number of buses starting at

.
:
:
5
6
4 01 p.m.
8 01 p
x
x .m.
=
=
a : nd Step 2 Step 3
objective function and constraints Writing
p p

1 2 3 4 5 6
minimize
s
z x x x x x x
ubject to
= + + + + +
( )

: :
6 1
1 2
x x 4
x x
j
12 01 a.m. - 4 00 a.m.
8
+ >
+ > ( ) : : 4 01 a.m. - 8 00 a.m.
1 2
( )
( )
( )
: :
: :
2 3
x x 10 8 01 a.m. - 12 00 noon
12 01 p m - 4 00 p x x 7 m
+ >
+ > ( )
(
: :
:
3 4
4 5
12 01 p.m. - 4 00 p x x 7
x x 1
.m.
4 2 01 p.m.
+ >
+ > ) : - 8 00 p.m.
8 01 12 01 4 > ( )
. , , , ,
: :

5 6
i
8 01 p.m. - 12 01 x x 4
x 0 j 1
a.m
2
.
6
+ >
> =
Optimum Solution Summary
A total of buses is needed to satisfy the demand.
The optimum schedule calls for
26
buses to start at
at
,
,
:
:
1
2
4
10
12 01 a.m.
4 01 a.m.
x
x
=
=
at
,
,

:
2
4
5
8
4
12 01 p.m. x
x
=
= at . :
3 6
, 4 01 p x x .m. 0 0 = =
5 3 6
p
other solutions: Find
Land Use and Development Example 1.2
Birdeyes Real Estate Co. owns acres of prime, The
Problem Statemen t
800 deyes ea stateCo.ow s ac eso p e,
but undeveloped, land on a scenic lake in the heart of the
Ozar
e 800
kMountains. Ozark Mountains.
lake shores are lined with clustered vacation homes. The
of the lack of sewage service, over the years,
seepage from the septic tanks has resulted severe ina
Because
water pollution r p ob .
curb further degradation in the quality of water,
lem
To g q y ,
county officials introduced and approvedsome stringent
ordinancesapplicabletoall futuredevelopme . nts ordinances applicable to all future developme . nts
Only single-, double-, and triple-familyhomes can be 1. y g , , p y
constructed, with the single-family homes accounting for
at least of the total. 50%
To limit the number of septic tanks, minimum lot sizes
o

%
2.
f and acresarerequiredfor single double and 2 3 4 of and acres are required for single-, double-, and
triple-family homes.
, , 2 3 4
Recreation areas of acre each must be established at
the rate of one area per families.
1
200
3.
To preserve the ecolog 4. y of the lake, underground water
maynot bepumpedfor houseor gardenuse may not be pumped for house or garden use.
id f i d l i d i h ibili
Problem Statemen on t - C 1
president of Birdeyes Real Estate is studying the possibility
of developing the company's acres on the lake.
d l ill i l d i
The
Th
800
l d bl d i l new development will include sing The le-, double-, and triple-
family homes.
ti t th t f th ill b di th H 15% estimates that of the acreage will beconsumed in the
opening of streets and easements for utilities.
l ti t hi t f th diff t h
He
H
15%
i it also estimates his returns from the different hous He ing units:
cost of connectingwater servicetotheareaisproportionate The
Problem Statement - Con 2
cost of connecting water service to the area is proportionate
to the number of units constructed
thecountystipulatesthat aminimumof
.
The
However $100,000 must the county stipulates that a minimum of , However $100,000 must
be collected for the project to be economically feasible
the expansion of the water system beyondits present
.
, Additionally p y y p
capacity is limited to gallons per day during peak periods.

,

y
Th
200,000
following data summarize the cost of connecting water service e
as well as the water consumption assuming an average size family:
Mathematical Model
company must decide on the number of units to be
constructed of each housing type together with the number
The
of recreation areas satisfying county ordinances.
Defi e n
b f i f i l f il h number of units of single-family homes
number of units of double-family homes


1
2
x
x
=
=
number of units of triple-family homes
number of recreatio


3
4
x
x
=
= n areas
4
objective of the company is to maximizetotal return.
objectivefunction isthusgivenas
The
The objective function is thus given as

The
1 2 3
z 10000x 12 maximize 000x 15000x = + +
The constraints of the problem include
Limit on land use 1.
2x 3x 4x 1x 6 0 8 s + + + .
Limit on the requirements for single-family
1 2 3 4
2x 3x 4 x 1x 6
2.
0

8 s + + +
homes relative to other styles
1
x
0 5 0 5 0 5 0 5 0 > > or
i i h i f i
.
1
1 2 3
1 2 3
x
0.5 0.5x 0.5x 0.5x 0
x x x
3
> >
+ +
Limit on the requirements for recreationareas
1 2 3
x 2x 3x
3.
200 2 3 0

+ +
or .
1 2 3
4 4 1 2 3
x 2x 3x
x 200x x 2x 3x 0
200
s >
+ +

The constraints of the problem include
Capital requirement for connecting water service
p
4.
.
Limitonpeak perioddailywater consumption
1 2 3 4
1000x 1200x 1400x 800x 100000
5
> + + +

Limit on peak- period daily water consumption
1
5.
0 40 x .
2 3 4
600x 840x 450x 200000 s + + +
1
Nonnegati y vit
2 3 4
6.
. , , ,
1 2 3 4
x 0 x 0 x 0 x 0 > > > >
: The impact of computational round off error
Discussion and Results
( )
the model above, you will notice that the coefficients in
constraints and are
:
it l d t ti
In
The impact of computational round - off error
4 5 relatively ( ) constraints and are capital and water consumption 4 5 relatively
larger than most of the coefficients in constraints , and
i i t l dt d i bl hi d
.
Thi
1 2 3
inconsistency may lead to undesirable machine round
-off error resulting from the mixed manipulation of relatively
largea
This
ndrelativelysmall coefficientsinthesameproblem large and relatively small coefficients in the same problem.
our present example, we can rectify this potential problem
b li d ll th ffi i t f h t i t b th
In
by scaling down all the coefficients of each constraint by the
constant .
Thi
1000
d h i re This duces the constraints to
.
1 2 3 4
1x 1.2x 1.4x 0 .8x 100 > + + +
.
1 2 3 4
.4x .6x .84x .45x 200 s + + +
and Discussion Results
notice that linear programming does not provide
integer solutions in general.
We
present solution yields
and
The
SINGLE RECR'N 339 152 1 696 and SINGLE RECR'N 339.152 = =
with DOUBLE
1.69
TRIPLE
6
0. = =
practical purposes, we can round this solution to
and
For
339 SINGLE RECR'N 2 = = and
(

which, incidentally, happens to be the optimum integer
l
339 SINGLE RECR'N 2 = =
) solution).
ti l ti d t dth t ti f
Analysis of optimum solu
Th
tion
optimum solution does not recommend the construction of
double and triple homes, despite the fact that their returns per
it( d )
The
$12 000 $15 000 hi h i b l t th unit( and ) are $12,000 $15,000 higher in absolute sense than
that for a single home.
result shows that the marginal returns as expressed in
the objective function are not sufficient to judge the profitability
This
of an activity.
must additionally consider the cost of the resources used by We
the activity.
, in order for either activity to be just profitable, we must Thus, y j p ,
either reduce the per unit cost of the resources or increase the
marginal return by an amount equal to its reduced cost. g y q
Trim- Loss or Stock-Slitting Pr
Problemstat
obl
ement
em Example 1.3
Pacific Paper Company produces paper rolls with a standard
widthof feeteach
The
Proble m stat ement
20 width of feet each.
customer Special
20
orders with different widths are produced by
slitting the standard rolls.

g
orders( ) are summarized
in the following table:
which may vary from day to day Typical
practice anorder isfilledbysettingtheslittingknivestothedesired In
Problem statement - con
practice, an order is filled by setting the slitting knives to the desired
widths.
thereareanumber of waysinwhichastandardroll canbeslit
In
Usually

there are a number of ways in which a standard roll can be slit
to fill a given order.
Usually
shows three possible knife settings for the - foot roll . Figure 1 20 p g
here are other feasible settings, we limit the discussion for
the moment to considering settings , , and in
t
.
Although
g
A B C Figure 1
can combine the given Settings in a number of ways to fill orders
for widths , , and feet .
We
5 7 9
following are two examples of feasible combinations:
Slit ( ) rolls using setting standard
The
1 0 . 30 Aand rolls using . 75 B
Slit rolls using setting and rolls using setting
combination is better? can answer this question by
id i h h h bi i

ill
.

" "
Which We
2. 200 A 100 C
d considering the that each combination will " " waste produce.
, the shaded portion represents surplus rolls not wide In Figure 3
enough to fill the required orders.
surplus rolls are referred to as . These trim loss



thesurplusrollsmayhavedifferent Since


widths weshould the surplus rolls may have different Since widths, we should
base the evaluation on the area of trim loss rather than the
number of surplusrolls number of surplus rolls.
assuming that the standard roll has a length feet,
ecancomp tethetrim lossareaasfollo s
, Thus L
we can compute the trim- loss area as follows
: ( ) ( ) ft
2
300 4 L 75 3 L 1425L Combination 1 + =
: ( ) ( ) ft
T

2
200 4 Comb L 100 1 inati L 900 on 2 = L +
areasaccountonlyfor theshadedportionsin hese Figure 1 T areas account only for the shaded portions in . hese Figure 1
however that any surplus production of the and oot rolls
mustbeconsideredinthecomputationof the area
, , , f Note
trim loss
5 7 9
must be considered in the computation of the area
in setting will produce a surplus of
.
, , Thus
trim- loss
combination 1 A 300 - 200
extra footrollswhilesetting will produce extra footrolls 100 7 B 75 7 = extra foot rolls while setting will produce extra foot rolls
the additiona area is ( ) ft
doesnotproducesurplusrollsof the and footroll
.
l " " Thus
2
wast
100 7 B 75 7
175 7 L e 1225L
7 9
=
Combination2
=
s does not produce surplus rolls of the and foot roll 7 9 Combination 2 s
however, does produce extra foot rolls, with
an addedwastearea
( ) ft
.
, Setting
2
C 200 150 50 5 -
50 5 L 250L
=
an added waste area
( ) ft
2
= 50 5 L 250L
t i l f ft T t l
As a result we have
2
C bi ti 1 + 1425L 1225L 1650L

trim loss area for : ft
trim loss area for : ft
Total
Total


2
2
Combination 1 + =
Combination 2 +
1425L 1225L 1650L
900L = 250L 1150L
is thus better because it yields a Combination 2 smalle area
obtain the optimum solution to the problem, it would be necessary
r .
To
trim loss
p p , y
first to determine all possible knife settings and then generate all the
feasible combinations.
the Although determination of all the settings may not be too difficult,
generating all feasible combinations may be a formidable task.
need for a systematic approach is thus eviden
is what the
t.

The
This LP model will accomplish. p
( ) seek to determine the knife setting combinations that will We
Mathematical Representation
variables

( ) ( ) fill the required orders with the least area
definitio
.
The
constraints objective trim loss
n of the variables as given must be translated in a way that
themill operator can se the mill operator can use
studying the way we constructed the two combinations, we note that
thevariablesshouldbedefinedasthenumb
.
By
er of standardrollstobeslit the variables should be defined as the number of standard rolls to be slit
according to a given knife setting
definition obviously requires identifying all possible knife settings as
.
This y q y g p g
summarized in the following . table
Mathematical Representation
and are given in
in mind that a promising setting cannot yield a roll of
, .

Settings
Keep
p

t
1 2 3 Figure 3
rim l s os in mind that a promising setting cannot yield a roll of
width feet or higher
express the model mathem

.

Keep
To
trim l s
5
os
atically, we define the variables as p y,
number of standard rolls to be slit according to setting ... .
constraintsof themodel deal directlywithsatisfyingtheminimum
, , ,
The
j
x j 1 6 = j =
constraints of the model deal directly with satisfying the minimum
number of rolls
The
ordered
if all thesettingsexhibitedinthetableareused weget
.
Thus if all the settings exhibited in the table are used we get

, , Thus
2 3 4 5
number of - ft rolls produced
number of ft rolls pro
5 2x 2x 4x x
7 duced x x 2x
= + + +
= + +
1 2 5
number of - ft rolls pro 7 duced
number o
x x 2x
9 f - ft rolls pro
= + +
1 3 6
duced x x 2x = + +
Mathematical Representation
general model may thus be written as The
minimize z x x x x x x = + + + + +
1 2 3 4 5 6
minimize
subject to
z x x x x x x = + + + + +
( )
2 3 4 5
2x 2x 4x x - ft r 150 5
x x
olls

+ + + >
+ ( ) 2x 200 7 ft rolls + >
1 2
x x + ( )
( )
5
1 3 6
2x 200 7
x x 2x 300 9
- ft rolls
- ft rolls


+ >
+ + >
... . , , , ,
j
x 0 j 1 2 6 = >

thefollowingtable: ) Using
Exercise of Trim- Loss
a

the following table: ) Using

a
express each of the following feasible solutions in terms of To
the variables and compute the area in each case
( ) rolls using s
.

j
trim los
200
s
1
x
etting and rolls using setting . 1 100 3 ( ) g g g g
[ area ft ]
( ) rolls using setting rolls using setting and rolls
. , , .
, ,
Ans
1 3
2
trim los x 200 x 100 1150L
50 2 75 5 50
s
2 1
= = =
( ) g g g g
using setting
[
, ,
.
Ans
6
area ft ]
2
2 5 6
tri x 50 x 75 x 150 6 ml s L o s 50 = = = = [ . Ans area ft ] , , , .

2 5 6
tri x 50 x 75 x 150 6 m l s L o s 50
the following table:
that theonlyavailablestandardroll is feet wide
) Using
Suppose
b
15 that the only available standard roll is feet wide.

Suppose 15
generate all possible knife settings for producing and
f t ll d t th i t d
, To 9 5 7
t f tl th i l foot rolls and compute the associated t per foot length
[ Settings: ( ) ( ) ( ) and( )
f f h f i ( ) ]
.
. , , , , , , , , , , . Ans 3 0 0 0 2 0 1 1 0 1 0 1
0 1
rim loss
T i 3 l 1 per foot for the four settings: ( ) ] , , , . 0 1 Trim 3 l 1 oss