BAB 2 LANDASAN TEORI
2.1 Proses Alokasi Andaikan terdapat sejumlah sumber daya modal tertentu, yaitu dapat berupa uang untuk investasi, mesin cetak , bahan bakar untuk kendaraan dan lain sebagainya. Suatu permasalahan yang sering terjadi yaitu bagaimana suatu modal dapat digunakan dengan cara yang berbeda. Dalam hal ini, masing-masing aplikasi yang mungkin disebut dengan kegiatan (activity). Adapun asumsi dasar yang perlu diperhatikan adalah: 1. Keuntungan dari suatu kegiatan tidak bergantung pada keuntungan dari kegiatan lainnya. 2. Jumlah keuntungan secara menyeluruh dapat diperoleh dari penjumlahan keuntungan tiap kegiatan. Permasalahan dasarnya adalah bagaimana membagi sumber daya modal pada setiap kegiatan untuk memaksimumkan fungsi keutungan. Secara matematis, permasalahan pengalokasian modal dapat diformulasikan sebagai berikut: max
,
,…,
subject to:
2.1
,
= fungsi keuntungan (return) pada kegiatan i dengan
di mana:
sumber
daya modal yang tersedia.
0,1, … ,
1, 2, … ,
1, 2, … , xiii
Universitas Sumatera Utara
Berdasarkan rumusan persoalan di atas, dapat digambarkan grafik fungsi return
Fungsi return
sebagai berikut:
Alokasi modal
Gambar 2.1 Grafik Fungsi Return Gambar di atas menunjukkan bahwa fungsi keuntungan bergantung pada jumlah modal yang dialokasikan dalam suatu kegiatan. Dimulai dari jumlah modal yang paling sedikit (
0 ) dengan tidak mendapatkan keuntungan, hingga batas
jumlah modal yang disediakan.
2.2 Program Dinamik Program dinamik adalah suatu teknik matematika untuk mengoptimalkan proses pengambilan keputusan, yaitu dengan membuat serangkaian keputusan yang saling berkaitan. Definisi 2.1. Tahap (stage) merupakan bagian dari masalah yang memiliki beberapa alternatif yang saling terpisah dimana alternatif yang terbaik akan ditentukan. Definisi 2.2. State merupakan mata rantai yang menghubungkan satu tahap dengan tahap lainnya.
xiv Universitas Sumatera Utara
2.2.1
Prinsip Keoptimalan
Pendekatan program dinamik didasarkan pada Prinsip optimisasi Bellman. Bellman (1950) mengemukakan bahwa “Suatu kebijakan optimal mempunyai sifat bahwa apapun keadaan dan keputusan awal, keputusan berikutnya harus membentuk suatu kebijakan optimal dengan memperhatikan keadaan dari hasil keputusan pertama”. Prinsip ini mengandung arti bahwa : 1. Diperkenankan untuk mengambil keputusan yang layak bagi tahap persoalan yang masih tersisa tanpa melihat kembali keputusan-keputusan masa lalu atau tahap-tahap terdahulu. 2. Dalam rangkaian keputusan yang telah diambil, hasil dari masing-masing tergantung pada hasil keputusan sebelumnya dalam rangkaian. Misalkan jika telah diambil keputusan yang salah pada tahap pertama atau tahap kedua, bukan berarti keputusan yang benar tidak dapat diambil pada tahap ketiga, keempat dan seterusnya. Stuart E. Dreyfuse dan Averill M. Law (1977) dalam bukunya yang berjudul “Mathematics In Science and Engineering: The Art and Theory of Dynamic Programming” mendefinisikan fungsi nilai optimal sebagai: max
2.2
, ,..,
di mana:
perolehan keuntungan maksimum dari kegiatan dengan
2.2.2
sampai
,
unit sumber daya yang tersisa untuk dialokasikan.
= alokasi untuk kegiatan 0,1, … ,
Karakteristik Persoalan Program Dinamik
Salah satu cara untuk mengetahui bahwa suatu kondisi dapat diformulasikan sebagai persoalan program dinamik, yaitu pembentukan struktur dasar persoalan xv Universitas Sumatera Utara
secara bertahap. Struktur dasar tersebut adalah karakteristik persoalan program dinamik yang disajikan sebagai berikut: 1. Persoalan dapat dibagi menjadi beberapa tahap (stage), yang pada setiap tahap hanya diambil satu keputusan. 2. Masing-masing tahap terdiri dari sejumlah status (state) yang berhubungan dengan
tahap
tersebut.
Secara
umum,
state
merupakan
bermacam
kemungkinan masukan yang ada pada tahap tersebut. 3. Hasil dari keputusan yang diambil pada setiap tahap ditransformasikan dari status yang bersangkutan ke status berikutnya pada tahap berikutnya. 4. Ongkos (cost) pada suatu tahap meningkat secara teratur (steadily) dengan bertambahnya jumlah tahapan. 5. Ongkos pada suatu tahap bergantung pada ongkos tahap-tahap yang sudah berjalan dan ongkos pada tahap tersebut. 6. Keputusan terbaik pada suatu tahap bersifat saling bebas terhadap keputusan yang dilakukan pada tahap sebelumnya. 7. Adanya hubungan rekursif yang mengidentifikasikan keputusan terbaik untuk setiap status pada tahap pada tahap
memberikan keputusan terbaik untuk setiap status
1.
8. Prinsip optimalitas berlaku pada persoalan tersebut.
2.2.3 Pendekatan Penyelesaian Program Dinamik Pendekatan Penyelesaian yang digunakan dalam program dinamik ada 2 cara, yaitu: 1. Perhitungan Maju (Forward) Pada perhitungan maju, suatu persoalan program dinamik umumnya dapat diselesaikan dengan menghitung proses rekursif ke
terlebih dahulu, lalu dilanjutkan berdasarkan
dan seterusnya.
Urutan perhitungannya adalah: xvi Universitas Sumatera Utara
→ Di mana
→
→⋯→
merupakan fungsi awal dari fungsi rekursif dan
merupakan fungsi
akhir. Diagram cara perhitungan maju:
: fungsi keuntungan pada tahap : variabel keadaan pada tahap n
2. Perhitungan Mundur (Backward) Pada perhitungan mundur, suatu persoalan program dinamik diselesaikan dengan menghitung berakhir di
terlebih dahulu, lalu dilanjutkan berdasarkan proses rekursif dan .
Urutan perhitungannya adalah: → Di mana
→
→⋯→
merupakan fungsi awal dari fungsi rekursif dan
merupakan fungsi
akhir. Diagram cara perhitungan mundur:
: fungsi keuntungan pada tahap : variabel keadaan pada tahap n Perbedaan dari kedua cara perhitungan ini terletak pada rumusan keadaan. Pada perhitungan maju, keadaan
dirumuskan sebagai alokasi untuk tahap dan
1 tahap sebelumnya. Sedangkan pada cara perhitungan mundur, keadaan
xvii Universitas Sumatera Utara
dirumuskan sebagai alokasi untuk tahap dan
tahap berikutnya. Dalam
memecahkan suatu persoalan tidak dapat segera diketahui cara mana yang lebih mudah digunakan. Oleh karena itu, jika mengalami kesulitan untuk merumuskan persoalan dengan menggunakan perhitungan maju maka dapat menggunakan cara perhitungan mundur.
2.3 Metode Lagrange Metode pengali Lagrange merupakan sebuah teknik dalam menyelesaikan masalah optimasi dengan kendala persamaan. Inti dari metode pengali Lagrange adalah mengubah persoalan titik ekstrim terkendala menjadi persoalan ekstrim bebas kendala. Fungsi yang terbentuk dari tranformasi tersebut dinamakan fungsi Lagrange. Misalkan permasalahan yang dihadapi adalah: ,
Maksimumkan/Minimumkan:
,
,…,
(2.3) , ,
Dengan kendala: , , ... , , Disini jika terjadi bahwa
maka tidak dapat diselesaikan. Akan tetapi untuk
dapat menyelesaikannya maka
(jumlah kendala lebih kecil daripada
variabel). Metode ini dimulai dengan pembentukan fungsi lagrange yang didefinisikan sebagai :
,
2.4
Arti dari pengali lagrange secara fisik yang menarik misalkan terdapat permasalahan optimasi dengan satu kendala sebagai berikut: Maks/Min :
(2.5)
Dengan kendala :
xviii Universitas Sumatera Utara
Fungsi lagrangenya adalah ,
(2.6)
Syarat perlu untuk penyelesaian di atas adalah 0 untuk
1,2, … ,
0 Maka persamaan di atas menghasilkan :
0 untuk
1,2, … ,
0 atau Diperoleh:
0 untuk
1,2, … ,
Atau
0
Atau
Atau
xix Universitas Sumatera Utara
Karena ∗
atau
Dapat diambil kesimpulan bahwa dari persamaan di atas pada penyelesaian optimum, perubahan fungsi tujuan
berbanding lurus dengan perubahan kendala
dengan faktor sebesar pengali lagrange .
2.3.1 Monotonicity dalam
Jika suatu nilai
bertambah dari 0 sampai ∞, maka ∑
monoton. Sehingga nilai
berkurang secara
dapat diperkirakan sebagai harga (price).
̅
,
2.7
2.8
Jika 0
, dari sifat maksimasi diketahui 2.9 2.10
Dari persamaan (2.8) dan (2.9) diperoleh 2.11 Sehingga, 2.12 Karena
0, diperoleh hasil yang diinginkan
xx Universitas Sumatera Utara
2.13 Hasil dari persamaan (2.12) digabungkan dengan persamaan (2.8) diperoleh 2.14
di mana
.
Monotonicity ini menyederhanakan penentuan nilai
dengan diberikannya nilai
.
xxi Universitas Sumatera Utara
