Pertemuan minggu pertama (2 x 50 menit)ftp.gunadarma.ac.id/handouts/S1_Sistem Informasi.1... · Web viewVB X1 X2 S1 S2 NK Z 0 0 5/2 ¼ 23.75 X2 0 1 5/2 -1/4 1.25 X1 1 0 -3/2 ¼ 3.75

Pertemuan minggu ke-1 (2 x 50 menit)

Pemrograman Bulat Linear (Integer Linear Programming - ILP)

Tujuan Instruksional Umum : Mahasiswa dapat menggunakan algoritma yang ada pada

metode pemrograman bulat untuk mendapatkan solusi

optimal permasalahan pemrograman linier, sehingga

diharapkan dapat membuat program aplikasinya.

Tujuan Instruksional Khusus :

1. Mahasiswa mengerti pentingnya penggunaan pemrograman bulat.

2. Mahasiswa dapat memahami algoritma metode Branch and Bound.

Apa itu Pemrograman Bulat

Metode simpleks (OR1) solusi optimal mungkin tidak integer.

Bayangkan misalnya jika kita tertarik untuk menentukan solusi optimal dari satu lini

perakitan televisi, yang memproduksi beberapa tipe televisi.

Mengganggu batasan

ILP

Catatan kuliah Riset Operasional 2, jurusan Sistem Informasi dan Teknik Informatika, dosen Hotniar Siringoringo, hal. 1

Pembulatan matematis ?

Metode Branch and bound

Algoritma:

Asumsikan permasalahan maksimisasi. Berikan z sebagai batas bawah solusi optimum

ILP.

1. Fathoming/Bounding. Pilih LPi sebagai subproblem untuk dibulatkan. Selesaikan

untuk LPi dan usahakan fathom.

Fathom dipenuhi jika salah satu kondisi ini dipenuhi:

1. subproblem menghasilkan solusi integer layak permasalahan ILP.

2. subproblem tidak dapat menghasilkan solusi yang lebih baik dari solusi batas

bawah terbaik yang ada (z) permasalahan ILP yang ada.

a. Jika LPi fathomed, perbaharui batas bawah z jika solusi ILP lebih baik.

Jika tidak, pilih subproblem yang baru dan ulangi ulangi langkah 1. jika

semua subproblem sudah diselidiki, stop. Solusi optimum ILP adalah z

batas bawah terakhir, jika ada. Jika tidak ada :

b. Jika LPi belum fathomed, teruskan ke langkah 2.

2. Branching (pencabangan). Pilih satu variabel xj yang nilai optimumnya tidak

memenuhi batasan integer. Hilangkan daerah , (dimana [A]

menunjukkan integer terbesar sedemikian shg £ A) dengan membuat dua subproblem

LP yang sesuai dengan 2 pembatas mutually exclusive :

dan

Kembali ke langkah 1.

Contoh :

Maks

Sub to :

Dengan simpleks, solusi optimal untuk kasus tersebut ditunjukkan tabel berikut:


VB X1 X2 S1 S2 NK

Z 0 0 5/2 ¼ 23.75

X2 0 1 5/2 -1/4 1.25

X1 1 0 -3/2 ¼ 3.75

Batasan integer untuk varaibek x1 dan x2 tidak dipenuhi, dimana nilai optimal masing-

masing secara berturut-turut adalah 3.75 dan 1.25. Solusi ini kita sebut sebagai LP0.

Penyelesaian dengan ILP :

1. Branching : pilih x1, maka batasan baru x1 £ 3 dan x1 ³ 3+1 (atau x1 ³ 4). Pilih

batasan x1 £ 3 (ini akan menjadi LP1), maka model matematik menjadi :

Maks

Sub to :

Selesaikan dengan simpleks, maka didapat tabel optimal:

VB X1 X2 S1 S2 S3 NK

Z 0 0 4 0 1 23

X2 0 1 1 1 -1 2

S2 1 0 0 0 -4 3

X1 0 0 0 0 1 3

2. solusinya memenuhi batasan integer (x1 = 3, x2 = 2 dan z = 23), sehingga dikatakan

LP1 sudah fathomed. Solusi ini adalah batas bawah.


LP1

2. Branching : Pilih batasan x1 ³ 4, maka model matematik menjadi :

Maks

Sub to :

Selesaikan dengan dual simpleks, maka didapat tabel optimal:


Z 0 0 0 2/3 5/3 23.333

