minimum cost flow

1

LAPORAN OBSERVASI

Penerapan Teori Graph untuk Pendistribusian Keripik Apel di Kota Batu

dengan Metode Minimum Cost Flow

Untuk memenuhi tugas matakuliah Penerapan Teori Graph yang dibimbing

oleh Dra. Sapti Wahyuningsih,M.Si

Oleh:

Cindy Meilinda Wijaya (409312417678)

Andrie Kurniawan M. (409312417687)

Tofan Adityawan (409312417690)

UNIVERSITAS NEGERI MALANG

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

JURUSAN MATEMATIKA

FEBRUARI 2012

2

DAFTAR ISI

BAB I PENDAHULUAN

1.1.Latar Belakang ···························································· 1

1.2.Rumusan Masalah ························································ 2

1.3.Tujuan Masalah··························································· 3

BAB II KAJIAN TEORI

2.1. Graf ········································································· 4

2.2. Digraf ······································································· 4

2.3. Mininimum Cost Flow ·················································· 6

2.4. Algoritma pada Minimum Cost Flow ································ 8

2.4.1. Algoritma Penghapusan Sikel ································· 9

2.4.2. Algoritma Lintasan Terpendek································ 9

2.4.3. Algoritma Jaringan Simpleks ·································· 9

2.4.4. Algoritma Shortest Augmenting Path ························ 9

2.4.5. Algoritma Cost Scaling ·········································· 9

2.5. Penelitian yang sudah dilakukan ····································· 10

2.6. Daftar Pustaka···························································· 19

BAB III METODOLOGI

3.1. Waktu dan tempat pelaksanaan ······································ 20

3.1.1. Waktu Pelaksanaan ·············································· 20

3.1.2. Tempat Pelaksanaan ············································· 20

3.1.3. Sumber data ······················································· 20

3.2. Algoritma yang digunakan ············································· 20

3.2.1. . Algoritma Penghapusan Sikel ································ 20

3.2.2. Algoritma Lintasan Terpendek································ 21

3.2.3. Algoritma Jaringan Simpleks ·································· 21

3.3. Alat Bantu Program ····················································· 21

BAB IV PEMBAHASAN

4.1. Narasi ······································································ 25

4.2. Penyelesaian Masalah Dengan Algoritma ·························· 27

3

4.2.1.Menggunakan Algoritma Penghapusan Sikel ··············· 27

4.2.2.Menggunakan Algoritma Jaringan Simpleks ··············· 35

4.2.3.Menggunakan Algoritma Lintasan Terpendek Berulang 38

4.3. Penyelesaian dengan Alat Bantu ······································ 42

4.4. Analisa Hasil ······························································ 51

BAB V KESIMPULAN DAN SARAN

5.1. Kesimpulan ································································ 53

5.2. Saran ······································································· 54

Lampiran ······································································· 55

4

ABSTRAK

Kelompok 5.2012.Penerapan Teori Graph Untuk Pendistribusian Keripik Apel Ramayana di

Kota Batu 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, Lintasan Terpendek Berulang, Jaringan Simplex,

Penghapusan sikel, Distribusi.

Graph merupakan salah satu cabang matematika yang banyak memiliki manfaat terutama

dalam kehidupan sehari hari seperti pendistribusian keripik apel.Distribusi disini adalah suatu

penyelenggaraan kegiatan usaha yang tercakup dalam pengangkutan barang dari tempat

pengolahan ketempat penjualan. Persoalan distribusi menjadi sangatpenting karena merupakan

jalan untuk mencapai keberhasilan penjualan, dan kepuasan pelanggan.

Distribusi produk disini digambarkan sebagai digraph yang memuat sisi berarah dan

titik. Titik dapat diartikan sebagai, sedangkan sisi diartikan arus distribusi. 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 sangat berkaitan dengan masalah

distribusi produk yang membuat biaya untuk pendistribusiannya minimum.

Beberapa teori yang mendukung antara lain: digraph, digraph bermuatan, jarak, lintasan,

jaringan, jaringan berarah, aliran, dan jaringan berarah sisaan. Dan masalah ini dapat

diselesaikan dengan AlgoritmaLintasan Terpendek Berulang,dan Algoritma Jaringan Simplex.

Keadaan distribusi digambarkan dalam bentuk digraph.

Laporan ini membahas terutama masalah pengoptimalisaian pengiriman produk, dengan

mengamati cara pendistribusiannya serta biaya yang diperlukan dan dengan memanfaatkan

algoritma algoritma dalam arus biaya minimum akan didapatkan suatu biaya pendistribusian

yang minimum.

5

BAB 1

PENDAHULUAN

1.1 Latar Belakang

Pada sekarang ini telah banyak kita jumpai berbagai jenis makanan ringan yang beredar di

pasaran salah satunya adalah keripik apel khas malang. Banyaknya para penjual makanan ringan

yang sejenis dengan keripik apel membuat daya saing produk ini menjadi meningkat. Oleh

karena itu setiap perusahaan menginginkan sebuah pengiriman makanan seperti keripik apel

tersebut dengan waktu yang sesingkat mungkin. Dan hal ini membuat banyak distributor keripik

mengalami masalah dalam hal pengirimannya kepada masing- masing pelanggannya.

Perusahaan keripik apel merupakah sebuah perusahaan yang bekera di bidang makanan,

