STUDI TRAVELLING SALESMAN PROBLEM (TSP) DENGAN MENGGUNAKAN PROGRAM DINAMIK

STUDI TRAVELLING SALESMAN PROBLEM (TSP) DENGAN MENGGUNAKAN PROGRAM DINAMIK

SKRIPSI

Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Sains

GOLTIANDY PANGARIBUAN 040803005

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2009

Goltiandy Pangaribuan : Studi Travelling Salesman Problem (TSP) Dengan Menggunakan Program Dinamik, 2009. USU Repository © 2009.

PERSETUJUAN

Judul

: STUDI TRAVELLING SALESMAN PROBLEM (TSP) DENGAN MENGGUNAKAN PROGRAM DINAMIK

Kategori : SKRIPSI Nama : GOLTIANDY PANGARIBUAN Nomor Induk Mahasiswa : 040803005 Program Studi : SARJANA (S1) MATEMATIKA Departemen : MATEMATIKA Fakultas : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA

Diluluskan di Medan, Maret 2009 Komisi Pembimbing : Pembimbing 1

Pembimbing 2

Drs. Faigiziduhu Bu’ulolo, M.Si NIP. 130 810 772

Drs. Henry Rani Sitepu, M.Si NIP. 131 238 729

Diketahui/ Disetujui oleh Departemen Matematika FMIPA USU Ketua,

Dr. Saib Suwilo, M.Sc NIP. 131 796 149


PERNYATAAN

STUDI TRAVELLING SALESMAN PROBLEM (TSP) DENGAN MENGGUNAKAN PROGRAM DINAMIK

SKRIPSI

Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.

Medan, Maret 2009

GOLTIANDY PANGARIBUAN 040803005


PENGHARGAAN Segala puji, hormat, dan syukur kepada Tuhan Yesus Kristus yang telah memberikan kasih dan anugerahNya kepada penulis selama masa perkuliahan hingga penulisan skripsi ini. Tujuan penulisan skripsi ini sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains Departemen Matematika pada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara. Penulis banyak menerima bimbingan, nasehat, dan dorongan dari berbagai pihak selama masa perkuliahan hingga penulisan skripsi ini. Pada kesempatan ini, penulis ingin mengucapkan terima kasih kepada : 1. Bapak Dr. Eddy Marlianto, M.Sc selaku Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara. 2. Bapak Dr. Saib Suwilo, M.Sc selaku Ketua Departemen Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara. 3. Bapak Drs. Henry Rani Sitepu, M.Si selaku Sekretaris Departemen Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara. 4. Bapak Drs. Faigiziduhu Bu’ulolo, M.Si dan Bapak Drs. Henry Rani Sitepu, M.Si selaku Dosen Pembingbing yang telah membimbing, mengarahkan, dan memberikan saran kepada penulis. 5. Bapak Drs. H. Haluddin Panjaitan dan Ibu Dra. Elly Rosmaini, M.Si selaku Dosen Pembanding yang telah memberikan saran dalam penulisan maupun perbaikan skripsi ini. 6. Seluruh dosen dan pegawai Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara. 7. Orangtua tercinta Parlaungan Pangaribuan dan Ernita Hotmauli br. Nasution serta Opung T. br. Hutabarat yang telah memberikan motivasi, kasih sayang, dan doa kepada penulis. 8. Adik-adik tercinta Jansen Pangaribuan, Nurlinda Pangaribuan, Juwita Ratna Sari Pangaribuan, dan Dian Siswanto Pangaribuan. 9. Lae Aan Berlin, Kak Nata, Kak Ibeth, Dame. Thanks buat semuanya. 10. Kekasih tercinta Tangi Ceria Isabella Pane, SE yang selalu memberikan dukungan, semangat, dan inspirasi. 11. Teman-teman mahasiswa Departemen Matematika khususnya Lae Justinus, Lae Jusyan, Lae Ronal Gomar, Lae Moan, HMM. Terus berjuang !! 12. Teman-teman NHKBP Bethesda khususnya Triadi Pane dan Resi Pane. Akhir kata, penulis mengucapkan terima kasih dan semoga Tuhan memberkati. Medan, Maret 2009

Goltiandy Pangaribuan Goltiandy Pangaribuan : Studi Travelling Salesman Problem (TSP) Dengan Menggunakan Program Dinamik, 2009. USU Repository © 2009.

ABSTRAK

Travelling Salesman Problem (TSP) dapat diilustrasikan sebagai pejalanan seorang salesman atau sekelompok salesman yang harusmelalui semua kota tujuan dengan biaya (cost) paling minimum, dalam perjalanannya setiap kota hanya boleh dilalui tepat satu kali. Solusi otimal dari TSP ialah biaya paling minimum yang dapat ditempuh oleh salesman tersebut. Rute perjalanan dengan aturan pengunjungan satu dan hanya satu kalipada setiap simpul (node) alam graph disebut dengan jalur Hamiltonian. TSP merupakan suatu permasalahan permutasi ; yaitu problem yang secara konensional diselesaikan dalam waktu n! (n faktorial), untuk n buah objek. Didalam tulidsan ini akan dibahas mengenai cara menentukan rute optimal pada TSP dengan menggunakan Proram Dinamik secara rekursif mundur.


ABSTRACT

Travelling Salesman Problem (TSP) can be illustrated as a journey of one or a group of salesman with a minimum cost to go by the destination cities; all at once. The optimal solution from TSP is the minimum cost that can be reached by the salesman. The journey’s route with one rule visitation and only one time at every knot (node) in graph called Hamiltonian route. TSP is the permutation case which is a conventional problem solved in n! (n factorial ) time for n object. In this paper, it will studied about how to decide the optimal route for TSP and use Dynamic Programming in rercursive backward.


DAFTAR ISI Halaman

Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar

ii iii iv v vi vii viii ix

Bab 1

Pendahuluan 1.1. Latar Belakang 1.2. Perumusan Masalah 1.3. Pembatasan Masalah 1.4. Tinjauan Pustaka 1.5. Tujuan Penulisan 1.6. Kontribusi Penulisan 1.7. Metodologi Penulisan

1 1 2 2 3 5 6 6

Bab 2

Landasan Teori 2.1. Terminologi Program Dinamik 2.2. Forward Program Dinamik 2.3. Tahap (stage) dan Kondisi (state) 2.4. Proses Keputusan Multistages 2.4.1. Representasi Proses Keputusan Multistages 2.4.2. Jenis Masalah Optimasi Bertahap 2.5. Konsep Sub Optimasi dan Prinsip Keoptimalan 2.5.1. Konsep Sub Optimasi 2.5.2. Prinsip Keoptimalan 2.6. Contoh Kasus Peminimuman Biaya Perjalanan

7 7 9 9 10 11 12 12 13 13 14

Bab 3

Analisa dan Pembahasan 3.1 Tahapan Penyelesaian TSP 3.2. Analisa Kasus TSP