S1 0 1 1 -1/6 -2/3 1/6

X2 1 0 0 1/6 5/3 5/6

X1 0 0 0 0 -1 4

3. solusinya belum memenuhi batasan integer (x1 = 4, x2 = 5/6 dan z = 23.333),

sehingga harus dibuat pencabangan.

Dari LP2, terbentuk cabang x2 ³ 1 dan x2 £ 0, demikian seterusnya sampai semua

cabang-cabangnya sudah ditelusuri.

Secara lengkap, cabang-cabang penyelesaian dari LP0 dengan memilih X1 untuk memulai

pencabangan LP1 dan seterusnya ditunjukkan oleh gambar 1 di bawah:

Maka solusi optimal ILP adalah solusi LP1.


LP2

X1 £ 4X1 ³ 5

X2 £ 0X2 ³ 1

X1 = 4; X2 = 0.8333; Z = 23.333

X1 = 3.75; X2 = 1.25; Z = 23.75

X1 = 3; X2 = 2; Z = 23

X1 = 4; X2 = 0; Z = 20

X1 = 4.5; X2 = 0; Z = 22.5Tidak ada solusi

Tidak ada solusi

LP0

LP1

LP3

LP2

LP4

LP5LP6

X1 £ 3X1 ³ 4

Gambar 1. Pohon penyelesaian ILP

Pertemuan minggu ke-2 (2 x 50 menit)

Metode Cutting-Plane


Mahasiswa dapat memahami algoritma metode Cutting-Plane dengan pure dan mixed

integer.

Perhatikan tabel simpleks berikut:

VB X1 ... Xi ... Xm W1 ... Wj ... Wn NK

Z 0 ... 0 ... 0 ... ...

X1 1 ... 0 ... 0 ... ...

. . ... . . . . . .


.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

Xi 0 ... 1 ... 0 ... ...

.

.

.

.

.

.

... .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

Xm 0 ... 0 ... 1 ... ...

Pure Integer

Digunakan jika semua variabel keputusan harus integer.

Algoritma Pure integer :

Input : solusi optimal primal simpleks.

1. Tentukan baris sumber baris variabel keputusan yang akan dibulatkan.

Jika lebih dari satu, boleh dipilih sembarang.

, tidak integer.

2. buat ke dalam bentuk fractional cut penambahan kendala baru.

atau

VB X1 ... Xi ... Xm W1 ... Wj ... Wn Si NK

Z 0 ... 0 ... 0 ... ... 0

X1 1 ... 0 ... 0 ... ... 0

.

.

.

.

... .

.

.

.

.

.

.

.

.

.

.

.

.

.


. . . . . . . . .

Xi 0 ... 1 ... 0 ... ... 0

.

.

.

.

.

.

... .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

Xm 0 ... 0 ... 1 ... ... 0

Si 0 ... 0 ... 0 -fi1 ... -fij ... -fin 1 -fi

3. selesaikan dengan dual simpleks.

Contoh Kasus :

Maks

Sub to :

positif dan bulat.

Solusi optimalnya dengan simpleks adalah :

VB X1 X2 S1 S2 NK

Z 0 0 28/11 15/11 63

X2 0 1 7/22 1/22 7/2

X1 1 0 -1/22 3/22 9/2

1. Ambil baris X2 sebagai baris sumber :

atau

2. Maka fractional cutnya adalah :

Dan tabel simpleksnya adalah :



Z 0 0 28/11 15/11 0 63

X2 0 1 7/22 1/22 0 7/2

X1 1 0 -1/22 3/22 0 9/2

S3 0 0 -7/22 -1/22 1 -1/2

3. Dengan dual simpleks, solusi optimalnya adalah :


Z 0 0 0 1 8 59

X2 0 1 0 0 1 3

X1 1 0 0 1/7 -1/7

S1 0 0 1 1/7 -22/7

Solusi belum bulat, sehingga baris sumber dan fractional cut baru harus dibentuk.

1. X1 sebagai baris sumber :

atau

2. Maka fractional cutnya adalah :

Dan tabel simpleksnya adalah :

VB X1 X2 S1 S2 S3 S4 NK

Z 0 0 0 1 8 0 59

X2 0 1 0 0 1 0 3

X1 1 0 0 1/7 -1/7 0

S3 0 0 1 1/7 -22/7 0

S4 0 0 0 -1/7 -6/7 1 -4/7


3. Dengan dual simpleks, solusi optimalnya adalah :

