Vol. 10, No. 2,  75-82,  Januari  2014
Metode Pengembangan Pendekatan Rata-rata Sampel untuk Menyelesaikan Masalah Program Stokastik Cacah Campuran
Faridawaty Marpaung 1

## Abstrak
Penelitian  ini  mengemukakan  atau  menjelaskan  suatu  strategi  penyelesaian  untuk menyelesaikan  masalah  program  integer  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, dijelaskan teknik statistik dan deterministik bounding untuk validasi kualitas dari sebuah calon penyelesaian optimal .
Kata Kunci : Program Stokastik, optimal.

## 1. Pendahuluan
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 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, dan 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:
1 Jurusan Matematika FMIPA Universitas Negeri Medan, email: farida2008.unim@gmail.com
1,2,3 Jurusan Matematika FMIPA Universitas Hasanuddin Makassar , Jl. Perintis Kemerdekaan Km.10 Makassar

## Faridawaty Marpaung
{ ( ) [ (    ( ))]} (1)
Kendala
dengan adalah  keputusan  antisipatif  tahap  pertama  yang  diambil  sebelum  peubah  acak teramati dan
(    ) { } (2)
merupakan  nilai optimal  dan   h W T q , , , :   menyatakan  vektor  dari parameter problem tahap  kedua. Diandaikan bahwa beberapa (atau semua)  komponen  acak, ditulis     , dan ekspektasi dalam (1) diambil berdasarkan sebaran peluang dari     yang diandaikan diketahui.  Persoalan  (1)  dengan  peubah 1 n R x  ,  membentuk  tahap  pertama  yang  perlu diputuskan  sebelum  realisasi     .  Persoalan  (2)    dengan  peubah 2 n R y  ,  membentuk recourse untuk  keputusan  tahap  pertama  yang  diketahui  dan  realisasi  dari  data  acak. Penelitian    ini  berkaitan  dengan  program  stokastik  dua  tahap  dengan recourse fix,  yaitu matriks W adalah tertentu (bukan acak) dan peubah recourse dipersyaratkan cacah, yaitu 2 n Z Y  dalam (2).
Diperlihatkan  dalam  [7]  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 (1) 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 Rata–rata Sampel (PRS) untuk program stokastik dengan recourse cacah. Untuk  menentukan [ (    ( ))] pada  persamaan (1) secara  eksak  sulit  dilakukan sehingga  dilakukan  pendekatan  yang  baik  bagi [ (    ( ))] .  Penelitian  ini  bertujuan  untuk mengembangkan  metode  pendekatan  rata-rata  sampel  untuk  menentukan  fungsi  biaya recourse dalam  masalah program stokastik cacah campuran.

## 2. Tinjauan Pustaka

## 2.1. Program Stokastik Dua Tahap
Penyelesaian  persoalan  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 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  sistem  kendala  persoalan.  Jika persoalan  program  stokastik  dengan  model  dua  tahap  dapat  diselesaikan  maka  pemilihan  dari rencana  awal  deterministik  akan  menjamin  keberadaan  (ekstensi)  vektor  acak  di  dalam kompensasi untuk sistem yang divergen.
Andaikan terdapat persoalan berikut:
(    ) (3) (4) (5) (6)
dimana:
{ } ( )
( ) ‖ ‖ ‖ ‖
Andaikan elemen dari matriks ( ) , vector ( ) dan ( ) benilai acak.

