Fuzzy Linear Programming – part 1

Sebelum kita mengarah pada bagaimana himpunan fuzzy dibuat untuk kekurangan pada Linear programming, sebaiknya kita terlebih dahulu mengetahui apa itu optimasi.

Optimasi

Menurut Nash dan Sofer (1996), optimasi adalah sarana untuk mengekspresikan model matematika yang bertujuan memecahkan masalah dengan cara terbaik. Untuk tujuan bisnis, hal ini berarti memaksimalkan keuntungan dan efisiensi serta meminimalkan kerugian, biaya atau resiko.

Hal ini juga berarti merancang sesuatu untuk meminimalisasi bahan baku atau memaksimalisasi keuntungan. Adapun keinginan untuk memecahkan masalah dengan model optimasi secara umum sudah digunakan pada banyak aplikasi.

Model optimasi telah digunakan selama berabad-abad. Pada masa sekarang ini, optimasi menjadi sangat esensial untuk tujuan bisnis yang semakin kompleks dan rumit. Para insinyur pun menjadi semakin ambisius dalam mengembangkan hal ini. Dalam banyak hal, keputusan dapat saja dibuat tanpa mempertimbangkan tujuan dari model tersebut. Sebagai contoh, dalam kerjasama multinasional, sebagian kecil perkembangan proses operasi dapat mencapai peningkatan keuntungan berjuta-juta dolar. Tetapi, untuk mencapainya dibutuhkan analisis dan kerjasama setiap divisi.

Untuk model yang kompleks, dengan berbagai kerumitan yang ada, keputusan bisnis akan sangat berpengaruh. Dalam beberapa dasawarsa ini, telah dikembangkan hardware dan software komputer, yang berhasil melakukan optimasi secara praktis dalam bisnis dan ilmu pengetahuan. Sekarang ini, pemecahan masalah dengan ribuan atau bahkan jutaan variabel menjadi mungkin untuk diselesaikan.

Linear Programming

Linear Programming merupakan model umum yang dapat digunakan dalam pemecahan masalah pengalokasian sumber-sumber yang terbatas secara optimal. Masalah tersebut timbul apabila seseorang diharuskan untuk memilih atau menentukan tingkat setiap kegiatan yang akan dilakukannya, di mana masing-masing kegiatan membutuhkan sumber yang sama sedangkan jumlahnya terbatas. Secara sederhana, dapat diambil contoh bagian produksi suatu perusahaan yang dihadapkan pada masalah penentuan tingkat produksi masingmasing jenis produk dengan memperhatikan batasan faktor-faktor produksi: mesin, tenaga kerja, bahan mentah, dan sebagainya untuk memperoleh tingkat keuntungan maksimal atau biaya yang minimal.

Pada masa modern sekarang, Linear Programming masih menjadi pilihan dalam upaya untuk memperoleh tingkat keuntungan maksimal atau biaya yang minimal.

Dalam memecahkan masalah di atas, Linear Programming menggunakan model matematis. Sebutan “linear” berarti bahwa semua fungsi matematis yang disajikan dalam model ini haruslah fungsi-fungsi linier. Dalam Linear Programming dikenal dua macam fungsi, yaitu fungsi tujuan (objective function) dan fungsi-fungsi batasan (constraint function). Fungsi tujuan adalah fungsi yang menggambarkan tujuan/sasaran di dalam  permasalahan Linear Programming yang berkaitan dengan pengaturan secara optimal sumber daya-sumber daya, untuk memperoleh keuntungan maksimal atau biaya minimal. Pada umumnya nilai yang akan dioptimalkan dinyatakan sebagai Z. Fungsi batasan merupakan bentuk penyajian secara matematis batasan-batasan kapasitas yang tersedia yang akan dialokasikan secara optimal ke berbagai kegiatan.

Menurut Supranto(1983,p76-82), suatu persoalan disebut persoalan Linear Programming apabila memenuhi:

1. Tujuan (obyektif) yang akan dicapai harus dapat dinyatakan dalam fungsi linier. Fungsi ini disebut fungsi tujuan (fungsi obyektif).

2. Harus ada alternatif pemecahan yang membuat nilai fungsi tujuan optimum (laba yang maksimum, biaya yang minimum).

3. Sumber-sumber tersedia dalam jumlah yang terbatas (bahan mentah, modal, dan sebagainya). Kendala-kendala ini harus dinyatakan di dalam pertidaksamaan linier (linear inequalities).

Pada dasarnya, persoalan Linear Programming dapat dirumuskan sebagai berikut.

Cari x1,x2, …, xj, …, xn.

sedemikian rupa sehingga

Z = c1×1 + c2×2 + … + cjxj + … + cnxn = Optimum (Maksimum atau Minimum)

dengan kendala:

Keterangan:

Ada n macam barang yang akan diproduksi masing-masing sebesar x1, x2, … , xj, … xn.

xj = banyaknya produksi barang yang ke j, j = 1,2,…,n
cj = harga per satuan barang ke j, disebut “price”

