Makalah Model Jaringan

BAB I

PENDAHULUAN

1.1  Latar Belakang

Telah banyak dikatakan bahwa tujuan umum perusahaan adalah membuat suatu produk atau jasa dengan biaya serendah – rendahnya, menjual dengan harga yang wajar guna mendapatkan keuntungan yang besar. Dari pernyataan tersebut dapat kita analisa bahwa ada dua fungsi yang utama dalam perusahaan yaitu fungsi produksi dan pemasaran. Fungsi produksi berkenaan dengan penawaran sedangkan fungsi pemasaran berkenaan dengan permintaan.

Dalam memasarkan produk guna memenuhi permintaan konsumen, perusahaan ataupun para manajer dihadapkan pada beberapa persoalan yang salah satunya adalah bagaimana merancang sistem transportasi guna meminimalkan biaya. Persoalan – persoalan transportasi atau distribusi yang berkaitan dengan masalah pengiriman dari suatu sumber ke suatu tujuan dengan ongkos transportasi minimum. Maka model transportasi tersebut dapat diselesaikan sebagai suatu jaringan.

Jaringan muncul di berbagai tempat dan dalam banyak bentuk transportasi, listrik, dan jaringan komunikasi adalah bagian dari kehidupan kita sehari-hari. Seiring dengan perkembangan era globalisasi yang semakin pesat, sebagian besar di berbagai bidang seperti produksi, distribusi, perencanaan proyek, perencanaan tata letak, manajemen sumber daya, dan perencanaan keuangan merasakan jaringan telah menjadi salah satu kebutuhan pokok

Salah satu perkembangan yang paling menggairahkan di bidang penelitian operasional pada beberapa tahun terkhir ini berlangsung pada bidang metodologi dan aplikasi model optimalisasi jaringan. Banyak model optimalisasi jaringan yang dapat digunakan bagi perusahan untuk mengoptimalkan penggunaan biaya salah satunya dalam hal transportasi.

Pada makalah ini, penulis mencoba untuk membahas model – model jaringan yang dapat digunakan untuk menjawab persoalan transportasi dan persoalan yang berkenaan dengan masalah jaringan antara lain persoalan rute terpendek, persoalan rentang pohon minimum, dan persoalan aliran maksimum.

1.2  Rumusan Masalah

Berdasarkan latar belakang tersebut maka rumusan masalah dari penulisan makalah ini adalah:

1. Model jaringan apa yang dapat menyelesaikan persoalan transportasi atau yang digunakan dalam riset operasi beserta contoh penerapannya.

1.3  Tujuan Penulisan

Tujuan penulisan makalah ini adalah sebagai salah satu tugas dalam mata kuliah Operasi Riset. Penulisan ini juga bertujuan untuk mengetahui model – model jaringan yang dapat digunakan dalam penyelesaian persoalan khususnya masalah transportasi.

1.4  Manfaat

Manfaat yang diharapkan dari penulisan makalah ini adalah makalah ini dapat memberikan tambahan pengetahuan bagi yang membaca dan dapat dipergunakan sebagai salah satu referensi dalam mempelajari model jaringan.

BAB 2

PEMBAHASAN

1.1    Model Jaringan

Jaringan lahir karena berbagai keperluan seperti: transportasi, listrik, komunikasi, perencanaan proyek, aliran air, pembuatan jalan, dan lain-lain. Saat ini jaringan sangat penting, sebab dengan jaringan maka masalah yang besar dan rumit dapat disederhanakan. Ada beberapa jaringan yang dapat diselesaikan dengan permasalahan program linear. Pada kajian di sini akan dibahas tiga masalah jaringan, yaitu: permasalahan lintasan terpendek, masalah diagram pohon terpendek, masalah aliran maksimum.

Dalam menggambarkan suatu jaringan kerja digunakan tiga buah simbol sebagai berikut:

1. Anak panah (arrow), menyatakan sebuah kegiatan atau aktivitas. Kegiatan di sini didefinisikan sebagai hal yang memerlukan jangka waktu tertentu dalam pemakaian sejumlah sumber daya (sumber tenaga, peralatan, material, biaya)
2. Lingkaran kecil (node), menyatakan sebuah kejadian atau peristiwa atau event. Kejadian didefinisikan sebagai ujung atau pertemuan dari satu atau beberapa kegiatan.
3. Anak panah terputus-putus, menyatakan kegiatan semu atau dummy . Dummy tidak mempunyai jangka waktu tertentu, karena tidak memakai sejumlah sumber daya.

Komponen jaringan tersebut dapat digambarkan pada gambar dibawah ini:

 

Cabang

 

Model Jaringan

1.        Model Rute Terpendek ( Shortest Route )

Model Rute Terpendek adalah salah satu model jaringan yang dapat digunakan untuk menentukan jarak terpendek dari berbagai alternative rute yang tersedia. Dalam hal ini, istilah rute tidak harus selalu dikaitkan dengan jarak. Kita bisa saja mengganti jarak, misalnya dengan biaya atau waktu.

