1.1 METODE PENGEMBANGAN PENDEKATAN RATA- RATA SAMPEL UNTUK PROGRAM STOKASTIK DUA TAHAP. Faridawaty Marpaung. Abstrak

METODE PENGEMBANGAN PENDEKATAN RATA- RATA SAMPEL UNTUK PROGRAM STOKASTIK DUA TAHAP Faridawaty Marpaung Abstrak Penelitian ini mengemukakan metode pengembangan pendekatan rata –rata sampel untuk program stokastik dua tahap. Metodologi ini menggunakan rata–rata program stokastik melalui sampel, dan pemecahan rata–rata 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 Kata kunci : Rata – rata sampel, program stokastik dua tahap

A. PENDAHULUAN 1.

Latar Belakang

Program stokastik adalah merupakan

selanjutnya,

program matematika, dimana beberapa

pengawasan operasi dapat berbentuk

data yang termuat pada tujuan atau

pilihan, pada biaya pasti, nilai tahap

kendala mengandung ketidakpastian yang

kedua atau peubah recourse. Tujuan

dicirikan oleh distribusi peluang pada

deterministik keputusan tahap pertama

parameter. Dalam persoalan program

sedemikian hingga jumlah biaya tahap

stokastik

pertama dan ekspektasi biaya recourse

adalah

membuat

sebuah

desain

atau

perbaikan

keputusan sekarang dan meminimumkan

minimum.

biaya

program stokastik dua tahap sebagai

rata-rata

harapan

sebagai

konsekuensi dari keputusan, paradigma ini dikenal sebagai Peubah

keputusan

Formulasi standar dari

berikut :

model recourse. problem

program

1.1

stokastik dua-tahap dipartisi menjadi dua himpunan.

Peubah

tahap

pertama

ditentukan sebelum melakukan realisasi

Kendala

parameter tak pasti. Kemudian, satu kejadian acak yang muncul sendiri, 84 Faridawaty Marpaung adalah Dosen Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Medan

adalah keputusan antisipatif

Disini dianalisis laju konvergensi dari

tahap pertama yang diambil sebelum

Pendekatan Rata–rata Sampel (PRS)

peubah acak teramati dan

untuk

dengan

program

stokastik

dengan

recourse cacah.

1.2 merupakan

nilai

optimal

dan

2.

Perumusan Masalah

Untuk menentukan

1.1

pada

 : q, T ,W , h menyatakan vektor dari

persamaan

parameter

dilakukan sehingga dilakukan pendekatan

problem

tahap

kedua.

Penelitian ini berkaitan dengan program

secara eksak

sulit

yang baik bagi

stokastik dua tahap dengan recourse fix, yaitu matriks W adalah tertentu (bukan acak)

dan

peubah

dipersyaratkan cacah, yaitu

recourse

3.

Y  Z n2

Penelitian

Diperlihatkan dalam Schultz, R. (1995) sumber

ini

mengembangkan

dalam (1.2).

dua

Tujuan Penelitian

kesulitan

dalam

bertujuan metode

untuk

pendekatan

rata-rata sampel untuk program stokastik dua tahap.

menyelesaikan program stokastik dengan recourse cacah adalah :

4.

1. Evaluasi eksak dari ekspektasi

Program stokastik dua tahap berisi vektor deterministik.

biaya recourse. 2. Mengoptimalkan

Metodologi Penelitian

Ekspektasi

Pada

tahap

pertama

penyelesaian persoalan rencana awal deterministik akan dibuat. Pembentukan

biaya recourse Dalam pendekatan yang diajukan, fungsi ekspektasi biaya recourse dalam 1.1

rencana awal deterministik dilakukan sebelum kondisi acak dari persoalan ditentukan. Sebuah vector acak pada

diganti oleh pendekatan rata-rata sampel

penyelesaian

persoalan

yang

dan

digunakan

untuk

merencanakan

kompensasi

divergensi,

problem

optimisasi

terkait

diselesaikan dengan memakai algoritma

sesuai

spesifikasi

khusus untuk optimisasi tak konveks. 85 Faridawaty Marpaung adalah Dosen Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Medan

