BAB 2 LANDASAN TEORI

BAB 2

LANDASAN TEORI

2.1. Bicriteria Linear Programming (BLP) Pesoalan optimisasi dengan beberapa fungsi tujuan memperhitungkan beberapa tujuan yang konflik secara simultan, secara umum Multi objective programming (MOP) memiliki bentuk umum sebagai berikut. Minimum

𝒇 𝒙 = 𝒇𝟏 𝒙 , 𝒇𝟐 𝒙 , … , 𝒇𝒑 𝒙

Kendala

𝒙∈𝑿

(2.1)

dimana 𝑋 ⊆ ℝ𝑛 adalah himpunan layak (feasible set) dan 𝑓𝑖 𝑥 , 𝑖 = 1,2, … , 𝑝 adalah fungsi bernilai riil. Persamaan (2.1) disebut multiple objective linear programming (MOLP) Minimum

𝒇 𝒙 = 𝒄𝑻𝒊 𝒙 , ∀ 𝒊 = 𝟏, 𝟐, … , 𝒑

Kendala

𝓧 = {𝒙 ∈ ℝ𝒏 : 𝑨𝒙 ≤ 𝒃, 𝒙 ≥ 𝟎}

(2.2)

Dimana 𝑐 = 𝑐1 , 𝑐2 , … , 𝑐𝑝 ∈ ℝ𝑛 , 𝑨 adalah matriks 𝑚 × 𝑛 dan 𝑏 = 𝑏1 , 𝑏2 , … 𝑏𝑚 ∈ ℝ𝑚 , 𝒇 𝒙 disebut objective space dan 𝓧 disebut decision space. Persoalan optimasi satu tujuan seperti linear programming biasaya memiliki satu penyelesaian yang disebut dengan solusi optimal. Sebaliknya persoalan optimasi kasus MOP meiliki semua penyelesaian layak (feasible solution) yang disebut dengan solusi efisien dan solusi efisien lemah. Definisi (Solusi efisien) Solusi layak dari 𝑥 ∈ 𝒳 dikatakan efisien atau pareto optimal jika dan hanya jika tidak terdapat titik lain 𝑥 ∈ 𝒳 sehingga 𝑓 𝑥 ≤ 𝑓(𝑥) Definisi (Solusi efisien lemah) Solusi layak dari 𝑥 ∈ 𝒳 dikatakan efisien lemah atau weakly pareto optimal jika dan hanya jika tidak terdapat titik lain 𝑥 ∈ 𝒳 sehingga 𝑓 𝑥 < 𝑓(𝑥)

4 Universitas Sumatera Utara

Bicreteria linear programming (BLP) merupakan kasus khusus dari persamaan (2.1) dengan 𝑝 = 2 yang dapat ditulis bentuk umum nya sebagai berikut Minimum

𝒄𝒙

Kendala

𝓧 = {𝒙 ∈ ℝ𝒏 : 𝑨𝒙 ≤ 𝒃, 𝒙 ≥ 𝟎}

dimana 𝑐 merupakan matriks 2 × 𝑚 Ehrgott (2005) mengemukakan solusi efisien dari BLP akan sama dengan penyelesaian optimum linear programming parametic yang memiliki bentuk umum : 𝒄 𝝀 ≔ 𝝀𝒄𝑻𝟏 + (𝟏 − 𝝀)𝒄𝑻𝟐 Minimum

𝒄 𝝀 𝒙

Kendala

𝑨𝒙 = 𝒃 ; 𝒙 ≥ 𝟎

(2.3)

