Minggu, 11 Juni 2017

METODE DUAL SIMPLEKS

METODE DUAL SIMPLEKS


Metode dual simpleks digunakan jika tabel optimal tidak layak. Jika fungsi kendala ada yang menggunakan pertidaksamaan ≥ dan tidak ada = dalam bentuk umum PL, maka metode dual simpleks dapat digunakan. Kita selesaikan contoh di bawah ini.
Min z = 21x1 + 18x2 + 15x3
Terhadap       90x1 + 20x2 + 40x3 ≥ 200
                      30x1 + 80x2 + 60x3 ≥ 180
                      10x1 + 20x2 + 60x3 ≥ 150
                                 x1, x2, x3 ≥ 0
semua kendala menggunakan pertidaksamaan ≥. Kendala dengan pertidaksamaan ≥ dapat diubah ke pertidaksamaan ≤ dengan mengalikan pertidaksamaan dengan -1. Bentuk umum PL di atas berubah menjadi:
Min z = 21x1 + 18x2 + 15x3
Terhadap          -90x1 - 20x2 - 40x3 ≤ -200
                         -30x1 - 80x2 - 60x3 ≤ -180
                         -10x1 - 20x2 - 60x3 ≤ -150 
                                   x1, x2, x3 ≥ 0
Semua fungsi kendala sudah dalam bentuk pertidaksamaan ≤, maka kita kita hanya perlu menambahkan variabel slack untuk mengubah bentuk umum ke bentuk baku/standar. Variabel slack akan berfungsi sebagai variabel basis awal.
Bentuk Baku/standar:
Min z = 21x1 + 18x2 + 15x3 + 0s1 + 0s2 + 0s3
Terhadap -90x1 - 20x2 - 40x3 + s1 = -200
-30x1 - 80x2 - 60x3 + s2 = -180
-10x1 - 20x2 - 60x3 + s3 = -150
x1, x2, x3, s1, s2, s3 ≥ 0
METODE DUAL SIMPLEKS
Metode dual simpleks digunakan jika tabel optimal tidak layak. Jika fungsi kendala ada yang menggunakan pertidaksamaan ≥ dan tidak ada = dalam bentuk umum PL, maka metode dual simpleks dapat digunakan. Kita selesaikan contoh di bawah ini.
Min z = 21x1 + 18x2 + 15x3
Terhadap       90x1 + 20x2 + 40x3 ≥ 200
                      30x1 + 80x2 + 60x3 ≥ 180
                      10x1 + 20x2 + 60x3 ≥ 150
                                 x1, x2, x3 ≥ 0
semua kendala menggunakan pertidaksamaan ≥. Kendala dengan pertidaksamaan ≥ dapat diubah ke pertidaksamaan ≤ dengan mengalikan pertidaksamaan dengan -1. Bentuk umum PL di atas berubah menjadi:
Min z = 21x1 + 18x2 + 15x3
Terhadap          -90x1 - 20x2 - 40x3 ≤ -200
                         -30x1 - 80x2 - 60x3 ≤ -180
                         -10x1 - 20x2 - 60x3 ≤ -150 
                                   x1, x2, x3 ≥ 0
Semua fungsi kendala sudah dalam bentuk pertidaksamaan ≤, maka kita kita hanya perlu menambahkan variabel slack untuk mengubah bentuk umum ke bentuk baku/standar. Variabel slack akan berfungsi sebagai variabel basis awal.
Bentuk Baku/standar:
Min z = 21x1 + 18x2 + 15x3 + 0s1 + 0s2 + 0s3
Terhadap -90x1 - 20x2 - 40x3 + s1 = -200
-30x1 - 80x2 - 60x3 + s2 = -180
-10x1 - 20x2 - 60x3 + s3 = -150
x1, x2, x3, s1, s2, s3 ≥ 0
Tabel di atas optimal tapi tidak layak (ingat, untuk fungsi tujuan minimisasi, tabel sudah optimal jika semua koefisien baris tujuan sudah negatif atau 0). Untuk membuat tabel tersebut layak, kita harus gunakan metode dual simpleks. Langkah-langkah penyelesaian simpleks menggunakan metode dual adalah: 1.
1.      Tentukan baris pivot. Baris pivot adalah baris dengan nilai kanan negatif terbesar. Jika negatif terbesar lebih dari satu, pilih salah satu sembarang.
2.       Tentukan kolom pivot. Kolom pivot diperoleh dengan terlebih dahulu membagi nilai baris z dengan baris pivot. Dalam hal ini, semua nilai baris pivot dapat menjadi pembagi kecuali nilai 0. Kolom pivot adalah kolom dengan rasio pembagian mutlak terkecil. Jika rasio pembagian mutlak terkecil lebih dari satu, pilih salah satu secara sembarang.
3.      Pembentukan tabel berikutnya sama dengan prosedur dalam primal simpleks.
Gunakan tabel awal simpleks di atas.
Ø  Baris pivot adalah baris S1, baris dengan nilai kanan negatif terbesar.
6 photo 6_zps31l0h6sb.jpg