Prosedur Shortest-Route

1. Tentukan node terdekat dari node asal. Selanjutnya tulis jarak pada kotak di dekat node.
2. Tentukan node terdekat berikutnya, dan tulis jarak pada kotak di dekat node. Dalam beberapa kasus, beberapa jalur harus diperiksa untuk mencari node terdekat
3. Ulangi langkah 2 hingga selesai seluruh jaringan.  Jarak pada node terakhir merupakan jarak terpendek.  Perlu diperhatikan bahwa jarak yang ditulis dekat node merupakan jarak terpendek untuk mencapai node tersebut.

Contoh Kasus

Sebuah perusahaan  ingin mengetahui jarak terdekat dari pabrik ke lokasi pasar yang terletak pada dua kota yang berbeda. Lokasi untuk menuju ke lokasi pasar melalui beberapa kota. 

Jarak tempuh antar nodes digambar sebagai berikut:

                                                                                [22,6]

                                                     17

                 [3, 3]                                              5                    6

                                            6

15

                               3                                    4          2              [6,5]

                    10                         4

pabrik                                                            [4,3]

                             [10,1]

Maka jalur yang dipilih adalah jalur 1 – 3 – 5 – 6 – 7 dengan jumlah biaya atau jarak sebesar 22. Untuk lebih jelas dapat dilihat pada tabel dibawah.

Titik Asal	Titik Tujuan	Jarak / Biaya
1	3	10
3	5	4
5	6	2
6	7	6
TOTAL		22

Jalur yang dipilih tersebut merupakan jalur dengan jarak atau biaya yang paling rendah dibandingkan alternative jalur yang lain.

2.        Model Rentang Pohon Minimum ( Minimal Spanning Tree )

Pohon rentang minimum (minimal spanning tree) adalah teknik mencari jalan penghubung yang dapat menghubungkan semua titik dalam jaringan secara bersamaan sampai diperoleh jarak minimum.

Masalah pohon rentang minimum serupa dengan masalah rute terpendek (shortest route), kecuali bahwa tujuannya adalah untuk menghubungkan seluruh simpul dalam jaringan sehingga total panjang cabang tersebut diminimisasi. Jaringan yang dihasilkan merentangkan (menghubungkan) semua titikdalam jaringan tersebut pada total jarak (panjang) minimum.

Prosedur Minimal Spanning Tree

1. Pilih sembarang node (atau untuk lebih konsisten pilih node pertama)
2. Hubungkan node tersebut dengan node terdekat
3. Kemudian, cari dan hubungkan node terdekat yang belum terhubungi.
4. Ulangi langkah ketiga hingga semua node terhubung

Contoh Kasus:

Andaikan perusahaan air minum daerah membangun jaringan pipa yang melewati beberapa node. Semua node harus terhubungi Dalam kasus ini seluruh node harus dapat dihubungkan, sehingga dapat diselesikan dengan metode Minimal Spanning Tree. Jalur pipa dan jarak antar node ditampilkan pada jalur berikut ini:

                                                         40

20                            50

                                              40                10               30         40

                                              40                         20

Jika daerah tersebut akan dipasang jaringan pipa maka jalur pipa yang harus dipasang adalah sebagai berikut:

1. Mulai dari titik/ stasiun 1. Titik terdekat dengan 1 adalah 2 dengan jarak 20, maka hubungkan antara 1 dengan 2.
2. Titik terdekat dari dua titik yaitu 1 dan 2 adalah titik 4 dan 5. Jarak titik 1 ke titik 4 lebih pendek yaitu sebesar 30 dibandingkan titik 2 ke 5 maka hubungkan antara 1 dengan 4.
3. Titik terdekat dari 4 yaitu titik 3 dan 6. Karena titik 3 lebih dekat dengan 4 dengan jarak 10 maka hubungkan titik 4 dengan 3.
4. Titik terdekat dari dua titik yaitu titik 4 dan titik 3 adalah titik 4 dengan titik 6, maka hubungkan titik 4 dengan 6
5. Titik terakhir yang belum terhubung adalah titik 5, maka hubungkan titik 3 dengan 5.

Total panjang jalur dari jaringan pipa tersebut dapat dilihat pada tabel dibawah:

Titik Awal	Titik Tujuan	Jarak
1	2	20
1	4	30
4	3	10
4	6	20
3	5	30
TOTAL		110

                                                                             30

20                                                   10

                                           30

                                                                            20

3.        Model Aliran Maksimum ( Maximal Flow )

