Tugas Kelompok OPTIMASI

GAME THEORY

Kelompok V

Abadi Gunawan Azis (H 121 10 287)Adi Suwandi (H 121 10 288) Ahmad Jamil (H 121 10 290)Edi Susilo (H 121 10 291) Siswanto (H 121 10 901)Musafirah (H 121 10 902)Andi Ammar Firaz (H 121 10 903)

PROGRAM STUDI STATISTIKAJURUSAN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAMUNIVERSITAS HASANUDDIN

MAKASSAR2012

BAB I

1 | P a g e

PENDAHULUAN

Dalam kehidupan sehari-hari sering dijumpai kegiatan-kegiatan yang

bersifat kompetitif yang diwarnai persaingan atau konflik. Persaingan atau konflik ini

dapat terjadi antara dua orang (dua pihak) atau sejumlah orang (grup). Contohnya

adalah :

1. persaingan antara dua perusahaan dalam memasarkan produk baru,

2. permainan catur,

3. dua buah partai politik yang bersaing dalam kampanye untuk memperoleh suara

terbanyak.

Tidak setiap keadaan persaingan dapat disebut sebagai permainan (game).

Kriteria atau ciri-ciri dari suatu permainan adalah :

1. terdapat persaingan kepentingan diantara pemain,

2. setiap pemain mempunyai sejumlah pilihan, terbatas atau tidak terbatas, yang

disebut strategi,

3. aturan permainan untuk mengatur pilihan-pilihan itu disebutkan satu-satu dan

diketahui oleh semua pemain,

4. hasil permainan dipengaruhi oleh pilihan-pilihan yang dibuat oleh semua pemain.

(Aidawayati.2011)

Teori permainan merupakan teori dimana dua orang atau lebih yang memiliki

kepentingan berbeda terlibat dalam suatu permainan untuk mencapai tujuan sesuai

dengan yang diinginkan. Teori ini pertama kali dikembangkan oleh Emile Borel pada

tahun 1921, yang dikembangkan lebih lanjut oleh John Von Newmann dan Oscar

Morgenstern. Penerapan teori ini sukses dilakukan dalam bidang militer , dengan

berjalannya waktu penggunaan teori ini semakin luas digunakan khususnya dalam

bidang ekonomi dan sosial.

(Andi Wijaya.2011)

2 | P a g e

Ide dasar dari teori permainan adalah tingkah laku strategi dari pemain atau

pengambil keputusan (player or decision maker). Setiap pemain dianggap

mempunyai suatu seri rencana atau model tingkah laku dari mana dia bisa memilih,

kalau memiliki suatu set strategi. Strategi menunjukkan untuk setiap situasi yang

timbul dalam proses permainan, gerakkan khusus mana yang harus dipilih.

(Johannes Supranto. 1988)

Manfaat teori permainan diantaranya untuk mengembangkan suatu kerangka

untuk analisa pengambilan keputusan dalam situasi persaingan (kerja sama).

Menguraikan metode kualitatif yang sistematik bagi pemain yang terlibat dalam

persaingan untuk memilih strategi yang tradisional dalam pencapaian tujuan.

Memberikan gambaran dan penjelasan fenomena situasi persaingan/konflik seperti

tawar menawar dan perumusan koalisi.

(Andi Wijaya.2011)

3 | P a g e

BAB II

LANDASAN TEORI

Teori permainan (game theory) adalah suatu teori yang di dalamnya terdapat

bentuk persaingan antara dua orang atau pihak atau antara dua kelompok atau grup

yang saling berhadapan dan melaksanakan aturan-aturan yang diketahui oleh kedua

belah pihak yang saling berhadapan. Dalam permainan, pihak pertama disebut dengan

pemain baris sedangkan pihak kedua disebut pemain kolom. Aturan-aturan dalam

permainan antara lain :

1. langkah atau strategi yang dapat dipilih oleh tiap-tiap pemain,

2. pembayaran, yang didefinisikan secara numerik, yang harus dipenuhi oleh setiap

pemain setelah permainan selesai.

(Aidawayati.2011)

A. Permainan menggunakan Strategi Murni

Dalam permainan strategi murni, pemain baris mengidentifikasi strategi

optimalnya melalui kriteria maksimin (maksimum di antara minimum baris), sedang

pemain kolom menggunakan kriteria minimaks (minimum di antara maksimum

kolom). Pada kasus nilai maksimin sama dengan minimaks maka dikatakan titik

ekuilibrium telah dicapai yang biasa disebut sebagai titik sadel (saddle point). Bila

tidak dicapai keadaan seperti itu, maka strategi murni tidak dapat diterapkan dan

digunakan strategi campuran .

(Aminudin. 2005).

B. Permainan menggunakan Strategi Campuran

Dalam suatu permainan, dikenal strategi campuran dimana

strategi ini digunakan jika permainan tidak seimbang atau dengan kata

lain titik equilibriumnya tidak ada. Selanjutnya di strategi campuran

4 | P a g e

akan dicari suatu nilai optimal dari masing-masing pemain yang

terlibat di dalamnya. Untuk mendapatkan nilai optimal tersebut,

biasanya digunakan beberapa cara yaitu:

- Metode penyelesaian dengan grafik

- Metode penyelesaian dengan program linier

(Aidawayati.2011)

Saat permainan tidak memiliki titik pelana, teori permainan menyarankan tiap

pemain untuk menggunakan distribusi probabilitas pada kumpulan strateginya. Untuk

menyatakan hal ini secara matematis, misalkan

