METODE OUT OF KILTER MENENTUKAN MINIMAL COST PADA PERSOALAN NETWORK

METODE OUT OF KILTER MENENTUKAN MINIMAL COST PADA PERSOALAN NETWORK

SKRIPSI

AFNI DEVINA SARI SIREGAR 060823010

DEPARTEMEN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS SUMATERA UTARA MEDAN 2009

Afni Devina Sari Siregar : Metode Out Of Kilter Menentukan Minimal Cost Pada Persoalan Network, 2009. USU Repository © 2009

METODE OUT OF KILTER MENENTUKAN MINIMAL COST PADA PERSOALAN NETWORK

SKRIPSI

Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai Sarjana Sains

AFNI DEVINA SARI SIREGAR 060823010

DEPARTEMEN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS SUMATERA UTARA MEDAN 2009


PERSETUJUAN Judul

Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas

: METODE OUT OF KILTER MENENTUKAN MINIMAL COST PADA PERSOALAN NETWORK : SKRIPSI : AFNI DEVINA SARI SIREGAR : 060823010 : SARJANA (S1) MATEMATIKA : MATEMATIKA : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA

Medan,

Maret 2009

Komisi Pembimbing : Pembimbing 2

Pembimbing 1

Drs. Sawaluddin, M.IT NIP. 132206398

Drs. Marwan Harahap M.Eng NIP. 130422443

Diketahui/Disetujui Oleh Departemen Matematika FMIPA USU Ketua,

Dr. Saib Suwilo, M.Sc. NIP. 131796149


PERNYATAAN

METODE OUT OF KILTER MENENTUKAN MINIMAL COST COST PADA PERSOALAN NETWORK

SKRIPSI

Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.

Medan,

Maret 2009

AFNI DEVINA SARI SIREGAR NIM. 060823010


PENGHARGAAN

Puji dan syukur penulis panjatkan kehadirat Allah SWT yang Maha Pemurah dan Maha Penyayang dengan limpahan karunia-Nya skripsi ini berhasil diselesaikan dalam waktu yang telah ditetapkan. Ucapan terima kasih saya sampaikan kepada Bapak Drs. Marwan Harahap M.Eng dan Bapak Drs. Sawaluddin, M.IT selaku pembimbing pada penyelesaian skripsi ini yang telah memberikan panduan dan penuh kepercayaan kepada saya untuk menyempurnakan skripsi ini. Panduan ringkas dan padat dan profesional telah diberikan kepada saya agar penulis dapat menyelesaikan skripsi ini. Ucapan terima kasih juga ditujuan kepada Ketua dan Sekretaris Departemen Dr. Saib Suwilo, M.Sc. dan Drs. Henri Rani Sitepu, M.Si., Dekan dan Pembantu Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara, semua Dosen pada Departemen Matematika FMIPA USU, dan teman – teman seperjuangan komp 06. Akhirnya, tidak terlupakan kepada Ayahanda, ibunda dan adik-adik tercinta yang selama ini telah memberikan bantuan dan semangat yang diperlukan. Semoga Allah SWT akan membalas semua jasa mereka. Amin...


ABSTRAK

Kajian ini memperkenalkan algoritma out of kilter untuk menemukan suatu aliran biaya minimum pada kapasitas network. Algoritma ini di mulai dengan tahap permulaan dengan memberikan nilai setiap xij = 0 , dan variabel dual dikatakan wi =0. Kemudiaan masuk tahap promal dengan menentukan status arc dan mencari sirkuit (cycle) pada network. Tahap ini arc yang statusnya out of kilter akan di tingkatkan atau diturunkan agar status arc menjadi in-kilter. Jika tidak ditemukan cycle dalam network, maka akan masuk tahap ke tahap dual. Tahap ini akan menghitung nilai zij - cij.. Jika semua arc statusnya sudah in-kilter, maka proses akan selesai.


THE OUT OF KILTER FORMULATION OF A MINIMAL COST NETWORK FLOW PROBLEM

ABSTRACT

This paper is introduces out of kilter algorithm to find a minimal cost flow in capacited. This algorithm started with start phase by giving value every xij = 0., and dual variable, say each wi =0. Then phase admission primal by determining atatus arc and looks for circuit (cycle) at network. This phase arc which out of kilter will be increasing or decreasing arc to become in-kilter. Otherwise is found cycle in network, hence will step into dual phase. This phase will calculate value zij-cij. If all arc its status in-kilter had, hence process would completed.


DAFTAR ISI

Halaman PERSETUJUAN PERNYATAAN PENGHARGAAN ABSTRAK ABSTRACT DAFTAR ISI DAFTAR TABEL DAFTAR GAMBAR BAB I

BAB II

BAB III

ii iv v vi

PENDAHULUAN 1.1. Latar Belakang 1.2. Perumusan Masalah 1.3. Tinjauan Pustaka 1.4. Tujuan Penelitian 1.5. Kontribusi Penelitian 1.6. Metode Penelitian

1 2 2 3 3 4

LANDASAN TEORI 2.1. Konsep Dasar Graph 2.2. Graph Berarah (Directed Graph) 2.3. Reprensentasi Graph Dalam Matriks 2.4. Path Minimum 2.5. Flow 2.6. Minimal Cost Flow

5 5 6 8 9 10

PEMBAHASAN 3.1. Metode Out of Kilter Menentukan Minimal Coct Pada Network

11

3.1.1. Dual pada Aliran Network 3.1.2. Kondisi – kondisi Complemntary Slackness 3.1.3. Strategi Out Of Kilter 3.1.4. Tahap Permulaan (Initiation Phase) 3.1.5. Tahap Primal : Merubah Aliran Afni Devina Sari Siregar : Metode Out Of Kilter Menentukan Minimal Cost Pada Persoalan Network, 2009. USU Repository © 2009

12 12 13 14 14

3.1.6. Tahap Dual : Merubah Variabel Dual 3.1.7. Prosedur Label pada Algoritma Out of Kilter 3.1.8. Tahap Inisialisas i 3.1.9. Tahap Utama 3.2. Contoh Algoritma Out Of Kilter 3.4. Contoh Transhippment Pada Algoritma Out Of Kilter 3.5. Bahasa C++ BAB IV

18 19 19 19 22 25

KESIMPULAN DAN SARAN 4.1. Kesimpulan 4.2. Saran

DAFTAR PUSTAKA LAMPIRAN A. LISTING PROGRAM

DAFTAR TABEL

Halaman Tabel 3.1 Status Kilter pada Arc ................................................................................. Tabel 3.2 Bilangan Kilter Kij ..................................................................................... .. Tabel 3.3 Jumlah dan Arah Perubahan Aliran Yang Diijinkan ...................................


