Pemecahan Linear Programming Dua Variabel Menggunakan Logika Fuzzy (Asep Saepuloh – Deni Ahmad)
PEMECAHAN LINEAR PROGRAMMING DUA VARIABEL MENGGUNAKAN LOGIKA FUZZY Asep Saepuloh 1, Deni Ahmad Jakaria 2 1)
Prodi Teknik Informatika STMIK DCI 2) Prodi Teknik Informatika STMIK DCI Jl. Komalasari II No. 28 Kota Tasikmalaya Email:
[email protected]
ABSTRACT Fuzzy logic is a methodology of solving the control system to be implemented in a system, ranging from a simple system, small, large, networks, multi-channel PC or workstation. Besides that, it can be implemented in hardware, software or a combination of both. Fuzzy logic provides a simple way to get definitive conclusions based on ketidaksamaran, ambiguity, imprecision, vagueness, or missing information. Fuzzy logic approach is to control the problem impersonation of someone who will make a decision. Linear programming is a way to establish a fast arrangement of a problem with a simple solution. Set of linear programming gives two reasons: (i) a lot of practical problems which can be formed as a linear programming problem, and (ii) no efficient way (eg simplex method) for solving linear programming problems. Linear programming problems is to find the values of a variable that is not known as a linear objective function that dimaksimasikan under the constraints described by linear equations. On fuzzy linear programming, will look a Z value which is the objective function to be optimized so that is subject to the restrictions are modeled using fuzzy sets. Linear programming is solved by fuzzy logic gives more precise results dibandingakan if without using fuzzy logic. This system provides an opportunity or a chance for the development of the system towards better Keyword : Logic, Fuzzy, Linear, Programming I.
PENDAHULUAN Logika Fuzzy adalah suatu metode yang mengadopsi penilaian yang dilakukan manusia terhadap suatu kebenaran. Pada kebanyakan sistem digital, kebenaran dinilai BENAR atau SALAH (0 dan 1). Padahal dalam penilaian manusia terdapat suatu kebimbangan antara benar dan salah. Sistem-sistem yang menggunakan logika fuzzy ini memperhitugkan kebimbangan nilai benar dan nilai salah tersebut. Aplikasi logika fuzzy sudah mulai dirasakan pada beberapa bidang. Salah
satu aplikasi terpentingnya adalah untuk membantu manusia dalam melakukan pengambilan keputusan. Aplikasi logika fuzzy untuk pendukung keputusan ini semakin diperlukan tatkala semakin banyak kondisi yang menuntut adanya keputusan yang tidak hanya bisa dijawab dengan “Ya” atau “Tidak”. Salah satu penerapan dari logika fuzzy ini adalah pada permasalahan Linear Programming. Linear Programming merupakan suatu model umum yang dapat digunakan dalam pengambilan keputusan dalam pemecahan masalah pengalokasian 1
Pemecahan Linear Programming Dua Variabel Menggunakan Logika Fuzzy (Asep Saepuloh – Deni Ahmad)
sumber-sumber yang terbatas secara optimal. Masalah tersebut timbul apabila seseorang diharuskan untuk memilih atau menentukan tingkat setiap kegiatan yang akan dilakukannya, dimana masing-masing kegiatan membutuhkan sumber yang sama sedangkan jumlahnya terbatas. Secara sederhana dapat digambarkan sebuah contoh keadaan bagian produksi suatu perusahaan yang dihadapkan pada masalah penentuan tingkat produksi masing-masing jenis produk dengan memperhatikan batasan faktor-faktor produksi: mesin, tenaga kerja, bahan mentah, dan sebagainya untuk memperoleh tingkat keuntungan masksimal atau biaya yang minimal. Pada linear programming ini logika fuzzy digunakan untuk mendukung pengambilan suatu keputusan dalam suatu permasalahan pengalokasian sumber dayasumber daya yang terbatas secara lebih tepat dan akurat, sehingga didapatkan hasil yang maksimal dalam suatu kegiatan produksi. Untuk memecahkan masalah linear programming digunakan dua metode, yaitu: Metode Grafik dan Metode Simplek. Pada metode grafik, hanya dapat digunakan dalam pemecahan masalah linear programming yang mengandung 2
(dua) kegiatan (atau variabel-variabel keputusan) saja. Sedangkan pada metode simplek, sudah melibatkan dua atau lebih kegiatan (lebih dari dua variabel). II. LANDASAN TEORI A. Model Linear Programming Model matematis perumusan masalah umum pengalokasian sumber daya untuk berbagai kegiatan, disebut sebagai model linear programming (LP). Model LP ini merupakan bentuk dan susunan dalam menyajikan masalah-masalah yang akan dipecahkan dengan teknik LP. Dalam model LP dikenal dua macam fungsi, yaitu fungsi tujuan (objective function) dan fungsi-fungsi batasan (constraint functions). Fungsi tujuan adalah fungsi yang menggambarkan tujuan/ sasaran di dalam permasalahan LP yang berkaitan dengan pengaturan secara optimal sumber daya-sumber daya, untuk memperoleh keuntungan maksimal atau biaya minimal. Pada umumnya nilai yang akan dioptimalkan dinyatakan dengan Z . Sedang fungsi batasan merupakan bentuk penyajian secara matematis batasanbatasan kapasitas yang tersedia yang akan dialokasikan secara optimal ke berbagai kegiatan.
2
Pemecahan Linear Programming Dua Variabel Menggunakan Logika Fuzzy (Asep Saepuloh – Deni Ahmad Jakaria)
Adapun model linear programming dapat dilihat pada tabel berikut ini: Tabel 2.1. Model linear programming Kegiatan Pemakaian sumber per unit kegiatan (keluaran) Sumber
.
1
2
3
…………….
1 2 3
a11 a 21 a31
a12 a 22 a32
m
..
..
a13 a 23 a33
……………. ……………. ……………. .. …………….
..
a m1
am2
a m3
C1 x1
C2 x2
C3 x3
Z pertam
bahan tiap unit Tingkat kegiatan
n
Kapasitas Sumber
a1n a2n a3n
b1 b2 b3 ..
..
bm
a mn
……………. …………….
Cn xn
B. Metode Simplek Linear Programming Metode simplek merupakan suatu cara yang digunakan untuk menentukan kombinasi optimal dari dua, tiga atau leih variabel. Langkah – langkah metode simplek: 1. Mengubah fungsi tujuan dan batasan-batasan menjadi bentuk kanonik, sebagai berikut: Fungsi tujuan diubah menjadi fungsi implisit, yang artinya semua C j xij digeser ke kiri. Kemudian tanda (ketidaksamaan) pada batasan-batasan diubah menjadi kesamaan. Tambahkan Slack Variabel ( S i ) 2. Menyusun persamaan-persamaan di dalam tabel simplek Tabel 2.2. Tabel simplek Variabel xn S n NK x1 x2 S1 S2 …… …… Z Dasar
Z
1
C1
C2
……
S1
0
a11
a12
……
S2
0 . .
a21
a22
. .
. .
. .
Cn
0
0
……
0
0
a1n
1
0
……
0
b1
……
a2 n . .
1 . .
…… . .
0 . .
b2
……
0 . .
Sn
am1 am 2 …… amn 0 3. Mencari Solusi Basis Visibel (BVS) dan memilih kolom kunci. 3
. .
bm 0 0 0 1 Jika seluruh Variabel NonBasic mempunyai koefisien non negatif
Pemecahan Linear Programming Dua Variabel Menggunakan Logika Fuzzy (Asep Saepuloh – Deni Ahmad Jakaria)
semua model linear programming, sehingga menimbulkan kebutuhan untuk merancang sebuah prosedur perhitungan otomatis untuk memulai iterasi simplek. Hal ini dilakukan dengan menambahkan variabel buatan (artificial variable) atau variabel tambahan dimana diperlukan untuk memainkan peran variabel slack. Tetapi, karena variabel buatan seperti ini tidak memiliki makna fisik dalam model semula (sehingga diberi nama “buatan”), ketentuan harus dibuat untuk membuatnya menjadi nol di iterasi optimum. Prosedur perhitungan yang dimaksud adalah Teknik Dua Tahap. Tahap 1. Tambahkan variabel buatan sebagaimana diperlukan untuk memperoleh pemecahan awal. Bentuklah fungsi tujuan baru yang mengusahakan minimisasi jumlah variabel buatan dengan batasan masalah semula yang dimodifikasi oleh variabel buatan tersebut. Jika nilai minimum dari fungsi tujuan yang baru itu adalah nol (yang berarti bahwa semua variabel buatan adalah nol), masalah tersebut meiliki ruang pemecahan yang layak. Lanjutkan ke Tahap 2. jika tidak, jika nilai minimum itu positif, masalah itu tidak memiliki pemecahan yang layak. Hentikan. Tahap 2. Gunakan pemecahan dasar optimum dari Tahap 1 sebagai pemecahan awal untuk masalah semula
(positif atau nol) pada baris fungsi tujuan ( Z ), maka BVS sudah optimal. Jika tidak, pilih salah satu variabel yang mempunyai koefisien paling negatif sebagai kolom kunci. Variabel tersebut disebut sebagai variabel masuk. 4. Hitung rasio Menghitung rasio / perbandingan dari ( NilaiKanan / KoefisienVariabelMasuk )
Pada setiap pembatas dimana koefisien pada variabel masuk bernilai positif. Variabel Dasar pada baris pembatas dengan rasio positif terkecil akan berubah status menjadi Variabel NonBasic atau variabel keluar, yaitu variabel yang meninggalkan basis. 5. Mengubah nilai-nilai baris kunci Nilai baris kunci diubah dengan cara membaginya dengan angka kunci. Gantilah variabel dasar pada baris itu dengan variabel yang terdapat pada bagian atas kolom kunci 6. Mengubah nilai-nilai selain pada baris kunci Nilai baris yang lain selain pda baris kunci dapat diubah dengan rumus sebagai berikut: Baris baru = baris lama – (koefisien pada kolom kunci) * nilai baru baris kunci. 7. Melanjutkan perbaikan-perbaikan Ulangi langkah 3 sampai dengan 6 untuk memperbaiki tabel-tabel yang telah diubah. Perubahan baru berhenti setelah pada baris pertama (fugsi tujuan) tidak ada yang bernilai negatif.
D. Pengantar Logika Fuzzy Logika fuzzy adalah suatu cara yang tepat untuk memetakkan suatu ruang input ke dalam suatu ruang output. Sebagai contoh: 1. Manajer pergudangan mengatakan kepada manajer produksi seberapa banyak persediaan barang pada akhir minggu ini, kemudian manajer produksi akan menetapkan jumlah barang yang harus diproduksi esok
C. Teknik Dua Tahap / Teknik Dua Fase dalam Metode Simplek Dalam semua batasan pada linear programming adalah berjenis . Sifat ini bersamaan dengan fakta bahwa sisi kanan dari semua batasan adalah non negatif, memberikan kita pemecahan dasar awal yang layak yang terdiri dari variabel slack. Kondisi seperti ini titidak dipenuhi oleh 4
Pemecahan Linear Programming Dua Variabel Menggunakan Logika Fuzzy (Asep Saepuloh – Deni Ahmad Jakaria)
hari. Penumpang taksi berkata pada sopir taksi seberapa cepat laju kendaraan yang diinginkan, sopir taksi akan mengatur pijakan gas taksinya. Ruang Input (semua total persediaan barang yang mungkin)
Persediaan barang akhir minggu
Salah satu contoh pemetaan suatu input-output dalam bentuk grafis seperti terlihat pada gambar 2.1.
KOTA K HITA M
Ruang Output (semua jumlah produksi barang yang mungkin)
Produksi barang esok hari
Gambar 2.1 Contoh Pemetaan Input-Output
dengan a adalah 1. Namun, jika a A , maka nilai yang berhubungan dengan a A x P(x) adalah 0. Notasi
Antara input dan output terdapat satu kotak hitam yang harus memetakan input ke output yang sesuai. Beberapa alasan mengapa logika fuzzy digunakan: 1. Konsep logika fuzzy mudah dimengerti. Konsep matematis yang mendasari penalaran fuzzy sangat sederhana dan mudah dimengerti. 2. Logika fuzzy sangat fleksibel. 3. Logika fuzzy memiliki toleransi terhadap data-data yang tidak tepat. 4. Logika fuzzy mampu memodelkan fungsi-fungsi nonlinear yang sangat kompleks. 5. Logika fuzzy dapat membangun dan mengaplikasikan pengalamanpengalaman para pakar secara langsung tanpa harus melalui proses pelatihan. 6. Logika fuzzy dapat bekerja sama dengan teknik-teknik kendali secara konvensional. 7. Logika fuzzy didasarkan pada bahasa alami.
menunjukkan bahwa A berisi item x dengan P (x ) benar. Jika X A merupakan fungsi karakteristik A dan properti P , maka dapat dikatakan bahwa P (x ) benar, jika dan hanya jika X A( X ) 1 . Himpunan fuzzy didasarkan pada gagasan untuk memperluas jangkauan fuzzy karakterisktik sedemikian hingga fungsi tersebut akan mencakup bilangan real pada interval [0,1]. Nilai keanggotaannya menunjukkan bahwa suatu item dalam semesta pembicaraan tidak hanya berada pada 0 atau 1, namun juga nilai yang terletak diantaranya. 2. Fungsi Keanggotaan Fungsi keanggotaan (membership function) adalah suatu kurva yang menunjukkan pemetaan titik-titik input data ke dalam nilai keanggotaannya (sering juga disebut dengan derajta keanggotaan) yang memiliki interval antara 0 dan 1. Perhatikan gambar 2.2. Misalkan kita akan membuat himpunan tinggi badan orang. Kata TINGGI menunjukkan derajat seberapa besar orang dikatakan tinggi.
E. Himpunan Fuzzy 1. Himpunan Crisp dan Himpunan Fuzzy Himpunan Crisp A didefinisikan oleh item-item yang ada pada himpunan itu. Jika a A , maka nilai yang berhubungan 5
Pemecahan Linear Programming Dua Variabel Menggunakan Logika Fuzzy (Asep Saepuloh – Deni Ahmad Jakaria)
Dengan menggunakan himpunan crisp, misalkan seseorang dikatakan tinggi jika
memiliki tinggi badan diatas 165 cm.
165 cm
Supaya benarbenar tinggi, tinggi badan seseorang harus lebih dari garis ini
Gambar 2.2 Orang-orang dengan tinggi badan yang berbeda Derajat Keanggotaan ( )
TINGGI
1
1
0
Tinggi Badan
TIDAK TINGGI
0
Gambar 2.3 Fungsi keanggotaan TINGGI secara tegas tersebut TIDAK TINGGI dengan ( ) 0 . Hal ini menjadi tidak adil, karena untuk orang yang memiliki tinggi badan 165,1 cm dikatakan TINGGI, sedangkan orang yang meiliki tinggi badan 165 cm dikatakan TIDAK TINGGI.
Secara tegas dapat dikatakan bahwa orang yang memiliki tinggi badan diatas 165 cm dikatakan TINGGI dengan nilai keanggotaan ( ) 1 . Sebaliknya, apabila seseorang memiliki tinggi badan kurang dari atau sama dengan 165 cm, maka secara tegas dikatakan bahwa orang 1
Derajat Keanggotaa n( ) 0
Tingg i Bada n
Mendekati TINGGI Kurang 0,75 TINGGI
0,2
Gambar 2.4 Fungsi Keanggotaan TINGGI secara kontinu 6
Pemecahan Linear Programming Dua Variabel Menggunakan Logika Fuzzy (Asep Saepuloh – Deni Ahmad Jakaria)
Dengan menggunakan himpunan fuzzy, kita bisa membuat suatu fungsi keanggotaan yang bersifat kontinu. Orang yang memiliki tinggi badan 160 cm sudah mendekati tinggi, artinya dia dikatakan TINGGI dengan 0,75 . Sedangkan orang yang memiliki tinggi badan 153 cm, dia memang kurang tinggi, artinya dia dikatakan TINGGI dengan 0,2 3. Domain Himpunan Fuzzy Domain himpunan fuzzy adalah
keseluruhan nilai yang diizinkan dalam semesta pembicaraan. Domain merupakan himpunan bilangan real yang senantiasa naik (bertambah) secara monoton dari kiri ke kanan. Nilai domain dapat berupa bilangan positif maupun negatif. Sebagai contoh, himpunan fuzzy BERAT memiliki domain antara 40 kg sampai 60 kg, seperti terlihat pada gambar 2.5.
BERAT 1
Derajat Keanggotaan ( (x) ) 0 40
45
50
55
60
Berat badan (kg)
Gambar 2.5 Himpunan Fuzy BERAT: berdasarkan berat badan dalam kg 3. Nilai Ambang Alfa – Cut Alfa-Cut atau level-alfa merupakan nilai ambang batas domain yang didasarkan pada nilai kanggotaan untuk tiap-tiap domain. Himpunan ini berisi
semua nilai domain yang merupakan bagian dari himpunan fuzzy dengan nilai keanggotaan lebih besar atau sama dengan .
BERAT 1
Derajat Keanggotaan
0,2
0,2 0 40
Berat badan (kg) 45
50
55
60
Gambar 2.6 Nilai ambang cut untuk himpunan fuzzy BERAT
1
Pemecahan Linear Programming Dua Variabel Menggunakan Logika Fuzzy (Asep Saepuloh – Deni Ahmad Jakaria)
cut lemah dapat dinyatakan sebagai: A (x) cut kuat dapat dinyatakan sebagai: A (x)
Nilai mabang ini membatsai domain himpunan fuzzy. Sebagai contoh, untuk
cut 0,2 , himpunan fuzzy BERAT dibatasi oleh domain 45 kg hingga 60 kg (Gambar 2.6).
Derajat Keanggotaan
BERAT
x
kuat 0
Berat badan (kg)
Gambar 2.7 Himpunan penyokong BERAT sebagai suatu ambang cut Ada 2 alasan, mengapa cut begitu berguna: pertama: cut kuat di nol (0) merupakan himpunan penyokong bagi suatu himpunan fuzzy. Kita dapat membandingkan dengan mudah himpunan level-alfa yang dihasilkan oleh fungsi ini (Gambar 2.6) dan himpunan penyokong
untuk BERAT (Gambar 2.7). Kedua, himpunan level-alfa menunjukkan tenaga atau fungsi kekuatan yang digunakan oleh suatu model fuzzy untuk memutuskan ada tidaknya suatu nilai kebenaran yang harus dipertimbangkan, bernilai sama dengan nol.
Pengantar Fuzzy Linear Programming Salah satu contoh model LP klasik, adalah: Maksimumkan:
f (C ) C T x dengan batasan:
dengan atau
ax b x0 C , x R n , b R m , a R m n
(2.2)
Minimumkan:
f (C ) C T x dengan batasan:
x b x 0
dengan
C , x R n , b R m , a R m n
a , b dan c adalah bilangan-bilangan crisp, tanda pada kasus maksimasi dan tanda pada kasus minimasi juga
(2.3)
bermakna crisp, demikian juga perintah “maksimumkan” atau “minimumkan” merupakan bentuk imperatif tegas. 8
Pemecahan Linear Programming Dua Variabel Menggunakan Logika Fuzzy (Asep Saepuloh – Deni Ahmad Jakaria)
Jika diasumsikan bahwa keputusan LP akan dibuat pada lingkungan fuzzy, maka bentuk (2.2) dan (2.3) akan mengalami sedikit perubahan, yaitu: 1. Bentuk imperatif pada fungsi obyektif tidak lagi benar-benar “maksimum” atau “minimum”, karena adanya beberapa hal yang perlu mendapat pertimbangan dalam suatu sistem. 2. Tanda (pada batasan) dalam kasus maksimasi dan tanda (pada batasan) dalam kasus minimasi tidak lagi bermakna crisp secara matematis, namun sedikit mengalami pelanggaran makna. Hal ini juga disebabkan karena
adanya beberapa yang perlu dipertimbangkan dalam sistem yang mengakibatkan batasan tidak dapat didekati secara tegas. a. Diagram Alir Data (DAD) / Data Flow Diagram (DFD) Diagram konteks dibuat untuk menggambarkan sistem secara keseluruhan. Dalam diagram konteks ini terdapat satu buah external entity (Pengguna) dan satu buah proses (Proses FLP). Data yang mengalir pada diagram konteks ini adalah Data Formula Matematis Linear Programming dan Informasi Hasil.
Diagram Konteks
Pengguna
Fungsi Tujuan, Fungsi Batasan, Toleransi
0 Fuzzy Linear Programming
Informasi Hasil
Gambar 3.4. Diagram Konteks
Gambar 3.5. DFD Level 1
2
Pemecahan Linear Programming Dua Variabel Menggunakan Logika Fuzzy (Asep Saepuloh – Deni Ahmad Jakaria)
III. DAFTAR PUSTAKA A Taha, Hamdy. Riset Operasi Suatu Pengantar, Jilid 1, Edisi kelima. Penerbit Binarupa Aksara, Jakarta, 1996. Aradea, ST. Analisis dan Perancangan Sistem. DCI, STMIK. Prosedur Pelaksanaan Studi Kasus/Tugas Akhir. Penerbit Yayasan Digita Loka, Tasikmalaya, 2006. Kusumadewi, Sri. Analisis dan Sistem Fuzzy menggunakan Tool Box Matlab. Penerbit Graha Ilmu, Yogyakarta, 2003. Kusumadewi, Sri. Aplikasi Logika Fuzzy untuk Pedukung Keputusan. Penerbit Graha Ilmu, Yogjakarta, 2004. Kusumadewi, Sri. Artificial Intellingence (Teknik dan Aplikasinya). Penerbit Graha Ilmu, Yogyakarta, 2003. Pressman, Roger S, Ph.D. Rekayasa Perangkat Lunak (Buku Satu). Penerbit Andi Yogyakarta, Yogyakarta, 2002. Subagyo, Pangestu, M.B.A., Asri, Marwan, M.B.A., Handoko, T. Hani, M.B.A,DR. Dasardasar Operation Research Edisi 2. Penerbit BPFE, Yogyakarta, 1993. Wang, Li-Xin. A Course In Fuzzy System And Control. Penerbit Pretince-Hall International, Inc., 1997.
10