Sebuah perusahaan pengecoran logam
mempunyai empat jenis mesin yang diberi nama M1, M2, M3 dan M4. Setiap mesin
mempunyai kapasitas yang berbeda dalam pengoperasiannya. Dalam minggu mendatang
perusahaan mendapatkan pesanan untuk menyelesaikan empat jenis pekerjaan (job)
yaitu J1, J2, J3 dan J4. Biaya pengoperasian setiap pekerjaan oleh keempat
mesin dapat dilihat dalam tabel berikut:
Masalahnya adalah bagaimana menugaskan keempat mesin untuk
menyelesaikan keempat jenis pekerjaan agar total biaya pekerjaan minimum!
Pembahasan/Langkah-langkah
Penyelesaian:
- Kurangkan semua biaya dengan biaya terkecil setiap baris, sehingga menghasilkan reduced cost matrix /matrik biaya yang telah dikurangi.
- Mengurangi kolom dengan cara memilih biaya terkecil setiap kolom untuk mengurangi seluruh biaya dalam kolom-kolom tersebut. Pada contoh di atas hanya dilakukan pada kolom III karena semua kolom lainnya telah mempunyai elemen yang bernilai nol (0). Jika langkah pertama telah menghasilkan paling sedikit satu nilai nol pada setiap kolom, maka langkah kedua ini dapat dihilangkan. Berikut matrix total opportunity cost, dimana setiap baris dan kolom terdapat paling sedikit satu nilai nol.
- Membentuk penugasan optimum dengan menarik sejumlah minimum garis horisontal dan/atau vertikal untuk meliputi seluruh elemen bernilai nol dalam total opportunity cost matrix. Jika jumlah garis sama dengan jumlah baris/kolom maka penugasan telah optimal. Jika tidak maka harus direvisi.
- Melakukan revisi tabel pada total opportunity cost dengan memilih angka terkecil yang tidak dilewati garis. (pada contoh di atas = 15), kemudian mengurangkan angka yang tidak dilewati garis dengan angka terkecil (15), selanjutnya menambahkan angka yang terdapat pada persilangan garis dengan angka terkecil (15) yaitu (80) pada J1 dan (85) pada J4. Selanjutnya kembali ke langkah ke 3.
- Sehingga Revisi tabel menjadi:
- Maka Tabel Penugasannya adalah:
TEORI PERMAINAN
Merupakan pendekatan matematis untuk merumuskan situasi konflik antara
berbagai kepentingan. Dikembangkan untuk menganalisis proses pengambilan
keputusan dari situasi-situasi persaingan antara 2 pemain atau lebih.Model teori permainan ditentukan oleh :
- Jumlah pemain
- Jumlah keuntungan dan kerugian
- Jumlah strategi
Dalam teori permainan, lawan disebut
sebagai pemain (player). Setiap pemain memiliki sejumlah pilihan, yang
terhingga atau tak terhingga, yang disebut strategi. Hasil (outcomes atau
payoff) dari sebuah permainan diringkas sebagai fungsi dari strategi yang
berbeda-beda dari setiap pemain. Sebuah permainan dengan dua pemain, dimana
keuntungan satu pemain sama dengan kerugian pemain lainnya, dikenal sebagai
permainan jumlah-nol-dua-orang (two-person zero-sum game). Dalam permainan
seperti ini, hasil dapat dinyatakan dalam bentuk hasil untuk salah satu pemain.
Sebuah matriks dipergunakan untuk meringkaskan hasil kepada pemain yang
strateginya dinyatakan dalam baris-baris matriks yang bersangkutan.
Pemecahan optimal untuk permainan
jumlah-nol-dua-orang kemungkinan mengharuskan setiap pemain untuk memainkan
strategi murni (pure strategy) atau gabungan dari beberapa strategi murni yang
disebut sebagai strategi campuran (mixed strategy).
A. STRATEGI MURNI ( PURE STRATEGY )
Pemecahan
optimal dikatakan dicapai jika tidak ada satupun pemain akan memperoleh manfaat
dari perubahan strateginya. Dalam kasus ini, permainan tersebut dikatakan
stabil.
Kriteria
pemecahan masalah yang digunakan adalah kriteria minimaks-maksimin.
Contoh Kasus :
Pertimbangkan matriks hasil diatas, yang
mewakili keuntungan Pemain A. !
Perhitungan nilai minimaks dan maksimin diperlihatkan dalam matrik diatas
dengan penjelasan sebagai berikut :
Pemain A memainkan strategi pertamanya, ia
dapat memperoleh 8, 2, 9 atau 5, yang bergantung pada strategi yang dipilih
Pemain B. Tetapi, ia pasti memperoleh keuntungan setidaknya sebesar min {
8,2,9,5 } = 2 tanpa bergantung pada strategi yang dipilih Pemain B.
Demikian pula jika Pemain A memainkan strateginya yang kedua, ia dijamin
memperoleh setidaknya min { 6,5,7,18 } = 5, dan jika ia memainkan strateginya
yang ketiga, ia dijamin memperoleh setidaknya min { 7,3,-4,10 } =
-4. Jadi nilai minimum di setiap baris mewakili keuntungan minimum yang
dijamin bagi Pemain A jika ia memainkan strategi murni. Angka-angka ini
ditunjukkan dalam matriks tersebut pada ”Minimum dari baris”. Selanjutnya
dengan memilih strateginya yang kedua, Pemain A memaksimumkan keuntungan
minimumnya. Keuntungan ini diketahui max ( 2, 5, -4 ) = 5. Pemilihan Pemain A disebut
strategi maksimin, dan keuntungannya disebut nilai maksimin (nilai bawah) dari
permainan.
Sebaliknya, Pemain B ingin meminimumkan
kerugiannya. Ia menyadari bahwa, jika ia memainkan strategi murni
pertamanya, ia akan merugi tidak lebih dari max { 8, 6, 7 } = 8 tanpa
bergantung pada pemilihan Pemain A. Argumen serupa dapat juga dibuat untuk
ketiga strategi lainnya. Hasil yang bersesuaian ditunjukkan dalam matriks
diatas dengan ”Maksimum dari kolom”. Jadi Pemain B akan memilih strategi yang meminimumkan
kerugian maksimumnya. Strategi ini diketahui strategi kedua dan kerugian yang
bersesuaian diketahui min { 8, 5, 9, 18 } = 5. Pemilihan Pemain B disebut
sebagai strategi minimaks dan kerugiannya disebut sebagai nilai minimaks (nilai
atas) dari permainan.
Dari kondisi yang mengatur kriteria minimaks, nilai
minimaks (nilai atas) adalah lebih besar atau sama dengan nilai maksimin (nilai
bawah). Dalam kasus dimana persamaan berlaku, yaitu : nilai minimaks =
nilai maksimin, strategi murni yang bersangkutan disebut sebagai strategi
”optimal” dan permainan tersebut dikatakan memiliki titik sadel (saddle point).
Nilai permainan ini, dengan dipilihnya strategi murni yang optimal tersebut,
adalah sama dengan nilai maksimin dan minimaks tersebut.
Dalam contoh diatas, nilai maksimin = nilai minimaks = 5.
Hal ini menunjukkan bahwa permainan ini memiliki titik keseimbangan yang
diketahui dengan entri (2, 2) dari matriks tersebut. Karena itu nilai permainan
ini adalah 5.
B. STRATEGI
CAMPURAN ( MIXED STRATEGY )
Strategi campuran (mixed strategy) digunakan apabila tidak ditemukan saddle
point.
Contoh kasus :
Dalam kasus diatas tidak ditemukan saddle point, maka penyelesaiannya
terlebih dahululu dengan menggunakan aturan dominan, yaitu dengan cara sebagai
berikut :
- Suatu kolom disebut dominan / superior terhadap kolom lain, bila nilai seluruh kolom tersebut lebih kecil dari yang lain, maka kolom yang lebih besar dapat dihapus.
- Suatu baris disebut dominan / superior terhadap baris lain, bila nilai seluruh baris tersebut lebih besar dari yang lain, maka baris yang lebih kecil dapat dihapus.
Masih belum ditemukan saddle point, maka diselesaikan dengan menggunakan
strategi campuran.
Dilihat dari Pemain A :
Misalnya :
- Probabilitas Pemain A menggunakan strategi A1 = p
- Probabilitas Pemain A menggunakan strategi A3 = 1 – p
Ø Bila Pemain B menggunakan strategi B1,
keuntungan yang diharapkan oleh Pemain A adalah :
Ø Bila Pemain B
menggunakan strategi B2,
maka keuntungan
yang diharapkan oleh Pemain A adalah :
0 Comments