BAB 2 LANDASAN TEORI

BAB 2 LANDASAN TEORI

2.1 Program Linier Program linier merupakan model umum yang dapat digunakan untuk menyelesaikan persoalan pengalokasian sumber-sumber yang terbatas di antara beberapa aktivitas yang bersaing secara optimal, dengan cara yang terbaik yang mungkin

dilakukan.

Sebagai

contoh

sederhana

sebuah

bank

hendak

mengalokasikan dananya untuk mencapai kemungkinan hasil tertinggi.Dalam hal ini bank tersebut harus beroperasi dalam peraturan likuiditas yang dibuat oleh pemerintah dan harus mampu menjaga fleksibilitas yang memadai untuk memenuhi permintaan pinjaman dari para nasabah. Dalam penerapannya program linier menggunakan model matematis dalam pemecahan berbagai persoalan.Kata sifat linier digunakan untuk menggambarkan hubungan antara dua atau lebih variabel, hubungan yang berlangsung haruslah berupa fungsi yang linier.Sedangkan kata program menyatakan penggunaan teknik matematika tertentu untuk mendapatkan kemungkinan pemecahan terbaik dari persolan yang melibatkan sumber yang serba terbatas.memiliki hubungan fungsional atau hubungan keterkaitan.

2.1.1 Syarat Utama Program Linier

Agar dapat menyusun dan merumuskan suatu persoalan atau permasalahanyang dihadapi ke dalam model program linier, maka ada lima syarat yang harus dipenuhi:

Universitas Sumatera Utara

1. Tujuan Apa yang menjadi tujuan permasalahan yang dihadapi yang ingin dipecahkan dan dicari jalan keluarnya. Tujuan ini harus jelas dan tegas yang disebut fungsitujuan. 2. Alternatif perbandingan Harus ada sesuatu atau berbagai alternatif yang ingin diperbandingkan, misalnya antara kombinasi waktu tercepat dan biaya tertinggi dengan waktuterlambat dan biaya terendah. 3. Sumber daya Sumber daya yang dianalisis harus berada dalam keadaan yang terbatas. 4. Perumusan kuantitatif Fungsi tujuan dan kendala harus dapat dirumuskan secara kuantitatif dalamapa yang disebut model matematika. 5. Keterkaitan peubah Peubah-peubah yang membentuk fungsi tujuan dan kendala tersebut harusmemiliki hubungan fungsional atau hubungan keterkaitan.

2.1.2 Asumsi dalam Model Program Linier Dalam menggunakan model program linear, diperlukan beberapa asumsi sebagai berikut: 1. Asumsi kesebandingan (proportionality) a. Konstribusi setiap variabel keputusan terhadap fungsi tujuan adalah sebanding dengan nilai variabel keputusan. b. Konstribusi suatu variabel keputusan terhadap ruas kiri dari setiap pembatas linier juga sebanding dengan nilai keputusan itu. 2. Asumsi penambahan (additivity) a. Konstribusi setiap variabel keputusan terhadap fungsi keputusan bersifat bergantung pada nilai dari variabel keputusan yang lain. b. Konstribusi suatu variabel keputusan pada nilai dari variabel keputusan ruas kiri dari setiap pembatas linier bersifat tidak bergantung pada nilai dari variabel keputusan yang lain.


3. Asumsi pembagian(divisiblity) Dalam persoalan program linier, variabel keputusan boleh diasumsikan berupa pecahan. 4. Asumsi kepastian (certainty) Setiap parameter, yaitu koefisien fungsi tujuan, ruas kanan, dan koefisien fungsi kendala diasumsikan dapat diketahui secara pasti.