19 19 22

Bab 4

Kesimpulan dan Saran 4.1. Kesimpulan 4.2. Saran

37 37 38

Dartar Pustaka


DAFTAR TABEL

Halaman Tabel 2.1. Tahap 4 Perjalanan Tabel 2.2. Tahap 3 Perjalanan Tabel 2.3. Tahap 2 Perjalanan Tabel 2.4. Tahap 1 Perjalanan Tabel 3.1. Tahap N Proses Penyelesaian Tabel 3.2. Tahap (N-1) Proses Penyelesaian Tabel 3.3. Tahap (N-2) Proses Penyelesaian Tabel 3.4. Tahap 1 Proses Penyelesaian Tabel 3.5. Tabel Biaya Soal 1 Tabel 3.6. Tahap 4 Penyelesaian Soal 1 Tabel 3.7. Tahap 3 Penyelesaian Soal 1 Tabel 3.8. Tahap 2 Penyelesaian Soal 1 Tabel 3.9. Tahap 1 Penyelesaian Soal 1 Tabel 3.10. Tahap Biaya Soal 2 Tabel 3.11. Tahap 5 Penyelesaian Soal 2 Tabel 3.12. Tahap 4 Penyelesaian Soal 2 Tabel 3.13. Tahap 3 Penyelesaian Soal 2 Tabel 3.14. Tahap 2 Penyelesaian Soal 2 Tabel 3.15. Tahap 1 Penyelesaian Soal 2

15 16 16 17 19 20 20 21 22 25 25 26 27 29 31 31 32 33 34


DAFTAR GAMBAR Halaman Gambar 2.1. Gambaran Persoalan Gambar 2.2. Problema Keputusan Tahap Tunggal Gambar 2.3. Proses Keputusan Multistages Gambar 2.4. Optimasi pada Tahap ke-i Gambar 2.5. Biaya dan Rute Perjalanan Gambar 2.6. Biaya dan Rute Perjalanan Optimal Gambar 3.1. Perjalanan soal 1 Gambar 3.2. Rute Perjalanan Optimal soal 1 Gambar 3.3. Perjalanan soal 2 Gambar 3.4. Rute Perjalanan Optimal soal 2

7 11 11 13 14 18 24 28 30 36


BAB 1

PENDAHULUAN

1.1. Latar Belakang

Persoalan perjalanan (Travelling) merupakan kasus yang sering dijumpai dalam kehidupan nyata, persoalan ini membutuhkan penyelesaian dengan memperhitungkan segala kemungkinan yang bisa terjadi pada setiap langkah penentuan kebijakannya. Pada hakekatnya perjalanan dilakukan oleh seseorang atau sekelompok orang. Travelling tidak terlepas dari beberapa faktor penting, yaitu : biaya (cost) perjalanan, lama (waktu) perjalanan, jarak tempuh perjalanan. Akan menjadi persoalan jika terdapat beberapa tempat yang harus dilalui dengan biaya yang berbeda-beda pada setiap tempat. Semakin banyak tempat yang harus dilalui, semakin banyak pula kombinasi rute yang mungkin untuk dilalui, sementara sales tersebut harus memilih satu rute yang akan dilalui dengan biaya minimum.

Program Dinamik adalah suatu teknik matematis untuk pembuatan serangkaian keputuasan yang saling berhubungan. Program Dinamik menyediakan prosedur sistematis untuk menentukan kombinasi keputusan yang optimal. Jika dihubungkan dengan masalah sales tersebut bahwa setiap keputusan yang diambilnya tentunya akan mempengaruhi keputusan yang akan diambil selanjutnya atau keputusan yang diambil sekarang merupakan keputusan yang mempertimbangkan keputusan sebelumnya. Dengan demikian akan diperoleh rangkaian kebijakan optimal. Atas dasar inilah penulis mengangkat judul “Studi Travelling Salesman Problem (TSP) dengan menggunakan Program Dinamik”.


1.2. Perumusan Masalah

Dalam kasus TSP ini diasumsikan bahwa kondisi lintasannya normal, sehingga biaya yang dianalisa adalah sudah merupakan biaya yang ditimbulkan dengan segala kendala pada masing-masing lintasan.

Semakin banyak tempat yang harus dilalui,

semakin banyak pula rute yang mungkin untuk dilalui. Persoalannya adalah “ Bagaimana menentukan rute yang harus dilalui dengan biaya paling minimum dari sekian banyak rute yang mungkin untuk dilalui? “.

1.3. Pembatasan Masalah

Adapun yang menjadi batasan masalah dalam tulisan ini adalah : 1. Persoalan TSP yang diambil adalah persoalan yang menyangkut penentuan rute perjalanan dengan biaya paling minimum, 2. Diasumsikan bahwa kondisi perjalanannya normal, sehingga data biaya yang disajikan dan dianalisis adalah data biaya yang diperoleh dari perhitungan biaya akhir pada setiap lintasan setelah memperhitungkan semua kendala pada lintasan yang bersangkutan, 3. Biaya pada setiap lintasan bisa saja sama atau berbeda, 4. Yang dimaksud dengan rute dalam tulisan ini adalah urutan perjalanan dari kota asal menuju ke semua kota tujuan kemudian kembali ke kota asal, 5.

Kota tujuan hanya boleh dikunjungi tepat satu kali dalam satu rute.


1.4. Tinjauan Pustaka

Pemahaman tentang Program Dinamik ini akan lebih mudah dipahami dengan dasar pemikiran mengatakan bahwa “Program Dinamik adalah suatu teknik matematis untuk pembuatan serangkaian keputusan yang saling berhubungan. Program Dinamik menyediakan prosedur sistematis untuk menentukan kombinasi keputusan yang optimal. Pendekatan program dinamik didasarkan pada prinsip optimasi Bellman (1950) yang mengatakan suatu kebijakan optimal mempunyai sifat bahwa apapun keadaan dan keputusan awal, keputusan berikutnya harus membentuk suatu kebijakan optimal dengan memperhatikan keadaan dari hasil keputusan pertama .“ (Frederick S. Hiller dkk, 1990).

Sebagai perbandingan perlu dipahami bahwa “Tidak seperti program linier, Program Dinamik tidak mempunyai standar formulasi matematik. Program Dinamik lebih merupakan suatu cara umum untuk melakukan optimasi dengan persamaan matematik yang cocok dengan masalah yang dihadapi.”(Djoko L, 2003).

Hubungan rekursif mengidentifikasi kebijakan optimal pada tahap n , bila diketahui kebijakan optimal untuk tahap (n + 1) .

Secara umum ditulis :

{

}

f s∗ ( s ) = min C sxn + f n∗+1 ( x n ) ………………………………...…………….(1.1) xn

Dalam hal ini, untuk menemukan keputusan kebijakan optimal, diperlukan penemuan nilai x n yang meminimumkan (membuat minimum) pada tahap n yang dimulai pada tahap s . Biaya minimum tersebut diperoleh dengan menggunakan nilai