khususnya makanan ringan. Dalam upaya mencapai keberhasilan penjualan dan kepuasan

pelanggan, persoalan distribusi sangat penting. Keberhasilan penjualan dapat dilihat dari

banyaknya penjualan atau kenaikan angka penjualan. Kepuasan pelanggan dapat disebabkan

cepatnya produk sampai ke pelenggaan dengan aman, tepat waktu dan tidak rusak, sesuai dengan

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.

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). Persoalan distribusi menjadi sangat penting karena merupakan jalan untuk mencapai

keberhasilan penjualan, dan kepuasan pelanggan (Woodward, 1982:2). Untuk menekan biaya

pengiriman barang, kita dapat menggunakan graph yaitu dengan menggunakan penerapan teori

graph yaitu dengan menggunakan minimim cost flow. Minimum cost flow adalah penentuan arus

distribusi yang tepat agar biaya yang dikeluarkan minimum. Pada prinsipnya, minimum cost

flow dapat digunakan sebagai unsur perencanaan pengoptimalan distribusi produk. Minimum

cost flow berkorespondensi dengan masalah distribusi produk yang bertujuan untutk

meminimumkan biaya distribusi produknya dalam hal ini yaitu keripik apel.

6

Terdapat beberapa metode atau algoritma yang dapat digunakan untutk menyelesaikan

permasalahan minimum cost flow. Antara lain dengan menggunakan algoritma penghapusan

sikel, algoritma jaringan simplek dan algoritma lintasan terpendek berulang . Dengan metode ini

diharapkan dapat membantu meminimalkan biaya distribusi di perusahaan keripik apel tersebut.

Untuk menyelesaikan masalah Minimum Cost Flow. Contoh laporan PKL yang menerapan

Minimum Cost Flow antara lain:

1. Optimalisasi biaya distribusi dengan menggunakan penerapan Minimum Cost Flow pada

pendistribusian elpiji 3 kg di UD Dwi Tunggal Jaya untuk wilayah Kota Madya Malang.

2. Optimalisasi pendistribusian knalpot di pabrik Fajar Indah Malang dengan

menggunakan metode Minimum Cost Flow.

3. Penerapan teori graph untuk pengoptimalan masalah pendistribusian “Brem Candi Mas”

di Madiun dengan metode Minimum Cost Flow.

sedangkan buku yang digunakan antaralain:

a. Handbook of Discrete and Combinatorial Mathematics oleh Kenneth H. Rosen.

b. Teori Graph oleh Purwanto.

1.2 Rumusan Masalah

Dari latar belakang yang telah diuraikan di atas, maka adapun rumusan masalahnya

1. Bagaimana mengidentifikasikan permasalahan yang ada dalam pendistribusian

keripik apel?

2. Bagaimana menentukan biaya minimum dalam pendistribusian kripik apel dengan

menerapkan Algoritma Minimum Cost Flow?

3. Bagaimana memberikan solusi alternatif dengan menggunakan alat bantu Giden

pada permasalahan pendistribusian dengan biaya minimum?

7

1.3 Tujuan Penulisan

Adapun tujuan dari pelaksanaan observasi adalah :

o Identifikasi permasalahan yang ada dalam pendistribusian keripik apel.

o Menerapkan algoritma-algoritma Minimum Cost Flow untuk meminimumkan

biaya pendistribusian keripik apel.

o Memberikan solusial alternatif untuk mendapatkan rute pendistribusian keripik

apel dengan biaya minimum.

8

BAB II

KAJIAN TEORI

2.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 | )(GV | dan banyaknya sisi pada

graph G dinotasikan dengan |E(G)|.

Dari Gambar 1.1 diatas dapat dilihat bahwa },,,,{)( edcbaGV dan

87654321 ,,,,,,,)( eeeeeeeeGE sehingga 5|)(| GV dan 8|)(| GE .

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.2 Digraph

Suatu digraph D terdiri atas suatu himpunan tak kosong yang masing-masing 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).

a

b c

d

e

e1

e2

e3

e5

e6

e7 e8

Gambar 1.1 Graph

G

9

Contoh:

a. Lintasan (Path)

Lintasan (path) adalah jalan yang sisi dan titiknya tidak boleh berulang.

b. Sikel

Sikel adalah jalan (v0,v0) = v0v1v2...vnv0 dengan n ≥ 0 dan vi ≠ vj, jika i ≠ j.

