ECE 307 – Techniques for Engineering

Decisions
Introduction to Linear Programming

George Gross
Department of Electrical and Computer Engineering
University of Illinois at Urbana-Champaign

ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 1
 OUTLINE

‰ The nature of a programming or optimization

problem

‰ The salient characteristics of a linear

programming (LP) problem

‰ The LP problem formulation

‰ The LP problem solution

‰ Extensive illustrations with numerical examples

ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 2
 EXAMPLE 1: HIGH/LOW HEEL SHOE
CHOICE PROBLEM
‰ You are headed to a party and are trying to find a
pair of shoes to wear; you choice is narrowed
down to two candidates:
 a high heel pair; and
 a low heel pair
‰ The high heel shoes look more beautiful but are
not as comfortable as the competing pair
‰ Which pair should you choose?
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 3
 MODEL FORMULATION
‰ You first quantify your assessment along the two
dimensions of looks and comfort and construct

assessment
maximum weight
aspect high
value low heels (%)
heels
esthetics 5.0 4.2 3.6 70
comfort 5.0 3.5 4.8 30

‰ Next you represent your decision in terms of two

decision variables:
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 4
 MODEL FORMULATION
⎧⎪1 choose high ⎧⎪1 choose low
xH = ⎨ xL = ⎨
⎪⎩0 otherwise ⎪⎩0 otherwise

‰ Formulate your objectives to maximize the

weighted assessment as

max {70% * esthetics + 30% * comfort}

‰ Use the defined variables to state the objective

max Z = x H [ (4.2)(0.7) + (3.5)(0.3) ] + x L [ (3.6)(0.7) + (4.8)(0.3)]

ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 5
 MODEL FORMULATION
‰ Next consider the problem constraints:

 only one pair of shoes can be selected

 the decision variables are nonnegative

‰ State the constraints in terms of x H and x L :

xH + xL = 1

xH ≥ 0 , xL ≥ 0
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 6
 PROBLEM STATEMENT SUMMARY

‰ Decision variables:
⎧⎪1 choose high ⎧⎪1 choose low
xH = ⎨ xL = ⎨
⎪⎩0 otherwise ⎪⎩0 otherwise
‰ Objective function:
max Z = 3.99 x H + 3.96 x L
‰ Constraints:
xH + xL = 1

xH ≥ 0, xL ≥ 0
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 7
 OPTIMAL SOLUTION

‰ We determine the values x H* and x *L which result

on the value of Z * such that

Z * = Z ( x H* , x L* ) ≥ Z x H , x L ( )
for all feasible (x H ,xL )
‰ We call such a solution an optimal solution
‰ A feasible solution is one that satisfies all the
constraints
‰ The optimal solution, denoted by *
, is selected
from all the feasible solutions to the problem
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 8
 SOLUTION APPROACH: EXHAUSTIVE
SEARCH
‰ We enumerate all the possible solutions: in this
problem there are only two choices:
⎧⎪ x H = 1 ⎧ xH = 0
A: ⎨ B: ⎨
⎪⎩ x L = 0 ⎩xL = 1
‰ We evaluate Z for A and B and compare
Z A = 3.99 Z B = 3.96
so that Z A > Z B and so A is the optimal choice
‰ The optimal solution is
x *H = 1 , x *L = 0 and Z * = 3.99
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 9
 CHARACTERISTICS OF A
PROGRAMMING/OPTIMIZATION PROBLEM
‰ Objective is to make a decision among various
alternatives and therefore requires the definition of
the decision variables
‰ The solution of the “best” decision is made
according to some objective and requires the
formulation of the objective function
‰ The decision must satisfy certain specified
constraints and so requires the mathematical
statement of the problem constraints
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 10
CLASSIFICATION OF PROGRAMMING
PROBLEMS
‰ The problem statement is characterized by :
continuous valued
 decision variables
integer valued

linear
 objective function
non linear