𝝀 adalah parameter yang bernilai 0 ≤ 𝜆 ≤ 1 dan 𝒄 𝝀 𝒙 adalah fungsi tujuan parameter. Langkah-langkah Parametric Simplex Algorithm pada Bicriteria Linear Programming yaitu : 1. Memodelkan data 𝐴, 𝑏, 𝐶 pada Bicriteria Linear Programming 2. Menambah slack variabel pada persamaan Bicriteria Linear Programming 3. Membuat tabel simplex, dimulai dengan 𝜆 = 1 4. Mendefinisikan basis yang akan keluar (ℬ) 5. Mendefinisikan variabel yang akan masuk (𝐼) Dimana 𝐼 = 𝑖 ∈ ℕ ∶ 𝑐𝑖2 < 0 , 𝑐𝑖1 ≥ 0 ≠ ∅ Jika 𝐼 = ∅ STOP, maka penyelesaian telah efisien −𝑐 2

6. Menetukan 𝜆′ = 𝑚𝑎𝑥𝑖∈𝐼 𝑐 1 −𝑐𝑖 2 𝑖

𝑖

−𝑐 2

7. Menentukan 𝑠 ∈ 𝑎𝑟𝑔𝑚𝑎𝑥 𝑖 ∈ 𝐼: 𝑐 1 −𝑐𝑖 2 𝑖

𝑖

𝑏

8. Menentukan 𝑟 ∈ 𝑎𝑟𝑔𝑚𝑖𝑛 𝑗 ∈ ℬ: 𝐴 𝑗 , 𝐴𝑗𝑠 > 0 𝑗𝑠


9. Kembali ke tahap 5 jika hasil belum merupakan solusi efisien

2.2 Bilangan Interval Moore (2009) Mengemukakan interval tertutup (untuk seterusnya disebut interval) dinotasikan dengan [𝑎, 𝑏] memiliki notasi 𝒂, 𝒃 = {𝒙 ∈ ℝ: 𝒂 ≤ 𝒙 ≤ 𝒃} Definisi (Degenerate Interval) Moore (2009) Andaikan 𝑋 = [𝑥, 𝑥] dan 𝑥 = 𝑥 maka 𝑥 merupakan suatu bilangan riil 𝑥 atau merupakan interval 𝑋 = [𝑥, 𝑥] Definisi (Operasi Aritmatika dari Interval) Andaikan 𝐴 = 𝑎, 𝑎 , 𝐵 = 𝑏, 𝑏 , 𝐶 = [𝑐, 𝑐] dan andaikan * dinotasikan sebagai operasi aritmatika + , − , × , ÷ pada interval. Maka * operasi dari interval dinotasikan. 𝐴∗𝐵 Sehingga Operasi Penjumlahan

𝐴 + 𝐵 = [𝑎 + 𝑏, 𝑎 + 𝑏]

Operasi Pengurangan

𝐴 − 𝐵 = [𝑎 − 𝑏, 𝑎 − 𝑏]

Operasi Perkalian

𝐴 × 𝐵 = min 𝑎 𝑏, 𝑎 𝑏, 𝑎 𝑏, 𝑎 𝑏 , max 𝑎 𝑏, 𝑎 𝑏, 𝑎 𝑏, 𝑎 𝑏

Operasi Perkalian skalar

𝑘. 𝐴 = 𝑘𝑎, 𝑘𝑎

Operasi Pembagi

𝑎 ÷ 𝐵 = 𝑎, 𝑎 × 1 𝑏 , 1 𝑏

Sifat komutatif Sifat asosiatif

𝐴+𝐵 =𝐵+𝐴; 𝐴×𝐵 = 𝐵×𝐴 𝐴+𝐵 +𝐶 =𝐴+ 𝐵+𝐶 ;

𝐴×𝐵 ×𝐶 =𝐴× 𝐵×𝐶


2.3 Interval Linear Programming Dengan kendala (≤) Allahdadi dan Mishmat (2011) mengemukakan pada kendala linear programming yang memiliki tanda ketidaksamaan lebih kecil sama dengan (≤) memiliki daerah feasible terbesar dan daerah feasible terkecil dinyatakan dalam notasi matematika Teorema 1 Andaiakan jika terdapat suatu pertidaksamaan interval maka

𝒏 𝒋=𝟏 𝒂𝒋 𝒙𝒋

≤ 𝒃 merupakan daerah feasible terbesar dan

𝒏 𝒋=𝟏

