Skripsi

Masalah knapsack 0-1 dalam penyelesaian travelling salesman problem (TSP) / oleh Dhia Ika Cahyanti

Abstrak
Teori graph merupakan salah satu penerapan matematika yang bermanfaat untuk menyelesaikan permasalahan dalam kehidupan sehari-hari. Salah satu permasalahan yang dapat diselesaikan menggunakan teori graph adalah masalah Knapsack yaitu permasalahan optimasi yang memaksimumkan atau meminimumkan fungsi tujuan dengan beberapa kendala yang harus dipenuhi. Masalah Knapsack yang dibahas dalam skripsi ini adalah masalah Knapsack 0-1 yang diaplikasikan pada masalah Travelling Salesman Problem (TSP) dalam graph berarah. Langkah pertama yang dilakukan untuk menyelesaikan masalah TSP dalam Knapsack 0-1 adalah mendefinisikan fungsi tujuan yaitu meminimumkan bobot setiap sisi yang terpilih serta mendefinisikan kendala yang harus dipenuhi yaitu semua titik harus dilewati tepat satu kali. Variabel keputusan yang digunakan dalam masalah TSP adalah 0 jika lintasan yang merupakan kandidat solusi tidak dilewati dan bernilai 1 jika lintasan tersebut dilewati. Langkah berikutnya untuk memperoleh solusi yang maksimum dilakukan dengan menggunakan algoritma Greedy yaitu dengan mengurutkan bobot sisi yang terhubung dari yang paling kecil kemudian mengambil bobot paling kecil tersebut sebagai solusi optimum lokal. Titik yang sudah terpilih tidak dipertimbangkan kembali. Sebagai perbandingan digunakan metode Branch and Bound untuk masalah TSP dengan melakukan reduksi baris dan kolom dari matriks bobot pada graph sampai setiap baris dan kolomya memuat paling sedikit satu buah nol sehingga diperoleh suatu sikel Hamilton dengan jarak minimum. Dengan menggunakan beberapa contoh kasus TSP diperoleh anggapan bahwa penyelesaian dengan menggunakan algoritma Greedy lebih efisien. Permasalahan TSP yang bobot pada sisi arah berlawananya sama solusi yang diperoleh dari kedua metode di atas adalah sama. Sedangkan untuk permasalahan TSP dengan bobot pada setiap sisi berarahnya tidak sama solusi yang optimum diperoleh dengan menggunakan metode Branch and Bound. Hal ini disebabkan oleh nilai ongkos yang dihitung pada setiap simpul adalah bobot yang paling kecil yang terdapat pada matriks tereduksi.

Informasi Detail

DDC

Rs 511.5 DHI m

Prodi

Skripsi (Sarjana)--Universitas Negeri Malang. Program Studi Matematika, 2007.

Deskripsi Fisik

ix, 84 hlm : il. : tab. ; 28 cm

Bahasa

Indonesia

No Reg

00883/KI/07

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang, 2007

Subjek

1. TEORI GRAPH
2. KNAPSACK
3. ALGORITMA GREEDY
4. TRAVELLING SALESMAN PROBLEM

Pembimbing

1. SAPTI WAHYUNINGSIH ; 2. DARMAWAN SATYANANDA

Lampiran Berkas