x i = probabilitas pemain 1 akan menggunakan strategi i (i=1 , 2 ,…, m)

y j = probabilitas pemain 2 akan menggunakan strategi j ( j=1 ,2 , …, n)

Dengan m dan n merupakan jumlah dari strategi yang tersedia. Oleh karena itu,

pemain 1 akan menetapkan rencananya dalam memainkan permainan ini dengan

menetapkan nilai untuk x1 , x2, …xm . Nilai-nilai ini adalah probabilitas sehingga nilai

ini harus non negatif dan berjumlah 1. Dengan cara yang sama, rencana untuk pemain

2 dinyatakan dengan nilai-nilai yang ia tetapkan untuk variabel keputusan y1 , y2 ,… yn

. Rencana-rencana ini (x1 , x2, …xm ) dan y1 , y2 ,… yn biasanya disebut strategi

campuran.

Ketika permainan benar-benar dimainkan, perlu bagi tiap pemain untuk

menggunakan satu dari strategi murni mereka. Bagaimanapun, strategi murni ini akan

dipilih dengan menggunakan alat pengacak untuk memperoleh nilai acak dari

distribusi probabilitas yang ditetapkan oleh strategi campuran, dengan nilai ini akan

mengindikasikan strategi murni mana yang akan digunakan.

(Gerald Frederick, 2008).

C. Permainan menggunakan Metode Grafik

5 | P a g e

Pemain kolom

Pemain baris

j . . . i . . . = 1- . . .

Metode grafik merupakan salah satu metode yang digunakan untuk mencari

nilai optimum dari setiap pemain yang terlibat di dalamnya. Metoda grafik dapat

digunakan untuk menyelesaikan masalah permainan yang mempunyai matriks pay off

berukuran 2 x n atau m x 2. Penyelesaian dengan menggunakan metode grafik ini

diawali dengan melihat nilai pay off yang diharapkan untuk setiap strategi murni

yang digunakan oleh lawan. Yang mana pada masalah ini nilai pay off yang

diharapkan ditentukan oleh peluang penggunaan setiap strategi. Untuk lebih jelasnya,

akan dijelaskan permainan 2 x n (baris) dan m x 2(kolom)

(Aidawayati.2011)

1) Permainan 2 x n

Bila matriks suatu permainan berukuran 2 x n, maka permainan tersebut dapat

diselesaikan dengan metode grafik didasarkan pada cara penyelesaian berikut :

- Bila X1 = X1* adalah peluang penggunaan strategi I dan X2 = X2

* adalah peluang

penggunaan strategi 2 oleh pemain baris, maka X1 + X2 = 1

- Nilai pay off yang diharapkan bagi pemain baris dapat diketahui untuk setiap

strategi murni yang digunakan oleh pemain kolom dengan didasarkan pada

peluang setiap strateginya tersebut (X1 danX2 ).

- Dilakukan pembuatan grafik hubungan nilai pay off yang diharapkan bagi

pemain baris pada setiap peluang untuk setiap strategi murni pemain kolom.

- Berdasarkan kriteria maksimin dapat ditentukan peluang penggunaan strategi

secara optimal untuk setiap pemain baris dan nilai permainannya.

(Aidawayati.2011)

Perhatikan permainan (2 xn) berikut ini:

Bentuk matriks pembayaran untuk permainan 2 xn

6 | P a g e

Diasumsikan bahwa permainan ini tidak memiliki titik sadel. Maka hasil yang

diperkirakan yang bersesuaian dengan strategi murni dari Pemain Kolom diketahui:

Tabel pembayaran harapan pemain 1

Strategi murni Pemain kolom Pembayaran harapan pemain baris

1

2

.

.

.

N

a11 x1+a21.(1-X1)=(a11-a21)X1+a21

a12 x1+a22..(1-X1)=(a12-a21)X1+a22

.

.

.

a1n X1+a2n-(1-X1)=(a1n-a2n)X1+a2n

2) Permainan m x 2

Bila matriks suatu permainan berukuran m x 2, maka permainan tersebut dapat

diselesaikan dengan metode grafik didasarkan pada cara penyelesaian berikut :

- Bila Y1 = Y1*adalah peluang penggunaan strategi 1 dan Y2 = Y2* adalah

penggunaan strategi 2 oleh pemain kolom, maka Y1 + Y2 = 1

- Nilai pay off yang diharapkan bagi pemain kolom dapat diketahui untuk setiap

strategi murni yang digunakan oleh pemain baris dengan didasarkan pada

peluang penggunaan setiap strateginya tersebut( Y1 dan Y2 ).

- Dilakukan pembuatan grafik hubungan nilai pay off yang diharapkan bagi

pemain kolom pada setiap peluang untuk setiap strategi murni pemain baris.

- Berdasarkan kriteria minimaks dapat ditentukan peluang penggunaan setiap

strategi yang optimum untuk pemain kolom dan nilai permainannya.

(Aidawayati.2011)

7 | P a g e

Perhatikan permainan (mx 2) berikut ini:

Bentuk matriks pembayaran untuk mx 2

Pemain kolom

y1 y2=1− y1

Pemain x1

baris x2

.

.

xm

J 1 2

i

1 a11 a12

2 a21 a22

.

.

m am1 am2

Dan adapun Pembayaran harapan yang berkaitan dengan strategi murni Pemain Baris

adalah sebagai berikut:

Tabel pembayaran harapan Pemain 2

Strategi murni pemain baris Pembayaran harapan pemain kolom

1

2

.

.

.

M

¿¿ - a12)y1+ a12

