Program Linier
Mata Kuliah Riset Operasi
Program Studi Pendidikan Matematika UNUGIRI
Oleh :
M. Ivan Ariful Fathoni, [Link].
Definisi Linear Programming
3 komponen dari linear programming
problem (LP)
Fungsi obyektif (tujuan): fungsi Dimaksimumkan
linier dari peubah keputusan
Diminimumkan
Fungsi kendala (constraints): Peubah Keputusan
fungsi linier yang membatasi nilai
peubah keputusan x1 ,..., xn
Batasan tanda (sign restrictions) Positif
bagi peubah keputusan Negatif
Tidak dibatasi tanda
Contoh Permasalahan LP
Perusahaan mainan kayu: Giapetto’s
Woodcarving
Memproduksi dua tipe mainan: Soilder &
Train
Biaya-biaya dibutuhkan untuk membuat per
buah mainan
Persediaan bahan mentah (kayu) dan jam
kerja untuk membuat per buah mainan
terbatas setiap minggunya
Berapa buah Soilder dan berapa buah Train
yang harus diproduksi per minggu agar
◦ Keuntungan maksimum
Tabel Biaya Giapetto’s Woodcarving
Batasan Apa peubah
#Soldier/ #Train/ Per keputusannya?
minggu minggu minggu
Harga Jual ($)/buah 27 21
x1 :# Soldier/minggu
Harga Bahan ($)/buah 10 9
x2 :# Train/minggu
Labor cost ($)/buah 14 10
Profit (Harga Jual -
Cost) 3 2
Carpentry Hour/buah 1 1 80
Finishing Hour/buah 2 1 100
Demand <=40 ∞
Fungsi Obyektif? Maksimum profit
Jumlah
Produksi/minggu X1 buah soldier X2 buah train
Profit/buah 3 2
max z = 3x1 + 2 x2
Fungsi Kendala? Semua sumber daya yang terbatas
Jumlah Batas/mi
produksi/minggu X1 soldier X2 train nggu
Carpentry Hour/buah 1 1 80
x1 + x2 80
Finishing Hour/buah 2 1 100 2 x1 + x2 100
Demand <=40 ∞ x1 40
Batasan tanda? Sifat dari peubah keputusan, jumlah x1 0
barang → harus non negatif
x2 0
LP untuk permasalahan Giapetto’s Woodcarving:
max z = 3x1 + 2 x2
s.t. x1 + x2 80
2 x1 + x2 100
x1 40
x1 0, x2 0
s.t.: subject to → semua peubah keputusan harus
memenuhi semua kendala dan batasan tanda
Feasibel Region and Optimal
Solution
Feasibel region (daerah feasibel):
Himpunan semua titik yang memenuhi kendala dan
batasan tanda
Optimal Solution (Solusi optimal): untuk
masalah maksimisasi/minimisasi
Titik di dalam daerah feasibel dengan nilai fungsi
obyektif paling besar/kecil
Penentuan Solusi Optimal Secara
Grafis (LP 2 Peubah)
Langkah 1: Gambar daerah feasibel
Langkah 2: Gambar garis isoprofit
Langkah 3: Gerakkan garis isoprofit di dalam
daerah feasibel yang menaikkan/menurunkan
nilai Z. Titik terakhir dalam daerah feasibel
yang terkena garis isoprofit/isocost adalah
solusi optimal (maks/min)
Solusi Grafis untuk LP 2 Peubah
Gambar daerah
feasibel: himpunan
seluruh titik yang
memenuhi kendala
x1 + x2 80
daerah di bawah garis CD :
x2 = 80 − x1
C : (80,0), D : (0,80)
2 x1 + x2 100
daerah di bawah garis AB :
x2 = 100 − 2 x1
A : (50,0), B : (0,100)
Solusi Grafis untuk LP 2 Peubah
x1 40
daerah di bawah garis EF :
x1 = 40
E : ( 40,0), D : ( 40,20)
x1 0, x2 0,
daerah dikuadran I
Daerah feasibel: H-E-
F-G-D
Solusi Grafis untuk LP 2 Peubah
Gambar Isoprofit line:
z = 3x1 + 2 x2 = 180
(60,0); (0,90)
Solusi optimal:
Titik di dalam HEFGD, yang
terkena isoprofit line paling
akhir (maks), jika isoprofit
line digerakkan sejajar dari
titik 0, ke arah atas
G : ( 20,60)
Max profit z = 3(20 ) + 2(60 ) = 180
Convex Set (Himpunan Konveks)
S: himpunan konveks jika garis yang
menghubungkan dua titik manapun di
dalam S juga berada di dalam S
(a) dan (b) himpunan
konveks
Extreme Point (Titik ekstrim)
Untuk sembarang himpunan konveks S, P di
dalam S adalah titik ekstrim jika:
Garis yang berada di dalam S mempunyai P
sebagai akhir garis
A, B, C, D di dalam (b) adalah
titik-titik ekstrim
Solusi Optimal
Dengan daerah feasibel berupa himpunan
konveks
Solusi Optimal selalu terletak pada salah
satu dari titik ekstrim pada wilayah
feasibel
Pencarian solusi optimal dibatasi pada
titik-titik ekstrim
◦ Tidak perlu pada semua titik di daerah feasibel
Masalah Woodcarving berdasarkan titik Ekstrim
H-E-F-G-D adalah titik-titik
ekstrim dari wilayah
feasibel
G : ( 20,60)
Titik ekstrim dengan nilai Z
paling besar
Max profit z = 3(20 ) + 2(60 ) = 180
Contoh Masalah Minimisasi
Dorian Auto memproduksi mobil dan
truk
Pelanggannya: high income women (HIW)
and high income men (HIM).
Dorian Auto mengiklankan produknya
dengan cara:
◦ Membeli 1 menit slot waktu iklan
Dua acara TV yang menjadi target:
◦ Acara komedi
◦ Acara pertandingan sepak bola
Ingin diputuskan berapa menit slot iklan
yang harus dibeli pada kedua acara
tersebut
◦ Agar sesuai target jumlah penonton iklan dari
HIW dan HIM
◦ Dengan biaya seminimum mungkin
Apa peubah keputusan?
x1 :# slot 1 menit iklan pada acara komedi
x2 :# slot 1 menit iklan pada acara sepak bola
Masalah Dorian Auto di dalam Tabel
# 1 menit # 1 menit
slot iklan di slot iklan di
Komedi Sepak Bola Target
Jumlah pemirsa HIW (juta orang) 7 2 28
Jumlah pemirsa HIM (juta orang) 2 12 24
Biaya (ribuan $) 50 100
Formulasi LP masalah Dorian
Fungsi Obyektif? Minimum biaya
X1: X2:
# 1 menit slot # 1 menit slot
iklan di iklan di Sepak
Komedi Bola
Biaya (ribuan $) 50 100
min z = 50 x1 + 100 x2
Kendala? Semua target yang ingin dicapai
X1 X2 Target
Jumlah pemirsa HIW (juta orang) 7 2 28
Jumlah pemirsa HIM (juta orang) 2 12 24
HIW 7 x1 + 2 x2 28 HIM 2 x1 + 12 x2 24
Formulasi Masalah Dorian
Batasan tanda? Semua peubah keputusan tidak ada
yang negatif
x1 0, x2 0
LP untuk masalah Dorian Auto:
min z = 50 x1 + 100 x2
s.t 7 x1 + 2 x2 28
2 x1 + 12 x2 12,
x1 , x2 0
Solusi Grafis untuk Masalah Dorian
Gambar daerah feasibel:
himpunan seluruh titik yang
memenuhi kendala
B
7 x1 + 2 x2 28
daerah di atas garis AB :
x2 = 14 − 7
2 x1
A : ( 4,0), B : (0,14)
2 x1 + 12 x2 24
daerah di atas garis CD : C
x2 = 2 − 12
2
x1
C : (12,0), D : (0,2)
Solusi Grafis untuk Masalah Dorian
x1 0, x2 0,
daerah dikuadran I B
Daerah feasibel: daerah
di atas C-E-B
Gambar Isocost line:
Z=600
z = 50 x1 + 100 x2 = 600 E
C
(12,0); (0,6)
Solusi Grafis untuk Masalah Dorian
Solusi Optimal:
B
Titik di dalam daerah
feasibel yang terkena
isocost line paling akhir
(min)
E : (3.6,1.4 ) Z=600
Perpotongan AB dan CD
AB : x2 = 14 − 7
2 x1 E
C
CD : x2 = 2 − 2
12 x1
Min cost z = 50(3.6 ) + 100(1.4 ) = 320