Didownload dari ririez.blog.uns.ac.id

Didownload dari ririez.blog.uns.ac.id

A. METODE PROGRAM LINIER Terdapat hubungan yang erat antara teori permainan dan program linier karena setiap bentuk permainan berjumlah nol dari dua orang (yang berhingga) dapat dinyatakan sebagai suatu bentuk program linier dan sebaliknya, setiap permasalahan program linier dapat disajikan sebagai suatu permainan. Dalam penyelesaian suatu permainan dengan metode program linier ini, sering dihadapkan kepada masalah metode simpleks dualitas. Untuk suatu permainan dengan matriks pembayaran yang berukuran besar (m x n) dan tidak mempunyai titik pelana serta metode dominasi tidak dapat digunakan untuk mereduksi ukuran matriks pembayaran menjadi lebih kecil, maka program linier menawarkan suatu metode penyelesaian yang efisien. Perhatikan matriks pembayaran di bawah ini. Pemain P2

Pemain P1

y1

y2

……..

yn

x1

a11

a12

……..

a1n

x2

a21

a22

a2n

x3

a31

a32

a3n

.

.

.

.

.

.

.

.

.

xm

am1

am2

……..

amn

dengan xi = probabilitas pemain P1 memilih stategi ke- i yi = probabilitas pemain P2 memilih stategi ke- j aij = nilai pembayaran yang bersesuaian dengan strategi ke-i pemain P1 dan ke-j pemain P2, i = 1, 2,...,m dan j = 1, 2, ..., n. • Untuk pemain P1 (pemain baris).

1


Pemain

P1

memilih

xi,

m    xi ≥ 0, ∑ xi = 1 yang i =1  

akan

menghasilkan

m m   m  max min ∑ ai1 xi , ∑ ai 2 xi ,..., ∑ ain xi  . x i =1 i =1  i =1  

Hal ini menunjukkan bahwa strategi campuran optimum pemain P1 memenuhi m m   m  max min ∑ ai1 xi , ∑ ai 2 xi ,..., ∑ ain xi  berdasar pembatas : x i =1 i =1  i =1   m

∑x i =1

i

= 1 dan xi ≥ 0, i = 1, 2, …, m.

Persoalan ini dapat disajikan ke bentuk program linier sebagai berikut ; m m  m  jika v = min ∑ a i1 xi , ∑ ai 2 xi ,..., ∑ a in xi  maka persoalan ini menjadi : i =1 i =1  i =1 

Memaksimumkan Z = v berdasarkan pembatas : m

∑a i =1

ij

xi ≥ v , j = 1, 2, …, n

i

= 1 , xi ≥ 0 untuk semua i

m

∑x i =1

v = nilai permainan Perumusan program linier di atas dapat disederhanakan dengan membagi (n+1) pembatas dengan v. Pembagian ini berlaku untuk v > 0. Jika v = 0 maka pembagian tidak berlaku. Sebaliknya, jika v < 0 maka pembagian ini juga tidak berlaku namun dapat diubah menjadi v > 0 dengan menambahkan suatu konstanta positif k pada semua elemen dalam matriks pembayaran yang akan menjamin nilai permainan untuk matriks yang dimodifikasi ini lebih besar dari nol. Sebagai pedoman, diambil k ≥ harga mutlak dari elemen yang terkecil sehingga sebelum merumuskan ke bentuk program linier perlu diperiksa nilai maximin barisnya karena jika nilai maximin tersebut negatif maka ada kemungkinan nilai permainannya negatif atau nol. Dengan demikian matriks pembayarannya perlu dimodifikasi dahulu dan sebagai konsekuensinya adalah jika solusi optimum telah diperoleh maka

2


nilai permainan yang sebenarnya ditentukan dengan mengurangi sebesar k tadi dari nilai permainan yang dimodifikasi itu. Pada umumnya jika nilai maximinnya positif maka nilai permainannya lebih besar daripada nol (terutama permainan yang mempunyai titik pelana). Oleh karena itu di dalam pembentukan rumusan program linier diasumsikan bahwa v > 0. Pembatas-pembatas (constraints) dalam rumusan program linier di atas menjadi : m

∑a i =1

ij

xi ≥ 1, j = 1, 2, 3, ..., n v

m

dan

xi

∑v i =1

=

1 , xi ≥0 untuk semua i. v

Atau ditulis secara lengkap :

a11

x x x1 x + a 21 2 + a31 3 + ... + a m1 m ≥ 1 v v v v

a12

x x x1 x + a 22 2 + a32 3 + ... + a m 2 m ≥ 1 v v v v

a13

x x x1 x + a 23 2 + a33 3 + ... + a m 3 m ≥ 1 v v v v

. . .

a1n

x x x1 x + a 2 n 2 + a3n 3 + ... + a mn m ≥ 1 v v v v

dan Jika

x x1 x 2 x3 1 + + + ... + m = v v v v v dinotasikan

Xi =

X 1 + X 2 + X 3 + ... + X m =

xi v

dengan

i

=

1 1 . Karena max V = min v v

= min [X1+X2+X3+...+Xm] Maka persoalan di atas menjadi :

3

1,

2,

...,

m

maka


Meminimumkan z = X 1 + X 2 + X 3 + ... + X m =

1 v

berdasarkan pembatas :

a11 X 1 + a 21 X 2 + a31 X 3 + ... + am1 X m ≥ 1 a12 X 1 + a22 X 2 + a32 X 3 + ... + a m 2 X m ≥ 1 a13 X 1 + a23 X 2 + a33 X 3 + ... + am3 X m ≥ 1 . . .

a1n X 1 + a 2n X 2 + a3n X 3 + ... + amn X m ≥ 1 X 1 , X 2 , X 3 ..., X m ≥ 0

Dari sini kemudian diselesaikan dengan metode simpleks. Penyelesaian bagi pemain P2 merupakan dual dari penyelesaian pemain P1. Jadi penyelesaian optimum bagi salah satu pemain dapat memberikan penyelesaian optimum bagi pemain lainnya meskipun penyelesaian bagi pemain P2 merupakan dual dari penyelesaian pemain P1. Perhitungan penyelesaian optimum pemain P2 dapat dilakukan dengan menggunakan metode simpleks dan penyelesaian pemain P1 merupakan dualnya. Pada kenyataannya bahwa lebih mudah untuk menghitung penyelesaian pemain P2 dengan metode simpleks terlebih dahulu.

