1

BAB I

PENDAHULUAN

1.1 Latar Belakang Masalah

Banyak hal dalam kehidupan sehari-hari yang tidak dapat diprediksi dengan

pasti, ada kalanya segala sesuatu berjalan sesuai dengan apa yang diharapkan atau

dapat pula sebaliknya. Misalnya saja dalam pembuatan sebuah film, seharusnya

film tersebut dapat diselesaikan dalam kurun waktu 4 bulan namun dikarenakan

terjadi kendala dalam proses pembuatannya maka film tersebut selesai dalam

waktu 6 bulan. Permasalahan tersebut hanya satu dari sekian banyak kejadian

dalam kehidupan nyata yang tidak dapat diprediksi dengan pasti atau dapat

dikatakan dengan adanya suatu ketidakpastian. Ketidakpastian ini terkadang

memberikan dampak yang positif/keuntungan atau dapat pula sebaliknya yaitu

memberikan kerugian atau dampak negatif. Dampak yang ditimbulkan tergantung

dari seberapa besar pengaruh dampak tersebut dari adanya ketidakpastian.

Masalah transportasi adalah salah satu masalah yang berkaitan dengan

adanya ketidakpastian, contoh secara nyata adalah waktu tempuh suatu

pengiriman barang dari sumber ke tujuan akan berada pada suatu selang waktu

tertentu karena dalam proses perjalanan yang dilakukan akan dihadapkan oleh

kendala yang ada. Oleh karenanya masalah transportasi merupakan masalah yang

menarik untuk dikaji lebih lanjut dalam kaitannya dengan ketidakpastian tersebut,

karena dalam kenyataannya terdapat kendala yang mempengaruhi setiap proses

transportasi sehingga untuk setiap masalah yang sama akan diperoleh hasil yang

berbeda tergantung proses dan cara untuk menyelesaikannya.

Menggunakan prinsip ketidakpastian tersebut, memacu penulis untuk

menyelidiki suatu keadaan di mana fungsi parameter seperti waktu, biaya ataupun

jarak berada dalam suatu selang tertentu, dengan mengasumsikan bahwa dalam

selang tertentu tersebut akan dipenuhi suatu keadaan yang optimal.

2

Kata optimal sendiri mempunyai arti bahwa dengan kendala tertentu dari

suatu permasalahan dapat memberikan keuntungan atau mempunyai kerugian

yang sedikit. Berdasarkan prinsip tersebut, misalkan dalam bidang transportasi

terdapat suatu jaringan dengan sumber dan tujuan. Kemudian diketahui

jumlah penawaran barang di sumber adalah sebanyak dan banyaknya

permintaan di tujuan adalah sebanyak , jumlah barang yang dikirim dari

sumber ke tujuan adalah sebanyak dan biaya yang dibutuhkan untuk

mengirim barang dari sumber ke tujuan adalah sebanyak . Diperoleh suatu

model optimasi yang mewakili masalah transportasi tersebut adalah:

Minimum ∑ ∑

dengan kendala, ∑ , ∑ untuk semua dan

Model optimisasi tersebut bertujuan untuk meminimalkan fungsi tujuan/fungsi

objektif.

Mengacu pada suatu keadaan ketidakpastian, memunculkan pemikiran jika

fungsi tujuannya akan berada dalam suatu selang tertentu dengan mengasumsikan

bahwa dalam selang tersebut dapat ditemukan suatu keadaan optimal.

Pembahasan skripsi ini adalah tentang suatu teknik pengambilan keputusan

kriteria minmax regret dalam masalah optimasi diskrit dengan data interval, yaitu

suatu permasalahan optimasi dengan datanya berupa interval-interval dan dalam

contohnya akan dibahas dalam model jaringan Pohon Pembangun Minimum

(Minimum Spanning Tree) dan model transportasi khusus yaitu masalah

Penugasan (Assignment) dan Rute Terpendek (Shortest Rute). Minmax regret

sendiri adalah suatu teknik pengambilan keputusan yang meminimalkan maksimal

regret. Kaitannya dengan masalah optimasi diskrit dengan data interval adalah

dimana dalam data interval tersebut akan memunculkan skenario (scenario) yang

3

mungkin terjadi, yaitu suatu realisasi tertentu yang mungkin terjadi dari

