BAB 2 DASAR TEORI. Jaringan komunikasi dapat dipandang sebagai sebuah keterhubungan dari entitasentitas

BAB 2 DASAR TEORI

2.1 Jaringan Komunikasi Jaringan komunikasi dapat dipandang sebagai sebuah keterhubungan dari entitasentitas komunikasi. Entitas komunikasi dapat diartikan sebagai sebuah entitas yang berdiri sendiri dan terlibat dalam sebuah proses komunikasi. Komputer, laptop, dan telepon merupakan contoh dari entitas komunikasi. Sebuah jaringan komunikasi mungkin mengandung komputer, tetapi ini bukan berarti bahwa jaringan komunikasi adalah sama dengan jaringan komputer. Pada hakekatnya, sebuah jaringan komputer hanya salah satu bentuk dari jaringan komunikasi, sebuah jaringan komputer pada dasarnya berarti sebuah keterhubungan dari beberapa komputer. Sedangkan, istilah jaringan komunikasi digunakan dalam arti yang lebih luas. Sekarang ini, dunia bergerak kepada jaringan yang terintegrasi. Telepon, smartTV dan komputer bisa terhubung dengan jaringan yang sama. Oleh karena itu, adalah lebih baik menyatakan jaringan saat ini sebagai sebuah jaringan komunikasi, lebih dari sebuah jaringan komputer.

2.1.1 Topologi Jaringan. Topologi dari sebuah jaringan diartikan sebagai keterhubungan fisik dari elemenelemen jaringan tersebut. Dengan kata lain, topologi dari sebuah jaringan menunjuk kepada cara elemen-elemen jaringan terhubung. Topologi-topologi yang paling umum adalah bus, ring, mesh, dan star (Wibi Hardani, 2004). Bus Topologi bus memiliki bentuk yang serupa dengan arsitektur bus di dalam komputer, yang menghubungkan CPU ke memori utama, ke disk drive, dan berbagai komponen lainnya. Bus merupakan sebuah jalur data sederhana yang terhubung ke semua

Universitas Sumatera Utara

7 perangkat di dalam jaringan, sehingga hanya satu perangkat saja yang dapat menggunakannya pada satu saat tertentu. Ring Secara logika, topologi Ring adalah konfigurasi di mana tiap-tiap terminal hanya dapat mengirimkan data ke terminal tetangga yang berada di posisi sesudahnya, dan menerima data dari terminal tetangga yang berada di posisi sebelumnya. Dengan kata lain, apabila hendak menerima sebuah frame dari terminal tetangga di posisi setelah anda, frame tersebut harus ”berjalan” mengelilingi seluruh cincin, melewati semua terminal yang ada sampai akhirnya sampai kepada anda. Mesh Pada sebuah topology Mesh, Masing-masing node terhubung dengan dua atau lebih node. Ada dua jenis topology Mesh yakni partially connected mesh dan full connected mesh. Pada partially connected mesh, sebuah node mempunyai dua atau lebih tetangga. Untuk full connected mesh, terdapat sebuah link terhubung antara setiap dua node dalam jaringan. Star Dengan konfigurasi star, sebuah perangkat berperan sebagai pusat jaringan dan terhubung ke semua perangkat lainnya, untuk melayani komunikasi di antara perangkatperangkat tersebut. Konfigurasi star atau Bintang seringkali disebut juga sebagai konfigurasi hub and spoke karena bentuknya mirip roda pedalti.

2.1.2 Jenis Jaringan Berdasarkan Luas Daerah yang Diliputi. Topology jaringan berhubungan erat dengan konsep luas jaringan dan pengklasifikasian berdasarkan pada topoloy ini menghasilkan tipe berbeda dari area jaringan (area networks). Alasan untuk hal ini adalah bahwa jaringan menjadi berbeda bentuk dan ukuran. lebih lanjut lagi, luas dari sebuah jaringan mempunyai pengaruh yang signifikan dalam banyak aspek dalam sebuah jaringan. Seperti, faktor bandwidth maksimum dan kecepatan (error rates ). Dua kelas/jenis penting dari area jaringan adalah Local Area Network (LAN)