• Untuk pemain P2 (pemain kolom) n   Pemain P2 memilih yj,  y j ≥ 0, ∑ y j = 1 yang akan menghasilkan j =1   n n   n  min max ∑ a1 j y j , ∑ a 2 j y j ,..., ∑ a mj y j  . yj  j =1 j =1  j =1  

Hal ini menunjukkan bahwa strategi campuran optimum pemain P2 memenuhi n n   n   min max  ∑ a1 j y j , ∑ a 2 j y j ,..., ∑ a mj y j   yj  j =1 j =1    j =1

4


n

berdasarkan pembatas

∑y j =1

j

= 1 dan yj > 0 , j = 0,1,2,…,n.

Persoalan ini dapat dirumuskan ke dalam bentuk program linear sebagai berikut. Jika n n  n  v = max ∑ a1 j y j , ∑ a 2 j y j ,..., ∑ a mj y j  j =1 j =1  j =1 

Maka persoalan di atas menjadi, meminimumkan Z = v berdasarkan pembatas n

∑a

ij

j =1 n

∑y j =1

j

y j ≤ v , i = 1, 2,…, m = 1 , yj > 0 untuk semua j

v = nilai permainan Asumsikan bahwa v > 0 maka pembatas-pembatas dalam rumusan program linear di atas menjadi yj

n

∑a j =1

ij

v

≤ 1 , i = 1, 2,…, m

dan n

yj

j =1

v

∑

=

1 , yj > 0 untuk semua j v

Atau ditulis secara lengkap y y y1 y + a12 2 + a13 3 + ... + a1n n ≤ 1 v v v v y y y y a21 1 + a22 2 + a23 3 + ... + a2 n n ≤ 1 v v v v M y y y y am1 1 + am 2 2 + am 3 3 + ... + amn n ≤ 1 v v v v a11

dan

y y1 y2 1 + + ... + n = v v v v

Jika dinotasikan Y j =

yj v

; j = 0,1,2,…,n maka

5


Y1 + Y2 + Y3 + ... + Yn = Karena min v = max

1 . v

1 v

= max[Y1 + Y2 + Y3 + ... + Yn ] , maka persoalan di atas menjadi

 1 w = Y1 + Y2 + Y3 + ... + Yn  =  berdasarkan  v

Memaksimumkan

pembatas-

pembatas a11Y1 + a12Y2 + a13Y3 + ... + a1nYn ≤ 1 a21Y1 + a22Y2 + a23Y3 + ... + a2 nYn ≤ 1

M am1Y1 + am 2Y2 + am3Y3 + ... + amnYn ≤ 1 Y1, Y2, Y3,…, Yn > 0 Kemudian diselesaikan dengan metode simpleks dan penyelesaian pemain P1 merupakan dual dari penyelesaian pemain P2 dan simpleksnya lebih sederhana.

Contoh 1 : Diberikan matriks pembayaran (3 x 3) sebagai berikut : Pemain P2

x1 Pemain P1 x2 x3

y1

y2

y3

2

-1

-3

-2

0

1

0

-3

2

dengan xi = probabilitas pemain P1 memilih stategi ke- i yi = probabilitas pemain P2 memilih stategi ke- j Ternyata bahwa permainan ini tidak mempunyai titik pelana dan aturan dominasi tidak digunakan. Karena nilai maximin = -2, maka ada kemungkinan nilai permainannya negatif atau nol. Oleh karena itu, matriks pembayaran di atas perlu dimodifikasi dengan menambahkan konstanta positif k = 4 sedemikian rupa sehingga matriks pembayaran modifikasinya adalah

6


Pemain P2 y1

y2

y3

x1

6

3

1

Pemain P1 x2

2

4

5

x3

4

1

6

Penyelesaian dengan metode simpleks untuk pemain P2. Formulasi program linear berdasarkan matriks pembayaran modifikasi untuk pemain P2 adalah : 1 Memaksimumkan z = Y1 + Y2 + Y3 (= ) berdasarkan pembatas v 6Y1 + 3Y2 + Y3 ≤ 1 2Y1 + 4Y2 + 5Y3 ≤ 1 4Y1 + Y2 + 6Y3 ≤ 1 Y1, Y2, Y3 ≥ 0 Bentuk di atas dibawa ke bentuk kanonik dengan memasukkan pengubahpengubah kelonggaran (slack), misalnya P, Q, R. Kemudian mencari Y1, Y2, Y3, P, Q, R ≥ 0 yang memenuhi 6Y1 + 3Y2 + Y3 + P = 1 2Y1 + 4Y2 + 5Y3 + Q = 1 4Y1 + Y2 + 6Y3 + R = 1 Memaksimumkan z = Y1 + Y2 + Y3 + OP + OQ + OR. Maka, Y = [Yj] = [Y1, Y2, Y3, P, Q, R] v = [vi] = [v1, v2, v3] = [1, 1, 1] c = [cj] = [1, 1, 1, 0, 0, 0]

 6 3 1 1 0 0   A = (aij) =  2 4 5 0 1 0  4 1 6 0 0 1   METODE SIMPLEKS Metode Simpleks mulai diperkenalkan oleh George B. Dantzig pada tahun 1949 Metode penyelesaian masalah:

7


-

iterasi dengan langkah-langkah perhitungan yang sama

-

perhitungan yang sama diulang beberapa kali sebelum solusi optimum dicapai

Langkah-langkah penyelesaian metode Simpleks: 1. Tentukan model formulasi 2. Tambahkan slack variable pada setiap constraint 3. Buat tabel simpleks Persamaan constraint khusus untuk slack variable harus membentuk matriks identitas 4. Hitung zj dan zj - cj Bila zj - cj < 0 belum optimal, harus dibuat tabel baru 5. Tentukan kolom pivot = kolom di mana zj - cj paling kecil 6. Tentukan baris pivot = baris di mana Harga bagi paling kecil Harga bagi =

Harga jawab Elemen pada kolom pivot