x n diatas dan mengikuti kebijakan optimal bila dimulai dari keadaan x n pada tahap

(n + 1) .

Notasi-notasi pada hubungan rekursif :

N = Banyaknya tahap,

n = Indeks untuk tahap sekarang (n = 1,2,..., N ) , s n = Keadaan sekarang untuk tahap n , s nk = Keadaan k yang mungkin ditempuh pada tahap n ( k ∈ bilangan bulat positif ),

x n = Peubah keputusan untuk tahap n , x n∗ = Nilai optimal x n ( diketahui s n ),

f n ( s n , x n ) = Kontribusi tahap n, n + 1,..., N , ( Ket. : Kepada fungsi tujuan bila sistem dimulai dari keadaan s n pada tahap n , keputusan sekarang adalah x n dan keputusan optimal dibuat sesudahnya), f n∗ ( s n ) = f n ( s n , x n∗ ) .

Hubungan rekursif yang digunakan pada persoalan-persoalan tertentu tergantung pada fungsi tujuannya, secara umum : f n∗ ( s n ) = max{ f n ( s n , x n )}………………………………………………….(1.2) xn

atau f n∗ ( s n ) = min{ f n ( s n , x n )}……………………………………………..……(1.3) xn

Dikatakan sebagai hubungan rekursif karena hubungan tersebut selalu berulang setiap proses bergerak ke belakang (mundur) tahap demi tahap. Dengan Goltiandy Pangaribuan : Studi Travelling Salesman Problem (TSP) Dengan Menggunakan Program Dinamik, 2009. USU Repository © 2009.

menggunakan hubungan rekursif ini, prosedur penyelesaian bergerak mundur tahap demi tahap sampai ditemukan kebijakan optimal yang dimulai dari tahap awal. Misalkan peubah keputusan x n (n = 1,2,3,4) adalah tujuan sekarang pada tahap ke- n ( perjalanan kereta ke- n ). Perjalanan dimulai dari A dan diakhiri di J, maka rute yang dipilih adalah :

A → x1 → x 2 → x3 → x 4

x4 = J Misalkan f n ( s, x n ) adalah total biaya seluruh polis terbaik untuk tahap-tahap yang tersisa, bila dianggap sipencari keberuntungan berada pada keadaan s , sedang bersiap untuk memulai tahap ke- n , dan memilih x n sebagai tujuan sekarang. Dengan menganggap s dan n diketahui, misalkan x n∗ melambangkan nilai x n yang meminimumkan f n ( s, x n ) dan misalkan f n∗ (s ) adalah nilai minimum dari f n ( s, x n ) .

Dengan demikian : f n∗ ( s ) = min f n ( s, x n ) = f n ( s, x n∗ ) …………………………...……………..(1.4)

f n ( s, x n ) = Biaya sekarang (tahap n ) + Biaya minimum mendatang (tahap n + 1 )……………………………...……………….….……….(1.5)

Tujuan adalah menemukan f1∗ ( A) dan rute yang sesuai. Pemograman dinamik menemukannya dengan secara berurutan menemukan : f 4∗ ( s ), f 3∗ ( s ), f 2∗ ( s )

Untuk setiap keadaan s yang mungkin dan kemudian menggunakan f 2∗ ( s ) untuk mencari f1∗ ( A) . Goltiandy Pangaribuan : Studi Travelling Salesman Problem (TSP) Dengan Menggunakan Program Dinamik, 2009. USU Repository © 2009.

( Frederick S. Hillier, dkk, 1990)

1.5. Tujuan Penulisan

Adapun yang menjadi tujuan penulisan ini adalah untuk menentukan solusi optimal (biaya yang minimum) dan rute yang harus dilalui pada TSP dengan menggunakan Program Dinamik.

1.6. Kontribusi Penulisan

Adapun kontribusi yang diperoleh dari tulisan ini adalah : 1. Dapat dijadikan sebagai teori dasar dalam melakukan penelitian-penelitian lebih lanjut menyangkut peminimuman biaya perjalanan. 2. Memperkaya literatur tentang persoalan TSP.

1.7. Metodologi Penulisan

Identifikasi Masalah

Untuk mengidentifikasi masalah, akan dibuatkan contoh kasus TSP. Diberikan contoh kasus yang diangkat dari literatur yang menyangkut peminimuman biaya perjalanan.

Model Permasalahan

Persoalan TSP tersebut digambarkan dalam bentuk tabel biaya atau graph perjalanan. Selanjutnya diekspresikan dalam model matematika dengan variabel-variabel yang disesuaikan dengan notasi-notasi pada kajian pustaka. Goltiandy Pangaribuan : Studi Travelling Salesman Problem (TSP) Dengan Menggunakan Program Dinamik, 2009. USU Repository © 2009.

Penyelesaian Soal

Penyelesaian kasus TSP ini adalah dengan menggunakan hubungan rekursif pada program dinamik, dengan urutan atau prosedur penyelesaian disesuaikan dengan teori yang disajikan dalam landasan teori pada bab berikutnya.

BAB 2

LANDASAN TEORI

Program Dinamik adalah suatu teknik matematis untuk pembuatan serangkaian keputuasan yang saling berhubungan. Program Dinamik menyediakan prosedur sistematis untuk menentukan kombinasi keputusan yang optimal. Pendekatan program dinamik didasarkan pada prinsip optimasi Bellman (1950) yang mengatakan “ Suatu kebijakan optimal mempunyai sifat bahwa apapun keadaan dan keputusan awal, keputusan

berikutnya

harus

membentuk

suatu

kebijakan

optimal

dengan

memperhatikan keadaan dari hasil keputusan pertama “.

2.1. Terminologi Program Dinamik Y

H

Goltiandy 3 Pangaribuan : Studi Travelling Salesman Problem (TSP) Dengan Menggunakan Program Dinamik, 2009. USU Repository © 2009.

2 2

L

5

3

F 2

1

D

7

−2

4

3 2

3 G

−3

5 O

I

1

4

1

0 −1

1

C

1

A 0

3

E

M 4

J 4

2 2

2

51

B 6

X

8 4 P

2

5

2

N

K Gambar 2.1. Gambaran persoalan

Persoalannya pada gambar 2.1 adalah untuk menentukan rute dari A sampai ke B dengan nilai minimum.

Fungsi nilai optimal S adalah suatu fungsi dari pasangan bilangan ( x, y ) melambangkan suatu titik pangkal dari pada suatu fungsi, seperti A atau C, pasangan

( x, y ) melambangkan suatu persimpangan jalan pada peta (untuk selanjutnya disebut vertex dari jaringan).

Didefenisikan fungsi nilai optimal S ( x, y ) dengan :

S ( x, y ) = Nilai perolehan minimum lintasan tersambung titik ( x, y ) dengan nilai

terminal ( x, y ) …………………....…………………………….(2.1)

