19
BAB 2 LANDASAN TEORI
2.1
Analytical Hierarcy Process (AHP)
2.1.1
Pengantar Analytical Hierarcy Process (AHP) Proses hierarki analitik (Analytical Hierarchy Process – AHP) dikembangkan oleh Dr. Thomas L. Saaty dari Wharton School of Business pada tahun 1970-an untuk mengorganisasikan informasi dan judgement dalam memilih alternatif yang paling disukai (Saaty, 1992). Dengan menggunakan AHP, suatu persoalan akan dipecahkan dalam suatu kerangka berpikir yang terorganisir, sehingga memungkinkan dapat diekspresikan untuk mengambil keputusan yang efektif atau persoalan tersebut. Persoalan yang kompleks dapat disederhanakan dan dipercepat proses pengambilan keputusan (Marimin, 2004, p76-78). Prinsip kerja AHP adalah penyederhanaan suatu persoalan kompleks yang tidak terstruktur, stratejik dan dinamik menjadi bagian – bagiannya, serta menata dalam suatu hierarki. Kemudian tingkat kepentingan setiap variabel diberi nilai numerik secara subjektif tentang arti penting variabel tersebut secara relatif dibandingkan dengan variabel yang lain. Dari berbagai pertimbangan tersebut kemudian dilakukan sintesa untuk menetapkan variabel
20
yang memiliki prioritas tinggi dan berperan untuk mempengaruhi hasil pada sistem tersebut. Secara grafis, persoalan keputusan AHP dapat dikonstrusikan sebagai diagram bertingkat, yang dimulai dengan goal atau sasaran, lalu kriteria level pertama, subkriteria dan akhirnya alternatif. AHP memungkinkan pengguna untuk memberikan nilai bobot relatif dari suatu kriteria majemuk (atau alternatif majemuk terhadap suatu kriteria) secara intuitif, yaitu melakukan perbandingan berpasangan (pairwise comparisons). Dr. Thomas L. Saaty, pembuat AHP, kemudian menentukan cara yang konsisten untuk mengubah perbandingan berpasangan/pairwise, menjadi suatu himpunan bilangan yang merepresentasikan prioritas relatif dari setiap kriteria dan alternatif.
2.1.2
Model Keputusan dengan AHP AHP memiliki banyak keunggulan dalam menjelaskan proses pengambilan keputusan, karena dapat digambarkan secara grafis, sehingga mudah dipahami oleh semua pihak yang terlibat dalam pengambilan keputusan. Dengan AHP, proses keputusan kompleks dapat diuraikan menjadi keputusan-keputusan lebih kecil yang dapat ditangani dengan mudah. Selain itu, AHP juga menguji konsistensi penilaian, bila terjadi penyimpangan yang terlalu jauh dari nilai konsistensi sempurna, maka hal ini
21
menunjukkan bahwa penilaian perlu diperbaiki, atau hierarki harus distruktur ulang. Beberapa keuntungan yang diperoleh bila memecahkan persoalan dan mengambil keputusan dengan menggunakan AHP adalah : Kesatuan : AHP memberikan suatu model tunggal yang mudah dimengerti, luwes untuk aneka ragam persoalan tidak terstruktur. Kompleksitas : AHP memadukan ancangan deduktif dan ancangan berdasarkan sistem dalam memecahkan persoalan kompleks. Saling
ketergantungan
:
AHP
dapat
menangani
saling
ketergantungan elemen – elemen dalam suatus sistem dan tidak memaksakan pemikiran linier. Penyusunan hierarki : AHP mencerminkan kecenderungan alami pikiran untuk memilah – milah elemen – elemen suatu sistem dalam berbagai tingkat berlainan dan mengelompokkan unsur yang serupa dalam setiap tingkat. Pengukuran : AHP memberikan suatu skala untuk mengukur hal – hal dan terwujud suatu metode untuk menetapkan prioritas. Konsistensi : AHP melacak konsistensi logis dari pertimbangan – pertimbangan yang digunakan untuk menetapkan berbagai prioritas. Sintesis : AHP menuntun ke suatu taksiran menyeluruh tentang kebaikan setiap alternatif.
22
Tawar – Menawar : AHP mempertimbangkan prioritas – prioritas relatif dari berbagai faktor sistem dan memungkinkan organisasi memilih alternatif terbaik berdasarkan tujuan – tujuan mereka. Penilaian dan Konsesus : AHP tidak memaksakan konsensus tetapi mensintesiskan suatu hasil yang representatif dari berbagai penilaian yang berbeda. Pengulangan memperhalus
Proses
:
AHP
defenisi
mereka
memungkinkan pada
suatu
organisasi
persoalan
dan
memperbaiki pertimbangan dan pengertian mereka melalui pengulangan
2.1.3
Prinsip Kerja AHP Ide dasar prinsip kerja AHP adalah : Penyusunan Hierarki Persoalan yang akan diselesaikan, diuraikan menjadi unsur – unsurnya, yaitu kriteria dan alternatif, kemudian disusun menjadi struktur hierarki. Diagram
berikut
merepresentasikan
keputusan
untuk
memilih
agroindustri, dengan menggunakan AHP. Adapun kriteria untuk membuat tersebut adalah bahan baku, pemasaran, dan teknologi proses, beserta dengan sub kriteria yang terkait dengan masing – masing kriteria tersebut.
23
Alternatif yang tersedia dalam membuat keputusan terlihat pada level yang paling bawah. Hierarki persoalan ini dapat pada gambar 2.1.
Gambar 2.1 Contoh Struktur Hierarki dalam AHP Penilaian Kriteria dan Alternatif Kriteria dan alternatif dinilai melalui perbandingan berpasangan. Menurut Saaty (1983), untuk berbagai persoalan, skala 1 sampai 9 adalah skala terbaik dalam mengekspresikan pendapat. Nilai dan defenisi pendapat kualitatif dari skala perbandingan Saaty dapat dilihat pada tabel berikut :
Tabel 2.1 Nilai dan Definisi Kualitatif dari Skala Perbandingan Saaty Nilai 1 3 5 7 9 2,4,6,8
Keterangan Kriteria/ alternatif A sama penting dengan kriteria / alternatif B A sedikit lebih penting dari B A jelas lebih penting dari B A sangat jelas lebih penting dari B Mutlak lebih penting dari B Apabila ragu - ragu antara dua nilai yang berdekatan
24
Nilai perbandingan A dengan B adalah 1 (satu) dibagi dengan nilai perbandingan B dengan A. Penentuan Prioritas Untuk setiap kriteria dan alternatif, perlu dilakukan perbandingan berpasangan (pairwise comparisons). Nilai – nilai perbandingan relatif kemudian diolah untuk menentukan peringkat relatif dari seluruh alternatif. Baik kriteria kualitatif, maupun kriteria kuantitatif, dapat dibandingkan sesuai dengan judgement yang telah ditentukan untuk menghasilkan bobot dan prioritas. Bobot atau prioritas dihitung dengan manipulasi matriks atau melalui penyelesaian persamaan matematik. Konsistensi Logis Semua elemen dikelompokkan secara logis dan diperingatkan secara konsisten sesuai dengan suatu kriteria yang logis.
2.1.4
Penggabungan Pendapat Responden Pada dasarnya AHP dapat digunakan untuk mengolah data dari satu responden ahli. Namun demikian dalam aplikasinya penilaian kriteria dan alternative dilakukan oleh beberapa ahli multidiplioner. Konsekuensinya pendapat beberapa ahli tersebut perlu dicek konsistensinya satu persatu. Pendapat yang konsisten kemudian digabungkan dengan menggunakan ratarata geometrik. Berikut rumusan rata-rata geometrik :
25
Aij =
n
Z 1 xZ 2 x...xZ n
Keterangan :
Aij = Nilai rata-rata perbandingan antara kriteria Ai dengan Aj untuk partisipan.
Z i = Nilai perbandingan antara kriteria Ai dengan Aj untuk partisipan ke-i i
= 1, 2, 3, ..., n
n
= Jumlah partisipan. Hasil penilaian gabungan ini yang kemudian diolah dengan prosedur
AHP yang telah diuraikan sebelumnya.
2.2
Diagram Sebab-Akibat (Causes and Effect Diagram)
2.2.1
Definisi dan Tujuan Diagram Sebab-Akibat Definisi diagram sebab-akibat (Gaspersz, 1998, p61) adalah suatu diagram yang menunjukkan hubungan antara sebab dan akibat. Berkaitan dengan pengendalian proses stastistikal, diagram sebab-akibat dipergunakan untuk menunjukkan faktor-faktor penyebab (sebab) dan karakteristik kualitas (akibat). Diagram sebab-akibat ini sering disebut sebagai diagram tulang ikan juga (fishbone diagram) karena bentuknya seperti kerangka ikan, atau diagram ishikawa (ishikawa’s diagram) karena pertama kali diperkenalkan oleh Prof. Kaouru Ishikawa dari Universitas Tokyo pada tahun 1953.
26
Pada dasarnya diagram sebab-akibat dapat dipergunakan untuk kebutuhan-kebutuhan sebagai berikut : Membantu mengidentifikasi akar penyebab dari suatu masalah. Membantu membangkitkan ide-ide untuk solusi dari suatu masalah. Membantu dalam penyelidikan atau pencarian fakta yang lebih lanjut.
2.2.2 Langkah-langkah Membuat Diagram Sebab-Akibat Langkah-langkah dalam penbuatan diagram sebab-akibat dapat dikemukakan sebagai berikut : Mulai dengan pernyataan masalah-masalah utama yang penting dan mendesak untuk diselesaikan. Tuliskan pernyataan masalah itu pada “kepala ikan” , yang merupakan akibat (effect). Tuliskan pada sisi sebelah kanan dari kertas (kepala ikan), kemudian gambarkan “tulang belakang” dari kiri ke kanan dan tempatkan pernyataan masalah itu dalam kotak. Tuliskan faktor-faktor penyebab utama (sebab-sebab) yang mempengaruhi masalah kualitas sebagai “tulang besar”, juga ditempatkan dalam kotak . Faktor –faktor penyebab atau kategorikategori-kategori utama dapat dikembangkan melalui stratifikasi ke dalam pengelompokan dari faktor-faktor : manusia, mesin peralatan, material, metode kerja, lingkungan kerja, pengukuran,
27
dan lain-lain, atau stratifikasi melalui langkah-langkah aktual dalam proses. Faktor–faktor penyebab atau kategori-kategori dapat dikembangkan melalui brainstorming. Tuliskan penyebab-penyebab sekunder yang mempengaruhi penyebab-penyebab utama (tulang-tulang besar), serta penyebabpenyebab
sekunder
itu
dinyatakan
sebagai
“tulang-tulang
berukuran sedang”. Tuliskan penyebab-penyebab sekunder yang mempengaruhi penyebab-penyebab utama (tulang-tulang besar), serta penyebabpenyebab
sekunder
itu
dinyatakan
sebagai
“tulang-tulang
yang
mempengaruhi
berukuran sedang”. Tuliskan
penyebab-penyebab
tersier
penyebab-penyebab sekunder (tulang-tulang berukuran sedang), serta penyebab-penyebab tersier dinyatakan sebagai “tulang-tulang berukuran kecil”. Tentukan item-item yang penting dari setiap faktor dan tandailah faktor-faktor penting tertentu yang kelihatannya memiliki penarug nyata terhadap karakteristik kualitas. Catatlah informasi yang perlu didalam diagram sebab-akibat itu, seperti : judul, nama produk, proses, kelompok, partisipan, tanggal, dan lain-lain.
28
2.3
Metode Transportasi
2.3.1
Definisi dan Aplikasi Metode Transportasi Dalam bagian ini, menyajikan definisi dari model transportasi. Kami lalu menjabarkan beberapa variasi dari model ini yang memperluas ruang lingkup aplikasinya ke berbagai masalah yang lebih luas di dunia nyata. (Taha, 1996, p203-204). Dalam arti sederhana, model transportasi berusaha menentukan sebuah rencana transportasi sebuah barang dari sejumlah sumber ke sejumlah tujuan. Data dalam model ini mencakup : Tingkat penawaran di setiap sumber dan jumlah permintaan di setiap tujuan. Biaya transportasi per unit barang dari setiap sumber ke setiap tujuan. Karena hanya terdapat satu barang, sebuah tujuan dapat menerima permintaannya dari satu sumber atau lebih. Tujuan dari model ini adalah menentukan jumlah yang harus dikirimkan dari setiap sumber ke setiap sumber ke setiap tujuan sedemikian rupa sehingga biaya transportasi total diminimumkan. Asumsi dasar dari model ini adalah bahwa biaya transportasi
di
sebuah rute tertentu adalah proposional secara langsung dengan jumlah unit yang dikirimkan. Definisi “unit transportasi” akan bervariasi bergantung pada jenis “barang” yang dikirimkan. Misalnya. Kita dapat membicarakan unit
29
transportasi sebagai setiap balok baja yang diperlukan untuk membangun jembatan. Atau dapat menggunakan beban truk dari sebuah barang sebagai unit transportasi. Bagaimanapun juga, unit penawaran dan permintaan harus konsisten dengan definisi tentang “unit yang dikirimkan”. Gambar
memperlihatkan sebuah model transportasi dari sebuah
jaringan dengan m sumber dan n tujuan. Sebuah sumber atau tujuan diwakili dengan sebuah node. Busur yang menghubungkan sebuah sumber dan sebuah tujuan mewakili rute pengiriman barang tersebut. Jumlah penawaan di sumber
i adalah ai dan permintaan di tujuan j adalah bj. Biaya unit transportasi antara sumber i adalah cij. Anggaplah Xij mewakili jumlah barang yang dikirimkan dari sumber i ke tujuan j; maka model LP yang mewakili masalah transportasi ini diketahui secara umum sebagai : Sumber
Tujuan
1
1
2
2
n
m
Gambar 2.2 Model LP yang mewakili masalah Transportasi Minimumkan z =
m
n
i =1
j=1
∑ ∑c
ij
x ij
30
Dengan batasan n
∑x j=1
ij
≤ ai ,
i=1, 2,…., m
ij
≤ b j,
j= 1, 2,…., n
m
∑x i =1
x ij ≥ 0,
untuk semua i dan j
Kelompok batasan pertama menetapkan bahwa jumlah pengiriman dari sebuah sumber tidak dapat melebihi penawarannya; demikian pula, kelompok batasan kedua mengharuskan bahwa jumlah pengiriman kesebuah tujuan harus memenuhi permintaannya. Model baru digambarkan diatas menyiratkan bahwa penawaran total n
m
∑a i =1
i
j=1
m
penawaran total sama dengan permintaan total ( ∑ a i = i =1
yang
∑b
harus setidaknya sama dengan permintaan total
dihasilkan
disebut
model
transportasi
j
. Ketika
n
∑b
j
), formulasi
berimbang
(balanced
j=1
transportation model). Model ini berbeda dengan model diatas hanya dalam fakta bahwa semua batasan adalah persamaan, yaitu: n
∑x j=1
ij
= ai ,
i=1, 2,…., m
ij
= bj,
j= 1, 2,…., n
m
∑x i =1
31
Dalam kehidupan nyata, tidak selalu dapat dipastikan bahwa penawaran sama dengan permintaan atau melebihinya. Tetapi, sebuah model transportasi
dapat
selalu
berimbang.
Pengimbangan
ini,
disamping
kegunaannya dalam permodelan situasi praktis tertentu, adalah penting untuk pengembangan sebuah metode pemecahan yang sepenuhnya memanfaatkan struktur khusus dari model transportasi ini.
2.3.2
Model Transportasi Berimbang Berikut ini adalah contoh mengenai model transportasi berimbang. MG Auto company memiliki pabrik di Los Angeles, Detroit, dan New Orleans. Pusat distribusinya terletak di Denver dan Miami. Kapasitas ketiga pabrik tersebut selama sekwartal adalah
1000, 1300, dan 1200 mobil.
Permintaan kwartalan di kedua pusat distribusi itu adalah 2300 dan 1400 mobil. Biaya transportasi darat per mobil per mil adalah sekitar 8 sen. Bagan jarak antara pabrik dan pusat distribusi tersebut adalah sebagai berikut : (Taha, 1996, p206-207).
Tabel 2.2 Bagan Jarak Antara Pabrik dan Pusat Distribusi
Los Angeles Detroit New Orleans
Denver Miami 1000 2690 1250 1350 1275 850
32
Bagan jarak diatas dapat diterjemahkan menjadi biaya per mobil dengan tarif 8 sen per mil. Ini menghasilkan biaya berikut ini (yang dibulatkan ke dollar terdekat). Yang mewakili cij dalam model umum:
Tabel 2.3 Cij dalam Model Umum
Los Angeles Detroit New Orleans
Denver (1) (1) 1000 (2) 1250 (3) 1275
Miami (2) 2690 1350 850
Situasi ini dikatakan tidak berimbang karena penawaran total (=3500) tidak sama dengan permintaan total (=3700). Dengan kata kata lain situasi yang tidak berimbang ini berarti bahwa tidak semua permintaan di pusat distribusi dapat dipenuhi. Tujuan kita adalah merumuskan ulang model transportasi ini dengan cara yang mendistribusikan kekurangan jumlah (=3700-3500=200 mobil) secara optimal diantara pusat – pusat distribusi. Karena permintaan lebih besar dari penawaran, sebuah sumber buatan atau dummy (pabrik) dapat ditambahkan dengan kapasitas sama dengan 200 mobil. Pabrik dummy tersebut diijinkan,
33
Tabel 2.4 Contoh Sumber Dummy
Los Angeles Detroit New Orleans Pabrik Dummy
Los Angeles Detroit New Orleans
Denver 80 100 102 0 2300
Denver 80 100 102 1900
Miami 215 108 68 0 1400
Miami 215 108 68 1400
100 1300 1200 200 Pusat Distribusi Dummy 0 0 0 400
1000 1500 1200
Dalam kondisi normal, untuk mengirimkan “produksinya” kesemua pusat distribusi. Secara fisik, jumlah yang dikirimkan ke tujuan dari sebuah pabrik dummy akan mewakili jumlah kekurangan di tempat tujuan itu. Satu – satunya informasi yang belum dapat untuk penyelesaian model ini adalah biaya unit “transportasi” dari sebuah pabrik dummy ke tujuan. Karena pabrik tersebut sebenarnya tidak ada, pengiriman fisik tidak terjadi dan biaya unit transportasinya adalah nol. Tetapi, dapat melihat situasi ini dengan cara yang berbeda dengan mengatakan bahwa biaya penalti yang dibayarkan untuk setiap unit permintaan yang tidak dipenuhi di pusat – pusat distribusi. Dalam kasus ini, biaya transportasi tersebut akan sama dengan biaya penalti per unit di berbagai tujuan. Tabel 2.2 meringkaskan model berimbang dengan batasan kapasitas yang baru ini dipabrik bahkan tujuan buatan atau tujuan dummy yang akan
34
menyerap selisih itu. Misalnya, anggaplah bahwa permintaan di Denver merosot menjadi 190 mobil. Tabel 2.4 meringkaskan model dengan pusat distribusi dummy ini. Setiap mobil yang dikirimkan dari sebuah pabrik ke sebuah pusat distribusi dummy mewakili jumlah surplus di pabrik itu. Biaya unit transportasi yang berkaitan dengannya adalah nol. Tetapi, dapat mengenakan biaya penyimpanan untuk penahanan mobil tersebut di pabrik, dimana biaya unit transportasi tersebut akan sama dengan biaya unit penyimpanan.
2.3.3
Teknik Transportasi Langkah – langkah dasar dari teknik transportasi adalah (Taha, 1996, p212-213) : 1. Tentukan pemecahan awal yang layak. 2. Tentukan variabel masuk dari diantara variabel nondasar. Jika semua variabel masuk memenuhi kondisi optimalitas (dari metode simpleks), berhenti; jika tidak, lanjutkan ke langkah ke 3. 3. Tentukan
variabel
keluar
(dengan
menggunakan
kondisi
kelayakan) dari diantara variabel – variabel dalam pemecahan dasar saat ini; lalu temukan pemecahan dasar baru. Kembali ke langkah 2.
35
Langkah – langkah ini akan mempertimbangkan secara terinci. Alat penjelasannya adalah masalah dalam Tabel 2.5. Biaya unit transportasi cij adalah dalam dollar. Penawaran dan permintaan diketahui dalam jumlah unit.
Tabel 2.5 Langkah – langkah Dasar dari Teknik Transportasi Tujuan 2
1 10 Sumber
1
x11
0
x12 12
2
x21
Permintaan
2.3.4
x13
x22
x31 5
Penawaran 11
x14 9
x23 14
x32 15
4 20
7
0 3
3
15 20
x24 16
x33 15
25 18
x34 10
Pemecahan Masalah Transportasi Penentuan Pemecahan Awal Definisi umum dari model transportasi dalam 2.3 mengharuskan m
bahwa
∑ai = i =1
n
∑b j=1
j
. Pesyaratan ini menghasilkan satu persamaan dependen,
yang berarti model tersebut hanya memiliki M + n-1 persamaan independen. Jadi, seperti dalam metode simpleks, pemecahan dasar yang layak harus mencakup m + n -1 variabel dasar. (Taha, 1996, p212-218). Biasanya, jika model transportasi dirumuskan sebagai sebuah tabel simpleks, kita perlu memanfaatkan variabel buatan untuk memperoleh
5
36
pemecahan dasar awal. Tetapi, ketika tabel transportasi dipergunakan, pemecahan dasar awal yang layak dapat diperoleh secara mudah dan langsung. Kami menyajikan prosedur yang disebut peraturan sudut barat laut (northwest-corner rule) untuk maksud ini. Dua prosedur lainnya, yang disebut metode biaya terendah (least-cost) dan pendekatan Vogel. Prosedur ini biasanya memberikan pemecahan awal yang lebih baik dalam arti bahwa nilai fungsi tujuan yang bersangkutan adalah lebih kecil.
Metode sudut barat laut memulai dengan mengalokasikan jumlah maksimum yang dapat diijinkan oleh penawaran dan permintaan ke variabel
x11 (variabel yang berada disudut barat laut dari tabel). Kolom (baris) yang sudah dipenuhi lalu disilang, yang menunjukkan bahwa variabel sisanya dalam kolom (baris) yang disilang tersebut adalah sama dengan nol. Jika sebuah kolom dan sebuah baris dipenuhi secara bersamaan, hanya satu (salah satunya) yang disilang. Kondisi ini menjamin penentuan variabel dasar nol, jika ada, secara otomatis.
Tabel 2.6 Metode sudut barat laut
1 2 3
1 5
5
2 3 10 5 15
4
5 5 15 15 10
15 25 5
37
Setelah menyesuaikan jumlah penawaran dan permintaan untuk semua baris dan kolom yang belum disilang, jumlah maksimum yang layak dialokasikan ke elemen pertama yang belum di silang di kolom (baris) yang baru. Proses ini diselesaikan ketika tepat satu baris atau satu kolom belum disilang. Prosedur yang harus dijabarkan diatas sekarang diterapkan untuk contoh dalam tabel 2.5 1. x11 = 5, yang menyilang kolom 1. Jadi tidak ada alokasi lebih lanjut dapat dibuat dalam kolom 1. Jumlah yang tersisa dalam baris 1 adalah 10 unit. 2. x12 = 10, yang menyilang baris 1. Dan meninggalkan 5 unit dalam kolom 2. 3. x22 = 5, yang menyilang kolom 2. Dan meninggalkan 20 unit di baris 2. 4. x23 = 15, yang menyilang kolom 3. Dan meninggalkan 5 unit di baris 2. 5. x24 = 5, yang menyilang baris 2. Dan meninggalkan 5 unit di kolom 4. 6. x34 = 5, yang menyilang baris 2 atau kolom 4. Karena hanya ada satu baris ata satu kolom yang tetap belum disilang, proses ini berakhir.
38
Pemecahan dasar awal yang dihasilkan diberikan dalam Tabel 2.6. Variabel dasar adalah x11 = 5, x12 = 10, x22 = 5, x23 = 15, x24 = 5, x34 = 5. Variabel sisanya adalah nondasar ditingkat nol. Biaya transportasi yang bersangkutan dengnnya adalah 5 X 10 + 10 X 0 + 5 X 7 + 15 X 9 + 5 X 20 + 5 X 18 = $ 410 Ketika baik sebuah kolom maupun baris terpenuhi secara bersamaan, variabel berikutnya yang harus ditambahkan ke pemecahan dasar akan dipastikan berada di tingkat nol. Tabel 2.7 mengilustrasikan hal ini ketika kolom 2 dan baris 2 dipenuhi secara bersamaan. Jika kolom 2 disilang, x23 menjadi dasar di tingkat nol dalam langkah berikutnya, karena penawaran sisanya untuk baris 2 adalah sekarang nol. (kasus ini diperlihatkan dalam tabel 2.7), jika baris 2 disilang, x32 akan menjadi varibel dasar nol.
Tabel 2.7 Kolom 2 dan Baris 2 Dipenuhi Secara Bersamaan 1 2 3
1 5
5
2 5 5 10 5
3 0 8 8
4
7 7
10 5 15
5 0
39
Penentuan Variabel Masuk (Metode Pengali) Variabel masuk ditentukan dengan menggunakan kondisi optimalitas dari metode simpleks. Seperti diterangkan lebih lanjut dalam bagian ini, perhitungan koefisien persamaan tujuan didasari oleh hubungan primal - dual. Pertama – tama akan disajikan mekanika metode ini dan lalu menyediakan penjelasan yang terinci tentang prosedur yang didasari oleh teori dualitas. Metode lainnya, yang disebut prosedur batu loncatan (stepping-stone
procedure), juga tersedia untuk menentukan variabel masuk. Walaupun perhitungan dalam kedua metode ini tepat setara, metode batu loncatan memberikan kesan bahwa prosedur ini sepenuhnya tidak berkaitan dengan metode simpleks. Dalam metode pengali kita mengaitkan penggali ui dan vj dengan baris
i dan kolom j dari tabel transportasi. Untuk setiap variabel dasar xij dalam pemecahan saat ini, pengali ui dan vj harus memenuhi persamaan berikut ini:
ui + vj = cij, untuk setiap variabel dasar xij Persamaan ini menghasilkan m + n -1 persamaan (karena hanya terdapat m + n -1 variabel dasar) dengan m + n pengali yang tidak diketahui. Nilai – nilai pengali dapat ditentukan dari persamaan ini dengan memberikan nilai sembarang pada salah satu pengali (biasanya u1 ditetapkan sama dengan nol) dan lalu memecahkan m + n -1 persamaan dengan m + n -1 pengali yang tidak diketahui. Setelah hal ini dilakukan, evaluasi terhadap setiap variabel nondasar xpq diketahui.
40
c pq = u p + v q − c pq , untuk setiap variabel nondasar xpq (Nilai – nilai ini akan sama tanpa bergantung pada pilihan sembarang nilai u1). Variabel dengan c pq yang paling positif lalu dipilih sebagai variabel masuk (dibandingkan dengan kondisi optimalitas minimisasi dari metode simpleks). Jika menerapkan prosedur ini pada variabel – variabel non dasar dalam Tabel 2.6 (pemecahan saat ini), persamaan yang berkaitan dengan variabel dasar diketahui :
x11 : u1 + v1 = c11 = 10 x12 : u1 + v2 = c12 = 0 x22 : u2 + v2 = c22 = 7 x23 : u2 + v3 = c23 = 9 x24 : u2 + v4 = c24 = 20 x34 : u3 + v4 = c34 = 18
Dengan membiarkan u1 = 0, nilai pengali secara berturut – turut ditentukan sebagai v1 = 10, v2 =0, u2 = 7, v3 =2, v4 = 13, dan u3 = 5. Jadi, evaluasi variabel nondasar diketahui sebagai berikut :
x13 : c13 = u1 + v3 - c13 = 0 + 2 – 20
= -18
x14 : c14 = u1 + v4 - c14 = 0 + 13 – 11
=2
x21 : c 21 = u2 + v1 – c21 = 7 + 10 – 12
=5
x31 : c 31 = u3 + v1 – c31 = 5 + 10 – 0
= 15
41
x32 : c 32 = u3 + v2 – c32 = 5 + 0 – 14
= -9
x33 : c 33 = u3 + v3 – c33 = 5 + 2 – 16
= -9
Karena x31 memiliki c pq yang paling positif, variabel ini dipilih sebagai variabel masuk. Persamaan ui + vj = cij, yang kita pergunakan untuk menentukan pengali, memiliki struktur yang begitu sederhana sehingga sebenarnya kita tidak perlu menuliskannya secara eksplisit. Biasanya jauh lebih sederhana untuk menentukan pengali secara langsung dari table transportasi dengan mencatat ui dari baris i dan vj dari kolom j sama dengan cij ketika baris i dan kolom j berpotongan disebuah sel yang memuat variabel dasar xij. Setelah ui dan vj ditentukan, dapat menghitung c pq untuk semua xpq nondasar dengan menambahkan up dari baris p dan vq dari kolom q dan lalu mengurangkan cpq dalam sel titik potong baris p dan kolom q.
Penentuan Variabel Keluar (Konstruksi Loop) Langkah ini setara dengan penerapan kondisi kelaykan dalam metode simpleks. Tetapi, karena semua koefisien batasan dalam model transportasi semula adalah nol atau 1, rasio (positif) dari kondisi kelayakan akan selalu memiliki penyebut yang sama dengan 1. Jadi nilai variabel dasar akan secara langsung memberikan rasio yang bersangkutan.
42
Untuk maksud penentuan rasio minimum, kiya mengembangkan loop
tertutup untuk variabel masuk saat ini (x31 dalam iterasi saat ini). Loop berawal dan berakhir di variabel nondasar yang ditunjukkan. Loop ini terdiri dari segmen horizontal dan vertical (yang tersambung) yang ujung – ujungnya haruslah variabel dasar, kecuali untuk titik – titik akhir yang berkaitan dengan bvariabel masuk. Ini berarti bahwa setiap elemen susut dari loop ini haruslah sebuah sel yang memuat variabel dasar. Tabel 2.8 mengilustrasikan sebuah untuk varibel masuk x31 dengan diketahui pemecahan dalam tabel -6. Loop ini dapat didefinisikan dalam bentuk variabel dasar sebagai x31 Æ x11 Æ x12 Æ
x22 Æ x24 Æ x34 Æ x31.
Tidak menjadi masalah apakah loop tersebut
ditelusuri searah atau berlawanan arah dengan jarum jam. Amati bahwa untuk satu pemecahan dasar tertentu, hanya satu loop yang unik yang dapat dikembangkan untuk setiap variabel nondasar. Dapat dilihat dari Tabel 2.8 bahwa jika x31 (variabel masuk) dinaikan dengan satu unit maka, unit mempertahankan kelayakan dari pemecahan, variabel dasar sudut dari loop x31 harus disesuaikan sebagai berikut. Turunkan
x11 dengan satu unit, naikkan x12 dengan satu unit, turunkan x22 dengan satu unit, naikkan x24 dengan satu unit, dan akhirnya turunkan x34 dengan satu unit. Proses ini diringkaskan dengan tanda plus + dan minus – di sudut – sudut yang sesuai dalam Tabel 2.8. Perubahan ini akan mempertahankan batasan penawaran dan perminyaan tetap dipenuhi.
43
Variabel keluar dipilih dari diantara variabel – variabel sudut dari loop ini yang akan menurun ketika variabel masuk x31 meningkat melewati tingkat nol. Ini ditunjukkan dalam Tabel 2.8 dengan variabel dalam kotak – kotak yang diberi label dengan tanda minus. Dari Tabel 2.8, x11, x22, dan x34 adalah variabel dasar yang akan menurun ketika x31 meningkat. Variabel yang memiliki nilai terkecil lalu dipikih sebagai variabel keluar , karena variabel itu akana menjadi variabel pertama yang mencapai nilai nol dan setiap penurunan lebih lanjut akan menyebabkan nilainya menjadi negatif (bandingkan kondisi kelayakan dari metode simpleks dimana variabel keluar dikaitkan dengan rasio minimum). Dalam contoh ini tiga variabel -, x11, x22, dan x34 nilai yang sama (=5), dimana salah satu dari ketiganya dapat dipilih sebagai variabel keluar. Anggaplah x34 bahwa diambil sebagi variabel keluar, lalu nilai x31 dinaikkan menjadi 5 dan nilai variabel sudut (dasar) disesuaikan (yaitu, masing – masing dinaikkan atau diturunkan dengan 5, bergantung pada apakah variabel itu memiliki tanda + atau – yang berkaitan dengannya).
44
Tabel 2.8 Tabel Penentuan Variabel Keluar (Konstruksi Loop) 1
2 10
1
5
0
4 20
11
10 12
15 + 7
5
2
9 15
14
0 3
3
20 5 + 18
16
x31
5 +
5
2.3.5
25 5
15
15
10
Pemecahan Awal yang Diperbaiki Metode Biaya Terendah Prosedurnya adalah sebagai berikut yaitu dengan memberikan nilai setinggi mungkin pada variabel dengan biaya unit terkecil dalam keseluruhan tabel. (beberapa biaya unit yang sama dipilih secara sembarang). Silang baris atau kolom yang dipenuhi. (Seperti dalam metode sudut barat laut, jika baik kolom maupun baris dipenuhi secara berbarengan, hanya satu yang disilang). Setelah menyesuaikan penawaran dan permintaan untuk semua baris dan kolom yang belum disilang. Ulangi proses dengan memberikan nilai setinggi mungkin pada variabel dengan biaya unit terkecil yang belum disilang. Prosedur ini diselesaikan ketika tepat satu baris atau satu kolom belum disilang. (Taha, 1996, p222-225).
45
Model transportasi dalam tabel 2.5 sekali lagi dipergunakan untuk mengilustrasikan penerapan metode biaya terkecil. Tabel 2.9 memberikan pemecahan awal yang dihasilkan, langkah – langkah pemecahan adalah sebagai berikut : x12 dan x31 adalah sebagai variabel – variabel yang berkaitan dengan biaya unit terkecil (c12 = c31 = 0). Dengan memilih secara sembarang, pilihlah x12, unit penawaran dan permintaan yang bersangkutan memberikan
x12 = 15, yang memenuhi baik baris 1 maupun kolom 2. Dengan menyilang kolom 2, penawaran yang tersisa dibaris 1 adalah nol. Kemudian x31 memiliki biaya unit terkecil yang belum disilang. Jadi
x31 = 5 memenuhi baik baris 3 maupun kolom 1. Dengan menyilang baris 3, permintaan dalam kolom 1 adalah nol. Elemen berbiaya terkecil yang belum disilang adalah c23 = 9. Unit penawaran dan permintaan memberikan x23 = 15, yang menyilang kolom 3 dan menyisakan 10 unit penawaran dalam baris 2. Elemen berbiaya terkecil yang belum disilang adalah c11 = 10. Karena penawaran yang tersisa dibaris 1 dan permintaan yang tersisa di kolom 1 keduanya nol, x11 = 0. Dengan menyilang kolom 1, penawaran yang “tersisa” dibaris 1 adalah nol. Variabel dasar sisanya diperoleh secara berturut – turur sebagai x14 = 0 x24 = 10. Lalu biaya total yang berkaitan dengan pemecahan ini adalah 0 X 10 + 15 X 0 + 0X 11 + 15 X 9 + 10 X 20 + 5 X 0 = $ 335, yang adalah lebih baik (lebih rendah) daripada yang diperoleh dengan metode sudut barat laut.
46
1
1
0
Tabel 2.9 Metode Biaya Terendah 2 3 1 2 0 0 0 15 1 2
7
2
3
1 1 15 2 0
9 15
1 4
0
4
10 1 6
1 8
5 5
25
5 15
15
10
Metode Pendekatan Vogel (VAM) Metode ini merupakan sebuah heuristik dan biasanya memberikan pemecahan awal yang lebih baik daripada metode barat laut atau metode biaya terendah. Pada kenyataannya, VAM umumnya menghasilkan pemecahan awal yang optimum, atau dekat dengan optimum. Langkah – langkah dari prosedur ini adalah sebagai berikut : 1. Evaluasi penalti untuk setiap baris (kolom) dengan mengurangkan elemen biaya terkecil dalam baris (kolom) dari elemen biaya
terkecil berikutnya dalam baris (kolom yang sama). 2. Identifikasi baris atau kolom dengan penalty terbesar, pilih nilai yang sama secara sembarang. Alokasikan sebanyak mungkin pada variabel dengan biaya terendah dalam baris atau kolom yang
47
dipilih. Sesuaikan penawaran dan permintaan dan silang baris atau kolom yang dipenuhi. Jika baris atau kolom dipenuhi secara bersamaan, hanya satu diantaranya yang disilang dan baris (kolom) sisanya diberikan penawaran (permintaan) nol. Setiap baris atau
kolom dengan penawaran atau permintaan nol tidak boleh dipergunakan dalam menghitung penuh berikutnya (dalam langkah 3). 3. (a) Jika tepat satu baris atau satu kolom yang belum disilang, berhentilah (b) Jika hanya satu baris (kolom) dengan penawaran (permintaan)
positif yang belum disilang tentukan variabel dasar dalam baris (kolom) tersebut dengan metode biaya terendah. (c) Jika semua baris dan kolom yang belum disilang memiliki (diberi) penawaran dan permintaan nol, tentukan variabel dasar nol berdasarkan metode biaya terendah. Berhentilah. (d) Jika tidak, hitung ulang penalti untuk baris dan kolom yang belum disilang, lalu kembali ke langkah 2. (perhatikan bahwa baris dan kolom dengan penawaran dan permintaan yang diberi nilai nol tidak boleh dipergunakan dalam menghitung penalti ini).
48
Tabel 2.10 Metode Pendekatan Vogel (VAM)
1
2 10
3 0
Penalti Baris
4 20
11
1 12
7
9
3
Penalti Kolom
14
10
25
2
5
14
20
2 0
15
16
18
5 5
15
15
10
10
7
7
7
Kita akan menerapkan VAM untuk masalah dalam Tabel 2.5. Tabel 2.10 memperlihatkan kelompok penalti baris dan kolom yang pertama. Karena baris 3 memiliki penalti terbesar (=14) dan karena c31 = 0 adalah biaya unit terendah dalam baris yang sama, jumlah 5 diberikan para x31. Baris 3 dan kolom 1 dipenuhi secara bersamaan. Asumsikan bahwa kolom 1 disilang. Penawaran yang tersisa untuk baris 3 adalah nol. Tabel 2.11 memperlihatkan sekelompok penalti baru setelah menyilang baris 1 dalam Tabel 2.10. (perhatikan bahwa baris 3 dengan penawaran nol tidak dipergunakan dalam menghitung penalti ini). Baris 1 dan kolom 3 memiliki penalti yang sama. Dengan memilih kolom 3 secara
49
sembarang, jumlah 12 diberikan pada x23, yang menyilang kolom 3 dan menyesuaikan penawaran dalam baris 2 menjadi 10. Penerapan VAM yang berikutnya menghasilkan x22 = 10 (menyilang baris 2). x12 = 5 (menyilang kolom 2 ), x14 = 10 (menyilang baris 1), dan x34 = 0.biaya program ini adalah $315, yang kebetulan merupakan pemecahan optimal. Versi VAM ini memilih dua penalti yang sama besar secara sembarang. Tetapi pemilihan ini penting dalam menghasilkan pemecahan awal yang baik. Contohnya. Dalam Tabel 2.11, jika baris 1 yang dipilih dan bukan kolom 3, pemecahan awal yang lebih buruk dihasilkan. (periksalah bahwa pemecahan ini adalah x12 = 15, x23 = 15, x24 = 10, x31 = 5, yang akan menghasilkan biaya total sebesar $335). Prosedur VAM yang lengkap memberikan perincian tentang cara – cara memilih penalti yang sama ini secara menguntungkan.
50
Tabel 2.11 Prosedur VAM
1
2 10
3 0
Penalti Baris
4 20
11
1 12
7
9
20
2 0 3
Penalti Kolom
11
15
14
16
25
10
2
5
0
-
18
5 5
15
15
10
-
7
11
9
