BAB 2 LANDASAN TEORI

BAB 2

LANDASAN TEORI

2.1 Program linier

Program linier adalah suatu teknik penyelesaian optimal atas suatu problema keputusan dengan cara menentukan terlebih dahulu fungsi tujuan (memaksimalkan atau meminimalkan) dan kendala-kendala yang ada ke dalam model matematik persamaan linier. Metode analisis yang paling bagus untuk menyelesaikan persoalan alokasi sumber ialah metode program linier. Pokok pikiran yang utama dalam menggunakan program linier ialah merumuskan masalah dengan jelas dengan menggunakan sejumlah informasi yang tersedia. Sesudah masalah terumuskan dengan baik, maka langkah berikutnya ialah menerjemahkan masalah yang ada ke dalam model matematika.

Program linier sering digunakan dalam menyelesaikan problema-problema alokasi sumber daya, seperti dalam bidang manufacturing, pemasaran, keuangan, personalia, administrasi dan lain sebagainya. Bentuk standar dari permasalahan program linier adalah: a.

Penulisan dalam bentuk skalar untuk kasus maksimasi

Maksimumkan : 𝑓 𝑥1 , 𝑥2 , … , 𝑥𝑛 = 𝑍 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛

(2.1)

Dengan kendala : 𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 = 𝑏1 𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 = 𝑏2 ⋮ 𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 = 𝑏𝑛

Universitas Sumatera Utara

𝑥1 , 𝑥2 , ⋯ , 𝑥𝑛 ≥ 0 Atau dapat juga ditulis dengan menggunakan lambang penjumlahan yaitu: Maksimumkan : 𝑓 𝑥1 , 𝑥2 , … , 𝑥𝑛 = 𝑍 =

𝑛 𝑗 =1 𝑐𝑗 𝑥𝑗

(2.2)

Dengan kendala: 𝑛 𝑗 =1 𝑎𝑖𝑗 𝑥𝑗

= 𝑏𝑖 ,

𝑖 = 1, 2, ⋯ , 𝑚

𝑥𝑗 ≥ 0,

𝑗 = 1, 2, ⋯ , 𝑛

Di mana 𝑐𝑗 , 𝑏𝑖 dan 𝑎𝑖𝑗 diketahui konstan.

Keterangan: 𝒄𝒋 =

parameter yang dijadikan kriteria optimisasi, atau koefisien peubah pengambilan keputusan dalam fungsi tujuan. Untuk kasus maksimasi 𝑐𝑗 menunjukkan keuntungan atau penerimaan per unit, sementara dalam kasus minimasi 𝑐𝑗 menunjukkan biaya per unit.

𝒙𝒋 =

peubah pengambilan keputusan atau kegiatan (yang ingin dicari; yang tidak diketahui). Karena 𝑗 = 1, 2, ⋯ , 𝑛 berarti dalam hal ini terdapat 𝑛 variabel keputusan.

𝒂𝒊𝒋 = koefisien teknologi peubah pengambilan keputusan dalam kendala ke-𝑖 . 𝒃𝒊 =

sumber daya yang terbatas, yang membatasi kegiatan atau usaha yang bersangkutan; disebut juga konstanta sebelah kanan dari kendala ke-𝑖. Karena 𝑖 = 1, 2, ⋯ , 𝑚 berarti dalam hal ini terdapat 𝑚 jenis sumber daya.

𝒁 = Nilai skalar kriteria pengambilan keputusan nilai fungsi tujuan.

b.

Penulisan dalam bentuk matriks untuk kasus maksimasi

Maksimumkan : 𝒁 = 𝒄𝑻 𝑿

(2.3)

Dengan kendala : 𝑨𝑿 = 𝑩 dan 𝑿 ≥ 𝟎


𝒃𝟏 𝒙𝟏 𝒄𝟏 𝒂𝟏𝟏 𝒂𝟏𝟐 … 𝒂𝟏𝒏 𝒙 𝒄 𝒂 𝒂 𝒂 𝒃 Dimana 𝑿 = 𝟐 , 𝑩 = 𝟐 , 𝒄 = 𝟐 , 𝑨 = 𝟐𝟏 𝟐𝟐 … 𝟐𝒏 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 𝒙𝒏 𝒄𝒏 𝒂𝒎𝟏 𝒂𝒎𝟐 …𝒂𝒎𝒏 𝒃𝒏 Dan 𝑻 menyatakan transpose.

2.2 Asumsi-asumsi yang Harus Dipenuhi dalam Program Linier