c. 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 ),( 21 vvw Contoh:

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

b c

b c 2

3

3

3

3

2 2

d

e a

Gambar 2.1 Digraph

d

e a 2

Gambar 2.2Digraph bermuatan D

10

d. Jaringan (Network)

Jaringan (dilambangkan N) adalah digraph sederhana, bermuatan, jika

memenuhi:

Satu titik yang merupakan titik sumber, tidak memiliki sisi masuk.

Satu titik yang merupakan titik tujuan, tidak memiliki sisi keluar.

Muatan sisi (i,j) disebut kapasitas sisi(i,j), dilambangkan cij dengan cij

adalah bilangan bulat non negatif. (Johsohnbaugh, 2001:391)

2.3 Minimum Cost Flow

Definisi 2.3.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 ijc dan kapasitas

muatan 0iju . Misal n V menyatakan jumlah titik dan m E menyatakan jumlah

sisi.

Masing-masinh titik i V mempunyai nilai yang disimbolkan ( )b i . Jika

( ) 0b i , maka i adalah titik pemberi.

( ) 0b i , maka i adalah titik penerima. (Rosen: 2000)

Harga adalah bilangan bulat non negatif yang menyatakan besarnya biaya untuk

memindahkan muatan dari satu titik ke titik lain. Kapasitas dari suatu sisi adalah

jumlah maksimum muatan yang dapat dialirkan melalui sisi-sisi. (Rosen, 2000:630)

Definisi 2.3.2

Suatu aliran feasible adalah suatu fungsi ( )ijx v didefinisikan pada sisi berarah

( , )i j E , yang memenuhi :

Batas kesetimbangan umum : { ( , ) } { ( , ) }

( ), ,ij ij

j i j E j j i E

x x b i i E

Batas kapasitas umum : 0 , ( , ) , dimana ( ) 0.ij ij

i V

x u i j E b i

11

Harga dari flow x adalah ( , )

.ij ij

i j E

c x

.

Definisi 2.3.3

Jaringan sisa ( )G x dalam suatu aliran x didefinisikan sebagai berikut :

Mengganti masing-masing sisi berarah ( , )i j E oleh dua sisi berarah ( , ) dan ( , )i j j i .

Sisi berarah ( , )i j mempunyai harga ijc dan kapasitas sisa

ij ij ijr u x , dan sisi

berarah ( , )j i mempunyai harga ijc dan kapasitas sisa

ij ijr x .

Definisi 2.3.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 ( ) ( )ij ijc c i j .

Definisi 2.3.5

Kondisi optimal kendala komplemen :

Misal x adalah solusi spanning tree fesibel dengan potensial titik yang diperlukan

yaitu (1) 0 dan 0ijc untuk semua sisi pada pohon. Maka x adalah minimum cost

flow jika :

0, ( , ) yang bukan pohon dengan 0ij ijc i j E x

0, ( , ) yang bukan pohon dengan ij ij ijc i j E x u

Definisi 2.3.6

Harga dari lintasan P dalam ( )G x adalah ( , )

( ) ij

i j P

c P c

.

Harga dari lintasan adalah jumlah harga pada setiap sisi dalam lintasan P .

12

Definisi 2.3.7

Suatu sikel negatif adalah suatu sikel terhubung W dalam ( )G x dimana

( , )

( ) 0ij

i j W

c W c

.

Definisi 2.3.8

Kondisi optimal sikel negatif adalah suatu aliran feasibel x yang disebut aliran

berharga minimum jika dan hanya jika jaringan sisa ( )G x tidak memuat sikel negatif.

2.4 Algoritma Pada Minimum Cost Flow

2.4.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 yang negatif, yang dimulai dengan aliran

fesibel 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.

Pemilihan sikel yang dimaksud adalah sikel sederhana (sikel yang tidak

memuat sisi berulang maupun titik berulang) dan untuk selanjutnya penulisan

sikel mengandung arti sikel sederhana.

13

2.4.2 Algoritma Lintasan Pendek Berulang

Untuk menyelesaikan asalah aliran biaya minimum (Minimum Cost Flow),

digunakan algoritma Succesive Shortest Path atau Lintasan Pendek

Berulang, dengan langkah-lakngkah sebagai berikut :

1. Mencari lintasan dari S ke T pada jaringan kerja

2. Mencari sebarang lintasan terpendek dari S ke T, kita sebut T

3. Mencari min{ ( ), ( ),min{ ( , ) }}ijb s b t r I i j P

4. Kurangi jiu pada lintasan terpendek P dengan

5. Ulangi langkah 2 sampai b(s) dan b(t) sama dengan nol.

2.4.3 Algoritma Jaringan Simplek

Berikut ini adalah Algoritma Jaringan Simplek :

a. Pilih sebarang spanning tree (T)

b. Cari aliran xij dan potensial titik Π

c. Jika ada arc non basis (non tree) melanggar komplementary slackness kondisi

optimal, pilih untuk masuk tree dan keluarkan arc basis dengan xij yang bila

ditambahkan ke kapasitasnya menjadi batas atas.

d. Ulangi langkah 2 sampai tidak ada arc yang melanggar complementary

slackness kondisi optimal.

2.4.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.4.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.

14

2.5 Penelitian yang Sudah Dilakukan

a. Berdasarkan Praktek Kerja Lapangan yang dilakukan oleh Rina Uktafiya dengan

laporan yang berjudul “Optimalisasi Biaya Distribusi dengan Menggunakan

Penerapan Minimum Cost Flow pada Pendistribusian Elpiji 3 Kg di UD Dwi

Tunggal Jaya untuk Wilayah Kota Madya Malang” pada tahun 2011 yang

menggunakan alat bantu Giden diperoleh hasil sebagai berikut.

Hasil perhitungan menggunakan algoritma penghapusan sikel dengan bantuan

giden menghasilkan total biaya distribusi dengan rute pendistribusian sesuai

keadaan lapangan adalah sebesar Rp 56.445,-. Sedangkan pada hasil di lapangan

yang dilakukan olehUD Dwi Tunggal Jaya Malang total biaya distribusi sebesar

Rp.140.000,- . UD Dwi Tunggal Jaya Malang – Solikim (Jl. Cindelaras No. 7) –

Neni (Jl. Tebo Tengah No. 2) – Emi (Jl. Bandulan Baru No. 94) – Ashari (Jl. IR.

Rais Gang IV) – Athena (Jl. Brigjend Katamso No. 16) – Sulaiman (Jl. S.

Supriyadi Gang V) – Mulyono (Jl. K.H. Wahid Hasyim No. 18) – Salon “Lina”

(Jl. Kawi No. 3C) – Sormin (Jl. Klampok Kasri Gang 2D).

b. Berdasarkan Praktek Kerja Lapangan yang dilakukan oleh Setya Widodo dengan

laporan berjudul “Optimalisasi Pendistribusian Knalpot di Pabrik Fajar Indah

Malang dengan Menggunakan Metode Minimum Cost Flow” pada tahun 2011

yang menggunakan alat bantu Program Giden V4a diperoleh hasil sebagai

berikut. Hasil perhitungan menggunakan algoritma succesive shortest

pathdengan bantuan giden diperoleh biaya minimum pengiriman knalpot yaitu

Rp 18.425.000,-. Dari hasil pengolahan data diatas didapat pengoptimalan biaya

distribusi dari sebesar Rp 18.425.000,- menjadi Rp 2.039.275,-. Dengan rute

Bandung –Jakarta, Malang – Solo, Solo –Yogyakarta, Malang – Yogyakarta,

Malang – Surabaya, Semarang – Bandung, Yogyakarta – Bandung, Solo –

Bandung, Surabaya – Semarang.

c. Berdasarkan Praktek Kerja Lapangan yang dilakukan oleh Dewi Ratna Ayu

Wulaningrum drengan judul laporan beerjudul”Penerapan Teori Graph untuk

Pengoptimalan Masalah Pendistribusian Brem Candi Mas di Madiun dengan

Metode Minimum Cost Flow “ pada tahun 2011 yang menggunakan alat bantu

giden diperoleh hasil sebagai berikut. Hasil perhitungan menggunakan algoritma

15

lintasan pendek berulang diperoleh Rp 300.000,- menjadi Rp 106.693,-. Dengan

rute Candi Mas – Toko Aneka, Candi Mas – Toko Mitra, Candi Mas – Toko

Metro, Candi Mas – Toko Sari Rasa, Toko Sari Rasa – Toko Mawar, Toko

Mawar – Toko Cahaya, Candi Mas – Mirasa, Toko Mirasa – Toko Citrarasa,

Toko Citrarasa – Toko Amanda, Candi Mas-RM.Duta, Candi Mas – Toko

Barokah, Toko Barokah – RM. Tlaga Indah.

Contohpenerapan :

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

16

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:

Langkah 2 :

Nilai Produk yang didistribusikan xij dapat ditentukan dari nilai kemampuan

masing-masing titik untuk memberi atau menerima b(i) dan kapasitas maksimum

pengangkutan uij dengan ketentuan dan

}),({}),({

)(Eijj

ji

Ejij

ij xxib

(20000,40000)

(10000,20000)

(10000,50000) (20000,20000)

(30000,30000)

Pabrik

PD I

PD II

TP

0

40000

0

-40000

(2,4)

(1,2)

(1,5) (2,2)

(3,3)

1

2

3

4

0

4

0

-4

17

Penentuan nilai xij-nya adalah dari syarat , sehingga:

Untuk , diperoleh

Untuk , diperoleh

Untuk , diperoleh

Untuk , diperoleh

Untuk , diperoleh

Dengan syarat

}),({}),({

)(Eijj

ji

Ejij

ij xxib , sehingga:

Untuk diperoleh ( ) ( ) , maka (pers. 1)

Untuk diperoleh ( ) ( ) , maka ( )

(pers. 2)

Untuk diperoleh ( ) ( ), maka ( )

(pers. 3)

Untuk diperoleh ( ) ( ), maka ( ) (pers.

4)

Misalkan , maka dari pers. 1, akan diperoleh ,

maka dari pers. 2, ( ) akan diperoleh , dengan

memisalkan , maka didapat , maka dari pers. 4,

( )akan diperoleh , sehingga nilai yang mungkin adalah

, dan

Gambar dari aliran fisibel tersebut adalah sebagai berikut:

3

0

1 1

3

1

2

3

4

0

4

0

-4

18

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 dan

Sisi ( ) mempunyai harga dan

Sisi ( ) mempunyai harga dan

Sisi ( ) mempunyai harga dan

Sisi ( ) mempunyai harga dan

Sisi ( ) mempunyai harga dan

Sisi ( ) mempunyai harga dan

Sisi ( ) mempunyai harga dan

Sisi ( ) mempunyai harga dan

Sisi ( ) mempunyai harga dan

Gambar jaringan sisaan:

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

0

(-2,3)

1

2

3

4

0

4 -4

(2,1)

(1,2)

(-2,1)

(-1,0)

(1,4)

(3, 0)

(-1,1) (2,1)

(-3,3)

19

memudahkan dalam menentukan sikel-sikel pada jaringan. Penghapusan sisi

berkapasitas juga dapat dilakukan diantara langkah-langkah yang lain.

Langkah 5:

Menentukan sikel W yang bernilai negatif ( ( ) ) dan mereduksinya

sehingga jaringan sisaan tidak memuat sikel negatif.

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 ( )

(-2,3)

1

2

3

4

0

4 -4

(2,1)

(1,2)

(-2,1)

(1,4)

(-1,1) (2,1)

(-3,3)

0

(-2,3)

1

2

3

4

0

4 -4

(2,1)

(1,2)

(-2,1)

(1,4)

(-1,1) (2,1)

(-3,3)

0

20

, sehingga W = [13421]

merupakan sikel negatif.

Pilih sikel W= [2342] dengan * + * +

Menambahkan pada aliran yang berlawanan dengan sikel W dan

mengurangkan pada aliran yang searah dengan sikel W, sehingga didapat

G(x) seperti pada gambar berikut:

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 pada aliran yang berlawanan dengan sikel W dan

mengurangkan pada aliranyang searah dengan sikel W, sehingga didapat

G(x) seperti pada gambar berikut:

(-2,3)

1

2

3

4

0

4 -4

(2,1)

(-2,1)

(-1,2)

(1,2)

(-3, 1)

(-1,3) (2,1)

(3,2)

0

21

Karena jaringan tersebut masih memuat nilai , maka nilai tersebut

dapat dihilangkan sehingga

(-2,2)

1

2

3

4

0

4 -4

(2,2)

(-2,2)

(-1,2)

(1,1)

(3,3)

(-1,4) (2,0)

(-3,0)

0

(-2,2)

1

2

3

4

0

4 -4

(2,2)

(-2,2)

(-1,2)

(1,1)

(3,3)

(-1,4)

0

(-2,2)

1

2

3

4

0

4 -4

(2,2)

(-2,2)

(-1,2)

(-1,4)

(-3, 0)

(-1,1)

(3,3)

0

22

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.

∑

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,2)

1

2

3

4

0

-4

(2,2)

(-2,2)

(-1,2)

(1,1)

(3, 3)

(-1,4)

0

4

23

2.6 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

24

BAB III

METODOLOGI

3.1 Waktu dan Tempat

3.1.1 Waktu Pelaksanaan

Kegiatan survey dilaksanakan pada tanggal 5 Februari 2012 sesuai dengan waktu yang

diberikan oleh instansi.

3.1.2 Tempat Pelaksanaan

Adapun instansi yang ditunjuk sebagai lokasi sebagai objek penelitian adalah Ramayana

(Jenang Apel dan Kripik) Jl. Rahayu No. 6 Bumiaji Batu.

3.1.3 Sumber Data

Data yang digunakan diperoleh dari pimpinan “Ramayana”. Adapun data-data yang

diperlukan dalam penelitian ini yaitu lokasi pendistribusian, biaya distribusi, jalur

pendistribusian, jumlahpermintaan Keripik Apel Ramayana.

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:

3.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≤uijdan 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.

25

3. Cari sikel negatif. Jika tidak ada maka sikel optimal.

4. Jika ada, tambah aliran sepanjang sikel negative 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 negative maka solusi optimal.

3.2.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 adalahAlgoritma 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) danb(t) sama dengan nol.