7. Tentukan unsur pivot = unsur (elemen) yang menjadi anggota dari kolom pivot dan baris pivot 8. Menentukan variabel yamg masuk = variabel pada kolom pivot Menentukan variabel yang keluar = variabel pada baris pivot 9. Membuat tabel baru Bagi elemen-elemen pada baris pivot dengan unsur pivot 10. Hitung elemen-elemen untuk baris lain dengan ketentuan nij = nij - nip. npj nij = elemen pada baris ke-i dan kolom ke-j yang baru nij = elemen pada baris ke-i dan kolom ke-j (tabel lama) nip = elemen pada baris ke i kolom pivot lama npj = elemen pada baris pivot kolom ke-j (tabel baru) 11. Ulangi langkah nomor 4 sampai mendapatkan tabel optimal 12. Bila telah mendapatkan tabel optimal, tentukan hasil solusi optimal

8


Karena A telah tereduksi lengkap (memuat matriks identitas I3) maka bentuk matriks itu dikatakan siap simpleks. Tabel simpleks untuk pemain P2

ci

cj

1

1

1

0

0

0

Yj

Y1

Y2

Y3

P

Q

R

vi

Ri

Yi 0

P

6

3

1

1

0

0

1

1

0

Q

2

4

5

0

1

0

1

1

0

R

4

1

6

0

0

1

1

1

zj

0

0

0

0

0

0

zj-cj

-1

-1

-1

0

0

0

1

Y1

1

1

0

0

1

0

Q

0

3

14

1

0

2

0

R

0

-1

16

0

1

1

zj

1

1

0

0

zj-cj

0

−1

0

0

1

Y1

1

17

0

−1

32

0

Q

0

31

1

−7

8

1

Y3

0

0

3

zj

1

2

1

2 2

1

6

6

3

−1

3

3

−2

3

1

6

−5

6

1

6 6

6 3 3

0

3

0

1

−3 16

1

−1

1

11

1

1 16

0

5

zj-cj

0

− 21

0

1 16

0

5

1

Y1

1

0

0

19

− 11 124

11 124

13

1

Y2

0

1

0

2

8

−7

3

32 8

32 32

16 4 8

124

31

9

31

16

5 3

32 8

1 16

32 32

31

124

31

6 2 4

1 1

7

1 16

5 3

17 31

-1/3


1

Y3

0

0

1

−7

zj

1

1

1

13

zj-cj

0

0

0

13

3

62

9

62

62

124

21 124

1 124

124

21 124

1 124

5

62

35

124

Karena semua zj-cj > 0 maka telah tercapai optimum. Didapatkan bahwa z = 35 124

[

Y = [ Y1, Y2, Y3, P, Q, R ] = 13 , 3 , 5 ,0,0,0 124 31 62 Karena Yi =

]

yi 1 Y dan v = maka yi = i untuk i = 1, 2, 3. v z z

Diperoleh bahwa y1 =

Y1 13 124 13 = x = = y1* z 124 35 35

y2 =

Y2 3 124 12 = x = = y2* z 31 35 35

y3 =

Y3 5 124 10 = x = = y3* z 62 35 35

dan nilai permainan sebenarnya adalah v* =

1 124 16 −k = −4 = − z 35 35

 13 12 10  Jadi strategi campuran optimum pemain P1 adalah Y * =  , ,  dan nilai  35 35 35  permainan v * = −

16 . 35

Selanjutnya akan dicari solusi optimum untuk pemian P1 melalui dualitas (berdasarkan solusi optimum matriks modifikasi). Bagi pemain P1 Y1 = 13

124

>0

Y2 = 3

31

>0

Y3 = 5

62

>0

X1> 0

6

3

1

=1

X2> 0

2

4

5

=1

X3> 0

4

1

6

=1

=1

=1

=1

10


Masalah dual : 6X1 + 2X2 + 4X3 = 1 3X1 + 4X2 + X3 = 1 X1 + 5X2 + 6X3 = 1 Merupakan sistem persamaan linier non homogen dengan 3 variabel, yaitu X1, X2, X3 dan 3 persamaan. Sistem ini diselesaikan dengan aturan Cramer.

6 2 4 ∆ = 3 4 1 = 124 1 5 6 1 2 4 1 4 1 X1 =

1 5 6 ∆

=

13 124

=

21 124

=

1 124

6 1 4 3 1 1 X2 =

1 1 6 ∆ 6 2 1 3 4 1

X3 =

1 5 1 ∆

Diperoleh bahwa z = Karena X i =

1 35 = X1 + X 2 + X 3 = v 124

xi X 1 dan z = maka xi = i untuk i = 1, 2, 3. v v z

Diperoleh bahwa

x1 =

X 1 13 124 13 = x = = x1* z 124 35 35

x2 =

X2 21 124 21 = x = = x 2* z 124 35 35

11


x3 =

X3 1 124 1 = x = = x3* z 124 35 35

 13 21 1  x* =  , ,   35 35 35  Jadi solusi optimum permainan ini adalah  13 21 1  Strategi campuran pemain P1 adalah X * =  , ,   35 35 35   13 12 10  Strategi campuran pemain P2 adalah Y * =  , ,   35 35 35  Nilai permainan v * = −

16 35

Contoh 2 Matriks pembayaran yang telah dimodifikasi.

Pemain P2

Pemain P1

y1

y2

y3

x1

6

3

1

x2

2

4

5

x3

4

1

6

Formulasi dalam program linier untuk pemain P1 adalah 1 Meminimumkan z = X1 + X2 + X3 (= ) v berdasarkan pembatas 6X1 + 2X2 + 4X3 ≥ 1 3X1 + 4X2 + X3 ≥ 1 X1 + 5X2 + 6X3 ≥ 1 X1, X2, X3 ≥ 0

12


Bentuk di atas dibawa ke bentuk kanonik dengan menambahkan pengubah kelonggaran (slack), misalnya P, Q, R. Dicari X1, X2, X3, P, Q, R ≥ 0 yang memenuhi : 6X1 + 2X2 + 4X3 – P = 1 3X1 + 4X2 + X3 – Q = 1 X1 + 5X2 + 6X3 – R = 1 Memaksimumkan z = X1 + X2 + X3 + 0P + 0Q + 0R Ternyata bahwa