Ø  Kolom pivot adalah kolom X1
7 photo 7_zpsquuttkqe.jpg

Ø  Iterasi-1
 photo 8_zpsgksk6kh4.jpg

Ø  Iterasi-2
 photo 9_zpsl8dd4l2c.jpg

Ø  Iterasi-3
 photo 10_zpsmgsfevhv.jpg
Sumber :
- http://webcache.googleusercontent.com/search?q=cache:SBT9daUFw5YJ:ishaq.staff.gunadarma.ac.id/Downloads/files/43852/metode-big-m-dua-fase-dan-dual-simpleks.pdf+&cd=1&hl=id&ct=clnk&client=firefox-b

METODE DUA FASE

METODE DUA FASE


Metode dua fase digunakan jika variabel basis awal terdiri dari variabel buatan. Disebut sebagai metode dua fase, karena proses optimasi dilakukan dalam dua tahap. Tahap pertama merupakan proses optimasi variabel buatan, sedangkan proses optimasi variabel keputusan dilakukan pada tahap kedua. Karena variabel buatan sebenarnya tidak ada (hanya ada di atas kertas), maka tahap pertama dilakukan untuk memaksa variabel buatan bernilai 0. Perhatikan kasus berikut: 
Tahap 1
Min A = A1 + A2
Terhadap:           x1 + x2 + A1 = 90
                  0.001x1 + 0.002x2 + s1 = 0.9
                  0.09x1 + 0.6x2 - s2 + A2 = 27
                    0.02x1 + 0.06x2 + s3 = 4.5 
                          x1, x2, s1, s2, s3 ≥ 0
karena A1 dan A2 berfungsi sebagai variabel basis pada solusi awal, maka koefisiennya pada fungsi tujuan harus sama dengan 0. untuk mencapai itu, gantikan nilai A1 dari fungsi kendala pertama (kendala yang memuat A1) dan nilai A2 dari fungsi kendala ketiga (kendala yang memuat A2).
Dari kendala -1 diperoleh :
                                           A1 = 90 - x1 - x2
Dari kendala-3 diperoleh: A2 = 27 - 0.09x1 - 0.6x2 + s2
 Maka fungsi tujuan tahap-1 menjadi:
Min A = (90 - x1 - x2) + (27 - 0.09x1 - 0.6x2 + s2)
            =117 - 1.09x1 - 1.6x2 + s2
Solusi awal
Iterasi

Iterasi 2          
3 photo 3_zps7xu2173o.jpg
Tahap 2
Min z = 2 x1 + 5.5 x2
Terhadap: tabel optimal tahap pertama
Dari tabel optimal tahap 1 diperoleh:
X1 = 52.94 – 17/12s2
X2 = 37.059 + 1.7542s2
Maka fungsi tujuan adalah:
Min z = 2(52.94 – 17/12s2) + 5.5 (37.059 + 1.7542s2)
= -17/6s2 + 9.6481s2 + 309.7045 = 6.814767s2 + 309.7045

Solusi awal            
3 photo 3_zps7xu2173o.jpg

Tabel di atas sudah optimal. Solusi optimal adalah :

X1 = 52.94; X2 + 37.059; dan z = 309.7045

Sumber : 
 - http://webcache.googleusercontent.com/search?q=cache:SBT9daUFw5YJ:ishaq.staff.gunadarma.ac.id/Downloads/files/43852/metode-big-m-dua-fase-dan-dual-simpleks.pdf+&cd=1&hl=id&ct=clnk&client=firefox-b