8 dan Wide Area Network(WAN). sebuah LAN adalah sebuah jaringan yang terbatas pada suatu wilayah kecil. Sebaliknya, WAN mencakup daerah yang sangat luas.

2.1.2.1 Local Area Network (LAN). Sebuah jaringan LAN merupakan sebuah jaringan yang terbatas pada suatu daerah kecil. LANs pada umumnya digunakan pada perusahaan untuk menghubungkan computer, server jaringan, printer dan entitas lainnya dalam jaringan. LAN dicirikan oleh beberapa sifat di bawah ini:

• Mempunyai sebuah diameter (jangkauan) dalam beberapa kilometer. • Biasanya milik pribadi dari sebuah perusahaan. • Bandwidthnya dianggap gratis dan oleh karena itu biaya bandwidth bukanlah sebuah pertimbangan penting. (perhatikan bahwa biaya hanya penting saat jaringan tersebut dibangun. Setelah itu, terlepas dari penggunaan bandwidth, tertentu dan variabel biaya kurang lebihnya akan sama. Oleh karena itu, bandwidth dikatakan menjadi gratis). • LANs dengan kecepatan rendah menyediakan bandwidth 416 Mbs. LANs yang lebih cepat dapat menyediakan bandwidth sampai 100-1000 Mbps.

2.1.2.2 Wide Area Network (WAN). Tidak seperti LAN, sebuah Wide Area Network (WAN) mencakup sebuah daerah yang luas. WANs digunakan terutama untuk menghubungkan lokasi-lokasi yang sangat tersebar. WANs dicirikan oleh beberapa sifat di bawah ini: • Mempunyai diameter (jangkauan) hingga ribuan kilometer. • jarang dimiliki oleh sebuah perusahaan. • Bandwidthnya sangat mahal. Oleh karena itu, biaya bandwidth memainkan peranan penting dalam proses pembuatan keputusan.


9 • Bandwidthnya berkisar 1-45 Mbps.

Untuk melihat perbedaan antara LANs dan WANs perhatikan gambar 2.1 berikut ini

Gambar 2.1 : Wide Area Network dan Local Area Network

2.1.3 Routing. Routing merupakan proses penyampaian paket data dari sumber ke tujuan masingmasing menggunakan elemen dalam jaringan yang disebut Router. Router merupakan perlengkapan

yang

digunakan

memeriksa

setiap

paket

yang

datang

kepadanya dan meneruskannya sesuai tujuan paket data tersebut.


10 2.1.3.1 Parameter Jalur. Terdapat beberapa parameter yang dapat menunjukkan bahwa suatu jalur adalah optimal antara lain (Sumit, et.al. 2005.) :

• Jumlah Hop: Salah satu cara sederhana untuk mencari lintasan optimal adalah dengan mencari jumlah router yang diperlukan untuk mencapai tujuan. Lintasan dengan jumlah router terkecil akan dipilih sebagai lintasan optimal. Walaupun sederhana, jumlah hop bukanlah ukuran yang akurat untuk mencari lintasan optimal. Sebuah lintasan dengan 3 router mungkin akan mentransfer data lebih lama daripada lintasan dengan 4 router karena mempunyai kapasitas link yang lebih baik. • Bandwidth: Beberapa protokol routing menggunakan bandwidth dari link untuk mencari lintasan terbaik. Contohnya, pada Open Shortest Path First (OSPF). • Delay: Delay menunjuk kepada waktu yang diperlukan untuk menyampaikan paket data dari sumber sampai ke tujuan nya. • Reliability: Ini menunjuk kepada tingkat kehilangan paket data dalam sebuah lintasan yang diberikan. • Load: Load dalam hal ini menunjuk kepada tingkat pemakaian link. Suatu link yang terisi mungkin akan menyebabkan delay yang lebih besar, bahkan dalam kasus yang ekstrim, menyebabkan kehilangan paket data.

