1 TINJAUAN MATA KULIAH I.1. Deskripsi Singkat Mata Kuliah Berdasarkan GBPP (Garis-Garis Besar Program Pengajaran) dan kurikulum revisi(2004)jurusanTeknikIndustri,FakultasTeknikUniversitasMalikussaleh Tahun2004,padamatakuliahpenelitianoperasionalIIiniakandibahas mengenai:pengertiansingkatdanmenyeluruhdaripenelitianoperasionalII, analisisjaringan,perencanaan&pengendalianproyekdenganCPMPERT, programadinamis,teoripermainan,rantaiMarkovdanteoriAntrianpadasuatu perusahaan industri. I.2. Kegunaan Mata kuliah Bagi Mahasiswa MatakuliahpenelitianoperasionalIIinimemilikibeberapakegunaanbagi mahasiswa nantinya, antara lain sebagai berikut: 1.Padasuatuperusahaandapatdiketahuibagaimanaanalisisjaringan, perencanaan&pengendalianproyeksuatukegiatanproduksiyangnantinya akandibutuhkanpadasuatuperusahaanterutamadalammenghasilkansuatu produk yang efektif dan efisien. 2.MahasiswadapatmengertidanmemahamikonseppenelitianoperasionalII secaramenyeluruhdanbagaimanapenerapannyapadasuatuperusahaan industri. 3.Dalamkehidupansehari-harimahasiswanantinyamampumenilai, mengevaluasisegmentasipasardanperkembanganprodukdengan menggunakan suatu sistemyang terdapat padapenelitian operasionalII,yang nantinya sangat berguna untuk pengembangan suatu perusahaan. 4.Mahasiswa mampu memahami bagaimana cara mengambil keputusan industri, baikitumelaluisuatupendekatantertentuataupunlangsungdengan menggunakan sumber daya yang ada. 5.Dalamsuatuperusahaanindustri,mahasiswanantinyamampumelihatdan menilaiberhasiltidaknyasuatuperusahaandalammengambilkeputusan berkaitan dengan kinerja, sumber daya dan kompetensi suatu perusahaan. 2 I.3. Tujuan Instruksional Umum (TIK)TujuanInstruksionalUmum(TIK)penelitianoperasionalIIyangterdapat dalamGBPPjurusanTeknikIndustri,FakultasTeknikUniversitasMalikussaleh Tahun2004menjelaskanbahwadenganmempelajarimatakuliahpenelitian operasionalIIinidiharapkanmahasiswamampumemahamimengenaiberbagai modeloptimasidanpengambilankeputusansertamampumenerapkandisiplin ilmu dalam penelitian operasional II tersebut dalam kehidupan sehari-hari. I.4. Susunan (Urutan) Bahan AjarAdapunsusunan(urutan)bahanajardariperkuliahanpertamasampai dengan perkuliahan terakhiradalah sebagai berikut: PERKULIAHAN KE 1:1.Pengantar Penelitian operasional II 1.1. Sejarah singkat perkembangan penelitian operasional 1.2. Komponen-komponen utama persoalan keputusan. 1.3. Model-model dalam penelitian operasional. 1.4. Metodologi penelitian operasional. PERKULIAHAN KE 2 DAN 3:2.Analisis Jaringan2.1.Pengantar Analisis Jaringan 2.2.Konsep Dan Definisi2.3.Algoritma Path2.4.Tree Problem.2.5.FlowProblem. PERKULIAHAN KE 4 DAN 5:3.Perencanaan & Pengendalian Proyek dgn CPM PERT. 3.1. Simbol-simbol yang digunakan. 3.2. Penentuan Waktu. 3 3.3. Perhitungan maju & Perhitungan mundur. 3.4. Perhitungan kelonggaran waktu. 3.5. Pembuatan peta waktu & Pengaturan sumber daya. 3.6. Perkiraan waktu penyelesaian suatu aktifitas. 3.7. Penentuan ongkos dalam penjadwalan proyek. PERKULIAHAN KE 6 DAN 7:4. ProgramaDinamis 4.1. Pengantar ProgramaDinamis 4.2 Teknik penyelesaian persoalan denganPrograma Dinamis PERKULIAHAN KE 8:5. Ujian mid semester. PERKULIAHAN KE 9, 10 DAN 11:6. Teori Permainan 6.1. Pengantar Teori Permainan. 6.2. Two person, Zero-Sum Game. 6.3.Pure-Strategy Game 6.4. Mixed-Strategy Game. 6.5. Solusi Grafis dari permainan (2xn) dan (mx2). 6.6.Solusi permaianan (mxn) dgn programa linier. PERKULIAHAN KE 12 DAN 13:7. Proses Keputusan Markov7.1. Pengantar proses keputusan Markov. 7.2. Ilustrasi Persoalan Keputusan Markov 7.3. Membangun Matriks Probabilitas Transisi 7.4. Model Program Dinamis dengan Stage Terbatas 7. 5. Model dengan Stage tidak Terbatas 4 PERKULIAHAN KE 14 DAN 15:8. Teori Antrian 8.1. Pengantar Teori antrian 8.2. Contoh Sistem Antrian PERKULIAHAN KE 16:9. Ujian semester. I.5. Petunjuk Bagi Mahasiswa Dalam mempelajari materi dalam setiap babtersebut diharapkan mahasiswa memilikiliteratureataubahanpeganganbaikberupatextbook,jurnalmaupun ringkasanmateridaribuku-bukuyangberkaitandennganmatakuliahpenelitian operasionalII,halinisangatbergunabagikelangsunganprosesbelajarmengajar pada mata kuliah penelitian operasional II ini. 5 PERKULIAHAN KE 1: PENGANTAR PENELITIAN OPERASIONAL II SESI/PERKULIAHAN KE: 1 TIK : Pada akhir perkuliahan ini mahasiswa diharapkan mampu: 1.Menjelaskan pengertian penelitian operasional. 2.Mengetahuikomponen-komponenyangdiperlukandalam pengambilan keputusan. Pokok Bahasan:Pengantar Penelitian operasional II Deskripsi singkat : Dalam pertemuan ini anda akan mempelajari beberapa pengertian yang berkaitan dengan penelitian operasional, memahami dan mengetahui Komponen-komponen utamapersoalankeputusan,model-modeldalampenelitianoperasionaldan metodologipenelitianoperasionalyangnantinyadapatditerapkandalam meyelesaikan persoalan pengambilan keputusan. I.Bahan Bacaan: 1.DonT.Philips,et.al.,OperationResearch:PrincipleandPractice,2nd edition, John Wiley and Sons, 1987. 2.HillierandLieberman,IntroductiontoMathematicalProgramming,1st edition, McGraw-Hill, 1991. 3.Taha,Hamdy,OperationResearch:AnIntroduction,Newyork:The MacMillan Co, 1985. II. Bahan Tambahan: 1.Dimyati,TjutjuTarliah,AhmadOperationsResearch,PT.SinarBaru Algensindo Bandung, 1999. 2.Wagner, H.M.PrincipleofOperationResearch, Englewood Cliffs, N.J : Prenntice-hall Inc, 1969. 3.Hillier,FrederickandGerald,J.Liebermam.IntroductiontoOperation Research , San Fransisco : Holden Day Ltd, 1977. 4.Wayne L.Winston, Operation Research: Application and Algorithms, 3rd edition, Duxbury Press, 1994. III.Pertanyaan Kunci/Tugas:Ketikaandamembacabahanbacaanberikut,gunakanlahpertanyaan-pertanyaan sebagai berikut: 1.Apa yang dimaksud dengan penelitian operasional? 2.Apa kegunaan mempelajari penelitian operasional? IV.Tugas: 1.Definisikanpengertianpenelitianoperasionalmenurutliteraturyanganda baca dan jelaskan pengertian tersebut sesuai dengan pendapat anda! 2.Carilahcontohkasuspersoalankeputusanyangberkaitandenganpenelitian operasional II! 3.Jelaskanlangkah-langkahdalammemecahkansuatupersoalankeputusan dalam suatu organisasi! 6 1.1.PENDAHULUAN DalamperkuliahanpengantarpenelitianoperasionalIIiniakandibahas mengenaisejarahsingkatperkembanganpenelitianoperasional,komponen-komponen utama persoalan keputusan, model-model dalam penelitian operasional dan metodologi penelitian operasional. Materi yang disampaikan sangat berkaitan antarasatudenganyanglainnya,halinibergunadalammenghasilkansuatu keputusan yang optimal dalam menyelesaikan suatu persoalan keputusan. 1.2.PENYAJIAN PENGANTAR PENELITIAN OPERASIONAL II 1.1. Sejarah Singkat Perkembangan Penelitian Operasional PadamasaPerangDuniaII,angkatanperanginggrismembentuksuatu teamyangterdiriatasparailmuwanuntukmempelajaripersoalan-persoalan strategisdantaktiksehubungandenganserangan-seranganyangdilancarkan musuh terhadap negaranya.Tujuannyaadalahuntukmenentukanpenggunaansumber-sumber kemiliteranyangterbatassepertiradardanbomber,dengancarayangpaling efektif.Karenatimmelakukanresearch(penelitian)terhadapoperasi-operasi militer,makamuncullahnamaMilitaryOperationResearch(penelitian operasionalkemiliteran),yangsejakawaltelahditandaidengandigunakannya pengetahuanilmiahdalamusahamenentukanpenggunaansumber-sumberdaya yang terbatas. HalyangserupadilakukanolehangkatanperangAmerikauntuk membentuktimyangmerekasebutteamOperationResearch.Merekaberhasil dalammemecahkanpersoalan-persoalanlogistik,suplybarang-barangkeperluan perang dan menentukan pola-pola dasar jaringan bagi operasi alat-alat elektronik.SetelahPerangDuniaIIberakhir,OperationResearchyanglahirdi InggrisinikemudianberkembangpesatdiAmerikakarenakeberhasilanyang dicapai oleh teamOperation Research tersebut,yang akhirnya menarik perhatian 7 orang-orangdiperindustrian.Sedemikianpesatperkembanganyakinimaka PenelitianOperasionaltelahdigunakanhampirpadaseluruhkegiatan,baik diperguruan tinggi, konsultan, rumah sakit, perencanaan kota dll. 1.2. Komponen-Komponen Utama Persoalan Keputusan. Munculnya persoalan-persoalan keputusan adalah karena seorang pengambil keputusanseringdihadapkanpadabeberapapilihantindakanyangharus dilakukan.Dalammenyelesaikanpersoalanyangberkaitandenganpengambilan keputusan ini harus diidentifikasikan terlebih dahulu 2 (dua) komponen utamanya, yaitu: 1.Objective (tujuan). 2.Variabel-variabel. Tujuan(objective)adalahhasilakhiryanghendakdicapaidengancara memilihsuatutindakanyangpalingtepatuntuksistemyangdipelajari.Dalam bidang-bidangusaha,tujuandiartikansebagaimemaksimumkanprofitatau meminimumkanongkosyangdikeluarkan.Akantetapidalambidang-bidang lainyangsifatnyanon-profit(tidakmencarikeuntungan),tujuandapatberupa pemberian kualitas pelayanan kepada para konsumen. Apabilatujuantelahdidefinisikan,makaselanjutnyaharusdilakukan pemilihantindakanterbaikyangdapatmencapaitujuantersebut.Dalamhalini, kualitaspemilihanakansangatbergantungkepadatahuatautidaknyasi pengambil keputusan dalam mencapai alternatif yang diharapkan tersebut. Untukdapatmenentukantindakan-tindakanyangmungkindilakukanitu maka haruslah diidentifikasikan variabel-variabel sistem yang dapat dikendalikan olehpengambilkeputusan,yangkeberhasilannyadalammengidentifikasikan variabel-variabelinipunakansangatbergantungpadabiasdanpelatihansi pengambil keputusan. 8 1.3. Model-Model dalam Penelitian Operasional. Modeladalahgambaranidealdarisuatusituasi(dunia)nyatasehingga sifatyayangkompleksdapatdisederhanakan.Adabeberapajenismodelyang biasa digunakan, diantaranya ialah: a.Model-model fisik/ ikonisYaituPenggambaranfisikdarisuatusistem,baikdalmbentukidealmaupun dalam skala yang berbeda. Contoh: Peta, foto, blueprint, globe. b.Model-model Analogi/ diagramatis Model-model ini dapat menggambarkan situasi-situasi yang dinamis dan lebih banyakdigunakandaripadamodel-modelikoniskarenasifatnyayangdapat dijadikan analogi bagi karakteristik sesuatu yang sedang dipelajari.Contoh:Kurvadistribusifrekuensipadastatistik,kurvasupplydemand,flow chart. c.Model-model Simbolis/ MatematisYaitu Penggambaran dunia nyata melalui simbol-simbol matematis.PadaawalnyaModel-modelSimbolis/Matematisiniberupamodel-model abstrakyangdibentukdidalampikiranseseorangyangkemudiandisusun menjadi model-model simbolis, seperti gambar, simbol atau rumus matematis. Model matematis yang paling banyak digunakan dalam penelitian operasional adalah model matematis berupa perasamaan atau ketidak samaan. d.Model-model simulasiYaituModel-modelyangmenirutingkahlakusistemdenganmempelajari interaksikomponen-komponennya.Dalamhalinitidakdiperlukanfungsi-fungsimatematissecaraeksplisituntukmerelasikanvariabel-variabelsistem, Model-modelsimulasiinidapatdigunakanuntukmemecahkansistem kompleksyangtidakdapatmemberikansolusiyangbenar-benaroptimum. Dimana jawaban yang dapat diperoleh ialah jawaban yang suboptimum, yaitu jawaban optimum dari alternatif-alternatif yang diuji/ dites. 9 e.Model-model heuristikKadang-kadangformulasimatematisbersifatsangatkompleksuntukdapat memberikansuatusolusiyangpasti.Ataumungkinsolusioptimumdapat diperoleh,tetapimemerlukanprosesperhitunganyangsangatpanjangdan tidakpratktis.Heuristicyaitusuatumetodepencarianyangdidasarkanatas aturan-aturantertentuuntukmemperolehsolusiyanglebihbaikdaripada solusi yang telah dicapai sebelumnya. Dalampenelitianoperasional,modelyangpalingbanyakdigunakanadalah model matematis/ simbolis. Disamping itu, digunakan juga model-model simulasi dan heuristic. 1.4. Metodologi Penelitian Operasional JikaPenelitianoperasionalakandigunakanuntukmemecahkansuatu persoalandisuatuorganisasi,makaharusdilakukan5(lima)langkahsebagai berikut: Langkah 1:MemformulasikanPersoalan,mendefinisikanpersoalanlengkapdengan spesifikasitujuanorganisasidanbagian-bagianorganisasiatausistemyang bersangkutan.Halinimutlakharusdipelajarisebelumpersoalannyadapat dipecahkan.Langkah 2:MengobservasikanSistem,kumpulkandatauntukmengestimasibesaran parameteryangberpengaruhterhadappersoalanyangdihadapi.Estimasiini digunakanuntukmembangundanmengevaluasimodelmatematisdari persoalannya. Langkah 3:Memformulasikanmodelmatematisdaripersoalanyangdihadapi.Dalam memformulasikanpersoalaninibiasanyadigunakanmodelanalitik,yaitumodel matematisyangmenghasilkanpersamaan.Jikapadasuatusituasiyangsangat 10 rumittidakdiperolehmodelanalitik,makaperludikembangkansuatumodel simulasi.Langkah 4:Mengevaluasimodeldanmenggunakannyauntukprediksi.Padalangkahini, tentukanapakahmodelmatematisyangdibangunpadalangkah3telah menggambarkankeadaanyangnyatasecaraakurat.Jikabelumbuatlahmodel yang baru. Langkah 5:Mengimplementasikanhasilstudi,Padalangkahinkitaharusmenterjemahkan hasilstudiatauhasilperhitungankedalambahasasehari-hariyangmudahdi mengerti. 1.3.PENUTUP Padabagianpenutup,diadakantanyajawabdandiskusibaikantar mahasiswa dan dosen, dan juga mahasiswa antar mahasiswa. Untuk itu diberikan juga tugas sebagai bahan latihan mahasiswa di luar jam perkuliahan. Tugas/latihan untuk pengantar penelitian operasional II adalah sebagai berikut: 1.Definisikanpengertianpenelitianoperasionalmenurutliteraturyanganda baca dan jelaskan pengertian tersebut sesuai dengan pendapat anda! 2.Carilahcontohkasuspersoalankeputusanyangberkaitandenganpenelitian operasional II! 3.Jelaskanlangkah-langkahdalammemecahkansuatupersoalankeputusan dalam suatu organisasi! 11 PERKULIAHAN KE 2 DAN 3: ANALISIS JARINGAN SESI/PERKULIAHAN KE: 2 DAN 3 TIK : Pada akhir perkuliahan ini mahasiswa diharapkan mampu: 1. Menjelaskan pengertian jaringan dalam persoalan keputusan. 2. Menyelesaikan persoalan keputusan mengenai analisis jaringan.Pokok Bahasan:Analisis Jaringan Deskripsi singkat : Dalampertemuaniniandaakanmempelajaribeberapapengertianyang berkaitandengananalisisjaringan,memahamidanmengetahuipersoalan algoritmapath,treeproblem,flowproblemtermasukpersoalanruteterpendek, persoalanrentangpohonminimumdanpersoalanaliranmaksimumpadasuatu jaringan kerja.I.Bahan Bacaan: 1.HillierandLieberman,IntroductiontoMathematicalProgramming,1st edition, McGraw-Hill, 1991. 2.Hillier,FrederickandGerald,J.Liebermam.IntroductiontoOperation Research , San Fransisco : Holden Day Ltd, 1977. 3.Taha,Hamdy,OperationResearch:AnIntroduction,Newyork: The MacMillan Co, 1985. II.Bahan Tambahan: 1. DonT.Philips,et.al.,OperationResearch:PrincipleandPractice,2nd edition, John Wiley and Sons, 1987. 2. Wayne L.Winston, Operation Research: Application and Algorithms, 3rd edition, Duxbury Press, 1994. III.PertanyaanKunci/Tugas:Ketikaandamembacabahanbacaanberikut, gunakanlah pertanyaan-pertanyaan sebagai berikut: 1.Apa yang dimaksud dengan jaringan? 2.Sebutkan contoh-contoh jaringan kerja! IV.Tugas: 1.Seorangpemudamengendaraimobildarikotaasalnyamenujukotayanglain.Dia mempunyaibeberapapilihanruteyangmelaluikota-kotaantara,jaraksuatukota dengan kotayanglain dalamsuatu ruteadalahseperti terlihatdalamnetworkberikut. Rutemanakahyangharusdilaluiagarjarakyangditempuholehorangtersebut minimum? 2.Carilah Jumlah unit maksimum suatu path dari s ke t dimana seluruh arc dari path itu termasuk di dalam sei I (Increasable path)! i(s,1)=5 i(1,2)=3i(2,t)=2 Kota Tujuan S C D B 5 3 3 3 2 A 3 T 7 Kota Asal Jarak Kota Antara 13 S12t 12 II.1. PENDAHULUAN DalamperkuliahanmengenaiAnalisisJaringaniniakandibahas mengenaipengertiandankonsepanalisisjaringan,memahamidanmengetahui persoalan rute terpendek, persoalan rentang pohon minimum dan persoalan aliran maksimumpadasuatujaringankerja.Materiyangdisampaikansangatberkaitan antarasatudenganyanglainnya,halinibergunadalammenghasilkankeputusan yangoptimaldalammenyelesaikanpersoalankeputusandalamsuatujaringan kerja. II.2. PENYAJIAN ANALISIS JARINGAN 2.1. Pendahuluan Networktheory(TeoriAnalisis Jaringan)adalahcabang-cabangmatematik yang digunakan secara luas dalam bidang praktek. Banyak problemayang timbul dalamberbagaibidangsepertipsikologi,kimia,tekniklistrik,transportasi, manajemen,pemasaran,danpendidikandapatdigambarkandidalambentuk problemadariNetworkTheory.OlehkarenaituNetworkTheorytidakhanya dikenal dan dikembangkan oleh kalangan sendiri, tetapi juga diikembangkan dari bidang-bidang lain. Network Theory tumbuh dan berkembang pesat pada awal abad ke 20 (dua puluh) dengan dimotivasi oleh perkembangan dari teori molekul dan teori listrik. Kiniperkembangananalisisjainganinimakincepatlagisetelahditemukannya alat komputer. Pengertianataudefinisi-definisiyangumumdijumpaidalamanalisis jaringan ini akan di bahas secara mendetail termasuk didalamnya berbagai model danuraiansingkatmengenaianalisisjaringansepertipersoalanShortestPath Problem(S.P.P),SpanningTreeProblem(S.T.P),FlowProblem(F.P),yang dilengkapi dengan algoritma penyelesaian optimum. Graph G adalah suatu bangun (struktur) yang terdiri satu set elemen N yang disebut node dan satu set elemen A yang disebut Arc. Secara Umum suatu graph dituliskan dengan notasi G (N,A), dimana: 13 N = Set dari node (1,2,3,..n) A = Set dari Arc (a,b,c,.....n)yang masing-masing menghubungkan suatu node dengan node yang lain. Sebagaicontoh,susunandarisatusetnodeN(1,2,3,4)dansatusetarc (a,b,c,d,e,f,g)membentuksuatugraphyangsalahsatudiantaranyaadalahdapat dilihat pada Gambar 2.1. berikut. Gambar 2.1. susunan dari satu set node N dan satu set arc membentuk graph Network(jaringan)adalahsuatugraphdimanaelemen-elemenApada graph tersebut merupakan suatu aliran . Contoh dari suatu network adalah sistem jaringan jalan raya yang menghubungkan kota-kotayangadapadasuatudaerah.Sebagainodedalamjaringantersebut adalah setiap kotayangada dalam jaringan tersebut dan sebagai arcadalah jalan raya yang menghubungkan satu kota dengan kota yang lain. Bobot dari Arc adalah dapatberupajarak,ongkosangkutataupunlamanyaperjalanandarisatukotake kota yang lain. 2.2. Konsep Dan Definisi Suatuarcyangmempunyainodeyangsamauntukkeduaujungdan pangkalnya disebut loop. C adalah Loop. Node Arc 1 2 4 3 a b c d f 32 c3 14 Sebuahnodedansebuaharcdisebutincedentsatusamalain,jikanode tersebutadalahmerupakanujungataupunpangkaldariarcyang bersangkutan. Dua buah arc dikatakan incedent satu sama lain, jika keduanya incedent kepada node yang sama. Duabuahnodedisebutadjacentsatusamalain,jikaadasebuaharc menghubungkan keduanya. Chainadalahbeberapaarcyangberurutandidalamsatugraphatau network. Panjangsuatuchainadalahsamadenganbanyaknyaarcdalamchain tersebut. Path adalah suatu chain yang dibentuk oleh beberapa arc yang searah. a 123 b Arcadannode2adalah incedent satu sama lainnya. Arcadanbadalahincedentsatu samalainnyakarenakeduanya incedent kepada node 2. Node 2 dan 3 adalah adjacent satu samalainnyakarenaadasatuarc yaituarcbmenghubungkan keduanya. a 123 b Arc a, e, h dan i adalah chain. a 1 3 b 5 46 72 i c e d h g f Arca,d,gdaniadalah sebuahpathyangarahnya dari node 6 ke node 1. Node6disebutnodeawal dannode1disebutnode akhir. a 1 3b 5 46 72 i c e d h g f a 123 b 15 Cycleadalahsuatuchainyangmempunyainodeawaldannodeakhir yangidentikataudengankatalain,cycleadalahsuatuchainyang tertutup. Circuitadalahsuatupathyangmempunyainodeawaldannodeakhir yangidentik,ataumerupakansuatupathyangtertutup.Dalamgambar di atas arc a, b dan c membentuk suatu circuit. Panjang suatu cycle dan circuitdidalamgraphadalahbanyaknyaarcyangmembentukcycle atau circuit tersebut. Suatugraphdisebutconnectedjikaterdapatsedikitnyasatuchaindari suatu node kepada setiap node yang lain di dalam graph tersebut. Arc c, e, h dan i membentuk suatu cycle. a 1 3 b 5 46 72 i c e d h g f Darisetiapnodeterdapat sedikitnyasatuchainkepada setiap node yang lain. a 1 3 b 5 4 6 7 2 i c e d h g f e 1 5 4 7 6 a c i f g b Sub-graph 2 Sub-graph 1 2 16 -Graphinitidakconnected,karenatidaksemuanodemempunyaichain kepada setiap node yang lain. Misalnya antara node 2 dengan node 4 tidak terdapatchain.Graphtersebutterdiridari2sub-graphdandisebutun-connected graph. -SuatusubgraphdariG(N,A),adalahsuatugraphGyangterdapatterdiri dariseluruharcdarisetAyangmenghubungkannodedidalamsubset tersebut. -SuatupartialgraphdariG(N,A)adalahsuatugraphyangterdiridari semua node N dan satu sub-set arc A. -Suatu graph G(N,A) dengan arc yang arahnya ditetapkan disebut directed graph. Bila arah dari arc tidak ditetapkan, maka disebut undirected graph. 7 6 5 42 1 a 3 d b e h i g c f j 2 4 5 3 1 a c b e f d 2 4 5 3 1 a c e b d 6 7 f 7 6 5 42 1 a 3 d b e h i g c f j 7 6 5 42 1 a 3 c b d f h g e i 17 -TreedarisuatuconnectedgraphG(N,A)adalahsuatuconnectedpartial sub-graph. Tree terdiri dari satu sub-set dari node dan satu sub-set dari arc yang menghubungkan sub-set node dan tidak membentuk cycle. -SpanningTreedarisuatuconnectedgraphadalahsetiaptreeyang terbentuk dari arc dan seluruh node dari graph tersebut. -Arborescenceadalahsuatutreedimanatidakterdapat2arcataulebih yangberujung pada node yang sama. 7 6 4 a 3 d b e h i g c f j 5 2 1 Tree Node(1,2,3,4dan5)dengan Arc(a,c,ddane)membentuk tree. Bukan Tree Graph yang dibentuk oleh Node (1,2,3,4 dan 5) dengan Arc (a,b,c,d dan e) bukan tree karena terdapat cycle. 6 4 1 a 3 c b d f h g e i 2 5 7 7 6 4 a 3 d b e h i g c f j 5 2 1 Spanning TreeGraphyangdibentukolehNode (1,2,3,4,5,6dan7)denganArc (a,c,d,e,f dan i). 1 426 5 3 a b c d e 18 -Spanning arborescence adalah arborescence dari spanning tree. 2.2.1. Matrix dari graph Setiap graph dapat jugadigambarkan dalam bentuk matriks. Ada beberapa macammatriksyangdapatdibuatuntukmenggambarkansuatumatriksdimana cara penggambaran tiap matriks ditentukan oleh penggunanya. Dalambagianinihanyadiuraikanduamacampenggambaransajayaituyang disebut incedence matrix dan adjaccency matrix. a.Incidence matrix Incidence matrix E dari suatu graph G dibentuk dengan cara berikut. Kolomdarimatriksadalahmerupakansetiaparcdanbarismatriksadalah node. Elemen-elemen dari matriks disebut eij ditentukan dengan cara berikut. Matrix dari undirected graph Elemen-elemen dari matriks untuk undirected graph adalah: -eij = 1, jika node i adalah salah satu ujung dari arc. -eij = 0, jika node i tidak merupakan salah satu ujung dari arc j. Contoh:

