BAB 2 LANDASAN TEORI
2.1 Definisi 2.1.1 Pembelian Menurut Kamus Besar Bahasa Indonesia Kontemporer, pembelian didefinisikan sebagai proses, pembuatan, atau cara membeli. Sedangkan Philip Kotler (2000, p218) dalam bukunya Manajemen Pemasaran, mengutip dari Webster dan Wind, mendefinisikan pembelian organisasional sebagai proses pengambilan keputusan yang dilakukan oleh organisasi formal untuk menetapkan kebutuhan akan barang dan jasa yang perlu dibeli untuk mengidentifikasi, mengevaluasi, dan memilih diantara alternatif merek dan pemasok.
2.1.2 Bahan Baku Menurut Kamus Besar Bahasa Indonesia Kontemporer, bahan baku adalah bahan yang digunakan dalam industri untuk diolah melalui proses produksi menjadi barang jadi. Sedangkan menurut McCarthy (1996, p198), bahan baku adalah barang pengeluaran yang belum diolah yang diangkut kedalam proses produksi dengan sedikit penanganan.
2.1.3 Pembelian Bahan Baku Jika digabungkan dari dua definisi di atas maka pembelian bahan baku adalah cara membeli bahan yang akan digunakan untuk diolah menjadi produk.
7 2.1.4 Optimasi Menurut Hamdy A. Taha (2003, p3), optimal adalah sebuah nilai yang memenuhi fungsi tujuan dan memenuhi segala persyaratan atau kendala yang terlibat.
2.2 Pemodelan Pada Riset Operasi Hamdy A. Taha (2003, p3) menuliskan bahwa dalam pemodelan riset operasi melibatkan 3 hal yaitu variabel keputusan, fungsi tujuan, dan kendala-kendala atau batasan-batasan. Secara umum akan ditulis dalam bentuk berikut : Maksimalkan atau minimalkan fungsi tujuan dengan kendala batasan-batasan Pada format diatas tidak terlihat variabel keputusan, tapi sebenarnya batasan-batasan dan fungsi tujuan itu terbentuk dari kumpulan variabel keputusan.
2.3 Tahapan Pemodelan Pada Riset Operasi Menurut Hamdy A. Taha (2003, p8), dalam melakukan pemodelan ada beberapa tahapan yang harus dilalui, yaitu : 1. Mendefinisikan permasalahan Pendefinisian permasalahan melibatkan pendefinisian ruang lingkup dari permasalahan yang akan diselesaikan. Hasil dari tahap ini berupa penjelasan dari keputusan-keputusan yang mungkin, penentuan fungsi tujuan, dan spesifikasi serta batasan-batasan dari model.
8 2. Membuat pemodelan Setelah pendefinisian dari permasalahan yang dihadapi dirumuskan maka pada tahap ini dilakukan pengubahan dari permasalahan yang telah didefinisikan tersebut kedalam bentuk matematikanya. 3. Membuat penyelesaian dari model Pada tahap ini, setelah permasalahan dimodelkan kedalam bentuk pemodelan matematika maka harus diputuskan algoritma optimalisasi apa yang akan digunakan. 4. Membuat validitas dari model Pada tahap ini, hasil dari penyelesaian pemodelan akan diperiksa apakah sudah cocok dengan permasalahan yang pada tahap 1 telah didefinisikan. Dengan kata lain, pada tahap ini diperiksa apakah penyelesaian yang dihasilkan dapat diterima atau tidak masuk akal. 5. Implementasi Tahap ini adalah penerapan penyelesaian dari model yang tervalidasi kedalam sistem yang lebih besar, misalnya diterapkan didalam sistem yang ada pada perusahaan.
2.4 Gambaran Umum Metode Pada
metode
simpleks,
untuk
permasalahan
primalnya
membutuhkan
penyelesaian dasar primal layak, untuk permasalahan dual simpleks membutuhkan penyelesaian dasar dual layak, sedangkan jika didapati permasalahan-permasalahan yang bukan primal layak atau pun dual layak, maka permasalahan itu diselesaikan dengan
9 mengganti permasalahannya, dengan cara menambahkan variabel buatan yang melalui variabel tersebut ketika didapati penyelesaian optimalnya akan bersesuaian dengan permasalahan sebelum diganti. Stanley Zionts, penemu metode Criss-Cross, dalam tulisannya berjudul The Criss-Cross Method for Solving Linear Programming Problems (1969, p426) mengatakan bahwa permasalahan yang diganti akan membutuhkan waktu yang lebih untuk mendapatkan penyelesaiannya dibanding dengan permasalahan dengan ukuran yang serupa yang telah memiliki penyelesaian dasar primal layak atau dual layak. Metode Criss-Cross adalah sebuah algoritma primal-dual untuk menyelesaikan permasalahan
pemograman
linear.
Bedanya,
metode
Criss-Cross
tidak
perlu
menggunakan penggantian permasalahan untuk mendapatkan penyelesaian dasarnya, entah itu berupa penyelesaian dasar primal atau penyelesaian dasar dual. Jika penyelesaian dasar berupa primal layak atau dual layak maka akan digunakan metode simpleks terkait. Maksudnya, jika penyelesaian dasar berupa primal layak maka digunakan metode primal simpleks sedangkan untuk penyelesaian dasar berupa dual layak maka digunakan metode dual simpleks. Pengembangan dari metode Criss-Cross, menurut Stanley Zionts, dengan menggunakan kriteria primal dan kriteria dual dalam memilih iterasi adalah lebih baik jika dibandingkan dengan menggunakan salah satunya saja yang dikombinasikan dengan penggunaan variabel buatan (1969, p426). Beliau juga menyertakan pembuktiannya dalam tulisan yang terpisah berjudul Some Empirical Tests of The Criss-Cross Method yang dipublikasikan beberapa tahun kemudian (Zionts S., 1972, p406-410). Metode Criss-Cross, sesuai kriteria yang cocok, akan secara bergantian melakukan iterasi primal dan iterasi dual sampai penyelesaian dasar primal layak didapat
10 atau penyelesaian dasar dual layak didapat. Lalu dengan menggunakan iterasi tersebut, akan tercapai keadaan dimana penyelesaiannya berupa primal dan dual layak. Ketika penyelesaian itu didapatkan maka penyelesaian optimal telah didapatkan.
2.5 Pilar Metode Criss-Cross 2.5.1 Teori Dualitas Berikut adalah bentuk umum dari permasalahan primal : n
Maksimalkan Z = ∑ c j x j , j =1
dengan kendala n
∑a j =1
ij
x j ≤ bi , untuk i = 1, 2, ..., m
dan
x j ≥ 0, untuk j = 1, 2, ...., n
Sedangkan bentuk umum dari permasalahan dual terkait dari permasalahan primal diatas adalah : m
Minimalkan
y 0 = ∑ bi yi , i =1
dengan kendala m
∑a i =1
ij
y i ≥ c j , untuk j = 1, 2, ..., n
dan y i ≥ 0, untuk i = 1, 2, ..., m
11 2.5.2 Hubungan Primal-Dual
Berikut adalah tabel yang menyatakan hubungan antara primal dan dual untuk mempermudah melihat hubungan diantaranya.
Koefisien dari . . .
x1
x2
a11 a21
a21 a22
. .
am1
am2
.
VI c1
VI c2
.
. . . . . .
.
xn
. .
a1n a2n
.
amn
.
VI cn
Ruas Kanan ≤ b1 ≤ b2 . . . ≤ bn
Koefisien Fungsi Tujuan (Memaksimumkan)
Koefisien dari
y1 y2 . . . ym Ruas Kanan
Masalah Dual
Masalah Primal
Koefisien Fungsi Tujuan (Memaksimumkan) Tabel 2.1 Hubungan Primal-Dual Dari tabel diatas terlihat bahwa bentuk primal dapat dilihat secara horisontal sedangkan bentuk dual dapat dilihat dengan cara vertikal. Tabel 2.1 diatas akan mempermudah dalam proses iterasi criss-cross nantinya terutama dalam menentukan : 1. apakah basis sudah dalam bentuk primal layak 2. atau basis sudah dalam bentuk dual layak 3. atau basis sudah dalam bentuk primal layak dan dual layak 4. atau basis bukan dalam bentuk primal layak dan dual layak.
12 2.5.3 Keadaan Primal Layak
Keadaan primal layak tercapai ketika seluruh ruas kanan pada masalah primal berada dalam nilai positif. Perhatikan pada tabel 2.1 bahwa permasalahan primal dapat dilihat secara horisontal. Perhatikan juga bahwa ruas kanan pada permasalahan primal adalah koefisien dari fungsi tujuan dari permasalahan dual.
2.5.4 Keadaan Dual Layak
Keadaan dual layak tercapai ketika seluruh ruas kanan pada masalah dual berada dalam nilai positif. Perhatikan pada tabel 2.1 bahwa permasalahan dual dapat dilihat secara vertikal. Perhatikan juga bahwa ruas kanan pada permasalahan dual adalah koefisien dari fungsi tujuan dari permasalahan primal.
2.6 Metode Criss-Cross
Metode criss-cross menggunakan representasi tabel simpleks. Sebuah variabel akan diasosiasikan dengan kolom jika merupakan variabel bukan dasar dan diasosiasikan dengan baris jika merupakan variabel dasar. Tidak membutuhkan variabel buatan ditambahkan kedalam permasalahan. Kendala pertidaksamaan dari bentuk
∑a j∈J
ij
x j ≥ bi ,
bi > 0 . diubah menjadi bentuk
∑− a j∈J
ij
x j ≤ −bi .
13 Setelah itu nilai-nilainya dimasukkan ke dalam basis.
Misalkan permasalahan diekspresikan sebagai berikut : Minimalkan
− c1 x1 + c 2 x 2
Dengan kendala
A11 x1 + A12 x 2 ≤ −b1
T
T
A21 x1 + A22 x 2 ≤ b2 x1 , x 2 ≥ 0
(1)
Keterangan :
A11 adalah matriks partisi berukuran m1 x n1, A12 adalah matriks partisi berukuran m2 x n1, A21 adalah matriks partisi berukuran m2 x n1, A22 adalah matriks partisi berukuran m2 x n2, m adalah bilangan dari variabel dasar, n adalah bilangan dari variabel non dasar.
Jika memperhatikan hubungan primal dan dual dalam sebuah permasalahan, seperti yang ditunjukkan pada tabel 2.1, maka bentuk primal dari permasalahan (1) adalah Minimalkan
− c1 x1
Dengan kendala
A21 x1 + A22 x 2 ≤ b2
T
x1 , x 2 ≥ 0
(2)
sedangkan bentuk dual dari permasalahan (1) adalah Minimalkan
+ c2 x2
Dengan kendala
A12 x 2 ≤ −b1
T
A22 x 2 ≤ b2 x2 ≥ 0
(3)
14 Pelaksanaan iterasinya dilakukan tergantung jenis iterasinya, primal atau dual, dimana x1 dan x2 mewakili variabel bukan dasar dan variabel slack yang tidak ditulis adalah variabel dasar. Perlu diketahui bahwa variabel dasar yang tidak ditulis adalah variabel slack terkait matriks yang telah diperbaharui tetapi tidak untuk permasalahan aslinya. Algoritma criss-cross menggunakan iterasi primal dan dual secara bergantian. Disebut iterasi primal yaitu dari permasalahan (2) di atas dilakukan iterasi simpleks primal dan kemudian melakukan pivot berdasarkan permasalahan (1). Disebut iterasi dual yaitu permasalahan (3) di atas dilakukan iterasi simpleks dual dan kemudian melakukan pivot berdasarkan permasalahan (1). Iterasi ini terus dilakukan hingga didapati penyelesaian primal layak atau penyelesaian dual layak. Jika penyelesaian primal layak telah didapati maka hanya iterasi simpleks primal yang dilakukan hingga dicapai penyelesaian optimal. Demikian juga jika penyelesaian yang didapati adalah penyelesaian dual layak maka hanya iterasi simpleks dual yang dilakukan hingga dicapai penyelesaian optimal. Cara melakukan penghitungan iterasi mirip dengan penghitungan iterasi yang ada pada metode simpleks, tetapi berbeda! Pada metode simpleks, setelah didapat baris pivot dan kolom pivot maka elemen-elemen baru pada basis yang baru menggunakan rumus berikut : elemen baru basis = elemen lama basis + baris pivot x koefisien kolom pivot Pada metode criss-cross juga akan menggunakan penghitungan yang demikian, bedanya terdapat pada nilai yang ada pada elemen pivot, nilai yang ada pada elemen-elemen baris pivot, dan nilai yang ada pada elemen-elemen kolom pivot. Berikut adalah penentuan
15 nilai pada elemen-elemen yang ada pada baris pivot maupun kolom pivot dan elemen pivot itu sendiri : Elemen pivot : elemen pivot baru = 1 / elemen pivot lama Baris pivot : Untuk iterasi primal : elemen baris pivot baru = elemen baris pivot lama x 1 x elemen pivot baru Untuk iterasi dual : elemen baris pivot baru = elemen baris pivot lama x -1 x elemen pivot baru Kolom pivot : Untuk iterasi primal : elemen baris pivot baru = elemen baris pivot lama x -1 x elemen pivot baru Untuk iterasi dual : elemen baris pivot baru = elemen baris pivot lama x 1 x elemen pivot baru
Jika iterasi telah mencapai 2m + 2n dan iterasi masih belum mencapai penyelesaian primal layak atau dual layak maka digunakan kendala regularisasi. Yang dilakukan adalah melakukan iterasi primal saja hingga didapati dual layak. Setelah itu dilakukan iterasi dual sampai didapati penyelesaian optimal didapati atau penyelesaian tidak berbatas didapati. Kendala regularisasi dikatakan tidak terikat bila penyelesaian optimal didapati dan kendala regularisasi dikatakan berikat bila penyelesaian yang didapati adalah penyelesaian tidak berbatas (jika dapat digambarkan dalam grafik, maka penyelesaian bukan berupa titik melainkan daerah).
16 Contoh : Berikut contoh permasalahan yang akan diselesaikan dengan metode criss-cross : Minimalkan
− 3 x1 + 4 x 2
Dengan kendala
x1 + 2 x 2 ≥ 2
3 x1 + x 2 ≥ 4 x1 − x 2 ≤ 1 x1 + x 2 ≤ 3
Penyelesaian : Pada kendala pertama, ditemukan x1 + 2 x 2 ≥ 2 ,
maka yang harus dilakukan adalah mengubahnya kedalam bentuk − x1 − 2 x 2 ≤ −2 .
Demikian juga diberlakukan pada kendala kedua, karena juga ditemukan bentuk pertidaksamaan 3 x1 + x 2 ≥ 4 ,
harus diubah kedalam bentuk − 3 x1 − x 2 ≤ −4 .
Sekarang semua kendala telah siap untuk dimasukkan kedalam basis. Yang dimasukkan kedalam basis adalah semua koefisien yang ada dari fungsi tujuan dan juga kendala. Basis akan berupa sebagai berikut sebagai keadaan awalnya :
17 X1
X2
Z
-3
4
0
X3
-1
-2
-2
X4
-3
-1
-4
X5
1
-1
1
X6
1
1
3
Terlihat dari basis diatas bahwa permasalahan belum dalam bentuk primal layak atau dual layak. (Untuk penjelasan apa yang dimaksud dengan primal layak atau dual layak ada pada sub bab 2.5 tentang pilar metode criss-cross). Jadi untuk iterasi pertama, bebas dipilih apakah iterasi primal atau iterasi dual. Pada contoh ini akan dimulai dengan iterasi dual terlebih dahulu. Untuk memulai dengan iterasi dual maka yang pertama harus dilakukan adalah mencari ruas kanan pada permasalah primal yang bernilai lebih kecil dari nol yang paling kecil. Maka akan didapat baris X4 sebagai baris pivot. Untuk penentuan kolom pivot, harus dicari nilai positif pada fungsi Z dan hasil baginya dengan nilai mutlak elemen yang ada pada baris pivot harus bernilai paling kecil. Maka akan didapat X2 sebagai kolom pivot. Setelah didapati kolom pivot dan baris pivot maka didapatlah elemen pivot. Elemen pivot adalah elemen dimana bertemunya baris pivot dan kolom pivot. Disini akan dilakukan pivot yang mirip dengan metode simpleks namun tidak sama. Perbedaannya terdapat pada elemen pivot pada basis yang baru bernilai satu dibagi elemen pivot yang lama. Disini dimulai iterasi pertama. Maka sekarang basis seperti ini :
18 Iterasi pertama : X1
X4
Z X3 X2
-1
X5 X6
Elemen pivot yang baru seolah tidak mengalami perubahan apa-apa, padahal nilai elemen pivot yang baru tersebut adalah hasil perhitungan dari 1 dibagi elemen pivot lama (yaitu -1) sehingga bernilai -1. Untuk pengisian elemen-elemen yang lain, karena iterasi yang digunakan adalah itearsi dual maka seluruh baris pivot yang lama akan dikalikan dengan -1 dan untuk kolom pivot dikalikan dengan 1, sehingga menjadi : X1
X4
Z
4
X3
-2
X2
3
-1
X5
-1
X6
1
4
Untuk elemen-elemen yang lain yang belum terisi, akan digunaka iterasi sebagaimana penghitungan elemen yang terdapat pada metode simpleks yaitu dengan rumus seperti yang terdapat pada sub bab 2.6. Dengan demikian, basis akan seperti ini :
19 X1
X4
Z
-15
4
-16
X3
5
-2
6
X2
3
-1
4
X5
4
-1
5
X6
-2
1
-1
Dengan didapatnya basis seperti diatas maka selesailah iterasi pertama. Basis masih belum dalam bentuk primal layak atau dual layak berarti iterasi berikutnya harus digunakan iterasi berselingan dengan iterasi sebelumnya. Karena iterasi sebelumnya menggunakan iterasi dual maka pada iterasi kedua harus digunakan iterasi primal. Untuk penentuan kolom pivot pada iterasi primal, pertama-tama adalah mencari nilai koefisien dari fungsi tujuan yang negatif yang paling kecil. Akan didapati nilai -15. Ini berarti bahwa X1 akan menjadi kolom pivot. Untuk menentukan baris pivot pada iterasi primal, harus didapati nilai paling minimum dari hasil bagi antara ruas kanan yang tidak negatif dengan elemen yang ada pada kolom pivot yang dimutlakkan nilainya. Akan didapati bahwa X3 akan menjadi baris pivot. X3 menjadi baris pivot karena nilainya paling kecil (6/5) jika dibandingkan dengan yang lainnya (4/3, 5/4). Didapatlah elemen pivot dan seperti yang sudah tertera pada sub bab 2.6 dalam mencari nilai elemen-elemen pada baris pivot dan kolom pivot, maka keadaan awal untuk iterasi kedua adalah berikut :
20 Iterasi kedua : X3 Z
3
X1
1/5
X2
-3/5
X5
-4/5
X6
2/5
X4
-2/5
6/5
Jika iterasi dilanjutkan maka selesailah iterasi kedua dengan keadaan akhir sebagai berikut : X3
X4
Z
3
-2
2
X1
1/5
-2/5
6/5
X2
-3/5
1/5
2/5
X5
-4/5
3/5
1/5
X6
2/5
1/5
7/5
Ternyata setelah iterasi kedua selesai didapati basis dalam keadaan primal layak. Oleh karena itu iterasi yang berikutnya hingga didapati basis primal layak dan dual layak akan terus menerus dilakukan iterasi primal. Dengan melakukan cara yang sama maka akan didapati kolom X4 sebagai kolom pivot dan X5 sebagai baris pivot. Berikut adalah basis yang menjadi keadaan awal untuk iterasi ketiga :
21 Iterasi ketiga : X3
X5
Z
10/3
X1
2/3
X2
-1/3
X4
-4/3
X6
5/3
1/3
-1/3
Jika iterasi dilanjutkan maka akan didapatkan basis sebagai berikut : X3
X5
Z
1/3
10/3
8/3
X1
-1/3
2/3
4/3
X2
-1/3
-1/3
1/3
X4
-4/3
5/3
1/3
X6
2/3
-1/3
4/3
Setelah iterasi ketiga ternyata basis sudah dalam bentuk primal layak dan dual layak. Artinya, solusi optimal telah tercapai. Solusi optimal dapat langsung dilihat hasilnya dengan cara melihat nilai ruas kanan dari fungsi objektif yaitu 8/3. 2.7 Flow Chart Metode Criss-Cross
Berikut adalah keterangan simbol-simbol dari flow chart : Permasalahan : Minimisasi
∑c j∈J
j
xj
22 dengan kendala
∑a j∈J
ij
x j ≤ bi (i ∈ I )
x j ≥ 0( j ∈ J )
dan
aij
— elemen dari matriks pemrograman linear
bi
— nilai sisi kanan sekarang dari baris ke i
cj
— nilai harga yang disederhanakan dari variabel pada kolom ke j
i
— indeks baris, anggota dari I
I
— rangkaian baris, rangkaian variabel dasar
IDSW — tanda untuk menandakan solusi tidak layak jika solusi bukan primal layak dan bukan dual layak IDUAL— tanda untuk menandakan apakah solusi dual layak. Jika dual layak maka IDUAL bernilai 1, sebaliknya jika tidak IDUAL bernilai 0 IPRIM — tanda untuk menandakan apakah solusi primal layak. Jika primal layak maka IPRIM bernilai 1, sebaliknya jika tidak IPRIM bernilai 0 j
— indeks kolom, anggota dari J
J
— rangkaian kolom, rangkaian variabel bukan dasar
k
— kolom dari variabel berikutnya
L
— indeks kolom atau baris
m
— jumlah dari variabel dasar
n
— jumlah dari variabel non dasar
r
— baris dari variabel yang keluar
IT
— penghitung iterasi dan tanda khusus untuk dipakai dalam kekonvergennan
M
— bilangan bulat positif besar yang cukup
23
Langkah Persiapan
Mulai
Hasilkan penyelesaian dasar dari permasalahan
Masukkan variabel dasar kedalam setiap kendala
Masukkan setiap variabel linear independen yang tidak dibatasi oleh tanda kedalam kendala
Masukkan nilai-nilai dari variabel dasar dan variabel non dasar
Atur nilai m dan n
IDSW = 0 IDPRIM = 0 IDUAL = 0
Pilih Jalur Primal?
Inisialisasi penanda
Yes
7
Untuk iterasi pertama, bebas memilih iterasi primal atau iterasi dual
No
Langkah iterasi dual
1
Atur r sehingga br = min(bj)
Pilih sisi kanan paling kecil Inisialisasi indeks baris L
L=0
br < 0?
No 3
Yes
2
Apakah sisi paling kanan bernilai negatif?
24
2
Menentukan variabel masuk untuk iterasi dual
MINDL
Variabel Xk ditemukan
Berhasil
4 Gagal
10
Yes
IDUAL = 1?
Variabel Xk tidak ditemukan
Apakah penyelesaian dual layak?
No 5
L=L+1
6
Yes
L > m?
Menaikkan indeks baris L
Sudahkah semua baris diperiksa?
No
5
No
bL < 0?
Apakah sisi kanan dari baris L negatif?
Yes k=L
2
Mengatur baris ke-L sebagai baris keluar
25
26
27
28
29
30
31
32
33 2.8 Perancangan Piranti Lunak
Menurut Prahasta (2005, p223), rekaya piranti lunak adalah sekumpulan aktifitasaktifitas yang berkaitan erat dengan perancangan dan implementasi produk-produk dan prosedur-prosedur yang dimaksudkan untuk merasionalisasikan produksi perangkat lunak berikut pengawasannya. Model yang digunakan adalah model waterfall, sebuah model yang bersifat terstruktur dan linear sehingga pendekatan yang digunakan berupa pendekatan sistematis dan berurutan (sequential) dalam pengembangan piranti lunak. Berikut adalah gambaran model waterfall :
Rekayasa Sistem
Analisis
Perancangan
Pemrograman
Pengujian
Operasi dan Pemeliaharaan
Gambar 2.1 Model Perancangan Waterfall
34
Berikut adalah penjelasan dari gambar diatas : 1. Rekayasa sistem Merupakan sebuah bagian dari sistem yang besar yang merupakan pengembangan dari semua kebutuhan elemen-elemen. Hasil dari tahap ini adalah spesifikasi sistem. 2. Analisis Pada tahap ini dilakukan pengumpulan semua yang menjadi kebutuhankebutuhan. Hasil dari tahap ini adalah spesifikasi dari kebutuhan piranti lunak. 3. Perancangan Pada tahap ini spesifikasi kebutuhan piranti lunak diubah kedalam bentuk arsitektur piranti lunak 4. Pemrograman Penulisan dan pembuatan program dilakukan. 5. Pengujian Pada tahap ini piranti lunak diintegrasikan dengan sistem secara keutuhan. 6. Operasi dan Pemeliharaan Pada tahap ini dilakukan perbaikan jika piranti lunak ditemukan bug atau error.