Prinsip optimalisasi bertahap ganda : a ( x, y ) + S ( x + 1, y + 1)  S ( x, y ) = min  u  …………………..……………..(2.2) a d ( x, y ) + S ( x + 1, y − 1) Goltiandy Pangaribuan : Studi Travelling Salesman Problem (TSP) Dengan Menggunakan Program Dinamik, 2009. USU Repository © 2009.

au diartikan sebagai perjalanan dari vertex ( x, y ) menuju vertex ( x + 1, y + 1) , a d diartikan sebagai perjalanan dari vertex ( x, y ) menuju vertex ( x + 1, y − 1) .

2.2. Forward Program Dinamik

Fungsi nilai optimal baru S dengan rumus :

S ( x, y ) = nilai perolehan minimum lintasan tersambung vertex awal (0,0) dengan vertex ( x, y ) .......………………………………………….…...(2.3)

Pendekatan relasi bertahap ganda unutk fungsi nilai optimal : a ( x − 1, y − 1) + S ( x − 1, y − 1)  S ( x, y ) = min  u  ………………..…………(2.4) a d ( x − 1, y + 1) + S ( x − 1, y + 1)

dengan syarat batas adalah S (0,0) = 0 …………………………………...…....….(2.5) biaya dari lintasan terbaik dari A ke diri sendiri adalah nol. Goltiandy Pangaribuan : Studi Travelling Salesman Problem (TSP) Dengan Menggunakan Program Dinamik, 2009. USU Repository © 2009.

2.3. Tahap (stage) dan Kondisi (state)

Untuk lebih memahami tentang tahap (stage) dan kondisi (state) dalam tulisan ini, maka diberikan karakteristik dari program dinamik sebagai berikut :

1. Permasalahannya dapat dibagi menjadi tahapan dengan keputusan kebijakan pada tiap tahap, 2. Tiap tahap mempunyai sejumlah kondisi terkait, 3. Pengaruh keputusan kebijakan pada setiap tahapan adalah transformasi kondisi yang terkait dengan awal dari tahapn berikutnya, 4. Prosedur penyelesaian dirancang untuk mendapatkan kebijakan optimum untuk seluruh tahapan, yaitu dengan membuat kebijakan optimum untuk setiap tahap pada setiap kemungkinan kondisi,

5. Pada suatu kondisi sebuah kebijakan optimum untuk tahapan selanjutnya tidak terkait oleh kebijakan optimum dari tahapan sebelumnya. Jadi keputusan optimum yang diambil hanya tergantung pada kondisi sekarang bukan dari bagaimana sampai pada kondisi sekarang. Inilah yang dinamai prinsip optimum dari Program Dinamik, 6. Prosedur penyelesaian mulai dengan mendapatkan solusi optimum untuk tahap terakhir, 7. Hubungan rekursif untuk memperoleh solusi optimum untuk tahap n, dengan solusi optimum untuk tahap (n+1) telah diketahui. Rumus menjadi :

{

}

f n* ( s ) = min c s ( x n ) + f n*+1 ( x n +1 ) ………………..…………….…………...(2.6) xn


2.4. Proses Keputusan Multistages

Dalam penggunaan Program Dinamik dikenal suatu proses yang dinamakan Proses Multistages. Proses Multistages merupakan proses keputusan tunggal yang saling berhubungan sehingga hasil dari suatu tahapan merupakan input pada tahapan berikutnya, sehingga semua tahapan saling berhubungan.

2.4.1. Representasi Proses Keputusan Multistages

Adapun proses keputusan tahap tunggal, seperti pada gambar berikut :

Fungsi objektif (F)

Input (S)

Output (T)


Keputusan (X)

Gambar 2.2. Problema keputusan tahap tunggal

Parameter yang digunakan pada problema keputusan tahap tunggal diatas adalah Input (S), Variabel keputusan (X), dan Output (T). Parameter output (T) direpresentasikan sebagai hasil keputusan.

Representasi skema proses keputusan Multistages : fn

xn Tahap-n

f n −1

x n −1 Tahan-(n-1)

fi

f1

xi

x1

Tahap-i

Tahap-1

Gambar 2.3. Proses keputusan Multistages

Dari skema diatas dapat dijelaskan sebagai berikut :

Pada tahapan ke-i input disimbolkan S i +1 dan output disimbolkan S i . Sehingga output dari tahap ke- (i + 1) menjadi input pada tahap ke-i. Dengan demikian, diperoleh nilai-nilai x1 , x 2 , x3 ,  , x n yang digunakan untuk memperoleh nilai optimum di fungsi F ( f1 , f 2 , f 3 ,  , f n ) .


2.4.2. Jenis Masalah Optimasi Bertahap

Adapun jenis masalah optimasi bertahap adalah sebagai berikut :

1. Masalah nilai awal Dinamakan masalah nilai awal, jika input bagi seluruh sistem diketahui sedangkan outputnya tidak diketahui. 2. Masalah nilai akhir Dinamakan masalah nilai akhir, jika output dari seluruh sistem saja yang diketahui sedangkan inputnya tidak diketahui. 3. Masalah nilai batas Dinamakan masalah nilai batas, jika input dan output dari seluruh sistem diketahui.

2.5. Konsep Sub Optimasi dan Prinsip Keoptimalan

Sebagai ilustrasi, disajikan proses optimal pada tahap tertentu, misalkan pada tahap ke-i sebagai berikut :

Biaya

Input ( S i +1 )

Output ( S i )

Tahap ( S i )

Keputusan ( xi ) Goltiandy Pangaribuan : Studi Travelling Salesman Problem (TSP) Dengan Menggunakan Program Dinamik, 2009. USU Repository © 2009.

Gambar 2.4. Optimasi pada tahap ke-i

2.5.1. Konsep Sub Optimasi

Adapun konsep sub optimasi yang digunakan adalah :

1. S1 tidak mempengaruhi tahap-tahap yang lain , sehingga tahap-1 dapat dioptimumkan tersendiri yang merupakan sub optimasi pertama.

2. Penyelesaian tahap pertama digabungkan dengan tahap yang kedua merupakan masalah sub optimasi kedua.

3. Penyelesaian masalah sub optimasi kedua dengan tahap ketiga akan menjadi masalah sub optimasi ketiga, demikian seterusnya.

2.5.2. Prinsip Keoptimalan

Sifat prinsip keoptimalan adalah bahwa apapun kondisi awal yang ditetapkan dan dan keputusan awal yang diambil, maka keputusan-keputusan berikutnya harus membentuk suatu kebijakan optimal.

2.6. Contoh Kasus Peminimuman Biaya Perjalanan

Sebagai gambaran, akan disajikan kasus yang menyangkut penentuan biaya termurah sebagai berikut : Goltiandy Pangaribuan : Studi Travelling Salesman Problem (TSP) Dengan Menggunakan Program Dinamik, 2009. USU Repository © 2009.