15 16 16

DAFTAR GAMBAR Gambar 2.1 Gambar 2.2 Gambar 2.3 Gambar 2.4 Gambar 2.5 Gambar 3.2 Gambar 3.3 Gambar 3.4 Gamabr 3.4a Gambar 3.4b Gambar 3.4c Gambar 3.4d Gambar 3.6 Gambar 3.7 Gambar 3.8 Gambar 3.9

Graph dengan Lima Verteks dan Enam Edge ................................ 5 Graph Berarah .............................................................................. 6 Graph Matriks Insiden .................................................................. 7 Graph dengan 6 Verteks dan 10 Edge ........................................... 8 Flow dalam Negatif ...................................................................... 9 Status Kilter pada Arc ................................................................ 17 Flowchart Out of Kilter .............................................................. 20 Contoh Network ........................................................................ 21 Breakthourgh dan Tahap Primal Pertama .................................... 21 Nonbreakthrough dan Tahap Dual ke Dua .................................. 22 Nonbreakthrogh dan Tahap Dual ke Dua .................................... 22 Solusi Optimal ........................................................................... 23 Problem Kapasitas Pengiriman .................................................. 25 Kendala Masalah Transshipment : Basic Solusi Layak ............... 26 Bentuk Cycle x56 dan Arus Basic Variable ................................ 27 Augmenting Flow ke x56,x35,x34, dan x,45 dilanjutkan ke iterasi berikutnya .................................................................................. 28


BAB I

PENDAHULUAN

1.1

Latar Belakang

Suatu aliran adalah suatu perjalanan objek dari satu tempat ke tempat lain dalam jaringan kerja ( network ). Ada dua masalah yang perlu diperhatikan pada aliran dalam network. Sebagai contoh, bagaimana memaksimalkan jumlah materi yang dikirim dari satu tempat ke tempat lain, menentukan cost yang minimal untuk mengirimkan sejumlah objek dari sumber s ke tujuan t .

Jaringan kerja (network) dapat digunakan untuk menjelaskan sebuah sistem seperti transportasi, aliran listrik, sambungan telepon, komunikasi, distribusi dan lain lain. Hal ini tentu saja bermanfaat pada hampir setiap kegiatan di berbagai bidang Ilmu Pengetahuan , Sosial dan Ekonomi.


Persoalan minimal cost flow merupakan permasalahan yang utama dalam network flow. Bentuk persoalan ini adalah menentukan cost pengiriman yang minimal pada sebuah komoditas melalui jaringan yang harus memenuhi node permintaan dan node persediaan. Secara umum suatu network dapat dinotasikan dengan himpunan G =(N,A), dimana N adalah node dan A adalah arc. Diberikan G = (N,A) sebagai network, misalkan jumlah bi adalah jumlah ketersediaan barang maka bi > 0 dan permintaan barang bi < 0. Node dengan bi >0 sering disebut sumber ( sources), dan node dengan bi < 0 sering disebut tujuan ( destination). Dimana bi adalah jumlah yang diminta untuk didatangkan (jumlah permintaan) node sumber i. Sedang i adalah indeks, jika bi = 0, maka tidak ada barang yang tersedia pada node i dan tidak diperlukan. Pada permasalahan ini node i sering disebut perantara ( intermediate ) node. Untuk setiap arc ( i,j ) pada vij adalah jumlah aliran pada edge (asumsikan 0 ≤ vij) dan cij adalah biaya pengiriman sepanjang arc. Dalam hal ini, penulis akan meninjau Algoritma Out of kilter serta beberapa penugasan, persoalan ongkos minimum/aliran maksimum, dan persoalan pengiriman barang (transshipment).

1.2 PERUMUSAN MASALAH

Permasalahan dalam tulisan ini adalah bagaimana algoritma out of kilter dapat menyelesaikan permasalahan distribusi aliran dalam network khususnya dalam mencari minimal – cost.

1.3

TINJAUAN PUSTAKA

Untuk mewujudkan maksud dan tujuan dari penelitian ini, penulis memanfaatkan bukubuku yang dipergunakan sebagai referensi salah satunya :

Aliran maksimal adalah suatu persoalan analisis jaringan kerja. Model aliran maksimal digunakan untuk menggambarkan nilai maksimal seluruh aliran didalam suatu jaringan kerja. [6]

Bazaara, Mokhtar S. Dan John J.Jarvis [3,bab 10] dalam bukunya “ Linear Programming and Network Flows “, memuat tentang, penyelesaian program integer seperti program linear, dengan rumus seperti di bawah ini : Afni Devina Sari Siregar : Metode Out Of Kilter Menentukan Minimal Cost Pada Persoalan Network, 2009. USU Repository © 2009

m

Minimumkan

m

∑∑c i =1 j =1

ij

x ij

m

m

j =1

k =1

∑ xij − ∑ x ki = 0

Kendala

i = 1, 2, …,m

xij ≥ lij

i,j = 1, 2, …,m

xij ≤ uij

i,j = 1, 2, …,m

dimana : m

: merupakan banyak node

cij

: merupakan cost dari node asal i ke node tujuan j

xij

: merupakan aliran (flow) dari node asal i ke node tujuan t

lij

: merupakan

uij

: merupakan batas atas

batas bawah

Kekekalan aliran yang memenuhi pada batasan tetap lij ≤ xij ≤ uij adalah feasible flow ( aliran yang layak). Asumsikan cij ,lij dan uij dan integer dan 0 ≤ lij ≤ uij . Karena semua nilai di sisi kanan pada persamaan kekekalan aliran adalah nol., dapat disimpulkan bahwa aliran dalam network tidak mempunyai node awal atau node akhir. Dengan demikian kekekalan aliran dalam network akan membentuk lingkaran berarah (directed cycles)

(Jean Marie PLA. 1971, hal.279) menyatakan karakteristik pemecahan masalah optimal dalam network flow yang paling sederhana adalah memperkenalkan masalah dual dan kondisi complementary slackness.

Dalam menyelesaikan persoalan network dengan algoritma out-of-kilter digunakan asumsi bahwa setiap arc dalam network jaringan mempunyai kapasitas tertentu, atau mempunyai batas bawah dan batas atas bagi alirannya. Afni Devina Sari Siregar : Metode Out Of Kilter Menentukan Minimal Cost Pada Persoalan Network, 2009. USU Repository © 2009

Algoritma out-of-kilter dapat dipergunakan untuk menyelesaikan beberapa persoalan jaringan berkapasitas, yaitu persoalan transportasi, persoalan penugasan, persoalan ongkos minimum/aliran maksimum, persoalan lintasan terpendek, dan persoalan transshipment.