(a21 - a22)y1+a22

.

.

.

8 | P a g e

(am1 - am2)y1+am2

Tabel di atas menunjukkan bahwa pembayaran harapan (rata-rata

pembayaran) bagi pemain P2 bervariasi secara linear dengan y1. Berdasarkan kriteria

minimax untuk pemain P2 harus memilih nilai y1 yang akan meminimumkan

pembayaran harapan (rata-rata pembayaran) maksimumnya (prinsip minimax). Hal

ini dapat dilakukan dengan cara menggambarkan garis-garis lurus di atas sebagai

fungsi dari y1. Sumbu vertikal menunjukkan pembayaran harapan (rata-rata

pembayaran) dan sumbu horizontal menunjukkan variasi dari y1 (0 ≤ y1 ≤ 1). Dalam

grafik ini dicari titik minimaxnya.

Penyelesaian dengan metode grafik dapat terjadi jika dan hanya jika salah

satu pemain yang terlibat dalam permainan tersebut mempunyai 2 strategi. Adapun

matriks pay off untuk dua pemain sebagai berikut :

Pemain II

Y1 Y2 … Yn

X1=X1*

a11 a12 … a1n

Pemain I X2

* = 1 – X1* a21 a22 … a2n

Keterangan :X1 = X1

* = probabilitas pemain 1 memainkan strategi kesatu

X2 = X2* = probabilitas pemain 1 memainkan strategi kedua

Yn = probabilitas pemain 2 memainkan strategi ke-n

Diasumsikan bahwa grafik ini tidak memiliki titik equilibrium. Karena

pemain I memiliki dua strategi dan pemain I merupakan pemain baris, maka peluang

terlaksananya setiap strategi adalah X1+ X2 = 1 sehingga dapat dituliskan sebagai

berikut X2 = 1- X1 , X1 ≥ 0, X2 ≥ 0. Maka langkah-langkah penyelesaiannya adalah

1. Menghitung nilai X1 dan X2 pada pemain I dengan menganggap pemain II

menggunakan strategi murni. Maka tabel pembayaran harapan bagi pemain I

adalah sebagai berikut :

9 | P a g e

Tabel pembayaran harapan untuk pemain I

Strategi MurniPemain 2

Pembayaran Harapan Pemain I

12׃

N

a11.x1+a21.(1-x1)=(a11-a21) X1+a21

a12.x1+a22.(1-x1)=(a12-a22) X1+a22

׃a1n.x1+a2n.(1-x1)=(a1n-a2n ) X1+a2n

Tabel di atas menunjukkan bahwa pembayaran harapan (rata-rata

pembayaran) bagi pemain P1 bervariasi secara linear dengan X1. Berdasarkan

kriteria minimax untuk pemain P1 harus memilih nilai X1 yang akan

memaksimalkan pembayaran harapan (rata-rata pembayaran) minimumnya

(prinsip maximin). Hal ini dapat dilakukan dengan cara menggambarkan

garis-garis lurus di atas sebagai fungsi dari X1 dalam suatu grafik yang mana

sumbu vertikal menunjukkan pembayaran harapan (rata-rata pembayaran) dan

sumbu horizontal menunjukkan nilai dari x1 (0 ≤ X1 ≤1).

2. Selanjutnya akan dicari nilai optimum pada pemain I (X1 dan X2) serta nilai

permainannya (v*). Nilai optimal maupun nilai permainan itu sendiri

diperoleh dengan mencari titik perpotongan dari dua garis yang

berlainan tanda dan paling mendekati sumbu horizontal dan titik inilah

yang disebut dengan titik maksimin. Dalam hal ini, harus memilih nilai X1

yang akan memaksimalkan pembayaran harapan minimum pada pemain I.

Setelah nilai optimal X1 diperoleh, maka nilai permainan dapat juga diketahui

dengan cara mensubstitusi nilai X1 ke dalam salah satu garis yang

berpotongan dan melalui titik maksimin.

3. Karena nilai optimal dari pemain I sudah diketahui maka untuk mencari nilai

optimal pemain II, digunakan titik perpotongan sebelumnya. Titik ini

menunjukkan banyaknya strategi pemain II yang dapat digunakan.

Maksudnya adalah dengan menggunakan rumus

10 | P a g e

v ¿=∑i=1

m

∑j = 1

n

aij X i¿ Y j

¿

sehingga nilai dari Y1, Y2,…, Yn dapat ditentukan. Dengan bantuan

rumus ini, maka akan terbentuk matriks pembayaran pemain II

yang baru, yang mana pemain I akan melakukan strategi murni

dan dalam pencarian nilai optimum pemain II, harus memilih

nilai Y1 (yang berpotongan pada dua buah garis) yang dapat

meminimumkan pembayaran harapan yang maksimum.

4. Setelah mendapatkan tabel pembayaran harapan yang baru

untuk pemain II atau pemain kolom maka dapat dibuatkan grafik

untuk mencari nilai optimalnya. Yang pada grafik, sumbu

horizontalnya menunjukkan nilai peluang Y dan sumbu

vertikalnya menunjukkan nilai pembayaran (pay off).

Perpotongan garis yang berlainan tanda dan paling

menjauhi sumbu horizontal dinamakan titik minimaks.

Dan titik inilah yang diperlukan dalam mencari nilai optimum

untuk pemain kolom.

(Aidawayati.2011)

11 | P a g e

BAB III

PEMBAHASAN

Soal 1 Strategi Campuran

Consider the game having the following payoff table.

B (S1) (S2) (S3)

A