VB X1 X2 S1 S2 S3 S4 NK

Z 0 0 0 0 2 7 55

X2 0 1 0 0 1 0 3

X1 1 0 0 0 -1 1 4

S1 0 0 1 0 -4 1 1

S2 0 0 0 1 6 -7 4

Maka solusi optimal ILPnya adalah : X1 = 4, X2 = 3 dan Z = 55.

Mixed Integer

Digunakan jika tidak semua variabel keputusan harus integer.

Algoritma mixed integer :

1. Tentukan baris sumber dengan memilih salah satu variabel yang akan dibulatkan

dari tabel optimal simpleks :

supaya xk integer, maka atau harus dipenuhi, dengan demikian :

2. definisikan himpunan subscript j dimana

= himpunan subscript j dimana

dan


mixed cut :

3. Masukkan ke tabel simpleks sebelumnya dan selesaikan dengan dual simpleks.

Maks

Sub to :

positif

x1 bulat.

Solusi optimalnya dengan simpleks adalah :

VB X1 X2 S1 S2 NK

Z 0 0 28/11 15/11 63

X2 0 1 7/22 1/22 7/2

X1 1 0 -1/22 3/22 9/2

Baris sumber (baris x1, karena hanya x1 yang akan dibulatkan) :

, ,

Mixed cut :

atau

Tabel simpleks :



Z 0 0 28/11 15/11 0 63

X2 0 1 7/22 1/22 0 7/2

X1 1 0 -1/22 3/22 0 9/2

S3 0 0 -1/22 -3/22 1 -1/2

Solusi optimalnya :


Z 0 0 23/11 0 10 58

X2 0 1 10/33 0 -1/3 10/3

X1 1 0 -1/11 0 1 4

S2 0 0 1/3 1 -22/3 11/3

Pertemuan minggu Ke-3 (2 x 50 menit)

Model Jaringan


model jaringan untuk mendapatkan solusi optimal

permasalahan pemrograman linier, sehingga diharapkan

dapat membuat program aplikasinya.


1. Mahasiswa dapat memahami dan menggunakan algoritma minimum spanning tree.

2. Mahasiswa dapat memahami dan menggunakan algoritma rute terpendek asiklik.

Apa itu Model Jaringan?

Perhatikan situasi berikut:


1. Disain jaringan pipa gas alam yang menghubungkan Arun Aceh dengan tangki

penampungan Pertamina di salah satu kota dengan tujuan minimisasi biaya

pemasangan pipa.

2. penentuan rute terpendek yang menghubungkan dua kota pada jaringan jalan yang

sudah ada.

3. penentuan kapasitas maksimum tahunan (dalam ton) jaringan pipa coal slurry yang

menghubungkan pertambangan dengan daerah pusat pembangkit energi.

4. penentuan jadwal aliran biaya-minimum dari pertambangan ke kilang pemurnia

dan akhirnya ke pusat pendistribusian minyak.

Jaringan adalah himpunan simpul yang dihubungkan oleh garis atau kurva.

Notasi standar jaringan G : G = (N,A).

Predecessor adalah aktivitas yang mendahului suatu aktivitas tertentu.

Successor adalah aktivitas yang mengikuti suatu aktivitas tertentu.

Algoritma Minimum Spanning Tree.

Asumsikan himpunan C sebagai himpunan simpul yang terhubung dan sebagai

himpunan simpul yang tidak terhubung.

Solusi Awal : C = { } dan beranggotakan semua simpul.

Pilih sembarang simpul sebagai titik awal, maka C sekarang memiliki satu

anggota dan berkurang satu.

Hubungkan simpul itu dengan simpul terdekat. C bertambah satu dan berkurang

satu.

Hubungkan salah satu dari kedua simpul yang ada pada C dengan simpul terdekat,

maka C bertambah satu lagi dan berkurang satu.

Demikian seterusnya sampai ={ } dan setiap simpul sudah terhubung.

Contoh :

Seorang petugas lapangan di The National Park Service setiap hari harus berkendaraan

menggunakan mobil untuk memantau empat lokasi yang ada di taman. Setiap area harus

dia kunjungi sekali, berangkat dari dan berakhir di pintu masuk. Area-area tersebut


beserta jarak jalan yang sudah dibangun ( dalam mil) antara satu area dengan area lainnya

ditunjukkan tabel di bawah.

Pintu

Masuk

air terjun Batu

