Soal Programa Dinamis

Perwakilan badan kesehatan dunia mendapat tugas untuk meningkatkan perawatan kesehatan dinegara-negara sedang berkembang. Badan tersebut memiliki 5 tim medis yang tersedia untuk dialokasikan diantara 3 negara sedang berkembang untuk meningkatkan perawatan kesehatan pendidikan kesehatan dan program-program pelatihan.
Oleh karena itu badan tersebut perlu untuk menentukan berapa banyak tim (jika ada) untuk dialokasikan pada masing-masing Negara tersebut untuk memaksimumkan efektifitas total dari kelima tim medis. Tim-tim tersebut harus tetap lengkap sehingga jumlah yang dialokasikan pada tiap-tiap Negara adalah integer.
Ukuran performance yang digunakan adalah penambahan tahun umur kehidupan orang (untuk beberapa Negara, ukuran ini sama dengan ekspetasi penambahan umur kehidupan di Negara tersebut dalam tahun dikalikan dengan populasinya).
Table dibawah ini memberikan tambahan umur kehidupan orang / penduduk (dalam perkalian peribuan) untuk tiap-tiap Negara untuk setiap alikasi tim medis yang memungkinkan.
Alokasi yang manakah yang memaksimumkan ukuran performansi?











Jawaban:
Perhitungan dimulai dari stage terakhir (n = 3) dan bergerak mundur hingga stage pertama (n = 1)
















Dengan demikian, maka solusi optimumnya adalah x1* = 1,
sehingga s = 5 – 1 = 4 untuk n =2. akibatnya x2* = 3.
selanjutnya s = 4 – 3 = 1 untuk n = 3 sehingga x3* = 1.
Karena f1* (5) = 170, maka alokasi (1, 3, 1) dari team kesehatan pada tiga Negara ini akan menhasilkan taksiran total 170.000 penambahan umur tahun kehidupan penduduk.

Soal Game Theory

Pertimbangkanlah game yang memiliki table payoff berikut:











Carilah saddle point dari game di atas!
Jawab:
• Nilai minimum pada baris:
Ke-1 = -4
Ke-2 = -4
Ke-3 = -1
Nilai minimaks = -1
• Nilai maksimum pada kolom:
Ke-1 = 3
Ke-2 = -1
Ke-3 = 2
Ke-4 = 1
Nilai maksimin = -1
Saddle point adalah bila nilai minimaks = maksimin. Jadi saddle point dari game di atas adalah -1.

Programa bilangan bulat

Merupakan bentuk lain dari programa linear (LP) dimana asumsi divisibilitasnya melemah atau hilang sama sekali. Bentuk ini muncul karena dalam kenyataannya tidak semua variabel keputusan dapat berupa bilangan pecahan. Asumsi divibilitas melemah, artinya sebagian dari nilai variabel keputusan harus berupa bilangan bulat (integer) dan sebagian lainnya boleh berupa bilangan pecahan. Persoalan integer programming (IP) dimana hanya sebagian dari variabel keputusan yang harus integer disebut sebagai persoalan IP campuran. Apabila seluruh variabel keputusan dari suatu persoalan programa linear (LP) harus berharga integer, maka persoalan tersebut sebagai persoalan programa bilangan bulat (IP) murni.

Menyelesaikan IP dengan teknik Cutting Plane
Pendekatan yang dilakukan dalam teknik cutting plane adalah dengan membuat pembatas tambahan yang memotong ruang fisibel dari LP relaksasi sehingga dapat mengeliminasi solusi yang tidak integer. Proses pemotongan akan terus berlangsung sehingga diperoleh solusi dengan seluruh variabel (yang dikehendaki) berharga integer. Keberhasilan teknik ini sangat terbatas, bergantung pada struktur persoalan yang dihadapi. Artinya, hanya persoalan tertentu yang dapat diselesaikan dengan teknik ini. Karena itu, sekarang teknik ini hamper tidak pernah digunakan lagi.

Sumber:
Dimyanti, Ahmad. Operations Research. Model-model pengambilan keputusan. Sinar Baru Algensindo. Bandung. 1999.


http://tugasuntukor2.blogspot.com/