METODE BIG M

METODE BIG M


Sering kita menemukan bahwa fungsi kendala tidak hanya dibentuk oleh pertidaksamaan ≤ tapi juga oleh pertidakasamaan ≥ dan/atau persamaan (=). Fungsi kendala dengan pertidaksamaan ≥ mempunyai surplus variable, tidak ada slack variables. Surplus variable tidak bisa menjadi variabel basis awal. Dengan demikian harus ditambahkan satu variabel baru yang dapat berfungsi sebagai variabel basis awal. Variabel  yang dapat berfungsi sebagai variabel basis awal hanya slack variables dan artificial variables (variabel buatan). 1.
1.      Jika semua fungsi kendala menggunakan pertidaksamaan ≤ maka variabel basis awal semuanya adalah slack variables. Penyelesaian solusi optimal untuk kasus seperti ini dilakukan dengan cara yang sudah diperkenalkan sebelumnya. 2.
2.      Jika fungsi kendala menggunakan pertidaksamaan ≥ dan/atau ≤ maka variabel basis awal adalah slack variables dan/atau variabel buatan. Penyelesaian solusi optimal untuk kasus seperti ini dilakukan dengan memilih antara metode Big M, Dua Fase atau Dual Simpleks.
3.      Jika fungsi kendala ada yang menggunakan persamaan maka variabel buatan akan ditemukan pada variabel basis awal. Penyelesaian solusi optimal untuk kasus seperti ini hanya dapat dilakukan dengan memilih antara metode Big M atau Dua Fase.
Kita akan bahas metode Big M dalam sub bab ini. Perbedaan metode Big M dengan primal simpleks biasa (teknik penyelesaian yang sudah dipelajari sebelumnya), terletak pada pembentukan tabel awal. Jika fungsi kendala menggunakan bentuk pertidaksamaan ≥, perubahan dari bentuk umum ke bentuk baku memerlukan satu variabel surplus. Variabel surplus tidak dapat berfungsi sebagai variabel basis awal, karena koefisiennya bertanda negatif. Sebagai variabel basis pada solusi awal, harus ditambahkan satu variabel buatan. Variabel buatan pada solusi optimal harus bernilai 0, karena variabel ini memang tidak ada.
Teknik yang digunakan untuk memaksa variabel buatan bernilai 0 pada solusi optimal adalah dengan cara berikut:
·         Penambahan variabel buatan pada fungsi kendala yang tidak memiliki variabel slack, menuntut penambahan variabel buatan pada fungsi tujuan.
·         Jika fungsi tujuan adalah maksimisasi, maka variabel buatan pada fungsi tujuan mempunyai koefisien +M; jika fungsi tujuan adalah minimisasi, maka variabel buatan pada fungsi tujuan mempunyai koefisien -M.
·         Karena koefisien variabel basis pada tabel simpleks harus bernilai 0, maka variabel buatan pada fungsi tujuan harus digantikan nilai dari fungsi kendala yang memuat variabel buatan tersebut.
Perhatikan contoh di bawah ini.
Bentuk Umum
Min. z = 4x1 + x 2
Terhadap:     3x1 + x2 = 3
4x1 + 3x2 ≥ 6
x1 + 2x2 ≤ 4
x1, x2 ≥ 0
Bentuk Baku:
Min. z = 4 x1 + x2
Terhadap:     3x1 + x2 = 3
4x1 + 3x2 - s1 = 6
x1 + 2x2 + s2 = 4 
x1, x2, s1, s2 ≥ 0
Kendala 1 dan 2 tidak mempunyai slack variables, sehingga tidak ada variabel basis awal. Untuk berfungsi sebagai variabel basis awal, pada kendala 1 dan 2 ditambahkan masing-masing satu variabel buatan (artificial variable). Maka bentuk baku Big M-nya adalah:
Min. z = 4 x1 + x2 + MA1 + MA2
Terhadap:   3x1 + x2 + A1 = 3
4x1 + 3x2 - s1 + A2 = 6
x1 + 2x2 + s2 = 4 
x1, x2, s1, s2 ≥ 0
1.      Nilai A digantikan dari fungsi kendala pertama.
A1 = 3 - 3x1 - x2
MA1 berubah menjadi M(3 - 3x1 - x2)             3M - 3Mx1 - Mx2