parameter dari persoalan akan muncul pada tahap kedua. Selanjutnya juga dibahas metode Pendekatan Rata-rata Sampel (PRS) tahap

yang digunakan pada

pertama

bertujuan

untuk

mengestimasi ekspektasi fungsi nilai

EQ x,   

Pada bagian akhir dibahas Algoritma Branch and Bound yang mengeksploitasi sifat struktural dengan mempartisi ruang pencarian sepanjang harga

oleh fungsi rata-rata

sampel N 1 n1 Q( x,  n ) . N

B. TINJAUAN PUSTAKA

1.

Metode Pendekatan Rata – rata

Hal penting yang perlu diperhatikan

Sampel

adalah :

( 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

N 1 n1 Q( x,  n ) . aproksimasi rata – N

Apakah

vˆ N dan

terhadap mitranya

xˆ N

konvergen

v * dan

x*

apabila ukuran sampel N dinaikkan ii. Jika

ya,

konvergensi,

dapat

dianalisis

lagi

karena

itu

dan

diestimasikan ukuran sampel yang

rata sampel yang diperoleh N   min  gˆ N ( x) : c T x  N 1  Q ( x,  n )  xX n 1  

i.

diperlukan (2.1)

memperoleh

optimal

sebenarnya. iii. Adalah pendekatan optimisasi yang

vˆ N

xˆ N

dan

menyatakan

masing – masing nilai

optimal

dan

penyelesaian optimal problem PRS (1.1) ; dan

v

*

menyatakan

serta

x

*

nilai

masing – masing optimal

dan

penyelesaian optimal problem awal 1.1 .

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 86

Faridawaty Marpaung adalah Dosen Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Medan

problem

awal.

Apakah

dapat

statistik

untuk

memvalidasi

calon

diberikan informasi tentang kualitas

penyelesaian yang didasarkan pada gap

dari calon penyelesaian ini.

optimalitas

al.

(1998)

Pertanyaan – pertanyaan diatas telah

demikian pula syarat optimalitas

(

terjawab untuk program linier stokastik

Shapiro end Homen de Mello, 1998 )

dua – tahap, yaitu apabila peubah tahap

telah diajukan. Lebih lanjut lagi, teknik

pertama dan kedua dalam 1.1 dan 1.2

sampling ini telah diintegrasikan dengan

kontinu. Telah dibuktikan bahwa untuk

algoritma

program linier stokastik dengan sebaran

menyelesaikan program linier stokastik

diskrit, suatu penyelesaian optimal dari

dari berbagai ukuran dengan hasil yang

PRS memberikan penyelesaian optimal

cukup akurat Linderoth et al. (2002).

eksak dari problem awal dengan peluang

Konvergensi dari pendekatan PRS telah

mendekati

juga diperluas untuk program stokastik

satu

secara

eksponensial

apabila N bertambah oleh and

Homem-de-Mello,

(Shapiro

2001

).

Uji

dengan

Norkin

et

dekomposisi

himpunan

untuk

keputusan

tahap

pertama diskrit dan berhingga Kleywegt et al. (2001).

C.

PEMBAHASAN DAN HASIL

Pada

bagian

konvergensi

ini dari

dibicarakan

sifat

estimastor

PRS,

dan peubah integer murni di tahap kedua. Konsep

dari

terutama yang diterapkan pada program

mengidentifikasi

dua tahap dengan recourse integer .

dengan

Untuk memakai hasil klasik, seperti

ruang pencarian.

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

1.

algoritma

ini

calon

berturut-turut

adalah

penyelesaian mempartisipasi

Tahap Pertama Diskrit

Metode

konvergensi

Kleywegt

et

diterapkan dengan

al.

pada

himpunan

PRS

(2001 program

dalam

)

apabila stokastik

keputusan

tahap

pertama yang berhingga.

integer dua tahap dengan sebaran diskrit

Perhatikan program stokastik dua – tahap

peubah integer campuran ditahap pertama

1.1 dengan karateristik berikut : 87


i. Himpunan keputusan tahap – pertama

berhingga

X

mungkin

sangat besar )

Qx,. terukur

