A. Perkembangan Pemrograman Dinamis
Pada persoalan praktis aplikasi pemrograman dinamis pengambilan kondisi berbeda dalam waktu, kondisi berbeda dalam ruang dan pada tingkat-tingkat (level) yang berbeda. Katakan, untuk sebuah komponen, untuk sebuah system atau sebuah sub system. Persoalan yang padanya dibuatkan keputusan secara berurutan disebut persoalan-persoalan dengan keputusan berturutan. Karena keputusan- keputusan ini dibuat dalam sejumlah tahap, mereka persoalannya juga dikatakan persoalan dengan keputusan bertahap banyak. (3)
Sejalan dengan pendapat di atas menyatakan, pemrograman dinamis adalah suatu pendekatan optimalisasi yang mengalihkan sebuah persoalan yang kompleks ke dalam sederetan persoalan-persoalan yang lebih sederhana yang mempunyai karakteristik utama sebagai tahapan prosedur-prosedur optimalisasi.(2)
Selanjutnya (3) membahas mengenai pemrograman dinamis seperti yang dipaparkan pada paragraph- paragraph berikut ini:
Pemrograman dinamis adalah sebuah teknik matematik yang sangat sesuai untuk optimalisasi dari persoalan- persoalan dengan keputusan bertahap banyak. Teknik ini dibuat oleh Richard Bellman pada awal tahun 1950-an.
Teknik pemrograman dinamis bila diterapkan, memperlihatkan atau menguraikan sebuah persoalan keputusan tahap banyak sebagai sebuah deretan dari persoalan- persoalan dengan penyelesaian bertahap tunggal. Jadi sebuah persoalan dengan N-variabel digambarkan sebagai sebuah deretan dari N buah persoalan tunggal yang diselesaikan secara berturut-turut.
Pada kebanyakan persoalan, N buah sub-persoalan ini lebih mudah diselesaikan dari program asalnya. Penguraian menjadi N buah sub-persoalan adalah dengan tujuan untuk mendapatkan penyelesaian optimal suatu persoalan asal menggunakan penyelesaian secara optimal dari sub-sub persoalan
Adalah penting untuk dicatat bahwa hanya satu teknik optimalisasi tertentu yang digunakan untuk optimasi persoalan-tunggal tidak selamanya relevan. Boleh jadi pemecahannya bervariasi dari proses berturutan sederhana sampai kalkulus diferensial atau sebuah teknik pemrograman non linear.
Persoalan dengan keputusan tahap banyak dapat juga diselesaikan dengan aplikasi langsung dari optimalisasi klasik. Akan tetapi, hal ini membutuhkan jumlah variabel yang kecil, fungsi-fungsi yang terlibat menjadi kontiniu dan dapat diturunkan (differentiable) secara kontiniu dan titik-titik optimum tidak berada pada titik batas (boundary).
Lebih jauh, persoalan harus relatif sederhana sehingga set dari persamaan-persamaan resultant dapat diselesaikan apakah secara analisis atau numerik. Teknik-teknik pemrograman non linear dapat digunakan untuk menyelesaikan secara lebih mudah persoalan- persoalan dengan keputusan bertahap yang ruwet (complicated). Tetapi aplikasi-aplikasi membutuhkan variabel-variabel yang kontiniu dan sebuah pengetahuan awal mengenai daerah maksimum dan minimum global. Pada keseluruhan kasus ini, pemakaian dari variabel-variabel stochastic membuat persoalan menjadi sangat kompleks dan bertele-tele. Persoalan ini tidak dapat diselesaikan kecuali dengan menggunakan beberapa pendekatan seperti optimisasi bersyarat kesempatan (change constained optimization).
Pemrograman Dinamis, pada sisi lain dapat berkesesuaian dengan variabel-variabel diskrit, tidak cembung (non convex) da fungsi-fungsi yang tidak dapat diturunkan (non differentiable). Secara umum, pemrograman ini dapat memasuki sejumlah variabel stokastik dengan modifikasi sederhana dari prosedur deterministic. Pemrograman dinamis menderita (mengalami) kekurangan dari apa yang disebut sebuah major drawback, dikenal dengan curse of dimensionality. Akan tetapi, karena kekurangan ini dia cocok untuk penyelesaian yang mempunyai wilayah luas dari persoalan-persoalan rumit (complex) pada beberapa hal pembuatan keputusan.
Beberapa penyelesaian pemrograman dinamis memakai metode graf maupun digraf.
Graf adalah himpunan berhingga titik-titik V yang diszebut Vertex dan garis-garis penghubungnya E yang disebut rusuk. Sementara digraf adalah suatu graf yang setiap rusuknya mempunyai arah dari titik awal (i) ke titik akhir (j).(1)
Sementara Wood (1984), menyatakan bahwa pemrograman dinamis mempunyai keunggulan melalui bentuk skema barisan, yang mana akan memperkecil dimensi dari
persoalan-persoalan. Juga dikatakan oleh Wood, andaikan terdapat empat unit dari system pembangkitan akan memungkinkan terjadi: 24 - 1 - 15, kombinasi dari system pembangkitan tersebut. Dalam pemakaian pemrograman dinamis pada pembangkitan, terdapat kemungkinan subyektif untuk menentukan prioritas mana yang akan diambil sebagai urutan-urutan penyalaan pembangkit.
B. Penyelesaian Penjadualan Pembangkitan dengan Pemrograman Dinamis.
Terdapat komitmen yang berlaku untuk penjadualan pembangkitan, yaitu:
Tidak ada biaya pembangkitan yang nol
Karakteristik input-output linear mulai dari beban nol sampai dengan beban penuh
Tidak ada pembatasan lain
Biaya awal (pemanasan) dianggap konstan.
Selain itu, dalam penyelesaian menggunakan pemrograman dinamis berikut terdapat asumsi-asumsi:
Adanya sebuah keadaan, di mana system terdiri dari deretan (matrix) unit pembangkit dengan karakteristik khusus sedang beroperasi dan lainnya berada di luar system tersebut dan siap masuk ke dalam system.
Biaya pembangkitan awal (pemanas) dari tiap unit adalah tidak terikat waktu dan dia tidak masuk dalam kurva input-output terpakai.
Tidak terdapat biaya dalam memutuskan pembangkit keluar dari system.
Terdapat instruksi yang ketat mengenai prioritas dan pada setiap interval sejumlah kapasitas minimum yang harus dioperasikan.
C. Pendekatan Pemrograman Dinamis Mundur ke belakang (backward).
Awal dari pendekatan pemrograman dinamis adalah dengan menggunakan pendekatan mundur ke belakang (backward) dalam waktu, yang mana penyelesaian mulai dari interval terakhir dan berjalan mundur menuju titik awal.Terdapat penentuan sebanyak M interval pada periode ini. Persamaan pemrograman dinamis untuk penghitungan biaya bahan bakar total yang minimum dalam sebuah rentang waktu, diberikan oleh persamaan berikut: (2,4)
…………………………… (1)
dimana:
= biaya bahan bakar total minimum dari keadaan I dimana dalam
interval K sampai akhir dari interval M
= biaya pembangkitan minimum dalam penyuplaian beban selama
interval K pada keadaan I
= kenaikan (incremental) biaya pemanasan dari keadaan I pada
interval ke K sampai keadaan J di dalam interval ke (K+1).
= set dari keadaan –keadaan yang mungkin di dalam interval K+1.
Biaya produksi diperoleh melalui pembebanan ekonomis unit-unit
terpasang pada keadaan I.
Sebuah jalur (path) adalah sebuah penjadualan dimulai dari sebuah keadaan pada interval ke akhir interval M.
Sebuah kalor optimal (optimal path) adalah sebuah jalur biaya yang mana total biaya beban adalah minimum.
Persamaan (1) memperlihatkan dengan memberikan jalur – jalur optimal mulai dari semua keadaan individual di dalam interval ke (K+1), jalur optimal mulai dari tiap keadaan di dalam interval ke K dapat diperoleh. Ini adalah sebuah keuntungan dari metode pemrograman dinamis. Prosedur untuk menentukan penjadualan optimal dan biaya bahan bakar total minimum diperlihatkan oleh flowchart pada gambar 1 halaman berikut.
D. Pendekatan Pemrograman Dinamis dengan Langkah Maju
Pendekatan langkah mundur yang dibahas sebelumnya, tidak mengatasi banyak situasi praktis, misalnya: bila biaya pemanasan awal tidak merupakan fungsi dari waktu dan berada di luar system (off line). Pada pendekatan langkah maju mungkin lebih cocok untuk dipakai bila keadaan praktis diperhatikan, seperti keadaan sebelum penjadualan dapat diperhitungkan pada setiap keadaan (stage). Hal ini dapat dilihat pada flowchart pada gambar 2..
Gambar 1. Flowchart Penyelesaian Metode Pemrograman Dinamis dengan Metode
Langkah Mundur
Gambar 2. Flowchart Penyelesaian Metode Pemrograman Dinamis dengan Metode
Langkah Maju
Hal tersebut, termasuk hal-hal lain, menjadi alasan praktis lain untuk memilih metode langkah maju.
Algoritma rekursi yang dipakai untuk menghitung biaya minimum dalam jam K pada kombinasi I adalah:
dimana:
= biaya total terkecil untuk mencapai keadaan (K,I)
= biaya produksi untuk keadaan (K,I)
= biaya transisi dari keadaan (K-1,L) ke keadaan (K,1) dimana
keadaan (K,I) adalah kombinasi ke I dalam jam
Dalam pendekatan Pemrograman Dinamis Langkah Maju, didefenisikan sebuah strategi mengenai transisi atau jalur, dari satu keadaan pada jam yang diberikan ke keadaan lain pada jam berikut.
Tercatat di sini ada dua variabel baru : X dan N seperti yang diperlihatkan pada gambar 2
X = banyaknya keadaan untuk meninjau tiap periode
N = banyaknya strategi atau jalur untuk menyelamatkan pada tiap langkah.
Variabel-variabel ini mengendalikan usaha perhitungan (lihat gambar 3). Untuk penderetan secara lengkap, nilai maximum dari X atau N adalah 2n - 1.
Sebagai contoh, dengan penjadualan ketat dari daftar yang diinstruksikan, batas dari X adalah n, sebesar banyaknya unit pembangkit. Mengurangi jumlah n berarti membuang jadual dengan biaya tertinggi pada tiap-tiap interval waktu dan hanya menggunakan jalur atau strategi N terendah. Tidak ada jaminan bahwa jadual teoritis akan diperoleh dengan mengurangi jumlah dari strategi dan rentang penyelidikan (nilai X): hanya pengharapan dengan sebuah program khusus akan mengindifikasikan potensial sehubungan dengan pembatasan nilai X dan N di bawah batas atas mereka.
Gambar 3. Jalur-jalur Pembatas pada Algoritma PD dengan N=3 dan X=5
Gambar 4. (a) Kurva Biaya Penaikan Step Tunggal
(b) Kurva Biaya Penaikan Step Berganda
Contoh:
Pada contoh ini, tentang penyelidikan lengkap akan digunakan dan tiga kasus akan dipelajari. Pertama adalah sebuah penjualan list-prioritas, kedua menggunakan contoh yang sama dengan deretan yang lengkap. Masing-masing dari ke dua kasus pertama tersebut mengabaikan biaya start pemanasan sebagaimana juga waktu minimum pelepasan dan penggabungan. Kasus ke tiga memasukkan biaya pemanasan awal begitu pula waktu penggabungan dan pelepasan pembangkit. Empat unit pembangkit disetujui untuk melayani sebuah pola pembebanan 8 jam. Data dari unit-unit dan pola pembebanan terlihat pada tabel 1 berikut.
Tabel 1. Karakteristik Unit, Pola Beban dan Status Awal untuk kasus pada contoh
Unit Max
(MW) Min
(MW) Incremental
Heat rate
(Btu/kWh) No-load*
Cost
(R/h) Full -load
Ave cost (R/mWh) Minimum
Times (h) Initialcon-ditions
Hours off-line (-) or on-line (+)
Up Down
1 80 25 10,440 213,00 2354 4 2 -5
2 250 60 9,000 585,62 20,30 5 3 8
3 300 75 8,730 684,74 19,74 5 4 8
4 60 20 11,900 252,00 28,00 1 1 -6
Unit Startup costs Load Pattern
Hot
(R)
Colt
(R)
Cold start ( h ) Hour Load (MW)
1 150 350 4 1 450
2 170 400 5 2 500
3 500 1,100 5 3 600
4 0 02 0 4 540
5 400
6 280
7 290
8 500
Dalam usaha untuk membuat perhitungan yang dikehendaki lebih efisien, sebuah model dari karakteristik unit digunakan. Pada aplikasi praktis, dua atau tiga bagian kurva penaikan bertahap dapat digunakan, seperti terlihat pada gambar 4. Untuk contoh yang diberikan, hanya satu step tunggal antara titik-titik daya minimum dan maksimum yang digunakan. Untuk contoh ini, biaya pemanasan awal untuk dua kasus pertama diambil sebagai biaya start “dingin”. Prioritas yang diperintahkan adalah: unit 3, unit 2, unit 1, unit 4. Untuk dua kasus pertama waktu minimum gabung dan lepas diambil 1 jam untuk tiap-tiap unit.
Pada ke tiga kasus dipakai patokan kapasitas yang diintruksikan terhadap setiap unit. Ini terlihat pada tabel 2, di mana kombinasi unit atau keadaan-keadaan diinstruksikan sebagai maksimum kapasitas bersih dari tiap kombinasi.
Tabel 2. Kapasitas Yang Ditetapkan Untuk Tiap Unit
Keadaan Kombinasi Unit Kapasitas bersih maksimum untuk kombinasi
15 1111 690
14 1110 630
13 0111 610
12 0110 550
11 1011 440
10 1101 390
9 1010 380
8 0011 360
7 1100 330
6 0101 310
5 0010 300
4 0100 250
3 1001 140
2 1000 80
1 0001 60
0 0000 0
Unit 1 2 3 4
1 = unit beroperasi
0 = unit tidak beroperasi
Kasus 1.
Pada Kasus 1 unit- unit beroperasi sesuai perintah prioritas. Yang artnya, unit-unit beroperasi beroperasi sampai beban terpenuhi. Biaya total dari interval adalah jumlah dari delapan biaya pembebanan ditambah dengan biaya transisi untuk starting tiap unit-unit.
Dalam kasus awal, sebuah pembebanan maksimum sebanyak 24 harus ditentukan. Untuk kasus 1 keadaan-keadaan yang diperhatikan terdiri dari:
Nomor Keadaan Status Unit Kapasitas (MW)
5 0010 300
12 0110 550
14 1110 630
15 1111 690
Jadi terlihat di sini, prioritas untuk:
keadaan 5 = unit 3; keadaan 12 = unit 3+2; keadaan 14 = unit 3 +2 +1 dan
keadaan 15 = unit 3 + 2 +1 +4.
Untuk 4 jam pertama hanya tiga keadaan terakhir yang diharapkan, perhitungan-perhitungan contoh menggambarkan keteknikan. Seluruh komitmen yang mungkin mulai pada keadaan 12 karena ini diberikan sebagai kondisi awal. Untuk jam ke-1 biaya minimum adalah keadaan 12 dan seterusnya. Hasil-hasil untuk prioritas yang dikehendaki adalah sebagai berikut:
Jam Keadaan dengan Biaya Total Minimum Petunjuk untuk Jam Sebelumnya
1 12(9208) 12
2 12(19857) 12
3 14(32472) 12
4 12(43300) 14
- - -
Catatan : keadaan 13 tidak tercapai di dalam instruksi prioritas.
Contoh perhitungan untuk kasus 1.
Keadaan yang diperbolehkan adalah:
{} = {0010,0110,1110,1111} = {5,12,14,15}
Pada jam 0{L} ={12}, kondisi awal
J=1; jam pertama
K
15 ]
]
= 9861 + 350 = 10211
14 ]
=
= 9493 + 350 = 9843
12 ]
= 9208 + 0 = 9208
J = 2; jam ke dua
Keadaan yang adalah: { 12,14,15} = {K}
Jadi X = 3
Anggap dua strategi diberlakukan pada tiap-tiap tahap, sehingga:
N = 2 dan
{L} = {12,14}
= 11301+ min = 20860
dan seterusnya.
Kasus 2.
Pada Kasus 2 deretan lengkap dicoba dengan batas 24 -1 = 15, pembebanan tiap – tiap 8 jam. Sedemikian sehingga terjadi kemungkinan maksimum terbesar : 158 = 2,56* 109.
Untungnya, sebagian besar darinya tidak layak, karena mereka tidak dapat mensuplai kapasitas yang cukup dan dapat dibuang dengan sedikit pertolongan analisis.
Gambar 5 memperlihatkan proses perhitungan untuk 4 jam pertama bagi kasus 2 pada penggambaran tersebut, lingkaran-lingkaran menunjukkan keadaan tiap jam. Angka-angka di dalam lingkaran adalah penunjuk. Dengan demikian, mereka menunjukkan nomor keadaan pada jam sebelumnya yang menyediakan jalur pada keadaan khusus dalam jang sedang berjalan. Sebagai contoh, pada jam ke 2, biaya minimum untuk keadaan 12,13,14 dan 15 semua hasilnya diperoleh dari transisi dari keadaan di dalam jam ke 1.
Biaya-biaya yang ditunjukkan pada titik hubung adalah biaya-biaya pemanasan. Pada tiap keadaan, gambar-gambar yang terlihat adalah biaya per jam/total cost.
Gambar 5. Penggambaran kasus 1 dan 2 (4 jam pertama)
Sementara gambar 6 memperlihatkan penyelesaian lengkap untuk kasus 1 dan 2
Gambar 6. Penyelesaian lengkap untuk kasus 1 dan 2
Pada kasus 2 komitmen optimal yang tepat diperoleh. Hal itu adalah, lebih kecil pengeluaran untuk menyalakan unit dengan kapasitas yang kurang efisien, nomor 4, untuk jam ke 3 dibandingkan dengan men-start unit 1 yang lebih efisien untuk periode tersebut. Pada jam ke 3 perbedaan total biaya adalah R 165 atau R 0,104 /MWh. Ini bukan jumlah yang tidak signifikan bila dibandingkan dengan biaya bahan bakar per MWh untuk rata-rata unit thermal dengan heat rate netto 10.000Btu/kWh dan sebuah pembiayaan R 2,00 Mbtu. Penghematan sebesar R 165 setiap 3 jam adalah sama dengan R 481.000 per tahun.
Total 8 jam pembangkitan untuk kasus 2 dan 2 terlihat pada gambar 6 di atas. Pengabaian penetapan penyalaan dan pemutusan pada kasus-kasus ini mengizinkan untuk melepaskan semua unit kecuali unit 3 pada jam ke 6 dan ke 7. Perbedaan satu-satunya pada dua perjalanan pembangkitan terjadi pada jam ke 3 sebagaimana yang telah dibahas pada paragraph sebelumnya.
Kasus 3.
Pada Kasus 3. ini data asli dari unit-unit dipakai, yang mana waktu-waktu penyalaan dan pemutusan ikut diteliti. Algoritma pemrograman dinamis dengan langkah maju diulangi untuk periode 8 jam yang sama. Penderetan lengkap digunakan. Dengan demikian, batas atas dari X yang terlihat pada flowchart adalah 15, tiga nilai berbeda untuk N, jumlah strategi dikenakan pada tiap tahap, diambil pada 4,8,10. Perjalanan (trajectory) pembangkitan yang sama terlihat pada gambar 7. Akan tetapi, bila hanya empat strategi dipakai, prosedur akan gagal (dengan kata lain gagal untuk mendapatkan jalur yang mungkin ) dalam jam ke 8, sebab strategi dengan biaya terendah pada jam ke 7 telah melepaskan unit-unit yang tidak dapat di-start ulang pada jam ke 8 disebabkan karena aturan pelepasan minimum yang berlaku.
Penanggulangan praktis untuk ketidak-efisienan ini dalam metode yang terlihat pada flowchart gambar 2 (dengan langkah maju) adalah kembali ke periode sebelumnya yaitu pada jam-jam dengan beban rendah dan kadang-kadang mengambil lebih (walaupun dengan biaya yang lebih banyak) banyak strategi. Ini berarti pembebasan untuk mengambil sejumlah strategi pada tiap-tiap tahap.
Alternatif lain adalah, tentu saja metode yang digunakan adalah menjalankan semua periode dengan lebih banyak strategi yang dikenakan
Gambar 7. Hasil Kasus 3
Selanjutnya kesimpulan yang diperoleh untuk kasus 1-3 diperlihatkan pada tabel berikut yang mana tabel tersebut memperlihatkan pemakaian metode pemrograman dinamis untuk tiga buah kasus dan juga memasukkan penyelesaian praktek pada metode ini.
Tabel 7. Kesimpulan dari kasus 1-3
E. Kesimpulan
Berdasarkan pada penjelasan di atas maka dapat ditarik kesimpulan sebagai berikut:
Dalam kasus pembangkitan, pemrograman dinamis hanya mengecek suatu aturan urutan penyalaan sejumlah pembangkit, bukan mencari pembangkit mana yang pantas dinyalakan atau sebaliknya dimatikan pada keadaan beroperasi
Pemograman dinamis pada system pembangkitan hanya cocok untuk perencanaan penjadualan pembangkitan secara coba-coba (trial and error), dengan melihat biaya terendah dari berbagai kombinasi pembangkit.
Metode ini akan mengalami hambatan bila diterapkan, apabila ada pembangkit yang tiba-tiba rusak sementara pembangkit tersebut masuk dalam prioritas yang harus dijalankan.
Referensi
1. Kreyzig Erwin, Matematika Teknik Lanjutan, Buku 2, Edisi 6, John Wiley & Sons,
terjemahan Gramedia Pustaka Utama, Jakarta, 1988
2. Momoh, James A., Electric Power System Application of Optimalization, Marcel
Dekker, Inc., New York, 2001
3. Rao,S.A., Optimalization, John Wiley & Sons, New York, 1990
4. Wood, Allen J.And Brice F. Wollenberg, Power Generation, Operation and
Control, John Wiley & Sons, New York, 1984
Pada persoalan praktis aplikasi pemrograman dinamis pengambilan kondisi berbeda dalam waktu, kondisi berbeda dalam ruang dan pada tingkat-tingkat (level) yang berbeda. Katakan, untuk sebuah komponen, untuk sebuah system atau sebuah sub system. Persoalan yang padanya dibuatkan keputusan secara berurutan disebut persoalan-persoalan dengan keputusan berturutan. Karena keputusan- keputusan ini dibuat dalam sejumlah tahap, mereka persoalannya juga dikatakan persoalan dengan keputusan bertahap banyak. (3)
Sejalan dengan pendapat di atas menyatakan, pemrograman dinamis adalah suatu pendekatan optimalisasi yang mengalihkan sebuah persoalan yang kompleks ke dalam sederetan persoalan-persoalan yang lebih sederhana yang mempunyai karakteristik utama sebagai tahapan prosedur-prosedur optimalisasi.(2)
Selanjutnya (3) membahas mengenai pemrograman dinamis seperti yang dipaparkan pada paragraph- paragraph berikut ini:
Pemrograman dinamis adalah sebuah teknik matematik yang sangat sesuai untuk optimalisasi dari persoalan- persoalan dengan keputusan bertahap banyak. Teknik ini dibuat oleh Richard Bellman pada awal tahun 1950-an.
Teknik pemrograman dinamis bila diterapkan, memperlihatkan atau menguraikan sebuah persoalan keputusan tahap banyak sebagai sebuah deretan dari persoalan- persoalan dengan penyelesaian bertahap tunggal. Jadi sebuah persoalan dengan N-variabel digambarkan sebagai sebuah deretan dari N buah persoalan tunggal yang diselesaikan secara berturut-turut.
Pada kebanyakan persoalan, N buah sub-persoalan ini lebih mudah diselesaikan dari program asalnya. Penguraian menjadi N buah sub-persoalan adalah dengan tujuan untuk mendapatkan penyelesaian optimal suatu persoalan asal menggunakan penyelesaian secara optimal dari sub-sub persoalan
Adalah penting untuk dicatat bahwa hanya satu teknik optimalisasi tertentu yang digunakan untuk optimasi persoalan-tunggal tidak selamanya relevan. Boleh jadi pemecahannya bervariasi dari proses berturutan sederhana sampai kalkulus diferensial atau sebuah teknik pemrograman non linear.
Persoalan dengan keputusan tahap banyak dapat juga diselesaikan dengan aplikasi langsung dari optimalisasi klasik. Akan tetapi, hal ini membutuhkan jumlah variabel yang kecil, fungsi-fungsi yang terlibat menjadi kontiniu dan dapat diturunkan (differentiable) secara kontiniu dan titik-titik optimum tidak berada pada titik batas (boundary).
Lebih jauh, persoalan harus relatif sederhana sehingga set dari persamaan-persamaan resultant dapat diselesaikan apakah secara analisis atau numerik. Teknik-teknik pemrograman non linear dapat digunakan untuk menyelesaikan secara lebih mudah persoalan- persoalan dengan keputusan bertahap yang ruwet (complicated). Tetapi aplikasi-aplikasi membutuhkan variabel-variabel yang kontiniu dan sebuah pengetahuan awal mengenai daerah maksimum dan minimum global. Pada keseluruhan kasus ini, pemakaian dari variabel-variabel stochastic membuat persoalan menjadi sangat kompleks dan bertele-tele. Persoalan ini tidak dapat diselesaikan kecuali dengan menggunakan beberapa pendekatan seperti optimisasi bersyarat kesempatan (change constained optimization).
Pemrograman Dinamis, pada sisi lain dapat berkesesuaian dengan variabel-variabel diskrit, tidak cembung (non convex) da fungsi-fungsi yang tidak dapat diturunkan (non differentiable). Secara umum, pemrograman ini dapat memasuki sejumlah variabel stokastik dengan modifikasi sederhana dari prosedur deterministic. Pemrograman dinamis menderita (mengalami) kekurangan dari apa yang disebut sebuah major drawback, dikenal dengan curse of dimensionality. Akan tetapi, karena kekurangan ini dia cocok untuk penyelesaian yang mempunyai wilayah luas dari persoalan-persoalan rumit (complex) pada beberapa hal pembuatan keputusan.
Beberapa penyelesaian pemrograman dinamis memakai metode graf maupun digraf.
Graf adalah himpunan berhingga titik-titik V yang diszebut Vertex dan garis-garis penghubungnya E yang disebut rusuk. Sementara digraf adalah suatu graf yang setiap rusuknya mempunyai arah dari titik awal (i) ke titik akhir (j).(1)
Sementara Wood (1984), menyatakan bahwa pemrograman dinamis mempunyai keunggulan melalui bentuk skema barisan, yang mana akan memperkecil dimensi dari
persoalan-persoalan. Juga dikatakan oleh Wood, andaikan terdapat empat unit dari system pembangkitan akan memungkinkan terjadi: 24 - 1 - 15, kombinasi dari system pembangkitan tersebut. Dalam pemakaian pemrograman dinamis pada pembangkitan, terdapat kemungkinan subyektif untuk menentukan prioritas mana yang akan diambil sebagai urutan-urutan penyalaan pembangkit.
B. Penyelesaian Penjadualan Pembangkitan dengan Pemrograman Dinamis.
Terdapat komitmen yang berlaku untuk penjadualan pembangkitan, yaitu:
Tidak ada biaya pembangkitan yang nol
Karakteristik input-output linear mulai dari beban nol sampai dengan beban penuh
Tidak ada pembatasan lain
Biaya awal (pemanasan) dianggap konstan.
Selain itu, dalam penyelesaian menggunakan pemrograman dinamis berikut terdapat asumsi-asumsi:
Adanya sebuah keadaan, di mana system terdiri dari deretan (matrix) unit pembangkit dengan karakteristik khusus sedang beroperasi dan lainnya berada di luar system tersebut dan siap masuk ke dalam system.
Biaya pembangkitan awal (pemanas) dari tiap unit adalah tidak terikat waktu dan dia tidak masuk dalam kurva input-output terpakai.
Tidak terdapat biaya dalam memutuskan pembangkit keluar dari system.
Terdapat instruksi yang ketat mengenai prioritas dan pada setiap interval sejumlah kapasitas minimum yang harus dioperasikan.
C. Pendekatan Pemrograman Dinamis Mundur ke belakang (backward).
Awal dari pendekatan pemrograman dinamis adalah dengan menggunakan pendekatan mundur ke belakang (backward) dalam waktu, yang mana penyelesaian mulai dari interval terakhir dan berjalan mundur menuju titik awal.Terdapat penentuan sebanyak M interval pada periode ini. Persamaan pemrograman dinamis untuk penghitungan biaya bahan bakar total yang minimum dalam sebuah rentang waktu, diberikan oleh persamaan berikut: (2,4)
…………………………… (1)
dimana:
= biaya bahan bakar total minimum dari keadaan I dimana dalam
interval K sampai akhir dari interval M
= biaya pembangkitan minimum dalam penyuplaian beban selama
interval K pada keadaan I
= kenaikan (incremental) biaya pemanasan dari keadaan I pada
interval ke K sampai keadaan J di dalam interval ke (K+1).
= set dari keadaan –keadaan yang mungkin di dalam interval K+1.
Biaya produksi diperoleh melalui pembebanan ekonomis unit-unit
terpasang pada keadaan I.
Sebuah jalur (path) adalah sebuah penjadualan dimulai dari sebuah keadaan pada interval ke akhir interval M.
Sebuah kalor optimal (optimal path) adalah sebuah jalur biaya yang mana total biaya beban adalah minimum.
Persamaan (1) memperlihatkan dengan memberikan jalur – jalur optimal mulai dari semua keadaan individual di dalam interval ke (K+1), jalur optimal mulai dari tiap keadaan di dalam interval ke K dapat diperoleh. Ini adalah sebuah keuntungan dari metode pemrograman dinamis. Prosedur untuk menentukan penjadualan optimal dan biaya bahan bakar total minimum diperlihatkan oleh flowchart pada gambar 1 halaman berikut.
D. Pendekatan Pemrograman Dinamis dengan Langkah Maju
Pendekatan langkah mundur yang dibahas sebelumnya, tidak mengatasi banyak situasi praktis, misalnya: bila biaya pemanasan awal tidak merupakan fungsi dari waktu dan berada di luar system (off line). Pada pendekatan langkah maju mungkin lebih cocok untuk dipakai bila keadaan praktis diperhatikan, seperti keadaan sebelum penjadualan dapat diperhitungkan pada setiap keadaan (stage). Hal ini dapat dilihat pada flowchart pada gambar 2..
Gambar 1. Flowchart Penyelesaian Metode Pemrograman Dinamis dengan Metode
Langkah Mundur
Gambar 2. Flowchart Penyelesaian Metode Pemrograman Dinamis dengan Metode
Langkah Maju
Hal tersebut, termasuk hal-hal lain, menjadi alasan praktis lain untuk memilih metode langkah maju.
Algoritma rekursi yang dipakai untuk menghitung biaya minimum dalam jam K pada kombinasi I adalah:
dimana:
= biaya total terkecil untuk mencapai keadaan (K,I)
= biaya produksi untuk keadaan (K,I)
= biaya transisi dari keadaan (K-1,L) ke keadaan (K,1) dimana
keadaan (K,I) adalah kombinasi ke I dalam jam
Dalam pendekatan Pemrograman Dinamis Langkah Maju, didefenisikan sebuah strategi mengenai transisi atau jalur, dari satu keadaan pada jam yang diberikan ke keadaan lain pada jam berikut.
Tercatat di sini ada dua variabel baru : X dan N seperti yang diperlihatkan pada gambar 2
X = banyaknya keadaan untuk meninjau tiap periode
N = banyaknya strategi atau jalur untuk menyelamatkan pada tiap langkah.
Variabel-variabel ini mengendalikan usaha perhitungan (lihat gambar 3). Untuk penderetan secara lengkap, nilai maximum dari X atau N adalah 2n - 1.
Sebagai contoh, dengan penjadualan ketat dari daftar yang diinstruksikan, batas dari X adalah n, sebesar banyaknya unit pembangkit. Mengurangi jumlah n berarti membuang jadual dengan biaya tertinggi pada tiap-tiap interval waktu dan hanya menggunakan jalur atau strategi N terendah. Tidak ada jaminan bahwa jadual teoritis akan diperoleh dengan mengurangi jumlah dari strategi dan rentang penyelidikan (nilai X): hanya pengharapan dengan sebuah program khusus akan mengindifikasikan potensial sehubungan dengan pembatasan nilai X dan N di bawah batas atas mereka.
Gambar 3. Jalur-jalur Pembatas pada Algoritma PD dengan N=3 dan X=5
Gambar 4. (a) Kurva Biaya Penaikan Step Tunggal
(b) Kurva Biaya Penaikan Step Berganda
Contoh:
Pada contoh ini, tentang penyelidikan lengkap akan digunakan dan tiga kasus akan dipelajari. Pertama adalah sebuah penjualan list-prioritas, kedua menggunakan contoh yang sama dengan deretan yang lengkap. Masing-masing dari ke dua kasus pertama tersebut mengabaikan biaya start pemanasan sebagaimana juga waktu minimum pelepasan dan penggabungan. Kasus ke tiga memasukkan biaya pemanasan awal begitu pula waktu penggabungan dan pelepasan pembangkit. Empat unit pembangkit disetujui untuk melayani sebuah pola pembebanan 8 jam. Data dari unit-unit dan pola pembebanan terlihat pada tabel 1 berikut.
Tabel 1. Karakteristik Unit, Pola Beban dan Status Awal untuk kasus pada contoh
Unit Max
(MW) Min
(MW) Incremental
Heat rate
(Btu/kWh) No-load*
Cost
(R/h) Full -load
Ave cost (R/mWh) Minimum
Times (h) Initialcon-ditions
Hours off-line (-) or on-line (+)
Up Down
1 80 25 10,440 213,00 2354 4 2 -5
2 250 60 9,000 585,62 20,30 5 3 8
3 300 75 8,730 684,74 19,74 5 4 8
4 60 20 11,900 252,00 28,00 1 1 -6
Unit Startup costs Load Pattern
Hot
(R)
Colt
(R)
Cold start ( h ) Hour Load (MW)
1 150 350 4 1 450
2 170 400 5 2 500
3 500 1,100 5 3 600
4 0 02 0 4 540
5 400
6 280
7 290
8 500
Dalam usaha untuk membuat perhitungan yang dikehendaki lebih efisien, sebuah model dari karakteristik unit digunakan. Pada aplikasi praktis, dua atau tiga bagian kurva penaikan bertahap dapat digunakan, seperti terlihat pada gambar 4. Untuk contoh yang diberikan, hanya satu step tunggal antara titik-titik daya minimum dan maksimum yang digunakan. Untuk contoh ini, biaya pemanasan awal untuk dua kasus pertama diambil sebagai biaya start “dingin”. Prioritas yang diperintahkan adalah: unit 3, unit 2, unit 1, unit 4. Untuk dua kasus pertama waktu minimum gabung dan lepas diambil 1 jam untuk tiap-tiap unit.
Pada ke tiga kasus dipakai patokan kapasitas yang diintruksikan terhadap setiap unit. Ini terlihat pada tabel 2, di mana kombinasi unit atau keadaan-keadaan diinstruksikan sebagai maksimum kapasitas bersih dari tiap kombinasi.
Tabel 2. Kapasitas Yang Ditetapkan Untuk Tiap Unit
Keadaan Kombinasi Unit Kapasitas bersih maksimum untuk kombinasi
15 1111 690
14 1110 630
13 0111 610
12 0110 550
11 1011 440
10 1101 390
9 1010 380
8 0011 360
7 1100 330
6 0101 310
5 0010 300
4 0100 250
3 1001 140
2 1000 80
1 0001 60
0 0000 0
Unit 1 2 3 4
1 = unit beroperasi
0 = unit tidak beroperasi
Kasus 1.
Pada Kasus 1 unit- unit beroperasi sesuai perintah prioritas. Yang artnya, unit-unit beroperasi beroperasi sampai beban terpenuhi. Biaya total dari interval adalah jumlah dari delapan biaya pembebanan ditambah dengan biaya transisi untuk starting tiap unit-unit.
Dalam kasus awal, sebuah pembebanan maksimum sebanyak 24 harus ditentukan. Untuk kasus 1 keadaan-keadaan yang diperhatikan terdiri dari:
Nomor Keadaan Status Unit Kapasitas (MW)
5 0010 300
12 0110 550
14 1110 630
15 1111 690
Jadi terlihat di sini, prioritas untuk:
keadaan 5 = unit 3; keadaan 12 = unit 3+2; keadaan 14 = unit 3 +2 +1 dan
keadaan 15 = unit 3 + 2 +1 +4.
Untuk 4 jam pertama hanya tiga keadaan terakhir yang diharapkan, perhitungan-perhitungan contoh menggambarkan keteknikan. Seluruh komitmen yang mungkin mulai pada keadaan 12 karena ini diberikan sebagai kondisi awal. Untuk jam ke-1 biaya minimum adalah keadaan 12 dan seterusnya. Hasil-hasil untuk prioritas yang dikehendaki adalah sebagai berikut:
Jam Keadaan dengan Biaya Total Minimum Petunjuk untuk Jam Sebelumnya
1 12(9208) 12
2 12(19857) 12
3 14(32472) 12
4 12(43300) 14
- - -
Catatan : keadaan 13 tidak tercapai di dalam instruksi prioritas.
Contoh perhitungan untuk kasus 1.
Keadaan yang diperbolehkan adalah:
{} = {0010,0110,1110,1111} = {5,12,14,15}
Pada jam 0{L} ={12}, kondisi awal
J=1; jam pertama
K
15 ]
]
= 9861 + 350 = 10211
14 ]
=
= 9493 + 350 = 9843
12 ]
= 9208 + 0 = 9208
J = 2; jam ke dua
Keadaan yang adalah: { 12,14,15} = {K}
Jadi X = 3
Anggap dua strategi diberlakukan pada tiap-tiap tahap, sehingga:
N = 2 dan
{L} = {12,14}
= 11301+ min = 20860
dan seterusnya.
Kasus 2.
Pada Kasus 2 deretan lengkap dicoba dengan batas 24 -1 = 15, pembebanan tiap – tiap 8 jam. Sedemikian sehingga terjadi kemungkinan maksimum terbesar : 158 = 2,56* 109.
Untungnya, sebagian besar darinya tidak layak, karena mereka tidak dapat mensuplai kapasitas yang cukup dan dapat dibuang dengan sedikit pertolongan analisis.
Gambar 5 memperlihatkan proses perhitungan untuk 4 jam pertama bagi kasus 2 pada penggambaran tersebut, lingkaran-lingkaran menunjukkan keadaan tiap jam. Angka-angka di dalam lingkaran adalah penunjuk. Dengan demikian, mereka menunjukkan nomor keadaan pada jam sebelumnya yang menyediakan jalur pada keadaan khusus dalam jang sedang berjalan. Sebagai contoh, pada jam ke 2, biaya minimum untuk keadaan 12,13,14 dan 15 semua hasilnya diperoleh dari transisi dari keadaan di dalam jam ke 1.
Biaya-biaya yang ditunjukkan pada titik hubung adalah biaya-biaya pemanasan. Pada tiap keadaan, gambar-gambar yang terlihat adalah biaya per jam/total cost.
Gambar 5. Penggambaran kasus 1 dan 2 (4 jam pertama)
Sementara gambar 6 memperlihatkan penyelesaian lengkap untuk kasus 1 dan 2
Gambar 6. Penyelesaian lengkap untuk kasus 1 dan 2
Pada kasus 2 komitmen optimal yang tepat diperoleh. Hal itu adalah, lebih kecil pengeluaran untuk menyalakan unit dengan kapasitas yang kurang efisien, nomor 4, untuk jam ke 3 dibandingkan dengan men-start unit 1 yang lebih efisien untuk periode tersebut. Pada jam ke 3 perbedaan total biaya adalah R 165 atau R 0,104 /MWh. Ini bukan jumlah yang tidak signifikan bila dibandingkan dengan biaya bahan bakar per MWh untuk rata-rata unit thermal dengan heat rate netto 10.000Btu/kWh dan sebuah pembiayaan R 2,00 Mbtu. Penghematan sebesar R 165 setiap 3 jam adalah sama dengan R 481.000 per tahun.
Total 8 jam pembangkitan untuk kasus 2 dan 2 terlihat pada gambar 6 di atas. Pengabaian penetapan penyalaan dan pemutusan pada kasus-kasus ini mengizinkan untuk melepaskan semua unit kecuali unit 3 pada jam ke 6 dan ke 7. Perbedaan satu-satunya pada dua perjalanan pembangkitan terjadi pada jam ke 3 sebagaimana yang telah dibahas pada paragraph sebelumnya.
Kasus 3.
Pada Kasus 3. ini data asli dari unit-unit dipakai, yang mana waktu-waktu penyalaan dan pemutusan ikut diteliti. Algoritma pemrograman dinamis dengan langkah maju diulangi untuk periode 8 jam yang sama. Penderetan lengkap digunakan. Dengan demikian, batas atas dari X yang terlihat pada flowchart adalah 15, tiga nilai berbeda untuk N, jumlah strategi dikenakan pada tiap tahap, diambil pada 4,8,10. Perjalanan (trajectory) pembangkitan yang sama terlihat pada gambar 7. Akan tetapi, bila hanya empat strategi dipakai, prosedur akan gagal (dengan kata lain gagal untuk mendapatkan jalur yang mungkin ) dalam jam ke 8, sebab strategi dengan biaya terendah pada jam ke 7 telah melepaskan unit-unit yang tidak dapat di-start ulang pada jam ke 8 disebabkan karena aturan pelepasan minimum yang berlaku.
Penanggulangan praktis untuk ketidak-efisienan ini dalam metode yang terlihat pada flowchart gambar 2 (dengan langkah maju) adalah kembali ke periode sebelumnya yaitu pada jam-jam dengan beban rendah dan kadang-kadang mengambil lebih (walaupun dengan biaya yang lebih banyak) banyak strategi. Ini berarti pembebasan untuk mengambil sejumlah strategi pada tiap-tiap tahap.
Alternatif lain adalah, tentu saja metode yang digunakan adalah menjalankan semua periode dengan lebih banyak strategi yang dikenakan
Gambar 7. Hasil Kasus 3
Selanjutnya kesimpulan yang diperoleh untuk kasus 1-3 diperlihatkan pada tabel berikut yang mana tabel tersebut memperlihatkan pemakaian metode pemrograman dinamis untuk tiga buah kasus dan juga memasukkan penyelesaian praktek pada metode ini.
Tabel 7. Kesimpulan dari kasus 1-3
E. Kesimpulan
Berdasarkan pada penjelasan di atas maka dapat ditarik kesimpulan sebagai berikut:
Dalam kasus pembangkitan, pemrograman dinamis hanya mengecek suatu aturan urutan penyalaan sejumlah pembangkit, bukan mencari pembangkit mana yang pantas dinyalakan atau sebaliknya dimatikan pada keadaan beroperasi
Pemograman dinamis pada system pembangkitan hanya cocok untuk perencanaan penjadualan pembangkitan secara coba-coba (trial and error), dengan melihat biaya terendah dari berbagai kombinasi pembangkit.
Metode ini akan mengalami hambatan bila diterapkan, apabila ada pembangkit yang tiba-tiba rusak sementara pembangkit tersebut masuk dalam prioritas yang harus dijalankan.
Referensi
1. Kreyzig Erwin, Matematika Teknik Lanjutan, Buku 2, Edisi 6, John Wiley & Sons,
terjemahan Gramedia Pustaka Utama, Jakarta, 1988
2. Momoh, James A., Electric Power System Application of Optimalization, Marcel
Dekker, Inc., New York, 2001
3. Rao,S.A., Optimalization, John Wiley & Sons, New York, 1990
4. Wood, Allen J.And Brice F. Wollenberg, Power Generation, Operation and
Control, John Wiley & Sons, New York, 1984
Postingan
Gambar flowchartnya mana ya?