Ada m macam bahan mentah masing-masing tersedia h1, h2, …, hj, …, hm.
hi = banyaknya bahan mentah ke i, i = 1,2, …,m
aij = banyaknya bahan mentah ke i yang dipergunakan untuk memproduksi 1 satuan barang ke j

xj unit memerlukan aij unit bahan mentah i.

Asumsi-asumsi Linear Programming

Asumsi-asumsi Linear Programming dapat dirinci sebagai berikut.

o Proportionality

Asumsi ini berarti bahwa naik turunnya nilai Z dan penggunaan sumber atau fasilitas yang tersedia akan berubah secara sebanding (proporsional) dengan perubahan tingkat kegiatan.

Z = C1X1 + C2X2 + C3X3 + …..CnXn

Setiap penambahan 1 unit X1 akan menaikkan Z dengan C1. Setiap penambahan 1 unit X2 akan menaikkan Z dengan C2, dan seterusnya.

a11X1 + a12X2 + a13X3 + ….. + anXn ≤ b1

Setiap penambahan 1 unit X1 akan menaikkan penggunaan sumber/fasilitas 1 dengan a11. Setiap penambahan 1 unit X2 akan menaikkan penggunaan sumber/fasilitas 1 dengan a12, dan seterusnya. Asumsinya adalah, setiap ada kenaikan kapasitas riil tidak perlu ada biaya persiapan (set up cost).

o Additivity

Asumsi ini berarti bahwa nilai tujuan tiap kegiatan tidak saling mempengaruhi, atau dalam Linear Programming dianggap bahwa kenaikan dari nilai tujuan (Z) yang diakibatkan oleh kenaikan suatu kegiatan dapat ditambahkan tanpa mempengaruhi bagian nilai Z yang diperoleh dari kegiatan lain.

Z = 3X1 + 5X2 di mana X1 = 10; X2 = 2;

Sehingga Z = 30 + 10 = 40

Jika X1 bertambah 1 unit, maka sesuai dengan asumsi, maka nilai Z menjadi 40 + 3 = 43. Jadi, nilai 3 karena kenaikan X1 dapat langsung ditambahkan pada nilai Z mula-mula tanpa mengurangi bagian Z yang diperoleh dari kegiatan 2 (X2). Dengan kata lain, tidak ada korelasi antara X1 dan X2.

o Divisibility

Asumsi ini menyatakan bahwa keluaran yang dihasilkan oleh setiap kegiatan dapat berupa bilangan pecahan. Demikian pula dengan nilai Z yang dihasilkan.

o Deterministic (certainty)

Asumsi ini menyatakan bahwa semua parameter yang terdapat dalam model Linear Programming (aij, bi, cj) dapat diperkirakan dengan pasti, meskipun jarang dengan tepat.

Simplex Linear Programming

Apabila suatu masalah Linear Programming hanya mengandung dua kegiatan (variabel-variabel keputusan) saja, maka dapat diselesaikan dengan metode grafik. Bila terdapat lebih dari dua variabel maka metode grafik tidak dapat digunakan lagi, sehingga diperlukan metode simpleks. Metode ini lazim dipakai untuk menentukan kombinasi dari tiga variabel atau lebih.

Masalah Linear Programming yang melibatkan banyak variabel keputusan dapat dengan cepat dipecahkan dengan bantuan komputer. Bila variabel keputusan yang dikandung tidak terlalu banyak, masalah tersebut dapat diselesaikan dengan suatu algoritma yang biasanya sering disebut metode tabel simpleks. Disebut demikian karena kombinasi variabel keputusan yang optimal dicari dengan menggunakan tabel-tabel.

Menurut Subagyo et al. (1983,p34-39), langkah-langkah metode tabel simpleks adalah sebagai berikut.

1. Mengubah fungsi tujuan dan batasan-batasan Fungsi tujuan diubah menjadi fungsi implisit, artinya semua cjxj digeser ke kiri.

2. Menyusun persamaan-persamaan di dalam tabel.
Setelah formulasi disusun ke dalam tabel dan simbol, maka akan tampak seperti pada tabel berikut.

Sumber: Subagyo (1983, p50)

NK adalah nilai kanan persamaan, yaitu nilai di belakang tanda sama dengan (=). Variabel dasar adalah variabel yang nilainya sama dengan sisi kanan dari persamaan. Pada tabel tersebut, nilai variabel dasar
pada fungsi tujuan (fungsi permulaan) ini harus 0, dan nilainya pada kendala-kendala bertanda positif.

Setelah data disusun dalam tabel-tabel di atas kemudian diadakan perubahan-perubahan agar dapat mencapai titik optimal, dengan langkahlangkah selanjutnya.

3. Memilih kolom kunci.
Kolom kunci adalah kolom yang merupakan dasar untuk mengubah tabel di atas. Dipilih kolom yang mempunyai nilai pada baris fungsi tujuan yang bernilai negatif dengan angka terbesar. Kalau suatu tabel
sudah tidak memiliki nilai negatif pada baris fungsi tujuan, berarti tabel itu tidak bisa dioptimalkan lagi.