Andaikan seorang pebisnis akan pergi dari kota A ke kota J dengan menggunakan kendaraan umum. Untuk sampai ke kota J ia harus melalui beberapa kemungkinan kota yang bisa dilalui dengan biaya yang berbeda. Besar biaya dan rute jalan dari A ke J disajikan sebagai berikut :

Tahap 1

Tahap 2

7

B

4

D

3

F

J

3

4 4

H

6

C 2

3

Tahap 4

4

3 A

1

E

4

6

2

Tahap 3

4

3

1

5

G

3

I

Gambar 2.5. Biaya dan rute jalan Dengan menyelesaikan bahwa dalam setiap tahap kita pilih yang biayanya termurah, jika diawali dari A maka diperoleh rute A-B-F-I-J dengan biaya 2 + 4 + 3 + 4 = 13. Sedangkan jika diawali dari J maka diperoleh rute J-H-E-C-A dengan biaya 3 + 1 + 3 + 4 = 11.

Formulasi 1 : Pilih variabel keputusan x n (n = 1,2,3,4) sebagai kota yang harus ditempuh pada tahap

n , sehingga rute seluruhnya adalah x1 → x 2 → x3 → x 4 dengan x1 = A dan x 4 = J. Goltiandy Pangaribuan : Studi Travelling Salesman Problem (TSP) Dengan Menggunakan Program Dinamik, 2009. USU Repository © 2009.

Kemudian pilih Pilih f n ( s, x n ) sebagai biaya total untuk kebijakan keseluruhan dari tahapan selanjutnya dengan pebisnis sampai pada kondisi s, siap berangkat ke tahap n, dengan memilih x n sebagai kota tujuan berikutnya.

Formulasi 2 : Pada kondisi s dan tahap n, gunakan

x n*

sebagai sembarang nilai yang

meminimumkan f n ( s, x n ) , gunakan f n* ( s ) sebagai nilai minimum dari f n ( s, x n ) . Dengan f n ( s, x n ) = biaya sekarang (tahap n) + minimum biaya (tahap n+1 dan selanjutnya). Diformulasikan sebagai : f n ( s, x n ) = c s ( x n ) + f n*+1 ( x n )

Prosedur penyelesaian : Pada tahap akhir n = 4, maka perjalanannya hanya ditentukan sepenuhnya oleh kondisi s sekarang (yaitu H atau I) dan tujuan akhir J, sehingga : f 4* ( s ) = f 4 ( s, J ) = c s ( J )

Pada tahap akhir n = 4 ini hasilnya ditabelkan sebagai berikut :

Tahap 4 Tabel 2.1. Tahap 4 perjalanan

s

f 4* ( s )

x 4*

H

3

J

I

4

J

Tabel diatas menyajikan fakta bahwa kalau pebisnis sudah sampai di H maupun di I, maka solusi feasiblenya adalah x 4* = J.

Tahap 3 Goltiandy Pangaribuan : Studi Travelling Salesman Problem (TSP) Dengan Menggunakan Program Dinamik, 2009. USU Repository © 2009.

Pada tahap n = 3, maka perjalanannya perlu melakukan beberapa hitungan. Misalkan dia sudah sampai di kota F , maka dia bisa menuju ke kota H atau I, dengan biaya pada tahap 3 ini adalah c F ( H ) = 6 atau c F ( I ) = 3 . Pada tahap n = 3 hasil ditabelkan sebagai berikut :

Tabel 2.2. Tahap 3 perjalanan f 3 = c s + f 4*

s

f 3* ( s )

x3*

H

I

E

4

8

4

H

F

9

7

7

I

G

6

7

6

H

E, H

→ 4=1+3

E, I

→ 8=4+4

F, H

→ 9=6+3

F, I

→ 7=3+4

G, H

→ 6=3+3

G, I

→ 7=3+4

Tahap 2


s

f 2* ( s )

x 2*

E

F

G

B

11

11

12

11

E,F

C

7

9

10

7

E

D

8

8

11

8

E,F


B, E

→ 11 = 7 + 4

B, F

→ 11 = 4 + 7

B, G

→ 12 = 6 + 6

C, E

→ 7=3+4

C, F

→ 9=2+7

C, G

→ 10 = 4 + 6

D, E

→ 8=4+4

D, F

→ 8=1+7

D, G

→ 11 = 5 + 6

Tahap 1


s

A

A, B

→ 13 = 2 + 11

A, C

→ 11 = 4 + 7

A, D

→ 11 = 3 + 8

B

C

D

13

11

11

f 2* ( s )

x1*

11

C,D

Dari hasil di atas nilai optimum telah tercapai yaitu 11, dengan rute : Rute 1 : A → C → E → H → J = 4 + 3 + 1 + 3 = 11 Rute 1 : A → D → E → H → J = 3 + 4 + 1 + 3 = 11 Rute 1 : A → D → F → I → J = 3 + 1 + 3 + 4 = 11


Rute tersebut dalam gambar berikut :

Tahap 1

Tahap 2

B

Tahap 3

E

1

Tahap 4

H

3 4

A

C

3

3 F

3

1

D

J

4

G

4

I

Gambar 2.6. Biaya dan rute perjalanan optimal


BAB 3

ANALISA DAN PEMBAHASAN

3.1. Tahapan Penyelesaian TSP

Ada banyak cara yang digunakan dalam menyajikan masalah dinamik, tergantung pada persoalan dinamiknya. Seperti yang dikatakan sebelumnya bahwa pada kasus TSP ini terdapat beberapa syarat, yaitu : sales harus melalui semua kota tujuan tepat satu kali dan kemudian kembali ke kota asal. Oleh karena itu tabel dan tahapan yang dibentuk adalah sebagai berikut :

Adapun tahapan yang disajikan adalah :

Tabel 3.1. Tahap N Proses Penyelesaian S

f n* ( s )

x n*

S ( n −1)1

…

Sn

S ( n −1) 2

…

Sn







S ( n −1) k

…

Sn


Dalam identifikasi masalah, diperoleh banyak tahapan yang mungkin untuk dilalui, dinotasikan dengan N. Pada tahap ini n = N , n merupakan indeks untuk tahap sekarang.

Sedangkan keadaan

yang mungkin untuk ditempuh pada tahap-

k

n dinotasikan dengan S nk , dan kadaan k yang mungkin untuk ditempuh pada tahap-

(n − 1) dinotasikan dengan S ( n −1) k , demikian seterusnya.

Tabel 3.2. Tahap ( N-1 ) Proses Penyelesaian f n ( s, x n ) = C sxn + f n∗+1 ( x n )

xn

s

x n∗

f n∗ (s )

s ( n −1)1

s ( n −1) 2

…

s ( n −1) k

s ( n − 2 )1

…

…

…

…

…

…

s( n−2)2

…

…

…

…

…

…

:

:

:

:

:

:

:

…

…

s( n−2)k

…

…

…

…

Dalam tahap ini n = N − 1 .