Ada beberapa asumsi yang harus dipenuhi dalam merumuskan suatu problema keputusan ke dalam model matematik persamaan linier sehingga problema itu dapat dikatakan absah menjadi suatu permasalahan program linier, yaitu:

a.

Asumsi Linierity (Linieritas)

Asumsi ini menyatakan bahwa fungsi tujuan dan semua kendala harus berbentuk linier. Dengan kata lain, apabila suatu kendala melibatkan dua variabel keputusan maka dalam diagram dimensi dua kendala tersebut akan berupa suatu garis lurus. Demikian juga apabila suatu kendala melibatkan tiga variabel akan menghasilkan suatu bidang datar dan kendala yang melibatkan 𝑛 variabel akan menghasilkan hyperplane (bentuk geometris yang rata) dalam ruang berdimensi 𝑛.

b.

Asumsi Additivity (Aditivitas/ Penambahan)

Asumsi ini menyatakan bahwa nilai parameter suatu kriteria optimasi (koefisien variabel keputusan dan fungsi tujuan) merupakan jumlah dari individu-individu 𝑐𝑗 dalam program linier. Misalnya, keuntungan total 𝑍 yang merupakan variabel keputusan, sama dengan jumlah keuntungan yang diperoleh dari masing-masing kegiatan (𝑐𝑗 𝑥𝑗 ). Dan juga, seluruh sumber daya yang digunakan untuk semua kegiatan harus sama dengan jumlah sumber daya yang digunakan untuk masing-masing kegiatan.

c.

Asumsi Proportionality (Proporsionalitas/ Kesebandingan)

Asumsi ini menyatakan bahwa jika variabel keputusan (𝑥𝑗 ) mengalami perubahan, maka dampak perubahannya akan menyebar dalam proporsi yang sama terhadap fungsi tujuan


(𝑐𝑗 𝑥𝑗 ) dan juga pada kendalanya (𝑎𝑖𝑗 𝑥𝑗 ). Misalnya, apabila variabel keputusan dinaikkan dua kali. Maka secara proporsional (seimbang dan serasi) nilai-nilai fungsi tujuan dan kendalanya juga akan menjadi dua kali lipat.

d.

Asumsi Divisibility (Divisibilitas/ Pembagian)

Asumsi ini menyatakan bahwa nilai variabel keputusan (𝑥𝑗 ) yang diperoleh tidak harus berupa bilangan bulat, artinya nilai variabel keputusan bisa diperoleh pada nilai pecahan.

e.

Asumsi Certainty (Deterministik/ Kepastian)

Asumsi ini menghendaki bahwa semua parameter dalam program linier (𝑐𝑗 , 𝑎𝑖𝑗 dan 𝑏𝑖 ) harus bernilai tetap dan diketahui atau ditentukan secara pasti.

2.3 Metode Simpleks

Pada umumnya permasalahan program linier dapat diselesaikan dengan menggunakan metode grafik dan metode simpleks. Kedua metode ini tentunya memiliki kebaikan dan kelemahannya. Aplikasi kedua metode ini tergantung atas problema yang dihadapi.

Metode grafik digunakan apabila jumlah variabel keputusan hanya dua dan jumlah kendala dalam model sedikit (pada umumnya tidak lebih dari 4 kendala). Apabila jumlah kendalanya banyak (> 4 kendala), maka akan sukar untuk melukiskan garis kendalanya dalam grafik.

Sehingga meskipun permasalahan program linier dapat diselesaikan dengan menggunakan metode grafik, akan tetapi untuk permasalahan program linier dengan lebih dari 3 variabel maka metode grafik ini tidak dapat digunakan. Oleh karena itu, pada tahun 1947 George Dantzig mengajukan satu metode yang paling berhasil untuk menyelesaikan suatu permasalahan program linier, dan metode itu dinamakan metode simpleks dan telah diperbaiki oleh beberapa ahli lain.


Metode simpleks adalah suatu metode yang secara sistematis dimulai dari suatu pemecahan dasar yang fisibel ke pemecahan dasar fisibel (feasible) lainnya dan ini dilakukan berulang-ulang (dengan jumlah ulangan yang terbatas) sehingga akhirnya tercapai suatu pemecahan dasar yang optimum dan pada setiap step/ iterasi menghasilkan suatu nilai dari fungsi tujuan yang selalu lebih besar atau sama dari step-step sebelumnya (Supranto, 1983).

2.3.1

Langkah-langkah Metode Simpleks

Mengubah bentuk baku model program linier ke dalam bentuk tabel akan memudahkan proses perhitungan simpleks. Langkah-langkah perhitungan dalam algoritma simpleks adalah: a.

