BAB II TINJAUAN PUSTAKA
2.1
Pemrograman Linier (Linear Programming) Pemrograman linier (linear programming) merupakan salah satu teknik riset
operasi yang mampu menyelesaikan masalah optimasi sejak diperkenalkan di akhir dasawarasa 1940-an. Keberhasilannya dalam menjabarkan berbagai situasi kehidupan nyata seperti di bidang militer, industri, pertanian, transportasi, ekonomi, kesehatan, dan bahkan ilmu sosial. Selain itu, tersedianya program komputer yang sangat efisien untuk memecahkan masalah pemrograman linier merupakan faktor penting dalam tersebarnya penggunaan teknik ini. Teknik pemrograman linier memberikan analisa pasca-optimum dan analisis parametrik yang sistematis untuk memungkinkan pengambilan keputusan (Taha, 1996). Permasalahan model program linier dapat memiliki pembatas-pembatas linier yang bertanda (≤,=,≥), dan peubah-peubah keputusannya dapat merupakan peubah nonnegatif, dapat pula peubah yang tidak terbatas dalam tanda (unrestricted in sign). Pemrograman dimulai dengan formulasi umum permasalahan pemrograman linier, formulasi umum tersebut terdiri dari fungsi tujuan yang akan dicari solusi optimalnya baik itu dalam memaksimumkan maupun meminimumkan berdasarkan ketentuan yang tersedia yang dirumuskan dalam fungsi pembatas.
5
6
Terdapat bentuk standar yang menjadi sifat pemrograman linier (Taha, 1996), antara lain: a. Semua pembatas linier membentuk persamaan dengan ruas kanan yang nonnegatif. b. Semua peubah keputusan harus merupakan peubah nonnegatif. c. Fungsi tujuan dapat berupa maksimasi atau minimasi. Berdasarkan ketentuan tersebut beberapa cara yang dapat digunakan untuk mengubah bentuk permasalahan pemrograman linier dari bentuk asli ke dalam bentuk standar adalah: 1. Pembatasan linier (linear constraint) a) Pada pembatasan linier bertanda “≤” dapat dibentuk menjadi suatu persamaan “=” dengan cara menambahkan ruas kiri dengan slack variable (peubah penambahan). Slack variable digunakan untuk mewakili jumlah kelebihan ruas kanan pembatasan linier dibandingkan dengan ruas kirinya, sehingga dapat diartikan untuk mewakili jumlah sumber daya yang tidak dipergunakan. Misalnya dalam batasan: +2
≤4
(2.1)
Maka tambahkan slack variable
≥ 0 ke sisi kiri untuk memperoleh
persamaan: +2
+
= 4 ,
≥0
(2.2)
7
b) Pada pembatas linier bertanda “≥” dapat dibentuk menjadi suatu persamaan “=” dengan cara mengurangkan ruas kiri dari pembatas linier dengan surplus variable (peubah penambah negatif). Pada pembatas linear bertanda “≥”, ruas kanan umumnya mewakili penetapan persyaratan minimum, sehingga surplus variable dapat diartikan untuk mewakili jumlah kelebihan ruas kiri pembatas linier dibandingkan persyaratan minimumnya. Misalkan dalam batasan: 3
+2
−2
≥ 6
(2.3)
Karena sisi kanan pembatas linier lebih kecil dari pada sisi kirinya, maka dikurangkan dengan surplus variable
≥ 0 dari sisi kiri untuk
memperoleh persamaan: +2
3
−2
−
= 6 ,
≥ 0
(2.4)
c) Ruas kanan dari suatu persamaan dapat dijadikan bilangan nonnegatif dengan cara mengalikan kedua ruas dengan -1. d) Arah pertidaksamaan berubah jika kedua ruas dikalikan dengan -1. 2. Peubah keputusan Suatu peubah keputusan
yang tidak terbatas dalam tanda dapat
dinyatakan
peubah
sebagai
dua
keputusan
nonnegatif
dengan
menggunakan substitusi: = dengan
,
−
(2.5)
≥ 0 . Selanjutnya substitusi ini harus dilakukan pada
seluruh pembatas linier dan fungsinya.
8
3. Fungsi tujuan Pemasalahan model pemrograman linier standar dapat berupa maksimasi atau minimasi (Taha, 1996). Secara matematis dapat dinyatakan sebagai berikut: Maksimumkan
( )
atau Minimumkan
( )
Model matematika pemrograman linier dapat ditulis dalam bentuk formulasi umum sebagai berikut: Fungsi tujuan: Optimalkan
( )=
Batasan:
,
+
+ … +
(2.6)
+
+ … +
≤
, atau
+
+ … +
≥
, atau
+
+ … +
=
,…,
≥0
Keterangan: : Variabel keputusan pemrograman linier ( ) : Fungsi tujuan : Koefisien fungsi tujuan : Koefisien fungsi kendala : Nilai fungsi kendala Untuk nilai = 1,2,3, … , Untuk nilai = 1,2,3, … ,
9
Berdasarkan formulasi umum pemrograman linier yang dijelaskan pada persamaan (2.6) di atas, terdapat dua kategori permasalahan yaitu masalah maksimasi dan masalah minimasi, masing-masing dijelaskan dalam persamaan (2.7) dan (2.8) pada formulasi umum sebagai berikut: Masalah Maksimasi ( )=
Maksimumkan : Batasan
+
+
: ,
+ … +
+ … +
,…,
(2.7)
≤
≥0
Masalah Minimasi Minimumkan: Batasan
( )= +
: ,
2.2
,…,
+
+ … +
+ … +
(2.8)
≥
≥0
Pemrograman Nonlinier Pemrograman nonlinier merupakan salah satu teknik penyelesaian masalah
optimasi dalam matematika. Suatu permasalahan optimasi disebut nonlinier jika fungsi tujuan dan kendalanya mempunyai bentuk nonlinier pada salah satu atau keduanya (Luknanto, 2000). Dalam penyelesaian permasalahan nonlinier terdapat dua kondisi yaitu nonlinier tanpa kendala dan nonlinier dengan kendala.
10
2.2.1 Pemrograman Nonlinier tanpa Kendala Pemrograman nonlinier tanpa kendala dikenal dua kondisi yaitu: 1. Satu Variabel tanpa Kendala Pada
optimasi
nonlinier
satu
variabel
tanpa
kendala,
dalam
menyelesaikan permasalahan maksimasi ( ) atau minimasi ( ) salah satunya dengan menggunakan kalkulus differensial. 2. Multi Variabel tanpa Kendala Cara analitis yang diterapkan pada permasalahan optimasi satu variabel tanpa kendala dapat pula diterapkan dalam permasalahan optimasi multi variabel tanpa kendala. 2.2.2 Pemrograman Nonlinier Berkendala Pemrograman nonlinier berkendala dikenal dua kondisi yaitu: 1. Multi Variabel dengan Kendala Persamaan Multi variabel dengan kendala persamaan mempunyai bentuk umum sebagai berikut: Maksimumkan/Minimumkan = ( ) dengan
=
,…
dengan kendala ( ) = 0, dengan = 1,2, … ,
; = 1,2, …
(2.9)
11
Dalam hal ini m ≤ n (banyak kendala lebih kecil daripada banyak variabel). Pada program minimasi dapat diubah ke dalam bentuk maksimasi dengan mengalikan -1 terhadap fungsi objektif, begitupula pada bentuk minimasi kedalam bentuk maksimasi. Metode yang dapat digunakan untuk menyelesaikan masalah ini adalah metode Lagrange (Luknanto, 2000). Sejauh ini proses optimasi dilakukan tanpa mengunakan kendala, padahal seringkali persoalan optimasi dihadapkan dengan kendala tertentu. Multiplier Lagrange, sesuai namanya dikemukakan oleh Joseph Louis Lagrange (1736-1813). Teori ini dapat digunakan untuk menangani permasalahan program nonlinier. Metode pengali Lagrange merupakan sebuah teknik dalam menyelesaikan masalah optimasi dengan kendala persamaan, yaitu dengan mengubah persoalan titik ekstrem berkendala menjadi bebas kendala. Fungsi yang membentuk dari transformasi tersebut dinamakan fungsi Lagrangian yang didefinisikan sebagai (Rao, 1984): ( , )= ( )+ Keterangan: : Fungsi Lagrange ( ) : Fungsi tujuan : Fungsi kendala : Variabel slack
( ) (2.10)
12
Teorema: Syarat perlu bagi sebuah fungsi f(X) dengan kendala gj(X) = 0, dengan j=1,2,…,m agar mempunyai minimum relatif pada titik X* adalah turunan parsial pertama dari fungsi Lagrange nya yang didefinisikan sebagai L=L(x1,x2,…,xn, λ1, λ2,…,λm) terhadap setiap argumenya mempunyai nilai nol. Teorema: Syarat harus bagi sebuah fungsi f(X) agar mempunyai minimum (atau maksimum) relatif pada titik
X* adalah jika fungsi kuadrat Q, yang
didefinisikan sebagai: =
(2.11)
dievaluasi pada X = X* harus definit positif (atau negatif) untuk setiap nilai dX yang memenuhi semua kendala. Syarat perlu agar persamaan (2.11) menjadi definit positif (atau negatif) untuk setiap variasi nilai dX adalah setiap akar dari polinomial, zi yang didapat dari determinan persamaan di bawah ini harus positif (atau negatif) (Rao,1984). (
− ) ( ⋮ ⋮
− ) ⋮
⋮
⋱
⋮
⋯ ⋯ ⋯ ⋮ ⋮ ⋯ ( − ) ⋯ 0 ⋯ 0 ⋯ ⋮ ⋮ ⋯ 0
⋯ ⋯ ⋮ ⋯ ⋯ 0 ⋯ 0 ⋯ ⋮ ⋯ 0 ⋯
⋮ 0 0 ⋮ 0
=0
13
dengan ( ∗, )
=
dan
( ∗)
=
(2.12)
Jika diperoleh nilai z negatif, maka penyelesaian sudah mencapai maksimum. Sementara apabila diperoleh nilai z positif, maka penyelesaian dapat dikatakan minimum. 2. Multi Variabel dengan Kendala Pertidaksamaan. Bentuk umum dari teknik optimasi multi variabel dengan kendala pertidaksamaan adalah sebagai berikut: Minimumkan = ( ) dengan
=
,
,…
(2.13)
dengan kendala ( ) ≤ 0, dengan = 1,2, … , Penyelesaian dari permasalahan tersebut adalah mengubah kendala pertidaksamaan menjadi persamaan dengan menambah variabel slack Sehingga permasalahan optimasi persamaan (2.13) dapat ditulis sebagai: Minimumkan = ( ) dengan
=
,
,…
dengan kendala ( , )= =
,
( )+ ,…
= 0 dengan = 1,2, … ,
adalah vektor variabel slack.
(2.14)
.
14
Permasalahan ini dapat diselesaikan metode pengali Lagrange. Untuk itu, dibentuk fungsi Lagrange sebagai berikut: ( , , )= ( )+
( , ) (2.15)
Syarat perlu untuk penyelesaian optimum dari persamaan (2.15), diperoleh dari penyelesaian sistem persamaan berikut: ( , , )=
( , , )=
( )+
( ) = 0 ; = 1,2, … , (2.16)
( , , )=
( , , )=2
( )+
= 0 ; = 1,2, … ,
(2.17)
= 0 ; = 1,2, … ,
(2.18)
Syarat optimasi agar persamaan (2.14) mencapai titik minimumnya dapat pula dicari dengan syarat Karush-Kuhn-Tucker (KKT). Syarat Karush-KuhnTucker (KKT) merupakan syarat perlu dan cukup untuk sebuah minimum global (Rao, 1984). 2.3 Syarat Karush-Kuhn-Tucker (KKT) Pada tahun 1951, H.W Kuhn dan A.W Tucker mengemukakan suatu teknik optimasi yang dapat dipergunakan untuk mencari solusi optimum dari suatu fungsi tanpa memandang linier atau nonlinier. Metode Karush-KuhnTucker (KKT) ini bersifat teknik umum dalam pencarian titik optimum dari setiap
fungsi.
Jika
menghadapi
masalah
optimasi
dalam
bentuk
maksimumkan/minimumkan: = ( ) dengan
=
,
,…,
(2.19)
15
dengan kendala ( ) ≤/≥ dengan = 1,2,3, … , ≥0 ≤
(jumlah kendala lebih kecil dari variabel)
Dalam Amalia (2010) pertama tuliskan kembali persyaratan-persyaratan yang tak negatif seperti − adalah
≤ 0, −
≤ 0, … , −
≤ 0 sehingga himpunan kendalanya
+ persyaratan ketidaksamaan yang masing-masing dengan tanda lebih
kecil dari pada atau sama dengan. Kemudian tambahkan variabel-variabel kurang ,
,…,
berturut-turut pada ruas kiri dari kendala-kendala tadi, yang
dengan demikian merubah tiap-tiap ketidaksamaan menjadi suatu kesamaan. Variabel slack yang ditambahkan berbentuk suku-suku kuadrat untuk menjamin bahwa mereka tak negatif. Kemudian bentuk fungsi Lagrange: ( )−
≡ ( )−
−
−
+
(2.20)
Fungsi lagrange yang dibentuk adalah fungsi tujuan ditambahkan dengan total kendala. Untuk
,
,…,
adalah pengali-pengali Lagrange. Langkah
terakhir selesaikan sistem persamaan: = 0 ( = 1,2, … ,2 +
) (2.21)
= 0 ( = 1,2, … ,
+ ) (2.22)
≥ 0 ( = 1,2, … ,
+ ) (2.23)
16
Persamaan-persamaan (2.21), (2.22), dan (2.23) membentuk persyaratan KarushKuhn-Tucker (KKT) untuk maksimasi/minimasi program linier dan nonlinier. Sehingga syarat Karush-Kuhn-Tucker (KKT) untuk persamaan (2.13) adalah sebagai berikut: Minimumkan: = ( ) dengan
=
,
,…,
dengan kendala ( ) ≤ 0 dengan = 1,2,3, … , dapat dinyatakan dalam satu set pernyataan sebagai berikut: +
= 0, ( = 1,2, … , ) (2.24)
= 0, ( = 1,2, … ,
)
≤ 0, ( = 1,2, … ,
)
≥ 0, ( = 1,2, … ,
)
Catatan: (i) Jika permasalahannya adalah memaksimumkan, maka (ii) Jika kendalanya adalah
≥ 0, maka
≤ 0.
≤ 0.
(iii) Jika permasalahannya adalah memaksimumkan dan jika kendalanya adalah ≥ 0, maka
≥ 0.
17
2.4
Metode Faktor Pengali Karush-Kuhn-Tucker (KKT) Nilai optimum (nilai maksimum atau nilai minimum) suatu fungsi multi
variabel dengan kendala (constrains) berupa suatu persamaan adalah suatu kasus optimasi yang sering ditemukan dalam teori maksimum dan minimum yang terdapat dalam kalkulus. Adapun metode matematika yang dapat digunakan untuk kasus tersebut adalah metode pengali Lagrange (Purcell et.al, 2004). Sedangkan menentukan nilai optimum suatu fungsi matematika multi variabel dengan kendala berupa suatu pertidaksamaan adalah suatu hal yang perlu dipelajari lebih lanjut dalam teori optimasi. Metode faktor pengali Karush-Kuhn-Tucker (KKT) adalah suatu metode untuk menentukan nilai optimum suatu fungsi dengan kendala berupa pertidaksamaan (Rao, 1984). 2.5
Prosedur Penggunaan Metode Karush-Kuhn-Tucker (KKT) Prosedur
menggunakan
metode
Karush-Kuhn-Tucker
(KKT)
dalam
memecahkan suatu masalah optimasi dengan kendala berupa pertidaksamaan, langkahnya sama halnya dengan menggunakan metode Lagrange untuk memecahkan masalah optimasi dengan kendala berupa suatu persamaan yaitu (Artawan, 2012): 1. Membentuk suatu fungsi ‘Lagrangian’ L, maka akan dapat menghitung titik-titik kritisnya dan menguji nilai fungsi objektif pada setiap titik kritis yang memuat fungsi objektif optimal.
18
Jadi dalam hal ini dibentuk suatu fungsi Lagrange yang didefinisikan dengan: ℎ ( ) (2.25)
( , )= ( )+
Selanjutnya optimumkan fungsi objektif
( ) terhadap
∈ ∆.
2. Mencari semua solusi ( , ) dalam himpunan persamaan berikut: ( , ) = 0 ; ( = 1,2, … , ) (2.26)
dengan ( , ) ≥ 0 ;
≥ 0 (2.27)
( , ) = 0 ; = 1,2 … (2.28) Penyelesaian dari
setiap sistem persamaan ini, selanjutnya disebut titik
kritis dari L. Selanjutnya jika kita misalkan M menotasikan himpunan titiktitik kritis yaitu M ={(x, λ)|(x, λ) adalah titik kritis dari L}. 3. Langkah terakhir yaitu menghitung nilai dari f untuk setiap titik kritis yang merupakan himpunan bagian dari M, yang memuat fungsi tujuan menjadi optimum. Adapun prosedur langkah penggunaaan metode Karush-KuhnTucker (KKT) untuk masalah minimasi adalah sama prosedurnya dengan masalah maksimasi hanya saja dalam masalah minimasi.