Tabel 3.3. Tahap ( N-2 ) Proses Penyelesaian f n ( s, x n ) = C sxn + f n∗+1 ( x n )

xn

s

f n∗ (s )

x n∗

s ( n − 2 )1

s( n−2)2

…

s( n−2)k

s ( n −3)1

…

…

…

…

…

…

s ( n −3) 2

…

…

…

…

…

…


:

:

:

:

:

:

:

s ( n −3) k

…

…

…

…

…

…

Dalam tahap ini n = N − 2 .

Prosedur ini terus dilakukan sampai pada tahap n = 1 , atau sampai pada tabel berikut :

Tabel 3.4. Tahap 1 Proses Penyelesaian

s

s1

f1∗ ( s )

f1 ( s, x1 ) = C sx1 + f 2∗ ( x1 )

x1 s 21

s 22

…

s 2k

…

…

…

…

…

x1∗

…

Dengan demikian penyelesaian optimal untuk keseluruhan masalah sekarang dapat diidentifikasi, dengan biaya yang tertera pada tabel 1 adalah f1∗ ( s ) .

Dalam penentuan rute, dapat dilihat pada setiap tabel dengan masing-masing n ; n = 1,2,..., N . Keadaan dengan nilai f n∗ (s ) terkcil adalah keadaan (jalur) yang ditempuh, begitu seterusnya. Karena dianalisis dilakukan dengan rekursif mundur, maka rute optimal diurutkan secara mundur.

Sebagai analisa, pada bab ini akan diberikan beberapa persoalan TSP yang diselesaikan dengan program dinamik secara rekursif mundur. Seperti yang dikatakan Goltiandy Pangaribuan : Studi Travelling Salesman Problem (TSP) Dengan Menggunakan Program Dinamik, 2009. USU Repository © 2009.

sebelumnya bahwa dalam kasus TSP ini diasumsikan bahwa kondisi lintasan normal (tidak berpengaruh), sehingga biaya yang dianalisis sudah merupakan perhitungan biaya akhir dengan mempertimbangkan setiap kendala pada masing-masing linatasan.

3.2. Analisa dan Pembahasan Contoh Kasus TSP

Contoh 1

Seorang sales akan memasarkan produknya ke kota B, C, dan D dari kota A. Dalam pendistribusian produknya, ia tidak diperbolehkan mengunjungi satu kota lebih dari satu kali, dan semua kota tujuan harus dilalui. Adapun biaya yang harus dikeluarkan pada masing-masing lintasan disajikan pada tabel berikut :

Tabel 3.5. Tabel biaya soal 1 Kota A

Kota B

Kota C

Kota D

Kota A

-

Rp. 80.000,-

Rp. 70.000,-

Rp. 50.000,-

Kota B

Rp. 40.000,-

-

Rp. 60.000,-

Rp. 60.000,-

Kota C

Rp. 50.000,-

Rp. 30.000,-

-

Rp. 70.000,-

Kota D

Rp. 60.000,-

Rp. 40.000,-

Rp. 50.000,-

-

Tentukanlah rute yang harus dilalui oleh sales tersebut dengan biaya paling minimum! Goltiandy Pangaribuan : Studi Travelling Salesman Problem (TSP) Dengan Menggunakan Program Dinamik, 2009. USU Repository © 2009.

Analisa dan pembahasan :

Sebagai perbandingan, akan disajikan penyelesaian dengan menampilkan kombinasi rute perjalanan yang mungkin terjadi. Dalam kasus ini, kota yang harus dihubungkan ada 4 kota, maka diperoleh 6 rute yang mungkin untuk dilalui.

Kombinasi rute : Rute 1 :

A

B

C

D

A

Rute 2 :

A

B

D

C

A

Rute 3 :

A

C

B

D

A

Rute 4 :

A

C

D

B

A

Rute 5 :

A

D

B

C

A

Rute 6 :

A

D

C

B

A

Biaya yang ditimbulkan :

Rute 1 : Rp.80.000,- + Rp.60.000,- + Rp.70.000,- + Rp.60.000 = Rp.270.000,Rute 2 : Rp.80.000,- + Rp.60.000,- + Rp.50.000,- + Rp.50.000 = Rp.240.000,Rute 3 : Rp.70.000,- + Rp.30.000,- + Rp.60.000,- + Rp.60.000 = Rp.220.000,Rute 4 : Rp.70.000,- + Rp.70.000,- + Rp.40.000,- + Rp.40.000 = Rp.220.000,Rute 5 : Rp.50.000,- + Rp.40.000,- + Rp.60.000,- + Rp.50.000 = Rp.200.000,Rute 6 : Rp.50.000,- + Rp.50.000,- + Rp.30.000,- + Rp.40.000 = Rp.170.000,-

Dari data biaya yang ditimbulkan diatas, maka diperoleh bahwa biaya minimum yang ditimbulkan dari keenam rute tersebut adalah Rp.170.000,- dengan rute : A

D

C

B

A.

Penyelesaian dengan Program Dinamik : Goltiandy Pangaribuan : Studi Travelling Salesman Problem (TSP) Dengan Menggunakan Program Dinamik, 2009. USU Repository © 2009.

Agar analisanya sesuai dengan teori yang telah disajikan sebelumnya, maka semua variabel pada kasus 1 ini diimplelentasikan ke notasi-notasi program dinamik. Adapun notasi-notasi yang digunakan adalah :

Notasi-notasi pada hubungan rekursif :

N = Banyaknya tahap,

n = Indeks untuk tahap sekarang (n = 1,2,..., N ) , s n = Keadaan sekarang untuk tahap n , s nk = Keadaan k yang mungkin ditempuh pada tahap n ( k ∈ bilangan bulat positif ), C S n = Biaya pada tahap n ,

S 0 = Kota asal , x n = Peubah keputusan untuk tahap n , x n∗ = Nilai optimal x n ( diketahui s n ),

f n ( s n , x n ) = Kontribusi tahap n, n + 1,..., N ,

Dengan demikian persoalan asles tersebut diimplementasikan dalam notasinotasi dinamik dengan N = 4 ; n = 1,2,3,4 . Karena dianalisa secara rekursif mundur, maka dimulai dari tahap akhir atau tahap 4 untuk kasus ini.

Gambaran rutenya sebagai berikut :

Tahap 1

Tahap 2

S11

S

S

Tahap 3

S 21

Tahap 4

S 31

S

4 S 2(TSP) S 32Program Dinamik, 2009. 12 0 Pangaribuan : Studi Travelling Goltiandy Salesman Problem Dengan Menggunakan 2 USU Repository © 2009.

S13

S 33

S 23

Gambar 3.1. Perjalanan soal 1 Sebagai catatan : S11 = kota ke-1 yang mungkin untuk dilalui pada tahap 1 S12 = kota ke-2 yang mungkin untuk dilalui pada tahap 1

 S nk = kota ke- k yang mungkin untuk dilalui pada tahap n