ii. Fungsi recourse dan

(tapi

E | Q ( x,  ( ))}

berhingga

untuk setiap x  X Dimana v * dan vˆ N , masing – masing menyatakan nilai optimal dari problem awal dan problem PRS. Kemudian untuk ε  0, andaikan X



Xˆ N

dan

Kemudian,

dengan

tambahan

pengandaian

( yang selalu berlaku dalam

kasus dimana sebaran    mempunyai berhingga ), konstanta   ,  

support

positif, dan untuk  dan  kecil dapat diestimasi sebagai

 ( ,  ) 

( *   ) 2 (   ) 2  3 2 3 2

(3.2)



Dengan  * : min xX | X g g ( x)  v * dan  2

optimal, masing – masing dari problem

dan  2 adalah variansi maksimal dari

menyatakan himpunan penyelesaian

awal dan PRS. Khususnya untuk   0 *

selisih tertentu antara nilai fungsi objektif

himpunan ini menjadi himpunan X dan

problem PRS. Perhatikan bahwa, karena

Xˆ N dari penyelesaian optimal problem

himpunan X berhingga,  * selalu lebih

terkait.

besar daripada

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

  ,    0 , bahkan jika    . Secara khusus,

Kleywegt, et al. (2001) bahwa

untuk

  0 dan   0,   terdapat

setiap

konstanta   ,    0

memberikan laju

eksponensial konvergensi dari peluang kejadian

xˆ

N

X*



adalah satu, untuk

setiap pilihan nilai optimal

xˆ N dari

problem PRS. Begitupun, untuk daerah layak X besar (

tapi

berhingga

)

selisih

* 

cenderung kecil. Estimasi ruas kanan dari

sheingga



   0,

untuk

pertidaksamaan (3.1)

*

teori Deviasi besar, diperlihatkan dalam

 , dan akibatnya

(3.2)



1  P Xˆ N  X  | X }e  N ( , )

(3.1)

mengakibatkan estimasi ukuran

sampel N  N  ,  ,   yang diperlukan untuk menyelesaika problem ‘awal’ (nilai 88


ekspektasi ) dengan peluang 1   dan

  0 dengan menyelesaikan

presisi

problem PRS untuk presisi   0,   . N

   2



dapat

Andaikan himpunan X terbatas ( tidak

v0

diketahui,

pandang

x  X terdapat

untuk setiap

yang memenuhi

konservatif

diameter dari himpunan

dipakai

ukuran

dalam

sampel,

ia

memperlihatkan

ketergantungan

logarithma dari

N  ,  ,   pada ukuran

himpunan dengan

X , maka

X v demikian dapat dibentuk

 v

Xv  D

n1

.

menciutkan himpunan layak

X dari problem tahap pertama.

himpunan

x' X v

x  x'  v . Jika D

Walaupun batasan di atas biasanya terlalu perhitungan

himpunan

bagian berhingga X v dari X sehingga

(3.3)

untuk

dipakai.

perlu berhingga ) dari R n1 . Untuk suatu

 X   log    

3 2



x : max x1 ,..., x n1

bagiannya

Xv,

Dengan X

ke

sebagai

Hasil diatas tidak membuat asumsi

konsekuensi dari (6) diperoleh estimasi

berkenaan dengan peubah recourse. Jadi

berikut tentang ukuran sampel, yang

analisis di atas secara langsung terpakai

dikehendaki

pada program stokastik dua – tahap

problem tereduksi dengan

dengan recourse cacah asalkan himpunan

' 

keputusan

layak

tahap

–

menyelesaikan akurasi

pertama

berhingga.

N

3 2  D   n1 log  log   (    ) 2  v 

Kemudian 2.

untuk

andaikan

bahwa

(3.4) fungsi

ekspektasi g  x  Lipschitz kontinu pada

Tahap Pertama Kontinu

Hasil konvergen tadi dapat disesuaikan

X modulus L . Maka suatu penyelesaian

yang berkaitan dengan kasus dimana

 ' - optimal dari problem tereduksi

beberapa atau semua peubah dapat

merupakan penyelesaian  ' - optimal dari