2.2 Distribusi Normal Boediono dan Wayan Koster. (2004). Distribusi normal merupakan distribusi kontinu yang sangat penting dalam statistik dan banyak dipakai memecahkan persoalan. Distribusi normal disebut juga distribusi Gauss. Distribusi ini sering digunakan untuk menerangkan fenomena alam, industri, perdagangan, tingkat pendapatan masyarakat, dll. Fungsi densitas peluang variabel acak X dengan mean µ dan varian σ 2 yang


11 berdistribusi normal diberikan sebagai berikut: 1 2 1 n(x; µ, σ) = √ e− 2σ2 (x−µ) σ 2π

(2.1)

dimana µ =mean, σ =standar deviasi, π = 3, 14159..., dan e = 2, 71828 Grafik distribusi normal digambarkan sebagai berikut

Gambar 2.2 : Grafik distribusi normal f (x)

Distribusi normal f (x) didefinisikan pada interval terbuka −∞ < x < +∞. Distribusi normal dengan parameter µ dan σ 2 biasanya ditulis N (0, 1). Dengan memperhatikan persamaan umum dan grafik distribusi normal f (x), tampak bahwa bentuk kurva normal ditentukan oleh dua parameter, yaitu rata-rata dan simpangan baku. Bila nilai simpangan baku mengecil, maka bentuk kurva akan lebih rapat dan semakin runcing dan sebagian besar nilai x akan berkumpul atau mendekati nilai rata-rata. Sebaliknya semakin besar nilai simpangan baku, maka bentuk kurva akan lebih renggang dan tumpul, dimana sebagian besar nilai-nilai x akan menjauhi nilai rata-rata. Perhatikan gambar berikut


12

Gambar 2.3 : Sifat grafik distribusi normal

2.2.1 Sifat-sifat Distribusi Normal. Ada beberapa sifat penting dari distribusi normal, yaitu sebagai berikut: 1. Grafik simetri terhadap garis tegak x = µ. 2. Nilai mean, Median dan modus adalah sama/berhimpit. 3. Grafik selalu di atas sumbu X atau f (x) < 0. 4. Mempunyai satu nilai modus. 5. Kurva mempunyai titik belok pada x = µ ± σ, cekung dari bawah bila µ − σ < X < µ + σ dan cekung dari atas untuk x lainnya. 6. Grafiknya mendekati sumbu X, tetapi tidak akan pernah memotong sumbu X, sumbu X merupakan garis batas (asimtot). 7. Luas daerah di bawah kurva f (x) dan di atas sumbu X sama dengan 1.

2.2.2 Distribusi Normal Standar. Sebuah distribusi normal dengan parameter µx = 0 dan σx = 1 disebut distribusi normal standar dan dinotasikan N (0, 1). Dengan mentranformasikan Z =

x−µx σx

maka

diperoleh fungsi densitas dari sebuah variabel Z normal standar sebagai berikut z2 1 fz (Z) = √ e− 2 2π

(2.2)


13 Fungsi distribusi dan variabel Z normal standar sering disimbolkan dengan φ(z). Grafik untuk fungsi densitas normal standar diberikan dalam gambar berikut

Gambar 2.4 : Distribusi normal standar

φ(z1 ) = p dan z1 = φ−1 (p)

Dimana p adalah peluang kumulatif. Fungsi distribusi N (0, 1). Tabel normal standar terlampir. Karena fungsi densitas dari fungsi densitas normal standar adalah simetri di sekitar nilai rata-rata (z = 0), oleh karena itu (Rao. 1977.): f (−z) = f (z)

(2.3)

φ(−z) = 1 − φ(z)

(2.4)

Dengan cara yang sama, nilai dari z yang bersesuaian dengan p < 0.5 dapat diperoleh sebagai z = φ−1 (p) = −φ−1 (1 − p)

(2.5)


14 2.2.3 Probabilitas. Rinaldi Munir. Probabilitas distribusi normal f (x) pada interval x1 < X < x2 ditentukan dengan memakai luas daerah di bawah kurva f (x) sebagaimana ditunjukkan pada gambar berikut ini.

Gambar 2.5 : Probabilitas x1 < X < x2