3.2.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 xij yang bila ditambahkan ke

kapasitasnya menjadi batas atas.

4. Ulangi langkah 2 sampai tidak ada arc yang melanggar complementary slackness kondisi

optimal

26

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:

a. Pilih menu File-New

27

b. Untuk menggambar titik pilih New Node

c. Untuk menggambar sisi pilih New Edge

28

d. Untuk merubah nama titik dan sisi pilih Edit Value

e. Pilih Solves-Minimum Cost Flow, selanjutnya pilih algoritma yang diperoleh maka

akan muncul hasil yang diinginkan.

29

BAB IV

PEMBAHASAN

4.1 Narasi

Perusahaan keripik apel Ramayana setiap minggunya mendapatkan pesanan dari

pelanggannya yang berbeda beda. Dan setiap minggunya perusahaan tersebut juga

mendistribusikan produknya ke masing-masing pelanggannya dengan rincian sebagai

berikut:

Tabel 1

Lokasi Jumlah Permintaan

Pusat 773

Pujon 189

Batu 170

Beji 142

Singosari 150

Malang 122

Biaya pengangkutan dan kapasitas armada sebagai bobot sisi

Biaya pengangkutan adalah:

Bumiaji ke Pujon Rp 6.800

Bumiaji ke Batu Rp 1.800

