![Minimum Cost Flow 1 [PDF]](https://pdfs.asia/img/200x200/minimum-cost-flow-1.jpg)
8 0 922 KB
Penerapan Teori Graph untuk Pengoptimalan Masalah Pendistribusian Tabloid Media Umat di kota Malang dengan Metode Minimum Cost Flow LAPORAN
Oleh: Farid Ahmadi
(307312410080)
Bunga S Bintari
(308312410091)
Etika Wahyu Kartika
(308312417501)
Aldila Sakinah Putri
(408312408014)
UNIVERSITAS NEGERI MALANG FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM JURUSAN MATEMATIKA MARET 2011
ABSTRAK
Kelompok 5.2011. Penerapan Teori Graph Untuk Pengoptimalan Masalah Pendistribusian Tabloid Media Umat Di Kota Malang Dengan Metode Minimum Cost Flow. Laporan Jurusan Matematika, FMIPA, Universitas Negeri Malang. Dosen pembina Penerapan Teori Graph Dra. Sapti Wahyuningsih M.si. Kata Kunci: Metode, Algoritma, Penghapusan Sikel, Lintasan Terpendek Berulang, Jaringan Simplex, distribusi. Graph merupakan salah satu cabang matematika yang memiliki banyak aplikasi. Antara lain aplikasi penerapan Graph dalam kehidupan sehari- hari yaitu pemasanagan pipa PDAM, pewarnaan peta, masalah permintaan dan penawaran, minimalisasi jumlah perawat di rumah sakit dan lain sebagainya. Teori graph merupakan salah satu cabang matematika yang banyak manfaat karena teori-teorinya dapat diterapkan untuk memecahkan masalah dalam kehidupan sehari-hari. Salah satu masalah dalam kehidupan yang dapat dipecahkan dalam teori graph adalah masalah distribusi tabloid. Yang dimaksud dengan distribusi adalah penyelenggaraan kegiatan usaha yang tercakup dalam pengangkutan barang dari tempat pengolahan ke tempat penjualan. Persoalan distribusi menjadi sangat penting karena merupakan jalan untuk mencapai keberhasilan penjualan, dan kepuasan pelanggan. Masalah distribusi produk dapat digambarkan sebagai suatu digraph yang memuat beberapa sisi berarah dan titik. Titik mewakili agen atau konsumen yang masing-masing terletak di lokasi yang berbeda, sedangkan sisi mewakili arus distribusi. Suatu jaringan terdiri dari himpunan titik dan himpunan sisi berarah bermuatan yang menghubungkan dua titik tertentu, dimana masing-masing titik, sisi berarah dan muatan pada sisi berarah mewakili kondisi tertentu. Masalah arus biaya minimum adalah masalah penentuan arus distribuasi yang tepat agar biaya yang dikeluarkan minimum. Masalah arus biaya minimum berkorespondensi dengan masalah distribusi produk yang bertujuan untuk meminimumkan biaya distribusi produknya. Dengan mencoba berbagai kemungkinan arus distribusi, menghitung biaya yang diperlukan maka dapat diperoleh biaya minimum. Dalam permasalahan ini diperlukan beberapa teori pendukung antara lain: digraph, digraph bermuatan, jarak, lintasan, jaringan, jaringan berarah, aliran, dan jaringan berarah sisaan. Dan masalah ini dapat diselesaikan dengan Algoritma Penghapusan Sikel, Lintasan Terpendek Berulang,dan Algoritma Jaringan Simplex. Keadaan distribusi digambarkan dalam bentuk digraph Masalah optimasi yang akan dibahas dalam laporan ini adalah masalah arus biaya minimum. Masalah arus biaya minimum adalah masalah penentuan arus distribuasi yang tepat agar biaya yang dikeluarkan minimum. Masalah arus biaya minimum berkorespondensi dengan masalah distribusi produk yang bertujuan untuk meminimumkan biaya distribusi produknya. Dengan mencoba berbagai kemungkinan arus distribusi, menghitung biaya yang diperlukan sehingga dapat diperoleh biaya minimum
BAB I PENDAHULUAN
1.1 Latar Belakang Teori graph merupakan salah satu cabang matematika yang banyak manfaat karena teori-teorinya dapat diterapkan untuk memecahkan masalah dalam kehidupan sehari-hari (Purwanto, 1998:1). Salah satu masalah dalam kehidupan yang dapat dipecahkan dalam teori graph adalah masalah distribusi tabloid. Yang dimaksud dengan distribusi adalah penyelenggaraan kegiatan usaha yang tercakup dalam pengangkutan barang dari tempat pengolahan ke tempat penjualan (Woodward, 1982:1). Persoalan distribusi menjadi sangat penting karena merupakan jalan untuk mencapai keberhasilan penjualan, dan kepuasan pelanggan (Woodward, 1982:2). Keberhasilan penjualan dapat dilihat dari banyaknya penjualan atau kenaikan angka penjualan. Kepuasan pelanggan dapat disebabkan karena cepatnya produk sampai ke pelanggan dengan aman, tepat waktu, tidak rusak, sesuai pesanan pelanggan, dan murahnya harga penjualan. Salah satu faktor yang mendukung murahnya harga penjualan adalah biaya distribusi yang rendah, sehingga harga penjualan dapat ditekan menjadi lebih murah. Masalah distribusi produk dapat digambarkan sebagai suatu digraph yang memuat beberapa sisi berarah dan titik. Titik mewakili agen atau konsumen yang masing-masing terletak di lokasi yang berbeda, sedangkan sisi mewakili arus distribusi. Suatu jaringan terdiri dari himpunan titik dan himpunan sisi berarah bermuatan yang menghubungkan dua titik tertentu, dimana masing-masing titik, sisi berarah dan muatan pada sisi berarah mewakili kondisi tertentu. Masalah optimasi yang akan dibahas dalam kegiatan ini adalah masalah arus biaya minimum. Masalah arus biaya minimum adalah masalah penentuan arus distribuasi yang tepat agar biaya yang dikeluarkan minimum. Masalah arus biaya minimum berkorespondensi dengan masalah distribusi produk yang bertujuan untuk meminimumkan biaya distribusi produknya. Dengan mencoba berbagai
kemungkinan arus distribusi, menghitung biaya yang diperlukan maka dapat diperoleh biaya minimum. Dalam kegiatan ini kami menggunakan beberapa buku yang berhubungan dengan Minimum Cost Flow, laporan PKL yang sesuai dengan materi ini, dan beberapa artikel dari internet mengenai algoritma-algoritma yang dapat digunakan untuk menyelesaikan masalah Minimum Cost Flow. Contoh laporan PKL yang menerapan Minimum Cost Flow antara lain: 1.
Optimalisasi biaya distribusi tabung elpiji pada PT.Gading Mas Indah dengan menerapkan algoritma pada Minimum Cost Flow.
2.
Penerapan algoritma lintasan pendek berulang pada Minimum Cost Flow untuk pendistribusian surat dan barang PT. Pos Indonesia Blitar. Sedangakan buku yang digunakan antara lain:
1.
Handbook of Discrete and Combinatorial Mathematics oleh Kenneth H. Rosen.
2.
Teori Graph oleh Purwanto. Tabloid Media Umat merupakan salah satu media bacaan yang terdapat di
kota Malang. Setiap hari tabloid ini terdistribusi ke masyarakat. Dalam pendistribusiannya, tabloid ini tidak memperhatikan biaya yang dikeluarkan. Sehingga dianggap kurang maksimal dalam memperoleh keuntungan. Oleh karena itu, untuk meminimumkan biaya pendistribusian tabloid Media Umat dapat diselesaikan dengan menggunakan konsep Minimum Cost Flow. Sehingga dapat diperoleh biaya optimal.
1.2 Rumusan Masalah 1.
Algoritma apa saja yang digunakan untuk menentukan Minimum Cost Flow?
2.
Bagaimana menerapkan algoritma penghapusan sikel, lintasan terpendek berulang, dan jaringan simplex pada pendistribusian tabloid Media Umat?
3.
Bagaimana penyelesaian algoritma dengan menggunakan alat bantu?
1.3 Tujuan 1. Mengetahui Algoritma apa saja yang digunakan untuk menentukan Minimum Cost Flow. 2. Mengetahui cara menerapkan algoritma penghapusan sikel, lintasan terpendek berulang, dan jaringan simplex pada pendistribusian tabloid Media Umat. 3. Mengetahui penyelesaian algoritma dengan menggunakan alat bantu.
BAB II KAJIAN PUSTAKA
2.1. Teori Dasar 2.1.1. Graph Suatu Graph G terdiri atas himpunan tak kosong dari elemen-elemen yang disebut titik (vertex) dan suatu daftar pasangan tidak terurut elemen itu yang disebut sisi (edge). Himpunan dari titik-titik pada graph G disebut himpunan titik G, dinotasikan dengan V(G), dan daftar dari sisi-sisi disebut daftar sisi G, dinotasikan dengan E(G) (Wilson, 1990:10). Banyaknya titik pada graph G dinotasikan dengan | V (G) | dan banyaknya sisi pada graph G dinotasikan dengan |E(G)|. b e1
c e2
e7
e6
e8
d e3
a
e5
e
Gambar 1.1 Graph G
Dari Gambar 2.1 diatas dapat dilihat bahwa E (G) e1 , e2 , e3 , e4 , e5 , e6 , e7 , e8 sehingga
V (G) {a, b, c, d , e}
| V (G) | 5
dan
dan
| E (G ) | 8
.
Dua sisi atau lebih yang menghubungkan pasangan titik yang sama disebut sisi rangkap, dan sebuah sisi yang menghubungkan sebuah titik dengan dirinya sendiri disebut loop (Wilson, 1990:10).
2.1.2. Digraph Suatu digraph D terdiri atas suatu himpunan tak kosong yang masingmasing unsurnya disebut titik (vertex) dan suatu himpunan pasangan berurutan dari titik-titik tersebut yang disebut sisi berarah (arc). Himpunan dari titik-titik disebut himpunan titik dari D, dinotasikan dengan V(D), dan daftar dari sisi-sisi berarah disebut daftar sisi-sisi berarah dari D, dinotasikan dengan A(D).
Contoh: c
b
d a
e Gambar 2.1 Digraph D
2.1.3. Lintasan (Path) Lintasan (path) adalah jalan yang sisi dan titiknya tidak boleh berulang.
2.1.4. Sikel Sikel adalah jalan (v0,v0) = v0v1v2...vnv0 dengan n ≥ 0 dan vi ≠ vj, jika i ≠ j.
2.1.5. Digraph Bermuatan Suatu digraph D = (V,A) dikatakan digraph bermuatan (weighted digraph) jika setiap sisi berarah pada digraph D diberikan muatan jika v1v2 adalah sisi berarah pada digraph D = (V,A) maka muatan v1v2 dilambangkan dengan w (v1 , v2 ) .
Contoh: b
c
2
3
3 2
2 3
a
d 3
2
e
Gambar 2.3 Digraph bermuatan D
w(a,b) = 2
w(a,e) = 2
w(b,c) = 2
w(b,e) = 3
w(c,d) = 3`
w(c,a) = 3
w(c,e) = 2
w(e,d) = 3
2.1.6. Jaringan (Network) Jaringan (dilambangkan N) adalah digraph sederhana, bermuatan, jika memenuhi: o Satu titik yang merupakan titik sumber, tidak memiliki sisi masuk. o Satu titik yang merupakan titik tujuan, tidak memiliki sisi keluar. o Muatan sisi (i,j) disebut kapasitas sisi(i,j), dilambangkan cij dengan cij adalah bilangan bulat non negatif. (Johsohnbaugh, 2001:391)
2.1.7. Minimum Cost Flow Definisi 2.1: Misal g = (V,E) adalah jaringan terhubung dengan himpunan titik V dan himpunan sisi berarah E. Masing-masing sisi (i,j) E mempunyai harga cij dan kapasitas muatan uij 0. Misal n =
V
dan m = E . Masing-masing titik i V
mempunyai nilai yang disimbolkan b(i). Jika b(i) > 0, maka titik i adalah titik pemberi; jika b(i) < 0, maka titik i adalah titik penerima. (Rosen: 2000) Harga adalah bilangan bulat non negatif yang menyatakan besarnya biaya untuk memindahkan muatan dari satu titik ke titik yang lain. Kapasitas dari suatu sisi adalah jumlah maksimum muatan yang dapat dialirkan melalui sisi-sisi. (Rosen, 2000:630) Definisi 2..2: Suatu aliran fisibel adalah suatu fungsi x = (vij) didefinisikan pada sisi berarah (i,j) E memenuhi :
Batas kesetimbangan umum :
Batas kapasitas :
0 xij u ij
x
ij { j ( i , j )E }
x
ji { j ( j ,i )E }
b(i) untuk semua i V,
untuk semua (i,j) E, dimana b(i) 0 . iV
Harga dari flow x adalah cij xij . (Rosen, 2000:673-674). ( i , j )E
Definisi 2.3: Jaringan sisa G(x) dalam suatu aliran x didefinisikan dalam sebagai berikut: Mengganti masing-masing sisi berarah (i,j) E oleh dua sisi berarah (i,j) dan (j,i). Sisi berarah (i,j) mempunyai harga cij dan kapasitas sisa rij = uij- xij, dan sisi berarah (j,i) mempunyai harga –cij dan kapasitas sisa rij = xij. (Rosen, 2000: 673-674). Definisi 2.4: Potensial titik i adalah besarnya
(i )
yang bersesuaian dengan batas
kesetimbangan umum pada titik i. Untuk himpunan potensial titik yang diberikan, biaya tereduksi dari suatu sisi (i,j) pada jaringan sisaan G(x) adalah cij cij (i ) ( j ) .
Definisi 2.5: Kondisi Optimal Kendala Komplemen: Misal x adalah solusi spanning tree fisibel dengan potensial titik yang diperlukan yaitu
(1)
0
dan
cij 0
untuk semua sisi pada pohon. Maka x
adalah minimum cost flow jika:
cij 0
untuk semua sisi (i,j) yang bukan pohon dengan
xij 0
cij 0
untuk semua sisi (i,j) yang bukan pohon dengan
xij uij
Definisi 2.6: Harga dari lintasan P dalam G(x) adalah c(P) = cij . (Rosen, 2000:674) ( i , j )P
Harga dari lintasan adalah jumlah harga pada setiap sisi dalam lintasan P. Definisi 2.7: Suatu sikel negatif adalah suatu sikel terhubung W dalam G(x) dimana c(W )
c
( i , j )W
ij
0.
(Rosen, 2000:674).
Definisi 2.8: Kondisi optimal sikel negatif adalah suatu aliran fisibel x yang disebut aliran berharga minimum jika dan hanya jika jaringan sisa G(x) tidak memuat sikel negatif. (Rosen, 2000:674)
2.2. Algoritma-Algoritma Minimum Cost Flow 2.2.1. Algoritma Penghapusan Sikel Algoritma Penghapusan Sikel merupakan salah satu metode dalam menyelesaikan masalah optimasi model jaringan. Algoritma Penghapusan Sikel didasarkan dari kondisi optimal sikel negatif, yang dimulai dengan aliran fisibel dan penambahan berturut-turut sikel negatif dalam jaringan sisaan sampai jaringan sisaan tersebut tidak memuat sikel negatif. Berikut ini adalah algoritma penghapusan sikel : 1.
Tentukan nilai aliran (xij) berdasarkan 0≤xij≤uij dan bi=∑xij-∑xji
2.
Ganti arc (i,j) dengan dua arc (i,j) dan (j,i). Arc (i,j) memiliki harga cij dan kapasitas sisaan rij=uij-xij. Sedang arc (j,i) memiliki harga –cij dan kapasitas rij=xij. Jika rij=0 hapus arc yang bersesuaian.
3.
Cari sikel negatif. Jika tidak ada maka sikel optimal.
4.
Jika ada, tambah aliran sepanjang sikel negatif terpilih dengan rij terkecil pada sikel tersebut. Kurangi uij disepanjang sikel dan naikkan kapasitas arc sebaliknya dari sikel tersebut sebesar rij terkecil dalam sikel.
5.
Ulangi langkah 3 sampai tidak ada sikel negatif maka solusi optimal.
2.2.4. Algoritma Lintasan Terpendek Berulang Algoritma Lintasan Terpendek Berulang merupakan salah satu metode lain dalam menyelesaikan masalah optimasi model jaringan. Algoritma Lintasan Terpendek Berulang didasarkan dari kondisi optimal jaringan sisaan, dimulai dengan digraph awal yang telah disederhanakan dan berturut-turut mencari lintasan terpendek sampai muatan pada titiknya bernilai nol. Berikut ini adalah Algoritma Lintasan Terpendek Berulang: 1.
Cari lintasan dari s ke t pada jaringan kerja
2.
Cari sebarang lintasan terpendek dari s ke t sebut P
3.
Cari δ=min{b(s),-b(t), min{rij I (i,j) є P}}
4.
Kurangi uij pada lintasan terpendek P dengan δ
5.
Ulangi langkah 2 sampai b(s) dan b(t) sama dengan nol.
2.2.4. Algoritma Jaringan Simplek Berikut ini adalah Algoritma Jaringan Simplek : 1. Pilih sebarang spanning tree (T) 2. Cari aliran xij dan potensial titik Π 3. Jika ada arc non basis (non tree) melanggar komplementary slackness kondisi optimal, pilih untuk masuk tree dan keluarkan arc basis dengan x ij yang bila ditambahkan ke kapasitasnya menjadi batas atas. 4. Ulangi langkah 2 sampai tidak ada arc yang melanggar complementary slackness kondisi optimal.
2.2.4. Algoritma Shorthess Augmenting Path Algoritma ini tergolong baru. Oleh karena itu, penjelasannya belum terlalu mendetail. Pada dasarnya algoritma ini mirip dengan algoritma successive shortest path, hanya saja pencarian lintasan terpendek dalam algoritma ini menggunakan algoritma dijkstra. Selain itu, keunggulan algoritma ini dapat menghitung minimum cost dari maksimum flow dari s ke t.
2.2.5 Algoritma Cost-Scaling Kita mulai dengan fungsi biaya nol dan sebarang maksimum flow. Setiap tingkatan scaling kita mulai dari residual arc (ε) dari hasil optimalisasi maksimum flow ke (ε/2) optimal maksimum flow. Untuk memulai tiap tingkatan scaling kita akan menjenuhkan semua biaya negatif dari residual arc. Kebaikan dari algoritma ini adalah bisa digunakan untuk menghitung kapasitas yang bukan merupakan bilangan bulat. Contoh penerapan algoritma:
Sebuah perusahaan mempunyai 1 pabrik, 2 pusat distribusi, 1 tempat penjualan.
Pabrik tersebut memproduksi 40.000 produk
2 pusat distribusi sebagai tempat penyimpanan sementara, sehingga kapasitasnya 0.
Tempat penjualan mampu menerima produk sebanyak 40.000
Biaya pengangkutan (per unit) adalah
Dari pabrik ke pusat distribusi I
: Rp. 20.000,-
Dari pabrik ke pusat distribusi II
: Rp. 20.000,-
Dari pusat distribusi I ke pusat distribusi II
: Rp. 10.000,-
Dari pusat distribusi I ke pusat penjualan
: Rp. 30.000,-
Dari pusat distribusi II ke pusat penjualan
: Rp. 10.000,-
Kapasitas armada pengangkutan: Dari pabrik ke pusat distribusi I
: Rp. 40.000,-
Dari pabrik ke pusat distribusi II
: Rp. 20.000,-
Dari pusat distribusi I menuju pusat distribusi II
: Rp. 20.000,-
Dari pusat distribusi I menuju pusat penjualan
: Rp. 30.000,-
Dari pusat distribusi II menuju pusat penjualan : Rp. 50.000,Langkah 1 Penggambaran keadaan distribusi produk perusahaan tersebut adalah 0
PD I (20000,40000)
40000
(30000,30000)
(10000,20000)
Pabrik (20000,20000)
TP
-40000
(10000,50000)
PD II 0
Karena masing-masing kapasitas maupun biaya dapat disederhanakan dengan membagi dengan 10.000 dan Pabrik diberi indeks 1 PD I diberi indeks 2 PD II diberi indeks 3 Pusat penjualan diberi indeks 4 Maka akan diperoleh keadaan produk dalam bentuk yang lebih sederhana, yaitu:
0
2 (3,3) (2,4)
(1,2)
1
4
4
(2,2)
-4
(1,5)
3 0
Langkah 2 : Nilai Produk yang didistribusikan xij dapat ditentukan dari nilai kemampuan masing-masing titik untuk memberi atau menerima b(i) dan kapasitas maksimum dan b(i)
pengangkutan uij dengan ketentuan Penentuan nilai xij-nya adalah dari syarat Untuk
,
diperoleh
Untuk
,
diperoleh
Untuk
,
diperoleh
Untuk
,
diperoleh
Untuk
,
diperoleh
Untuk
diperoleh ( )
(
)
Untuk
diperoleh ( )
(
)
ij { j ( i , j )E }
x
ji { j ( j ,i )E }
, sehingga:
x
Dengan syarat b(i)
x
ij { j ( i , j )E }
x
ji { j ( j ,i )E }
, sehingga: , maka , maka
(pers. 1) (
)
(
)
(pers. 2) Untuk ( Untuk (pers. 4)
diperoleh ( )
(
), maka
) (pers. 3) diperoleh ( )
(
), maka
Misalkan
, maka dari pers. 1, (
maka dari pers. 2, dengan memisalkan (
akan diperoleh
)
akan diperoleh
, maka didapat
)akan diperoleh
adalah
,
, maka dari pers. 4,
, sehingga nilai
,
,
yang mungkin
dan
Gambar dari aliran fisibel tersebut adalah sebagai berikut: 0
2 3 3 4
4
0
1
-4
1
1
3 0
Langkah 3 : Jaringan sisaan diperoleh dari digraph awal yag dimodifikasi dengan cara mengganti setiap sisi ( i, j) dengan dua sisi ( i, j) dan ( j, i). Sisi ( i , j) punya harga cij dan kapasitas sisa
sedangkan sisi ( j, i) mempunyai harga –cij
dan kapasitas sisa Sisi (
) mempunyai harga
Sisi (
) mempunyai harga
Sisi (
) mempunyai harga
Sisi (
) mempunyai harga
Sisi (
) mempunyai harga
Sisi (
) mempunyai harga
Sisi (
) mempunyai harga
Sisi (
) mempunyai harga
Sisi (
) mempunyai harga
Sisi (
) mempunyai harga
dan dan dan dan dan dan dan dan dan dan
Gambar jaringan sisaan: 0
2 (-3,3)
(-2,3)
(3, 0)
(2,1) 4
1
4
(-1,0)
(1,2)
-4
(1,4) (2,1) (-1,1) (-2,1)
3 0
Langkah 4: Nilai
berarti tidak ada arus distribusi produk dari titik i ke titik j sehingga
penghapusan sisi ini tidak berpengaruh terhadap arus distribusi produk total dalam jaringan. Penghapusan sisi berkapasitas
bermanfaat untuk memudahkan
dalam menentukan sikel-sikel pada jaringan. Penghapusan sisi berkapasitas juga dapat dilakukan diantara langkah-langkah yang lain. 0
2 (-3,3)
(-2,3) (2,1) 4
1
4
(1,2)
-4
(1,4) (2,1) (-1,1) (-2,1)
3 0
Langkah 5: Menentukan sikel W yang bernilai negatif ( ( ) sehingga jaringan sisaan tidak memuat sikel negatif.
) dan mereduksinya
0
2 (-3,3)
(-2,3) (2,1) 4
1
4
(1,2)
-4
(1,4) (2,1) (-1,1) (-2,1)
3 0
Iterasi 1 Sikel-sikel yang termuat dalam jaringan sisaan tersebut adalah [1231], [2342], [13421]. Sikel W = [1231] mempunyai nilai
( )
, sehingga W = [1231] bukan sikel negatif. Sikel W = [2342] mempunyai nilai ( )
,
sehingga W = [2342] merupakan sikel negatif. Sikel W = [13421] mempunyai nilai ( )
, sehingga W
= [13421] merupakan sikel negatif. *
Pilih sikel W= [2342] dengan
+
*
+
Menambahkan
pada aliran yang berlawanan dengan sikel W dan
mengurangkan
pada aliranyang searah dengan sikel W, sehingga
didapat G(x) seperti pada gambar berikut: 0
2 (3,2)
(-2,3)
(-3, 1)
(2,1) 4
4
(-1,2)
1
(1,2) (2,1) (-1,3) (-2,1)
3 0
-4
Iterasi 2: Berdasarkan iterasi 1 diperoleh sikel yang bernilai negatif adalah sikel W = [13421] dengan nilai ( )
dan
sikel W = [1231] dengan nilai ( ) *
Pilih sikel W =[13421] dengan dengan *
+
+ Tambahkan
mengurangkan
pada aliran yang berlawanan dengan sikel W dan pada aliranyang searah dengan sikel W, sehingga didapat
G(x) seperti pada gambar berikut: 0
2 (-3,0)
(-2,2)
(3,3)
(2,2) 4
4
(-1,2)
1
-4
(1,1) (2,0) (-1,4) (-2,2)
3 0
Karena jaringan tersebut masih memuat nilai
, maka nilai
tersebut
dapat dihilangkan sehingga 0
2 (-2,2) (3,3)
(2,2) 4
4
(-1,2)
1
(1,1) (-1,4) (-2,2)
3 0
-4
0
2 (3,3)
(-2,2)
(-3, 0)
(2,2) 4
4
(-1,2)
1
-4
(-1,1) (-1,4) (-2,2)
3 0
Jaringan sisaan G(x) yang terbentuk dari iterasi kedua ini sudah tidak memuat sikel bernilai negatif sehingga sesuai dengan kondisi optimum sikel negatif maka G(x) tersebut merupakan solusi yang optimum. Langkah 6: Masalah arus distribusi produk mempunyai fungsi tujuan, yaitu meminimumkan ∑
(
)
, sehingga biaya pengangkutan yang diperlukan minimum.
cij menunjukkan harga pengangkutan atau biaya yang diperlukan dari titik i ke titik j, sedangkan xij didapat dari rij yang mempunyai harga negatif. 0
2 4
(-2,2) (3, 3)
(2,2)
4
(-1,2)
1
(1,1) (-1,4) (-2,2)
3 ∑
0
-4
Jadi nilai minimum yang dibutuhkan untuk mendistribusikan produk dari perusahaan ke tempat penjualan pada contoh tersebut adalah Rp (14 x 10000 x 10000) = Rp 1400000000,-. Nilai 10000 x 10000 diperoleh dari penyederhanaan pada awal langkah dimana biaya dibagi 10000 dan kapasitas pengangkutan juga dibagi 10000.
2.3 Penelitian yang sudah dilakukan 1.
Berdasarkan Praktek Kerja Lapangan yang dilakukan oleh Binti isroul fauziah dengan laporan yang berjudul “Penerapan Algoritma Lintasan Pendek Berulang Pada Minimum Cost Flow Untuk Pendistribusian Surat Dan Barang PT. Pos Indonesia Blitar”, pada tahun 2006 dengan menggunkan alat bantu giden diperoleh hasil sebagai berikut. Hasil perhitungan biaya distribusi surat dan barang PT. Pos indonesia blitar dengan menggunakan rute mobil sesuai keadaan di lapangan, biaya distribusi yang dibutuhkan untuk wilayah timur sebesar 1.431.700 dan wilayah barat sebesar 1.547.200. hasil ini diperoleh dengan menggunakan lintasan terpendek berulang. Rute pengiriman terbentuk wilayah timur adalah dari kantor pos pusat ke KPC 1 (Nglegok) – KPC 2 (garum) – KPC 3 (talun) – KPC 4 (Gandusari) – KPC 5 (wlingi) – KPC 6 (doko) – KPC 7 (kesamben) – KPC 8 (Binangun) dan untuk wilayah barat adalah dari kantor pos pusat ke KPC 1 (kanigoro) – KPC 2 (lodoyo) – KPC 3 (kademangan) – KPC 4 (sanamkulon) – KPC 5 (ponggok) – KPC 6 (srengat) – KPC 7 (wono dadi) – KPC 8 (udanawu).
2.
Berdasarkan Praktek Kerja Lapangan yang dilakukan oleh Marta Yulian S dengan laporan yang berjudul “Optimalisasi Biaya Distribusi Tabung Elpiji Pada PT.Gading Mas Indah Dengan Menerapkan Algoritma Pada Minimum Cost Flow”, pada tahun 2006. Diperoleh hasil sebagai berikut. Untuk tabung gas elpiji 12 kg biaya distribusi produknya sebesar Rp 157.487, hasil tersebut diperoleh dengan menggunakan algoritma penghapusan sikel, algoritma lintasan terpendek berulang, algoritma jaringan simpleks. Rute yang diperoleh dengan menggunakan algoritma penghapusan sikel adalah gudang ke tandan, gudang ke pom, pom ke toko laba tlogomas,
pom ke BC 7 dan toko laba ke toko top, sedangkan dengan menggunakan algoritma lintasan terpendek berulang dan algoritma simpleks adalah gudang ke tandon, gudang ke pom, gudang ke toko laba, pom ke BC 7 dan toko laba ke toko top. Fakta di lapangan pengiriman tabung gas elpiji dilakukan setiap hari dengan melewati setiap toko yang memesan tabung gas maupun yang tidak memesan. Untuk pengiriman tabung gas elpiji 12 kg rute yang ditempuh adalah gudang-tandon-pom tlogomas-toko laba-BC 7-toko top-gudang dengan biaya Rp 750.000. Untuk pengiriman tabung gas elpiji 50 kg rute yang ditempuh adalah gudang-RST sopraoen-Bandulan-Pandanlandung-PG Konagung-Depot 59-RM nikmat lezat-Pecinan-Gudang dengan biaya sebesar Rp 750.000.
2.4 Daftar Pustaka JohsohnBaugh, R. 2001. Discrete Mathematics. New Jersey : Prentice Hall, Inc. Purwanto. 1998. Teori Graph. Malang : FPMIPA IKIP MALANG. Rosen, H., Kenneth. Handbook of Discrete and Combinatorial Mathematics. Washington, D. C. : CRC Press. Woodward, H., Frank. 1972. Manajemen Transpor. Terjemahan oleh Ny. P. Hadinoto. 1982. Jakarta: Pustaka Binaman Pressindo. Zealint. 2007. Minimum Cost Flow, Part 2: Algorithms, (Online), (www.topcoder.com/tc?module=Static&d1=tutorials&d2=minimum CostFlow2 - 54k - Cached, diakses 14 Februari 2011, pukul 15:00)
BAB III METODOLOGI KEGIATAN
3.1 Waktu dan Tempat 3.1.1 Waktu Pelaksanaan Kegiatan survey dilaksanakan pada tanggal 10 Februari 2011 sesuai dengan waktu yang diberikan oleh instansi.
3.1.2 Tempat Pelaksanaan Adapun instansi yang ditunjuk sebagai lokasi sebagai objek penelitian adalah Redaksi Tabloid “Media Ummat” Jl. Wilis No. 11 Malang .
3.1.3 Waktu Pelaksanaan Kegiatan survey pada tanggal 10 Februari 2011 dilaksanakan pada pukul 10.30-12.00.
3.1.4 Sumber Data Data yang digunakan diperoleh dari staf redaksi Tabloid “Media Ummat”. Adapun
data-data
yang
diperlukan
dalam
penelitian
ini
yaitu
lokasi
pendistribusian, biaya distribusi, jalur pendistribusian, jumlah permintaan Tabloid Media Ummat. Berikut beberapa objek yang akan kita kaji: a. Nama- nama agen yang berperan sebagai titik. b. Jalur pendistribusian yang dilalui berperan sebagai sisi. c. Biaya pengiriman dan kapasitas muatan sebagai bobot.
3.2 Algoritma yang digunakan: 4.3.1 Algoritma Penghapusan Sikel Algoritma Penghapusan Sikel merupakan salah satu metode dalam menyelesaikan masalah optimasi model jaringan. Algoritma Penghapusan Sikel didasarkan dari kondisi optimal sikel negatif, yang dimulai dengan aliran fisibel dan penambahan berturut-turut sikel negatif dalam jaringan sisaan sampai jaringan sisaan tersebut tidak memuat sikel negatif. Berikut ini adalah algoritma penghapusan sikel : 1. Tentukan nilai aliran (xij) berdasarkan 0≤xij≤uij dan bi=∑xij-∑xji 2. Ganti arc (i,j) dengan dua arc (i,j) dan (j,i). Arc (i,j) memiliki harga cij dan kapasitas sisaan rij=uij-xij. Sedang arc (j,i) memiliki harga –cij dan kapasitas rij=xij. Jika rij=0 hapus arc yang bersesuaian. 3. Cari sikel negatif. Jika tidak ada maka sikel optimal. 4. Jika ada, tambah aliran sepanjang sikel negatif terpilih dengan rij terkecil pada sikel tersebut. Kurangi uij disepanjang sikel dan naikkan kapasitas arc sebaliknya dari sikel tersebut sebesar rij terkecil dalam sikel. 5. Ulangi langkah 3 sampai tidak ada sikel negatif maka solusi optimal.
4.3.2 Algoritma Lintasan Terpendek Berulang Algoritma Lintasan Terpendek Berulang merupakan salah satu metode lain dalam menyelesaikan masalah optimasi model jaringan. Algoritma Lintasan Terpendek Berulang didasarkan dari kondisi optimal jaringan sisaan, dimulai dengan digraph awal yang telah disederhanakan dan berturut-turut mencari lintasan terpendek sampai muatan pada titiknya bernilai nol. Berikut ini adalah Algoritma Lintasan Terpendek Berulang: 1. Cari lintasan dari s ke t pada jaringan kerja 2. Cari sebarang lintasan terpendek dari s ke t sebut P 3. Cari δ=min{b(s),-b(t), min{rij I (i,j) є P}} 4. Kurangi uij pada lintasan terpendek P dengan δ 5. Ulangi langkah 2 sampai b(s) dan b(t) sama dengan nol.
4.3.3 Algoritma Jaringan Simplek Berikut ini adalah Algoritma Jaringan Simplek : 1.
Pilih sebarang spanning tree (T)
2.
Cari aliran xij dan potensial titik Π
3.
Jika ada arc non basis (non tree) melanggar komplementary slackness kondisi optimal, pilih untuk masuk tree dan keluarkan arc basis dengan x ij yang bila ditambahkan ke kapasitasnya menjadi batas atas.
4.
Ulangi langkah 2 sampai tidak ada arc yang melanggar complementary slackness kondisi optimal
3.3
Alat Bantu Program Dalam menentukan Minimum Cost Flow dapat digunakan beberapa alat
bantu. Alat bantu yang digunakan adalah Giden. Adapun langkah-langkah menggunakan Giden adalah sebagai berikut: Pilih menu File-New
Untuk menggambar titik, pilih New Node
Untuk menggambar sisi, pilih New Edge
Untuk merubah nama titik dan sisi, pilih Edit Value
Pilih Solvers-Minimum Cost Flow-Pilih algoritma yang diperoleh maka akan mumcul hasil yang diinginkan.
BAB IV HASIL SURVEI
4.1 Hasil Data Data yang diperoleh dari survei di lapangan adalah 1. Lokasi pendistribusian tabloid Media Ummat sebagai titik-titik pada graf dan jumlah permintaan tabloid sebagai bobot titik yaitu: Tabel 1 lokasi
Jumlah permintaan
pusat
5600
Kec. Klojen
1320
Kec. Lowokwaru
840
Kec. Blimbing
1400
Kec. Kedungkandang
640
Kec. Sukun
1400
2. Biaya pengangkutan dan kapasitas armada sebagai bobot sisi
Biaya pengangkutan adalah Dari pusat ke klojen
: Rp. 5.000,-
Dari pusat ke lowokwaru
: Rp. 30.000,-
Dari pusat ke Blimbing
: Rp. 27.000,-
Dari pusat ke Kedungkandang
: Rp. 32.000,-
Dari pusat ke Sukun
: Rp. 20.000,-
Dari klojen ke Sukun
: Rp. 11.000,-
Dari lowokwaru ke Sukun
: Rp. 38.000,-
Dari lowokwaru ke Blimbing
: Rp. 12.000,-
Dari Kedungkandang ke Blimbing
: Rp. 35.000,-
Dari kedungkandang ke Sukun
: Rp. 29.000,-
Kapasitas armada pengangkutan: Dari pusat ke klojen
: 300
Dari pusat ke lowokwaru
: 300
Dari pusat ke Blimbing
: 300
Dari pusat ke Kedungkandang
: 300
Dari pusat ke Sukun
: 300
Dari klojen ke Sukun
: 300
Dari lowokwaru ke Sukun
: 300
Dari lowokwaru ke Blimbing
: 300
Dari Kedungkandang ke Blimbing
: 300
Dari kedungkandang ke Sukun
: 300
4.2 Model Graph
Klojen
Lowokwaru
Sukun
Pusat Blimbing
Kedungkandang
4.3 Hasil Perhitungan 4.3.1
Menggunakan Algoritma Penghapusan Sikel
Dengan perhitungan manual
1. Penentuan nilai aliran fisibel xij Penentuan nilai xij-nya adalah dari syarat 0 untuk i=1, j=2 diperoleh 0
x12
300
untuk i=1, j=3 diperoleh 0
x13
300
untuk i=1, j=4 diperoleh 0
x14 300
untuk i=1, j=5 diperoleh 0
x15 300
untuk i=1, j=6 diperoleh 0
x16
300
untuk i=2, j=6 diperoleh 0
x26
300
untuk i=3, j=4 diperoleh 0
x34
300
untuk i=3, j=6 diperoleh 0
x36
300
untuk i=5, j=4 diperoleh 0
x54
300
untuk i=5, j=6 diperoleh 0
x56
300
dan syarat b(i) =
x
ij { j ( i , j )E }
x
ji { j ( j , i )E }
.,
xij
uij sehingga diperoleh
sehingga diperoleh:
untuk i = 1 diperoleh b(1) = 560 = x12 + x13 + x14 + x15+ x16……..(1)
untuk i = 2 diperoleh b(2) = - 132 = x26 - x12 ……........................(2)
untuk i = 3 diperoleh b(3) = - 84 = x34 + x36 - x13….......................(3)
untuk i = 4 diperoleh b(4) = - 140 = - x14 - x34 - x54……...............(4)
untuk i = 5 diperoleh b(5) = - 64 = x56 + x54 – x15....................….(5)
untuk i = 6 diperoleh b(6) = - 140 = - x16 - x26 - x36 – x56……........(6)
Dari persamaan (1) misalkan x12 = 140, x13 = 100, x14 = 120, x15 = 100 maka diperoleh: x54 = 120 Dari persamaan (2) x26 - 140 = - 132 X26 = 8 Dari persamaan (3) misalkan x34 = 10 maka diperoleh: x36 + 10 - 100 = - 84 x36 = 6 Dari persamaan (4) -120 – 10 – x54 = - 140 X54 = 10 Dari persamaan (5) x56 + 10 - 100 = - 64 x56 = 26 sehingga diperoleh: x12 = 140
x26 = 8
x13 = 100
x34 = 10
x14 = 120
x36 = 6
x15 = 100
x54 = 10
x16 = 100
x56 = 26
Sehingga gambar aliran fisibel tersebut adalah
2. Penentuan jaringan sisaan G(x) Jaringan sisaan G(x) dalam suatu aliran x didefinisikan sebagai mengganti masing-masing sisi(i,j) dengan dua sisi berarah (i,j) dan (j,i). Sisi berarah (i,j) mempunyai harga cij dan kapasitas sisa rij = uij - xij, dan sisi berarah (j,i) mempunyai harga -cij dan kapasitas sisa rij = xij.
Sisi (1,2) mempunyai harga : c12 = 5 dan r12 = 160
Sisi (2,1) mempunyai harga : c21 = -5 dan r21 = 140
Sisi (1,3) mempunyai harga : c13 = 30 dan r13 = 200
Sisi (3,1) mempunyai harga : c31 = -30 dan r31 = 100
Sisi (1,4) mempunyai harga : c14 = 27 dan r14 = 180
Sisi (4,1) mempunyai harga : c41 = -27 dan r41 = 120
Sisi (1,5) mempunyai harga : c15 = 32 dan r15 = 200
Sisi (5,1) mempunyai harga : c51 = -32 dan r51 = 100
Sisi (1,6) mempunyai harga : c16 = 20 dan r16 = 200
Sisi (6,1) mempunyai harga : c61 = -20 dan r61 = 100
Sisi (2,6) mempunyai harga : c26 = 11 dan r26 = 292
Sisi (6,2) mempunyai harga : c62 = -11 dan r62 = 8
Sisi (3,4) mempunyai harga : c34 = 12 dan r34 = 290
Sisi (4,3) mempunyai harga : c43 = -12 dan r43 = 10
Sisi (3,6) mempunyai harga : c36 = 38 dan r36 = 294
Sisi (6,3) mempunyai harga : c63 = -38 dan r63 = 6
Sisi (4,5) mempunyai harga : c45 = -35 dan r45 = 10
Sisi (5,4) mempunyai harga : c54 = 35 dan r54 = 290
Sisi (6,5) mempunyai harga : c65 = 29 dan r65 = 274
Sisi (5,6) mempunyai harga : c56 = -29 dan r56 = 26 Diperoleh jaringan sisaan berikut:
3. Penghapusan sisi berkapasitas rij = 0 Tidak ada nilai rij = 0 sehingga langkah ini bias dilewati. 4. Menentukan sikel w yang negative (c (w) < 0) dan mereduksinya sehingga jaringan sisaan tidak memuat sikel negative. Iterasi 1 Jaringan sisaan yang terbentuk masih memuat sikel negative. Salah satu sikel negatifnya adalah [1 2 6 1] dengan c(w) = -5. Sikel negative tersebut mempunyai nilai = min {160, 292, 100} = 100 Tambahkan = 100 ke aliran yang berlawanan arah dengan sikel tersebut dan kurangkan = 100 ke aliran yang searah dengan sikel tersebut, kemudian menghapus sisi yang berkapasitas rij = 0 diperoleh jaringan sisaan sebagai berikut:
Iterasi 2 Jaringan sisaan yang terbentuk masih memuat sikel negative. Salah satu sikel negatifnya adalah [1 4 3 1] dengan c(w) = -15. Sikel negative tersebut mempunyai nilai = min {120, 10, 100} = 10 Tambahkan = 10 ke aliran yang berlawanan arah dengan sikel tersebut dan kurangkan = 10 ke aliran yang searah dengan sikel tersebut, kemudian menghapus sisi yang berkapasitas rij = 0 diperoleh jaringan sisaan sebagai berikut:
Iterasi 3 Jaringan sisaan yang terbentuk masih memuat sikel negative. Salah satu sikel negatifnya adalah [1 4 5 1] dengan c(w) = -40. Sikel negative tersebut mempunyai nilai = min {170, 10, 100} = 10 Tambahkan = 10 ke aliran yang berlawanan arah dengan sikel tersebut dan kurangkan = 10 ke aliran yang searah dengan sikel tersebut, kemudian menghapus sisi yang berkapasitas rij = 0 diperoleh jaringan sisaan sebagai berikut:
Iterasi 4 Jaringan sisaan yang terbentuk masih memuat sikel negative. Salah satu sikel negatifnya adalah [1 2 6 5 1] dengan c(w) = -45. Sikel negative tersebut mempunyai nilai = min {60, 192, 26, 60} = 26 Tambahkan = 26 ke aliran yang berlawanan arah dengan sikel tersebut dan kurangkan = 26 ke aliran yang searah dengan sikel tersebut, kemudian menghapus sisi yang berkapasitas rij = 0 diperoleh jaringan sisaan sebagai berikut:
Iterasi 5 Jaringan sisaan yang terbentuk masih memuat sikel negative. Salah satu sikel negatifnya adalah [1 2 6 3 1] dengan c(w) = -52. Sikel negative tersebut mempunyai nilai = min {34, 166, 6, 100} = 6 Tambahkan = 6 ke aliran yang berlawanan arah dengan sikel tersebut dan kurangkan = 6 ke aliran yang searah dengan sikel tersebut,
kemudian
menghapus sisi yang berkapasitas rij = 0 diperoleh jaringan sisaan sebagai berikut:
5. Penentuan nilai optimum Gambar terakhir merupakan solusi optimum. Nilai fungsi tujuan dari distribusi produk adalah Z =
x c
ij ij
= x12c12 + x13c13 + x14c14 + x15c15 + x26c26 = 572 ∙ 5 + 84 ∙ 30 + 140 ∙ 27 + 64 ∙ 32 + 140 ∙ 11 = 11248 Jadi biaya minimum dalam sekali distribusi adalah Rp. 11248,-. Dengan menggunakan program Giden Iterasi 1
Iterasi 2
Iterasi 3
Iterasi 4
Iterasi 5
Iterasi 6 k
4.3.2
Menggunakan Algoritma Lintasan Terpendek Berulang
Dengan Penghitungan Manual
a. Menetukan Lintasan Terpendek - Dipilih titik s dan t yaitu titik 1 dan 2 Lintasan terpendek s ke t adalah [1,2] * ( ) *
( )
{
}+
+
Diperoleh jaringan sisaan yang terbentuk dari lintasan terpendek [1,2]
- Dipilih titik s dan t yaitu titik 1 dan 3 Lintasan terpendek s ke t adalah [1,3] * ( )
( )
*
{
}+
+
Diperoleh jaringan sisaan yang terbentuk dari lintasan terpendek [1,3]
- Dipilih titik s dan t yaitu titik 1 dan 4 Lintasan terpendek s ke t adalah [1,4] * ( ) *
( )
{
}+
+
Diperoleh jaringan sisaan yang terbentuk dari lintasan terpendek [1,4]
- Dipilih titik s dan t yaitu titik 1 dan 5 Lintasan terpendek s ke t adalah [1,5] * ( )
( )
*
{
}+
+
Diperoleh jaringan sisaan yang terbentuk dari lintasan terpendek [1,5]
- Dipilih titik s dan t yaitu titik 1 dan 6 Lintasan terpendek s ke t adalah [1,2,6] * ( ) *
( )
{
}+
+
Diperoleh jaringan sisaan yang terbentuk dari lintasan terpendek [1,6]
Karena jaringan sisaan pada gambar terakhir muatan semua titiknya sudah nol, maka jaringan jaringan pada gambar terakhir merupakan solusi optimum dengan aliran
dengan nilai
b. Menentukan Nilai Optimum
negatif.
Dengan menggunakan Program Giden
Iterasi 1
Iterasi 2
Iterasi 3
Iterasi 4
Iterasi 5
Iterasi 6
4.3.3
Menggunakan Algoritma Simplek Dengan Penghitungan Manual
1. Menentukan Spanning Tree
Iterasi 1 Kemudian menentukan nilai -
Nilai
()
-
-
Nilai ( ) ( )
( )
( )
( )
( )
( )
-32
Nilai ()
()
Ada sisi yang bukan pohon melanggar definisi (nilainya < 0) yaitu sisi (2,6) sehingga jaringan belum optimum. Masukkan sisi (2,6) ke pohon sehingga menghasilkan sikel [1261], kemudian keluarkan sisi (1,2). Tambahkan nilai
pada
yang searah dan kurangkan pada
berlawanan arah, sehingga diperoleh ( ) Sehingga diperoleh gambar:
yang
Iterasi 2 Kemudian menentukan nilai -
Nilai
-
Nilai ( )
-
()
( )
( )
( )
( )
( )
( )
-32
Nilai ()
()
Ada sisi yang bukan pohon melanggar definisi (nilainya < 0) yaitu sisi (1,2) sehingga jaringan belum optimum. Masukkan sisi (1,2) ke pohon sehingga menghasilkan sikel [1261], kemudian keluarkan sisi (1,6). Tambahkan nilai
pada
yang searah dan kurangkan pada
berlawanan arah, sehingga diperoleh ( ) ( )
Sehingga diperoleh gambar:
yang
Iterasi 3 Kemudian menentukan nilai -
Nilai
-
Nilai ( )
-
()
( )
( )
( )
( )
( )
( )
Nilai ()
()
-32
Karena semua sisi nilai
memenuhi definisi maka jaringan sudah
optimum. 2. Penentuan Nilai Optimum Solusi optimum diperoleh dengan gambar sebagai berikut:
Nilai fungsi tujuan dari distribusi produk adalah ∑
(
)
(
)
(
)
(
)
(
)
Dengan menggunakan program Giden
Iterasi 1
4.4 Analisis Hasil Dari ketiga algoritma yang digunakan diperoleh biaya minimum yang diperlukan untuk pendistribusian Tabloid Media Ummat sebesar Rp 11.248 yaitu dengan rincian sebagai berikut: Tabel 2
Aliran distribusi
cost
capacity
Dari pusat ke klojen
: Rp. 5.000,-
272
Dari pusat ke lowokwaru
: Rp. 30.000,-
84
Dari pusat ke Blimbing
: Rp. 27.000,-
140
Dari pusat ke Kedungkandang
: Rp. 32.000,-
64
Dari pusat ke Sukun
: Rp. 20.000,-
0
Dari klojen ke Sukun
: Rp. 11.000,-
140
Dari lowokwaru ke Sukun
: Rp. 38.000,-
0
Dari lowokwaru ke Blimbing
: Rp. 12.000,-
0
Dari Kedungkandang ke Blimbing
: Rp. 35.000,-
0
Dari kedungkandang ke Sukun
: Rp. 29.000,-
0
Tabel 3 Algoritma yang digunakan
Biaya minimum
Rute yang ditempuh
Penghapusan sikel
Rp 11. 248
Pusat ke Klojen ke Sukun, Pusat ke lowokwaru, Pusat ke Blimbing, Pusat ke Kedungkandang
Lintasan terpendek berulang
Rp 11. 248
Pusat ke Klojen ke Sukun, Pusat ke lowokwaru, Pusat ke Blimbing, Pusat ke Kedungkandang
Metode simplek
Rp 11. 248
Pusat ke Klojen ke Sukun, Pusat ke lowokwaru, Pusat ke Blimbing, Pusat ke Kedungkandang
BAB V KESIMPULAN DAN SARAN
5.1 Kesimpulan Dari pengamatan di lapangan mengenai biaya distribusi Tabloid Media Ummat, kesimpulan yang dapat diperoleh adalah: Tabel 3 Algoritma yang digunakan
Biaya minimum
Rute yang ditempuh
Penghapusan sikel
Rp 11. 248
Pusat ke Klojen ke Sukun, Pusat ke lowokwaru, Pusat ke Blimbing, Pusat ke Kedungkandang
Lintasan terpendek berulang
Rp 11. 248
Pusat ke Klojen ke Sukun, Pusat ke lowokwaru, Pusat ke Blimbing, Pusat ke Kedungkandang
Metode simplek
Rp 11. 248
Pusat ke Klojen ke Sukun, Pusat ke lowokwaru, Pusat ke Blimbing, Pusat ke Kedungkandang
5.2 Saran 1. Rute pengiriman Tabloid Media Ummat yang telah didapatkan dapat digunakan sebagai pertimbangan perusahaan sehingga biaya pendistribusian menjadi minimum. 2. Perhitungan biaya distribusi dapat digunakan sebagai bahan pertimbangan perusahaan untuk menentukan biaya operasional harian. 3. Program Giden yang digunakan dapat dijadikan sebagai alternatif untuk menghitung biaya pendistribusian Tabloid Media Ummat.
LAMPIRAN
Pengalaman Survei (Farid) Tabloid Media Ummat merupakan tabloid yang berada dalam lingkungan pesantren. Banyak pengalaman yang diperoleh dari survey yang telah dilakukan ke tempat ini. Dari segi lingkungan terasa berbeda. Lingkungan di tempat ini terasa aroma pesantren begitu kental, pegawai putra mayoritas memakai sarung dan kopyah sedangkan yang putri berjilbab rapi. Berbeda dengan lingkungan dari kampus yang umumnya beragam. Kami datang ke tempat dengan 2 personil yang berpenampilan agak berbeda. Keduanya tidak berkerudung dan berpenampilan agak nyentrik sehingga membuat kelompok kami agak canggung masuk dalam lingkungan yang mirip pesantren. Awalnya kelompok kami agak canggung berhadapan dengan para penerus ajaran Nabi Muhammad SAW tersebut, tapi ternyata mereka menyambut kami dengan baik dan ramah. Selain sambutan mereka yang menyenangkan, salah satu personil kelompok kami mengerti bahasa ala pesantren sehingga komunikasi antara kelompok kami dengan pihak instansi bisa berjalan. Dari sinilah kami menemukan pentingnya kerjasama dalam tim. Dari survey yang kami lakukan, kami merasakan bahwa survey tersebut merupakan langkah yang harus ditempuh sebagai langkah awal dalam mempersiapkan PKL. Dari pengalaman yang diperoleh dari survey akan banyak membantu dalam pencarian tempat PKL, penentuan tempat PKL, dan pelaksanaan PKL. Dari survey ini juga kami dapat merasakan bahwa ternyata kita tidak bisa sembarangan dalam mencari tampat PKL. Kami juga dapat merasakan bahwa mencari tempat PKL saja butuh perjuangan apalagi mencari kerja.
Pengalaman Survei (Bunga) Survei dilakukan pada hari kamis tanggal 10 Februari 2011 sekitar pukul 10.30 setelah mendapat izin dari bu Sapti karena dilakukan pada jam kuliah terapan graph. Kami berempat berangkat ke tempat survei yaitu redaksi tabloid
Media Ummat yang terletak di jalan wilis bersama-sama, dengan mengendarai sepeda motor berboncengan dua-dua. Karena jalan wilis tidak terlalu jauh dari kampus UM jadi perjalanan tidak terlalu lama, sekitar 15 menit kami sudah sampai di tempat lokasi. Kesan pertama saat tiba di lokasi adalah kesan sederhana yang terlihat. Tempatnya bersebelahan dengan tempat praktek seorang dokter. Ketika masuk kami disambut oleh salah satu staf, dan seorang staf perempuan. Para staf redaksi media ummat sangat ramah pada kami. Mereka melayani kami dengan baik. Hal pertama yang mereka minta adalah surat tugas dari pihak kampus, kemudian mereka melihat proposal survei kami dan sambil staf tersebut membaca proposal, kami menerangkan maksud tujuan kami ke tempat tersebut. Dan alhamdulilah beliau paham apa yang kami inginkan. Dengan senang hati beliau memberikan data yang kami inginkan. Pengalaman survey ini sebagai latihan bagi saya untuk melaksanakan kegiatan PKL berikutnya. Alur dalam kegiatan ini tidak jauh berbeda dengan alur untuk melaksanakan kegiatan PKL sehingga sedikit banyak saya sudah mendapat gambaran tentang apa yang harus saya lakukan nanti ketika akan melaksanakan kegiatan PKL.
Pengalaman Survei (Etika) Tabloid Media Ummat merupakan tabloid yang berada dalam lingkungan pesantren. Di tempat inilah pertama kali saya melakukan dan merasakan bagaimana survey. Banyak pengalaman yang diperoleh dari survey yang telah dilakukan ke tempat ini. Pertama merasa canggung karena tempat suvey yang kami kunjungi merupakan Tabloid Media Ummat, yang pastinya kental dengan keislamannya, sedangkan saya tidak berjilbab. Padahal pegawai putra mayoritas memakai sarung dan kopyah sedangkan yang putri berjilbab rapi. Untungnya salah satu anggota dari kelompok kami sudah mengenali salah satu pegawai yang ada di Tabloid Media Ummat, jadi kelompok kami tidak merasa mengalami kesulitan ataupun kendala untuk mendapatkan data yang kami perlukan. Dan yang mengejutkan salah satu dari pegawai Tabloid Media Ummat
adalah alumni dari UM, jadi mereka bisa memaklumi kedatangan kami yang bermaksud untuk meminta data. Survey yang kami lakukan ini juga sebagai latihan nanti ketika saya akan melaksanakan PKL, dengan survey ini saya bisa mengerti bagaimana nantinya jika kita akan melaksanakan PKL, karena pada survey ini benar-benar alur yang dilakukan seperti pada PKL, dari yang mulai membuat proposal, meminta surat keterangan, membuat surat izin survey, hingga pada akhirnya membuat laporan survey. Pengalaman Survei (Aldila) Berada di jalan Wilis No. 11 Malang, merupakan tempat yang strategis untuk menjadi pusat penerbitan Tabloid Media Ummat. Tabloid Media Ummat adalah salah satu tabloid terbaik yang beredar di masyarakat dengan genre tabloid bernuansa islami. Karena begitu terkenalnya, tabloid ini banyak diminati masyarakat, khususnya santri-santri pesantren yang ingin belajar ilmu agama secara lebih mendalam. Tak heran sebegitu terkenalnya, Tabloid Media Ummat banyak beredar sampai ke luar kota Malang. Setelah membuat proposal dan surat izin survey, kami segera melakukan survey lapangan. Survey yang kami lakukan berjalan cukup lancar. Karena pada hari sebelumnya salah satu anggota kelompok sudah melakukan perjanjian dengan salah satu pegawai, sehingga ketika berada disana kami diberi data-data secara langsung. Pegawai yang baik dan ramah adalah salah satu pendukung suksesnya survey kali ini, karena kebaikan hatinyalah kami bisa mendapatkan data secara lengkap. Data yang diberikan meskipun lengkap namun kami masih memilahmilih data mana yang akan kami gunakan dikarenakan batasan masalah yang kami buat terbatas hanya dalam kota Malang. Tujuan dilakukan survey kali ini tidak hanya untuk penyusunan laporan saja, namun lebih khususnya bertujuan untuk membantu redaksi bagaimana cara melakukan pendistribusian tabloid dengan biaya paling minimum. Sehingga dapat meminimumkan pengeluaran dan meningkatkan pendapatan dari pembendaharaan Tabloid Media Ummat.