dengan k ∈ bilangan bulat positif ; n = 1,2,3,...N

Tabel 3.6. Tahap 4 penyelesaian soal 1 S

f 4* ( s )

x 4*

S 31

Rp.40.000,-

S4

S 32

Rp.50.000,-

S4

S 33

Rp.60.000,-

S4

Untuk tahap selanjutnya, biaya yang di tampilkan adalah dalam ribuan rupiah.

Tabel 3.7. Tahap 3 penyelesaian soal 1 Goltiandy Pangaribuan : Studi Travelling Salesman Problem (TSP) Dengan Menggunakan Program Dinamik, 2009. USU Repository © 2009.

f 3 ( s, x3 ) = C sx 3 + f 4∗ ( x3 )

x3

S

S 31

S 32

S 33

S 21

-

50 + 60

60 + 60

S 22

40 + 30

-

60 + 70

S 23

40 + 40

50 + 50

-

f 3* ( s )

x3*

f 3* ( s )

x3*

atau

f 3 ( s, x3 ) = C sx 3 + f 4∗ ( x3 )

x3

S

S 31

S 32

S 33

S 21

-

110

120

110

S 32

S 22

70

-

130

70

S 31

S 23

80

100

-

80

S 31

Dalam tahap 3 ini diperoleh nilai f 3* ( s ) paling minimum adalah rute yang melalui S 31 dengan f 3* ( s ) = Rp.70.000,- . Dengan demikian pada tahap 3 ini rute yang diambil adalah S 31 . Proses dilanjutkan pada tahap 2 berikutnya.

Tabel 3.8. Tahap 2 penyelesaian soal 1 f 2 ( s, x 2 ) = C sx 2 + f 3∗ ( x 2 )

x2

S

S 21

S 22

f 2* ( s )

x 2*

S 23


S11

-

70 + 60

80 + 60

S12

110 + 30

-

80 + 70

S13

110 + 40

70 + 50

-

atau f 2 ( s, x 2 ) = C sx 2 + f 3∗ ( x 2 )

x2

S

f 2* ( s )

x 2*

S 21

S 22

S 23

S11

-

130

140

130

S 22

S12

140

-

150

140

S 21

S13

150

120

-

120

S 22

Dalam tahap 2 ini diperoleh bahwa nilai f 2* ( s ) paling minimum adalah yang melalui S 22 dengan f 2* ( s ) = Rp.120.000,- , dengan demikian pada tahap 2 ini rute yang diambil adalah S 22 . Proses dilanjutkan pada tahap 1 berikutnya.

Tabel 3.9. Tahap 1 penyelesaian soal 1 f1 ( s, x1 ) = C sx1 + f 2∗ ( x1 )

x1

S S0

f1* ( s )

S11

S12

S13

130 + 80

140 + 70

120 + 50

x1*


atau f1 ( s, x1 ) = C sx1 + f 2∗ ( x1 )

x1

S S0

S11

S12

S13

210

210

170

f1* ( s )

x1*

170

S13

Penentuan rute :

Untuk analisa awal, tahap yang diperhatikan adalah tahap 2 dengan kondisi f 2* ( s ) paling minimum dengan S 22 sebagai rutenya. Kemudian tahap 3 dengan kondisi f 3* ( s ) paling minimum dengan S 31 sebagai rutenya. Untuk setiap S1 ( S11 , S12 , S13 )

yang mungkin, kemudian menggunakan f 2* ( s ) untuk mencari f1* ( s ) . Maka dipilihlah rute S13 karena biayanya paling minimum di S1 dengan nilai f1* ( s ) = Rp. 170.000,-.

Maka rute yang harus dilalui sales tersebut adalah :

S0

Tahap 1

Tahap 2

S13

S 22

S 31

Tahap 3

S4

Tahap 4


S0

S11

S 21

S 31

S12

S 22

S 32

S13

S 23

S 33

S4

Gambar 3.2. Rute optimal soal 1

Dalam hal ini sales tersebut seharusnya melalui rute secara berurutan dari kota A ke kota D, C, B, dan kembali ke kota A.

Dengan biaya = Rp.50.000,- + Rp.50.000,- + Rp. 30.000,- + Rp. 40.000,= Rp.170.000,-

Contoh 2 : Goltiandy Pangaribuan : Studi Travelling Salesman Problem (TSP) Dengan Menggunakan Program Dinamik, 2009. USU Repository © 2009.

Seorang sales akan mendistribusikan produknya ke kota P, Q, R, dan S dari kota A. Dalam pendistribusian produknya, ia hanya boleh mengunjungi satu kota tepat satu kali dan semua kota harus dilalui. Setelah sales itu menghitung biaya yang akan ditimbulkan pada masing-masing lintasan, diperoleh tabel biaya sebagai berikut:

Tabel 3.10. Tabel biaya soal 2 Kota A

Kota P

Kota Q

Kota R

Kota A

-

Kota P

Rp.300.000,-

Kota Q

Rp.400.000,- Rp.600.000,-

Kota R

Rp.200.000,- Rp.400.000,- Rp.600.000,-

Kota S

Rp.500.000,- Rp.300.000,- Rp.700.000,- Rp.400.000,-

Kota S

Rp.500.000,- Rp.200.000,- Rp.800.000,- Rp.200.000,-

Rp.500.000,- Rp.600.000,- Rp.400.000,-

Rp.300.000,- Rp.500.000,-

Rp.200.000,-

Tentukanlah rute yang harus dilalui oleh sales tersebut dengan biaya paling minimum!

Analisa dan penyelesaian :

Dalam analisa dan penyelesaian contoh 2 ini, notasi-notasi yang digunakan sama dengan notasi-notasi yang digunakan pada contoh 1, namun untuk contoh 2 ini N = 5 ; n = 1,2,3,4,5 . Dengan semakin besarnya nilai N , maka akan semakin banyak

pula kemungkinan rute yang dapat dilalui.


Keterangan :

S11 = kota ke-1 yang mungkin untuk dilalui pada tahap 1 S12 = kota ke-2 yang mungkin untuk dilalui pada tahap 1

 S nk = kota ke- k yang mungkin untuk dilalui pada tahap n

dengan k ∈ bilangan bulat positif ; n = 1,2,3,...N

Tabel 3.11. Tahap 5 penyelesaian soal 2 S

f 5* ( s )

x5*

S 41

Rp.300.000,-

S5

S 42

Rp.400.000,-

S5

S 43

Rp.200.000,-

S5

S 44

Rp.500.000,-

S5

Untuk tahap selanjutnya, biaya yang di tampilkan adalah dalam ribuan rupiah.


x4 S

S 43

f 4* ( s )

S 41

S 42

S 31

-

400 + 500

200 + 600 500 + 400

S 32

300 + 600

-

200 + 300 500 + 500

S 33

300 + 400 400 + 600

-

500 + 200

S 34

300 + 300 400 + 700