Berdasarkan bentuk baku, tentukan solusi awal (initial basic feasible solution)

dengan menetapkan n-m variabel nonbasis sama dengan nol. Di mana n jumlah variabel dan m banyaknya kendala. b.

Kemudian dipilih sebuah entering variable (variabel yang masuk) di antara yang

sedang menjadi variabel nonbasis, yang jika dinaikkan di atas nol, dapat memperbaiki nilai fungsi tujuan. Apabila tidak ada maka berhenti, berarti solusi sudah optimal. Jika tidak, maka lanjutkan ke langkah c. c.

Selanjutnya pilih sebuah leaving variable (variabel yang keluar) di antara yang

sedang menjadi variabel basis yang harus menjadi nonbasis (nilainya menjadi nol) ketika entering variable menjadi variabel basis. d.

Tentukan solusi yang baru dengan membuat entering variable dan leaving

variable menjadi nonbasis. Selanjutnya kembali ke langkah b.

Selanjutnya akan dijelaskan langkah-langhkah penyelesaian persoalan yang formulasinya mempunyai bentuk sebagai berikut: Maksimumkan: 𝑍=


(2.4)

Dengan kendala:


𝑛 𝑗 =1 𝑎𝑖𝑗 𝑥𝑗

≤ 𝑏𝑖 ,

𝑥𝑗 ≥ 0, 𝑖 = 1, 2, ⋯ , 𝑚 , 𝑗 = 1, 2, ⋯ , 𝑛

Perhitungan simpleks yang lebih rinci akan diterangkan dengan langkah berikut: Langkah 1 : Mengubah fungsi tujuan dan fungsi kendala. Fungsi tujuan diubah menjadi bentuk implisit dengan jalan menggeser semua 𝑐𝑗 𝑥𝑗 ke kiri. Fungsi kendala selain kendala nonnegatif diubah menjadi bentuk persamaan dengan menambahkan variabel slack, yaitu suatu variabel yang mewakili tingkat pengangguran kapasitas yang merupakan batasan.

Langkah 2 : Mentabulasikan persamaan-persamaan yang diperoleh pada langkah 1.

Tabel 2.1 Bentuk Umum Tabel Simplek Awal Basis

𝑪

𝐶1

𝐶2

.

.

𝐶𝑛

0

0

.

.

0

𝒙𝟏

𝒙𝟐

.

.

𝒙𝒏

𝑺𝟏

𝑺𝟐

.

.

𝑺𝒎

Solusi

𝑺𝟏

0

𝑎11

𝑎12

.

.

𝑎1𝑛

1

0

.

.

0

𝑏1

𝑺𝟐

0

𝑎21

𝑎22

.

.

𝑎2𝑛

0

1

.

.

0

𝑏2

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

𝑺𝒎

0

𝑎𝑚1

𝑎𝑚2

.

.

𝑎𝑚𝑛

0

0

.

.

1

𝑏𝑚

−𝐶1

−𝐶2

.

.

−𝐶𝑚

0

0

.

.

0

0

𝒁𝒋 − 𝑪𝒋

Kolom baris menunjukkan variabel yang sedang menjadi basis yaitu 𝑆1 , 𝑆2 , ⋯ , 𝑆𝑚 yang nilainya ditunjukkan oleh kolom solusi. Secara tidak langsung ini menunjukkan bahwa variabel nonbasis 𝑥1 , 𝑥2 , ⋯ , 𝑥𝑛 (yang tidak ditunjukkan pada kolom basis) sama dengan nol.


Langkah 3 : Menentukan entering variable (variabel yang masuk). Tabel di atas memperlihatkan bahwa pada baris 𝑍𝑗 − 𝐶𝑗 kolom 𝑥1 , 𝑥2 , ⋯ , 𝑥𝑛 nilainya negatif. Untuk persoalan dengan fungsi maksimasi, baris 𝑍𝑗 − 𝐶𝑗 dapat diperbaiki dengan meningkatkan nilai 𝑥1 , 𝑥2 , ⋯ , 𝑥𝑛 pada baris 𝑍𝑗 − 𝑐𝑗 menjadi tidak negatif. Untuk itu pilihlah kolom pada baris 𝑍𝑗 − 𝐶𝑗 (termasuk kolom slack) yang mempunyai nilai negatif terbesar, selanjutnya kolom ini digunakan sebagai entering variable. Jika ditemukan lebih dari satu nilai negatif angka terbesar pilihlah salah satu, sebaliknya jika tidak ditemukan nilai negatif berarti solusi sudah optimal. Sebaliknya untuk kasus minimasi, pilihlah kolom pada baris 𝑍𝑗 − 𝐶𝑗 yang nilainya positif terbesar. Jika tidak ditemukan nilai positif berarti solusi sudah optimal. Dan pada persoalan di atas kolom 𝑥2 merupakan entering variable. Langkah 4 : Menentukan leaving variable (variabel yang keluar). Leaving variable dipilih dari rasio yang nilainya positif terkecil. Rasio diperoleh dengan cara membagi nilai solusi dengan koefisien pada kolom entering nya.