6 2 4 −1 0 0    A=  3 4 1 0 − 1 0   1 5 6 0 0 − 1   belum siap simpleks. Oleh karena itu perlu ditambah lagi dengan pengubah-pengubah semu (artificial variables), misalnya S, T, W sehingga Akan dicari X1, X2, X3, P, Q, R, S, T, W ≥ 0 yang memenuhi 6X1 + 2X2 + 4X3 – P + S = 1 3X1 + 4X2 + X3 – Q + T = 1 X1 + 5X2 + 6X3 – R + W = 1 Meminimumkan z = X1 + X2 + X3 + 0P + 0Q + 0R + MS + MT + MW dengan M = bilangan positif besar. Maka, X = [X1, X2, X3, P, Q, R, S, T, W] v = [vi] = [v1, v2, v3] = [1, 1, 1] C = [cj] = [1, 1, 1, 0, 0, 0, M, M, M]

6 2 4 −1 0 0 1 0 0   A = (aij) =  3 4 1 0 − 1 0 0 1 0  1 5 6 0 0 −1 0 0 1   Karena matriks A telah tereduksi lengkap maka matriks A dinamakan telah siap simpleks. Tabel simpleks untuk pemain P1 adalah sebagai berikut:

13

Didownload dari ririez.blog.uns.ac.id P1

cj

1

1

1

0

0

0

M

M

M

Yj

X1

X2

X3

P

Q

R

S

T

W

vi

Ri

6

2

4

-1

0

0

1

0

0

1

1

Yi M M M

M M 1

M 1 1

S T W

3

4

1

5

1

0

6

0

-1

0

0

0

-1

0

1

0

0

1

1

1

zj

10M

11M

11M

-M

-M

-M

M

M

M

zj-cj

10M-1

11M-1

11M-1

-M

-M

-M

0

0

0

S

28

0

8

-1

0

2

1

1

−2

T X2

11 1

5 0

5 1

5

5

− 19 6

0

-1

4

5 0

5 0

−1

0

5

−4

1

5 0

0

1

5

1

5

1

− 11 M + 6 5 5

-M

-M

6 M−1 5 5

M

M

−6 M + 1 5 5

zj-cj

39 M − 4 5 5

0

− 11 M + 1 5 5

-M

-M

6 M−1 5 5

0

0

−6 M − 1 5 5

S

0

0

124

-1

− 28

− 18

1

28

X1 X2 zj zj-cj

1 0 1 0

0 1 1 0

− 19 17

0

11 0

11

124 124

11 11

M −2

-M

11

-M M − 13 11

−5

4

11

11 0

11

5

−3 11

− 28 M − 4 11 11

− 18

11

M M−1 11

28

− 28

− 18

11

0 M−1 11

17

11

M −4

11 14

−1 11 11

11

11

−4

11

1 11

0

28

11

M +4

11

3 11

M +4

11

11

18 7

5 5

1

5

39 M + 1 5 5

11

1

3

5

zj

11

1

11

1 11

M−1 11

M−1 11

4 5

28

1 11 1

1 124

1 11 2

11

5

3

2

11

2

17

Didownload dari ririez.blog.uns.ac.id 1 1 1

X3 X1 X2 zj zj-cj

0 1 0 1 0

0 0 1 1 0

1 0 0 1 0

− 11 124

− 38

− 19

− 239

17

124

124

150

− 18

124

7

341

− 13 124

− 166

− 13 124

− 166

62

−3

341

−5

341

−5

341

15

124

62

11 124

28

19

239

124

− 17

124

18

124 341

− 150

62

13 124

166

62

13 −M 124

166

341

341

−7 3 5

341 −M

124

5

62

13 124 21 124

62

35

62 62

1 124

−M

124


Dari tabel tersebut dapat dilihat bahwa semua zj-cj ≤ 0. Karena semua zj-cj ≤ 0 maka optimum telah tercapai. Nilai optimumnya adalah 1 35 z = X1 + X2 + X3 (= ) = v 124 Solusi optimum X = [X1, X2, X3, P, Q, R, S, T, W]

 13 21 1  = , , ,0,0,0,0,0,0 124 124 124  Karena X i =

xi X 1 dan z = maka xi = i untuk i = 1, 2, 3. v v z

Diperoleh bahwa

x1 =

X 1 13 124 13 = = = x1* x z 124 35 35

x2 =

X2 21 124 21 x = = = x 2* z 124 35 35

x3 =

X3 1 124 1 = x = = x3* z 124 35 35

Dan nilai permainan sebenarnya adalah v * =

1 124 16 −k = −4= − z 35 35

 13 21 1  Jadi strategi campuran optimum pemain P1 adalah X * =  , ,  dan nilai permainan  35 35 35  v* = −

16 . Selanjutnya akan dicari solusi optimum untuk pemian P2 melalui dualitas 35

(berdasarkan solusi optimum matriks modifikasi). Bagi pemain P2 Y1 > 0

Y2 > 0

Y3 > 0

6

3

1

=1

X2 = 21 124

2

4

5

=1

X3 = 1 124

4

1

6

=1

=1

=1

=1

X1= 13

124

Masalah dual 6Y1 + 3Y2 + Y3 = 1 2Y1 + 4Y2 + 5Y3 = 1

16


4Y1 + Y2 + 6Y3 = 1 Sistem persamaan linier non homogen dengan tiga anu yaitu Y1, Y2, Y3 dan tiga persamaan ini diselesaikan dengan aturan Cramer.

6 3 1 ∆ = 2 4 5 = 124 4 1 6 1 3 1 1 4 5 Y1 =

1 1 6 ∆

=

13 124

=

12 124

=

10 124

6 1 1 2 1 5 Y2 =

4 1 6 ∆ 6 3 1 2 4 1

Y3 =

4 1 1 ∆

Diperoleh bahwa z = Karena Yi =

1 35 = Y1 + Y2 + Y3 = v 124

yi Y 1 dan z = maka yi = i untuk i = 1, 2, 3. v v z

Diperoleh bahwa

y1 =

Y1 13 124 13 = x = = y1* z 124 35 35

y2 =

Y2 12 124 12 = x = = y 2* z 124 35 35

y3 =

Y3 10 124 10 = = = y 3* x z 124 35 35

 13 12 10  Y* =  , ,   35 35 35  Jadi solusi optimum permainan ini adalah  13 21 1  o Strategi campuran optimum pemain P1 adalah X * =  , ,   35 35 35 

17


 13 12 10  o Strategi campuran optimum pemain P2 adalah Y * =  , ,   35 35 35 