abcdefG 11100000 21011000 30110110 40001011 50000101 Graph G (N,A) E= 1 4 5 3 a b c d e f 2 g 1 4 6 5 3 a b c d e 7 f 2 19 DarimatriksEiniterlihatbahwabanyaknyabarismatriksadalahsama denganbanyaknyanode(n)padagraph6(N,A)danbanyaknyakolom.Sama dengan banyaknya arc (a) dari graph tersebut, sehingga matriks terbentuk adalah matriks E (n x a). -Matriks dari directed graph. Elemen-elemen eij dari matriks untuk indirected graph adalah: -eij=1,jikaarc jadalahincidentdengannodeidanarahnyamenujunodei tersebut. -eij = -1, jika arc j adalah incident dengan node i dan arahnya tidak menuju node i tersebut. -eij=0, jika arc j adalah tidak incident dengan node i. Contoh: abcdEfg 1-1100000 2101-1000 30-1-10-110 400010-11 5000010-1 b.Adjacency matrix -Adjacency matriks E dari suatu graph G dibentuk dengan cara berikut. Baris dan kolom matriks adlah merupakan selutuh node dari graph. Sama halnya dengan incidence matrix, elemen-elemen dari adjcency matrix (eij) untukundirected graph berbeda dengan elemen-elemen matriks untuk directed graph. (1). Undirect adjacency matrix. Elemen-elemendariundirectadjacencyeij,didefinisikansebagai berikut: -eij =1, jika arc yang menghubungkan node i dengan node j.-eij = 0, jika tidak ada arc yang menghubungkan node i dengan node j. E= 1 4 5 3 a b c d e f 2 g 20 Contoh: 12345 101100 210110 311011 401101 500110 (2). Direct adjacency matrix. Elemen-elemendariundirectadjacencyeij,didefinisikansebagai berikut: -eij =1, jika ada sebuah arc yang berasal dari node i menuju node j.-eij = 0, yaitu: - jika ada sebuah arc yang berasal dari node j menuju node i.- Jikatidakadasebuaheijyangmenghubungkannodeidan node j.Disiniterlihatbahwabaikundirectadjacencymatrix,maupundirect adjacencymatrixkeduanyamarupakanmatriksbujursangkarE(nxn)karena masing-masingdibentukdarihubunganantaranodedengannodepadasuatu graph. Salahsatutujuanutamadaripenggambarangraphdannetworkkedalam bentuk matriks adalah untuk komputerisasi dari graph dan network tersebut. Penggambarangraphdannetworkdalambentukdiagramditujukanhanyauntuk memperlihatkan hubungan antara keadaan sistem nyata dengan node diagramnya. Denganpenggambarandemikianakanditemukankesulitandidalammanipulasi graph dan network. Untuk tujuan optimisasi karena peranan komputer tidak dapat dimanfaatkansemaksimalmungkin.Komputerdapatmenyimpandan memanipulasiangka-angkadenganmudah,tetapitidakdapatmenyimpansecara langsung inforamasi yang berbentuk gambar atau diagram E= 1 4 5 3 a b c d e f 2 g 21 2.2.2 Matrix dari network. Padauraiansebelumnyasudahdijelaskanbahwanetworkadalahsuatu graph dengan arc yang mempunyai aliran. Network ditulis dengan notasi W (N,A,d), dimana:N = set dari node (1,2,,n) A = set dari arc (a,b,....................) di = bobot dari arc i. Suatu network disebut non negatif jika di>0 untuk seluruheijeE. Adjacencymatrixdarinetworkadalahidentikdenganadjacencymatrix dari graph hanya saja elemen-elemen matriks ditentukan oleh arah dari setiap arc dari network tersebut.Contoh dari sebuah network adalah seperti terlihat dalam gambar berikut. Networkiniadalahmerupakansuatujaringanjalanrayadisuatudaerah Node (1, 2, 3, 4, 5) adalah kota-kota yang dilintasi oleh jalan raya tersebut. Arc (1-2) adalah jarak antar kota 1 dengankota 2 dan seterusnya. Samahalnyadengangraphpadanetworkjugaditemukanbentukundirecteddan directed network. 2.3. Algoritma Path Dalambagianiniakandiuraikanbeberapaalgoritmauntukmencaripath yang mempunyai sifat-sifat optimum tertentu. -Pertama adalahalgoritma untuk mencari pathyang terpendek (shortespath) antara dua node didalam suatu network,-Keduaadalahalgoritmauntukmencaripathyangterpendekdiantarasetiap pasang node didalam network. 1 4 5 3 3 2 4 1 6 2 2 3 22 2.3.1.Algoritma Terpendek Antara Dua Node Tertentu. Contoh-contoh problema dan mencari arc yang terpendek adalah: Contoh 1. Seorangsupirsedangbepergiandenganmengendaraimobildarikota asalnyamenujukotayanglain.Untukmencapaikotatujuantersebut,dia mempunyai beberapa pilihan ruteyang melalui kota-kota antara, jarak suatu kota dengankotayanglaindalamsuaturuteadalahsepertiterlihatdalamnetwork berikut.Rutemanakahyangharusdilaluiagarjarakyangditempuholehorang tersebut minimum? Contoh 2. Seorang pengusaha ingin menanamkan uangnya secara optimal pada salah satuataubeberapabidangusaha,yaitumembelisahamdipasaruangdanmodal, membelibondataumendepositokandibank,diahanyainginmenanamkan uangnya pada satu jenis usaha, pada tiap kali mengadakan investasi. sesuai dengan peraturanyangberlakusaatini,bahwapengusahatersebuthanyadibenarkan untukinvestasiataumenarikmdalnyapadaharipertamatiapkwartal.Besarnya keuntunganyangdiharapkantiapbulanselamasatutahundinyatakansebagai panjang dari arc. Kota Tujuan s 4 3 2 Awal Kwartal 4 Akhir 4 3 2 4 3 2 t Kwartal 3Kwartal 2Kwartal 1 s 3 4 2 4 3 4 3 3 2 1 2 t 7 2 Kota Asal Jarak Kota Antara 23 Dari kedua contoh problema tersebut, terlihat bahwa sebagai penyelesaian optimumadalahlintasan(path)yangmemberikanjarakterpendekdarisket. Hanyasajapadacontohdua,panjangtiappathharusdinyatakansebagaiharga negatifdarikeuntunganyangdiharapkanpadatiapkwartal.Adabeberapa algoritma untuk mencari penyelesaian optimum di problemapath yang terpendek (shortespathproblem).Yangpalingbanyakdigunakanadalahalgoritmadikstra (1959), Karena algritma ini sangat efisien. Tetapii penggunaannya terbatas hanya untuknonnegatifnetwork.Untuknegatifnetworkdapatdigunakanalgoritma chimbel dan gellman atau algoritma ford. Ide dari algoritma dikstra adalah sebagai berikut: Misalkandiketahuibahwadalamnetwork,mnodesdanjugapadambuahnode tersebut,kemudiannodeke(m+1)yangterpendekkenodesdicarisebagai berikut: Untuksetiapnode,bentuklahsebuahpathdarinodeskenodeydengan menghubungkan path terpendek dri s ke t dengan arc (x, y) untuk semua node x.

