Optimization and
Linear Programming
Rini Novrianti Sutardjo Tui
The Optimal Decision Problem
Decision which incurs the least cost among
the set of permissible decisions
The decisions can be
ranked according to
whether they incur
greater or lesser cost
The set of all
permissible
decisions is
known
The cost of
each
decision is
known
Optimization Methods
Dynamic
Programming
Linear
Programming
Discrete-time
Optimal Control
Non-linear
Programming
Linear Programming (LP)
Standard form of LP problem with m constraints and n variables
Maximize/minimize
: Z = c1x1 + c2x2 + + cnxn
Constraints
: a11x1 + a12x2 + + a1nxn = b1
a21x1 + a22x2 + + a2nxn = b2
am1x1 + am2x2 + + amnxn = bm
x1 0 ; x2 0 ; ; xn 0
b1 0 ; b2 0 ; ; bm 0
Linear Programming in Vector Form
Amxn =
Maximize/minimize
: Z = cx
Constraints
: Ax = b
x0
b0
a11 a12
a
21 a22
... ...
am1 am 2
x1
x
xn1 2
...
xn
... a1n
... a2 n
... ...
... amn
b1
b
bm1 2
...
bm
c1n c1 c2 ... cn
Prerequisites of LP Model
Function of objective is
maximize or minimize
Constant in right
side of constraints
is non-negative
All constraints are stated
as equations
All variables are nonnegative
Linear Programming Model
x2
x1 = 8
15
Minimize
: Z = 40x1 + 36x2
Constraints
x1
8
x2 10
10
x2 = 10
5x1 + 3x2 45
x1 0 ; x 2 0
5
A (8, 5/3)
x1
Simplex Method
Simplex
For complex and broad
problem of linear
programming
All
constraints
have to be
equations, if not
then slack variable or
surplus variable is
needed.
Constant in
right side of
constraint
equations has
to be nonnegative, if not
then it has to be
transformed to
positive value.
General Model of Simplex Method
Maximize
Function of Objective: Maximize
Z C1X1-C2X2- . . . . . CnXn-0S1-0S2-. . .-0Sn = NK
Function of Constraints:
a11X11+a12X12+. . . .+a1nXn+ S1+0S2+. . .+0Sn = b1
a21X21+a22X22+. . . .+a2nXn+ 0S1+1S2+. . .+0Sn = b2
. ..
. .. .. . ..=
am1Xm1+am2Xm2+. . . .+amnXn+ S1+0S2+. . .+1Sn = bm
Activities Variables
Slack Variables
General Model of Simplex Method
Minimize
Function of Objective: Minimize
Z C1X1-C2X2- . . . . . CnXn-0S1-0S2-. . .-0Sn = RhV
Function of Constraints:
a11X11+a12X12+. . . .+a1nXn - S1 -0S2-. . . - 0Sn = b1
a21X21+a22X22+. . . .+a2nXn - 0S1-1S2 -. . . - 0Sn = b2
. ..
. .. .. . ..=
am1Xm1+am2Xm2+. . . .+amnXn- S1- 0S2 -. . . -1Sn = bm
Activities Variables
Surplus Variables
Solving Simplex Model
Formulate LP problem into standard form of LP
Transform LP model into simplex model
Formulate simplex table
Take steps of solving
Simplex Model
Column table of
basic variables
Row table of Cj - Zj
Table of Matrix
Linear Programming
COLUMN TABLE OF MATRIX
OF BASIC VARIABLES
Example Step 1
Maximize:
Linear Programming Method
Function of Objective:
Maximize: Z=8X1 + 6X2 (in thousand IDR)
Function of Constraints:
Material A : 4X1 + 2X2 60
Material B : 2X1 + 4X2 48
X1, X2 0
Step 2
Simplex Model:
Function of Objective: Maximize
Z 8X16 X20S1- 0S2 = 0
Function of Constraints:
4X1+2X2+ S1+ 0S2 = 60
2X1+4X2+0S1+ 1S2 = 48
X1, X2, S1, S2 0
Step 3 1
Simplex Table
Basic
Variables
X1
X2
S1
S2
RhV
Step 3 2
Simplex Table
Basic
Variables
Z
S1
S2
X1
X2
S1
S2
RhV
Step 3 3
Simplex Table
Basic
Variables
X1
X2
S1
S2
RhV
-8
-6
S1
S2
Step 3 4
Simplex Table
Basic
Variables
X1
X2
S1
S2
RhV
-8
-6
S1
60
S2
Step 3 5
Simplex Table
Basic
Variables
X1
X2
S1
S2
RhV
-8
-6
S1
60
S2
48
Step 4 1
First iteration Iteration-0
Basic
Variables
X1
X2
S1
S2
RhV
-8
-6
S1
60
S2
48
Step 4 2
Iteration-1: Determining key column
Basic
Variables
X1
X2
S1
S2
RhV
-8
-6
S1
60
S2
48
Key column: column with biggest negative
value of coefficients of function of constraints.
Step 4 3
Iteration-1: Determining key row
Basic
Variables
X1
X2
S1
S2
RhV
Index
-8
-6
S1
60
15
S2
48
24
Key number
Index value: RV/key column
Key row: row with smallest index value (positive).
Step 4 4
Iteration-1: Changes of row value
Basic
Variables
X1
X2
S1
S2
RhV
15
Z
X1
S2
New key row: (previous key row)/key number
Other row value: (previous row value) ( (new
key row) x key column of the row itself).
Step 4 5
Iteration-1: Changes of row value
Basic
Variables
X1
X2
S1
S2
RhV
X1
15
S2
18
New key row: (previous key row)/key number
Other row value: (previous row value) (new
key row) x key column of the row itself
Step 4 6
Iteration-1: Changes of row value
Basic
Variables
X1
X2
S1
S2
RhV
-2
120
X1
15
S2
18
New key row: (previous key row)/key number
Other row value: (previous row value) (new
key row) x key column of the row itself
Step 4 7
Iteration-2: Determining key column
Basic
Variables
X1
X2
S1
S2
RhV
-2
120
X1
15
S2
18
Step 4 8
Iteration-2: Determining key row
Basic
Variables
X1
X2
S1
S2
RhV
Index
-2
120
X1
15
30
S2
18
Step 4 9
Iteration-2: Changes of row value
Basic
Variables
X1
X2
S1
S2
RhV
Index
- 1/6
1/3
Z
X1
X2
Step 4 10
Iteration-2: Changes of row value
Basic
Variables
X1
X2
S1
S2
RhV
Index
5/3
2/3
132
X1
1/3
- 1/6
12
X2
- 1/6
1/3
Solution
X1 = 12
Optimal
Zmax =
IDR
132,000
X2 = 6
Linear Programming
ROW TABLE OF MATRIX OF
CJ - ZJ
Example Step 1
Maximize:
Linear Programming Method
Function of Objective:
Maximize: Z=3X + 5Y
Function of Constraints:
2X 8
3Y 15
6X + 5Y 30
X, Y 0
Step 2
Simplex Model:
Function of Objective: Maximize
Z=3X+5Y+0S1+0S2+0S3
Function of Constraints:
2X+0Y+ 1S1+ 0S2+0S3 = 8
0X+3Y+ 0S1+ 1S2+0S3 = 15
6X+5Y+ 0S1+ 0S2+1S3 = 30
X,Y, S1, S2 , S3 0
Step 3 Enter each coefficient into
simplex table
Basic Var.
Obj.
Cj
S1
S2
S3
S1
S2
15
S3
30
Zj
Cj-Zj
Qty. Ratio
Step 4 Determine key column
Basic Var.
Obj.
Cj
S1
S2
S3
S1
S2
15
S3
30
Zj
Cj-Zj
Key column: column with biggest positive
value of Cj Zj (maximize), or column with
biggest negative value of Cj Zj (minimize).
Qty. Ratio
Step 5 Determine key row
Basic Var.
Obj.
Cj
S1
S2
S3
Qty. Ratio
S1
8/0 = ~
S2
15
15/3 = 5
S3
30
30/5 = 6
Zj
Cj-Zj
Quantity _ ratio
Q _ value
coefficient _ of _ var iables _ of _ key _ column _ of _ responding _ row
Key row: row with the smallest value of
quantity ratio.
Step 6 Determine pivot point
Basic Var.
Obj.
Cj
S1
S2
S3
Qty. Ratio
S1
8/0 = ~
S2
15
15/3 = 5
S3
30
30/5 = 6
Zj
Cj-Zj
Step 7 Change value of key row
New value : previous key row value/pivot point
New value for row S2:
15/3
5
0/3
3/3
0/3
1/3
1/3
0/3
0
Step 8 Change value of non-key
row
New value = previous value (FR x previous value of key row)
FR (fixed ratio) is coefficient of variables of key column of corresponding row/pivot point
Row S1:
FR = 0/3 = 0,
Since value of FR is 0, therefore for row S1, new value = previous value
Row S2:
FR = 5/3,
30
(5/3) x 15
-5/3
Step 9 Change table in step 3
Basic Var.
Obj.
Cj
S1
S2
S3
S1
1/3
S3
-5/3
Zj
5/3
Cj-Zj
-5/3
Change in basic variable: variables of key
column (Y) replace variable of key row (S2)
Qty. Ratio
Step 10 Optimality test
Simplex table is considered optimal if value of Cj- Zj 0 for case of
maximize and value of Cj Zj 0 for case of minimize.
Table in step 9 indicates that there is still positive value of Cj-Zj,
therefore optimal condition has not been reached yet.
Repeat step 3 9 until optimized solution is achieved.
Step 11 Repeat step 3 9
Basic
Var.
Obj.
Cj
S1
S2
S3
S1
38/6
5/9
-2/6
1/3
5/6
-5/18
1/6
Zj
15/18
3/6
Cj-Zj
-15/18
-3/6
Qty. Ratio
Solution
X = 5/6
Optimal
Z = (3 x
5/6) + (5 x
5) = 27.5
Y=5
M i n i n g
M a n a g e m e n t
