Optimasi Jaringan Masalah Optimasi Jaringan Model Optimasi Jaringan Penyelesaian Optimasi Jaringan dengan Simpleks
Pendahuluan Sebuah model jaringan terdiri dari dua buah element utama,
yaitu: Arc, marupakan garis penghubung antar node, Node, merupakan titik hubung sebuah arc.
Sebuah grafik, merupakan susunan beberapa arc dan node yang
saling berhubungan Sebuah directed graph, merupakan grafik dimana setiap arc memiliki arah tertentu (disimbolkan dengan anak panah) Sebuah model jaringan merupakan sebuah diagram grafik (biasanya merupakan directed graph)
Beberapa contoh jaringan Beberapa contoh jaringan:
Nodes
Arcs
Flow
Kota Call Switching Centre Sambungan pipa
Jalan Saluran telepon Pipa
Kendaraan Panggilan telepon Air
B A
A
B
C
C
D D
(a) a graph
E
(b) directed graph (digraph)
E
Definisi dasar Source node, sebuah node yang digunakan untuk masukan flow
ke dalam sebuah jaringan Sink node, sebuah node yang digunakan sebagai keluaran dari sebuah jaringan Flow capacity, batas atas (kadang merupakan batas bawah) flow yang mampu dialirkan di dalam sebuah arc Spanning tree, sebuah jalur di mana setiap node dalam sebuah jaringan terhubung
Masalah optimasi jaringan Masalah-masalah pada sebuah jaringan yang berhubungan
dengan teknik optimasi adalah: Shortest route, jalur terpendek yang menghubungkan titik asal ke
titik tujuan dalam sebuah jaringan Minimum spanning tree, jalur terpendek yang dapat menghubungkan semua node dalam sebuah jaringan Maximum flow, kapasitas maksimum sebuah jaringan untuk mengalirkan data dari source node ke sink node
Network flow programming Network flow programming, merupakan formulasi dan
penyelesaian masalah jaringan dengan menggunakan program linier Setiap bentuk jaringan dapat diubah ke dalam program linier dengan bentuk minimum-cost network flow programming
Karakteristik program linier jaringan (1) Variable, didefinisikan sebagai aliran di dalam sebuah arc yang
tidak diketahui, xi Aliran pada sebuah node,
Total aliran yang masuk ke sebuah node sama dengan total aliran
yang keluar dari sebuah node x x 0 outflows
j
inflows
j
Aliran pada source node dan sink node,
x x b Konstanta b bernilai positif untuk source node, negatif untuk sink node, dan bernilai NOL untuk node selain source dan sink Bentuk dapat merupakan sebuah persamaan atau lebih sering merupakan sebuah pertidaksamaan outflows
j
inflows
j
i
Karakteristik program linier jaringan (2) Aliran di dalam sebuah arc, aliran di dalam sebuah arc dapat
memiliki batas atas atau batas bawah (merupakan variable di dalam model linier) xj ≥ bj adalah lower bound aliran dalam sebuah arc, xj ≤ bj adalah upper bound aliran dalam sebuah arc, Default-nya, sebuah arc memiliki batas bawah bernilai NOL dan
tidak memiliki pada atas
Cost per-unit of flow, untuk setiap arc terdapat cost per-unit of
flow, ci,
Default-nya c bernilai NOL
Fungsi tujuan, adalah untuk menentukan nilai-nilai variabel xi
sedemikian hingga total cost seluruh jaringan menjadi minimum minimize c x arcs
j
j
Formulasi model program linier jaringan (1) Ada tiga buah parameter yang berhubungan dengan setiap arc,
yaitu lower bound, upper bound, dan cost per-unit of flow Label untuk setiap arc [l,u,c]
Source dan sink node ditentukan oleh label pada node, jika memiliki lower dan upper yang sama, maka bentuknya adalah
persamaan Jika memiliki lower dan upper yang berbeda, maka bentuknya adalah pertidaksamaan
Setelah diagram jaringan memiliki label untuk setiap arc dan
node, maka diagram tersebut dapat diubah ke dalam bentuk program linier
Formulasi model program linier jaringan (2) [4,0,-6]
[0,12,5]
arc 2 [0,6,0] A
arc 1 [0,inf,0]
C
arc 3 [0,3,2.5]
B
arc 4 [4,inf,3.7]
arc 5 [0,inf,0.5]
D
[8,8,0]
Formulasi model program linier jaringan (3) Fungsi kendala untuk diagram jaringan dihasilkan dari:
Node A : x1+ x2+ x3 ≤ 12 Node B: x4 – x1 = 0 Node C : x5 – x2 ≥ -4 Node D : -x3 – x4 – x5 = -8 Variable bound dihasilkan dari: Flow bound arc 2 : x2 ≤ 6 Flow bound arc 3 : x3 ≤ 3 Flow bound arc 4 : x4 ≥ 4 Nonnegative : x1, x2, x3, x4, x5 ≥ 0 Fungsi tujuan dihasilkan dari: minimize (5A – 6C + 2.5x3 + 3.7x4 + 0.5x5)
Permasalahan optimasi jaringan (1) Shortest route, untuk menyelesaikan permasalahan ini dilakukan
dengan prosedur:
Buatlah diagram jaringan, Setiap arc diberi label: Lower bound (l) bernilai NOL Upper bound (u) bernilai infinity Cost per-unit of flow (c) merupakan panjang arc Node asal merupakan source node dan memiliki nilai l dan u tepat 1,
serta c bernilai NOL
jadi label untuk node asal adalah [1,1,0]
Node tujuan merupakan sink node dan memiliki nilai l dan u tepat 1,
serta c bernilai NOL
jadi label untuk node tujuan adalah [1,1,0]
Hasilnya, arc dengan nilai positif merupakan rute terpendek pada
jaringan tersebut
Permasalahan optimasi jaringan (2) Minimum spanning tree, untuk menyelesaikan permasalahan ini
dilakukan dengan prosedur:
Buatlah diagram jaringan, Setiap arc diberi label: Lower bound (l) bernilai NOL Upper bound (u) bernilai infinity Cost per-unit of flow (c) merupakan panjang arc Node asal merupakan source node dan memiliki nilai l dan u tepat n,
serta c bernilai NOL
jadi label untuk node asal adalah [n,n,0]
Setiap node tujuan merupakan sink node dan memiliki nilai l dan u tepat
1, serta c bernilai NOL
jadi label untuk node tujuan adalah [1,1,0]
Hasilnya, arc dengan nilai positif merupakan minimum spanning tree
pada jaringan tersebut
Permasalahan optimasi jaringan (3) Maximum flow, untuk menyelesaikan permasalahan ini dilakukan
dengan prosedur:
Buatlah diagram jaringan, Setiap arc diberi label: Lower bound (l) bernilai NOL Upper bound (u) bernilai kapasitas setiap arc Cost per-unit of flow (c) bernilai NOL Node asal merupakan source node dan memiliki kapasitas yang besar
(yang mungkin terjadi)
jadi label untuk node asal adalah [0,M,0] M merupakan angka yang sangat besar
Setiap node tujuan merupakan sink node dan memiliki memiliki
kapasitas yang besar dengan nilai c bernilai -1 jadi label untuk node tujuan adalah [0,M,-1]
Kapasitas jaringan total akan diperoleh pada node tujuan End of slides