o Nilai permainan v * = −

16 35

Dengan demikian terlihat bahwa penyelesaian simpleks untuk pemain P1 (pemain baris ) lebih rumit daripada penyelesaian simpleks untuk pemain P2. Oleh karena itu disarankan untuk menyelesaikan dengan metode simpleks bagi pemain P2 (pemain kolom) dahulu dan baru penyelesaian pemain P1 sebagai dualnya.

KESIMPULAN PENYELESAIAN BERJUMLAH NOL DARI DUA ORANG 1. Dalam studi kasus buatlah matriks pembayaran atau matriz permainannya terlebih dahulu. 2. Perhatikan baik-baik matriks pembayaran yang diberikan atau matriks pembayaran yang baru disajikan bila studi kasus. 3. Selidi apakah mempunyai titik pelana. 4. Kalau ditemukan titik pelana, maka permainan tersebut dapat diselesaikan dengan strategi murni. Kalau titik pelana tidak ditemukan maka permainan tersebut diselesaikan dengan strategi campuran. 5. Memeriksa apakah mtriks pembayaran dapat direduksi dengan aturan dominasi. 6. Selesaikan permainan ini dengan salah satu metode penyelesaian yang cocok.

•

Metode aljabar untuk ukuran 2 x 2

•

Metode grafik untuk ukuran 2 x 2, 2 x n, m x 2

•

Metode aljabar matriks dan metode program linier untuk usuran m x n

B. PERMAINAN BERJUMLAH NOL DARI n ORANG 1.

Pendahuluan Pada bab-bab sebelumnya telah dibahas tentang permainan berjumlah nol dari 2 orang, yaitu suatu permainan yang hanya memuat dua pertentangan kepentingan (oppositing

interest). Dalam bab ini akan sedikit dibahas tentang permainan berjumlah nol dari n orang. Perbedaannya dengan bab-bab sebelumnya adalah bahwa permainan pada babbab sebelumnya dimainkan hanya oleh dua orang (pihak) saja tetapi dalam bab ini jumlah pemainnya lebih dari dua orang (pemain). Ada dua asumsi yang dipakai di dalam pembahasan permainan berjumlah nol dari n orang ini, yaitu:

18


1.

Setiap pemain dalam permainan ini dapat berkomunikasi dan berunding dengan pemain yang lain untuk membuat suatu perjanjian yang mengikat. Hal ini berarti ada kerjasama di antara pemain. Barangkali perjanjian itu meliputi dua jenis, yaitu koordinasi strategi dan pembagian pembayaran. Jika suatu kelompok pemain menyatakan untuk bekerja sama maka mereka membentuk koalisi. Suatu koalisi adalah persetujuan di antara beberapa pemain untuk mengkoordinasikan strategi mereka yang ada dalam suatu cara (jalan) sedemikian sehingga seluruh anggota koalisi itu akan beruntung. Analisis mengenai bentuk koalisi inimerupakan bagian yang terpenting di dalam mempelajari permainan berjumlah nol dari n orang ini.

2. Para pemain dapat membuat pembayaran sampingan (side payment), yaitu suatu transfer (pemindahan) pembayaran di antara pemain. Oleh karena itu mereka akan membentuk suatu koalisi jika pembayaran-pembayaran itu sedemikian rupa sehingga anggota-anggota koalisi (melalui kerjasama) dapat mencapai total pembayaran untuk koalisi itu lebih besar daripada mereka bermain secara individu. Setelah koalisi memaksimumkan total pembayarannya, penbayaran untuk para anggota koalisi itu diatur dengan pembuatan pembayaran sampingan

(side

payment) itu. Sesuai dengan definisi permainan di sini maka diasumsikan bahwa pemain-pemain di dalam permainan n orang ini dapat dibagi menjadi dua kelompok (koalisi) yang saling berhadapan (besaing). Setelah terbentuk dua koalisi (kelompok), permainan n orang ini dapat diberlakukan sebagai permainan dua orang, yaitu koalisi I melawan koalisi II. Nilai permainan, yang mana terdaftar di dalam fungsi karakteristik untuk permainan ini adalah nilai maximin untuk koalisi I yang berarti bahwa minimum total pembayaran anggota-anggota koalisi I dapat diperoleh tanpa memperhatikan tindakan yang diberikan oleh anggota koalisi II. Oleh karena itu total pembayaran dari koalisi I sama dengan negatif dari total pembayaran koalisi II di dalam setiap vektor pembayaran dalam matriks pembayaran. 2.

Bentuk Koalisi Secara umum di dalam permainan berjumlah nol n orang terdapat 2n-1 cara yang mungkin untuk mengelompokkan n orang (pemain) itu ke dalam dua kelompok yang saling berhadapan. Misalnya, permainan yang berjumlah nol 4 orang (A, B, C, D). Para pemain dalam permainan ini dapat membentuk 24-1=8 koalisi yang berbeda yaitu: 19


Grup I melawan

Grup II

1. ABCD

Ø

2. ABC

D

3. ABD

C

4. ACD

B

5. BCD

A

6. AB

CD

7. AC

BD

8. AD

BC

Kalau dilihat pada bentuk koalisi yang kesatu, yaitu ABCD VS Ø maka jelas ini tidak dipakai di sini. Karena koalisi kosong (Ø) tidak mempunyai langkah, tidak mempunyai pengaruh, tidak ada keuntungan ataupun kerugian. Demikian juga komplemen dari koalisi kosong (Ø) ini, yaitu ABCD, walaupun mempunyai banyak anggota dan langkah juga tidak mempunyai pengaruh dan tidak ada kerugian atau keuntungan karena jelas bahwa koalisi ABCD ini tidak mempunyai lawan bersaingnya. Dengan membagi n orang (pemain) menjadi dua grup tersebut

maka permainan

berjumlah nol dari n orang ini dapat diberlakukan sebagai suatu permainan berjumlah nol dari dua orang (grup). Dengan demikian di dalam menghitung solusi optimumnya dapat menggunakan metode-metode untuk permainan berjumlah nol dari dua orang. Hanya ada sedikit perbedaan yaitu mengenai pembagian pembayaran untuk masing-masing anggota koalisi yang bersangkutan. Contoh 3 Diberikan permainan berjumlah nol dari 3 orang (A, B, C) dengan masing-masing pemain mempunyai 2 pilihan strategi. Misalnya: -