Pada gambar , probabilitas P (x1 < x < x2 ) ditunjukkan oleh luas daerah yang diarsir, yang dibatasi oleh kurva f (x), sumbu X, garis tegak X = x1 , dan X = x2 . Oleh karena f (x) merupakan fungsi kontinu, maka probabilitas P (x1 < X < x2 ) dengan memakai integral dari fungsi f (x) yang dibatasi oleh x = x1 danx = x2 yaitu: P (x1 < X < x2 ) =

R x2 x1

f (x)dx =

R x2 x1

√1 σ 2π

− 12

e

x−µ σ

dx

akan tetapi, secara matematis bentuk integral dari fungsi f (x) tersebut sulit dipecahkan secara langsung dengan teknik integral. Oleh karena itu, penyelesainnya dilakukan dengan memakai transformasi nilai-nilai X menjadi nilai-nilai baku Z. Sehingga diperoleh fungsi distribusi normal Z, probabilitas nilai-nilai Z pada interval z1 < Z < Z2 dapat dihitung dengan rumus berikut. P (z1 < Z < z2 ) =

R z2 z1

f (z)dz =

R z2 z1

1 2 √1 e− 2 z dz 2π

Berdasarkan integral dari fungsi distribusi normal standar tersebut, probabilitas P (z1 < Z < z2 ) dihitung dengan memakai tabel distribusi normal standar. Contoh 2.1 Variabel X berdistribusi normal dengan mean 50 dan standar deviasi 10. Carilah


15 probabilitas untuk menemukan nilai X bernilai antara 45 dan 62? Dari soal µ = 50 dan σ = 10, x1 = 45 dan x2 = 62 dengan mereduksi nilai x ke z, diperoleh

(x1 − µ) σ 45 − 50 = = −0.5 10 (x2 − µ) = σ 62 − 50 = = 1.2 10

z1 =

z2

sehingga

P (45 < x < 62) = P (−0.5 < z < 1.2) P (−0.5 < z < 1.2) = P (z < 1.2) − P (z < −0.5) = 0.8849 − 0.3085 = 0.5764

2.3 Chance Constrained Programming Merupakan teknik kedua dari program stokastik yang dikembangkan oleh Charnes dan Cooper, seperti yang dinyatakan dari namanya program chance constrained adalah satu teknik yang bisa dipakai untuk menyelesaikan persoalan yang mengandung kendala peluang, kendala tersebut mempunyai peluang terbatas tertentu untuk dilanggar. Program chance constrained ini memperbolehkan kendala untuk dilanggar oleh sebuah peluang tertentu (peluang kecil) dimana teknik lain tidak ada. Rao. (1977). Bentuk umum progam chance constrained Programming dari persoalan program linier stokastik dapat dirumuskan sebagai berikut: Minimize f (x) =

n X

cj xj

(2.6)

j=1


16 dengan kendala P

X n

aij xj ≤ bi ≥ pi , i = 1, 2, ..., m

(2.7)

j=i

xj ≥ 0, j = 1, 2, ..., n

(2.8)

dimana cj , aij , dan bi adalah variabel acak dan pi adalah peluang tertentu. Perhatikan bahwa persamaan 2.7 menunjukkan bahwa kendala ke-i n X

aij xj ≤ bi

(2.9)

j=i

harus dipenuhi dengan sebuah peluang dari setidaknya pi dimana 0 ≤ pi ≤ 1. Untuk penyederhanaan asumsikan bahwa variabel keputusan xj adalah deterministik. Akan dimisalkan kasus dimana hanya cj atau aij atau bi adalah variabel acak. Diasumsikan bahwa semua variabel acak adalah berdistribusi normal dengan mean dan standar deviasi diketahui.

2.3.1 Untuk Hanya aij yang Variabel Acak. Misalkan a ¯ij dan Var (aij ) = σa2ij merupakan rata-rata dan varians dari distribusi normal variabel acak aij . Asumsikan bahwa distribusi multivariat dari aij , i = 1, 2, ..., m; j = 1, 2, ..., n, juga diketahui dengan covarian, Cov(aij , akl ) antara variabel acak aij dan akl . Definisikan jumlah di sebagai di =

n X

aij xj , i = 1, 2, ..., m

(2.10)

j=i