Bumiaji ke Beji Rp 2.900

Bumiaji ke Malang Rp 6.100

Bumiaji ke Singosari Rp 7.700

Pujon ke Batu Rp 5.400

Batu ke Beji Rp2.300

Batu ke Singosari Rp 7.700

Beji ke Singosari Rp 5.900

Beji ke Malang Rp 6.800

Singosari ke Malang Rp 4.100

30

Kapasitas armada pengangkutan adalah :

Bumiaji ke Pujon 200

Bumiaji ke Batu 200

Bumiaji ke Beji 200

Bumiaji ke Malang 200

Bumiaji ke Singosari 200

Pujon ke Batu 200

Batu ke Beji 200

Batu ke Singosari 200

Beji ke Singosari 200

Beji ke Malang 200

Singosari ke Malang 200

Model graph

31

4.2 Penyelesaian Masalah dengan Algoritma

4.2.1 Menggunakan Algoritma Penghapusan Sikel

Penentuannilaialiranfisibelxij

Penentuannilaixij-nyaadalahdarisyarat 0 xijuijsehinggadiperoleh

untuk i=1, j=2 diperoleh 0 x12200

untuk i=1, j=3 diperoleh 0 x13200

untuk i=1, j=4 diperoleh 0 x14 200

untuk i=1, j=5 diperoleh 0 x15 200