mengambil nilai kontinu. Perhatikan

problem (1), dengan

bahwa dua norm sembarang pada ruang

v :     2 L

berdimensi

berhingga

R

n1

adalah

ekivalen untuk alasan teknis bentuk

   ' Lv . Buat dan

 '    Lv        2 .

89 Faridawaty Marpaung adalah Dosen Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Medan

N

bersebaran

12 2  2 DL   log   (3.5)  n1 log (   ) 2    

diskrit

dengan

dukungan

berhingga. Diperlihatkan bahwa dalam

Estimasi (3.5) ini memperlihatkan bahwa

hal demikian problem awal dan PRS

ukuran sampel yang diperlukan untuk

dapat diformulasikan secara ekivalen

menyelesaikan

sebagai problem pada daerah layak

problem

(1)

dengan

peluang 1   dan akurasi   0 setelah

berhingga.

menyelesaikan problem PRS dengan

Dengan asumsi berikut :

akurasi

   , tumbuh secara linier

dalam dimensi n , dari tahap pertama

 A1  . Sebaran dari vektor data acak   

problem.

mempunyai

Estimasi (3.5)

terpakai langsung pada

program stokastik dua – tahap dengan integer recourse asalkan ekspektasi nilai

g x

fungsi

Diperlihatkan

Lipschitz

dalam

kontinu.

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

dukungan

berhingga

Ξ = {ξ1,. .. , ξK } dengan peluang masing –

p1 ,..., p K

masing

setiap

realisasi

 k  q k , Tk ,W , hk , k  1,..., K dari    disebut skenario. Maka nilai ekspektasi sama dengan



K k 1

jadi problem awal

E[Q ( x,  ( ))]

pk Q( x,  k ) ,

1.1

dapat ditulis

berikut : K   min  g ( x) : cT x   pk Q( x,  k )  (3.6) xX k 1  

lunak tambahan dipenuhi. Sebaliknya, jika

   mempunyai sebaran diskrit

maka g  x  tidak kontinu.

disini





Q ( x,  k ) : inf qkT y : Wy  hk  Tk x (3.7) yY

dengan X   n1 , c   n1 , Y   n2 , 3.

Tahap

Pertama

Kontinu

dan

Sebaran Diskrit Program stokastik dua – tahap dengan

W   n1 , dan untuk semua

k , q k   n2 , Tk   m2 xn1 dan hk   m2

integer recourse apabila vektor data acak 90 Faridawaty Marpaung adalah Dosen Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Medan

Dalam beberapa aplikasi jumlah total

sebagai sifat recourse relatif lengkap

skenario

Wets (1996 ) karena

K sangat besar , membuat

jumlah

recourse relatif lengkap selalu dapat

pk Q( x,  k ) tidaklah mungkin. Ini

dicapai dengan menambahkan penalti

evaluasi



K k 1

tepat

memotivasi

dari

kebutuhan

pendekatan

berbaris sampling untuk menyelesaikan

peubah antifisial pada problem tahap

 A5 

kedua. Asumsi

dapat dipenuhi

dengan pemberian skala yang sesuai

(3.6).

 A2  . Peubah tahap pertama kontinu, dan himpunan kendala

X

tidak kosong,

kompak dan polihedral.

 A3  .

kompak,

X

apabila elemen matriks rasional. Pada asumsi

 A3 

setiap

  EQ.,   merupakan nilai

diperoleh bahwa, untuk

fungsi optimal dari program integer

Peubah tahap kedua yang integer

murni ,yaitu Y  Z n2 dalam 1.2

murni dan dikenal sebagai konstan Z  Z n2

perbagian yaitu, untuk setiap

dan   E fungsi Q.,   konstan pada

Perhatikan bahwa asumsi peubah tahap

himpunan Schultz et al. (1998 )

pertama kontinu merupakan hal yang wajar. Tahap pertama Integer campuran dapat diatasi dalam kerangka berikut tanpa kesulitan konseptual. Tambahan

 A1    A3  juga diandaikan.

 A4  .



dengan notasi "" dan "" terpakai per komponen. Maka akibatnya untuk

z  Z n2 fungsi