## 2.2. Metode Pendekatan Rata-rata Sampel
Suatu  sampel
N   ,..., 1 dari N realisasi  vektor  acak    dibentuk,  dan  akibatnya ekspektasi  fungsi  nilai
        , x Q E diestimasi  oleh  fungsi  rata–rata  sampel    N n n x Q N 1 1 ) , (  . Aproksimasi rata–rata sampel yang diperoleh:
            N n n T N X x x Q N x c x g 1 1 ) , ( : ) ( ˆ min  (7)
N v ˆ  dan N x ˆ   masing–masing menyatakan nilai optimal dan penyelesaian optimal problem  PRS (1);  dan * v serta * x masing–masing  menyatakan  nilai  optimal  dan  penyelesaian  optimal problem awal (1).  Hal penting yang perlu diperhatikan adalah:
i. Apakah N v ˆ   dan N x ˆ     konvergen  terhadap  mitranya * v dan * x apabila  ukuran sampel N dinaikkan?
ii. Jika  (i)  terjawab,  maka  lakukan  analisis  konvergensi  dan  estimasi  ukuran  sampel yang diperlukan untuk memperoleh nilai optimal sebenarnya.
iii. Pendekatan  optimisasi  yang  efisien  untuk  menyelesaikan  problem  PRS  dengan ukuran sampel yang diinginkan.
iv. Perhatikan  bahwa  untuk N yang  diketahui  penyelesaian N x ˆ   adalah  layak  dan merupakan calon untuk penyelesaian optimal terhadap problem awal. Apakah dapat diberikan informasi tentang kualitas dari calon penyelesaian ini?
Pertanyaan–pertanyaan  di  atas  telah  terjawab  untuk  program  linier  stokastik  dua  tahap,  yaitu apabila  peubah  tahap  pertama  dan  kedua  dalam  (1)  dan  (2)  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  (lihat  [10]).  Uji  statistik  untuk  memvalidasi  calon

## Faridawaty Marpaung
penyelesaian yang didasarkan pada gap optimalitas menurut Norkin et al. (lihat [5] dan [6]), dan demikian pula syarat optimalitas telah diajukan (lihat [8]). Lebih lanjut lagi, teknik sampling ini telah diintegrasikan dengan algoritma dekomposisi untuk menyelesaikan program linier stokastik dari berbagai ukuran dengan hasil yang cukup akurat (lihat Linderoth et al. [4]). Konvergensi dari pendekatan PRS telah juga diperluas untuk program stokastik dengan himpunan keputusan tahap pertama diskrit dan berhingga  oleh Kleywegt et al. [3].

## 3. Penyelesaikan Problem PRS
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  menyebar  saling  bebas dan  identik.  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 di tahap pertama dan peubah integer murni  di  tahap  kedua.  Konsep  dari  algoritma  ini  adalah  mengidentifikasi  calon  penyelesaian dengan berturut-turut mempartisipasi ruang pencarian.
Secara  prinsip  teknik  enumerasi  Schultz et  al. [8]  dapat  dipakai  untuk  menyelesaikan problem  PRS.  Namun  umumnya  sangat  sulit  untuk  mengkarakterisasi  himpunan N V 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  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. ([1]  dan  [2])  untuk  menyelesaikan problem  PRS.  Di  samping  mengkarakterisasi  himpunan  calon  penyelesaian n V ,  algoritma  ini mengidentifikasi  calon  penyelesaian  dengan  berturut–turut  mempartisi  ruang  pencarian.  Lebih lanjut  lagi,  algoritma  memanfaatkan  informasi  batas bawah  untuk  mengeliminasi  bagian  daerah pencarian  sehingga  mencegah  enumerasi  lengkap.  Karena  algoritma  tidak  secara  eksplisit menelusuri n V , harus dipastikan bahwa penyelesaian akhir yang diperoleh tidak termasuk dalam himpunan ini untuk mencapai konvergensi.
Berikut  ini  diuraikan  algoritma    sebagai  penambahan  terhadap  asumsi     5 1 A A  .
Algoritma  mengandaikan   6 A Matriks teknologi T , yang mengaitkan problem tahap pertama dan kedua adalah deterministik, yaitu T T k  untuk semua k .
Perhatikan  transformasi  linier  dari  peubah  problem  tahap  pertama x dengan  memakai T oleh x T x  : .  Peubah x dikenal  sebagai  peubah    “lunak“    dalam  literatur  program  stokastik.  Ide prinsip dibelakang algoritma  adalah memandang problem PRS dalam peubah lunak.
  ˆ ˆ
min ( ) : ( ) ( ) N N
G           (8)
dimana
  1 1 ˆ ( ) : inf : , ( ) : ( , ) N T j x X N N n c x Tx N n                  ( , ) : inf : T y Y q y Wy h        
dan   X x T X X X x m      , : : 2
X memiliki dimensi lebih kecil dari pada x . Lebih penting lagi, transformasi ini memberikan struktur  tertentu  terhadap  fungsi  diskontinu ( ) N   .  Khususnya,  dapat  diperlihatkan  dalam Ahmed et al. ([1] dan [2]) bahwa     2 : m N mempunyai sifat berikut :
i. Fungsi tak naik sepanjang setiap komponen j X , 2 ,..., 1 m j  dari X ii. Untuk setiap 2 m Z z  , konstan pada himpunan     N n z h X z h X z C n n N ,..., 1 , 1 : :       
Perhatikan  bahwa  himpunan   z C N dikaitkan  dengan  himpunan   z C N oleh transformasikan x T X  .  Juga  perhatikan  baku   z C N adalah  empat  persegi  karena 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 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  struktural  di  atas  dengan  mempartisi  ruang menjadi    daerah  berbentuk ∏ [ ) ,  dimana merupakan  komponen    ke dari suatu titik dimana fungsi nilai tahap kedua ̂ (  ) diskontinu. Perhatikan bahwa ̂ (  ) hanya dapat diskontinu di suatu titik dimana sekurang–kurangnya satu dari komponen vektor merupakan  integral  untuk  beberapa
.  Jadi,  partisi  ruang pencarian sepanjang nilai .
Berikut ini diberikan pernyataan formal dari algoritma Branch and Bound .
Notasi:
Daftar sub problem
Nomor  iterasi;  juga  dipakai  untuk  mengindikatorkan  sub problem terpilih
Partisi yang berkaitan dengan i
Batas atas yang diperoleh di iterasi i
Batas bawah pada sub problem i
Penyelesaian layak untuk nilai sub problem Batas atas pada nilai optimal global Batas bawah pada nilai optimal global Calon optimum global

## Algoritma Inisialisasi
Proses problem dengan membentuk hiper-persegi berbentuk
Faridawaty Marpaung
sehingga . Tambahkan problem dengan  kendala untuk  mendaftarkan  sub  problem terbuka   . Buat dan penghitung iterasi Proses Iterasi. Langkah 1 : Jika , berhenti dengan penyelesaian , jika tidak, pilih sub problem   ,  yang didefinisikan  sehingga dengan  kendala
dari  sub  problem  saat  ini.
Buat . Langkah 2: Problem batas bawah yang memenuhi Jika . Tentukan penyelesaian layak dan hitung batas atas Langkah  2.a: Buat Langkah  2.b: Jika , maka dan Langkah  2.c: Hentikan daftar sub problem, yaitu Jika kembali ke Langkah    dan pilih sub problem lain.
Langkah 3: Partisi menjadi
dan . Buat yaitu persoalan kedua sub problem dari kendala , dan  dari kendala ke daftar  sub  problem  terbuka.  Untuk  tujuan  pemilihan .    Buat dan
kembali  ke Langkah 1.

## 4. Kesimpulan
Dalam  penelitian  ini  dikembangkan  metode  pendekatan rata-rata  sampel  untuk  program stokastik  dua  tahap.  Penyelesaian  persoalan  program  stokastik  dua  tahap  berisi  vektor 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  vektor  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,  maka  dapat  dipastikan  bahwa penyelesaian  akhir  yang  diperoleh  tidak  termasuk  dalam  himpunan  ini  untuk  mencapai konvergensi.

## Daftar Pustaka
[1] Ahmed  S.,  2000.  “Strategic  planning  under  uncertainty:  Stochastic  integer programming approaches ” Ph.D. Thesis . University of Illinois at Urbana-Champaign.
[2] 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/..
[3] 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.
[4] 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.
[5] Norkin  V.I.,  Pﬂug  Ch.,  and  Ruszczynski  A.,  1998.  “A  branch  and  bound  method  for stochastic global optimization”. Mathematical Programming ,  83: 425–450.
[6] Norkin  V.I.,  Ermoliev  Y.M.,  and  Ruszczynski  A.,  1998.  “On  optimal  allocation  of indivisibles under uncertainty” Operations Research , 46: 381–395.
[7] Schultz  R.,  1995.  “On  structure  and  stability  in  stochastic  programs  with  random technology matrixand complete integer recourse”. Mathematical Programming , 70(1): 73– 89.
[8] 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: 229–252.
[9] 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.
[10]  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.