1 of 22

Metode Kuantitatif Pengambilan Keputusan (MKPK)

Week 12

BAB 10 –Markov Chain & Markov Decision Process

1

Muhamad Wahid Ibrahim, SE., M.Sc.

Photo by Robert Schöller on Unsplash

2 of 22

BAB 10 – Rantai Markov (Markov Chain) & Markov Decision Process (MDP)

Model stokastik untuk sistem yang berubah dari waktu ke waktu

Perubahan Keadaan Berdasarkan Probabilitas

Rantai Markov menggambarkan bagaimana suatu sistem berpindah dari satu keadaan ke keadaan lain berdasarkan probabilitas transisi antar keadaan.

Sistem Tanpa Ingatan (Memoryless)

Ciri khas rantai Markov adalah probabilitas transisi hanya bergantung pada keadaan saat ini, bukan pada riwayat sebelumnya.

Beragam Aplikasi Dunia Nyata

Digunakan dalam berbagai bidang seperti antrian, manajemen stok, analisis keuangan, ekonomi makro, dan pemeliharaan mesin.

3 of 22

Tujuan Pembelajaran

Setelah mempelajari bab ini, mahasiswa mampu:

Memahami Dasar Rantai Markov

Menjelaskan konsep inti dari rantai Markov, termasuk sifat memoryless dan bagaimana sistem stokastik dapat dimodelkan.

Menganalisis Matriks Transisi

Menyusun dan membaca matriks transisi, serta menghitung probabilitas steady-state dan waktu kembali rata-rata.

Menguasai Konsep MDP

Menjelaskan struktur dan elemen penting dalam Markov Decision Process (MDP) dan aplikasinya.

Mengaitkan dengan Dunia Nyata

Menghubungkan teori Markov dan MDP dengan aplikasi dalam sistem antrian, manajemen stok, keuangan, dan lainnya.

4 of 22

10.1 Pendahuluan Rantai Markov

Model probabilistik untuk sistem stokastik

  • Definisi Rantai Markov: Model probabilistik yang memodelkan transisi antar keadaan dalam sistem stokastik yang berubah dari waktu ke waktu.
    • Sifat Tanpa Ingatan (Memoryless): Probabilitas menuju keadaan selanjutnya hanya bergantung pada keadaan saat ini, bukan pada riwayat sebelumnya.
    • Kegunaan Luas: Digunakan untuk memodelkan sistem antrian, persediaan barang, dan pergerakan ekonomi atau pasar.

Photo by Nik on Unsplash

5 of 22

Contoh Intuitif Rantai Markov

Ilustrasi transisi antar keadaan mesin pabrik

Definisi Keadaan Mesin

Mesin dalam tiga keadaan: Baik, Rusak Ringan, dan Rusak Berat. Mewakili kondisi sistem pada setiap periode waktu.

Sifat Markovian dalam Mesin

Kondisi minggu depan hanya bergantung pada kondisi minggu ini, bukan pada kondisi-kondisi sebelumnya.

Model Transisi Probabilistik

Perpindahan antar keadaan dijelaskan melalui probabilitas transisi, membentuk dasar rantai Markov.

6 of 22

10.2 Karakteristik Rantai Markov: Keadaan (States)

Definisi dan contoh keadaan dalam sistem stokastik

  • Keadaan Harus Saling Eksklusif: Setiap sistem hanya bisa berada dalam satu keadaan pada satu waktu tertentu. Tidak boleh tumpang tindih antar state.
    • Keadaan Harus Lengkap: Semua kemungkinan kondisi sistem harus terdefinisi sebagai state. Tidak ada kondisi yang dibiarkan tanpa representasi.
    • Contoh Keadaan: Antrian: 0, 1, 2 pelanggan | Mesin: baik, rusak ringan, rusak berat | Ekonomi: boom, stabil, resesi

Photo by Robert Schöller on Unsplash

7 of 22

Transisi & Sifat Markovian

Pergerakan antar state dan konsep tanpa ingatan

  • Transisi Antar Keadaan: Perubahan sistem dari satu keadaan ke keadaan lain seiring waktu, direpresentasikan oleh probabilitas Pᵢⱼ.
    • Sifat Tanpa Ingatan (Memoryless): Probabilitas transisi hanya bergantung pada keadaan saat ini, tidak dipengaruhi oleh urutan sebelumnya.
    • Contoh Praktis: Jika hari ini stok 10 unit, maka peluang stok besok hanya bergantung pada angka 10 tersebut, bukan histori stok sebelumnya.

Photo by Roman Mager on Unsplash

8 of 22

Jenis Rantai Markov