Pilihlahpathyangterpendekdarinbuahpathini,anggapbahwauntuk sementara,pathyangdipilihinimerupakanpathyangterpendekdarisket. Sekarang, node yang manakah yang merupakan node ke ( m+1), yang terdekat ke s adalah node yang belum diberi warna yang merupakan path terpendek sementara darissepertitelahdihitungdiatas.Haliniadalahbenarkarenapathyang terpendek dari s kepadanodeyang ke(m+1)yang jaraknya terpendek kenode s, harus menggunakan node yang telah berwarna sebagai node antara. Olehkarenaitu,jikakembuahnodeyangterdekatkepadanodes diketahui, maka nodeke (m+1) dapat dicari, seperti yang diuraikan di atas mulai denganm=0,danprosestersebutdilakukanberulang-ulangsehinggapathyag terpendek dari s ke t telah diperoleh. 24 Untuk jelasnya algoritma dikstra ini dapat dijelaskan sebagai berikut: Langkah 1 :Untuksemuanodedanarcyangbelumdiwarnai.Beriangkad(x) kepadasetiapnodexuntukmenunjukkanpanjangdaripathyang terpendekdarisketyanghanyamenggunakannodeyangberwarna sebagai node antara. Beri pula d(s) = 0 dan d (x) = ~ untuk semua x=s. misalkanya adalah node pertama yang akan diberi warna. Beri warna pada s dan misalkan y = s. Langkah 2:Untuk setiap node xyang belum berwarna, tentukan d(x) dengan cara sebagai berikut:d(x) = Min { d(x), d(y) + a(y,x)} Jikad(x)=~,untuksemuaxyangtidakberwarna,makaiterasi dihentikan karena tidak ada path dari s kepada setiap node yang belum berwarnatersebut.Jikad(x) = ~,beriwarnanodexyangbelum berwarnayangmempunyaihargad(x)terkecil.Jugaberiwarnapada arcyanglangsungmenujunodexdarinodeberwarnadimanaharga d(x) yang minimum tadi ditemukan. Misalkan y = x. Langkah 3:Jika node t sudah diberi warna, maka iterasi dihentikan, karena sebuah pathyangterpendekdarisketsudahditemukan.Jikanodetbelum berwarna, kembali ke langkah 2. Bila algoritma dikstara ini digunakan untuk contoh soal 1 di atas maka penyelesaian optimum yang diperoleh adalah sebagai berikut. s 2 4 3 4 3 4 3 3 2 1 2 t 7 2 25 Langkah 1:Beri warna pada node s, d(s) = 0 dan d(x)= ~ untuk seluruh x = s. Langkah 2: y = s d(1) = Min { d(1), d(s) + a(s,1)} = Min {~, (0+4)} = 4 d(2) = Min { d(2), d(s) + a(s,2)} = Min {~, (0+7)} = 7 d(3) = Min { d(3), d(s) + a(s,3)} = Min {~, (0+3)} = 3 d(4) = Min { d(4), d(s) + a(s,4)} = Min {~, (0+~)} = ~ d(t) = Min { d(5), d(s) + a(s,5)} = Min {~, (0+~)} = ~ Karenad(3)=3adalahMin{d(1),d(2),d(3),d(4),d(t)},makanode3danarc (s,3) diberi warna. Path yang terpendek sementara adalah dari node s ke node 3. Langkah 3: Node t belum berwarna, maka kembali kepada langkah 2. Langkah 2: y = s d(1) = Min { d(1), d(3) + a(3,1)} = Min {4, (3 + 4)} = 4 d(2) = Min { d(2), d(3) + a(3,2)} = Min {7, (3 + ~)} = 7 d(4) = Min { d(4), d(3) + a(3,4)} = Min {~, (3 + 3)} = 6 d(t) = Min { d(t), d(3) + a(3,t)} = Min {~, (3 + ~)} = ~ Karenad(1)=4adalahMin{d(1),d(2),d(4),d(t)},makanode1danarc(s,1) diberi warna. Path arborescence terpendek adalah arc (s,3) dan (s,1). Langkah 3: Node t belum berwarna, maka kembali kepada langkah 2. Langkah 2: y = 1 d(2) = Min { d(2), d(1) + a(1,2)} = Min {7, (4+3)} = 7 d(4) = Min { d(4), d(1) + a(1,4)} = Min {4, (4+2)} = 6 d(t)= Min { d(t), d(1) + a(1,t)} = Min {~, (4+~)} = ~ Karena d(4) = 4 adalah Min {d(2), d(4), d(t)}, maka node 4 diberi warna.s 3 3 s 3 3 1 4 26 Salahsatudariarc(3,4)danarc(1,4)jugadiberiwarna.Misalkandipiliharc (3,4) maka path arborecence terpendek adalah: Langkah 3: Node t belum berwarna, maka kembali kepada langkah 2. Langkah 2: y = d d(2) = Min { d(2), d(4) + a(4,2)} = Min {7, (6+~)} = 7 d(t)= Min { d(t), d(4) + a(4,t)} = Min {~, (6+2)} = 8 Karena d(2) = 7 adalah Min {d(2), d(t)}, maka node 2 dan arc (s,2) diberi warna.Salahsatudariarc(3,4)danarc(1,4)jugadiberiwarna.Patharborecence terpendek adalah sebagai berikut. Langkah 3: Node t belum berwarna, maka kembali kepada langkah 2. Langkah 2: y =2 d(t)= Min { d(t), d(2) + a(2,t)} = Min {8, (7+2)} = 8 Beri warna pada node t dan arc (4,t) maka path arborecence terpendek adalah: 2 s 3 3 1 4 4 3 7 2 2 s 3 3 1 4 4 3 5 s 3 3 1 4 4 3 27 Daripatharborecenceiniterlihatbahwapathyangterpendekdarisket terdiri dari arc (s,3), (3,4), dan (4,5) dengan jarak 3 + 3 + 2 = 8. Karenaalgoritmadikstrauntukmencaripathyangterpendekdalam prosesnyamembentukarborescencemakaalgoritmainijugadapatdigunakan untuk mencari minimum spanning arborescence dari suatu graph atau network. 2.3.2.Shortest Path antara seluruh Node. Problempadauraianterdahuluadalahmencarisuatushortestpath (lintasanterpendek)diantara2(dua)nodetertentudidalamgraph.Bagianini akanmempelajarishortestpathantatratiappasangnodedidalamgraph. Misalnya,suatugraphterdiridarisetelemenN(1,2,3,4dan5)dansatuset elemenA{(1,2),(2,3),(3,1),(3,6),(5,4),(4,6),(1,4),(6,5)}sepertiterlihatpada gambar berikut. Problemaadalahmencarilintasanyangterpendekdarisuatunodeke seluruhnodeyanglain,misalnyaantaranode1dengannode3,antaranode2 dengannode6danseterusnya.Sudahbarangtentu,problemainiakandapat diselesaikandenganmenggunakanalgoritmadikstrasepertiyangtelahdiuraikan sebelumnyasecaraberulang-ulang.Tetapipenyelesaiandengancarainisangat tidakefisienkarenamembutuhkanperhitunganyangsangatbanyakdansangat dipengaruhi oleh banyaknya node yang terdapat di dalam graph. Untukproblemayangdemikian,akandapatdiselesaikandenganlebih mudahdanlebihsingkatdenganmenggunakanalgoritmaShimbelandBellman (1954),algoritmaFloyd(1962)danalgoritmawantzig(1967).Padabagianini 3 1 4 3 24 5 2 6 2 5 3 2 Bobot arc menyatakan jarak antara tiap pasang node 28 hanyaalgoritmaFloydsajayangakandiuraikansedangkanalgoritmalainnya dapat dibaca pada buku Optimization Algoritma for networks and Graphs. Contoh. Suatuperusahaanpenerbangandomestikharusmenyinggahisejumlahkota setiaphari.Untukmenghematpenggunaanbahanbakardanwaktupenerbangan maka,perusahaantersebutinginuntukmeminimumkantotaljarakyangharus ditempuhnya. Suatu hal yang sangat membantu untuk mencapai tujuan ini adalah dengan mendapatkan rute yang terpendek antara setiap kota yang harus disinggahi oleh pesawat. DalamalgoritmaFloydinidigunakanbeberapanotasiyaitu:nomordari nodeadalah1,2,3,...................,N.Pathyangterpendekdarinodeidanj,dimana hanyambuahnodeyangpertamadiizinkansebagainodeantaradinyatakan sebagaidmij =~.berdasarkandefinisiini,makadoij adalahpanjangdaripath terpendekdariikej(pathyangtidakmempunyaipathantara)dandIij adalah panjangdaripathtersebuthanyaterdapatsatunodeantara.Pengertianinidapat dijelaskan dengan graph berikut. Path dari 1 ke 4 doij=3, dengan path terpendek (1,4) dIij= ~, tidak ada path dari node 1 ke 4 yang mempunyai 1 node antara. d2ij= 11, dengan path terpendek (1,2), (2,5), (5,4) d3ij= ~, tidak ada path dari node 1 ke 4 yang mempunyai 3 node antara. d4ij= 13, dengan path terpendek (1,2), (2,3), (3,6), (6,5), (5,4). 3 1 4 3 24 5 2 6 2 5 3 2 7 4 29 Sehingga jelas bahwa doij = 0, untuk semua i. Misalkan Dm adalah matriks NxNyangmempunyaielemen(i,j)adalahdmij,jikapanjangsetiaparcdalam graph diketahui maka matriks D0 dapat dicari. Sebagai tujuan adalah mencari DN yaitumatriksNxNdimanaelemen(i,j)adalahdNij,yangmerupakanpanjang dari path terpendek antara node i dengan node j. AlgoritmaFloyddimulaidariD0 dan D1 dihitungberdasarkanD0

