BAB 2 LANDASAN TEORI
2.1
Pemodelan Dalam melakukan analisis terhadap suatu kasus nyata, pemodelan seringkali
diperlukan untuk membantu memecahkan kasus nyata itu. Starr dan Miller menyatakan, model adalah representasi dari suatu realita yang dipergunakan untuk menjelaskan, menggambarkan perilaku beberapa aspeknya. Jadi model merupakan penghampiran dart suatu sistem nyata yang biasanya sulit untuk dianalisis secara langsung. Pembuatan model diperlukan karena dapat digunakan untuk mendekati permasalahan yang kompleks itu, membuat abstraksi suatu realita sehingga lebih mudah dipahami dan dimengerti. Model tentu saja lebih sederhana namun demikian tetap mampu mewakili sistem nyata yang ada. Pendekatan dilakukan melalui analisis kepentingan modelnya. Model hanya memuat bagian-bagian tertentu yang penting saja yang merupakan sosok kunci sistem, model tidak akan menceritakan kenyataan yang ada secara detail. Ada beberapa tahap yang harus dilalui dalam pemodelan yaitu : 1. Tahap Identifikasi dan Perumusan Masalah Sebelum membentuk model untuk menyelesaikan suatu masalah maka masalahnya itu sendiri harus sudah jelas, masalahnya harus sudah ditemukan dan dapat dirumuskan dengan teliti. Kecuali itu, dalam tahap ini juga perlu diketahui tujuan pemodelannya; melakukan identifikasi terhadap konstanta, parameter, variabel yang terkait sehingga dapat ditentukan mana yang sangat berpengaruh terhadap sistem dan mana yang sebaliknya. 2. Tahap Penyusunan Model Dalam tahap ini ada beberapa hal yang harus dilakukan, yaitu : -
Menyatakan hubungan antar variabel berdasarkan prinsip-prinsip yang telah diketahui, data yang dikumpulkan secara khusus, intuisi dan refleksi. Bila diperlukan maka batasi dengan asumsi dan lakukan prediksi.
-
Menyusun model dengan memadukan semua hubungan ke dalam suatu sistem hubungan simbolik. Kemudian lakukan manipulasi simbolik.
6
3. Tahap Validasi dan Verifikasi Model Pada tahap ini kita menemukan pemecahan bagi model. Kemudian dilakukan pengujian terhadap model yang telah dibentuk tadi dengan menggunakan keadaan dan data nyata. Lakukan pengecekan apakah model yang ada cukup valid karena hasil yang didapatkan cocok dengan sistem nyatanya. Jika ternyata bahwa model tidak benar maka harus kembali ke langkah sebelumnya (penyusunan model) untuk melakukan perubahan dan perbaikan. 4. Tahap Implementasi Hasil Tahap ini adalah melakukan implementasi lebih lanjut terhadap hasil yang telah dicapai sehingga dapat dipergunakan untuk membantu dalam pengambilan keputusan. Tahap-tahap pemodelan di atas dapat digambarkan dalam bentuk diagram alir seperti terlihat pada gambar 2.1. Model matematik yang sering digunakan dalam membahas suatu metodologi programa matematis mempunyai struktur tertentu. Struktur model matematik itu meliputi bagian-bagian sebagai berikut : 1. Fungsi Tujuan Model, yaitu suatu fungsi yang digunakan sebagai indikator bagi pencapaian tujuan. Umumnya, fungsi tujuan menghendaki hasil yang optimal (maksimasi/minimasi) dari penyelesaian masalah yang dilingkupinya
7
Idantifikasi dan perumusan Masalah
Penyusunan Model
Perubahan dan Perbaikan Valid ?
Tidak
Ya Implementasi Hasil
Gambar 2.1 : Diagram Pemodelan 2. Variabel Keputusan Model, yaitu suatu faktor yang selalu berubah nilainya sesuai dengan status sistemnya. Faktor ini sangat menentukan dalam merealisasikan fungsi tujuan. Penentuan nilai yang tepat bagi variabel keputusan akan memberikan hasil yang optimal bagi sistem. Variabel keputusan adalah karakteristik utama bagi sistemnya. 3. Parameter Model, yaitu suatu besaran tetap yang dikaitkan dengan model, artinya parameter hanya tetap nilainya untuk keadaan tertentu raja dan akan berubah bila kondisi itu juga berubah. 4. Konstanta Model, yaitu suatu besaran tetap yang dikaitkan dengan sistem nyata, artinya konstanta akan selalu tetap nilainya walaupun terjadi perubahanperubahan tertentu. 5. Fungsi Pembatas Model, yaitu kondisi yang membatasi usaha pencapaian tujuan. Fungsi pembatas timbul karena ada keterbatasan-keterbatasan dalam sistem
8
nyata, memperkuat kenyataan bahwa suatu sistem nyata bukanlah sistem ideal seperti yang sering dibayangkan. Suatu model dapat dikatakan baik bila memenuhi kriteria-kriteria berikut : 1. Kesesuaian dan kesederhanaan, yaitu model harus dapat merangkum unsur-unsur yang ada dalam sistem nyatanya, model cukup merangkum unsur-unsur yang pokok sesuai persoalan yang dihadapi. 2. Derajat generalisasi yang tinggi, yaitu semakin umum sifat suatu model maka akan semakin baik model itu. 3. Jelas mekanismenya sehingga mudah dipelajari, dipecahkan dan dilihat ulang. 4. Potensial untuk dikembangkan lebih lanjut. Suatu model tidak boleh statis, harus bisa dikembangkan sesuai perubahan yang terjadi. 5. Mempunyai kepekaan terhadap perubahan asumsi. Asumsi diberikan untuk mempermudah
pembentukan
model,
namun
pada
akhirnya
seringkali
dikehendaki pemberian asumsi yang lebih longgar agar makin mendekati sistem nyatanya, akibatnya model juga harus berubah supaya dapat menggambarkan keadaan yang baru itu. Pemodelan memang diperlukan terhadap sistem nyata yang rumit dan kompleks. Namun karena sifatnya yang ingin mendekati sistem nyata itulah maka model yang terbentuk juga harus terus dikendalikan dan disesuaikan sejalan dengan perubahan dan perkembangan sistem nyatanya itu. Hal ini perlu karena akan dapat mengurangi penyimpangan-penyimpangan yang timbul.
2.2
Peramalan Dalam menghadapi ketidakpastian masa depan perlu dilakukan persiapan-
persiapan untuk menyongsongnya. Salah satu cara untuk persiapan itu adalah dengan membuat perkiraan-perkiraan tentang masa depan tadi sehingga tampak jelas arah persiapan yang diperlukan. Membuat perkiraan tentang masa depan memerlukan bantuan dari alat/metode tertentu, misalnya metode-metode peramalan.
9
2.2.1
Gambaran dan Peranan Peramalan Sering terdapat senjang waktu (time lag) antara kesadaran akan peristiwa atau
kebutuhan mendatang dengan peristiwa itu sendiri. Adanya waktu tenggang (lead time) ini merupakan alasan utama bagi perencanaan dan peramalan. Peramalan merupakan alat bantu yang penting dalam perencanaan yang efektif dan efisien. Peramalan merupakan bagian integral dari kegiatan pengambilan keputusan. Organisasi selalu menentukan sasaran dan tujuan, berusaha menduga faktor-faktor lingkungan, lalu, memilih tindakan yang diharapkan akan menghasilkan sasaran dan tujuan itu. Kebutuhan akan peramalan meningkat sejalan dengan usaha manajemen untuk mengurangi ketergantungannya pada hal-hal yang belum pasti. Peramalan menjadi lebih ilmiah sifatnya dalam menghadapi lingkungan manajemen. Ada beberapa langkah yang perlu diperhatikan berkenaan dengan peramalan, yaitu: identifikasi dan defenisi masalah peramalan, aplikasi serangkaian metode peramalan, pemilihan metode yang tepat untuk suatu situasi, tertentu, dan dukungan bagi penerapan dan penggunaan metode peramalan secara formal. Dengan tersedianya sejumlah metode peramalan maka timbul persoalan bagaimana memahami karakteristik dari suatu metode peramalan sehingga cocok dengan situasi pengambilan keputusan yang dihadapi. Pemilihan metode peramalan harus mempertimbangkan situasi peramalannya. Situasi peramalan sangat beragam tergantung dari rentang waktu peramalan, faktor-faktor yang menentukan hasil sebenarnya, pola data yang dimiliki dan berbagai aspek lainnya. Karena ada banyak metode peramalan, maka dilakukan pengelompokkan dalam dua bagian besar yaitu metode kuantitatif dan metode kualitatif atau teknologis. Metode kuantitatif meliputi deret berkala (time series) & metode kausal (eksplanatoris), sedang metode kualitatif dibagi dalam metode eksploratoris & metode normatif. Peramalan kuantitatif dapat diterapkan bila terdapat kondisi berikut : 1. Tersedia informasi tentang masa lalu. 2. Informasi tersebut dapat dikuantifikasikan dalam bentuk data numerik. 3. Dapat diasumsikan bahwa beberapa aspek pola masa lalu akan terus berlanjut di masa mendatang.
10
Suatu dimensi tambahan untuk mengklasifikasikan metode peramalan kuantitatif adalah dengan memperhatikan model yang mendasarinya. Terdapat dua model peramalan yang utama yaitu model deret berkala dan model regresi (kausal). Model deret berkala menduga masa depan berdasarkan nilai masa lalu dari suatu variabel. Metode peramalan deret berkala ini mencoba menemukan pola dalam deret data historis dan mengekstrapolasikan pola tersebut ke masa depan. Lain halnya dengan model kausal, model ini mengasumsikan bahwa faktor yang diramalkan menunjukkan suatu hubungan sebab akibat dengan satu atau lebih variabel bebas. Maksud dari model kausal ini adalah menemukan bentuk hubungan tersebut dan menggunakannya untuk meramalkan nilai mendatang dari variabel tak bebas. Bila data yang diperlukan tersedia, suatu hubungan peramalan dapat dihipotesiskan baik sebagai fungsi dari waktu atau sebagai fungsi dari variabel bebas, kemudian diuji. Metode peramalan kualitatif, di lain pihak, tidak memerlukan data yang serupa dengan metode peramalan kuantitatif. Masukan yang diperlukan tergantung pada metode tertentu dan biasanya merupakan hasil dari pemikiran intuitif, perkiraan dan pengetahuan yang telah didapat. Metode kualitatif dibagi dua, yaitu metode eksploratoris dan metode normatif. Metode eksploratoris (seperti Delphi, kurva-S, analogi, dan penelitian morfologis) dimulai dengan masa lalu dan masa kini sebagai titik awalnya dan bergerak ke arah masa depan secara heuristik, seringkali dengan melihat semua kemungkinan yang ada. Metode normatif (seperti matriks keputusan, pohon relevansi., analisis sistem) dimulai dengan menetapkan sasaran dan tujuan yang akan datang, kemudian bekerja mundur untuk melihat apakah hal ini dapat dicapai atau tidak berdasarkan kendala, sumberdaya yang tersedia. Dalam perencanaan selalu melibatkan peramalan. Karenanya peramalan juga perlu mendapatkan perhatian yang memadai. Sejauh mana ketepatan, ruang lingkup, horizon waktu, dan biaya yang diinginkan sangat menentukan pilihan metode peramalan. Keterpaduan peramalan dengan perencanaan dan pengambilan keputusan kiranya perlu terus dipertahankan.
11
2.2.2
Regresi Sederhana (Simple Regression) Dalam metode eksplanatoris dicoba untuk mengajukan variabel lain yang
berkaitan dengan rangkaian data dan mengembangkan suatu model yang menyatakan adanya saling ketergantungan fungsional diantara semua variabel itu. Untuk model regresi sederhana hanya terdapat satu variabel bebas dan satu variabet tak bebas. Model regresi berganda memiliki beberapa variabel bebas dengan satu variabet tak bebas, sedangkan model-model ekonometrik mempunyai beberapa variabel bebas dengan beberapa variabel tak bebas. Dalam model regresi sederhana ini, tiap pengamatan menghasilkan pasangan data X dan Y (X variabel bebas dan Y variabel tak bebas). Model ini berusaha menemukan kesesuaian terbaik bagi suatu garis lurus melalui titik-titik yang menggambarkan pasangan data X dan Y tadi.
2.2.2.1 Persamaan Regresi Sederhana Persamaan regresi didapat melalui jumlah dari kuadrat setiap kemiringan deviasi D2 terhadap titik dari setiap n data.
D 2 ≡ ∑ [ y i − f ( xi , a1 , a 2 ,..., a n )]
2
Agar D2 mencapai minimum, maka syarat yang harus dipenuhi adalah: ∂( D 2 ) =0 ∂ai
Misalnya f(a, b) adalah fungsi pendekatan persamaan garis dengan i = 1,2,3...n untuk kondisi linear, maka: f (a, b) = bxi + a Jadi n
D 2 (a, b) ≡ ∑ [ y i − (a + bxi )]
2
i =1
n ∂( D 2 ) = −2∑ [ y i − (a + bxi )] = 0 ∂a i =1
n ∂( D 2 ) = −2∑ [ y i − (a + bxi ) xi ] = 0 ∂b i =1
12
Ini menuju ke persamaan n
n
i =1
i =1
na + b∑ xi = ∑ y i n
n
i =1
i =1
n
a ∑ x i + b ∑ x = ∑ xi y i 2 i
i =1
dalam bentuk matriks ⎤ ⎤ ⎡ n x yi ⎥ ∑ ∑ i ⎥ ⎢ ⎡a ⎤ i =1 ⎥ ⎥ ⎢ ⎥ = ⎢ ni =1 n 2 ⎥ ⎣b ⎦ ⎢ xi xi yi ⎥ ∑ ∑ ⎥⎦ ⎥ ⎢ i =1 ⎦ ⎣ i =1
⎡ ⎢ n ⎢ n ⎢ x i ⎢⎣∑ i =1
n
jadi ⎡ n a ⎡ ⎤ ⎢ ⎢b ⎥ = ⎢ n ⎣ ⎦ ⎢ x i ⎢⎣∑ i =1
⎤ xi ⎥ ∑ i =1 ⎥ n 2⎥ x ∑ i ⎥⎦ i =1 n
−1
⎤ ⎡ n ⎢ ∑ yi ⎥ ⎥ ⎢ ni =1 ⎢ xy⎥ i i ⎥⎦ ⎢⎣∑ i =1
invers matriksnya adalah n n n ⎤ ⎡ n 2 y x x xi y i ⎥ − ∑ ∑ ∑ ∑ i i i ⎢ ⎡a ⎤ 1 i =1 i =1 ⎥ ⎢ i =1 n i =1 n n ⎢b ⎥ = n 2 n ⎥ ⎢ ⎣ ⎦ ⎛ ⎞ n∑ xi2 − ⎜ ∑ xi ⎟ ⎢ n∑ xi y i − ∑ xi ∑ y i ⎥ i =1 i =1 i =1 ⎦ i =1 ⎝ i =1 ⎠ ⎣
jadi hasilnya
a=
n
n
i =1
i =1
n
n
∑ y i ∑ xi − ∑ xi ∑ xi y i 2
i =1
i =1 2
⎛ ⎞ 2 n∑ xi − ⎜ ∑ xi ⎟ i =1 ⎝ i =1 ⎠ n
n
n ⎛ n 2⎞ y ⎜ ∑ xi ⎟ − x ∑ xi y i i =1 = ⎝ i =1 n ⎠ 2 ∑ x i − nx 2 i =1
n
b=
n
n
n∑ xi y i − ∑ xi ∑ y i i =1
i =1
i =1
⎛ ⎞ n∑ xi − ⎜ ∑ xi ⎟ i =1 ⎝ i =1 ⎠ n
2
n
2
13
⎛ n ⎞ ⎜ ∑ x i y i ⎟ − nx y ⎠ = ⎝ i =n1 2 ∑ x i − nx 2 i =1
Jika kita nyatakan Y sebagai variabel tak bebas dan X sebagai variabel bebas maka penggunaan model regresi sederhana dimaksudkan untuk menemukan persamaan garis lurus: Ŷ = a + bX
(II-1)
sedemikian rupa sehingga untuk setiap nilai X tertentu, kesalahan kuadrat : (Y – Ŷ)2 = e2
(II-2)
jika dijumlahkan akan menghasilkan total minimum. Kesalahan dinyatakan sebagai panjang garis vertical dari titik tertentu ke garis (a + bX). Setelah nilai pengamatan Y dimodelkan dalam bentuk suatu pola, maka : Y = a + bX + e
(II-3)
Y=Ŷ+e
(II-4)
dengan Ŷ adalah penduga atau penaksir Y. Dalam mendapatkan pemecahan kuadrat terkecil untuk persamaan (II-4), rumusrumus dari regresi sederhana adalah sebagai berikut: -
Penentuan koefisien kemiringan (slope), b : b=
-
n∑ XY − (∑ X )(∑ Y ) n∑ X 2 − (∑ X )
2
=
Cov xy Varx
(II-5)
Penentuan koefisien intersepsi, a : a=
∑Y − b ∑ X n
n
(II-6)
dengan n adalah jumlah pengamatan.
2.2.2.2 Koefisien Kolerasi
Untuk mengetahui apakah antara variabel-variabel yang ada itu benar memiliki hubungan, digunakan hasil perhitungan korelasi antara dua variabel. Koefisien korelasi (r) adalah suatu ukuran asosiasi (linear) relative antara dua variabel. Nilai r adalah -1 ≤ r ≤ 1. Jika r = 0 atau mendekati nol, maka hubungan antara kedua variabel sangat lemah
14
atau tidak terdapat hubungan sama sekali. Bila r = 1 atau mendekati positif satu, maka korelasi antara dua variabel dikatakan positif dan sangat kuat. Dan nilai r = -1 atau mendekati negatif satu mempunyai arti bahwa korelasi antara dua variabel tadi sangat kuat tetapi negatif. Tanda (+) dan (-) pada koefisien korelasi memiliki arti yang khas. Bila harga r positif maka korelasi antara dua variabel itu bersifat searah, artinya kenaikan/penurunan nilai-nilai X terjadi bersama-sama dengan kenaikan/penurunan nilai-nilai Y. Sebaliknya, jika r berharga negative maka kenaikan nilai-nilai X terjadi bersama-sama dengan penurunan nilai-nilai Y, atau kebalikannya yaitu penurunan nilai X akan terjadi bersama-sama dengan kenaikan nilai Y. Perhitungan koefisien korelasi antara dua variabel dan Y yang dinotasikan dengan rxy untuk n pasangan observasi (Xi ,Yi) dengan i = 1,2,3,...,n adalah : Nilai rata-rata X = X =
1 n ∑ Xi n i =1
(II-7)
Nilai rata-rata Y = Y =
1 n ∑ Yi n i =1
(II-8)
Kovarians antara X dan Y adalah :
Cov xy =
1 n ∑ (X i − X )(Yi − Y ) n i =1
(II-9)
Varians X = Cov xx = Varx =
1 n (X i − X )2 = S x2 ∑ n i =1
(II-10)
Varians Y = Cov yy = Vary =
1 n (Yi − Y )2 = S y2 ∑ n i =1
(II-11)
Kolerasi antara X dan Y adalah :
rxy =
Cov xy Cov xx Cov yy
=b
Varx Vary
=
Cov xy
(II-12)
SxSy
dengan S x = Cov xx dan S y = Cov yy adalah deviasi standart X dan Y. Atau menggunakan rumus berikut : rxy =
n∑ XY − (∑ X )(∑ Y )
n∑ X 2 − (∑ X )
2
n∑ Y 2 − (∑ Y )
2
(II-12a)
15
2.2.2.3 Koefisien Determinasi
Koefisien determinasi (R2) adalah korelasi kuadrat antara variabel tak bebas Y dengan nilai taksirannya Ŷ. Koefisien determinasi akan selalu positif. Secara intuitif dapat dikatakan bahwa R2 menyatakan proporsi varians pada Y yang dapat diterangkan oleh X. Variabel tak bebas Y mempunyai sejumlah variabelitas tertentu, yang didefinisikan sebagai variansnya. Nilai-nilai taksiran Ŷ juga mempunyai sejumlah varians tertentu. Rasio kedua varians tersebut adalah R2 :
R2 =
var iansnilai − nilaiYˆ var iansnilai − nilaiY
∑ (Yˆ − Y ) = ∑ (Y − Y )
2
i
2
= ry2yˆ
(II-13)
i
Pada kasus regresi sederhana, deviasi total (Yi − Y ) dapat dijelaskan sebagai berikut (lihat gambar 2.2) :
(Y
i
−Y
) = (Y
i
) (
− Yˆi + Yˆi − Y
Y
)
(II-14)
Yi *
(Y
i
(Y − Yˆ )
−Y )
i
*
i
Yˆ = a + bX
(Yˆ − Y ) i
Y
X Gambar 2.2 : Pemecahan Deviasi Total pada Regresi Sederhana
16
2.2.2.4 Uji-F Untuk Signifikansi Menyeluruh
Uji-F dapat dipergunakan untuk menguji signifikasi model regresi linear atau untuk menjawab pertanyaan secara statistik: Apakah terdapat hubungan yang signifikan antara X dan Y ? Dalam uji-F ini kita membandingkan nilai F dari tabel (Ftabel) dengan nilai F dari hasil perhitungan (Ftest). Nilai Ftest diperoleh dari perhitungan :
Ftest
(
) ⎞⎟⎠
(
) ⎞⎟⎠
⎛⎜ Yˆ − Y ⎝∑ (k − 1) = ⎛⎜ Y − Yˆ ⎝∑ (n − k )
2
2
(II-15) dimana,
k : jumlah parameter (koefisien) pada persamaan regresi. n : jumlah pengamatan (observasi).
Nilai F juga dapat dihitung dari koefisien determinasi, yaitu :
Ftest
R2 (k − 1) = 1− R2 (n − k )
(
) (II-16)
Dalam menentukan nilai Ftabel dengan α (kesalahan duga atau erorr of estimate) tertentu dari tabel yang tersedia, perlu ditentukan derajad kebebasan untuk koreksi dari pembilang dan penyebutnya. Di sini, derajad kebebasan pembilang (df1) adalah (k-1), sedangkan derajad kebebasan pembilang (df2) adalah (n-k). Penentuan signifikansi hubungan antara Y dan X dilakukan dengan membandingkan nilai Ftest dan Ftabel. Jika nilai Ftabel < Ftest mala hubungan linier dari kedua variabel itu sangat signifikan.
2.2.3
Regresi Berganda (Multiple Regression)
Model regresi berganda digunakan untuk menggambarkan hubungan variabel tak bebas Y dengan dua atau lebih variabel bebas X1, X2, X3,...,Xn.
17
2.2.3.1 Persamaan Regresi Berganda
Program komputer umumnya digunakan untuk menemukan bilai koefisienkoefisien dari suatu model regresi berganda. Namun demikian, pengetahuan tentang apa yang ada dibalik semua itu juga diperlukan. Berikut ini adalah bentuk pragmatis dari model regresi berganda. Y = b0 + b1 X 1 + b2 X 2 + ... + bk X k + e (II – 17) dan untuk setiap pengamatan ke-i maka: Yi = b0 + b1X1i + b2X2i + ... + bkXki + ei (II – 18) atau: Yi = Ŷi + ei (II – 19) dengan komponen kesalahannya adalah: ei = Yi + Ŷi (II – 20) dan metode kuadrat terkecil (least sqaure) digunakan untuk mendapatkan jumlah kuadrat minimum dari bagian kesalahan tersebut, yaitu n
Minimumkan φ = ∑ ei2 i =1
n
(
= ∑ Yi − Yˆi i =1
)
2
n
= ∑ (Yi − b0 − b1 X 1i − ... − bk X ki )
2
(II – 21)
i =1
Jika persamaan regresi umum dinyatakan dalam bentuk matriks berikut ini: Y = Xb + e (II – 22) dengan, Y adalah matriks n x 1 X adalah matriks n x k b adalah matriks k x 1
18
e adalah matriks n x 1
maka untuk memperoleh nilai b, minimumkan jumlah kuadrat deviasi:
∑e
2 i
′ = e′e = (Y − Xb ) (Y − Xb ) (II – 23)
′ dengan e′ = (Y − Xb ) adalah transpose e. Dengan demikian, e′e = (Y ′ − b ′X ′)(Y − Xb ) = Y ′Y − Y ′Xb − b ′X ′Y + b ′X ′Xb = Y ′Y − 2b ′X ′Y + b ′X ′Xb
ini terjadi karena b ′X ′Y adalah suatu saklar dan oleh karenanya sama dengan transposenya (Y ′Xb ) . Untuk mendapatkan nilai e′e yang minimum maka diturunkan (diferensiasi) terhadap b’ dan turunanya disamakan dengan nol.
∂e′e = −2 X ′Y + 2 X ′Xb = 0 ∂b′ (II – 24) X ′Y = X ′Xb
(II – 25) dan, b = ( X ′X ) X ′Y −1
(II – 26) dengan ( X ′X ) adalah invers (kebalikan) dari X ′X . −1
2.2.3.2 Korelasi Berganda dan Koefisien Determinasi
Korelasi antara Y dan Ŷ dapat dihitung dengan persamaan (II – 12a). Kuadrat korelasi ini disebut koefisien determinasi ( RY2Yˆ ) . R sendiri disebut koefsien korelasi
berganda yang merupakan korelasi antara variabel tak bebas Y dengan taksiran Ŷ berdasarkan variabel-variabel bebas berganda, dan sering ditulis dengan RYX1 X 2 ... X k Dalam menghitung R2, sama seperti pada regresi sederhana, digunakan persamaan (II-13). Namun jika ingin memperhitungkan pengaruh derajad kebebasan, maka nilai R2 terkoreksi menjadi:
19
R 2 = 1 − (1 − R 2 )
(dftotal )
(dfkesalahan ) (n − 1) = 1 − (1 − R 2 ) (n − k − 1) (II – 27)
2.2.3.3 Uji –F Untuk Signifikan Menyeluruh
Sama seperti pada regresi sederhana. Nilai F dari persamaan (II – 15) dan (II -16) hanya berubah derajad kebebasanya saja. Derajad kebebasan pembilang menjadi k, sedangkan derajad penyebutnya menjadi n − (k + 1) . Oleh karena itu persamaan (II-15) berubah menjadi:
(
)
(
)
⎛⎜ Yˆ − Y 2 ⎞⎟ ⎝∑ ⎠ k F= ⎛⎜ Y − Yˆ 2 ⎞⎟ ⎝∑ ⎠ n − k −1
(II – 28) sedangkan persamaan (II – 16) menjadi: R2 k F= 1− R2 (n − k − 1)
(
)
(II – 29 )
2.2.3.4 Pengujian Kesalahan Nilai Sisa (Residuals Error)
Penelaahan nilai sisa sangat penting untuk memutuskan kecocokan model peramalan yang diberikan. Jika kesalahan secara esensial bersifat random maka model tersebut mungkin baik. Jika kesalahan menunjukkan suatu pola tertentu berarti model tersebut tidak memperhatikan semua informasi sistematis yang ada pada himpunan data. Cara analisis kesalahan yang sering digunakan adalah menghitung statsistik DurbinWatson. Statistik Durbin-Watson dihitung dengan:
20
n
D −W =
∑ (e t =2
t
− et −1 )
n
∑e t −1
2
2 t
(II-30) Nilai statistik Durbin-Watson berkisar dari nol sampai empat dengan suatu nilai pertengahan sebesar dua. Nilai terbaik bagi statistik Durbin-Watson adalah yang mendekati dua karena berarti bahwa kesalahan bersifat random/acak atau dengan kata lain model peramalan yang digunakan baik (tidak terdapat autokorelasi nilai sisa). Grafik distribusi Durbin-Watson dapat dilihat pada gambar 2.3.
Tidak ada autokolerasi
Tidak diketahui Auto kolerasi
Tidak diketahui Auto kolerasi
D-WL D-WU Gambar 2.3: Grafik Distribusi Durbin-Watson
2.3
Program Linear
Masalah pemrograman secara umum dapat dijelaskan sebagai masalah pengalokasian sumber daya yang terbatas dengan cara sebaik mungkin sehingga diperoleh keuntungan yang maksimum atau ongkos yang minimum. Dalam pemrograman itu, keputusan diambil dengan memilih dari beberapa alternatif yang ada. Cara pengambilan keputusan yang demikian merupakan persoalan optimasi, yaitu suatu persoalan yang ingin mendapatkan hasil maksimum atau minimum dengan memperhatikan semua kendala yang ada. 21
Program Linear adalah salah satu bentuk pemrogram yang dapat digunakan untuk memcahkan masalah optimasi itu, sehingga program linear mempunyai dua bentuk persoalan yaitu bentuk maksimasi dan bentuk minimasi. Sifat-sifat yang dimiliki program linear adalah fungsi-fungsi yang menyatakan tujuan dan pembatasanya semua bentuk fungsi linear. Fungsi-fungsi itu harus dipenuhi oleh jawaban-jawaban yang diperoleh. Pembatas-pembatas ini dapat berbentuk persamaan atau ketidaksamaan linear dengan variabel-variabel yang non-negatif. Program linear adalah persoalan pemrograman yang memenuhi syarat-syarat linearitas. Syarat-syarat itu adalah (phillips, hal.13): 1. Variabel keputusan yang digunakan tidak negatif (harus positif atau nol). 2. Kriteria pemilihan nilai terbaik dari variabel keputusan ditentukan oleh suatu fungsi linear dari variabel keputusan itu. Fungsi yang menggambarkan kriteria ini disebut fungsi tujuan (objective function) 3. Aturan operasi yang mengatur proses (langkahnya sumber daya dan sumber dana) dapat digambarkan sebagai satu set persamaan atau ketidasamaan linear. Set ini disebut kendala (constraint). Prosedur pemecahan masalah pemrogram linear bersifat interatif, sehingga akan menguntungkan jika digunakan bantuan komputer karena komputer dapat melakukan dengan cepat tanpa banyak kesalahan.
2.3.1
Batasan Umum Program Linear
Program Linear dapat berbentuk persoalan maksimasi atau minimasi. Kendalakendalanya dapat berupa ketidaksamaan (≤, ≥) atau persamaan, dan variabelnya nonnegatif. Secara umum, model program linear dapat digambarkan sebagai berikut: Bila terdapat m buah persamaan dan atau ketidaksamaan linear yang di dalamnya memuat n buah variabel dan selanjutnya ingin dicari nilai dari variabel-variabel itu yang memenuhi kondisi-kondisi seperti yang dinyatakan oleh fungsi tujuan dan kendalanya, maka secara matematis persoalan itu dapat dirumuskan sebagai berikut: n
Maksimasi/Minimasi : Z = ∑ C j X j j =1
( II – 31)
22
dengan memperhatikan kendala: n
∑A j =1
ij
X j (≥, =, ≤ )Bi
( II – 32) Xj ≥0
( II - 33) untuk itu: i = 1,2,3, ...,m j = 1,2,3, ...,m Cj, Aij, Bi, adalah konstanta yang nilainya ditentukan oleh teknologi permasalahan. Xj ialah variabel keputusan. Masalah pemrograman linear adalah masalah alokasi sehingga perumusan di atas secara fisik dapat diinterpretasikan sebagai berikut: Bj : jumlah sumber daya atau dana ke-i yang tersedia. Aij : jumlah sumber daya atau dana ke-i yang dialokasikan pada kegiatan ke-j. Cj : nilai dari kegiatan ke-j. Harga-harga Xj yang memenuhi persamaan (II – 33) disebut jawaban (solution), sedangkan bila memenuhi persamaan (II – 32) dan (II – 33) dinamakan jawaban fisibel (feasibel solution). Apabila Jawaban fisibel ini memenuhi kondisi optimal yang
disyaratkan permasaan (II – 31) maka jawaban fisibel itu disebut sebagai jawaban fisibel optimal (optimal feasibel solution).
23
Kendala (constrain) :
n
∑ A X (≥, =, ≤ )B j =1
ij
j
i
Fungsi tujuan (objective function)
Jawaban fisibel optimal
Daerah Feasible
Gambar 2.4 : Grafik Program Linear
2.3.2
Penyajian Persoalan Program Linear
Persoalan program linear dapat digambarkan dalam berbagai bentuk, misalnya maksimaksi, minimaksi dengan kendala lebih besar, sama, atau lebih kecil. Untuk memecahkan persoalan itu diperlukan suatu bentuk baku tertentu. Ada dua bentuk yang biasa digunakan untuk menyajikan persoalan program linear, yaitu bentuk standar dan bentuk kanonik. 1 Bentuk Kanonik Bentuk ini memiliki karakteristik sebagai berikut: a. semua variabel keputusannya adalah non-negatif. b. semua fungsi pembatas yang ada berjenis ketidaksamaan lebih kecil sama dengan (≤ ) . c. Fungsi tujuannya berjenis maksimasi. Secara matematis dapat dinyatakan sebagai berikut: n
Maksimasi : Z = ∑ C j X j j =1
24
dengan memperhatikan pembatas: n
∑ j =1
Aij X j ≤ Bi
Xj ≥0
untuk: i = 1,2,3, ...,m j = 1,2,3, ...,n 2
Bentuk standar Bentuk ini memiliki karakteristik sebagai berikut: a. semua kendalanya berbentuk persamaan, kecuali kendala yang non-negatif. b. Elemen ruas kanan tiap kendala adalah non-negatif c. Semua variabel adalah non-negatif. d. Fungsi tujuannya dapat berbentuk maksimasi maupun minimasi. Secara matematis dapat dinyatakan sebagai berikut: Maksimasi/minimasi: n
Z = ∑C j X j j =1
Dengan memperhatikan kendala: n
∑ j =1
Aij X j = B j
X j,Bj ≥ 0
untuk: i = 1,2,3, ...,m j = 1,2,3, ...,n jika dalam persoalan ini kendalanya berupa ketidaksamaan maka ketidaksamaan itu dapat dirubah menjadi persamaan dengan menambahkan/mengurangkan variabel slack pada ruas kiri. Variabel slack ini juga non-negatif. Jika bentuk ketidaksamaannya < maka variabel slack ditambahkan pada ruas kiri, jika ketidaksamaannya > maka variabel slack harus dikurangi pada ruas kiri.
25
2.3.3
Pemecahan Persoalan Program Linear
Menyelesaikan persoalan program linear selalu dikaitkan dengan mencari solusi optimal bagi persoalan yang sama, yaitu solusi terbaik yang dapat dicapai dalam lingkup batasan/kendala yang ada. Beberapa metode dapat digunakan untuk menyelesaikan pemrograman linear. Misalnya solusi grafis dan metode simpleks. Solusi grafis akan efektif jika persoalannya memiliki variabel yang sedikit. Untuk persoalan dengan jumlah variabel banyak biasa diselesaikan dengan metode simpleks. Metode Simpleks adalah suatu metode yang secara sistematis dimulai dengan suatu pemecahan dasar yang fisibel ke pemecahan dasar yang fisibel lainnya, ini dilakukan berulang-ulang dengan jumlah pengulangan terbatas hingga akhirnya ditemukan hasil terbaiknya (maksimasi keuntungan atau minimasi ongkos). Jadi, mencari solusi yang optimal bagi pemrogram linear, metode simpleks memerlukan dua kondisi yaitu kondisi fisibelitas dan kondisi optimalitas.
2.4
Teorema Dualitas
Teorema ini merupakan salah satu konsep program linear yang ide dasarnya adalah bahwa setiap program linear mempunyai suatu pemrograman linear yang berkaitan disebut dual, sedemikian hingga solusi pada dualnya. Jika dibandingkan, maka ada hubungan antara primal dan dual, yaitu: 1. Koefisien fungsi tujuan pada primal menjadi konstanta ruas kanan pada dual. Sebaliknya, konstanta ruas kanan pada primal menjadi koefisien fungsi tujuan pada dual. 2. Tanda ketidaksamaan pada pembatas menjadi terbalik, jika pada primal ≤ berubah menjadi ≥ pada dual. 3. Fungsi tujuan berubah bentuk, maksimasi pada primal akan berubah menjadi minimasi pada dual. 4. Setiap kolom kendala pada primal berhubungan dengan baris kendala pada dual. Sebaliknya, setiap baris kendala pada primal akan menjadi kolom kendala pada dual. 5. Dual dari dual adalah primal.
26
2.4.1
Bentuk Umum Persoalan Primal-Dual
Secara matematis, rumusan persoalan primal dan dual adalah sebagai berikut: 1. Bentuk Kanonik Primal Maksimasi : n
Z = ∑C j X j j =1
dengan memperhatikan: m
∑A i =1
X j ≤ Bi
ij
Yi ≥ 0
Bentuk primal tersebut dapat dinyatakan dalam bentuk dual berikut: Minimasi : m
V = ∑ Bi Yi i =1
Dengan memperhatikan: m
∑A Y ij
i =1
i
≥ Cj
Yi ≥ 0
Untuk, i = 1,2,3, ...,m j = 1,2,3, ...,n 2. Bentuk Standar Primal, Maksimasi/Minimasi : n
Z = ∑C j X j j =1
dengan memperhatikan: n
∑A j =1
ij
X j = Bi
Xj ≥0
Bentuk primal tersebut dapat dinyatakan dalam bentuk dual berikut: 27
m
Minimasi/Maksimasi : V = ∑ Bi Yi i =1
dengan memperhatikan : m
∑ A Y (≥, atau ≤ )C i =1
ij i
j
Yi tidak bertanda (unrestricted in sign) 2.4.2
Beberapa Teorema Dualitas
Ada beberapa teorema dualitas yang perlu diperhatikan karena hubungan yang sangat penting antara solusi dual dengan solusi primal. Teori-teori itu adalah: 1. Teorema Dualitas Lemah (Weak Duality Theorem) Harga fungsi tujuan dari masalah maksimasi (primal) untuk setiap solusi fisibel selalu lebih kecil atau sama dengan harga fungsi tujuan dari masalah minimasi (dual). Bukti: Misalkan X ο dan Yο adalah vektor solusi fisibel bagi primal dan dual, maka harus dibuktikan bahwa: CX ο ≤ Yο B
Karena X ο fisibel bagi primal maka: AX ο ≤ B Xο ≥ 0
(II – 34) Karena Yο fisibel bagi dual maka: Yο A ≥ C Yο ≥ 0
(II – 35) Jika ketidaksamaan (II – 34) dikalikan dengan Yο , maka: Yο AX ο ≤ Yο B
(II – 36)
28
Jika ketidaksamaan (II – 35) dikalikan dengan X ο , maka: Yο AX ο ≥ CX ο
(II – 37) Eliminasi ketidaksamaan (II – 36) dan (II – 37) menghasilkan: CX ο ≤ Yο AX ο ≤ Yο B
atau: CX ο ≤ Yο B
dari Teorema Dualitas lemah ini, dapat dikemukakan beberapa kesimpulan, yaitu: a. Harga fungsi tujuan primal maksimasi untuk setiap solusi fisibel primal adalah batas bawah bagi harga fungsi tujuan dual minimasi. Sebaliknya, harga fungsi tujuan dual minimasi untuk setiap solusi fisibel dual adalah batas atas bagi harga fungsi tujuan primal maksimasi.
b. Jika masalah primal fisibel dan harga fungsi tujuannya tak terbatas maka masalah dualnya menjadi tidak fisibel. Sebaliknya, jika masalah dual fisibel dan harga fungsi tujuannya tak terbatas maka masalah primalnya menjadi tidak fisibel. c. Bila masalah primal fisibel dan dualnya tidak fisibel maka solusi primal tidak terbatas. Sebaliknya, bila masalah dual fisibel dan primalnya tidak fisibel maka solusi dual tidak terbatas. 2. Teori Kriteria Optimalitas (Optimality Criterion Theorem) Jika solusi fisibel primal X ο dan dual Yο memberikan harga fungsi tujuan primal dan dual yang sama, maka solusi fisibel tadi pada kenyataannya adalah solusi optimal bagi primal dan dual itu. Bukti: Misalnya X adalah solusi fisibel yang lain bagi primal, maka menurut Teori Dualitas Lemah berlaku demikian: CX ≤ Yο B
Karena CX ο = Yο B maka juga CX < CX ο . Dan menurut definisi X ο adalah solusi optimal primal, demikan pula dengan Yο untuk dual. 29
3. Teorema Dualitas Utama (Main Duality Theorem) Bila masalah primal dan dual semuanya fisibel, maka keduanya mempunyai solusi optimal sedemikian hingga nilai optimal dari fungsi tujuan itu keduanya sama. Bukti: Untuk masalah primal dan dual yang fisibel, berdasarkan kesimpulan dari Theorema Dualitas lahan maka ada solusi optimal (maksimum) primal yang menjadi batas bawah bagi dual, dan solusi optimal (minimum) dual yang menjadi batas atas bagi primal. Ini berarti bahwa solusi maksimum primal juga menjadi solusi minimum dual, atau dengan kata lain solusi optimal bagi primal dan dual itu sama. 4. Teori Kelonggaran Komplimenter (Complementary Slackness Theorem) Jika X ο dan Yο adalah solusi bagi primal dan dual, maka X ο dan Yο optimal bagi primal dan dual jika dan hanya jika:
(Yο A − C )X ο + Yο (B − AX ο ) = 0 Yο AX ο − CX ο + Yο B − Yο AX ο = 0 Yο B − CX ο = 0
Bukti: Misalkan U adalah vektor kolom yang terdiri dari variabel slack bagi persoalan primal, dan V adalah vektor baris yang merupakan vektor slack bagi dual. Karena X ο dan Yο adalah solusi fisibel, maka: AX ο + U ο = B ;
X ο ,U ο ≥ 0
(II – 38) Yο A − Vο = C ;
Yο ,Vο ≥ 0
(II – 39) dengan U ο dan Vο adalah harga vektor U dan V pada saat X ο dan Yο fisibel. Jika ( II – 38) dikalikan dengan Yο , maka: Yο AX ο + Yο U ο = Yο B
(II – 40)
30
Jika ( II – 39) dikalikan dengan X ο , maka: Yο AX ο − Vο X ο = CX ο
(II – 41) Setelah ( II – 41) dikurangkan pada ( II – 40), maka diperoleh: Yο U ο + Vο X ο = Yο B − CX ο
(II – 42) Untuk membuktikan Teorema Kelonggaran Komplimenter diatas maka harus: Yο U ο + Vο X ο = 0
(II – 43) Bagian I: Diasumsikan X ο dan Yο adalah solusi optimal bagi primal dan dual, maka kita harus membuktikan bahwa persamaan (II -43) adalah benar. Buktinya demikian, karena X ο dan Yο optimal maka menurut Teorema Dualitas Utama, CX ο = Yο B dan karenanya Yο B − CX ο = 0 atau Yο U ο + Vο X ο = 0 .
Bagian II: Diasumsikan persamaan (II – 43) benar dan kita harus membuktikan bahwa X ο dan Yο adalah solusi optimal bagi primal dan dual. Buktinya demikian,
jika persamaan (II – 43) benar maka Yο B = CX ο , dan karenanya menurut Teorema Kriteria Optimalitas X ο dan Yο adalah solusi Optimal bagi primal dan dual.
2.4.3
Kondisi Kelonggaran Komplimenter (Complimentary Slackness Condition)
Persamaan ( II – 43) dapat disederhanakan menjadi: Vοj X οj = 0 , dengan j = 1,2,3, ...,n
( II – 44) YοjU οj = 0 , dengan i = 1,2,3, ...,m
( II – 45) Hal diatas dapat dilakukan karena: 31
1. X ο ,U ο ,Vο , Yο ≥ 0 sehingga Vο X ο ≥ 0 dan Yο U ο ≥ 0 2. Bila jumlah semua variabel non-negatif diatas adalah nol maka tiap variabel juga akan nol. Persamaan (II – 44) dan (II – 45) disebut kondisi atau syarat kelonggaran komplimenter. Dengan lebih jelas, syarat kelonggaran komplimenter dinyatakan sebagai
berikut: 1. Bila variabel primal X οj positif, maka kendala dual yang berhubungan dengan variabel primal tersebut akan dipenuhi sebagai suatu persamaan pada saat optimum dicapai yaitu Vοj = 0 . 2. Bila kendala primal berbentuk ketidaksamaan pada saat optimum dicapai yaitu U οi > 0 , maka variabel dual Yοi yang berhubungan dengan kendala primal
tersebut harus nol pada saat optimum dicapai. 3. Bila variabel dual Yοi positif, maka kendala primal yang berhubungan dengan variabel dual tersebuat akan dipenuhi sebagai suatu persamaan pada saat optimum dicapai yaitu U οi = 0 . 4. Bila kendala dual berbentuk ketidaksamaan pada saat optimum dicapai yaitu Vοj > 0 , maka variabel primal X οj yang berhubungan dengan kendala dual
tersebut harus sama dengan nol pada saat optimum dicapai. Pemakaian dari kondisi kelonggaran komplimenter secara umum adalah: 1. Menentukan solusi optimal primal dari solusi optimal dual tertentu, dan sebaliknya. 2. Memeriksa apakah solusi fisibel, optimal bagi persoalan primal. Misalnya, untuk memeriksa apakah kendala primal merupakan ketidaksamaan pada titik optimamnya, atau dengan kata lain, apakah semua sumberdaya yang tersedia digunakan seluruhnya atau tidak. 3. Memeriksa sifat solusi optimal bagi primal dan dual.
2.5 Persoalan Transportasi
Model persoalan transportasi merupakan salah satu bentuk model program linear yang khusus dikembangan untuk menangani masalah-masalah yang berkaitan dengan 32
pengangkutan atau distribusi sejumlah komoditi dari berbagai titik sumber ke beberapa titik tujuan. Yang dimaksud titik sumber adalah lokasi yang mensuplai komoditi itu misalnya pabrik, kilang minyak, gudang, atau depot. Kriteria yang biasa digunakan sebagai ukuran untuk memecahkan persoalannya adalah ongkos angkut, jarak angkut, atau waktu angkut. Beberapa asumsi dasar yang melandasi model persoalan transportasi adalah sebagai berikut: 1. Jumlah komoditi yang tersedia dan lokasinya diketahui. 2. Jumlah komoditi yang diminta dan lokasi permintaannya diketahu. 3. Terdapat beberapa sumber dan tujuan. Komoditi akan dikirimkan melalui jaringan transportasi yang ada dan memakai moda angkutan yang tersedia dari titik-titik sumber ke titik-titik tujuan. 4. Besarnya ongkos pengangkutan per unit komoditi yang diangkut dari titik sumber ke titik tujuan diketahui sehingga tujuan akhir untuk meminimumkan total ongkos transportasi dapat dilakukan.
2.5.1
Formulasi Model
Jika dimisalkan terdapat m buah sumber dan n buah tujuan. Dan dalam hubungan antara sumber dengan tujuan itu terdapat perumusan-perumusan sebagai berikut: C ij : ongkos angkutan tiap unit komoditi dari sumber ke-i menuju tujuan ke-j. X ij : jumlah komoditi yang dialokasikan/dipindahkan dari sumber ke-i menuju
tujuan ke-j. Ai : jumlah komoditi yang dapat dialokasikan dari sumber ke-i (i = 1,2,3, ...,m) Bj : jumlah komoditi yang diperlukan oleh tujuan ke-j (j = 1,2,3, ...,n) Maka persoalan diatas dapat digambarkan sebagai berikut (lihat gambar 2.5):
33
Sumber
C1 1 ; X1 1
Tujuan
A1
1
1
B1
A2
2
2
B2
. . .
. . .
m
n
Am
Bn
Cm n ; X m n Gambar 2.5: Modal Jaringan Transportasi dengan m Sumber dan n Tujuan
Secara sistematis model bagi persoalan transportasi dapat dinyatakan sebagai berikut: m
Minimasi : Z = ∑ i =1
n
∑C j =1
ij
X ij
dengan memperhatikan: n
∑X j =1
ij
= Ai
ij
= Bj
m
∑X i =1
X ij ≥ 0 , bagi semua i dan j
untuk, i = 1,2,3, ..., m j = 1,2,3, ...,n Keadaan diatas adalah model persoalan transportasi dengan jumlah suplai sama dengan jumlah permintaan (balanced transportation model), dinyatakan: m
n
i =1
i =1
∑ Ai = ∑ B j Dalam keadaan jumlah suplai tidak sama dengan jumlah permintaan maka model transportasi menjadi:
34
m
Minimasi : Z = ∑ i =1
n
∑C j =1
ij
X ij
dengan memperhatikan : n
∑X j =1
ij
≤ Ai
ij
≥ Bj
m
∑X i =1
X ij ≥ 0
yang berarti bahwa jumlah komoditi yang dialokasikan ke pusat permintaan tidak melampaui kemampuan sumbernya, dan jumlah komoditi yang diminta oleh pusat permintaan tidak melebihi jumlah komoditi yang dialokasikan dari sumbernya. Persoalan transportasi juga dapat disajikan dalam bentuk tabel seperti diperlihatkan pada tabel 2.1. Tujuan ke-j 1
S
X 11
e
C12
...
C in
A1
X in
C 21 X 21
Persediaan
n
...
X 12
2
b
...
C11
1
u m
2
Jumlah
C 22
C 2n
...
A2
X 2n
X 22
...
...
...
...
...
r ke-i
C mi
M X mi
Cm2
C mn
...
X m2
Am
X mn m
Jumlah Permintaan
B1
B2
...
Bn
n
∑A = ∑B i =1
i
j =1
j
Tabel 2.1: Tabel Persoalan Transportasi
35
Dalam persoalan transportasi yang disajikan di atas, jumlah permintaan harus sama dengan jumlah suplai, bila tidak sama maka harus ditambahkan sumber/tujuan semu.
2.5.2
Pemecahan Persoalan Transportasi
Perhitungan untuk menyelesaikan persoalan transportasi dapat dilakukan dengan bantuan beberapa metode, antara lain adalah: 1. Metode Simpleks Metode Simpleks dapat digunakan untuk menyelesaikan persoalan transportasi karena dapat disajikan dalam bentuk persoalan program linear. Dalam menyelesaikan persoalan program linear dengan metode simpleks, pemecahan dimulai dengan suatu solusi fisibel basis ke solusi fisibel basis lainnya. Proses pengulangan (interatif) ini diteruskan dilakukan sampai suatu jumlah terbatas, yang disetiap langkahnya sampai suatu jumlah terbatas, yang disetiap langkahnya nilai fungsi tujuan makin mendekati nilai optimalitasnya dipenuhi. Langkah-langkah yangdiperlukan dalam penggunaan metode Simpleks adalah sebagai berikut (metode Simpleks dalam bentuk tabel): Langkah 1: Memformulasikan Masalah a. Membuat fungsi tujuan dan kendala bagi persoalan yang bersangkutan. b. Semua
kendala
diubah
ke
dalam
bentuk
persamaan,
dengan
menambahkan/mengurangkan variabel slack. c. Memodifikasi fungsi tujuan dengan mengikutsertakan variabel slack sesuai koefisieannya. Langkah 2: Menemukan Solusi Fisibel Awal Membuat solusi fisibel awal, hanya variabel slack yang termasuk dalam variabel basis. Langkah 3: Uji Optimalitas Hitung harga C j − Z j (koefisisen ongkos relatif) untuk tiap kolom. Untuk persoalan maksimasi, kondisi optimal dicapai jika semua koefisien ongkos relatifnya bernilai nol atau negatif. Sedangkan untuk persoalan
36
minimasi, semua koefisien ongkos relatif harus bernilai nol atau positif untuk mencapai solusi optimal. Memperbaiki solusi fisibel (bila solusi belum optimal). Langkah-langkah yang diperlukan untuk membuat solusi fisibel baru adalah: 1. Menentukan Kolom Kunci Kolom kunci bagi persoalan maksimasi adalah kolom yang
memiliki koefisien ongkos relatif terbesar.Bagi persoalan minimasi, kolom kuncinya adalah kolom yang memiliki koefisien ongkos relatif negatif terbesar. Variabel yang ada di kolom kunci ini kemudian menjadi variabel basis baru menggantikan variabel basis lama yang keluar. 2. Bilangan-bilangan yang ada pada kolom ruas kanan dibagi dengan bilangan-bilangan yang ada pada kolom kunci, hasil bagi ini disebut rasio. Baris dengan nilai rasio terkecil disebut baris kunci. Variabel yang ada pada baris kunci keluar dari
keanggotaan sebagai variabel basisi yang selanjutnya menjadi variabel non-basis. Bilangan yang terletak pada perpotongan antara baris kunci dan kolom kunci disebut bilangan kunci. Kemudian semua bilangan yang ada di baris kunci dibagi dengan bilangan kunci ini. 3. Merubah Baris non-kunci (Operasi pivat) Untuk setiap baris non-kunci dapat diganti dengan cara mengurangi bilangan pada baris yang lama dengan hasil kali bilangan-bilangan pada baris kunci yang lama dengan rasio kunci. Rasio kunci adalah hasil bagi bilangan pada baris yang
lama di dalam kolom kunci dengan bilangan kunci. 4. Isikan hasil-hasil di atas ke dalam tabel baru sebagai perbaikan solusi fisibel. Langkah 4: Mencari Solusi Optimal Lakukan pengulangan langkah 3 di atas sampai solusi optimal tercapai (kondisi optimalitas dipenuhi)
37
2. Metode Pendekatan Vogel Metode pendekatan Vogel umumnya hanya memberikan solusi fisibel bagi persoalan yang dihadapinya. Pencarian solusi optimal lebih lanjut dilakukan dengan menggunakan metode lain, misalnya metode Stepping-stone. Langkah-langkah dalam menggunakan metode pendekatan Vogel adalah sebagai berikut: Langkah 1: Mencari harga penalty dari setiap baris/kolom dengan cara mengurangkan elemen ongkos terkecil kedua dari baris/kolom yang sama. Langkah 2: Pilih baris/kolom yang memiliki harga penalty terbesar. Bila ada lebih dari satu baris/kolom yang sama-sama memiliki harga penalty terbesar, maka pilih salah satu. Langkah 3 : Alokasi komoditi sebanyak-banyaknya pada alternatif yang memiliki ongkos terkecil dalam baris/kolom terpilih sampai syarat-syarat kapasitas yang ditetapkan dapat terpenuhi. Langkah 4 : Hapus baris/kolom yang persediaan atau permintaannya sudah terpenuhi secara bersamaan, maka hanya salah satu saja yang dihapus, sedangkan baris/kolom yang lainnya itu ditetapkan sebagai sumber/tujuan kosong. Sumber/tujuan ini selanjutnya tidak diikut sertakan lagi dalam perhitungan harga penalty. Langkah 5 : Ulangi langkah 1 sampai 4 hingga seluruh baris dan kolom terhapus. Jika seluruhnya telah selesai maka semua komoditi juga telah dialokasikan dari sumber ke tujuan yang ada. Dalam hal ini diasumsikan bahwa sejumlah suplai sama dengan jumlah permintaan, atau bila tidak harus dibuat sumber/tujuan semua. Langkah 6 : Hitung total ongkos angkut dengan menggunakan hasil perhitungan alokasi di atas. 3. Algoritma Out of Kilter Algoritma
Out
of
Kilter
merupakan
metode
yang
digunakan
untuk
menyelesaikan persoalan jaringan yang memiliki kapasitas terbatas pada setiap busurnya (capacitated network). Persoalan transportasi dapat disajikan dalam bentuk jaringan sehingga persoalan transportasi juga dapat diselesaikan dengan Algoritma Out of Kilter.
38
Pembahasan lebih lanjut dari Algoritma Out of Kilter ini akan dilakukan sendiri dalam sub bab 2.7
2.6 Analisis Jaringan (Network Analysis)
Dalam menyelesaikan persoalan-persoalan ekonomi transportasi, model analisis jaringan (network analisis) sering digunakan. Model-model analisis jaringan digunakan untuk memecahkan kasus-kasus nyata itu. Kesederhanaan konsep yang dimiliki oleh model analisis jaringan menjadikannya mudah untuk dipahami dan diterapkan. Analisis jaringan bukanlah suatu teori terintegrasi yang rumit. Analisis jaringan bukanlah suatu teori terintegrasi yang rumit. Analisis jaringan hanya merupakan pengembangan ide-ide yang bervariasi, yang bertujuan memecahkan masalah nyata itu. Dalam memecahkan kasus nyata tadi, analisis jaringan mampu memberikan solusi dari berbagai pendekatan. Sebagai contoh adalah kasus pengiriman produk, cara pemecahan bagi masalah ini dapat didekati dari berbagai tujuan, misalnya dari tujuan ingin memaksimumkan jumlah produk yang diangkut, meminimumkan waktu angkut yang diperlukan, meminimumkan ongkos angkutnya, atau yang lainnya. Analisis jaringan dapat memberikan solusi-solusi itu sesuai yang diharapkan dari pembuatan penyelesaian masalah.
2.6.1
Gambaran Umum dan Notasi Jaringan
Sebuah jaringan biasanya dimodelkan dalam batasan grafis. Dalam grafik itu jaringan merupakan kumpulan dari simpul (node) dan busur (arc). Simpul merupakan pertemuan busur-busur. Contoh nyata yang dapat merepresentasikan simpul adalah terminal, pusat pembagian aliran listrik, atau kantor pos pengolah surat. Busur menggambarkan aliran yang terjadi antar simpul, ada hubungan ketergantungan yang spesifik antara simpul-simpul itu. Contoh bagi busur ini adalah rute pesawat, jalan raya, pipa air minum, dll. Jaringan digunakan untuk menggambarkan proses fisik (aliran) berupa pemindahan komoditi dari satu simpul ke simpul lainnya. Simpul yang menyediakan komoditi disebut simpul sumber, sedangkan simpul yang memerlukan komoditi itu disebut simpul tujuan. Dalam batasan garfis, sebuah jaringan dapat dinyatakan dalam notasi G = (N,A). N merupakan kumpulan simpul N1, N2, N3, ..., Nn. A menyatakan kumpulan busur yang
39
menghubungkan simpul i dengan simpul j. Suatu busur dinyatakan dengan (i, j) untuk i tidak sama j. Busur (i, j) adalah busur yang menghubungkan simpul ke-i dengan simpul ke-j. Jumlah aliran yang melewati suatu busur seringkali dibatasi, dalam keadaan demikian busur tadi dinyatakan berkapasitas. Ongkos pengiriman pada suatu busur biasanya diberi simbol C ij . Ongkos di sini dapat mewakili ongkos pengiriman yang sebenarnya, waktu kirim, jarak tempuh, atau yang lainnya. Bagi suatu busur yang menghubungkan dua buah simpul, biasanya busur itu digambarkan dengan arah tertentu. Busur dengan arah tertentu demikian disebut busur berarah. Sebaliknya, busur yang tidak memiliki arah tertentu dinamakan busur tidak berarah. Busur tidak berarah dapat dianggap sebagai dua buah busur berarah.
Dalam menentukan status suatu simpul, apakah simpul itu merupakan simpul sumber atau simpul tujuan atau yang lainnya maka perlu dilakukan perhitungan terhadap jumlah komoditi yang keluar masuk simpul itu. Bila Bi menyatakan selisis antara jumlah komoditi yang meninggalkan simpul dengan jumlah komoditi yang memasuki simpul sama, maka suatu simpul dengan Bi > 0 adalah suatu simpul sumber. Simpul dengan harga Bi > 0 merupakan simpul tujuan, dan simpul dengan Bi = 0 disebut sebagai simpul peralihan
. Dalam penerapannya untuk suatu algoritma diasumsikan bahwa jaringan mengandung satu simpul sumber dan satu simpul tujuan. Dengan demikian, jaringan dapat dibentuk dengan membuat simpul super sumber (super source node) dan simpul super tujuan (super sink node), dan kemudian menghubungkan simpul-simpul sumber itu ke super sumber serta menghubungkan simpul-simpul tujuan ke simpul super tujuan dengan busur-busur semu (lihat gambar 2.6) Dalam analisis jaringan ada beberapa istilah yang biasa digunakan, yaitu (lihat gambar 2.6):
40
2
5
7
3
6
8
1
Gambar 2.6: Simpul Super Sumber dan Simpul Super Tujuan
2 1
4
5
3 Gambar 2.7: Ilustrasi Jaringan
1. Lintasan (path), dari simpul i ke simpul j adalah urutan-urutan busur dengan simpul awal suatu busur merupakan simpul akhir dari busur sebelumnya. Dalam lintasan ini semua busur mengarah ke simpul j. Contoh dalam gambar 2.7 bagi lintasan adalah busur (1, 2). 2. Rantai (chain), adalah lintasan yang sebagian busurnya tidak mengarah ke simpul j. Contoh dalam gambar 2.7 bagi rantai adalah urutan busur (1, 2), (3, 2), (3, 4), (4, 5). 3. Sirkuit (circuit),adalah suatu lintasan dalam simpul i sama dengan simpul j atau merupakan lintasan tertutup. Contoh sirkuit dalam gambar 2.7 adalah urutan busur (1, 2), (2, 3), (3, 1). 4. Lingkaran (cycle), adalah rantai tertutup, lintasan yang berawal pada simpul yang sama dan berakhir juga pada simpul yang sama. Contoh lingkaran dalam gambar 2.7 adalah urutan busur (1, 2), (2, 4), (1, 3), (3, 4), (4, 5). 5. Pohon (tree), adalah suatu jaringan yang tidak memiliki siklus. Contoh pohon dalam gambar 2.7 adalah urutan busur (1, 2), (3, 2), (2, 4), (4, 5). Bila setiap busur pada jaringan mempunyai arah tertentu maka jaringan tersebut dinamakan jaringan berarah. Bila sebaliknya, yaitu tidak mempunyai arah sama sekali
41
maka disebut jaringan tidak berubah. Busur berarah (i, j) berarti busur tersebut memiliki arah dari i ke j. Jaringan berkapasitas (capitated network) memiliki batas bawah (lower bound) dan batas atas (upper bound) bagi aliran busurnya. Pembatasan kemampuan aliran busur-busur ini memang diperlukan untuk menggambarkan kapasitas busur yang sebenarnya.
2.6.2
Variabel dan Parameter Jaringan
Dalam analisis jaringan, karakteristik yang menjadi variabel adalah jumlah aliran (flow) dari tiap busur. Variabel ini merupakan variabel keputusan yang sangat
mempengaruhi tercapainya hasil akhir (fungsi tujuan) bagi jaringan itu. Parameter yang digunakan dalam analisis jaringan, untuk setiap busurnya adalah: 1. Ongkos, yang dapat berupa ongkos dalam arti sebenarnya, waktu, jarak atau yang lainnya. Ongkos ini harus dikeluarkan untuk setiap unit komoditi yang melewati suatu busur. Bagi tiap busur, besarnya ongkos tiap unit ini dapat berbeda-beda. 2. Batas atas kapasitas, merupakan jumlah maksimum yang dapat dialirkan oleh suatu busur. 3. Batas bawah kapasitas, merupakan jumlah minimum yang harus dialirkan oleh suatu busur.
2.6.3
Aliran Fisibel Jaringan
Aliran X ij
menggambarkan jumlah aliran pada busur yang menghubungkan
simpul ke-i dan simpul ke-j. Jika busur-busur dalam jaringan tersebut adalah busurbusur yang berkapasitas maka aliran pada busur itu akan memiliki batas bawah ( Lij ) dan batas atas (U ij ) . Aliran fisibel bagi busur itu harus memenuhi: Lij ≤ X ij ≤ U ij , dan
∑X j
ij
− ∑ X ki = Bi k
(II – 46)
42
Bi > 0 Jika simpul ke-i itu adalah simpul sumber Bi < 0 jika simpul ke-i itu adalah simpul tujuan Bi = 0 jika simpul ke-i itu adalah simpul perantara Bi adalah jumlah aliran yang keluar-masuk jaringan.
Persamaan (II – 46) di atas dinamakan konservasi aliran atau Hukum Kirchoff. Dalam menyelesaikan persoalan jaringan dengan ongkos minimum digunakan asumsi bahwa pada seluruh jaringan
∑B
i
= 0 . Jika tak sama dengan nolmaka harus
i
ditambahkan simpul-simpul semu dengan ongkos busurnya nol.
2.7 Algoritma Out of Kilter
Algoritma Out of Kilter merupakan algoritma yang dikembangkan untuk dapat menyelesaikan persoalan jaringan berkapasitas capacitated network. Jaringan berkapasitas adalah suatu jaringan yang busur-busurnya memiliki keterbatasan kemampuan, yaitu dibatasi oleh batas atas (maksimum) dan batas bawah (minimum). Dengan keterbatasan kemampuan pada busur-busurnya itu, Algoritma Out of Kilter mencari alternatif aliran jaringan pada busur-busur tadi yang menghasilkan total ongkos pemindahan minimum. Algoritma Out of Kilter menggunakan teori Dualitas
dan kondisi
Complementary Slackness sebagai pendekatan. Algoritma Out of Kilter serupa dengan
algoritma primal-dual yang dimulai dengan solusi dual fisibel tetapi tidak memrlukan primal fisibel. Dilakukan pengulangan antara persoalan primal dan dual hingga kondisi optimalitas tercapai. Jaringan kerja adalah kumpulan simpul dan busur yang menggambarkan proses fisik berupa pemindahan atau distribusi. Sejumlah komoditi dari simpul satu ke simpul yang lain. Jaringan kerja terbatas selalu dibatasi oleh batas atas dan batas bawah untuk aliran busur-busurnya. Untuk selanjutnya dipergunakan beberapa notasi berikut: X ij : jumlah aliran dari simpul ke-i menuju simpul ke-j. Lij : batas bawah (minimum) aliran pada busur (i, j). U ij : batas atas (maksimum) aliran pada busur (i, j).
43
C ij : ongkos pemindahan per unit aliran dari simpul ke-i menuju simpul ke-j.
Bila suatu jaringan G = (N, A) dengan N merupakan kumpulan simpul (m buah simpul), A adalah kumpulan busur yang menghubungkan simpul-simpul itu. Busurbusur itu memiliki batas atas (U ij ) dan batas bawah (Lij ) serta koefisien ongkos linear C ij . Maka persoalan minimasi ongkos pemindahan pada jaringan kerja itu secara
matematis dapat dirumuskan sebagai berikut: m
m
Minimasi: Z = ∑
∑C
i =1
j =1
ij
X ij
dengan memperhatikan: m
∑X j =1
m
ij
− ∑ X ki = 0 , untuk i = 1,2,3, ..., m k =1
( II – 47) X ij ≥ Lij dan X ij ≤ U ij
( II – 48) 0 ≤ Lij ≤ U ij , untuk i,j = 1,2,3,..., m Kendala (II – 47) merupakan pembatas konservasi aliran (concervation of flow constraints). Kendala ini digunakan untuk menjamin bahwa jumlah aliran yang masuk
ke suatu simpul sama dengan jumlah aliran yang meninggalkan simpul yang bersangkutan. Sedangkan kendala ( II – 48) disebut pembatas kapasitas busur (i, j). Aliran yang memenuhi kendala ( II – 48) disebut aliran fisibel (solusi fisibel). Diasumsikan juga bahwa U ij dan Lij adalah integer. Bentuk persoalan primal minimasi di atas dapat diganti dengan bentuk maksimasi berikut: m
Maksimasi: Z = ∑ i =1
m
∑−C j =1
ij
X ij
dengan memperhatikan: m
m
j =1
k =1
∑ X ij − ∑ X ki = 0 , untuk semua i ∈ N X ij ≤ U ij
(kendala batas atas)
44
− X ij ≤ − Lij
(kendala batas bawah)
X ij ≥ 0
(kondala non-negatif)
Bila π adalah variabel dual yang berkaitan dengan pembatas konsevasi aliran pada primal, α ij adalah variabel dual yang berhubungan dengan pematas atas primal X ij ≤ U ij dan β ij menyatakan variabel dual yang berhubungan dengan pemtas bawah
primal X ij ≥ Lij , maka formulasi matematis dual (perubahan dari primal) dari persoalan aliran dengan ongkos minimum adalah: m
Minimasi: V = ∑ i =1
m
m
j =1
i =1
∑U ijα ij − ∑
m
∑L β j =1
ij
ij
dengan memperhatikan:
π i − π j + α ij − β ij ≥ −Cij α ij , β ij ≥ 0 π unrestricted in sign untuk i, j = 1,2,3,..., m
2.7.1
Kondisi Optimalitas
Penyelesaian persoalan primal dan dual masing-masing optimal jika dan hanya jika kedua penyelesaian primal dan dual itu fisibel. Fisibelitas Primal: m
m
j =1
k =1
P1 : ∑ X ij − ∑ X ki = 0, i ∈ N (konservasi aliran)
PZ : Lij ≤ X ij ≤ U ij , (i, j ) ∈ A (pembatas kapasitas)
Fisibelitas Dual: D1 : π i − π j + α ij − β ij ≥ −C ij , (i, j ) ∈ A D2 : α ij ≥ 0
, (i, j ) ∈ A
D3 : β ij ≥ 0
, (i, j ) ∈ A
Complementary Slackness: C1 : jika π i − π j + α ij − β ij > −C ij
maka X ij = 0
45
C 2 : jikaα ij > 0
maka X ij = U ij
C 3 : jikaβ ij > 0
maka X ij = Lij
Formulasi Kondisi Optimalitas dapat dinyatakan dengan hubungan sebagai berikut (untuk semua i ∈ N ): I.
Jika π j − π i > C ij maka α ij > 0 dan X ij = U ij
II.
Jika π j − π i < C ij maka β ij > 0 dan X ij = U ij
III.
Jika π j − π i = C ij maka U ij ≥ X ij ≥ Lij
dengan menetapkan: IV.
α ij = max{0; (π j − π i − Cij )}
V.
β ij = max{0; (− π j + π i + Cij )} dan
VI.
m
m
j =1
k =1
∑ X ij − ∑ X ki = 0
Jika diasumsikan bahwa kondisi IV dan V terpenuhi dan dengan mendefinisikan CPij = C ij + π i − π j , maka kondisi I, II, III dan VI dapat dinyatakan dalam bentuk
berikut: k1 : Jika CPij < 0
, maka X ij = U ij
k 2 : Jika CPij > 0
, maka X ij = Lij
k 3 : Jika CPij = 0
, maka Lij ≤ X ij ≤ U ij
k 4 : konservasi aliran telah terpenuhi
Bila dua simpul i dan j dihubungkan oleh busur (i, j) dan busur itu memenuhi kondisi optimalitas k1, k2 atau k3 maka busur (i, j) tadi ada dalam kondisi in kilter, jika sebaliknya maka busur (i, j) dikatakan Out of Kilter. Solusi optimal dicapai jika semua busur ada dalam kondisi in kilter dan kondisi k4 (pembatas konservasi aliran) terpenuhi. Algoritma Out of Kilter pada dasarnya digunakan untuk menemukan varibel dual
π i dan jumlah aliran X ij yang memenuhi kondisi optimalitas diatas. Algoritma ini dimulai dengan inisialisasi terhadap nilai variabel dual π i dan jumlah aliran X ij itu. Dengan nilai π i dan Xij tertentu, maka busur (i, j) akan berada pada salah satu status seperti yang ditunjukkan oleh tabel 2.2. 46
Solusi optimal diperoleh jika semua busur ada dalam kondisi in kilter. Oleh karena itu, pada busur yang masih Out of Kilter harus dilakukan perubahan nilai aliran Xij dan atau variabel dual π i -nya agar menjadi in kilter. No
Keterangan
Status
Kondisi
Busur
CPij
Xij
(Kij)
1
A
CPij > 0
Xij = Lij
0
In Kilter
2
A1
CPij > 0
Xij < Lij
|Xij - Lij|
Out Kilter
3
A2
CPij > 0
Xij > Lij
|Xij - Lij|
Out Kilter
4
B
CPij = 0
Lij ≤ Xij ≤ Uij 0
In Kilter
5
B1
CPij = 0
Xij < Lij
|Xij - Lij|
Out Kilter
6
B2
CPij = 0
Xij > Uij
|Xij - Uij|
Out Kilter
7
C
CPij < 0
Xij = Uij
0
In Kilter
8
C1
CPij < 0
Xij < Uij
|Xij - Uij|
Out Kilter
9
C2
CPij < 0
Xij > Uij
|Xij - Uij|
Out Kilter
Kilter Number
Tabel 2.2: Kemungkinan Status Suatu Busur (i, j)
Secara grafik, status suatu busur (i, j) dapat ditunjukkan pada gambar 2.8: Xij In Kilter
Out of Kilter
Uij
Out of Kilter
In Kilter Lij
In Kilter
0
CPij
Gambar 2.8 : Grafik kemungkinan Status Busur (i,j)
Berdasarkan kemungkinan status busur (i,j) di atas maka kondisi optimal (in kilter) dapat dicapai dengan menambah atau mengurangi aliran busur. Dalam mengubah
jumlah aliran busur tersebut harus dijaga agar syarat konservasi aliran tetap terpenuhi.
47
Ada suatu ukuran jarak yang diperlukan untuk mencapai kondisi optimalitas. Ukuran jarak ini disebut kilter number. Jelasnya, kilter number busur (i,j) yang dinyatakan dengan K ij adalah perubahan aliran minimal yang diperlukan busur (i,j) untuk berubah dari Out of Kilter menjadi in kilter. Harga kilter number selalu non-negatif ( K ij ≥ 0 ). Kilter number dari busur yang in kilter adalah nol, sedangkan yang Out of Kilter adalah positif. Kilter number yang diperlukan oleh berbagai status busur untuk menjadi in kilter dapat dilihat pada gambar 2.9: *
X ij − U ij
Xij *
X ij − U ij *
Uij
X ij − U ij *
X ij − Lij Lij
0
X ij − Lij
X ij − Lij
CPij
* * Gambar 2.9 : Kilter Number yang diperlukan oleh berbagai Status Busur (i, j)
2.7.2
Langkah-langkah Pelabelan
Dalam mengubah aliran busur yang Out of Kilter ke aliran yang in kilter terdapat suatu cara yang disebut dengan prosedur pelabelan (labeling procedure). Langkahlangkah pelabelan itu adalah: 1. Bila busur (i, j) berada pada salah satu status berikut: Status a1 , dengan CPij > 0 dan X ij < Lij
;atau
Status b2 , dengan CPij = 0 dan X ij < Lij
;atau
Status c3 , dengan CPij < 0 dan X ij < U ij
, maka busur (i, j) itu harus
dinaikkan alirannya agar menjadi in kilter. Berikan label (q j , i + ) pada simpul j, yang berarti bahwa simpul j menerima tambahan aliran sebesar q j unit dari simpul i. Jika busur (i, j) ada pada status a1 maka besarnya q j adalah (Lij − X ij ) ,
48
dan jika busur (i, j) ada pada status b1 dan c1 maka besarnya q j adalah
(U
ij
− X ij ) .
2. Bila busur (i, j) berada pada salah satu status berikut: Status a 2 , dengan CPij > 0 dan X ij > Lij
;atau
Status b2 , dengan CPij = 0 dan X ij > U ij
;atau
Status c 2 , dengan CPij < 0 dan X ij > U ij
, maka busur (i, j) itu harus
diturunkan alirannya agar menjadi in kilter. Berikan label (qi , j − ) pada simpul i, yang berarti bahwa aliran yang berasal dari simpul i ke simpul j harus dikurangi sebesar qi . Jika busur (i, j) ada pada status a 2 dan b2 maka besarnya qi adalah
(X (X
ij
− Lij ) , dan jika busur (i, j) ada pada status c 2 maka besarnya qi adalah
ij
− U ij ) .
3. Bila busur berada pada salah satu status a, b atau c maka busur (i, j) itu ada dalam kondisi in kilter, dan aliran busurnya tidak perlu di ubah lagi, kecuali pada status b yang alirannya memungkinkan untuk dinaikkan atau diturunkan sepanjang batas atas dan batas bawah yang ada tanpa mengubah busur itu ke kondisi Out of Kilter. Sebelum melakukan perubahan aliran pada busur (i, j) maka harus didapatkan sebuah lintasan (path) dari simpul j ke simpul i yang berupa loop dengan busur (i, j) ada di dalamnya. Hal ini perlu dilakukan agar konservasi aliran pada setiap simpulnya tidak terganggu oleh perubahan aliran yang dilakukan itu. Pada busur (i, j) yang masih Out of Kilter, simpul i dan simpul j diberi label sesuai dengan prosedur perlabelan di atas. Setelah simpul i dan simpul j selesai diberi label maka akan diperoleh suatu lintasan yang disebut dengan FAP (flow augmenting path) dari simpul j ke simpul i sehingga perubahan aliran pada busur (i, j) dapat
dilakukan. Apabila prosedur labelisasinya gagal maka dilakukan perubahan harga variabel dual π . Ketika proses labelisasinya gagal, maka terdapat sejumlah simpul yang belum diberi label dan sejumlah simpul pul yang telah diberi label. Non-breakthrough adalah kejadian pada saat diperoleh kumpulan simpul yang sudah diberi label dan yang belum
49
diberi label. Sedangkan breakthrough adalah keadaan dengan semua simpul sudah diberi label. Misalnya dinyatakan bahwa A adalah kumpulan simpul yang telah diberi label., dan A menyatakan kumpulan simpul yang belum diberi label, amka ada dua kasus yang berkaitan dengan hal di atas, yaitu: Kasus I: B adalah kumpulan semua busur yang berasal dari simpul anggota A menuju simpul anggota A dengan nilai CPij > 0 dan X ij ≥ Lij . Kasus II: B adalah kumpulan semua busur yang berasal dari simpul anggota A menuju simpul anggota A dengan nilai CPij < 0 dan X ij ≥ Lij . Karena CPij dapat dihitung setiap busur pada kumpulan B dan B , maka perubahan variabel dual π dapat dilakukan dengan cara sebagai berikut: 1. kasus I: untuk setiap CPij > 0 Tetapkan δ 1 =
[
]
min CPxy jika B ≠ ø ; lainnya δ 1 = ∞ B
2. kasus II: untuk setiap CPij < 0 Tetapkan δ 2 =
[
]
min − CPxy jika B ≠ ø ; lainnya δ 2 = ∞ B
3. Hitung δ = min[δ 1 , δ 2 ] 4. Ubah harga variabel dual π k menjadi π k , dengan menambahkan δ , yaitu:
πk
, jika k ∈ A
π k' =
(π k + δ ) , jika k ∈ A Setelah didapatkan variabel dual baru. Iterasi dilanjutkan kembali ke prosedur perlabelan sampai semua brosur (i, j) ada dalam keadaan in kilter (proses optimasi tercapai).
50
2.7.3
Langkah-langkah Perhitungan Algoritma Out of Kilter
Dalam menyelesaikan persoalan jaringan berkapasitas (capacitated network) dengan menggunakan algoritma Out of Kilter diperlukan langkah-langkah sebagai berikut: Langkah 1: Inisialisasi Menetapkan aliran X ij dan variabel dual π yang memenuhi pembatas konservasi aliran. Pilih yang menghasilkan busur in kilter sebanyak mungkin. Langkah 2: Memeriksa Optimalitas Lakukan perhitungan terhadap harga CPij dan K ij pada setiap busur (i, j). Bila semua busur (i, j) memiliki harga K ij = 0 (in kilter) maka STOP karena solusi optimal telah diperoleh. Bila masih ada busur yang Out of Kilter
(K
ij
> 0) maka lanjutkan ke langkah 3.
Langkah 3: Memeriksa Status Busur (i, j) Lakukan pemeriksaan status terhadap busur (i, j) yang masih Out of Kilter. Bila status busur (i, j) termasuk a1 ,b2 atau c1 maka lanjutkan ke langkah 4. bila status busur (i, j) termasuk a z , bz , atau c z maka lanjutkan ke langkah 5. Langkah 4: Menambah Aliran pada Busur (i, j) Dengan menggunakan prosedur pelabelan, temukan lintasan dari simpul j ke sumpul i sehingga aliran masih dapat dilewatkan dengan tidak menyebebakn kondisi busur (i, j) tersebut makin Out of Kilter. Jika lintasan ditemukan maka tambahkan sejumlah aliran pada busur (i, j), dan apabila busur (i, j) sudah Out of Kilter maka kembali ke langkah 2. jika bususr (i, j) masih tetap Out of Kilter maka ulangi kembali langkah 4 ini. Atau lanjutkan ke langkah 6 seandainya lintasan tidak ditemukan. Langkah 5: Mengurangi Aliran pada Busur (i, j) Dengan menggunakan prosedur pelabelan, temukan lintasan dari simpul i ke simpul j sehingga aliran masih dapat dilewatkan dengan tidak mengakibatkan kondisi busur (i, j) tersebut makin Out of Kilter. Jika lintasan ditemukan maka kurangkan sejumlah aliran pada busur (i, j), dan apabila busur (i, j)
51
sudah in kilter maka kembali ke langkah 2. jika bususr (i, j) masih tetap Out of Kilter maka ulangi kembali langkah 5 ini. Atau lanjuktkan ke langkah 6 seandainya lintasan tidak ditemukan. Langkah 6: Mengubah Harga Variabel Dual π Lakukan perubahan terhadap harga variabel dual π . Hapuskan semua label dan kembali ke langkah 2. bila nilai simpul δ = ∞ , STOP. Tidak ada aliran yang fisibel.
2.7.4
Penerapan Algoritma Out of Kilter
Dalam menyelesaikan persoalan jaringan dengan algoritma Out of Kilter digunakan asumsi bahwa setiap busur berarah dalam jaringan mempunyai kapsitas tertentu, atau mempunyai batas bawah dan batas atas bagi alirannya. Dalam pemakaian algoritma Out of Kilter, ada dua langkah penting yang diperlukan untuk memformulasikan masalah, yaitu: 1. Permasalahan diformulasikan dalam bentuk jaringan berkapasitas dengan loop tertutup. 2. Insisialisasi harga varibel dual π i dan jumlah aliran X ij sehingga pembatas konservasi aliran terpenuhi. Algoritma Out of Kilter dapat dipergunakan untuk menyelesaikan beberapa persoalan jaringan berkapasitas, yaitu: 1. Persoalan transportasi (transportation problem) 2. Persoalan penugasan (assignment problem) 3. Persoalan ongkos minimum/aliran maksimum (minimum cost/maximum flow problem) 4. Persoalan lintas terpendek (shortest-path tree problem) 5. Persoalan transshipment (transshipment problem)
52
