OPTIMASI PENYUSUNAN PEGAS DENGAN METODE SISTEM PERBEDAAN BATASAN DAN ALGORITMA JALUR TERPENDEK

Johan Varian Alfa, Rully Soelaiman, Chastine Fatichah

Abstract


Pada permasalahan nyata, khususnya dunia fisika, penyusunan pegas dengan batasan-batasan tertentu
yang optimal merupakan salah satu permasalahan optimasi yang muncul, dimana batasan yang diberikan
adalah besaran-besaran yang membentuk gaya pegas. Pada penelitian ini, diusulkan sebuah desain
algoritma optimasi penyusunan pegas, yang dimulai dengan memodelkan permasalahan ke dalam graf,
kemudian menggunakan metode sistem perbedaan batasan dan juga algoritma jalur terpendek untuk
menghasilkan susunan pegas yang optimal. Sistem perbedaan batasan digunakan untuk memodelkan
permasalahan ke dalam bentuk pertidaksamaan. Kemudian dicari penyelesaiannya dengan menggunakan
konsep graf yang disebut graf batasan. Penyelesaian akhir yang digunakan agar mendapatkan solusi yang
optimal adalah algoritma jalur terpendek. Algortima jalur terpendek yang digunakan adalah algoritma
Perbaikan Dijkstra. Hasilnya mampu menghasilkan susunan pegas yang optimal dan benar. Dan setelah
diuji coba, algoritma Perbaikan Dijkstra yang digunakan mampu lebih efisien dari segi performa waktu
eksekusi dibandingkan algoritma Bellman-Ford. Penghematan waktu yang didapat dengan menggunakan
algoritma Perbaikan Dijkstra rata-rata mencapai 83,55%.


Keywords


Graf, Jalur Terpendek, Optimasi, Sistem Perbedaan Batasan

References


Cormen, Thomas H., Leiserson,

Charles E., Rivest, Ronald L. dan

Stein, Clifford. [2001]. Introduction

to Algorithms, Second Edition. MIT

Press.

Wang Shu-Xi [2012], “The Improved

Dijkstra's Shortest Path Algorithm

and Its Application”, ELSEVIER:

Procedia Enginering 29, pp 11861190

A.V. Goldberg, T. Radzik [1993], “A

Heuristic Improvement Of The

Bellman–Ford Algorithm”,

AMLETS: Appl. Math. Lett. 6, pp 3–

D. Cantone, S. Faro [2004], “TwoLevels-Greedy:

A Generalization Of

Dijkstra’s Shortest Path Algorithm”,

Electron. Notes Discrete Math. 17,

pp 81–86.

T. Takaoka [2004], “A Faster

Algorithm For The All-Pairs Shortest

Path Problem And Its Application,

In: K.Y. Chwa, J.I. Munro (Eds.)”,

COCOON, In: Lecture Notes in

Computer Science, vol. 3106,

Springer, pp. 278–289.

J. Fakcharoenphol [2006], “S. Rao,

Planar Graphs, Negative Weight

Edges, Shortest Paths, And Near

Linear Time”, J. Comput. System Sci.

, pp 868–889.

Anonim, [2013]. Sphere Online

Judge. SPRING LOADED.

http://www.spoj.com/problems/SPRI

NG/, diakses tanggal 22 September


Refbacks

  • There are currently no refbacks.