Karena ai1 , ai2 ,...ain berdistribusi normal, dan x1 , x2 , ..., xn merupakan konstan, di juga akan berdistribusi normal dengan nilai rata-rata d¯i =

n X

a ¯ij xj , i = 1, 2, ..., m

(2.11)

j=1

dan sebuah varian dari V ar(di ) = σd2i = X T Vi X

(2.12)


17 Dimana Vi adalah matriks covarian ke-i didefinisikan sebagai  Cov(ai1 , a12 )  V ar(aij )     Cov(ai2 , ai1 ) V ar(ai2 )  Vi =   .. ..  . .    Cov(ain , ai1 ) Cov(ain , ai2 )



· · · Cov(ai1 , ain )     · · · Cov(ai2 , ain )     .. ..  . .    ··· V ar(ain )

(2.13)

maka kendala dapat diperlihatkan sebagai P [di ≤ bi ] ≥ pi

(2.14)

di − d¯i bi − d¯i P p ≤p ≥ pi , i = 1, 2, ..., m (2.15) V ar(di ) V ar(di ) p dimana {di − d¯i / V ar(di )}dapat dipandang sebagai sebuah variabel normal standar

dengan sebuah rata-rata nol dan sebuah varian satu. Oleh karena itu peluang di lebih kecil atau samadengan bi dapat dituliskan sebagai bi − d¯i P [di ≤ bi ] = φ p V ar(di )

(2.16)

Dimana φ(x) menunjukkan fungsi kumulatif distribusi dari distribusi normal standar terhadap x. Jika ei menunjukkan nilai dari variabel normal standar dimana φ(ei ) = pi

(2.17)

maka kendala pada persamaan 2.15 dapat dinyatakan sebagai bi − d¯i ≥ φ(ei ), i = 1, 2, ..., m φ p V ar(di ) pertidaksamaan tersebut akan terpenuhi hanya jika bi − d¯i p ≥ ei V ar(di )

(2.18)

(2.19)

atau, d¯i + ei

p

V ar(di ) − bi ≤ 0, i = 1, 2, ..., m

(2.20)

Dengan mensubsitusikan persamaan 2.11 dan 2.12 , diperoleh n X

a ¯ij xj + ei

p

X T Vi X − bi ≤ 0, i = 1, 2, ..., m

(2.21)

j=1


18 Oleh karena itu solusi dari persoalan program stokastik yang ditunjukkan pada persamaan 2.6 dan 2.7 dapat diperoleh dengan menyelesaikan persoalan program deterministik berikut Minimize f (X) =

n X

cj xj

(2.22)

j=1

dengan kendala n X

a ¯ij xj + ei

p

X T Vi X − bi ≤ 0, i = 1, 2, ..., m

(2.23)

xj ≥ 0, j = 1, 2, ..., n

(2.24)

j=i

Jika distribusi normal variabel acak aij adalah adalah saling bebas, maka covarian akan menjadi nol dan persamaan 2.13 bereduksi menjadi sebuah matriks diagonal



 0  V ar(aij )     0 V ar(ai2 )  Vi =   .. ..  . .    0 0

···

0

···

0

..

.. .

.

· · · V ar(ain )

           

Dalam kasus ini, kendala dari persamaan 2.21 diturunkan menjadi v uX n X u n a ¯ij xj + et [V ar(aij )x2j ] − bi ≤ 0, i = 1, 2, ..., m j=i

(2.25)

j=i

2.3.2 Untuk Hanya bi yang Variabel Acak. Misalkan ¯bi dan V ar(bi ) menunjukkan rata-rata dan varian dari distribusi normal variabel acak bi . Kendala dari persamaan 2.7 dapat dinyatakan kembali den-


19 gan P

X n j=i

Pn bi − ¯bi j=1 aij xj − bi p ≤p aij xj ≤ bi = P V ar(bi ) V ar(bi ) Pn ¯ bi − ¯bi j=1 aij xj − bi = P p ≥ p ≥ pi V ar(bi ) V ar(bi ) i = 1, 2, ..., m