𝑅𝑎𝑠𝑖𝑜 = 𝑘𝑜𝑒𝑓𝑖𝑠𝑖𝑒𝑛

𝑛𝑖𝑙𝑎𝑖 𝑠𝑜𝑙𝑢𝑠𝑖

(2.5)

𝑘𝑜𝑙𝑜𝑚 𝑒𝑛𝑡𝑒𝑟𝑖𝑛𝑔𝑛𝑦𝑎

Baris yang memiliki rasio yang nilainya positif terkecil selanjutnya akan digunakan sebagai leaving variable. Jika tidak ada elemen yang nilainya positif dalam kolom kunci (kolom entering variable) ini, maka persoalan tidak memiliki pemecahan. Kolom pada entering variable dinamakan entering column, dan baris yang berhubungan dengan leaving variable dinamakan persamaan pivot. Elemen pada perpotongan entering column dan persamaan pivot dinamakan elemen pivot.

Langkah 5 : Menentukan persamaan pivot baru.

𝑃𝑒𝑟𝑠𝑎𝑚𝑎𝑎𝑛 𝑝𝑖𝑣𝑜𝑡 𝑏𝑎𝑟𝑢 =

𝑝𝑒𝑟𝑠𝑎𝑚𝑎𝑎𝑛 𝑝𝑖𝑣𝑜𝑡 𝑙𝑎𝑚𝑎 𝑒𝑙𝑒𝑚𝑒𝑛 𝑝𝑖𝑣𝑜𝑡

(2.6)


Langkah 6 : Menentukan persamaan-persamaan baru selain persamaan pivot baru. Persamaan baru = (Persamaan lama) – (Koefisien kolom entering x persamaan pivot baru)

(2.7)

Langkah 7 : Lanjutkan perbaikan-perbaikan. Lakukan langkah perbaikan dengan cara mengulang langkah 3 sampai langkah 6 hingga diperoleh hasil optimal.

2.3.2 Program QM

Program QM adalah paket program komputer untuk menyelesaikan persoalan-persoalan metode kuantitatif, manajemen sains atau riset operasi. Program QM juga adalah salah satu software yang dapat digunakan untuk membantu perhitungan masalah program linier.

Gambar 2.1 Tampilan Sementara (Splash) dari Program QM


2.4 Teori Himpunan Crisp Dan Teori Himpunan Fuzzy

Himpunan Crisp A didefinisikan oleh item-item yang ada pada himpunan itu. Pada teori himpunan Crisp, keberadaan suatu elemen pada suatu himpunan A, hanya akan memiliki dua kemungkinan keanggotaan, yaitu menjadi anggota A atau tidak menjadi anggota A (Chak, 1998). Suatu nilai yang menunjukkan seberapa besar tingkat keanggotaan suatu elemen 𝑥 dalam suatu himpunan A, sering disebut dengan nama nilai keanggotaan atau derajat keanggotaan, dinotasikan dengan 𝜇𝐴 𝑥 . Pada himpunan Crisp, hanya ada 2 nilai keanggotaan, yaitu 𝜇𝐴 𝑥 = 1 untuk 𝑥 menjadi anggota A, dan 𝜇𝐴 𝑥 = 0 untuk 𝑥 bukan anggota A.

Teori himpunan fuzzy yang ditemukan oleh Lotfi A. Zadeh pada tahun 1965 merupakan kerangka matematis yang digunakan untuk mempresentasikan ketidakpastian, ketidakjelasan, ketidaktepatan, kekurangan informasi, dan kebenaran parsial (Tettamanzi, 2001). Himpunan fuzzy didasarkan pada gagasan untuk memperluas jangkauan fungsi karakteristik 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. Dengan kata lain, nilai kebenaran suatu item tidak hanya bernilai benar atau salah. Nilai 0 menunjukkan salah, nilai 1 menunjukkan benar, dan masih ada nilai-nilai yang terletak antara benar dan salah.

Menurut (Kusumadewi, 2002) Misalkan dimiliki variabel umur yang dibagi menjadi 3 kategori, yaitu: MUDA

umur < 35 tahun

SETENGAH BAYA