setiap

Q x,  k  berhingga x  X dan



C ( z,  ) : x   n1 : h  z  1  Tx  h  z (3.8)

konstan



K k 1

pada

p k Q.,  k  himpunan

k  1,..., K

C  z  :  kK1 C  z ,  k  . Perhatikan bahwa

 A5  .

Cz 

Matriks kendala tahap – kedua

integer, yaitu

W  Z m2 xn2

Asumsi

 A4 

Q x,  k   

dan

daerah

terbuka

polihedral

ataupun

tertutup

yang

tidak

sekarang,



andaikan Z : z  Z m2 : C z   X  

berarti

bahwa

Q x,  k   

x  X dan k  1,..., K . Yang pertama dari dua pertidaksamaan ini dikenal

Karena

X terbatas oleh asumsi



 A2  ,

himpunan Z berhingga diperoleh bahwa himpunan

X

dapat disajikan sebagai

gabungan sejumlah berhingga himpunan 91


polihedral

C z   X ,

setiap himpunan

z  Z . Pada

C z   X

ekspektasi

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 )

untuk

semua x  X .



Perlihatkan x : x   m2 : x  Tx , x  X



dan andaikan D diameter x . Perhatikan D   . Maka, untuk suatu

(3.9)

h k fix,

z j dapat menjadi bila paling banyak

dengan vert (S) menyatakan himpunan verteks polihedral S. Perhatikan bahwa X adalah polihedral oleh defenisi , jadi

keberhinggaan

himpunan

h kj  T j x 

karena x kompak, X juga kompak, jadi

zZ

dari

z j mengambil nilai

V

aktuality

Z

berhingga

.

Telah

diperlihatkan Schultz et al. (1998) bahwa

D  1 nilai. Jika sekarang, diperhatikan

semua

K

mengambil mungkin.

skenario,

zj

dapat

K D  1

nilai

yang

Akibatnya,

dapat

dibatasi

dari

Z

sebagai

kardinalitas

terhadap asumsi problem (3.6) memiliki

| Z | [ K ( D  1)]m2 . Sekarang perhatikan

penyelesaian optimal x *  V . Dari hasil

untuk sembarang z  Z , sistem

ini, maka (3.6)

dapat dinyatakan

sehingga program stokastik dua – tahap berikut

dengan

keputusan

tahap

–





cl C  z   x   n1 : x  0, Tx  h k  z, Tx  h k  z  1, k





 x   n1 : x  0, Tx  h  z , Tx  h  z  1

pertama berhingga : K   min  g ( x)  cT x   pk Q( x,  k )  xV k 1  

(3.10)

 

h  min k h k

dengan

dan

 

Diajukan dalam Schultz et al. (1998)

h  max k h k , operasi maks dan min

untuk menyelesaikan

perbagian. Dengan mengandaikan bahwa

(3.10)

dengan





mengenumerasi himpunan berhingga V .

X  x   n1 : Ax  b, x  0 dimana

Bagaimana mengestimasi V . Dari (3.8)

matriks

jelas bahwa himpunan

Z mencakup

m1 xn1 ,

terdapat

A

untuk

sembarang z  Z ,

semua vektor integer z , sehingga untuk h k fix, komponen ke j dari

z , yaitu





clC  z   X  x  n1 : Ax  b, x  0, Tx  h  z, Tx  h  z  1


Sistem diatas terdefenisi paling banyak untuk

(3.13)

Vn :  zZ N vert(C N ( z )  X )

n1  m1  2m2 , pertidaksamaan

linier ( termasuk non – negativitas ), jadi paling banyak memiliki



C N  z  :  nN1 C z ,  n

Dengan



Z N : z  Z m2 : C N z   x  



dan



 n1  m1  2m2  m1  2 m2    (n1  m1  2m2 ) n1  

Perhatikan bahwa himpunan V dan V N

Titik ekstrim. Jadi diperoleh batas atas

sama, himpunan ini masing – masing

dalam problem 3.10 dan 3.12 tidak

| V | [ K ( D  1)] ( n1  m1  2m2 )

(3.11)

m1  2 m2