2.1.3 Karakteristik Program Linier Dalam membangun model dari formulasi suatu persoalan akan digunakan karakteristik-karakteristik yang biasa digunakan dalam persoalan program linier, yaitu: 1. Peubah keputusan Peubah keputusan adalah peubah yang menguraikan secara lengkap keputusan-keputusan yang akan dibuat. 2. Fungsi tujuan (objective function) Fungsi tujuan merupakan fungsi dari peubah keputusan yang akan dimaksimumkan (untuk pendapatan) atau diminimumkan (untuk ongkos). Untuk menyatakan fungsi tujuan biasanya digunakan peubah z sehingga fungsi tujuan dapat dinyatakan: 𝑧𝑧 = 𝑓𝑓(𝑥𝑥)

3. Pembatas Linier (linier constraints)

Pembatas linear merupakan kendala yang dihadapi sehingga kita tidak dapat menentukan harga-harga variabel keputusan secara sembarang. Koefisien dari variabel keputusan pada pembatas linear dinamakan koefisien fungsi kendala, sedangkan bilangan yang ada di sisi (ruas) kanan setiap pembatas linear dinamakan ruas kanan pembatas. 4. Pembatas tanda / kondisi pengetat Pembatas tanda adalah pembatas yang menjelaskan apakah variabel keputusannya diasumsikan hanya berharga nonnegatif atau variabel keputusannya tidak terbatas dalam tanda (boleh positif - boleh negatif).


Secara umum model program linier dapat dirumuskan sebagai berikut: 𝑛𝑛

Maksimum atau minimumkan

𝑧𝑧 = � 𝑐𝑐𝑗𝑗 𝑥𝑥𝑗𝑗

Kendala

� 𝑎𝑎𝑖𝑖𝑖𝑖 𝑏𝑏𝑗𝑗 ≤ 𝑏𝑏𝑗𝑗 (𝑖𝑖 = 1, 2, … , 𝑚𝑚)

Keterangan: 𝑥𝑥𝑗𝑗

𝑛𝑛

𝑗𝑗 =1

𝑗𝑗 =1

𝑥𝑥𝑗𝑗 ≥ 0

(𝑗𝑗 = 1, 2, … , 𝑛𝑛)

= variabel keputusan

𝑐𝑐𝑗𝑗

= koefisien fungsi tujuan

𝑏𝑏𝑗𝑗

= jumlah masing-masing sumber daya yang ada (ruas kanan pembatas)

𝑎𝑎𝑖𝑖𝑖𝑖 = koefisien fungsi kendala

2.2 Metode Simpleks Cara yang paling sederhana unrtuk menyelesaikan permasalahan program linier adalah dengan pendekatan grafikal. Namun cara tersebut hanya bisa diterapkan untuk program linier dengan dua variabel keputusan. Pada kenyataannya sebagian besar permasalahan program linier mempunyai lebih dari dua variabel keputusan.Hal ini tentu sulit untuk menerapkan pendekatan grafikal untuk memperoleh penyelesaian dari permasalahan tersebut. Oleh karen itu, pada tahun 1947 George Dantzig mengajukan suatu metode yang tepat untuk menyelesaiakn permasalahan program linier yang disebut metode simpleks. Metode simpleks merupakan prosedur aljabar yang bersifat iteratif yang bergerak selangkah demi selangkah, dimulai dari titik ekstrim pada daerah feasible (ruang sousi) menuju titik ekstrim yang optimum. Berikut langkah-langkah dalam menyelesaikan permasalahan program linier dengan metode simpleks: 1. Konversikan formulasi persoalan ke dalam bentuk standar.


Agar persamaan garis batasan memenuhi persyaratan penyelesaian daerah kelayakan (feasible) maka semua pertidaksamaan diubah menjadi persamaan dengan cara menambahkan variabel slack, surplus dan variabel buatan (artifisial variabel) pada tiap batasan (constraint) serta memberi harga nol pada setiap koefisien tujuannya. Batasan dapat dimodifikasi sebagai berikut: a. Untuk batasan bernotasi (≤) diubah ke dalam bentuk persamaan dengan menambahkan variabel slack.

b. Untuk

batsan

bernotasi

(≥)