linear
 constraints
non linear
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 11
 PROGRAMMING PROBLEM CLASSES

‰ Linear/nonlinear programming

‰ Static/dynamic programming

‰ Integer programming

‰ Mixed programming
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 12
EXAMPLE 2: CONDUCTOR PROBLEM
‰ A company is producing two types of conductors
for EHV transmission lines
production
metal needed profits
type conductor capacity
(tons/unit) ($/unit)
(unit/day)
1 ACSR 84/19 4 1/6 3
2 ACSR 18/7 6 1/9 5

‰ The supply department can provide daily up to 1

ton of metal
‰ We schedule the production so as to maximize the
profits of the company
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 13
 PROBLEM ANALYSIS

‰ Determination of the objective: to maximize the

profits of the company
‰ Means of attaining this objective: decision of how
many units of product 1 and of product 2 to
produce each day
‰ Consideration of the constraints: the daily
production capacity limits, the daily metal supply
limit and common sense requirements
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 14
 MODEL CONSTRUCTION

‰ We define the decision variables to be

x 1 = number of type 1 units produced per day
x 2 = number of type 2 units produced per day
‰ We define the objective to be

Z = profits ($/day)
= 3 x1 + 5 x 2
‰ Sanity check for units of the objective function
($/day) = ($/unit) • (unit/day)
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 15
 PROBLEM STATEMENT
‰ Objective function:
max Z = 3 x 1 + 5 x 2
‰ Constraints:
 capacity limits:
x1 ≤ 4 x2 ≤ 6
 metal supply limit:
x1 x2
+ ≤ 1
6 9
 common sense requirements:
x 1 ≥ 0, x 2 ≥ 0
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 16
 PROBLEM STATEMENT

max Z = 3 x1 + 5x 2

s .t .
x1 ≤ 4

x2 ≤ 6

x1 x2
+ ≤ 1
6 9

x 1 ≥ 0, x 2 ≥ 0
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 17
CONSTRUCTION OF THE FEASIBLE
REGION
x2
x1 = 4

( 4,0 )x
(0, 0 ) 1

x1 ≤ 4 , x 1 ≥ 0, x 2 ≥ 0
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 18
CONSTRUCTION OF THE FEASIBLE
REGION

x2

x2 = 6
(0 ,6 )
x 2 ≤ 6 , x 1 ≥ 0, x 2 ≥ 0

x1
( 0, 0 )

ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 19
CONSTRUCTION OF THE FEASIBLE
REGION

x2
x1 x2
( 0,9) 6
+
9
≤1

x 1 ≥ 0, x 2 ≥ 0
( 6,0)
( 0,0) x1

ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 20
 THE FEASIBLE REGION
x2 x1 = 4
( 2, 6)
x2 = 6
( 0 , 6)
feasible
region

( 4, 3)
x1 x2
+ = 1
6 9

( 0, 0 ) x1
( 4,0 )
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 21
 FEASIBLE SOLUTIONS
x2 x1 = 4
( 2, 6)
x2 = 6
( 0 , 6)
D max Z = 3 x 1 + 5 x 2
(1.5, 4.5)
Z = 27 ( 4, 3)
° ( 2, 2 ) x1 x2
Z = 16 + = 1
6 9
x1
( 0, 0 ) ( 4, 0 )
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 22
 CONTOURS OF CONSTANT Z
x2 x1 = 4
( 0, 6) ( 2, 6)
x2 = 6
Z = 25
Z = 20 max Z = 3 x 1 + 5 x 2
Z = 15
Z = 36
Z = 10 ( 4, 3)
x1 x2
( 0, 2) + = 1
6 9
x1
( 0, 0 ) ( 4, 0 )
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 23
 OPTIMAL SOLUTION

‰ We can graphically determine the optimal solution

‰ The optimal solution of this problem is:

x *
1 = 2 and x *
2 = 6

‰ The objective value at the optimal solution is