35 tahun ≤ umur ≤ 55 tahun

TUA

umur > 55 tahun Dengan menggunakan pendekatan himpunan Crisp, amatlah tidak adil untuk

menetapkan nilai SETENGAH BAYA. Pendekatan ini bisa saja dilakukan untuk hal-hal yang bersifat diskontinu. Misalkan klasifikasi untuk umur 55 tahun dan 56 tahun


sangatlah jauh berbeda, di mana umur 55 tahun termasuk dalam

setengah baya,

sedangkan umur 56 tahun termasuk sudah tua. Demikian juga halnya untuk klasifikasi muda dan tua. Orang yang berumur 34 tahun dikatakan muda, sedangkan orang yang berumur 35 tahun sudah tidak muda lagi. Orang yang berumur 55 tahun termasuk stengah baya menurut pengklasifikasian, tetapi orang yang berumur 55 tahun lebih 1 hari sudah tidak setengah baya lagi tetapi sudah termasuk tua.

2.5 Fungsi Keanggotaan Trapezoidal (Trapesium)

Fungsi keanggotaan (membership function) adalah suatu kurva yang menunjukkan pemetaan titik-titik input data ke dalam nilai keanggotaannya (sering juga disebut dengan derajat keanggotaan) yang memiliki interval antara 0 sampai 1. Atau dapat dinotasikan sebagai berikut : 𝜇𝐴 : 𝕽 → 0, 1 Untuk x ∈ 𝕽 maka µA(x) adalah derajat keanggotaan x dalam A.

Suatu fungsi keanggotaan himpunan fuzzy disebut fungsi keanggotaan trapezoidal jika mempunyai empat buah parameter, yaitu 𝑎, 𝑏, 𝑐, 𝑑 ∈ ℝ dengan 𝑎 < 𝑏 < 𝑐 < 𝑑, dan dinyatakan dengan 𝑇𝑟𝑎𝑝𝑒𝑠𝑖𝑢𝑚 𝑥, 𝑎, 𝑏, 𝑐, 𝑑 dengan aturan: 𝑥−𝑎 𝑏−𝑎

1

untuk 𝑎 ≤ 𝑥 ≤ 𝑏

(2.8)

untuk 𝑏 ≤ 𝑥 ≤ 𝑐

𝑇𝑟𝑎𝑝𝑒𝑠𝑖𝑢𝑚 𝑥; 𝑎, 𝑏, 𝑐, 𝑑 = 𝑑−𝑥 𝑑−𝑐

0

untuk 𝑐 ≤ 𝑥 ≤ 𝑑 untuk lainnya

Fungsi keanggotaan tersebut dapat juga dinyatakan dengan formula sebagai berikut:


𝑇𝑟𝑎𝑝𝑒𝑠𝑖𝑢𝑚 𝑥; 𝑎, 𝑏, 𝑐, 𝑑 = 𝑚𝑎𝑥 𝑚𝑖𝑛

𝑥−𝑎 𝑏−𝑎

𝑑−𝑥

, 1, 𝑑−𝑐 , 0

(2.9)

2.6 Fuzzy Linear Programming (FLP) Dalam fuzzy linear programming akan dicari suatu nilai 𝑍 yang merupakan fungsi objektif yang akan dioptimasikan sedemikian hingga tunduk pada batasan-batasan yang dimodelkan dengan menggunakan himpunan fuzzy.

Bentuk umum dari fuzzy linear programming (FLP) untuk kasus maksimasi adalah: Maksimumkan: 𝑍=


(2.10)


≤ 𝑏𝑖 ,

𝑥𝑗 ≥ 0 ,

𝑖 = 1, 2, ⋯ , 𝑚 𝑗 = 1, 2, ⋯ , 𝑛

Di mana 𝑐𝑗 , 𝑎𝑖𝑗 , dan 𝑏𝑖 semuanya adalah bilangan fuzzy. Keterangan: 𝑍

=

Fungsi tujuan

𝑐𝑗

=

Nilai kontribusi

𝑥𝑗

=

Variabel keputusan

𝑎𝑖𝑗

=

Koefisien teknologi

𝑏𝑖

=

Konstanta sebelah kanan (sumber daya)

2.6.1 Program Linier Dengan Koefisien Teknologi Berbentuk Bilangan Fuzzy

Bentuk umum dari program linier dengan koefisien teknologi berbentuk bilangan fuzzy untuk kasus maksimasi adalah:


Maksimumkan: 𝑛 𝑗 =1 𝑐𝑗 𝑥𝑗

𝑍=

(2.11)


≤ 𝑏𝑖 ,

