PENELITIAN OPERASIONAL I (TIN 4109)
Lecture 9
LINEAR PROGRAMMING
Lecture 9 • Outline: – Analisa Sensitivitas Simplex – Duality
• References: – Frederick Hillier and Gerald J. Lieberman. Introduction to Operations Research. 7th ed. The McGraw-Hill Companies, Inc, 2001. – Hamdy A. Taha. Operations Research: An Introduction. 8th Edition. Prentice-Hall, Inc, 2007.
Sensitivity Analysis – Objective Function –
• Contoh kasus: 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑧 = 3𝑥1 + 2𝑥2 + 5𝑥3
𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑥1 + 2𝑥2 + 𝑥3 ≤ 430 (𝑂𝑝𝑒𝑟𝑎𝑡𝑖𝑜𝑛 1) 𝑥1 + 2𝑥3 ≤ 460 (𝑂𝑝𝑒𝑟𝑎𝑡𝑖𝑜𝑛 2) 𝑥1 + 4𝑥2 ≤ 420 (𝑂𝑝𝑒𝑟𝑎𝑡𝑖𝑜𝑛 3) 𝑥1 , 𝑥2 , 𝑥3 ≥ 0
𝑥1 = mainan – kereta 𝑥2 = mainan – truk 𝑥3 = mainan - mobil
• Hasil Optimal: Basic
𝒙𝟏
𝒙𝟐
𝒙𝟑
𝒙𝟒
𝒙𝟓
𝒙𝟔
Solution
𝒛
4
0
0
1
2
0
1350
𝒙𝟐
-1/4
1
0
1/2
-1/4
0
100
𝒙𝟑
3/2
0
1
0
1/2
0
230
𝒙𝟔
2
0
0
-2
1
1
20
Shadow Price • It is often important for managers to determine how a change in a constraint’s right-hand side changes the LP’s optimal z-value. • With this in mind, we define the shadow price for the ith constraint of an LP to be the amount by which the optimal z-value is improved—increased in a max problem and decreased in a min problem—if the righthand side of the ith constraint is increased by 1. • This definition applies only if the change in the righthand side of Constraint i leaves the current basis optimal.
Contoh: Shadow Price
6
Contoh: Shadow Price Max x1 3x 2 ST 2x1 3x 2 x 3 8 x1 x 2 x4 1 x1 , x 2 , x 3, x 4 0
b1 ditambah 1 unit menjadi 9
Shadow price jika resource b1 bertambah 1 unit
Nilai z bertambah 4/5 (shadow price) 7 + 4/5 = 39/5
DUALITAS Terima kasih kepada Prof.Dr.Ir. Abdullah Alkaff, M.Sc. yang telah menyiapkan versi awal dalam tulisan tangan dari materi ini
Linear Programming ● LP dalam bentuk standard
Linear Programming
Linear Programming Kondisi keoptimalan: z0 = y b = y1b1 + y2b2 + … + ymbm
(1)
zj = y aj = y1a1j + y2a2j + … + ymamj
(2)
sehingga persoalan LP dapat diintepretasikan sebagai berikut:
cari y1, y2, …, ym sedemikian hingga (1) dan (2) terpenuhi
Linear Programming Dapat dilakukan dengan menyelesaikan LP sebagai berikut:
Min
z0 = y1b1 + y2b2 + … + ymbm
subject to
y1a1j +y2a2j + … + ymamj cj y1 ,
y2 ,
ym
0
Maka diperoleh problem LP yang baru yang disebut DUAL dari problem semula atau disingkat PROBLEM DUAL
Primal and Dual Primal Problem
Dual Problem m
n
Max s.t.
Z cjxj, j 1
n
a
ij
x j bi ,
j1
for i 1,2,, m. x j 0, for j 1,2,, n.
Min
W bi yi , i 1
s.t.
m
a i 1
for
ij
yi c j , j 1,2,, n.
yi 0, for i 1,2,, m.
The dual problem uses exactly the same parameters as the primal problem, but in different location.
Primal Dual dalam Matriks Primal Problem Maximize
Dual Problem
Z cx,
subject to
Minimize W
yb,
subject to
yA c
Ax b
y 0.
x 0.
Where c and y y1 , y2 ,, ym are row vectors but b and x are column vectors.
Contoh: Primal – Dual Dual Problem in Algebraic Form
Primal Problem in Algebraic Form Max Z 3x1 5x2 , s.t.
4 2 x2 12 3x1 2 x2 18 x1 0, x 2 0
x1
Min
W 4 y1 12 y2 18 y3 , s.t.
y1
3 y3 3 2 y2 2 y3 5
y1 0, y2 0, y3 0
Programa Dual Hubungan antara PRIMAL dan DUAL adalah sebagai berikut : PRIMAL
DUAL
RHS
Fungsi Tujuan
MAX
MIN
Constrain
Variable
Programa Dual
y2
a21
a22
a2n
b2
ym
am1 c1
am2 c2
amn cn
bm
Koefisien Fungsi Objektif (Maksimisasi)
Koefisien Fungsi Objektif (Minimisasi)
RHS b1
xn a1n
x2 a12
y1
x1 a11
DUAL
PRIMAL
Contoh Programa Dual PRIMAL :
Max s.t.
3x1 + 5x2 4 2x2 12 3x1 + 2x2 18 x1, x2 0 x1
DUAL :
Min s.t.
4y1 + 12y2 + 18y3 y1
+ 3y3 3 2y2 + 2y3 5 y1, y2 , y3 0
DUAL dari DUAL adalah PRIMAL
Primal of Diet problem
RI-1333 OR1/sew/2007/#6
Diet Problem – Dual
RI-1333 OR1/sew/2007/#6
PRIMAL – DUAL Secara umum hubungan antara DUAL dan PRIMAL dapat digambarkan seperti pada tabel di bawah ini
Unrestricted
=
=
Unrestricted
Constraint
MAKSIMASI
Variable
Constraint
Variable
MINIMASI
Contoh PRIMAL :
DUAL :
Max s.t.
Min s.t.
8x1 + 3x2 x1 – 6x2 4 5x1 + 7x2 = – 4 x1 0 x2 0 4w1 – 4w2
w1 + 5w2 8 – 6w1 + 7w2 3 w1 0 w2 unrestricted
Contoh 2 Primal: Max. z = 3x1 + 2x2 subject to 2x1 + x2 100 x1 + x2 80 x1 40 x1, x2 0
(Obj. Func.) (Finishing constraint) (Carpentry constraint) (Bound on soldiers)
Optimal Solution: z = 180, x1 = 20, x2 = 60 Dual : Min. w = 100y1 + 80y2 + 40y3 subject to 2y1 + y2 + y3 3 y1 + y2 2 y1, y2, y3 0
(Obj. Func.)
RI-1333 OR1/sew/2007/#6
Complementary Basic Solution Problem Dual : Constraint
zj – cj 0 ; zj cj zj – Surplus Var = cj
atau
Surplus Var. = zj – cj Dalam Tableau Original Variables x1
x2
Baris 0: z1 – c1 z2 – c2
Slack Variables
xn
xn+1
xn+2
xn+m
z n – cn
y1
y2
ym
Complementary Basic Solution Dalam Tableau Original Variables x1
x2
Baris 0: z1 – c1 z2 – c2
Slack Variables
xn
xn+1
xn+2
xn+m
zn – cn
y1
y2
ym
PRIMAL VARIABLES
DUAL VARIABLES
Original Variable :
xj
zj – cj
: Surplus Variable
Slack Variable
xn+i
yi
: Original Variable
Basic Nonbasic
:
Nonbasic Basic
Complementary Basic Solution PRIMAL VARIABLES
DUAL VARIABLES
Original Variable :
xj
zj – c j
: Surplus Variable
Slack Variable
xn+i
yi
: Original Variable
:
Basic Nonbasic 1) Bila xj > 0, maka ………..…. 2) Bila xn+i > 0, maka…………. 3) Bila yi > 0, maka ……….……
4) Bila zj–cj > 0, maka…….…...
Nonbasic Basic
Complementary Basic Solution Dapat diringkas sebagai berikut:
1. xn+i yi = 0 2. (zj – cj) xj = 0 Jadi constraint di satu problem adalah renggang (nonbinding), maka variabel yang berkaitan dengan constrain ini dalam problem yang lain harus nol. Hasil ini biasa dikenal sebagai Complementary Slackness
Contoh: The Dakota Furniture Company manufactures desk, tables, and chairs. The manufacture of each type of furniture lumber and two types of skilled labor: finishing and carpentry. The amount of each resource needed to make each type of furniture is given in Table Resource
Desk
Table
Chair
8 board ft
6 board ft
1 board ft
Finishing hours
4 hours
2 hours
1.5 hours
Carpentry hours
2 hours
1.5 hours
0.5 hours
Lumber
At present, 48 bard feet of lumber, 20 finishing hours, and 8 carpentry hours are available. A desk sells for $60, and a table for $30, and a chair for $20. Dakota believes that demand for desks, chairs and tables is unlimited. Since available resource have already been purchased. Dakota wants to maximize total revenue
Max z 60 x1 30 x2 20 x3 s.t.
8 x1 6 x2
x3 48
4 x1 2 x2 1.5 x3 20 2 x1 1.5 x2 0.5 x3 8 x1 , x2 , x3 0
Min w 48 y1 20 y2 8 y3 s.t.
8 y1 4 y2 2 y3 60 6 y1 2 y2 1.5 y3 30 y1 1.5 y2 0.5 y3 20 y1 , y2 , y3 0
z 280, x1 2, x2 0, x3 8
s1 48 82 60 18 24
s2 20 42 20 1.58 0
s3 8 22 1.50 0.58 0
w 280, y1 0, y2 10, y3 10
e1 80 410 210 60 0
e2 60 210 1.510 30 5
e3 10 1.510 0.510 20 0
Contoh
x1 3 x2
M ax
x1 3x2
M ax
Subject to
Subject to 2 x1 3 x2 8
2 x1 3x2 x3
x1 x2 1
x1 x2
x1 , x2 0
8 x4 1
x1 , x2 , x3 , x4 0
z
x1
x2
x3
x4
RHS
z
1
-1
-3
0
0
0
x3
0
2
3
1
0
8
x4
0
-1
1
0
1
1
z
1
-4
0
0
3
3
x3
0
5
0
1
-3
5
x2
0
-1
1
0
1
1
z
1
0
0
0.8
0.6
7
x1
0
1
0
0.2
-0.6
1
x2
0
0
1
0.2
0.4
2
Pada Problem Dual
1
2
3
4
z
1
-1
-3
0
0
0
x3
0
2
3
1
0
8
z
1
-4
0
0
3
3
x3 Primal x
0
5
0
1
-3
5
0
-1
1
0
1
1
z
1
0
0
0.8
0.6
7
x1
0
1
0
0.2
-0.6
1
x2
0
0
1
0.2
0.4
2
x4
2
Hubungan - 1Dual1 0 -1 1 Primal 0
Dual
Hubungan PRIMAL – DUAL DUAL Constraint
yAc x 0 y Ax cx
Ax b y b cx Bila x adalah feasible terhadap PRIMAL dan y feasible terhadap DUAL, maka cx yb Nilai objektif problem Max Nilai objektif problem Min
Teorema Dualitas ● Bila x* adalah penyelesaian dari PRIMAL dan y* adalah penyelesaian dari DUAL, maka cx* = y*b ● Bila x0 feasible terhadap PRIMAL dan y0 feasible terhadap DUAL sedemikian hingga cx0 = y0b, maka x0 dan y0 adalah penyelesaian optimal z
Menyelesaikan DUAL
DUAL FR
PRIMAL FR Menyelesaikan PRIMAL
Optimal (PRIMAL – DUAL FEASIBLE)
Teorema Dualitas 1. P optimal
D optimal
2. P tak terbatas D tak terbatas
D tidak feasible P tidak feasible
3. P tidak feasible D tidak feasible
D tak terbatas/tidak feasible P tak terbatas/tidak feasible
Lecture 10 – Preparation • Materi: – Integer Linear Programming