2.     Nilai A digantikan dari fungsi kendala ketiga.
A2 = 6 - 4x1 - 3x2 + s1
MA2 berubah menjadi M(6 - 4x1 - 3x2 + s1)
6M - 4Mx1 - 3Mx2 + Ms1
3.      Fungsi tujuan berubah menjadi
Min z   = 4x1 + x2 + 3M - 3Mx1 - Mx2 + 6M - 4Mx1 - 3Mx2 + Ms1
= (4 -7M)x1 + (1 - 4M)x2 + Ms1 + 9M
Sumber :  
- http://webcache.googleusercontent.com/search?q=cache:SBT9daUFw5YJ:ishaq.staff.gunadarma.ac.id/Downloads/files/43852/metode-big-m-dua-fase-dan-dual-simpleks.pdf+&cd=1&hl=id&ct=clnk&client=firefox-b

Jumat, 28 April 2017

Study Kasus Tentang Jaringan Jalan Untuk Menentukan Rute Terpendek



          Study Kasus Tentang Jaringan Jalan Untuk Menentukan Rute Terpendek

      Kota Balik papan merupakan salah satu kota yang berada di Provinsi Kalimantan Timur yang memiliki peningkatan perkembangan pembangunan yang sangat pesat. Salah satunya adalah pembangunan pusat kesehatan antara lain rumah sakit dan puskesmas. Peran dari pusat kesehatan tersebut tidak kalah penting fungsinya seperti bangunan,bangunan penting lainnya yang ada di Kota Balikpapan. Keberadaan pusat kesehatan sangat penting karena dapat membantu mengobati
dan merawat orang yang sakit serta memberikan pelayanan Unit Gawat Darurat (UGD) selama 24 jam bagi masyarakat yang mengalami kecelakaan atau perawatan yang harus segera ditolong.Bagi warga Kota Balikpapan, khususnya warga pendatang masih ada yang belum mengetahui dimana saja letak pusat kesehatan dan harus melewati jalur mana yang lebih dekat dari tempat mereka berada. Pada saat mereka mengalami keadaan yang sangat genting, misalnya saja salah satu keluarga mereka mengalami kecelakaan, sementara mereka baru beberapa hari
berada di Kota Balikpapan, maka mereka kesulitan dalam menentukan harusdibawa ke mana dan melewati jalur mana yang lebih dekat dari tempat kejadian, agar orang tersebut segera mendapatkan pertolongan medis untuk memperkecil resiko yang
tidak diinginkan.Oleh karena itu diperlukan adanya sistem Penentuan RuteTerpendek menggunakan Metode Dijkstra berbasis WebGIS. Dimana sistem
informasi berbasis WebGISini,dapat diakses di semua tempat dan waktu serta bisa dilakukan oleh siapa saja. Dikemas dalam bentuk sistem informasi yang gratis dan legal, dan dapat digunakan dengan mudah. Rumusan Masalah Berdasarkan latar belakang tersebut dapat dirumuskan suatu masalah sebagai berikut,
“Bagaimana Membangun Aplikasi Penentuan Rute Terpendek menggunakan Metode Dijkstra Berbasis WebGIS ”.Batasan Masalah Pada penelitian ini pembahasan masalah
dibatasi pada :
1.Daerah yang menjadi objek penelitian adalah Kota Balikpapan.
2.Data spasial yang digunakan adalah lokasi Rumah Sakit dan Puskesmas, serta Data Jalan.
3.Input data berupa titik pusat kesehatan (Rumah Sakit/Puskesmas) sebagai titik nol (awal) dan titik tujuan.
4.Output yang dihasilkan berupa peta, rute yang dilalui, jarak tempuh dan transportasi yang digunakan antara tempat pemakai system menuju pusat kesehatan yang terdekat.