𝒂𝒊𝒋 𝒂𝒊𝒋 𝒙𝒋 ≤ 𝒃, 𝒃


≤ 𝒃 Merupakan

daerah feasible terkecil. Bukti 𝒏 𝒋=𝟏 𝒂𝒋 𝒙𝒋

Andaikan

≤ 𝒃 merupakan versi tegas dari pertidaksamaan. 𝒏 𝒋=𝟏 𝒂𝒋 𝒙𝒋

 Untuk beberapa solusi 𝒙𝒋 ≥ 𝟎 didapat 𝒏 𝒋=𝟏 𝒂𝒋 𝒙𝒋

≤ 𝒃 maka memungkinkan


≤

≤



oleh karena itu jika

≤ 𝒃 ≤ 𝒃 sehingga titik 𝑥

berada pada area feasible terbesar. 𝒏 𝒋=𝟏 𝒂𝒋 𝒙𝒋

 Untuk beberapa solusi 𝒙𝒋 ≥ 𝟎 didapat 𝒏 𝒋=𝟏 𝒂𝒋 𝒙𝒋

≤ 𝒃 maka memungkinkan


≤

≤



oleh karena itu jika

≤ 𝒃 ≤ 𝒃 sehingga titik 𝑥

berada pada area feasible terkecil. ∎

Gambar 2.1 Daerah Feasible Terkecil dan Daerah Feasible Terbesar


Allahdadi dan Mishmat (2011) mengemukakan berdasarkan Teorema 1 maka didapat langkah-langkah penyelesaian Interval Linear Programming dengan kendala (≤) 1. memodelkan suatu kasus Interval linear programming Minimum

𝒏 𝒋=𝟏

Kendala

𝒏 𝒋=𝟏

𝒁=

𝒄𝒋 𝒄𝒋 𝒙𝒋

𝒂𝒊𝒋 𝒂𝒊𝒋 𝒙𝒋 ≤ 𝒃𝒊 𝒃𝒊

; 𝒙 ≥ 𝟎.

2. Menyelesaikan Best optimum dari (2.2). Best optimum merupakan suatu keputusan optimum terbaik yang dapat terjadi dinyatakan. Minimum

𝒁=

𝒏 ′ 𝒋=𝟏 𝒄𝒋 𝒙𝒋

′′ 𝒏 𝒋=𝟏 𝒂𝒊𝒋 𝒙𝒋

Kendala

≤ 𝒃𝒊 ; 𝒙 ≥ 𝟎.

3. Menyelesaikan Worst optimum dari (2.2). Worst optimum merupakan suatu keputusan optimum terburuk yang dapat terjadi dinyatakan. Minimum

𝒁=

𝒏 ′′ 𝒋=𝟏 𝒄𝒋 𝒙𝒋

𝒏 ′ 𝒋=𝟏 𝒂𝒊𝒋 𝒙𝒋

Kendala

≤ 𝒃𝒊 ; 𝒙 ≥ 𝟎.

4. Menarik Kesimpulan 𝑐𝑗 dan 𝑐𝑗 merupakan batas bawah dan batas atas koefisien fungsi tujuan. 𝑎𝑖𝑗 dan 𝑎𝑖𝑗 merupakan batas bawah dan batas atas konstanta teknologis. 𝑏𝑖 dan 𝑏𝑖 merupakan batas bawah dan batas atas dari konstanta pembatas. Dimana 𝒂′𝒋 , 𝒂′′𝒋 , 𝒄′𝒋 , 𝒄′′𝒋

𝑎𝑖𝑗′

𝑐𝑗′

𝑎𝑖𝑗 𝑗𝑖𝑘𝑎 𝑥𝑗 ≥ 0 =

𝑎𝑖𝑗 𝑗𝑖𝑘𝑎 𝑥𝑗 ≤ 0 𝑐𝑗 𝑗𝑖𝑘𝑎 𝑥𝑗 ≥ 0

=

𝑐𝑗 𝑗𝑖𝑘𝑎 𝑥𝑗 ≤ 0

