Sabtu, 23 April 2011

contoh cara menentukan KKM

Siswa dikatakan tuntas belajar secara individu jika memenuhi KKM (kriteria Ketuntasan Minimal) yang telah ditetapkan. Adapun syarat untuk menentukan KKM adalahmenentukan kompleksitas materi, daya dukung dan intake. Secara sederhana kompleksitas materi merupakan sulit atau mudahnya materi tsb dipahami oleh siswa. Misalnya   Menyelesaikan sistem pertidak samaan linier ditentukan nilai kompleksitasnya 76 dan Merancang model matematika dari masalah program linier dan penyelesaiannya ditentukan nilai kompleksitasnya 74, hal ini menunjukkan bahwa materi Menyelesaikan sistem pertidak samaan linier lebih sulit dibandingkan dengan materi Merancang model matematika dari masalah program linier dan penyelesaiannya.Daya dukung merupakan komponen yang mendukung tercapainya KKM yaitu kemampuan guru dalam mengajar, sarana dan prasarana termasuk alat peraga dan media pembelajaran.Nilai daya dukung dapat ditentukan sesuai dengan keadaan dilapangan.Sedangkan yang termasuk Intake adalah kemampuan awal siswa yang dilihat dari nilai sebelumnya.
Berikut adalah contoh penentuan kriteria  ketuntasan minimal (KKM).

CONTOH PENENTUAN
KRITERIA KETUNTASAN MINIMAL(KKM)
Nama Sekolah
Mata Pelajaran
Kelas
Semester
Tahun Pelajaran
:
:
:
:
:

Matematika
XII Bahasa
Ganjil
2010/2011


No.
Kompetensi Dasar / Indikator
SKBM

KRITERIA PENENTUAN
Rata-Rata

Kompleksitas
Daya Dukung
Intake


1.1.  Menyelesaikan sistem pertidak samaan linier
76
76
76
76


1.2.  Merancang model matematika dari masalah program linier dan penyelesaiannya
74
74
74
74


1.3.  Menyelesaikan model matematika dari masalah program linier dan penyelesaiannya
72
72
72
72



2.1Menggunakan sifat dan operasi matrik untuk menunjukkan bahwa suatu matrik adalah suatu invers dari matrik persegi lai
78
78
78
78






2.2  Menentukan determinan dan invers matrik berordo 2
76
76
76
76



2.3.  Menggunakan determinan dan invers dalam menyelesaikan sistem persaman linier dua variabel
74
74
74
74

contoh penghitungan pekan efektif

Ketepatan dalam menyelesaikan materi pembelajaran sesuai yang dituntut oleh kurikulum merupakan hal yang sangat penting. 
Untuk keperluan tsb seorang guru diharuskan untuk membuat perhitungan pekan efektif. Pekan efektif adalah hari efektif
pelaksanaan pembelajaran setelah dikurangi pekan MOS, libur awal puasa dan hari raya, pelaksanaan UTS, libur semester dan libur hari besar.
Panduan pembuatan pekan efektif adalah kalender akademik Depdiknas. Berikut disajikan contoh perhitungan pekan efektif .


PERHITUNGAN ALOKASI WAKTU
Nama Sekolah      :                                                     Kelas/Semester    : XII  Bahasa / 1
Mata Pelajaran     : Matematika                                   Tahun Pelajaran    : 2009 – 2010

 catatan: pebuatan pekan efektif harus dengan panduan kalender akademik

1.       Banyaknya Pekan

NO
BULAN
JUMLAH PEKAN
1.
2.
3.
4.
5.
6.
7.
Juli 2008
Agustus 2008
September 2008
Oktober 2008
November 2008
Desember 2008
Januari 2009
3 Pekan
4 Pekan
4 Pekan
5 Pekan
4 Pekan
5 Pekan
4 Pekan
Jumlah
29 Pekan

2.       Banyaknya Pekan Tidak Efektif

NO
Uraian
JUMLAH PEKAN
1.
2.
3.
4.
5.
MOS + MPS
Libur awal Puasa dan Idul Fitri
Kegiatan Tengah Semester
Libur Hari Besar Nasional
Libur Semester
2 Pekan
7 Pekan
1 Pekan
1 Pekan
1 Pekan
Jumlah
12 Pekan