permasalahan yang dibahas. Untuk tiap-tiap skenario-skenario tersebut akan

menghasilkan suatu solusi yang sama ataupun berbeda-beda, dengan

menggunakan kriteria minmax regret tersebut akan memunculkan suatu skenario

terburuk (worst case scenario) dan dengan skenario terburuk tersebut yang

nantinya digunakan untuk mencari maksimal regret.

1.2 Perumusan Masalah

Seperti yang telah dijelaskan dalam latar belakang, rumusan masalah yang

akan dipelajari dalam penulisan skripsi ini adalah sebagai berikut:

Mempelajari contoh permasalahan dalam Pohon Pembangun Minimum,

Masalah Penugasan dan Rute Terpendek dengan data tunggal.

Mempelajari cara menyelesaikan permasalahan Rute Terpendek, Pohon

Pembangun Minimum dan Masalah Penugasan dengan data tunggal.

Mempelajari permasalahan Rute Terpendek, Pohon Pembangun Minimum

dan Masalah Penugasan dengan data interval.

Mempelajari skenario yang mungkin terjadi dalam permasalahan Rute

Terpendek, Pohon Pembangun Minimum dan Masalah Penugasan dengan

data interval.

Mempelajari cara menyelesaikan permasalahan Rute Terpendek, Pohon

Pembangun Minimum dan Masalah Penugasan dengan data interval.

Mempelajari maksimal regret yang mungkin terjadi dalam permasalahan

Rute Terpendek, Pohon Pembangun Minimum dan Masalah Penugasan

dengan data interval.

Mempelajari program WINQSB yang nantinya digunakan untuk

menyelesaikan setiap skenario yang mungkin.

4

1.3 Batasan Masalah

Pada penyusunan skripsi ini akan dibahas mengenai masalah optimasi

dengan aplikasinya dalam permasalahan pohon pembangun minimum, rute

terpendek dan penugasan dimana fungsi parameter yang menggambarkan biaya,

jarak atau waktu adalah data tunggal. Kemudian akan dijelaskan model

permasalahan tersebut dimana data parameternya berupa interval serta metode

penyelesaian dengan menggunakan teori pengambilan keputusan minmax regret.

Selanjutnya dalam penyelesaian masalah untuk masalah optimasi dengan data

interval, bobot yang menyatakan parameter biaya, jarak, waktu dan sebagainya

hanya untuk semua bilangan bulat positif.

1.4 Maksud dan Tujuan

Penyususan skripsi ini selain untuk memenuhi syarat kelulusan Program

Strata-1 (S1) Program Studi Matematika Universitas Gadjah Mada adalah untuk

mempelajari lebih lanjut masalah optimasi yang telah dipelajari dalam

perkuliahan terutama dalam kaitannya dengan masalah pohon pembangun

minimum, rute terpendek dan masalah penugasan dengan data tunggal yang

kemudian dibawa ke dalam data interval, dan dalam skripsi ini juga dibahas

mengenai teori pengambilan keputusan kriteria minmax regret yaitu suatu

pengambilan keputusan yang meminimalkan maksimal kerugian (regret). Teknik

pengambilan keputusan ini nantinya akan digunakan dalam masalah optimasi

guna mencari solusi terbaik dimana solusi tersebut merupakan solusi dengan

regret terkecil/minimal.

1.5 Tinjauan Pustaka

Skripsi ini membahas tentang pengambilan keputusan minmax regret dalam

masalah optimasi diskrit dengan data interval khususnya dalam permasalahan

Rute Terpendek (Shortest Path), Pohon Pembangun Minimum (Minimum

Spanning Tree) dan Penugasan (Assignment). Dalam pembahasannya juga dibahas

mengenai proses penyelesaian dengan menggunakan algoritma yang telah dikenal

dalam teknik menyelesaikan masalah optimasi, yaitu algoritma pohon pembangun

5

minimum untuk menyelesaikan masalah Pohon Pembangun Minimum, algorithma

djikstra untuk menyelesaikan masalah Rute Terpendek dan metode hungarian

untuk menyelesaikan masalah Penugasan.

Skripsi ini mengacu pada beberapa sumber dalam pembahasannya, untuk

