Teknik Riset Oprasi

Nama : Surtanto Adi WicaksonoKelas : 4KB06NPM : 29110786Jurusan : Sistem Komputer

Model PenugasanTeori PermainanPemerograman DinamicJaringanTeori AntrianTerori Rantai MArkov

Model Penugasan

• Sebagai gambaran model penugasan adalah menyangkut penempatan para pekerja pada bidang yang tersedia agar biaya yang ditanggung dapat diminimumkan.

• Misal pekerja dianggap sebagai sumber dan pekerjaan dianggap sebagai tujuan, maka pada model penugasan jumlah pasokan pada setiap sumber dan jumlah permintaan pada setiap tujuan adalah satu.

• Hal ini berarti setiap pekerja hanya menangani satu pekerjaan, atau sebaliknya satu pekerjaan hanya ditangani oleh satu pekerja

Model matematis untuk masalah penugasan :

Fungsi tujuan : Min Z =

m

i

n

jijij XC

1 1

Fungsi Batasan :

n

jijX

1

m

iijX

1

= 1, i = 1, 2, ......, m

= 1, j = 1, 2, ......., n

Xij = 0 atau 1

Catatan :Xij = 0, bila pekerjaan ke-i tidak ditugaskan pada mesin ke-j.

Xij = 1, bila pekerjaan ke-i ditugaskan pada mesin ke-j.

Penyelesaian Model Penugasan :

• Metode yang digunakan untuk menyelesaikan masalah penugasan adalah metode Hungarian

Langkah-langkah metode Hungarian

1. Lakukan pengurangan baris dengan cara mengurangkan nilai terendah pada suatu baris dari semua nilai pada baris tersebut.

2. Lakukan pengurangan kolom dengan cara mengurangkan nilai terendah pada suatu kolom dari semua nilai pada kolom tersebut.

3. Tarik sejumlah garis horizontal dan vertikal yang diperlukan untuk mencoret semua angka nol pada tabel biaya oportunity yang lengkap.

4. Jika diperlukan garis lebih sedikit dari m (dimana m = jumlah baris atau kolom), maka semua nilai lain yang tercoret dikurangkan dengan nilai terendah dari nilai-nilai yang tidak tercoret tersebut. Kemudian nilai terendah tersebut ditambahkan pada sel-sel dimana dua garis berpotongan, sedangkan nilai yang lain tetap. Ulangi langkah 3.

5. Jika diperlukan garis sebanyak m, maka solusi optimal tercapai. Sehingga dapat dilakukan analisis m penugasan yang unik. Jika masih diperlukan garis lebih sedikit dari m, maka ulangi langkah 4.

Contoh :

ACC mempunyai 4 pertandingan bola basket pada suatu malam tertentu. Kantor pusat bermaksud mengirim 4 tim pendamping ke empat pertandingan sedemikian sehingga total jarak yang harus ditempuh minimal. Jarak tiap tim pendamping ke lokasi tiap pertandingan ditunjukkan pada tabel berikut :

Tim Lokasi PertandinganK L M N

A 210 90 180 160B 100 70 130 200C 175 105 140 170D 80 65 105 120

Teori PermanianPendahuluan

• Teori permainan digunakan untuk mengambil keputusan pada situasi konflik dimana terdapat satu atau lebih pemain (lawan)

• Lawan atau pemain memiliki intelegensia yang sama. Setiap pemain mempunyai beberapa strategi untuk saling mengalahkan.

• Teori yang terkenal dari strategi ini adalah Two Person Zero Sum Game yaitu permainan dengan dua pemain dengan perolehan kemenangan (keuntungan) bagi salah satu pemain merupakan kehilangan (kerugian) bagi pemain lainnya.

Strategi permainan

• Strategi seorang pemain adalah aturan yang ditetapkan sebelumnya dimana aksi-aksi yang akan dilakukan dibuat dalam bentuk daftar sepanjang permainan.

• Matriks / Tabel Pay-Off (perolehan) adalah tabel yang menunjukkan perolehan bagi pemain baris

• Ada dua jenis strategi yang digunakan :• Strategi Murni• Strategi Campuran

Strategi murni (pure Strategy)• Digunakan jika permainan stabil • Ada titik saddle (saddle point) yaitu elemen dari matriks yang merupakan