3.       Banyaknya Pekan Efektif

NO
Uraian
JUMLAH PEKAN
1.
2.
Jumlah Pekan
Jumlah Pekan Tidak Efektif
28 Pekan
11 Pekan
Jumlah
17 Pekan

4.       Banyaknya Jam Pelajaran Efektif

NO
Uraian
JUMLAH PEKAN
1.
2.
Jumlah Pekan Efektif
Jumlah Jam / Minggu
17 Pekan
4 jam
Jumlah Jam Pelajaran Efektif
68 Jam

contoh cara menentukan KKM


CONTOH PENENTUAN
KRITERIA KETUNTASAN MINIMAL(KKM)
Nama Sekolah
Mata Pelajaran
Kelas
Semester
Tahun Pelajaran
:
:
:
:
:

Matematika
XII Bahasa
Ganjil
2010/2011


No.
Kompetensi Dasar / Indikator
SKBM

KRITERIA PENENTUAN
Rata-Rata

Kompleksitas
Daya Dukung
Intake


1.1.  Menyelesaikan sistem pertidak samaan linier
76
76
76
76


1.2.  Merancang model matematika dari masalah program linier dan penyelesaiannya
74
74
74
74


1.3.  Menyelesaikan model matematika dari masalah program linier dan penyelesaiannya
72
72
72
72



2.1Menggunakan sifat dan operasi matrik untuk menunjukkan bahwa suatu matrik adalah suatu invers dari matrik persegi lai
78
78
78
78






2.2  Menentukan determinan dan invers matrik berordo 2
76
76
76
76



2.3.  Menggunakan determinan dan invers dalam menyelesaikan sistem persaman linier dua variabel
74
74
74
74

contoh aplikasi teori graph-oleh M. Dhito .P Mhs ITB

