Masalah knapsack 0-1 dalam penyelesaian travelling salesman problem (TSP) / oleh Dhia Ika Cahyanti
| Main Author: | Dhia Ika Cahyanti |
|---|---|
| Format: | Thesis NonPeerReviewed |
| Terbitan: |
, 2009
|
| Subjects: | |
| Online Access: |
http://repository.um.ac.id/16735/ |
Daftar Isi:
- Teorigraphmerupakansalahsatupenerapanmatematikayangbermanfaatuntukmenyelesaikanpermasalahandalamkehidupansehari-hari.SalahsatupermasalahanyangdapatdiselesaikanmenggunakanteorigraphadalahmasalahKnapsackyaitupermasalahanoptimasiyangmemaksimumkanataumeminimumkanfungsitujuandenganbeberapakendalayangharusdipenuhi.MasalahKnapsackyangdibahasdalamskripsiiniadalahmasalahKnapsack0-1yangdiaplikasikanpadamasalahTravellingSalesmanProblem(TSP)dalamgraphberarah.LangkahpertamayangdilakukanuntukmenyelesaikanmasalahTSPdalamKnapsack0-1adalahmendefinisikanfungsitujuanyaitumeminimumkanbobotsetiapsisiyangterpilihsertamendefinisikankendalayangharusdipenuhiyaitusemuatitikharusdilewatitepatsatukali.VariabelkeputusanyangdigunakandalammasalahTSPadalah0jikalintasanyangmerupakankandidatsolusitidakdilewatidanbernilai1jikalintasantersebutdilewati.LangkahberikutnyauntukmemperolehsolusiyangmaksimumdilakukandenganmenggunakanalgoritmaGreedyyaitudenganmengurutkanbobotsisiyangterhubungdariyangpalingkecilkemudianmengambilbobotpalingkeciltersebutsebagaisolusioptimumlokal.Titikyangsudahterpilihtidakdipertimbangkankembali.SebagaiperbandingandigunakanmetodeBranchandBounduntukmasalahTSPdenganmelakukanreduksibarisdankolomdarimatriksbobotpadagraphsampaisetiapbarisdankolomyamemuatpalingsedikitsatubuahnolsehinggadiperolehsuatusikelHamiltondenganjarakminimum.DenganmenggunakanbeberapacontohkasusTSPdiperolehanggapanbahwapenyelesaiandenganmenggunakanalgoritmaGreedylebihefisien.PermasalahanTSPyangbobotpadasisiarahberlawananyasamasolusiyangdiperolehdarikeduametodediatasadalahsama.SedangkanuntukpermasalahanTSPdenganbobotpadasetiapsisiberarahnyatidaksamasolusiyangoptimumdiperolehdenganmenggunakanmetodeBranchandBound.Halinidisebabkanolehnilaiongkosyangdihitungpadasetiapsimpuladalahbobotyangpalingkecilyangterdapatpadamatrikstereduksi.