(2.26) p Dimana [bi − ¯bi / V ar(bi )] adalah sebuah variabel normal standar dengan rata-rata nol dan varian satu. Pertidaksamaan 2.26 dapat dinyatakan sebagai Pn ¯ bi − ¯bi j=1 aij xj − bi 1−P p ≤ p ≥ Pi , i = 1, 2, ..., m V ar(bi ) V ar(bi )

(2.27)

atau, bi − ¯bi P p ≤ V ar(bi )

Pn

j=1

p

aij xj − ¯bi

V ar(bi )

≤ 1 − pi , i = 1, 2, ..., m

(2.28)

Jika ei menunjukkan nilai dari variabel normal standar dimana φ(ei ) = 1 − pi

kendala pada persamaan 2.28 dapat diperlihatkan sebagai Pn ¯ j=1 aij xj − bi p φ ≤ φ(ei ), i = 1, 2, ..., m V ar(bi ) pertidaksamaan tersebut akan terpenuhi hanya jika Pn ¯ j=1 aij xj − bi p ≤ ei , i = 1, 2, ..., m V ar(bi )

(2.29)

(2.30)

atau, n X

aij xj − ¯bi − ei

p

V ar(bi ) ≤ 0, i = 1, 2, ...m

(2.31)

j=1

Oleh karena itu program stokastik linier pada persamaan 2.6 sampai 2.8 adalah sama dengan persoalan linier program deterministik di bawah ini: Minimize f (X) =

n X

cj xj

(2.32)

j=1


20 dengan kendala n X

aij xj − ¯bi − ei

p V ar(bi ) ≤ 0, i = 1, 2, ...m

(2.33)

xj ≤ 0, j = 1, 2, ..., n

(2.34)

j=1

dan

Contoh 2.2 Sebuah perusahaan memproduksi dua bagian mesin menggunakan mesin Lathes, mesin milling dan dan mesin grinding. Waktu operasi mesin yang diperbolehkan per minggu pada mesin yang berbeda dan keuntungan dari masing-masing bagian mesin diberikan dibawah ini. Jika waktu operasi yang diperbolehkan pada tiap-tiap mesin adalah berdistribusi normal dengan parameter yang diberikan pada tabel 2.1. Tentukan jumlah dari bagian mesin I dan II yang akan diproduksi perminggu untuk memaksimalkan keuntungan. fungsi kendala harus dipenuhi dengan seubah peluang setidaknya 0.99 .


21 Tabel 2.1 : Waktu operasi mesin dan parameter-parameter distribusi normal nya

Tipe Mesin

Waktu proses yang diperlukan untuk satu bagian(menit) Part I

Part II

Lathes

a11 = 10

a12 = 5

Milling

a21 = 4

a22 = 10

Grinding

a31 = 1

a32 = 1.5

Profit per unit (Rs)

c1 = 50

Waktu operasi maksimum per minggu (menit)

Mean ¯b1 = 2500 ¯b2 = 2000 ¯b3 = 450

Standar Deviasi σb1 = 500 σb2 = 400 σb3 = 50

c2 = 100

Misalkan jumlah dari bagian mesin I dan II diproduksi per minggu sebagai x1 dan x2 , nilai variabel normal standar (ei ) pada (ei ) = 1 − pi = 1/100 tidak dapat didapat langsung dari tabel lampiran A secara langsung. tetapi, perhatikan bahwa ei < 0.0 karena 1 − pi < 0.5 dan oleh karena itu φ(−ei ) = 1 − φ(ei ) = 0.99. sesuai dengan pi = 0.99, dari tabel diperoleh bahwa ei = −2.33. Oleh karena itu pertidaksamaan yang memenuhi dapat ditunjukkan dari persamaan 2.31 sebagai: 10x1 + 5x2 − 2500 − (−2.33)(500) ≤ 0 4x1 + 10x2 − 2000 − (−2.33)(400) ≤ 0 x1 + 1.5x2 − 450 − (−2.33)(50) ≤ 0 Persoalan persamaan deterministik program linier sekarang dapat ditetapkan, menggunakan persamaan 2.31 sampai 2.33 sebagai: Maksimum f = 50x1 + 100x2 dengan kendala 10x1 + 5x2 − 1335 ≤ 0