𝑖 = 1, 2, ⋯ , 𝑚

𝑥𝑗 ≥ 0,

𝑗 = 1, 2, ⋯ , 𝑛

Untuk kasus program linier dengan koefisien teknologi berbentuk bilangan fuzzy, terdapat beberapa asumsi yang harus dipenuhi, yaitu:

Asumsi 1: Koefisien teknologi

𝑎𝑖𝑗

dikatakan berbentuk bilangan fuzzy apabila

memenuhi syarat fungsi keanggotaan linier berikut: 1

jika 𝑥 < 𝑎𝑖𝑗

𝑎 𝑖𝑗 +𝑑 𝑖𝑗 −𝑥

𝜇𝑎 𝑖𝑗 𝑥 =

(2.12)

jika 𝑎𝑖𝑗 ≤ 𝑥 < 𝑎𝑖𝑗 𝑑𝑖𝑗

𝑑 𝑖𝑗

jika 𝑥 ≥ 𝑎𝑖𝑗 + 𝑑𝑖𝑗

0

di mana 𝑥 ∈ 𝑅 dan 𝑑𝑖𝑗 > 0 untuk semua 𝑖 = 1, 2, ⋯ , 𝑚, 𝑗 = 1, 2, ⋯ , 𝑛.

Defuzzyfikasi adalah perubahan dari suatu besaran fuzzy ke suatu besaran numerik, sedangkan fuzzyfikasi adalah perubahan dari besaran numerik ke suatu besaran fuzzy.

Untuk mendefuzzyfikasi permasalahan ini, pertama-tama fungsi objektif (tujuan) harus diubah ke dalam kondisi fuzzy, yaitu dengan menghitung batas bawah (𝑍𝑙 ) dan batas atas (𝑍𝑢 ) dari nilai optimal awal. Batas-batas dari nilai optimal ini akan diperoleh dengan menyelesaikan permasalahan program linier standar berikut: Maksimumkan: 𝑍1 =


(2.13)


≤ 𝑏𝑖 ,

𝑖 = 1, 2, ⋯ , 𝑚


𝑥𝑗 ≥ 0,

𝑗 = 1, 2, ⋯ , 𝑛

Dan juga Maksimumkan: 𝑍2 =


(2.14)

Dengan kendala: 𝑛 𝑗 =1

𝑎𝑖𝑗 + 𝑑𝑖𝑗 𝑥𝑗 ≤ 𝑏𝑖 , 𝑥𝑗 ≥ 0,

𝑖 = 1, 2, ⋯ , 𝑚 𝑗 = 1, 2, ⋯ , 𝑛

Dari persamaan di atas, nilai dari fungsi objektif (tujuan) berada di antara 𝑍1 dan 𝑍2 di mana nilai koefisien teknologi mengalami perubahan di antara 𝑎𝑖𝑗 dan 𝑎𝑖𝑗 + 𝑑𝑖𝑗 . Dengan nilai batas bawah 𝑍𝑙 = 𝑚𝑖𝑛 𝑍1 , 𝑍2 dan nilai batas atas 𝑍𝑢 = 𝑚𝑎𝑥 𝑍1 , 𝑍2 . Asumsi 2: Permasalahan linier crisp yaitu persamaan 𝑍1 dan 𝑍2 di atas memiliki nilai optimal yang terbatas. Pada kasus ini nilai optimal dari himpunan fuzzy 𝐺, di mana merupakan himpunan bagian dari 𝑅 𝑛 , dalam buku Klir dan Yuan didefinisikan sebagai:

0

jika 𝑛 𝑗 =1 𝐶𝑗 𝑥 𝑗 −𝑍 𝑙

𝜇𝐺 𝑥 =

𝑍𝑢 −𝑍𝑙

1

jika jika


𝑍𝑙 ≤

< 𝑍𝑙



(2.15) < 𝑍𝑢

≥ 𝑍𝑢

Himpunan fuzzy dari kendala ke-𝑖, yaitu 𝐶𝑖 yang merupakan himpunan bagian dari 𝑅 𝑚 , didefinisikan ke dalam persamaan: , 𝑏𝑖 <

0 𝜇𝐶 𝑖 𝑥 =

𝑏 𝑖 − 𝑛𝑗=1 𝑎 𝑖𝑗 𝑥 𝑗 𝑛 𝑑 𝑥 𝑗 =1 𝑖𝑗 𝑗

1

,



, 𝑏𝑖 ≥

𝑛 𝑗 =1

(2.16)

≤ 𝑏𝑖 <

𝑛 𝑗 =1