berikutnya, algoritma menghitungD2 dan D1 dan seterusnya. Jikahal-haldibawahinitelahdiketahuimakaIdedariperhitungan-perhitungan tersebut adalah sebagai berikut: a) Shortestpathdarinodeikenodemyanghanyamelalui(m-1)buahnode antara. b)Shortestpathdarinodemkenodejyanghanyamelalui(m-1)buahnode antara. c)Shortestpathdarinodeikenodejyanghanyamelalui(m-1)buahnode antara.Karenadalampathinitidakterdapatcircuitataupunarcyang panjangnya negatif, maka path yang lebih pendek diantara (4) dan (5) berikut iniadalahmerupakanshortestpathdariikej,yanghanyamelaluimbuah node antara. d)Path yang dibentuk dari sambungan path pada (1) dan path pada (2). e)Path pada (3). Sehingga: dmij = Min { (d1 mim +d1 mmj), d1 mij} Daripersamaantersebutterlihatbahwahanyaelemen-elemendarimatriksDm-1 yang diperlukan untuk menghitung elemen-elemen dari matriks Dm. Algoritma Floyd untuk shortest path ini adalah: Langkah 1 : Beri nomor pada node dari graph yaitu 1,2,3,........,N. CarilahmatriksDO,yaitusuatumatriksyangelemen(i,j)sama denganpanjangdariarcyangterpendekdarinodeikenodej.Jika arc ini tidak ada, beri doij = ~ . Misalkan doij = 0 untuk seluruh i 30 Langkah2:Untukm=1,2,3,........,N,secaraberturut-turutcarielemenelemen darimatriksDm darielemen-elemenDm-1 denganmenggunakan formula berikut. dmij = Min { (d1 mim +d1 mmj), d1 mij} Bilasetiapelemensudahditentukan,catatlahpathyangbersangkutan. Elemen-elemen dari matriks DN adalah merupakan panjang dari shortest path dari node i ke node j. 2.4. Tree Problem Salah satu variasi dari shortest path problem adalah minimum spanning tree problem. Dalam penyelesaian pada shortest path problem, set dari node dan jarak antaratiappasangnodetersebutterlebihdahulutelahdiketahui.Padashortest pathprobleminiyangdicariadalahlintasanyangmemberikanjarakterpendek dari suatu tempat asal (source) ke suatu tempat tujuan (terminal) melalui beberapa alternatif daerah antara. Bedahalnyadenganshortestpathproblemminimumspanningtree problem,menyangkutpemilihanarcdarigraphsedemikianrupasehingga terdapat satu rute antara suatu node dengan node yang lain, tetapi total jarak harus sekecilmungkin.Dalamhalini,arcyangterpilihharuslahmembentuksuatu spanningtree(treeyangmenghubungkanseluruhnodeyangadadidalam graph).Dengankatalain,problemaadalahmencarispanningtreedengantotal bobot arc yang sekecil-kecilnya. Uraianberikutinimempelajarialgoritmauntukpenyelesaianproblem spanning tree (pembentukan tree) didalam graph. Yang pertama adalah algoritma untukpenyelesaianproblemaspanningtreepadagraphdanberikutnyaadalah algoritma untuk penyelesaian minimum/ maksimum spanning tree problem. 31 2.4.1.Algoritma untuk Spanning Tree Padabagianiniakandipelajari2(dua)macamalgoritmayaituyang pertama adalah algoritma untuk membentuk tree (tree algoritm) Pada suatu graph, danyangkeduaadalahalgoritmauntukmembentukminimumspanningtree (minimumspanningtreealgoritm)yaituspanningtreedarisuatugraphyang mempunyaitotalbobotminimumdiantaraseluruhspanningtreeyangmungkin dibentuk dari graph tersebut. Didalam penyelesaian problema spanning tree didalam suatu graph (N,A) dimisalkan bahwa bobot dariarc (x,y)adalaha(x,y), total bobot dari sebuahtree adalah jumlah bobot dari seluruh arc yang terbentuk dari tree tersebut. Contoh problema dari spanning tree adalah: Departemenpekerjaanumummenginginkanpembangunanjalanbaru secukupnyauntukmenghubungkan5(lima)buahkotadisuatudaerahyangbaru dibuka.Biayauntukpembangunan2buahkotatertentudiketahuisepertiterlihat pada Tabel 2.1. berikut. Tabel 2.1. Biaya untuk pembangunan 2 buah kota 1 2345 105308090 250706050 350700820 480608010 5905020100 Bagaimanakahcaranyapembangunanjalantersebutdilakukansehingga totalbiayayangdikeluarkanolehdepartemenpekerjaanumumtersebutadalah minimum? Kota 1 Kota 2 Kota 4Kota 3 Kota 5 Ke Dari 32 Problemainidapatdiformulasikankedalambentukgraphdimanasetiap kota dinyatakan sebagai node dan setiap kemungkinan jalan yang dapat dibangun untukmembangun2kotadinyatakansebagaiarc.Bobotdaritiaparcadalah besarnyabiayayangdibutuhkanuntukpembangunanjalanantarasetiap2kota, seperti pada gambar berikut. Algoritmadapatdiringkaskansebagaiberikut,pertaman-tamaseluruharc adalah tidak berwarna dan semua bucket adalak kosong. Langkah1:Pilihlahsalahsatuarcyangbukanmerupakanloop.Beriwarnabiru padaarcinidantempatkanlahkeduanodeujungdannode pangkalnya kedalam suatu bucket (bucket 1) dan bucket yang disebut bucket 2. Langkah 2: Pilih arc lain yang belum berwarna yang juga bukan loop.Jikatidakadalagiarcyangdemikian,algoritmadihentikan.Berarti graph tersebut tidak mempunyai spanning tree. Bila arc tersebut masih ada maka, pada setiap pemerikasa arc, salah satu dari keempat keadaan ini mesti ditemui yaitu: 1.Keduanodeujungataupangkaldariarcyangsedangdiperiksa, sudah ada didalam salah satu bucket. Bila hal ini terjadi, maka arc tersebut diberi warna orange dan kembali ke langkah 2. 2.Salahsatudarinodeujungataunodepangkaldariarctersebut beradadalamsalahsatubucket,dannodeujungyanglaintidak berada dalam bucket.Bila hal ini terjadi, beri warna biru padaarc tersebutdanpindahkanlahnodeyangbelumberadadalambucket kedalambucketdimananodeujungataunodepangkaltadi terdapat. 1 60 3 50 70 80 5 8 10 20 502 4 5 70 33 3.Tidakadasatupundarinodeujungataupunnodepangkaldariarc beradadalamsalahsatudarike2bucket.Bilahaliniterjadi,beri warnabirupadaarcinidankeduanodeujungdannode pangkalnya dimasukkan kedalam bucket 2. 4.masing-masingnodeujungdannodepangkaldalamarcberada dalambucketberbeda.Bilahaliniterjadimakaberiwarnabiru padaarctersebutdanisidarikeduabucketinidigabungdidalam bucket 1. bucket 2 menjadi kosong kembali. Langkah3:Jikaseluruhnodedarigraphsudahberadadalambucket1, makaalgoritmadihentikan,karenaarcyangberwarnabirusudah membentuksuatuspanningtree,jikabelumamakakembalike langkah 2. Jikaalgoritmatidakdapatdihentikankarenapersyaratandiatastidak terpenuhisecaraterus-menerus,makapadagraphtidakdapatdibentukspanning tree. Algoritma ini mempunyai sifat-sifat bahwa masing-masing arc diperiksa satu persatu. Bila suatu arc sudah diberi warna (biru / orange) maka arc tersebut tidak akan diperhatikan lagi. 2.4.2. Algoritma untuk Minimum/ Maksimum Spanning Tree. Padapenyelesaianproblemaspanningtreepadasuatugraphyangseluruh arcnyamempunyaibobotalgoritmadiatasmasihdapatdigunakan.Hanyasaja diperlukanpenyesuaian.Bilaproblemaadalahmembentukspanningtreepada graphdenganbobotdariarcmembentuknyasekecilmungkin,makadisebut sebagaiminimumspanningtreeproblem.Sebaliknyajikajumlahbobottersebut sebesar-besarnya, maka disebut maksimum spanning tree problem. Algoritma untuk penyelesaian minimum spanning tree problem adalah sama denganalgoritmapenyelesaianspanningtree,tetepidisinipemilihanarc dilakukanmulaidaribobotterkecildarisuatuarcyangakandiperiksa.Oleh karenaitupertama-tamayangharusdilakukanadalahmembuatlistdariarc menurut Ascending order (yang terkecil pertama dan terbesar pada bagian akhir). 34 Jikagraphmempunyaibeberapaarcyangbobotnyasamamakapemilihan salahsatudariarcinidapatdilakukansecaraarbitrary.Padapenyelesaian maksimum spanning tree problem, list dari arc disusun menurut discending order (yang terbesar pertama dan terkecil pada bagian yang terakhir). Contoh:Selesaikanlahproblematentangpembangunanjalanrayasepertiyangtelah diperlihatkan dalam contoh sebelumnya. Penyelesaian: Pertama-tamadilakukanpenyusunanlistdariarcmenurutascendingorder, kemudianalgoritmadiatasdigunakan.HasilnyadapatdilihatpadaTabel2.2. berikut. Jadi minimum spanning tree dari graph tersebut adalah spanning tree yang dibentuk oleh node {1, 2, 3, 4,5 } dan arc {(1,2), (3,4), (4,5), (2,5)}. Tabel 2.2.Penyusunan list dari arc menurut ascending order ArcBobotWarnaBucket 1Bucket 2 ---KosongKosong Langkah 1:(1,2)5 Biru1,2Kosong Langkah 2:(3,4) (4,5) (3,5) (2,5) 8 10 20 50 Biru Biru Orange Biru 1,2 1,2 1,2 1,2,3,4,5 3,4 3,4,5 3,4,5 Kosong Langkah 3:Stop (1,3) (2,4) (2,3) (1,4) (1,5) 50 60 70 80 90 Banyaknya arc yang berwarna biru sama denganbanyaknya node dikurangi satu. Semua node telah berada dalam satu bucket. 1 60 3 50 70 80 5 8 10 20 502 4 5 90 1 3 2 4 5 5 10 50 8 35 Berdasarkanpenyelesaianinidiperolehbahwauntukmemberibiaya pembangunanjalanrayainisekecilmungkin,makajalan-jalanyangharus dibangun adalah: -Dari kota 1 ke kota 2, dengan biaya =5 -Dari kota 2 ke kota 5, dengan biaya = 50-Dari kota 5 ke kota 4, dengan biaya = 10 -Dari kota 3 ke kota 4, dengan biaya = 8 Jumlah biaya= 73