Z = 3x + 5x
* *
1
*
2 = 36
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 24
 LINEAR PROGRAMMING (LP)
PROBLEM

A linear programming problem is an optimization

problem with a linear objective function and linear

constraints.

ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 25
 EXAMPLE 3: ONE-POTATO, TWO-
POTATO PROBLEM
‰ Mr. Spud manages the Potatoes-R-Us Co. which
processes potatoes into packages of freedom
fries ( F ), hash browns ( H ) and chips ( C )
‰ Mr. Spud can buy potatoes from two sources;
each source has distinct characteristics/limits
‰ The problem is to determine the respective
quantities Mr. Spud needs to buy from source 1
and from source 2 so as to maximize profits
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 26
 EXAMPLE 3: ONE-POTATO, TWO-
POTATO PROBLEM
‰ The known data are summarized in the table
source 1 source 2
product sales limit (tons)
uses (%) uses (%)
F 20 30 1.8
H 20 10 1.2
C 30 30 2.4
profits ($/ton) 5 6

‰ The following assumptions hold:

 30% waste for each source
 production may not exceed sales limit
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 27
 ANALYSIS

‰ Decision variables:
x 1 = quantity purchased from source 1
x 2 = quantity purchased from source 2
‰ Objective function:
max Z = 5 x 1 + 6 x 2
‰ Constraints:
0.2 x 1 + 0.3 x 2 ≤ 1.8 ( F )
0.2 x 1 + 0.1 x 2 ≤ 1.2 ( H ) x 1 ≥ 0, x 2 ≥ 0
0.3 x 1 + 0.3 x 2 ≤ 2.4 (C)
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 28
FEASIBLE REGION DETERMINATION
x2 x2

6 freedom fries
F 12
4
10
2 hash browns
x2 x1 8
0 2 4 6 8 H
6
8
chips 4
6
C 2
4
x1
2 0 2 4 6 8
x1
0 2 4 6 8
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 29
 THE FEASIBLE REGION
x2

12
10
8 feasible
region
6
4
2
x1
2 4 6 8 10 12
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 30
 EXAMPLE 3: CONTOURS OF
CONSTANT Z
x2
Z = 36 max Z = 5 x 1 + 6 x 2
Z = 30 6
Z = 40.5
Z = 24 5
Z = 18 4
3 ( 4.5, 3)
2
1
x1
1 2 3 4 5 6
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 31
 THE OPTIMAL SOLUTION

‰ The optimal solution of this problem is:

x 1* = 4.5 x 2* = 3

‰ The objective value at the optimal solution is:

Z * = 5 x*1 + 6 x*2 = 40.5

ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 32
 OBSERVATIONS
‰ Constant Z lines are parallel and change
monotonically along the normal direction to the
contours of constant values of Z
‰ An optimal solution must be at one of the corner
points of the feasible region: fortuitously, there are
only a finite number of corner points
‰ If a particular corner point gives a better solution
(in terms of the Z value) than that at each adjacent
corner point, then, it is an optimal solution
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 33
 SOLUTION PROCEDURE: SIMPLEX
APPROACH
‰ Initialization step: start at a corner point

‰ Iteration step: move to a better adjacent corner

point and repeat this step as many times as

needed

‰ Stopping rule: stop when the corner point solution

is better than that at each adjacent corner point

ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 34
 EXAMPLE 3: THE SIMPLEX
APPROACH
x2
Z = 36 max Z = 5 x1 + 6 x2
( 0 , 6) 6
5
Z = 40.5
4
3
( 4.5, 3)
2
1 Z = 30
Z = 0 ( 6,0 ) x1
( 0, 0 ) 0
1 2 3 4 5 6
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 35
EXAMPLE 3 : APPLICATION OF THE
SIMPLEX METHOD

step x1 x2 Z

0 0 0 0

1 0 6 36

2 4.5 3 40.5