Raksasa

Sunset

Point

The

Meadow

Pintu Masuk - 7.1 19.5 19.1 25.7

Air Terjun 7.1 - 8.3 16.2 13.2

Batu Raksasa 19.5 8.3 - 18.1 5.2

Sunset Point 19.1 16.2 18.1 - 17.2

The Meadow 25.7 13.2 5.2 17.2 -

Penyelesaian :

Jaringan dari kasus di atas adalah:

Solusi Awal : C = { PM} = {AT, BR, SP, TM}

Iterasi 1 : C = {PM, AT} = {BR, SP, TM}, Total jarak = 7.1

Iterasi 2 : C = {PM, AT, BR} ={SP, TM}, Total jarak = 15.4

Iterasi 3 : C = {PM, AT, BR, TM} = { SP}, Total jarak = 20.6

Iterasi 4 : C = {PM, AT, BR, TM, SP} ={ }, Total jarak = 36.8

Solusi Optimum :


PM

AT

BR

SP

TM5.2

19.2

7.1 16.2

8.313.2

17.219.5

25.718.1

PM

AT

BR

SP

TM5.2

7.1 16.2

8.3

Rute Terpendek.

Acyclic

Jaringan asiklik kalau tidak memuat loop.

Algoritma :

Berikan uj = jarak terpendek dari simpul 1 ke simpul j, maka u1 = 0.

Hitung uj untuk j=2, 3, ... secara rekursif dengan rumus berikut:

ui = jarak terpendek ui ke simpul yang langsung mendahului.

dij = jarak antara simpul j dengan semua predecessor i.

Label [d,n] dimana d adalah total jarak dari simpul awal dan n adalah predecessor

langsung.

Contoh :

Tentukan rute terpendek!!!

Penyelesaian :

Simpul jPerhitungan uj Label

1

2

3

4

5

u1 = 0

u2 = u1 +d12 = 0+2 = 2, dari 1

u3 = u1 +d13 = 0+4 = 4, dari 1

u4 = min {u1 +d14 , u2 +d24 , u3 +d34 }= min {0+10, 2+11, 4+3} = 7,

dari 3

u5 = min { u2 +d25 , u4 +d45 }= min {2+5, 7+8} = 7, dari 2

[0, -]

[2, 1]

[4, 1]

[7, 3]

[7, 2]


5

1

1

108

4

2

63

5

743

2

7

6

9

11

6

7

u6 = min {u3 +d36 , u4 +d46 }= min {4+1, 7+1} = 5, dari 3

u7 = min {u5 +d57 , u6 +d67 }= min {7+6, 5+9} = 13, dari 5

[5, 3]

[13, 5]

Pertemuan minggu Ke-4 (2 x 50 menit)Tujuan Instruksional Khusus :

1. Mahasiswa dapat memahami dan menggunakan algoritma rute terpendek siklik.

2. Mahasiswa dapat memahami dan menggunakan algoritma aliran maksimum.

Siklik

Jaringan siklik memuat loop Algoritma Dijkstra digunakan.

Algoritma siklik menggunakan 2 label, yaitu label sementara dan label permanen.

Iterasi 0 : simpul 1 diberi label pemanen [0, -].

Iterasi 1 : simpul 2 label sementara [2, 1], simpul 3 label sementara [4, 1] dan simpul 4

label sementara [10, 1] min [2, 1] maka simpul 2 diberi label

permanen.

Iterasi 2 : dari simpul 2 (simpul terakhir dengan label permanen) simpul 3 dapat

label sementara lagi [2+7, 2], simpul 5 label sementara [2+5, 2]. Dari [4, 1],

[10, 1], [9, 2] dan [7, 2] minimum adalah [4, 1], maka [4, 1] menjadi label

permanen.

Iterasi 3 : label sementara berikutnya bertambah dengan [7, 3] simpul 4 dan [5, 3] simpul

6. Label [5, 3] menjadi permanen.


1

1

108

4

2

63

5

743

2

7

6

9

117

5

Iterasi 4 : [14, 6] menjadi label sementara. Sehingga label sementara sekarang menjadi

[10, 1], [7, 2], [9, 2], [7, 3], [14, 6]. Label [7, 3] menjadi label permanen.

Iterasi 5 : label [15, 4] menjadi label sementara, sehingga label sementara menjadi [7, 2],

[9, 2], [14, 6], [15, 4]. Label [7, 2] menjadi label permanen.