22 4x1 + 10x2 − 1068 ≤ 0 x1 + 1.5x2 − 333.5 ≤ 0 x1 ≥ 0, x2 ≥ 0

Solusi dari program linier di atas dapat diperoleh dengan menggunakan metode grafik atau metode simpleks

2.3.3 Untuk Hanya cj yang Variabel Acak. Karena cj merupakan variabel acak berdistribusi normal, maka fungsi objektif f (X) juga akan menjadi variabel acak berdistribusi normal. Rata-rata dan varian dari f diberikan sebagai berikut f¯ =

n X

c¯j xj

(2.35)

j=1

dan V ar(f ) = X T V X

(2.36)

Dimana c¯j adalah nilai rata-rata dan matriks V adalah matriks covarian dari cj didefinisikan sebagai 

 Cov(c1 , c2 )  V ar(c1 )     Cov(c2 , c1 ) V ar(c2 )  V =  .. ..  . .    Cov(cn , c1 ) Cov(cn , c2 )

· · · Cov(c1 , cn )     · · · Cov(c2 , cn )     .. ..  . .    ··· V ar(cn )

(2.37)

Dengan V ar(cj ) dan Cov(ci , cj ) menunjukkan varian dari cj dan covarian antara ci dan cj . Fungsi objektif deterministik baru untuk minimasi dapat diformulasikan sebagai F (X) = k1 f¯ + k2

p

V ar(f )

(2.38)

Dimana k1 dan k2 adalah konstanta positif yang nilai nya menunjukkan relative importance dari f¯ dan standar deviasi dari f untuk meminimasi. Oleh karena itu k2 = 0 menunjukkan bahwa nilai harapan dari f diminimalkan tanpa memperhatikan standar


23 deviasi dari f . Sebaliknya,jika k1 = 0, itu menunjukkan bahwa perlu meminimalkan variabilitas dari f disekitar nilai rata-rata nya tanpa memperhatikan apa yang terjadi dengan nilai rata-rata f . Demikian pula, jika k1 = k2 = 1, ini menunjukkan bahwa adanya kepentingan yang sama pada minimasi dari nilai rata-rata dan standar deviasi dari f . Oleh karena itu solusi dari persoalan program linier stokastik yang dinyatakan pada persamaan 2.6 sampai 2.7 dapat diperoleh dengan menyelesaikan persamaan program nonlinier deterministik : Minimize n X

√ c¯j xj + k2 X T V X

(2.39)

aij xj − bi ≤ 0, i = 1, 2, ..., m

(2.40)

f (x) = k1

j=1

dengan kendala n X j=1

xj ≥ 0, j = 1, 2, ..., n

(2.41)

Jika semua varibel acak cj adalah saling bebas, maka fungsi objektif direduksi menjadi v uX n X u n f (x) = k1 c¯j xj + k2 t V ar(cj )x2j (2.42) j=1

j=1

Setelah itu Liu mengembangkan CCP dalam permasalahan yang tidak hanya kendala stokastik tetapi juga fungsi tujuan stokastik . misalkan x sebuah vektor keputusan, ξ sebuah vektor stokastik, f (x, ξ) adalah fungsi hasil, dan gj (x, ξ) adalah fungsi kendala stokastik, j = 1, 2..., p. karena kendala stokastik gj (x, ξ) ≤ 0, j = 1, 2, ..., p tidak menetapkan sebuah himpunan penyelesaian deterministik yang feasible, maka perlu memberikan kendala stokastik sebuah tingkat jaminan α. Oleh karena itu diperoleh sebuah kendala peluang seperti berikut (Liu B. 2009), P r{gj (x, ξ) ≤ 0, j = 1, , ..., p} ≥ α

(2.43)

ini disebut dengan sebuah kendala peluang gabungan Definisi 2.1: Titik x disebut feasible jika dan hanya jika tingkat peluang dari kejadian {gj (x, ξ) ≤ 0, j = 1, 2, ..., p} setidaknya α.


24 Dengan kata lain, kendala tersebut akan dilanggar paling banyak (1 − α) kali. terkadang, kendala peluang gabungan dipisah sebagai P r{gj (x, ξ) ≤ 0} ≥ α, j = 1, , ..., p