3 6 0 30

ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 36
EXAMPLE 3 : THE SIMPLEX
APPROACH

x2
(0,6) Z = 36 max Z = 5 x1 + 6 x 2
6
5

3 (4.5,3) Z = 40.5

1
(0,0) 0 Z=0 Z = 30 (6,0) x
1
1 2 3 4 5 6
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 37
 EXAMPLE 3 : THE SIMPLEX
APPROACH
1. Start at (0,0) with Z (0,0) = 0
2. (i) Move from (0,0) to (0,6), Z (0,6) = 36
(ii) Move from (0,6) to (4.5,3) and evaluate
Z (4.5,3) = 40.5
3. Compare the objective at (4.5,3) to values at (6,0)
and at (6,0):
Z (4.5,3) ≥ Z (6,0)
Z (4.5,3) ≥ Z (6,0)
therefore, (4.5,3) is optimal
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 38
 REVIEW

‰ Key requirements of a programming problem:

 to make a decision and so to define decision

variables

 to achieve some objective and so to formulate

an objective function

 to ensure that the decision satisfies certain

constraints which are mathematically stated

ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 39
 REVIEW

‰ Key attributes of an LP
 objective function is linear
 constraints are linear
‰ Basic steps in formulating a programming
problem
 definition of decision variables
 statement of objective function
 formulation of constraints
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 40
 REVIEW

‰ Words of caution: care is required with units and

attention to not ignoring the implicit constraints,
such as nonnegativity, and common sense
requirements in an LP formulation
‰ Graphical solution approach
 feasible region determination
 contours of constant Z
*
 identification of the vertex with optimal Z
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 41
EXAMPLE 4 : INSPECTION OF GOODS
PRODUCED
‰ There are 8 grade 1 and 10 grade 2 inspectors
available for QC inspection; at least 1800 pieces
must be inspected in each 8-hour day
‰ Problem data are summarized below:

grade speed accuracy wages

level (unit/hr) (%) ($/h)

1 25 98 4

2 15 95 3
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 42
EXAMPLE 4 : INSPECTION OF GOODS
PRODUCED
‰ Each error costs $ 2

‰ The problem is to determine the optimal

assignment of inspectors, i.e., the number of

inspectors of grade 1 and that of grade 2 to result

in the least-cost inspection effort

ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 43
 EXAMPLE 4 : FORMULATION

‰ Definition of decision variables:

x 1 = number of grade 1 inspectors assigned

x 2 = number of grade 2 inspectors assigned

‰ Objective function

 optimal assignment ⇒ minimum costs

 costs = wages + errors

ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 44
EXAMPLE 4 : FORMULATION

• each grade 1 inspector costs:

4 + 2 (25)(0.02) = 5 $/hr

• each grade 2 inspector costs:

3 + 2 (15)(0.05) = 4.5 $/hr

• total daily inspection costs in $ are

Z = 8 [5 x 1 + 4.5 x 2] = 40 x 1 + 36 x 2 ($)
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 45
 EXAMPLE 4 : FORMULATION
‰ Constraints:
 job completion:
8(25) x 1 + 8(15) x 2 ≥ 1, 800
⇔ 200 x 1 + 120 x 2 ≥ 1, 800
⇔ 5 x1 + 3 x2 ≥ 45
 availability limit:
x1 ≤ 8
x 2 ≤ 10
 nonnegativity:
x 1 ≥ 0, x 2 ≥ 0
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 46
 EXAMPLE 4 : PROBLEM STATEMENT
SUMMARY
‰ Decision variables:
x1 = number of grade 1 inspectors assigned
x2 = number of grade 2 inspectors assigned
‰ Objective function:
min Z = 40 x1 + 36 x2
‰ Constraints:
5 x 1 + 3 x 2 ≥ 45
x1 ≤ 8
x 2 ≤ 10
x 1 ≥ 0, x 2 ≥ 0
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 47
 MULTI – PERIOD SCHEDULING