atau

(=)

deselesaikan

dengan

menambahkan variabel surplus dan variabel buatan. Dengan penambahan variabel buatan ini akan merusak sistem batasan, hal ini dapat diatasi dengan membuat suatu bilangan penalty M (M bilangan positif yang sangan besar) sebagai harga dari variabel buatan tersebut dalam fungsi tujuan. Untuk kasus maksimasi maka dibuat –M sebagai harga dari variabel buatan dan untuk kasus minimasi dibuat +M sebagai harga dari variabel buatan. Cara pendekatan ini dikenal dengan metode M besar (Big M method).

2. Susun persamaan-persamaan ke dalam tabel simpleks Tabel 2.1. Bentuk Tabel Simpleks 𝐶𝐶𝑗𝑗

𝐶𝐶1

...

Variabel

Harga

Basis

Basis

𝑋𝑋𝑩𝑩1

𝐶𝐶𝐵𝐵1

𝑎𝑎11

...

𝑋𝑋𝑩𝑩𝑚𝑚

𝐶𝐶𝐵𝐵𝐵𝐵

𝑎𝑎𝑚𝑚1

...

⋮

𝑍𝑍𝑗𝑗 − 𝐶𝐶𝑗𝑗

⋮

𝑋𝑋1 ⋮


...

...

𝐶𝐶𝑛𝑛

Basis

𝑎𝑎1𝑛𝑛

𝑏𝑏1

𝑎𝑎𝑚𝑚𝑚𝑚

𝑏𝑏𝑚𝑚

𝑋𝑋𝑛𝑛 ⋮


⋮

𝐶𝐶𝐵𝐵 𝑏𝑏


3. Pilih kolom kunci, yaitu kolom yang memiliki nilai �𝑍𝑍𝑗𝑗 − 𝐶𝐶𝑗𝑗 � yang paling positif untuk kasus maksimasi atau yang memiliki nilai �𝑍𝑍𝑗𝑗 − 𝐶𝐶𝑗𝑗 � yang

paling negatif untuk kasus minimasi.

4. Pilih baris kunci yang memiliki nilai indeks terkecil. Nilai indeks adalah perbandingan nilai kanan dengan kolom kunci, 5. Tentukan nilai elemen cell, yaitu nilai perpotongan antara kolom kunci dan baris kunci. 6. Lakukan iterasi dengan menentukan baris kunci baru, baris Z baru, dan baris variabel-variabel slack baru. a. Baris kunci baru ditentukan dengan membagi baris kunci lama dengan elemen cell. b. Baris Z baru dan baris-baris lainnya ditentukan dengan cara: Baris lama – (nilai kolom kunci baris yang sesuai × baris kunci baru) c. Letakkan nilai-nilai baris yang baru diperoleh ke dalam tabel. 7. Lakukan uji optimalisasi. Jika semua koefisien pada baris �𝑍𝑍𝑗𝑗 − 𝐶𝐶𝑗𝑗 � sudah

tidak ada lagi yang bernilai positif (untuk kasus maksimasi) atau sudah tidak ada lagi yang bernilai negatif (untuk kasus minimasi) berarti sudah optiamal. Jika kriteria belum terpenuhi, diulangi dari langkah 3.

2.3 HimpunanFuzzy Istilah fuzzylahir dari gagasan seorang guru besar pada University of California, Berkeley, Amerika Serikat, Prof. Lotfi Asker Zadeh.Sejak tahun 1960 Zadeh telah merasa bahwa sistem analisis matematika tradisional yang dikenal sampai saat itu bersifat terlalu eksak sehingga tidak dapat berfungsi dalam banyak masalah dunia nyata yang seringkali amat kompleks.Pada akhirnya di tahun 1965 Zadeh mempublikasikan karangan ilmiahnya berjudul “Fuzzy Set”. Terobosan baru yang deperkenalkan oleh Zadeh ini telah memperluas konsep himpunan klasik menjadi himpunan fuzzy yang dapat mempresentasikan nilai-nilai ketidakpastian yang ditemui dalam kehidupan nyata.