elemen terkecil dalam barisnya dan elemen terbesar pada kolomnya.• Titik saddle → minimaks = maksimin• Contoh : tentukan strategi terbaik bagi masing-masing pemain

Penyelesaian :Minimaks =maksimin = 11 → permainan seimbang (stabil)Titik saddle → 11 nilai permainan (v)

Strategi campuran (mixed strategy)

• Strategi campuran digunakan jika permainan tidak seimbang. Pemilihan strategi dilakukan dengan mengevaluasi kombinasi strategi lawan menggunakan prinsip peluang (distribusi probabilitas).

• Definisikan : • xi adalah peluang pemain baris akan mengunakan

strategi ke-i• yj adalah peluang pemain kolom akan menggunakan

strategi ke-j

Solusi grafik

• Solusi grafik dapat digunakan jika paling salah satu pemain mempunyai hanya 2 strategi (2 x n atau mx2)

• Perhatikan matriks payoff untuk dua pemain sebagai berikut :

• Menghitung x1 dan x2 dengan menganggap pemain B menggunakan strategi murni. Maka ekpektasi perolehan bagi pemain A adalah sebagai berikut :

• Ekspektasi digambarkan dengan sumbu horizontal x1 (0 sampai 1) dan vertikal sebagai ekspektasi perolehan.

• Nilai optimum (x1 , x2 dan v) akan didapat dari titik perpotongan.

• Titik perpotongan menunjukkan strategi B yang digunakan , maka y1, y2, …yn selanjutnya dapat ditentukan.

Contoh

• Perhatikan matriks pay-off permainan di bawah ini :• Permainan di bawah ini memiliki nilai minimaks = 3 dan

maksimin = -2 (permainan tidak seimbang)

Pada penyelesaian persoalan dengan metode ini:1. terdapat sejumlah berhingga pilihan yang mungkin,2. solusi pada setiap tahap dibangun dari hasil solusi

tahap sebelumnya,3. kita menggunakan persyaratan optimasi dan

kendala untuk membatasi sejumlah pilihan yang harus dipertimbangkan pada suatu tahap.

Tinjau graf di bawah ini. Kita ingin menemukan lintasan terpendek dari 1 ke 10.

1 3

2

4

5

6

7

8

9

10

7

2

4

3

1

3

4

5

3

3

3

6

4

14

6

4 3

2

4

Prinsip Optimalitas

• Pada program dinamis, rangkaian keputusan yang optimal dibuat dengan menggunakan Prinsip Optimalitas.

• Prinsip Optimalitas: jika solusi total optimal, maka bagian solusi sampai tahap ke-k juga optimal.

• Prinsip optimalitas berarti bahwa jika kita bekerja dari tahap k ke tahap k + 1, kita dapat menggunakan hasil optimal dari tahap k tanpa harus kembali ke tahap awal.

• ongkos pada tahap k +1 = (ongkos yang dihasilkan pada tahap k ) +

(ongkos dari tahap k ke tahap k + 1)

• Dengan prinsip optimalitas ini dijamin bahwa pengambilan keputusan pada suatu tahap adalah keputusan yang benar untuk tahap-tahap selanjutnya.

• Pada metode greedy hanya satu rangkaian keputusan yang pernah dihasilkan, sedangkan pada metode program dinamis lebih dari satu rangkaian keputusan. Hanya rangkaian keputusan yang memenuhi prinsip optimalitas yang akan dihasilkan.

Karakteristik Persoalan Program Dinamis

1. Persoalan dapat dibagi menjadi beberapa tahap (stage), yang pada setiap tahap hanya diambil satu keputusan.

2. Masing-masing tahap terdiri dari sejumlah status (state) yang berhubungan dengan tahap tersebut. Secara umum, status merupakan bermacam kemungkinan masukan yang ada pada tahap tersebut.

Graf multitahap (multistage graph). Tiap simpul di dalam graf tersebut menyatakan status, sedangkan V1, V2, … menyatakan tahap.

1

3

2

4

6

7

8

9

11

10

5

12

V 1 V 2 V 3 V 4 V 5

3. Hasil dari keputusan yang diambil pada setiap tahap ditransformasikan dari status yang bersangkutan ke status berikutnya pada tahap berikutnya.

4. Ongkos (cost) pada suatu tahap meningkat secara teratur (steadily) dengan bertambahnya jumlah tahapan.