(S1) 5 0 3 (S2) 2 4 2 (S3) 3 2 4

finding optimal mixed strategies ?

(Sumber : Frederick S. Hillier dan Gerald J. Lieberman.Introduction to Operations

Research Seventh Edition.2005.Number 14.5-2 page 747)

Penyelesaian :

Langkah 1

Mula-mula akan dicoba dulu dengan menggunakan strategi murni. Bagi pemain baris

akan menggunakan aturan maximin dan pemain kolom akan menggunakan aturan

minimax. Untuk pemain baris (A) , pilih nilai yang paling kecil untuk setiap baris

(Baris satu nilai terkecilnya 0 , untuk baris kedua nilai terkecilnya 2 dan baris tiga

12 | P a g e

nilai terkecilnya 2). Selanjutnya dari dua nilai terkecil tersebut, pilih nilai yang paling

besar, yakni nilai 2.

BMaksimin

(S1) (S2) (S3)

A

(S1) 5 0 3 0 (S2) 2 4 2 2 (S3) 3 2 4 2

Langkah 2

Untuk pemain kolom (B), pilih nilai yang paling besar untuk setiap kolom (kolom

satu nilai terbesarnya 5, kolom dua nilai terbesarnya 4, dan kolom tiga nilai

terbesarnya 4). Selanjutnya dari tiga nilai terbesar tersebut, pilih nilai yang paling

kecil bagi B, yakni nilai 4.

BMaksimin

(S1) (S2) (S3)

A

(S1) 5 0 1 0 (S2) 2 4 2 2 (S3) 3 2 4 2

Minimax 5 4 4

Langkah 3

Dari tabel di atas terlihat bahwa pemain baris-A dan pemain kolom-B tidak sama,

dimana pemain A maksiminnya adalah 2 dan pemain B minimaksnya adalah 4,

dengan demikian maka permainan ini dapat dikatakan belum optimal karena belum

ditemukan nilai permainan (titik keseimbangan) yang sama. Oleh karena itu perlu

dilanjutkan dengan menggunakan strategi campuran, yang langkahnya adalah sebagai

berikut :

Langkah 4

13 | P a g e

Masing-masing pemain akan menghilangkan strategi yang menghasilkan keuntungan

atau kerugian paling buruk. Bila diperhatikan pada tabel sebelumnya, untuk pemain

A, strategi S1 adalah paling buruk, karena bisa menimbulkan kemungkinan kerugian

bagi A. Dan bagi pemain B, strategi S1 adalah paling buruk karena kerugiannya yang

bisa terjadi paling besar (perhatikan nilai-nilai kerugian di strategi S1

pemain/perusahaan B).

Langkah 5

Setelah pemain A membuang strategi S1 dan pemain B membuang stretgi S1,

diperoleh tabel sebagiai berikut :

B (S2) (S3)

A

(S2) 4 2 (S3) 2 4

Setelah mendapatkan pay off yang baru, tentukan minimaks dan maksimin jika telah

mendapatkan titik keseimbangan maka nilai sudah optimal, karena pay off yang baru

maksiminnya 2 dan minimaksnya 4 maka belum optimal sehingga dilanjutkan untuk

mengoptimalkan nilai pembayaran tersebut.

Perhatikan bahwa setelah masing-masing membuang strategi yang paling buruk,

maka sekarang persaingan atau permainan dilakukan dengan kondisi, perusahaan A

menggunakan strategi S2 dan S3, sementara perusahaan B menggunakan strategi S2

dan S3.

Langkah 6

14 | P a g e

Langkah selanjutnya adalah dengan memberikan nilai probabilitas terhadap

kemugkinan digunakannya kedua strategi bagi masing-masing perusahaan. Untuk

perusahaan A, bila kemungkinan keberhasilan penggunaan strategi S2 adalah sebesar

p, maka kemungkinan keberhasilan digunakannya strategi S3 adalah (1-p). Begitu

pula dengan pemain B, bila kemungkinan keberhasilan penggunaan strategi S2 adalah

sebesar q, maka kemungkinan keberhasilan digunakannya strategi S3 adalah (1-q).

B(S2)(q)

(S3)(1-q)

A

(S2)(p)

4 2

(S3)(1-p)

2 4

Langkah 7

Selanjutnya mencari nilai besaran probabilitas setiap strategi yang akan digunakan

dengan menggunakan nilai-nilai yang ada serta nilai probalitas masing-masing

strategi untuk menghitung titik keseimbangan yang optimal, dengan cara sebagai

berikut :

Untuk perusahaan A

Bila, apapun strategi yang digunakan A, perusahaan B meresponnya dengan strategi

S2, maka :

4p + 2(1-p) = 4p + 2 – 2p = 2 + 2p

Bila, apapun strategi yang digunakan A, perusahaan B meresponnya dengan strategi

S3, maka :

2p + 4(1-p) = 2p + 4 – 4p = 4 - 2p

15 | P a g e

Bila kedua hasil persamaan tersebut digabung, maka :

2 + 2p = 4 - 2p

-2=-4p

P = 2/4 = 0,5

Dan apabila nilai p = 0,5, maka nilai (1-p) adalah (1 – 0,5) = 0,5, sehingga kedua nilai

probabilitas untuk strategi S2 dan S3 milik perusahaan A sudah diketahui nilainya.

Apabila kedua nilai probabilitas tersebut dimasukkan dalam kedua persamaan di atas,

maka keuntungan yang diharapkan oleh perusahaan A adalah :

Dengan persamaan ke-1 Dengan persamaan ke-2