Menurut Zadeh, himpunan fuzzy (fuzzy set) adalah sebuah kelas dari obyek denganserangkaian kesatuan dari nilai keanggotaan. Sebuah set dikarakterisasikan oleh sebuah fungsi keanggotaan yang memberikan tiap obyek sebuah nilai keanggotaan yang rentang nilainya antara 0 dan 1.

2.4 Fungsi Keanggotaan Fuzzy Sebuah himpunan fuzzy 𝐴𝐴̃ pada X ditandai oleh fungsi keanggotaan 𝑓𝑓𝐴𝐴� (𝑥𝑥) yang berhubungan dengan setiap titik di X, sebuah bilangan riilpada interval [0,1]

dengan nilai dari 𝑓𝑓𝐴𝐴� (𝑥𝑥) pada x mewakili derajat keanggotaan x pada 𝐴𝐴̃. Maka,

semakin dekat nilai 𝑓𝑓𝐴𝐴� (𝑥𝑥)ke semesta pembicaraan, semakin tinggi derajat

keanggotaan x pada 𝐴𝐴̃. Fungsi keanggotaan (membership function) adalah suatu

kurva yang menunjukkan pemetaan titik – titik input data ke dalam nilai keanggotaan yang mempunyai interval antara 0 sampai 1.

Definisi 2.1: X adalah sebuah himpunan tak kosong. Sebuah himpunan fuzzy 𝐴𝐴̃pada X ditandai oleh fungsi keanggotaannya: 𝐴𝐴̃: 𝑋𝑋 → [0,1]

Dan 𝐴𝐴̃(𝑥𝑥)diinterpretasikan sebagai derajat keanggotaan dari

elemen x pada himpunan fuzzy𝐴𝐴̃.untuk setiap 𝑥𝑥 ∈ 𝑋𝑋.

Nilai 0 digunakan untuk mewakili bukan anggota, nilai 1 digunakan untukmewakili keanggotaan penuh, dan nilai – nilai di antaranya digunakan untuk mewakili derajat keanggotaan menengah. Pemetaan 𝐴𝐴̃juga disebut sebagai fungsi keanggotaan dari himpunan fuzzy𝐴𝐴̃.

Definisi 2.2: Sebuah himpunan fuzzy adalah kosong jika dan hanya jika fungsi keanggotaannya sama dengan 0 pada 𝐴𝐴̃.


2.5 Bilangan Fuzzy Konsep bilangan fuzzy muncul dalam kehidupan sehari-hari maupun dalam aplikasi teori fuzzy dalam bentuk besaran yang dinyatakan dengan bilangan yang tidak tepat, misalnya “kurang lebih 10 orang”, kira-kira 3 jam”, “sekitar 5 km”, dan lain sebagainya. Secara intuitif dapat diterima bahwa ungkapan “kurang lebih 10” dapat dinyatakan dengan suatu himpunan kaburpada semesta bilangan riil, di mana bilangan 10 mempunyai derajat keanggotaan kurang dari 1, dan semakin jauh bilangan itu dari derajat keanggotaanya semakin mendekati 0. Definisi 2.3: Sebuah bilangan fuzzy 𝐴𝐴̃ adalah himpunan fuzzy dalam semesta bilangan riil yang memenuhi kondisi normal dan konveks.

Definisi 2.4: Sebuah bilangan fuzzy 𝐴𝐴̃ = (𝑎𝑎, 𝑏𝑏, 𝑐𝑐, 𝑑𝑑)disebut bilanga trapezoidal fuzzy jika fungsi keanggotaanya diberikan oleh: 0 ; lainnya ⎧𝑥𝑥 − 𝑎𝑎 ⎪ ; 𝑎𝑎 ≤ 𝑥𝑥 ≤ 𝑏𝑏 𝑏𝑏 − 𝑎𝑎 𝜇𝜇𝐴𝐴� (𝑥𝑥) = ⎨ 1 ; 𝑏𝑏 ≤ 𝑥𝑥 ≤ 𝑐𝑐 ⎪ 𝑑𝑑 − 𝑥𝑥 ⎩ 𝑑𝑑 − 𝑐𝑐 ; 𝑐𝑐 ≤ 𝑥𝑥 ≤ 𝑑𝑑