4. Memilih baris kunci.
Baris kunci adalah baris yang merupakan dasar untuk mengubah tabel tersebut di atas. Untuk itu, terlebih dahulu dicari indeks tiap-tiap baris dengan cara membagi nilai-nilai pada kolom NK dengan nilai yang
sebaris pada kolom kunci.

Indeks = nilai kolom NK / nilai kolom kunci. Kemudian dipilih angka yang memiliki nilai positif terkecil.

5. Mengubah nilai-nilai baris kunci.
Nilai baris kunci diubah dengan cara membaginya dengan angka kunci.

6. Mengubah nilai-nilai selain pada baris kunci.
Nilai-nilai baris yang lain, selain pada baris kunci dapat diubah dengan rumus berikut:
Baris baru = baris lama – (koefisien pada kolom kunci) x nilai baru baris kunci

7. Melanjutkan perbaikan-perbaikan/perubahan-perubahan Ulangi langkah perbaikan mulai langkah ke-3 sampai langkah ke-6 untuk memperbaiki tabel-tabel yang telah diubah/diperbaiki nilainya. Perubahan baru berhenti setelah baris pertama (fungsi tujuan) tidak ada yang bernilai negatif.

Menurut Subagyo et al. (1995,p43-46), terdapat beberapa ketentuan tambahan yang berupa :

1) Terdapat lebih dari satu kolom bernilai “negatif terbesar yang sama”.
Kalau pada baris fungsi tujuan terdapat lebih dari satu kolom yang mempunyai nilai negatif yang angkanya terbesar dan sama, maka ada dua kolom yang bisa terpilih menjadi kolom kunci. Untuk mengatasi hal ini, dapat dipilih salah satu secara sembarang.

2) Dua baris atau lebih mempunyai indeks positif terkecil.
Kalau ada dua baris atau lebih yang mempunyai nilai positif terkecil yang sama, maka ada beberapa baris yang dapat terpilih sebagai baris kunci. Dapat dipilih baris kunci secara bebas di antara keduanya dan hasilnya akan sama.

3) Kenaikan nilai Z tidak terbatas.
Nilai Z (tujuan) suatu permasalahan dapat ditambah terus bila paling tidak ada satu kegiatan yang tidak ada batasannya. Kalau di dalam Linear Programming muncul hal-hal semacam ini, tidak perlu dilanjutkan, cukup disebutkan bahwa kenaikan nilai Z dapat tidak terbatas. Di samping itu, ada baiknya pula bila diteliti lagi formulasi masalahnya, sebab hal ini dapat pula terjadi karena kesalahan dalam formulasi.

4) Multiple Optional Solutions.
Untuk mengetahui apakah suatu masalah Linear Programming bersifat multiple solutions atau tidak, dilihat baris fungsi tujuan pada tabel terakhir (optimal). Apabila dalam baris itu terdapat paling tidak satu kolom variabel yang mempunyai nilai 0 maka masalah itu bersifat multiple solutions. Masalah itu akan menghasilkan paling tidak dua alternatif yang mempunyai nilai Z yang sama. Selain itu juga ada  penyimpangan-penyimpangan daribentuk standar, dimana penyimpangan-penyimpangan tersebut akan diatasi agar bisa diselesaikan dengan metode simpleks.

a) Batasan dengan tanda “sama dengan”.
Kalau suatu batasan memakai tanda kesamaan, maka cara mengatasinya dengan menambahkan variabel buatan (artificial variable).

b) Minimasi
Fungsi tujuan dari permasalahan Linear Programming yang bersifat minimasi, harus diubah menjadi maksimasi, agar sesuai dengan bentuk standar, yaitu maksimasi. Caranya adalah dengan mengganti tanda
positif dan negatif pada fungsi tujuan.

c) Fungsi pembatas bertanda ≥.
Bila suatu fungsi pembatas bertanda ≥, maka harus diubah menjadi ≤ dan akhirnya menjadi = agar dapat
diselesaikan dengan metode simpleks.

d) Bagian kanan persamaan bertanda negatif.
Bila bagian kanan persamaan bertanda negatif maka harus diubah menjadi positif. Caranya dengan mengubah tanda positif negatif dari tiap-tiap koefisien, kemudian ditambah dengan variabel buatan.

e) Bila minimum nilai Xj boleh negatif.
Pada bentuk standar, nilai Xj harus selalu positif (dengan batasan Xj ≥ 0). Tetapi kadang-kadang suatu
masalah dapat menghasilkan formulasi Linear Programming yang memungkinkan nilai Xj negatif.

f) Bila nilai Xj boleh positif atau negatif Kalau hasil Linear Programming memungkinkan nilai Xj positif maupun negatif dan tidak ada batas negatif tertentu (negatif berapa pun dimungkinkan) maka nilai Xj
diubah menjadi X’j – X”j, dengan ketentuan sebagai berikut:

X’j = mewakili nilai positif dari Xj
X”j = mewakili nilai negatif dari Xj

ref : http://ai.indra-ehm.net

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: