model arus jaringan
DESCRIPTION
resume manajemen sains model arus jaringanTRANSCRIPT
BAB I
PENDAHULUAN
A.LATAR BELAKANG
Suatu jaringan(network) adalah suatu pengaturan jalur yang menghubungkan berbagai titik, menggunakan satu atau lebih kendaraan untuk berpindah dari satu titik ke titik yang lain.Hampir semua orang mengetahui jaringan semacam ini, jaringan yang mirip dengan system jalan raya, jaringan telepon, system rel keret api, dan jaringan televisi.Sebagai contoh, jaringan rel kereta api terdiri atas sejumlah rute rel tetap(jalur) yang dihubungkan dengan terminal di berbagai persimpangan rute rel.
Pada tahun-tahun terakhir, penggunaan model jaringan telah menjadi sebuah teknis sains manajemen yang sangat popular untuk beberapa alasan yang sangat penting.Pertama, jaringan digambarkan sebagai diagram, yang secara harfiah memberikan gambaran dari system yang dianalisis.Hal ini memungkinkan manajer untuk menginteprestasikan system tersebut secara visual sehingga ia dapat meningkatkan pemahamannya.Kedua, sejumlah besar system dalam kehidupan nyata dapat dimodelkan sebagai jaringan, yang realtif mudah untuk dipahami dan dibuat.
B. RUMUSAN MASALAH
1.Apa pengertian dari jaringan?
2.Apa saja permasalahan dalam menggunakan model arus jaringan?
C.TUJUAN
1.Mengetahui pengertian jaringan
2.Mengetahui permasalahan-permasalah dalam menggunakan model arus jaringan.
BAB II
ISI
A.PENGERTIAN JARINGAN
Jaringan adalah suatu susunan garis edar (path) yang terhubung pada berbagai titik, dimana satu atau beberapa barang bergerak dari satu titik ke titik lain (Taylor, 2005) .Jaringan digambarkan sebagai diagram yang terdiri atas dua komponen utama, yaitu noda dan cabang.Noda(nodes) mewakili titiik persimpanngan, sebagia contoh, perpotongan dari beberapa jalan.Cabang(branches) menghunbungkan noda-noda dan mencermikan arus dari satu titik dalam jaringan ke titik yang lain.Noda ditunjukkan dalam diagram jaringan dengan lingkaran , dan cabang diwakili oleh garis yang menghubungkan noda-noda tersebut.Noda biasanya diwakili lokalitas, seperti kota, perpotongan, atau terminal udara atau kereta api, cabang adalah jalur yang menghubungkan noda-noda tersebut seperti jalan yang menghubungkan kota-kota dan perpotongan rel kereta api atau rute udara yang menghubungkan terminal-terminal.Sebagai contoh, rute rel kereta yang berbeda antara Atlanta, Georgia, dan St.Louis, Missouri, dan terminal-terminal perantara.
Gambar tersebut mempunyai empat noda dan empat cabang.Noda yang mewakili Atlanta menunjukkan lokasi asal, dan ketiga noda yang lain merupakan tujuan, tergantung pada apa yang akan diputuskan terkait jaringan tersebut.Nilai yang ditentukan pada cabang biasanya mewakili jarak, waktu, biaya.Tujuan dari jaringan adalah untuk menentukan jarak terdekat, waktu paling singkat, dan biaya palin rendah antartitik di dalam jaringan.
B.PERMASALAHAN-PERMASALAHAN MODEL ARUS JARINGAN
1.PERMASALAHAN RUTE TERPENDEK
Permasalahan rute terpendek adalah menentukan jarak terpendek antara satu titik asal dan beberapa titik tujuan.Sebagai contoh, stagecoach shipping company mengangkut jeruk dengan enam truk dari Los Angels dan kota-kota tujuan dan lamanya waktu tempuh, dalam jam yang dibutuhkan oleh sebuah truk menempuh setiap rute.Manajer dari perusahaan pengiriman tersebut ingin menentukan rute terbaik(dalam arti waktu tempuh minimum) bagi
2
1
3
4
nashville
St.louis
memphis
atlanta
4
6
5
3
9
truk-truk tersebut untuk mancapi tujuan mereka.permasalahn ini dapat diseleseikan dengan menggunakan teknik solusi rute terpendek.
PENDEKATAN SOLUSI RUTE TERPENDEK
Mulai teknik solusi rate terpendek dari noda 1 (asal) dan menentukan waktu terpendek yang dibutuhkan untuk mencapai sebuah noda yang terhubung secara langsung ( yaitu yang bersebelahan). Tiga noda yang secara langsung terhubung adalah 2,3,4.Dari ketiga noda tersebut pendekatannya adalah 9 jam, yaitu noda 3.Kemudian, dimisalkan noda 1 dan 3 sebagai rangkaian permanen untuk memastikan bahwa telah menemukan rute terpendek menuju noda-noda tersebut( karena tidak ada rute yang menuju noda 1, noda ini secara otomatis berada dalam rangkain permanen).
1
32
4
6
72
5216
25
8
35
12 1419
915
17 14
22
1
3
4
2
16
16
35
35
9
0
Rangkain permanen cabang waktu
(1) 1-2 16
1-4 35
1-3
Rute terpendek menuju noda 3 ditarik dengan garis tebal, dan waktu terpendek menuju noda 3 (9 jam) berada dalam kotak.Ulangi langkah-langkah sebelumnya yang digunakan untuk menentukan rute terpendek menuju noda 3.Tentukan semua noda yang terhubung secara langsung dengan noda dalam rangkaian permanen (1 dan 3). Noda 2,4,6 semuanya terhubung secara langsung ke noda 1 dan 3.
Rangkain permanen cabang waktu
(1.3) 1-2
1-4 35
3-4 24
3-6 31
9
1
2
6
4
3
16
16
35
9 15
220
9
16
Langkah berikutnya adalah menentukan rute terpendek menuju tiga noda (2,4,dan 6) yang terhubung secara langsung pada noda rangkain permanen.Terdapat dua cabang yang berawal dari noda 2 (1-2 dan 1-4) dan dua cabang dari noda 3 (3-4 dan 3-6).Cabang terpendek adalah yang menuju noda 2, dengan waktu 16 jam .Jadi noda dua menjadi bagian dari rangkain permanen .Waktu menuju noda 6 (cabang3-6) adalah 31 jam, yang ditentukan dengan menambhakna waktu 22 jam dari cabang 3-6 ke waktu rute terpendek 9 jam di noda 3.
Langkah selanjutnya , rangkain permanen terdiri atas noda 1,2, dan 3.Tentukan noda mana yang terhubung secara langsung dengan noda rangkain permanen.Noda 5 adalah satu-satunya noda yang bersebelahan yang sekarang tidak terhubung dengan rangkaian permanen.Jadi noda tersebut dihubungkan secara langsung dengan noda 2.Selain itu noda 4 sekarang terhubung secara langsung dengan noda 2 (karena noda 2 telah terhubung dengan rangkaian permanen).
Rangkain permanen cabang waktu
(1,2.3) 1-4 35
2-4 28
2-5 41
3-4
3-6 31
2 5
6
4
3
1
16
24
9
16
25
1235
915
22
24
Jadi, rute terpendek menuju noda 4, dan noda ini terhubung dengan rangkain permanen.Perhatikan bahwa waktu terpendek menuju noda 4 (24jam) adalah rute dari noda 1 melalui noda 3.Rute lain yang menuju noda 4 dari noda 1 melalui noda2 ternyata lebih panjang , oleh karena itu tidak akan mempertimbangkan lebih jauh sebagai rute alternative menuju noda 4.
Kemudian, ulang kembali proses penentuan noda-noda yang terhubung secara langsung dengan noda-noda rangkain permanen.Noda-noda yang terhubung secara langsung adalah 5,6, dan 7.Cabang dari noda 1 dan 2 menuju noda 4 dihilangkan karena telah ditentukan bahwa rute dengan waktu terpendek menuju noda 4 tidak meliputi cabang tersebut.
Rangkaian permanen cabang waktu
(1,2,3,4) 2-5 41
3-6
4-5 38
4-7 43
4-6 41
Cabang-cabang yang menuju noda 5,6,7, cabang 3-6 mempunyai waktu kumulatif trependek, yaitu 31 jam.Jadi noda 6 ditambahkan ke dalam rangkaian permanen.Sehingga,
6
7
3
4
5
1
2
16
24
311
9
16
9 15
1419
17
22
31
telah menentukan rute terpendek menuju noda 1,2,3,4, dan 6.Noda-noda yang secara langsung terhubung(bersebelahan) dengan rangkaian permanen adalah noda 5 dan 7.Cabang 4 dan 6 dihilangkan karena rute terbaik menuju noda 6 adalah rute yang melalui noda 3 dan bukan melalui noda 4
.
Rangkain permanen cabang waktu
(1,2,3,4,6) 2-5 41
4-5
4-7 43
6-7 45
Dari cabang-cabang yang mengarah dari rangkaian permanen menuju noda 5 dan 7, cabang 4-5 mempunyai waktu kumulatif terpendek, yaitu 38 jam.Jadi noda 5 terhubung dengan rangkain permanen.Satu-satunya noda yang tersisa yang terhubung secara langsung dengan
7
6
5
4
3
1
2
16
38
24
9
31
16
25
915
1419
22
14
38
rangkaian permanen adalah noda 7.Drai ketiga cabang yang menghubungkan noda 7 pada rangkain permanen, cabang 4-7 mempunyai waktu terpendek, yaitu 43 jam.Oleh karena itu noda 7 terhubung dengan rangkain permanen.
Rangkain permanen Cabang waktu
(1,2,3,4,5,6) 4-7
6-7 45
5-7 46
Rute dengan waktu terpendek dari asal (noda 1) menuju ke-enam noda yang lain dan waktu tempuhnya, dapat diringkas sebagai berikut:
2
1
3
5
4
6
7
16
24
38
43
319
0
16
915
22
1419
14
8
43
516
38
Dari los Angels ke: Rute Total jam
Salt Lake City (noda2) 1-2 16
Phoenix (noda3) 1-3 9
Denver (noda4) 1-3-4 24
Des Moines (noda5) 1-3-4-5 38
Dallas (noda6) 1-3-6 31
St,Louis (noda7) 1-3-4-7 43
Langkah-langkah metode solusi rute terpendek adalah:
1.Pilih noda dengan rute langsung terpendek dari asal
2.Tetapkan sebuah rangkaian permanen dengan noda asal dan noda yang dipilih pada langkah 1
3.Tentukan semua noda yang erhubung secara langsung dengan noda rangkain permanen.
4.Pilih noda dengan rute(cabang) terpendek dari kelompok noda yang terhubung secara langsung dengan noda rangkaian permanen.
5.Ulangi langkah 3 dan 4 hingga semua noda terhubung dalam rangkaian permanen.
2.PERMASALAHAN POHON RENTANG MINIMAL
Permasalahan pohon rentang minimal adalah serupa dengan permasalahan rute terpendek kecuali bahwa tujuannya adalah untuk menghubungkan semua noda di dalam jaringan
6
74
3
1
224
43
319
0
16
9 15
1419
22
sehingga total panjang cabangnya terminimalkan. Jaringan yang dihasilkan merentang(menghubungkan) semua titik di dalam jaringan dengan total jarak (atau panjang) minimum.
Contoh, Metro Cable Television Company akan memasang sistem kabel televisi di komunitas yang terdiri atas tujuh kota satelit.Masing-masing kota satelit harus dihubungkan dengan sistem kabel utama.Perusahaan televisi kabel tersebut ingin meletakkan jaringan kabel utama dengan cara yang akan meminimalkan total panjang kabel yang harus dipasang.Kemungkinan jalur yang tersedia untuk perusahaan televise kabel tersebut(dengan persetujuandewan kota) dan jumlah kaki dari kabel(dalam ribuan kaki) yang dibutuhkan untuk tiap-tiap jalur seperti gambar di bawah ini.
Cabang dari noda 1 menuju noda 2 mewakili jalur kabel yang tersedia antara kota satelit 1 dan 2.Cabang tersebut membutuhkan 16.000 kaki kabel.
PENDEKATAN SOLUSI POHON RENTANG MINIMAL
Mulai dengan noda manapun di dalam jaringan dan dipilih noda yang terdekat untuk digabungkan dengan pohon rentang.Pilih noda yang terdekat dengan noda manapun di dalam area rentang.Dimulai dari noda 1, pilih noda yang paling dekat untuk bergabung dengan pohon rentang . Cabang terpendek dari noda 1 adalah menuju noda 3, dengan panjang 9( ribu kaki).
6
7
5
3
4
1
2
16
35
25
12
14
8
1915
9
17
22
5
7
63
4
1
2
16
35
9 15 1722
12
25
14
8
1914
Langkah berikutnya adalah dengan memilih noda terdekat yang sekarang belum berada dalam pohon rentang.Noda yang terdekat dengan noda 1 atau noda 3(noda-noda dalam pohon rentang sekarang) adalah noda 4.Dengan panjang 15.000 kaki.
Berikutnya, mengulang proses memilih noda yang terdekat dengan pohon rentang (noda 1, 2, dan 4).Noda terdekat yang sekarang belum terhubung dengan noda-noda didalam pohon rentang adalah noda 2.Panjang cabang dari noda 4 menuju noda 2 adalah 12.000 kaki.
6
7
5
4
3
1
216
25
12
35
15
917
22
14
19
8
14
52
16
12
25
14
8
Pohon rentang sekarang terdiri atas noda 1, 2, 3, dan 4.Noda yang terletak dengan pohon rentang ini adalah noda 5, dengan panjang cabang 14.000 kaki menuju noda 4.Jadi, noda 5 bergabung dengan pohon rentang.
Pohon rentang tersebut sekarang terdiri atas noda 1,2,3,4,dan 5.Noda terdekat yang belum terhubung dengan pohon rentang adalah noda 7.Cabang yang menghubungkan noda 7 ke noda 5 mempunyai panjang 8.000 kaki.
7
63
4
1
35
15
9
19
14
17
22
5
7
6
4
3
1
2
16
35
15
9
17
22
19
14
14
25
12 8
4 7
5
1
216
35
25
12
14
8
19
Sekarang pohon rentang meliputi noda 1,2,3,4,5, dan 7.Satu-satunya noda yang tersisa yang belum terhubung pada pohon rentang adalah noda 6.Noda di dalam pohon rentang yang terdekat dengan noda 6 adalah noda 7, dengan panjang cabang 14.000 kaki.Pohon rentang tersebut membutuhkan jumlah kabel televise minimum untuk menghubungkan ketujuh kota satelit tersebut -72.000 kaki.Pohon rentang minimal yang sama didapatkan dengan memulai di enam noda manapun selain dari noda 1.
Jaringan rute terpendek mewakili jalur terpendek antara asal dan tiap-tiap noda tujuan( yaitu, enam rute berbeda).Sebaliknya, jaringan pohon rentang minimal memperlihatkan cara untuk menghubungkan seluruh dari tujuh noda sehingga total jaraknya)panjangnya) terminimalkan.
Ringkasan, langkah-langkah dari metode solusi pohon rentang minimal:
1.Pilih noda awal mana pun(secara konvensional dipilih noda 1)
2.Pilih noda yang terdekat pada noda awal untuk bergabung dengan pohon rentang.
3.Pilih noda yang terdekat yang belum berada dalam pohon rentang.
4.Ulangi langkah 3 hingga semua noda telah bergabung dengan pohon rentang.
3. PERMASALAHAN ARUS MAKSIMAL
3
6
15
917
22
14
6
7
5
4
3
1
2
16
35
15
9
25
12
14
8
19
17
22
14
Tujuan dari jaringan ini adalah untuk memaksimal total jumlah arus dari asal ke tujuan. Permasalahan ini dirujuk sebagai permasalahan arus maksimal. Permasalahan arus maksimal dapat melibatkan air dan minyak yang melalui jaringan pipa atau arus lalu lintas yang melalui jalan raya. Masing-masing contoh tersebut cabang dari jaringan kapasitas arus terbatas dan berbeda. Dengan kondisi ini, pengambil keputusan dapat menentukan arus maksimum yang bisa didapatkan melalui sistem ini.
Suatu contoh suatu jaringan kereta api antara antara Omaha dan St. Louis yang tampak pada gambar. Scott Tractor Company mengirimkan bagian-bagian traktor dari Omaha ke St. Louis dengan kereta api. Tetapi jumlah gerbong dibatasi setiap cabang selama seminggu.
Dengan kondisi yang terbatas, perusahaan harus mengetahui jumlah maksimum gerbong kereta api yang dapat dikirim dari Omaha ke St. Louis selama seminggu. Jumlah gerbong kereta api yang tersedia untuk perusahaan tersebut diindikasikan dengan angka yang berada di sebelah kanan setiap noda iap noda (yang mewakili persimpangan rel). contoh, enam gerbong tersedia dari noda 1 menuju noda 2, delapan gerbong tersedia dari noda 2 menuju noda 5, lima gerbong tersedia dari noda 4 menuju noda 6 dan seterusnya. Angka yang berada di sebelah kiri adalah gorbang yang tersedia untuk pengiriman ke arah sebaliknya. Contoh dari noda 2 ke noda 1 tidak ada gerbong yang tersedia. Cabang dari noda 1 menuju noda 2 sebagai cabang berarah karena hanya ada 1 arah. Tetapi arus dapat dimungkinkan menjadi cabang tidak berarah contohnya cabang di antara noda 2 dan 4 serta noda 3 dan noda 4.
PENDEKATAN SOLUSI ARUS MAKSIMAL
Langkah pertama dalam menentukan arus yang maksimum adalah dengan memilih jalur manapun secara sembarang dari asal ke tujuan dan sebanyak mungkin pada jalur tersebut.
1
2
4
3
6
5
8
0
300 4
05
2
03
07
0 2
6
64
St. Louis
Masukan
Hasil
Omaha
Misalnya kita akan memilih jalur 1-2-5-6. Jumlah maksimum gerbong kereta api yang dapatdikirimkan melalui rute adalah empat.
Pada noda 1 menuju noda 2 dan dari noda 2 menuju noda 5 secara berturut-turut adalah dua dan empat gerbong dan tidak tersedia di noda 5 menuju noda 6. Nilai ini didapatkan dari mengurangkan arus empat gerbong dari jumlah awal yang tersedia. Arus aktual sebanyak emapat gerbong di sepanjang cabang diperlihatkan dalam kotak. Perhatikan bahwa masukan sekarang sebesar emapat gerbong menuju noda 1 dan hasil empat gerbongdari noda 6 juga ditentukan.
Penyesuaian trakhir pada jalur ini adalah dengan menambahkan yang telah arus yang telah ditentukan sebesar empat gerbong pada nilai tepat disebelah kiri dari setiap noda pada jalur kada jalur kita, 1-2-5-6. Ini adalah arus menuju ke arah sebaliknya. Jadi, nilai 4 ditambahkan pada nol di noda-noda 2,5 dan 6. Mungkin tampak tidak pada tempatnya untuk menetapkan arus ke arah yang tidak mungkin tetapi, ini adalaah cara yang digunakan dalam pendekatan solusi untuk menghitung arus bersih sepanjang sebuah cabang. (jika, sebagai contoh. Pengulangan di saat kemudian memperlihatkan arus saut gerbong dari noda 5 menuju noda 2, arus bersih ke arah yang benar akan dihitung dengan mengurangkan arus satu ke arah yang salah ini dari arus empat ke arah yang benar sebelumnya. Hasilnya adalah arus bersih tiga ke arah yang benar).
Kita sekarang telah menyelesaikan satu pengulangan dari proses solusi tersebut dan harus mengulang langkah-langkah sebelumnya. Sekali lagi, kita secara sembarang memilih suatu jalur. Kali ini kita akan emilih jalur 1-4-6, seperti yang tampak pada gambar. Arus maksimum di sepanjang jalur ini adalah empat gerbang, yang dikurangi di tiap-tiap noda. Hal ini meningkatkan total arus melalui jaringan tersebut menjadi delapan gerbong (karena arus empat sepanjang jalur 1-4-6 ditambahkan ke arus sebelumnya yang ditentukan dalam gambar)
1
2
4
3
6
5
8
0
300 4
05
2
03
07
0 2
6
64
4 4
2
04
4
44
44
4
Sebagai langkah akhir, arus empat gerbong ditambahkan pada arus d sepanjang jalur yang menuju arah sebaliknya pada noda 4 dan 6
Sekarang, kita secara sembarang memilih jalur yang lain. Kali ini, kita akan memilih jalur 1-3-6, dengan kemungkinan arus maksimum enam gerbong. Arus enam ini dikurangkan dari cabang-cabang si sepanjang jalur 1-3-6 dan ditambahkan pada cabang-cabang yan g menunju ke arah sebaliknya, seperti yang ada di gambar.
Arus 6 untuk jalur ini ditambahkan pada arus 8 sebelumnya, yang menghasilkan total arus sejumlah 14 gerbong kereta api.
Perhatikan bahwa pada titik ini jumlah jalur yang dapat kita ambil adalah terbatas. Sebagai contoh, kita tidak dapat mengambil cabang dari noda 3 menuju noda 6 karena
1
2
4
3
6
5
4
0
344 0
45
2
03
07
0 2
6
24
8 8
4 40 1 44
1
2
4
3
6
5
4
4
344 0
41
2
43
07
0 2
6
20
14
141
6
0
66 6
tersedia kapasitas arus nol. Demikian juga, tidak ada jalur yang meliputi cabang dari noda 1 menuju noda 4 yang memungkinkan.
Kapasitas arus yang tersedia di sepanjang jalur 1-3-4-6 adalah satu gerbong, seperti tampak pada gambar. Ini meningkatkan total arus dari 14 gerbong menjadi 15 gerbong. Jaringan hasilnya tampak pada gambar. Pengamatan yang lebih cermat terhadap jaringan dalam gambar memperlihatkan bahwa tidak ada jalur dengan kapasitas arus yang tersedia. Semua jalur yang keluar noda 3,4 dan 5 menunjukkan kapasitas tersedia nol, yang membuat tidak ada jalur lain lagi yang dalat melalui jaringan tersebut.
Dengan ini selsaikan solusi arus maksimalkan untuk permasalahan contuk permasalahan contoh kita. Arus maksimumnya adalah 15 gerbong kereta api. Arus yang akan terjadi di sepanjang tiap-tiap cabang muncul dalam kotak dalam gambar
Singkatannya, langkah-langkah metode solusi arus maksimum adalah :
1. Secara sebarang, pilih jalur manapun dalam jaringan dari asal ke tujuan2. Sesuaikan kapasitas di setiap noda dengan mengurangi arus maksimalkan untuk jalur
yang dipilih dalam langkah 1
1
2
4
3
6
5
4
4
344 0
414
3
61
6 2
0
20
15
150
71
1
11 32
0 5
1
2
4
3
6
5
4
5
344 0
404
3
60
7 1
0
20
44
4
415
15
7 6
5
13
0
3. Tambahkan arus maksimalkan di sepanjang jalur yang menuju arah sebalinya di setiap noda
4. Ulangi langkah 1, 2 dan 3 hingga tidak terdapat lagi jalur dengan kapasitas arus yang tersedia.
BAB III
KESIMPULAN
1.Jaringan adalah suatu pengaturan jalur yang menghubungkan berbagai titik menggunakan kendaraan.
2.Masalah rute terpendek adalah menemukan jarak terpendek antara titik asal dan beberapa titik tujuan.
3.Permasalahan pohon rentang minimal adalah untuk menghubungkan semua noda di dalam sebuah jaringan sehingga total panjang cabangnya terminimalkan.
4.Permasalahan arus maksimal adalah untuk memaksimalkan total jumlah arus dari satu asal ke suatu tujuan.