200 + 400

-

x 4*

S 44


atau f 4 ( s, x 4 ) = C sx 4 + f 5∗ ( x 4 )

x4 S

f 4* ( s )

x 4*

S 41

S 42

S 43

S 44

S 31

-

900

800

900

800

S 43

S 32

900

-

500

1000

500

S 43

S 33

700

1000

-

700

700

S 44

S 34

600

1100

600

-

600

S 41 atau S 44

Dalam tahap 4 ini diperoleh nilai f 4* ( s ) paling minimum adalah yang melalui S 43 dengan f 4* ( s ) = Rp. 500.000,-, dengan demikian pada tahap 4 ini rute yang diambil adalah S 43 . Proses dilanjutkan pada tahap 3 berikutnya.

Tabel 3.13. Tahap 3 Penyelesaian soal 2 f 3 ( s, x3 ) = C sx 3 + f 4∗ ( x3 )

x3 S

S 33

f 3* ( s )

S 31

S 32

S 21

-

500 + 500

700 + 600 600 + 400

S 22

800 + 600

-

700 + 300 600 + 500

S 23

800 + 400 500 + 600

-

600 + 200

S 24

800 + 300 500 + 700

700 + 400

-

x3*

S 34


atau f 3 ( s, x3 ) = C sx 3 + f 4∗ ( x3 )

x3 S

f 3* ( s )

x3*

S 31

S 32

S 33

S 34

S 21

-

1000

1300

1000

1000

S 32 atau S 34

S 22

1400

-

1000

1100

1000

S 33

S 23

1200

1100

-

800

800

S 34

S 24

1100

1200

1100

-

1100

S 31 atau S 33

Dalam tahap 3 ini nilai f 3* ( s ) paling minimum adalah yang melalui S 34 dengan nilai f 3* ( s ) = Rp.800.000,- , maka pada tahap 3 ini rute yang diambil

adalah S 34 . Proses dilanjutkan pada tahap 2 berikutnya.


x2 S

f 2* ( s )

S 21

S 22

S 23

S 24

S11

-

1000 + 500

800 + 600

1100 + 400

S12

1000 + 600

-

800 + 300

1100 + 500

S13

1000 + 400

1000 + 600

-

1100 + 200

x 2*


S14

1000 + 300

1000 + 700

800 + 400

-

atau f 2 ( s, x 2 ) = C sx 2 + f 3∗ ( x 2 )

x2 S

f 2* ( s )

x 2*

S 21

S 22

S 23

S 24

S11

-

1500

1400

1500

1400

S 23

S12

1600

-

1100

1600

1100

S 23

S13

1400

1600

-

1300

1300

S 24

S14

1300

1700

1200

-

1200

S 23

Dalam tahap 2 ini nilai f 2* ( s ) = Rp. 1.200.000,- dengan melalui S 23 sebagai rute paling minimum. Proses dilanjutkan pada tahap 1 berikutnya.

Tabel 3.15. Tahap 1 penyelesaian soal 2 f1 ( s, x1 ) = C sx1 + f 2∗ ( x1 )

x1 S

S11

S12

S13

f1* ( s )

x1*

S14


S0

1400 + 500

1100 + 200

1300 + 800

1200 + 200

atau f1 ( s, x1 ) = C sx1 + f 2∗ ( x1 )

x1 S

S0

S11

S12

S13

S14

1900

1300

2100

1400

f1* ( s )

x1*

1300

S12

Untuk analisa awal pada contoh 2 ini, pada tahap 2 dengan kondisi

f 2* ( s )

paling minimum dengan S 23 sebagai rute. Selanjutnya pada tahap 3 dengan kondisi f 3* ( s ) paling minimum dengan S 34 sebagai rute. Pada tahap 4 dengan kondisi f 4* ( s )

paling minimum dengan rute S 43 sebagai rute.

Untuk setiap S1 ( S11 , S12 , S13 , S14 ) yang mungkin, kemudian menggunakan f1* ( s ) . Maka dipilihlah rute S12 karena biayanya paling

f 2* ( s ) untuk mencari minimum di S1 .

Dengan demikian, rute yang harus dilalui sales tersebut agar biaya minimum adalah : S0

S12

S 23

S 34

S 41

S5

Dalam hal ini sales tersebut seharusnya melalui rute secara berurutan dari kota A ke kota Q, R, S, P, dan kembali ke kota A.


Dengan biaya : = Rp.200.000,- + Rp.300.000,- + Rp.200.000,- + Rp.300.000,- + Rp.300.000 = Rp.1.300.000,-

BAB 4

KESIMPULAN DAN SARAN

4.1. Kesimpulan

Setelah memaparkan teori dan pembahasan TSP dengan Program Dinamik, maka dari tulisan ini dapat disimpulkan sebagai berikut :

1. Persoalan penentuan rute perjalanan dengan biaya paling minimum dari semua kemungkinan rute yang mungkin untuk dilalui pada persoalan TSP dapat diselesaiakan dengan menggunakan Program Dinamik. Goltiandy Pangaribuan : Studi Travelling Salesman Problem (TSP) Dengan Menggunakan Program Dinamik, 2009. USU Repository © 2009.

2. Persoalan TSP dapat diselesaikan dengan menggunakan Program Dinamik secara rekursif mundur dengan menyajikan tabelisasi dan perhitungan matematis pada entri tabelnya, pengambilan kebijakan optimal dapat dilihat melalui tabel akhir pada setiap tahap penyelesaiannya.

4.2. Saran

Adapun saran-saran yang penulis sampaikan adalah sebagai berikut :

1. Penyelesaian secara rekursif pada Program Dinamik ini dijadikan sebagai teori dasar

untuk

mendukung

penelitian-penelitian

lebih

lanjut

mengenai

peminimuman biaya perjalanan pada kasus-kasus yang lebih kompleks.

2. Teori ini dapat juga digunakan dalam penentuan jarak terpendek atau waktu tersingkat (tercepat) pada persoalan Travelling Salesman Problem (TSP).


DAFTAR PUSTAKA

C. L. LIU. 1995. Dasar-dasar Matematika Diskret. Jakarta: PT.Gramedia Pustaka Utama.

Dreyfus, Stuart E., Law, Averill M.. 1997. The Art and Theory of Dynamic Programming. New Jersey San Fransisco London: Academic Press.


Hiller, Frederick S., Liberman, Gerald J.. 1990. Introduction to Operations Researc. first edition. Mc Grow- Hill: Inc..

Luknanto, Djoko. 2002. Program Dinamik. Yogyakarta: FT-UGM.

Mulyono, S.. 2002. Riset Operasi. Jakarta: FE-UI.

Seymour S., Lipson, Marc L. 2001. Matematika Diskrit. Jakarta: Salemba Teknika.


STUDI TRAVELLING SALESMAN PROBLEM (TSP) DENGAN MENGGUNAKAN PROGRAM DINAMIK

Recommend Documents