![Makalah Metode Perjalanan Salesman [PDF]](https://pdfs.asia/img/200x200/makalah-metode-perjalanan-salesman.jpg)
16 0 501 KB
Mata kuliah Program Linier
Dosen pengampu Hayatun Nufus, S.Pd, M.Pd.
Metode Perjalanan Salesman
Oleh: 1. Afrida Agustina (11715200037) 2. Annisa Mardhotillah(11715201357) 3. Briliannisa (11715201533)
PROGRAM STUDI PENDIDIKAN MATEMATIKA FAKULTAS TARBIYAH DAN KEGURUAN UNIVERSITAS ISLAM NEGERI SULTAN SYARIF KASIM RIAU PEKANBARU 1441 H/2019 M
KATA PENGANTAR Penulis mengucapkan segala puji bagi Allah yang senantiasa memberikan rahmat dan karunia-Nya, shalawat serta salam kepada nabi Muhammad Solalluhu’alaihi wasallam, keluarganya, sahabatnya, atau seluruh umatnya. Penulis bersyukur kepada Allah Swt yang telah memberikan kesehatan serta hidayah-Nya sehingga makalah yang berjudul “Metode Perjalanan Salesman” dapat terselesaikan.Penulisan makalah ini untuk memenuhi salah satu tugas yang diberikan oleh dosen pengampu matakuliah Program Linier. Materi dalam makalah ini diselesaikan berdasarkan studi pustaka dengan referensi-referensi yang sesuai dengan tujuan agar lebih mengetahui tentang Penggunaan Metode Perjalanan Salesman. Penulis mengetahui bahwa dalam makalah ini terdapat kekurangan. Oleh karena itu, penulis meminta saran dan kritik untuk kesempurnaan makalah ini.Semoga makalah ini bermanfaat bagi para pembaca dan bagi masyarakat.
Pekanbaru, April 2019
Penulis
i
DAFTAR ISI
KATA PENGANTAR ........................................................................................................... i DAFTAR ISI......................................................................................................................... ii DAFTAR TABEL ............................................................................................................... iii
BAB I PENDAHULUAN ..................................................................................................... 1 A.
Latar Belakang Masalah................................................................................................. 1
B.
Rumusan Masalah ......................................................................................................... 2
C.
Tujuan Makalah............................................................................................................. 2
BAB II PEMBAHASAN ...................................................................................................... 5 A.
Pengertian metode perjalanan salesmen ........................................................................ 5
B.
Langkah-langkah metode perjalanan salesmen .............................................................. 4
C.
Contoh soal..................................................................................................................... 7
D.
Soal latihan..................................................................................................................... 8
E.
Penyelesaian soal latihan ................................................................................................ 9
F.
Kunci Jawaban .............................................................................................................. 14
BAB III PENUTUP ............................................................................................................ 15 A.
Kesimpulan .................................................................................................................. 15
B.
Saran ............................................................................................................................. 15
DAFTAR PUSTAKA ......................................................................................................... 16
ii
DAFTAR TABEL
Tabel Permasalahan 1 ........................................................................................................... 5 Tabel Iterasi – 1.1 ................................................................................................................ 6 Tabel Iterasi – 2.1 ................................................................................................................ 6 Tabel 1 Solusi Awal ............................................................................................................. 6 Tabel 1 Iterasi Solusi Awal .................................................................................................. 7 Tabel 1 Solusi Akhir ............................................................................................................. 7 Tabel Permasalahan 2 ........................................................................................................... 8 Tabel Iterasi – 1.2 ................................................................................................................ 8 Tabel Iterasi – 2.2 ................................................................................................................ 9 Tabel 2 Solusi Awal ............................................................................................................. 9 Tabel 2 Iterasi Solusi Awal ................................................................................................. 10 Tabel 2 Solusi Akhir .......................................................................................................... 11 Tabel Iterasi – 1.3 ............................................................................................................... 12 Tabel 3 Solusi Awal ........................................................................................................... 12 Tabel 3 Solusi Akhir .......................................................................................................... 12
iii
BAB I PENDAHULUAN A. Latar Belakang Program linier merupakan suatu model umum yang dapat digunakan dalam pemecahan masalah pengalokasian sumber-sumber yang terbatas secara optimal. Masalah tersebut timbul apabila seseorang diharuskan untuk memilih atau menentukan tingkat setiap kegiatan yang akan dilakukannya dengan ketersediaan sumber yang terbatas untuk mendapatkan hasil yang optimal. Dalam dunia usaha dan industri, manajemen sering menghadapi permasalahan yang berhubungan dengan penugasan optimal dari bermacammacam sumber yang produktif atau personalia yang mempunyai tingkat efisiensi yang berbeda-beda untuk tugas yang berbeda-beda pula. Salah satu contoh permasalahan yang terjadi adalah : Seorang sales manager suatu perusahaan akan mengirimkan salesmen (penjual-penjual) ke empat daerah. Manager ini telah mendapatkan empat calon yang memiliki kemampuan dan pengalaman untuk mencapai keuntungan yang sebesarbesarnya. Di bawah ini adalah tabel yang menunjukkan nilai keuntungan yang dapat dicapainya (dalam ratusan ribu rupiah) : A
B
C
D
I
35
27
28
37
II
28
34
29
40
III
35
24
32
33
IV
24
32
25
28
Berdasarkan tabel di atas, akan dicari berapa keuntungan terbesar yang dapat dicapai oleh salesmen dan ke mana sajakah masing-masing salesmen tersebut ditugaskan. Persoalan di atas harus diselesaikan sebaik mungkin sehingga dapat dicapai keuntungan yang maksimum. Memperhatikan masalah tersebut, penulis ingin memperkenalkan salah satu teknik yang dianggap efisien dan efektif untuk mencari keuntungan maksimum
1
dalam perjalanan salesmen, yaitu teknik perjalanan salesmen. Teknik ini merupakan suatu cara yang layak digunakan dalam menyelesaikan permasalahan penunjukan salesmen untuk melakukan suatu tugas perjalanan demi mencapai keuntungan yang maksimum. Dari uraian di atas, penulis mencoba untuk mengangkat teknik perjalanan salesmen untuk mencapai keuntungan yang maksimum.1 B. Rumusan Masalah 1. Apa pengertian metode perjalanan salesmen? 2. Bagaimana Langkah-langkah penggunaan metode perjalanan salesmen? 3. Bagaimana contoh soal dari metode perjalanan salesmen? 4. Bagaimana soal latihan dari metode perjalanan salesmen? 5. Bagaimana penyelesaian soal latihan metode perjalanan salesmen? 6. Apa kunci jawaban dari soal metode perjalanan salesmen?
C. Tujuan Penulisan 1. Untuk mengetahui pengertian metode perjalanan salesmen. 2. Untuk mengetahui Langkah-langkah penggunaan metode perjalanan salesmen. 3. Untuk mengetahui contoh soal dari metode perjalanan salesmen. 4. Untuk mengetahui soal latihan dari metode perjalanan salesmen. 5. Untuk mengetahui penyelesaian soal latihan metode perjalanan salesmen. 6. Untuk mengetahui kunci jawaban dari soal metode perjalanan salesmen.
1
Hayatun Nufus, “Perjalanan Salesmen”, http://www.academia.edu/3330561/perjalanan_Salesmen, hlm. 1.
2
BAB II PEMBAHASAN A. Pengertian Metode Perjalanan Salesmen Teknik ini merupakan tata cara yang layak digunakan dalam menyelesaikan permasalahan penunjukkan salesmen untuk melakukan tugas perjalanan demi mencapai keuntungan yang maksimum. Teknik perjalanan salesmen merupakan penerapan dari prosedur model penunjukkan yang menyangkut masalah maksimasi (tabel menunjukkan tingkat keuntungan). Metode Perjalanan Salesmen atau Travelling Salesman Problem (TPS) merupakan permasalahan yang banyak ditemukan dalam bidang transportasi khususnya masalah perjalanan, yaitu mengunjungi semua lokasi dengan setiap lokasi hanya
dikunjungi
tepat
satu
kali.Tujuan
dari
penyelesaian
ini
adalah
meminimumkan/memaksimalkan jarak tempuh dan waktu perjalanan sehingga diperoleh rute optimal.2
B. Langkah-Langkah Penggunaan Metode Perjalanan Salesmen Langkah-langkah penggunaan teknik perjalanan salesmen adalah sebagai berikut: 1. Pilihlah bilangan terbesar dari setiap baris pada tabel. 2. Tentukan selisih bilangan pada tiap baris dengan bilangan terbesar yang telah ditentukan pada langkah 1. 3. Bila langkah 2 belum menghasilkan paling sedikit satu nilai nol pada tiap kolom, maka pilihlah bilangan terkecil dari setiap kolom yang belum memiliki nilai nol satupun. 4. Kurangkan setiap bilangan pada masing-masing kolom yang belum memiliki nilai nol dengan bilangan terkecil yang telah ditentukan pada langkah 3. 5. Tariklah sejumlah garis minimum horizontal dan/atau vertikal untuk meliput seluruh elemen bernilai nol yang terdapat dalam tabel. Bila jumlah garis sama
Rendra Firman Pratama, Purwanto, dan Mohammad Yasin, “Penyelesaian Travelling Salesman Problem ( Tsp ) Dengan Menggunakan Artificial Bee Colony” Skripsi Universitas Negeri Malang, 2012, hlm.1. 2
3
dengan jumlah baris atau kolom, maka penunjukan telah mencapai hasil yang optimal. Jika tidak sama, maka tabel harus direvisi. 6. Untuk merevisi tabel, pilih bilangan terkecil yang belum terliput garis.3 7. Kurangkan seluruh bilangan yang belum terliput oleh garis dengan bilangan terkecil yang telah ditentukan pada langkah 6. 8. Tambahkan bilangan yang terletak pada persilangan garis dengan bilangan yang telah ditentukan pada langkah 6. 9. Ulangi langkah 5. Jika jumlah sumber-sumber yang ditugaskan tidak sama dengan jumlah tugas yang akan diselesaikan, maka perlu ditambahkan baris atau kolom semua sebanyak selisih baris atau kolom pada baris atau kolom yang jumlahnya lebih sedikit, sehingga jumlah baris dan kolom menjadi sama. Selanjutnya, dapat diterapkan algoritma teknik perjalanan salesmen.4 C. Contoh soal Persoalan Seorang sales manager suatu perusahaan Kaligrafi akan mengirimkan salesmen (penjual-penjual) ke empat daerah. Manager ini mendapat empat calon yang memiliki kemampuan dan pengalaman untuk mencapai keuntungan yang sebesar-besarnya. Di bawah ini adalah tabel yang menunjukkan nilai keuntungan yang dapat dicapainya (dalam ratusan ribu rupiah) :
3 4
A
B
C
D
I
35
27
28
37
II
28
34
29
40
III
35
24
32
33
IV
24
32
25
28
Hayatun Nufus dan Erdawati Nurdin, Program Linear, (Pekanbaru: Cahaya Firdaus, 2019), hlm. 133. Ibid., hlm.134.
4
Berdasarkan tabel di atas, berapakah keuntungan terbesar yang dapat dicapai oleh salesmen?5
Penyelesaian: Tabel Permasalahan 1 A
B
C
D
I
35
27
28
37
II
28
34
29
40
III
35
24
32
33
IV
24
32
25
28
1. Memilih bilangan terbesar dari setiap baris pada tabel Bilangan terbesar pada tiap baris tabel permasalahan 1 adalah: Baris I = 37 Baris II = 40 Baris III = 35 Baris IV = 32 2. Menentukan selisih bilangan pada tiap baris dengan bilangan terbesar yang telah ditentukan pada langkah 1
5
Ibid.
5
Baris I kolom A : 37-35 = 2
Baris III kolom A : 35-35 = 0
Baris I kolom B : 37-27 = 10
Baris III kolom B : 35-24 = 11
Baris I kolom C : 37-28 = 9
Baris III kolom C : 35-32 = 3
Baris I kolom D : 37-37 = 0
Baris III kolom D : 35-33 = 2
Baris II kolom A : 40-28 = 12
Baris IV kolom A : 32-24 = 8
Baris II kolom B : 40-34 = 6
Baris IV kolom B : 32-32 = 0
Baris II kolom C : 40-29 = 11
Baris IV kolom C : 32-25 = 7
Baris II kolom D : 40-40 = 0
Baris IV kolom D : 32-28 = 4
Berdasarkan uraian di atas, maka tabel permasalahan 1 berubah menjadi : Tabel Iterasi – 1.1 A
B
C
D
I
2
10
9
0
II
12
6
11
0
III
0
11
3
2
IV
8
0
7
4
3. Pada langkah 2, kolom C belum terdapat bilangan nol. Oleh karena itu, dipilihlah bilangan terkecil dari kolom C, yaitu 3 4. Mengurangkan setiap bilangan pada kolom B dengan 3, sehingga: Kolom C baris I : 9-3 = 6 Kolom C baris II : 11-3 = 8 Kolom C baris III : 3-3 = 0 Kolom C baris IV : 7-3 = 4 Berdasarkan uraian di atas, maka tabel iterasi – 1.1 berubah menjadi : Tabel Iterasi – 2.1 A
B
C
D
I
2
10
6
0
II
12
6
8
0
III
0
11
0
2
6
IV
8
0
4
4
5. Pada tabel iterasi – 2.1, hanya terdapat minimum garis sebanyak 3, seperti terlihat pada tabel Tabel 1 Solusi Awal A
B
C
D
I
2
10
6
0
II
12
6
8
0
III
0
11
0
2
IV
8
0
4
4
6. Pada tabel di atas, banyaknya garis tidak sama dengan banyaknya jumlah baris dan kolom. Terdapat 3 buah garis dari 4 buah baris dan kolom, sehingga perlu dilakukan revisi tabel. Oleh karena itu, dipilih bilangan terkecil yang belum terliput garis, yaitu bilangan 2. 7. Mengurangkan seluruh bilangan yang belum terliput oleh garis dengan bilangan Baris I kolom A : 2-2 = 0 Baris I kolom B : 10-2 = 8 Baris I kolom C : 6-2 = 4 Baris II kolom A : 12-2 = 10 Baris II kolom B : 6-2 = 4 Baris II kolom C : 8-2 = 6 8. Menambahkan bilangan yang terletak pada persilangan garis, yaitu bilangan 2 (kolom D baris III) dan 4 (kolom D baris IV) dengan bilangan 2. Kolom D baris III : 2+2 = 4 Kolom D baris IV : 4+2 = 6 Tabel 1 Iterasi Solusi Awal A
B
C
D
I
0
8
4
0
II
10
4
6
0
7
III
0
11
0
4
IV
8
0
4
6
9. Pada tabel solusi awal, terdapat minimum garis sebanyak 4, seperti terlihat pada tabel berikut: Tabel 1 Solusi Akhir A
B
C
D
I
0
8
4
0
II
10
4
6
0
III
0
11
0
4
IV
8
0
4
6
Pada tabel di atas, banyaknya garis sama dengan banyaknya baris dan kolom. Oleh karena itu, tabel-6 telah mencapai hasil yang maksimum. Jadi, keempat salesmen tersebut dapat ditugaskan berdasarkan : Karyawan I ditugaskan ke daerah A = 35 Karyawan II ditugaskan ke daerah D = 40 Karyawan III ditugaskan ke daerah C = 32 Karyawan IV ditugaskan ke daerah B = 32
35+40+32+32 = 139
Dengan total keuntungan maksimum yang dapat diperoleh adalah sebesar Rp.139.000,006
D. Soal Latihan 1. Suatu perusahaan akan meneliti 3 pekerjaan kontruksi mesjid di Riau dengan menempatkan 3 pekerja pada ketiga pekerjaan tersebut. Adapun keutungan maksimum yang akan dicapai pekerja:
6
Ibid., 135.
8
I
II
III
A
23
17
31
B
14
17
29
C
26
23
22
Berapakah keuntungan maksimum yang dapat dicapai oleh pekerja kontruksi mesjid tersebut? (Dalam ribuan dollar) 2. Bu siti akan memproduksi baju syar’i dan akan mengirimkan 4 orang salesmennya ke 4 wilayah di Pekanbaru. Dibawah ini adalah tabel yang menunjukkan keuntungan yang dapat dicapainya? (Dalam ribuan rupiah) I II III IV 1000 900 1100 900 A 1100 1000 950 950 B 1050 950 900 1050 C 1150 1000 950 1000 D Tentukan penunjukkan salesmen agar keuntungan yang diperoleh maksimum!7 E. Penyelesaian Soal Latihan Soal 1 1. Memilih bilangan terbesar dari setiap baris pada tabel Baris I = 31 Baris II= 29 Baris III= 26 2. Menetukan selisih bilangan pada tiap baris dengan bilangan terbesar pada langkah 1: Tabel Permasalahan 2 I
II
III
A
31 – 23 = 8
31 – 17 = 14
31 – 31 = 0
B
29 – 14 = 15 29 – 17 = 12
29 – 29 = 0
Hungarian“Masalahmaksimasi(maksimal)”,https://aimprof08.wordpress.com/2012/04/15/hungarian-masalahminimisasi-minimal/ 7
9
C
26 – 26 = 0
26 – 23 = 3
26 – 22 = 4
Jadi tabel permasalahan 2 berubah menjadi: Tabel Iterasi – 1.2 I
II
III
A
8
14
0
B
15
12
0
C
0
3
4
3. Pada langkah 2, kolom II belum terdapat bilangan nol. Oleh karena itu pilih bilangan terkecil dari kolom II yaitu 3. 4. Kurangkan setiap bilangan pada kolom yang belum mempunyai nilai nol dengan bilangan terkecil yang ditentukan pada langkah 3. Kolom II baris A = 14 – 3 = 11 Kolom II baris B = 12 – 3 = 9 Kolom II baris C = 3 – 3 = 0 Maka tabel iterasi – 1 berubah menjadi: Tabel Iterasi – 2.2 I
II
III
A
8
11
0
B
15
9
0
C
0
0
4
10
5. Tariklah sejumlah garis minimum horizontal/vertikal untuk meliput seluruh elemen bernilai nol, seperti pada tabel berikut: Tabel 2 Solusi Awal I
II
III
A
8
11
B
15
9
0
C
0
0
4
0
6. Pada tabel diatas banyak garis tidak sama dengan banyaknya jumlah baris dan kolom. Terdapat 2 buah garis dan 3 buah baris dan kolom, sehingga perlu dilakukan revisi tabel. Oleh karena itu pilihlah bilangan terkecil yang belum terliput oleh garis, yaitu bilangan 8. 7. Kurangkan seluruh bilangan yang belum terliput oleh garis dengan bilangan terkecil yang ditentukan pada langkah 6. Baris A kolom I =8–8=0 Baris A kolom II = 11 – 8 =3 Baris B kolom I = 15 – 8 = 7 Baris B kolom II =9–8=1 8. Menambahkan bilangan yang terletak pada persilangan garis, yaitu bilangan 4 (baris C kolom III) Baris C kolom III = 4 + 8 = 12 Tabel 2 Iterasi Solusi Awal I
II
III
A
0
3
0
B
7
1
0
C
0
0
12
11
9. Pada tabel solusi awal terdapat minimuum garis sebanyak 3, seperti pada tabel berikut ini: Tabel 2 Solusi Akhir I
II
0
A
3
III 0
B
7
1
0
C
0
0
12
Pada tabel diatas, banyaknya garis sama dengan banyaknya baris dan kolom. Oleh karena itu, tabel 2.6 telah mencapai hasil yang maksimum.
Jadi ketiga pekerja tersebut dapat ditugaskan berdasarkan: Pekerja A ditugaskan ke daerah I = 23 Pekerja B ditugaskan ke daerah II = 29 Pekerja C ditugakan ke daerah III = 23 23 + 29 + 23 = 75 Dengan total keuntungan maksimum yang dapat diperoleh adalah sebesar $ 75000.
Soal 2 1.
Bilangan terbesar : Baris A = 1100 Baris B = 1100 Baris C = 1050 Baris D = 1150;
12
2. Menentukan selisih antar bilangan Tabel Iterasi – 1.3 A B C D
I 1100-1000 = 100 1100-1100 = 0 1050-1050 = 0 1150-1150 = 0
II 1100-900 = 200 1100-1000 =100 1050-950 =100 1150-1000 = 150
III 1100-1100 = 0 1100-950 = 150 1050-900 = 150 1150-950 = 200
IV 1100-900 = 200 1100-950 = 150 1050-1050 = 0 1150-1000 = 150
3. Karena pada kolom 2 belum mempunyai nilai nol satupun, maka 4. Kurangkan setiap bilangan pada masing-masing kolom yg belum memiliki nilai nol dengan bilangan terkecil yg telah ditentukan pada tabel diatas Tabel 3 Solusi Awal A B C D
I 100 0 0 0
II III 200-100=100 0 100-100=0 150 100-100=0 150 150-100=50 200
IV 200 150 0 150
5. Penarikan Garis Minimum Tabel 3 Solusi Akhir A B C D 6.
I 100 0 0 0
II 100 0 0 50
III 0 150 150 200
V 200 150 0 150
Tabel sudah mencapai optimal dengan penempatan: Selisih A
III = 1100
Selisih B
II = 1000
Selisih C
IV = 1050
Selisih D
I = 1150
1100 + 1000 + 1050 + 1150 = 4300
13
Jadi, keuntungan yg diperoleh maksimum adalah sebesar Rp. 4.300.000,008
F. Kunci Jawaban 1. $ 75000 2. Rp.4.300.000,00
8
Hungarian“Masalahmaksimasi(maksimal)”,https://aimprof08.wordpress.com/2012/04/15/hungarian-masalah-
minimisasi-minimal/
14
BAB III PENUTUP A. Kesimpulan Metode perjalanan salesmen ini dapat digunakan untuk menentukan keuntungan terbesar dari seorang salesmen dan kemana rute seorang salesmen tepat satu kali perjalanan. Metode ini terdapat sembilan langkah dimana baris dan kolom dari soal harus sama sehingga dapat diselesaikan dengan metode perjalanan salesmen.
B. Saran Penulis menyarankan agar metode perjalanan salesmen ini dapat berkembang lagi dimasa mendatang, bisa digunakan untuk permasalahan yang lainnya, dan digunakan tidak hanya untuk masalah perjalanan seorang salesmen. Dan metode ini bisa teliti lagi agar cara pengerjaannya bisa lebih sederhana.
15
DAFTAR PUSTAKA Nufus, Hayatun dan Nurdin, Erdawati. 2019. Program Linear. Pekanbaru: Cahaya Firdaus. Nufus,Hayatun“PerjalananSalesmen”dikutip 14 april http://www.academia.edu/3330561/perjalananSalesmen, hlm. 1.
2019
dari:
Pratama, Firman Rendra dkk . 2012. “Penyelesaian Travelling Salesman Problem ( Tsp ) Dengan Menggunakan Artificial Bee Colony” Skripsi Universitas Negeri Malang. Hungarian“Masalahmaksimasi(maksimal)”,dikutip
17
april
2019
https://aimprof08.wordpress.com/2012/04/15/hungarian-masalah-minimisasiminimal/
16
dari:
