Jumat, 14 Januari 2022

[menuju akhir]

Soal 2 tugas UAS Optimasi 
Referensi : Skripsi harni Ulfiana, Universitas Negeri Semarang 2009

OPTIMASI JARINGAN LISTRIK DENGAN ALGORITMA PRIM DAN APLIKASI PROGRAM MATLAB 


1. Tujuan [kembali]
Mampu memecahkan kasus terkait perancangan optimasi

1. ALgoritma Prim
Persoalan pohon rentang minimum merupakan variasi dari persoalan rute terpendek yang perbedaannya terletak pada lintasan yang dicari. 
    Salah satu metode untuk mencari pohon rentang minimum ditemukan oleh Robert C. Prim. Metode ini disebut algoritma Prim. Algoritma Prim membentuk pohon rentang minimum dengan langkah per langkah. Pada setiap langkah kita mengambil sisi graf G yang memiliki bobot minimum namun yang terhubung dengan pohon rentang T yang telah terbentuk.
Secara formal algoritma Prim adalah sebagai berikut: 
0. Inisialisasi: mula-mula T adalah graf kosong. 
1. Ambil sembarang v∈V(G). Masukkan v ke dalam V(T). 
2. V(G) = V(G) – {v}. 
3. Untuk i = 1, 2, ..., n-1, lakukan: 
a. Pilihlah garis e ∈ E(G) dan e ∉E(T) dengan syarat: 
  i.e berhubungan dengan satu titik dalam T dan tidak membentuk siklus.
  ii.e mempunyai bobot terkecil dibandingkan dengan semua garis yang berhubungan dengan titik-titik dalam T, misalkan w adalah titik ujung e yang tidak berada dalam T. 
b. Tambahkan e ke E(T) dan w ke V(T)
c. V(G) = V (G) – {w}

2. MATLAB


MATLAB adalah sebuah lingkungan komputasi numerikal dan bahasa pemrograman komputer generasi keempat. Dikembangkan oleh The MathWorks, MATLAB memungkinkan manipulasi matriks, pem-plot-an fungsi dan data, implementasi algoritme, pembuatan antarmuka pengguna, dan peng-antarmuka-an dengan program dalam bahasa lainnya.

Mencari pohon rentang minimum termasuk ke dalam masalah optimasi yaitu mencari total jarak minimum sedemikian hingga semua titik dalam jaringan tersebut terhubung dan tidak membentuk siklus.

Di dalam MATLAB terdapat fungsi untuk menyelesaikan masalah program 0-1 yaitu fungsi bintprog, dengan formatnya

min f(x) 

st A(x) ≤ b 

Aeq(x) = beq  

Sintaksnya adalah sebagai berikut. 

x = bintprog (f, A, b) atau 

x = bintprog (f, A, b, Ae, be)

Untuk menentukan pohon rentang minimum dengan algoritma Prim langkah-langkah yang dilakukan adalah sebagai berikut.

1. Memiliah A1 sebagai titik awal sehingga V(T) = {A1} dan E(T)={}

2. (iterasi pertama) A1 sisi X1 maka ditambahkan X1 ke E(T) dan tambahkan titik ujung X1 yaitu A2 ke V(T).  


3. (iterasi kedua) memilih V(T) berbobot kecil titik-titik di V(T) adalah X2 (dengan bobot 189) dan X17 (dengan bobot 207). Sisi dengan bobot terkecil dan tidak membentuk siklus adalah X2. Tambahkan X2 ke E(T) dan titik ujung X2 ke V(T) yaitu A3. Sehingga V(T) = {A1, A2, A3} dan E(T) = {X1, X2}.

4. (iterasi ketiga) pilih sisi yang berhubungan dengan titik di V(T) dengan bobot terkecil dan tidak membentuk siklus

tabel 1. Tabel iterasi pencarían pohon rentang mínimum dari jaringan distribusi listrik PLN Kota Pekalongan wilayah distribusi Pekalongan 1 dengan algoritma Prim

model matematika berdasarkan permasalahan tersebut adalah

X1 : sisi dari titik A1 ke A2, 

X2 : sisi dari titik A2 ke A3, 

X3 : sisi dari titik A3 ke A4, 

X4 : sisi dari titik A4 ke A5, 

X5 : sisi dari titik A5 ke A6, 

X6 : sisi dari titik A6 ke A7, 

X7 : sisi dari titik A7 ke A8, 

X8 : sisi dari titik A8 ke A9, 

X9 : sisi dari titik A9 ke A10, 

X10 : sisi dari titik A10 ke A11, 

X11 : sisi dari titik A11 ke A12, 

X12 : sisi dari titik A12 ke A13,

X13 : sisi dari titik A13 ke A14, 

X14 : sisi dari titik A14 ke A15,

 X15 : sisi dari titik A15 ke A16, 

X16 : sisi dari titik A16 ke A17, 

X17 : sisi dari titik A2 ke A18, 

X18 : sisi dari titik A18 ke A19, 