Iterasi 6 : label sementara bertambah dengan [13, 5], sehingga menjadi [9, 2], [14, 6], [15,

4], [13, 5]

Iterasi Label sementara Label permanen Simpul

0. - [0, -] 1

1. [2, 1], [4, 1], [10, 1] [2, 1] 2

2. [4, 1], [10, 1], [7, 2], [9, 2] [4, 1] 3

3. [10, 1], [7, 2], [9, 2], [7, 3], [5, 3] [5, 3] 6

4. [10, 1], [7, 2], [9, 2], [7, 3], [14, 6] [7, 3] 4

5. [7, 2], [9, 2], [14, 6], [15, 4] [7, 2] 5

6. [10, 1], [9, 2], [14, 6], [15, 4], [13, 5] [13, 5] 7

Maka rute terpendek dari simpul 1 ke simpul 7 adalah : 1 2 5 7,

dari simpul 1 menuju 6 adalah : 1 3 6, demikian seterusnya.

Aliran Maksimum

Digunakan untuk jaringan yang mempunyai kapasitas terbatas. Jaringan tidak berarah

dalam arti aliran dimulai dari simpul sumber dan berakhir pada simpul tujuan. Arkus (i,j)

mungkin mempunyai 2 arah kapasitas, dari i ke j atau dari j ke i.

Ide dasar algoritma : mencari jalur yang menghubungkan sumber dan tujuan sedemikian

sehingga kapasitas arkus pada jalur adalah positif.

Contoh kasus :


Pendistribusian minyak dari 3 lokasi kilang pemurnian ke 2 terminal penampungan.

Minyak dipompa dari kilang ke terminal menggunakan 3 pompa dengan bentuk jaringan

seperti yang ditunjukkan gambar di bawah. Kapasitas kilang pemurnian masing-

masingnya diperkirakan 200,000, 250,000 dan 300,000 bbl per hari. Permintaan pada

kedua terminal diketahui 400,000 dan 450,000 bbl per hari. Permintaan pada kedua

terminal yang tidak dapat dipenuhi dari ketiga kilang pemurnain akan disuplai dari tempat

lain. Hitunglah kapasitas aliran setiap hari yang melalui masing-masing pompa tersebut!!

Penyelesaian :

Iterasi –1:

Iterasi-2:


1

2

35

4

6

7

8

20

1050

20

15

20

3030

10

10

50

20

pemurnian Stasiun pompa terminal

1

2

35

4

6

7

8

(20, 0)

(10, 0)

(50,0)

(20,0)

(15,0)

(20,0)

(30,0)(30,0)

(10,0)

(10,0)

(50,0)

(20,0)

C*=50

Iterasi-3:

Iterasi-4:

Iterasi-5:


1

2

35

4

6

7

8

(20, 0)

(10, 0)

(0,50)

(20,0)

(15,0)

(20,0)

(30,0)

(30,0)

(10,0)

(10,0)

(0,50)

(20,0)

1

2

35

4

6

7

8

(0, 20)

(10, 0)

(0,50)

(20,0)

(15,0)

(0,20)

(10,20)

(30,0)

(10,0)

(10,0)

(0,50)

(20,0)

1

2

35

4

6

7

8

(0, 20)

(10, 0)

(0,50)

(0,20)

(15,0)

(0,20)

(10,20)(10,20)

(10,0)

(10,0)

(0,50)

(0,20)

C*=50+20 =70

C*=70+20 =90

C*=90+10 =100

1

2

35

4

6

7

8

(0, 20)

(10, 0)

(0,50)

(0,20)

(5,10)

(0,20)

(0,30)(10,20)

(10,0)

(10,0)

(0,50)

(0,20)

C*=100+10 =110

Solusi optimal :

Jumlah yang dipompa dari pompa 4 adalah 30 bbl, pompa 5 sebesar 50 bbl dan pompa 6

sebesar 70 bbl. Aliran maksimum (c*) = 110 bbl.


Teori Keputusan

Tujuan Instruksional Umum : Mahasiswa dapat menjelaskan jenis-jenis pengambilan

keputusan berdasarkan sifat datanya dan menggunakan

kriteria pengambilan keputusan sehingga diharapkan dapat

membuat program aplikasinya.


1. Mahasiswa dapat menggunakan kriteria Laplace untuk pengambilan keputusan.

2. Mahasiswa dapat menggunakan kriteria minimaks dan maksimin untuk