‰ More than one period is involved

‰ The result of each period affects the initial

conditions for the next period and therefore the

solution

‰ We need to define variables to take into account

the initial conditions in addition to the decision

variables of the problem

ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 48
 EXAMPLE 5 : HYDROELECTRIC
POWER SYSTEM OPERATIONS
‰ We consider a single operator of a system

consisting of two water reservoirs with a

hydroelectric plant attached to each reservoir

‰ We schedule the two power plant operations over

a two–period horizon

‰ We are interested in a plan to maximize the total

revenues of the system operator

ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 49
 EXAMPLE 5 : HYDROELECTRIC
POWER SYSTEM OPERATIONS

res A wA wA wB wB
res A plant res B plant
inflow A B

sA sB
res B
inflow

ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 50
EXAMPLE 5 : kAf RESERVOIR DATA

parameter reservoir A reservoir B

maximum capacity 2,000 1,500
predicted inflow in
200 40
period 1
predicted inflow in
130 15
period 2
minimum allowable
1,200 800
level
level at start of period 1 1,900 850
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 51
 EXAMPLE 5 : SYSTEM
CHARACTERISTICS
plant A 1 kAf 400 MWh
plant A

plant B 1 kAf 200 MWh

plant B

reservoir max kAf for generation per period

A 150

B 87.5

ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 52
 EXAMPLE 5 : SYSTEM
CHARACTERISTICS
‰ Demand in MWh ( for each period )
 up to 50,000 MWh can be sold @ $ 20/MWh
 all additional MWh are sold @ $ 14/MWh
$/MWh
non-linear objective
function
14 $/MWh
20
$/MWh
xh xh MWh

50,000
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 53
EXAMPLE 5 : DECISION VARIABLES

variable quantity denoted units

x Hi energy sold at 20 $/MWh MWh
x Li energy sold at 14 $/MWh MWh
w Ai plant A water supply for generation kAf
wB i
plant B water supply for generation kAf
s Ai reservoir A spill kAf
s Bi reservoir B spill kAf
rA i
reservoir A end of period i level kAf
i
rB reservoir B end of period i level kAf

superscript i denotes period i, i = 1, 2

ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 54
EXAMPLE 5 : OBJECTIVE FUNCTION

maximize total revenues from sales

max Z = 20( x H1 + x H2 ) + 14( x L1 + x L2 )

4 of the 16 decision variables

2 for each period

units are in $
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 55
 EXAMPLE 5 : CONSTRAINTS
‰ Period 1
 energy conservation in a lossless system
• total generation 400 w A1 + 200 w B1 ( MWh )
x
• total sales H1
+ x 1
L ( MWh )
• losses are negelected and so
x 1
H + x 1
L = 400 w 1
A + 200 w 1
B

 maximum available capacity limit

w 1A ≤ 150
w B1 ≤ 87.5
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 56
 EXAMPLE 5 : CONSTRAINTS
 conservation of flow relations for each
reservoir
• reservoir A:
w A1 + s A1 + r A1 = 1, 900 + 200 = 2,100 ( kAf )

res. Res.level
level at at res. Res.level
level at at predicted
Res.level at
e.o.p.10
e.o.p. e.o.p.00
e.o.p. inflow
e.o.p. 0

• reservoir B:
w B1 + s B1 + r B1 = 850 + 40 + w A1 + s A1 ( kAf )
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 57
 EXAMPLE 5 : CONSTRAINTS

 limitation on reservoir variables

• reservoir A:

1,200 ≤ r 1
A ≤ 2,000 ( kAf )

• reservoir B:

800 ≤ r B1 ≤ 1,500 ( kAf )

 sales constraint

x 1H ≤ 50,000 ( kAf )
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 58
 EXAMPLE 5 : CONSTRAINTS

‰ Period 2
 energy conservation in a lossless system