𝑎𝑗′′

𝑐𝑗′′

=

=

𝑎𝑖𝑗 𝑗𝑖𝑘𝑎 𝑥𝑗 ≥ 0 𝑎𝑖𝑗 𝑗𝑖𝑘𝑎 𝑥𝑗 ≤ 0

𝑐𝑗 𝑗𝑖𝑘𝑎 𝑥𝑗 ≥ 0 𝑐𝑗 𝑗𝑖𝑘𝑎 𝑥𝑗 ≤ 0


2.4 Teori Himpunan Fuzzy Teori himpunan fuzzy yang ditemukan oleh Lotfi A. Zadeh pada tahun 1965 merupakan kerangka matematis yang digunakan untuk mempresentasikan ketidakpastian, ketidakjelasan, ketidaktepatan dan kekurangan informasi. Setiadji (2009) mengemukakan pada teori himpunan tegas (Crisp) keberadaan suatu elemen pada suatu himpunan (misal himpunan 𝐴) hanya memiliki dua kemungkinan keanggotaan yaitu anggota 𝐴 atau bukan anggota 𝐴. Zadeh mengkaitkan fungsi keanggotaan atau derajat keanggotaan ke dalam suatu himpunan tertentu yaitu himpunan fuzzy. Susilo (2006) Mengemukakan bahwa fungsi keanggotaan atau derajat keanggotaan adalah suatu nilai atau parametr yang menunjukan seberapa besar tingkat keanggotaan elemen (𝑥) dalam suatu himpunan A yang dinotasikan dengan 𝜇𝐴 𝑥 . Pada himpunan tegas hanya ada dua nilai yaitu 𝜇𝐴 𝑥 = 1 untuk 𝑥 menjadi anggota 𝐴 dan 𝜇𝐴 𝑥 = 0 untuk 𝑥 bukan anggaota 𝐴.

𝜇𝐴 𝑥 =

1,

𝑥∈𝐴

0,

𝑥∉𝐴

Definisi (Himpunan Fuzzy) Andaikan 𝑋 adalah himpunan semesta dimana elemenya dinotasikan sebagai 𝑥. Maka himpunan fuzzy 𝐴 dinotasikan 𝐴 dinyatakan sebagai himpunan pasangan terurut 𝐴 = {(𝑥, 𝜇𝐴 𝑥 )|𝑥 ∈ 𝑋} dimana 𝜇𝐴 𝑥 adalah fungsi keanggotaan dari himpunan kabur 𝐴 yang merupakan suatu pemetaan dari himpunan semesta 𝑋 ke selang tertutup [0,1] . 𝜇𝐴 ∶ 𝑋 → [0,1] Definisi (𝜶 − 𝒄𝒖𝒕𝒔) Bector dan Chandra (2005) Andaikan 𝐴 adalah suatu himpunan fuzzy di 𝑋 dan 𝛼 ∈ (0,1]. Maka 𝛼 − 𝑐𝑢𝑡 dari himpunan fuzzy 𝐴 adalah himpunan tegas 𝐴𝛼 dinotasikan 𝐴𝛼 = 𝑥 ∈ 𝑋 ∶ 𝜇𝐴 𝑥 ≥ 𝛼


2.5 Bilangan Fuzzy Klir dan Yuan (1995) mengemukakan bilangan fuzzy didefinisikan sebagai setiap himpunan fuzzy di ℝ dimana fungsi keanggotaan sifat 𝜇𝐴 (𝑥) berikut : 1. 𝐴 haruslah himpunan fuzzy normal dan convex 2. 𝐴𝛼 dalam selang tertutup untuk setiap 𝛼 ∈ (0,1] 3. Mempunyai pendukung yang terbatas Suatu bilangan kabur bersifat normal, jika fungsi keanggotaan bernilai sama dengan 1 untuk 𝑥 = 𝑎. Pendukung yang terbatas dan 𝛼-cuts untuk 𝛼 ≠ 0 harus dalam interval tertutup sebagai syarat untuk mendefinisikan operasi atitmatika pada bilangan fuzzy. Definisi (Bilangan Fuzzy) Andaikan 𝐴 merupakan himpunan fuzzy di ℝ. Maka 𝐴 adalah suatu bilangan fuzzy jika dan hanya jika terdapat pada suatu interval tertutup 𝑎, 𝑏 ≠ ∅ sehingga 1, 𝜇𝐴 𝑥 =