5. Ongkos pada suatu tahap bergantung pada ongkos tahap-tahap yang sudah berjalan dan ongkos pada tahap tersebut.

6. Keputusan terbaik pada suatu tahap bersifat independen terhadap keputusan yang dilakukan pada tahap sebelumnya.

7. Adanya hubungan rekursif yang mengidentifikasikan keputusan terbaik untuk setiap status pada tahap k memberikan keputusan terbaik untuk setiap status pada tahap k + 1.

8. Prinsip optimalitas berlaku pada persoalan tersebut.

Dua pendekatan PD

• Dua pendekatan yang digunakan dalam PD: maju (forward atau up-down) dan mundur (backward atau bottom-up).

• Misalkan x1, x2, …, xn menyatakan peubah (variable) keputusan yang harus dibuat masing-masing untuk tahap 1, 2, …, n. Maka,

1. Program dinamis maju. Program dinamis bergerak mulai dari tahap 1, terus maju ke tahap 2, 3, dan seterusnya sampai tahap n. Runtunan peubah keputusan adalah x1, x2, …, xn.

2. Program dinamis mundur. Program dinamis bergerak mulai dari tahap n, terus mundur ke tahap n – 1, n – 2, dan seterusnya sampai tahap 1. Runtunan peubah keputusan adalah xn, xn-1, …, x1.

Langkah-langkah Pengembangan Algoritma Program Dinamis

1. Karakteristikkan struktur solusi optimal.2. Definisikan secara rekursif nilai solusi

optimal.3. Hitung nilai solusi optimal secara maju atau

mundur.4. Konstruksi solusi optimal.

Lintasan Terpendek (Shortest Path)

• Tentukan lintasan terpendek dari simpul 1 ke simpul 10:

1 3

2

4

5

6

7

8

9

10

7

2

4

3

1

3

4

5

3

3

3

6

4

14

6

4 3

2

4

Penyelesaian dengan Program Dinamis Mundur

• Misalkan x1, x2, …, x4 adalah simpul-simpul yang dikunjungi pada tahap k (k = 1, 2, 3, 4).

• Maka rute yang dilalui adalah 1x1x2x3x4 , yang dalam hal ini x4 = 10.

Pada persoalan ini,• Tahap (k) adalah proses memilih simpul tujuan

berikutnya (ada 4 tahap).

• Status (s) yang berhubungan dengan masing-masing tahap adalah simpul-simpul di dalam graf.

Relasi rekurens berikut menyatakan lintasan terpendek dari status s ke x4 pada tahap k:

