BAB 2 LANDASAN TEORI
2.1.
Peramalan
2.1.1. Faktor-Faktor Pertimbangan Dalam Peramalan Kuantitatif Menurut Sofjan Assauri, ” Peramalan adalah kegiatan untuk memperkirakan apa yang akan terjadi pada masa yang akan datang ” (Sofjan Assauri, 1984:1). Sedangkan menurut Hendra Kusuma, ”Peramalan adalah perkiraan tingkat permintaan satu atau lebih produk selama bebrapa periode mendatang” (Henra Kusuma, 1999:13). Pada dasarnya metode peramalan kuantitatif ini dapat dibedakan atas: 1)
Metode peramalan yang didasarkan atas penggunaan analisis pola hubungan antara variabel yang akan diperkirakan dengan variabel waktu, yang merupakan deret waktu, atau ”time series”.
2)
Metode peramalan yang didasarkan atas penggunaan analisis pola hubungan antara variabel yang akan diperkirakan dengan variabel yang lain yang mempengaruhinya, yang bukan waktu, yang disebut metode korelasi atau sebab akibat ” causal methods” (Sofjan Assauri,1984:9). Peramalan kuantitatif hanya dapat digunakan apabila terdapat tiga kondisi sebagai
berikut: 1.
Adanya informasi tentang keadaan yang lain.
2.
Informasi tersebut dapat dikuantifikasikan dalam bentuk data.
7
3.
Dapat diasumsikan bahwa pola yang lalu akan berkelanjutan pada masa yang akan datang (Sofjan Assauri,1984:5) Ada empat jenis pola data, antara lain:
1.
Pola horizontal atau stationary, bila nilai-nilai dari data observasi berfluktuasi disekitar nilai konstan rata-rata. Dengan demikian dapat dikatakan pola ini sebagai stationary pada rata-rata hitungnya (means ).
2.
Pola seasonal atau musiman, bila suatu deret waktu dipengaruhi oleh faktor musim (seperti kuartalan, bulanan , mingguan dan harian).
3.
Pola cyclical atau siklus bila data observasi dipengaruhi oleh fluktuasi ekonomi jangka panjang yang berkaitan atau bergabung dengan siklus usaha (business cycle).
4.
Pola trend bila ada pertambahan atau kenaikan atau penurunan dari data obserfasi untuk jangka panjang. Pola ini terliahat pada penjualan produk dari banyak perusahaan. Pendapatan Domestik Nasional Bruto (GDP/GNP) dan indikator ekonomi (Sofjan Assauri,1984:5)
2.1.2. Model Peramalan Moving Averages Metode moving averages diperoleh melalui penjumlahan dan pencarian nilai ratarata dari sejumlah periode tertentu, setiap kali menghilangkan nilai terlama dan menambah nilai baru.
8
Y +Y +Y +Y Yˆt +1 = t t −1 t − 2 t − n +1 n Keterangan: Yˆt +1
= Nilai peramalan pada periode berikutnya
Yˆt
= Nilai aktual perintaan periode sebelumnya
n
= Periode dalam rata-rata bergerak
Dengan tambahan bahwa satu nilai Y diganti setiap periode. Perhitungan rata-rata dilakukan dengan bergerak ke depan untuk memperkirakan periode yang akan datang dan dicatat dalam posisi terpusat pada rata-ratanya. Moving Averages secara efektif meratakan dan menghaluskan fluktuasi pola data yang ada. Tentu saja semakin panjang periodenya, semakin rata kurvanya. Kebaikan lainnya adalah bahwa metode Moving Averages dapat diterapkan pada data apapun juga, apakah data sesuai dengan kurva matematik atau pun tidak. Kelemahan metode ini adalah tidak mempunya persamaan untuk peramalan. Sebagai gantinya digunakan rata-rata bergerak terahir sebagai ramalan periode berikutnya. (T. Hani Handoko, 1984:276).
2.1.3. Model Peramalan Double Eksponential Smooting Eksponential Smooting adalah suatu tipe teknik peramalan rata-rata bergerak yang melakukan penimbangan terhadap data masa lalu dengan cara eksponensial sehingga
9
data paling akhir mempunyai bobot atau timbangan lebih besar dalam rata-rata bergerak. Dengan Eksponential Smooting sederhana, peramalan dilakukan dengan cara ramalan periode terahir ditambah dengan porsi perbedaan (disebut α) antara permintaan nyata periode terahir dan ramalan periode terahir. Persamaan Eksponential Smooting adalah :
Yˆt = Yˆt −1 + α (Yt −1 − Yˆt −1 )
α = 1−
2 ( N + 1)
Keterangan : Ŷt
= Peramalan Pada Periode t
Ŷt-1
= Peramalan Pada Periode t-1
α
= Konstanta Pemulusan
Yt-1
= Data Permintaan Aktual pada Periode t-1
N
= Banyaknya Periode Data Permintaan Aktual
Eksponential Smooting sederhana tidak memperhitungkan trend , sehingga tidak ada nilai α yang sepenuhnya menggantikan trend dalam data. Nilai-nilai α rendah akan menyebabkan jarak yang lebih lebar dengan trend karena hal itu akan memberikan bobot yang lebih kecil pada permintaan yang sekarang. Nilai α yang rendah terutama cocok bila permintaan produk relativ stabil (yang berat, tampa trend atau variasi siklikal) tetapi variasi acak adalah tinggi. Nilai-nilai α lebih tinggi adalah lebih berguna dimana perubahan perubahan yang sesungguhnya cenderung terjadi karena lebih responsif terhadap fluktuasi permintaan. Sebagai
10
contoh niali α tidak mungkin cocok bagi industri barang-barang mode tanggapan yang cepat dan dramatik. Pengenalan-pengenalan produk baru, kampanye promosional, dan bahkan antisipasi terhadap resesi juga memerlukan penggunaan nilai-nilai α yang lebih tinggi. Nilai α yang tepat pada umumnya dapat ditentukan dengan pengujian ”trial – and – eror” (coba-coba) terhadap α yang berbeda-beda untuk menemukan satu nilai α yang menghasilkan kesalahan terkecil bila digunakan pada data masa lalu (T. Hani Handoko, 1984:279). Dengan cara analogi yang dipakai waktu berangkat dari rata-rata bergerak tunggal ke pemulusan (smoothing) eksponensial tunggal, kita juga dapat berangkat dari ratrata bergereak ganda ke pemulusan eksponensial ganda. Perpindahan seperti itu mungkin menarik karena salah satu keterbtasan dari rata-rata bergerak tunggal yaitu perlunya menyimpan N nilai terakhir masih terdapat pada rata-rata bergerak linear, kecuali bahwa jumlah nilai data yang diperlukan sekarang adalah 2N-1. pemulusan eksponensial linear dapat dihitung hanya dengan tiga nilai data dan satu nilai untuk α. Pendekatan ini juga memberikan bobot yang semakin menurun pada observasi masa lalu. Perbedaan nilai pemulusan tunggal dan ganda dapat ditambahkan kepada nilai pemulusan tunggal dan disesuaikan untuk trend (S. Makridakis 1988,279).. Adapun persamaannya sebagai berikut: Yˆt +1 = αY1 + (1 − α )Yˆt
α t = Yˆt + (Yˆt − Yˆt −1 )
11
bt =
α ˆ ˆ (Yt − Yt ) 1−α
Yt + m = at + bt m
2.1.4. Model Peramalan Linear Regretion Model analisis garis kecenderungan dipergunakan sebagai peramalan apabila pola hitoris data actual permintaan menunjukan adanya suatu kecenderungan naik dari waktu ke waktu. Model analisis garis kecenderungan yang paling sederhana adalah menggunakan persamaan garis lurus (straight line equation), sebagai berikut: 1. Perhitungan slope
b=
∑ t (Y ) − n(t − bar )(Y − bar ) ∑ t − n(t − bar ) t
t
2
2
2. Perhitungan intersep
a = (Yt − bar ) − b(t − bar ) 3. Nilai ramalan ramalan permintaan periode t Yˆt = a + bt
Keterangan: Yˆt
= Nilai ramalan pada periode t
a
= intersep
b
= Slope dari garis kecenderunga (trend line), merupakan tingkat perubahan dalam permintaan
12
t
= Indeks waktu
n
= Banyaknya periode
t-bar
= nilai rata-rata dari t
Yt
= Variable permintaan (data aktual)
Yt − bar = Nilai rata-rata permintaan per periode waktu
2.1.5. Model peramalan Holt-Winters Additive Algorithm
Metode ini digunakan untuk pola data musiman (seasonal). Metode ini merupakan lanjutan dari metode Holt dua parameter. Perbedaannya hanya pada penambahan satu parameter untuk nilai musiman (seasonality). Nilai musiman ini diperoleh dari perkalian antara seasonal indeks (Yt/At) dengan konstanta musiman γ kemudian ditambahkan dengan perkalian nilai musiman sebelumnya (St-L) dengan (1-γ). Persamaan yang digunakan adalah sebagai berikut: 1. Pemulusan eksponential At = α
Yt + (1 − α )( At −1 + Tt −1 ) St−L
2. Perkiraan kecenderungan Tt = β ( At − At −1 ) + (1 − β )Tt −1 3. Perkiraan nilai musiman S4 = γ
Yt + (1 − γ ) S t − L At
4. Peramalan pada perioda 5 adalah sebagai berikut:
13
Yˆt + p = ( At + pTt ) S t − L + p Keterangan : At
= Nilai Pemulusan baru
α
= Konstanta pemulusan (0<α<1)
Yt
= Nilai Peramalan Aktual pada periode t
β
= Konstanta pemulusan trend (0<β<1)
T1
= Nilai perkiraan trend
γ
= Konstanta pemulusan seasonal
St
= Nilai seasonal perkiraan
p
= periode peramalan
L
= Panjang Musiman
Yˆt + p
= Nilai peramalan pada periode berikutnya
Satu masalah dalam metode Winters adalah menentukan nilai-nilai untuk α ,β , dan
γ tersebut yang akan meminimumkan MSE atau MAPE. Pendekatan untuk menentukan nilai ini biasanya secara coba dan salah (trial & eror), walaupun mungkin juga digunakan alogaritma optimasi non-Linear unutk mendapatkan nilai parameter optimal. Karena ke dua pendekatan tersebut memakan banyak waktu dan mahal, maka metode ini jarang digunakan. Metode ini dipakai jika banyak himpunan data yang harus ditangani.
14
2.1.6. Analisis Kesalahan Peramalan Beberapa alternatif analisis kesalahan peramalan yang digunakan adalah: 1) Mean Squared Eror (MSE) : 2) Mean Absolute Percentage Error (MAPE) Keterangan: Nilai Tengah Kesalahan Kuadrat (Mean Squared Error) n
∑ (Y
t
MSE =
− Yˆt )
t =1
n
(2-2)
Nilai Tengah Kesalahan Persentase Absolut (Mean Absolute Percentage Error) | Yt − Yˆt | Yt MAPE = t =1 n n
∑
Dua ukuran tersebut, merupakan alat evaluasi teknik-teknik peramalan untuk berbagai macam parameter. Semakin rendah nilai MAPE dan MSE, peramalan semakin baik (mendekati data masa lalu). Tetapi nilai terrendah (kecuali nol) tidak memberikan indikasi seberapa baik metode peramalan yang digunakan dibandingkan dengan metode lainnya (Hendra Kusuma, 199:38).
15
2.1.7. Verifikasi dan Pengendalian Peramalan Langkah penting setelah peramalan adalah verivikasi peramalan sedemikian rupa sehingga dapat mencerminkan data masa lalu dan sistem sebab-akibat yang mendasari permintaan itu. Jika proses verivikasi ditemukan keraguan atas validitas peramalan maka harus dicari metode yang lebih cocok. Validitas harus ditentukan dengan uji statistika yang sesuai. Peramalan harus selalu dibandingkan dengan permintaan aktual secara teratur. Pada suatu saat harus diambil tindakan revisi terhadap peramalan tersebut apabila ditemukan bukti yang meyakinkan adanya perubahan pola permintaan. Selain itu penyebab perubahan pola permintaan pun harus diketahui. Penyesuaian metode peramalan dilakukan segera perubahan pola permintaan diketahui (Hendra Kusuma, 1999:40). Terdapat banyak perkakas yang digunakan untuk memverivikasi peramalan dan mendeteksi perubahan sistem sebab akibat yang melatar belakangi perubahan pola permintaan. Tetapi bentuk yang paling sederhana diusulkan oleh Bigel adalah peta kendali peramalan, mirip peta kendali kualitas. Tracking signal adalah suatu ukuran bagaimana baiknya suatu ramalan memperkirakan nilai-nilai aktual. Tracking signal dihitung sebagai running sum of the forcast errors (RSFE) dibagi dengan mean absolut deviation (MAD), sebagai berikut: Tracking ⋅ Signal =
=
RSFE MAD
∑ ( actual ⋅ demand ⋅ in ⋅ period ⋅ i − forecast ⋅ demand ⋅ in ⋅ period ⋅ i ) ⋅ MAD
16
MAD =
∑ ( absolut ⋅ dari ⋅ forecast ⋅ eror ) ⋅ MAD
Tracking signal yang positif yang menunjukkan bahwa nilai aktual permintaan lebih besar dari peramalan, sedangkan tracking signal yang negatif berarti nilai aktual permintaan lebih kecil dari pada ramalan. Suatu tracking signal disebut baik apabila memiliki RSFE yang rendah, dan mempunyai positife eror yang sama banyak atau seimbang dengan negatife eror, sehingga pusat dari tracking signal mendekati nol. Apabila tracking signal telah dihitung kita dapat membangun peta kontrol signal sebagaimana halnya dengan peta-peta kontrol dalam pengendalin proses statistical (statistical proses control = SPC) yang memiliki bats kontrol atas (upper control limit) dan batas control bawah (lower control limit). Beberapa ahli dalam sistem peramalan seperti George Plossl dan Oliver Wight, dua pakar Production Planning and Inventory Control, menyarankan untuk menngunakan tracking signal maksimum ±4, sebagai batas-batas pengendalian untuk tracking signal. Dengan demikian apabila tracking signal telah berada diluar batasbatas pengendalian, model peramalan perlu ditinjau kembali, karena akurasi peramalan tidak adapat diterima (Vincent Gaspersz, 2002:81).
17
2.2.
Optimasi Model Pengambilan Keputusan
2.3.1. Pengaruh Ketersediaan Data Terhadap Permodelan Apapun jenis model akan memiliki sedikit nilai praktis jika tidak didukung oleh data yang handal. Walaupun sebuah model didefinisikan dengan baik, mutu pemecahan model tersebut sangat tergantung pada pengestimasian data yang diperlukan. Jika estimasi tersebut terdistorsi, pemecahan yang diperoleh, walaupun optimal dalam arti matematis, pada kenyataannya dapat bermutu rendah dari sudut pandang system nyata. Dalam beberapa permasalahan, data tidak dapat diketahui dengan pasti sehingga data tersebut dapat diestimasi berdasarkan distribusi probabilitas. Pada permasalahan tersebut, struktur model kemungkinan perlu diubah untuk mengakomodasi sifat probabilistic dari permintaan. Jadi berdasarkan ketersediaan data, permodelan dapat dibagi menjadi 2 jenis model, yaitu model probabilistic atau stochastic dan model deterministic (Hamdy A Taha, 1993:7). Pada kenyataannya, pengumpulan data merupakan bagian paling sulit dari sebuah model.
2.3.2. Penyelesaian Terhadap Model Pengambilan Keputusan Dalam operasional riset terdapat 2 jenis perhitungan yang berbeda, yaitu: 1. Model-model simulasi Memecahkan system yang dimodelkan kedalam modul-modul dasar atau elementer yang kemudian dikaitkan satu sama lain dengan hubungan-hubungan logis yang didefinisikan dengan baik.
18
2. Model-model matematis Pemecahan yang optimal dari sebuah model matematis biasanya tidak tesedia dalam bentuk tertutup, melainkan solusi optimal dicapai dalam langkah-langkah atau iterasi. Jadi dapat dikatakan bahwa pemecahan menyatu secara iteratif ke pemecahan optimal. Selanjutnya akan dijelaskan mengenai model matematis yang merupakan model dari operasional riset. Terdapat dua alasan mengapa tidak semua model matematis memiliki alogaritma pemecahan optimal, yaitu: 1) Alogaritma pemecahan dapat terbukti menyatu ke pemecahan optimal, tetapi dalam arti teoritis. 2) Kompleksitas model matematis dapat membuat perancangan alogaritma pemecahan tidak mungkin dilakukan (Hamdy A Taha, 1993:8). Selanjutnya akan diterangkan mengenai salah satu model matematis yang mengasumsikan bahwa tujuan dan batasan sebuah model dapat diekspresikan secara kuantitatif data sebagai fungsi matematis dari variable keputusan, yaitu Linear Programming
2.3.
Linear Programming
2.3.1. Pengantar Linear Programming Keberhasilan suatu teknik riset operasi pada akhirnya diukur berdasarkan penyebaran penggunaannya sebagai suatu alat pengambil keputusan sejak diperkenalkan diakhir tahun 1940 -an, Linear Programming telah terbukti merupakan
19
salah satu riset operasi yang paling efektif. Keberhasilannya berakar dari keluwesannya dalam menjabarkan berbagai situasi kehidupan nyata dibidang – bidang berikut ini, yaitu militer, industri, pertanian, transportasi, ekonomi, kesehatan, dan bahkan ilmu sosial dan perilaku. Disamping itu, tersedianya program komputer yang sangat efisien untuk memecahkan masalah – masalah linear programming yang sangat luas merupakan faktor penting dalam tersebarnya penggunaan teknik ini. Kegunaan linear programming adalah lebih luas daripada aplikasinya semata – mata. Pada kenyataannya, linear programming harus dipandang sebagai dasar penting pengembangan teknik – teknik riset operasi lainnya, termasuk program integer, stokastik, arus jaringan dan kuadratik. Dalam hal ini, pemahaman akan linear programming adalah penting untuk implementasi teknik – teknik tambahan ini. Linear programming adalah sebuah alat deterministik, yang berarti bahwa semua parameter model yang diasumsikan diketahui dengan pasti. Tetapi dalam kehidupan nyata, jarang seseorang mengahadapi masalah dimana terdapat kepastian yang sesungguhnya. Teknik linear programming mengkompensasikan ”kekurangan” ini dengan memberikan analisis paska optimal dan analisis parametrik yang sistematis untuk memungkinkan pengambil keputusan yang bersangkutan untuk menguji sensivitas pemecahan yang optimal yang statis terhadap perubahan diskrit atau kontinue dalam berbagai parameter dari model tersebut. Pada intinya teknik tambahan ini memberikan dimensi dinamis pada sifat pemecahan linear programming yang optimal.
20
Tujuan dari linear programming adalah suatu hasil yang mencapai tujuan yang ditentukan (optimal) dengan cara yang paling baik diantara semua alternatif yang mungkin dengan batasan sumber daya yang tersedia. Meskipun mengalokasi sumber – sumber daya kepada kegiatan – kegiatan merupakan jenis aplikasi yang paling umum, linear programming mempunyai banyak aplikasi penting lainnya. Sebenarnya, setiap masalah yang metode matematisnya sesuai dengan format umum bagi linear programming merupakan masalah bagi linear programming. Selanjutnya suatu prosedur penyelesaian yang sangat efisien, yang dinamakan metode simpleks, tersedia untuk menyelesaikan masalah – masalah linear programming bahkan untuk masalah yang besar sekalipun. Linear programming merupakan proses optimasi dengan menggunakan model keputusan yang dapat diformulasikan secara sistematis dan timbul karena adanya keterbatasan dalam mengalokasikan sumber – sumber daya. Don T. Philips dalam bukunya ”operasion research principles and practice” menyatakan bahwa linear programming merupakan masalah pemrograman yang harus memenuhi tiga kondisi berikut ini: 1.
Variabel – variabel keputusan yang terlibat harus tidak negatif
2.
Kriteria – kriteria untuk memilih nilai terbaik dari variabel keputusan dapat diekspresikan sebagai fungsi linear variabel tersebut. Fungsi kriteria itu bisa disebut sebagai ”fungsi objektif”.
21
3.
Aturan – aturan operasi yang mengarahkan proses – proses dapat diekspresikan sebagai suatu set persamaan atau pertidaksamaan linear. Set tersebut dinamakan ”fungsi pembatas”.
2.3.2. Pembuatan Model Untuk menyelesaikan suatu masalah dapat digunakan model linear programming. Adapun langkah – langkah pemodelannya adalah sebagai berikut: a.
Menentukan variabel – variabel dari persoalan.
b.
Menentukan batasan – batasan yang harus dikenakan atas variabel untuk memenuhi batasan sistem yang di modelkan.
c.
Menentukan tujuan yang harus dicapai untuk menentukan pemecahan Optimal (terbaik) dari semua nilai yang layak dari variabel tersebut (Hamdi A. Taha,1993:17). Langkah – langkah pemodelan dapat diformulasikan sebagai berikut:
a.
Identifikasi variabel, misalnya X1, X2, dan seterusnya.
b.
Fungsi pembatas diformulasikan sebagai berikut: a11X1 + a12X2 + ... + a1nXn
( ≤ ; = ;≥ )
b1
a21X1 + a22X2 + ... + a2nXn
( ≤ ; = ;≥ )
b2
!
!
!
!
!
!
!
!
am1X1 + am2X2 + ... + amnXn (≤; = ;≥) X1, Xn, …, Xn ≥ 0
bm
22
Keterangan: Xj
=
Variabel Keputusan
Cj
=
Konstanta variabel keputusan
ajj
=
Konstanta variabel keputusan pada persamaan / pertidak samaan pembatas
bi
=
Konstanta ruas kanan dari setiap persamaan / pertidaksamaan pembatas
c.
i
=
1,2, ...., m
j
=
1,2, ...., m
Fungsi tujuan (baik maksimasi ataupun minimasi) dapat diformulasikan sebagai berikut: Z
=
C1X1 + C2X2 + ... + CnXn
Bentuk umum model diatas, bila ditulis dalam notasi vektor matriks, dapat diekspresikan sebagai berikut: Maksimasi atau Minimasi:
Z = C.X
Dengan memperhatikan:
a.X=b X (≤; = ; ≥) 0 X ≥0
23
2.3.3. Bentuk Baku Formulasi Model Linear Programing Terdapat 4 buah karakter yang menjadi ciri dari bentuk standar, yaitu sebagai berikut: a.
Semua pembatas berupa persamaan
b.
Elemen ruas kanan tiap pembatas adalah non – negatif
c.
Semua variabel adalah non – negatif
d.
Fungsi tujuan berjenis maksimasi atau minimasi Pembatas yang pertidaksamaan dapat diubah menjadi persamaan dengan
menambah atau mengurangi ruas kiri dengan suatu variabel non – negatif. Variabel baru ini disebut ”varibel slack”, yang harus ditambahkan ke ruas kiri bila dibentuk pertidaksamaan ≤ dan dikurangi bila bentuk pertidaksamaan ≥ variabel slack (Sj) ≥ 0 mempunyai sifat menggunakan satu satuan sumber terbatas untuk setiap satuan Sj yang terjadi, dan juga mempunyai sifat tidak mempengaruhi besaran fungsi tujuan. a1X1 + a2X2 ≥ b1
→
a1X1 + a2X2 – S1 = b1
b1 ≥ 0 a1X1 + a2X2 ≥ b2
S1 ≥ 0
→
a1X1 + a2X2 – S2 = b1
b2 ≥ 0
S2 ≥ 0
Didalam menyelesaikan persoalan linear programming dengan menggunakan metode simpleks, bentuk dasar yang digunakan adalah bentuk standar. Karena itu setiap masalah linear programming harus diubah menjadi bentuk standar sebelum dapat dipecahkan dengan metode simpleks.
24
Hal lain yang perlu diperhatikan dalam memecahkan masalah persoalan dengan menggunakan metode simpleks adalah harus adanya variabel – variabel basis dalam fungsi pembatas untuk memperoleh solusi awal yang feasible. Untuk fungsi – fungsi pembatas dengan tanda ≤, maka variable basis dapat diperoleh dengan menambahkan varible slack atau sebaliknya. Tetapi apabila fungsi pembatas mempunyai bentuk persamaan, maka tidak selalu diperoleh varible basis. Untuk mendapatkan variable basis tersebut, dapat ditambahkan dengan suatu variable semu, yang disebut ”variabel artificial”. variabel artificial adalah variable yang di tambahkan pada fungsi pembatas mempunyai hubungan persamaan untuk memperoleh basis, atau juga dapat dinyatakan sebagai satuan variable semu (palsu) yang mempunyai sifat menggunakan satu satuan sumber artificial ini mempunyai koefisien fungsi tujuan yang sangat besar, dimana harga ini dapat bernilai negatif atau positif, tergantung pada sifat fungsi tujuannya maksimasi atau minimasi: Cn
= -M ; untuk maksimasi fungsi tujuan
Cn
= +M ; untuk minimasi fungsi tujuan
Keterangan: M
= bilangan bulat positif yang sangat besar
Cn
= koefisien fungsi tujuan untuk variabel artificial X
2.3.4. Metode Simplex Pada tahun 1947, seorang ahli matematika, george b. Dantzig menemukan dan mengembangkan suatu metode pemecahan model linear programming. Metode
25
tersebut adalah metode simpleks. Metode ini merupakan teknik yang dapat memecahkan model yang mempunyai variabel keputusan dan pembatas yang lebih besar dari dua. Bahkan pada akhirnya, secara teoritis, metode ini dapat menangani variabel keputusan dan pembatas dengan jumlah yang tak terbatas atau terhingga. Algoritma simpleks diterangkan dengan menggunakan logika aljabar matriks, sehingga operasi perhitungan dapat lebih efisien. Metode simpleks mempunyai prosedur yang bersifat iterasi dan bergerak selangkah demi selangkah. Dimulai dari suatu titik ekstrim (solusi feasible dasar) didaerah feasible menuju ke titik ekstrim yang optimal. Pada setiap perpindahan dari satu solusi feasible dasar ke solusi feasible dasar lainnya, dilakukan sedemikian rupa sehingga terjadi perbaikan pada nilai fungsi tujuan. Pada dasarnya, metode simpleks menggunakan dua kondisi untuk mendapatkan solusi yang optimal,yaitu: •
Kondisi optimalitas Yang menyatakan bahwa solusi yang dioptimalkan adalah solusi terbaik.
•
Kondisi feasibilitias yang menyatakan bahwa yang dioptimalkan adalah solusi feasible dasar (basic feasible solution).
Karena perhitungan metode simpleks dilakukan dengan secara bertahap dan model perhitungan dapat digunakan tabel simpleks, dengan pola umum seperti pada tabel dibawah ini:
26
Tabel 2.1 Format Tabel Simplek Cj Basis C1 B1 C2 B2 : : : : Cn Bn Crow = Cj - Ji Ci
C1 X1 a11 a12 : : a1n C1 – Z1
C2 X2 a21 a22 : : a2n C2 – Z2
,,,,,,,,, ,,,,,,,,, ,,,,,,,,, ,,,,,,,,, : : ,,,,,,,,,
Cn Xn am1 am2 : : amn Cm –Zm
Konstanta b1 b2 : : bn Z = ∑aij - Ci
Keterangan : Ci = koefisien fungsi tujuan yang berhubungan dengan variabel basis ke – i Cj = koefisien fungsi tujuan dari semua variabel ke – j (variabel basis maupun variabel non basis) bi = nilai dari variabel ke – i, sedangkan nilai variabel non – basis adalah nol aij = substitution ratio pada perpotongan baris ke – i dan kolom ke – j di bawah variabel non basis; sedangkan yang berada di bawah variabel basis adalah matriks satuan dengan harga 1 atau 0. Langkah – langkah pemecahan model linear programming dengan metode simpleks adalah sebagai berikut: 1.
Formulasikan masalah a.
Membuat fungsi tujuan dan fungsi pembatas
b.
Mengubah bentuk suatu pertidaksamaan menjadi persamaan dengan menambah variabel slack atau variabel surplus serta varible artificial.
27
c.
Modifikasi fungsi tujuan dengan memasukkan variable slack, variable surplus, atau variable artificial, bersama – sama dengan koefisien yang sesuai.
2.
Program awal Membuat program awal sehingga hanya variable slack atau variable artificial yang termasuk di dalam jawaban. Gambarkan program ini di dalam tabel simpleks.
3.
Tes untuk optimalisasi a.
Hitung harga – harga (Cj – Zj) pada setiap kolom.
b.
Tes untuk optimalitas. Jika semua harga tersebut sudah nol atau negatif, maka untuk persoalan maksimasi jawabannya sudah mencapai optimal. Sebaliknya jika harga – harga tersebut nol atau positif untuk persoalan minimasi, maka hasil jawaban tersebut sudah mencapai optimal.
c.
Program perbaikan: 1.
Menentukan sebuah kolom kunci (incoming variable). Untuk kolom yang mempunyai harga (Cj – Zj) positif terbesar di jadikan kolom kunci, dalam masalah maksimasi dan kolom yang mempunyai harga (Cj – Zj) negatif terbesar dijadikan kolom kunci untuk persoalan minimasi.
2.
Tentukan baris kunci dan bilangan kunci (outgoing variable). Bilangan – bilangan di bawah kolom di bagi dengan bilangan –
28
bilangan pada kolom kunci. Hasil dari pembagian ini disebut replacement quantities (rasio). Bandingkan harga – harga rasio ini. Baris yang mempunyai rasio terkecil dijadikan baris kunci (outgoing variable). Bilangan yang terletak pada perpotongan antara kolom kunci dengan baris kunci disebut bilangan kunci. 3.
Mengubah bentuk baris kunci. Kurangkan bilangan pada baris yang lama (pada setiap kolom) dengan hasil kali bilangan – bilangan pada baris kunci yang lama dengan rasio tetap. Dimana rasio tetap adalah hasil bagi bilangan pada baris yang lama di dalam kolom kunci dengan bilangan kunci. Letakkan hasil ini pada posisi yang sama pada tabel berikutnya. Gunakan transformasi ini untuk semua baris – baris yang bukan kunci.
4.
Mencari program optimal Ulangi kembali langkah 3.b dan 3.c sampai suatu program optimal dicapai.
2.3.5. Nilai Fungsi Tujuan Nilai fungsi tujuan menunjukkan maksimasi keuntungan, dengan hasil perhitungan reduced cost, slack atau surplus dan dual cost. a. Reduced Cost Jika variable keputusan mempunyai solusi optimal nol, maka reduced cost akan menunjukkan besarnya biaya minimum per unit variable yang harus
29
ditingkatkan agar solusi optimal untuk variable keputusan tersebut bernilai positif (menjadi variable basic). Jika nilai keputuasn positif (variable basic), maka nilai reduced cost akan selau nol. Initinya, reduced cost ini menunjukkan besarnya nilai minimum suatu variable non basic yang harus ditingkatkan untuk menjadi variable basic. b. Slack atau Surplus Niali slack menunjukkan kelebihan kapasitas yang ada setelah nilai optimal didapat serta menunjukkan status kendala terbatas atau berlebih. Kendala terbatas adalah kendala yang mempunyai harga slack sama dengan nol, yang berarti bahwa semua kapasitas yang ada pada kendala tersebut telah penuh. Sedangkan kendala berlebih adalah kendala yang mempunyai harga slack positif, yang berarti bahwa terdapat kelebihan kapasitas pada kendala tersebut. c. Dual Cost Menunjukkan besarnya kenaikan atau penurunan nilai tujuan yang disebabkan oleh kenaikan 1 unit kapasitas kendala terbatas
2.3.6. Daerah Batasan Basis Tidak Berubah Daerah batasan ini menunjukkan kenaikan atau penurunan besarnya nilai yang diperoleh agar solusi tetap optimal dan fesible. Pada bagian ini dibahas mengenai analisis sensifitas untuk: 1. Koefisien fungsi tujuan
30
Sasaran analisis sensifitas untuk koefisien fungsi tujuan adalah menentukan kisaran fariasi dalam setiap koefisien fungsi tujuan yang akan membuat titik sudut optimal saat ini tetap tidak berubah (L. Winston Wayne, 1993:196) 2. Daerah ruas kanan Masalah ini berkaitan dengan studi sensifitas dari pemecahan optimal terhadap perubahan dalam sisi kanan batasan. Sasaran spesifik dari masalah ini adalah untuk menentukan perubahan dalam sisi kanan batas terhadap nilai optimum dengan tetap mempertahankan feasibilitas (L. Winston Wayne, 1993:198)
2.3.7. Peraturan 100% Untuk Perubahan Nilai Secara Simultan 1. Perubahan Koefisien Fungsi Tujuan Peraturan 100% ini mempertimbangkan 2 kondisi, yaitu: a. Semua variabel yang nilai koefisien fungsi tujuannya diubah memiliki nilai reduced cost ≠ 0. b. Setidaknya satu variabel yang niali koefisien fungsi tujuannya diubah memiliki nilai reduced cost = 0 (L. Winston Wayne, 1993:262) Pada kondisi ke-1, optimalitas tetap dapat dipertahankan jika dan hanya jika perubahan koefisien fungsi tujuan masih dalam range perubahan yang diizinkan. Pada kondisi ke-2, peraturan 100% diberlakukan dengan perhitungan rasio sebagai berikut:
31
∆cj ≥ 0,
rj = ∆cj / Ij
∆cj ≥ 0,
rj = -∆cj / Dj
Dimana:
∆cj
= Koefisien fungsi tujuan dari X1
∆cj
= Selisih dari nilai cj baru dengan niali cj awal
Ij
= Perubahan nilai cj maksimum yang diperbolehkan
Dj
= Perubahan nilai cj minimum yang diperbolehkan
Kondisi optimalitas dari perubahan simultan yang dilakukan terhadap koefisien fungsi tujuan masih dapat dipertahankan, jika nilai ∑ r j ≤ 1 2. Perubahan Daerah Ruas Kanan Peraturan 100% ini mempertimbangkan 2 kondisi, yaitu: a. Semua kendala yang nilai daerah ruas kanannya dimodifikasi merupakan kendala berlebih. b. Setidaknya satu kendala yang nilai ruas kanannya dimodifikasi merupakan kendala terbatas (L. Winston Wayne, 1993:265).
∆bj ≥ 0,
rj = ∆bj / Ij
∆bj ≥ 0,
rj = -∆bj / Dj
Dimana:
∆bj
= Nilai daerah ruas kanan dari persamaan ke-j
∆bj
= Selisih dari nilai bj baru dengan niali bj awal
32
Ij
= Perubahan nilai cj maksimum yang diperbolehkan
Dj
= Perubahan nilai cj minimum yang diperbolehkan
Kondisi optimalitas dari perubahan simultan yang dilakukan terhadap koefisien fungsi tujuan masih dapat dipertahankan, jika nilai ∑ r j ≤ 1
2.3.8. Kasus-kasus Khusus Dalam Aplikasi Metode Simpleks
Dalam metode simpleks terdapat beberapa kasus khusus, yaitu: 1. Degenerasi Jika dalam metode simpleks terdapat minimal 2 rasio minimum yang sama, sehingga dapat dipilih secara sembarang untuk mentukan variabel keluar, Tetapi ketika hal tersebut terjadi, satu variabel dasar atau lebih pasti akan sama dengan nol dalam iterasi berikut. Dalam kasus ini, pemecahan baru tersebut adalah degenerasi. Secara teoritis, degenerasi memiliki dua implikasi, yaitu: a. Berkaitan dengan fenomena perputaran (Cycling) dimana prosedur simpleks akan mengulang urutan iterasi yang sama tampa pernah memperbaiki tujuan dan tidak pernah mengakhiri perhitungan. b. Penerapan prosedur simpleks yang dapat memberi kemungkinan terdapat perbedaan dalam mengklasifikasi variabel sebagai variabel dasar dan non dasar akan memberikan nilai identik untuk semua variabel dan nilai fungsi tujuan (Hamdy A. Taha, 1993:87).
33
2. Alternatif optimal Ketika fungsi tujuan adalah sejajar dengan satu batasan yang mengikat, maka fungsi tujuan akan memiliki nilai optimal yang sama di lebih dari satu titik sudut. Kerena alasan tersebut, pemecahan ini disebut alternatif optimal (Hamdy A. Taha, 1993:90). Dalam penerapan metode simpleks kasus alternatif optimal ini dapat diidentifikasikan permasalahannya dengan melihat tabel iterasi metode simpleks, dengan ciri-ciri damana nilai koefisien variable non basic dalam persamaan x adalah sebesar nol. Pengetahuan tentang alternatif optimal adalah berguna, karena hal ini memberikan kesempatan bagi manajemen untuk memilih pemecahan yang paling sesuai dengan situasi tampa mengalami penurunan nilai tujuan. 3. Pemecahan yang tidak dibatasi Dalam beberapa model Linear Programmning, nilai variabael dapat menigkat secara tidak terbatas tanpa melanggar salah satu batasan, yang berarti bahwa ruang pemecahan tidak dibatasi (underbounded) dalam setidaknya satu arah. Akibatnya, nilai fungsi tujuan dapat meningkat (kasus maksimasi) atau menurun (kasus minimasi) secara tidak terbatas (Hamdy A. Taha, 1993:92). Pada kasus ini dapat dikatakan bahwa baik ruang pemecahan maupun nilai fungsi tujuan optimal tidak dibatasi. Pada kasus pemecahan yang tidak dibatasi dapat segera diidentifikasi dari iterasi table simpleks, dimana semua koefisien pembatas pada kandidat kolom kunci bernilai negatif atau nol. 4. Pemecahan tidak ada (tidak layak)
34
Jika batasan tidak dapat dipenuhi secara simultan, model tersebut dikatakan tidak memiliki pemecahan yang layak ≤ (dengan asumsi konstanta sisi kanan yang nonnegatif), karena variable slack selalu memberikan pemecahan yang layak. Tetapi ketika menggunakan variable artificial yang berdasarkan pada rancangannya sendiri tidak memberikan pemecahan yang layak untuk model semula. Ketentuan pinalti untuk memaksa variable artificial bernilai nol di pemecahan optimal menyebabkan model memiliki ruang layak (Hamdy A. Taha, 1993:93). Jika tidak memiliki pemecahan yang layak ditandai dengan ciri-ciri dimana setidaknya satu variabel artificial bernilai positif di iterasi tabel simpleks optimal.