X19 : sisi dari titik A19 ke A20, 

X20 : sisi dari titik A20 ke A21, 

X21 : sisi dari titik A21 ke A22, 

X22 : sisi dari titik A22 ke A23,

 X23 : sisi dari titik A23 ke A24, 

X24 : sisi dari titik A24 ke A25, 

X25 : sisi dari titik A25 ke A26, 

X26 : sisi dari titik A26 ke A27, 

X27 : sisi dari titik A27 ke A28, 

X28 : sisi dari titik A28 ke A29, 

X29 : sisi dari titik A29 ke A30, 

X30 : sisi dari titik A30 ke A31, 

X31 : sisi dari titik A31 ke A32, 

X32 : sisi dari titik A32 ke A7, 

X33 : sisi dari titik A19 ke A33, 

X34 : sisi dari titik A33 ke A34, 

X35 : sisi dari titik A34 ke A35, 

X36 : sisi dari titik A35 ke A31, 

X37 : sisi dari titik A21 ke A36, 

X38 : sisi dari titik A36 ke A37,

X39 : sisi dari titikA37 ke A27, 

X40 : sisi dari titik A37 ke A24, X41 : sisi dari titik A3 ke A38, X42 : sisi dari titik A38 ke A39, X43 : sisi dari titik A39 ke A40, X44 : sisi dari titik A40 ke A41 X45 : sisi dari titik A41 ke A42, X46 : sisi dari titik A7 ke A43, X47 : sisi dari titik A43 ke A44, X48 : sisi dari titik A44 ke A45, X49 : sisi dari titik A45 ke A46, X50 : sisi dari titik A46 ke A47, X51 : sisi dari titik A47 ke A48, X52 : sisi dari titik A48 ke A49, X53 : sisi dari titik A49 ke A50, X54 : sisi dari titik A50 ke A51, X55 : sisi dari titik A51 ke A52, X56 : sisi dari titik A52 ke A53, X57 : sisi dari titik A53 ke A54, X58 : sisi dari titik A54 ke A55, X59 : sisi dari titik A55 ke A11, X60 : sisi dari titik A11 ke A56, X61 : sisi dari titik A56 ke A57, X62 : sisi dari titik A57 ke A58, X63 : sisi dari titik A58 ke A28, X64 : sisi dari titik A59 ke A60, X65 : sisi dari titik A60 ke A30, X66 : sisi dari titik A8 ke A60, X67 : sisi dari titik A60 ke A58, X68 : sisi dari titik A9 ke A59, X69 : sisi dari titik A59 ke A57, X70 : sisi dari titik A43 ke A61, X71 : sisi dari titik A61 ke A62, X72 : sisi dari titik A62 ke A63, X73 : sisi dari titik A63 ke A64, X74 : sisi dari titik A64 ke A65, X75 : sisi dari titik A65 ke A66, X76 : sisi dari titik A46 ke A61, X77 : sisi dari titik A47 ke A62, X78 : sisi dari titik A62 ke A8, X79 : sisi dari titik A63 ke A67, X80 : sisi dari titik A67 ke A68, X81 : sisi dari titik A68 ke A69, X82 : sisi dari titik A64 ke A70, X83 : sisi dari titik A70 ke A71, X84 : sisi dari titik A65 ke A72, X85 : sisi dari titik A72 ke A73, X86 : sisi dari titik A49 ke A66, X87 : sisi dari titik A66 ke A10, X88 : sisi dari titik A54 ke A74, X89 : sisi dari titik A74 ke A75, X90 : sisi dari titik A75 ke A76, X91 : sisi dari titik A76 ke A77, X92 : sisi dari titik A77 ke A78, X93 : sisi dari titik A78 ke A79, X94 : sisi dari titik A54 ke A80, X95 : sisi dari titik A80 ke A81, X96 : sisi dari titik A81 ke A12, X97 : sisi dari titik A81 ke A82, X98 : sisi dari titik A82 ke A83, X99 : sisi dari titik A83 ke A84, X100 : sisi dari titik A84 ke A85, X101 : sisi dari titik A85 ke A86, X102 : sisi dari titik A85 ke A17, X103 : sisi dari titik A84 ke A16, X104 : sisi dari titik A83 ke A87, X105 : sisi dari titik A82 ke A76, X106 : sisi dari titik A82 ke A14, X107 : sisi dari titik A14 ke A88, X108 : sisi dari titik A88 ke A89, X109 : sisi dari titik A89 ke A90, X110 : sisi dari titik A15 ke A88, dan X111 : sisi dari titik A16 ke A89

Fungsi tujuan : 