untuk i=1, j=6 diperoleh 0 x16200

untuk i=2, j=3diperoleh 0 x23200

untuk i=3, j=4 diperoleh 0 x34200

untuk i=3, j=5diperoleh 0 x35200

untuk i=4, j=5diperoleh 0 x45200

untuk i=4, j=6diperoleh 0 x46200

untuk i=5, j=6 diperoleh 0 x56200

32

dan syarat b(i) = .}),({}),({

Eijj

ji

Ejij

ij xx ,

sehingga diperoleh:

untuk i = 1 diperoleh b(1) = 773 = x12 + x13 + x14 + x15+ x16……..(1)

untuk i = 2 diperoleh b(2) = - 189 = x23 - x12 ……........................(2)

untuk i = 3 diperoleh b(3) = - 175 = x34 + x35 – (x23+ x13).......................(3)

untuk i = 4 diperoleh b(4) = - 142 = x45+ x46 – (x14 + x34 )……...............(4)

untuk i = 5 diperoleh b(5) = - 122 = x56–( x45+ x35+ x15 )...................….(5)

untuk i = 6 diperoleh b(6) = - 150 = - (x56+x46+ x16)……........(6)

Dari persamaan (1)

misalkan x12 = 189, x13 = 182, x14 = 137, x15 = 120

maka diperoleh:

x16 = 145

Dari persamaan (2)

x23 = 0

Dari persamaan (3)

misalkan x34 = 12

maka diperoleh:

x35 = 0

Dari persamaan (4)

misalkan x46= 0

maka diperoleh:

x45 = 7

Dari persamaan (5)

x35= 0

Dari persamaan (6)

x56 =5

33

sehingga diperoleh:

x12 = 189 x13 = 182

x14 = 137 x15 = 120

x16 = 145 x46 = 0

x23 = 0 x34 = 12

x35= 0 x45= 7 x56= 5

34

Sehingga gambar aliran fisibel tersebut adalah

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 = 68 dan r12 = 11

Sisi (2,1) mempunyai harga : c21 = -68 dan r21 = 189

Sisi (1,3) mempunyai harga : c13 = 18 dan r13 = 18

Sisi (3,1) mempunyai harga : c31 = -18 dan r31 = 182

Sisi (1,4) mempunyai harga : c14 = 29 dan r14 = 169

Sisi (4,1) mempunyai harga : c41 = -29 dan r41 = 137

Sisi (1,5) mempunyai harga : c15 = 77 dan r15 = 80

Sisi (5,1) mempunyai harga : c51 = -77 dan r51 = 120

Sisi (1,6) mempunyai harga : c16 = 61 dan r16 = 55

Sisi (6,1) mempunyai harga : c61 = -61 dan r61 = 145

35

Sisi (2,3) mempunyai harga : c23 = 54 dan r23 = 200

Sisi (3,2) mempunyai harga : c23 = -54 dan r62 = 0

Sisi (3,4) mempunyai harga : c34 = 23 dan r34 = 188

Sisi (4,3) mempunyai harga : c43 = -23 dan r43 = 12

Sisi (3,5) mempunyai harga : c35 = 77 dan r35 = 200

Sisi (5,3) mempunyai harga : c53 = -77 dan r53 = 0

Sisi (4,5) mempunyai harga : c45 = 59 dan r45 = 193

Sisi (5,4) mempunyai harga : c54 = -59 dan r54 = 7

Sisi (4,6) mempunyai harga : c46 = 68 dan r46 = 200

Sisi (6,4) mempunyai harga : c64 = -68 dan r56 = 0

Sisi (5,6) mempunyai harga : c56 = 41 dan r56 = 195

Sisi (6,5) mempunyai harga : c65 = -41 dan r65 = 5

Diperoleh jaringan sisaan berikut:

Penghapusansisiberkapasitasrij = 0

36

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 43 1] dengan c(w) = -12.

Sikel negative tersebut mempunyai nilai = min {163, 12, 182} = 12

Tambahkan = 12 ke aliran yang berlawanan arah dengan sikel tersebut dankurangkan

= 12ke aliran yang searah dengan sikel tersebut, kemudian menghapus sisi yang

berkapasitas rij = 0 diperoleh jaringan sisaan sebagai berikut:

37

Iterasi 2

Jaringan sisaan yang terbentuk masih memuat sikel negative. Salah satu sikel negatifnya

adalah [1 65 1] dengan c(w) = -57.

Sikel negative tersebut mempunyai nilai = min {55, 5, 120} = 5

Tambahkan = 5 ke aliran yang berlawanan arah dengan sikel tersebut dankurangkan =

5ke aliran yang searah dengan sikel tersebut, kemudian menghapus sisi yang

berkapasitas rij = 0 diperoleh jaringan sisaan sebagai berikut:

38

Iterasi 3

Jaringan sisaan yang terbentuk masih memuat sikel negative. Salah satu sikel negatifnya

adalah [1 5 4 1] dengan c(w) = -11.

Sikel negative tersebut mempunyai nilai = min {80, 7, 137} = 7

Tambahkan = 7 ke aliran yang berlawanan arah dengan sikel tersebut dankurangkan =

7ke aliran yang searah dengan sikel tersebut, kemudian menghapus sisi yang

berkapasitas rij = 0 diperoleh jaringan sisaan sebagai berikut:

Penentuan nilai optimum

Gambar terakhir merupakan solusi optimum.

Nilai fungsi tujuan dari distribusi produk adalah

Z = ijijcx

= x12c12 + x13c13 + x14c14 + x15c15 + x16c16

= 189 ∙ 68 + 18 ∙ 182 + 61 ∙ 145 + 29 ∙ 137 + 77 ∙ 120

= 38574

Jadi biaya minimum dalam sekali distribusi adalah Rp. 38.574,-.

39

4.2.2 Menggunakan Algoritma Jaringan Simplex :

Menentukan spanning tree :

40

Iterasi1 :

Selanjutnya menentukan nilai( ) ( ) :

Nilai ( ) :

nilai ( ) :

( )

( )

( )

( )

( )

( )

nilai :

( ) ( )

( ) ( )

( ) ( )

( ) ( )

( ) ( )

( ) ( )

( ) ( )

( ) ( )

( ) ( )

( ) ( )

( ) ( )

( ) ( )

Karena semua sisi nilai sudah memenuhi definisi maka jaringan sudah optimum.

41

Mencari Nilai Optimum :

∑

( ) ( ) ( ) ( ) ( )

( ) ( ) ( ) ( ) ( )

42

4.2.3 Menggunakan Algoritma Lintasan Terpendek Berulang

Dengan Penghitungan Manual

Menetukan Lintasan Terpendek

- 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]