(2.44)

2.3.4 Maximax Program Chance Constrained. Dalam lingkungan stokastik, dalam tujuan untuk memaksimalkan hasil optimistik dengan memberikan sebuah tingkat jaminan terhadap kendala peluang, Liu memberikan CCP berikut ini: max maxf¯

(2.45)

Pr {f (x, ξ) ≥ f¯} ≥ β

(2.46)

Pr {gj (x, ξ) ≤ 0, j = 1, 2, ..., p} ≥ α

(2.47)

dengan kendala

Dimana α dan β adalah tingkat jaminan, dan maxf¯ adalah β-optimistic return

2.3.5 Minimax Chance Constrained Programming. Dalam lingkungan stokastik, untuk memaksimalkan pessimistic return dengan sebuah tingkat jaminan yang diberikan pada kendala peluang, Liu menyediakan model minimax CCP dibawah ini:


25

max minf¯

(2.48)

Pr {f (x, ξ) ≤ f¯} ≥ β

(2.49)

Pr {gj (x, ξ) ≤ 0, j = 1, 2, ..., p} ≥ α

(2.50)

dengan kendala:

Dimana α dan β adalah tingkat jaminan, dan maxf¯ adalah β-optimistic return Persamaan Deterministik Dalam mencari penyelesaian akhir dari CCP diperlukan mengubah kendala peluang ke dalam masing-masing persamaan deterministiknya. Seperti yang diketahui, proses ini biasanya sulit dan hanya berhasil untuk beberapa kasus saja. Misalkan dibawah ini formula dari kendala peluang, P r{g(x, ξ) ≤ 0} ≥ α.

(2.51)

Theorema 1 Asumsikan bahwa vektor stokastik ξ degenerates menjadi sebuah variabel acak ξ dengan distribusi peluang φ, dan fungsi g(x, ξ) mempunyai formula g(x, ξ) = h(x) − ξ. Maka P r{g(x, ξ) ≤ 0} ≥ α jika dan hanya jika h(x) ≤ Kα , dimana Kα adalah bilangan terbesar sehingga P r{Kα ≤ ξ} ≥ α.

Bukti: Asumsi tersebut secara tidak langsung menyatakan bahwa P r{Kα ≤ ξ} ≥ α dapat dituliskan denggan formula di bawah ini, P r{h(x) ≤ ξ} ≥ α

Untuk setiap tingkat jaminan α(0 < α < 1), Misal Kα merupakan bilangan terbesar sehingga P r{Kα ≤ ξ} ≥ α Perhatikan bahwa peluang P r{Kα ≤ ξ} akan meningkat jika Kα diganti dengan sebuah bilangan yang lebih kecil. Oleh karena itu P r{Kα ≤ ξ} ≥ α jika dan hanya jika h(x) ≤ Kα .


26 Remark 1: Untuk varibel acak kontinu ξ, persamaan P r{Kα ≤ ξ} = 1−φ(Kα )selalu tetap, dan diperoleh, Kα = φ−1 (1 − α) Dimana φ−1 adalah fungsi invers dari φ Contoh 2.3 Asumsikan bahwa dibawah ini kendala peluang,     P r{3x1 + 4x2 ≤ ξ1 } ≥ 0.8    P r{x2 + x3 ≤ ξ2 } ≥ 0.9 1 2 Dimana ξ1 adalah variabel acak berdistribusi eksponensial Exp(2) dengan distribusi peluang dinotasikan dengan φ1 , dan ξ2 adalah variabel acak berdistribusi normal N (2, 1) dengan peluang distribusi dinotasikan φ2 . Memakai formula pada teorema 1 bahwa kendala peluang di atas samadengan     P r{3x1 + 4x2 ≤ φ−1 1 (1 − 0.8) = 0.446    P r{x2 + x3 ≤ φ−1 (1 − 0.9) = 0.719 2 1 2


BAB 2 DASAR TEORI. Jaringan komunikasi dapat dipandang sebagai sebuah keterhubungan dari entitasentitas

Recommend Documents