pengambilan keputusan.


1

2

35

4

6

7

8

(0, 20)

(0, 10)

(0,50)

(0,20)

(5,10)

(0,20)

(0,30)

(10,20)

(10,0)

(0,10)

(0,50)

(0,20)

3. Mahasiswa dapat menggunakan kriteria Savage regret untuk pengambilan

keputusan.

4. Mahasiswa dapat menggunakan kriteria Hurwicz untuk pengambilan keputusan.

Pengertian Metode Keputusan Tidak Pasti

Data yang digunakan dalam pengambilan keputusan bersifat tidak pasti dan

ketidakpastian tersebut tidak dapat dihitung dalam bentuk peluang.

Lawan (opponen) pengambil keputusan adalah alam.

Kriteria Laplace

Setiap kriteria keputusan dianggap mempunyai peluang yang sama untuk terjadi.

Contoh Diberikan tabel perolehan dalam bentuk biaya berikut :

Suplai

level

Kategori customer

1 2 3 4

a1 5 10 18 25

a2 8 7 8 23

a3 21 18 12 21

a4 30 22 19 15

Penyelesaian :

E{a1} = (1/4)(5+10+18+25) = 14.5

E{a2} = (1/4)(8+7+8+23) = 11.5E{a3} = (1/4)(21+18+12+21) = 18.0

E{a4} = (1/4)(30+22+19+15) = 21.5

Kriteria Minimaks dan Maksimin

Biasanya digunakan oleh pengambil keputusan yang bersifat pesimis.

Memilih yang terbaik dari antara yang terburuk.

Minimaks tabel perolehan dalam bentuk biaya (kerugian).

Maksimin tabel perolehan dalam bentuk keuntungan.


Contoh Diberikan tabel perolehan dalam bentuk biaya berikut :

Suplai

level

Kategori customer

1 2 3 4

a1 5 10 18 25

a2 8 7 8 23

a3 21 18 12 21

a4 30 22 19 15

Penyelesaian :

Suplai

level

Kategori customer Maksimum

1 2 3 4

a1 5 10 18 25 25

a2 8 7 8 23 23

a3 21 18 12 21 21a4 30 22 19 15 30

Jika tabel di atas dianggap perolehan dalam bentuk keuntungan, maka penyelesaiannya

adalah:

Suplai

level

Kategori customer Minimum

1 2 3 4

a1 5 10 18 25 5

a2 8 7 8 23 7

a3 21 18 12 21 12

a4 30 22 19 15 15

Kriteria Savage Regret

Perbaikan dari Minimaks dan Maksimin


Minimaks

Maksimin

Contoh : Diberikan tabel perolehan dalam bentuk biaya berikut:

Suplai

level

Kategori

customer

Maksimum

1 2

a1 5 100 100

a2 50 100 100

a3 90 85 90

a4 60 90 90

Dengan Savage regret

Bentuk tabel savage regret, lalu gunakan kriteria minimaks.

Suplai

level

Kategori

customer

Maksimum

1 2

a1 0 15 15a2 45 15 45

a3 85 0 85

a4 55 5 55

Kriteria Hurwicz

Contoh Diberikan tabel perolehan dalam bentuk biaya berikut. Misalkan = 0.4.

Suplai

level

Kategori customer

1 2 3 4

a1 5 10 18 25

a2 8 7 8 23

a3 21 18 12 21

a4 30 22 19 15

Penyelesaian :


Minimaks

Minimaks

Suplai

level

Kategori customer Maksimum Minimum

1 2 3 4

a1 5 10 18 25 25 5

a2 8 7 8 23 23 7

a3 21 18 12 21 21 12

a4 30 22 19 15 30 15

E{a1} = (0.4*5)+(0.6*25) = 17

E{a2} = (0.4*7)(0.6*23) = 16.6E{a3} = (0.4*12)(0.6*21) = 17.4

E{a4} = (0.4*15)(0.6*30) = 24


Teori Permainan


teori permainan untuk mendapatkan solusi optimal

permasalahan pemrograman linier, sehingga diharapkan

dapat membuat program aplikasinya.


1. Mahasiswa dapat menggunakan strategi murni.

2. Mahasiswa dapat menyelesaikan permainan menggunakan solusi grafik.

Aplikasi Teori Permainan

Lawan pemain (punya intelegensi yang sama). Setiap pemain mempunyai beberapa

strategi untuk saling mengalahkan.