Menetukan Lintasan Terpendek

- Dipilih titik s dan t yaitu titik 1 dan 3

Lintasan terpendek s ke t adalah [1,3]

43

* ( ) ( ) { } +

* +

Diperoleh jaringan sisaan yang terbentuk dari lintasan terpendek [1,3]

Menetukan Lintasan Terpendek

- Dipilih titik s dan t yaitu titik 1 dan 6

Lintasan terpendek s ke t adalah [1,6]

* ( ) ( ) { } +

* +

Diperoleh jaringan sisaan yang terbentuk dari lintasan terpendek [1,6]

44

Menetukan Lintasan Terpendek

- 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]

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]

45

Menentukan Nilai Optimum

46

4.3 Penyelesaian dengan Alat Bantu

Dengan menggunakan alat bantu gidden :

Algoritma Penghapusan Sikel

Iterasi 1

Iterasi 2

47

Iterasi 3

Iterasi 4

48

Iterasi 5

Iterasi 6

49

Iterasi 7

Iterasi 8

50

Iterasi 9

Algoritma Lintasan Terpendek Berulang

Iterasi 1

Iterasi 2

51

Iterasi 3

52

Iterasi 4

Iterasi 5

53

Iterasi 6

Iterasi 7

54

Algoritma Jaringan Simplek

Iterasi 1

Iterasi 2

Iterasi 3

55

4.4 Analisis Hasil

Dari ketiga algoritma yang digunakan diperoleh nilai minimum yang diperlukan untuk

pendistribusian Keripik Apel Ramayana sebesar 38574, karena dalam penghitungan

dilakukan penyusutan sebesar 100, maka biaya sebenarnya sebesar Rp 3.857.400

untuk mendstribusikan 773 pack. Di keadaan lapangan setiap 20 pack dikenakan

biaya sebesar Rp 125.000, sehingga dari perhitungan dengan algoritma diperoleh

dalam pengiriman 20 pack dikenakan biaya sebesar Rp 99.800 yaitu dengan rincian

sebagai berikut:

Tabel 2

Aliran distribusi Cost Capacity

Bumiaji ke Pujon Rp. 6.800,- 189

Bumiaji ke Batu Rp. 1.800,- 170

Bumiaji ke Malang Rp. 6.100,- 122

Bumiaji ke Beji Rp. 2.900,- 142

Bumiaji ke Singosari Rp. 20.000,- 150

Pujon ke Batu Rp. 11.000,- 0

Batu ke Beji Rp. 38.000,- 0

Batu ke Singosari Rp. 12.000,- 0

Beji ke Singosari Rp. 35.000,- 0

56

Beji ke Malang Rp. 29.000,- 0

Singosari ke Malang Rp 4.150,- 0

Tabel 3

Algoritma yang

digunakan Biaya minimum Rute yang ditempuh

Penghapusan sikel Rp 3.857.400,-

Pusat ke malang

Pusat ke beji

Pusat ke singosari

Pusat ke batu

Pusat ke pujon

Lintasan terpendek

berulang Rp 3.857.400,-

Pusat ke malang

Pusat ke beji

Pusat ke singosari

Pusat ke batu

Pusat ke pujon

Metode simplek Rp 3.857.400,-

Pusat ke malang

Pusat ke beji

Pusat ke singosari

Pusat ke batu

Pusat ke pujon

57

BAB V

KESIMPULAN DAN SARAN

5.1 Kesimpulan

Dari penyelesaian permasalahan pendistribusian kripik apel, awalnya pendistribusian