Tujuan Penelitian Tujuan yang ingin dicapai dari penelitian ini adalah sebagai berikut :
1.Dapat mempermudah masyarakat dalam mencari informasi dan letak bangunan Rumah Sakit dan Puskesmas yang terdapat di Kota Balikpapan.
2.Terciptanya aplikasi Penentuan Rute Terpendek menggunakan Metode Dijkstra
untuk membantu memberikan informasi dalam
bentuk peta yang berbasis web (WebGIS).
3.Waktu yang digunakan oleh pengguna sistem (user) untuk mencari pusat kesehatan menjadi lebih singkat dan rute menjadi lebih dekat.
TINJAUAN PUSTAKA
Algoritma Dijkstra Algoritma Dijkstra (sesuai dengan nama penemunya, Edsger W. Dijkstra) merupakan sebuah algoritma yang diterapkan untuk menentukan lintasan terpendek dalam sejumlah langkah pada graf berarah maupun graf takberarah. Algoritma tersebut menggunakan prinsip greedy, yakni pada setiap langkah dipilih sisi yang berbobot minimum dan dimasukkan ke dalam himpunan solusi. Berikut
salah satu versi Algoritma Dijkstra [10]:
1.    Misalkan sebuah graf berbobot dengan n buah simpul dinyatakan dengan matriks ketetanggaan
M = [mij] yangdalam hal ini,
mij = bobot sisi (i, j)
(pada graf takberarah mij = mji)
mii = 0
mij = ∞, jika tidak ada sisi dari simpul i ke simpul j
2.    Selain matriks M, digunakan pula
S = [si] yang dalam hal ini,
si = 1, jika simpul i termasuk ke dalam lintasan terpendek
si = 0, jika simpul i tidak termasuk ke dalam lintasan terpendek
3.    Dan tabel D = [di] yang dalam hal ini,
di = panjang lintasan dari simpul awal s ke simpul i

Sistem Informasi Geografis
Sistem Informasi Geografis merupakan suatu sistem informasi yang berbasis komputer, dirancang untuk bekerja dengan menggunakan data yang memiliki informasi spasial (bereferensi keruangan). Sistem ini meng-capture, mengecek, mengintegrasikan,memanipulasi, menganalisa, dan menampilkan data yang secara spasial mereferensikan kepada kondisi bumi.SIG adalah suatu sistem berbasis komputer yang memiliki kemampuan dalam menangani data bereferensi geografi yaitu pemasukan data, manajemen data (penyimpanan dan pemanggilan kembali), manipulasi dan analisis data, serta keluaran sebagai hasil akhir (output). Hasil akhir
(output) dapat dijadikan acuan dalam pengambilan keputusan pada masalah yang berhubungan dengan geografi.SIG sebagai sistem berbasis komputer yang digunakan untuk memasukkan, menyimpan, mengelola, menganalisis dan mengaktifkan kembali data yang mempunyai referensi keruangan untuk berbagai tujuan yang berkaitan dengan pemetaan dan perencanaan.MapServer MapServer adalah program CGI (CGI : Common Gateway Interface) yang terpasang dan
berjalan tapi tidak aktif dalam server (aktif hanya saat dipanggil). Saat
request/permintaan dikirimkan kemapserver, maka akan digunakan informasi yang
dikirimkan lewat URL dan mapfile untuk membuat (generate) peta yang diinginkan. Permintaan ini bisa juga termasuk permintaan untuk membuat legenda, peta referensi, batang skala, dan variabel lain yang dikirimkan ke CGI.Program CGI akan dieksekusi di webserver dan berdasarkan beberapa parameter tertentu (khususnya konfigurasi dalam bentuk file *.MAP) maka akan menghasilkan data yang kemudian dikirim ke web browser, baik dalam bentuk gambar peta maupun bentuk lain.

QuantumGIS
QuantumGIS (QGIS) adalah aplikasi SIG gratis yang mencakup pemetaan, analisis spasial, dan beberapa fitur DesktopGIS lainnya. Aplikasi ini sama dengan paket aplikasi GIS komersial, namun aplikasi ini didistribusikan secara gratis dibawah
lisensi GNU. QuantumGIS mendukung format data vektor, raster, dan database (PostGIS dan Oracle). QuantumGIS juga dapat diprogram ulang untuk mengerjakan tuga yang lebih spesifik. Aplikasi ini juga merupakan suatu aplikasi multi-platform yang dapat dijalankanpada sistem operasi yang berbeda-beda termasuk MacOS X, Linux, Unix dan Windows.HASIL DAN PEMBAHASAN.