Pemain A mempunyai 2 strategi : X1, X2.

-

Pemain B mempunyai 2 strategi : Y1, Y2.

-

Pemain C mempunyai 2 strategi : Z1, Z2. Dengan matriks pembayaran di bawah ini.

20


Strategi A

Pembayaran B

C

A

B

C

X1

Y1

Z1

-1

1

0

X1

Y1

Z2

-3

2

1

X1

Y2

Z1

0

2

-2

X1

Y2

Z2

3

-2

-1

X2

Y1

Z1

-2

0

2

X2

Y1

Z2

0

-1

1

X2

Y2

Z1

-1

-2

3

X2

Y2

Z2

2

1

-3

Dari sini ada 3 koalisi yang mungkin, yaitu: Grup I melawan

Grup II

1. A

BC

2. B

AC

3. C

AB

Diselidiki untuk A melawan B, C; dengan matriks pembayarn sebagai berikut:

BC Y1 Z1 A

X1 X2

-1 -2

Y 1Z2

Y2 Z1

Y2 Z2

-3 0

0 -1

3 2

Dalam matriks pembayaran tabel ini tidak mempunyai titik pelana. Diselesaikan metode grafik. Misalnya x1 = probabilitas pemain A memainkan strategi kesatu. Pembayaran harapan pemain A yang berkaitan dengan strategi murni pemain (BC) adalah: Strategi murni pemain BC

Pembayaran harapan pemain A

1

x1 - 2

2

-3x1

3

x1-1

4

x1 + 2 21

Didownload dari ririez.blogg.uns.ac.id

Keempat garis lurus tersebut digambarkan sebagai fungsi dari x1 pada grafik dibawah

ini. Dan kolom olom ke 3 dan ke 4 pada tabel atau persamaan garis lurus (3) dan (4) didominasi oleh kolom ke 1 atau garis lurus (1). Dapat Dapat diperlihatkan pada grafik 1 di

bawah ini.

Grafik 1 Titik maximin dilalui oleh garis lurus (1) dan (2) maka:

x1 – 2 = -3x1 4x1 = 2

< = > x1 = ½ = x1

Sehinggaa berarti bahwa x2 = ½ dan nilai permainan v* = -

3 2

Sekarang strategi optimum pemain (BC) dengan dualitas. Misalnya Yj Y = probabilitas pemain (BC) memilih kolom ke j; j = 1, 2, 3, 4.

y1 > 0

y2 > 0

y3 > 0

y4 > 0

1 = x1 2

-1

-3

0

3

=

1 = x2 2

-2

0

-1

2

=

ǁ

ǁ

V

v

3 2

3 2

3 2

3 3 2

Dual: -y1 – 3y2 = -3/2 -2y1

= -3/2

< = > y1 =

3 = y1* 4

< = > y2 =

1 = y2* 4 22


1 1 Jadi strategi optimum pemain A adalah X* =  ,  2 2 3 1  Strategi optimum pemain BC adalah Y* =  , ,0,0 4 4 

dan v* = -

3 2

Diselidiki untuk B melawan AC dengan matriks pembayaran sebagai berikut: AC X1 Z1 B

Y1 Y2

X 1Z2 2 -2

1 2

X2 Z1 0 -2

X2 Z2 -1 1

Ternyata tidak mempunyai titik pelana dan ke 1 dan 2 didominasi oleh kolom ke 3. misalnya x1 = probabilitas pemain B memilih strategi ke 1. Pembayaran harapan

pemain B yang berkaitan dengan strategi murni pemain (AC) adalah: Strategi murni pemain AC

Pembayaran harapan pemain B

3

2x1-2

4

1 - 2x1

Ketiga garis lurus ini digambarkan sebagai fungsi dari x1 pada grafik 2 di bawah ini.

Grafik 2

Ternyata titik maximum dilalui oleh garis lurus (3) dan (4) maka

2 2 1 2 4 3 ⇔ 23

3 ∗ 4


⇔ = = ∗ dan

v* = −

1 2

Strategi optimum bagi pemain AC dengan dualitasnya. Misalnya = probabilitas pemain AC memilih strategi ke j; j = 3,4

x1 = x2 =

y3

y4

0

-1

=−

-2

1

=−

ǁ

ǁ

−

1 2

−

1 2

Dual

−4 = −

1 2

−2 + = −

1 = ∗ 2 1 ⇔ = = ∗ 2

⇔ = 1 2

Jadi strategi optimum pemain B adalah

∗ = 0,0, ,

Strategi optimum pemain AC adalah dan v * = −

∗ = ,

1 2

3. Untuk C melawan AB dengan matriks pembayaran : AB

C

Z1 Z2

X1,Y1

X1,Y2

X2,Y1

0 1

-2 -1

2 1

X2,Y2 3 -3

Ternyata tidak mempunyai titik pelana dan kolom ke 1 dan 3 didomonasi oleh kolom ke 2. Misalnya = probabilitas pemain C memilih langkah ke 1. Pembayaran harapan pemain C yang berkaitan dengan strategi murni AB.

24


Strategi murni pemain AB

Pembayaran harapan pemain C

2

-x1-1

4

6x1-3

Kedua garis lurus ini digambarkan sebagai fungsi dari x1 pada da grafik 3 dibawah ini.

Grafik 3 Karena titik maximum dilalui oleh dua garis lurus, yaitu (1) dan (4) maka 1 7 2

6 3 2 ∗ 7

⇔

⇔ ∗

dan

∗

Strategi optimum pemain AB melalui dualitas. Misalnya Yj = probabilitas pemain AB memilih strategi kej;j=2,4

x1 =

x2 =

y2 > 0

y4 > 0

-2

3

=

-1

-3

=

ǁ

ǁ

9 7

Dual : 2 3

3 3

⇔ ∗

⇔ ∗

25

9 7


∗ = ,

Jadi Strategi optimum pemain C adalah Strategi optimum pemain C adalah

∗ = 0, , 0,

dan ∗ = Dengan demikian didapatkan bahwa : Nilai permainan untuk A yaitu

!"# = −

,

Nilai permainan untuk B yaitu

!$# = −

,

!"%# =

!%# = −

,

!"$# =

Nilai permainan untuk C yaitu