2.5. FlowProblem Aliran(flow)didefenisikansebagaisuatucarauntukpengirimanbenda-benda dari suatu tempat ke tempat yang lain. Misalnya pengiriman bahan jadi dari suatupabrikkepadasuatudistribusi,keberangkatanpegawaidarirumahmasing-masing ke tempat kerjaataupun pengiriman surat drai kantor pos ke alamatyang ditujukan dapat dipandang sebagai aliran. Berikut ini adalah merupakan uraian tentang aliran yang dijelaskan dalam bentukgraphdenganberbagaiproblemnyadanalgoritmapenyelesaiandari problem tersebut. 2.5.1. Flow argumentation problem Flowargumentationproblemadalahmencarijumlahunitmaksimumyang dapatditambahkankedalamaliranyangtelahadadidalamsuatupath.Problem initimbulsebagaiakibatdariadanyaperbedaankapasitasmaksimumdarisetiap arc yang membentuk path tersebut. Logika yang mendasari algoritma untuk penyelesaian problem penambahan jumlahunitpadaaliranadalah:misalkanbahwagraphuntukprobleminitelah digambarkan.Misalkanpulabahwajumlahunityangmelintasmelaluiarc(x,y) dinyatakan dengan f (x,y) dan kapasitas yang dibenarkan mengalir dalam arc (x,y) dengan c (x,y), sesuai persamaan: 0s f(x,y) s f(x,y) Seluruh arc dari graph dapat dibagi atas 3 (tiga) kategori, yaitu N, I, R, 36 Dimana: N (Nonincreasablepath) = Setdari arcyang tidak memungkinkan pertambahan atau pengurangan jumlah unityang mengalir melalui arc bersangkutan. I (Increasable path) =Setdariarcyangjumlahunitoadaalirannyamasih dapat ditambahkan. R (Reducable path) =Setyangarcyangjumlahunitpadaalirannyamasih dapat dikurangi. Misalkan i(x,y) dinyatakan sebagai jumlah unit yang maksimum masih bisa ditambahkan ke dalamarc (x,y) dan r(x,y) sebagai jumlah unit maksimumyang dapat dikurangi dari arc (x,y). Maka: i(x,y) = c(x,y) f(x,y) dan r(x,y) = f(x,y) Contoh: Carilah suatu path dari s ke t dimana seluruh arc dari path itu termasuk di dalam set I (Increasable path). i(s,1)=3 i(1,2)=2i(2,t)=1 Jumlahunitmaksimumyangdapatditambahkanmelaluipathdarisketini adalah: I = Min {(s,1),i(1,2),i(2,t)} = Min {3,2,1} =1. Contoh: Carilah suatu path dari t ke s dimana seluruh arc dari path itu termasuk di dalam set R (Reducable path). r(1,s)=1 r(2,1)=2 r(t,2)=1 Jumlah unit maksimum yang dapat dikurangi melalui path dari t ke s ini adalah: R=Min {(1,s),i(2,1),i(t,2)}= Min {1,2,1} =1. S12t S12t 37 Contoh : Carilahflowaugmentingchaindarisketdalamnetworksepertiterlihatdibawah ini. Keterangan: N = Non increasable pathI = Increasable path R = Reducable path Maka flow augmenting chain dari network tersebut adalah: (s,1), (1,3), (2,3), (2,t) dan jumlah maksimum unit tambahan yang dapat dikirim dari s ke t: Min{i(s,1), i(1,3), r(2,3), i(2,t)} = Min {4,3,2,2} = 2 Arcmaju(s,1),(1,3)dan(2,t)dapatditambahkansebanyak2unit, sedangkan arc mundur (2,3) dapat dikurangi alirannya sebanyak 2 unit. Ini berarti, bahwa2unityangsebelumnyamengalirmelaluiarc(2,3)dapatdipindahkanke arc (2,t) dan kemudian digantikan pada node 3 oleh 2 unit tambahan yang datang dari s melalui arc (s,1) dan arc (1,3). 2.5.2. Maximum flow problem Maximum flow problem didefinisikan sebagai problem untuk mencari suatu caraterbaikuntukmemaksimumkanjumlahunityangdapatdikirimdarisket didalam suatu network yang mempunyai arc dengan kapasitas terbatas. Contoh: Carilah aliran maksimum pada network berikut: 1 s 3 2 4 t IR R R I IR N R I N R 2 2 s 12t 4 3 1 2 3 i (s,1) = 4r(s,1) = 6 i (1,3) = 3 r(s,3) = 1 i (2,t) = 2 r(1,2) = 7 i (3,4) = 5 r(2,3) = 2 r(2,4) = 3 r(3,4) = 2 38 Penyelesaian: -Untuk permulaan dipilih flow augmenting chain : (s,1), (1,2), (2,t) Besarnyaaliranmaksimumyangmasihditambahkankedalamchainini adalah = Min {i(s,1), i(1,2), i(2,t)}= Min {2,3,2}=2 Jadijumlahunityangdapatditambahkanpadasetiaparcdidalamchainini adalah 2 unit, yaitu f(s,1)=2 ;f(1,2)=2 ; f(2,t) = 2. -Untuk flow augmenting yang kedua dipilih: (s,2), (1,2), (1,3), (3,t) Besarnyaaliranmaksimumyangmasihditambahkankedalamchainini adalah = Min {i(s,2), i(1,2), i(1,3), i(3,t)} = Min {3,2,4,1}= 1 Jadi 1unit tambahan dapat dikirimkan sepanjang chain dari s ke t. Aliran padasetiaparcmajuyaituarc(s,2),arc(1,3),arc(3,t)dalamchaininiakan ditambahkan masing-masing sebesar 1 unit, dan aliran pada arc mundur yaitu arc(1,2)dalamchaindikurangi1unit.Dengandemikian,aliransekarang menjadi:f(s,1)=2 ; f(1,2)=1 ;f(2,t)=2 ;f(s,2)=1 ;f(1,3)=1 ;f(3,t)=1 Jumlahunityangdapatdialirkanmelaluiruteberikutiniadalahsebagai berikut: -2 unit dialirkan dari s ke t melalui (s,1), (1,2), (2,t) -1 unit dialirkan dari s ke t melalui (s,2), (2,t) -1 unit dialirkan dari s ke t melalui (s,1), (1,3), (3,t) II.3.PENUTUP Padabagianpenutup,diadakantanyajawabdandiskusibaikantar mahasiswa dan dosen, dan juga mahasiswa antar mahasiswa. Untuk itu diberikan juga tugas sebagai bahan latihan mahasiswa di luar jam perkuliahan. 39 Tugas/latihan untuk materi analisis jaringan adalah sebagai berikut: 1.Seorangpemuda mengendarai mobil dari kota asalnya menuju kota yang lain. Diamempunyaibeberapapilihanruteyangmelaluikota-kotaantara,jarak suatu kota dengan kota yang lain dalam suatu rute adalah seperti terlihat dalam networkberikut.Rutemanakahyangharusdilaluiagarjarakyangditempuh oleh orang tersebut minimum? 2.Carilah Jumlah unit maksimum suatu path dari s ke t dimana seluruh arc dari path itu termasuk di dalam sei I (Increasable path)!

i(s,1)=5 i(1,2)=3i(2,t)=2 Kota Tujuan S C D B 5 3 3 3 2 A 3 T 7 Kota Asal Jarak Kota Antara 13 S12t 40 PERKULIAHAN KE 4 DAN 5:PERENCANAAN & PENGENDALIAN PROYEK DGN CPM PERT. SESI/PERKULIAHAN KE: 4 DAN 5 TIK : Pada akhir perkuliahan ini mahasiswa diharapkan mampu: 1. Menjelaskanpengertiandanlangkah-langkahpenyelesaian masalah keputusan dengan menggunakan CPM PERT. 2. Menerapkanteknikpemecahanmasalahdenganmenggunakan CPM PERT tersebut.Pokok Bahasan:Perencanaan & Pengendalian Proyek Dgn CPM PERT. Deskripsi singkat : Dalampertemuaniniandaakanmempelajaribeberapapengertianyang berkaitandenganperencanaan&pengendalianproyekdgnCPMPERT, termasuksimbol-simbolyangdigunakan,penentuanwaktu,perhitunganmaju, perhitunganmundur,perhitungankelonggaranwaktudanpenentuanongkos dalam penjadwalan proyek. I.Bahan Bacaan: 1. DonT.Philips,et.al.,OperationResearch:PrincipleandPractice,2nd edition, John Wiley and Sons, 1987. 2. HillierandLieberman,IntroductiontoMathematicalProgramming,1st edition, McGraw-Hill, 1991. 3. Taha,Hamdy,OperationResearch:AnIntroduction,Newyork:The MacMillan Co, 1985. II.Bahan Tambahan: 1. Hillier,FrederickandGerald,J.Liebermam.IntroductiontoOperation Research , San Fransisco : Holden Day Ltd, 1977. 2. Wagner,H.M.PrincipleofOperationResearch,EnglewoodCliffs,N.J: Prenntice-hall Inc, 1969. III. PertanyaanKunci/Tugas:Ketikaandamembacabahanbacaanberikut, gunakanlah pertanyaan-pertanyaan sebagai berikut: 1. Apa yang dimaksud dengan perencanaan? 2. Apa yang dimaksud dengan pengendalian? 3. Apa yang dimaksud dengan proyek? IV. Tugas: 1.Apa yang dimaksud dengan total Float, jelaskan! 2.Dari suatu proyek diperoleh data: AktivitasAktivitas yang telah dilalui (predecessor)Waktu penyelesaiana (duration) A B - - 6 4 41 C D E F G H I J A A B D,E D,E C,D,E C,D,E I,F 4 6 4 6 4 10 14 12 Buatlah diagram networknya dan tentukan lintasan kritis serta waktu penyelesaian proyek tersebut! III.1. PENDAHULUAN Dalamperkuliahanmengenaiperencanaan&pengendalianproyekdgn CPM PERT ini akan dibahas mengenai pengertian perencanaan & pengendalian proyekdgnCPMPERT,termasuksimbol-simbolyangdigunakan,penentuan waktu, perhitungan maju & perhitungan mundur, perhitungan kelonggaran waktu, pembuatan peta waktu& pengaturan sumber daya, perkiraan waktu penyelesaian suatuaktifitasdanpenentuanongkosdalampenjadwalanproyek.Materiyang disampaikansangatberkaitanantarasatudenganyanglainnya,haliniberguna dalammenghasilkankeputusanyangoptimaldalammenyelesaikanpersoalan keputusan dalam perencanaan dan pengendalian suatu proyek. III.2. PENYAJIAN PERENCANAAN DAN PENGENDALIAN PROYEKDENGAN PERT-CPM Pengelolaanproyek-proyekberskalabesaryangberhasilmemerlukan perencanaan,penjadwalandanpengorganisasianyangterjagadariberbagai aktivitasyangsaringberkaitan.Untukitu,makapadatahun1950telah dikembangkanprosedur-prosedurformalyangdidasarkanataspenggunaan network(jaringan)danteknik-tekniknetwork.Proseduryangpalingutamadari prosedur-prosedurinidikenalsebagaiPERT(ProgramEvaluationandReview Technique)danCPM(CriticalPathMethod),yangkeduanyaterdapatbeberapa perbedaanpenting.Namun,kecenderunganpadadewasainiadalah menggabungkankeduapendekatantersebutmenjadiapayangbiasadikenal sebagai PERT-type system. 42 Tujuan PERT-type Sistem adalah : 1.Untuk menentukan probabilitas tercapainya batas waktu proyek. 2.Untukmenetapkankegiatanmanayangmerupakanbottlenecks(menentukan waktupenyelesaianseluruhproyek)sehinggadapatdiketahuipadakegiatan mana kita harus bekerja keras agar jadwal dapat terpenuhi 3.Untukmengevaluasiakibatdariperubahan-perubahanprogram,PERT-type sistem ini juga dapat mengevaluasi akibat dari terjadinya penyimpangan pada jadwal proyek. 3.1. Simbol-Simbol yang Digunakan. Dalam menggambarkan suatu network digunakan tiga buah simbol sebagai berikut: 1.Anak Panah= arrow, menyatakan sebuah kegiatan atau aktivitas. 2.O Lingkaran Kecil = node, menyatakan kegiatan atau peristiwa atau event. 3.---)AnakPanahterputus-putus,menyatakankegiatansemuataudummy. Dummy disini berguna untuk membatasi mulainya kegiatan. Simbol-simbolinidigunakandenganmengikutiaturan-aturansebagai berikut : 1.Di antara dua event yangsama, hanya boleh digambarkan satu anak panah. 2.Nama suatu aktivitas dinyatakan dengan huruf atau dengan nomor event. 3.Aktivitasharusmengalirdarieventbernomorrendahkeeventbernomor tinggi. 4.Diagram hanya memiliki sebuah initial event dan sebuah terminal event. Logika ketergantungan kegiatan-kegiatan itu dinyatakan sebagai berikut : 1.Jika kegiatan A harus diselesaikan dahulu sebelum kegiatan B dapat dimulai, maka hubungan antara kedua kegiatan tersebut dapat digambarkan sebagai

1 2 3 AB 43 2.Kegiatan C, D, dan E harus selesai sebelum kegiatan F dapat dimulai, maka :

3.Jika kegiatan G dan H harus selesai sebelum kegiatan I dan J, maka : 4.Jika kegiatan K dan L harus selesai sebelum kegiatan M dapat dimulai, tetapi kegiatan N sudah boleh dimulai bila kegiatan L sudah selesai, maka:

5.Jika kegiatan P, Q, dan R mulai dan selesai pada lingkaran kejadian yang sama, maka : 5 4 3 2 1 D C E F 6 5 4 3 2 G H I J 2 3 7 6 4 5 K L M N 3134 33 32 P Q R Atau 3134 33 32 P Q R 44 3.2. Penentuan Waktu Dalam mengestimasi dan menganalisis waktu ini, akan kita dapatkan satu atau beberapa lintasan tertentu dari kegiatan kegiatan padanetwork tersebut yang menentukanjangkawaktupenyelesaianseluruhproyek.Lintasaninidisebut lintasankritis(criticalpath).Disampinglintasankritisiniterdapatlintasan-lintasanlainyangmempunyaijangkawaktuyanglebihpendekdaripadalintasan kritis.Dengandemikian,makalintasanyangtidakkritisinimempunyaiwaktu untuk bisa terlambat, yang dinamakan float. 3.2.1. Notasi yang Digunakan. Untuk memudahkan perhitungan penentuan waktu ini digunakan notasi-notasi sebagai berikut : TE = earliest event occurence time, yaitu saat tercepat terjadinyaevent. TL= latest event occurence time, yaitu saat paling lambat terjadinya event. ES= earliest activitiy start time, yaitu saat tercepat dimulainya aktivitas. EF = earliest activity finish time, yaitu saat tercepat diselesaikannya aktivitas. LS=latest activity start time, yaitu saat paling lambat di mulainya aktivitas. LF=latestactivityfinishtime,yaitusaatpalinglambatdiselesaikannya aktivitas. t=activitydurationtime,yaituwaktuyangdiperlukanuntuksuatuaktivitas (biasa dinyatakan dalam hari). S = total slack / total float. SF = free slack / free float. 3.3. Perhitungan Maju Ada tiga langkah yang dilakukan pada perhitungan maju, yaitu : 45 1.Saattercepatterjadinyainitialeventditentukanpadaharikenolsehingga untukinitialeventberlakuTE=O.(Asumsiinitidakbenaruntukproyek yang berhubungan dengan proyek-proyek lain. 2.Kalau initial event terjadi pada hari yang ke nol, maka: ES (i,j) = TE(0) = 0 EF(i,j)= ES(i,j) + t(i,j) =TE(t)+ t(i,j) 3.Event yang menggabungkan beberapa aktivitas (merge event). (i1,j) Contoh

3.4. Perhitungan Mundur Pada perhitungan mundur ini pun terdapat tiga langkah, yaitu : t ji(i,j) EF(i1,j) EF(i1,j) EF(i1,j) j 1 4 2 8 3 7 6 20 5 20 4 19 8 36 0 0 A B C E D F G H I J K 5 10 3 11 7 31 12 15 4 8 9 7 8 46 1. Pada terminal event berlaku TL = TE. 2.Saatpalinglambatuntukmemulaisuatuaktivitassamadengansaatpaling lambatuntukmenyelesaikanaktivitasitudikurangidengandurationaktivitas tersebut.

LS = LF- t LF(i,j) = TL dimana TL = TE Maka: LS(i,j) = TL(i) - t (i,j)

3. Event yang "mengeluarkan" beberapa aktivitas (burst event). Contoh: 3.5. Perhitungan Kelonggaran Waktu (Float Atau Slack) i j TETL (i,j) LS(i1,j1) LS(i,j2) LS(i,j3) j 36 31 20 2011 33 0 18 8 1 4 2 8 3 7 6 20 5 20 4 19 8 36 0 0 A B C E D F G H I J K 5 10 3 11 7 31 12 15 4 8 9 7 8 47 Kelonggaranwaktu (float/slack) dari aktivitas (i.j).yang terdiri atastotal float dan free float.Totalfloatadalahjumlahwaktudimanawaktupenyelesaiansuatuaktivitas dapatdiundurtanpamempengaruhisaatpalingcepatdaripenyelesaianproyek secara keseluruhan. Karena itu, total float ini dihitung dengan cara mencari selisih antarasaatpalinglambatdimulainyaaktivitasdengansaatpalingcepatdi mulainyaaktivitas(LS-ES),ataubisajugadenganmencariselisihantarasaat palinglambatdiselesaikannyaaktivitasdengansaatpalingcepatdiselesaikannya aktivitas (LF - EF). freefloatadalahjumlahwaktudimanapenyelesaiansuatuaktivitasdapat diukurtanpamempengaruhisaatpalingcepatdaridimulainyaaktivitasyanglain atau saat paling cepat terjadinya event lain pada network. Freefloataktivitas(i,j)dihitungdengancaramencariselisihantarasaat tercepatterjadinyaeventdiujungaktivitasdengansaattercepatdiselesaikannya aktivitas (i, j) tersebut. Atau : SF (i,,j) - TE (j) -EF(i,,j) Dari perhitungan maju didapat EF (i,,j) = TE (i) + t (i,,j), maka : SF(i,,j) = TE(,j) - TE(i,) - t(i,,j)

48 Contoh: Perhitunganuntukmenentukanlintasankritisinidapatdirangkumdan dapatdilihatpadaTabel3.1.berikut,yangmemuatseluruhinformasiyang diperlukan untuk membuat peta waktu (time_chart) pelaksanaan proyek. Tabel 3.1.Perhitungan menentukan lintasan kritis AktifitasDurationPaling cepatPaling lambatTotalFree (i,j)t(i,j)MulaiSelesaiMulaiSelesaiFloatFloat (ES)(EF)(LS)(LF)SSF (0,1) (0,2) (0,3) (1,4) (2,4) (2,5) (3,6) (4,8) (5,6) (5,8) (6,7) (7,8) 4 8 7 15 6 12 9 3 0 10 11 5 0 0 0 4 8 8 7 19 20 20 20 31 4 8 7 19 19 20 20 36 20 36 31 36 0 0 0 18 8 8 11 33 20 20 20 31 18 8 11 33 33 20 20 36 20 36 31 36 14 0 4 14 19 0 4 14 0 6 0 0 0 0*) 0 0 5 0*) 4 14 0*) 6 0*) 0*) 3.6. Penentuan Ongkos Dalam Penjadwalan Proyek 36 31 20 2011 33 0 18 8 1 4 2 8 3 7 6 20 5 20 4 19 8 36 0 0 A B C E D F G H I J K 5 10 3 11 7 31 12 15 4 8 9 7 8 49 Dalampenjadwalanproyek,aspekongkosdiperhitungkandengan membuathubunganongkosdengandurationuntuk-setiapaktivitaspadaproyek itu.Yangdimaksuddenganongkosdisiniialahongkoslangsungsaja,tidak termasuk ongkos-ongkos administrasi, supervisi dan lain-lain. Kebanyakanproyekmenggambarkanhubunganongkosdengandurationini sebagai garis lurus yang dapat dilihatpada Gambar 3.1. berikut. Gambar 3.1. Hubungan ongkos dengan duration