1.4. TUJUAN PENELITIAN Untuk menganalisa permasalahan distribusi aliran barang (commodity) sampai mencari minimal cost dengan menggunakan Algoritma out of kilter dan mengimplementasikan dengan suatu program.

1.5. KONTRIBUSI PENELITIAN

Metode out of kilter dengan menentukan minimal cost pada persoalan network bermanfaat untuk jaringan transportasi, jaringan pipa (Aliran PAM),dan lalu lintas atau perniagaan.

1.6. METODE PENELITIAN

1. Menguraikan pendekatan pada Graph 2. Menentukan lintasan (path) dari sumber (source) ke tujuan ( destination) 3. Menguraikan tentang masalah aliran minimal cost dan hal – hal yang menyangkut konsep algoritma out of kilter. 4

Menjelaskan penggunaan algoritma Out of Kilter dalam mencari minimal cost.

5

Implementasikan metode algoritma out of kilter dengan suatu program..


BAB II

LANDASAN TEORI

2.1.

Konsep Dasar Graph

Definisi 2.1. Sebuah graph G= (N,A), di mana himpunan N adalah himpunan yang anggotanya disebut node dan A dari pasangan node yang disebut arc.

Secara umum graph dapat digambarkan dengan suatu diagram di mana verteks ditunjukkan sebagai titik yang dinotasikan dengan ni , i = 1, 2, …,P dan arc Afni Devina Sari Siregar : Metode Out Of Kilter Menentukan Minimal Cost Pada Persoalan Network, 2009. USU Repository © 2009

digambarkan dengan sebuah garis lurus atau garis lengkung yang menghubungkan dua verteks (ni, nj) dan dinotasikan dengan ak . Sebagai ilustrasi dapat dilihat Gambar 2.1. yaitu suatu graph yang mempunyai lima node dan enam arc.

n1

a4

a1

a5

n2

a2

n3

n5 a6

a3

n4

Gambar 2.1. Graph dengan lima node dan enam arc

2.2.

Graph Berarah ( Directed Graph)

Graph berarah G terdiri dari suatu himpunan N dari node – node dan suatu himpunan A dari arc - arc sedemikian rupa sehingga setiap arc a ∈ A menghubungkan pasangan node terurut. Jika terdapat sebuah arc a yang menghubungkan pasangan terurut (v,w) dari node, dapat ditulis dengan a =(v,w) yang menyatakan sebuah arc dari v ke w.

n1

n4 a4 a5

n5

a1 a3 a6

n2

a2

n3

Gambar 2.2. Graph Berarah (Directed Graph)