• total generation 400 w A2 + 200 w B2 ( MWh )
• total sales x H2 + x L2 ( MWh )
• losses are negelected and so
x 2
H + x 2
L = 400 w 2
A + 200 w 2
B

 maximum available capacity limit

w A2 ≤ 150
w B2 ≤ 87.5
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 59
 EXAMPLE 5 : CONSTRAINTS

 conservation of flow relations for each

reservoir
• reservoir A:
w A2 + s A2 + r A2 = r A1 + 130 ( kAf )

res. Res.level
level at at res. level atat
Res.level Res.level at
predicted
e.o.p.20 e.o.p. 0 e.o.p. 0
e.o.p. e.o.p. 1 inflow

• reservoir B:
w B2 + s B2 + r B2 = r B1 + 15 + w A2 + s A2 ( kAf )
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 60
 EXAMPLE 5 : CONSTRAINTS

 limitation on reservoir variables

• reservoir A:

1,200 ≤ r A2 ≤ 2,000 ( kAf )

• reservoir B:

800 ≤ r B2 ≤ 1,500 ( kAf )

 sales constraint

x H2 ≤ 50,000 ( kAf )
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 61
 EXAMPLE 5 : PROBLEM STATEMENT

‰ 16 decision variables:
x Hi , x Li , w Ai , w Bi , s Ai , s Bi , r Ai , r Bi , i = 1, 2

‰ Objective function:

max Z = 20( x 1H + x H2 ) + 14( x 1L + x L2 )

‰ Constraints:

 20 constraints for the periods 1 and 2

 nonnegativity constraints on all variables

ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 62
 EXAMPLE 6 : DISHWASHER AND
WASHING MACHINE PROBLEM
‰ The Appliance Co. manufactures dishwashers and
washing machines
‰ The sales targets for next four quarters are:

quarter t
product variable
1 2 3 4

dishwasher Dt 2,000 1,300 3,000 1,000

washing
Wt 1,200 1,500 1,000 1,400
machine
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 63
 EXAMPLE 6 : QUARTERLY COST
COMPONENTS
quarter t
cost component parameter unit costs ($)
1 2 3 4
dishwasher ct 125 130 125 126
manufacturing
($/unit) washing
vt 90 100 95 95
machine
dishwasher jt 5.0 4.5 4.5 4.0
storage
($/unit) washing
kt 4.3 3.8 3.8 3.3
machine
hourly labor ($ /hour) pt 6.0 6.0 6.8 6.8
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 64
 EXAMPLE 6 : CONSTRAINTS

‰ Each dishwasher uses 1.5 and each washing

machine uses 2 of labor

‰ The labor hours in each quarter cannot grow or

decrease by more than 10%; there were 5,000 h of

labor in the quarter preceding the first quarter

‰ At the start of the first quarter, there are 750 dish-

washers and 50 washing machines in storage

ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 65
 EXAMPLE 6 : PROBLEM AIM

How to schedule the production in each of the

four quarters so as to minimize the costs while

meeting the sales targets?

ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 66
EXAMPLE 6 : QUARTER t DECISION
VARIABLES
symbol variable

dt number of dishwashers produced

wt number of washing machines produced

rt final inventory of dishwashers

st final inventory of washing machines

ht available labor hours during Qt

t = 1, 2, 3, 4
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 67
EXAMPLE 6 : OBJECTIVE FUNCTION

minimize the total costs for the four quarters

manufacturing storage labor

costs costs costs

min Z = c1d1 + v1 w1 + j1 r1 + k1 s1 + p1 h1 quarter 1

+ c2 d 2 + v2 w2 + j2 r2 + k2 s2 + p2 h2 quarter 2
+ c3 d 3 + v3 w3 + j3 r3 + k3 s3 + p3 h3 quarter 3
+ c4 d 4 + v4 w4 + j4 r4 + k4 s4 + p4 h4 quarter 4
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 68
 EXAMPLE 6 : CONSTRAINTS