!$%# =

Sekarang timbul permasalahan mengenai bagaimana pembagian (pendistribusian) pembayaran

setiap

pemain/anggotanya.

Aturan

pendistribusian

(pembagian)

pembayaran setiap pemain (anggota) dikenal dengan imputasi (imputations) C. IMPUTASI Imputasi adalah suatu distribusi (pembagian) yang mungkin dari pembayaran yang tersedia yang dinyatakan sebagai vektor pembayaran untuk suatu permainan yang memenuhi kriteria. 1.

Jumlah dari pembayaran-pembayaran tiap individu (pemain ) harus sama dengan nol (karena permainan berjumlah nol). Dalam permainan berjumlah nol dari n oramg yang bekerja sama (membentuk koalisi) dapat disajikan suatu imputasi sebagai vektor pembayaran P = [p1, p2, p3, ..., pn] dengan Pi

I menyatakan suatu besaran pembayaran

yang diterima oleh pemain ke i ∈ I = {1, 2, ..., n}. Ini dapat disajikan sebagai

∑p i∈I

2.

i

=0

Pembayaran untuk setiap pemain harus lebih besar atau sama dengan pembayaran yang dapat diperolehnya secara individu. Dapat disajikan sebagai pi ≥ v ({i}), untuk semua i ∈ I, dengan v ({i}) adalah nilai permainan untuk pemain ke – i.

Contoh 4 Pada contoh 3 didapatkan bahwa V(A) = -1,5

V(AC) = 1,5

V(B) = -0,5

V(AC) = 0,5

V(C) = - 1.286

V(AB) = 1,286

Sebagai imputansi – imputansi yang berbentuk vector [PA, PB, PC] adalah 26


[-15, 0,5, 1] [0,5, -0,25, 0,25] [0,75, 0,25, -1] dan sebagainya . Contoh yang bukan imputansi : [0,2, -0,7, 0,5] karena -0,7 < 0,5 [-2, 1,5, 0,5] karena -2 < 1,5

Dari contoh 4 di atas ternyata bahwa terdapat banyak (bahkan tak berhingga jumlahnya) imputansi dari permainan n orang itu sehingga yang menjadi masalah adalah untuk mendapatkan kriteria yang memungkinkan kita untuk menentukan salah satu imputansi terpilih dari imputansi-imputansi yang lain. Kriteria ini dinamakan criteria dominasi. Misalnya diberikan dua imputansi yang berbeda P1 dan P2. Imputansi P1 dikatakan mendominasi imputan P2 untuk suatu koalisi jika pembayaran-pembayaran untuk semua anggota koalisi itu lebih besar untuk P1 daripada untuk P2 dan jika total pembayaran untuk koalisi itu adalah cukup besar untuk menyediakan pembayaran secara individu yang diberikan P1.

Contoh 5 Perhatikan contoh 4. Misalkan P1= [-1,5 , 0,5 , 1] dan P2= [ 0,5 , -0,25 , -0,25] Maka P1 mendominasi P2 untuk menjadi koalisi (BC) 1,5 Karena [-1,5 , 0,5 , 1] > [ 0,5 , -0,25 , -0,25] > >

Tetapi P2 tidak mendominasi P1 untuk koalisi BC karena [ 0,5 , -0,25 , -0,25] ≯ [-1,5 , 0,5 , 1] <

<

27


D. DOMINANSI DARI IMPUTASI Untuk mengetahui apakah suatu imputasi lebih baik dibandingkan imputasi lainnya, yaitu dengan melihat pada dua imputasi x dan y. Karena

∑x i∈N

i

= v(N ) = ∑ y i i∈N

jika untuk suatu i berlaku xi > y i maka pasti terdapat j sedemikian sehingga y j > x j . Sebab suatu imputasi tidak lebih baik dari imputasi yang lain untuk suatu pemain, tetapi terdapat kemungkinan untuk suatu koalisi istimewa, x lebih baik daripada y untuk setiap anggota. Jadi bisa dikehendaki suatu koalisi yang kuat untuk mendapatkan imputasi yang lebih baik. Berikut ini definisi mengenai dominasi dari imputasi. Definisi 1. (Parthasarathy dan Raghavan, 1971: 220-221) Misalkan x = ( x1 , x 2 , K , x n ) dan y = ( y1 , y 2 , K , y n ) imputasi untuk permainan kooperatif n-pihak dimana v adalah fungsi karakteristik, dan S adalah himpunan bagian dari himpunan pemain. Imputasi

(x1 , x2 ,K, xn )

mendominasi imputasi ( y1 , y 2 , K , y n ) , yang dinotasikan x f y, pada S jika

memenuhi: 1) S ≠ Ø 2)

∑x i∈S

i

≤ v (S )

3) xi > y i , ∀i ∈ S Dari definisi tersebut dapat dikatakan bahwa x f y jika terdapat suatu himpunan yang tidak kosong S ⊆ N sedemikian sehingga

∑x i∈S

i

≤ v(S ) dan xi > y i , ∀i ∈ S . Jika x

f y pada S (dinotasikan x f S y), maka S harus memuat paling sedikit dua dan paling i dan x f S y maka y i < xi ≤ v({} banyak (n − 1) anggota. Sebab jika S = {} i ) . Kondisi (2) pada Definisi 1 dilanggar. Jika S = N dan x f N y maka xi > y i untuk setiap i ∈ N sehingga

∑x > ∑y i∈N

i

i∈N

i

= v( N )

Maka x bukan imputasi karena tidak memenuhi kondisi (1) pada Definisi 1. Jika x f S y, maka kedua kondisi berikut harus benar yaitu (Winston, 1994: 856): 28


1. Tiap anggota dari S lebih memilih x daripada y 2. Karena ∑ xi ≤ v(S ) , anggota S mendapat perolehan yang diberikan x i∈S

Kondisi (1) sesuai dengan kondisi (3) pada Definisi 2, sedangkan kondisi (2) menghendaki bahwa perolehan yang diberikan x cukup menjamin anggota S. Definisi 2 (Thomas, 1984: 91) x dikatakan mendominasi y (x f y) jika x mendominasi y untuk suatu koalisi S. Jika terdapat dua imputasi dengan perolehan bagi beberapa pihak pada imputasi yang satu lebih besar daripada perolehan dari imputasi yang lain, maka pihak tersebut cenderung memilih imputasi yang paling menguntungkan baginya. Berikut ini akan diberikan contoh mengenai dominasi dari imputasi. Contoh 5: Jika x = (0, 12 , 12 ) dan y = ( 12 , 14 , 14 ) Maka x mendominasi y untuk koalisi {2,3} karena 1