Pemanfaatan Teori Graf untuk Menguraikan Permasalahan
dalam Pemodelan Persoalan Penjadwalan Kereta Api
Muhammad Dhito Prihardhanto - 13507118
Prodi Teknik Informatika, Sekolah Teknik Elektro dan Informatika (STEI)
Institut Teknologi Bandung, Jalan Ganeca 10 Bandung, email: muh_dhito@students.itb.ac.id
Abstract – Teori graf merupakan sebuah ilmu yang
terbukti dapat membantu menyelesaikan beberapa
permasalahan dalam berbagai disiplin ilmu maupun
permasalahan sosial dalam kehidupan sehari-hari.
Salah satu bidang yang banyak memanfaatkan teori
graf adalah dunia perkeretaapian. Dalam perkeretaapian
graf digunakan dalam merepresentasikan
jaringan perkeretaapian yang menghubungkan
berbagai kota di suatu negara, merepresentasikan
persilangan jalur rel kereta api, dan sebagaimana
yang akan diulas pada makalah ini, yaitu
dimanfaatkan untuk membantu menyelesaikan
permasalahan yang ada dalam penjadwalan kereta
api demi mendapatkan sebuah jadwal kereta api yang
optimum dan tepat. Namun, dalam makalah ini tidak
akan mengulas hingga ke terbentuknya jadwal kereta
api yang tepat, tetapi hanya ingin menunjukkan
bagaimana graf dapat menyelesaikan permasalahan
yang dihadapi dalam penyusunan jadwal kereta api
saja.
Kata Kunci: teori graf,penyusunan jadwal, kereta api
1. PENDAHULUAN
Dewasa ini aplikasi graf telah banyak digunakan oleh
manusia untuk merepresentasikan permasalahan yang
ada agar lebih mudah dipecahkan. Ilmuwan kimia
menggunakan graf dalam memodelkan molekul
senyawa karbon, orang teknik elektro menggunakan
graf dalam perancangan integrated circuit, serta
masalah kemacetan lalu lintas dapat diselesaikan
dengan memodelkan jalan raya dalam graf.
Ilmu terapan graf tersebut terus berkembang hingga
saat ini. Kini graf juga dapat digunakan untuk
optimisasi dalam masalah penjadwalan kereta api.
Persoalan itulah yang ingin diulas dalam makalah ini.
Para peneliti di Eropa, khususnya Jerman dan Italia,
dan dengan disponsori oleh perusahaan kereta api di
sana telah berusaha menemukan metode untuk
menentukan jadwal perjalanan kereta api-kereta api
dengan menggunakan teori graf dengan tetap
mengindahkan permasalahan yang ada di lapangan
seperti kapasitas jalur rel kereta api dan kendala yang
lainnya.
Kereta api tersebut harus memenuhi syarat, yaitu
memiliki jadwal perjalanan yang bersifat periodik,
sebagai contoh, Kereta Api Turangga yang memiliki
jadwal perjalanan Bandung-Surabaya setiap hari pukul
19.00. Selain itu, dalam permasalahan ini, atau yang
biasa disebut dengan the Train Timetabling Problem
(TTP), hanya berlaku untuk jaringan kereta api dengan
rel tunggal satu arah yang menghubungkan dua stasiun
besar, dengan sejumlah stasiun kecil di antara
keduanya. Di sinilah peran teori graf dalam
menguraikan permasalahan tersebut.
2. PEMODELAN TTP
Dalam pemodelan TTP ini waktu tempuh kereta api,
atau yang disebut waktu saja, bersifat diskrit dan
diekspresikan sebagai bilangan bulat (integer) dari 1
sampai q, di mana q merepresentasikan lamanya
waktu tempuh tiap periode dalam 1 hari itu.
Selanjutnya, didefinisikan pula waktu sesaat dan
selang waktu.
Diberikan S = {1,…,s} yang merepresentasikan
himpunan dari stasiun kereta api, yang memiliki
nomor sesuai dengan urutan stasiun tersebut sepanjang
jalur rel yang dilalui kereta api. Stasiun awal
dilambangkan dengan nomor 1 dan stasiun akhir
dilambangkan dengan s. Selanjutnya, diberikan T =
{1,…,t} yang melambangkan himpunan kereta api
yang akan melakukan perjalanan pada setiap periode
dari horizon waktu yang diberikan. Untuk setiap
kereta api j Î T, diberikan stasiun awal fj dan stasiun
akhir sebagai lj (lj > fj). Diberikan lagi Sj = { fj,…, lj} Í
S merupakan himpunan stasiun yang dilalui secara
berurutan oleh kereta api j.
Sebuah jadwal kereta api, untuk setiap j Î T, terdiri
atas waktu keberangkatan dari fj, waktu kedatangan di
lj, serta waktu keberangkatan dan kedatangan untuk
stasiun fj + 1,…, lj + 1. Waktu tempuh dari kereta api
j pada jadwal tersebut didefinisikan sebagai lamanya
waktu yang dilalui sejak keberangkatan j dari fj dan
kedatangan j di lj.
Dari pemodelan tadi akan didapatkan jadwal yang
ideal untuk setiap kereta api, tetapi masih
memungkinkan untuk dimodifikasi karena
menyesuaikan permasalahan yang ada di lapangan,
seperti terbatasnya kapasitas jalur rel. Dengan
demikian, akan dimungkinkan pula, sebuah kereta api
diperlambat perjalanannya atau menambah waktu
berhenti kereta api di stasiun agar sesuai dengan
jadwal ideal yang didapatkan tadi. Selain itu juga,
akan dimungkinkan pula sebuah kereta api harus
diubah waktu keberangkatannya atau bahkan
dibatalkan agar sesuai dengan jadwal ideal tadi. Solusi
akhir dari TTP ini akan dirujuk untuk dijadikan
sebagai jadwal perjalanan kereta api yang sebenarnya
yang akan diterapkan dalam kehidupan nyata.
Terkait dengan masalah kapasitas jalur rel kereta api
yang hanya bisa dilalui satu kereta api saja, maka ada
kemungkinan untuk terjadi susul-menyusul kereta api.
Tapi tentu saja itu terjadi hanya ketika kereta api
pertama sedang berhenti di stasiun saja. Akibatnya,
dimungkinkan sebuah kereta api untuk berhenti di
stasiun antara (walaupun dalam jadwal ideal kereta api
tidak seharusnya berhenti di stasiun tersebut) supaya
memberikan kesempatan bagi kereta api lain di
belakangnya untuk menyusulnya. Dalam kehidupan
nyata itu sangat sering terjadi. Seperti di Indonesia,
kereta api kelas ekonomi harus berhenti di stasiun agar
kereta api kelas eksekutif di belakangnya bisa
menyusul. Lagipula, untuk setiap stasiun i Î S,
terdapat batas bawah ai dan di pada selang waktu
antara dua kedatangan berturutan dan dua
keberangkatan berturutan.
Karena kecepatan kereta api diasumsikan konstan,
maka selang waktu antara dua kereta api yang berjalan
berturutan pada jalur rel yang menghubungkan stasiun
i dan i + 1 sedikitnya adalah nilai maksimum dari
{di,ai+1}. Hanya saja, yang perlu diperhatikan, terkait
dengan terbatasnya kapasitas rel kereta api ini,
sedangkan jadwal ini akan berulang setiap periode,
maka apabila kasus seperti itu selalu terjadi, mungkin
saja salah satu kereta api harus dibatalkan
penjadwalannya agar mendapatkan solusi yang
mungkin.
Persyaratan kondisi lain yang harus dipenuhi dalam
pemodelan TTP ini adalah kereta api j harus datang di
stasiun tidak lebih lama dari waktu yang diberikan dan
berangkat dari stasiun tidak lebih awal dari waktu
yang diberikan. Dengan demikian, kondisi ini akan
dapat membantu dalam menjamin ketepatan hubungan
antar kereta api lain yang juga sedang berjalan.
Dalam formulasi yang disusun, bertujuan untuk
mencari keuntungan (profit) yang sebesar-besarnya
dengan penjadwalan kereta api tersebut, yang akan
dijelaskan selanjutnya. Keuntungan yang didapatkan
dari tiap kereta api j bergantung kepada keuntungan
ideal (ideal profit) kereta api p
j, pada shift vj,
didefinisikan sebagai nilai mutlak dari selisih waktu
antara waktu keberangkatan dari stasiun fi pada jadwal
ideal dengan jadwal sebenarnya, dan stretch m
j,
didefinisikan sebagai nilai mutlak dari selisih waktu
antara waktu perjalanan pada kenyataan dan jadwal
ideal. Secara formal, keuntungan kereta api j dapat
dituliskan
pj - fj (vj) - gjmj, (1)
di mana f
j (.) adalah fungsi dari shift kereta api vj
(dengan f
j (0) = 0, nilai dari fungsi selalu naik
membesar), dan g
j adalah parameter bukan negatif.
Jadi, apabila keuntungan kereta api j yang dihasilkan
adalah negatif, maka akan lebih baik kereta api
tersebut tidak dijadwalkan.
Dalam jurnal-jurnal yang membahas TTP memang
mengangkat permasalahan yang berbeda-beda. Pada
makalah ini batasan yang diambil adalah waktu
bersifat diskrit dan jalur rel hanya satu arah. Untuk
alasan ini, ada sebuah pembuktian eksplisit NPhardness
untuk permasalahan yang diulas dalam
makalah ini. Pembuktian tersebut akan menunjukkan
bahwa bagaimanapun algoritma aproksimasi waktu
polinomial dengan kinerja terburuk tidak akan
berguna dalam TTP kecuali jika P=NP. Itu dapat
diturunkan dari NP-hard Max-Independent Set
Problem (MISP), yaitu diberikan graf tidak berarah
H = (N,E), di mana N adalah himpunan simpul, dan E
adalah himpunan sisi, sebut himpunan bagian S Í N
dengan kardinalitas maksimum sehingga (i,j) Ï E
untuk semua i,j Î S.
Proposisi 1. Untuk sembarang MISP dapat diubah
secara polinomial ke bentuk TTP sehingga ada
penyelesaian korespondensi satu-satu antara MISP dan
TTP, dan penyelesaian korespondensi memiliki nilai
yang sama.
Pembuktian. Diberikan H = (N,E) adalah graf MISP,
dengan E = {e1, e2,…,em}, di mana ei = (ji,ki) untuk I =
1,…,m. Kita definisikan TTP sebagai berikut. Setiap
kereta api berkorespondensi dengan sebuah simpul di
N. Kita akan menentukan apakah setiap kereta api
akan dijadwalkan sesuai dengan jadwal idealnya, atau
dibatalkan. Untuk j Î T, akan kita berikan pj = 1,
fj
(0) = 0, dan f
j(x) = 1 untuk x 0, dan gj = 1. Perlu
diperhatikan, karena waktu dinyatakan sebagai
bilangan bulat (integer), setiap jadwal yang tidak ideal
akan mempunyai shift atau stretch kurang dari 1
menit, dan akibatnya keuntungan akan menjadi
negatif. Jumlah stasiun adalah m + 1 dan kita berikan
fj = 1, lj = m+1 untuk setiap kereta j Î T. Selain itu,
selang waktu minimum ai dan di antara kedatangan
dan keberangkatan dari setiap stasiun diubah menjadi
1.
Jadwal ideal akan didefinisikan sehingga jadwal ideal
dari dua kereta api j dan k tidak kompatibel (yaitu dua
kereta api tidak dapat memiliki jadwal yang sama) jika
dan hanya jika (j,k) Î E. Untuk setiap sisi ei Î E,
dalam jadwal ideal, kereta api ji dan ki berangkat pada
saat yang sama dari stasiun i dan tiba pada saat
bersamaan di stasiun i+1. Tentu saja ini tidak mungkin
terjadi dalam kehidupan nyata karena hanya terdapat
satu jalur rel kereta api.
Untuk lebih tepatnya, ambil sisi pertama dari graf H
adalah e1 = (j1,k1). Supaya jadwal kereta api j1 dan k1
tadi menjadi kompatibel, ubah waktu keberangkatan j1
dan k1 menjadi j1 dari stasiun 1, sedangkan untuk
setiap kereta j j1, waktu keberangkatan k1 dari
stasiun diubah menjadi j; Semua kereta api datang di
stasiun 2 setelah keberangkatan mereka dari stasiun 1.
Dengan cara yang serupa, dua kereta api yang tidak
kompatibel dengan sisi e2 = (j2,k2) dimodelkan dengan
mengubah waktu keberangkatan kereta api j2 dan k2
dari stasiun 2 menjadi t+1+j2, sedangkan untuk semua
kereta api j yang lain waktu keberangkatan dari
stasiun 2 diubah menjadi t+1+j; Sebagaimana
sebelumnya, semua kereta api tiba di stasiun 3 satu
menit setelah keberangkatan mereka dari stasiun 2.
Dengan langkah yang sama seperti di atas, akan
diselesaikan permasalahan untuk stasiun 3,4,…m dan
untuk pasangan kereta api (j3,k3), (j4,k4),…, (jm,km).
Lebih tepat lagi, untuk i = 1,…,m diberikan waktu
keberangkatan dari stasiun i sama dengan (i-1)(t+1)+ji
untuk kereta api ji dan ki dan sama dengan (i-1)(t+1)+j
untuk j ji, ki, dan kedatangan di stasiun i+1 selalu
satu menit setelah keberangkatan semua kereta dari
stasiun i. Langkah-langkah di atas ini akan
menghasilkan sebuah TTP sesuai dengan yang
diharapkan.
Gambar 1: Transformasi dari MISP menjadi TTP, H =(N,E)
dengan N = {1,2,3,4} dan E = {(1,2),(1,3),(,4),(2,3),(3,4)}.
Jumlah stasiun adalah 6.
3. PEMODELAN GRAF
Selanjutnya, terdapat sebuah ilustrasi permasalahan
matematik yang disebut keuntungan maksimum
(maximum-profit) dari himpunan lintasan pada sebuah
graf ganda (multigraph). Diberikan G = (V,A) adalah
graf-ganda asiklik berarah yang didefinisikan sebagai
berikut (lihat gambar 2 sebagai ilustrasi). Himpunan
simpul V memiliki bentuk {s,t } È (U2 È È Us) È
(W1 È È Ws-1), di mana s dan t adalah simpul asal
buatan (artificial source node) dan simpul terminal
buatan (artificial terminal node), sedangkan himpunan
Ui, i Î S \ {1}, dan Wi, I Î S \ {s}, merepresentasikan
himpunan waktu di mana kereta api dapat datang dan
berangkat dari stasiun i. Simpul-simpul dalam U2 È
È Us dan W1 È È Ws-1 disebut simpul
kedatangan (arrival node) dan simpul keberangkatan
(departure node).
Diberikan q(v) adalah waktu yang diasosiasikan
dengan simpul v Î V. Selain itu, juga diberikan D(u,v)
= q(v) - q(u) jika q(v) ³ q(u), dan D(u,v) = q(v) - q(u)
+ q jika q(v) < q(u). Karena horizon waktu bersifat
siklik, kita katakan bahwa simpul u mendahului
simpul v jika D(v,u) ³ D(u,v) (yaitu jika selang waktu
siklik antara q(v) dan q(u) lebih kecil dari pada selang
waktu siklik antara q(u) dan q(v)).
Gambar 2: Contoh lintasan kereta api-kereta api dalam graf G (dengan s = 4, t = 3, f1 = 2, l1 = 4, f2 = 1, l2 = 4, f3 = 1, l3 = 3).
Sementara itu, himpunan sisi A dipartisi menjadi
himpunan A1,…,At, setiap himpunan bagian tersebut
adalah untuk setiap kereta api j Î T. Untuk setiap
kereta api j Î T, Aj memiliki:
_ Sebuah himpunan sisi permulaan (starting
arc) berbentuk (s,v), untuk setiap v Î W fj
berkorespondensi ke keberangkatan kereta
api j dari stasiun fj.
_ Sebuah himpunan sisi stasiun (station arc)
berbentuk (u, v), untuk setiap u Î Ui dan v Î
Wi sehingga i Î Sj \ { fj, lj}, dan D(u,v) adalah
setara dengan waktu pemberhentian
minimum kereta api j di stasiun i (yaitu
waktu pemberhentian di stasiun i dalam
jadwal ideal).
_ Sebuah himpunan sisi bagian berbentuk (v,u),
untuk setiap v Î Wi dan u Î Ui+1 sehingga i
Î Sj \ {lj}, dan D(v,u) adalah setara dengan
waktu perjalanan minimum kereta api j dari
stasiun i ke stasiun i+1 (yaitu waktu
perjalanan dalam jadwal ideal).
_ Sebuah himpunan sisi akhir berbentuk (u,t),
untuk setiap u Î Ulj berkorespondensi ke
kedatangan kereta api j di stasiun lj.
Dari konstruksi tersebut, graf G adalah asiklik dan
setiap lintasan Pj dari s menuju t dalam graf G yang
hanya menggunakan sisi-sisi dalam Aj
berkorespondensi ke jadwal yang mungkin untuk
kereta api j (lihat gambar 2). Dengan kata lain semua
kemungkinan kendala yang akan dihadapai kereta api
secara implicit telah termasuk dalam struktur graf G.
Untuk setiap kereta api j kita asosiasikan dengan
keuntungan (profit) pa dengan setiap sisi a Î Aj,
didefinisikan sebagai berikut. Untuk setiap sisi
permulaan (starting arc) berbentuk (s,v), v Î W fj,
diberikan n(v) adalah shift yang diasosiasikan dengan
simpul v, yaitu,
n(v) = |q(v) – [waktu keberangkatan ideal kereta api j
dari stasiun fj]|
Keuntungan sisi (s,v) adalah sama dengan p(s,v) = pj -
fj
(n(v)). Sedangkan keuntungan setiap sisi stasiun
(u,v), u Î Ui, v Î Wi, i Î Sj \ { fj, lj}, adalah p(u,v) = -
gjm(u,v), di mana m(u,v) adalah stretch yang
diasosiasikan dengan sisi (u,v), yaitu,
m(u,v) = D(u,v) – [waktu pemberhentian ideal kereta
api j di stasiun i].
Dengan analogi yang sama, keuntungan setiap sisi
bagian (v,u), v Î Wi , u Î Ui+1, i Î Sj \ {lj},
didefinisikan sebagai p(v,u) = -gjm(v,u), di mana m(v,u)
adalah stretch yang diasosiakan dengan sisi (v,u),
yaitu,
m(v,u) = D(v,u) – [waktu perjalanan ideal kereta api j
dari stasiun I ke stasiun i+1].
Sedangkan keuntungan sisi akhir (u,t), u Î Ulj, adalah
sama dengan nol.
Keuntungan keseluruhan dalam penjadwalan kereta
api didapatkan dari penjumlahan keuntungan sisi-sisi
pada lintasan graf G yang berkorespondensi kepada
kereta api yang dijadwalkan.
Gambar 3: Pasangan sisi yang tidak kompatibel
Dari, gambar 2 di atas terdapat beberapa pasangan
sisi, diasosiasikan dengan dua kereta api yang
berbeda, yang tidak memenuhi kendala kapasitas jalur
kereta api, sehingga tidak dapat dimasukkan ke dalam
solusi keseluruhan. Adalah cukup untuk menyatakan
bahwa untuksetiap pasangan sisi kereta api j, k dan
untuk setiap stasiun i Î (Sj \ {lj}) Ç (Sk \ {lk}), dua
sisi bagian (v1, u1) Î Aj dan (v2, u2) Î Ak, v1, v2 Î Wi,
u1, u2 Î Ui+1, tidak dapat diambil karena sedikitnya
memenuhi satu kondisi di bawah ini:
_ Selang waktu antara waktu sesaat yang
diasosiasikan dengan v1 dan v2 adalah lebih
kecil daripada di (yaitu D(v1,v2) < di), lihat
gambar 3(a).
_ Selang waktu antara waktu sesaat yang
diasosiasikan dengan u1 dan u2 adalah lebih
kecil daripada ai+1 (yaitu D(u1,u2) < ai+1), lihat
gambar 3(b).
_ Dua sisi saling bersilang satu sama lain, lihat
gambar 3(c).
Pasangan sisi seperti yang digambarkan pada gambar
3 itu disebut tidak kompatibel, sedangkan pasangan
sisi lainnya yang tidak digambarkan dalam gambar 3
itu berarti kompatibel.
Selanjutnya, semua permasalahan di atas yang telah
diuraikan, akan diselesaikan dengan berbagai model
alternatif. Keterbatasan kapasitas jalur rel kereta api
yang menjadi problem di atas dapat dimodelkan
dengan menggunakan variabel yang diasosiasikan
dengan simpul graf G ataupun sisi-sisi graf G.
Pemodelan itu dikenal dengan Lagrangian relaxation.
Selanjutnya kita akan mengenal apa yang disebut
dengan Lagrangian profit yang diasosiasikan dengan
simpul graf G. Cara itu lebih baik daripada dengan
menggunakan sisi-sisi graf G sebagai asosiasi dengan
Lagrangian profit. Lalu, di samping dengan metode
Lagrangian tadi, juga digunakan metode heuristik
untuk menghitung solusi heuristik dengan meranking
kereta api berdasarkan nilai Lagrangian profitnya.
Kemudian, melakukan penjadwalan kereta api satu
persatu. Akhirnya, diperolehlah jadwal kereta api yang
ideal. Di Eropa sendiri, contoh negara yang telah
menerapkan ini adalah Italia.
4. KESIMPULAN
Dari ulasan di atas, telah ditunjukkan bahwasannya
teori graf ternyata sangat berguna dalam membantu
menguraikan permasalahan yang ada di dunia
perkeretaapian, khususnya dalam masalah
penjadwalan kereta api untuk mendapatkan
penjadwalan yang tepat dan ideal. Permasalahan yang
ada di dalam penjadwalan kereta api seperti terjadinya
susul-menyusul kereta api, keterbatasan kapasitas rel
kereta api, dan banyaknya stasiun yang dilalui dapat
dimodelkan dengan graf, baik dengan cara
menentukan stasiun sebagai simpul, kereta api sebagai
simpul, lintasan kereta api sebagai sisi, dan
sebagainya. sehingga permasalahan dapat lebih mudah
diselesaikan, meskipun terdapat berbagai asumsi yang
berlaku dalam kasus TTP ini.
DAFTAR REFERENSI
[1] A. Caprara, M. Fischetti, P. Toth, “Modelling and
Solving the train Timetabling Problem”,
Operations Research 50(5), Bologna University,
Padova University, Italia, 2002.
[2] B. Erol, M. Klemenz, T. Schlechte, Soren
Schultz, A. Tanner. “TTPlib 2008 – A Library for
Train Timetabling Problems”, ZIB-Report 08-19,
Germany, 2008.
[3] Rinaldi Munir, Matematika Diskrit, Penerbit
Informatika,2005.
[4] Wikipedia, Graph Theory <http://en.wikipedia.
org/wiki/Graph_theory>, diakses tanggal 4
Januari 2008 pukul 10.43