BAB II LANDASAN TEORI
Bab ini berisi landasan dan dasar teori yang akan digunakan dalam melakukan analisis, perancangan, dan implementasi tugas akhir yang dilakukan pada bab-bab selanjutnya.
2.1 Bar Steel Bar steel merupakan salah satu bahan dasar bangunan yang memiliki peranan penting dalam satu kesatuan bangunan. Bar steel menjadi fondasi dari berdirinya bangunan karena dipakai hampir diseluruh bagian bangunan. Pada tahap awal konstruksi, bentuk bangunan dibuat dari bermacam- macam bar steel, sesuai dengan kebutuhan bangunan. Bar steel dibuat oleh pabrik dengan panjang standar. Satu batang bar steel yang dihasilkan oleh pabrik dengan panjang standar tersebut biasanya dihitung sebagai satu rol bar steel. Oleh karena itu, bar steel dipotong-potong sesuai dengan kebutuhan bentuk bangunan. Saat perancangan, arsitek yang merancang bangunan telah memilki perhitungan mengenai panjang-panjang bar steel yang digunakan, sehingga dapat ditentukan kebutuhan panjang bar steel untuk konstruksi.
Bar steel yang dijual oleh produsen bar steel terdiri dari 3 jenis, yaitu: 1. Hot Rolled Bar steel (HR Bar steel) HR Bar steel punya banyak tipe, beberapa tipe tersebut dapat dilihat pada Tabel II-1.
Tabel II-1. HR Bar steel [CEN07] Gambar
Ti pe
Spesifikasi
HR Steel Half Rounds
ASTM A 36, ASTM A 709 Gr 36
HR Steel Half Ovals
ASTM A 36, ASTM A 709 Gr 36
Steel Concrete Reinforcing Bars
Data spesifikasi t idak d itemukan
HR Steel Strip
Data spesifikasi t idak d itemukan
II-1
2. Cold Finished Bar steel (CF Bar steel) CF Bar steel punya banyak tipe, beberapa tipe tersebut dapat dilihat pada Tabel II-2. Tabel II-2. CF Bar steel [CEN07] Gambar
Ti pe HR Steel Rounds
Spesifikasi 1018, 10L18 (1018 juga tersedia yang telah dibengkokkan, telah diasah & dihaluskan) 1045 (juga tersedia yang telah dibengkokkan, telah diasah & dihaluskan) 1117, 11L17 1141, 11L41 (1141 juga tersedia yang telah dibengkokkan, telah diasah & dihaluskan) 1141 telah d iberi pola gambar, diasah & dihaluskan – Akurasi khusus 1144 12L14, 12L14 w/Seleniu m, 12L14 w/Telluriu m 1215 (juga tersedia yang telah diberi pola Gambar, diasah & dihaluskan – Akurasi khusus) ASTM A 311 Kelas B, Gr 1144 atau STRESSPROOF® ((juga tersedia yang telah diasah & dihaluskan)
CF Steel Hexagons
1018 1045 1117 1137 12L14, 12L14 w/Seleniu m, 12L14 w/Telluriu m 1215 ASTM A 311 Class B, Gr 1144 or STRESSPROOF® INcut® 100/1214 SA, INcut® 200
CF Steel Squares
1018 1045 1117, 11L17 12L14 1215
CF Steel Flats
1018 11L17
II-2
3. Alloy Bar steel Alloy Bar steel memiliki tipe yang sama bentuk dengan CF Bar steel, namun bedanya, Alloy Bar steel terbuat dari campuran beberapa logam.
2.2 Algoritma Optimasi Jika diberikan suatu permasalahan yang solusinya dapat diselesaikan dengan menggunakan fungsi f dan solusi optimal yang diinginkan adalah f(x), maka algoritma optimasi adalah metode yang digunakan untuk menemukan nilai x, misalnya menemukan kemungkinan yang terbesar (atau terkecil) dari suatu fungsi f dengan constraint yang diberikan oleh variabel x. Dalam hal ini, x, dapat berupa nilai skalar atau vektor dari nilai yang kontinu atau nilai diskrit [WIK07-a].
2.2.1 Algortima Brute Force 2.2.1.1 Penjelasan Umum Algoritma Brute Force Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan masalah, biasanya didasarkan pula pada pernyataan masalah (problem statement) dan definisi konsep yang dilibatkan. Algoritma brute force memecahkan masalah dengan sangat sederhana, langsung dan dengan cara yang jelas (obvious way) [MUN06].
Sebetulnya brute force tidak dapat dikatakan sebagai sebuah algoritma karena brute force tidak menggunakan suatu cara yang khusus dalam memecahkan masalah. Brute force hanya memeriksa semua kemungkinan yang ada. Metode ini tidak pintar dan tidak memiliki efisiensi sama sekali. Suatu metode dapat dikatakan algoritma jika memiliki efisiensi yang lebih baik dibanding metode lain.
2.2.1.2 Karakteristik Algoritma Brute Force Algoritma brute force pada umumnya tidak “cerdas” dan tidak mangkus, karena ia membutuhkan jumlah langkah yang besar dalam penyelesaiannya, terutama bila masalah yang akan dipecahkan berukuran besar (dalam hal ini ukuran masukannya). Walaupun algoritma brute force tidak mangkus, namun algoritma ini dapat dijadikan II-3
perbandingan solusi dengan algoritma lain yang lebih mangkus karena algoritma brute force pasti menghasilkan solusi yang paling optimal. Algoritma brute force membandingkan semua kemungkinan solusi sehingga solusi yang dihasilkan pasti paling optimal [MUN06].
2.2.1.3 Penyelesaian Masalah Menggunakan Algoritma Brute Force Salah satu implementasi persoalan optimasi yang dapat diselesaikan dengan algoritma brute force adalah persoalan knapsack. Inti dari permasalahan ini adalah misalnya diberikan n buah objek dan sebuah knapsack (karung, tas, dsb) dengan kapasitas bobot K. Setiap objek memiliki property bobot (weight) wi dan keuntungan pi. Objektif persoalan adalah bagaimana memilih objek-objek yang ada untuk dimasukkan kedalam knapsack sehingga tidak melebihi kapasitas knapsack namun memberikan keuntungan yang maksimal. Contoh persoalannya adalah sebagai berikut:
Jika terdapat sebuah knapsack dengan kapasitas K = 5 dan objek-objek dengan spesifikasi sebagai berikut: w1 = 2; p1 = 65 w2 = 3; p2 = 80 w3 = 1; p3 = 30 Langkah- langkah pencarian solusi 0/1 Knapsack secara brute force dirangkum dalam Tabel II-3.
Tabel II-3. Tabel Penyelesaian Persoalan Knapsack dengan Brute force Hi mpunan Bagian
Total Bobot
Total Keuntungan
{}
0
0
{1}
2
65
{2}
3
80
{3}
1
30
{1,2}
5
145
{1,3}
3
95
{2,3}
4
110
{1,2,3}
6
Tidak layak (Bobot > K)
II-4
Himpunan bagian objek yang memberikan keuntungan maksimum adalah {1,2} dengan total keuntungan 80. Jadi, solusi untuk persoalan knapsack diatas adalah X = {1, 1, 0}, yang artinya objek 1 dan 2 dimasukkan kedalam knapsack, sedangkan objek 3 tidak dimasukkan. Penyelesaian masalah knapsack menggunakan algoritma brute force mempunyai komplesitas O(n.2n ).
2.2.2 Algortima Greedy 2.2.2.1 Penjelasan Umum Algoritma Greedy Algoritma greedy membentuk solusi langkah per langkah (step by step). Terdapat banyak pilihan yang perlu dieksplorasi pada setiap langkah solusi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Keputusan yang telah diambil pada suatu langkah tidak bisa diubah lagi pada langkah selanjutnya. Sebagai contoh, jika menggunakan algoritma greedy untuk menempatkan komponen diatas sirkuit, sekali sebuah komponen telah ditetapkan posisinya, komponen tersebut tidak dapat dipindahkan lagi. Pendekatan yang digunakan di dalam algoritma greedy adalah membuat pilihan yang “tampaknya” memberikan perolehan terbaik, yaitu dengan membuat pilihan optimum lokal (local optimum) pada setiap langkah dengan harapan bahwa sisanya mengarah ke solusi optimum global (global optimum) [MUN06].
Metode pencarian menggunakan greedy dapat dikatakan sebuah algoritma pencarian karena metode ini dapat mengurangi sampel yang digunakan selama proses pencarian. Dengan begitu greedy dapat meningkatkan efisiensi pencarian dengan mengurangi sampel yang diperbandingkan. Namun, pada sebagian masalah algoritma greedy tidak selalu berhasil memberikan solusi yang benar-benar optimum.
2.2.2.2 Skema Umum Algoritma Greedy Semua algoritma greedy mempunyai skema umum yang sama. Secara umum, skema algoritma greedy dapat dirumuskan sebagai berikut: [MUN06] 1. Buat elemen-elemen pendukung algoritma greedy, yaitu: a) Himpunan Kandidat Himpunan yang berisi elemen-elemen pembentuk solusi. II-5
b) Himpunan Solusi Himpunan yang berisi kandidat-kandidat yang akan terpilih sebagai solusi persoalan. c) Fungsi Seleksi Fungsi yang pada setiap langkah dijalankan untuk memilih kandidat yang paling memungkinkan mencapai solusi optimal. d) Fungsi Kelayakan Fungsi yang memeriksa apakah suatu kandidat yang telah dipilih dapat memberikan solusi yang layak, yakni kandidat tersebut bersama-sama bersamasama dengan himpunan solusi yang telah terbentuk tidak melanggar constraints yang ada. e) Fungsi Objektif Fungsi yang memaksimumkan atau meninimumkan nilai solusi. 2. Inisialisasi S dengan kosong 3. Pilih sebuah kandidat (dengan fungsi seleksi) dari C, 4. Kurangi C dengan kandidat yang sudah dipilih dari langkah 3 diatas. 5. Periksa apakah kandidat yang dipilih tersebut bersama-sama dengan himpunan solusi membentuk solusi yang layak yang dilakukan oleh fungsi kelayakan. Jika ya, masukkan kandidat tersebut ke dalam himpunan solusi; jika tidak, buang kandidat tersebut dan tidak perlu dipertimbangkan lagi. 6. Periksa apakah himpunan solusi sudah memberikan solusi yang lengkap menggunakan fungsi objektif. Jika ya, berhenti, jika tidak, ulangi dari langkah 3.
2.2.2.3 Pseudocode Algoritma Greedy Pseudocode algoritma greedy diberikan pada Algoritma II-1.
2.2.2.4 Penyelesaian Masalah Menggunakan Algoritma Greedy Salah satu implementasi persoalan optimasi yang dapat diselesaikan dengan algoritma greedy adalah persoalan knapsack. Contohnya adalah sebagai berikut:
Jika terdapat sebuah knapsack dengan kapasitas K = 5 dan objek-objek dengan spesifikasi sebagai berikut: II-6
w1 = 2; p1 = 65 w2 = 3; p2 = 80 w3 = 1; p3 = 30 Secara matematis, persoalan 0/1 knapsack menggunakan algoritma greedy dapat dirumuskan sebagai berikut: maksimasi f = ∑ pix i dengan constraint ∑wix i ≤ K yang dalam hal ini, x i = 0 atau 1, i = 1, 2, 3, …, n
function greedy (input C: himpunan_kandidat) himpunan_kandidat {Mengembalikan solusi dari persoalan optimasi dengan algoritma greedy Masukan: himpunan kandidat C Keluaran: himpunan solusi yang bertipe himpunan_kandidat } Deklarasi x: kandidat S: himpunan_kandidat Algoritma S {Inisialisasi kosong} while (not SOLUSI(S)) and (C ≠ {} ) do x SELEKSI(C) {pilih sebuah kandidat dari C} C C – {x} {elemen himpunan kandidat berkurang satu} if LAYAK(S U {x}) then S S U {x} endif endwhile {SOLUSI(S) or C = {}} if SOLUSI(S) then return S else write(‘tidak ada solusi’) endif
Algoritma II-1 Pseudocode algoritma greedy Langkah- langkah penyelesaian masalah diatas dengan algoritma greedy adalah sebagai berikut: 1. Buat elemen-elemen pendukung algoritma greedy, yaitu: a) Himpunan Kandidat, C Objek-objek yang akan dimasukkan kedalam knapsack, yaitu C = {w1 , w2 , w3 } b) Himpunan Solusi, S Objek-objek yang terpilih sehingga jumlah nilai objek yang dimasukkan kedalam knapsack bernilai paling tinggi tanpa melebihi kapasitas knapsack K.
II-7
c) Fungsi Seleksi Pilihlah objek yang bernilai paling optimal berdasarkan 3 kriteria, yaitu bobot, keuntungan yang diberikan (profit), dan densitas(pi /wi). Untuk kriteria profit dan densitas pilihlah objek yang bernilai paling tinggi untuk masing- masing criteria tersebut, sedangkan untuk kriteria bobot pilihlah objek yang berbobot paling rendah. d) Fungsi Kelayakan Fungsi yang memeriksa apakah total bobot objek-objek yang telah dimasukkan kedalam knapsack tidak melebihi K (kapasitas knapsack). e) Fungsi Objektif Fungsi yang memilih jumlah keuntungan yang paling besar dari kandidat solusi yang layak. 2. Inisialisasi S dengan kosong 3. Pilih sebuah kandidat (dengan fungsi seleksi) dari C, 4. Pada Tabel II-4 direpresentasikan nilai- nilai yang dimiliki objek untuk 3 kriteria optimasi, yaitu profit, bobot, dan densitas. 5. Objek yang terpilih untuk masing- masing kriteria adalah objek yang nilainya dicetak tebal.
Tabel II-4. Nilai-nilai yang dimiliki oleh objek knapsack profit
Objek
bobot
densitas
w1
65
2
32.5
w2
80
3
26.67
w3
30
1
30
1. Kurangi C dengan kandidat yang sudah dipilih dari langkah 3 diatas. 2. Periksa apakah kandidat yang dipilih tersebut bersama-sama dengan himpunan solusi membentuk solusi yang layak yang dilakukan oleh fungsi kelayakan. Jika ya, masukkan kandidat tersebut ke dalam himpunan solusi, jika tidak, buang kandidat tersebut dan tidak perlu dipertimbangkan lagi. 3. Periksa apakah himpunan solusi sudah memberikan solusi yang lengkap menggunakan fungsi objektif. Jika ya, berhenti, jika tidak, ulangi dari langkah 3. 4. Solusi persoalan telah didapatkan. Solusi dapat dilihat pada Tabel II-5.
II-8
Tabel II-5. Solusi persoalan knapsack menggunakan algoritma greedy Properti objek i
pi
Kriteri a optimasi
wi
pi / wi
profi t
bobot
Solusi Opti mal
densitas
1
65
2
32.5
1
1
1
1
2
80
3
26.67
1
0
0
1
3
30
1
30
0
1
1
0
Total bobot
5
3
3
5
Total Keuntungan
145
95
95
145
Penyelesaian masalah ini dengan algoritma greedy mempunyai kompleksitas O(n2 ).
2.2.3 Algoritma Program Dinamis 2.2.3.1 Penjelasan umum Algoritma Program Dinamis Program dinamis adalah metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan. Pada penyelesaian persoalan dengan metode ini terdapat sejumlah berhingga pilihan yang mungkin, solusi pada setiap tahap dibangun dari hasil solusi tahap sebelumnya, dan kita menggunakan persyaratan optimasi dan kendala untuk me mbatasi sejumlah pilihan yang harus dipertimbangkan pada suatu tahap [MUN06].
Pada algoritma program dinamis setiap tahap pencarian memperhitungkan tahaptahap sebelum dan sesudahnya sehingga keputusan yang diambil pada setiap tahap dapat memberikan efek yang baik terhadap tahap selanjutnya.
2.2.3.2 Skema Umum Algoritma Program Dinamis Secara umum, ada empat langkah yang dilakukan dalam mengembangkan algoritma program dinamis, yaitu: [MUN06] 1. Karakteristikkan struktur solusi optimal 2. Definisikan secara rekursif nilai solusi optimal 3. Hitung nilai solusi optimal secara maju atau mundur 4. Konstruksi solusi optimal II-9
2.2.3.3 Penyelesaian Masalah Menggunakan Algoritma Program Dinamis Salah satu implementasi persoalan optimasi yang dapat diselesaikan dengan algoritma program dinamis adalah persoalan knapsack. Contohnya adalah sebagai berikut: Jika terdapat sebuah knapsack dengan kapasitas K = 5 dan objek-objek dengan spesifikasi sebagai berikut: w1 = 2; p1 = 65 w2 = 3; p2 = 80 w3 = 1; p3 = 30 Secara matematis, persoalan 0/1 knapsack menggunakan algoritma program dinamis dapat dirumuskan sebagai berikut: f o (y) = 0,
y = 0, 1, 2, …, K
(basis)
f k(y) = -∞,
y<0
(basis)
f k(y) = max{f k-1 (y),pk + f k-1 (y-wk)}, k = 1, 2, …, n
(rekurens)
Langkah- langkah penyelesaian masalah diatas dengan algoritma program dinamis adalah sebagai berikut: 1. Karakteristikkan struktur solusi optimal Struktur solusi optimal adalah (x 1 , x 2 , x3, x4 ) dimana x i memiliki nilai 0 jika objek wi tidak dimasukkan kedalam knapsack dan memiliki nilai 1 jika wi dimasukkan kedalam knapsack.
Definisikan secara rekursif nilai solusi optimal Relasi rekurens untuk masalah ini adalah
f 0 (y) = 0,
y = 0, 1, 2, …, K
(basis)
f k(y) = -∞,
y<0
(basis)
f k(y) = maks{f k-1 (y), pk + f k-1 (y-wk)}, k = 0, 1, 2, …,n
(rekurens)
yang dalam hal ini, f k(y) adalah keuntungan optimum dari persoalan 0/1 knapsack pada tahap k untuk kapasitas karung sebesar y. Perhatikanlah f 0 (y) = 0 adalah nilai dari persoalan knapsack kosong (tidak ada persoalan knapsack) dengan kapasitas
II-10
y, sedangkan f k(y) = -∞ adalah nilai dari persoalan knapsack untuk kapasitas negatif.
2. Hitung nilai solusi optimal secara maju Perhitungan secara maju terbagi menjadi 3 tahap karena persoalan knapsack ini terdiri dari 3 objek. 1. Tahap 1 Tabel II-6 merupakan tabel yang merepresentasikan tahap 1 program dinamis. f k(y) = max{f0 (y), p1 + f0 (y-w1 )} = max{ f0 (y), 65 + f 0 (y-2)} 2. Tahap 2 Tabel III-7 merupakan tabel yang merepresentasikan tahap 2 program dinamis. f k(y) = max{f1 (y), p2 + f1 (y-w2 )} = max{f1 (y), 80 + f 1 (y-3)} 3. Tahap 3 Tabel III-8 merupakan tabel yang merepresentasikan tahap 3 program dinamis. f k(y) = max{f2 (y), p3 + f2 (y-w3 )} = max{f2 (y), 30 + f 2 (y-1)} 4. Konstruksi solusi optimal 5. Solusi optimum dari persoalan 0/1 knapsack diatas adalah (1, 1, 0) dengan nilai keuntungan maksimum adalah 145. 6. Penyelesaian masalah ini dengan algoritma program dinamis mempunyai kompleksitas O(2n2 ).
Tabel II-6 Tahap 1 Penyelesaian masalah knapsack dengan program dinamis Solusi Opti mum y f0 (y)
65 + f0 (y-2)
f1 (y)
(x 1 *, x 2*, x 3 *)
0
0
-∞
0
(0, 0, 0)
1
0
-∞
0
(0, 0, 0)
2
0
65
65
(1, 0, 0)
3
0
65
65
(1, 0, 0)
4
0
65
65
(1, 0, 0)
5
0
65
65
(1, 0, 0)
II-11
Tabel II-7 Tahap 2 Penyelesaian masalah knapsack dengan program dinamis Solusi Opti mum
y f1 (y)
80 + f1 (y-3)
f2 (y)
(x 1 *, x 2*, x 3 *)
0
0
80 + (-∞) = -∞
0
(0, 0, 0)
1
0
80 + (-∞) = -∞
0
(0, 0, 0)
2
65
80 + (-∞) = -∞
65
(1, 0, 0)
3
65
80 + 0 = 80
80
(0, 1, 0)
4
65
80 + 0 = 80
80
(0, 1, 0)
5
65
80 + 65 = 145
145
(1, 1, 0)
Tabel II-8 Tahap 3 Penyelesaian masalah knapsack dengan program dinamis Solusi Opti mum
y f2 (y)
30 + f2 (y-1)
f3 (y)
(x 1 *, x 2*, x 3 *)
0
0
30 + (-∞) = -∞
0
(0, 0, 0)
1
0
30 + (-∞) = -∞
0
(0, 0, 0)
2
65
30 + 0 = 30
65
(1, 0, 0)
3
80
30 + 65 = 95
95
(1, 0, 1)
4
80
30 + 80 = 110
110
(0, 1, 1)
5
145
30 + 80 = 110
145
(1, 1, 0)
II-12