Titik (Dn, Cn) menyatakan hubungan duration Dn dengan ongkosnya Cn, jikaaktivitasdiselesaikandalamkondisinormal.DurationDninidapat dipersingkatdengancarameningkatkanpengalokasiansumberyangdengan sendirinya berarti meningkatkan ongkos langsung. Contoh:

Titik percepatan Titik normal duration Ongkos DnDc Cc Cn 50 Sebagailangkahpertamaprosedurperhitungannyaialahmengasumsikan bahwaseluruhaktivitasterjadipadawaktu(duration)normal.Darinetwork&di atas dapat dilihat bahwa perhitungan lintasan kritisnya adalah berdasarkan kondisi normaldenganaktivitas(1,2)dan(2,5)sebagaiaktivitas-aktivitasyang membentuklintasankritis.Waktupenyelesaianproyekiniadalah18dengan ongkos 580. Karenaaktivitas(1,2)mempunyaikemiringanyanglebihkecil,maka aktivitasinidipilihsebagaiaktivitasyangakanditekanwaktupenyelesaiannya. Berdasarkantabelhubunganongkosdenganwaktudiatas,aktivitas(1,2)ini dapatditekansebanyak2satuanwaktu,suatubatasyangditentukanolehtitik percepatannya (oleh sebab itu disebut sebagai batas percepatan atau crash limit). salah satu cara untuk memprediksi apakah lintasan kritis yang baru itu akan terjadi sebelummencapaititikpercepatanataukahtidak,ialahdenganmemperhatikan freefloatdariaktivitas-aktivitasyangtidakkritis.sepertitelahdijelaskan,free float ini bersifat independen terhadap saat dimulainya aktivitas-aktivitas yang lain. Maka,apabilapadasaatdilakukanpenekananterhadapaktivitaskritisterjadi penguranganhargafreefloatdaripositifmenjadinol,aktivitaskritisitutidak boleh ditekan tanpa melakukan pemeriksaan lebih lanjut, karena ada kemungkinan bahwaaktivitasdenganfreefloatnolinimenjadiaktivitaskritis.Dengan demikian, selain crash limit kita juga harus memperhatikan free float limit. untukmenentukanfreefloatlimitini,pertama-tamakurangilahduration dariaktivitaskritisterpirih(terdasarkanslope-nya)sebanyaksatusatuanwaktu. Maka, dengan menghitunt ulang nilai-nilai dari seluruh aktivitas yang tidak kritis, akandapatdilihataktivitas-aktivitasmanayangfreefloat-nyatelahberkurang sebanyaksatusatuanwaktujuga.Nilaifreefloatterkecil(sebelumdilakukan pengurangan)dariseluruhaktivitassemacamitulahyangdimaksudsebagaifree float limit. Perhatikan sekarang bahwa dengan mengurangiduration dari aktivitas (1, 2)sebanyaksatusatuanwaktuakanmenurunkanSFdariaktivitas(3,4)dari semula berharga 1 menjadi nol. SF dari aktivitas (4, 5) tetap berharga 5.Dengan demikian, maka SF limit = 1. Karena crash limit dari (1, 2) adalah 2, maka batas 51 penekanannya(compressionlimit)samadengannilaiminimumcrashlimit dengan SF limitnya, yaitu min (2, 1) = 1.

-duration dari proyek keseluruhan = 17 -Ongkos baru= ongkos pada penjadwalan sebelumnya +ongkos penekanan waktu. = 580 + (18-17) 50 = 630 - Lintasan kritis tetap, yaitu (1, 2, 5) Karenaaktivitas(1,2)inimasihmerupakanaktivitaskritisterpilihuntuk dipercepat,makalakukanlahlagiperhitungancrashlimitdanSFlimit-nya, sehingga diperoleh penjadwalan baru sebagai berikut :