𝑎𝑖𝑗 + 𝑑𝑖𝑗 𝑥𝑗

𝑎𝑖𝑗 + 𝑑𝑖𝑗 𝑥𝑗


Dengan menggunakan definisi keputusan fuzzy yang diperkenalkan oleh Bellman dan Zadeh, maka terdapat: 𝜇𝐷 𝑥 = 𝑚𝑖𝑛 𝜇𝐺 𝑥 , min𝑖 𝜇𝐶𝑖 𝑥

(2.17)

Untuk kasus ini keputusan fuzzy yang optimal adalah solusi dari permasalahan: max𝑥≥0 𝜇𝐷 𝑥

= max𝑥≥0 𝑚𝑖𝑛 𝜇𝐺 𝑥 , min𝑖 𝜇𝐶𝑖 𝑥

(2.18)

Dengan demikian bentuk umum dari program linier dengan koefisien teknologi berbentuk bilangan fuzzy menjadi permasalahan optimisasi: Maksimumkan: 𝑍=𝜆

(2.19)

Dengan kendala: 𝜇𝐺 𝑥 ≥ 𝜆 𝜇𝐶𝑖 𝑥 ≥ 𝜆, 𝑖 = 1, 2, ⋯ , 𝑚 𝑥 ≥ 0,

0≤𝜆≤1

Dengan menggunakan persamaan (2.15) dan (2.16), permasalahan di atas dapat ditulis ke dalam bentuk:

Maksimumkan: 𝑍=𝜆

(2.20)

Dengan kendala: 𝜆 𝑍𝑢 − 𝑍𝑙 − 𝑛 𝑗 =1


+ 𝑍𝑙 ≤ 0

𝑎𝑖𝑗 + 𝜆𝑑𝑖𝑗 𝑥𝑗 − 𝑏𝑖 ≤ 0,

𝑖 = 1, 2, ⋯ , 𝑚, 𝑗 = 1, 2, ⋯ , 𝑛 𝑥𝑗 ≥ 0, 0 ≤ 𝜆 ≤ 1

Dengan catatan kendala dalam permasalahan ini mengandung aturan cross product yaitu 𝜆𝑥𝑗 adalah nonkonveks. Oleh Karena itu solusi dari permasalahan ini memerlukan


penyelesaian khusus yang diadopsi dari penyelesaian permasalahan optimisasi nonkonveks.

2.6.2 Program Linier Dengan Koefisien Teknologi Dan Konstanta Sebelah Kanan Berbentuk Bilangan Fuzzy

Bentuk umum dari program linier dengan koefisien teknologi dan konstanta sebelah kanan berbentuk bilangan fuzzy untuk kasus maksimasi adalah:

Maksimumkan: 𝑍=


(2.21)


≤ 𝑏𝑖 ,

𝑥𝑗 ≥ 0,

𝑖 = 1, 2, ⋯ , 𝑚 𝑗 = 1, 2, ⋯ , 𝑛

Untuk kasus program linier dengan koefisien teknologi dan konstanta sebelah kanan berbentuk bilangan fuzzy, terdapat beberapa asumsi yang harus dipenuhi, yaitu:

Asumsi 1: Koefisien teknologi

𝑎𝑖𝑗

dan konstanta sebelah kanan

𝑏𝑖 dikatakan

berbentuk bilangan fuzzy apabila memenuhi syarat fungsi keanggotaan linier berikut:

1 𝜇𝑎 𝑖𝑗 𝑥 =

𝑎 𝑖𝑗 +𝑑 𝑖𝑗 −𝑥 𝑑 𝑖𝑗

0

jika

𝑥 < 𝑎𝑖𝑗

jika

𝑎𝑖𝑗 ≤ 𝑥 < 𝑎𝑖𝑗 + 𝑑𝑖𝑗

jika

𝑥 ≥ 𝑎𝑖𝑗 + 𝑑𝑖𝑗

(2.22)

Dan juga


1 𝑏 𝑖 +𝑝 𝑖 −𝑥

𝜇𝑏 𝑖 𝑥 =

𝑑 𝑖𝑗

0

jika

𝑥 < 𝑏𝑖

jika

𝑏𝑖 ≤ 𝑥 < 𝑏𝑖 + 𝑝𝑖

jika

𝑥 ≥ 𝑏𝑖 + 𝑝𝑖

(2.23)

Di mana 𝑥 ∈ 𝑅. Untuk mendefuzzyfikasi permasalahan ini, pertama-tama akan dicari nilai optimal dari batas atas 𝑍𝑢 dan batas bawah 𝑍𝑙 permasalahan tersebut. Nilai batas-batas tersebut akan diperoleh dengan menyelesaikan permasalahan program linier standar, dengan mengasumsikan bahwa batas-batas tersebut memiliki nilai optimal yang terbatas. Untuk 𝑍1 , persamaannya adalah: Maksimumkan: 𝑍1 =


