15
BAB 2 LANDASAN TEORI
2.1
Efisiensi Menurut Vincent Gaspersz (1998, hal 14), efisiensi adalah ukuran yang menunjukan bagaimana baiknya sumber daya digunakan dalam proses produksi untuk menghasilkan output. Efisiensi merupakan karakteristik dari proses yang mengukur performansi aktual dari sumber daya relatif terhadap standar yang ditetapkan. Peningkatan dalam efisiensi pada proses produksi akan menurunkan biaya per unit output.
2.2
Model Model adalah abstraksi atau penyederhanaan realitas sistem yang kompleks di mana hanya komponen – komponen yang relevan atau faktor – faktor yang dominan dari masalah yang dianalisis diikutsertakan. Model menunjukan hubungan (langsung dan tidak langsung) dari aksi dan reaksi dalam pengertian sebab dan akibat. Karena sebuah model adalah suatu abstraksi realitas, model akan tampak kurang kompleks dibanding realitas itu sendiri. Model itu, agar menjadi lengkap, perlu mencerminkan semua realitas yang sedang diteliti. Salah satu alasan dalam pembentukan model adalah
untuk menemukan variabel –
variabel apa yang penting atau menonjol. Penemuan variabel – variabel yang penting itu berkaitan erat dengan penyelidikan hubungan yang ada diantara
16
variabel – variabel itu. Teknik – teknik kuantitatif seperti statistik dan simulasi digunakan untuk menyelidiki hubungan yang ada diantara banyaj variabel dalam suatu model. (Sri Mulyono, 2002, hal 4) 2.2.1
Mathematic (Simbolic) Model Diantara jenis model yang lain, model matematik sifatnya paling abstrak.
Model ini menggunakan seperangkat simbol matematik untuk menunjukan komponen – komponen (dan hubungan antar mereka) dari sistem nyata. Namun, sistem nyata tidak selalu dapat diekspresikan dalam rumusan matematik. Model ini dapat dibedakan menjadi dua kelompok, yaitu dererministik dan probabilistik. Model deterministik dibentuk dalam situasi kepastian. Model ini memerlukan penyederhanaan – penyederhanaan dari realitas karena kepastian jarang terjadi. Namun, keuntungan model ini adalah bahwa ia dapat dimanipulasi dan diselesaikan lebih mudah. Jadi, sistem yang rumit dapat dimodel dan dianalisa jika dapat diasumsikan bahwa semua komponen sistem itu dapat diketahui dengan pasti. Model probabilistik meliputi kasus – kasus di mana diasumsikan ketidakpastian. Meskipun penggabungan ketidakpastian dalam model dapat menghasilkan suatu penyajian sistem nyata yang lebih realistis, model ini umumnya lebih sulit untuk dianalisa. Kadang – kadangm model yang pertama kali dibuat masih terlalu rumit. Ada beberapa cara untuk membuat model menjadi lebih sederhana, misalnya : 1. Melinierkan hubungan yang tidak linier.
17
2. Mengurangi banyaknya variabel dan kendala. 3. Mengubah sifat variabel, misalnya dari diskrit menjadi kontinyu. 4. Mengganti tujuan ganda menjadi tujuan tunggal. 5. Mengeluarkan unsur dinamik (membuat model menjadi statik) 6. Mengasumsikan variabel random menjadi suatu nilai tunggal (deterministik).
Pembentukan model adalah esensi dari pendekatan Operation Research karena solusi dari pendekatan ini tergantung pada ketepatan model yang dibuat. Philips, Ravindran, dan Solberg (1976) mengingatkan sepuluh prinsip dalam pembentukan model, yaitu: 1. Jangan membuat model yang rumit jika yang sederhana akan cukup. 2. Hati – hati dalam merumuskan masalah, agar disesuaikan dengan teknik penyelesaian. 3. Hati – hati dalam memecahkan model, jangan membuat kesalahan matematik. 4. Pastikan kecocokan model sebelum diputuskan untuk diterapkan. 5. Model jangan sampai keliru dengan sistem nyata. 6. Jangan membuat model yang tidak diharapkan. 7. Hati – hati dengan model yang terlalu banyak. 8. Pembentukan model itu sendiri hendaknya memberikan beberapa keuntungan. 9. Sampah masuk, sampah keluar artinya nilai suatu model tidak lebih baik dari pada datanya. 10. Model tidak dapat menggantikan pengambilan keputusan.
18
Pola dasar penerapan OR terhadap suatu masalah dapat dipisahkan menjadi beberapa tahap: a. Merumuskan masalah Sebelum solusi terhadap suatu persoalan dipikirkan, pertama kali sautu definisi persoalan yang tepat harus dirumuskan. Sering dilaporkan oleh organisasi – organisasi bahwa
kegagalan dalam penyelesaian masalah
diakibatkan karena kesalahan mendefinisakan persoalan. Dalam perumusan masalah ini ada tiga pertanyaan yang harus dijawab: o Variabel keputusan yaitu unsur – unsur dalam persoalan yang dapat dikendalikan oleh pengambil keputusan. Ia sering disebut sebagai instrument. o Tujuan (objective). Penetapan tujuan membantu pengambil keputusan memusatkan perhatian pada persoalan dan pengaruhnya terhadap organisasii. Tujuan ini diekspresikan dalam variabel keputusan. o Kendala (constraint) adalah pembatas – pembatas terhadap alternatif tindakan yang tersedia.
b. Pembentukan Model Sesuai dengan definisi persoalannya, pengambil keputusan menentukan model yang paling cocok untuk mewakili sistem. Model merupakan ekspresi kuantitatif dari tujuan dan kendala – kendala persoalan dalam variabel
19
keputusan. Jika model yang dihasilkan cocok dengan salah satu model matematik yang biasa (misalnya linier), maka solusinya dapat dengan mudah diperoleh dengan program linier. Jika hubungan matematik model begitu rumit untuk penerapan solusi analitik, maka suatu model probabilita mungkin lebih cocok. Beberapa kasus membutuhkan penggunaan kombinasi model matematik dan probabilitas. Ini tentu saja bergantung pada sifat – sifat dan kerumitan sistem yang dipelajari. c. Mencari penyelesaian masalah Pada tahap ini bermacam – macam teknik dan metode solusi kuantitatif yang merupakan bagian utama dari Operation Research memasuki proses. Penyelesaian masalah sesungguhnya merupakan aplikasi satu atau lebih teknik – teknik ini terhadap model. Seringkali solusi terhadap model berarti nilai – nilai variabel keputusan yang mengoptimumkan salah satu fungsi tujuan dengan nilai fungsi tujuan lain yang dapat diterima. Disamping solusi model, perlu juga mendapat informasi tambahan mengenai tingkah laku solusi yang disebabkan karena perubahan parameter sistem. Ini biasanya dinamakan sebagai Analisis Sensitivitas. Analisis ini terutama diperlukan jika parameter sistem tak dapat diduga secara tepat. d. Validasi Model Asumsi – asumsi yang digunakan dalam pembentukan model harus absah. Dengan kata lain, model harus diperiksa apakah ia mencerminkan berjalannya sistem yang diwakili. Suatu metode yang biasa digunakan untuk menguji
20
validitas model adalah membandingkan performancenya dengan data masa lalu yang tersedia. Model dikatakan valid jika dengan kondisi input yang serupa, ia dapat menghasilkan kembali performamce seperti masa lampau. Masalahnya adalah bahwa tak ada yang menjamin performance masa depan akan berlanjut meniru cerita lama. (Sri Mulyono, 2002, hal 5 – 8)
2.2.2
Linear Programming Linear Programming merupakan suatu model umum yang dapat digunakan
dalam pemecahan masalah pengalokasian sumber – sumber yang terbatas secara optimal. Kata “linear” berarti bahwa semua fungsi – fungsi matematis yang disajikan dalam model ini haruslah fungsi – fungsi linear maka linear programming mencakup perencanaan kegiatan – kegiatan untuk mencapai suatu hasil yang “optimal”, yaitu suatu hasil yang mencerminkan tercapainya saasran tertentu yang paling baik (menurut model matematis) di antara alternatif – alternatif yang mungkin, dengan menggunakan fungsi linear (Pangestu, 2002, hal 9 – 10). George B. Dantzig diakui umum sebagai pioner LP, karena jasanya dalam menemukan metode mencari solusi masalah LP dengan banyak variabel keputusan (Sri Mulyono, 2002, hal 13). Model Linear Programming dikenal 2 macam “fungsi”, yaitu fungsi tujuan (objective function) dan fungsi – fungsi batasan (constraint function). Fungsi tujuan adalah fungsi yang menggambarkan tujuan atau sasaran di dalam permasalahan Linear Programming yang berkaitan
21
dengan pengaturan secara optimal sumber daya – sumber daya, untuk memperoleh keuntungan maksimal atau biaya minimal. Agar memudahkan pembahasan model LP ini, digunakan simbol – simbol sebagai berikut : m = macam batasan – batasan sumber atau fasilitas yang tersedia. n
= macam kegiatan – kegiatan yang menggunakan sumber atau fasilitas tersebut.
i
= Nomor setiap macam sumber atau fasilitas yang tersedia ( i = 1, 2, 3,..., m).
j
= Nomor setiap macam kegiatan yang menggunakan sumber atau fasilitas yang tersedia ( j = 1, 2,.., n).
xj
= tingkat kegiatan ke j ( j = 1, 2,..., n).
aij = banyaknya sumber i yang diperlukan untuk menghasilkan setiap unit keluaran (output) kegiatan j ( i = 1, 2, ..., m, dan j = 1, 2, ..., n). bi
= banyaknya sumber (fasilitas) i yang tersedia untuk dialokasikan ke setiap unit kegiatan ( i = 1, 2, ..., n).
Z
= nilai yang dioptimalkan (maksimum atau minimum).
Cj = Kenaikan nilai Z apabila ada pertambahan tingkat kegiatan (xj) dengan satu satuan (unit); atau merupakan sumbangan setiap satuan keluaran kegiatan j terhadap nilai Z.
22
Keseluruhan simbol – simbol diatas selanjutnya disusun ke dalam bentuk tabel standar LP seperti di bawah ini : Tabel 2.1. Data untuk model Linear Programming Pemakaian sumber per
Kapasitas
unit kegiatan (keluaran)
sumber
1
2
3
......
n
1
a11
a12
a13 ......
a1n
b1
2
a21
a22
a23 ......
a2n
b2
3
a31
a32
a33 ......
a3n
b3
.
.
.
.
.
.
.
.
.
m
am1
am2
am3 ......
amn
ΔZ pertambahan tiap unit
C1
C2
C3
......
Cn
Tingkat Kegiatan
X1
X2
X3
......
Xn
bm
Atas dasar tabel diatas kemudian dapat disusun suatu model matematis yang digunakan untuk mengemukakan suatu permasalahan LP sebagai berikut : Fungsi tujuan : Maksimumkan Z = C1 X 1 + C 2 X 2 + C 3 X 3 + .... + C n X n
23
Batasan – batasan : 1) a11 x1 + a12 x 2 + ... + a1n x n ≤ b1 2) a 21 x1 + a 22 x 2 + ... + a 2 n x n ≤ b2 . . . 3) a m1 x1 + a m 2 x 2 + ... + a mn x n ≤ bm dan X 1 ≥ 0, X 2 ≥ 0,....... X n ≥ Bantuk atau model LP diatas merupakan bentuk standar bagi masalah – masalah LP yang akan dipakai selanjutnya. Dengan kata lain bila setiap masalah dapat diformulasikan secara matematis mengikuti model diatas, maka masalah tersebut dapat dipecahkan dengan teknik LP. Terminologi umum untuk model LP yang diuraikan diatas dapat diringkas sebagai berikut: 1. Fungsi yang akan dimaksimumkan : C1 X 1 + C 2 X 2 + C 3 X 3 + .... + C n X n disebut fungsi tujuan (objective function).
24
2. Fungsi – fungsi batasan dapat dikelompokkan menjadi dua macam, yaitu : 1. Fungsi batasan fungsional, yaitu fungsi – fungsi batasan sebanyak m (yaitu ai1 x1 + ai 2 x 2 + ... + ain x n ). 2. Fungsi batasan non-negatif (non-negatif-constraints) yaitu fungsi – fungsi batasan yang dinyatakan dengan Xi ≥ 0. 3. Variabel – variabel Xj disebut decision variables. 4. aij, bi dan Cj, yaitu masukan – masukan (input) konstan; disebut sebagai parameter model.
Berikut adalah beberapa contoh permasalahan Linear Programming selain maksimasi : 1. Masalah minimasi, dimana seseorang dituntut untuk menentukan kombinasi (output) yang dapat meminimumkan pengorbanan (misalnya : biaya). Dalam hal ini, fungsi tujuan dinyatakan sebagai berikut : Meminimumkan Z = C1X1 + C2X2 + ...... + CnXn 2. Masalah dengan fungsi batasan fungsional yang memiliki tanda matematis ≥; sehingga apabila dirumuskan terlihat sebagai berikut: a i1 x1 + a i 2 x 2 + ... + a in x n ≥ bi 3. Masalah dengan fungsi batasan fungsional yang memiliki tanda matematis =; sehingga bila dirumuskan sebagai berikut: a i1 x1 + a i 2 x 2 + ... + a in x n = bi
25
4. Masalah tertentu, dimana fungsi batasan non – negatif tidak diperlukan; atau dengan kata lain xj tidak terbatas. (Pangestu. 2002, hal 10 – 13)
Berikut adalah beberapa asumsi – asumsi dasar Linear Programming : 1. Proportionality Asumsi ini berarti bahwa naik turunnya nilai Z dan penggunaan sumber atau fasilitas yang tersedia akan berubah secara sebanding (proportional) dengan perubahan tingkat kegiatan. Misal : a) Z = C1 X 1 + C 2 X 2 + ..... + C n X n Setiap pertambahan 1 unit X1 akan menaikkan Z dengan C1, setiap pertambahan 1 unit X2 akan menaikkan nilai Z dengan C2, dan seterusnya. b) a11 X 1 + a12 X 2 + ...... + a n X n ≤ b1 Setiap pertambahan 1 unit X1 akan menaikkan penggunaan sumber atau fasilitas 1 dengan a11, setiap pertambahan 1 unit X2 akan menaikkan penggunaan sumber atau fasilitas 1 dengan a12, dan seterusnya. Dengan kata lain, setiap ada kenaikan kapasitas riil tidak perlu ada biaya persiapan (set up cost).
26
2. Additivity Asumsi ini berarti bahwa nilai tujuan
tiap kegiatan tidak saling
mempengaruhi, atau dalam LP 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. Misal : Z = 3X 1 + 5X 2
Dimana
X 1 = 10; X 2 = 2;
Sehingga
Z = 30 + 10 = 40
Andaikata X1 bertambah 1 unit, maka sesuai dengan asumsi pertama, 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. 3. Divisibility Asumsi ini menyatakan bahwa keluaran (output) yang dihasilkan oleh setiap kegiatan dapat berupa bilangan pecahan. Demikian pula dengan nilai Z yang dihasilkan. Misal : X1 = 6,5; Z = 1000,75.
27
4. Deterministic (Certainly) Asumsi ini menyatakan bahwa semua parameter yang terdapat dalam model LP (aij, bi, Cj) dapat diperkirakan dengan pasti, meskipun jarang dengan tepat. (Pangestu. 2002, hal 13 – 15)
2.2.3
Simpleks Metode Simpleks merupakan metode yang paling berhasil dikembangkan
untuk memecahkan persoalan LP yang mempunyai variabel keputusan dan pembatas yang besar. Algoritma simpleks ini diterangkan dengan menggunakan logika secara aljabar matriks, sedemikian sehingga operasi perhitungan dapat dibuat lebih efisien. Metode simpleks pertama kali diperkenalkan oleh George B. Dantzig pada tahun 1947 dan telah diperbaiki oleh beberapa ahli lain. Metode ini menyelesaikan masalah LP melalui perhitungan ulang (iteration) dimana langkah – langkah perhitungan yang sama diulang berkali – kali sebelum solusi optimum dicapai. (Sri Mulyono, 2002, hal 31) Metode simpleks merupakan suatu metode dalam pemprograman linier yang umum digunakan untuk menentukan hasil yang optimal bagi permasalahan yang memiliki tiga variabel atau lebih. Masalah pemprograman linier yang hanya mengandung dua variabel dapat diselesaikan dengan metode grafik. Tetapi apabila masalah tersebut mengandung lebih dari dua variabel maka metode grafik
28
akan sangat sulit untuk diterapkan sehingga diperlukan penggunaan metode simpleks. (Tjutju Tarliah Dimyati, 2003, hal 53-57). Masalah program linier 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 algoritmayang biasanya sering disebut tabel metode simpleks. Disebut demikian karena kombinasi variabel keputusan yang optimal dicari dengan menggunakan tabel – tabel.
Adapun tahap-tahap yang digunakan dalam penyelesaian arah dengan menggunakan metode simpleks adalah: 1. Penentuan letak bilangan yang paling negatif pada baris terbawah tabel (yakni cj - zj). Jika terdapat lebih dari satu bilangan yang paling negatif, maka pilih salah satu kolom yang ada bilangan ternegatif dan kolom ini disebut kolom kerja. Pembentukan nilai-nilai banding dengan membagi setiap bilangan positif dalam kolom kerja dengan elemen dalam kolom H yang merupakan nilai XB yang baru dengan mengabaikan baris terakhir. Dalam masalah penemuan arah dengan metode simpleks ini, variabel dinotasikan dengan huruf S dan SB menyatakan vektor arah yang akan dicari tersebut.
29
2. Gunakan operasi Baris elementer untuk mengubah elemen pivot menjadi 1 dan reduksi semua elemen lain dalam kolom kerja menjadi 0. 3. Gantikan matriks basis B, misalkan dalam kolom ke-r dan baris pivot dengan Ak yang terdapat dalam kolom pivot. B = (B1, B2, ..., Ak, ..., Bm)T merupakan variabel dasar baru. 4. Ulangi kembali langkah 1 sampai 4 sehingga tidak terdapat lagi elemen yang negatif dalam baris terakhir atau semua cj - zj > 0. 5. Pemecahan optimal diperoleh dengan menetapkan nilai variabel yang bersangkutan pada kolom H yang berasosiasi dengan variabel dalam basis. Variabel yang non basis ditetapkan bernilai nol. Sedangkan nilai optimal fungsi objektif adalah bilangan yang berada pada baris akhir kolom H untuk masalah maksimisasi dan negatif bilangan tersebut jika untuk masalah minimisasi.