= 4p + 2(1-p) = 2p + 4(1-p)

= 4 (0,5) + 2 (0,5) = 2 (0,5) + 4 (0,5)

= 3 = 3

Perhatikan, bahwa keduanya menghasilkan keuntungan yang diharapkan adalah

sama, yakni sebesar 3. Coba diingat di atas, bahwa sebelum menggunakan strategi

campuran ini keuntungan perusahaan A hanya sebesar 2, berarti dengan digunakan

strategi campuran ini, keuntungan perusahaan A bisa meningkat 1 menjadi 3.

Untuk perusahaan B

Bila, apapun strategi yang digunakan B, perusahaan A meresponnya dengan strategi

S2, maka :

4q + 2(1-q) = 4q + 2 – 2q = 2 – 2q

Bila, apapun strategi yang digunakan B, perusahaan A meresponnya dengan strategi

S3, maka :

2q + 4(1-q) = 2q + 4 – 4q = 4 - 2q

2 – 2q = 4 - 2q

-2 = -4q

q = 2/4 = 0,5

16 | P a g e

Dan apabila nilai q = 0,5, maka nilai (1-q) adalah (1 – 0,5) = 0,5, sehingga kedua nilai

probabilitas untuk strategi S2 dan S3 milik perusahaan B sudah diketahui nilainya.

Apabila kedua nilai probabilitas tersebut dimasukkan dalam kedua persamaan di atas,

maka kerugian minimal yang diharapkan oleh perusahaan B adalah :

Dengan persamaan ke-1 Dengan persamaan ke-2

= 4q + 2(1-q) = 2q + 4(1-q)

= 4 (0,5) + 2 (0,5) = 2 (0,5) + 4 (0,5)

= 3 = 3

Perhatikan, bahwa keduanya menghasilkan kerugian minimal yang diharapkan adalah

sama, yakni sebesar 3. Coba diingat di atas, bahwa sebelum menggunakan strategi

campuran ini kerugian minimal perusahaan B adalah sebesar 4, berarti dengan

digunakan strategi campuran ini, kerugian minimal perusahaan B bisa menurun

sebesar 1 menjadi 3.

Kesimpulan :

Kerena penggunaan strategi murni belum mampu menemukan nilai permainan (titik

keseimbangan) yang sama, maka penyelesaian masalah permainan/persaingan di atas

dilanjutkan dengan digunakannya strategi campuran. Penggunaan strategi campuran

ini terbukti disamping mampu menemukan nilai permainan (titik keseimbangan) yang

sama, strategi campuran ini juga mampu memberikan hasil yang lebih baik bagi

masing-masing perusahaan. Perusahaan A keuntungan yang diharapkan naik menjadi

3 dan kerugian minimal yang diterima perusahaan B juga dapat turun hanya sebesar

3. Sudah optimal.

Soal 2 Metode Grafik 2 xn

For each of the following payoff tables, use the graphical procedure

B1 B2 B3

A1 4 3 1

17 | P a g e

A2 0 1 2

(Sumber : Frederick S. Hillier dan Gerald J. Lieberman.Introduction to Operations

Research Seventh Edition.2005.Number 14.4-3 page 746)

Penyelesaian :

Dengan menggunakan strategi murni, dilakukan aturan maximin bagi pemain A

(pemain baris) dan aturan minimax bagi pemain B (pemain kolom)

Langkah 1

Untuk pemain baris (pemain A), pilih nilai yang paling kecil untuk setiap baris

(baris pertama nilai terkecilnya 1 dan baris kedua nilai terkecilnya 0). Selanjutnya

dari dua nilai terkecil tersebut, pilih nilai yang paling baik atau besar, yakni nilai 1

(Maximin).

Langkah 2

Untuk pemain kolom (pemain B), pilih nilai yang paling besar untuk setiap

kolom (kolom pertama nilai terbesarnya 4, kolom kedua nilai terbesarnya 3, dan

kolom ketiga nilai terbesarnya 2). Selanjutnya dari tiga nilai terbesar tersebut, pilih

nilai yang paling kecil, yakni nilai 2 (minimax).

Pem

ain

A

Pemain BMaximinStrategi

1 Strategi 2

Strategi 3

Strategi 1

4 3 1 1

Strategi 2

0 1 2 0

Minimax 4 3 2 Langkah 3

18 | P a g e

Karena nilai Maximin (1) dan Minimax (2) ini tidak sama (tidak optimal), maka

akan diselesaikan dengan menggunakan Metode Grafik sbb:

Metode Grafik :

Grafik ini akan menggunakan strategi baris

StrategiPemain B

Y1 Y2 Y31 2 3

Pem

ain

A

X1 1 4 3 1

X2=1−X1 2 0 1 2

Penyelesaian :

X1 = probabilitas pemain 1 memainkan strategi kesatu

X2 = probabilitas pemain 1 memainkan strategi kedua

Yj = probabilitas pemain 2 memainkan strategi ke-j

maka pembayaran harapan bagi pemain A yang berkaitan dengan strategi murni B

adalah :

19 | P a g e

Strategi Murni Pemain B Pembayaran Harapan Pemain A1

2

3

4 x1+0 (1−x1)=4 x1

3 x1+1 (1−x1 )=2 x1+1

x1+2 (1−x1)=−x1+2

Catatan :

1. 4 x1

2. 2 x1+1

3. −x1+2

Karena yang ditinjau pertama kali adalah pemain baris, maka harus memilih nilai x1

yang akan memaksimalkan pembayaran harapan minimumnya (kriteria maksimin)

