UKURAN DEVIASI DALAM STOKASTIK PROGRAMMING DENGAN RECOURSE INTEGER CAMPURAN
TESIS
Oleh MUJIO 077021066/MT
SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
UKURAN DEVIASI DALAM STOKASTIK PROGRAMMING DENGAN RECOURSE INTEGER CAMPURAN
TESIS
Diajukan Sebagai Salah Satu Syarat untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Sekolah Pascasarjana Universitas Sumatera Utara
Oleh MUJIO 077021066/MT
SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
Judul Tesis
: UKURAN DEVIASI DALAM STOKASTIK PROGRAM MING DENGAN RECOURSE INTEGER CAMPURAN Nama Mahasiswa : Mujio Nomor Pokok : 077021066 Program Studi : Matematika
Menyetujui, Komisi Pembimbing
(Prof. Dr. Herman Mawengkang) Ketua
(Dr. Tulus, M.Si) Anggota
Ketua Program Studi
Direktur
(Prof. Dr. Herman Mawengkang)
(Prof. Dr. Ir. T.Chairun Nisa. B,M.Sc)
Tanggal lulus: 29 Mei 2009
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
Telah diuji pada Tanggal: 29 Mei 2009
PANITIA PENGUJI TESIS Ketua
: Prof. Dr. Herman Mawengkang
Anggota
: 1. Dr. Tulus, M.Si 2. Prof. Dr. Opim Salim S, M.Sc 3. Drs. Open Darnius, M.Sc
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
ABSTRAK Tesis ini bertujuan memberi masukan terhadap pengukuran yang sistematis dari suatu resiko dalam memutuskan persoalan ketidakpastian. Pembahasan dibatasi untuk deviasi yang sering digunakan untuk mengukur resiko yaitu Standar Deviasi,Standar Semideviasi, Absolut semideviasi dan Ekspektasi Berlebih dari sebuah target yang ditetapkan. Memilih diantara pilihan resiko adalah isu utama dalam teori keputusan ditinjau dari pendekatan aksiomatik ordo dominasi stokastik dan ukuran resiko koheren. Selanjutnya dibahas ukuran deviasi dan diasosiasikan dengan model-model Mean-Risiko yang terkait dalam konteks konsep ini. Model Mean-Resiko adalah sebuah problema optimasi bicriteria pada rumpun variabelvariabel acak yang dikaitkan dengan sebuah fungsi biaya. Pandangan mengenai persoalan keputusan yang menghasil struktur dan stabilitas dari model-model mean-resiko dari struktur fungsi biaya dan menggunakan hasil-hasil ini untuk program stokastik dengan recourse, diakhiri perhatian terhadap sifat kontinuitas dan konveksitas sebuah fungsi dari persoalan optimasi. Sifat-sifat ini berperan penting terhadap implikasi yang berbeda untuk ukuran deviasi yang berbeda dan program stokastik dengan dan tanpa variabel-variabel integer tetapi dititik beratkan pada pembentuknya. Kata kunci: Program Stokastik, Ukuran Deviasi, Model Mean, Resiko, Optimisasi Integer Campuran
i Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
ABSTRACT This thesis sims to contribute to the systematic measurement of risk in decision problems under uncertainty. in particular, we intend to support the choice of a risk measure in stochastic linear programming with mixed-integer recourse. We restrict our discussion to deviation measures which include in our terminoloty such frequently used risk measures as the standard deviation, the standard semideviation, the absolute semideviation, and the expected excess of a fixed target. The choice among risky alternatives is one major issue in decision theory. We review the axiomatic approaches of stochastic dominance orders and coherent risk measures. Then, we discuss deviation measures and the associated mean risk models in the context of these concepts. A mean-risk model is a bicriteria optimization problem on a family of random variables. In stochastic programming, the random variables are liked by a cost function. We provide a general view on the underlying decision problem, derive results on the structure and the stability of the mean-risk models from the structure of the cost function, and apply these results to stochastic programming with recourse. More precisely, we conclude properties concerning the continuity and the convexity of the optimal value functions and concerning the qualitative stability of the optimization problems. These properties lead to different implications for the different deviation measures. We investigate stochastic programs with and without integer variables but focus on the former. Keyword: Stochastic Program, Deviation Measures, Mean Model, Risk, Mix Integer Optimization
ii Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
KATA PENGANTAR Pertama sekali penulis mengucapkan puji dan syukur kehadirat Allah swt yang telah memberikan Rahmat dan KaruniaNya kepada penulis ,sehingga penulis dapat menyelesaikan tesis ini sesuai dengan waktu yang dikehendaki. Tesis ini berjudul ” Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran ” yang merupakan persyaratan tugas akhir pada Program Studi Matematika SPs Universitas Sumatera Utara. Pada kesempatan yang baik ini penulis menyampaikan ucapan terima kasih yang sebesar-besarnya dan penghargaan setingi-tingginya kepada : Prof.Dr.Ir.T.Chairun Nisa. B,M.Sc selaku Direktur Sekolah Pascasarjana Universitas Sumatera Utara yang memberi kesempatan kepada penulis untuk kuliah di SPs Universitas Sumatera Utara . Prof.Dr.Herman Mawengkang selaku Ketua Program Studi Matematika SPs Universitas Sumatera Utara dan selaku Ketua pembimbing Tesis yang telah banyak membantu dalam menyelesaikan penulisan tesis ini. Dr. Tulus , M.Sc selaku anggota pembimbing penulisan tesis yang telah memberikan masukan serta membantu menyelesaikan tesis ini. Prof.Dr. Opim Salim S M.Sc, Drs.Open Darnius M.Sc selaku pembanding dan penguji, serta Seluruh Staf Pengajar , pegawai dan rekan mahasiswa angkatan 2006/2007 dan angkatan 2007/2008 pada program Magister Matematika SPs Universitas Sumatera Utara yang banyak membantu penulis selama mengikuti kuliah. Gubernur Sumatera Utara yang telah memberi bantuan bea siswa pendidikn kepada penulis melalui BAPEDASU Pengurus Yaspendhar yang telah memberi izin kepada penulis untuk kuliah di
iii Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
SPs Universitas Sumatera Utara. Istriku Nurhayati S.PdI dan anak-anak tersayang Muarif Azzuri,Sri Wahyuni serta Fahri Muhayat, juga rekan-rekan Guru SMA Harapan 1 dan 2 yang memberi motivasi dan dorongan kepada penulis untuk mengikuti perkuliahan di S.Ps Universitas Sumatera Utara serta menyelesaikan perkuliahan ini. Penulis menyadari sebagai manusia biasa,yang tidak terlepas dari kesalahan dan kekhilafan terutama dalam menulis tesis ini, terima kasih atas saransaran yang penulis terima baik dari pembimbing maupun pembanding yang sangat berguna untuk perbaikan, demi sempurnanya tesis ini dan semoga berguna dan bermanfaat bagi pembaca dan pihak-pihak yang memerlukan.
Medan, Mei 2009 Penulis,
Mujio
iv Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
RIWAYAT HIDUP Penulis dilahirkan di Joho(Jawa),Kota Madia Kediri ,Jawa Timur pada tanggal 10 April 1957, merupakan anak pertama dari 6 bersaudara dari ayah Kedah(Alm) dan Ibu Supiyah (Almh) . Menamatkan Sekolah Dasar Negeri di Simpang Pulau Rambung Kec. Bohorok, Kab.Langkat tahun 1972 , Sekolah Menengah Pertama (SMP) Negeri Tanjung Langkat, Kec.Salapian, Kab.Langkat Tahun 1975, Sekolah Menengah Atas (SMA) persiapan Kuala, Kec.Kuala, Kab. Langkat jurusan IPA Tahun 1979 , kemudian tahun 1980 kuliah di Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara jurusan Matematika dan memperoleh gelar sarjana Matematika pada tahun 1987. Sejak masih menjadi mahasiswa penulis sudah mengajar matematika di berbagai SMA dan SMK Swasta di Medan dan setelah meraih gelar sarjana menjadi Dosen Di Institut Sains dan Teknologi Pardede dan kemudian pindah ke Fakultas Teknik Universitas Darma Agung hingga sekarang. Tahun 2003 memperoleh sertifikat mengajar (AktaIV) dan sejak tahun 2005 hingga sekarang dipercaya memimpin SMA Harapan 2 Medan.
vi Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
DAFTAR SIMBOL
Rentang Bilangan N
= himpunan {1, 2, 3, . . .}
Z+
= himpunan {0, 1, 2, . . .}
R
= himpunan (−∞, ∞)
R+
= himpunan [0, ∞)
Probabilitas dan Ukurannya Ω
= ruang kejadian
ω
= elemen dari Ω, kejadian
A
= sigma aljabar dalam Ω
IP
= ukuran probabilitas pada Ω
(Ω, ω, IP )
= ruang probabilitas
ξ
= variabel acak pada (Ω, ω, IP ) dengan realisasi didalam R
µ
= ukuran bayangan yang di induksi oleh ξ
Bl
= aljabar Borel dalam Rl
E
= nilai ekspektasi
R
= ukuran resiko umum
D2
= deviasi standar
Dp
= sentral deviasi order p
Dp+
= semideviasi order p
Epη
= perkiraan kelebihan dari sebuah target η order p
Fungsi Biaya Acak x
= variabel keputusan dalam Rn
ξ Z¯
= parameter acak dalam Rl = fungsi biaya acak yang dipetakan dari Rn × Rl ke R vii
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
QE
= fungsi nilai ekspektasi yang dipetakan dari Rn ke R
QR
= fungsi resiko umum yang dipetakan dari Rn ke R
Program Stokastik x
= variabel tahap-pertama
y
= variabel tahap-kedua
T
= matriks teknologi
W
= matriks recourse
Φ
= fungsi recourse
viii Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
DAFTAR ISI Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
i
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ii
KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iii
RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vi
DAFTAR SIMBOL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
viii
DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ix
BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2 Perumusan Masalah . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.4 Kontribusi Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.5 Metode Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
BAB 2 TINJAUAN PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
BAB 3 LANDASAN TEORI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3.1 Pengertian Program Stokastik . . . . . . . . . . . . . . . . . . . . . .
10
3.2 Program Stokastik Linier . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.3 Program Stokastik Integer Campuran . . . . . . . . . . . . . . . . .
14
3.4 Program Stokastik Linier Dengan Recourse Integer Campuran
15
3.5 Ukuran Deviasi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
3.6 Dominasi stokastik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
ix Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
3.7 Ukuran Resiko Konveks dan Ukuran Resiko Koheren . . . . . .
28
BAB 4 PEMODELAN MEAN-RESIKO, STRUKTUR DAN ALGORITMA PEMBAHASAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
4.1 Model Mean Resiko . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
4.2 Struktur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
4.3 Model Nilai Ekspektasi . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
4.4 Ukuran Deviasi Program Stokastik Linier Dengan Recourse Integer Campuran. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
BAB 5 KESIMPULAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
x Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
BAB 1 PENDAHULUAN
1.1 Latar Belakang Pada umumnya data yang digunakan pada penelitian yang sudah dilakukan diasumsikan bahwa semua parameter ataupun variabelnya sudah tertentu atau sudah pasti (deterministik). Dalam situasi perencanaan produksi yang demikian ini yaitu informasi data saat itu sudah tertentu (deterministik), tentunya digunakan optimasi deterministik, namun untuk masa yang akan datang data yang diperlukan mengandung ketidakpastian (Stokastik). Pada prakteknya, problema perencanaan didalam mengambil keputusan optimal dicari dengan kendala ketidakpastian problema data (Birge, 1997). Problema-problema ini sering dimulai dari model-model perencanaan, dimana keputusannya dibuat pada saat ini, sebagai efeknya hanya diketahui pada masa yang akan datang. Beberapa data empiris ada yang hilang atau menyimpang, atau kendalanya berpengaruh terhadap gangguan eksternal yang tidak dapat dikontrol oleh siperencana. Jika ketidakpastian tidak diperhitungkan dalam penyelesaian model, maka biaya yang hilang tidak dapat diperhitungkan bila model tersebut digunakan. Bagaimanapun juga, penyelesaian yang diperoleh dari suatu program optimasi mungkin dioptimalkan untuk nilai tertentu dari parameter problema (Birge, 1997). Tetapi untuk nilai yang sesungguhnya atau nilai akhir dari parameterparameter ini dapat diambil suatu keputusan yang mungkin jauh dari optimal 1 Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
2 atau bahkan tidak layak dengan beberapa kendala dari problema. Problema-problema yang disebabkan ketidakpastian didalam data disajikan dengan stokastik, yakni stokastik programming atau optimasi pada kondisi ketidakpastian, yang akan menggambarkan perluasan secara alamiah dari program matematika untuk tetap mempertahankan ketidakpastian didalam problema data, dan perhitungan dilakukan secara eksplisit untuk tetap berada dalam tahapan pemodelan. Didalam model optimasi stokastik, parameter tertentu adalah variabel stokastik yang mempunyai beberapa distribusi peluang yang kontiniu atau diskrit (Birge, 1997). Program stokastik linier adalah komposisi dari program linier acak dan model stokastik yang mana bentuk modelnya dinyatakan sebagai berikut;
inf {cx : A(ω) ≥ b(ω)}
x∈Rn +
(1.1)
yang memiliki karakteristik dengan parameter acak A dan b yang dipetakan dari ruang kejadian Ω terhadap Rs×n × R. Sebagai catatan, kasus dari koefisien biaya acak c(ω) tertutupi dengan formula diatas untuk setiap ω ∈ Ω dengan reformulasi yang ekuivalen inf {z : z ≥ c(ω)x, A(ω)x ≥ b(ω)}
x∈Rn +
(1.2)
berdasarkan masalah dari persamaan 1 (Markert, 2005). Model stokastik ini bertugas untuk mendefinisikan apa yang diinginkan untuk menyelesaikan masalah persamaan (1,1) . Masalah distribusi untuk distribusi
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
3 peluang adalah nilai optimal dan solusi optimal dari persamaan (1.1) diberikan ukuran peluang IP pada ruang ukuran (Ω, A). Model yang digunakan untuk beberapa moment dari distribusi peluang ini adalah tertutup dengan masalah distribusi (Mrkert, 2005). Selanjutnya, terdapat masalah wait and see yaitu; Z
inf {cx : A(ω)x ≥ b(ω)} IP (dω)
x∈Rn +
(1.3)
Ω
yang berhubungan dengan ekspektasi matematika yang tanggap terhadap distribusi peluang pada nilai optimal. ¯ Pada prakteknya sering menggantikan parameter acak A(ω) dan ¯bb(ω) dengan nilai ekspektasi
A :=
ZR
A(ω)IP (dω) dan ¯b :=
Ω
ZR
b(ω)IP (dω)
Ω
Secara jelas, hasil dari masalah deterministiknya adalah inf
x∈X⊂Rn
{cx : Ax ≥ b}
yang merupakan bagian terbesar dari informasi yang diberikan oleh ukuran probabilitas IP dan akan dimanfaatkan untuk skala yang lebih besar atau situasi kompleks dimana model lain tak dapat diaplikasikan (Markert, 2005). Program stokastik adalah merupakan program matematika, dimana beberapa data yang termuat pada tujuan atau kendala mengandung ketidakpastian yang dicirikan oleh distribusi peluang pada parameter. Dalam persoalan program stokastik adalah membuat sebuah keputusan sekarang dan meminimumkan biaya rata-rata harapan sebagai konsekuensi dari keputusan sebelumnya, paradigma ini
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
4 dikenal sebagai model recourse (Dantzig, 1955). Sehingga dapat ditulis program linier acak dari tipe ini yaitu ; inf
x∈X,y(ω)∈Rn +
{cx + q(ω)y(ω) : T (ω)x + W (ω)y(ω) = h(ω)}
selanjutnya, parameter acak ξ := (q, T, W, h) : Ω → Rm × Rs×n × Rs×m × Rs adalah terdefinisi pada ruang probabilitas (Ω, P, A). Himpunan X ⊂ {x ∈ Rn : Ax = b} mengandung semua kendala deterministik dari x, dan kendala ketaksamaan dapat juga ditambah variabelya dengan memperkenalkan variabel slack yang sesuai. Pada kenyataannya bahwa secara ekslusif sesuai dengan masalah yang berhubungan dengan matrix recourse W dan biaya recourse q yang deterministik, kasus deterministik dari matriks recourse W disebut dengan recourse tetap atau fixed recourse (Dantzig, 1955) Pengukuran resiko berhubungan dengan ketidakpastian investasi telah menjadi topik utama dalam matematika finansial untuk beberapa dekade, dan fokus dari penelitian ini didasarkan pada kelayakan bentuk konseptual dari ukuran resiko yaitu apakah ukuran resiko berdampakterhadap resiko pengambilan keputusan.
1.2 Perumusan Masalah Beberapa tahun terakhir, perhitungan resiko telah menjadi bidang penelitian pada program stokastik. Disini, selain dari kelayakan pendekatan konseptual, konsistensi dari ukuran resiko dengan struktur program matematika juga merupakan hal yang menarik. Selanjutnya, bagaimana penyelidikan tentang jumlah ukuran
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
5 resiko dalam kerangka program stokastik linier dengan recourse integer campuranran terhadap resiko dalam pengambilan keputusan dengan struktur program matematika.
1.3 Tujuan Penelitian Tujuan dari penelitian ini adalah menentukan ukuran resiko pada program stokastik linier dengan recourse integer campuran dan juga menentukan ukuran deviasi yang digunakan dalam ukuran resiko seperti standard deviasi, standard deviasi, semideviasi absolut dan ekspektasi dari target yang ditentukan.
1.4 Kontribusi Penelitian Penelitian ini memberikan ukuran sistematik dari resiko dalam masalah keputusan atas ketidakpastian.
1.5 Metode Penelitian Metode penelitian yang digunakan dalam penelitian ini adalah menggunakan literatur yang bersifat penjelasan dan uraian. Adapun langkah-langkah yang dilakukan adalah :
1. Menjelaskan pengertian program stokastik 2. Menjelaskan program stokastik linier. 3. Menjelaskan program stokastik integer campuran 4. Menjelaskan program stokastik linier dengan recourse integer campuran.
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
6 5. Menjelaskan ukuran deviasi. 6. Menjelaskan pengertian stokastik dominan. 7. Menentukan ukuran resiko konveks dan koheren. 8. Menentukan model mean-resiko dan struktur. 9. Menentukan model nilai ekspektasi. 10. Menentukan ukuran deviasi dari program stokastik linier dengan recourse integer campuran.
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
BAB 2 TINJAUAN PUSTAKA
Penelitian tentang ukuran deviasi pada program stokastik telah banyak dilakukan, hal ini berkaitan dengan berbagai jenis program stokastik yang salah satu diantaranya berkenaan dengan resiko. Pertanyaanya adalah bagaimana resiko akan diukur pada masalah pengambilan keputusan dibawah ketidakpastian (stokastik) sebagaimana telah ditunjukkan oleh Pflug (1999) dan diperkenalkan oleh Steinbanch(2001). Andaikan x variabel keputusan kemudian Y = Y (x) adalah fungsi dari x dan diperlukan sebuah instrumen untuk menentukan yang mana x optimal berdasarkan sebuah struktur pilihan (preference) yang diberikan sebagaimana yang akan diperlihatkan bahwa ada sebuah perlawanan antara resiko sosial (sosial risk) dan resiko individu (individual risk) dan keseimbangan antara keduanya merupakan isu yang mendasar dalam kebijakan publik. Bila R(Y ) adalah generalisasi fungsi resiko konveks konvolusi dan didefinisikan re N 1 P Y i dan resiko individu siko bersama sebagai berikut ; SR (Y ) = R N i=1 N δ P R(Y i) dan karena sifat konveksitas IR (Y ) ≥ SR(Y ), maka IR (Y ) = N i=1 didefinisikan resiko tak wajar sebagai berikut ; UR (Y ) = IR(Y )SR (Y ) ≥ 0. Selanjutnya andaikan R adalah ukuran variansi, yaitu R(Y ) = E(Y ) + δ Var (Y ) meru N 1 P E(Y ) + pakan konveks konvolusi secara umum,dan didapat ; IR(Y ) = N i=1 N δ P Var (Yi ) N i=1 N N 1 P 1 P E(Y ) + δ Var Yi dan resiko tak wajar menjadi SR (Y ) = N i=1 i=1 N P δ UR (Y ) = Var (Y iY j) 2 2N i6=j 7 Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
8 Lebih banyak hal yang dibahas berdasarkan teori rasional dibawah ketidak pastian yang dikembangkan oleh Morgenstern dan von Neumann (1947) dan juga penelitian tentang model mean-risk yang diperlihatkan oleh Markowitz (1959). Yaitu ; inf[EZ(x), RZ(x)] dimana {Z(x) : x ∈ X} adalah sebuah himpunan variabel acak, sedangkan E dan R masing-masing menyatakan nilai ekspektasi dan suatu ukuran resiko. Cabang lain yang juga penting adalah masalah order stokastik dominan (stochastic dominance orders). yang mengedepankan model mean-risk berdasarkan ukuran resiko asimetrik yang diperlihatkan oleh Fishburn (1977). Pembahasan komprehensif dari order stokastik termasuk dominan stokastik akan digunakan pada konsep dominan stokastik untuk mendisain algoritma pada masalah optimisasi stokastik spesial yang telah diperlihatkan oleh Artzner et al. (1999,2003) merupakan konsep aksiomatik dari ukuran resiko koheren dan konveks secara luas. Kristoffersen (2005) telah mengajukan ukuran deviasi pada pengaturan sederhana berdasarkan ekspektasi. Ukuran deviasi termasuk ukuran resiko yang mencerminkan dispersi dari objek acak dan juga model Mean-Risk yang diperluas dari hasil model berdasarkan sifat-sifat struktur seperti kontinuitas ,turunan (differensial) dan konveksitas dari kestabilannya. Algoritma dengan metode L-shaped juga diperkenalkan oleh M¨arkert dan Schultz (2005) dan telah menunjukkan ektensi dari ekspektasi tradisional berdasarkan program integer stokastik ke model mean-risk. Risiko diukur dengan ekspektasi deviasi dari varibel acak yang cocok terhadap rata-rata atau dari target yang ditentukan.
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
9 Sifat-sifat struktural dari hasil program stokastik dan algoritma untuk dekomposisi masalah juga diperlihatkan. Romisch (2000) telah menunjukkan program stokastik dengan ukuran resiko pada fungsi objektifnya serta sifat-sifat kestabilannya berdasarkan struktur dekomposisi.Diperlihatkan juga model dinamik yakni program stokastik multi tahap dengan ukuran resiko multi periode. Pada konteks ini, akan didefinisikan kelas dari ukuran risiko polihedral sedemikian hingga program stokastic dengan ukuran resiko yang diambil dari sifat-sifat layak yang dimiliki. Ukuran resiko polyhedral didefinisikan sebagai nilai optimal dari program stokastik linier yang pasti dimana argumen dari ukuran resiko berdasarkan right hand side dari kendala dinamik. Representasi dual untuk ukuran resiko polihedral diturunkan dan digunakan untuk menghasilkan kriteria konveksitas dan koherensi. Contoh dari ukuran resiko polihedral juga diperlihatkan untuk ekstensi multi periode dari Value-at-Risk kondisional. Eichhorn dan Romisch (2006) telah menunjukkan aspek kestabilan dari program linier stokastik multi tahap dengan ukuran resiko polihedral pada nilai fungsi objektifnya. Pada bagian lain, juga diperlihatkan sensitivitas nilai optimal dengan gangguan didalam proses pemasukan stokastik. Hasil kestabilan yang didapat untuk program stokastik multi tahap dengan ekspektasi dibawa kedalam kasus objektifitas resiko polihedral. Disamping Lr - distance dari hasil ini juga filtrasi jarak dari gangguan untuk proses stokastik. Ditentukan pula kebutuhan untuk ukuran resiko polihedral sedemikian hingga masalah yang berkaitan dengan pemilihan jarak dapat dibatasi oleh kebebasan masalah yang lain.
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
BAB 3 LANDASAN TEORI
3.1 Pengertian Program Stokastik Keputusan adalah suatu kesimpulan dari suatu proses untuk memilih tindakan yang terbaik dari sejumlah alternatif yang ada,sedangkan pengambilan keputusan adalah proses yang mencakup semua pemikiran dan kegiatan yang dilakukan,guna membuktikan dan memperlihatkan pilihan terbaik tersebut. Oleh karena itu diperlukan tehnik analisis yang berkenaan dengan pengambilan keputusan melalui berbagai model. Selanjutnya persoalan keputusan dapat dimodelkan dengan menggunakan program matematika yang bertujuan untuk menentukan nilai maksimum atau minimum. Keputusan yang dihasilkan akan bergantung kepada kendala yang dibatasi oleh adanya keterbatasan sumber dana,tenaga ,waktu dan yang lainnya. Sebagai contoh misalnya disebabkan bertambahnya biaya marginal atau menurunnya perolehan marginal dari sebuah proses produksi atau proses penjualan atau proses investasi dan lain sebagainya. Persoalan program matematika tersebut dapat dinyatakan sebagai berikut;
Min Z = g0 (x) Dengan kendala gi (x) ≤ 0, i = 1, 2, 3, . . . , m x ∈ X ⊂ Rn Dimana diketahui X juga sebagai fungsi 10 Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
11 gi : Rn → R, i = 0, 1, 2, . . . , m
Program stokastik merupakan bagian dari program matematika ,dimana beberapa data yang termuat pada fungsi tujuan (fungsi objektif) atau kendala mengandung ketidakpastian yang dicirikan dengan distribusi peluang pada parameternya. Selanjutnya dalam proses pengambilan keputusan terhadap suatu persoalan secara logis,yang diperlukan adalah membuat sebuah keputusan sekarang dan meminimumkan biaya rata-rata harapan sebagai konsekwensi dari keputusan yang telah diambil,dan ini dikenal sebagai model rekursif (recourse). Progran Linier acak dari tipe ini adalah ; inf
{cx + q(ω)y(ω) : T (ω)x + W (ω)y(ω) = h(ω)}
(3.1)
x∈X,y(ω)∈R+m
Parameter acak ξ := (q, T, W, h) : Ω → Rm × Rs×n × Rs×m × Rs adalah ter definisi pada ruang probabilitas (Ω, IP, A) dan himpunan X ⊂ x ∈ Rn+ : Ax = b , mengandung semua kendala deterministik pada variabel x. Persamaan konstrain (3.1) dapat dipedomani dengan menambah variabelvariabel slack yang tepat,dan model yang ditunjukkan sebagai model dengan dua tahap. Selanjutnya bentuk model Recourse dibentuk dengan menambahkan ukuran fungsi objektif, yang dinyatakan dengan model seperti berikut; ¯ ξ(ω)) inf c(ω)x + Φ(x,
x∈X
(3.2)
dimana ¯ Φ(x, ξ(ω)) =
inf {qy : T (ω)x + W y = h(ω)} y ∈ Rn+
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
(3.3)
12 ¯ ¯ : Rn ×Rs×n ×Rs → R dapat diukur dan Z := cx + Φ(x, ξ(ω)) : x ∈ X asalkan Φ dianggap sebagai rumpun variabel-variabel acak. Sekarang setiap fungsi R : Z → R, berupa nilai ekspektasi,dan merupakan ukuran resiko atau jumlah bobot keduanya (ekspektasi dan resiko) dapat digunakan sebagai ukuran fungsi objektifnya.
3.2 Program Stokastik Linier Berdasarkan paradigma standar program stokastik dua tahap,variabel keputusan dari sebuah problema optimasi oleh ketidakpastian dibagi menjadi dua himpunan, yaitu variabel-variabel tahap pertama telah ditentukan sebelum direalisasi secara nyata dari parameter ketidakpastian dan selanjutnya mendesain atau memperbaiki kebijakan cara kerjanya yang dapat dilakukan dengan memilih sebuah cost yang pasti pada variabel-variabel dari tahap kedua ( recourse). Variabel-variabel tahap kedua telah dianggap sebagai suatu ukuran untuk koreksi atau peninjauan kembali suatu ketidaklayakan yang diperoleh dari sebuah fakta yang direalisasikan dari suatu ketidakpastian. Bagaimanapun juga problema tahap kedua menjadi sebuah cara kerja dalam pengambilan keputusan yang mengikuti sebuah rencana pada tahap pertama dan merealisasikan suatu ketidakpastian. Sudah menjadi satu ketentuan dari sebuah ketidakpastian, bahwa biaya pada tahap kedua adalah sebuah variabel acak yang bertujuan untuk memilih variabel tahap pertama mengenai jumlah dari biaya tahap pertama dan nilai ekspektasi untuk meminimalkan biaya tahap kedua. Konsep dari recourse telah banyak diaplikasikan pada program stokastic linier,program integer dan program nonlinier . Khusus untuk program stokastik
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
13 linier dua tahap mempunyai bentuk standar berikut; Minct x + Eω∈Ω [Q(x, ω)] untuk x ∈ X
(3.4)
Q(x, ω) = min f(ω)t y untuk D(ω)y ≥ h(ω) + T (ω)x, y ∈ Y
(3.5)
dengan
dimana x ⊂ Rn1 dan y ⊂ Rn2 adalah himpunan Polyhedral.disini C ∈ Rn1 ,dan ω sebuah variabel acak dari ruang probabilitas (Ω, E, IP ) dengan Ω ⊆ Rk , f : Ω → Rn2 , h : Ω → Rm2 , D : Ω → Rm2 ×n2 dan T : Ω → Rm2 ×n1 Problema (3.4) dengan variabel x merupakan tahap pertama yang diperlukan untuk ditentukan terlebih dahulu guna merealisasikan parameter ketidakpastian ω ∈ Ω, problema (3,5) dimana y merupakan variabel tahap kedua. Berdasarkan asumsi distribusi diskrit pada parameter ketidakpastian, problema dapat di ekivalensikan rumusnya sebagai satu program linier untuk skala yang luas yang dapat diselesaikan dengan menggunakan teknik stndar program linier,serta sifat konveksitas dari fungsi recourse cukup efetif digunakan dalam strategi penyelesaian berdasarkan dekomposisi,untuk parameter distribusi kontiniu. Sifat-sifat ini telah digunakan untuk pengembangan sampling berdasarkan dekomposisi dan skema aproksimasi sama seperti algoritma dasar gradien. Formulasi dua tahap dengan mudah dapat digunakan untuk problema multi tahap yang dipasangkan dengan model ketidakpastian sebagai sebuah proses filtrasi. Berdasarkan distribusi diskrit, reduksi ini untuk sebuah pohon skenario oleh realisasi parameter dan skema dekomposisi membagi waktu secara bertahap sama seperti membagi ruang skenario yang telah dikembangkan untuk program linier multi tahap.
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
14 3.3 Program Stokastik Integer Campuran Didalam matematika programming ,problema yang sering dihadapi adalah masalah penentuan bilangan yang digunakan apakah bilangan ril atau integer. Program bilangan integer merupakan suatu kasus yang khusus dari program linier dimana semua atau beberapa variabel dibatasi sebagai bilangan integer tak negatif. Kalau semua variabel dibatasi pada bilangan integer,maka problemanya disebut problema program bilangan integer (integer programming),namun apabila beberapa variabel tertentu dibatasi pada bilangan integer, sedangkan yang lainnya tidak,maka problemanya disebut problema program integer campuran(mixed integer programming). Demikian juga halnya apabila problemanya pada program Stokastik maka disebut problema stokastik integer campuran (Stochastic Mixed Integer Programming)atau disingkat dengan SMIP. Didalam problema stokastik integer campuran ini dilakukan bertahap atau rekursif (recourse) dengan minimal dua tahap, dan untuk menyelesaikan atau setidaknya suatu pendekatan dari problema program stokastik dua tahap (recourse) dengan variabel tahap pertama diskrit yakni; X = {x ∈ Z n1 Ax = b, 0 ≤ x ≥ u}
(3.6)
dan dengan variabel-variabel tahap kedua yang kontiniu atau diskrit yaitu; y ∈ Y = y ∈ Rn+2 beberapa yi boleh integer
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
(3.7)
15 Selanjutnya akan di identifikasi parameter acak dari program stokastik integer campuran berikut ; Min
o n t cT x + q T y : T x + W y = Z(ω), x ∈ X, y ∈ Z+m × Rm +
(3.8)
Bersamaan dengan informasi dari kendala yang ada bahwa dalam tahap pertama x harus dipilih terlebih dahulu untuk meninjau Z(ω), dan selanjutnya pada tahap kedua y yang dipilih dan kondisi ini sering menjadi acuan agar pemilihan y ini tidak mendahului pemilihan nilai x. Berikutnya diasumsikan bahwa vektor-vektor dan matrix pada (3.8) memiliki ukuran yang dapat dipenuhi ,dimana W memiliki entri bilangan rasional ,dan x ⊆ Rm adalah sebuah polyhedron tak nol,boleh jadi meliputi integer yang dibutuhkan untuk nilai komponen-komponen dari x.
3.4 Program Stokastik Linier Dengan Recourse Integer Campuran Konsep yang mendasari model recourse adalah dengan asumsi dua tahap dalam pengertian bahwa pada tahap pertama beberapa variabel x yang ditentukan dan saat yang lain variabel y nilainya dapat ditunda untuk satu waktu yaitu bila ketidakpastian telah dinyatakan dan dapat ditulis sebuah program linier acak untuk model ini sebagai berikut ;
inf
x∈X,y(ω)∈Rm +
{c(ω)x + q(ω)y(ω) : T (ω)x + W (ω)y(ω) = h(ω)}
(3.9)
dengan parameter acak ξ := (c, q, T, W, h) : Ω → Rn × Rs×n × Rs×m × Rs didefini sikan pada ruang probabilitas (Ω, IP, A) dan himpunan X ⊂ x ∈ Rn+ : Ax = b memuat semua konstrain (kendala) x yang deterministik.
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
16 Persamaan konstrain dapat digunakan untuk persamaan (3.9) dengan memperkenalkan slack variabel yang sesuai dan model (3.9) yang diarahkanuntuk sebuah model dua tahap, sebagai konstrain yang mencakup parameter acak yang berarti feasibel dan optimasi tidak jelas, oleh karenanya dilengkapi model recourse dengan menambah sebuah fungsi objektif yang standar. Dituliskan kembali model (3.9) sebagai berikut;
inf {C(ω)x + φ(x, ω)}
(3.10)
φ(x, ω) = inf n {q(ω)y : T (ω)x + W (ω)y = h(ω)}
(3.11)
x∈X
dimana ; y∈IR+
Perlu diketahui bahwa,terbukti φ : IRn × Ω dapat diukur dan dianggap Z := {c(ω)x + φ(x, ω) : x ∈ X} sebagai sebuah rumpun variabel acak. Selanjutnya untu setiap fungsi R : Z → R, misalnya nilai ekspektasi , ukuran resiko atau sebuah ukuran dari jumlah bobot keduanya yang dapat disajikan sebagai objektif dasar yakni ; inf R [c(ω)x + φ(x, ω)]
x∈X
(3.12)
dan yang perlu diperhatikan adalah model integer yakni dalam menjumlahkan konstrain yang digunakan pada problem (3.9) dapat dilengkapi syaratsyarat pada variabel x dan y. Berikutnya diberikan suatu bilangan berhingga dari skenario ξj , j = 1, 2, 3, . . . , s dengan probabilitas πj , maka problem (3.12)
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
17 dapat dirubah menjadi min
( t
cj x +
m ×Z m x∈X,yj ∈Z+ +
X
sπj qj yj : Tj x + Wj yj = hj , ∀j
)
(3.13)
j=1
Fungsi recourse yang diharapkan QE dimana ; ( ) ∞ P min t πj qj yj : Tj x + Wj yj = hj , ∀j , untuk semua x ∈ QE(x) = Cj x + m XRm yj ∈Z+ +
j=1
n
R , dan program (3.5.5) adalah program linier integer campuran deterministik yang berskala besar dengan sebuah batasan struktur yang kuat. Selanjutnya berdasarkan variabel tahap pertama , sebuah formulasi yang ekivalen dengan (3.13) dapat dinyatakan sebagai berikut; ( s ) X πj (cj xj + qj yj ) : x1 = x2 = . . . = xs , (xj , yj ) ∈ Mj , ∀j min xj yj
(3.14)
j=1
dimana ; Mj = {(xj , yj ) : Tj xj + Wj yj = hj , xj ∈ X, yj ∈ Y } , j = 1, 2, . . . , s dan berdasarkan matriks konstrain (3.14) dapat di identifikasi himpunan S yang merupakan subproblema bertahap tunggal yang dikaitkan dengan persamaan konstrain pada penulisan variabel tahap pertama dan ditulis s X
Hj xj = 0, dimana H = (H1 , H2 , . . . , Hj )
j=1
3.5 Ukuran Deviasi Pada bagian ini akan diperkenalkan sebuah ukuran dasar yang dipergunakan untuk ukuran resiko dari suatu kegiatan atau proses pengambilan keputusan dari variabel acak berdasarkan ketidakpastian,yang mana ukuran dimaksud adalah ukuran deviasi (deviation measure). Berikutnya dipilih kerangka minimalisasi dalam memilih nilai-nilai variabel acak yang lebih kecil (law cost) dan ini tercermin dalam definisi ukuran resiko yang diberikan,dimana X adalah sebuah variabel
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
18 acak yang didefinisikan pada ruang probabilitas (Ω, A, IP ) dan η0 adalah sebuah nilai yang ditargetkan didalam R. Ada tiga jenis deviasi yang dipergunakan yaitu; - Deviasi sentral orde p yaitu : p1 Z Dp (X) = |X − EX|p IP (dω) Ω
- Semideviasi orde p yaitu :
Dp+
=
R
1
p
p
max{X − EX, 0} IP (dω) Ω 1 p R - Perkiraan kelebihan orde p yaitu : Epη (X) = max{X − η0}p IP (dω) Ω
terutama sekali yang paling penting adalah masalah dimana nilai-nilai p yang dipilih adalah 1 atau 2. Untuk p = 2 sentral deviasi berubah menjadi deviasi standar, dan untuk perkembangan selanjutnya bahwa kwadrat dari deviasi standar adalah variansi dan sering digunakan untuk mengukur resiko, selanjutnya semideviasi order 1 disebut semideviasi absolut dan semideviasi order 2 dianggap sebagai semideviasi standar. Kemudian semideviasi selalu menjadi pilihan pertama bila fokus penelitiannya adalah pencegahan kelebihan mean dan kekurangan dibawahnya. Dalam konteks maksimisasi, ini disebut sebagai perkiraan kekurangan target dan pendapatan dibawah-target, dan perkiraan kelebihan target bisa dipandang sebagai pengganti untuk semideviasi dalam sebuah situasi, bila masalahnya melibatkan kelebihan mean dan kekurangan dibawahnya sulit diselesaikan.
3.6 Dominasi stokastik Pertanyaan tentang pemilihan orde (parsial) yang tepat atas rumpun variabelvariabel acak yang timbul bila masalah keputusan mengharuskan perbandingan variabel-variabel acak. Pada bagian ini ditinjau konsep orde dominasi stokastik
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
19 yang merupakan orde parsial yang menarik perhatian . Menetapkan kerangka minimisasi, yaitu lebih memilih nilai yang kecil ,dan untuk menghindari notasi yang membingungkan ketika beralih dari minimisasi ke maksimisasi dan sebaliknya, perlu disesuaikan konsep penentuan order stokastik dan teori keputusan dengan ukuran minimisasi. Dalam Morgenstern dan von Neumann (1947), dibahas pertanyaan apakah utilitas kejadian bisa diukur. Pertanyaan yang agak konseptual ini dijawab dan diikuti dengan perumusan aksioma pengambilan keputusan rasional yang diterima secara umum. Aksioma ini, antara lain, mengisyaratkan bahwa setiap pengambil keputusan rasional mempunyai fungsi utilitas f yang berfungsi untuk membandingkan variabel-variabel acak. Khususnya, perkiraan prinsip utilitas menyatakan bahwa pengambil keputusan lebih menginginkan variabel acak X ketimbang variabel acak Y jika berlaku Ef(X) ≤ Ef (Y ), di mana Ef (X) =
Z
Ωf (X)P(dω)
Di dalam praktek, tidak mungkin menentukan dengan tepat fungsi utilitas dari masing- masing pengambil keputusan. Akan tetapi, fungsi mungkin diketahui termasuk dalam satu rumpun fungsi-fungsi. Sebagai contoh misalnya, di perkirakan bahwa fungsi utilitas dari pengambil keputusan yang rasional lebih menginginkan nilai kecil yang termasuk ke dalam kelas fungsi-fungsi nondecreasing. Fakta, bahwa banyak masalah keputusan mengharuskan penyelesaian yang sah untuk sejumlah pengambil keputusan dengan fungsi utilitas yang berbedabeda, memberikan alasan lain untuk mempertimbangkan suatu rumpun fungsifungsi dan bukan fungsi tunggal.
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
20 Definisi 3.6.1 (orde stokastik pertama, X ≤FSD Y ) Variabel acak X lebih kecil dari atau sama dengan variabel acak Y terhadap orde stokastik pertama jika dan hanya jika Ef(X) ≤ Ef(Y ) untuk semua fungsi tak turun f untuk mana kedua ekspektasi ada. di tulis X ≤FSD Y . Karena f tidak turun jika dan hanya jika −f tidak naik, diperoleh ekuivalensi
X ≤FSD Y ⇔ Ef(X) ≥ Ef (Y ) untuk semua fungsi tak naik f
(3.15)
asalkan kedua ekspektasi ada. Fungsi distribusi kumulatif FX dari variabel acak X didefinisikan dengan FX (t) := P(X ≤ t) untuk semua t ∈ R. Dapat dinyatakan hubungan orde stokastik pertama dalam bentuk fungsi distribusi kumulatif FX dan FY masing-masing dari variabel acak X dan Y .
Lemma 3.6.3 (Fishburn (1964)) Berlaku bahwa X ≤FSD Y ⇔ FX (t) ≥ FY (t)∀t ∈ R Perlu dicatat bahwa FX (t) ≥ FY (t) juga mengimplikasikan P(X > t) ≤ P(Y > t). Dengan demikian, preferensi nilai kecil tercermin dalam fakta bahwa probabilitas dari X lebih besar dari target riil sebarang t lebih kecil dari probabilitas Y lebih besar dari target. Dikatakan X mendominasi Y sebagai orde stokastik pertama jika dan hanya jika X ≤FSD Y dan Y 6≤FSD X, yaitu suatu fungsi tak naik g sedemikian sehingga Eg(X) > Eg(Y ). Selain itu, jika pengambil keputusan menghindar dari resiko, secara umum diterima mengasumsikan bahwa ia lebih menyukai variabel acak konstan EX ke-
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
21 timbang variabel acak aktual X tidak soal bagaimana distribusi X. Dengan kata lain hasil yang pasti dievaluasi lebih tinggi daripada setiap alternatip beresiko. Dalam hal fungsi utilitas, berlakulah f (EX) ≤ Ef (X). Menurut ketaksamaan Jensen inilah yang terjadi jika dan hanya jika f konveks dan menghasilkan hubungan orde stokastik kedua.
Definisi 3.6.4 (orde stokastik kedua, X ≤SSD Y ) Variabel acak X lebih kecil dari atau sama dengan variabel acak Y terhadap. orde stokastik kedua jika dan hanya jika Ef(X) ≤ Ef(Y ) untuk semua fungsi konveks tak-turun f untuk mana kedua ekspektasi ada. Kita tulis X ≤SSD Y . Karena f adalah konveks tak turun jika dan hanya jika −f adalah konkaf tak naik, definisi yang ekuivalen diberikan oleh
X ≤SSD Y ⇔ Ef (X) ≤ Ef (Y )
(3.16)
untuk semua fungsi konkaf tak naik f , asalkan kedua ekspektasi ada. Analog dengan orde stokastik pertama, ada syarat ekuivalen untuk X ≤SSD Y yang melibatkan fungsi yang terkait dengan fungsi distribusi kumulatif dari X dan Y .
Lemma 3.6.6 (Hadar dan Russell (1969)) Berlaku bahwa X ≤SSD Y ⇔ E max{X − t, 0} ≤ E max{Y − t, 0}∀t ∈ R Di katakan X mendominasi Y dengan orde stokastik kedua jika dan hanya jika X ≤SSD Y dan Y 6≤SSD X. Hubungan dengan fungsi distribusi kumulatif yang disebutkan di atas diberikan R Oleh E max{X − t, 0) = P(X > t)P(dω), Ω
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
22 Dan ini memotivasi definisi dari dominasi stokastik orde-p untuk p ∈ N. R Secara rekursif, di alokasikan FX1 (t) := P(X > t) dan FXp+1(t) := FXp (t)P(dω) Ω
untuk semua t ∈ R.
Definisi 3.6.7 (orde stokastik ke-p, X ≤p Y ) Variabel acak X lebih kecil dari atau sama dengan variabel acak Y terhadap orde stokastik ke-p jika dan hanya jika FXp (t) ≥ Fγp(t) untuk semua t ∈ R. ditulis X ≤p Y . Definisi rekursif FXp dan pernyataan monotonisitas diperoleh hasil sebagai berikut;
Lemma 3.6.7 Misalkan p ∈ N. Berlaku bahwa X ≤p Y ⇔ X ≤p+1 Y Walaupun Definisi 3.6.1 dan 3.6.4 dari orde stokastik lebih intuitif terhadap preferensi yang dinyatakannya, syarat-syarat ekuivalen dalam bentuk f ungsi distribusi kumulatif (gabungan) memberikan kriteria optimisasi yang dapat diakses. Akan tetapi, jika variabel acak berdistribusi kontinu, kedua orde stokastik menghasilkan masalah optimisasi multi-kriteria dengan rangkaian kesatuan kriteria yang bersesuaian dengan perbandingan fungsi tak naik dan fungsi konkaf tak-naik. Untuk distribusi diskrit, fungsi f (t) := P(X > t) dan g(t) := E max{X − t, 0} masing-masing adalah konstan sepotong-sepotong dan linier sepotong-sepotong. Optimisasi terhadap orde stokastik pertama dan kedua tereduksi menjadi programming matematik multi-kriteria dengan sejumlah hingga kriteria tergantung pada jumlah atom probabilitas variabel acak. Mari diklarifikasikan topik untuk dominasi stokastik orde pertama.
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
23 Asumsikan untuk kelas X dari variabel-variabel acak berdistribusi diskrit dan andaikan bahwa semua variabel acak X dalam X mempunyai S atom pro1 babilitas yang dicapai dengan probabilitas . Untuk X dalam X kita notasikan S atom-atom probabilitas sebagai X1 , . . . , XS dan daftar orde (yang dimulai dengan yang paling kecil) dari atom-atom probabilitas ini dengan X(1) , . . . , X(S) . Maka, variabel acak yang optimal terhadap dominasi stokastik orde pertama bisa ditentukan dengan masalah optimisasi multikriteria
min X(1), . . . , X(S) X∈ℵ
(3.17)
akan dibuktikan sebuah Lemma yang membuktikan ekuvalensi ini.
Lemma 3.6.10 Misalkan X dan Y adalah dua variabel acak berdistribusi diskrit 1 dengan S atom probabilitas yang dicapai dengan probabilitas . Misalkan statisS tik orde ini diberikan oleh X(1) , . . . , X(S) dan Y(1) , . . . , Y(S) , yaitu berlaku X(1) ≤ . . . ≤ X(S) dan Y(1) ≤ . . . ≤ Y(S) . Maka diperoleh X(j) ≤ Y(j) , j = 1, . . . , S ⇔ X ≤FSD Y . Bukti : Misalkan FX (t) dan Fγ (t) adalah fungsi distribusi kumulatif masingmasing dari X dan Y .Asumsikan X(j) ≤ Y(j) untuk j = 1, . . . , S. Misalkan t ∈ R. tanpa kehilangan keumuman,di asumsikan bahwa X(j) ≤ t untuk semua j ≤ j ∗ dan X(j) > t untuk semua j > j ∗ , j ∗ ∈ {1, . . . , S}, diperoleh P(X ≤ t) = FX (t) =
j∗ ≥ Fγ (t) = P(Y ≤ t) S
dengan demikian X mendominasi Y dalam orde stokastik pertama.
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
24 Sebaliknya, asumsikan X ≤FSD Y . Asumsikan ada j ∗ ∈ {1, . . . , S} sedemikian sehingga X(j ∗ ) > Y(j ∗ ). Misalkan t := Y(j ∗ ) . diperoleh P(X ≤ t) = FX (t) ≤
j∗ j∗ − 1 < = Fγ (t) = P(Y ≤ t) S S
Ini kontradiksi dengan X ≤FSD Y . Karena itu, berlakulah X(j) ≤ Y(j) untuk j = 1, . . . , S. Algoritma yang efisien untuk program bilangan-bulat multikriteria dengan sejumlah besar kriteria tidak ada tersedia sekarang ini. Model mean-resiko lebih memungkinkan dari segi perhitungan dan algoritma. Variabel-variabel acak dibandingkan atas dua kriteria skalar - perkiraan nilai dan ukuran resiko. Dan selanjutnya diselidiki daftar ukuran-ukuran resiko terhadap,konsistensinya dengan dominasi stokastik orde pertama dan kedua.
Definisi 3.6.11 (konsistensi ukuran resiko dengan dominasi stokastik) Misalkan α > 0. Ukuran resiko R adalah konsisten-α dengan dominasi stokastik orde p jika dan hanya jika X ≤p Y ⇔ EX + αR(X) ≤ EY + αR(Y ) Definisi ini sifatnya intuitif, dan tidak memilih variabal acak yang didominasi dengan pendekatan jumlah berbobot terhadap masalah mean-resiko. Konsistensiα dari ukuran resiko dengan suatu orde dominasi stokastik adalah konsistensi-α0 dengan orde yang sama untuk semua α0 dengan 0 < α0 ≤ α. Ukuran resiko R, yang merupakan konsisten-α dengan dominasi stokastik berorde p untuk semua α ∈ R, disebut konsisten dengan dominasi stokastik berorde p. Aplikasi. Dalam ulasan selanjutnya pada bagian ini, dibahas ukuran resiko yang diperkenalkan pada sebelumnya terhadap dominasi stokastik. Perlu dicatat bahwa
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
25 perkiraan nilai variabel acak konsisten dengan dominasi stokastik orde pertama dan juga kedua.
Lemma 3.6.12 Berlaku bahwa X ≤FSD(SSD)⇔ EX ≤ EY .
Bukti . Fungsi f (x) = −x adalah tidak naik dan konkaf. Dengan memasukkan fungsi ini ke dalam definisi 3.6.1 dan 3.6.4 dihasilkan EX ≤ EY pada kedua kasus. Deviasi pusat berorde p tidak konsisten dengan dominasi stokastik orde pertama maupun kedua. Diberikan contoh berikut;.
Contoh 1. Misalkan X dan Y adalah dua variabel acak yang didefinisikan atas ruang probabilitas (Ω, A, P) dan misalkan k > 0. Asumsikan q ∈ (0, 1], P(X = −k) = 1 − P(X = 0) = q, dan Y ≡ 0. Maka, berlaku P(X > t) = P(Y > t)t ∈ R\[−k, 0) Dan P(X > t) = a ≤ 1 = P(Y > t)t ∈ [−k, 0) Akibatnya, X mendominasi Y dengan orde stokastik pertama dan karena itu juga dengan orde stokastik kedua. Sekarang, perhatikan model mean-resiko untuk p ∈ N dan α > 0 dihitung EX = −qk dan 1
1
mathcalDp(X) = (E|X − EX|) p = (q| − k + qk|p + (1 − q)|qk|p) p 1
= (q(1 − q)p + q p(1 − q)) p k Dan juga EY = Dp (Y ) = 0. Di tunjukkan bahwa terdapat α > 0 sedemikian sehingga EX +αDp (X) > EY +αDp (Y ) atau ekuivalen dengan f(q) := (q −p+1 (1−
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
26 1
q)p + (1 − q)) p >
1 . α
Jika p > 1 maka f (q) mendekati ∞ apabila q mendekati 0
dan f(q) mendekati 0 apabila q mendekati 1. Dengan demikian, tidak konsisten dengan orde stokastik pertama dan kedua.Untuk p = 1 kita peroleh inkonsistensi bila ketaksamaan (1 − q) > 1/2α berlaku. Ini menghasilkan contoh-kontra untuk konsistensi ukuran resiko dengan orde stokastik pertama dan kedua untuk devaiasi pusat berorde 1 jika α > 12 . Deviasi pusat berorde p adalah konsisten-1 dengan dominasi stokastik berorde p +1 jika distribusi variabel acak yang dikaji simetris terhadap mean. Dalam lemma berikut ditutup kesenjangan yang diperoleh dalam contoh di atas untuk deviasi pusat berorde 1.
Lemma 3.6.13 D1 adalah 12 -konsisten dengan stokastik dominan order pertama dan kedua.
Bukti : Perumusan ulang deviasi pusat berorde 1
D1 (X) = E|X − EX| = E(max{X − EX, 0} + max{EX − X, 0}) = E max{X − EX, 0} + E max{EX − X, 0} = E max{X, EX} − EX + E(max{EX, X} − X) = 2E max{X, EX} − 2EX
Dengan demikian, berlakulah R(X) := EX + αD1 (X) = (1 − 2α)EX + 2αE max{X, EX} Perkiraan nilai konsisten dengan dominasi stokastik orde pertama dan kedua, bandingkan Lemma 3.6.12 untuk menunjukkan konsistensi suku kedua. Asum-
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
27 sikan X mendominasi Y dalam orde stokastik pertama (kedua). Ini mengimplikasikan EX ≤ EY dan karenanya f (x) := E max{x, EX} adalah tidak turun dan konveks, diperoleh dengan X ≤FSD(SSD) Y hubungan E max{X, EY } ≤ E max{Y, EY }. Dengan demikian, ukuran resiko R0(X) := E max{X, EX} konsisten dengan dominasi stokastik orde pertama dan juga orde kedua. Karena itu, juga berlaku R(X) ≤ R(Y ) bila X mendominasi Y dengan orde stokastik pertama atau kedua dan bila 1 − α ≥ 0, yaitu bila α ≤
1 . 2
Untuk ukuran resiko yang
tersisa disebutkan dua hasil dalam bentuk lemma berikut ;
Lemma 3.6.14 (Fishburn (1977), Teorema 3) Untuk semua p ∈ N, perkiraan kelebihan berorde p konsisten dengan dominasi stokastik orde pertama dan kedua.. Pernyataan ini sama umumnya dengan pernyataan yang dibutuhkan dalam konteks kita. Perhatikan Lemma 3.6.6 untuk melihat hubungan erat dari perkiraan kelebihan berorde 1 dan dominasi stokastik berorde kedua. Semideviasi berorde p adalah konsisten-1 tetapi tidak konsisten-α dengan dominasi stokastik berorde 1, . . . , p + 1 untuk α > 1. Ini bisa diketahui dengan menggunakan Contoh 1
Contoh 2. Misalkan p ∈ N. Dibiarkan spesifikasi Contoh 1 tidak berubah dan √ dihitung Dp+ (X) = qk p 1 − q. Maka ketaksamaan EX +αDp (X) > EY +αDp (Y ) √ dipenuhi jika p 1 − q lebih besar dari 1/α. Karena X mendominasi Y dengan orde stokastik pertama, Dp+ tidak menjadikan α konsisten dengan dominasi stokastik berorde p untuk α > 1 dan p ∈ N.
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
28 Sebagian hasil dalam bagian ini dirangkum dalam Tabel 3.6. Ukuran resiko konsisten dengan dominasi stokastik berorde pertama dan kedua untuk nilai yang ditampilkan α dan p. di berikan contoh kontra untuk bobot dan orde lainnya. Ukuran Risiko Bobot Orde 1 0<α≤ 2 p=1 Dp Dp+ 0<α≤1 p∈N η α ∈ R+ p∈N Ep Tabel 3.6. Konsistensi Konveks dan Ukuran Resiko Koheren
3.7 Ukuran Resiko Konveks dan Ukuran Resiko Koheren Dalam bagian ini dijelaskan pengertian resiko dengan beberapa sifat aksioma sebagaimana yang telah didefinisikan oleh Artzner yang didasarkan oleh adanya kebutuhan dalam pasar uang sebagai berikut :
Definisi 1: Andaikan X dan Y terletak pada suatu rumpun variabel acak pada ruang probabilitas (Ω, A, IP ), disebut suatu ukuran resiko koheren R bila dipenuhi empat aksioma berikut ; - Translasi invarian : R(X + C) = R(X) + C, ∀C ∈ R - Homogen positif : R(λX) = λR(X), ∀λ ∈ R - Sub aditive : R(X + Y ) ≤ R(X) + R(Y ) - Monoton : X ≤ Ya.s ⇒ R(X) ≤ R(Y )
Definisi 2 : Andaikan X dan Y terletak pada suatu rumpun variabel acak pada ruang probabilitas (Ω, A, IP ), disebut suatu ukuran resiko konveks R bila dipenuhi aksioma berikut;
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
29 - Translasi invarian : R(XC ) = R(X) + C, ∀C ∈ R - Konveksitas : R(λX + (1 − λ)Y ≤ λR(X) + (1 − λ)R(Y ), ∀λ ∈ [0, 1] - Monoton : X ≤ Ya.s ⇒ R(X) ≤ R(Y )
Oleh karena memenuhi aksioma konveksitas dari hegemonitas positif dan subaditif ,ukuran resiko koheren juga merupakan ukuran resiko konveks. Sekali lagi sentraldeviasi order 1 digunakan untuk menentukan sebuah aturan tertentu ,dan objek yang dihitung, yakni ; R(X) = EX + αD1 (X) = (1 − 2α)EX + 2αE max{X, EX} yang memenuhi aksioma monotonitas untuk α ∈ 0, 12 dan bentuk akhir E max {X, EX}, aksioma berikutnya homogenitas positif dan sub aditif dari nilai maksimum,oleh karenanya R adalah sebuah ukuran resiko konveks dan koheren untuk α ∈ 0, 12 . Akibat ekspektasi dari sebuah target η0 order p adalah monoton,oleh sebab ia memenuhi X ≤ Ya.s ⇒ X ≤FSD Y ⇒ E max{X − η0 , 0}p ≤ E max{Y − η0 , 0}p Target yang ditetapkan η, yang butuh penyesusaian ketika mengganti satu variabel acak dengan variabel acak yang lain dan ini hanya untuk jumlah sebuah konsep yang sama terhadap ukuran resiko koheren bila dianggap ukuran resiko sebagai fungsi η. Andaikan C, η ∈ R, λ ∈ R+ dan ρ ∈ [0, 1] di definisikan;
- Translasi invarian terhadap target yang yang ditentukan Rη (X + C) = Rη−c (X) - Homogen positif terhadap target yang ditentukan Rη (λX) = λRη (X)
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
30 - Sub aditif terhadap target yang ditentukan : Rη (X +Y ) ≤ Rpη X +R(1−p)η Y , kemudian sebuah ukuran resiko adalah koheren terhadap target yang ditetapkan apabila ia memenuhi tiga aksioma diatas bersama dengan aksioma monotonik ini, dalam pengertian perkiraan kelebihan dari sebuah target η, koheren terhadap target tertentu dalam pemjumlahan perkiraan kelebihan oleh sebuah target yang memenuhi aksioma konveks,dan dapat dibuktikan dengan pertidaksamaan konveksitas.
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
BAB 4 PEMODELAN MEAN-RESIKO, STRUKTUR DAN ALGORITMA PEMBAHASAN
4.1 Model Mean Resiko Ukuran Deviasi selalu berkaitan dengan mean oleh karena itu diperlukan model dari Mean-Resiko ( Mean-Risk Model). Perhatikan problema optimasi berikut ;
inf [EZ(x), RZ(x)]
x∈X
(4.1)
dimana {Z(x) : x ∈ X} adalah sebuah rumpun variabel acak,sebagaimana E dan R yang masing-masing menyatakan nilai ekspektasi dan ukuran resiko, dan penyelesaian yang efisien untuk problema (4.1) diperoleh dengan menggunakan definisi berikut;
Definisi 4.1: Sebuah penyelesaian x ∈ X disebut penyelesaian efisien apabila tidak ada satu titik lain y ∈ X,untuk satu atau lebih pasangan yang memenuhi pertidaksamaan berikut:
i. EZ(y) < EZ(x) dan RZ(y) ≤ RZ(x) ii. EZ() ≤ EZ(x) dan RZ(y) < RZ(x)
Titik-titik (EZ(x), RZ(x)) dalam ruang bayangan fungsi dipasangkan dengan penyelesaian efisien x ∈ X disebut tak dominan,dan penyelesaian efisien 31 Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
32 adalah tidak kosong apabila untuk himpunan kejadian x 6= φ adalah padat, sedangkan fungsi x → EZ(x) dan fungsi x → RZ(x) merupakan semi kontiniu yang diturunkan pada x. Selanjutnya bidang optimasi multikriteria yang ditawarkan untuk mendapatkan solusi efisien yang dijadikan sebagai referensi,diantaranya jumlah pendekatan dalam pembobotan dari ; inf EZ(x) + αRZ(x), α ∈ R
x∈X
(4.2)
Untuk α > 0, problema (4.2) dapat menghasilkan sebuah penyelesaian yang efisien, dan bila himpunan X konveks dan dua fungsi x → EZ(x) dan fungsi x → RZ(x) adalah konveks kemudian jumlah bobot pendekatan yang menghasilkan potensi untuk menghitung semua solusi yang efisien, seperti parameter α yang telah berubah. Bagaimanapun juga dalam masalah yang lebih umum bila fungsi-fungsi x → EZ(x) dan fungsi x → RZ(x) tidak konveks atau kejadian yang diskontiniu, himpunan penyelesaian yang tak dominan dapat menjadi tak konveks dan tak koneks. Pertanyaannya jelas yaitu bagaimana akan merobah satu parameter α dalam sebuah barisan dari problema pada (4.2). Diberikan dua penyelesaian tak dominan {EZ(x1 ), RZ(x1)} dan {EZ(x2), RZ(x2 )} dengan EZ(x1) < EZ(x2) dan RZ(x1 ) > RZ(x2) maka problema (4.2) dengan ; α=
EZ(x2) − EZ(x1) RZ(x1) − RZ(x2 )
menghasilkan sebuah penyelesaian yang tak mempengaruhi (EZ(¯ x), RZ(¯ x)) dex ≤ EZ(x2) dan RZ(x2 ) ≤ RZ(¯ x) ≤ RZ(x1 ). ngan EZ(x1) ≤ EZ(¯
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
33 4.2 Struktur Pertama, dikaji syarat-syarat yang mana fungsi resiko terdefinisi dengan jelas,karena itu, didefinisikan himpunan fungsi terintegralkan-p sebagai berikut; Z p 1 p L := g : R → R : |g(ξ)| µ(dξ) < ∞ Rt
untuk ukuran probabilitas tetap µ.
Proposisi 4.2.1. Misalkan x0 ∈ Rn dan η0 ∈ mathbbR. Asumsikan Z(x0, ·) adalah fungsi terukur-µ. Maka
(i) QE (x0) adalah bernilai riil jika Z(x0, ·) berada di dalam L1, dan (ii) QDp (x0 ), QDp+ (x0 ) dan QEpη (x0 ) adalah bernilai riil jika Z(x0 , ·) berada di dalam Lp.
Bukti Komposisi fungsi-fungsi terukur jika semua komponennya terukur. Dengan demikian, keterukuran-µ dari integrand |Z(x0 , ·) − QE (x0)|p , max {Z(x0 , ·) − QE (x0), 0}p dan max {Z(x0 , ·) − η0 , 0}p adalah karena keterukuran - µ dari Z(x0, ·) dan x → max {f (ξ), g(ξ)} dengan fungsi terukur f dan g. (i) Keberhinggaan ekspektasi fungsi nilai adalah karena asumsi Z(x0 , ·) ∈ L Berlakulah |QE (x0)| ≤
R
|Z(x0 , ξ)| µ(dξ) < ∞.
Rt
(iii) Untuk mengetahui keberhinggaan deviasi sentral digunakan taksiran |Z(x0 , ξ) −QE (x0)|p ≤ 2p |Z(x0 , ξ)|p + 2p |QE (x0)|p untuk semua ξ ∈ R1 dan ketaksamaan Minkowski, diperoleh
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
34 QDp (x0) ≤
R
1
p
p
|Z(x0, ξ) − QE (x0 )| µ(dξ) Rt 1 1 p p R R p p ≤2 |Z(x0, ξ)| µ(dξ) + |2 |QE (x0 )| µ(dξ) t Rt R 1 p R =2 |Z(x0, ξ)|p µ(dξ) + 2 |QE (x0)| Rt
R
Menurut asumsi diperoleh
|Z(x0, ξ)|p µ(dξ) < ∞ dan pernyataan (i) meng-
Rt
hasilkan |QE (x0 )| < ∞. Ini membuktuikan |QDp (x0 )| < ∞. Bisa ditaksir semideviasi berorde p sebagai berikut |QDp+ (x0)| =
R
Rt
=
≤
M R
R
p
p1
max {Z(x0, ξ) − QE (x0), 0} µ(dξ) p1 p |Z(x0 , ξ) − QE (x0 )| µ(dξ) 1p p |Z(x0 , ξ) − QE (x) | µ(dξ)
Rt
di mana M := {ξ ∈ R1 : Z(x, ξ) ≥ QE (x0)} dan digunakan monotonisi√ tas fungsi x → p x. Dalam penaksiran QDp (x0) telah ditunjukkan bah1 p R p |Z(x0, ξ) − QE (x0)| µ(dξ) adalah berhingga. Ini menghasilkan wa Rt
QDp+ (x0 ) ∈ R. Terakhir, ditunjukkan keberhinggaan ekspektasi kelebihan target η0 berorde p dengan menggunakan taksiran |Z(x, ξ) − η0 |p ≤ 2p |Z(x, ξ)|p + 2p |η0|p dan ketaksamaan Minkowski QEpη (x0 ) ≤
R
p
p1
p
1p
|Z(x, ξ) − η0 | µ(dξ)
M
≤
R
|Z(x, ξ) − η0 | µ(dξ)
Rt
≤2
R
1
|Z(x, ξ)|p µ(dξ)) p + 2|η0 |
Rt
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
35 di mana M := {ξ ∈ R1 : Z(x, ξ) ≥ η0 }. Dengan demikian, ekspektasi kelebihan berorde p juga berhingga dengan asumsi yang diajukan dan bukti lengkap.
Menurut teorema Weierstrass, fungsi semikontinu bawah mencapai minimumnya pada setiap himpunan kompak takkosong. Jadi, semikontinuitas bawah merupakan sifat penting untuk masalah minimisasi. Timbul pertanyaan apakah semikontinuitas bawah dari variabel acak Z(·, ξ) tidak diubah oleh sebuah fungsi resiko dan apakah operasi-operasi dasar yang terlibat dalam definisi fungsi resiko melanggengkan sifat ini. Perhatikan fungsi f : R → R yang merupakan semi kontiniu bawah (low semicontinius), tetapi tidak kontinu di t0, yaitu lim inf t→t0 f (t) > f (t0 ). Karena lim inf t→t0 −f(t) < −f(t0 ), fungsi −f adalah semikontinu atas (uper semicontinous) tetapi bukan semikontinius bawah (lower semicontinous) di t. Sama halnya, perhatikan fungsi f : R → R yang merupakan semikontinius bawah. tetapi tidak kontinu pada himpunan T − := {t ∈ Rl : f (t) < 0} 6 =∅, yaitu terdapat t ∈ T − sedemikian sehingga lim inf t→t0 f (t) > f(t0). Maka kuadrat g := f 2 dari f bukan semikontinius bawah di t jika | lim inf t→t0 f (t)| < |f(t0 )|. Pengamatan pertama, pada umumnya, menunjukkan ukuran resiko yang melibatkan pengurangan sebuah fungsi semikontiniu bawah bukan semikontiniu bawah. Inilah yang terjadi untuk deviasi sentral dan semideviasi berorde p ∈ N Kedua fungsi resiko melibatkan pengurangan dari mean QE (x0) yang akan ditunjukkan, merupakan semikontiniu bawah. Akan tetapi, untuk semideviasi berorde 1 ini cacat dan dapat diperbaiki
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
36 dalam model mean-resiko bila α berada dalam (0,1]. Sebelum di buktikan semikontinuitas bawah dari fungsi resiko di nyatakan dua lemma.
Lemma 4.2.2 Misalkan f, g : Rn → R dan x0 ∈ Rn . Asumsikan f dan g adalah l.s.c. di x0. Maka fungsi x → max {f (x), g(x)} adalah semikontiniu bawah( l.s.c.) di x0.
Bukti Misalkan {xk } adalah barisan dalam Rn yang konvergen ke x0. Untuk semua k ∈ N berlaku max{f(xk ), g(xk )} ≥ f (xk ) dan max{f(xk ), g(xk )} ≥ g(xk ). Dengan demikian, diperoleh lim inf max {f (xk ), g(xk )} ≥ lim inf f (xk ) k→∞
k→∞
lim inf max {f (xk ), g(xk )} ≥ lim inf g(xk ) k→∞
k→
dan karenanya n o lim inf max {f (xk ), g(xk )} ≥ max lim inf f (xk ), lim inf g(xk ) k→∞
k→∞
k→∞
(4.3)
Fungsi f dan g adalah semikontiniu bawah di x0 yang berarti lim inf f (xk ) ≥ f (x0 ) k→∞
dan lim inf g(xk ) ≥ g(x0 ). Karena itu, ketaksamaan (4.3) menghasilkan k→∞
lim inf max {f(xk ), g(xk )} ≥ max {f(x0), g(x0 )} k→∞
(4.4)
Karena barisan {xk } dipilih secara sebarang, maka ketaksamaan (4.4) bersesuaian dengan semikontinuitas bawah maksimum. Lemma 4.2.5 Misalkan f : Rn → R dan g : R → R. Asumsikan f adalah semikontiniu bawah di x0 dan g adalah semikontiniu di f (x0 ) dan tidak naik,
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
37 maka fungsi h yang didefinisikan sebagai h(x) := g(f (x)) untuk semua x ∈ Rn adalah semikontiniu bawah di x0 . Bukti Misalkan {xk } adalah barisan dalam Rn yang konvergen ke x0. Karena g adalah semikontiniu bawah di f (x0 ) diperoleh lim inf g(f (xk )) ≥ g(lim inf f (xk )). k→∞
k→∞
Semikontinuitas bawah f menghasilkan lim inf f (xk ) ≥ f (x0 ). Karenanya, g tidak k→∞
turun dan diperoleh lim inf g(f (xk )) ≥ g(f (x0 )) k→∞
ini berarti h adalah semikontiniu bawah di x0 . Catatan 4.2.6 Fungsi x → xp dan x →
√ p x tidak turun pada R+ . Bisa di-
aplikasikan Lemma 4.2.5 untuk fungsi ini jika fungsi dalam f nonnegatip dan semikontiniu bawah. Ini berlaku untuk f (x) := max{h(x), 0} dengan fungsi semikontiniu bawah h(x). Untuk suatu fungsi berharga real, f yang terdefinisi pada beberapa interval I ⊆ R konveks minorant dari f adalah fungsi konveks terbesar pada I yang terbatas keatas oleh f . Proposisi 4.2.7 Misalkan x0 ∈ Rn , η0 ∈ R, α ∈ R+ dan r, p ∈ N. Asumsikan bahwa terdapat neighborhood Uδ (x0) dari x0 dengan δ > 0 sedemikian sehingga Z(x, ·) adalah fungsi terukur-µ untuk semua x ∈ Uδ (x0 ) dan bahwa Z(·, ξ) adalah semikontiniubawah di x0 untuk semua ξ ∈ R1 . Asumsikan lebih lanjut bahwa Z(x, ·) ∈ Lt untuk semua x ∈ Uδ (x0) dan bahwa terdapat fungsi terukur-µ g ∈ L1 sedemikian sehingga g(ξ) ≤ Z(x, ξ) untuk semua ξ ∈ R1 dan semua x ∈ Uδ (x0 ). Maka
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
38 (i) QE : Rn → R adalah l.s.c. di x0 , (ii) QE + αQDt : Rn → R adalah l.s.c. di x0 untuk semua α ∈ (0, 12 ], (iii) QE + αQDt+ : Rn → R adalah l.s.c. di x0 untuk semua α ∈ (0, 1], dan (iv) QEpη : Rn → R adalah l.s.c. di x0 jika berlaku r ≥ p Bukti : Untuk mengaplikasikan lemma dibutuhkan minorant terintegralkan dari integrand. Misalkan {xk } adalah barisan yang konvergen ke x0. diasumsikan {xk } ⊂ Uδ (x0). (i) Secara bersama-sama Lemma Fatou dan semikontinuitas bawah Z(·, ξ) di x0 menghasilkan lim inf QE (xk ) ≥ lim inf Z(xk , ξ)µ(dξ) ≥ k→∞
Z
k→∞
Z(x0, ξ)µ(dξ) = QE (x0)
Rt
dengan mana minorant g dari Z(·, ξ) ada menurut asumsi. Dengan demikian ekspektasi fungsi nilai adalah semikontiniu bawah di x0 . (ii) Untuk membuktikan semikontinuitas bawah dari fungsi QE +αQDt di x0 untuk α ∈ (0, 12 ] sekali lagi digunakan formulasi ulang Di X = 2E max{X, EX} − 2EX, bandingkan Lemma 3.6.13. dan diperoleh; QE (x0) + αQDt (x0 ) = (1 − 2α)QE (x0) + 2α
Z
max{Z(x0, ξ), QE (x0)}µ(dξ)
Rt
Ekspektasi fungsi nilai QE adalah semikontiniu bawah di x0 menurut (i), fungsi Z(·, ξ) adalah semikontiniu bawah di x0 menurut asumsi, dan karenanya juga maksimumnya x → max{Z(·, ξ), QE (·)} Untuk α ∈ (0, 12 ] fungsi (1 − 2α)QE juga l.s.c. di x0 dan ini menghasilkan penegasan. (iii) Mari kembali ke semideviasi berorde 1 (semideviasi absolut).
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
39 Digunakan max{a, 0} = max{a+ b, b}− b untuk a, b ∈ R untuk merumuskan kembali
QE (x0) + αQDt+ (x0) = QE (x0 ) + α
R
max{Z(x0 , ξ) − QE (x0 ), 0}µ(dξ)
Rt
= (1 − α)QE (x0) + α
R
max{Z(x0, ξ), QE (x0)}µ(dξ)
Rt
Dengan mengikuti argumentasi dalam (ii) di peroleh bahwa jumlah fungsi (1 − α)QE (·) dan R α max{Z(·, ξ), QE (·)} juga adalah semikontiniu bawah untuk α dalam (0, 1]. ini Rt
membuktikan semikontiniu bawah dari semideviasi absolut.
(i) Terakhir, sampai pada ekspektasi kelebihan target η0 . Fungsi x → max{Z(x, ξ) − η0, 0} adalah semikontiniu bawah di x0 karena Z(x, ξ) adalah semikontiniu bawah di x0. (ii) Pangkat ke-p dari fungsi f adalah semikontiniu bawah, atas domain di mana fungsi f adalah nonnegatip dan semikontiniu bawah. (iii) Karena itu x → max{Z(x, ξ) − η0 < 0}p adalah semikontiniu bawah di x0. Karena g 0 (ξ) ≡ 0 adalah minorant untuk integrand (disini tidak dibutuhkan eksistensi minorant g ), Lemma Fatou menghasilkan
lim inf k→∞
≥
R
R
max{Z(xk , ξ) − η0 , 0}p µ(dξ)
Rt
lim inf k→∞ max{Z(xk , ξ) − η0 , 0}p µ(dξ)
Rt
≥
R
max{Z(xk , ξ) − η0 , 0}p µ(dξ)
Rt
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
40 R
max{Z(x, ξ) − η0 , 0}p adalah nonnegatip. Menurut Lemma Rt √ 4.2.2 semikontinuitas bawah dari x → p x menghasilkan pernyataan tegas. Fungsi x →
Tentu saja, tertarik pada syarat-syarat dengan fungsi resiko adalah kontinu. Di berikan syarat cukup atas ukuran µ, karena itu definisikan himpunan titik-titik diskontinuitas Z(·, ξ)dix
DZ0 (x) = {ξ ∈ R1 : Z(·, ξ) diskontinu di x} = {ξ ∈ R1 : ∃{xk } ⊂ Rn , xk → x dengan batasan Z(xk , ξ) 6→ Z(x, ξ)}
Catatan bahwa himpunan DZ0 terukur. Proposisi 4.2.8 Misalkan x0 ∈ Rn dan η0 ∈ R. Asumsikan bahwa terdapat neighborhood Uδ (x0 ) dari x0 dengan δ > 0 sedemikian sehingga Z(x, ·) adalah fungsi terukur-µ untuk semua x ∈ Uδ (x0 ) dan bahwa Z(x, ·) adalah semikontiniu bawah di x0 untuk semua ξ ∈ R1 . Asumsikan lebih lanjut fungsi terukur-µg ∈ L1 sedemikian sehingga |Z(x, ξ)| ≤ g(ξ) untuk semua ξ ∈ R1 dan semua x ∈ Uδ (x0 ). Misalkan DZ0 (x0 ) adalah himpunan nol-µ. Maka
(i) QE : Rn → R adalah kontinu di x0 dan (ii) jika g berada dalam Lp maka QDp , QDp+ dan QDpµ sebagai fungsi dari Rn ke R adalah kontinu di x0.
Bukti: Bukti pada dasarnya didasarkan pada teorema konvergensi didominasi Lebesgue, lihat Billingsley (1995). Untuk aplikasinya perlu kiranya ditunjukkan bahwa integrand yang bersesuaian konvergen hampir pasi-? dan bahwa terdapat
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
41 majorant terintegralkan atas integrand masing-masing fungsi resiko. Misalkan {xk } adalah barisan yang konvergen ke x0 dan diasumsikan (xk ) ⊂ Uδ (x0). (i) Menurut asumsi µ(DZ0 (x0 )) = 0, diperoleh lim Z(xn , ξ) = Z(x0 , ξ)∀ξ ∈ R1\DZl (x0)
n→∞
(4.5)
yaitu, konvergensi hampir pasti-µ dari Z(xn , ·) ke Z(x0 , ·). Ini, bersama-sama dengan asumsi eksistensi majorant g ∈ L1 menghasilkan Z Z lim Z(xk , ξ)µ(dξ) = Z(x0, ξ) = QF1 (x0) lim QF1 (xk ) = k→∞
k→∞
Rt
Rt
dan dengan demikian, kontinuitas QE di x0. (ii) Menurut persamaan (3.10) dan kontinuitas QE di x0 di peroleh lim |Z(xk , ξ) − QE (xk )| = |Z(x0, ξ) − QE (x0 )| ∀ξ ∈ R1 \DZl (x0)
k→∞
Karena x → xp juga kontinu, diperoleh konvergensi hampir pasti-µ dari integrand deviasi sentral berorde p lim |Z(xk , ξ) − QE (xk )|p = |Z(x0, ξ) − QE (x0)|p R1 \, ∀ξ ∈ R1\DZl (x0)
k→∞
Untuk inegrand berlaku |Z(xk , ξ) − QE (xk )|p ≤ 2p |Z(xk , ξ)|p + |QE (xk )|p ≤ 2p (g(ξ)p + |QE (xk )|p) untuk semua k ∈ N dan semua ξ ∈ R1. Menurut asumsi diperoleh |Z(xk , ξ)| ≤ g(ξ) untuk semua ξ ∈ R1 dan semua k ∈ N dengan demikian diperoleh Z Z |QE (xk )| = |Z(xk , ξ)|µ(dξ) ≤ g(ξ)µ(dξ) ≤ C < ∞ Rl
Rl
karena g berada dalam Lp maka fungsi 2p (g p +C p) adalah majorant terintegralkan untuk |Z(xk , ξ) − QE (xk )|p untuk semua k ∈ N. Teorema konvergensi dominan Lebesgue memberikan
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
42
lim
k→∞
R
|Z(xk , ξ) − QE (xk )|pµ(dξ) =
Rl
R Rl
=
R
lim |Z(xk , ξ) − QE (xk )|pµ(dξ)
k→∞
|Z(xk , ξ) − QE (x0)|p µ(dξ)
Rl
Terakhir, kontinuitas fungsi x →
√ p x memberikan kontinuitas dari QDp di x0.
Kembali ke semideviasi berorde p. Karena kontinuitas QE di x0 dan konvergensi hampir pasti-µ dari Z(xn , ξ) bahwa max {Z(xn , ξ) − QE (xn ), 0}p hampir pasti konvergen-µ ke max {Z(xn , ξ) − QE (xn ), 0}p untuk semua p > 0. diperoleh majorant terintegralkan dengan taksiran
|max {Z(xk , ξ) − QE (xk ), 0)}| ≤ max {|Z(xk , ξ) − QE (xk )|, 0)} ≤ |Z(xk , ξ)| + |QE (xk )| R ≤ g l (ξ) := g(ξ) + Rl g(ξ)µ(dξ) untuk semua ξ ∈ R1 dan semua k ∈ N. Karena g 0 adalah majorant dari fungsi nonnegatip max{Z(xk , ξ)0QE (xk , 0)}, pangkatnya (g 0)p juga merupakan majorant dari max{Z(xk ξ) − QE (xk , 0)}p untuk semua ξ ∈ R1 dan semua k ∈ N. Majorant yang disebut terakhir terintegralkan menurutasumsi. Diaplikasikan teorema konvergensi dominan Lebesgue lim
Z
p
max {Z(xk , ξ) − QE (xk ), 0} µ(dξ) =
k→∞ Rll
l
dan dengan kontinuitas x →
Z
max {Z(x0, ξ)) − QE (X0 ), 0}p µ(dξ)
Rll
√ p x kita peroleh kontinuitas QDp+ di x0.
Konvergensi hampir pasti-µ dari max{Z(xn , ξ) − η0 , 0} berlaku karena kontinuitas x → max{x, 0} dan konvergensi hampir pasti-µ dari Z(xn , ξ). Didefinisikan g 0 (ξ) := f(ξ) + |η0 | untuk semua ξ ∈ R1 . Menurut asumsi berlaku
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
43 g 0 (ξ) ≥ |Z(xk , ξ)| + |η0 | ≥ max{Z(xk , ·) − η0 , 0} untuk semua ξ ∈ R1 dan semua k ∈ N. Karena max{Z(xk , ·) − η0 , 0} nonnegatip, (g 0)p adalah majorant dari max{Z (xk , ·) − η0 , 0}p untuk semua ξ ∈ R1 dan semua k ∈ N. Teorema konvergensi dominan Lebesgue menghasilkan lim
Z
k→∞
p
max{Z(xk , ξ) − η0 , 0} µ(dξ) =
Rl
dan bersama-sama dengan kontinuitas x →
Z
max{Z(x0, ξ) − η0 , 0}p µ(dξ)
Rl
√ p
x diperoleh kontinuitas dari QDpµ di
x0 . Catatan 4.2.9 Jika Z(·, ξ) kontinu di x0 untuk semua ξ ∈ R1 , di peroleh DZ0 (x0 ) = ∅ dan Proposisi 4.2.8 berlaku. Bila masalah keputusan konveks sangat diperlukan dalam menggunakan ukuran resiko yang melanggengkan konveksitas. Ada hubungan kuat antara pertanyaan ini dan kelas ukuran resiko konveks ternyata, bila diperhatikan fungsi resiko yang merupakan pemetaan komposit dengan tipe Q = R ◦ Z di mana Z : Rn → Z, memberikan x ke Z(x, ξ(w)) dimana R : Z → R adalah ukuran resiko. Dengan Z adalah konveks, syarat cukup untuk konveksitas pemetaan komposit Q adalah bahwa ukuran resiko R tidak turun monoton dan konveks. Maka untuk λ1 , λ2 ∈ [0, 1], λ1 + λ2 = 1 berlaku; ¯ ¯ ¯ ¯ R(Z¯ (λ1 x + λ2 y)) ≤ R((λ1 Z(x)λ 2 Z(y)) ≤ λ1 R(Z(x)) + λ2 R((Z(y))
(4.6)
di mana ketaksamaan pertama adalah disebabkan konveksitas Z dan monotonisitas dari R dan ketaksamaan kedua adalah disebabkan konveksitas R
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
44 Proposisi 4.2.11 Misalkan η0 ∈ R, α ∈ R+ dan r ∈ N. Asumsikan Z(x, ·) adalah terukur-µ dan elemen dari Lr untuk semua x ∈ X. Asumsikan lebih lanjut bahwa Z(·, ξ) adalah konveks atas X untuk semua ξ ∈ R1 . Maka
(i) QE : Rn → R adalah konveks atas X untuk r ≥ 1, (ii) QE + αQD : Rn → R adalah konveks atas X untuk α ∈ 0, 12 dan r ≥ 1, (iii) QE + αQD+ : Rn → R adalah konveks atas X untuk α ∈ (0, 1] dan r ≥ p, dan (iv) QEpη : Rn → R adalah konveks atas X untuk r ≥ p.
Bukti : Telah diketahui bahwa ekspektasi nilai, ekspektasi kelebihan target dan 1
ukuran resiko EX + α2 D1 (X) dan EX + α(E max{X − EX, 0}p ) p untuk α ∈ (0, 1] memenuhi monotonisitas dan juga aksioma konveksitas, dengan demikian, persamaan (4.5) sah untuk fungsi resiko dalam (i)-(iv). 4.3 Model Nilai Ekspektasi Model nilai ekspektasi inf QE (x), x→X R dimana QE (x) = Rl cx + φ(h − T x)µ(dξ) dan dipadukan terhadap problema khusus yang diberikan oleh ; ¯ ξ(ω))] dan diasumsikan recourse lengkap W (Rm ) = Rs dan feainf R[(cx + φ(x, +
x∈X
sibel dual oleh φ untuk mengemukakan problem inf QE (x) adalah x→X
inf
x∈X
Z
max dj (h − T x)µ(dξ)
Rl j=1,2,··· ,j
(4.7)
Dimana dj, j = 1, 2, 3, · · · , J adalah puncak dari himpunan {u ∈ Rs : U W ≤
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
45 q} dan keterbatasan momen absolut dari h dan T cukup untuk QE menjadi bernilai ril. s Proposisi : 4.3.2. Diasumsikan bahwa recourse lengkap W (Rm +) = R R batasan primal φ : {U ∈ Rs : U W ≤ q} = 6 ∅ dan eksistensi harapan ||h|| + Rl
||T ||µ(dξ) < δ, maka;
1. QE (x) bernilai ril untuk ∀x ∈ Rn 2. QE : Rn → R adalah konveks 3. Bila µ diskrit dan ukuran probabilitas berhingga ,maka QE : Rn → R adalah sebuah fungsi polyhedral.
4.4 Ukuran Deviasi Program Stokastik Linier Dengan Recourse Integer Campuran. Perluasan model mean-risk program stokastik linier dua tahap integer campuran berbentuk ; min{QE (x, µ) : x ∈ X} dimana ; QE (x, µ) =
Z
(cT x + φ(Z − T x))µ(dz)
(4.8)
(4.9)
Rl
Dan φ(t) := min{q T y + q T y 0 : W y + W 0 y 0 = t, y ∈ Z+m , y 0 ∈ Rp }p
(4.10)
matriks semua unsur diatas diasumsikan mempunyai dimensi yang sesuai ,selain itu rasional W dan W 0 dan X ⊆ Rm adalah sebuah polyhedron tak kosong,mungkin syarat integer diperlukan terhadap x, ukuran probabilitas µ, termasuk P (Rs ) yang
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
46 merupakan himpunan ukuran semua probabilitas Borel pada Rs . Ketergantungan QE pada keduanya ( x dan µ) sejak ditetapkan dan akhirnya QE dan objekobjek yang berkaitan akan dipelajari yang mana keduanya sebagai fungsi x dan fungsi bersama f (x, µ), untuk sementara ditetapkan ,andaikan µ ∈ P (Rs ). Asumsi berikut menjamin bahwa model-model diatas akan terdefinisi ,dalam arti bahwa QE (x, µ) ∈ R, untuk semua x ∈ Rm Asumsi 4.4.5 φ : {u ∈ RS : uW ≤ q, W IT u ≤ q l} 6= φ ¯l
m ¯ ) + W 0(R+ ) = RS Asumsi 4.4.4 W (Z+m
Asumsi 4.4.6
R
||Z||µ(dz) < +∞.
RS
Model (4.8), (4.9),(4.10) terjadi dari program linier integer campuran dua tahap atas ketidakpastian,dimana variabel keputusan diambil dalam dua kategori yakni ;
i. Keputusan tahap pertama nilai x diambil dengan cara here and now sebelum diketahui hasil data acak Z = Z(ω). ii. Keputusan tahap kedua (y, y 1) dipilih kemungkinan terbaik , dan keputusan dua tahap ini prosesnya dibawa ke nilai biaya acak yang dapat dinyatakan sebagai berikut ; f(x, z(ω)) := cT x + φ(z(ωz − T x))
Persoalan untuk mendapatkan sebuah keputusan x terbaik here and now pada keadaan tersebut diatas sama seperti mendapatkan sebuah variabel acak terbaik dalam rumpun {f(x, z(ω)) : x ∈ X} yang merupakan pedoman untuk
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
47 perluasan mean-risk yakni ; min{QE (x, µ) + αQR (x, µ) : x ∈ X}
(4.11)
dan dari model (4.11) dengan faktor bobot yang ditentukan α > 0, dan bentuk resiko QR. Ada tiga versi untuk model (4.11) yang memberikan spesifikasi berikut ; - Deviasi central QR(x, µ) := QD (x, µ) :=
Z
|f (x, z) − QE (x, µ)|µ(dz) jika 0 ≤ α ≤
1 2
(4.12)
RS
-Semideviasi QR(x, µ) := QD+ (x, µ) :=
Z
max{f (x, z) − QE (x, µ), 0}µ(dz) jika 0 ≤ α ≤ 1
RS
(4.13) - Kelebihan ekspektasi dari sebuah target η ∈ R QR (x, µ) := QDη (x, η) :=
Z
max{f (x, µ) − η, 0}µ(dz) jika α ≥ 0
(4.14)
RS
Besaran-besaran diatas disebut ukuran deviasi karena semua didasarkan pada deviasi ekspektasi,oleh variabel acak mean atau dari suatu target sebelum dipilih . Penekanan pada ukuran deviasi ditentukan oleh operasi linier sebagiansebagian (diambil nilai mutlak atau maksimum) yang sebagian besar berupa algoritma,dan akan terlihat bahwa linieritas sebagian-sebagian dari problem (4.10) dapat berhasil dilakukan oleh perluasan tehnik program linier integer campuran ,asalkan didasarkan ukuran µ yang diskrit. Motivasi lain untuk mengingat ukuran deviasi diatas merupakan sandaran dalam konsistensi yang disebabkan dominasi stokastik .
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
BAB 5 KESIMPULAN
A. Masa yang akan datang adalah tidak pasti,dan banyak persoalan-persoalan yang meliputi data masa yang akan datang, yang merupakan subjek ketidakpastian. Kemudian masalah ketidakpastian masuk pada bidang optimasi yang bertujuan untuk membuat keputusan optimal. Program stokastik linier dengan recourse integer programming campuran begitu luas apilkasinya pada bidang optimasi oleh ketidakpastian, diasumsikan sebagai sebuah distribusi probabilitas untuk parameter acak A dan b, yang dibedakan oleh penetapan dan kuatnya suatu optimasi terhadap skedul model stokastik,ditambah asumsi bahwa distribusi dari parameterparameter acak tidak bergantung oleh keputusan vektor x. B. Karakteristik yang berkaitan dengan kotinuitas dan koveksitas dari nilai fungsi serta stabilitas persoalan optimasi dapat berakibat terhadap implikasi berbeda untuk ukuran deviasi yang berbeda pula. Fokus model dari penelitian ini adalah program stokastik integer yang berarti bahwa pada kaidah persoalan memilih persyaratan integer terhadap variabel. Dalam kasus demikian fungsi nilai diasumsikan mempunyai semikontinu bawah (l.s.c) dan dari konsep l.s.c dapat diperoleh ukuran resiko seperti tertera pada tabel 5.1 dibawah ini.
48 Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
49 Persoalan Mean-Resiko Bobot Ordo QE + αWDp α ∈ 0, 12 P =1 + QE + αQDp α ∈ (0, 1] P = 1 ν QE + α ∈ QEp α ∈ R+ P =N Tabel 5.1 : Semikontiniu bawah dari ukuran resiko
Bobot dan Ordo untuk mana model Mean-Resiko di kelompokkan ( Tabel 5.1) merupakan l.s.c.
Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008
DAFTAR PUSTAKA
[1] Andreas Markert & Rudiger Schultz (2005), On deviation measures in stochastic integer programming, Operations Research Letters 33/5, pp. 441-449. [2] Artzner, P.; F. Delbaen; J.-M. Eber; D. Heath (1999), Coherent Measures of Risk, Mathematical Finance 9/3, pp. 203-228. [3] Artzner, P.; F. Delbaen; J. M.Eber; D. Heath; H. Ku (2003), Coherent Multi period Risk Measurement, Preprint, http://www.math.ethz.ch/ Delbaen/. [4] Birge JR. Louveaux FV. (1997), Introduction to stochastic Programming, Springer New York. [5] Eichhorn dan Rmisch (2006), Stability of multistage stochastic programs incorporating polyhedral risk measures, Optimization. [6] Fishburn, P.C. (1977), Mean-Risk Analysis with Risk Associated with Below Target Returns, American Economic Review 67/2, pp. 116-26. [7] Kristoffersen (2005), Deviation Measures in Linear Two-Stage Stochastic Programming Mathematical Methods of Operations Research 62/2, pp. 255-274. [8] Kristoffersen .T.Krogh,(2007) Stochastic Programming With Applications to Power Systems, Department of Operations Research, University Aarhus, Denmark. [9] Markowitz, H.M. (1959), Portfolio selection: Efficient Diversification of Investments, Wiley, New York. [10] Muller, A.; D. Stoyan (2002), Comparison Methods for Stochastic Models and Risk, Wiley, Chichester. [11] Pflug, G. (1999), How to Measure Risk, Festschrift for F. Ferschl, Physica Verlag, Wrzburg [12] Steinbach, M.C. (2001), Markowitz Revisited: Mean-Variance Models in Financial Portfolio Analysis, SIAM Review 43/1, pp. 31-85.
50 Mujio : Ukuran Deviasi Dalam Stokastik Programming Dengan Recourse Integer Campuran, 2009 USU Repository © 2008