pembahasan awal yaitu mengenai masalah optimasi dengan data tunggal dan

teknik penyelesaiannya mengacu pada buku Winston (2004) dan Taha (2008).

Untuk masalah optimasi diskrit dengan data interval dan teknik penyelesaiannya

mengacu pada buku Kasperski (2008), dalam buku tersebut dibahas mengenai

permasalahan optimasi dengan data interval dengan menggunakan teknik

pengambilan keputusan minmax regret. Materi pembahasan masalah optimasi

diskrit dengan data interval didalamnya membahas mengenai skenario (scenario)

yaitu suatu realisasi tertentu dalam masalah optimasi yang berkaitan dengan

interval datanya, untuk pembahasan skenario ini juga mengacu dari buku

Kouvelis (1997).

Pada pembahasan skripsi ini juga mengacu dari berbagai jurnal yang terkait

dengan masalah optimasi diskrit dengan data interval, dalam jurnalnya Averbakh

(2004) membahas mengenai teknik pengambilan minmax regret dengan interval

data dalam masalah optimasi. Untuk pembahasan contoh minmax regert yaitu

dalam permasalahan Rute Terpendek, Pohon Pembangun Minimum dan Masalah

Penugasan bersumber dari buku Kasperski (2008).

1.6 Metodologi Penelitian

Dalam proses penulisan skripsi ini, diawali dengan melakukan studi literatur

mengenai masalah optimasi dan algoritma yang digunakan dalam penyelesaian

masalah optimasi tersebut. Masalah yang dikaji dalam masalah optimasi tersebut

merupakan masalah optimasi diskrit yang biasa terjadi dalam segala bidang,

misalnya dalam permasalahan ekonomi yang bertujuan mencapai hasil yang

optimal dari suatu permasalahan yang ada. Dalam pembahsannya diambil contoh

permasalahan Rute Terpendek, Pohon Pembangun Minimum dan Penugasan.

Setelah menentukan contoh permasalahan tersebut selanjutnya dipelajari

algoritma yang digunakan untuk menyelesaikan permasalahan tersebut, karena

6

untuk masing-masing permasalahan mempunyai teknik sendiri dalam

penyelesaiannya.

Selanjutnya berdasarkan unsur ketidakpastian, masalah optimasi tersebut

dalam realitanya tidak hanya akan berbentuk dalam data yang pasti, sehingga

muncul permasalahan yang ada tersebut akan berada dalam suatu selang tertentu

sesuai dengan parameter yang menggambarkannya. Kemudian dipelajari masalah

optimasi tersebut dalam suatu interval data dengan berasumsi bahwa dalam selang

interval data tersebut suatu permasalahan akan mencapai solusi optimal.

Dengan menggunakan teori pengambilan keputusan kriteria minmax regret

masalah optimasi diskrit tersebut yaitu khususnya dalam permasalahan Rute

Terpendek, Pohon Pembangun Minimum dan Penugasan dicari solusi optimal

yaitu solusi dengan regret/kerugian terkecil.

1.7 Sistematika Penulisan

Pada penulisan skripsi ini, penulis menggunakan sistematika sebagai

berikut:

BAB I PENDAHULUAN

Pada bab ini dibahas mengenai latar belakang masalah, perumusan masalah,

batasan masalah, maksud dan tujuan, tinjauan pustaka, metodologi penelitian dan

sistematika penulisan.

BAB II LANDASAN TEORI

Pada bab ini berisi landasan teori yang digunakan sebagai dasar untuk

pembahasan dalam bab selanjutnya, diantaranya adalah: definisi dan sifat-sifat

graf, optimasi kombinatorial, model optimasi kombinatorial deterministik dan

teori pengambilan keputusan minmax regret.

BAB III PEMBAHASAN

Bab ini merupakan bab pembahasan utama yaitu mengenai minmax regret

masalah optimasi dengan data interval dengan penerapannya dalam permasalahan

Rute Terpendek, Pohon Pembangun Minimum dan Penugasan, namun

sebelumnya akan dibahas untuk masalah optimasi dengan bobot tunggal.

7

BAB IV PENUTUP

Pada bab ini akan diuraikan kesimpulan-kesimpulan serta saran dari pembahasan

materi-materi pada bab sebelumnya.