Graph berarah pada gambar 2.2 adalah graph berarah dengan himpunan node N(G) ={n1,n2,n3,n4,n5} dan himpunan sisi A(G) ={a1,a2,a3,a4,a5,a6} yaitu pasangan terurut dari { (n1,n2), (n2,n3), (n3,n4),(n4,n5),(n5,n1),(n2,n5).

Pada suatu graph dua buah node n1 dan n2 dikatakan adjacent jika kedua node tersebut dihubungkan oleh suatu arc. Pada gambar 2.2 node n1 adjacent ( bertetangga) dengan node n2. Sementara itu a1 dikatakan incident ( bersisian) dengan node n1 dan node n2.

2.3.

Representasi Graph dalam Matriks

1.

Matriks Insiden

Matriks insidency atau matriks bersisian adalah matriks yang mereprensentasikan hubungan antara node dan arc. Misalkan B adalah matriks dengan m baris untuk setiap node dan n kolom untuk setiap arc. Jika node terhubung dengan arc, maka elemen matriks bernilai 1. Sebaliknya, Jika node tidak terhubung dengan arc maka elemen matriks bernilai 0. Sebuah loop adalah node dengan titik awal sama dengan titik akhirnya, yaitu sebuah node yang mulai dan berakhirnya pada titik yang sama.

a6

a3

n1

n4

a1

a5 a2

n2

n3 a4

Gambar 2.3 Graph Matriks Insiden

v1

e1

e2

e3

e4

e5

e6

1

1

1

0

0

0


B=

bij =

2

v2

1

0

0

1

0

0

v3

0

1

0

1

1

0

v4

0

0

1

0

1

0

1

jika node ni adalah insiden pada arc aj

0

Jika tidak ada node ni yang insiden pada arc aj

Matriks Adjacency

Misalkan G adalah graph berarah yang terdiri dari n node tanpa arc pararel. Matriks Adjacency pada graph G adalah matriks bujur sangkar n x n, A( aij) dengan

aij =

1

jika ada arc (ni,nj) di G

0

Jika tidak ada arc (ni,nj) di G

Matriks adjacency dapat dilihat dari graph gambar 2.3 adalah :

A=

v1

v2

v3

v4

v1

0

1

1

1

v2

1

0

1

0

v3

1

1

0

1

v4

1

0

1

0

2.4. Path Minimum

Salah satu aplikasi graph berarah yang sering dipakai adalah mencari lintasan (path) terpendek diantara 2 pasang node (s ke t ). Jika masalahnya adalah mencari jalur Afni Devina Sari Siregar : Metode Out Of Kilter Menentukan Minimal Cost Pada Persoalan Network, 2009. USU Repository © 2009

tercepat, maka path terpendek tetap dapat digunakan dengan cara menggantikan nilai edge.

Definisi 2.2. Lintasan (Path) adalah suatu barisan edge (ei1,ei2 , ..,eik) sedemikian rupa sehingga verteks terminal eij berimpit dengan verteks awal ei(j+1) untuk 1≤ j ≤ k – 1. Contoh 2.1. e4 e5 v3 e2 v1

e3 e6

v2 e1

v4

e7

e10

e8 e9 v6

v5

Gambar 2.4. Graph dengan 6 verteks dan 10 edge

Pada Gambar 2.4 di atas terdapat: a. Semua edge berbeda (e1, e3, e4, dan e5 masing-masing muncul sekali). Ada verteks yang berulang (v3 muncul 2 kali). Verteks awal dan verteks akhir tidak sama (verteks awal = v1 dan verteks akhir = v4). Barisan ini merupakan path dari v1 ke v4 dengan panjang 4. b. Ada edge yang muncul lebih dari sekali, yaitu e5 (muncul 2 kali) berarti barisan tersebut merupakan walk dari v1 ke v5 dengan panjang 5.

2.5. Flow

Flow bisa saja dianggap sebagai bentuk kesatuan material yang meninggalkan suatu node menuju suatu node. Jika suatu arc aj insident ke dua node vi dan vj, maka suatu flow fj pada arc aj dapat ditunjukkan dengan sistematis.

Defenisi 2.3. Suatu flow pada suatu network G=(X,A) adalah suatu aliran pada suatu graph berarah dan berkapasitas, dimana setiap arc (x,y) ∈ A memiliki kapasitas non negatif c(x,y)≥0. jika (x,y) ∉ A, maka diasumsikan c(x,y) = 0. Afni Devina Sari Siregar : Metode Out Of Kilter Menentukan Minimal Cost Pada Persoalan Network, 2009. USU Repository © 2009

6

X1

X3

8 a1

a4

6 a8

s

0

5

a5 a3

a7

a2 6 6

X2

t

4 a9 8 X4

a6

Gambar 2.5. Flow dalam network

Gambar 2.5 memperlihatkan bahwa setiap arc terletak pada tiap-tiap node dari sumber s ke tujuan t. Arc menggambarkan saluran dengan kapasitas tertentu. Kapasitas merupakan batas maksimal di mana setiap material (misalnya air, gas, listrik) dapat dialirkan melalui saluran. Sedangkan node menggambarkan persimpangan saluran. Material mengalir melalui node tanpa mengumpulkan material tersebut pada node yang dilalui (kecuali pada node sumber dan node tujuan).

2.6. Minimal Cost Flow

Definisi 2.4 Suatu network yang mempunyai arc cost. Cost flow adalah perkalian cost dan flow sehingga cost flow adalah suatu bilangan..

Suatu flow f adalah suatu minimal cost flow jika f mempunyai minimal cost diantara semua flow yang ada dengan nilai flow, maka yang akan dicari dalam masalah minimal cost flow adalah suatu minial cost dengan nilai flow yang maksimal.

Definisi 2.5 Anggap G=(X,Y) adalah suatu network yang berarah menggambarkan suatu himpunan node X dan suatu arc A yang berarah. Setiap arc (x,y) ∈ A mempunyai Afni Devina Sari Siregar : Metode Out Of Kilter Menentukan Minimal Cost Pada Persoalan Network, 2009. USU Repository © 2009

non-negatif cost u(x,y) yang mengalirkan unit flow pada setiap arc dan juga memiliki kapasitas c(x,y). Jumlah cost suatu flow dari sumber s ke tujuan t, secara berurut adalah :

cos t ( f ) =

∑ f ( x, y ) u ( x, y )

( x , y )∈ A

Dimana ; f

: merupakan aliran (flow)

x,y

: merupakan arc

u

: merupakan batas atas

BAB III

PEMBAHASAN

3.1.

Metode of Kilter Menentukan Minimal Cost Pada Persoalan Network

Bentuk umum dari masalah aliran minimal cost dapat dituliskan sebagai berikut. Afni Devina Sari Siregar : Metode Out Of Kilter Menentukan Minimal Cost Pada Persoalan Network, 2009. USU Repository © 2009

m

Minimumkan

m

∑∑ c i =1 j =1

m

Kendala

∑x j =1

ij

x ij m

ij

− ∑ x ki =0

i = 1, 2, ...,m

(3.1)

k =1

xij ≥ lij

i,j = 1, 2, …,m

xij ≤ uij

i,j = 1, 2, …,m

keterangan : m

: merupakan banyak node

cij

: cost dari node asal i ke node tujuan j

xij

: aliran (flow) dari node asal i ke node tujuan j

lij

: batas

uij

: batas atas

bawah

Kekekalan aliran yang memenuhi pada batasan tetap lij ≤ xij ≤ uij adalah feasible flow(Aliran yang layak). Asumsikan cij, lij, dan uij integer dan 0 ≤ lij ≤ uij. Karena semua nilai di sisi kanan pada persamaan kekekalan aliran adalah nol, maka dapat disimpulkan bahwa aliran dalam network tidak akan terlihat di titik awal atau titik akhir, tapi akan beredar terus-menerus sepanjang aliran di network tersebut. Dengan demikian kekekalan aliran dalam network akan membentuk lingkaran berarah (directed cycles). 3.1.1. Dual pada Aliran Network Sesuaikan variabel dual wi dengan setiap node pada Persamaan 3.1, variabel dual hij dengan batasan xij ≤ uij (yang mana ditetapkan - xij ≥ - uij untuk mencari dual), dan variabel dual vij dengan batasan xij ≥ lij, dual dari out-of-kilter pada permasalahan aliran network minimal cost dituliskan sebagai berikut.

m

Maksimalkan

m

∑∑ l i =1 j =1

Kendala

m

ij

v ij -

m

∑∑ u i =1 j =1

ij

hij

wi – wj + vij – hij = cij hij,vij ≥ 0

i, j = 1,…, m i, j = 1,…, m


wi tak terbatas (unrestricted) i = 1,…, m Keterangan : vij

: nilai constraint atau nilai pembatas xij ≥ uij

hij

: nilai contraint atau nilai pembatas xij ≤ uij

wi

: nilai

wj

: nilai bobot dari node tujuan j

zij

: merupakan nilai optimal dari node asal i ke node tujuan j

bobot dari node asal i

Jika wi (asumsikan semua wi integer), maka dual constraint untuk arc (i, j) menjadi vij – hij = cij – wi + wj,

hij ≥ 0, vij ≥ 0

dan dapat dipenuhi oleh vij = Maksimum {0, cij - wi + wj } hij = Maksimum {0, - (cij - wi + wj }

3.1.2. Kondisi-kondisi Complementary Slackness

Kondisi-kondisi complementary slackness untuk mendapatkan nilai yang optimal dari perumusan out-of-kilter adalah sebagai berikut:

(xij – lij)vij = 0

i,j = 1, 2,…, m

(3.2)

(uij – xij)vij = 0

i,j = 1, 2,…, m

(3.3)

zij – cij ≡ wi – wj - cij . Kemudian dari definisi vij dan hij didapat vij = Maksimum {0, -(zij – cij)}

(3.4)

hij = Maksimum {0, zij – cij}

(3.5)

Catatan bahwa zij – cij akan dikenal sebagai koefisien xij dalam barisan fungsi objektif pada tabel simpleks batas atas-batas bawah yang mempunyai solusi dasar pada masalah primal. Afni Devina Sari Siregar : Metode Out Of Kilter Menentukan Minimal Cost Pada Persoalan Network, 2009. USU Repository © 2009

Bila diberikan nilai pada wi, maka dapat dihitung zij – cij = wi – wj - cij. Jika melihat persamaan pada (3.4) dan (3.5), maka kondisi complementary slackness (3.2) dan (3.3) diperoleh zij – cij < 0

vij > 0

xij = lij

i, j = 1, 2,..., m

(3.6)

zij – cij > 0

hij > 0

xij = uij

i, j = 1, 2,..., m

(3.7)

Memasukkan kondisi tambahan zij – cij = 0

lij ≤ xij ≤ uij

i, j = 1, 2,..., m

(3.8)

3.1.3 Strategi Out-Of-Kilter Langkah umum algoritma out-of-kilter (diuraikan pada gambar 3.3) adalah sebagai berikut : 1

Mulai dari kekekalan aliran (node masuk sama dengan node yang keluar), masing-masing xij = 0, dan solusi yang layak untuk dual, masing-masing wi = 0, dengan hij, vij seperti yang dijelaskan pada Persamaan (3.4) dan (3.5). Identifikasi keadaan kilter dan hitung bilangan kilter.

2

Jika pada network memiliki arc out-of-kilter, maka lakukan tahap primal algoritma. Selama tahap ini arc out-of-kilter terpilih dan mencoba membuat bentuk kekekalan aliran baru sedemikian bilangan kilter tidak ada arc memburuk dan arc yang terpilih ditingkatkan.

3

Ketika ditentukan bahwa tidak ada aliran yang meningkat terbangun selama tahap primal, algoritma membuat solusi dual yang baru sedemikian tidak ada bilangan kilter yang memburuk (worsened) dan ulangi tahap 2.

4

Iterasi antara tahap 2 dan tahap 3, algoritma secepatnya membangun solusi optimal atau menentukan tidak ada solusi yang layak. Algoritma out-of-kilter yang lengkap terdiri dari 3 (tiga) tahap: tahap permulaan

(initiation phase), tahap primal (primal phase), tahap dual (dual phase).

3.1.4 Tahap Permulaan (Initiation Phase) Dimulai dengan sebuah aliran, katakan untuk setiap xij = 0, dan inisial dual variabel, katakan wi = 0. Hitung zij – cij = wi – wj - cij.

3.1.5 Tahap Primal: Merubah Aliran Afni Devina Sari Siregar : Metode Out Of Kilter Menentukan Minimal Cost Pada Persoalan Network, 2009. USU Repository © 2009

Tentukan status kilter dan bilangan kilter untuk setiap arc. Kemudian cari dalam network yang membentuk sirkuit (cycle). Jika semua arc in-kilter, maka stop. Dengan diperoleh solusi optimal. Jika tidak, maka pilih atau lanjutkan dengan arc out-of-kilter (p,q) yang sebelumnya terpilih. Dari network G membentuk network G’ menurut Tabel 3.3. Untuk setiap arc (i,j) pada G adalah salah satu dari status kilter yang membolehkan aliran meningkat, tempatkan arc(i, j) di dalam G’ dengan arus yang dibolehkan meningkatkan. Untuk setiap arc (i,j) pada G adalah salah satu dari status kilter yang membolehkan aliran berkurang, selanjutnya tempatkan arc(j, i) di dalam G’ dengan arus yang dibolehkan. Untuk arc-arc di dalam G yang bagian dari status yang dibolehkan itu tidak ada aliran berubah, kemudian tempatkan tidak ada arc di dalam G’. Penentuan sirkuit seperti itu disebut breakthrough. Jika sirkuit seperti itu didapatkan, maka tentukan perubahan aliran Δ sama dengan minimum dari aliran yang berubah pada arc dalam sirkuit. Ubah aliran pada setiap arc dari siklus berhubungan dalam G dengan jumlah Δ menggunakan orientasi yang ditetapkan oleh sirkuit sebagai arah peningkatan. Khususnya, misalkan x’ij = xij + Δ jika (i, j) adalah anggota dari sirkuit G’; misalkan x’ij = xij - Δ jika (j, i) adalah anggota dari sirkuit G’; misalkan x’ij = xij sebaliknya. Ulangi tahap primal. Jika tidak ada sirkuit berisi arc (p, q) ada tersedia

di dalam G’, maka

lakukan tahap dual. Penentuan tidak ada sirkuit seperti itu disebut nonbreakthrough

Tabel 3.1. Status kilter pada arc


zij – cij < 0

zij – cij = 0

zij – cij > 0

xij > uij

Out-of-kilter

Out-of-kilter

Out-of-kilter

xij = uij

Out-of-kilter

In-kilter

In-kilter

lij < xij< uij

Out-of-kilter

In-kilter

Out-of-kilter

xij = lij

In-kilter

In-kilter

Out-of-kilter

xij < lij

Out-of-kilter

Out-of-kilter

Out-of-kilter

Keadaan in-kilter dan out of kilter pada tiap – tiap arc dalam network dapat dijelaskan pada tabel 3.1. 

Jika zij – cij < 0 dan xij > uij

maka statusnya out of kilter



Jika zij – cij < 0 dan xij = uij




Jika zij – cij < 0 dan lij < xij < uij




Jika zij – cij < 0 dan xij < lij




Jika zij – cij = 0 dan xij > uij




Jika zij – cij = 0 dan xij < lij




Jika zij – cij > 0 dan xij > ui j




Jika zij – cij > 0 dan lij < xij < uij




Jika zij – cij > 0 dan xij = lij




Jika zij – cij > 0 dan xij < lij




Jika zij – cij < 0 dan xij < lij

maka statusnya In-kilter




Jika zij – cij = 0 dan xij = uij



Jika zij – cij = 0 dan lij < xij < uij maka statusnya In- kilter



Jika zij – cij = 0 dan xij = lij




Jika zij – cij > 0 dan xij = uij



Tabel 3.2 Bilangan kilter Kij zij – cij < 0

zij – cij = 0

zij – cij > 0

xij > uij

| xij - lij|

| xij - uij|

| xij - uij|

xij = uij

| xij - lij|

0

0

lij < xij< uij

| xij - lij|

0

| xij - uij|

xij = lij

0

0

| xij - uij|

xij < lij

| xij - lij|

| xij - lij|

| xij - uij|

Tabel 3.3 Jumlah dan arah perubahan aliran yang memenuhi zij – cij < 0

zij – cij = 0

zij – cij > 0

lij < xij< uij

|x – l |

|x – l |

xij = uij

|x – u |

xij > uij

|x – u |

|x – u |


xij = lij

|x – l |

xij < lij

xij

Out-of-kilter In-kilter

In-kilter

uij

In-kilter

Out-of-kilter lij

zij - cij Out-of-kilter

Gambar 3.2. Status kilter pada arc

Ada banyak perbedaan ukuran jarak (measure distance) untuk masalah out-ofkilter. Pada Tabel (3.2) dijelaskan satu ukuran jarak yang disebut dengan bilangan kilter (Kilter number) Kij pada arc (i, j). Bilangan kilter didefenisikan bilangan yang Afni Devina Sari Siregar : Metode Out Of Kilter Menentukan Minimal Cost Pada Persoalan Network, 2009. USU Repository © 2009

mengubah aliran di arc menjadi minimal sehingga dapat menentukan lintasan kilternya. Perlu diingat bahwa karena syarat melibatkan nilai absolut, maka bilangan kilter pada arc harus non negatif. Jika arc yang in-kilter, maka bilangan kilter adalah nol (0) dan jika arc out-of-kilter, maka bilangan kilter adalah harus positif. Jika zij – cij < 0, maka arc (i, j) adalah in-kilter jika dan hanya jika aliran adalah sama dengan lij dan oleh sebab itu bilangan kilter |xij - lij| menandai seberapa jauh arus aliran xij adalah dari kasus ideal lij. Dengan cara yang sama, jika zij – cij > 0, maka bilangan kilter |xij - uij| memberi jarak dari aliran ideal uij. Terakhir, jika zij – cij = 0, maka arc adalah in-kilter bila lij ≤ xij ≤ uij. Khususnya, jika

xij > uij, maka arc dibawa ke in-kilter dan

pengurangan aliran oleh |xij - uij|, dan jika xij < lij, maka arc dibawa ke in-kilter dan peningkatan aliran oleh |xij - lij|, dan karenanya masuk kedalam kolom zij – cij = 0 pada Tabel (3.2)

Tahap Dual : Merubah Variabel Dual Tahap dual adalah tahap dimana dilakukan proses perubahan nilai variabel dual yang fungsinya adalah mengurangi bilangan kilter untuk mendapatkan nilai pada arc menjadi in – kilter. Adapun prosesnya sebagai berikut : Menentukan satuan dari node X yang dapat dicapai dari node q sepanjang path pada G’. Misalkan X = N – X. Dalam G, dapat digambarkan S1 dan S2 oleh S1 = {(i, j): i Є X, j Є X, zij - cij < 0, xij ≤ uij } S2 = {(i, j): i Є X, j Є X, zij - cij > 0, xij ≥ lij } Ө = Minimum {| zij - cij |, ∞ } Jika Ө = ∞, maka berhenti; tidak ada solusi yang layak. Sebaliknya, ubah wi dan zij - cij menurut wi + Ө

jika

i∈X

wi

jika

i∈X

(zij - cij)

jika

(i, j) Є (X, X) U(X, X)

wi =


(zij - cij)’ =

(zij - cij) + Ө

jika

(i, j) Є (X, X)

(zij - cij) - Ө

jika

(i, j) Є (X, X)

dan lakukan tahap primal.

3.1.7 Prosedur Label pada Algoritma Out-Of-Kilter Misalkan untuk setiap node j label L( j ) = ( + i, Δj). Label (i, Δj) menunjukkan bahwa aliran pada arc (i, j) dapat ditingkatkan dengan jumlah Δj tanpa memperburuk bilangan kilter pada arc manapun Δj tanpa memperburuk bilangan kilter pada arc manapun. Sebagai catatan bahwa Δj mewakili perkiraan aliran dari nilai aliran yang diubah yang dapat berlangsung sepanjang siklus yang berisi arc out-of-kilter dan arc (i, j) atau (j, i) Mulai Misalkan xij = 0 dan wi = 0

Hitung zij – cij = wi – wj - cij

Hitung

Periksa status kilter.Semua arc inkilter?

Ya

m

m

∑∑ c x i =1 j =1

ij ij

Tidak Tentukan arc yang out-of-kilter (p, q)

Ya Temukan sirkuit (direct cycle) pada network G’

Tidak Hitung S1 dan S2

Tidak Afni Devina Sari Siregar : Metode Out Of Kilter Menentukan Padaada Persoalan Network, 2009. Ya Minimal Cost USU Repository © 2009 solusi yang Hitung Ө; Jika Ө = ∞

layak Berhenti

dengan demikian bahwa bilangan kilter dari arc yang tidak ada ditingkatkan. Algoritma label terdiri dari 2 (dua) tahap, yaitu tahap inisialisasi dan tahap utama.

3.1.8 Tahap Inisialisasi Tentukan sebuah aliran, sebagai contoh, setiap xij = 0, dan nilai dari variabel dual, misalkan setiap wi = 0.

3.1.9 Tahap Utama 1. Jika semua arc adalah in-kilter sesuai Tabel 3.2, maka stop; dengan demikian nilai optimal diperoleh. Jika tidak, maka pilih (atau lanjutkan dengan pilihan selanjutnya) arc out-of-kilter, misal (p, q). Hapus semua label-label. Jika (p, q) adalah salah satu status di mana aliran meningkat., Δpq, sesuai Tabel 3.3, maka tetapkan s = q, t = p, dan L(s) = (+t, Δpq). Sebaliknya, jika (p, q) adalah salah satu status di mana aliran berkurang, Δpq, sesuai Tabel 3.3, maka tetapkan

s

= p, t = q, dan L(s) = (-t, Δpq). 2. Jika node i memiliki label, node j tidak memiliki label, dan aliran akan ditingkatkan dengan jumlah Δij sepanjang arc (i, j) sesuai dengan Tabel 3.3, maka menetapkan node j label L(j) = (+i, Δj ) di mana Δj = minimum{ Δi, Δij }. Jika node i memiliki label, node j tidak memiliki label, dan aliran dikurangi dengan jumlah Δji sepanjang arc (j, i) sesuai dengan Tabel 3.3, maka berikan node j label L(j) = (-i, Δj) di mana Δj = minimum{ Δi, Δji }. Ulangi langkah 2 sampai setiap node t diberi label atau sampai tidak ada lagi node-node yang Afni Devina Sari Siregar : Metode Out Of Kilter Menentukan Minimal Cost Pada Persoalan Network, 2009. USU Repository © 2009

diberi label. Jika node t diberi label, maka lanjut ke langkah ke 3 (breakthrough telah terjadi); jika tidak, maka lanjut ke langkah ke 4 (nonbreakthrough telah terjadi). 4.

Misalkan Δ = Δt. Ubah aliran sepanjang siklus yang dikenali sebagai berikut. Mulai dari node t. Jika masukan pertama di L(t) adalah + k, maka tambahkan Δ ke xkt. Sebaliknya, jika masukan pertama L(t) adalah – k, maka kurangi Δ dari xtk. Mundur ke node k dan ulangi proses sampai node t dicapai lagi dalam proses mundur(backtrack process).

3.3 Transportasi dan Transshipment Problem Model transportasi merupakan salah satu bentuk khusus atau variasi dari program linear yang dikembangkan khusus untuk memecahkan masalah yang berhubungan dengan transportasi (pengangkutan) dan distribusi produk atau sumber daya dari berbagai sumber ( pusat pengadaan, atau titik suplai) ke berbagai tujuan ( node permintaan).

3.2.1 Masalah Kapasitas Transshipment Menggunakan Algoritma Out Of Kilter

Masalah transportasi untuk menemukan total minimum cost pengiriman dari sumber (sources) s, dengan masing – masing persediaan yang berbeda, ke n tujuan (destination), dengan masing – masing permintaan ( demand) tertentu.

Masalah transshipment merupakan suatu bentuk umum model transportasi sedangkan model transportasi adalah bentuk khususnya di mana terdapat pusat- pusat asal atau sumber asli, pusat tujuan yang asli, dan titik – titik transshipmentnya. Titiktitik transshipment bisa terdapat pada pusat asal maupun pusat tujuan. Dalam model ini setiap pusat dapat mengirim dan menerima arus barang angkutan. Hal ini berarti terdapat keleluasaan dalam penetapan rute arus barang dari node i ke node j, selain rutenya yang langsung.


Ada beberapa cara untuk merumuskan masalah transshipment secara matematis. Andaikan, xij

= Jumlah yang diangkut dari titik j ; i≠ j ; i, j = 1,2, ...n.

cij

= Biaya angkutan dari node i ke node j ; cij ≥ 0.

ri

= Selisih node i.

si

= Persediaan (supply)

dj

= Permintaan (demand) Setiap node atau lokasi yang ada harus dapat memenuhi suatu rumusan

keseimbangan yaitu antara arus barang yang keluar (diangkut) dikurangi arus barang yang masuk (diterima) harus sama dengan kebutuhan bersih/ selisihnya.

3.3 Contoh Transshipment Pada Algoritma Out Of Kilter

S1 = 10

1

3 $5

$ 20 $10 12

D5 = 12 5

6 3

$7 8

7 $11

8 $12 $6 7 S2=15 2 1

$15

$15

4

10

$7

5

6

D6=13

17

Gambar 3.6 Problem kapasitas pengiriman

Kita temukan solusi layak dengan percobaan (trial) dan kesalahan (error) :

Variable dasar flow Basic

Batas bawah

flow

variable nonbasic

Batas Atas

Flow

variable nonbasic

X13

9

X12

0

X15

6

X12

5

X56

0

X24

10

X34

3

X65

0


X35

6

X46

13

Solusi yang paling pokok pada basic variable pohon (tree) pada gambar dibawah ini, ditunjukkan aliran cyclenya dibawah arcnya.

$20 S1=10

1 $10

3 $5

6

9

12

6 $7

3

D5 = 12

5 7 $11

8 8 $12

S2=15

$6 2

10 7 $15

$7

13 $15 4

10

5 6

17

D6=13

Flow

Gambar 3.7 Kendala Masalah Transshipment: Basic Solusi Layaknya

ITERASI 1 Ambil U1melalui 0 kemudian, Langkah 1

: Tentukan Uij

Variable Basic

Cij - Zij = 0

Substitusikan

X13

C13 - U1 + U3 = 0

X21

C21 – U2 + U1 = 0

6-

X34

C34 – U3 + U4 = 0

12 – (-10) + U4 = 0

U4 = - 22

X35

C35 – U3 + U5 =0

7 – (-10) + U5 = 0

U5= - 17

X46

C46 – U4+ U6 = 0

15 – (- 22) +U6 = 0

U6 = - 37

Langkah 2 dan 3

10 – 0 + U3 = 0

Dinyatakan

U2 + 0 = 0

U3 = -10 U2 =

6

: Tentukan nilai Cij - Zij untuk variable nonbasic dan variable Masukan.

Variable Batas Bawah Variable X12

Hitung Cij - Zij C12 – U1 = U2 = 5 – 0 + 6 = 11

Out of Kilter ? Tidak


X56

C56 – U5 + U6 = 11 – (-17) + (-37) = -19

Ya

X65

C65 – U6 + U5 = 7 – (-37) + (-17) = 27

Tidak

Variable Batas Atas Variable

Hitung Cij - Zij

Out of Kilter ?

X15

C15 – U1 +U5 = 20 – 0 + (-17) = 3

Ya

X24

C24 – U2 + U4 = 15 – 6 + (-22) = -1

Tidak

Langkah 4

: Tentukan perubahan variable basicnya

Pada gambar 3.8 ditunjukkan X56 berbentuk cycle dengan variable basic X35 , X34, dan X46. Dan X56 berada dibatas bawah (0), maka variable basicnya meningkat. Dari gambar 3.9 menunjukkan , ketika X56 meningkat, X35 harus meningkat dan X46 menurun. Maka X34 juga harus meningkat

D=5 5 $7 3

7 $11 8

8 $12

4 $15 17

6 D6=13

Gambar 3.8 Bentuk Cycle X56 dan arus basic variable

Jumlah maksimum akan dihitung dari perubahan di 4 variable sebelum sampai batasannya yang ditunjukkan digambar, sebagai berikut :

Variable

Nilai awal

Batas Atas

Maksimum meningkat


Meningkatkan X56

0

7

7–0=7

X35

6

8

8–6=2

Variable Menurun

Nilai awal

Batas Bawah

Maksimum menurun

X34

3

0

3–0=3

X46

13

0

13 – 0 = 13

Minimum dari maksimum di ubah menjadi 2, ditentukan X35 meningkat melalui variable batas atas. Lalu kita jumlah kan 2 melalui aliran di arc X56 dan X35 dan kurang 2 dari aliran selama X34 dan X46 digambarkan pada diagram network flow.

$20 S1=10 1

6

6 12 $10

5

9

D6=12

8

3 $5

$7

8

7 $11

1 8 $12

5

2

1

$6 S2=15

2

$15

10

4

10

$15

11

6

D6=13

17

Gambar 3.9 Augmenting Flow ke X56,X35,X34, dan X45 dilanjutkan ke iterasi berikutnya.

ITERASI 2 Afni Devina Sari Siregar : Metode Out Of Kilter Menentukan Minimal Cost Pada Persoalan Network, 2009. USU Repository © 2009

Variable basic

Flow

Batas bawah

Flow

nonbasic variable

Batas atas

Flow

variable nonbasic

X13

9

X12

0

X15

6

X21

5

X65

0

X24

10

X34

1

X35

8

X46

11

X56

2

Langkah 1 : Tentukan Uij Ambil U1 melalui 0

Variable basic

Nilai peluang = 0

Subsitusi

Dinyatakan

X13

C12 – U1 + U3 = 0

10 – 0 + U3 = 0

U3 = -10

X21

C21 – U2 + U1 =0

6 – U2 + 0 = 0

U2 = 6

X34

C34 – U3 +U4 = 0

12 – (-10) + U4 = 0

U4 = -22

X46

C46 – U4 + U6 = 0

15 – (-22) + U6 = 0

U6 = -37

X56

C56 – U5 + U6 = 0

1 – U5 + (- 37) = 0

U5 = -26

Langkah 2 : Tentukan nilai Cij - Zij dari variable nonbasic Variable batas bawah

Variable

Hitung Cij - Zij

Out of Kilter ?

X12

C12 – U1 + U2 = - 0+ 6 = 11

Tidak

X65

C65 – U6 + U5 = 7 – (-37) + (-26) = 18

Tidak

Variable Batas Atas

Hitung Cij - Zij

Variable

Out of kilter ?

X15

C15 – U1 + U5 = 20 – 0 + (-26)

=-6

Tidak

X24

C24 – U2 + U4

=-1

Tidak

X35

C35 – U3 + U5

7 – (-10) + (-26) = -9

Tidak

15 – 6 + (-22)

Tidak semua arc – arc adalah out of kilter, Kita akan menemukan Solusi optimalnya : Dari

Ke

Jumlah (Amount)

Unit Cost

Transportasi Cost


Node 1

Node 3

9

$10

$ 90

Node 1

Node 5

6

$20

$ 120

Node 2

Node 1

5

$6

$ 30

Node 2

Node 4

10

$15

$ 150

Node 3

Node 4

1

$12

$ 12

Node 3

Node 5

8

$7

$ 56

Node 4

Node 6

11

$15

$ 165

Node 5

Node 6

2

$11

$ 22 Total = $ 645

Dilangkah ke-3 dari algoritma, dua atau variable basic lainnya boleh berakhir di 0 atau dibatas atas pada waktu bersamaan. Jika menurun. Kita pilih salah satu variable yang dimulai dari nonbasic untuk dilanjutkan ke iterasi selanjutnya, basic lainnya harus sama nilainya 0 atau berada dibatas atas.

3.4.

BAHASA C++

Bahasa C++ merupakan program yang terbentuk fungsi – fungsi. Seperti main () merupakan nama dari suatu fungsi yang harus ada diprogram C++ dan diletakkan dibagian tertentu yang menunjukkan kepada compiler dimana awal dari suatu program. Selain itu main () ini hanya dapat dikatakan bahwa setiap program C harus mengandung fungsi main() agar dapat diproses.

Tanda brance pembuka ”{” yang diletakkan dibawah nama fungsi main() menunjukkan tanda awal dari perintah – perintah yang akan ditulis atau tanda ”{” merupakan awal dari function body atau fungsi blok. Tanda brance penutup ”}” menunjukkan akhir dari suatu fungsi blok. Suatu program C++ dapat terdiri dari lebih dari satu tubuh fungsi. Suatu tubuh fungsi dapat berisi beberapa fungsi, sedangkan suatu fungsi dapat dibuat dari satu atau lebih statement atau library function ( fungsi pustaka) yang sudah


BAB 4

KESIMPULAN DAN SARAN

4.1. Kesimpulan

Berdasarkan uraian-uraian dalam tulisan ini, penulis melihat bahwa algoritma out-ofkilter berperan penting dalam menghasilkan minimal cost dalam network flow.

Kesimpulan yang diperoleh pada kajian ini adalah sebagai berikut: 1. Algoritma minimal cost memelihara kelayakan promal dengan memenuhi kendala – kendala kapasitas, serta berusaha memenuhi persamaan kekekalan Afni Devina Sari Siregar : Metode Out Of Kilter Menentukan Minimal Cost Pada Persoalan Network, 2009. USU Repository © 2009

aliran (conserving flow) pada masing – masing node dengan memakai prosedur – prosedur berdasarkan pada penambahan aliran, penyesuaian biaya, dan menaikkan fungsi dual. 2. Di dalam algoritma out-of-kilter perlu diperhatikan nilai Ө. Ada dua kemungkinan nilai Ө. Jika 0 < Ө < ∞ , maka wi’ = wi + Ө

i ∈ X dan wi’ = wi

i ∈X .

Jika Ө = ∞, maka tidak ada solusi yang layak. Keterangan ; wi’ adalah variabel dual yang diubah wi adalah variabel dual 3. Aliran distribusi yang dihasilkan dapat menjadi output yang dapat dipertanggung jawabkan secara ilmiah, karena data tersebut memiliki dengan data pendukungnya, baik kendala maupun fungsi tujuan, sehingga menghasilkan nilai yang optimal untuk implementasinya

4.2. Saran Dalam mengimplementasikan Out of kilter pada network flow dapat diterapkan untuk semua masalah distribusi contohnya distribusi pipa minyak dari tempat tambang minyak menuju ke pabrik penyulingan. Bukan itu saja, bisa juga di implementasikan pada distribusi saluran pembuangan air di perumahan dan distribusi lainnya, dan dapat meminimalkan aliran dengan meminimalisasi biaya sehingga menghasilkan nilai yang optimal.


DAFTAR PUSTAKA Ahuja, Ravindra, K. “ Graph and Network Optimization “. USA: University of Florida, 1998. Bazaraa, Mokhtar S. dan John J. Jarvis, “ Linear Programing and Network Flows “. Canada: John Wiley and Sons Inc 1997. Elmaghraby, S., “ An Algebra for the Analysis of Generalized Actifity Networks “, Manage. Sci. , 10 (3), pp 494 – 514. 1964. Eisner, H., ” A Generalized Network Approach to the Planning and Scheduling of a Research Project “, Oper. Res., 10,pp.115-125, 1962. Afni Devina Sari Siregar : Metode Out Of Kilter Menentukan Minimal Cost Pada Persoalan Network, 2009. USU Repository © 2009

Evans, James R. “ Optimization Algorithms for Networks and Graphs“.

New

York: Marcel Dekker,Inc, 1992. Ford, L.R, Jr. And Fulkerson, D. R. “ Flows in Network “. Princeton, New Jersey: Priceton University Press, 1962. Ghare P. M, Moore, James M, Tihe, “ Applications of Graph Theory Algorithms” Elsever North Holland, Inc, 1979. Liu, Jipping. “Algorithms for Minimum - cost Flow “. Computer Science Departement, The University of Western Ontario, 2003. Sedgemick Robert. “ Algorithm in C- Part 5 Graph Algorithm “. Third Edition. Canada: Addison Wesley, Inc, 1990. Taha, Hamdy A., ” Riset Operasi ”, Binarupa Aksara, Jakarta, 1996.



METODE OUT OF KILTER MENENTUKAN MINIMAL COST PADA PERSOALAN NETWORK

Recommend Documents