LINEAR PROGRAMMING
What is Linear Programming?
• Mathematical technique
– Not computer programming
• Allocates scarce resources to achieve an
objective
• Pioneered by George Dantzig in World
War II
– Developed workable solution called Simplex
Method in 1947
Examples of Successful LP
Applications
• Picking blends of raw materials in feed mills
to produce finished feed combinations at
minimum costs
• Selecting the product mix in a factory to
make best use of machine- and labor-hours
available while maximizing the firm’s profit
• Allocating space for a tenant mix in a new
shopping mall so as to maximize revenues
to the leasing company
Assumption of Linear
Programming
• Certainty (Deterministic) semua parameter yang
terdapat dalam model LP (aij; bj; Cj) dapat diperkirakan
dengan pasti.
• Proportionality (naik turunnya nilai Z dan penggunaan
resources yang tersedia akan berubah sebanding dengan
perubahan tingkat kegiatan.
• Additivity nilai tujuan tiap kegiatan tidak saling
mempengaruhi, atau kenaikan dalam nilai Z yang
diakibatkan kenaikan suatu kegiatan dapat ditambahkan
tanpa mempengaruhi bagian nilai Z yang diperoleh
baggian lain.
• Divisibility keluaran (output) yang dihasilkan oleh setiap
kegiatan dapat berupa bilangan pecahan, demikian juga
nilai Z yang dihasilkan.
• Nonnegative variables Semua variabel bernilai positif.
Requirements of a Linear
Programming Problem
• Must seek to maximize or minimize some
quantity (the objective function)
• Presence of restrictions or constraints -
limits ability to achieve objective
• Must be alternative courses of action
from which to choose
• Objectives and constraints must be
expressible as linear equations or
inequalities
Formulating Linear
Programming Problems -
continued
• Let:
X1 = number of Walkmans
X2 = number of Watch-TVs
• Then:
4X1 + 3X2 240 electronics constraint
2 X1 + 1X2 100 assembly constraint
7X1 + 5X2 = profit maximize profit
Graphical Solution Method
► Draw graph with vertical & horizontal
axes (1st quadrant only)
► Plot constraints as lines, then as planes
Use (X1,0), (0,X2) for line
► Find feasible region
► Find optimal solution
Corner point method
Iso-profit line method
Company Problem
Hours Required to
Produce 1 Unit
Department X1 X2 Available Hours
Walkmans Watch-TV’s This Week
Electronic 4 3 240
Assembly 2 1 100
Profit/unit $7 $5
Constraints: 4x1 + 3x2 240 (Hours of Electronic Time)
2x1 + 1x2 100 (Hours of Assembly Time)
Objective: Maximize: 7x1 + 5x2
Company Constraints
Electronics
120 (Constraint A)
100
Assembly
Number of Watch-TVs (X2)
(Constraint B)
80
60
40
20
0
0 10 20 30 40 50 60 70 80
Number of Walkmans (X1)
Company Feasible Region
Electronics
120 (Constraint A)
100 Assembly
(Constraint B)
Number of Watch-TVs (X2)
80
60
40 Feasible
Region
20
0
0 10 20 30 40 50 60 70 80
Number of Walkmans (X1)
Company Iso-Profit Lines
120 Electronics
(Constraint A)
100 7*X1 + 5*X2 = 420
Assembly
(Constraint B)
Number of Watch-TVs (X2)
80
60
Iso-profit line
40 7*X
1 +5
*X
2 =
210
20
0
0 10 20 30 40 50 60 70 80
Number of Walkmans (X1)
Company Corner Point
Solutions
Electronics
(Constraint A)
Iso-profit line
Assembly
120 (Constraint B)
Number of Watch-TVs (X2)
100 Possible Corner
80 Point Solution
60
40
20
0
0 10 20 30 40 50 60 70 80
Number of Walkmans (X1)
Company Optimal Solution
Electronics
(Constraint A)
Iso-profit line
Assembly
120 (Constraint B)
Number of Watch-TVs (X2)
100 Possible Corner
Point Solution
80
60
40 Optimal solution
20
0
0 10 20 30 40 50 60 70 80
Number of Walkmans (X1)
Company Optimal Solution
Electronics
(Constraint A)
Iso-profit line Assembly
120 (Constraint B)
Number of Watch-TVs (X2)
100 Possible Corner
Point Solution
80 X1 = 30
60 X2 = 40
40 Optimal solution
20
0
0 10 20 30 40 50 60 70 80
Number of Walkmans (X1)
Formulation of Solution
• Decision variables
X1 = tons of BW chemical produced
X2 = tons of color chemical produced
• Objective
Minimize Z = 2500X1 + 3000X2
• Constraints
X1 ≥ 30 (BW); X2 ≥ 20 (Color)
X1 + X2 ≥ 60 (Total tonnage)
X1 ≥ 0; X2 ≥ 0 (Non-negativity)
Simplex Steps for Maximization
• Choose the variable with the greatest positive
Cj- Zj to enter the solution
• Determine the row to be replaced by selecting
that one with the smallest (non-negative)
quantity-to-pivot column ratio
• Calculate the new values for the pivot row
• Calculate the new values for the other row(s)
• Calculate the Cj and Cj-Zj values for this
tableau.
• If there are any Cj-Zj numbers greater than
zero, return to step 1.
Simplex Steps for Minimization
• Choose the variable with the greatest negative Cj- Zj
to enter the solution
• Determine the row to be replaced by selecting that one
with the smallest (non-negative) quantity-to-pivot
column ratio
• Calculate the new values for the pivot row
• Calculate the new values for the other row(s)
• Calculate the Cj and Cj-Zj values for this tableau. If
there are any Cj-Zj numbers less than zero, return to
step 1.
Simplex
1. Menentukan fungsi tujuan
fungsi tujuan (cj) max = 420x1 + 320X2 + 260X3
fungsi kendala/batasan =
120x1 + 100x2 + 80x3 ≤ 8.000
6x1 + 4x2 + 2x3 288
x1; x2; x3 ≥ 0
Cont’……
Standarisasi model:
Fungsi Tujuan:
Z – 420X1 – 328X2 – 260X3 = 0
Fungsi batasan:
120x1 +100x2 + 80x3 + S1 = 8.000
6x1 + 4x2 + 2x3 +S2 = 288
X1; x2; x3; S1; S2 ≥ 0
Cont’……
2. Membuat tabel /matrik awal dengan variabel
“slack”
Var. Z X1 X2 X3 S1 S2 NK Tes
Basis (RHS) Ration
Z -420 -320 -260 0 0
S1 0 120 100 80 1 0 8000 66,67
S2 0 6 4 2 0 1 288 48
Kolom kunci
Cont’..
3. Menentukan kolom kunci yaitu: “pay off” terbesar cj – Zj
4. Menentukan baris kunci yaitu : “angka index” terkecil NK = tes ratio
KK
5. Membuat matrix baru :
• Pada baris kunci = bilangan pada baris kunci (S2)
angka index
• Diluar baris kunci
Nilai baru = nilai baris lama – (koef pada KK x nilai baru baris
kunci)
• Nilai pada baris ke 2 ( S1):
(120; 100; 80; 1; 0 ; 8000 )
120 ( 1 ; 4/6; 2/6; 0; 1/6; 48 )-
(0 ; 20 ; 40 ; 1 ; -20; 2240 )
S2 6/6; 4/6; 2/6; 0; 1/6; 288/6
S1 120 - (120 x 6/6) = 0
100 – (120 x 4/6) = 20
80 – (120 x 2/6) = 40
1 – (120 x 0) = 1
0 – (120 x 1/6) = -20
8000 – (120 x 48) = 2240
Cj – Zj 420 – (420 x 6/6) = 0
320 – (420 x 4/6) = 40
260 – (420 x 2/6) = 120
0 – (420 x 0) = 0
0 – (420 x 1/6) = -70
Matrix baru (mengubah var dasar dengan
var yang berada diatas kolom kunci)
Basis Cj X1 X2 X3 S1 S2 Q Tes
ratio
Z 0 -40 -120 0 -70
S1 0 0 20 40 1 -20 2240 56 Baris
X1 420 6/6 4/6 2/6 0 1/6 48 144 kunci
Kolom kunci
baru
6. Tentukan baris dan kolom kunci yang baru
S1= X3 0/40; 20/40; 40/40; 1/40; -20/40; 2240/40
X1 6/6 – (2/6 x 0) = 1 cj-Zj 0 – (120 x 0) = 0
4/6 – (2/6 x ½) = 3/6 40 – (120 x ½) = -20
2/6 – (2/6 x 1) = 0 120 – (120 x 1) =
0
0 – (2/6 x 1/40) = -1/120 0 – (120 x 1/40) = -3
1/6 – (2/6 x -1/2) = 2/6 70 – (120 x -1/2) = -10
48 – (2/6 x 56) = 88/3
Matrix baru
Basis Cj X1 X2 X3 S1 S2 Q Tes
ratio
420 320 260 0 0
X3 260 0 1/2 1 1/40 -1/2 56
X1 420 1 1/2 0 - 1/3 88/3
1/120
Zj 420 340 260 3 10
Cj-Zj 0 -20 0 -3 -10
Solusi yang optimal
Kasus 2
Z max = 25x1 + 15x2
Fungsi kendala:
3x1 + 3x2 ≤ 24 (input I)
2x1 + 4x2 ≤ 20 (input II)
3x1 ≤ 21
x1; x2 ≥ 0
1. Standarisasi model:
Z max = 25x1 + 15x2
3x1 + 3x2 + S1 = 24 (input I)
2x1 + 4x2 + S2 = 20 (input II)
3x1 + S3 = 21 (input III)
x1; x2; S1; S2; S3 ≥ 0
Matrix
Basis Cj X1 X2 S1 S2 S3 Q Tes
ratio
25 15 0 0 0
S1 0 3 3 1 0 0 24 8
S2 0 2 4 0 1 0 20 10
S3 0 3 0 0 0 1 21 7
Zj 0 0 0 0 0
Cj-Zj 25 15 0 0 0
S3 3/3; 0/3; 0/3; 0/3; 1/3; 21/3
S1 3 – (3 x 3/3) = 0 S2 2 – (2 x 3/3) = 0
3 – (3 x 0/3) = 3 4 – (2 x 0/3) = 4
1 – (3 x 0/3) = 1 0 – (2 x 0/3) = 0
0 – (3 x 0/3) = 0 1 – (2 x 0/3) = 1
0 – (3 x 1/3) = -1 0 – (2 x 1/3) = -2/3
24 – (3 x 21/3) = 3 20 – (2 x 21/3) = 6
Cj- Zj 25 – (25 x 3/3) = 0
15 – (25 x 0/3) = 15
0 – (25 x 0/3) = 0
0 – (25 x 0/3) = 0
0 – (25 x 1/3) = 25/3
Matrix baru
Basis Cj X1 X2 S1 S2 S3 Q Tes
ratio
25 15 0 0 0
S1 0 0 3 1 0 -1 3 1
S2 0 0 4 0 1 -2/3 6 3/2
X1 25 1 0 0 0 1/3 7 ∞
Zj 25 0 0 0 25/3
Cj-Zj 0 15 0 0 -
25/3
S1= X2 0/3; 3/3; 1/3; 0/3; -1/3; 3/3
S2 0 – (4 x 0/3) = 0 X1 1 – (0 x 0/3) = 1
4 – (4 x 3/3) = 0 0 – (0 x 3/3) = 0
0 – (4 x 1/3) = -4/3 0 – (0 x 1/3) = 0
1 – (4 x 0) = 1 0 – (0 x 0/3) = 0
-2/3 – (4 x -1/3) = 2/3 1/3 – (0 x -1/3) =
1/3
6 – (4 x 3/3) = 2 7 – (0 x 3/3) = 7
cj – Zj 0 – (15 x 0/3) = 0
15 – (15 x 3/3) = 0
0 – (15 x 1/3) = -5
0 – (15 x 0/3) = 0
-25/3 – (15 x -1/3) = -10/3
Matrix baru
Basis Cj X1 X2 S1 S2 S3 Q Tes
ratio
25 15 0 0 0
X2 15 0 1 1/3 0 -1/3 1
S2 0 0 0 -4/3 1 2/3 2
X1 25 1 0 0 0 1/3 7
Zj 25 15 5 0 10/3 190
Cj-zj 0 0 -5 0 -10/3
Ketentuan-ketentuan tambahan:
• Jika terdapat lebih dari satu kolom bernilai
negatif angka terbesar pilih salah satu
diantara 2 secara sembarang, akan
menghasilkan keputusan yang sama.
• Dua baris atau lebih memiliki indeks positif
terkecil pilih baris kunci secara bebas
diantara keduanya.
• Kenaikan nilai Z tidak terbatas LP tidak perlu
diteruskan cukup disebutkan bahwa kenaikan
nilai Z dapat tidak terbatas. (mis: batasan X2
tidak ada).
Penyimpangan-penyimpangan dari
bentuk standar
• Batasan dengan tanda “sama dengan”.
Jika batasan menggunakan tanda “sama
dengan” maka cara mengatasi dengan
menambah variabel buatan (artificial variabel).
Misal: fungsi tujuan: Z = 3X1 + 5X2
Batasan: 1) 2X1 ≤ 8
2) 3X2 ≤ 15
3) 6X1 + 5X2 = 30
Penambahan var artificial
Standarisasi model:
Fungsi tujuan: Z = 3X1 + 5X2 – MX5, sehingga
menjadi:
Z – 3X1 – 5X1 + MX5 = 0
Batasan:
1) 2X1 + X3 = 8
2) 3X2 + X4 = 15
3) 6X1 + 5X2 + X5 = 30
Karena ada penambahan var buatan, maka fungsi
tujuan harus disesuaikan dengan menambah
bilangan M
Sehingga fungsi tujuan menjadi
Z = 3X1 + 5X2 – MX5
Bilangan M bernilai besar tetapi tidak
terbatas, sehingga nilai Z bisa diperoleh
jika nilai X5 = 0. sehingga standarisasi
funhgsi tujuan menjadi:
Z – 3X1 – 5X1 + MX5 = 0
• Persamaan tersebut tidak memungkinkan menggunakan
metode simplex, sebab nilai pada var dasar pada
persamaan harus bernilai 0, padahal X5 merupakan var
dasar pada tabel permulaan. Oleh karena itu diubah
dengan cara: mengurangi dengan M dikalikan dengan
baris batasan yang bersangkutan. Contoh diatas
menjadi:
( -3 ; -5 ; 0 ; 0; M ;0 )
M ( 6 ; 5 ; 0 ; 0 ; 1 ; 30 ) –
((-6M-3); (-5M-5) ; 0 ; 0 ; 0 ;-30M)
Analisis Sensitivitas
• Setelah ditemukan yang optimal dari LP model,
kadang dirasa perlu ditelaah lagi kemungkinan-
kemungkinan yang terjadi sebagai akibat
terjadinya perubahan-perubahan pada koefisien
dalam model.
• Apabila hal itu terjadi, harus memutuskan
menghitung lagi dari awal dengan masalah baru
(karena perubahan koefisien).
• Ini memakan waktu yang lama
mempermudah dilakukan analisis sensitivitas
(Post Optimality Analysis).
Perubahan yang mungkin
terjadi:
• Katerbatasan kapasitass resources nilai
kanan fungsi batasan
• Koefisien-koefisien fungsi tujuan
• Koefisien teknis fungsi batasan, yaitu
koefisien yang menunjukkan erapa bagian
kapasitas resources yang di “konsumsi”
oleh satu satuan kegiatan
• Penambahan variabel baru
• Penambahan batasan baru
Akibat perubahan:
• Penyelesaian optimal tidak berubah
var. dasar maupun nilai-nilainya tidak
mengalami perubahan
• Variabel-variabel dasar mengalami
perubahan, tetapi nilai-nilainya tidak
berubah
• Penyelesaian optimal sama sekali
berubah