Two-Person Zero-Sum Game Permainan dengan 2 pemain dengan perolehan

(keuntungan) bagi salah satu pemain merupakan

kehilangan (kerugian) bagi pemain lainnya.

Matriks/tabel payoff (perolehan) tabel yang menunjukkan perolehan bagi pemain

baris


Strategi Murni

Digunakan jika permainan stabil ada titik saddle (saddle point)

Titik sadel minimaks = maksimin

Contoh :

Pemain A Pemain B

Strategi 1 Strategi 2 Strategi 3 Strategi 4 Strategi 5 Strategi 6

Strategi 1 5 10 -20 15 5 7

Strategi 2 15 8 16 -10 13 12

Strategi 3 11 11 12 14 14 12

Tentukan strategi terbaik bagi masing-masing pemain!!

Jawab :

Pemain A Pemain B Minimum

Strategi 1 Strategi 2 Strategi 3 Strategi 4 Strategi 5 Strategi 6

Strategi 1 5 10 -20 15 5 7 -20

Strategi 2 15 8 16 -10 13 12 -10

Strategi 3 11 11 12 14 14 12 11maks 15 11 16 15 13 12

Minimaks = maksimin = 11 permainan seimbang (stabil)

Titik sadel 11 nilai permainan (v)

Strategi Campuran

Strategi campuran digunakan jika permainan tidak seimbang. Pemilihan strategi dilakukan

dengan mengevaluasi kombinasi strategi lawan menggunakan prinsip peluang.

Definisikan : xi adalah peluang pemain baris akan menggunakan strategi ke-i

Yj adalah peluang pemain kolom akan menggunakan strategi ke-j.

y1 y2 ... yn

Strategi 1 Strategi 2 ... Strategi n

x1 Strategi 1 a11 a12 ... a1n


x2 Strategi 2 a21 a22 ... a2n

.

.

.

.

.

.

.

.

.

.

.

.

xm Strategi m am1 am2 ... amn

Solusi Grafik

Solusi grafik dapat digunakan jika paling salah satu pemain mempunyai hanya 2 strategi (2

x n atau m x 2).

Perhatikan matriks payoff untuk dua pemain berikut :

A

B

y1 y2 y3 ... yn

x1 a11 a12 a13 ... a1n

x2 = 1-x1 a21 a22 a23 ... a2n

Menghitung x1 dan x2 dengan menganggap pemain B menggunakan strategi

murni. Maka ekspektasi perolehan bagi pemain A adalah sbb:

Strategi murni B Ekspektasi perolehan A

1 a11 x1 + a21x2

2 a12 x1 + a22x2

3

.

.

.

n

a13 x1 + a23x2

.

.

.

a1n x1 + a2nx2

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 1:

Perhatikan matriks payoff permainan di bawah ini:

Pe

ma

in

A

Pemain B

Strategi 1 Strategi 2 Strategi 3 Strategi 4 Strategi 5

Strategi 1 2 4 5 -2 -1

Strategi 2 3 -1 -2 6 5

Permainan di atas memiliki nilai minimaks = 3 dan nilai maksimin = -2 permainan

tidak seimbang

Dengan solusi grafik:

Pe

ma

in

A x1

x2

Pemain B

y1 y2 y3 y4 y5


Strategi 1 2 4 5 -2 -1

Strategi 2 3 -1 -2 6 5

Bagi Pemain A :

Strategi murni B Ekspektasi perolehan A

1 2x1 + 3x2 =(2-3)x1+3

2 5x1-1

3

4

5

7x1-2

-8x1+6

-6x1+5


5

4

5

Ada 6 titik perpotongan yang menjadi kandidat solusi optimal untuk x1 (titik perpotongan

garis (1,2), (1,3), (2,4), (2,5), (3,4) dan (3,5)). Karena pemain A adalah pemain baris

dimana dia akan memaksimumkan ekspektasi perolehan minimumnya, maka solusi

optimalnya adalah titik perpotongan ungu (perpotongan garis (2,4)). Dengan demikian x1

= 7/13 dan x2 = 1-7/13 = 6/13.

v = 5x1 -1 = 22/13 diperoleh dengan memasukkan nilai x1 pada pers (2) atau (4).

Bagi Pemain B:

Solusi optimal bagi pemain A di atas merupakan perpotongan garis (2) dan (4), Hal ini

menunjukkan bahwa B dapat mengkombinasikan kedua strategi tersebut.