Tidak secara langsung jelas apakah penyelesaian (3.12)

Jadi kardinalitas dari V , demikian pula yang

dan

himpunan bagian yang disampel dari  .

m2

usaha



dinyatakan oleh himpunan

kardinalitas dari V , yaitu

dibutuhkan

dalam

mengevaluasi calon penyelesaian x  V . Sebagian besar tergantung pada

K.

termasuk dalam

himpunan calon penyelesaian optimal

V . Untungnya, karena vektor yang disampel membentuk himpunan bagian  , akibatnya

dari

Vn  V . Jadi

PRS

sembarang penyelesaian untuk (3.12)

konsiderasi terhadap semua skenario

merupakan calon penyelesaian optimal

1 ,...,  K 

terhadap problem awal. Sekarang dapat

Dengan

Pandang

memakai dalam

pendekatan dapat



sampel

1

dihindari.

,...,  N



dari

parameter tak pasti problem, dengan ukuran sampel

N jauh lebih kecil

daripada K . Maka problem PRS yang terkait dengan (3.10) adalah : 1  min  gˆ N ( x )  cT x  xVn N 

N

 Q ( x,  n 1

n

 ) 

secara

langsung

hasil

konvergensi eksponensial dari (4.10) terhadap

program

recourse

integer

pertama

kontinu.

pertidaksamaan (3.12)

diterapkan



stokastik

dengan

dan peubah Secara

tahap khusus

(3.1) menjadi



1  P Xˆ N  X  | V | e  N ( , )

(3.14)

Dimana, seperti sebelumnya Xˆ N adalah Dengan V N sampel mitra dari himpunan

himpunan

V yaitu,

 - optimal terhadap problem PRS, X 

penyelesaian

secara 93


-

ekspektasi terkait dari fungsi objektif

optimal terkadang problem awal, dan

kecil, yaitu andaikan  batasan konstan

  ,   dapat diestimasi

nilai mutlak dari perbedaan antara nilai –

adalah himpunan penyelesaian konstanta menggunakan (3.14)

3.2

Dengan memakai

nilai ekspektasi Q x,    , yang diambil

V

terhadap sebaran diskrit dan kontinu dari

dan estimasi dari

dalam

(3.11) dapat ditentukan ukuran sampel

   , untuk semua

untuk problem PRS yang menjamin suatu

jika

penyelesaian

-

x merupakan penyelesaian

 - optimal terhadap

optimal dari problem nilai ekspektasi

1

terhadap salah satu sebaran ini, maka x

problem awal dengan peluang

merupakan

sebagai berikut . N

x  X . Akibatnya

  2  -

penyelesaian

optimal dari problem nilai ekspektasi

3 2 (m2 log[ K ( D  1)])  (m1  2m2 )(n1  m1  2m2 )  log  ) (   )2

terhadap sebaran lainnya. Karena itu ,

(3.15)

jika fungsi nilai ekspektasi yang diambil

Walaupun estimasi ukuran sampel N ini

terhadap sebaran kontinu, adalah kontinu

terlalu konservatif untuk tujuan praktis, ia

Lipschitz pada X , maka estimasi (3.4)

memperlihatkan bahwa N berkembang

dapat diaplikasikan terhadap problema

secara linier terhadap

dengan

problem terhadap

dan

dimensi

secara

jumlah

logarithmically skenario

sebaran

terdiskritisari

yang

disesuaikan untuk konstanta yang terkait.

K.

Ini mengidentifikasikan bahwa dapat diperoleh penyelesaian cukup akurat terhadap

problem

yang

mencakup

sejumlah besar skenario dengan memakai

4.

Menyelesaikan Problem PRS

Secara prinsip teknik enumerasi Schultz et

al.

(1998) dapat

menyelesaikan

ukuran sampel sedikit.

problem

dipakai

untuk

PRS

(3.12).

Namun umumnya sangat sulit untuk Sekarang

perhatikan

situasi

dimana

sebaran ‘sebenarnya’ dari    kontinu

mengkarakterisasi himpunan VN kecuali problem tahap – kedua memiliki struktur

sedangkan sejumlah berhingga skenario