yaitu :

v¿=max ( x1 ) {min (4 x1 ,¿2 x1+1 ,−x1+2)}¿

karena hanya garis (1) dan (3) yang melalui titik maximin maka :

v¿=max ( x1 ) {min (4 x1 ,¿−x1+2)}¿

dari sini nilai optimum x1 = titik potong garis (1) dengan garis (3) :

20 | P a g e

4 x1=−x1+2=¿>5 x1=2

x1=x1¿=2

5

x2¿=1−x1

¿=35

Jadi, strategi campuran optimal A X* = [ 25

,35 ]

Nilai permainan yang diperoleh :

v¿=4 x1¿=4.

25=8

5atau v¿=−x1

¿+2=−25

+2=−25

+105

=85

Selanjutnya akan dihitung strategi optimal pemain B . Nilai yang optimal bagi pemain

pembayaran B dapat diperoleh dari nilai pembayaran harapan permainan, yaitu; :

v ¿=∑i=1

m

∑j = 1

n

aij X 2¿ Y j

¿

v ¿= y1¿ {(a11 −a21 ) X2

¿ + a21 } + y2¿ {(a12 −a22 ) X2

¿ + a22 } +⋯+ yn¿ {(a1 n − a2 n) X2

¿+ a2n }Sehingga :

y1¿ (4 x1

¿ )+ y2¿ (2 x1+1 )+ y3

¿ (−x1+2 )=85

85

y1

¿

+ 95

y2¿+ 8

5y

3

¿

=85

85

y1

¿

+0+ 85

y3

¿

=85

85

y1

¿

+ 85

y3

¿

=85

¿¿ = 0 karena tidak melalui titik maximin )

Solusi untuk pemain A adalah perpotongan garis (1) dan (3). Dengan

menggunakan titik perpotongan tersebut, dapat dibentuk matriks pembayaran II yang

baru.

21 | P a g e

Strategi Pemain B

Y 1 Y 3=1−Y 1

1 3

Pemain A1 4 1

2 0 2

Setelah mendapatkan pay off yang baru, tentukan minimaks dan maksimin telah

didapatkan titik keseimbangan maka nilai sudah optimal, karena pay off yang baru

maksiminnya 1 dan minimaksnya 2 maka belum optimal sehingga dilanjutkan untuk

mengoptimalkan nilai pembayaran tersebut.

Tabel pembayaran harapan untuk pemain B yang bersesuaian dengan strategi

murni pemain A adalah :

Strategi Murni Pemain A Pembayaran Harapan Pemain B1

2

4 y1+1 (1− y1 )=3 y1+1

0 y1+2 (1− y1 )=−2 y1+2

22 | P a g e

Keterangan :

1. 3 y1+1

2. −2 y1+2

Karena B menginginkan untuk meminimumkan kekalahan yang maksimum maka

pemain B harus memilih nilai yang maksimum, yaitu:

v¿=min ( y1 ) {max (3 y1+1 ,−¿2 y1+2)}¿

karena kedua garis (1) dan (2) melalui titik minimax maka nilai optimum titik potong

kedua garis tersebut, diperoleh

3 y1+1=−¿2 y1+2¿

5 y1=1

y1=15

y1= y1¿=1

5

y3¿=1− y1

¿=45

Nilai permainan yang diperoleh :

23 | P a g e

v ¿=∑i=1

m

∑j = 1

n

aij X i¿ Y 2

¿

v ¿= X1¿ {(a11 −a12)Y 2

¿ + a12 } + X2¿ {(a21 −a22 )Y 2

¿ + a22 } +⋯+ Xn¿ {(a1n − a2n ) Y 2

¿+ a2n }

v¿=3 y1¿+1=3.

15+1=8

5

atau v¿=−2 y1¿+2=−2.

15+2=−2

5+10

5=8

5

jadi strategi optimal B y* = [15

, 0,45

], dan nilai permainan v* = 85

Soal 3 Metode Grafik m x2

Solve the following by graphical method

B1 B2

A1 1 2

A2 5 4

A3 -7 9

A4 -4 -3

A5 2 1

(Sumber : N.V.R. Naidu, K.M. Babu, G. Rajendra.Operations Research

Question.2007.I K International. Page 153. Number 19)

Penyelesaian :

Dengan menggunakan strategi murni, dilakukan aturan maximin bagi pemain A

(pemain baris) dan aturan minimax bagi pemain B (pemain kolom)

Langkah 1 :

24 | P a g e

Untuk pemain baris (pemain A), pilih nilai yang paling kecil untuk setiap baris

(baris pertama nilai terkecilnya 1, baris kedua nilai terkecilnya 4, baris ketiga nilai

terkecilnya -7, baris keempat nilai terkecilnya -4 dan baris kelima nilai terkecilnya 1).

Selanjutnya dari dua nilai terkecil tersebut, pilih nilai yang paling baik atau besar,

yakni nilai 4 (Maximin).

Langkah 2 :

Untuk pemain kolom (pemain B), pilih nilai yang paling besar untuk setiap

kolom (kolom pertama nilai terbesarnya 5, dan kolom kedua nilai terbesarnya 9).

Selanjutnya dari tiga nilai terbesar tersebut, pilih nilai yang paling kecil, yakni nilai 5

(minimax).

Pem

ain

A

Pemain BStrategi 1

Strategi 2

Maximin

Strategi 1

1 2 1

Strategi 2

5 4 4

Strategi 3

-7 9 -7

Strategi 4

-4 -3 -4

Strategi 5

2 1 1

Minimax 5 9

