BAB 2 LANDASAN TEORI 2.1 Proyek Konstruksi Proyek konstruksi adalah suatu rangkaian kegiatan yang melibatkan banyak pihak dan sumber daya untuk mencapai suatu tujuan tertentu (Ervianto, 2005). Proses ini biasanya dilakukan dalam jangka waktu pendek dan hanya satu kali. Dikarenakan melibatkan banyak pihak dan banyak faktor maka kegiatan proyek ini sangat riskan dalam menimbulkan konflik. Proyek konstruksi mempunyai tiga karakteristik, yaitu unik, melibatkan sumber daya dan membutuhkan organisasi. Dalam menyelesaikan proyek harus memperhitungkan tiga hal, yaitu spesifikasi (tepat mutu), time schedule (tepat waktu), dan biaya / cost (tepat biaya). Berikut ini merupakan penjelasan mengenai tiga karakteristik proyek konstruksi (Ervianto, 2005) : a. Bersifat unik Proyek disebut unik karena setiap proyek tidak pernah terjadi suatu rangkaian kegiatan yang sama persis dan melibatkan pekerja yang berbeda – beda. b. Melibatkan sumber daya Proyek konstruksi melibatkan sumber daya dalam pelaksanaannya hingga selesai. Sumber daya yang dimaksud adalah pekerja, uang, mesin, metode, dan material. Keseluruhan sumber daya ini diatur oleh manajer proyek. c. Membutuhkan organisasi Kegiatan proyek yang melibatkan banyak orang memerlukan sebuah organisasi. Di dalam organisasi itu sendiri terdapat sejumlah individu dengan karakter, keahlian, dan hasrat yang berbeda – beda. Hal utama yang harus dilakukan oleh manajer proyek adalah menyatukan semua individu tersebut menjadi satu visi atau tujuan.
2.2 Teori Graph Graph dapat didefinisikan menggunakan G = (V, E), di mana V itu merupakan himpunan berhingga tidak kosong dari vertex – vertex = {v1, v2, v3 ... vn} dan E tersebut merupakan himpunan sisi (edges) yang mana menghubungkan sepasang vertex {e1, e2, e3 ... en}.
5
6
Vertex di dalam graph ini merupakan kota, sedangkan edge atau sisi itu merupakan rute atau jalur yang menghubungkan antar vertex / kota. a
b
d
c
Gambar 2.1 Graph dengan 4 vertex Berikut ini merupakan keterangan dari gambar di atas, G merupakan graph dengan, V ={a, b, c, d} E = {(a, b), (a, c), (a, d), (c, a), (c, d), (b, b), (b, d), (d, b)} = {e1, e2, e3, e4, e5, e6, e7, e8}
Pada umumnya graph dapat dibedakan menjadi dua jenis, yaitu sebagai berikut 1. Graph tak-berarah (undirected graph) adalah graph yang mana edge-nya tidak memiliki arah tertentu.
Gambar 2.2 Graph tak berarah
2. Graph berarah (directed graph atau digraph) adalah graf yang mana semua edgenya memiliki arah tertentu.
Gambar 2.3 Graph berarah
7
2.3 Graph Hamilton Lintasan Hamilton itu adalah lintasan yang melewati setiap vertex di dalam suatu graph tepat satu kali. Apabila lintasan itu kembali ke vertex awal maka akan terbentuk lintasan tertutup (sirkuit), lintasan tertutup tersebut dinamakan sirkuit Hamilton. Jadi, sirkuit Hamilton itu adalah sirkuit yang melewati setiap vertex di dalam suatu graph tepat satu kali. Suatu graph yang memiliki sirkuit Hamilton seringkali dinamakan graph Hamilton, sedangkan yang memiliki lintasan Hamilton seringkali disebut graph semi-Hamilton. Setiap graph yang lengkap adalah graph Hamilton. a
b
d
c
a
b
a
b
d
c
d
c
Gambar 2.4 Gambaran Graph Hamilton Keterangan gambar: a) Graph yang memiliki lintasan Hamilton (misal: c, b,a, d) b) Graph yang memiliki sirkuit Hamilton (a, b, c, d, a) c) Graph yang tidak memiliki lintasan maupun sirkuit Hamilton
2.4 Dynamic / Multistage Programming Dynamic / multistage programming adalah salah satu metode pendekatan matematika tentang optimisasi proses banyak tahap. Metode ini digunakan untuk menyelesaikan persoalan dengan membagi suatu permasalahan menjadi bagian yang lebih kecil atau sub problem kemudian menggabungkan kembali bagian – bagian tersebut untuk mendapatkan jawaban yang dikehendaki (Mulyono, 2007). Penerapan dynamic programming mampu menyelesaikan masalah – masalah sebagai berikut, a. Masalah alokasi b. Masalah muatan (knapsack / cargo-loading problem) c. Masalah capital budgeting d. Masalah pengendalian persediaan e. Stagecoach (shortest route) problem
8
Pada dynamic programming, rangkaian keputusan yang optimal dibuat dengan menggunakan Prinsip Optimalitas. Prinsip Optimalitas: jika solusi optimal, maka bagian solusi pada tahap ke-k juga optimal. Prinsip optimalitas berarti bahwa bahwa jika kita bekerja dari tahap k ke tahap k+1, kita dapat menggunakan hasil optimal dari tahap k tanpa hasus kembali ke tahap awal. Ongkos pada tahap k+1 = (ongkos yang dihasilkan pada tahap k) + (ongkos dari tahap k ke tahap k+1). Dengan prinsip optimalitas ini dijamin bahwa pengambilan keputusan yang benar untuk tahap – tahap selanjutnya.
2.4.1 Model Dynamic programming Pada umumnya model dari dynamic programming dituliskan sebagai berikut:
Keterangannya sebagai berikut, = return pada tahap n dari nilai status input
dan keputusan
= kondisi awal = kondisi akhir = keputusan yang dibuat pada setiap tahap = keputusan pada tahap akhir = return function = return optimal pada tahap n – 1 dari nilai status input
dan
keputusan
Dalam penelitian ini, model dari Dynamic programming menjadi seperti di bawah ini,
Keterangannya sebagai berikut, = panjang optimal dari lintasan = himpunan berhingga yang tidak kosong dari vertex – vertex pada sebuah graph = himpunan vertex pada suatu graph yang dikurang vertex 1 (awal) = vertex yang terhubung ke vertex 1 (awal)
9
= bobot dari vertex 1 (awal) ke k
2.4.2 Konsep Dasar Dynamic programming Dynamic programming mempunyai beberapa konsep dasar. Adapun konsep – konsep dasar tersebut adalah sebagai berikut, a.
Dekomposisi Permasalahan dynamic programming itu dapat dipecah menjadi sub-permasalahan atau tahapan yang lebih kecil dan berurutan. Setiap tahap itu dapat disebut juga sebagai titik keputusan. Pada suatu tahap, setiap keputusan yang dibuat akan mempengaruhi keputusan – keputusan pada tahap berikutnya.
b.
Status Status adalah kondisi awal (Sn) dan kondisi akhir (Sn-1) di setiap tahap, yang mana di setiap tahap tersebut dibuat keputusan (Dn). Status akhir pada sebuah tahap tergantung kepada status awal dan keputusan yang dibuat pada tahap yang bersangkutan. Status akhir pada suatu tahap merupakan awal bagi tahap berikutnya.
c.
Variabel Keputusan dan Hasil Keputusan yang dibuat pada setiap tahap (Dn) merupakan keputusan yang berorientasi kepada return yang diakibatkannya (Rn │ Dn), tingkat maksimal atau minimal.
d.
Fungsi Transisi Fungsi transisi itu menjelaskan secara pasti bagaimana tahap – tahap itu saling berhubungan. Fungsi ini berbentuk fungsi hubungan antar status pada setiap tahap yang berurutan. Fungsi transisi secara umumnya berbentuk seperti di bawah ini: Sn-1 = Sn - Dn Di mana Sn-1 = status pada tahap n-1, atau status akhir pada tahap-n. Sn adalah status awal pada tahap-n.
e.
Optimasi Tahap Optimasi tahap dalam dynamic programming adalah menentukan keputusan optimal pada setiap tahap dari berbagai kemungkinan nilai status inputnya. Fungsi umum dari keputusan optimal sebagai berikut, fn (Sn, Dn)
= return pada tahap-n dari nilai status input Sn, dan keputusan, Dn
fn *(S)
= return optimal pada tahap-n dari nilai input status Sn
10
f.
Fungsi Rekursif Fungsi rekursif umumnya digunakan pada berbagai program komputer, di mana nilai sebuah variabel pada fungsi tersebut merupakan nilai kumulatif dari nilai variabel tersebut pada tahap yang sebelumnya. Pada dynamic programming, penulisan fungsi umumnya sebagai berikut:
prosedur optimasi diawali dari tahap akhir menuju tahap awal (backward).
2.4.3 Karakteristik Dynamic programming Karakteristik dynamic programming adalah: 1. Permasalahan dapat dipecah menjadi beberapa tahap (stages). Keputusan kebijakan yang standard dan saling berhubungan dibutuhkan setiap tahap. 2. Sejumlah status (state) dimiliki setiap tahap. Pada umumnya, sekumpulan status ini merupakan berbagai kemungkinan kondisi yang timbul dari sistem permasalahannya. Informasi yang dibutuhkan diberikan status ini dan berdampak pada tahap yang berikutnya. Jumlah status pada setiap tahap bisa definit atau infinit. 3. Setiap keputusan kebijakan yang dibuat pada suatu tahap ditransformasikan ke dalam status yang berkaitan pada tahap berikutnya. Hubungan antar status pada suatu tahap yang berurutan dapat bersifat deterministik atau probabilistik. Pada sebuah permasalahan dengan n-tahap, terdapat dua input, yaitu: (1) state pada tahap-n (Sn) dan decision variable (Xn). Sedangkan outputnya adalah: (1) return atau akibat dari setiap Xn yang dipilih, fn (S, Xn); dan (2) status baru yang menjadi input pada tahap berikutnya (Sn-1). Return function menentukan hubungan antara Xn dan fn (S, Xn). Transition function menentukan hubungan antar status pada tahapan tertentu. 4. Optimalitas yang dikembangkan Bellman menjadi prinsip solusi pada dynamic programming. 5. Persoalan dynamic programming diselesaikan mulai dari solusi awal pada suatu tahap, kemudian secara berurutan menuju tahap berikutnya dengan proses yang
11
terbalik (backward induction process). Keputusan pada tahap berikutnya bersifat independen terhadap keputusan sebelumnya. 6. Hubungan dalam bentuk fungsi rekursif (recursion relationship) menjadi prinsip bagi solusi optimal yang dihasilkan pada setiap tahap. Pada umumnya bentuk fungsi rekursif sebagai berikut, fn *(Sn) = max/min {fn (Sn, Xn)} Keterangan: fn *(Sn) = adalah hasil optimal dari keputusan pada tahap-n.
2.4.4 Ciri – ciri dasar permasalahan dynamic programming Permasalahan dynamic programming memiliki ciri – ciri dasar sebagai berikut, 1.
Dalam suatu permasalahan dynamic programming, optimasi pada suatu tahap merupakan tanda keputusan tentang suatu masalah pada tahap sebelumnya. Hal ini bukan keserentakan. Dari hal tersebut dapat diartikan untuk menyelesaikan suatu masalah dengan dynamic programming , masalah tersebut harus dipisahkan menjadi n sub problem.
2.
Apabila ada masalah yang memerlukan pilihan atau keputusan yang dibuat pada masing – masing tahap, artinya masalah tersebut berkaitan dengan Dynamic programming. Sistem status atau state pada setiap tahap mengatur dan mencerminkan seluruh kemungkinan pilihan.
3.
Return function berhubungan dengan setiap keputusan pada setiap tahap. Return function mengevaluasi keputusan yang dibuat, artinya apa saja yang diberikan kepada tujuan keseluruhan dari masalah tersebut (maksimisasi atau minimisasi).
4.
Fungsi transisi menghubungkan setiap tahap proses keputusan dengan tahap yang berdekatan.
5.
Untuk menghubungkan kebijaksanaan optimum pada tahap n dengan n-1 menggunakan suatu hubungan rekursif. Prosedur rekursif ada dua macam, yaitu: a. Foreward recursive equation (perhitungan dari depan ke belakang) b. Backward recursive equation (perhitungan dari belakang ke depan)
Langkah – langkah untuk mengembangkan dynamic programming adalah sebagai berikut: 1.
Buat karakteristik struktur solusi optimal.
12
2.
Lakukan pendefinisian secara rekursif nilai solusi optimal.
3.
Penghitungan nilai solusi optimal secara maju ataupun mundur.
4.
Buat konstruksi solusi optimal.
2.4.5 Pencarian solusi optimal dalam penelitian ini Langkah – langkah yang perlu dilakukan untuk menyelesaikan masalah dalam penelitian ini adalah sebagai berikut, Langkah pertama, Menentukan basis dari graph dengan persamaan
,
Langkah kedua, Lakukan penghitungan
untuk
, hitung menggunakan persamaan
Dengan ketentuan, adalah bobot rute terpendek adalah rangkaian jalur S dikurangi vertex j i dan j adalah vertex –vertex dalam V adalah bobot dari vertex i ke j
Dari hasil tersebut dilanjutkan menghitung
untuk
hingga
.
Langkah ketiga, Setelah diperoleh hasil dari langkah di atas, kemiduain hitung persamaan hubungan rekursif,
Dengan ketentuan,
13
adalah panjang optimal dari tour adalah himpunan vertex dari suatu graph yang dikurang vertex 1 (awal) adalah himpunan berhingga tidak kosong dari vertex-vertex sebuah graph adalah vertex yang terhubung ke vertex 1 (awal) adalah bobot dari vertex 1 (awal) ke k
Langkah keempat, Setelah mendapatkan hasil dari persamaan rekursif di atas, maka akan didapatkan bobot rute terpendek. Dari hasil tersebut masih perlu kita hitung untuk memperoleh solusi optimal / rute terpendek.
artinya adalah
panjang jalur dari vertex awal (1) menuju vertex 1 setelah melewati vertex 2, 3, 4, ..., n dengan urutan seminimum mungkin kemudian dicari pembentuk dari solusi optimal yang diperoleh.