sangat

diperoleh

kardinalitas V sangat besar, sehingga

dengan

diskritisari

fungsi

sebaran ini. Jika diskritisari demikian cukup baik, maka perbedaan antara nilai

sederhana,

tambahan

lagi

enumerasi tidak dimungkinkan secara komputasi. Alternatifnya, dapat dicoba 94


untuk

menyelesaikan

deterministik

ekivalen dari (3.12) dengan memakai

kedua adalah deterministik, yaitu Tk  T untuk semua k

algoritma branch and bound. Namun, teknik demikian tidak mencoba untuk

Perlihatkan

linier

dari

mengeksplotasi

peubah problem tahap pertama

x

struktur

yang

dapat

transformasi

teruraikan dari problem, dan metode ini

dengan memakai

akan gagal kecuali ukuran sampel kecil.

Peubah

Dekomposisi berbaris algoritma Branch

lunak

and Bound

yang dihentangkan dalam

stokastik.

Ahmed et al. (2000) untuk menyelesaikan

algoritma

problem

PRS dalam peubah lunak.

PRS.

mengkarakterisasi penyelesaian mengidentifikasi

Disamping himpunan

Vn ,

calon

algoritma

calon

ini

penyelesaian

dengan berturut – turut mempartisi ruang pencarian. Lebih lanjut lagi , algoritma memanfaatkan informasi batas bawah untuk

mengeliminasi

bagian

daerah

x dikenal sebagai peubah “

dalam Ide

literatur

prinsip

program dibelakang

adalah memandang problem

 





(3.16) dimana





ˆ (  ) : N 1   (  ,  j n) (  ) : inf xX cT x : Tx   ,  N N n 1



N

 (  ,  ) : inf qT y : Wy  h   yY





dan X : X   m2 : X  Tx , x  X

Karena algoritma tidak secara eksplisit menelusuri Vn , harus dipastikan bahwa penyelesaian akhir yang diperoleh tidak termasuk dalam himpunan ini untuk mencapai konvergensi.

“

ˆ ( ) min Gˆ N (  ) :  (  )   N

pencarian sehingga mencegah enumerasi lengkap.

x : Tx .

oleh

T

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)

Berikut ini diuraikan algoritma sebagai

bahwa  N :  m2   mempunyai sifat

penambahan

berikut :

terhadap

 A1    A5  , algoritma  A6 

Matriks

asumsi

mengandaikan

teknologi

T,

yang

mengaitkan problem tahap pertama dan 95 Faridawaty Marpaung adalah Dosen Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Medan

i.

Ia

tak

naik

sepanjang

setiap

komponen X j , j  1,..., m2

dari

Jadi dipartisi ruang pencarian sepanjang nilai

pernyataan formal dari algoritma branch

X

ii. Untuk setiap z  Z m2 , ia konstan pada

himpunan



C N  z  : X : h n  z  1  X  h n  z , n  1,..., N

and bound . Notasi :



Daftar subproblem

Perhatikan bahwa himpunan C N z  dikaitkan dengan himpunan C N z  oleh transformasikan X  Tx . Juga perhatikan baku C N z  adalah hiper – empat persegi karena ia merupakan perkalian kartesian dari interval. Jadi, fungsi nilai ekspektasi  N () konstan perbagian

tahap kedua

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 maka

X

X kompak,

juga kompak. Jadi daerah

demikian dalam himpunan layak problem berhingga. Algoritma

mengeksploitasi

sifat structural di atas dengan mempartisi ruang

demikian. Dibawah ini diberikan

menjadi

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

daerah berbentuk

, dimana komponen ke

Nomor iterasi; juga dipakai untuk

merupakan

dari suatu titik

Inisialisasi

mana fungsi nilai tahap kedua diskontinu. Perhatikan bahwa

Proses

hanya dapat diskontinu di suatu titik dimana sekurang – kurangnya satu dari komponen vector integral untuk beberapa

Algoritma

pada

problem

dengan

hiper-persegi

berbentuk sehingga

merupakan .

membentuk .

Tambahkan problem 96


dengan untuk subproblem terbuka

kendala