25 | P a g e

Langkah 3:

Karena nilai Maximin (4) dan Minimax (5) ini tidak sama (tidak optimal), maka

akan diselesaikan dengan menggunakan Metode Grafik sbb:

Metode Grafik :

Membuat matriks pay off permainan seperti di bawah ini :

Pem

ain

A

Pemain B

Strategi 1 Strategi 2

Strategi 1 1 2

Strategi 2 5 4

Strategi 3 -7 9

Strategi 4 -4 -3

Strategi 5 2 1

Untuk pemain B

Mendahulukan pemain B karena pemain B yang juga merupakan pemain kolom

mempunyai tipe permainan m x 2. Untuk mencari stategi campuran optimum untuk

pemain B maka ada beberapa langkah yang harus dilakukan yaitu :

Langkah 4 :

Membuat tabel pembayaran harapan pada pemain B dengan memisalkan peluang

terlaksananya strategi 1 pada pemain B = Y1 dan peluang terlaksananya strategi 2 =

Y2 = 1-Y1. Adapun tabelnya sebagai berikut :

Tabel pembayaran (pay off)

26 | P a g e

Pem

ain

A

Pemain B

Y 1 Y 2=1-Y1

X1 1 2

X 2 5 4

X3 -7 9

X4 -4 -3

X5 2 1

Langkah 5 :

Selanjutnya pada langkah ini, akan ditentukan nilai pembayaran yang diharapkan

(expected pay off) pada pemain kolom (pemain B) dengan menganggap pemain baris

(pemain A) menggunakan strategi murni. Hal ini dapat ditunjukkan dalam tabel

seperti di bawah ini :

Strategi Murni A Pembayaran harapan B

1 Y1+2(1-Y1) = 2-Y1

2 5Y1+4(1-Y1) = 4+Y1

3 -7Y1+9(1-Y1) = 9-16Y1

4 -4Y1+(-3)(1-Y1) = -3-Y1

5 2Y1+1(1-Y1) = 1+Y1

Langkah 6 :

Setelah diketahui persamaan pembayaran harapannya (expected pay off), maka

selanjutnya akan digambarkan lima garis lurus fungsi dari Y1 ke dalam grafik, yang

mana grafik itu sendiri merupakan hubungan peluang dengan nilai pay offnya. Sumbu

horizontal menunjukkan nilai peluang penggunaan strategi (Y1) dan sumbu verikal

menunjukkan nilai pay offnya/ average pay off. Adapun nilai-nilai Y1 dari setiap

strategi adalah :

Strategi 1 : 2− y1

27 | P a g e

Strategi 2 : 4+ y1

Strategi 3 : 9−16 y1

Strategi 4 : −3− y1

Strategi 5 : 1+ y1

Maka kelima garis lurus fungsi dari Y1 tersebut dapat digambarkan pada grafik

sebagai berikut :

Keterangan :

1. 2− y1

2. 4+ y1

3. 9−16 y1

4. −3− y1

5. 1+ y1

Menurut kriteria minimaks Pemain B, mengharuskan pemain B memilih strategi

campuran yang meminimumkan nilai pembayaran harapan maksimumnya.

v¿=min ( y1 ) {max (2− y1 ,¿4+ y1 , 9−16 y1 ,−3− y1 , 1+ y1)}¿

karena hanya garis 3 dan garis 5 yang melalui titik maksimin yang ditunjukkan oleh

titik pada perpotongan garis yang paling mendekati sumbu horizontal maka :

28 | P a g e

v¿=min ( y1 ) {max (9−16 y1 ,¿1+ y1)}¿

dari sini nilai optimum Y1 adalah titik potong garis 2 dan garis 3 :

9−16 y1=¿1+ y1¿

9−1=16 y1+ y1

8=17 y1

y1=8

17

y1= y1¿= 8

17

y2=1− y1¿=1− 8

17=17

17− 8

17= 9

17

Jadi strategi campuran optimum untuk pemain B, Y*= [8

17,

917

]

Nilai permainan yang diperoleh :

v¿=9−16 y1¿=9−16.

817

=9−12817

=15317

−12817

=2517

Atau

v¿=1+ y1¿=1+ 8

17=17

17+ 8

17=25

17

Langkah 7 :

Selanjutnya akan dihitung strategi optimum pemain A. Nilai yang optimum bagi

pemain A dapat diperoleh dari nilai pembayaran harapan permainan, yaitu

v ¿=∑i=1

m

∑j = 1

n

aij Y 2¿ X i

¿

v ¿= X1¿ {(a11 −a21)Y 2

¿ + a21 } + X2¿ { (a12 −a22 )Y 2

¿ + a22 } +⋯+ Xn¿ {(a1n − a2n ) Y 2

¿+ a2 n}sehingga

29 | P a g e

v ¿= X1¿ {(2−Y 1

¿) } + X2¿ {(4+Y 1

¿ )} +X3¿ {(9−16 Y 1

¿ )}+ X4¿ {(−3−Y 1

¿) }+X 5¿ {(1+Y 1

¿) }2517

= 2617

X1¿ + 32

17X2

¿ +2517

X 3¿−32

17X 4

¿+2517

X5¿

2517

=0+ 0+ 2517

X3

¿ −0+2517

X5

¿

2517

= 2517

X3¿ +25

17X5

¿

¿, karena tidak melalui titik maksimin)

Jadi strategi kesatu,kedua dan keempat pemain A tidak dimainkan, sehingga

matriks pembayaran menjadi :

Tabel pembayaran (pay off) :