(2.24)


𝑎𝑖𝑗 + 𝑑𝑖𝑗 𝑥𝑗 ≤ 𝑏𝑖 , 𝑥𝑗 ≥ 0,

𝑖 = 1, 2, ⋯ , 𝑚 𝑗 = 1, 2, ⋯ , 𝑛

Untuk 𝑍2 , persamaannya adalah: Maksimumkan: 𝑍2 =


(2.25)


≤ 𝑏𝑖 + 𝑝𝑖 ,

𝑖 = 1, 2, ⋯ , 𝑚 𝑗 = 1, 2, ⋯ , 𝑛

𝑥𝑗 ≥ 0, Untuk 𝑍3 , persamaannya adalah: Maksimumkan: 𝑍3 =


(2.26)


𝑎𝑖𝑗 + 𝑑𝑖𝑗 𝑥𝑗 ≤ 𝑏𝑖 + 𝑝𝑖 ,

𝑖 = 1, 2, ⋯ , 𝑚


𝑥𝑗 ≥ 0,

𝑗 = 1, 2, ⋯ , 𝑛

Dan untuk 𝑍4 , persamaannya adalah: Maksimumkan: 𝑍4 =


(2.27)


≤ 𝑏𝑖 ,

𝑖 = 1, 2, ⋯ , 𝑚

𝑥𝑗 ≥ 0,

𝑗 = 1, 2, ⋯ , 𝑛

Maka batas bawah 𝑍𝑙 = 𝑚𝑖𝑛 𝑍1 , 𝑍2 , 𝑍3 , 𝑍4 dan batas atas 𝑍𝑢 = 𝑚𝑎𝑥 𝑍1 , 𝑍2 , 𝑍3 , 𝑍4 . Nilai dari fungsi objektif berada di antara batas bawah dan batas atas sementara nilai koefisien teknologi berada di antara 𝑎𝑖𝑗 dan 𝑎𝑖𝑗 + 𝑑𝑖𝑗 , dan nilai konstanta sebelah kanan berada di antara 𝑏𝑖 dan 𝑏𝑖 + 𝑝𝑖 . Asumsi 2: Nilai optimal himpunan fuzzy 𝐺, didefinisikan sebagai:

0

jika 𝑛 𝑗 =1 𝐶𝑗 𝑥 𝑗 −𝑍 𝑙

𝜇𝐺 𝑥 =

jika

𝑍𝑢 −𝑍𝑙

1

jika


𝑍𝑙 ≤

< 𝑍𝑙



(2.28) < 𝑍𝑢

≥ 𝑍𝑢

Himpunan fuzzy dengan kendala ke-𝑖 yaitu 𝐶𝑖 yang merupakan himpunan bagian dari 𝑅 𝑛 didefinisikan ke dalam: , 𝑏𝑖 <

0 𝜇𝐶 𝑖 𝑥 =

𝑏 𝑖 − 𝑛𝑗=1 𝑎 𝑖𝑗 𝑥 𝑗

,

𝑛 𝑑 𝑥 𝑗 =1 𝑖𝑗 𝑗


, 𝑏𝑖 ≥

1


𝑛 𝑗 =1

≤ 𝑏𝑖

(2.29) 𝑛 𝑗 =1

𝑎𝑖𝑗 𝑥𝑗 + 𝑝𝑖

𝑎𝑖𝑗 + 𝑑𝑖𝑗 𝑥𝑗 + 𝑝𝑖

Dengan menggunakan metode defuzzyfikasi, permasalahan direduksi menjadi: Maksimumkan: 𝑍=𝜆

(2.30)


Dengan kendala: 𝜆 𝑍𝑢 − 𝑍𝑙 − 𝑛 𝑗 =1


+ 𝑍𝑙 ≤ 0

𝑎𝑖𝑗 + 𝜆𝑑𝑖𝑗 𝑥𝑗 + 𝜆𝑝𝑖 − 𝑏𝑖 ≤ 0,

𝑖 = 1, 2, ⋯ , 𝑚, 𝑗 = 1, 2, ⋯ , 𝑛 𝑥𝑗 ≥ 0, 0 ≤ 𝜆 ≤ 1

Dengan catatan seperti pada kasus program linier dengan koefisien teknologi berupa bilangan fuzzy.


BAB 2 LANDASAN TEORI

Recommend Documents