Programa dinamis

Adalah suatu teknik matematis untuk membuat suatu keputusan dari serangkaian keputusan yang saling berkaitan. Model ini digunakan untuk mempermudah penyelesaian persoalan optimasi yang mempunyai karakteristik tertentu. Dasar dari programasi dinamis ini adalah membagi persoalan menjadi beberapa bagian yang lebih kecil sehingga memudahkan penyelesaiannya berbeda dengan programa lain. Persoalan programasi dinamis ini tidak ada formulasi matematis yang standar.

Karakteristik programa dinamis.
1. Persoalan dapat dibagi menjadi beberapa tahap (stage), yang masing-masing stage diperlukan adanya keputusan. Pada ilustrasi diatas, persoalan dibagi menjadi 4 stage. Pada tiap stage merupakan penempatan kota tujuan berikutnya yang harus ditempuh.
2. Masing-masing stage terdiri atas sejumlah state yang berhubungan dengan stage yang bersangkutan. Pada ilustrasi diatas, state yang berhubungan dengan masing-masing stagenya adalah kota yang dapat disinggahi pada masing-masing tahap perjalanan.
3. Hasil dari keputusan yang diambil pada setiap stage ditransformasikan dari stage yang bersangkutan ke state berikutnya pada stage yang berikutnya pula.
4. Keputusan terbaik pada suatu stage bersfat independent terhadap keputusan yang dilakukan pada stage sebelumnya.
5. Prosedur pemecahan masalah dimulai dengan mendapatkan cara (keputusan) terbaik untuk tiap stage dari stage terakhir.
6. Ada suatu hubungan timbale balik yang menidentifikasikan keputusan terbaik untuk setiap stage pada stage n, berdasarkan keputusan terbaik untuk setiap stage pada stage (n+1).
7. Dengan menggunakan hubungan timbale balik ini, prosedur penyelesaian bergerak mundur stage demi stage, pada setiap stage berusaha diperoleh keputusan optimum untuk masing-masing stage hingga akhirnya diperoleh eputusan optimum yang menyeluruh, mulai dari stage awal.

Programa dinamis deterministic
Suatu cara untuk mengategorikan persoalannya dengan cara melhat bentuk fungsi tujuan. Contoh, fungsi tujuannya mungkin meminimumkan jumlah kontribusi dari masing-masing stage atau dapat pula memaksimumkan atau meminimumkan hasil perkaliannya, dan sebagainya. Cara pengkategorian lainnya yang lain didasarkan pada keadaan dari kumpulan (set) state pada suatu stage. Artinya apakah state itu dapat direpresentasikan sebagai variabel state diskrit atau kontinu, atau mungkin diperlukan suatu vector state (lebih dari suatu variabel). Untuk dapat menentukan state-nya kta harus dapat menentukan pertanyaan seperti:
1. Apakah yang berubah dari suatu stage ke stage berikutnya?
2. Berdasarkan keputusan yang telah dibuat pada stage berikutnya dapat ditentukan?
3. Informasi apa tentang suatu stage yang diperlukan untuk menentukan keputusan optimum berikutnya.

Programa dinamis probabilistic
Berbeda dengan programa dinamis deterministic. Stage berikutnya tidak dapat seluruhnya ditentukan oleh stage dan keputusan pada stege saat ini, teapi ada suatu distribusi yang kemungkinan mengenai apa yang akan terjadi. Namun, distribusi kemungkinan ini masih seluruhnya di tentukan oleh state dan keputusan pada state saat ini. Struktur probabilistk ini mengakibatkan menjadi lebh rumit dari pada untuk prorama dinamis deterministik. Bentuk yang tepat untuk hubungan ini akan ergantung pada bentuk fungsi tujuan secara keseluruhan.

Sumber:
Dimyanti, Ahmad. Operations Research. Model-model pengambilan keputusan. Sinar Baru Algensindo. Bandung. 1999.

Struktur dasar model-model antrian.