-Duration dari proyek keseluruhan = 16 -Ongkos = 630 + (17-16) 50= 680 -Lintasan kritis tetap, yaitu (1, 2, 5) Sekarang,aktivitas(1,2)sudahtidakdapatdipercepatlagikarenatelah mencapaicrashlimit-nya.Karenalintasankritisnyatetap,yaitu(1,2,5),maka 52 tinggallahaktivitas(2,5)yangharusdipercepat.Aktivitas(2,5)inimempunyai crash limit = 10 - 5 = 5. Dari penjadwalan yang terakhir kita lihat bahwa pada saat aktivitas(1,2)ditekansebanyak1satuanwaktu,makahanyaadasatuaktivitas tidak kritis yang SF-nya berharga positif dan bekurang sebanyak1 satuan waktu. Aktivitas tersebut adalah (4, 5), di mana SF-nya berkurang dari 5 menjadi 4. Maka tidakadapilihanlainkecualimenetapkanbahwaSFlimitnyaadalah4.Dengan demikian,compressionlimituntukaktivitas(2,5)adalahmin(5,4)=4,dengan hasil penjadwalan baru sebagai berikut: -duration dari proyek keseluruhan = 12 -Ongkos = 680 + (16-12) 60= 920 -Lintasan kritis ada dua, yaitu (1, 2, 5) dan (1, 3, 4, 5) Karena pada persoalan di atas crash limit-nya sama dengan 1, maka SF-limitnya dengan sendirinya tidak perlu dihitung. Penjadwalan baru dari hitungan ini adalah : -duration dari proyek = 11 -Ongkos= 920 + (12-11) (60+10)= 990 Slope (2, 5), slope (4, 5) -Lintasan kritis tetap, yaitu (1, 2, 5) dan (1, 3, 4, 5) III.3.PENUTUP 53 Padabagianpenutup,diadakantanyajawabdandiskusibaikantar mahasiswa dan dosen, dan juga mahasiswa antar mahasiswa. Untuk itu diberikan juga tugas sebagai bahan latihan mahasiswa di luar jam perkuliahan. Tugas/latihanuntukmateriPerencanaan&PengendalianProyekDgnCPMPERT adalah sebagai berikut: 1. Apa yang dimaksud dengan total Float, jelaskan! 2. Dari suatu proyek diperoleh data: AktivitasAktivitas yang telah dilalui (predecessor) Waktu penyelesaiana (duration) A B C D E F G H I J - - A A B D,E D,E C,D,E C,D,E I,F 6 4 4 6 4 6 4 10 14 12 Buatlah diagram networknya dan tentukan lintasan kritis serta waktu penyelesaian proyek tersebut! PERKULIAHAN KE 6 DAN 7: PROGRAMADINAMIS. SESI/PERKULIAHAN KE: 6 DAN 7 TIK : Pada akhir perkuliahan ini mahasiswa diharapkan mampu: 1.Menjelaskan pengertian dan ide dasar programa dinamis. 2.Menerapkanteknikpemecahanmasalahdenganmenggunakan programa dinamis.Pokok Bahasan:Programa Dinamis Deskripsi singkat : Dalampertemuaniniandaakanmempelajaripersoalankeputusandengan menggunakanprogramadinamistermasukpengantardankarakteristikpersoalan programadinamis,programadinamisdeterministiksertabagaimanacara menyelesaikanpersoalankeputusandenganmenggunakanprogramadinamis tersebut. I.Bahan Bacaan: 1. Dimyati,TjutjuTarliah,AhmadOperationsResearch,PT.SinarBaru 54 Algensindo Bandung, 1999. 2. HillierandLieberman,IntroductiontoMathematicalProgramming,1st edition, McGraw-Hill, 1991. 3. Taha,Hamdy,OperationResearch:AnIntroduction,Newyork:The MacMillan Co, 1985. II.Bahan Tambahan. 1. Wagner,H.M.PrincipleofOperationResearch,EnglewoodCliffs,N.J: Prenntice-hall Inc, 1969. 2. WayneL.Winston,OperationResearch:ApplicationandAlgorithms,3rd edition, Duxbury Press, 1994. III.PertanyaanKunci/Tugas:Ketikaandamembacabahanbacaanberikut, gunakanlah pertanyaan-pertanyaan sebagai berikut: 1.Apa yang dimaksud dengan programa dinamis? 2.Carilahcontohpersoalanyangdapatdiselesaikandenganmenggunakan programa dinamis. IV.Tugas: 1.Kapan metode programa dinamis dapat dilaksanakan? Dan berikan contohnya!2.5(Lima)orangperawatdalam1(satu)teamkesehatandaripuskesmasRindinaharus ditempatkanditigabalaipengobatandikotaBandarjaya,dalamrangka menyempurnakanpelayanankesehatan,pendidikankesehatan,danprogramalatihan. Tabelberikutiniadalahtaksiranpertambahanumur(tahunorang)dalamsatuanribu untuktiapbalaipengobatandantiapalokasiteamyangmungkindilakukan.Berikut ukurandarikeefektifaniniialahpertambahanumur(yaituberapatahunumurorang akan bertambah dengan adanya team tersebut). Jumlah tim yang dialokasikan Pertumbuhan umur (ribuan tahun-orang) Balai pengobatan 123 0 1 2 3 4 5 0 45 35 70 90 120 0 21 20 45 75 102 0 24 50 70 120 130 Berapa team yang harus ditempatkan di tiap-tiap balai pengobatan, sehingga keefektifan total dari lima team itu dapat dimaksimumkan? IV.1. PENDAHULUAN Dalamperkuliahanmengenaiprogramadinamisiniakandibahas mengenaipengantardankarakteristikpersoalanprogramadinamis,programa dinamisdeterministik,danprogramadinamisprobabilistiksertabagaimanacara menyelesaikanpersoalankeputusandenganmenggunakanprogramadinamis tersebut.Materiyangdisampaikansangatberkaitanantarasatudenganyang lainnya,halinibergunadalammenghasilkankeputusanyangoptimaldalam menyelesaikan persoalan keputusan suatu perusahaan. 55 IV.2. PENYAJIAN PROGRAMA DINAMIS Programa dinamis adalah suatu teknik matematis yang biasanya digunakan untukmembuatsuatukeputusandariserangkaiankeputusanyangsaling berkaitan.Tujuanutamamodeliniialahuntukmempermudahpenyelesaian persoalan optimasi yang mempunyai karakteristik tertentu. Ide dasar programa dinamis ini ialah membagi persoalan menjadi beberapa bagian yang lebih kecil sehingga memudahkan penyelesaiannya. 4.1.Pengantar Programa Dinamis Seorang salesman harus berangkat dari satu kota ke kota lainnya. Di antara kotaasaldankotatujuanituterdapatbeberapakotalainyangdapatdigunakan sebagaitempatpersinggahansementara.Kota-kotayangdapatdilewatiitudapat digambarkan sebagai berikut : Data ongkos yang harus dibayar jika salesman itu meninggalkan kota i dan menuju ke kota j (cij) adalah sebagai berikut : 2345678910 1243274651483 332466394 4415733 Rute manakah yang dapat menimbulkan ongkos terkecil ? 4tahap(stage)yangharusdijalaniuntukmelakukanperjalanandarikota(state) asal di 1 ke tujuan di 10. 56 Tetapkanvariabel-variabelkeputusanxnsebagaitempat-tempat persinggahanpadastagen(n=l,2,3,4).Makaruteyangdijalaniadalah 1x1x2x3x4, di mana x4 adalah kota (state) 10 atau x4 = 10. Selanjutnya tetapkan pula variabel-variabel berikut : 1.fn (s, xn) = ongkos total yang harus dibayar jika salesman itu berada di kota s dan memilih xn sebagai tempat persinggahan berikutnya. 2.Untuk s dan n tertentu, xn adalah nilai xn yang meminimumkan fn (s. xn). 3.fn (S) = nilai minimum dari fn (s, xn) sehingga fn (s) = fn(S, Xn ). Tujuannyaadalahuntukmendapatkanf1*(1)dengancaramencarif4*(s), f3*(s),danf2*(s),terlebihdahulu.Jadi,programadinamismenyelesaikansuatu persoalandenganmelakukanperhitunganmundurwalaupununtukpersoalan tertentu bisa dengan perhitungan maju. Solusi persoalan dengan satu stage ini adalah: SF4*(S)X4* 8 9 3 4 10 10 Hasil keseluruhan dari persoalan dengan dua stage ini adalah : x3 f3 (s,x2) = csx3 + f4* (x3)f3* (s)x3* s89 5 6 7 4 9 6 8 7 7 4 7 6 8 9 8 Hasil selengkapnya dari persoalan dengan tiga stage ini adalah : x2 f1 (s,x2) = csx2 + f3* (x2)f1* (s)X2* S567 2 3 4 11 7 8 11 9 8 11113 atau 4 57 Persoalandengan4stage,ongkosnyaadalahongkospadastagepertama ditambah dengan ongkos minimum berikutnya yaitu : x2 f1 (s,x2) = csx2 + f3* (x2) f1* (s)x1* s234 1131111113 atau 4 Dengandemikian,makasalahsaturuteoptimalnvaadalah 135810.Apabilasalesmanitumemilihx1=4,makadidapatduarute optimumyanglain,yaitu145810dan146910.semuanyaitu memberikan ongkos totat yang sama, yaitu f1*(1) = 11. 4.2. KARAKTERISTIK PERSOALAN PROGRAMA DINAMIS. Salah satu cara untuk mengenal situasi yang dapat diformulasikan sebagai persoalan programa dinamis ini ialah dengan memperhatikan bahwa struktur dasar persoalanprogramadinamisinimerupakananalogidaripersoalansalesmandi atas. Berikutinidiberikanbeberapagambarandasaryangmenandai(menjadiciri) persoalan programa dinamis : 1.Persoalandapatdibagimenjadibeberapatahap(stage,yangpadarnasing-masing stage diperlukan adanya satu keputusan. 2.Masing-masingstageterdiriatassejumlahstageyangberhubungandengan stage yang bersangkutan. 3.Hasildarikeputusanyangdiambilpadasetiapstageditransformasikandari state yang bersangkutan ke state berikutnya pada stage yang berikutnya pula. 4.Keputusanterbaikpadasuatustagebersifatindependenterhadapkeputusan yang dilakukan pada stage sebelumnya. 5.Prosedur pemecahan persoalan dimulai dengan mendapatkan cara (keputusan) terbaik untuk setiap state dari stage terakhir. 58 6.Adasuatuhubungantimbal-balikyangmengidentifikasikeputusanterbaik untuksetiapstatepadastagen,berdasarkankeputusanterbaikuntuksetiap state pada stage (n + 1). 7.Denganmenggunakanhubungantimbal-balikini,prosedurpenyelesaian persoalanbergerakmundurstagedemistage,padasetiapstageberusaha diperolehkeputusanoptimumuntukmasing-masingstatehinggaakhirnya diperoleh keputusan optimum yang menyeluruh, mulai dari stage awal. 4.3.PROGRAMA DINAMIS DETERMINISTIK Programadinamisdeterministikinidapatditerangkandengandiagram berikut :

Dengan demikian, maka pada stoge n, prosesnya akan berada pada state sn. Pada state ini dibuat keputusan xn, kemudian proses bergerak ke state sn + 1 pada stage(n+1).Darititikinikedepan,nilaifungsitujuanuntukkeputusan optimumnya telah terlebih dahulu dihitung, yaitu f*n+1 (sn+1) Keputusan memilih xn,jugamemberikankontribusiterhadapfungsitujuan,yangdengan menggabungkankeduabesaraniniakandiperolehnilaifungsitujuan.Fn(sn,xn) yang berawal pada stage n. Minimumkan nilai telsebut dengan memperhatikan xn sehingga diperoleh fn*(sn = fn (sn,xn).Setelah hal ini dilakukan untuk semua nilai snyangmungkin,makaprosedurpenyelesaiannyabergerakkembalipada persoalan dengan satu stage. Contoh: BadanKesehatanDunia(WHO)bermaksudakanmenyempurnakan pelayanankesehatandinegara-negarayangsedangberkembang.SaatiniWHO Kontribusi dari xn sn+1 sn f*n+1 (sn+1) fn (sn,xn) Stage n+1 Stage n Stage 59 mempunyai5teamkesehatanyangharusditempatkanditiganegarauntuk menyempurnakanpelayanankesehatan,pendidikankesehatan,danprograma latihan. Dengan demikian maka WHO harus menentukan berapa team yang harus ditempatkan di tiap-tiap negara, sehingga keefektifan total dari lima team itu dapat dimaksimumkan.Sebagaiukurandarikeefektifaniniialahpertambahanumur (yaitu berapa tahun umur orang akan bertambah dengan adanya team tersebut). Tabelberikutiniadalahtaksiranpertambahanumur(tahunorang)dalam satuan ribu untuk tiap negara dan tiap alokasi team yang mungkin dilakukan. Jumlah tim yang Pertumbuhan umur (ribuan tahun-orang) - Nergara dialokasikan123 0 1 2 3 4 5 0 45 70 90 105 120 0 20 45 75 110 150 0 50 70 80 100 130 Berikut ini adalah hasil perhitungan seluruhnya, dimulai dari stage terakhir (n = 3) dan bergerak mundur hingga stage pertama (n = 1). n = 3 sf3* (s) x3 0 1 2 3 4 5 0 50 70 80 100 130 0 1 2 3 4 5 n = 2 x2F2 (s,x2) = p2 (x2) + f3* (s-x2)F2* (s)x2* s012345 0 1 2 0 50 70 20 70 45 0 50 70 0 0 0,1 60 3 4 5 80 100 130 90 100 120 95 115 125 75 125 145 110 160 150 95 125 160 2 3 4 n = 1 x2F1 (s,x1) = p1 (x1) + f2* (s-x1)F1* (s)x1* s012345 51601701651601551201701 Dengan demikian, maka solusi.optimumnya adalah x1* = 1, sehingga s = 5 1=4untukn=2.Akibatnyax2*=3.Selanjutnyas=4-3=1untukn=3 sehingga x3* = 1. karena f1*(5) = 170, maka alokasi (1, 3, 1) dari team kesehatan pada tiga negara ini akan menghasilkan taksiran total 170.000 penambahan tahun orang. IV.3. PENUTUP Padabagianpenutup,diadakantanyajawabdandiskusibaikantar mahasiswa dan dosen, dan juga mahasiswa antar mahasiswa. Untuk itu diberikan juga tugas sebagai bahan latihan mahasiswa di luar jam perkuliahan. Tugas/latihan untuk materi programa dinamis adalah sebagai berikut: 1.Kapan metode programa dinamis dapat dilaksanakan? Dan berikan contohnya! 2.PuskesmasAtmajayamemiliki7(Tujuh)orangperawatdalam1(satu)team kesehatan dari puskesmas Rindina harus ditempatkan di tiga balai pengobatan dikotaBandarjaya,dalamrangkamenyempurnakanpelayanankesehatan, pendidikan kesehatan, dan programa latihan. Tabel berikut ini adalah taksiran pertambahanumur(tahunorang)dalamsatuanribuuntuktiapbalai pengobatandantiapalokasiteamyangmungkindilakukan.Berikutukuran darikeefektifaniniialahpertambahanumur(yaituberapatahunumurorang akan bertambah dengan adanya team tersebut). Jumlah tim yangDialokasikan Pertumbuhan umur (ribuan tahun-orang) Balai pengobatan 123 0000 61 1 2 3 4 5 6 7 45 35 70 90 98 105 120 21 20 45 75 102 110 150 24 50 70 80 100 120 130 Berapateamyangharusditempatkanditiap-tiapbalaipengobatan,sehingga keefektifan total dari lima team itu dapat dimaksimumkan? PERKULIAHAN KE 8: Ujian MID SEMESTER SESI/PERKULIAHAN KE: 8 TIK :Pada perkuliahan ini mahasiswa diharapkan mampu menyelesaikan persoalan-persoalanberkaitandenganmateriyangtelahdiberikan pada perkuliahan sebelumnya. Pokok Bahasan :Materi yang termasuk dalam ujianmid semester adalah: Pengantar PenelitianoperasionalII,AnalisisJaringan,Perencanaan& Pengendalian Proyek dgn CPM PERT dan ProgramaDinamis Deskripsi singkat : Dalam pertemuan ini anda akan mengerjakan dan menyelesaikan persoalan-persoalanpenelitianoperasionalIIsesuaidenganmateri yangtelahdiberikanpadaperkuliahansebelumnya.Sifatujianmid semesteradalahopenbook.Setiapmahasiswadapat menyelesaikan dan mencari jawaban tiap persoalan pada buku maupun bahan-bahan pembelajaran yang dimilikinya. 62 1.I. Bahan Bacaan: 1. Dimyanti,TjutjuTarliah,AhmadOperationsResearch,PT.SinarBaru Algensindo Bandung, 1999. 2. Don T.Philips, et.al., Operation Research: Principle and Practice, 2nd edition, John Wiley and Sons, 1987. 3. Taha,Hamdy,OperationResearch:AnIntroduction,Newyork:The MacMillan Co, 1985. 4. WayneL.Winston,OperationResearch:ApplicationandAlgorithms,3rd edition, Duxbury Press, 1994. II.Bahan Tambahan: 1.Hillier and Lieberman, Introduction to Mathematical Programming, 1st edition, McGraw-Hill, 1991. 2.Wagner,H.M.PrincipleofOperationResearch,EnglewoodCliffs,N.J: Prenntice-hall Inc, 1969. 3.Hillier,FrederickandGerald,J.Liebermam.IntroductiontoOperation Research , San Fransisco : Holden Day Ltd, 1977. III.PertanyaanKunci/Tugas:Sebelumujianmidsemester,mahasiswadiberikan kesempatan untuk bertanya berkaitan dengan persoalan yang diberikan. IV.Tugas Tidakadapemberiantugassetelahujianmidsemester,halinidikarenakanujian tersebutmerupakantabulasidanevaluasinilaimahasiswaterhadapperkuliahan sistem produksi, setelah menjalani perkuliahan selama 7 (tujuh) kali pertemuan. V.1. PENDAHULUAN Dalamperkuliahaninimahasiswaakanmengerjakandan menyelesaikanpersoalan-persoalanpenelitianoperasionalIIsesuaidengan materiyangtelahdiberikanpadaperkuliahansebelumnya.Sifatujianmid semesteradalahopenbook.Setiapmahasiswadapatmenyelesaikandan mencarijawabantiappersoalanpadabukumaupunbahan-bahan pembelajaran yang dimilikinya. V.2. PENYAJIAN Pada perkuliahan ini akan diberikan persoalan yang berkaitan dengan materiyangtelahdipelajaripadaperkuliahansebelumnya.Persoalanyang diberikan antara lain: 63 1.Apakeuntunganmempelajarinetworktheorydanberikancontoh peristiwa suatu network! 2.Sebuahperusahaankendaraanumummengoperasikanarmadanyadari kotaskekotat.Adabeberapaalternatifyangbisadilaluidalam menempuh perjalanan tersebut, dengan jaringan sebagai berikut: Tentukan rute terpendek dari kedua kota tersebut! 3.Dari suatu proyek diperoleh data sebagai berikut: Tentukan lintasan kritis serta waktu penyelesaian proyek tersebut! 4.Langkahapasajayangharusdilakukandalammemecahkansuatu persoalandalamsuatuorganisasiberkenaandenganditerapkannya penelitian operasional dalam organisasi tersebut? Jelaskan! Persoalan yang diberikan tidak harus sesuaipada persoalan tersebut di atas saja, tetapi dapat juga ditambah dan diganti dengan persoalan lainnya sesuaidengankebutuhan,ketepatandanketerbatasanwaktupengerjaan persoalan, tentunya sesuai dengan materi yang telah diberikan. V.3.PENUTUP s 3 4 2 3 4 3 3 2 1 2 t4 Kota Asal Jarak Kota Antara Kota Tujuan 8 1 2 3 6 5 4 0 A B E D F G H I J K 10 3 11 7 12 15 3 6 9 7 6 C 8 64 Padabagianpenutup,diadakantanyajawabmengenaipersoalan-persoalanyangdiberikan.Tidakadapemberiantugassetelahujianmid semester, hal ini dikarenakan ujian tersebut merupakan tabulasi dan evaluasi nilaimahasiswaterhadapperkuliahanPenelitianOperasionalII,setelah menjalani perkuliahan selama 7 (tujuh) kali pertemuan. PERKULIAHAN KE 9, 10 DAN 11: TEORI PERMAINAN SESI/PERKULIAHAN KE: 9, 10 DAN 11 TIK : Pada akhir perkuliahan ini mahasiswa diharapkan mampu: 1.Menjelaskan pengertian dan ide dasar teori permainan. 2.Mengetahuipenyelesaianpersoalanpenelitianoperasionaldengan menggunakan teori permainan. Pokok Bahasan:Teori Permainan Deskripsisingkat:Dalam pertemuan ini anda akan mempelajari persoalan keputusan dengan menggunakanteoripermainantermasukpengantarteoripermainan,two personzero-sumgame,pure-strategygame,mixed-strategygame,solusi grafisdaripermainan(2xn)dan(mx2),solusipermainan(mxn)dgn programaliniersertabagaimanacaramenyelesaikanpersoalankeputusan dengan menggunakan teori permainan tersebut. I.Bahan Bacaan: 1.Dimyati,Tjutju Tarliah, Ahmad Operations Research, PT. Sinar Baru Algensindo Bandung, 1999. 2.DonT.Philips,et.al.,OperationResearch:PrincipleandPractice,2ndedition, 65 John Wiley and Sons, 1987. 3.WayneL.Winston,OperationResearch:ApplicationandAlgorithms,3rd edition, Duxbury Press, 1994. II. Bahan Tambahan: 1.Hillier and Lieberman, Introduction to Mathematical Programming, 1st edition, McGraw-Hill, 1991. 2.Hillier, Frederick and Gerald, J.Liebermam. Introduction to Operation Research , San Fransisco : Holden Day Ltd, 1977. 3.Taha,Hamdy,OperationResearch:AnIntroduction,Newyork:The MacMillan Co, 1985. 4.Wagner,H.M.PrincipleofOperationResearch,EnglewoodCliffs,N.J: Prenntice-hall Inc, 1969. III.PertanyaanKunci/Tugas:Ketikaandamembacabahanbacaanberikut,gunakanlah pertanyaan-pertanyaan sebagai berikut: 1.Apa yang dimaksud dengan teori permainan dalam penelitian operasional? 2.Cari contoh persoalan yang dapat diselesaikan dengan menggunakan teori permainan. IV.Tugas: 1.Apa yang dimaksud dengan teori permainan? 2.Perusahan pasta gigi fantana berusaha menarik hati konsumennya dengan memberikan undianberhadiah,halinijugadilakukanolehperusahaansejeniskardilasyang merupakanpesaingterberatperusahaantersebut.Saatinimasing-masingperusahaan menguasai50%pasaran.Jikamasing-masingperusahaantidakmelakukanundian berhadiahmakapengusahaanpasartersebuttidakberubah, jikasalahsatumelakukan undianberhadiahyanglebihmenarikmakaperusahaanyanglainakankehilangan sejumlahlangganannya.Darihasilpenelitianpasarternyatabahwapresentasi langganan yang dapat dijangkau melalui media televisi adalah 50% dan melalui koran 30%danmelaluiradio20%.Keduaperusahaaniniharusmemilihmediayangsesuai untuk mempromosikan produknya dengan undian berhadiah tentunya denganmencari media promosi terbaik yang digunakan. a.Buatlah matriks payoff dari persoalan tersebut! b.Tentukan nilai game-nya. VI.1. PENDAHULUAN Dalamperkuliahanmengenaiteoripermainaniniakandibahasmengenai pengantarteoripermainan,twopersonzero-sumgame,pure-strategygame, mixed-strategygame,solusigrafisdaripermainan(2xn)dan(mx2),solusi permainan(mxn)dgnprogramaliniersertabagaimanacaramenyelesaikan persoalankeputusandenganmenggunakanteoripermainantersebut.Materiyang disampaikansangatberkaitanantarasatudenganyanglainnya,haliniberguna dalammenghasilkankeputusanyangoptimaldalammenyelesaikanpersoalan keputusan dalam suatu perusahaan. VI.2. PENYAJIAN TEORI PERMAINAN 66 6.1. Pengantar Teori Permainan. Teoripermainanadalahbagiandariilmupengetahuanyangberkaitan denganpembuatankeputusanpadasaatpihakataulebihberadadalamkondisi persaingan atau konflik. Model-modelpermainaninidapatdiklasifikasikandalambeberapacara, bergantung pada faktor-faktor berikut: banyaknya pemain, jumlah keuntungan dan kerugian,danbanyaknyastrategiyangdilakukandalampermainan.Sebagai contoh,jikabanyaknyapemainadalahduapihakmakapermainannyadisebut sebagaipermainanduaorang(two-persongame).Jikabanyaknyapemainadalah N pihak (N>3), Pemainnya disebut Permainan N orang (zero-sum game). Perhatikanpersoalantwo-personzero-sumgamedenganmatriks pembayaran sepertipada tabel berikut. Pemain B B1B2B3 Pemain AA1692 A2854 Beberapa pengertian dari persoalan di atas adalah sebagai berikut: 1.Bilangan-bilangan ynag ada di dalam matriks pembayaran (payoff matrix) menyatakanoutcomeataupembayaranstrategipermainanyangberbeda. Payoffataupembayaraninidiartikansebagaisuatuukurankeefektifan sepertiuang,persentasedaerahpemasaran,atauutilitas.Berdasarkan perjanjian, dalam two-person zero-sum game ini bilangan-bilangan positif menyatakanperolehan(keuntungan)bagipihakyangditulispadabaris sebgaipemainyangakanmemaksimumkan,dansekaligusmerupakan kerugianbagipihakyangditulispadakolomsebagaipemainyangakan meminimumkan. 2.Strategi adalah tindakan pilihan. 67 3.Aturanpermainanmenjelasknatentangbagaimanasarapemainmemilih strategi-strategi mereka.4.Suatustrategidinyatakandominanapabilasetiappayoffyangadapada suatu strategi bersifat superior (paling tinggi) dibandingkan dengan setiap payoff pada strategi lainnya. 5.Nilai permainan menyatakan ekspektasi outcome per permainan jika kedua pemainmelakukanstrategiterbaik(strategioptimum)mereka.Suatu permainan dikatakan adil jika nilai permainannya nol.6.strategioptimumadalahstrategiyangmenjadikanseorangpemainberada padaposisipilihanterbaik,tanpamemperhatikantindakan-tindakan pemain lawannya. 7.tujuanmodelpermainanadalahuntukmengidentifikasistrategioptimum bagi masing-masing pemain. 6.2. Two Person, Zero-Sum Game. Adaduajenispersoalantwo-personzero-sumgameyangbiasadijumpai. Jenis pertama adalah permainan yang posisi pilihan terbaiknya bagi setiap pemain dicapaidenganmemilihsatustrategitunggalsehinggapermainannyadisebut permainanmurni(pure-strategygame).Jenisyangkeduaadalahpermainanyang kedua pemainnya melakukan pencampuran terhadap strategi-strategi yang berbeda denganmaksuduntukmencapaiposisipilihanterbaik.Dengandemikian,jenis yang kedua ini disebut permainan strategi sampuran (mixed-strategy game). 6.3. Pure-Strategy Game Pure-Strategy Game, pemain yang akan memaksimumkan (pada contoh adalah pemain A) akan mengidentifikasikan strategi optimumnya dengan menggunakan kriteria maksimum, sedangkan pemain yang akan meminimumkan (pemain B) akan mengidentifikasikan strategi optimumnya dengan menggunakan kriteria minimaks. Jika nilai maksimin sama dengan nilai minimaks, maka permainan telah terpecahkan. (Untuk menguji hal ini, nilai tersebut harus merupakan nilai maksimum bagi kolom yang bersangkutan, dan sekaligus 68 merupakan niliai minimum bagi baris yang bersangkutan). Dalam kasus seperti ini, maka telah tercapai titik keseimbangan. Titik ini dikenal sebagai titik sadel (saddle point). Perhatikansuatusituasiketikaduabuahperusahaanbesarsedangdalam prosesperencnaanstrategiadvertensimasing-masing.Asumsikanbahwa perusahaanAmempunyaiduabuahstrategi,danperusahaanBmempunyaitiga buah strategi. Struktur strategi dan payoffnya adalah sebagai berikut: Pemain BMinimum Baris B1B2B3 Pemain AA11921 A28544 Maksimum Kolom894 Matrikspayoffpadatabeldiatasadalahuntukpemainyangakan memaksimumkan(perusahaanA).JikaAmemilihstrategiA1,MakaBakan memilihstrategiB1,sehinggapayoffuntukAadalah1.JikaAmemilihstrategi A2,makaBmemilihstrategiB3sehinggapayoffuntukAadalah4.dengan demikian,jelasbahwaperusahaanAakanberadapadaposisipilihanterbaikjika ia melakukan suatu strategi tunggal yaitu strategi A2. Kriteriamaksimin(untukpemainyangmemaksimumkan)yaitu mendapatkannilaiminimumdarimasing-masingbaris.Nilaiterbesar(nilai maksimum)darinilai-nilaiminimuminiadalahnilaimaksimin.Dengan demikian, maka untuk permainan dengan strategi murni ini, strategi optimumnya adalah baris tempat nilai maksimin terletak. Kriteriaminimaks(untukpemainyangmeminimumkan)yaitu mendapatkannilaimaksimumdarimasing-masingkolom.Nilaiterkecil(nilai minimum)darinilai-nilaimaksimuminiadalahnilaiminimaks.Dengan demikian, maka untuk permainan dengan strategi murni ini, strategi optimumnya adalah kolom tempat nilai minimaks terletak Karenanilaiminimaksdanmaksiminbernilaisama(=4),makapertanyaan berikutnyaadalah:apakahpermainaninimempuyaisaddlepoint?Jawabnya adalahya,karenanilai4merupakannilaimaksimumpadakolomnya,dan 69 sekaligusjugamerupakannilaiminimumpadabarisnya.Setelahkitaketahui saddle point ini ada, maka kita dapat menyatakan bahwa strategi optimum bagi A adalah A2 dan strategi optimum bagi B adalah B3. 6.4. Mixed-Strategy Game. Sepertitelahdijelaskandiatas,padagameyangtidakmempunyaisaddle point, penyelesaiannya harus dilakukan dengan menggunakan strategi campuran. Perhatikan matriks payoff dari suatu game berikut ini: Pemain BMinimum Baris B1B2B3 Pemain A10-22-2 254-3-3 323-4-4 Maksimum Kolom542 Karena nilai maksimin tidak sama dengan nilai minimaks, maka permainan diatstidakmempunyaisaddlepoint.Padagameini,jikaAmemilihstrategi1, makaBmemilihstrategi2.TetapijkaBmemilihstrategi2,makaAmemilih strategi 2 sehingga B akan memilih strategi 3 dan A memilih strategi 1. demikian seterusnyasehinggapermainansepertiinidikenalsebagaipermainanyangidak stabil (unstable game). Secara matematis: -Pemain A akan memilih xi (xi >0, ==mixi11) yang menghasilkanV = maks xi {min (=mia111 xi, =mia112xi,......, =miain1 xi)}. -Pemain B akan memilih yj (yj >0, ==njyj11) yang menghasilkanV =min yj{min (=njj a11yj, =njj a12yj,......, =njamj1yj)}. Nilai-nilaidiatasadalahnilai-nilaimaksimindanminimaksdariekspektasi payoff.Sepertihalnyapadakasusstrategimurni,padastrategicampuraninipun berlaku hubungan.: 70 Minimaks ekspektasi payoff> maksimin ekspektasi payoff atauv >v.Jika xi dan yj berkorespondensi dengan solusi optimum, makav= v dimana nilai yang diperoleh akan sama dengan nilai ekspektasi optimum dari permainan. 6.5. Solusi Grafis dari Permainan (2xn) dan (mx2). Solusigrafishanyadapatdigunakanuntukmenyelesaikanpersoalan permainanbilapalingsedikitsalahseorangpemainhanyamempunyai2buah strategi. Perhatikan permainan (2xn) berikut ini.Y1 Y2................Yn x1 x2 =1-x1 a11a12...............a1n a21 a22..............a2n Disinidiasumsikanbahwapermainannyatidakmempunyaisaddlepoint.Karena A mempunyai dua strategi, maka x2 = 1 x1, dengan x1> 0, x2> 0. Berdasarkan strategi murni dari B, maka ekspektasi payoff untuk A adalah: Strategi MurniEkspektasi payoff A 1 2 . . n (a11 a21) x1 +a21 (a12 a22) x1 +a22 . . (a1n a2n) x1 +a2n HalinimemperlihatkanbahwaekspektasipayoffbagiAbervariasisecara linierterhadapx1.Berdasarkankriteriauntukpermainandenganstrategi campuran,pemainAharusmemilihnilaix1yangakanmemaksimumkan ekspektasipayoffminimumnya.Halinidapatdilakukandengancara menggambarkan garis-garis lurus ke atas sebagai fungsi dari x1. Contoh: B 12 3 1 2 0-2 2 5 4-3 A A 71 Persoalaninitidakmempunyaisaddlepointdanakandiselesaikandengancara grafis. Berdasarkan strategi murni dari B, maka ekspektasi payoff untuk A adalah: Strategi MurniEkspektasi payoff A 1 2 3 -5x1 + 5 -6x1 + 4 5x1 - 3 Ketiga garis lurus ini digambarkan sebagai fungsi dari x1 sebagai berikut:Ekspektasi payoff Maksimin ekspektasi payoff V = Maks xi { min (5-5x1), (4-6x1), (-3+5x1)} Maks xi { min (4-6xi), (-35x1)}Titik potong dicari secara aljabar biasa: 4-6x1= -3+5x1 11x1= 7 x1* = 7/11 karena x1* + x2* =1 maka x2* = 4/11 v = v* -3 + 5 (7/11) = 2/11 padahal v* =vdan v* = ijaijxiyjSehingga:Y1*(5-5x1)+y2*(4-6x1)+y3*(-3+5x1)=2/11..................................(1) 5 0 4 -3 1/21x1 11 2 3 Maksimin 72 2/11 y1* + 2/11 y2* +2/11 y3* = 2/11 dengan y1* + y2* + y3* = 1 Dalamhal,persamaan aij xiyangtidakmelewatititikmaksimin berkorespondensi dengan yj=0 (supaya tidak menaikkan expected payoff). Karena itu, y1* = 0 sehingga:y2*+y3*=1 atau y3*=1-y2*. Masukkan pada persamaan (1). Jika x1 = 0maka4y2*-3y3* = 2/11 x2 = 1-2y2*+2y3* =2/11 Sehingga: y3* = 6/11 y2* = 5/11 Dengan demikian, maka solusi optimum untuk kedua pemain adalah: - Pemain A: (x1,x2) = (7/11, 4/11) - Pemain B: (y1,y2,y3) =(0, 5/11,6/11) Dengan nilai game v*2/11 6.6. Solusi permaianan (mxn) dgn programa linier. Sepertidikemukakansebelumnya,kriteriamaksimindapatdiformulasikan sebagai: Maks xi {min (=miai11xi, =12iai xi,............ =miain1xi)} Dimana =mi 1xi = 1 dan xi >0 i = 1,..............,m Contoh: Matriks payoff dari suatu permainan adalah sebgai berikut: B 123 1 2 3 3-1 -3 -3 3 -1 -4 -3 3 Tentukan strategi optimum untuk masing-masing pemain? Penyelesaian. A 73 Matrikspayoffdiatastahubahwanilaimaksiminnyaadalah-3sehingganilai permainannyadapatberharganegatifataunol.Karenaitu,diperlukansuatu konstantakyangharga-nyapalingsedikitsamadengannilaimaksiminyang negatifitu.Konstantakitukemudianditambahkankepadaseluruhelemen matriks. Misalnya digunakan k=5, maka matriksnya menjadi seb