𝑥∈𝐴

𝑙 𝑥 ,

𝑥 ∈ −∞, 𝑎

𝑟 𝑥 ,

𝑥 ∈ (𝑏, ∞)

Dimana 𝑙: −∞, 𝑎 → [0,1] bergerak naik dan 𝑙 𝑥 = 0 untuk semua 𝑥 ∈ −∞, 𝑤1 , 𝑤1 < 𝑎 𝑟: 𝑏, ∞ → [0,1] bergerak turun dan 𝑟 𝑥 = 0 untuk semua 𝑥 ∈ 𝑤2 , ∞ , 𝑤2 < 𝑏

2.6 Operasi Aritmatika Pada Bilangan Fuzzy Bector dan Chandra (2005) mengemukakan aritmatika Fuzzy merupakan sifat dasar dari 𝛼 − 𝑐𝑢𝑡 dimana 𝐴 merupakan bilangan fuzzy dan 𝐴𝛼 berada pada suatu interval tertutup. 𝐴𝛼 = 𝑎𝛼𝐿 , 𝑎𝛼𝑅 , 𝛼 ∈ (0,1]


Definisi (Operasi dari dua bilangan fuzzy) Bector dan Chandra (2005) Andaikan 𝐴, 𝐵, 𝐴𝛼 , 𝐵𝛼 dimana 𝐴𝛼 = 𝑎𝛼𝐿 , 𝑎𝛼𝑅 , 𝐵𝛼 = 𝑏𝛼𝐿 , 𝑏𝛼𝑅 , 𝛼 ∈ (0,1] dan andaikan * dinotasikan sebagai operasi aritmatika + , − , × , ÷ pada bilangan fuzzy.Maka * operasi dari bilangan fuzzy dinotasikan. 𝐴∗𝐵

𝛼

= 𝐴𝛼 ∗ 𝐵𝛼 ,

𝛼 ∈ (0,1]

2.7 Bilangan Fuzzy Triangular Susilo (2006) Mengemukakan suatu fungsi keanggotaan himpunan kabur disebut fungsi keanggotaan segitiga jika mempunyai tiga parameter, yaitu 𝑎𝑙 , 𝑎, 𝑎𝑟 ∈ ℝ dengan 𝑎𝑙 < 𝑎 < 𝑎𝑟 dan dinyatakan dengan 𝐴 = (𝑎𝑙 , 𝑎, 𝑎𝑟 ) dengan aturan : 0, 𝜇𝐴 𝑥 =

𝑥 < 𝑎𝑙 , 𝑥 > 𝑎𝑟

𝑥 − 𝑎𝑙 , 𝑎 − 𝑎𝑙 𝑎𝑟 − 𝑥 , 𝑎𝑟 − 𝑎

𝑎𝑙 < 𝑥 ≤ 𝑎 𝑎 < 𝑥 ≤ 𝑎𝑟

𝛼 − 𝑐𝑢𝑡 dari bilangan fuzzy triangular 𝐴 = [𝑎𝑙 , 𝑎, 𝑎𝑟 ] merupakan interval tertutup pada 𝑎𝛼𝐿 , 𝑎𝛼𝑅 𝑎𝛼𝐿 , 𝑎𝛼𝑅 =

𝑎 − 𝑎𝑙 𝛼 + 𝑎𝑙 , 𝑎𝑟 − 𝑎𝑟 − 𝑎 𝛼 ,

𝛼 ∈ (0,1]

Gambar 2.2 Fuzzy Triangular


BAB 2 LANDASAN TEORI

Recommend Documents