mendaftarkan

. Buat

Langkah

i.2.a

:

Buat

dan penghitung iterasi Langkah i.2.b : Jika

Iterasi i:

, maka

dan

Langkah i.1 : Jika

, berhenti

dengan penyelesaian

, jika tidak, pilih

,

subproblem

yang didefinisikan

sehingga

dengan kendala dari subproblem saat ini.

Buat

Langkah

i.2.c

:

Hentikan daftar

subproblem, yaitu Jika

pergi ke langkah

pilih subproblem lain. Langkah i.3 : Partisi dan

Langkah i.2 : Problem batas bawah yang memenuhi Jika . penyelesaian layak

Tentukan dan hitung

dan

menjadi

. Buat

yaitu

persoalan kedua subproblem dari kendala

dan dari

kendala

ke

subproblem

terbuka.

pemilihan dan

Untuk

daftar tujuan

. Buat

kembali

ke

langkah

i.1

batas atas D. KESIMPULAN Dalam penelitian ini dikembangkan metode

pendekatan

rata-rata

sampel

digunakan sebuah vector acak pada persoalan

yang

sesuai

untuk

untuk program stokastik dua tahap.

merencanakan kompensasi divergensi,

Penyelesaian persoalan program stokastik

spesifikasi parameter.

dua tahap berisi vector deterministik . Pada tahap pertama, dibuat penyelesaian persoalan rencana awal deterministik. Pembentukan rencana awal deterministik dilakukan sebelum kondisi acak dari

Dua

kesulitan

dalam

menyelesaikan

program stokastik adalah : 1.

Evaluasi eksak dari ekspektasi biaya recourse .

persoalan ditentukan. Pada tahap kedua 97 Faridawaty Marpaung adalah Dosen Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Medan

2.

Mengoptimalkan Ekspektasi biaya

pencarian.

recourse.

informasi

Algoritma Branch

and Bound

untuk

menyelesaikan problem PRS. Algoritma Branch and Bound juga mengkaraterisasi himpunan

calon

mengidentifikasi

penyelesaian calon

dan

penyelesaian

dengan berturut – turut mempartisi ruang

Algoritma batas

memanfaatkan 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.

DAFTAR PUSTAKA Ahmed, S. (2000). Strategic Planning under Uncertainty:Stochastic Integer Programming Approaches. Ph.D. Thesis, University of Illinois at Urbana-Champaign. Ahmed, S., Tawarmalani, M., and Sahinidis, N.V. (2000). A finite branch and bound algorithm for two stage stochastic integer programs. Submitted for publication. E-print available in the Stochastic Programming EPrint Series:http://dochost.rz.huberlin.de/speps/. 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:479–502. 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. Norkin, V.I., Pflug, Ch., and Ruszczyński, A. (1998). A branch and bound method for stochastic global optimization. Mathematical Programming, 83:425–450. Norkin, V.I., Pflug, G.C., and Ruszczynski, A. (1998). A branch and bound method for stochastic global optimization. Mathematical Programming, 83:425–450. Norkin, V.I., Ermoliev, Y.M., and Ruszczynski,A. (1998). On optimal allocation of indivisibles under uncertainty. Operations Research, 46:381–395. Schultz, R. (1995). On structure and stability in stochastic programs with random technology matrixand complete integer recourse. Mathematical Programming, 70(1):73–89. Schultz, R., Stougie,L., and Vlerk,M.H. (1998).

Van der Solving 98


stochastic programs with integer recourse by enumeration: A framework using Gröbner basis reductions. Mathematical Programming, 83:229–252 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):301–325. Shapiro,A., and Homem-de-Mello,T. (2001). On rate of convergence of Monte Carlo approximations of stochastic programs. SIAM Journal on Optimization,11:70–86. Wets,R.J-B. (1966). Programming under uncertainty: The solution set. SIAM Journal on Applied Mathematics, 14:1143 – 1151.


1.1 METODE PENGEMBANGAN PENDEKATAN RATA- RATA SAMPEL UNTUK PROGRAM STOKASTIK DUA TAHAP. Faridawaty Marpaung. Abstrak

Recommend Documents