tidak perhatikan rute yang ditempuh sehingga biaya distribusi tidak dapat

diminimalisasikan. Namun, dengan penyelesaian pendistribusian menggunakan minimum

cost flow diperoleh rute yang dapat meminimalkan biaya distribusi. Untuk menentukan

biaya minimum yang diperoleh dengan menggunakan algoritma pada minimum cost flow,

yaitu dimulai dengan mencari iterasi pada setiap algoritma yang digunakan berdasarkan

algoritma yang digunakan. Selanjutnya setelah iterasi sudah selesai kita mencari nilai

optimumnya yang digunakan untuk menentukan biaya minimumnya berdasarkan pada hasil

iterasi yang terakhir. Algoritma pada minimum cost flow yang kami gunakan antara lain

algoritma jaringan simplex, algoritma lintasan pendek berulang dan algorima penghapusan

sikel. Untuk algoritma jaringan simplek dan algoritma lintasan pendek berulang lebih cepat

utuk memperoleh solusi optimumnya sedangkan untuk algoritma penghapusan sikel lebih

rumit untuk memperoleh solusi optimumnya.

Dengan menggunakan alat bantu Giden diperoleh hasil sebagai berikut :

Algoritma yang

digunakan Biaya minimum Rute yang ditempuh

Penghapusan sikel Rp 3.857.400,-

Pusat ke malang

Pusat ke beji

Pusat ke singosari

Pusat ke batu

Pusat ke pujon

Lintasan terpendek

berulang Rp 3.857.400,-

Pusat ke malang

Pusat ke beji

Pusat ke singosari

Pusat ke batu

Pusat ke pujon

Metode simplek Rp 3.857.400,-

Pusat ke malang

Pusat ke beji

Pusat ke singosari

Pusat ke batu

58

Pusat ke pujon

Sehingga pendistribusian dengan algoritma sebesar Rp 3.857.400,- dalam pengiriman per 20

pack dikenalkan biaya Rp 99.800,-. Sedangkan pada kenyataanya pendistribusiannya sebesar

Rp 4.831.250,- tiap pendistribusian per 20 pack dikenakan biaya Rp 125.000,-. Maka lebih

efektif menggunakan algoritma pada Minimum Cost Flow karena lebih meminimumkan

biaya sebesar Rp 973.850,- sehingga biaya semula sebesar Rp 4.831.250,- menjadi

Rp 3.857.400,-.

5.2 Saran

1. Rute pengiriman Kripik Apel 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 Kripik Apel.

59

LAMPIRAN I

Pengalaman Survey:

Kripik apel “Ramayana” merupakan olahan dari industri rumahan yang terletak di

daerah Batu. Selain itu tempatnya juga strategis yaitu terletak di daerah wisata Batu. Karena

letaknya tersebut maka sangat menunjang untuk pendistribusian hasil olahannya yaitu kripik

apel.

Setelah surat dan proposal sudah selesai, kami melakukan survey ke tempat tersebut

pada hari minggu tanggal 05 februari 2012. Karena salah satu dari teman kami mengenal

tempat produksi pengolahan kripik apel “Ramayana” maka kami lebih mudah untuk

mendapatkan ijin. Pada mulanya kami ragu apakah kami diperbolehkan untuk survey di

tempat tersebut, karena kami khawatir tidak diterima dan yang lebih kami khawatirkan lagi

data di perusahaan tersebut tidak cocok dengan materi yang kami peroleh. Akhirnya dengan

penuh tekad untuk memenuhi tugas, kami berani untuk melakukan survey di tempat tersebut.

Seteleh sampai di tempat kami di sambut oleh para karyawan yang bekerja di

perusahaan tersebut lalu kami diminta menunggu di ruang tunggu, karena pemilik perusahaan

yaitu bapak Mashudi sedang keluar. Setelah menunggu beberapa menit, akhirnya bapak

Mashudi datang. Kami langsung mewawancarai bapak Mashudi terkait masalah tempat

pendistribusiannya, permintaan dari masing masing pelanggan, armada yang digunakan dan

lain lain yang berkaitan dengan data yang diperlukan untuk minimum cost flow. Dan

akhirnya survey kami di tempat tersebut berjalan lancar dan diberi ijin oleh pemiliknya. Pada

saat kami melakukan survey, kami dibantu oleh pemilik perusahaan yaitu bapak Mashudi

secara langsung serta karyawan disana untuk melihat secara nyata sehingga survey bisa

maksimal sesuai yang kami harapkan.

Setelah memperoleh semua data yang kami inginkan, kami mengucapkan terima kasih

kepada bapak Mashudi selaku pemilik perusahaan serta karyawan karyawan di sana, serta

60

meminta maaf apabila dalam kami melakukan survey, kami melakukan hak yang tidak

berkenan kepada bapak Mashudi serta karyawan karyawan di perusahaan tersebut.

Tujuan dilakukan survey kali ini tidak hanya untuk penyusunan laporan saja, namun

lebih khususnya bertujuan untuk membantu pendistribusian kripik apel yaitu bagaimana cara

melakukan pendistribusian kripik apel dengan biaya paling minimum. Sehingga dapat

meminimumkan pengeluaran dan meningkatkan pendapatan untuk pemilik kripik apel

“Ramayana”

LAMPIRAN II

Google Map

61

LAMPIRAN III

62

63