METODE PENGEMBANGAN PENDEKATAN RATA RATA SAMPEL UNTUK MENYELESAIKAN MASALAH PROGRAM STOKASTIK CACAH CAMPURAN
TESIS
Oleh
FARIDAWATY MARPAUNG 067021003/MT
SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008
METODE PENGEMBANGAN PENDEKATAN RATA RATA SAMPEL UNTUK MENYELESAIKAN MASALAH PROGRAM STOKASTIK CACAH CAMPURAN
TESIS
Untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Sekolah Pascasarjana Universitas Sumatera Utara
Oleh
FARIDAWATY MARPAUNG 067021003/MT
SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008
Judul Tesis
: METODE PENGEMBANGAN PENDEKATAN RATA-RATA SAMPEL UNTUK MENYELESAIKAN MASALAH PROGRAM STOKASTIK CACAH CAMPURAN Nama Mahasiswa : Faridawaty Marpaung Nomor Pokok : 067021003 Program Studi : Matematika
Menyetujui, Komisi Pembimbing
(Prof. Dr. Herman Mawengkang) Ketua
(Dr. Saib Suwilo, M.Sc) Anggota
Ketua Program Studi,
Direktur,
(Prof. Dr. Herman Mawengkang)
(Prof. Dr. Ir. T.Chairun Nisa. B,M.Sc)
Tanggal lulus: 15 Juli 2008
Telah diuji pada Tanggal 15 Juli 2008
PANITIA PENGUJI TESIS Ketua
: Prof. Dr. Herman Mawengkang
Anggota
: 1. Dr. Saib Suwilo, M.Sc 2. Drs. Marwan Harahap, M.Eng 3. Drs. Opim Salim S., MIkom. PhD
ABSTRAK Penelitian ini mengemukakan atau menjelaskan suatu strategi penyelesaian untuk menyelesaikan masalah program integer stokastik dua tahap. Metodologi ini menggunakan ratarata program stokastik melalui sampel, dan pemecahan ratarata masalah melalui sebuah algoritma optimal. Tujuan dari skema ini akan menghasilkan sebuah penyelesaian optimal untuk masalah yang sebenarnya dengan pendekatan sebuah eksponensial yang cepat sebagai ukuran sampel yang fix, dijelaskan teknik statistik dan deterministik bounding untuk memvalidasi kualitas dari sebuah calon penyelesaian optimal. Kata Kunci : Program stokastik, Optimal.
i
ABSTRACT This thesis addresses a solution strategy for solving two stage stochastic integer programming problems. The proposed methodology relies on approximation the underlying stochastic program via sampling, and solving the approximate problem via a specialized optimization algorithm. The proposed scheme will produce an optimal solution to the true problem with probability approaching one exponentially fast as the sample size increased. For fixed sample size, we described statistical and deterministic bounding techniques to validate the quality of a candidate optimal solution. Keywords : Stochastic program, Optimal
ii
KATA PENGANTAR Puji dan syukur kehadirat Allah SWT penulis panjatkan atas limpahan rahmat dan karunia-Nya atas terselesaikannya penulisan tesis ini yang berjudul ”Metode Pengembangan pendekatan rata-rata sampel untuk menyelesaikan masalah program stokastik”. Pada kesempatan ini, penulis menyampaikan ucapakan terima kasih yang sebesar-besarnya kepada: Bapak Prof. dr. Chaeruddin P. Lubis, DTM&H, Sp.A(K) selaku Rektor Universitas Sumatera Utara yang sudah memberi kesempatan kepada penulis untuk menempuh pendidikan di Universitas Sumatera Utara. Ibu Prof. Dr. Ir. T. Chairun Nisa B., M.Sc. selaku Direktur Sekolah Pascasarjana Universitas Sumatera Utara yang sudah memberikan kesempatan kepada penulis untuk mengikuti Program Studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara. Bapak Prof. Dr. Herman Mawengkang selaku Ketua Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara dan selaku Anggota Komisi Pembimbing yang telah membantu dalam penyelesaian tesisi ini. Bapak Dr. Saib Suwilo, M.Sc. selaku Sekretaris Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara yang telah memberikan motivasi kepada penulis. Bapak Prof. Dr. Herman Mawengkang selaku Ketua Komisi Pembimbing yang telah banyak memberikan saran dan bimbingan kepada penulis.
iii
Drs.
Marwan Harahap, M.Eng.
dan Bapak Drs.
Opim Salim S.,
MIkom. PhD. selaku Pembanding atas segala saran dan masukannya. Seluruh staf pengajar pada Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara yang sudah membimbing dan membantu selama penulis mengenyam pendidikan. Seluruh keluarga, Ayahanda A.T. Marpaung dan Ibunda T. Siahaan dan adik-adik yang senantiasa mendukung dan mendoakan untuk keberhasilan penulis dalam menyelesaikan pendidikan ini. Ibu Darmawaty, S.Pd. dan keluarga yang sudah banyak membantu penulis dalam menghadapi banyak kesulitan selama menyelesaikan pendidikan ini. Kepada semua teman-teman serta semua pihak yang tidak dapat disebutkan satu persatu penulis ucapkan terima kasih atas bantuan dan dorongan yang telah diberikan sehingga penulis dapat menyelesaikan pendidikan tepat waktu. Tidak lupa terima kasih untuk Misiani, SSi. selaku staf Administrasi Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara yang telah memberikan pelayanan yang baik kepada penulis. Penulis menyadari tesis ini masih mempunyai kekurangan, namun demikian harapan penulis, semoga tesis ini dapat bermanfaat bagi yang membutuhkannya.
Medan,
Juli 2008
Penulis,
Faridawaty Marpaung
iv
RIWAYAT HIDUP Penulis dilahirkan di Medan pada tanggal 30 Oktober 1971, sebagai anak kedua dari tujuh bersaudara dari ayah A.T. Marpaung dan Ibu T. Siahaan. Penulis menamatkan Sekolah Dasar Negeri 060833 Medan pada tahun 1984, Sekolah Menengah Pertama Negeri 17 Medan pada tahun 1987, Sekolah Menengah Atas Negeri 4 Medan pada tahun 1990, dan pada tahun 1990 melanjutkan pendidikan di Universitas Sumatera Utara (USU) Medan, Fakultas Matematika dan Ilmu Pengetahuan Alam, Jurusan Matematika dan lulus pada tahun 1996. Dari tahun 2002 sampai dengan sekarang penulis menjadi staf pengajar, di Universitas Muhammadiyah Sumatera Utara (UMSU). Pada tahun 2006 penulis mengikuti pendidikan pada Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara.
v
DAFTAR ISI Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
i
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ii
KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . .
iii
RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . .
v
DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vi
BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . .
1
1.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . .
1
1.2 Perumusan Masalah . . . . . . . . . . . . . . . . . . . .
3
1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . .
3
1.4 Kontribusi Penelitian . . . . . . . . . . . . . . . . . . .
4
1.5 Metodologi Penelitian . . . . . . . . . . . . . . . . . . .
4
BAB 2 TINJAUAN PUSTAKA . . . . . . . . . . . . . . . . . . . .
5
2.1 Pengertian Program Stokastik . . . . . . . . . . . . . . .
5
2.2 Program Stokastik Dua Tahap . . . . . . . . . . . . . . .
8
2.3 Pengertian Dasar Program stokastik Tahap Ganda . . . . .
12
2.4 Metode Pendekatan Rata-rata Sampel ( PRS ) . . . . . . .
21
BAB 3 PENGEMBANGAN RATA-RATA SAMPEL . . . . . . . . . .
23
3.1 Tahap Pertama Diskrit . . . . . . . . . . . . . . . . . .
23
3.2 Tahap Pertama Kontinu . . . . . . . . . . . . . . . . . .
25
3.3 Tahap Pertama Kontinu dan Sebaran Diskrit
27
vi
. . . . . . .
3.4 Menyelesaikan Problem PRS
. . . . . . . . . . . . . . .
32
BAB 4 KESIMPULAN . . . . . . . . . . . . . . . . . . . . . . . .
37
DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . .
38
vii
BAB 1 PENDAHULUAN
1.1 Latar Belakang Dalam model operasional dan perencanaan diperlukan syarat bilangan cacah pada peubah keputusan. Untuk hal, keputusan peningkatan sumber penghasilan, memiliki faktor seperti harga tetap, perubahan biaya, dan lain-lain menunjukkan model program cacah campuran. Berbagai aplikasi seperti yang muncul dalam skedul, rotasi, lokasi, perencanaan produksi, dan pembelanjaan, menunjukkan model bilangan cacah. 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, paradigma ini dikenal sebagai model recourse. Program stokastik cacah campuran adalah cabang program stokastik yang berkaitan dengan program stokastik dimana peubah keputusan meliputi syarat umum. Dalam program stokastik cacah campuran bertujuan mencari non-antisipasi keputusan (disini dan sekarang) yang diprioritaskan untuk mengetahui realisasi peubah acak. Keputusan ini dibutuhkan untuk menjadikan cara menjumlahkan total biaya atau hasil akhir optimal, dan lagi pula berbagai keputusan (termasuk melakukan recourse) dibatasi untuk bilangan cacah. Berbagai macam masalah
1
2 program stokastik cacah campuran yang timbul tergantung pada keputusan bilangan cacah yang dibuat, jarang untuk hasil observasi peubah acak. Peubah keputusan problem program stokastik dua-tahap dipartisi menjadi dua himpunan. Peubah tahap pertama ditentukan sebelum melakukan realisasi parameter tak pasti. Kemudian, satu kejadian acak yang muncul sendiri, selanjutnya, desain atau perbaikan pengawasan operasi dapat berbentuk pilihan, pada biaya pasti, nilai tahap kedua atau peubah recourse. Tujuan deterministik keputusan tahap pertama sedemikian hingga jumlah biaya tahap pertama dan ekspektasi biaya recourse minimum. Formulasi standar dari program stokastik dua tahap sebagai berikut: min {g(x) := cT x + E[Q(x, ξ(ω))]} x∈X
Kendala Ax = b
(1.1)
0 x ∈ RM +
dengan x adalah keputusan antisipatif tahap pertama yang diambil sebelum peubah acak teramati dan Q(x, ω) := inf {q T y : Wy ≥ h − Tx} y∈Y
(1.2)
merupakan nilai optimal dan ξ := (q, T, W, h) menyatakan vektor dari parameter problem tahap kedua. Diandaikan bahwa beberapa (atau semua) komponen ξ acak, ditulis ξ(ω), dan ekspektasi dalam diambil berdasarkan sebaran peluang dari ξ(ω) yang diandaikan diketahui. Persoalan dengan peubah x ∈ Rn1 , membentuk tahap pertama yang perlu diputuskan sebelum realisasi ξ(ω). Persoalan (1.2) dengan peubah y ∈ Rn2 , membentuk recourse untuk keputusan tahap pertama yang diketahui dan realisasi ξ dari data acak.
3 Penelitian ini berkaitan dengan program stokastik dua tahap dengan recourse fix, yaitu matriks W adalah tertentu (bukan acak) dan peubah recourse dipersyaratkan cacah, yaitu Y ⊆ Z n2 dalam (1.2). Diperlihatkan dalam Schultz, R. (1995) dua sumber kesulitan dalam menyelesaikan program stokastik dengan recourse cacah adalah:
1. Evaluasi eksak dari ekspektasi biaya recourse. 2. Mengoptimalkan Ekspektasi biaya recourse
Dalam pendekatan yang diajukan, fungsi ekspektasi biaya recourse dalam diganti oleh pendekatan rata-rata sampel dan problem optimisasi terkait diselesaikan dengan memakai algoritma khusus untuk optimisasi tak konveks. Disini dianalisis laju konvergensi dari Pendekatan Ratarata Sampel (PRS) untuk program stokastik dengan recourse cacah.
1.2 Perumusan Masalah Untuk menentukan E[Q(x, ξ(ω))] pada persamaan secara eksak sulit dilakukan sehingga dilakukan pendekatan yang baik bagi E[Q(x, ξ(ω))].
1.3 Tujuan Penelitian Penelitian ini bertujuan untuk mengembangkan metode pendekatan ratarata sampel untuk menentukan fungsi biaya recourse dalam masalah program stokastik cacah campuran.
4 1.4 Kontribusi Penelitian Penelitian ini diharapkan memperolehnya metode pengembangan pendekatan rata-rata sampel untuk menyelesaikan persoalan keputusan dan perencanaan yang mengandung ketidakpastian.
1.5 Metodologi Penelitian Penelitian ini membahas metode pengembangan pendekatan rata-rata sampel untuk memecahkan program stokastik cacah campuran. Sebagai langkah awal pada bab III dibicarakan konsep dasar program stokastik dan program stokastik dua tahap yang bertujuan untuk menggeneralisasi program stokastik dua tahap. Program stokastik dua tahap berisi vektor deterministik. Pada tahap pertama penyelesaian persoalan rencana awal deterministik akan dibuat. Pembentukan rencana awal deterministik dilakukan sebelum kondisi acak dari persoalan ditentukan. Sebuah vector acak pada penyelesaian persoalan yang sesuai digunakan untuk merencanakan kompensasi divergensi, spesifikasi parameter dari persoalan akan muncul pada tahap kedua. Selanjutnya pada bab III juga dibahas metode Pendekatan Rata-rata Sampel (PRS) yang digunakan pada tahap pertama bertujuan untuk mengestimasi ekspektasi fungsi nilai E[Q(x, ξ(ω))] oleh P n fungsi rata-rata sampel N −1 N n=1 Q(x, ξ ) Pada bagian akhir dibahas Algoritma Branch and Bound yang mengeksploitasi sifat struktural dengan mempartisi ruang pencarian sepanjang harga x.
BAB 2 TINJAUAN PUSTAKA
2.1 Pengertian Program Stokastik Persoalan keputusan dapat dimodelkan dengan menggunakan program matematika, tujuannya adalah untuk menentukan nilai maksimum atau minimum. Keputusan yang dihasilkan bergantung kepada kendala yang dibatasi oleh sumber dana, persyaratan minimum dan lain-lain. Keputusan dinyatakan oleh peubah berupa bilangan cacah atau nonnegatif. Sebagai contoh dari persoalan data termasuk biaya perunit, rata-rata produksi, penjualan atau kapasitas. Andaikan keputusan dinyatakan dengan peubah (x1, x2 , . . . , xn ). Sebagai contoh xi menyatakan produksi ke i dari n produk. Bentuk umum program matematikanya adalah: max Z = f (x) Kendala fi (x) ≥ bi , i = 1, 2, . . . , n
(2.1)
x ≥ 0, x ∈ X dimana X adalah himpunan real non negative. Program stokastik adalah sebuah nama yang menyatakan program matematika yang dapat berupa linear, cacah, cacah campuran, non linear dengan menampilkan elemen stokastik pada data. Sehingga program stokastik dapat dinyatakan bahwa: a. Pada program matematika deterministik, data adalah bilangan bilangan yang diketahui. 5
6 b. Pada program stokastik, data merupakan bilangan tidak pasti yang disajikan sebagai distribusi peluang. Program stokastik adalah merupakan program matematika, dimana beberapa data yang termuat pada tujuan atau kendala mengandung ketidakpastian, ketidakpastian biasanya dicirikan oleh distribusi peluang pada parameter. Walaupun ketidakpastian didefinisikan dengan tepat, tetapi pada prakteknya diberikan beberapa scenario yang spesifik dan distribusi peluang gabungan yang cepat. Ada dua model dalam permasalahan program stokastik, yaitu: 1. Recourse Models (Model Rekursif) 2. Probabilistically Constrained Models (Model Kendala Berpeluang) Dalam persoalan program stokastik adalah membuat sebuah keputusan sekarang dan meminimumkan biaya rata-rata harapan sebagai konsekuensi dari keputusan, paradigma ini dikenal sebagai model recourse. Andaikan x adalah vektor keputusan yang diambil, dan y(w) adalah sebuah vektor keputusan yang menyatakan aksi terbaru atau konsekuensi dari x. Himpunan berbeda yang berisi y akan dipilih dari tiap-tiap hasil yang mungkin dari w. Formulasi dua tahapnya adalah min h1 (x) + E[h2 (y(w), w)] Kendala g1 (x) ≤ 0, . . . , gm (x) ≤ 0 f1 (x, y(w)) ≤ 0, ∀w ∈ W .. . fk (x, y(w)) ≤ 0, ∀w ∈ W x ∈ X, y(w) ∈ Y
(2.2)
7 Dimana himpunan kendala f1 , f2 , . . . , fk menggambarkan hubungan antara keputusan tahap pertama x dan keputusan tahap kedua y(w). Dicatat bahwa dipersyaratkan tiap-tiap kendala dipenuhi dengan peluang 1, atau untuk setiap w ∈ W yang mungkin. Fungsi h2 merupakan penyelesaian yang sering muncul dari persoalan matematika. Tidak dibutuhkan untuk membuat korelasi yang berubahubah (recourse) untuk keputusan tahap pertama, perlu untuk dibuat korelasi yang terbaik. Untuk persoalan tahap ganda, pengaruh keputusan sekarang akan ditunggu untuk beberapa ketidakpastian yang diselesaikan kembali (direalisasikan), sehingga pembuatan keputusan yang lain didasarkan pada apa yang terjadi. Tujuannya adalah untuk meminimumkan biaya yang diharapkan dari semua keputusan yang diambil. Pada beberapa kasus, dapat digunakan suatu model yang lebih tepat untuk mencoba menentukan sebuah keputusan, yang mana keputusan tersebut dijamin oleh himpunan kendala yang akan dipenuhi oleh sebuah peluang tertentu. Model umum dengan kendala berpeluang disebut probabilistically constrained models yang dirumuskan sebagai berikut: min Z = f (x) Kendala P [g1(x) ≤ 0 . . . gm (x) ≤ 0] ≥ α h1(x) ≤ 0 h2(x) ≤ 0 x∈X
(2.3)
8 2.2 Program Stokastik Dua Tahap Banyak persoalan perencanaan dan manajemen yang mengandung resiko dan ketidakpastian dibahas dengan program stokastik dua tahap.
Persoalan
stokastik dengan kompensasi dari divergensi pada system dengan kendala mempunyai aplikasi yang lebih banyak dari pada model program yang lain. Penyelesaian persoalan program stokastik dua tahap berisi vektor deterministik. Pada tahap pertama, penyelesaian persoalan rencana awal deterministik akan dibuat. Pembentukan rencana awal deterministic dilakukan sebelum kondisi acak dari persoalan ditentukan. Sebuah vektor acak pada penyelesaian persoalan yang sesuai digunakan untuk merencanakan kompensasi divergensi, spesifikasi parameter dari persoalan akan muncul pada tahap kedua. Tujuan dari manager pada persoalan di atas adalah meminimum nilai rata-rata yang mana tidak hanya termasuk pengeluaran pada tahap perencanaan pendahuluan tetapi juga pada tahap kedua yang diperlukan untuk mengkompensasi pada divergensi di dalam system kendala persoalan. Jika persoalan program stokastik dengan model dua tahap dapat diselesaikan maka pemilihan dari rencana awal deterministic akan menjamin keberadaan (ekstensi) vektor acak di dalam kompensasi untuk sistem yang divergen. Andaikan terdapat persoalan berikut: min(C, X)
(2.4)
A0X = B 0
(2.5)
AX = B
(2.6)
X≥0
(2.7)
9 Dimana: C = {cj }, j = 1, 2, . . . , m B = {bi}, i = 1, 2, . . . , m B 0 = {b0k }, k = 1, 2, . . . , m A0 = {a0kj }, k = 1, 2, . . . , m, j = 1, 2, . . . , n A = {aij }, i = 1, 2, . . . , m, j = 1, 2, . . . , n Andaikan elemen dari matriks A = A(ω), vektor B = B(ω) dan C = C(ω) bernilai acak. Maka untuk proses penyelesaian dari persoalan (3.4-3.7) akan dibahas menjadi dua tahap, sebelum pengamatan dari parameter acak pada kondisi dari tahap pertama dipilih rencana non-negative deterministik X 0 yang memenuhi kondisi (3.5) pada tahap kedua ditentukan spesifikasi ω 0 dari setiap kejadian acak yang bersamaan sesuai dengan nilai A(ω 0 ) dan B(ω 0). Hitung divergensi B(ω 0 )A(ω 0)X 0 yang muncul pada kondisi (3.6) setelah realisasi ω 0 ∈ Ω. Definisikan vektor kompensasi divergensi Y ≥ 0 yang sesuai dengan hubungan berikut: D(ω 0 )Y (ω 0 ) = B(ω 0 )A(ω 0)X 0
(2.8)
Dimana D = kdil k, i = 1, 2, . . . , m; l = 1, 2, . . . , n1 adalah sebuah matriks kompensasi yang berisi elemen acak. Sehingga diasumsikan bahwa realisasi acak ω yang diamati pada tahap kedua tidak bergantung pada pemilihan rencana pendahuluan X 0 . Perhatikan persoalan program matematika berikut : Tentukan vektor X berdimensi n dan vektor Y (ω) berdimensi n1 , ω ∈ Ω. Yang menghasilkan min Eω {(C(ω), X) + min(H, Y (ω))} X
Y
(2.9)
10 Dengan kendala A0X = B 0 A(ω)X + D(ω)Y = B(ω), ω ∈ Ω X ≥ 0, Y (ω) ≥ 0
(2.10) (2.11) (2.12)
H adalah vektor penalty yang bergantung pada nilai komponen dari vektor Y (ω) yang mana merupakan kompensasi divergensi. E adalah notasi ekspekstasi matematika setelah ditentukan rencana awal X 0 , dipilih komponen vektor Y (ω) dengan cara menjamin penalty minimum untuk konpensasi divergensi pada kondisi dari persoalan. Dengan kata lain, setelah ditentukan vektor X 0 , perlu penyelesaian persoalan {min(H, Y (ω))|D(ω)Y (ω) = B(ω)A(ω)X, Y (ω) ≥ 0} Y
(2.13)
Persoalan (2.13) akan mempunyai banyak rencana, vektor Y (ω) tidak dapat ditentukan pada tiap ω ∈ Ω yang menjamin penemuan kondisi (2.11). Persoalan (2.9)-(2.12) dikenal sebagai persoalan program stokastik dua tahap dan persoalan tahap kedua. Model dan pendekatan dari penyelesaian persoalan program stokastik dua tahap dapat digunakan untuk perspektif perencanaan dan operasional manajemen, karena selalu terdapat keacakan yang mempengaruhi yang sudah direncanakan pada system manajemen (pelaksanaan). Model dua tahap juga kurang sensitive terhadap perubahan pada parameter dari kondisi persoalan, yang menyebabkan lebih stabil. Akibatnya vektor dapat diterima untuk rencana tahap pertama yang diperlukan untuk setiap ω ∈ Ω, terdapat vektor Y ≥ 0 sedemikian
11 hingga. D(ω)Y (ω) = B(ω)A(ω)X
(2.14)
Andaikan kendala tambahan yang disebutkan secara implicit pada (2.14) muncul pada tahap kedua dari persoalan yang dihasilkan; dan andaikan kondisi yang ditentukan pada vektor non-negatif X dari persamaan (2.10) sudah ditentukan. Andaikan himpunan K1 = {X : A0 = B 0 , X ≥ 0} didefinisikan oleh kendala yang sudah ditentukan tetapi K2 = {X : ∀ω ∈ Ω, ∃Y ≥ 0, A(ω)X = B(ω)D(ω)Y (ω)} didefinisikan oleh kendala yang dihasilkan. Maka himpunan K = K1 ∩ K2 adalah himpunan vektor X yang layak memenuhi persoalan (2.9)(2.12). Jika X ∈ K, maka vektor X memenuhi kendala yang sudah ditentukan A0 X = B, X ≥ 0 dan sampai itu, persoalan tahap kedua (2.6) akan memiliki banyak rencana. Untuk perhitungan lanjutan diperlukan hasil berikut:
Teorema 1 Himpunan K dengan vektor X pada persoalan program stokastik dua tahap adalah konveks.
Bukti :
K = K1 ∩ K2 tetapi K1 = {X : A0 = B 0 , X ≥ 0} adalah konveks.
Didefinisikan untuk ω ∈ Ω yang ditentukan pada himpunan K2ω = {X|∃Y (ω) ≥ 0} sedemikian hingga A(ω)X = B(ω)D(ω)Y (ω) adalah konveks. Hal ini menyatakan bahwa K2 = ∪ω∈Ω K2ω dan K = K1 ∩ K2 adalah himpunan konveks sebagai pertolongan himpunan konveks.
12 2.3 Pengertian Dasar Program stokastik Tahap Ganda Persoalan program stokastik dinamik digeneralisasi oleh kasus dua tahap. Banyak persoalan praktis yang berupa perencanaan, perencanaan dan manajemen tidak dapat digambarkan dengan bantuan model statis. Untuk model bertujuan, metode program stokastik tahap ganda seringkali digunakan. Model program stokastik tahap ganda dan metode untuk realisasi secukupnya bergantung pada informasi mengenai nilai parameter di dalam kondisi persoalan, dimana memiliki waktu untuk membuat keputusan selanjutnya. Persoalan dinamik dari tiap-tiap tahap berurutan disyaratkan untuk melengkapi kompensasi divergensi yang dikondisikan realisasi persoalan dan oleh pembuatan keputusan tercepat dari tahap sebelumnya. Pada masalah yang lain, disyaratkan bahwa tiap-tiap tahap peluang yang memenuhi kendala tidak melebihi nilai tertentu yang diberikan sebelumnya atas ekspektasi matematika pada fungsi dari divergensi di dalam kondisi yang dibatasi oleh bilangan yang diberikan atau nilai dari fungsi pada parameter acak yang direalisasikan pada tahap sebelumnya. Persoalan dinamik akan memiliki salah satu bentuk yaitu : tidak dapat dikondisikan, kondisi probabilitas atau kendala statistik. Untuk persoalan dinamik dengan kendala tidak dapat dikondisikan, karateristik keputusan adalah membuat pada basis informasi mengenai distribusi yang dikombinasikan oleh parameter acak dari kondisi pada semua tahap. Pada persoalan dinamik dengan kondisi dua kasus kendala dapat dibedakan menjadi : (a) momen pembuatan keputusan hanya realisasi dari parameter acak pada tahap sebelumnya yang diperkirakan diketahui dan (b) momen pembuatan keputusan melengkapi informasi yang tersedia mengenai realisasi parameter acak
13 yang dinyatakan dengan tahapan, tetapi nilai dari parameter acak pada tahapan berurutan tidak diketahui. Penyelesaian optimal untuk persoalan program stokastik dinamik dapat diperoleh dengan strategi murni atau campuran. Pada komponen kasus akhir dari penyelesaian atau karateristik statistic dari distibusi yang memberikan penyelesaian akan bergantung pada nilai parameter acak di dalam kondisi persoalan, yang direalisasikan oleh momen pembuatan keputusan Untuk perhitungan selanjutnya dalam analisis persoalan program stokastik tahap ganda, didefinisikan konsep yang diberikan berikut ini. Andaikan terdapat tahap ke-i yaitu Ωi , i = 0, 1, . . . , n untuk beberapa ruang kejadian elementer ωi , dimana Ωi berisi satu elemen Ω0 . Andaikan Ωk adalah descartian product Ωi , i = 1, 2, . . . , k : ω k = (ω1 , . . . , ωk ); Ωn = Ω dan andaikan pada Ω diberikan ukuran probabilistic p yang didefinisikan dengan cara : jika A ⊂ Ωk maka pk (A) = p(A × Ωk+1 × · · · × Ωn ). Diperkenalkan ruang probabilistic (Ω, Σ, P ) dengan Σ berkaitan dengan σ-algebra, definisikan Pk sebagai kondisi ukuran probabilistik pada Ωk Pk (A|ω k−1 ∈ B) =
Pk (A × B) Pk (Ωk × B)
Untuk sembarang A ⊂ Ωk , B ⊂ Ωk−1 X k dinyatakan sebagai descartian product Xi , untuk setiap i = 1, 2, . . . , k dan X k = (xi , . . . , xk ) ∈ X k , X k ∼ X dimana X0 , X1 , . . . , Xn adalah barisan himpunan dari struktur sembarang X k ∈ χk , k = 0, 1, . . . , n dan himpunan X termasuk satu titik X0 .
14 Andaikan mk diberikan sebagai fungsi vektor pada ϕk (ω k , X k ) berdimensi untuk setiap ω k ∈ Ωk , X k ∈ X k , k = 1, 2, . . . , n dan juga untuk setiap ω ∈ Ω pada himpunan X fungsi ϕ0 (ω n , X n ). Masukkan himpunan acak G0k = G0k (ω k ) dan bk (ω k−1 )mk fungsi vektor Bk dinyatakan sebagai ruang Banach yang termasuk P pada fungsi vektor berdimensi bk (ω k ) ki=1 mi . Akhirnya, Eωk (U (ω k )|ω k−1 ) menyatakan kondisi ekspektasi matematika U (ω k ) dibawah perkiraan realisasi ω k−1 yang diketahui. Andaikan dibahas model berbeda pada persoalan program stokastik tahap ganda dengan menggunakan notasi yang diperkenalkan diatas. Andaikan terdapat persoalan program stokastik tahap ganda: Eϕ0 = (ω n , X n ) → inf
(2.15)
Eϕ0 = (ω k , X k ) ≥ bk
(2.16)
X k ∈ Gk , k = 1, 2, . . . , n
(2.17)
Untuk memformulasikan persoalan secara lengkap, diperlukan titik luar apabila kendala yang tidak dapat dikondisikan atau kondisional, apakah penyelesaian persoalan ditentukan dengan strategi murni atau strategi campuran, dan didalam kelas fungsi yang terukur atau distribusi yang akan mendapatkan penyelesaian. Persoalan praktisnya akan bergantung pada makna isi, penyelesaian pada tiaptiap tahap dapat dihitung sebagai vektor deterministic atau sebagai rule-function pada penyelesaian dari realisasi dan parameter acak yang diobservasi dari kondisi, atau sebagai distribusi menentukan distribusi kontinu Xk dengan perkiraan informasi yang diperlukan mengenai nilai yang direalisasikan data initial acak yang diperoleh model konkrit untuk persoalan dan struktur informasinya ditentukan
15 oleh keputusan selanjutnya. Didalam syarat-syarat yang diajukan oleh Ermolyev (1970), hasil-hasil persoalan stokastik tahap ganda dari rangkaian tipe. - Pengamatan - keputusan - pengamatan - · · · - keputusan Keputusan - pengamatan - keputusan - · · · - keputusan Andaikan dibahas bermacam-macam model persoalan program stokastik tahap ganda yang menggunakan klasifikasi yang diberikan oleh Judin (1972). Persoalan stokastik tahap ganda dengan kendala yang tidak dapat dikondisikan adalah Z
ϕn (ω n , X n )dFωn ,X n→inf
(2.18)
ϕk (ω k , X k )dFωk ,X k
(2.19)
X k ∈ Gk , k = 1, 2, . . . , n
(2.20)
Ωn ×X n
Z
Ωk X k
Pemilihan beberapa kelas yang paling menarik untuk aplikasi dari sejumlah struktur informasi yang merupakan persyaratan persoalan program tahap ganda dengan kendala kondisional. Model kongkrit dari (2.15)-(2.17) pada kasus persoalan dengan kendala kondisional, diselesaikan dengan strategi campuran adalah: Z ϕ0 (ω n , X n )dFωn ,X n→inf (2.21) n n Ω ×X Z ϕk (ω k , X k )dFωk |ω dFωk |ωk−1 ≥ bk (ω k−1 ) (2.22) Ωk X k
X k ∈ Gk (ω k ), k = 1, 2, . . . , n
(2.23)
Penyelesaian persoalan akan menjadi himpunan fungsi distribusi FX k|ωk . Biasanya untuk mengatakan persoalan diselesaikan dengan distribusi yang ditentukan kemudian jika FX k|ωk didefinisikan setelah realisasi dan pengamatan parameter acak ω k , distribusi yang ditentukan kemudian bergantung pada X k−1 dan
16 ω k . Dikatakan bahwa persoalan yang diselesaikan dengan distribusi yang ditentukan sebelumnya, jika FX k|ωk didefinisikan setelah realisasi dan pengamatan X k−1 tetapi sebelum pengamatan ω k , distribusi yang ditentukan sebelumnya bergantung pada X k−1 dan ω k−1 . Jika persoalan tahap ganda dengan kendala kondisional diselesaikan dengan strategi murni, model konkrit (2.15)-(2.17) akan menjadi Z Z
ϕ(ω n , X n )dFωn→inf
(2.24)
ϕk (ω k , X k )dFωk |ωk−1 ≥ bk (ω k−1
(2.25)
X k ∈ Gk (ω k ), k = 1, 2, . . . , n
(2.26)
Ωn ×X n
Ωk X k
Fungsi Xk dari parameter acak yang direalisasikan dan diamati pada kondisi dari persoalan penyelesaian. Persoalan diselesaikan dengan aturan yang ditentukan kemudian jika keputusan dibuat setelah realisasi dan pengamatan ω k . Aturan-aturan yang ditentukan kemudian untuk penyelesaian sedemikian hingga X k = X k (ω k ). Dikatakan bahwa persoalan diselesaikan dengan aturan yang ditentukan sebelumnya jika keputusan dibuat setelah realisasi dan pengamatan ω k−1 , tetapi sebelum pengamatan ω k . Pada kasus aturan sebelumnya: X k = X k = (ω k−1 )
Biasanya, persoalan (2.21)-(2.23) atau (2.24)-(2.26) dikenal sebagai persoalan stokastik tahap ganda dengan rigid model, jika kondisi (2.22) atau (2.25) tidak dihadirkan, keputusan tiap-tiap tahap dibuat setelah observasi kondisi dan keputusan pada tahap sebelumnya.
17 Relasi tertentu yang dimiliki antara determinasi domain untuk persoalan dengan kendala yang tidak dapat dikondisikan dan kendala yang dapat dikondisikan. Pernyataan berikut akan menggeneralisasi hasil yang diperoleh, yang telah dikerjakan oleh Eisner (1971) untuk persoalan stokastik tahap ganda parsial linear. Pernyataan yang berikut diambil dari Judin (1974) Andaikan U adalah himpunan penyelesaian yang layak untuk persoalan stokastik tahap ganda dengan kendala yang tidak dapat dikondisikan U = {X k ∈ Gi × · · · × Gn |Eϕk (ω k , X k ) ≥ bk , k = 1, 2, ×, n} Dan V [bn (ω n−1 ] adalah himpunan penyelesaian (aturan penyelesaian, distribusi sebelum atau sesudah penyelesaian) pada persoalan dengan kendala kondisional.
Teorema 2 Himpunan U dan V adalah terhubung oleh relasi U = {X k ∈ V [˜bn (ω n−1 )]|E˜bk (ω n−1 ) = bk , k = 1, 2, ×, n}
Bukti : V˜ = {X k ∈ V [˜bn (ω n−1 )]|E˜bk (ω n−1 ) = bk , k = 1, 2, ×, n}. Andaikan X n ∈ V˜ . Yang menyatakan bahwa Eωkϕk (ω k , X k ) = Eωk−1 {Eωkϕk (ω k , X k )|omegak−1 } ≥ Eωk−1 ˜bk (ω k−1 ) = bk ; k = 1, 2, . . . , n Karena X n ∈ U . Andaikan X n ∈ U , didefinisikan ˜bk (ω k−1 ) = Eωk {ωk (ω k , X k )|ω k−1 + bk E kϕk (ω k , X k )} ω ≤ Eωk {ωk (ω k , X k )|ω k−1 , k = 1, 2, . . . , n}
18 Dengan definisi ˜bk (ω n−1 ) didapatkan Eωk1 ˜bk (ω k−1 ). Sehingga X n ∈ V˜ .
Akibat. Dengan fungsi sama ϕk (ω k , X k ) dan himpunan Gk , k = 1, 2, . . . , n domain penyelesaian layak dari persoalan (2.18)-(2.20) dan (2.21)-(2.23) atau (2.24)(2.26) (bergantung pada persoalan yang diselesaikan dengan strategi campuran atau strategi murni) bersamaan bentuknya jika dan hanya jika Ebk (ω k−1 ) = bk . Pernyataan diatas menyebabkan kemungkinan untuk memformulasi ulang hasil kualitatif dan seringkali juga menghitung metode yang dikerjakan untuk persoalan kelas lain. Relasi antara distribusi penyelesaian dan aturan penyelesaian sangat menarik. Jika fungsi ϕ0 adalah konveks dan komponen fungsi vektor ϕk adalah konkaf pada X dengan tiap-tiap ω, maka nilai optimal dari fungsi objektif yang dicapai pada distribusi penyelesaian dapat dicapai juga dengan aturan penyelesaian. Konveksitas dari ω0 dan ωk tidak menghabiskan kondisi dengan strategi optimal murni dan strategi campuran yang didefinisikan menyatu dan nilai sama dari fungsi tujuan. Nilai fungsi tujuan untuk aturan optimal sebelumnya pada persoalan stokastik tahap ganda di dalam rigid model dengan nilai fungsi tujuan didistribusi penyelesaian optimal sebelumnya. Pernyataan lebih tegas untuk aturan penyelesaian sesudahnya dan distribusi penyelesaian diberikan berikut.
Teorema 3 (a). Andaikan ukuran probabilistik Fω didalam Ω = Ωn adalah kontinu (b) andaikan terdapat fungsi positif G(ω) dan Gk (ω k ) berkendala atas menurut module ϕ0(ω n , X n ) dan semua komponen ϕk (ω k , X k ). Maka penyelesaian aturan
19 optimal sesudahnya untuk persoalan stokastik tahap ganda didefinisikan oleh nilai yang sama pada fungsi tujuan sebagai distribusi penyelesaian optimal sesudahnya.
Teorema 2.3 untuk persoalan stokastik satu tahap telah dibuktikan oleh Judin (1972). Persoalan program stokastik tahap ganda dengan kendala kondisional dapat didistribusikan untuk system persamaan yang memenuhi pemisahan tahapan. Andaikan akan dibahas persoalan (2.24)-(2.26) yang diselesaikan dengan strategi murni ( dengan penyelesaian sebelum aturan penyelesaian sesudahnya ) Untuk definisi domain pada persoalan tahap ke-I berkaitan dengan himpunan: Ki ={Xi ∈ G0 |∃{yi+1 ∈ G0i+1 , . . . , yn ∈ G0n }} Eωi [ϕi (ω i , X i )|wi−1 ] ≥ bi (ω i−1 ) Eωi+s [ϕi (ω
i+s
I
, X , yi+1,...,yi+s )|w
(2.27) i+s−1
]
≥ bi+s (ω i+s−1 ) Jika ∀ωi+s−1 , . . . , ω n−1 , s = 1, 2, . . . , n − i G0i menyatakan proyeksi Gi terhadap hyper-plane dari koordinat yang didefinisikan oleh komponen vektor Xi . Persyaratan keberadaan dari vektor yi+s , s = 1, 2, . . . , n − i yang memenuhi kondisi (2.27) adalah ekivalen terhadap keberadaan kendala di dalam persoalan dua tahap. Kondisi cukup dan perlu untuk menyelesaikan persoalan (2.24)-(2.26) adalah kondisi Ki 6= Φ (fungsi objektif (2.24) dengan asumsi berkendala). Jika disamping K1 6= Φ, Ki 6= Φ, i = 1, 2, 3, . . . , n.
20 Fungsi tujuan dari persoalan Qi (Xi ) pada tahap ke i mengatakan kondisional ekspektasi matematika ϕ0 (ω n , X n ) pada asumsi senua tahapan sebelum tahap ke i, himpunan ω i−1 merupakan parameter yang direalisasikan dengan kondisi persoalan dan komponen keputusan himpunan X i−1 , dan sesudah tahapan ke i ∗ , . . . , Xn∗ keputusan optimal berikutnya : Xi+1
Qi (Xi ) = Eωn |ω n , X i−1 , Xi , Xi+1 , . . . , Xnk
(2.28)
Sejauh ini, definisi penyelesaian aturan optimal pada tahap ke i dari persoalan stokastik tahap ganda direduksi untuk menyelesaikan persoalan program matematika berikut inf Qi(Xi )
(2.29)
Xi ∈Xi
Aturan sesudahnya untuk penyelesaian adalah : Xi = Xi (ω i ), yi+s ; s = 1, 2, . . . , n − i, dan aturan sebelumnya untuk penyelesaian adalah: Xi = Xi (ω i−1 ; yi+s (ω i+s−1 ); s = 1, 2, . . . , n − i
Jika fungsi tujuan dapat dipisahkan, yaitu ϕ0(ω n , X n ) =
Pn
j=1
ϕ0 (ω j , X j )
kita mempunyai Qi(Xi ) = Eωi |ωi−1 {ϕ0 (ω i , X i ) + Q∗i+1 (ω i , X i )} Dimana Q∗i+1 (ω i−1 , X i−1 )} = inf Eωi |ωi−1 {ϕ0(ω i , X i ) + Q∗i+1 (ω i , X i )}, i = 1, 2, . . . , n − 1 Xi ∈Ki
Dengan i = n Q∗n (ω n−1 , X n−1 ) = inf Eωi |ωi−1 {ϕ0n (ω n , X n ) Xi ∈Ki
21 Analog dengan persoalan pemisahan tahapan untuk persoalan stokastik tahap ganda dengan strategi campuran yang dikonstruksikan.
2.4 Metode Pendekatan Rata-rata Sampel ( PRS ) Suatu sampel ξ 1 , . . . , ξ N dari N realisasi vektor acak dibentuk dan akibatnya ekspektasi fungsi nilai E [Q (x, ξ (ω))] diestimasi oleh fungsi rata-rata sampel P n N −1 N n=1 Q(x, ξ ). Aproksimasi rata-rata sampel yang diperoleh ) ( N X min gˆN (x) := cT x + N −1 Q(x, ξ n ) (2.30) x∈X
n=1
vˆN dan x ˆN masing-masing menyatakan nilai optimal dan penyelesaian optimal problem PRS (1.1) dan v ∗ serta x∗ masing-masing menyatakan nilai optimal dan penyelesaian optimal problem awal . Hal penting yang perlu diperhatikan adalah:
i. Apakah vˆN dan x ˆN konvergen terhadap mitranya V ∗ dan X ∗ apabila ukuran sampel N dinaikkan. ii. Jika ya, dapat dianalisis lagi konvergensi, dan karena itu diestimasikan ukuran sampel yang diperlukan memperoleh optimal sebenarnya. iii. Adalah pendekatan optimisasi yang efisien untuk menyelesaikan problem PRS dengan ukuran sampel yang diinginkan. iv. Perhatikan bahwa untuk N yang diketahui penyelesaian x ˆN adalah layak dan merupakan calon untuk penyelesaian optimal terhadap problem awal. Apakah dapat diberikan informasi tentang kualitas dari calon penyelesaian ini.
22 Pertanyaan-pertanyaan diatas telah terjawab untuk program linier stokastik dua-tahap, yaitu apabila peubah tahap pertama dan kedua dalam dan kontinu. Telah dibuktikan bahwa untuk program linier stokastik dengan sebaran diskrit, suatu penyelesaian optimal dari PRS memberikan penyelesaian optimal eksak dari problem awal dengan peluang mendekati satu secara eksponensial apabila N bertambah oleh (Shapiro and Homem-de-Mello, 2001). Uji statistik untuk memvalidasi calon penyelesaian yang didasarkan pada gap optimalitas Norkin et al. (1998) demikian pula syarat optimalitas (Shapiro end Homen de Mello, 1998) telah diajukan. Lebih lanjut lagi, teknik sampling ini telah diintegrasikan dengan algoritma dekomposisi untuk menyelesaikan program linier stokastik dari berbagai ukuran dengan hasil yang cukup akurat Linderoth et al. (2002). Konvergensi dari pendekatan PRS telah juga diperluas untuk program stokastik dengan himpunan keputusan tahap pertama diskrit dan berhingga Kleywegt et al. (2001).
BAB 3 PENGEMBANGAN RATA-RATA SAMPEL
Pada bagian ini dibicarakan sifat konvergensi dari estimastor PRS, terutama yang diterapkan pada program dua tahap dengan recourse integer . Untuk memakai hasil klasik, seperti Hukum Bilangan Besar, perlu diandaikan bahwa sampel yang dibentuk bersebaran bebas identik (bbi). Namun perlu diperhatikan bahwa sifat konvergensi dapat diturunkan terhadap kondisi lebih luas. Disini diajukan algoritma Branch and Bound untuk program stokastik integer dua tahap dengan sebaran diskrit peubah integer campuran ditahap pertama dan peubah integer murni di tahap kedua. Konsep dari algoritma ini adalah mengidentifikasi calon penyelesaian dengan berturut-turut mempartisipasi ruang pencarian.
3.1 Tahap Pertama Diskrit Metode konvergensi PRS dalam Kleywegt et al. (2001) apabila diterapkan pada program stokastik dengan himpunan keputusan tahap pertama yang berhingga. Perhatikan program stokastik dua-tahap dengan karateristik berikut:
i. Himpunan keputusan tahap-pertama X berhingga (tapi mungkin sangat besar) ii. Fungsi recourse Q(x, ·) adalah terukur dan E[Q(x, ξ(ω))] adalah berhingga 23
24 untuk setiap x ∈ X.
Dimana v ∗ dan vˆN , masing-masing menyatakan nilai optimal dari problem ˆ ε menyaawal dan problem PRS. Kemudian untuk ε ≥ 0, andaikan X ε dan X N takan himpunan penyelesaian ε optimal, masing-masing dari problem awal dan ˆ N dari PRS. Khususnya untuk ε = 0 himpunan ini menjadi himpunan X ∗ dan X penyelesaian optimal problem terkait. Dapat diperlihatkan bahwa, dengan asumsi (i) dan (ii) diatas, vˆN merupakan estimator konsisten dari v ∗, yaitu vˆN konvergen dengan peluang satu terhadap v ∗ jika N → ∞. Juga dengan memakai teori Deviasi besar, diperlihatkan dalam Kleywegt, et al. (2001) bahwa untuk setiap ε ≥ 0 dan δ ∈ [0, ε] terdapat konstanta γ(δ, ε) ≥ 0, sehingga ˆ Nδ ⊂ X ε ≤ |X}e−N γ(δ,ε) 1−P X
(3.1)
Kemudian, dengan pengandaian tambahan (yang selalu berlaku dalam kasus dimana sebaran ξ(ε) mempunyai support berhingga), konstanta γ(δ, ε) positif, dan untuk δ dan ξ kecil dapat diestimasi sebagai γ(δ, ε) ≥
(ε∗ − δ)2 (ε − δ)2 ≥ 3σ 2 3σ 2
(3.2)
Dengan ε∗ := minx∈X|X εg g(x) − v ∗danσ 2 adalah variansi maksimal dari selisih tertentu antara nilai fungsi objektif problem PRS. Perhatikan bahwa, karena himpunan X berhingga, ε∗ selalu lebih besar daripada ε, dan akibatnya γ(δ, ε) ≥ 0, bahkan jika δ = ε. Secara khusus, untuk δ = ε = 0, pertidaksamaan (3.1) memberikan laju eksponensial konvergensi dari peluang kejadian {ˆ xN ∈ X ∗ } adalah satu, untuk setiap pilihan nilai optimal x ˆN dari problem PRS.
25 Begitupun, untuk daerah layak X besar (tapi berhingga) selisih ε∗ − ε cenderung kecil. Estimasi ruas kanan dari (3.2) mengakibatkan estimasi ukuran sampel N = N (ε, δ, α) yang diperlukan untuk menyelesaikan problem awal (nilai ekspektasi) dengan peluang 1 − α dan presisi ε > 0 dengan menyelesaikan problem PRS untuk presisi δ ∈ [0, ε). 3δ 2 N≥ log (ε − δ)2
|X| α
(3.3)
Walaupun batasan di atas biasanya terlalu konservatif untuk dipakai dalam perhitungan ukuran sampel, ia memperlihatkan ketergantungan logaritma dari N (ε, δ, α) pada ukuran |X| dari problem tahap pertama. Hasil diatas tidak membuat asumsi berkenaan dengan peubah recourse. Jadi analisis di atas secara langsung terpakai pada program stokastik dua-tahap dengan recourse cacah asalkan himpunan keputusan layak tahap-pertama berhingga.
3.2 Tahap Pertama Kontinu Hasil konvergen tadi dapat disesuaikan yang berkaitan dengan kasus dimana beberapa atau semua peubah dapat mengambil nilai kontinu. Perhatikan bahwa dua norm sembarang pada ruang berdimensi berhingga Rn1 adalah ekivalen untuk alasan teknis bentuk kxk := max {|x1| , . . . , |xn1 |} dapat dipakai. Andaikan himpunan X terbatas (tidak perlu berhingga) dari Rn1 . Untuk suatu v > 0 diketahui, pandang himpunan bagian berhingga Xv dari X sehingga untuk setiap x ∈ X terdapat x0 ∈ Xv yang memenuhi kx − x0 k ≤ v. Jika D diameter dari himpunan X, n maka himpunan Xv demikian dapat dibentuk dengan |Xv | ≤ Dv 1 . Dengan menciutkan himpunan layak X ke himpunan bagiannya Xv , sebagai konsekuensi dari
26 (6) diperoleh estimasi berikut tentang ukuran sampel, yang dikehendaki untuk menyelesaikan problem tereduksi dengan akurasi ε0 > δ 3δ 2 N≥ 0 (ε − δ)2
D n1 log − log α v
(3.4)
Kemudian andaikan bahwa fungsi ekspektasi g(x) Lipschitz kontinu pada X modulus L. Maka suatu penyelesaian ε0-optimal dari problem tereduksi merupakan penyelesaian ε0 -optimal dari problem (1), dengan ε = ε0 + Lv. Buat v := (ε − δ)/2L dan ε0 = ε − Lv = ε − (ε − δ)/2. Pergunakan (2.4) diperoleh estimasi ukuran sampel N yang diperlukan untuk menyelesaikan problem (1.1). 12δ 2 N≥ (ε − δ)2
2DL − log α n1 log ε−δ
(3.5)
Estimasi (3.5) ini memperlihatkan bahwa ukuran sampel yang diperlukan untuk menyelesaikan problem (1) dengan peluang 1 − α dan akurasi ε > 0 setelah menyelesaikan problem PRS dengan akurasi δ < ε, tumbuh secara linier dalam dimensi n, dari tahap pertama problem. Estimasi (3.5) terpakai langsung pada program stokastik dua-tahap dengan integer recourse asalkan ekspektasi nilai fungsi g(x) Lipschitz kontinu. Diperlihatkan dalam Schultz (1995) bahwa dalam kasus program dua-tahap dengan integer recourse nilai fungsi ekspektasi g(x) adalah Lipschitz kontinu pada suatu himpunan kompak jika vektor data acak ξ(ω) mempunyai sebaran kontinu dan beberapa syarat lunak tambahan dipenuhi. Sebaliknya, jika ξ(ω) mempunyai sebaran diskrit maka g(x) tidak kontinu.
27 3.3 Tahap Pertama Kontinu dan Sebaran Diskrit Program stokastik dua-tahap dengan integer recourse apabila vektor data acak bersebaran diskrit dengan dukungan berhingga. Diperlihatkan bahwa dalam hal demikian problem awal dan PRS dapat diformulasikan secara ekivalen sebagai problem pada daerah layak berhingga. Dengan asumsi berikut: (A1). Sebaran dari vektor data acak ξ(ω) mempunyai dukungan berhingga Ξ = {ξ1 , . . . , ξK } dengan peluang masing-masing p1 , . . . , pK setiap realisasi ξk = (qk , Tk , W, hk ), k = 1, . . . , K) dari ξ(ω) disebut skenario. P Maka nilai ekspektasi E[Q(x, ξ(ω))] sama dengan K k=1 pk Q(x, ξk ), jadi problem awal (1.1) dapat ditulis berikut: (
min g(x) := cT x + x∈X
K X
pk Q(x, ξk )
)
(3.6)
k=1
disini Q(x, ξk ) := inf qkT y : W y ≥ hk − Tk x y∈Y
(3.7)
dengan X ⊆
28 yang wajar. Tahap pertama Integer-campuran dapat diatasi dalam kerangka berikut tanpa kesulitan konseptual. Tambahan (A1)−(A3) juga diandaikan. (A4). Q(x, ξk ) berhingga ∀ x ∈ X dan k = 1, . . . , K (A5). Matriks kendala tahap-kedua integer, yaitu W ∈ Z m2 ×n2 .
Asumsi (A4) berarti bahwa Q(x, ξk ) < +∞ dan Q(x, ξk ) > −∞ dan k = 1, . . . , K. Yang pertama dari dua pertidaksamaan ini dikenal sebagai sifat recourse relatif lengkap Wets (1996 ) karena X kompak, recourse relatif lengkap selalu dapat dicapai dengan menambahkan penalti peubah antifisial pada problem tahap kedua. Asumsi (A5) dapat dipenuhi dengan pemberian skala yang sesuai apabila elemen matriks rasional. Pada asumsi (A3) diperoleh bahwa, untuk setiap ξ ∈ EQ(·, ξ) merupakan nilai fungsi optimal dari program integer murni dan dikenal sebagai konstan perbagian yaitu, untuk setiap Z ∈ Z n2 dan ξ ∈ E fungsi Q(·, ξ) konstan pada himpunan Schultz et al. (1998 ) C(z, ξ) := {x ∈
(3.8)
dengan notasi ” ≤ ” dan ” ≤ ” terpakai per komponen. Maka akibatnya unPK tuk setiap z ∈ Z n2 fungsi k=1 pk Q (·, ξk ) konstan pada himpunan C (z) := ∩K k=1 C (z, ξk ). Perhatikan bahwa C(z) daerah polihedral yang tidak terbuka ataupun tertutup sekarang, andaikan: Z := {z ∈ Z m2 : C (z) ∩ X 6=⊆ φ}
Karena X terbatas oleh asumsi (A2), himpunan Z berhingga diperoleh bahwa himpunan X dapat disajikan sebagai gabungan sejumlah berhingga himpunan polihedral C(z) ∩ X, z ∈ Z. Pada setiap himpunan C(z) ∩ X ekspektasi
29 nilai fungsi g(x) adalah linier dan nilai optimal dicapai pada suatu titik ekstrim (verteks) dari C(z) ∩ X. Defenisikan V :=
[
vert(C(z) ∩ X)
(3.9)
z∈Z
dengan vert (S) menyatakan himpunan verteks polihedral S. Perhatikan bahwa X adalah polihedral oleh defenisi, jadi dari keberhinggaan Z aktuality himpunan V berhingga . Telah diperlihatkan Schultz et al. (1998) bahwa terhadap asumsi problem (3.6) memiliki penyelesaian optimal x∗ ∈ V . Dari hasil ini, maka (3.6) dapat dinyatakan sehingga program stokastik dua-tahap berikut dengan keputusan tahap-pertama berhingga: (
min g(x) = cT x + x∈V
K X
pk Q(x, ξk )
)
(3.10)
k=1
Diajukan dalam Schultz et al. (1998) untuk menyelesaikan (3.10) dengan mengenumerasi himpunan berhingga V . Bagaimana mengestimasi |V |. Dari (3.8) jelas bahwa himpunan Z mencakup semua vektor integer z, sehingga untuk hk fix, komponen ke j dari z, yaitu zj mengambil nilai bhkj − Tj xc untuk semua x ∈ X. Perlihatkan x := {x ∈ <m2 : x = Tx , x ∈ X} dan andaikan D diameter x. Perhatikan karena x kompak, X juga kompak, jadi D ≤ ∞. Maka, untuk suatu hk fix, zj dapat menjadi bila paling banyak D + 1 nilai. Jika sekarang, diperhatikan semua K skenario, zj dapat mengambil k(d + 1) nilai yang mungkin. Akibatnya, dapat dibatasi kardinalitas dari Z sebagai |Z| ≤ [K(D + 1)]m2 . Sekarang perhatikan untuk sembarang z ∈ Z, sistem cl (C (z)) = x ∈
30 dengan h = mink {hk } dan ¯h = maxk {hk }, operasi maks dan min perbagian. Dengan mengandaikan bahwa X = {x ∈
(3.11)
Jadi kardinalitas dari V , demikian pula usaha yang dibutuhkan dalam mengevaluasi calon penyelesaian x ∈ V . Sebagian besar tergantung pada K. Dengan memakai pendekatan PRS konsiderasi terhadap semua skenario {ξ1 , . . . , ξK } dalam dapat dihindari. Pandang sampel {ξ 1 , . . . , ξ N } dari parameter tak pasti problem, dengan ukuran sampel N jauh lebih kecil daripada K. Maka problem PRS yang terkait dengan (3.10) adalah: ( min
x∈Vn
gˆN (x)
N 1 X T =c x+ Q(x, ξ n ) N n=1
)
(3.12)
Dengan VN sampel mitra dari himpunan V yaitu, Vn := ∪z∈ZN vert(CN (z) ∩ X)
(3.13)
n m2 : CN (z) ∩ x 6= φ} PerDengan CN (z) := ∩N n−1 C (z, ξ ) dan ZN := {z ∈ Z
hatikan bahwa himpunan V dan VN dalam problem (3.10) dan (3.12) tidak sama,
31 himpunan ini masing-masing dinyatakan oleh himpunan Ξ dan himpunan bagian yang disampel dari Ξ. Tidak secara langsung jelas apakah penyelesaian (3.12) termasuk dalam hmpunan calon penyelesaian optimal V . Untungnya, karena vektor yang disampel membentuk himpunan bagian dari Ξ, akibatnya Vn ⊂ V . Jadi sembarang penyelesaian untuk (3.12) merupakan calon penyelesaian optimal terhadap problem awal. Sekarang dapat secara langsung diterapkan hasil konvergensi eksponensial dari (4.10) terhadap program stokastik dengan recourse integer dan peubah tahap- pertama kontinu. Secara khusus pertidaksamaan (3.1) menjadi ˆ δ ⊂ X ε ≤ |V |e−N γ(δ,ε) 1−P X N
(3.14)
ˆ δ adalah himpunan penyelesaian secara δDimana, seperti sebelumnya X N optimal terhadap problem PRS, X ε adalah himpunan penyelesaian ε-optimal terkadang problem awal, dan konstanta γ(δ, ξ) dapat diestimasi menggunakan (3.2). Dengan memakai (3.14) dan estimasi dari |V | dalam (3.11) dapat ditentukan ukuran sampel untuk problem PRS yang menjamin suatu penyelesaian ε-optimal terhadap problem awal dengan peluang 1 − α sebagai berikut. N≥
3δ 2 (m2 log[K(D + 1)]) + (m1 + 2m2 )(n1 + m1 + 2m2 ) − log α) (3.15) (ε − δ)2
Walaupun estimasi ukuran sampel N ini terlalu konservatif untuk tujuan praktis, ia memperlihatkan bahwa N berkembang secara linier terhadap dimensi problem dan secara logarithmically terhadap jumlah skenario K. Ini mengidentifikasikan bahwa dapat diperoleh penyelesaian cukup akurat terhadap problem yang mencakup sejumlah besar skenario dengan memakai ukuran sampel sedikit. Sekarang perhatikan situasi dimana sebaran sebenarnya dari ξ(ω) kontinu sedangkan sejumlah berhingga skenario diperoleh dengan diskritisari fungsi se-
32 baran ini. Jika diskritisari demikian cukup baik, maka perbedaan antara nilai ekspektasi terkait dari fungsi objektif kecil, yaitu andaikan η batasan konstan nilai mutlak dari perbedaan antara nilai-nilai ekspektasi Q(x, ξ(ω)), yang diambil terhadap sebaran diskrit dan kontinu dari ξ(ω), untuk semua x ∈ X. Akibatnya jika x ¯ merupakan penyelesaian ε-optimal dari problem nilai ekspektasi terhadap salah satu sebaran ini, maka x ¯ merupakan penyelesaian (ε + 2η-optimal dari problem nilai ekspektasi terhadap sebaran lainnya. Karena itu , jika fungsi nilai ekspektasi yang diambil terhadap sebaran kontinu, adalah kontinu Lipschitz pada X, maka estimasi (3.4) dapat diaplikasikan terhadap problema dengan sebaran terdiskritisari yang disesuaikan untuk konstanta yang terkait.
3.4 Menyelesaikan Problem PRS Secara prinsip teknik enumerasi Schultz et al. (1998) dapat dipakai untuk menyelesaikan problem PRS (3.12). Namun umumnya sangat sulit untuk mengkarakterisasi himpunan VN kecuali problem tahap-kedua memiliki struktur sangat sederhana, tambahan lagi kardinalitas V∞ sangat besar, sehingga enumerasi tidak dimungkinkan secara komputasi. Alternatifnya, dapat dicoba untuk menyelesaikan deterministik ekivalen dari (3.12) dengan memakai algoritma branch and bound. Namun, teknik demikian tidak mencoba untuk mengeksplotasi struktur yang dapat teruraikan dari problem, dan metode ini akan gagal kecuali ukuran sampel kecil. Dekomposisi berbaris algoritma Branch and Bound yang dihentangkan dalam Ahmed et al. (2000) untuk menyelesaikan problem PRS. Disamping mengkarakterisasi himpunan calon penyelesaian Vn , algoritma ini mengidentifikasi calon penyelesaian dengan berturut-turut mempartisi ruang pencarian.
33 Lebih lanjut lagi, algoritma memanfaatkan informasi batas bawah untuk mengeliminasi bagian daerah pencarian sehingga mencegah enumerasi lengkap. Karena algoritma tidak secara eksplisit menelusuri Vn , harus dipastikan bahwa penyelesaian akhir yang diperoleh tidak termasuk dalam himpunan ini untuk mencapai konvergensi. Berikut ini diuraikan algoritma sebagai penambahan terhadap asumsi (A1)− (A5 ), algoritma mengandaikan (A6) matriks teknologi T , yang mengaitkan problem tahap pertama dan kedua adalah deterministik, yaitu Tk = T untuk semua k. Perlihatkan transformasi linier dari peubah problem tahap pertama x dengan memakai T oleh x := Tx. Peubah x dikenal sebagai peubah lunak dalam literatur program stokastik. Ide prinsip dibelakang algoritma adalah memandang problem PRS dalam peubah lunak. n o ˆ N (χ) ˆ N (χ) := Φ(χ) + Ψ min G
(3.16)
χ∈χ
dimana ˆ N (χ) = N −1 Φ := inf {c x : T x = χ}, Ψ T
x∈X
N X
Ψ)N (χ, ξ j n)
n=1
Ψ(χ, ξ) := inf q T y : W y ≥ h − χ y∈Y
dan X := {X ∈ <m2 : X = Tx, x ∈ X} X memiliki dimensi lebih kecil dari pada x. Lebih penting lagi, transformasi ini memberikan struktur tertentu terhadap fungsi diskontinu ΨN (·). Khususnya, dapat diperlihatkan Ahmed et al. (2000) bahwa ΨN : <m2 → < mempunyai sifat berikut:
34 i. Ia tak naik sepanjang setiap komponen Xj , j = 1, . . . , m2 dari X. ii. Untuk setiap z ∈ Z m1 , ia konstan pada himpunan CN (z) := {X : hn − z − 1 ≤ X ≤ hn − z, n = 1, . . . , N }
Perhatikan bahwa himpunan CN (z)-dikaitkan dengan himpunan CN (z) oleh transformasikan X = Tx. Juga perhatikan baku CN (z) adalah hiper-empat persegi karena ia merupakan perkalian kartesian dari interval. Jadi, fungsi nilai ekspektasi tahap kedua ΨN (·) konstan perbagian pada daerah empat persegi dalam ruang peubah lunak X. Maka diskontinuitas dari ΨN (·) hanya dapat terletak di batas daerah-daerah ini dan, karena itu, semua ortogonal pada sumbu peubah lebih lanjut lagi, karena X kompak, maka X juga kompak. Jadi daerah demikian dalam himpunan layak problem berhingga. Algoritma mengeksploitasi sifat structural di atas dengan mempartisi ruang Qm2 [lj , uj ), dimana uj merupakan komponen ke χ menjadi daerah berbentuk j=1 j dari suatu titik χ pada mana fungsi nilai tahap kedua ϕ(·) diskontinu. Perhatikan bahwa ϕˆN (·) hanya dapat diskontinu di suatu titik χ dimana sekurangkurangnya satu dari komponen vector hn − χ merupakan integral untuk beberapa n = 1, . . . , N . Jadi dipartisi ruang pencarian sepanjang nilai χ demikian.
35 Dibawah ini diberikan pernyataan formal dari algoritma branch and bound. Notasi: L i P αi βi χi U L χ∗
Daftar subproblem Nomor iterasi; juga dipakai untuk mengindikatorkan subproblem terpilih Partisi yang berkaitan dengan i Batas atas yang diperoleh di iterasi i Batas bawah pada subproblem i Penyelesaian layak untuk nilai subproblem Batas atas pada nilai optimal global Batas bawah pada nilai optimal global Calon optimum global
Algoritma Inisialisasi Proses problem dengan membentuk hiper-persegi berbentuk P 0 :=
Qm1
0 0 j=1 [lj , uj )
ˆ N (χ) dengan kendala χ ∈ χ ∩ P 0 sehingga χ ⊂ P 0. Tambahkan problem min G untuk mendaftarkan subproblem terbuka L. Buat U ← +∞ dan penghitung iterasi i ← 0.
Iterasi i: Langkah i.1 : Jika =∅, berhenti dengan penyelesaian χ∗, jika tidak, pilih subˆ N (χ) dengan kendala χ ∈ χ ∩ P 0 problem i, yang didefinisikan sehingga min G dari subproblem saat ini. Buat L ← L\{i}.
ˆ N (χ) : χ ∈ Langkah i.2 : Problem batas bawah β i yang memenuhi β I ≤ inf{G χ ∩ P i }. Jika ξ ∩ P i = ∅, β i = +∞. Tentukan penyelesaian layak ξ i ∈ χ dan ˆ N (χi ). hitung batas atas αi ≥ G
36
Langkah i.2.a : Buat L → minl∈L∪{i} β l. Langkah i.2.b : Jika αi < U , maka χ∗ ← χi dan U ← αi . Langkah i.2.c : Hentikan daftar subproblem, yaitu L ← L\{l : β l ≥ U }. Jika β i ≥ U pergi ke langkah i.1 dan pilih subproblem lain.
Langkah i.3 : Partisi P i menjadi P i1 dan P i2 . Buat L ← L{i1 , i2} yaitu perˆ N (χ) kendala ˆ N (χ) kendala χ ∈ χ ∩ P i1 dan dari G soalan kedua subproblem dari G χ ∈ χ ∩ P i2 ke daftar subproblem terbuka. Untuk tujuan pemilihan β i1 , β i2 ← β i. Buat i ← i + 1 dan kembali ke langkah i.1
BAB 4 KESIMPULAN
Dalam penelitian ini dikembangkan metode pendekatan rata-rata sampel untuk program stokastik dua tahap. Penyelesaian persoalan program stokastik dua tahap berisi vector deterministik. Pada tahap pertama, dibuat penyelesaian persoalan rencana awal deterministik. Pembentukan rencana awal deterministik dilakukan sebelum kondisi acak dari persoalan ditentukan. Pada tahap kedua digunakan sebuah vector acak pada persoalan yang sesuai untuk merencanakan kompensasi divergensi, spesifikasi parameter. Dua kesulitan dalam menyelesaikan program stokastik adalah:
1. Evaluasi eksak dari ekspektasi biaya recourse. 2. Mengoptimalkan Ekspektasi biaya recourse.
Algoritma Branch and Bound untuk menyelesaikan problem PRS. Algoritma Branch and Bound juga mengkaraterisasi himpunan calon penyelesaian dan mengidentifikasi calon penyelesaian dengan berturut-turut mempartisi ruang pencarian. Algoritma memanfaatkan informasi batas bawah untuk mengeliminasi bagian daerah pencarian. Karena algoritma tidak secara eksplisit menelusuri himpunan calon penyelesaian dipastikan bahwa penyelesaian akhir yang diperoleh tidak termasuk dalam himpunan ini untuk mencapai konvergensi.
37
DAFTAR PUSTAKA
Ahmed, S. (2000). Strategic Planning under Uncertainty:Stochastic Integer Programming Approaches. Ph.D. Thesis, University of Illinois at UrbanaChampaign. Ahmed, S., Tawarmalani, M., and Sahinidis, N.V. (2000). A ?nite branch and bound algorithm for two stage stochastic integer programs. Submitted for publication. E-print available in the Stochastic Programming E-Print Series:http://dochost.rz.hu-berlin.de/speps/. Bienstock, D., and Shapiro, J.F. (1998). Optimizing resource acquisition decisions by stochastic programming. Management Science, 34:215229. Birge, J.R. and Dempster, M.A.H. (1996). Stochastic programming approaches to stochastic scheduling. Journal of Global Optimization, 9(3-4):417451. Birge, J.R., dan Louveaux, F. (1997). Introduction to Stochastic Programming. Spinger-Verlag, New York. Birge, J.R., and Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York, NY. Care, C.C., and Schultz, R. (1999). Dual Decomposition in Stochastic Integer Programming. Operation Research Letters 24, 37-45. Caroe, C.C., Ruszczynski, A., and Schultz, R. (1997). Unit commitment under uncertainty via two-stage stochastic programming. In Proceedings of NOAS 97,Caroeet al.(eds.), Department of Computer Science, University of Copenhagen, pages 2130. Caroe, C.C. (1998). Decomposition in stochastic integer programming. PhD thesis, University of Copenhagen. Engell, S., Mrkert, A., Sand, G., and Schultz, R. (2004). Aggregated Scheduling of a Multiproduct Bacth Plant by Two-Stage Stochastic Integer Programming. Optimazation and Engineering 5, 335-359 Ermolyev, J.M.(1970). Stochastic Quasi-Gradient Methods and Applications, Ph.D. in Institute of Cybernetics Ukrainian S.S.R. Academy of Sciences,Kiec. Eisner, M.J., Kaplan, R.S., dan Soden,. J.V. (1971). Admissible Rules for the EModel of Chance-Constrained Programming, Management Sci., No. 17. Judin, D.B. (1972). Multi-Stage Planning Problems under Risk and Uncertainty, Technologi Cybernetics. No.6 Kall, P., and Wallace, S.W. (1994). Stochastic Programming. John Wiley and Sons, Chichester, England.
38
39 Kleywegt, A. J., Shapiro, A., and Homem-De-Mello,T. (2001). The sample average approximation method for stochastic discrete optimization. SIAM Journal of Optimization, 12:479502. Laporte, G., Louveaux, F.V., and Van Hamme, L. (1994). Exact solution of a stochastic location problem by an integer L-shaped algorithm. Transportation Science, 28(2):95103. Linderoth, J., Shapiro, S., and Wright, S. (2002). The empirical behavior of sampling methods for stochastic programming. Optimization Technical Report 02-01, Computer Sciences Department, University of Wisconsin-Madison. Mak, W.K., Morton, D.P., and Wood, R.K. (1999). Monte Carlo bounding techniques for determining solution quality in stochastic programs. Operations Research Letters, 24:475. Norkin, V.I., P?ug, Ch., and Ruszczynski, A. (1998). A branch and bound method for stochastic global optimization. Mathematical Programming, 83:425450. Norkin, V.I., P?ug, G.C., and Ruszczynski, A. (1998). A branch and bound method for stochastic global optimization. Mathematical Programming, 83:425450. Norkin, V.I., Ermoliev, Y.M., and Ruszczynski,A. (1998). On optimal allocation of indivisibles under uncertainty. Operations Research, 46:381395. Sahinidis, N.V. (2004). Optimization Under Uncertainty : state-of- the-art and opportunities. Computers and Chemical Enginneering 28, 971 983. Schultz, R. (1995). On structure and stability in stochastic programs with random technology matrixand complete integer recourse. Mathematical Programming, 70(1):7389. Schultz, R. (1996). Rates of convergence in stochastic programs with complete integer recourse. SIAM J. Optimization, 6(4):11381152. Schultz, R., Stougie,L., and Van der Vlerk,M.H. (1998). Solving stochastic programs with integer recourse by enumeration: A framework using Grobner basis reductions. Mathematical Programming, 83:229252 Shapiro, A., and Homem de Mello,T. (1998). A simulation-based approach to two stage stochastic programming with recourse. Mathematical Programming, 81(3, Ser. A):301325. Shapiro,A., and Homem-de-Mello,T. (2001). On rate of convergence of Monte Carlo approximations of stochastic programs. SIAM Journal on Optimization,11:7086. Tayur, S.R., Thomas, R.R., and Natraj, N.R. (1995). An algebraic geometry algorithm for scheduling in the presence of setups and correlated demands. Mathematical Programming, 69(3):369401.
40 Tiil, J., Sand, G., Engell, S., Emmerich, M., and Schnemann, L. (2005). A Hybrid Algorithm for Solving Two-Stage Stochastic Integer Programming by Combining Evo;utionary Algorithms and Mathematical Programming Methods. Volume 20A of Computer-Aided Chemcal Engineering, Amsterdam, Elsevier 187-192. Verweij, B., Ahmed, S., Kleywegt, A.J., Nemhauser, G., and Shapiro, A. (2001). The sample average approximation method applied to stochastic routing problems: A computational study. Submitted for publication. Wets,R.J-B. (1966). Programming under uncertainty: The solution set. SIAM Journal on Applied Mathematics, 14:1143 1151.
