hai sis.......dsini gwe mau bagi2 tips buat kalian....
dmana lo2....pada dah ngerasa dicuekin sama pasangan kalian......jadi lo2 pada jangan kuatir....gwe kan bonkar2 rahasia mujarap tuk lo semua.
langkah-langkah yang harus lo laku'n :
berusaha lah sebisa mungkin tuk selalu lo yg memperhatikan doi.....kubur jauh2 gengsi lo2 pada tuk cwo lo yg telpn dlu'n .....biasanya dengan lo yg berinisiatip tuk lebih memperhatikan doi....gwe yakin tuh doi akan merasa diperhatikan lo, dsayangin lo......so......doi akan yakin lo jg emang pantas tuk diperhatikan karena doi percaya lo emang benar-benar tulus....."kejar lah cinta lo...gak benar kalau cinta gak memiliki.....cinta harus memiliki....kalau lo gak memiliki x sis....mungkin tanpa lo sadar,lo menyakiti hati lo sendi. jangan bohongin hati lo....kalau lo sayang/cinta, katakan aja lo cinta ma orang yg lo sayang....
bersabar. kunci sabar itu seperti intan yang mahal buat cwo....karena sebagian besar cowo suka dengan cwe yang sabaran...gak cepat emosian gtu deh sis.... jadi redam emosi lo pada. coba lah tuk tenang, omongin baik2 ma cwo lo.....tanya'n maunya apa.......(^_^)........kata pepatah diam itu emas.....nah sis......ilmu mujarap juga nih sis kalau lo ngambek ma cwo lo...lo diamin aja tuh...pasti doi gak tahan pengen berbaikan ma lo....gwe yakin dia akan mulai merubah sikapnya tuh lebih memperhatikan lo....so......selamat mencoba......
Jumat, 16 Desember 2011
Rabu, 30 November 2011
GRAF
Salah satu algorithma yang sering digunakan dalam teknik pemampatan data adalah Kode Huffman (Huffman’s Code). Proses pemampatan dengan menggunakan Kode Huffman dilakukan dengan pengkodean tiap karakter dengan rangkaian beberapa bit sehingga menghasilkan hasil yang optimal.
Kode Huffman secara luas telah digunakan pada berbagai aplikasi pemampatan dan transmisi data digital, seperti pada mesin fax, modem, jaringan komputer, high-definition televition (HDTV) dan berbagai aplikasi yang berhubungan dengan transmisi data. Didalam pemampatan data, kode Huffman mampu memampatkan media penyimpan data dan waktu transmisi data antara 20%-90%.
Tujuan dari penulisan makalah ini adalah untuk mengetahui keefektifan algorithma Huffman dalam pemampatan data.
Untuk mencapai tujuan tersebut, penulis melakukan serangkaian kegiatan yaitu mengumpulkan data dan eferensi-referensi serta melakukan studi pustaka.
Dasar Teori
1. Algorithma Huffman
Algorithma Huffman, dibuat pertama kali oleh Prof. David A. Huffman (1925-1999) pada tahun 1952 sebagai desertasi Ph.D dengan publikasi berjudul ”A Method for the Construction of Minimum-Redundancy Codes”. Algorithma Huffman menggunakan prinsip bahwa setiap karakter dikodekan dengan serangkaian bit, dimana karakter yang sering muncul dikodekan dengan rangkaian bit yang pendek dan karakter yang jarang muncul dikodekan dengan rangkian bit yang lebih panjang. [4].
Berdasarkan tipe pemetaan kode yang digunakan untuk mengubah data awal menjadi codeword, algorithma Huffman adalah algorithma yang menggunakan metode statik, yaitu selalu menggunakan pemetaan kode yang sama. Dalam metode ini ada dua fase yang harus dilalui, yaitu: fase pertama adalah menghitung probabilitas kemunculan tiap karakter dan menentukan pemetaan kodenya, dan fase kedua adalah mengubah data menjadi sekumpulan kode yang akan ditransmisikan.
Berdasarkan teknik pengkodeannya, algorithma Huffman menggunakan metode symbolwise, yaitu menghitung peluang kemunculan dari setiap karakter, dimana karakter yang sering muncul diberi kode yang lebih pendek dibandingkan dengan karakter yang jarang muncul.[3]
2. Pembentukan Pohon Huffman (Huffman Tree)
Kode Huffman adalah string biner yang digunakan untuk mengkodekan setiap karakter di dalam data. Kode Huffman pada dasarnya merupakan kode prefiks (prefiks code), yaitu berisi sekumpulan kode biner yang dalam hal ini tidak ada kode biner yang menjadi awal bagi kode biner yang lain.
Kode prefiks biasanya direpresentasikan sebagai pohon biner yang berlabel 0 (cabang kiri) atau 1 (cabang kanan). Rangkaian bit yang terbentuk pada setiap lintasan dari akar sampai tree merupakan kode prefiks untuk karakter yang berpadanan.
Pada awalnya David Huffman hanya menencoding karakter dengan hanya menggunakan pohon biner biasa, namun setelah itu David Huffman menemukan bahwa penggunaan algoritma greedy dapat membentuk kode prefiks yang optimal.[5]
Penggunaan algoritma greedy pada algoritma Huffman adalah pada saat pemilihan dua pohon dengan frekuensi terkecil dalam membuat pohon Huffman. Algoritma greedy ini digunakan pada pembentukan pohon Huffman agar meminimumkan total cost yang dibutuhkan. Cost yang digunakan untuk menggabungkan dua buah pohon pada akar setara dengan jumlah frekuensi dua buah pohon yang digabungkan, oleh karena itu total cost pembentukan pohon Huffman adalah jumlah total seluruh penggabungan. Penggabungan dua buah pohon dilakukan setiap langkah dan algoritma Huffman selalu memilih dua buah pohon yang mempunyai frekuensi terkecil untuk meminimumkan total cost. Oleh karena itu algoritma Huffman adalah salah satu contoh algoritma yang menggunaan dari algoritma Greedy.
Langkah-langkah pembentukan pohon Huffman adalah sebagai berikut:
1. Baca semua karakter di dalam data untuk menghitung frekuensi kemunculan karakter. Setiap karakter penyusun teks dinyatakan sebagai pohon bersimpul tunggal.Setiap simpul di-assign dengan frekuensi kemunculan karakter.
2. Terapkan algorithma Greedy yaitu dengan menggabungkan dua buah pohon yang mempunyai frekuensi terkecil pada sebuah akar. Setelah digabungkan akar tersebut akan mempunyai frekuensi yang merupakan jumlah dari frekuensi dua buah pohon-pohon penyusunnya.
3. Ulangi langkah 2 sampai hanya tersisa satu buah pohon Huffman. Agar pemilihan dua pohon yang akan digabungkan berlangsung cepat, maka semua harus terurut naik berdasarkan frekuensinya. [6]
Sebagai contoh diberikan tabel frekuensi untuk setiap karakter sebagai berikut:
| No | Karakter | Frekuensi |
| 1 | Spasi | 76 |
| 2 | A | 77 |
| 3 | E | 120 |
| 4 | F | 24 |
| 5 | H | 50 |
| 6 | M | 24 |
| 7 | N | 67 |
| 8 | R | 59 |
| 9 | T | 85 |
| 10 | U | 37 |
TEORI GRAF NINDA
GRAPH PADA STRUKTUR DATA
Graph adalah istilah untuk suatu model stuktur data yang bersifat interkoneksi n-ke-n. Beberapa di antara kita mengadaptasinya ke bahasa Indonesia menggunakan istilah geraf atau graf. Dalam matematika diskret graph merupakan pokok bahasan penting yang membahas analisis & teori serta algoritma terkait dengannya. Dalam kuliah Struktur Data, hal-hal tersebut diperdalam dengan bahasan bagaimana model itu diterjemahkan menjadi struktur data yang dapat diimplementasikan. Pada dasarnya ada tiga cara implementasi graph: adjacent matrix, edge list, dan adjacent vertex list. Masing-masing memiliki keunggulannya sendiri terkait dengan query yang dilakukan pada cara-cara tsb.
Bagian kedua adalah pembahasan ulang algoritma-algoritma graph dengan pembahasan dikaitkan dengan analisisnya terkait ketiga struktur di atas. Pertama yang dibahas adalah algoritma BFS (Breadth First Search) yang dapat digunakan untuk pencarian shortest path pada unweighted graph. Kedua adalah algoritma Dijkstra untuk pencarian single-source shortest paths pada weighted graph. Algoritma ketiga adalah pencarian minimum spanning tree (MST) dengan algoritma Kruskal dan algoritma Prim pada wieghted graph. Ke empat adalah melakukan topological sorting pada suatu directed acyclic graph.
Secara umum, kondisi graph sangat menentukan pemilihan cara implementasinya. Untuk dense graph (atau graph dengan interkoneksi yang tinggi antara verteks), adjacent matrix memberikan performance yang baik sementara kebalikannya sparse graph (graph dengan interkoneksi yang rendah) akan lebih efisien jika menggunakan adjacent vertex list. Edge list lebih efisien untuk algoritma yang mentraverse seluruh edge seperti Algoritma Kruskal pada masalah MST.
Struktur Data Hirarkis (Tree)
Materi Abstract Data Type (ADT) berikutnya adalah struktur data hirarkis atau dalam istilah lebih teknisnya struktur data pohon/tree. Struktur data ini diperlukan untuk bisa menyimpan kumpulan data yang mana setiap elemen data memiliki hubungan hirarkis satu sama lainnya misalnya struktur organisasi, taksonomi makhluk hidup, pohon silsilah keluarga, struktur isi direktori dalam sistem file komputer, dll. Secara umum dalam struktur data tree setiap elemen data (selanjutnya disebut node) memiliki link/hubungan/pointer ke sejumlah node lainnya tanpa terjadinya siklus (Siklus adalah situasi yang terjadi jika hubungan berantai dari suatu node pada suatu ketika kembali lagi ke node itu sendiri. Untuk kasus adanya siklus akan dibahas dalam struktur data graph yang akan dibahas di bagian akhir semester).
Struktur data binary tree, yaitu pencabangan pada setiap node maksimum hanya boleh ada dua cabang. Selanjutnya setiap cabang dibedakan antara cabang kiri dan cabang kanan.
Materi pembahasan berisikan topik-topik algoritma non-rekursif untuk tree traversal, level-order traversal, representasi array pada complete binary tree. Apabila dalam kuliah sebelumnya tree traversal dilakukan dengan algoritma rekursif, dalam sesi kuliah ini dilakukan dengan algoritma non-rekursif dengan bantuan stack. Level order traversal adalah traversal lain yang dapat dilakukan dengan bantuan queue. Binary Tree secara normal direpresentasikan dengan struktur dinamis (selerti linked-list namun dua pointer ke subtree kiri dan ke subtree kanan) namun kusus untuk complete binary tree direpresentasikan dengan array tanpa kehilangan informasi strukturalnya. Dalam implementasi array ini hubungan struktural antara data masih terekam sebagai hubungan aritmatis bolak-balik antara indeks parent dengan indeks children dalam array tsb.
Binary Search Tree (BST)
Pengorganisasian data dalam array memungkinkan pencarian O(log n) dengan menggunakan algoritma binary search, namun dengan syarat data terurut. Untuk menjaga data selalu terurut saat terjadi perubahan data: insert, delete, dan update, diperlukan operasi penggeseran O(n). Masalah lainnya adalah keterbatasan ukuran array.
Binary tree dapat digunakan untuk mengorganisasikan data dengan pencarian data O(log n) tanpa adanya keterbatasan seperti pada array dan namun operasi perubahan data dapat dilakukan secara O(log n) juga. Binary tree pertama yang memungkinkan hal ini adalah Binary Search Tree ( BST). BST adalah binary tree yang mana data di dalamnya tersusun sedemikian rupa sehingga pada setiap subtree di dalamnya berlaku setiap data di subtree kiri < data root subtree < setiap data di subtree kanan.
Dengan asumsi tree yang terbentuk adalah “segitiga” membesar ke bawah, pencarian data adalah menelusuri ke cabang data itu berada sehingga berjalan secara O(log n). Jika data masuk ke dalam BST secara acak, operasi penyisipan ke dalam BST tersebut dilakukan dengan penelusuran dari root hingga leaf tempat seharusnya data tsb berada sehingga terjadi secara O(log n). Operasi penghapusan dilakukan dengan pencarian data di dalam BST lalu dilakukan penghapusan menggunakan langkah-langkah yang sesuai dengan kasus dari 3 kasus yang bisa terjadi. Operasi penghapusan dapat dilakukan secara O(log n)
AVL Tree (Balanced Binary Search Tree)
Worst Case dari BST terjadi saat bentuk tree yang tidak balance, misalnya jika sederetan data terurut diinsert ke dalamnya akan membentuk cabang yang berbentuk rantai panjang (tanpa pencabangan lain). Situasi ini mengakibatkan operasi searching pada BST menjadi O(n), tidak sebagaimana yang diharapkan yaitu O(log n). Adelson-Velskii dan Landis mempelajari mekanisme tambahan pada operasi-operasi insert/delete pada BST sehingga BST selalu kembali ke dalam situasi “balanced”. Untuk memungkinkan mekanisme tsb bekerja secara O(log n) maka didefinisikan AVL tree sebagai BST dengan tinggi subtree kiri dan subtree kanan dari setiap node di dalamnya berbeda tidak boleh lebih dari 1 (jadi, jika HL dan HR adalah masing-masing tinggi subtree kiri dan kanan, maka HL – HR| ≤ 1).
Mekanisme rebalancing pada operasi insert dilakukan dengan mencari subtree terkecil yang mengalami “kerusakan” sesaat insert dilakukan. Di posisi itu dilakukan “operasi rotasi” yang dilakukan secara O(1). Ada empat jenis rotasi Single Right Rotation (SRR), Single Left Rotation (SLR), Double Right Rotation (DRR), dan Double Left (Rotation) sesuai dengan kondisi “kerusakan yang terjadi. Setelah rotasi yang dilakukan, subtree tersebut kembali menjadi AVL-tree dengan tinggi yang sama dengan tinggi sebelum insert. Dengan demikian, rotasi hanya dilakukan satu kali saja. Karena menentuan subtree terkecil mana yang terjadi kerusakan adalah operasi backtrack dari leaf ke arah root, maka mekanisme rebalancing ini menjadi operasi O(log n). Mekanisme rebalancing pada operasi remove mirip dengan yang dilakukan pada insert kecuali operasi rotasi bisa terjadi beberapa kali karena setelah suatu rotasi di suatu subtree dilakukan, karena tinggi subtree kemudian menjadi berkurang, maka subtree yang lebih besar di atasnya harus diperiksa pula karena kemungkinan juga tidak balanced. Namun, operasi keseluruhan tetap adalah O(log n).
Red-Black Tree
Struktur ini dibahas sebagai varian BST disamping AVL Tree yang memungkinkan rebalancing guna mencapai performance O(log n). Selain itu struktur ini dapat menjadi cara untuk mengimplementasikan 2-3 Tree (2-3 Tree adalah varian dari keluarga (a,b)-tree dimana B-Tree berada di dalamnya sebagai salah satu varian). Red-Black Tree juga sering digunakan dalam mengimplementasikan sejumlah abstraksi yang lebih tinggi lainnya.
Red-Black Tree adalah suatu binary search tree dengan tambahan 4 property: (1) node berwarna merah atau hitam; (2) root berwarna hitam; (3) node merah tidak boleh memiliki anak node merah ; (4) dalam lntasan dari suatu internal node ke semua leaf node di bawahnya, node hitam sama jumlahnya. Dengan property ini suatu Red-Black Tree dengan jumlah node n menjamin jumlah tinggi tree minimum log(n+1) dan maksimum 2.log(n+1).
Agar operasi penyisipan dapat dilakukan secara O(log n), algoritma penyisipan data pada awalnya dilakukan sebagaimana pada BST yaitu O(log n) dan node baru tersebut berwarna merah, dilanjutkan dengan operasi untuk membuatnya kembali menjadi Red-Black Tree apabila dari penyisipan terjadi pelanggaran pada satu atau beberapa dari keempat sifat di atas. Materi kuliah ini membahas kasus-kasus yang terjadi dan algoritma penanganan dari setiap kasus. Untuk penghapusan, awalnya terjadi hal yang sama dengan apa yang dilakukan pada BST. Selanjutnya, berdasarkan kasus-kasus yang terjadi dilakukan algoritma untuk mengembalikan menjadi Red-Black Tree kembali jika terjadi pelanggaran terhadap sifat-sifat tsb. Algoritma-algoritma tersebut memiliki performance worst-case O(log n) sehingga secara keseluruhan tetap O(log n).
Kelemahan Red-Black Tree dibandingkan AVL Tree adalah tinggi tree yang dihasilkan worst case 2 log (n+1) sementara AVL Tree 1.44 log(n+2), tetapi dengan adanya lebih banyak kasus-kasus yang bisa terjadi dengan penanganan yang lebih sederhana memungkinan Red-Black Tree memiliki real performance yang lebih baik.
B+Tree
Struktur data ini semula adalah varian dari struktur data (a,b)-Tree, namun dalam perkembangannya struktur ini digunakan secara spesifik sebagai struktur data eksternal (i.e., indexed file) dan kemudian dalam DBMS relasional untuk mengorganisasikan index key dari tabel basis data.
Sebagai struktur data eksternal B+Tree biasanya berupa n-ary tree dengan n bilangan yang cukup besar. Dengan demikian untuk n=100, data dalam jumlah jutaan dapat diorganisasikan dalam B+Tree yang memiliki tinggi = 3. Dengan bentuknya yang landai demikian memungkinkan data diakses secara cepat dengan hanya melalui pembacaan 3 buah node B+Tree sebelum membaca blok datanya .
Mekanisme yang terjadi saat masuknya key data ke dalam struktur B+Tree serta saat suatu key data dihapuskan dari struktur tsb. Saat masuknya data baru ke dalam tabel, key data dan referensi data dalam tabel disimpan dalam node leaf struktur B+Tree. Terdapat kapasitas maksimum setiap node sehingga saat key baru dimasukan sementara node sudah mencapai kapasitas maksimum, akan terjadi mekanisme “split”. Demikian pula, saat terjadi penghapusan data yang berakibat key pada node berkurang, apabila jumlah key melalui batas minimal kapasitas, maka akan terjadi mekanisme “merge” atau kalau tidak “redistribusi” isi node. Mekanisme-mekanisme itu memaintain struktur B+Tree tetap memenuhi kaidah sebagai suatu B+Tree agar setiap operasi dapat dilakukan secara O(log n) dengan basis logaritma bilangan yang besar.
Hash Table
Hingga saat ini sudah sekian struktur yang telah dipelajari untuk bisa menyimpan data dan mencari atau menghapusnya kembali, mulai dari struktur tabel (biasa baik unsorted array maupun sorted array), struktur linear linked list, struktur hirarkis (BST, AVL, BTree), hingga graph.
Semua struktur itu memiliki performance yang terkait dengan jumlah data N. Struktur array unsorted memerlukan O(1) untuk menyimpan data tapi dalam pencarian kembali data dan menghapus data memerlukan O(n). Pada struktur sorted array sebaliknya, menyimpan dan menghapus dengan O(n), tetapi pencarian data memerlukan O(log n) (yaitu menggunakan algoritma Binary Search). Sementara, struktur hirarkis memungkinan semua proses dapat dilakukan secara O(log n).
Struktur yang memungkinkan secara teoritis semua operasi itu dilakukan secara O(1) atau konstan tidak bergantung jumlah data yang bernama hash table. Bagaimana itu bisa terjadi? Hash table menggunakan suatu fungsi (disebut fungsi hash) untuk menentukan dimana penempatan data dalam tabel berdasarkan komputasi atas key data tersebut. Komputasi fungsi hanya bergantung pada harga key itu saja dan idealnya fungsi tsb harus memetakan setiap kemungkinan key ke dalam bilangan nomor entry pada tabel untuk menaruh data. Tabel sendiri merupakan array biasa. Apakah itu selalu bisa terjadi? Tentu saja sepanjang fungsi hash memenuhi keunikan penempatan itu.
Kenyataannya sulit (atau bahkan tidak mungkin) mendapatkan fungsi hash ideal tersebut terutama jika key data unpredictable. Karena itu maka pembahasan materi kuliah ini berpokok pada metoda-metoda untuk menangani situasi jika penempatan data tidak dapat dilakukan secara unik yaitu terjadi tabrakan di suatu posisi. Cara penangan tabrakan atau collison ini dibedakan antara open-hashing dan close-hashing. Open-hashing menangani collision dengan memperluas entry tabel tersebut dengan menaruh data kedua, ketiga, dst (yang collision di posisi tsb.) ke dalam “bucket”. Biasanya bucket diimplementasikan sebagai linked-list untuk memungkinkan kedinamisan ukuran bucket. Close-hashing menangani collision dengan mencarikan posisi alternatif untuk data yang collision itu masih di tabel yang sama (tidak ke luar tabel). Ada tiga kelompok cara untuk mencarikan posisi alternatif, atau yang disebut “probing” ini: linear probing, quaratic probing, dan double hashing. Semua cara penanganan collision itu haruslah bisa menjaga agar operasi pada hash table tetap konstan atau “mendekati konstan”.
Binary Heap dan Priority Queue
Kembali ke struktur data hirarkis, terdapat satu struktur binary tree yang bernama binary heap. Suatu binary heap adalah binary tree yang didalamnya tersimpan data dengan cara pengurutan tertentu: dalam binary heap dengan kaidah “minheap” data pada setiap parent dalam tree harus tidak boleh lebih besar dari data pada anak-anaknya. Dengan demikian root dari tree berisi bilangan terkecil dari semua bilangan dalam tree. Dalam binary heap dengan kaidah “maxheap”, parent tidak boleh lebih kecil dari anak-anaknya sehingga root berisi bilangan terbesar dari semua bilangan dalam tree.
Semantara itu, dalam kuliah mengenai struktur hirarkis dibahas definisi complete binary tree. Suatu complete binary tree adalah suatu binary tree yang memiliki bentuk khusus sehingga menjadi satu-satunya binary tree yang dapat direpresentasikan hanya dengan array tanpa kehilangan informasi strukturnya (siapa ayah, siapa anak-akannya, dapat diketahui melalui fungsi antara indeks di dalam array tsb).
Konsep binary heap ini dikombinasikan dengan konsep complete binary tree tersebut menghasilkan suatu struktur priority queue yang memiliki performance O(log n). Tanpa itu, suatu priority queue memerlukan operasi O(n), ie. , dengan sorted array memerlukan enqueue O(n) dequeue O(1) atau unsorted array memerlukan enqueue O(1) dan dequeue O(n). Yang menarik, perbaikan performance dari O(n) menjadi O(log n) hanya pada konsep abstraksinya saja semetara representasinya tetap sama-sama dengan array.
Operasi enqueue (menginsert data ke dalam queue) pada struktur ini bisa mencapai O(log n) dengan suatu proses PercolateUp dan operasi dequeue (meremove data terkecil untuk minheap / data terbesar untuk maxheap) dengan proses PercolateDown. Kedua algoritma ini beriterasi secara worse case antara root dengan leaf tanpa mengganggu node-node lainnya.
Manfaat selain sebagai suatu priority queue, struktur ini mengilhami algoritma sorting yang bernama heapsort yang memiliki performance O(n log n) seanding dengan quicksort dan mergesort. Heapsort mengurutkan data mirip seperti selection-sort namun jika selection-sort melakukan pencarian data minimum secara sikuensial (O(n)) pada data , heapsort hanya melakukan dequeue secara O(log n). Di awal priority queue yang semula berisi semua data yang tersusun membentuk heap dengan suatu proses heapify yang bersifat O(n log n).
Selain itu, terdapat sejumlah manfaat lainnya yaitu dalam struktur pendukung proses external data sorting.
TEORI PERMAINAN NINDA DWI SISWANTI
(TEORI PERMAINAAN)
Teori permainan adalah suatu model matematika yang digunakan dalam situasi konflik antara berbagai kepentingan yang saling berhadapan sebagai pesaing. Dalam permaian peserta adalah pesaing. Keuntungan bagi yang satu merupakan kerugian bagi yang lain. Model-model permainan dapat dibedakan berdasarkan jumlah pemain, jumlah keuntungan atau kerugian, dan jumlah startegi yang digunakan dalam permainan. Bila jumlah pemain ada dua, permainan disebut sebagai permainan dua pemain. Bila keuntungan atau kerugian sama dengan nol, disebut permainan jumlah nol.
A. SOLUSI OPTIMAL TWO PERSON ZERO SUM GAMES
Ada dua macam two person zero sum games, pertama jenis permainan startegi murni (pure strategy game) dimana setiap pemain hanya menjalankan strategi tunggal, dan kedua permainan strategi campuran (mixed strategy game) dimana kedua pemain menjalankan strategi yang berbeda-beda.
1. PURE STRATEGY GAME
Criteria maksimin untuk keuntungan, dimana pemain akan memilih strategi yang memaksimumkan keuntungan dari kemungkinan pay off yang minimum. Sedangkan, criteria minimax untuk kerugian, dimana pemain berusaha meminimumkan kerugian dari kerugian yang diperkirakan maksimum. Dalam permaian strategi murni, pemain baris mengidentifikasi strategi optimalnya melalui criteria maksimin, sedang pemain kolom menggunakan criteria minimax. Pada kasus nilai maksimin sama dengan minimax maka dikatakan titik keseimbangan telah dicapai yang biasa disebut titik pelana (saddle point). Bila tidak dicapai keadaan seperti itu, maka strategi murni tidak dapat diterapkan dan digunakan strategi campuran.
Berikut merupakan contoh matriks pay off permaianan dua pemain jumlah nol (two person zero sum games) permainan strategi murni.
2. MIXED STRATEGY GAME
Sebagai suatu contoh perhatikan kasus berikut:
Terapkan startegi dominan, strategi undian dan diskon pada perusahaan A didominasi oleh strategi kupon, sehingga strategi undian dan diskon pada perusahaan A dapat dihilangkan dan tersisa strategi hadiah dan kupon. Sementara itu strategi hadiah dan kupon pada perusahaan B didominasi oleh strategi diskon, sehingga strategi hadiah dan kupon pada perusahaan B dapan dihilangkan dan tersisa strategi undian dan diskon. Sehingga matriks pay off menjadi:
Misalkan P adalah kemungkinan perusahaan A menggunakan strategi “hadiah” dan (1 – P) adalah kemungkinan perusahaan A menggunakan strategi “kupon”. Terdapat dua kemingkinan:
1. Jika perusahaan B menggunakan strategi “undian”, maka harapan menang untuk perusahaan A adalah: -7P + 4(1 – P) = -7P + 4 – 4P = 4 – 11P
2. Jika perusahaan B menggunakan strategi “diskon”, maka harapan menang untuk
perusahaan A adalah: 4P + -1(1 – P) = 4P -1 + P = 5P – 1
Karena mixed strategy beranggapan bahwa apapun yang dipilih perusahaan B berakibat
sama bagi perusahaan A, maka:
4 – 11P = 5P – 1;
-11P – 5P = -1 – 4
-16P = -5
P = 5/16 = 0.3125
Solusi mixed strategy ini akan menghasilkan harapan menang bagi perusahaan A atau harapan kalah bagi perusahaan B. Ini berarti perusahaan A seharusnya mempergunakan strategi “hadiah” sebesar 5/16 dan sisanya strategi kupon sebesar 11/16. Kemudian harapan menang untuk perusahaan A adalah:
= -7 (5/16) + 4(11/16) = -35/16 + 44/16
= 4 (5/16) – 1(11/16) = 20/16 – 11/16
= 9/16 = 0.5625
Artinya, jika games dilakukan berulang kali, maka rata-rata pertumbuhan pangsa pasar perusahaan A atau rata-rata penurunan pangsa pasar perusahaan B adalah sebesar 56.25%. Namun, jika games hanya terjadi sekali solusinya adalah pure strategy tunggal bagi setiap perusahaan dan salah satu perusahaan itu akan dirugikan.
B. SOLUSI PERMAINAN MENGGUNAKAN LP
Bila model permainan dipecahkan dengan metode simpleks, langkah awal adalah menyederhanakan matriks pay off-nya bila mungkin. Bentuk program liniernya dan cari solusi optimumnya. Sebagai ilustrasi mari kita kembali kekasus permaian dua pemain jumlah nol diatas. Untuk mempermudah penjelasan kita notasikan:
N = nilai permainan
X1 dan X2 = probabilitas masing-masing strategi perusahaan A
Y1 dan Y2 = probabilitas masing-masing strategi perusahaan B
Dengan perusahaan A sebagai pemain baris (maximizing player), maka dapat dinyatakan harapan menang perusahaan A dalam tanda (≥). Jadi:
-7X1 + 4X2 ≥ N Bila perusahaan B menggunakan strategi undian
4X1 – X2 ≥ N Bila perusahaan B menggunakan strategi diskon
Diketahui:
X1 + X2 = 1 dan X1, X2 ≥ 0
Dengan perusahaan B sebagai pemain kolom (minimizing player), maka dapat dinyatakan harapan kekalahan perusahaan B dalam tanda (≤). Jadi:
-7Y1 + 4Y2 ≤ N Bila perusahaan A menggunakan strategi hadiah
4Y1 – Y2 ≤ N Bila perusahaan A menggunakan strategi kupon
Diketahui:
Y1 + Y2 = 1 dan Y1, Y2 ≥ 0
Dengan membagi setiap petidaksamaan dan persamaan diatas dengan N, maka:
Perusahaan A adalah maximizing player, maka fungsi tujuannya adalah memaksimumkan N atau ekuivalen dengan meminimumkan 1/N, dengan fungsi tujuan X1 + X2 = 1/N, maka linier programming bagi perusahaan A adalah:
Perusahaan B adalah minimizing player, maka fungsi tujuannya adalah meminimumkan N atau ekuivalen dengan memaksimumkan 1/N, dengan fungsi tujuan X1 + X2 = 1/N, maka linier programming bagi perusahaan B adalah:
C. SOLUSI GRAFIK UNTUK GAMES TEORY
Mengikuti contoh sebelumnya:
Dengan demikian maka:
N = 4 – 11(0.3125) = 0.5625
N = 5(0.3125) – 1 = 0.5625
REFERENSI
1. Aminudin, Prinsip-Prinsep Riset Operasi, Jakarta, Penerbit Erlangga,
2. Siswanto, Operations Research - Jilid 2, Jakarta, Penerbit Erlangga.
3. Sri Mulyono, Riset Operasi, Jakarta: Lembaga Penerbit Fakultas Ekonomi UI, 2002
4. Taha, Hamdy A., Riset Operasi – Jilid 1, Jakarta: Binarupa Aksara, 1996
(TEORI PERMAINAAN)
Teori permainan merupakan konsep / metode pengambilan suatu keputusan secara individual beberapa kelompok individu yang bersaing untuk mencapai hasil yang optimal / terbaik.
A. SOLUSI OPTIMAL TWO PERSON ZERO SUM GAMES
(permainan jumlah-nol dua-orang)
Pemecahan optimasi untuk jumlah-nol dua-orang mengharuskan setiap pemain untuk memainkan 2 strategi, yaitu:
1. Strategi murni (true strategy) strategi domain
2. Strategi campuran (mixed strategy / dari beberapa strategi murni)
Langganan:
Postingan (Atom)