Fungsi keanggotaan trapezoidalfuzzy 𝐴𝐴̃ = (𝑎𝑎, 𝑏𝑏, 𝑐𝑐, 𝑑𝑑)digambarkan sebagai berikut: 𝜇𝜇(𝑥𝑥)

1

0

𝑥𝑥

a b c d Gambar 2.1Grafikfungsikeanggotaantrapezoidal fuzzy (Sumber: Sri Kusumadewi, 2002)


Definisi 2.5: Misalkan 𝐴𝐴̃ = (𝑎𝑎, 𝑏𝑏, 𝑐𝑐, 𝑑𝑑) dan 𝐵𝐵� = (𝑒𝑒, 𝑓𝑓, 𝑔𝑔, ℎ) adalah dua bilangan trapezoidal fuzzy, maka (i)

𝐴𝐴̃ ⊕ 𝐵𝐵� = (𝑎𝑎, 𝑏𝑏, 𝑐𝑐, 𝑑𝑑) ⊕ (𝑒𝑒, 𝑓𝑓, 𝑔𝑔, ℎ)

= (𝑎𝑎 + 𝑒𝑒, 𝑏𝑏 + 𝑓𝑓, 𝑐𝑐𝑐𝑐, 𝑑𝑑 + ℎ)

(ii) 𝐴𝐴̃ ⊝ 𝐵𝐵� = (𝑎𝑎, 𝑏𝑏, 𝑐𝑐, 𝑑𝑑) ⊝ (𝑒𝑒, 𝑓𝑓, 𝑔𝑔, ℎ)

= (𝑎𝑎 + 𝑒𝑒, 𝑏𝑏 + 𝑓𝑓, 𝑐𝑐𝑐𝑐, 𝑑𝑑 + ℎ)

(iii) 𝐴𝐴̃ ⊗ 𝐵𝐵� ≈ (𝛼𝛼, 𝛽𝛽, 𝛾𝛾, 𝛿𝛿)

di mana 𝛼𝛼 = minimum (𝑎𝑎𝑎𝑎, 𝑎𝑎ℎ, 𝑑𝑑𝑑𝑑, 𝑑𝑑ℎ)

𝛽𝛽 = minimum (𝑏𝑏𝑏𝑏, 𝑏𝑏𝑏𝑏, 𝑐𝑐𝑐𝑐, 𝑐𝑐𝑐𝑐)

𝛾𝛾 = maksimum (𝑏𝑏𝑏𝑏, 𝑏𝑏𝑏𝑏, 𝑐𝑐𝑐𝑐, 𝑐𝑐𝑐𝑐)

𝛿𝛿 = maksimum (𝑎𝑎𝑎𝑎, 𝑎𝑎ℎ, 𝑑𝑑𝑑𝑑, 𝑑𝑑ℎ)

(iv) 𝑘𝑘(𝑎𝑎, 𝑏𝑏, 𝑐𝑐, 𝑑𝑑) = (𝑘𝑘𝑘𝑘, 𝑘𝑘𝑘𝑘, 𝑘𝑘𝑘𝑘, 𝑘𝑘𝑘𝑘) untuk 𝑘𝑘 ≥ 0 (v) 𝑘𝑘(𝑎𝑎, 𝑏𝑏, 𝑐𝑐, 𝑑𝑑) = (𝑘𝑘𝑘𝑘, 𝑘𝑘𝑘𝑘, 𝑘𝑘𝑘𝑘, 𝑘𝑘𝑘𝑘) untuk 𝑘𝑘 ≤ 0