Digitasi Peta Pada QuantumGIS
Peta Kota Balikpapan yang telah diperoleh sebelumnya akan digunakan untuk proses digitasi.Teknik digitasipeta pada prinsipnya adalah pembuatan peta melalui proses komputer. Penyimpanan filedi komputer dari hasil digitasi peta tersebut dikelompokkan berdasarkan layeryang sesuai dengan tipenya masing-masing. Dalam proses digitasi peta Kota Balikpapan ini digunakan 3 jenis layer, yaitu tipe
polygon (ruang), tipe point(titik), dan tipe line (garis). Pada setiap proses digitasi, ditambahkan sejumlah atribut sesuai kebutuhan masing-masing objek, yang nantinya akan ditampilkan sebagai suatu informasi pada objek tersebut. Berikut tampilan hasil akhir proses digitasi peta Kota Balikpapan:

Hasil DigitasiPeta Kota Balikpapan
Menggunakan QuantumGIS Setelah peta selesai di digitasi, dilanjutkan dengan mengexport peta kedalam bentuk file *.MAP agar dapat ditampilkan dalam web.
Kemudian membuat database pada PgAdmin III dengan nama Balikpapan, yang isi tabelnya diperoleh dari hasil import database pada QuantumGIS.Rancangan Sistem
Berikut adalah rancangan system yang dibangun menggunakan empat jenis pemodelan UML beserta dengan penjelasannya, antara lain :

Use Case
Diagram WebGIS Penentuan Rute Terpendek Menuju Pusat Kesehatan
Sebuah Use Case menggambarkan interaksi antara aktor dengan sistem dan fungsionalitas dari aplikasi Penentuan Rute Terpendek Menuju Pusat Kesehatan Menggunakan Metode Dijkstra Berbasis WebGIS. Diagram tersebut terdiri dari satu aktor dan sembilan Use Case. Dimana antara Use Case satu dengan lainnya
saling berkaitan jika kondisi tertentu terpenuhi.

Activity
Diagram WebGIS Penentuan Rute Terpendek Menuju Pusat Kesehatan Activity Diagrammenggambarkan berbagai alur aktivitas secara umum dalam sistem yang
sedang dirancang, bagaimana masing-masing alur berawal, decision yang mungkin terjadi dan bagaimana berakhir. Pada diagram tersebut alur berawal dari guest yang membuka sistem Penentuan Rute Terpendek Menuju Pusat Kesehatan Kota Balikpapan, lalu memilih Menu

Peta Balikpapan dan melakukan pencarian dengan memilih titik awal dan titik tujuan, kemudian sistem akan melakukan proses perbandingan kemungkinan
rute yang terpendek. Alur berakhir dengan pengguna mendapatkan informasi mengenai Rumah Sakit atau Puskesmas yang dituju, Rute Terpendek, Jarak Tempu
h, Nama Jalan, dan Transportasinya.

Sequence
Diagram
WebGIS Penentuan Rute Terpendek Menuju Pusat Kesehatan Sequence Diagram
menggambarkan interaksi antar objek didalam sistem. Dimana pada diagram tersebut menggambarkan langkah-langkah yang dilakukan dalam sistem yang terdiri dari satu aktor, enam participant dengan lifelinenya dan 10 message.

Class
Diagram
Penentuan Rute Terpendek Menuju Pusat Kesehatan Class Diagram menggambarkan hubungan struktur dan deskripsi class, package beserta objek
antar tabel yang terdapat pada sistem. Dimana terdapat tujuh tabel yakni tabel peta_balikpapan, jalanutama, jalanlain,pusatkesehatan, transport, hubungan, dan simpangan yang saling berhubungan antar satu sama lain.Implementasi Sistem
Implementasi sistem meliputi lingkungan implementasi serta implementasi program.
Lingkungan Implementasi Merupakan lingkup dimana tempat penyimpanan file-file
yang digunakan dan saling berhubungan untuk mendukung pengembangan
aplikasi. Yakni dengan membuat folder-folder yang digunakan untuk menampung aplikasi yang telah dibuat. Folder yang dipakai untuk menyimpan aplikasi adalah folder latihan yang berada pada “File System:\var\www\”. Folderlatihan terdiri dari subfolder data, etc, map, dan mapscript. Subfolder “data”memiliki subfolder lagi, yakni subfolder shp berfungsi untuk menyimpan data simbol peta dalam format (*.shp) yang digunakan dalam sistem. Subfolder “etc” digunakan untuk menyimpan gambar-gambar yang berfungsi sebagai simbol pada legenda yang melambangkan kelurahan,jalanutama, jalanlain, pusatkesehatan, dan informasi lainnya yang diperlukan. Subfolder “map” berisi file PETA_BPP.map yang digunakan untuk menghubungkan antara file yang berekstensi .shp dan database PostgreSQL dengan mapscript. Dan Subfolder “mapscript” berisi file-file untuk mengelola WebGIS pencarian rute terpendek menuju pusat kesehatan Kota Balikpapan.