Model Aliran Maksimum ( Maximal Flow ), sesuai dengan namanya adalah sebuah model yang dapat digunakan untuk mengetahui nilai maksimum seluruh arus di dalam sebuah system jaringan. Jaringan listrik, pipa saluran dan jalur lalu lintas dalam sebuah system jaringan yang tertutup adalah contoh – contohnya. Kapasitas pada setiap jaringan hubungan akan membatasi jumlah arus atau aliran yang melewatinya. Sebagai contoh, sebuah kabel listrik dengan  kapasitas 10 ampere akan segera terbakar apabila kita memaksa kabel itu dilewati oleh arus 50 ampere pada tingkat tegangan yang sama. Contoh lain, lalu lintas pada sebuah arus jalan searah akan macet apabila kemampuannya untuk menampung jumlah kendaraan terlampaui.

Situasi yang telah dijelaskan oleh kedua contoh diatas merupakan pusat perhatian model aliran maksimum yang mempunyai tujuan untuk memaksimumkan jumlah arus yang melewati jaringan hubungan dalam sebuah sistim jaringan. Hal ini tentunya sangat umum terjadi pada bidang – bidang transportas,  produksi/operasi, komunikasi dan distribusi.

Prosedur Maximal Flow

1. Cari dan temukan path dari titik sumber ke titik lokasi tujuan yang memiliki arah dengan aliran kapasitas yang lebih besar dari nol untuk seluruh segitiga di dalam path. Jika tidak ada path yang tersedia,  berarti optimal solution telah tercapai
2. Cari di aliran kapasitas yang paling kecil (S_f) di dalam path yang terpilih di Step 1. Lakukan perubahan di dalam aliran di dalam jaringan dengan mengirimkan sejumlah (S_f)
3. Untuk path yang terpilih di Step 1, kurangkan seluruh arus kapasitas dengan (Sf) di node arah masuk dan tambahkan di arus balik node sebesar (Sf)
4. Ulangi Step 1.
5. Hentikan algoritma, ketika di node arah lebih kecil dari nol

Contoh : Aliran Maksimum

 

            6                     3          4                      0

      5                              5                                      8

                                     

                                                     0                                      0

                                  0          6                         0

Kapasitas aliran yaitu 5

Iterasi 1 adalah 1 – 2 – 3 – 4 : Sf : 2 – 3 = 5

 

               Iterasi 2 yaitu 1 – 3 – 5 : Sf: 1 – 3 = 5

               Akumulasi = 5 + 5

 

            Iterasi 3 yaitu 1 – 2 – 4 – 3 – 5 : Sf : 1 – 2 = 1

Tabel aliran maksimal tersebut dapat diliat pada tabel berikut:

	Awal	Akhir	Kapasitas	Kapasitas				Aliran
				Mula		Akhir
Cabang 1	1	2	6	6	3	0	9	6
Cabang 2	1	3	5	5	0	0	5	5
Cabang 3	2	3	5	5	0	0	5	5
Cabang 4	2	4	4	4	0	3	1	1
Cabang 5	3	4	7	2	5	3	4	-1
Cabang 6	3	5	6	6	0	0	6	6
Cabang 7	4	5	8	8	0	3	5	6

BAB III

KESIMPULAN

1.         Model Rute Terpendek adalah salah satu model jaringan yang dapat digunakan untuk menentukan jarak terpendek dari berbagai alternative rute yang tersedia sehingga akan mengurangi biaya transportasi. Dalam model ini tidak semua alternative pilihan jalur harus diambil karena jalur yang dipilih adalah jalur yang paling pendek

2.        Pohon rentang minimum (minimal spanning tree) adalah teknik mencari jalan penghubung yang dapat menghubungkan semua titik dalam jaringan secara bersamaan sampai diperoleh jarak minimum. Model ini mengharuskan semua titik terhubung dengan prioritas adalah jarak terdekat dari titik awal atau titik sebelumnya.

3.         Model Aliran Maksimum ( Maximal Flow ), adalah sebuah model yang dapat digunakan untuk mengetahui nilai maksimum seluruh arus di dalam sebuah system jaringan. Dalam menggunakan model ini adalah dengan memperhatikan aliran arus / kapasitas yang disesuaikan dengan persediaan yang ada. Iterasi dapat dihentikan jika telah terjadi arus balik.

DAFTAR PUSTAKA

Dimyati. Tjutju, Operations Research Model – model Pengambilan Keputusan, Sinar Baru Algensindo, Bandung, 2003.

Handoko, Dasar – dasar Manajemen Produksi Dan Operasi. BPFE, Yogyakarta, 1997.

Hamdy Taha, Operation Research An Introduction, Edisi 4, Macmillan, New York

Richard Bronson, Theory and Problem of Operation Research , McGraw-Hill, Singapore.

Subagyo Pangestu, Marwan Asri, dan T. Hani Handoko. Dasar-Dasar Operation Research, Yogyakarta: PT. BPFE-Yogyakarta, 2000.

Aminudin, Prinsip-Prinsip Riset Operasi, Erlangga, 2005

Yulian Zamit, Manajemen Kuantitatif, BPFE, Yogyakarta