Definisi 2.6: Sebuah fungsi rangking ℜ: 𝐹𝐹(𝑅𝑅) → 𝑅𝑅, di mana 𝐹𝐹(𝑅𝑅) adalah

himpunan dari semua bilangan fuzzy yang terdefinisi dalam himpunan bilngan rill, adalah pemetaan setiap bilangan fuzzy ke dalam himpunan bilangan rill. Untuk bilngan trapezoidal fuzzy𝐴𝐴̃ = (𝑎𝑎, 𝑏𝑏, 𝑐𝑐, 𝑑𝑑), maka fungsi rangkingnya adalah: 1 ℜ�𝐴𝐴̃� = (𝑎𝑎 + 𝑏𝑏 + 𝑐𝑐 + 𝑑𝑑) 4

2.6 Program Linier Fuzzy Program Linier Fuzzy adalah sebuah aplikasi dari teori himpunan fuzzy pada masalah proses pengambilan keputusan linear, di mana sebagian besar dari masalah tersebut terkait dengan permasalahan program linear dengan variabel fuzzy. Secara

umum

model

program

linier

fuzzy

dinyatakan

oleh:

𝑛𝑛

Maksimumkan atau minimumkan 𝑧𝑧 = � 𝑐𝑐𝑗𝑗 𝑥𝑥�𝑗𝑗 𝑗𝑗 =1


𝑛𝑛

� 𝑎𝑎𝑖𝑖𝑖𝑖 𝑥𝑥�𝑗𝑗 ≤ℜ 𝑏𝑏�𝑖𝑖

Kendala

𝑗𝑗 =1

𝑥𝑥�𝑗𝑗 ≥ℜ 0�

(𝑖𝑖 = 1, 2, … , 𝑚𝑚)

(𝑗𝑗 = 1, 2, … , 𝑛𝑛)

di mana koefisien fungsi tujuan (𝑐𝑐𝑗𝑗 ) dan koefisien fungsi kendala (𝑎𝑎𝑖𝑖𝑖𝑖 ) adalah koefisien crisp dan 𝑏𝑏�𝑖𝑖 adalah konstanta fuzzyserta 𝑥𝑥�𝑗𝑗 adalah variabel keputusan

fuzzy.

2.7 Program Linier Fuzzy Penuh Program Linier Fuzzy adalah sebuah aplikasi dari teori himpunan fuzzy pada masalah proses pengambilan keputusan linear, di mana semua parameter yaitu koefisien, variabel maupun konstanta dalam model berupa bilangan fuzzy. Bentuk umum program linier fuzzy penuh dengan 𝑚𝑚 buah kendala

pertidaksamaan fuzzy dan 𝑛𝑛 buah variabel fuzzy: 𝑛𝑛

Maksimumkan atau Minimumkan 𝑧𝑧 = � 𝑐𝑐̃𝑗𝑗 𝑥𝑥�𝑗𝑗

Kendala

𝑛𝑛

𝑗𝑗 =1

� 𝑎𝑎�𝑖𝑖𝑖𝑖 𝑥𝑥�𝑗𝑗 ≤ℜ 𝑏𝑏�𝑖𝑖 𝑗𝑗 =1

𝑥𝑥�𝑗𝑗 ≥ℜ 0�

(𝑖𝑖 = 1, 2, … , 𝑚𝑚)

(𝑗𝑗 = 1, 2, … , 𝑛𝑛)

dengan𝑎𝑎�𝑖𝑖𝑖𝑖 , 𝑐𝑐̃𝑗𝑗 , 𝑥𝑥�𝑗𝑗 , 𝑏𝑏�𝑗𝑗 adalah bagian dari himpunan semua bilangan fuzzy yang terdefinisi dalam himpunan bilangan rill.


BAB 2 LANDASAN TEORI

Recommend Documents