Sumber input.
Karakteristik dari sumber input ini adalah ukurannya (jumlahnya), yaitu jumlah total unit yang memerlukan pelayanan dari waktu ke waktu disebut jumlah langganan potensial. Ini bisa dianggap terbatas ataupun tidak terbatas. Asumsi lain yang harus dispesifikasikan mengenai kelakuan unit-unit (langganan) yang memerlukan pelayanan ini adalah apa yang disebut balking, yaitu unit-unit yang memerlukan pelayanan itu akan menolak memasuki system antrian jika antrian itu terlalu panjang.

Antrian
Karakteristi suatu antrian ditentukan oleh jumlah unit maksimum yang boleh ada dalam sistemnya. Antrian ini dikatakan terbatas atau tidak terbatas, bergantung pada jumlah unitnya.

Disiplin pelayanan
Berkaitan dengan cara memilih anggota antrian yang akan dilayani. Contoh: disiplin pelayanan ini dapat berupa first come-first serve (yang dating lebih dulu dilayani lebih dulu), atau random, atau dapat pula berdasarkan prioritas tertentu. Asumsi yang digunakan adalah first come-first served.

Mekanisme pelayanan
Terdiri atas satu atau lebih fasititas pelayanan yang masing-masing terdiri atas satu atau lebih saluran pelayanan parallel. Jika ada satu atau lebih maka unit-unit yang memerlukan pelayanan akan dilayani oleh serangkaian fasilitas pelayanan. Suatu model antrian harus menetapkan urutan-urutan fasilitas semacam itu sekaligus dengan jumlah pelayanan pada masing-masing saluran parallel. Waktu yang digunakan sejak pelayanan dimulai sampai satu unit selesai dilayani, disebut waktu pelayanan (holding time). Biasanya diasumsikan bahwa distribusi kemungkinan dari waktu pelayanan ini adalah distribusi erlang atau distribusi eksponensial atau waktu pelayanan tetap (constant service time).

Sumber:
Dimyanti, Ahmad. Operations Research. Model-model pengambilan keputusan. Sinar Baru Algensindo. Bandung. 1999.

Elemen-elemen dasar teori permainan

Two-person, zero-sum game
Ada dua jenis persoalan Two-person, zero-sum game. Pertama, pemain yang posisi pilihan terbaiknya bagi bagi setiap pemain dicapa dengan memilih satu strategi tunggal sehingga permainannya disebut permainan strategi murni (pure-strategi game). Kedua, permainan yang kedua pemainnya melakukan pencampuran terhadap strategi-strategi yang berbeda dengan maksud untuk mencapai posisi pilihan terbaik. Disebut strategi permainan campuran (mixed-strategy game)

pure-strategi game
pemain yang akan memaksimumkan dan mengidentifikasi strategi optimumnya dengan menggunakan criteria maksimum, sedangkan pemain yang meminimumkan akan mengidentifikasi starategi optimumnya dengan menggunakan criteria minimaks. Jika nilai sama maka permainan telah terpecahkan. Dalam kasus seperti itu, maka telah terjadi titik keseimbangan. Disebut saddle point. Jika nilai maksimin tidak sama dengan minimaks, maka titik keseimbangan tidak akan tercapai dan berarti tidak dapat diselesaikan dengan strategi murni sebaliknya dilakukan dengan strategi campuran
criteria maksimin (untuk pemain yang memaksimumkan)
dapatkan nilai minimum dari masing-masing baris. Nilai terbesar (nilai maksimum) dari nilai-nilai minimum ini adalah nilai maksimin. Dengan demikian, maka untuk permainan dengan strategi murni ini, strategi optimumnya adalah baris tempat nilai maksimin terletak.
criteria minimaks (untuk permainan yang meminimumkan)
dapatkan nilai maksimum pada masing-masing kolom. Nilai terkecil (nilai minimum) dari nilai-nilai maksimum ini adalah nilai minimaks. Dengan demikian, maka untuk permainan dengan strategi murni ini, strategi optimumnya adalah kolom tempat nilai minimaks terletak.