Kombinasi strategi 2 dan 4 menunjukkan bahwa y1 = y3 = y5 = 0.

Pe

ma

in

A x1

x2

Pemain B

y2 y4

Strategi 2 Strategi 4

Strategi 1 4 -2

Strategi 2 -1 6

Strategi murni A Ekspektasi perolehan B

1 4y2 - 2y4 =(4+2)y2-2=6y2-2

2 -7y2+6


x1

0 10.5

3

1

2

4

-2

1

2

3

6y2-2=-7y2+6, maka y2 = 8/13 dan y4 = 5/13; y1 = y3 = y5 = 0; v = 22/13 (sama dengan nilai

di atas).

Contoh 2:

Perhatikan permainan dengan matriks payoff berikut:

A

B

1 2

1 2 4

2 2 3

3 3 2

4 -2 6

Penyelesaian :

Tidak ada saddle point, dan pemain B memiliki hanya 2 strategi solusi grafik.

Bagi Pemain B:

Strategi murni A Ekspektasi payoff B

1

2

3

4

-2y1+4

-y1+3

y1+2

-8y1+6


0 10.5

3

5

1

2

4

-2

1 2

3

4

y1

Ada 3 titik maksimum (perpotongan warna ungu, biru dan hijau). Pemain B sebagai

pemain kolom akan meminimumkan ekspektasi perolehan maksimumnya, maka solusi

optimalnya adalah titik hijau y1 = 2/3 dan y2 = 1/3; v = -2*2/3 + 4 =8/3

Pemain A

Titik optimum bagi pemain B merupakan perpotongan strategi 1 dan 3 pemain A.

A

B

1 2

1 2 4

3 3 2

Strategi murni B Ekspektasi payoff A

1

2

-x1+3

2x1+2

-x1+3 = 2x1+2 x1 = 1/3, x2 = 0, x3 = 2/3, x4 = 0 dan v = 8/3 (sama dengan di atas).



Mahasiswa dapat membentuk model LP teori permainan dan menyelesaikannya

menggunakan metode simpleks.


Metode Simpleks

Bentuk umum LP bagi pemain baris :

Min

Sub. To :

;

Bentuk umum LP bagi pemain kolom (Dual pemain baris)

Maks.

Sub. To :

;

Perhatikan kembali matriks payoff berikut:

Pe

ma

in

A

Pemain B


Strategi 1 2 4 5 -2 -1

Strategi 2 3 -1 -2 6 5

Maka bentuk umum LP untuk pemain baris (pemain A) adalah :


Min.

Sub. To :

Maka bentuk umum LP untuk pemain kolom (pemain B) adalah :

Maks.

Sub. To:

Tabel simpleks awal (iterasi-0):

VB Y1 Y2 Y3 Y4 Y5 s1 s2 NK

w -1 -1 -1 -1 -1 0 0 0

s1 2 4 5 -2 -1 - 0 1

s2 3 -1 -2 6 5 0 1 1

Iterasi-1:


w -3/5 -1/5 0 -7/5 -6/5 1 0 1/5

Y3 2/5 4/5 1 -2/5 -1/5 1 0 1/5

s2 19/5 3/5 0 26/5 23/5 2 1 7/5

Iterasi-2 :



w 11/26 -1/26 0 0 1/26 6/13 7/26 15/26

Y3 9/13 11/13 1 0 5/26 15/13 1/13 4/13

Y4 19/26 3/26 0 1 23/26 5/13 5/26 7/26

Iterasi-3: optimal


w 5/11 0 1/22 0 0.0472 7/22 3/11 13/22

Y2 9/11 1 13/11 0 5/22 15/11 1/11 4/11

Y4 7/11 0 -3/22 1 0.85839 5/22 2/11 5/22

Y1 = Y3 = Y5 = 0 y1 = y3 = y5 = 0; w = 13/22 v=1/w=

Y2 = 4/11 y2 = ; Y4 = 5/22 y4 =

z = w = 13/22; X1 = s1 = 7/22 x1 =

X2 = s2 = 3/11 x2 =


Pertemuan minggu pertama (2 x 50 menit)ftp.gunadarma.ac.id/handouts/S1_Sistem Informasi.1... · Web viewVB X1 X2 S1 S2 NK Z 0 0 5/2 ¼ 23.75 X2 0 1 5/2 -1/4 1.25 X1 1 0 -3/2 ¼ 3.75

Documents