BAB 2 LANDASAN TEORI
2.1 Tinjauan Pustaka 2.1.1 Riset Operasi Penelitian Operasi atau Operations Research mulai berkembang pada masa Perang Dunia II, dimana pada waktu itu angkatan perang Inggris membentuk suatu team yang terdiri atas para ilmuwan untuk mempelajari persoalan-persoalan strategi dan taktik sehubungan dengan serangan-serangan yang dilancarkan musuh terhadap negaranya. Tujuan mereka adalah untuk menentukan penggunaan sumber kemiliteran yang terbatas, seperti radar dan bomber, dengan cara yang paling efektif. Karena team tersebut melakukan research (penelitian) terhadap operasi-operasi militer, maka muncullah nama “Military Operations Research”, yang semenjak kelahirannya ditandai dengan digunakannya pengetahuan ilmiah dalam usaha menentukan penggunaan sumber-sumber yang terbatas. Keberhasilan yang diperoleh angkatan pernag Inggris ini kemudian mendorong angkatan perang Amerika untuk melakukan aktivitas serupa, team mereka berhasil dalam memecahkan persoalan-persoalan logistik suplai barangbarang keperluan perang, menentukan pola dasar penerbangan yang lebih efisien, serta menentukan pola-pola dasar jaringan bagi operasi alat-alat
19
elektronik. Setelah Perang Dunia II berakhir, Operations Research yang lahir di Inggris ini kemudian berkembang pesat di Amerika karena kebehasilan yang telah dicapai oleh team dalam bidang militer ini telah menarik perhatian orangorang industri. Sebagai suatu teknik pemecahan masalah, penelitian operasional harus dipandang sebagai suatu ilmu dan seni. Aspek ilmu terletak pada penggunaan teknik-teknik dan algoritma-algoritma matematik untuk memecahkan berbagai persoalan yang dihadapi; sedangkan sebagai seni ialah karena keberhasilan dari solusi model matematis ini sangat bergantung pada kreativitas dan kemampuan seseorang sebagai penganalisis dalam pengambilan keputusan (the art of balancing).
2.1.1.1 Komponen-komponen Utama Persoalan Keputusan Sebuah
model
keputusan
semata-mata
merupakan
alat
untuk
meringkaskan sebuah masalah keputusan dengan cara yang memungkinkan identifikasi dan evaluasi yang sistematis terhadap semua alternatif keputusan dari sebuah masalah. Sebuah keputusan lalu dicapai dengan memilih alternatif yang dinilai terbaik diantara semua pilihan yang tersedia. Keputusan yang didasari oleh kedua alternatif pertama hanya akan menghasilkan apa yang disebut pemecahan suboptimal. Hal ini menunjukan pentingnya untuk mengenali semua alternatif yang layak dari sebuah masalah keputusan jika kita ingin memperoleh pemecahan terbaik terhadap masalah
20
keputusan yang bersangkutan. Pada intinya, “kualitas” dari pemecahan yang optimal adalah fungsi dari sekelompok alternatif layak yang kita definisikan untuk masalah tersebut. Dalam beberapa situasi, identifikasi semua pemecahan yang layak adalah terlalu mahal atau tidak memungkinkan, sehingga dalam kasus demikian kita tidak memiliki pilihan apapun selain “hidup dengan” pemecahan yang suboptimal Munculnya persoalan-persoalan keputusan adalah karena seorang pengambil keputusan sering dihadapkan pada beberapa pilihan tindakan yang harus dilakukan. Dalam penyelesaian persoalan yang berkaitan dengan pengambilan keputusan ini harus diidentifikasi dahulu dua komponen utamanya, yaitu: 1. Objective (tujuan) Tujuan (objective) adalah hasil akhir yang hendak dicapai dengan cara memilih suatu tindakan yang paling tepat untuk sistem yang dipelajari. Dalam bidangbidang usaha biasa, tujuan diartikan sebagai “memaksimumkan profit” atau “meminimumkan ongkos”. Akan tetapi dalam bidang-bidang yang lain yang sifatnya non-profit, tujuan dapat berupa “pemberian kualitas pelayanan kepada para pelanggan”. Sedangkan yang dimaksud dengan Goal yaitu merupakan hasil akhir yang hendak dicapai namun tidak memiliki pilihan atas tindakan yang paling tepat, yaitu tidak ada maksimum ataupun minimum.
21
2. Variabel-variabel Manakala tujuan telah didefinisikan, maka harus dilakukan pemilihan tindakan terbaikyang dapat mencapai tujuan tersebut. Dalam hal ini, kualitas pemilihan akan sangat bergantung pada apakah si pengambil keputusan mengetahui seluruh alternatif tindakan atau tidak. Untuk dapat menentukan tindakantindakan yang mungkin dilakukan itu haruslah diidentifikasi variabel-variabel sistem
yang
dapat
dikendalikan
oleh
pengambil
keputusan,
yang
keberhasilannya dalam mengidentifikasi variabel-variabel ini pun akan sangat bergantung pada bias dan pelatihan pengambil keputusan.
2.1.1.2 Model-model Dalam Penelitian Operasional Model adalah gambaran ideal dari suatu situasi (dunia) nyata sehingga sifatnya yang kompleks dapat disederhanakan. Ada beberapa jenis model yang biasa digunakan, diantaranya adalah: 1. Model-model ikonis / fisik Yaitu penggambaran fisik dari suatu sistem, baik dalam bentuk yang ideal maupun dalam skala yang berbeda. Contoh: foto, blueprint, peta, globe 2. Model-model analog / diagramatis Model-model ini dapat menggambarkan situasi-situasi yang dinamis dan lebih banyak digunakan daripada model fisik karena sifatnya yang dapat dijadikan analogi bagi karakteristik sesuatu yang sedang dipelajari.
22
Contoh: kurva distribusi frekuensi pada statistik, kurva suplai demand, flowchart. 3. Model-model simbolis / matematis Yaitu penggambaran dunia nyata melalui simbol-simbol matematis. Pada awalnya model matematis/simbolis ini berupa model-model abstrak yang dibentuk didalam pikiran seseorang, kemudian disusun menjadi modelmodel simbolis, seperti gambar, simbol atau rumus matematis. Model matematis yang paling banyak digunakan dalam penelitian operasional adalah model matematis yang berupa persamaan atau ketidaksamaan. 4. Model-model simulasi Yaitu model-model yang meniru tingkah laku sistem dengan mempelajari interaksi komponen-komponennya. Karena tidak memerlukan model matematis secara eksplisit untuk merelasikan
variabel-variabel sistem,
maka model-model simulasi ini dapat digunakan untuk memecahkan sistem kompleks yang tidak dapat diselesaikan secara matematis. Akan tetapi model-model ini tidak dapat memberikan solusi yang benar-benar optimum. Yang dapat diperoleh ialah jawaban yang suboptimum, yaitu jawaban optimum dari alternatif-alternatif yang dites. 5. Model-model heuristik Kadang formulasi matematis bersifat sangat kompleks untuk dapat memberikan suatu solusi yang pasti. Atau mungkin suatu solusi optimum dapat diperoleh, tetapi memerlukan suatu proses perhitungan yang sangat
23
panjang dan tidak praktis. Untuk mengatasi kasus seperti ini dapat digunakan suatu model heuristik, yaitu suatu metode pencarian yang didasarkan atas intuisi atau aturan-aturan empiris untuk memperoleh suatu solusi yang lebih baik daripada solusi yang telah dicapai sebelumnya.
2.1.1.3 Metodologi Penelitian Operasional Jika penelitian operasional (Operations Research) akan digunakan untuk memecahkan suatu persoalan disuatu organisasi, maka harus dilakukan lima langkah sebagai berikut: Langkah 1: Memformulasikan persoalan Definisikan persoalan lengkap dengan spesifikasi tujuan organisasi dan bagian-bagian organisasi atau sitem yang bersangkutan. Hal ini mutlak harus dipelajari sebelum persoalannya dapat dipecahkan. Langkah 2: Mengobservasi sistem Kumpulkan data untuk mengestimasi besaran parameter yang berpengaruh terhadap persoalan yang dihadapi. Estimasi ini digunakan untuk membangun dan mengevaluasi model matematis dari persoalannya. Langkah 3: Memformulasikan model matematis dari persoalan yang dihadapi Dalam memformulasikan persoalan ini biasanya digunakan model analitik, yaitu model matematis yang menghasilkan persamaan. Jika
24
pada suatu situasi yang sangat rumit tidak diperoleh model analitik, maka perlu dikembangkan suatu model simulasi. Langkah 4: Mengevaluasi model dan menggunakannya untuk prediksi Pada langkah ini tentukan apakah model matematis yang telah dibangun pada langkah 3 telah menggambarkan keadaan nyata secara akurat. Jika belum, buatlah model yang baru. Langkah 5: Mengimplementasikan hasil studi Pada langkah ini kita harus menerjemahkan hasil studi atau hasil perhitungan kedalam bahasa sehari-hari yang mudah dimengerti.
2.1.2 Programa Dinamis Programa Dinamis atau Dynamic Programming adalah suatu teknik matematis yang biasanya digunakan untuk membuat suatu keputusan dari serangkaian keputusan yang saling berkaitan. Tujuan utama model ini ialah untuk mempermudah penyelesaian persoalan optimasi yang mempunyai karakteristik tertentu (Tjutju-Ahmad Dimyati, 2003). Sedangkan menurut Hamdy A. Taha (edisi 5, Jilid 1), Pemograman Dinamis adalah prosedur matematis yang terutama dirancang untuk memperbaiki efisiensi perhitungan masalah pemograman matematis tertentu dengan menguraikannya menjadi bagian-bagian masalah yang lebih kecil, dan karena itu lebih sederhana dalam perhitungan.
25
Ide dasar programa dinamis ini adalah membagi persoalan menjadi beberapa bagian yang lebih kecil atau dalam tahap-tahap sehingga memudahkan penyelesaiannya, dengan setiap tahap meliputi tepat satu variabel optimasi. Perhitungan ditahap yang berbeda-beda dihubungkan melalui perhitungan rekursif dengan cara yang menghasilkan pemecahan optimal yang mungkin bagi seluruh masalah. Akan tetapi, berbeda dengan programa linier, pada persoalan programa dinamis tidak ada formulasi matematis yang standar. Karena itu, persamaan-persamaan yang terpilih harus digunakan untuk dikembangkan agar dapat memenuhi masing-masing situasi yang dihadapi. Dengan demikian, maka antara persoalan yang satu dengan yang lainnya dapat mempunyai struktur penyelesaian persoalan yang berbeda. Teori utama dalam Dynamics Programming adalah prinsip optimalitas. Prinsip itu pada dasarnya menentukan bagaimana suatu masalah yang diuraikan dengan benar dapat dijawab dalam tahap-tahap (bukannya sebagai satu kesatuan) melalui pemakaian perhitungan rekursif.
2.1.2.1 Model Dynamic Programming Dalam Dynamic Programming, perhitungan dilakukan dalam tahap-tahap dengan memerinci masalah menjadi beberapa bagian masalah. Setiap bagian masalah kemudian dipertimbangkan secara terpisah dengan tujuan untuk mengurangi jumlah dan kerumitan perhitungan. Tetapi, karena semua bagian masalah saling bergantung, harus dipikirkan sebuah prosedur untuk
26
menghubungkan perhitungan dengan cara yang menjamin bahwa pemecahan yang layak untuk tiap-tiap tahap juga layak untuk keseluruhan masalah. Sebuah tahap dalam Dynamic Programming didefinisikan sebagai bagian dari masalah yang memiliki beberapa alternatif yang saling menggantikan, yang dari itu alternatif terbaik akan dipilih. Gagasan dasar Dynamic Programming adalah secara praktis menghilangkan pengaruh saling ketergantungan antara tahap-tahap dengan menghubungkan definisi suatu keadaan dengan setiap tahap. Suatu keadaan biasanya didefinisikan untuk menunjukan status batasan yang mengikat semua tahap secara bersama-sama. Keadaan sistem mungkin merupakan konsep yang paling penting dalam model pemograman dinamis. Hal itu mewakili “hubungan” antara tahap-tahap (secara berturut-turut) sehingga ketika setiap tahap dioptimumkan secara terpisah, keputusan yang dihasilkannya dengan sendirinya layak untuk seluruh masalah. Lebih lanjut, hal itu memungkinkan untuk mengambil keputusan optimum untuk tahap-tahap yang selebihnya tanpa harus memeriksa pengaruh keputusan itu dimasa yang akan datang dengan keputusan-keputusan yang diambil sebelumnya. Definisi keadaan biasanya adalah konsep yang paling tidak jelas dalam perumusan pemograman dinamis. Tidak ada jalan yang mudah untuk mendefinisikan keadaan, tetapi petunjuk biasanya dapat ditemukan dengan mengajukan dua pertanyaan berikut: 1. Hubungan apa yang mempersatukan tahap-tahap itu?
27
2. Informasi apa yang diperlukan untuk mengambil keputusan yang layak pada tahap sekarang tanpa memeriksa kelayakan dari keputusan yang diambil pada tahap-tahap sebelumnya?
2.1.2.2 Penganggaran Modal (Capital Bugetting) Masalah penganggaran modal mewakili masalah alokasi yang umum dimana sebuah sumber (atau, pada umumnya, sumber-sumber) dibagikan (secara optimal) diantara sejumlah kegiatan (tahap-tahap). Definisi keadaan sistem untuk semua masalah alokasi yang pada umumnya sama: yaitu, jumlah sumber yang dialokasikan pada sejumlah tahap berturut-turut mulai dari tahap terakhir.
2.1.2.2.1 Persamaan Rekursif Maju dan Rekursif Mundur Perhitungan yang dilakukan dengan menggunakan urutan metode f1 → f 2 → f 3 yaitu merupakan metode perhitungan yang dikenal sebagai proses maju (forward procedure) karena penghitungannya dilakukan maju dari tahap pertama hingga tahap akhir. Tetapi, jika dipelajari lebih jauh mengenai sebagian besar literatur Dynamic Programming, akan ditemukan bahwa persamaan rekursif disusun sedemikian rupa sehingga perhitunga dimulai pada tahap akhir
28
dan kemudian “berlanjut” kebelakang ketahap 1. proses ini dinamakan proses mundur (backward procedure). Perbedaan utama antara metode maju dan mundur terjadi dalam cara mendefinisikan keadaan sistem. Agar lebih spesifik, dipertimbangkan dahulu perbedaan definisi antara proses maju dan proses mundur. Pada proses maju, didefinisikan keadaan x j sebagai x1 = jumlah modal yang dialokasikan untuk tahap 1 x 2 = jumlah modal yang dialokasikan untuk tahap 1 dan 2
x3 = jumlah modal yang dialokasikan untuk tahap 1,2 dan 3 sedangkan untuk proses mundur, didefinisikan keadaan y j sebagai y1 = jumlah modal yang dialokasikan untuk tahap 1,2 dan 3 y 2 = jumlah modal yang dialokasikan untuk tahap 2 dan 3
y 3 = jumlah modal yang dialokasikan untuk tahap 3 Untuk memahami perbedaan antara definisi keadaan x j dan y j dalam metode maju dan mundur, kedua definisi diringkas secara grafis dalam Gambar 2.1.
29
Gambar 2.1 Definisi keadaan x j dan y j dalam metode maju dan mundur, Sekarang dapat didefinisikan : f 3 ( y 3 ) = pendapatan optimal untuk tahap 3 dengan diketahui y 3 f 2 ( y 2 ) = pendapatan optimal untuk tahap 2 dan 3 dengan diketahui y 2 f1 ( y1 ) = pendapatan optimal untuk tahap 1, 2 dan 3 dengan diketahui y1
Persamaan rekursif maju dengan demikian dapat ditulis sebagai f 3 (x3 ) = max
{R1 (k1 )}
k1
c1 ( k 1 )≤ x1
f j (x j ) = max
{R (k ) + f [x j
j
j +1
j
]
− c j (k j ) } , j = 2,3
kj cj ( kj )≤ xj
dimana, c = jumlah biaya atau waktu yang digunakan, R = pendapatan atau keuntungan dari setiap usulan dan k j = usulan pada tahap j dan persamaan rekursif mundurnya
30
dan persamaan rekursif mundurnya
f 3 ( y 3 ) = max
{R3 (k3 )}
k3
c 3 ( k 3 )≤ y 3
f j ( y j ) = max
{R (k ) + f [y j
j
j +1
j
]
− c j (k j ) }
, j = 1,2
kj cj ( kj )≤ yj
Perhitungan tahap urutan dengan demikian adalah
f 3 → f 2 → f1