Perbandingan waktu diskrit dan waktu kontinu

  • Waktu Diskrit: Observasi sistem dilakukan pada interval waktu tertentu (harian, mingguan, bulanan). Cocok untuk sistem periodik seperti antrian atau manajemen stok.
    • Waktu Kontinu: Perubahan keadaan dapat terjadi kapan saja, tanpa batas waktu diskrit. Cocok untuk proses berkelanjutan seperti pemeliharaan mesin.
    • Pemilihan Tipe Bergantung Aplikasi: Pemilihan jenis rantai Markov ditentukan oleh sifat sistem yang dimodelkan dan kebutuhan observasinya.

Photo by Daniele Levis Pelusi on Unsplash

9 of 22

10.3 Matriks Transisi

Representasi probabilitas perpindahan antar keadaan

  • Definisi Matriks Transisi: Tabel yang memuat probabilitas berpindah dari satu state ke state lainnya dalam satu langkah waktu.
    • Elemen Pᵢⱼ: Menunjukkan probabilitas berpindah dari state i ke state j. Digunakan untuk memprediksi dinamika sistem.
    • Sifat Matriks: Jumlah seluruh elemen dalam satu baris = 1. Setiap baris menggambarkan total kemungkinan dari satu state.

Photo by Alexander Grey on Unsplash

10 of 22

Matriks Transisi n-Langkah

Melihat perkembangan sistem dalam beberapa langkah ke depan

  • Konsep Pⁿ: Pⁿ menunjukkan probabilitas berpindah antar state setelah n langkah waktu.
    • Cara Menghitung: Gunakan perkalian matriks berulang: P² = P × P, P³ = P × P × P, dst.
    • Kegunaan Praktis: Berguna untuk memprediksi kondisi sistem jangka menengah atau panjang secara matematis.

Photo by Anessa Pennington on Unsplash

11 of 22

10.4 Klasifikasi Keadaan

Memahami jenis-jenis state dalam rantai Markov

  • Keadaan Menyerap (Absorbing): State yang jika dimasuki tidak dapat keluar lagi. Misalnya: kerusakan total mesin.
    • Keadaan Transien (Transient): State yang cenderung dikunjungi sementara dan tidak dikunjungi kembali setelah waktu tertentu.
    • Keadaan Berulang & Periodik: State yang pasti akan dikunjungi kembali (recurrent) atau hanya bisa dikunjungi kembali pada kelipatan waktu tertentu (periodik).

Photo by Volodymyr Hryshchenko on Unsplash

12 of 22

Keadaan Menyerap & Transien

Analisis sifat-sifat state dalam sistem Markov

  • State Menyerap (Absorbing): Sekali dimasuki, sistem tidak dapat keluar. Ciri: Pⱼⱼ = 1, elemen lain = 0.
    • Contoh Keadaan Menyerap: Kerusakan total mesin, utang macet, kegagalan permanen.
    • State Transien (Transient): State sementara yang kemungkinan besar tidak akan dikunjungi kembali setelah beberapa waktu.

Photo by Wesley Tingey on Unsplash

13 of 22

Keadaan Berulang & Periodik

State yang dikunjungi kembali secara teratur atau berkala

  • Keadaan Berulang (Recurrent): Sistem pasti akan kembali ke state tersebut. Probabilitas kembali = 1.
    • Keadaan Periodik: State hanya bisa dikunjungi lagi dalam kelipatan waktu tertentu (t, 2t, dst).
    • Contoh Aplikasi: Harga yang selalu kembali ke nilai keseimbangan (recurrent), musim panen setiap 3 periode (periodik).

Photo by Dan Meyers on Unsplash

14 of 22

10.5 Probabilitas Steady-State

Distribusi probabilitas jangka panjang dalam rantai Markov

  • Definisi Steady-State: Kondisi jangka panjang di mana distribusi probabilitas tidak berubah lagi meskipun sistem terus berjalan.
    • Vektor Steady-State (π): π = [π₁, π₂, ..., πₙ], di mana π = πP dan ∑πᵢ = 1.
    • Makna πᵢ: Menunjukkan proporsi waktu sistem berada pada state ke-i dalam jangka panjang.

Photo by Brett Jordan on Unsplash

15 of 22

Contoh Steady-State: Antrian 2 Keadaan

Perhitungan dan interpretasi steady-state dalam sistem sederhana

  • Matriks Transisi Antrian: P = [[0,8 0,2], [0,4 0,6]]; mewakili probabilitas berpindah antar dua keadaan: 0 pelanggan dan 1 pelanggan.
    • Perhitungan Steady-State: Gunakan sistem persamaan π = πP dan π₀ + π₁ = 1 untuk menemukan nilai π.
    • Hasil dan Interpretasi: π₀ ≈ 0,667 → 66,67% waktu tanpa pelanggan, π₁ ≈ 0,333 → 33,33% waktu ada 1 pelanggan. Bermanfaat untuk perencanaan kapasitas layanan.