Pem

ain

A

Pemain B

Y1 Y2 = 1- Y2

X3 = X3* -7 9

X5= X5* = 1- X3 2 1

Setelah mendapatkan pay off yang baru, tentukan minimaks dan maksimin jika telah

mendapatkan titik keseimbangan maka nilai sudah optimal, karena pay off yang baru

maksiminnya 1 dan minimaksnya 2 maka belum optimal sehingga dilanjutkan untuk

mengoptimalkan nilai pembayaran tersebut.

Maka pembayaran harapan bagi pemain A yang berkaitan dengan strategi murni

pemain B adalah :

Strategi Murni B Pembayaran harapan A

1 -7X3 + 2(1-X3) = 2-9X3

2 9X3 +1(1-X3) = 1 +8X3

30 | P a g e

Kedua garis lurus fungsi dari X3 tersebut dapat digambarkan pada grafik :

Keterangan :

1. 2-9X3

2. 1 +8X3

Karena pemain A menginginkan untuk memaksimumkan keuntungan yang minimum

maka pemain A harus memilih nilai X3 sesuai dengan kriteria minimaks yaitu :

v¿=max ( x3 ) {min (2−9 X3 ,¿1+8 x3)}¿

karena kedua garis 1 dan 2 melalui titik maksimin maka nilai optimum X3* adalah

titik potong kedua garis tersebut, diperoleh :

2−9 x3=¿1+8 x3 ¿

2−1=8 x3+9 x3

1=17 x3

x3=1

17

x3=x3¿= 1

17

x5=1−x3¿=1− 1

17=17

17− 1

17=16

17

31 | P a g e

Nilai permainan yang diperoleh :

v ¿=∑i=1

m

∑j = 1

n

aij X 2¿ Y j

¿

v ¿= Y 1¿ {(a11 −a21 ) X2

¿ + a21 } + Y 2¿ {(a12 −a22 ) X2

¿ + a22 } +⋯+ Y n¿ {(a1 n − a2n ) Y 2

¿+ a2n }

v¿=2−9 x3¿=2−9.

117

=2− 917

=3417

− 917

=2517

Atau

v¿=1+8 x3¿=1+8.

117

=1717

+ 817

=2517

Jadi strategi optimal pemain A, X* = [0, 0, 1

17, 0,

1617

] dan nilai permainan v* = 2517

sama dengan nilai permainan pada pemain B.

BAB IV

PENUTUP

Kesimpulan

Teori permainan (game theory) adalah suatu teori yang di dalamnya terdapat

bentuk persaingan antara dua orang atau pihak atau antara dua kelompok atau

grup yang saling berhadapan dan melaksanakan aturan-aturan yang diketahui

oleh kedua belah pihak yang saling berhadapan.

Permainan dengan menggunakan Strategi Murni.Dalam permainan strategi

murni, pemain baris mengidentifikasi strategi optimalnya melalui kriteria

maksimin (maksimum di antara minimum baris), sedang pemain kolom

menggunakan kriteria minimaks (minimum di antara maksimum kolom). Pada

kasus nilai maksimin sama dengan minimaks maka dikatakan titik ekuilibrium

telah dicapai yang biasa disebut sebagai titik sadel (saddle point). Bila tidak

dicapai keadaan seperti itu, maka strategi murni tidak dapat diterapkan dan

digunakan strategi campuran . (Aminudin. 2005).

32 | P a g e

Permainan dengan menggunakan Strategi Campuran.Dalam suatu permainan,

dikenal strategi campuran dimana strategi ini digunakan jika permainan tidak

seimbang atau dengan kata lain titik equilibriumnya tidak ada. Selanjutnya di

strategi campuran akan dicari suatu nilai optimal dari masing-masing pemain

yang terlibat di dalamnya. Untuk mendapatkan nilai optimal tersebut,

biasanya digunakan beberapa cara yaitu:

- Metode penyelesaian dengan grafik

- Metode penyelesaian dengan program linier

(Aidawayati Rangkuti.Modul Optimasi game theory. Makassar.)

Metode grafik merupakan salah satu metode yang digunakan untuk mencari

nilai optimum dari setiap pemain yang terlibat di dalamnya. Metoda grafik

dapat digunakan untuk menyelesaikan masalah permainan yang mempunyai

matriks pay off berukuran 2 x n atau m x 2. Penyelesaian dengan

menggunakan metode grafik ini diawali dengan melihat nilai pay off yang

diharapkan untuk setiap strategi murni yang digunakan oleh lawan. Yang

mana pada masalah ini nilai pay off yang diharapkan ditentukan oleh peluang

penggunaan setiap strategi. Untuk lebih jelasnya, akan dijelaskan permainan

2 x n (baris) dan m x 2(kolom)

(Aidawayati Rangkuti.Modul Optimasi game theory. Makassar.)

33 | P a g e

DAFTAR PUSTAKA

Aminudin. 2005. Prinsip-prinsip Riset Operasi. Erlangga

Hiller Frederick S. dan Gerald J. Lieberman.Introduction to Operations Research

Seventh Edition.2005.

Johannes Supranto. 1988. Riset Operasi Untuk pengambilan Keputusan.

Universitas Indonesia

N.V.R. Naidu, K.M. Babu, G. Rajendra.Operations Research Question.2007.I K

International

Rangkuti,Aidawayati.Modul Optimasi Game Theory. Makassar.

34 | P a g e

Wijaya, Andi.2011. Pengantar Riset Operasi. Jakarta: Penerbit Mitra Wacana

Media.

35 | P a g e