(0, 12 , 12 )

( 12 , 14 , 14 )

f > >

Gambar 1. x mendominasi y untuk koalisi {2,3} Tetapi y tidak mendominasi x untuk koalisi {2,3} karena

( 12 , 14 , 14 )

(0, 12 , 12 )

f < <

Gambar 2. y tidak mendominasi x untuk koalisi {2,3} E. PUSAT IMPUTASI (CORE) Pusat imputasi merupakan salah satu konsep solusi yang penting untuk permainan kooperatif n-pihak, dan didefinisikan secara eksplisit oleh Gillies (1959). Konsep solusi ini didasarkan pada penggunaan ide dominasi dari imputasi.

29


Sebelum membuktikan bagaimana menentukan pusat imputasi dari permainan kooperatif n-pihak, terlebih dahulu akan diberikan pengertian pusat imputasi. Pusat imputasi didefinisikan sebagai berikut. Definisi 3. (Jones, 1980: 200) Himpunan semua imputasi yang tidak terdominasi pada permainan kooperatif n-pihak disebut pusat imputasi. Pusat imputasi suatu permainan dengan fungsi karakteristik v dinotasikan dengan

C (v ) . Kerugian yang mungkin timbul dalam mencari solusi permainan kooperatif n-pihak dengan menggunakan konsep ini adalah pusat imputasi kosong. Untuk lebih memahami konsep solusi di atas, akan diberikan sebuah contoh sebagai berikut. Contoh 6: Diketahui fungsi karakteristik dari permainan sebagai berikut:

v(Ø) = v({1}) = v({2}) = v({3}) = 0 v({1,2}) = v({1,3}) = v({2,3}) = 1 v({1,2,3}) = 1 Tentukan pusat imputasi dari permainan tersebut. Jawab: Misalkan x = ( x1 , x 2 , x3 ) merupakan pusat imputasi Perolehan terbesar yang didapat jika semua pemain yaitu pemain 1, 2 dan 3 bekerjasama dalam satu koalisi adalah 1 yaitu x1 + x 2 + x3 = 1 Jika pemain 1 dan 2 bekerjasama dalam satu koalisi, maka perolehan yang didapat paling sedikit sebanyak 1 yaitu

x1 + x2 ≥ 1 Jika pemain 1 dan 3 bekerjasama dalam satu koalisi, maka perolehan yang didapat paling sedikit sebanyak 1 yaitu x1 + x3 ≥ 1 Jika pemain 2 dan 3 bekerjasama dalam satu koalisi, maka perolehan yang didapat paling sedikit sebanyak 1 yaitu x 2 + x3 ≥ 1 30


Jika x1 + x 2 + x3 = 1

x1 + x2 ≥ 1 mengakibatkan x3 ≤ 0 x1 + x3 ≥ 1 mengakibatkan x2 ≤ 0 x 2 + x3 ≥ 1 mengakibatkan x1 ≤ 0 Kontradiksi dengan pengandaian bahwa x1 + x 2 + x3 = 1 . Jadi tidak terdapat x = ( x1 , x 2 , x3 ) ∈ C (v ) dengan kata lain C (v ) = Ø. F. NILAI SHAPLEY (SHAPLEY VALUE) Terdapat konsep solusi alternatif lain untuk permainan kooperatif n-pihak, yaitu Nilai Shapley, yang dikemukakan oleh Lloyd Shapley (1953). Konsep ini memberikan solusi yang lebih adil dibandingkan pusat imputasi. Shapley melihat bahwa tiap pemain dapat membayangkan harapan perolehannya sebelum permainan dimulai. Menurut Shapley, ada tiga aksioma yang harus dipenuhi oleh suatu Φ i (v ) , dengan Φ i (v ) merupakan harapan perolehan pemain ke-i dalam permainan dengan fungsi karakteristik v. Ketiga aksioma tersebut adalah: S1

Φ i (v ) haruslah independen dari penomoran pemain. Jika π adalah permutasi 1,2, K , n dan πv adalah fungsi karakteristik dari permainan dengan nomor pemain

telah dipermutasi oleh π , maka Φ π (i ) (π v ) = Φ i (v )

S2

Jumlah

seluruh

(1) harapan

perolehan

pemain

sama

dengan

harapan

perolehan maksimum dalam permainan, jadi

∑ Φ (v ) = v(N ) i∈N

S3

(2)

i

Jika u,v adalah fungsi karakteristik dari dua permainan, u + v adalah fungsi karakteristik dari permainan yang dimainkan bersama-sama, maka Φ memenuhi: Φ i (u + v ) = Φ i (u ) + Φ i (v )

(3)

Selanjutnya Shapley membuktikan bahwa terdapat satu fungsi yang memenuhi ketiga aksioma di atas, yang dituangkan dalam teorema berikut. Teorema 1. (Thomas, 1984: 102) Hanya terdapat satu fungsi yang memenuhi S1, S2 dan S3 yaitu: Φ i (v ) =

∑

S :i∈S

(# S − 1)!(n−# S )! (v(S ) − v(S \ {} i )) n!

31

(4)


dengan penjumlahan atas semua koalisi S yang memuat pemain i dan #S adalah jumlah pemain dalam koalisi S. Φ i (v ) merupakan nilai Shapley. Contoh 7: Diketahui fungsi karakteristik dari permainan sebagai berikut:

v(Ø) = v({1}) = v({2}) = v({3}) = 0 v({1,2}) = v({1,3}) = v({2,3}) = 1 v({1,2,3}) = 1 Tentukan nilai Shapley dari permainan tersebut. Jawab: Φ1 =

0!2! (0) + 1!1! (1) + 1!1! (1) + 2!0! (1 − 1) = 1 3! 3! 3! 3! 3

Dengan sifat simetri, Φ 1 = Φ 2 = Φ 3 =

1

3

.

Sehingga x= ( 13 , 13 , 13 ) .

32

Didownload dari ririez.blog.uns.ac.id

Recommend Documents