MINIMUMKAN 90X1 + 189X2 + 42X3 + 175X4 + 42X5 + 154X6 + 231X7 + 158X8 + 270X9 + 154X10 + 121X11 + 47X12 + 180X13 + 198X14 + 186X15 + 204X16 + 207X17 + 63X18 + 72X19 + 180X20 + 117X21 + 144X22 + 90X23 + 90X24 + 261X25 + 161X26 + 112X27 + 56X28 + 57X29 + 154X30 + 77X31 + 144X32 + 171X33 + 153X34 + 117X35 + 182X36 + 117X37 + 36X38 + 369X39 + 189X40 + 108X41 + 189X42 + 126X43 + 90X44 + 63X45 + 91X46 + 98X47 + 217X48 + 112X49 + 84X50 + 98X51 + 256X52 + 209X53 + 55X54 + 165X55 + 115X56 + 120X57 + 94X58 + 171X59 + 187X60 + 228X61 + 204X62 + 190X63 + 167X64 + 217X65 + 245X66 + 252X67 + 198X68 + 278X69 + 126X70 + 140X71 + 85X72 + 138X73 + 99X74 + 94X75 + 224X76 + 252X77 + 133X78 + 39X79 + 44X80 + 85X81 + 39X82 + 116X83 + 50X84 + 66X85 + 457X86 + 105X87 + 130X88 + 35X89 + 160X90 + 85X91 + 120X92 + 170X93 + 94X94 + 149X95 + 116X96 + 245X97 + 372X98 + 122X99 + 192X100 + 289X101 + 192X102 + 216X103 + 321X104 + 187X105 + 249X106 + 162X107 + 192X108 + 222X109 + 90X110 + 102X111


Fungsi kendala:


X1 = 1 

X41 + X42 + X43 + X44 + X45 = 5 

X79 + X80 + X81 = 3 

X82 + X83 = 2 

X84 + X85 = 2 

X91 + X92 + X93 = 3 

X101 = 1 

X104 = 1 

X109 = 1 

X1 + X2 + X3 + X4 + X5 + X6 + X7 + X8 + X9 + X10 + X11 + X12 + X13 + X14 + X15 + X16 + X17 + X18 + X19 + X20 + X21 + X22 + X23 + X24 + X25 + X26 + X27 + X28 + X29 + X30 + X31 + X32 + X33 + X34 + X35 + X36 + X37 + X38 + X39 + X40 + X41 + X42 + X43 + X44 + X45 + X46 + X47 + X48 + X49 + X50 + X51 + X52 + X53 + X54 + X55 + X56 + X57 + X58 + X59 + X60 + X61 + X62 + X63 + X64 + X65 + X66 + X67 + X68 + X69 + X70 + X71 + X72 + X73 + X74 + X75 + X76 + X77 + X78 + X79 + X80 + X81 + X82 + X83 + X84 + X85 + X86 + X87 + X88 + X89 + X90 + X91 + X92 + X93 + X94 + X95 + X96 + X97 + X98 + X99 + X100 + X101 + X102 + X103 + X104 + X105 + X106 + X107 + X108 + X109 + X110 + X111 = 89

X2 + X3 + X4 + X5 + X6 + X17 + X18 + X31 + X32 + X33 + X34 + X35 + X36 ≤ 12 

X19 + X20 + X27 + X28 + X29 + X30 + X33 + X34 + X35 + X36 + X37 + X38 + X39 ≤12 

X21 + X22 + X23 + X37 + X38 + X40 ≤ 5 X24 + X25 + X26 + X39 + X40 ≤ 4 X47 + X48 + X49 + X70 + X77 ≤ 4 X50 + X71 + X77 + X78 ≤ 3 

X51 + X52 + X72 + X73 + X74 + X75 + X78 + X86 ≤ 7 

X7 + X46 + X70 + X71 + X76 ≤ 4

 X8 + X9 + X72 + X73 + X74 + X75 + X76 + X87 ≤ 7 

X10 + X53 + X54 + X55 + X56 + X57 + X58 + X59 + X86 + X87 ≤ 9

 X7 + X30 + X31 + X32 + X65 + X66 ≤ 5 

X8 + X64 + X66 + X68 ≤ 3 

X28 + X29 + X63 + X65 + X67 ≤ 4 

X62 + X64 + X67 + X69 ≤ 3 

X9 + X10 + X60 + X61 + X68 + X69 ≤ 5 

X11 + X58 + X59 + X94 + X95 + X96 ≤ 5 

X88 + X89 + X90 + X94 + X95 + X97 + X105 ≤ 6 

X12 + X13 + X96 + X97 + X106 ≤ 4

 X14 + X15 + X98 + X99 + X103 + X106 ≤ 5 

X16 + X100 + X102 + X103 ≤ 3 

X14 + X107 + X110 ≤ 2 

X15 + X108 + X110 + X111 ≤ 3 

X8 + X30 + X31 + X32 + X46 + X64 + X65 + X68 + X70 + X71 + X78 ≤ 10 

Mencari solusi optimum dengan fungsi bintprog. 

Sintaknya adalah [x, fx] = bintprog(f, a, b, ae, be) 

Membaca dan menganalisis hasil yang diperoleh. Sebagian hasil output dapat dilihat pada tabel berikut ini.

 tabel 2. Tabel output program MATLAB

By di

Tidak ada komentar:

Posting Komentar

Langganan: Posting Komentar (Atom)