‰ Quarterly flow balance relations:

d 1 , w1 d 2 , w2 d 3 , w3 d 4 , w4

r0 , s 0 r1 , s 1 r2 , s 2 r3 , s 3 r4 , s 4
t=1 t=2 t=3 t=4

D 1 ,W 1 D 2 ,W 2 D 3 ,W 3 D 4 ,W 4

⎧⎪ rt −1 + d t − rt = D t
⎨ t = 1, 2, 3, 4
⎪⎩ s t −1 + w t − s t = W t
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 69
 EXAMPLE 6 : CONSTRAINTS

‰ Quarterly labor constraints

⎧1.5 d t + 2 w t − h t ≤ 0
⎪
⎨ t = 1, 2, 3, 4
⎪ 0.9 h ≤ h ≤ 1.1h
⎩ t −1 t t −1

h 0 = 5, 000

ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 70
EXAMPLE 6 : PROBLEM STATEMENT
d1 w1 r1 s1 h1 d2 w2 r2 s2 h2 d3 w3 r3 s3 h3 d4 w4 r4 s4 h4
1 -1 = 1250
1 -1 = 1150
1.5 2 -1 ≤0
1 ≥ 4500
1 ≤ 5500
1 1 -1 = 1300
1 1 -1 = 1500
1.5 2 -1 ≤0
-0.9 1 ≥0
-1.1 1 ≤0
1 1 -1 = 3000
1 1 -1 = 1000
1.5 2 -1 ≤ 0
-0.9 1 ≥0
-1.1 1 ≤0
1 1 -1 = 1000
1 1 -1 = 1400
1.5 2 -1 ≤0
-0.9 1 ≥0
-1.1 1 ≤0
125 90 5.0 4.3 6.0 130 100 4.5 3.8 6.0 125 95 4.5 3.8 6.8 126 95 4.0 3.3 6.8 minimize

ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 71
 LINEAR PROGRAMMING PROBLEM
max (min) Z = c 1 x 1 + ... + c n x n
s.t.
a 11 x 1 + a 12 x 2 + ... + a 1n x n = b1
a 21 x 1 + a 22 x 2 + ... + a 2n x n = b2

# #
a m1 x 1 + a m2 x 2 + ... + a mn x n = b m
x 1 ≥ 0, x 2 ≥ 0, ... , x n ≥ 0
b 1 ≥ 0, b 2 ≥ 0, ... , b m ≥ 0
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 72
 STANDARD FORM OF LP (SFLP)

coefficient matrix
max (min) Z = c T x m× n
A ∈ \
n
x ∈ \
decision
Ax= b vector b ∈ \m
n
c ∈ \
x ≥ 0
requirement
vector profits
(costs)
vector
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 73
 CONVERSION OF LP INTO SFLP

‰ An inequality may be converted into an equality

by defining an additional nonnegative slack
variable

 xslack ≥ 0

 replace the given inequality ≤ b by

inequality + x slack = b

 replace the given inequality ≥ b by

inequality – x slack = b
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 74
 CONVERSION OF LP INTO SFLP

‰ An unsigned variable x u is one whose sign is

unspecified

‰ x u is converted into two signed variables x+ and x-

with
⎧⎪ x u xu ≥ 0 ⎧ 0 xu ≥ 0
x+ = ⎨ x− = ⎨
⎪⎩0 xu < 0 ⎩- x u xu < 0
and with xu replaced by
x u = x + − x−
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 75
 SFLP CHARACTERISTICS

‰ x is feasible if and only if x ≥ 0 and A x = b

‰ S = { x | A x = b , x ≥ 0} is the feasible region

‰ If S = ∅ ⇒ LP is infeasible

‰ x* is optimal ⇒ cT x * ≥ cTx , ∀ x ∈ S

‰ x* may be unique, or may have multiple values

‰ x * may be unbounded
ECE 307 © 2005 - 2009 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 76