mixed-strategy game
pada game yang tidak memiliki saddle point, penyelesainannya harus dilakukan dengan menggunakan strategi campuran. Para pemain dapat memainkan seluruh strateginya sesuai dengan set probabilitas yang telah ditetapkan. Solusi persoalan strategi campuran ini masih didasarkan pada kriteria maksimin dan minimaks. Perbedaanya adalah kolom memaksimumkan ekspektasi payoff terkecil, sedangkan baris meminimumkan ekspektasi payoff terbesar pada suatu baris. Seperti halnya strategi murni, pada strategi campuran berlakunya hubungan. Ada beberapa metode untuk menyelesaikan permainan jenis ini, diantaranya adalah dengan cara grafis dengan menggunakan program linier.

Sumber:
Dimyanti, Ahmad. Operations Research. Model-model pengambilan keputusan. Sinar Baru Algensindo. Bandung. 1999.

INTEGER PROGRAMMING

Dalam masalah integer programming, jika model mengharapkan semua variabel basis bernilai integer (bulat positif atau nol), dinamakan pure all integer programming. Jima model hanya mengharapkan variabel tertentu bernilai integer, dinamakan mixed integer programming. Dan jika model hanya mengharapkan nilai nol atau satu untuk variabelnya, dinamakan zero one integer programming.
a. Pendekatan pembulatan
Suatu pendekatan yang sederhana dalam menyelesaikan masalah integer programming adalah dengan membulatkan nilai variabel keputusan yang diperoleh melalui LP. Pendekatan ini mudah dan praktis dalam usaha, waktu, dan biaya yang diperlukan untuk memperoleh solusi. Bahkan pendekatan pembulatan merupakan cara yang efektif untuk masalah integer programming. Yang besar dimana biaya perhitungan sangat tinggi atau untuk masalah dimana nilai-nilai solusi variabel keputusan besar.
b. metode grafik
masalah yang hanya melibatkan dua variable dapat diselesaikan secara grafik. Pendekatan ini identik dengan metode grafik linear programming kecuali solusi optimum harus memenuhi persyaratan bilangan bulat. Pendekatan yang termudah untuk menyelesaikan masalah integer programming dua dimensi adalah dengan menggunakan kertas grafik dan mengambarkan sekumpulan titik integer dalam ruang solusi layak.
c. metode gomory (cutting plane algorithm)
suatu prosedur sistematik untuk memperoleh solusi integer optimum terhadap pure integer programming pertama kali dikemukakan oleg R.E Gomory pada tahun 1958. Langkah-langkah prosedur gomory adalah:
• Sewlesaikan integer programming menggunakan metode simpleks jika masalahnya sederhana diselesaikan dengan pendekatan grafik sehingga pendekatan gomory kurang efisien.
• Periksa solusi optimum, jika variabel basis memiliki nilai integer, solusi optimum integer telah diperoleh dan proses solusi berakhir. Jika satu atau lebih variable basis memiliki nilai pecah terus ketahap selanjutnya.
• Buat suatu kendala gomory (suatu bidang pemotong atau cuttingplane) dan cari solusi optimum selalui prosedur dual simpeks.
d. metode branch & bound
metode ini diperkenalkan oleh and dan doig, dan dikembangkan lebih lanjut oleh little dan peneliti lainnya. Teknik ini dapat diterapkan untuk masalah pure maupun mixed integer programming. Langkah untuk metode maksimasi adalah:
• Selesaikan masalah linear programming dengan metode simpleks biasa tanpa pembatas bilangan bulat.
• Teliti solusi uptimumnya. Jika variabel basis yang diharapkan buat maka telah tercapai. Jika satu atau lebih variabel basis yang diharapkan bulat ternyata tidak bulat, lanjutkan langkah selanjutnya.
• Nilai solusi pecah yang layak dicabangkan kedalam sub-sub masalah. Tujuannya adalah untuk menghilangkan solusi kontinu yang tidak memenuhi persyaratan bulat dari masalah ini.
• Nilai solusi optimum kontinu fungsi tujuan ditetapkan sebagai batas atas. Solusi bulat terbaik menjadi batas bawah. Sub-sub masalah memiliki batas atas kurang dari batas bawah yang suatu solusi bulat layak adalah sama baik atau lebih baik dari batas atas untuk setiap submasalah yang dicari.

Sumber;
Mulyono. Sri, S.E.,M.Sc. Riset Operasional. Fakultas Ekonomi Universitas Indonesia. 2002.