Tampilan Halaman Peta
Prosedur Algoritma Dijkstra
Seperti dijelaskan pada bab sebelumnya, algoritma dijkstra adalah algoritma menentukan lintasan terpendek dalam sejumlah langkah pada
graf berarah maupun graf tak-berarah yang pada setiap langkah dipilih sisi yang berbobot minimum dan dimasukkan ke dalam himpunan solusi. Pada sistem ini prosedur algoritma dijkstra yang dilakukan adalah sebagai berikut :
1.Ditentukan titik awal (startnode) dan titik tujuan (bestnode) untuk mencari rute terpendek. Kemudian dilakukan percobaan sebanyak mungkin hingga didapatkan rute terpendek
2.Dilakukan update titik (rute) terbaru dan sebelumnya hingga kemungkinan maximal percobaan ditemukan.Pada bagian ini perhitungan dijkstra dilakukan, yakni dengan menambahkan setiap jarak yang dilalui oleh tiap-tiap titik sehingga didapat kan hasil jarak yang ditempuh kemudian dibandingkan dengan hasil percobaan sampai ditemukan jarak yang terpendek.
3.Jika maximal percobaan telah mendapatkan hasil akhir rute terpendek maka
bestnode (rute terpendek) akan ditampilkan sebagai hasil pencarian.Pengujian Sistem Pengujian pertama diambil pencarian secara manual yakni dari titik awal,
Puskesmas Baru Ulu menuju RSU Kanudjoso, terdapat beberapa jalan
alternatif seperti berikut :
1.5-4-6-7-41-1-42-52-53-55-56-57-58-21-18 dengan jarak 7455m
2.5-4-6-7-41-1-20-19-9-10-11-13-18 dengan jarak 11765m
3.5-4-6-7-41-1-42-43-44-52-53-55-56-57-58-21-18 dengan jarak 9855m
4.5-4-6-7-41-1-42-43-44-45-56-57-58-21-18 dengan jarak 7475m
Maka Jalur terpendeknya adalah
a 5-4-6-7-41-1-42-52-53-55-56-57-58-21-18 dengan jarak7455m
Untuk pencarian menggunakan sistem adalah
sebagai berikut :
Hasil Pencarian Dari Puskesmas Baru Ulu Menuju RSU Balikpapan Hasil dari perbandingan pencarian rute terpendek secara manual dan menggunakan sistem
Dimana rute dari titik awal Puskesmas Baru Ulu menuju titik tujuanRSU Balikpapan adalah 5-4-6-7-41-1-42-52-53-55-56-57-58-21-18dengan jarak tempuh 7455 meter. Pada sistem ini juga ditampilkan jalan yang dilalui dan angkutan umum yang dapat digunakan menuju pusat kesehatan yang telah dipilih.

KESIMPULAN
Berdasarkan dari hasil pengujian sistem, dapat disimpulkan bahwa :
1.Sistem dapat mencari jalur terpendek yang dapat mempermudah masyarakat dalam mencari informasi dan letak pusat kesehatan yang terdapat di Kota Balikpapan.
2.Dengan adanya WebGIS penentuan rute terpendek menuju pusat kesehatan Kota Balikpapan menggunakan metode dijkstra ini, dapat membantu memberikan informasi dalam bentuk peta.
3.Waktu yang digunakan oleh pengguna sistem untuk mencari pusat kesehatan lebih singkat dan rute menjadi lebih dekat.