4)(

4 sxcsf (basis)

)}({min)(1 kksxxk

xfcsfkk

, (rekurens)

k = 1, 2, 3 Keterangan:

a. xk : peubah keputusan pada tahap k (k = 1, 2, 3). b.

ksxc : bobot (cost) sisi dari s ke xk

c. fk(s, xk) : total bobot lintasan dari s ke xk

d. fk(s) : nilai minimum dari fk(s, xk) Tujuan program dinamis mundur: mendapatkan f1(1) dengan cara mencari f4(s), f3(s), f2(s) terlebih dahulu.

Tahap 4:

4)(

4 sxcsf

Solusi Optimum

s f4(s) x4*

8 3 10 9 4 10

Catatan: xk

* adalah nilai xk yang meminimumkan fk(s, xk).

Tahap 3: )}({min)(

343 33

xfcsfsxx

f3(s, x3) = cs,x3 + f4(x3) Solusi Optimum x3

s 8 9 f3(s) x3*

5 4 8 4 8 6 9 7 7 9 7 6 7 6 8

Tahap 2: )}({min)(

232 22

xfcsfsxx

f2(s, x2) = cs,x2 + f3(x2) Solusi Optimum x2

s 5 6 7 f2(s) x2*

2 11 11 12 11 5 atau 6 3 7 9 10 7 5 4 8 8 11 8 5 atau 6

Tahap 1: )}({min)(

121 11

xfcsfsxx

f1(s, x1) = cs,x1 + f2(x1) Solusi Optimum x1

s 2 3 4 f1(s) x1*

1 13 11 11 11 3 atau 4

Solusi optimum dapat dibaca pada tabel di bawah ini: x1 x2 x3 x4 Panjang Lintasan

Terpendek 1

3 4

5 5 6

8 8 9

10 10 10

11 11 11

Jadi ada tiga lintasan terpendek dari 1 ke 10, yaitu

1 3 5 8 10 1 4 5 8 10 1 4 6 9 10

Panjang ketiga lintasan tersebut sama, yaitu 11.

Penganggaran Modal (Capital Budgeting)

• Sebuah perusahaan berencana akan mengembangkan usaha (proyek) melalui ketiga buah pabrik (plant) yang dimilikinya. Setiap pabrik diminta mengirimkan proposal (boleh lebih dari satu) ke perusahaan untuk proyek yang akan dikembangkan. Setiap proposal memuat total biaya yang dibutuhkan (c) dan total keuntungan (revenue) yang akan diperoleh (R) dari pengembangan usaha itu. Perusahaan menganggarkan Rp 5 milyar untuk alokasi dana bagi ketiga pabriknya itu.

• Tabel berikut meringkaskan nilai c dan R untuk masing-masing proposal proyek. Proposal proyek bernilai-nol sengaja dicantumkan yang berarti tidak ada alokasi dana yang diberikan ntuk setiap pabrik. Tujuan Perusahaan adalah memperoleh keuntungan yang maksimum dari pengalokasian dana sebesar Rp 5 milyar tersebut. Selesaikan persoalan ini dengan program dinamis.

Peubah status yang terdapat pada tahap 1, 2, dan 3: x1 = modal yang dialokasikan pada tahap 1 x2 = modal yang dialokasikan pada tahap 1 dan 2 x3 = modal yang dialokasikan pada tahap 1, 2, dan 3 x3 x2

x1 Tahap 1 Tahap 2 Tahap 3 Kemungkinan nilai-nilai untuk x1 dan x2 adalah 0, 1, 2, 3, 4, 5 (milyar), sedangkan nilai untuk x3 adalah 5

Pabrik 1 Pabrik 2 Pabrik 3

Proyek c1 R1 c2 R2 c3 R3

1 0 0 0 0 0 0 2 1 5 2 8 1 3 3 2 6 3 9 - - 4 - - 4 12 - -

Penyelesaian dengan Program Dinamis Maju.

Misalkan,Rk(pk) = keuntungan dari alternatif pk pada tahap k

fk(xk) = keuntungan optimal dari tahap 1, 2, …, dan k yang diberikan oleh status xk

Relasi rekurens keuntungan optimal:

1_

11max)(

pproposalfeasible

xf {R1(p1)} (basis)

kpproposalfeasiblekk

xf_

max)( {Rk(pk) + fk-1(xk-1) } (rekurens)

k = 2, 3 Catatan: 1. xk – 1 = xk – ck(pk) c(pk) adalah biaya untuk alternatif pk pada tahap k. 2. Proposal pk dikatakan layak (feasible) jika biayanya,

c(pk), tidak melebihi nilai status xk pada tahap k.

Relasi rekurens keuntungan optimal menjadi

111 )(11max)(

xpcxf

{R1(p1)} (basis)

kkk xpckkxf

)(max)( {Rk(pk) + fk-1[xk – ck(pk)] } (rekurens)

k = 2, 3

Tahap 1

3,2,1)(11

1

111

max)(

pxpc

xf {R1(p1)}

R1(p1) Solusi Optimal

x1 p1 = 1 p1 = 2 p1 = 3 f1(x1) p1*

0 0 - - 0 1 1 0 5 - 5 2 2 0 5 6 6 3 3 0 5 6 6 3 4 0 5 6 6 3 5 0 5 6 6 3

Tahap 2

4,3,2,1)(22

2

222

max)(

pxpc

xf {R2(p2) + f1[(x2 – c2(p2)]},

R2(p2) + f1[(x2 – c2(p2)] Solusi

Optimal

x2

p2 = 1 p2 = 2 p2 = 3 p2 = 4 f2(x2) p2*

0 0 + 0 = 0 - - - 0 1 1 0 + 5 = 5 - - - 5 1 2 0 + 6 = 6 8 + 0 = 8 - - 8 2 3 0 + 6 = 6 8 + 5 = 13 9 + 0 = 9 - 13 2 4 0 + 6 = 6 8 + 6 = 14 9 + 5 = 14 12 + 0 = 12 14 2 atau 3 5 0 + 6 = 6 8 + 6 = 14 9 + 6 = 15 12 + 5 = 17 17 4

Tahap 3

2,1)(33

3

333

max)(

pxpc

xf {R3(p3) + f2[(x3 – c3(p3)]},

R3(p3) + f2[(x3 – c3(p3)] Solusi Optimal

x3 p3 = 1 p3 = 2 f3(x3) p3*

5 0 + 17 = 17 3 + 14 = 17 17 1 atau 2

Rekonstruksi solusi:

x3 p3* x2 p2

* x1 p1* (p1

*, p2*,

p3*)

1

1 2

(5 – 0 = 5) (5 – 1 = 4)

4

2

3

(5 – 4 = 1) (4 – 2 = 2) (4 – 3 = 1)

2

3

3

(2, 4, 1)

(3, 2, 2)

(2, 3, 2)

Pengertian Jaringan

• Jaringan adalah suatu susunan garis edar (path) yang terhubung pada berbagai titik, dimana satu atau beberapa barang bergerak dari satu titik ke titik lain (Taylor, 2005)

• Contoh : sistem jalan tol, jaringan telepon, jaringan rel kereta api, jaringan televisi, dsb.

• Pada dasarnya model arus jaringan juga merupakan pengembangan dari model transportasi atau distribusi yang berkaitan dengan pemindahan / pengiriman komoditas dari suatu sumber ke suatu tujuan dengan ongkos transportasi minimum.

• Pada perkembangannya ternyata model transportasi ini dapat juga digambarkan dan diselesaikan dalam suatu bentuk jaringan

• Jaringan digambarkan sebagai suatu diagram yang terdiri dari 2 komponen, yaitu:– simpul (nodes), biasanya digambarkan dalam bentuk

lingkaran – cabang (branches), dalam bentuk garis yang

menghubungkan simpul-simpul tersebut.• Simpul (nodes) melambangkan titik-titik persimpangan

atau perhentian. Pada umumnya menyatakan lokasi, kota, stasiun, dsb.

• Cabang (branches) melambangkan arus dari satu titik ke titik yang lain dalam jaringan tersebut. Pada umumnya menyatakan waktu tempuh, jarak, panjang, dsb.

Topik pembicaraan dibatasi pada 3 macam persoalan, yaitu:

• Masalah Rute Terpendek (Shortest Route)• Masalah Rentang Pohon Minimum (Minimal

Spanning Tree)• Masalah Aliran Maksimum (Maximal Flow)

Masalah Rute Terpendek (Shortest Route) :

Masalah rute terpendek berguna untuk menentukan jarak tersingkat antara titik awal

(sumber) dengan beberapa titik tujuan

Langkah-langkah penyelesaian adalah :

1. Pilihlah simpul dengan rute langsung tersingkat dari titik awal.

2. Buatlah suatu setelan permanen (Permanent Set) dengan titik awal dan simpul terpilih dalam langkah 1. Permanent Set digunakan untuk menandakan bahwa telah ditemukan rute tersingkat ke simpul-simpul ini.

3. Tentukan seluruh simpul yang berhubungan langsung dengan simpul-simpul setelan permanen.

4. Pilihlah simpul dengan rute (cabang) terpendek dari kumpulan simpul-simpul yang berhubungan langsung dengan simpul-simpul setelan permanen.

5. Ulangi langkah 3 dan 4 sampai seluruh simpul bergabung dengan setelan permanen.

Contoh:

Sebuah perusahaan yang berlokasi di kota O memproduksi pupuk yang akan dikirimkan ke 6 distributor yang terletak pada 6 kota yang berbeda A, B, C, D, E, dan F dengan menggunakan 6 truk. Angka-angka yang tertulis dalam diagram di bawah ini menyatakan waktu (dalam jam) yang ditempuh. Gambar berikut merupakan pola jalan dan kota-kota yang dituju.Pimpinan perusahaan ingin menentukan rute terbaik (yang dinyatakan dalam waktu perjalanan minimum) bagi truk-truk tersebut untuk mengirimkan pupuk ke masing-masing tujuan mereka.

A D

O C

F

B E

16

35

9

25

1214 8

19

15

17 14

22

Masalah Rentang Pohon Minimum (Minimal Spanning Tree)

• Masalah rentang pohon minimum sebenarnya serupa dengan masalah rute terpendek, dimana perbedaannya adalah:– Tujuan masalah rute terpendek adalah menentukan rute

terpendek antara titik awal dan simpul tujuan dalam jaringan tersebut.

– Tujuan dari masalah rentang pohon minimum adalah menghubungkan seluruh simpul dalam jaringan sehingga total panjang cabang dapat diminimumkan.

• Jaringan yang dihasilkan merentangkan (menghubungkan) semua titik dalam jaringan tersebut pada total jarak (panjang) minimum.

Langkah-langkah penyelesaian adalah :

1. Pilihlah simpul awal manapun.2. Pilihlah simpul yangterdekat dengan simpul

awal untuk bergabung dengan pohon rentang.

3. Pilihlah simpul terdekat yang belum termasuk dalam pohon rentang.

4. Ulangi langkah 3 sampai seluruh simpul telah bergabung dalam pohon rentang.

Contoh :

Sebuah perusahaan TV kabel akan memasang suatu sistem kabel televisi dalam suatu komunitas yang terdiri dari 7 kota (A, B, C, D, E, F, dan G). Masing-masing kota harus dihubungkan ke sistem kabel utama. Perusahaan tersebut ingin merancang jaringan kabel utama dengan cara yang dapat meminimisasi total panjang kabel yang harus dipasang (dalam satuan meter). Jalur yang mungkin tersedia untuk perusahaan tersebut (dengan seijin dewan kota) dan panjang kabel yang dibutuhkan untuk setiap jalur digambarkan sebagai berikut :

A D

O C

F

B E

16

35

9

25

1214 8

19

15

17 14

22

Masalah Arus Maksimum (Maximal Flow):

• Masalah aliran maksimum merupakan masalah jaringan dimana cabang-cabang jaringan tersebut memiliki kapasitas arus yang terbatas.

• Tujuan dari masalah arus maksimum adalah memaksimumkan total jumlah arus dari satu titik awal ke satu tujuan

Masalah arus maksimum dapat mencakup:

• arus (aliran) air, gas, atau minyak melalui suatu jaringan pipa,

• arus formulir melalui suatu sistem pemrosesan dalam kantor pemerintah,

• arus lalu lintas melalui jaringan jalan raya, • arus produk melalui suatu sistem lini produksi, • dll.

Dalam kondisi tersebut, pengambil keputusan ingin menentukan arus maksimum yang dapat diperoleh melalui

sistem tersebut.

Langkah-langkah penyelesaian adalah :

1. Pilihlah secara arbitrer (sembarang) garis edar dalam jaringan tersebut dari titik awal ke titik tujuan.

2. Sesuaikan kapasitas pada setiap simpul dengan mengurangkan arus maksimal untuk garis edar yang dipilih pada langkah 1.

3. Tambahkan arus maksimal sepanjang garis eadr ke arus berlawanan arah pada setiap simpul.

4. Ulangi langkah 1, 2, dan 3 sampai tidak ada lagi garis edar dengan kapasitas arus yang tersedia.

Contoh:

Dipunyai suatu jaringan kereta api dari kota A ke kota T. Ingin ditentuakn rute perjalanan kereta api tersebut sedemikian sehingga jumlah total perjalanan kereta api yang dapat dilakukan setiap harinya maksimum, tanpa melanggar batas maksimum perjalanan yang dapat dilakukan pada masing-masing jalan.Diketahui data (informasi) tentang jumlah perjalanan yang dapat dilakukan pada masing-masing rute yang menghubungkan satu stasiun dengan stasiun lainnya, atau dapat dikatakan bahwa data tentang kapsitas aliran pada masing-masing cabang adalah :

1

1

6

0

094 0

0

5

4 0

2

0

1

1

3

0

4

0

75

A

B

C

D F

E

T

0

0

Gambar di atas dibaca sebagai berikut :·  Dari A ke B dapat dilakukan maksimum 5 kali perjalanan setiap hari, sedangkan dari B

ke A tidak ada perjalanan kereta api yang dapat dilakukan.·  Dari B ke D maksimum 1 kali perjalanan, begitu juga dari D ke B dapat dilakukan

maksimum 1 kali perjalanan setiap hari.

Teori AntrianPengantar

Teori antrian: teori yang menyangkut studi matematis dari antrian -antrian atau baris baris penungguan.

Merupakan bidang probabilitas terapan (statistik-matematika terapan)Dimana kita temui ?Antrian di bank, antrian di supermarket, antrian di

restoran, antrian di pintu tol, antrian di traffic lightAntrian proses, antrian transfer data, antrian pencetakan,

antrian akses web, reservasi penerbangandan masih banyak lagi

Istilah-istilah

• Beberapa istilah yang muncul dalam teori antrian :– Sistem Antrian– Elemen dalam antrian– Komponen sistem antrian– ….

CONTOH SISTEM ANTRIAN

Sistem Garis tunggu atau antrian Fasilitas

1. Lapangan terbang Pesawat menunggu di landasan

Landasan pacu

2. Bank Nasabah (orang) Kasir

3. Pencucian Mobil Mobil Tempat pencucian mobil

4. Bongkar muat barang Kapal dan truk Fasilitas bongkar muat

5. Sistem komputer Program komputer CPU, Printer, dll

6. Bantuan pengobatan darurat

Orang Ambulance

7. Perpustakaan Anggota perpustakaan Pegawai perpustakaan

8. Registrasi mahasiswa Mahasiswa Pusat registrasi

9. Skedul sidang pengadilan

Kasus yang disidangkan Pengadilan

Stuktur Model Antrian

1. Garis tunggu atau sering disebut antrian (queue)2. Fasilitas pelayanan (service facility)

Garis tunggu atau antrian

1

2

s

FasilitasPelayanan

Pelanggan masukKe dalam sistem

antrianPelanggan keluar dari

sistemantrian

STUKTUR SISTEM ANTRIAN

Elemen-elemen Antrian

• Pelanggan/nasabah (customer) dari suatu populasi (source) memasuki antrian (queue) untuk menerima layanan (service) dari fasilitas layanan (service facility)

Elemen Antrian: “Customer”

• merepresentasikan pihak yang meminta pelayanan– Permintaan pengiriman pesan dalam jaringan– Permintaan pelanggan untuk dilayani pembayaran atas

pembelian sejumlah barang– …

Elemen Antrian: Service Facility

• Service: sesuatu yang dilakukan sistem sesuai permintaan customer

• Server/channel: pemberi service• Bisa hanya satu, bisa banyak• Bisa juga dalam berbagai bentuk:

– Waktu (dalam scheduling), – Tempat (dalam alokasi memori), – Item obyek (CPU dalam multiprocessing)

Elemen Antrian: Queue

• Jika customer yang meminta layanan melebihi dari kapasitas fasilitas layanan maka sisanya berada dalan antrian (Queue)

Model Proses Markov dikembangkan oleh seorang ahli Rusia bernamaA.A. Markov, pada tahun 1906. Rantai Markov (Markov Chains) adalah suatu teknik matematika yang biasa digunakan untuk melakukan pembuatan model (modelling) bermacam – macam sistem

dan proses bisnis. Teknik ini dapat digunakan untuk memperkirakan perubahan – perubahan diwaktu yang akan datang dalam variabel – variabel dinamis atas dasar

perubahan – perubahan dari variabel – variabel dinamis tersebut di waktu yang lalu. Teknik ini dapat juga digunakan untuk menganalisa kejadian – kejadian di waktu – waktu

mendatang secara sistematis.

Pengertian Rantai Markov

Untuk dapat menerapkan analisa rantai Markov kedalam suatu kasus, ada beberapa syarat yang harus dipenuhi :1. Jumlah probabilitas transisi untuk suatu keadaan awal dari system sama dengan 1.2. Probabilitas-probabilitas tersebut berlaku untuk semua partisipan dalam system.3. Probabilitas transisi konstan sepanjang waktu.4. Kondisi merupakan kondisi yang independent sepanjang waktu.

Dasar TeoriModel Rantai MarkovAda beberapa prosedur dalam model rantai markov, antara lain :1. Menyusun Matriks Probabilitas Transisi.Untuk menggambarkan proses markov, akan disajikan suatu contoh masalah tentang kegiatan – kegiatan pemilihan merek dan peramalan probabilitas transisi yang kemungkinan dilakukan para konsumen, yaitu pergantian dari satu merek ke merek lain