Photo by Mika Baumeister on Unsplash

16 of 22

10.6 Waktu Kembali Rata-Rata (Mean Return Time)

Mengukur seberapa lama sistem kembali ke state tertentu

  • Definisi Mean Return Time: Jumlah langkah rata-rata untuk kembali ke state j setelah meninggalkannya. Berlaku untuk state berulang.
    • Rumus Perhitungan: mⱼ = 1 / πⱼ, di mana πⱼ adalah probabilitas steady-state dari state j.
    • Contoh & Aplikasi: Jika πⱼ = 0,25 → mⱼ = 4 langkah. Berguna untuk pemeliharaan mesin dan estimasi normalisasi antrian.

Photo by Icons8 Team on Unsplash

17 of 22

10.7 Markov Decision Process (MDP): Konsep Dasar

Perluasan dari rantai Markov dengan aksi dan keputusan

  • MDP = Markov Chain + Keputusan: Tidak hanya transisi antar state, tapi juga mempertimbangkan aksi yang memengaruhi transisi dan hasil.
    • Struktur MDP: Setiap state memiliki beberapa pilihan aksi. Aksi tersebut memengaruhi probabilitas transisi dan reward.
    • Tujuan MDP: Mencari kebijakan optimal (policy) untuk memaksimalkan reward atau meminimalkan biaya dalam jangka panjang.

Photo by Edho Pratama on Unsplash

18 of 22

Komponen Utama MDP

Struktur pembentuk Markov Decision Process

  • States (S): Mewakili kondisi sistem, seperti kondisi mesin: baik, rusak ringan, rusak parah.
    • Actions (A): Tindakan yang bisa diambil di setiap state, seperti: do nothing, perbaikan ringan, ganti mesin.
    • Transition Probabilities (Pᵢⱼ(a)): Probabilitas berpindah dari state i ke j jika aksi a diambil.
    • Reward / Cost (R atau C): Hasil (positif/negatif) dari aksi dan state tertentu.
    • Policy (π): Strategi aksi terbaik yang dipilih di tiap state untuk hasil optimal.

19 of 22

Contoh MDP: Pemeliharaan Mesin

Membangun kebijakan optimal dari state dan aksi

  • State Mesin: K0: Baik, K1: Rusak Ringan, K2: Rusak Parah. Mewakili kondisi operasional mesin.
    • Pilihan Aksi: A: Do Nothing, B: Pemeliharaan. Setiap kombinasi state–aksi punya reward & cost berbeda.
    • Evaluasi Nilai Harapan (EV): Menghitung nilai harapan tiap aksi di tiap state untuk menentukan kebijakan terbaik.

Photo by Emanuele Diviso on Unsplash

20 of 22

10.8 Aplikasi Dunia Nyata

Penerapan Markov Chain dan MDP dalam berbagai bidang

  • Sistem Antrian: Digunakan untuk memperkirakan waktu tunggu dan menentukan jumlah staf atau loket optimal di bank, rumah sakit, call center.
    • Manajemen Stok: Membantu menetapkan kebijakan pemesanan untuk mengurangi risiko kekurangan atau kelebihan stok.
    • Model Ekonomi & Pasar: Memodelkan pergerakan harga saham dan siklus ekonomi (boom, stabil, resesi).
    • Keuangan & Investasi: MDP digunakan untuk merancang strategi portofolio dengan mempertimbangkan risiko dan return.

Photo by Clint Adair on Unsplash

21 of 22

10.9 Ringkasan Bab

Intisari konsep Rantai Markov dan MDP

Rantai Markov

Model stokastik dengan sifat memoryless, terdiri dari state dan matriks transisi (P).

Klasifikasi State

Termasuk menyerap, transien, berulang, dan periodik. Mempengaruhi analisis perilaku jangka panjang.

Steady-State & Return Time

Distribusi probabilitas jangka panjang (π) dan waktu kembali rata-rata (mⱼ = 1/πⱼ).

Markov Decision Process (MDP)

Memasukkan aksi dan kebijakan untuk optimasi keputusan dalam ketidakpastian.

22 of 22

Referensi

Sumber utama untuk pendalaman materi Rantai Markov dan MDP

  • Hillier & Lieberman (2015): Introduction to Operations Research – Referensi klasik untuk topik optimisasi dan pemodelan stokastik.
    • Render, Stair, Hanna, & Hale (2015): Quantitative Analysis for Management – Cocok untuk pengantar analisis keputusan dan MDP.
    • Taha (2017): Operations Research: An Introduction – Sangat lengkap dan aplikatif untuk Markov Chain & MDP.

Photo by Thomas Kelley on Unsplash