BAB 2 LANDASAN TEORI
2.1
Model Matematika Model matematika adalah suatu rumusan matematika (dapat berbentuk
persamaan, pertidaksamaan, atau fungsi) yang diperoleh dari hasil penafsiran seseorang ketika menerjemahkan suatu masalah ke dalam bahasa matematika.
2.2
Pengoptimalan Dalam kamus besar bahasa Indonesia, mengoptimalkan diartikan sebagai proses,
cara, perbuatan untuk menjadikan paling baik, paling tinggi, paling menguntungkan, dan sebagainya. Hasil dari pengoptimalan tersebut disebut hasil yang optimal.
2.3
Masalah Pengoptimalan Menurut Bronson (1997,p1), suatu pengoptimalan menentukan suatu kuantitas
maksimal atau minimal yang spesifik yang disebut objektif, tergantung pada suatu bilangan terhingga atau variabel input. Variabel–variabel tersebut dapat berdiri sendirisendiri atau berkaitan satu sama lain melalui satu atau beberapa kendala (constraint).
2.4
Pemrograman Linier Pemrograman linier (linear programming) merupakan suatu bentuk model
matematika yang dapat digunakan untuk memecahkan masalah pengoptimalan. Menurut Subagyo et al. (1995,p9) pemrograman linier merupakan suatu model umum yang dapat
5
6 digunakan dalam pemecahan masalah pengalokasian sumber–sumber yang terbatas secara optimal. Masalah yang timbul bila seseorang diharuskan memilih atau menentukan tingkat setiap kegiatan yang harus dilakukannya, di mana masing–masing kegiatan membutuhkan sumber yang sama sedangkan jumlahnya terbatas. Sebagai contoh bagian produksi suatu perusahaan yang dihadapkan pada penentuan tingkat produksi masing–masing jenis barang dengan memperhatikan batasan faktor–faktor produksi seperti mesin, tenaga kerja, bahan mentah, dan sebagainya. Tujuannya adalah memperoleh tingkat keuntungan maksimal atau biaya yang minimal. Seperti yang disebutkan dalam contoh di atas, dalam pemrograman linier terdapat kendala–kendala atau batasan–batasan yang perlu diperhatikan, yang dapat diterjemahkan ke dalam bentuk pertidaksamaan linier. Setiap kendala atau batasan memiliki peubah–peubah yang nilai–nilainya memenuhi sistem pertidaksamaan linier yang dirumuskan ke dalam fungsi kendala atau fungsi batasan. Dari berbagai kemungkinan tersebut terdapat sebuah penyelesaian yang lebih memberikan hasil terbaik, yaitu hasil yang optimal. Jadi, pemrograman linier bertujuan mengoptimalkan suatu fungsi objektif dengan memperhatikan fungsi–fungsi kendala yang ada. Dengan demikian, suatu persoalan disebut persoalan pemrograman linier apabila memenuhi (Supranto,1983,p4) : 1. Adanya tujuan (objektif) yang akan dicapai yang harus dinyatakan dalan bentuk fungsi linier yang disebut fungsi tujuan (fungsi objektif). 2. Adanya alternatif pemecahan yang membuat nilai fungsi tujuan optimal (laba yang maksimum, biaya yang minimum, dan sebagainya) yang harus dipilih. 3. Adanya keterbatasan sumber–sumber yang tersedia (bahan baku, modal, tempat penyimpanan barang, dan sebagainya) yang dapat dinyatakan dalam
7 bentuk pertidakasamaan linier (linier inequality) yang disebut fungsi kendala (fungsi batasan).
2.5
Metode Simpleks Pada saat ini masalah–masalah linear programming yang melibatkan banyak
variabel–variabel keputusan (decision variable) dapat dengan cepat dipecahkan dengan bantuan komputer. Bila variabel keputusan yang dikandung tidak terlalu banyak masalah tersebut dapat diselesaikan dengan suatu algoritma yang biasanya sering disebut metode simpleks tabel. Disebut demikian karena kombinasi variabel keputusan yang optimal dicari menggunakan tabel–tabel. Persoalan harus dinyatakan dalam bentuk standar, lalu dilakukan langkahlangkah sebagai berikut. Langkah 1: Mengubah fungsi dan tujuan batasan–batasan Fungsi tujuan diubah menjadi fungsi implisit, artinya semua CjXij digeser ke kiri. Misalnya fungsi tujuan pada contoh sebelumnya Z = 3X1 + 5X2 diubah menjadi Z – 3X1 – 5X2 = 0. Pada bentuk standar semua batasan mempunyai tanda lebih kecil sama dengan. Ketidaksamaan ini harus diubah menjadi kesamaan. Caranya dengan menambah slack variable. Variabel slack ini adalah Xn+1, Xn+2, …..Xn+m. Karena tingkat atau hasil kegiatan diwakili oleh X1 dan X2, maka variabel slack dimulai dari X3, X4 dan seterusnya sebagai berikut. 1) 2X1
< 8
menjadi 2X1 + X3 = 8
2) 3X2
< 15 menjadi 3X2 + X4 = 15
3) 6X1
< 30 menjadi 6X1
+ X5 = 30
8 Berdasarkan perubahan persamaan–persamaan di atas dapat disusun formulasi yang telah diubah itu, sebagai berikut. Fungsi tujuan : Maksimumkan Z – 3X1 – 5X2 Batasan–batasan (fungsi kendala) : 1) 2X1
+
2)
3X2
3) 6X1
+
X3 +
= X4
5X2
=
15
+X5
=
8
30
Langkah 2: menyusun persamaan–persamaan di dalam tabel Setelah formulasi diubah, kemudian disusun ke dalam suatu tabel, yaitu tabel simpleks berikut. Tabel 2.1 Tabel dasar simpleks Sumber: Dasar-dasar operations research (Subagyo,p.35) Variabel Dasar
Z
X1
X2 …….. Xn
Xn+1
Xn+2 …….. Xn+m
NK
Z
1
-C1
-C2 ……... -Cn
0
0 …………. 0
0
Xn+1
0
a11
a12 …….. a1n
1
0 ………….. 0
b1
Xn+2
0
a21
a22 ……… a2n
0
1 ………….. 0
b2
Xn+m
0
am1
am2 ……... amn
0
0 …………. 1
bm
NK adalah nilai kanan persamaan, yaitu nilai di belakang tanda sama dengan (=). Untuk kendala 1 sebesar 8, kendala 2 sebesar 15, dan kendala 3 sebesar 30. Variabel dasar adalah variabel yang nilainya sama dengan sisi kanan dari persamaan. Pada persamaan 2X1 + X3 = 8, kalau belum ada kegiatan apa–apa, berarti nilai X1 = 0, dan semua kapasitas masih menganggur. Pengangguran ada 8 satuan, atau nilai X3 = 8. pada
9 tabel tersebut. Nilai variabel dasar (X3, X4, X5) pada fungsi tujuan pada tabel permulaan ini harus 0, dan nilainya pada kendala-kendala bertanda positif. Contoh: data dalam tabel simpleks yang pertama Tabel 2.2 Tabel simpleks ke-1 Sumber: Dasar-dasar operations research (Subagyo,p.36) Variabel dasar Z X3 X4 X5
Z
X1
X2
X3
X4
X5
NK
1 0 0 0
-3 2 0 6
-5 0 3 5
0 1 0 0
0 0 1 0
0 0 0 1
0 8 15 30
Langkah 3: Memilih kolom kunci Setelah data di susun di dalam tabel kemudian diadakan perubahan–perubahan agar dapat mencapai titik optimal, dengan langkah memilih kolom kunci. Kolom kunci adalah kolom yang merupakan dasar untuk mengubah tabel di atas. Pilihlah kolom yang baris Z nya bernilai negatif dengan angka terbesar. Dalam hal ini kolom X2 dengan nilai pada baris Z adalah -5. Kemudian beri tanda segi empat pada kolom X2 .Kalau suatu tabel sudah tidak memiliki nilai negatif pada fungsi tujuan, berarti tabel ini tidak dapat dioptimalkan lagi (sudah optimal). Tabel 2.3 Tabel simpleks ke-2 Sumber: Dasar-dasar operations research (Subagyo,p.36) Variabel dasar Z X3 X4 X5
Z
X1
X2
X3
X4
X5
NK
1 0 0 0
-3 2 0 6
-5 0 3 5
0 1 0 0
0 0 1 0
0 0 0 1
0 8 15 30
Keterangan
15/3 = 15 (minimum) 30/5=6
10 Langkah 4: Memilih baris kunci Baris kunci adalah baris yang merupakan dasar untuk mengubah tabel tersebut di atas. Untuk itu terlabih dahulu dicari indeks tiap–tiap baris dengan cara membagi nilai– nilai pada kolom NK dengan nilai yang sebaris pada kolom kunci. Rumus:
Indeks =
Nilai kolom NK Nilai kolom kunci
Untuk baris kendala 1 besarnya indeks = 8/0 = ∞ /~, baris kendala 2 = 15/3 = 5, dan baris kendala 3 = 30/5 = 6. Dipilih baris yang mempunyai indeks positif dengan angka terkecil. Dalam hal ini kendala 2 yang terpilih sebagai baris kunci. Tanda segi empat diberikan pada baris kunci. Nilai yang masuk dalam kolom kunci dan juga termasuk dalam baris kunci disebut angka kunci. Tabel 2.4 Tabel simpleks ke-3 Sumber: Dasar-dasar operations research (Subagyo,p.37)
Variabel Dasar Z X3 X4 X5 Z X3 X2 X5
Z
X1
X2
X3
X4
X5
NK
1 0 0 0 1 0 0 0
-3 2 0 6
-5 0 3 5
0 1 0 0
0 0 1 0
0 0 0 1
0 8 15 30
0
1
0
1/3
0
5
Langkah 5: Mengubah nilai–nilai baris kunci
Nilai baris kunci diubah dengan cara membaginya dengan angka kunci, seperti yang terlihat pada tabel di atas bagian bawah (0/3 = 0; 3/3 = 1; 0/3 = 0; 1/3 = 1/3; 0;15/3
11 = 5). Variabel dasar pada baris itu diganti dengan variabel yang terdapat pada bagian atas kolom kunci (X2). Langkah 6: Mengubah nilai–nilai selain pada baris kunci
Nilai–nilai baris yang lain, selain pada baris kunci dapat diubah dengan rumus sebagai berikut. Baris baru = baris lama – (koefisien pada kolom kunci) x nilai baru baris kunci
Untuk data di atas, nilai baru baris pertama (Z) sebagai berikut. [ -3 (-5) [ 0 nilai baru =
[ -3
-5
0
0
0,
0]
1
0
1/3
0,
5]
0
0
5/3
0,
5]
(-)
Baris ke-2 (kendala 1):
0 nilai baru =
[2
0
1
0
0,
8]
[0
1
0
1/3
0,
5]
[2
0
1
0
0,
8]
(-)
Baris ke-4 (kendala 3):
5 nilai baru =
[6
5
0
0
1,
30 ]
[0
1
0
1/3
0,
5 ]
[6
0
0
-5/3
1,
5 ]
(-)
Nilai–nilai baru di atas dipakai untuk melengkapi isi tabel dan hasilnya adalah tabel di bawah ini:
12 Tabel 2.5 Tabel simpleks ke-4 Sumber: Dasar-dasar operations research (Subagyo,p.39)
Variabel dasar Z X3 X4 X5 Z X3 X2 X5
Z
X1
X2
X3
X4
X5
NK
1 0 0 0 1 1 0 0
-3 2 0 6 -3 -3 0 6
-5 0 3 5 0 0 1 0
0 1 0 0 0 0 0 0
0 0 1 0 5/3 5/3 1/3 -5/3
0 0 0 1 0 0 0 1
0 8 15 30 25 25 5 5
Langkah 7: Melanjutkan perbaikan–perbaikan atau perubahan–perubahan
Ulangi langkah–langkah perbaikan mulai dari langkah ke-3 sampai langkah ke-6 untuk memperbaiki tabel–tabel yang telah diubah/diperbaiki nilainya. Perubahan baru berhenti setelah pada baris pertama (fungsi tujuan) tidak ada yang bernilai negatif. Tabel 2.6 Tabel simpleks ke-5 Sumber: Dasar-dasar operations research (Subagyo,p.40)
Variabel dasar Z X3 X4 X5 Z X3 X2 X5
Z
X1
X2
X3
X4
X5
NK
1 0 0 0 1 0 0 0
-3 2 0 6
0 0 1 0
0 1 0 0
5/3 0 1/3 -5/3
0 0 0 1
25 8 Æ 8/2 = 4 5 5 Æ5/6 = 5/6 (minimum)
1
0
0
-5/18
5/6
5/6
Nilai baru baris–baris lain kecuali baris kunci sebagai berikut. Baris ke-1:
13 [-3
0
0
5/3
0,
25
]
(-3) [ 1
0
0
-5/18
1/6,
5/6
]
[0
0
0
5/6
1/2,
27½
]
[2
0
1
0
0,
8
]
[1
0
0
-5/18
1/6,
5/6
]
[0
0
1
5/9
-1/3,
6⅓
]
Nilai baru:
(-)
Baris ke-2:
2 Nilai baru:
Baris ke-3: tidak berubah, karena nilai pada kolom kunci = 0 Kalau hasil perubahan di atas dimasukan ke dalam tabel, maka hasilnya akan terlihat seperti di bawah ini. Tabel 2.7 Tabel simpleks ke-6 Sumber: Dasar-dasar operations research (Subagyo,p.41)
Variabel dasar Z X3 X2 X1
Z
X1
X2
X3
X4
X5
NK
1 0 0 0
0 0 0 1
0 0 1 0
0 1 0 0
5/6 5/9 1/3 -5/18
1/2 -1/3 0 1/6
27½ 6⅓ 5 5/6
Kalau dilihat baris pertama (Z) pada tabel di atas tidak ada lagi yang bernilai negatif, semua positif. Berarti tabel ini tidak dapat dioptimalkan lagi, sehingga hasil dari tabel tersebut merupakan hasil optimal. Rangkuman langkah–langkah secara keseluruhan. Kalau tabel awal (sebelum diubah), tabel hasil perubahan pertama dan tabel hasil perubahan kedua dijadikan satu, maka akan tampak jelas perubahannya. Dari tabel ini akan tampak maksud dari tiap variabel dan nilai–nilai yang ada pada tabel optimal.
14 X1 = 5/6, sehingga I1 = 5/6 lusin setiap hari. X2 = 5 ; sehingga I2 = 5 lusin setiap hari. Z maksimum = 27½ ; artinya laba yang akan diperoleh Rp.275.000,00 per hari. Tabel 2.8 Tabel simpleks ke-7 Sumber: Dasar-dasar operations research (Subagyo,p.42)
Variabel dasar Z X3 X4 X5 Z X3 X2 X5 Z X3 X2 X1 2.6
Z
X1
X2
X3
X4
X5
NK
1 0 0 0 1 0 0 0 1 0 0 0
-3 2 0 6 -3 2 0 6 0 0 0 1
-5 0 3 5 0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 0 0 1 0 0
0 0 1 0 5/3 0 1/3 -5/3 5/6 5/9 1/3 -5/18
0 0 0 1 0 0 0 1 1/2 -1/3 0 1/6
0 8 15 30 25 8 5 5 27½ 6⅓ 5 5/6
Capital Budgeting
Penganggaran modal adalah alat managerial yang sangat dibutuhkan. Salah satu tugas seorang manajer keuangan adalah untuk memilih investasi dengan arus kas dan tingkat pengembalian yang memuaskan. Oleh karena itu, seorang manajer keuangan harus mampu memutuskan apakah suatu investasi cukup berharga untuk ditanamkan modalnya dan bisa memilih dengan cerdas diantara dua atau lebih alternatif. Untuk dapat melakukan ini, suatu prosedur untuk mengevaluasi, membandingkan, dan memilih proyek diperlukan. Prosedur ini disebut capital budgeting. Capital expenditure adalah sejumlah dana yang dibutuhkan untuk suatu proyek
yang diharapkan dapat memberikan pemasukan dalam kurun waktu tertentu melebihi
15 jangka waktu satu tahun. Contoh-contoh proyek ini antara lain: investasi di bidang properti, pabrik dan peralatan, riset dan proyek pengembangan dan kampanye periklanan atau proyek-proyek lainnya yang membutuhkan pengeluaran modal dan menciptakan perputaran uang di masa yang akan datang. Terdapat banyak kriteria untuk menentukan suatu proyek. Beberapa pemegang saham mungkin menginginkan perusahaan memilih proyek yang dapat menghasilkan pendapatan yang besar dalam waktu yang singkat, sementara itu pemegang saham lain mungkin akan menekankan pada pertumbuhan jangka panjang dengan memberikan lebih sedikit perhatian terhadap performa jangka pendek. Dilihat dari sudut pandang ini, akan cukup sulit untuk memuaskan kepentingan yang berbeda-beda dari semua pemegang saham. Dengan adanya keterbatasan modal, manajemen perlu secara hati-hati memutuskan apakah proyek tertentu secara ekonomis bisa diterima. Di dalam suatu kasus yang melibatkan lebih dari satu proyek, manajemen harus mengidentifikasi proyek yang akan memberikan kontribusi laba dan kepada nilai dari perusahaan itu. Pada intinya, hal inilah yang menjadi basis penganggaran modal.
2.7
Capital Budgeting Problem Capital budgeting problem pada dasarnya adalah suatu permasalahan
pengambilan keputusan pada suatu perusahaan atau individu. Permasalahan timbul karena adanya berbagai macam alternatif investasi yang dapat dilakukan oleh perusahaan atau individu, sedangkan modal yang tersedia terbatas. Perusahaan atau individu tersebut harus dapat memilih secara tepat jenis investasi apa saja yang diambil
16 sesuai dengan modal yang ada. Pilihan tersebut diharapkan mampu menghasilkan keuntungan yang maksimal. Zero one integer programming merupakan model yang tepat dalam mewakili
permasalahan capital budgeting, karena zero one integer programming hanya menghasilkan solusi satu atau nol. Solusi ini dapat diartikan sebagai ya dan tidak. Artinya apabila suatu permasalahan capital budgeting menghasilkan jawaban “satu” maka artinya sebagai jawaban “ya” atas suatu jenis pilihan investasi dan apabila menghasilkan jawaban “nol” maka artinya sebagai jawaban “tidak” atas suatu jenis pilihan investasi. Model dari suatu permasalahan capital budgeting dapat dirumuskan sebagai berikut : Maksimumkan Z =
∑
N j =1
AjXj
Fungsi kendala :
∑
N j =1
BjiXj ≤ Ci
Dimana : Xj
= jenis investasi
N
= banyaknya investasi
Bij
= dana yang dibutuhkan untuk investasi ke-j pada tahun ke-i
Ci
= dana yang tersedia pada tahun ke-i
2.8
Integer Programming Linear programming menggunakan asumsi divisibility untuk setiap variabel
keputusan. Asumsi tersebut menunjukan bahwa nilai variabel keputusan diperbolehkan
17 dalam bentuk pecahan. Hal ini dimungkinkan apabila penyelesaiaan linear programming bersifat non-integer. Misalnya, solusi optimum masalah product mix menunjukan bahwa perusahaan menghasilkan produk A sebanyak 10,25 unit per hari. Secara ekonomis interpretasi dari hasil tersebut berarti perusahaan harus menghasilkan produk A diatas 10 unit per hari. Dalam beberapa kasus linear programming interpretasi tersebut mungkin tidak feasible. Oleh karena itu haruslah nilai variabel keputusan sebagian atau seluruhnya berupa bilangan bulat (non-integer). Persyaratan seperti ini disebut dengan masalah Integer Programming (IP). Bentuk umum model integer programming: 1. All Integer Programming atau Pure Integer Programming, yaitu jika semua variabel keputusan berbentuk integer. Optimumkan (maksimum atau minimum) Z = 3X1 + 2x2 Dengan kendala-kendala: [1]
X1
[2] [3]
X1
[4]
X1,
+
≤
2
X2
≤
2
X2
≤
3,5
X2
≥
0 dan integer
2. Mixed Integer Programming (MIP), yaitu jika beberapa variabel keputusan berbentuk integer. Optimumkan (maksimum atau minimum) Z = 4X1 + 3X2 Dengan kendala-kendala: [1]
2X1
+
2X2
≤
2
18 [2] [3]
X1
[4]
X1,
+
X2
≤
1
X2
≤
1
X2
≥
0 dan integer
3. Binary Integer Programming atau 0-1 Integer Programming, yaitu jika semua variabel keputusan berbentuk integer dan memiliki sepasang nilai 0 atau 1. Maksimumkan Z = 100X1 + 75X2 Dengan kendala-kendala:
2.8.1
[1]
4X1
+
2X2
≤
100
[2]
2X1
+
X2
≤
50
[3]
X1,
X2
=
0 atau 1
Algoritma Branch and Bound
Algoritma
Branch
and
Bound
merupakan
salah
satu
metode
untuk
menyelesaikan persoalan integer programming. Ide dasar dari algoritma ini adalah dengan cara mempartisi (branching) himpunan solusi- solusi yang feasible ke dalam suatu model yang lebih kecil dan mengeliminasi solusi yang tidak feasible. Proses partisi ini terus berlanjut sampai ditemukan solusi integer terbaik yang ada. Langkah – Langkah dalam algoritma Branch and Bound: 1. Hitung persamaan dengan cara linear programming biasa, setelah itu kita dapatkan nilai optimal dan nilai non-integer dari variabel–variabel yang dicari. Nilai optimal ini menjadi batas atas. Setelah itu dilakukan pembulatan ke bawah dari nilai–nilai non-integer variabel–variabel yang ada. Kemudian dimasukkan lagi nilai–nilai
pembulatan tadi ke dalam fungsi objektif dan nilai optimal yang diperoleh akan menjadi batas bawah.
19 2. Tentukan salah satu variabel untuk dibuat cabangnya. 3. Variable tadi dipecah menjadi 2 cabang; yang satu “lebih besar dari” dan yang lainnya “lebih kecil dari”. Persamaan ini menjadi fungsi kendala baru dalam integer programming.
4. Setelah itu dilakukan penghitungan ulang dan di antara kedua cabang tadi dicari nilai fungsi objektif yang paling optimal, lalu dijadikan batas atas baru untuk subset cabang. 5. Apabila solusi integer ditemukan dengan nilai fungsi objektif yang lebih tinggi dari batas bawah, maka kita batas bawah diganti. Nilai ini adalah nilai optimal terbaik yang ditemukan sampai saat ini. 6. Iterasi diteruskan sampai nilai batas atas yang diperoleh lebih besar atau sama dengan nilai batas bawah.
2.8.2
Algoritma Additive
Algoritma additive merupakan suatu algoritma yang didesain secara spesifik untuk menyelesaikan permasalahan zero one integer programming. Algoritma ini merupakan pengembangan dari algoritma branch and bound. Algoritma ini bekerja secara efektif dalam menyelesaikan permasalahan zero one integer programming, karena tidak membutuhkan penyelesaian secara linear programming seperti yang dibutuhkan dalam algoritma branch and bound. Agar dapat menyelesaikan suatu permasalahan dengan menggunakan algoritma additive maka suatu bentuk persamaan, baik fungsi objektif dan fungsi-fungsi kendalanya harus diubah dahulu ke dalam format tertentu. Langkah–langkah dalam mengubah bentuk persamaan adalah sebagai berikut.
20 1. Ubah fungsi objektif menjadi bentuk minimasi dengan mengalikannya dengan “minus satu”. Contoh: Fungsi objektif : Maksimumkan 20X1 + 40X2 + 20X3 + 15X4 + 30X5 Fungsi di atas mencari nilai maksimum bukan untuk nilai minium sehingga semua variabel dikalikan dengan -1 menjadi: Fungsi objektif: Minimumkan -20X1 - 40X2 - 20X3 - 15X4 - 30X5 2. Apabila fungsi kendalanya berbentuk lebih kecil sama dengan (≤), harus diubah ke dalam bentuk lebih besar sama dengan (≥) dengan mengalikannya dengan -1. Ruas kanan dari persamaan ini dapat berubah menjadi negatif. Contoh: Fungsi kendala: 5X1
+ 4X2 + 3X3 + 7X4 + 8X5 ≤ 25
X1
+ 7X2 + 9X3 + 4X4 + 6X5 ≤ 25
8X1
+ 10X2 + 2X3 + X4 + 10X5 ≤ 25
Karena bentuk fungsi kendala yang pertama berbentuk (≤), maka harus diubah menjadi bentuk (≥) dengan mengalikannya dengan -1, menjadi: Fungsi kendala: -5X1
- 4X2 - 3X3 - 7X4
- X1
- 7X2 - 9X3 - 4X4 - 6X5 ≥ -25
-8X1
- 10X2 - 2X3 - X4
- 8X5 ≥ -25
- 10X5 ≥ -25
21 3. Apabila setelah fungsi objektif dikalikan dengan -1 dihasilkan koefisien negatif pada variabel-variabelnya, maka didefinisikan variabelnya menjadi Yj = 1 - Xj atau Xj= 1Yj. Variabel yang memiliki nilai positif menjadi Yj = Xj. Setelah itu disubstitusikan ke dalam fungsi objektif dan semua fungsi kendala. Apabila setelah disubstitusikan, fungsi objektif mengandung konstanta non-variable, maka konstanta dianggap nol. Contoh: Fungsi objektif: Maksimumkan 20X1 + 40X2 + 20X3 + 15X4 + 30X5 Fungsi kendala: 5X1
+ 4X2 + 3X3 + 7X4 + 8X5 ≤ 25
X1
+ 7X2 + 9X3 + 4X4 + 6X5 ≤ 25
8X1
+ 10X2 + 2X3 + X4 + 10X5 ≤ 25
Setelah dilakukan langkah 1 dan langkah 2, persamaan berubah menjadi : Fungsi objektif : Minimumkan -20X1 - 40X2 - 20X3 - 15X4 - 30X5 Fungsi kendala : -5X1
- 4X2 - 3X3 - 7X4
- X1
- 7X2 - 9X3 - 4X4 - 6X5 ≥ -25
-8X1
- 10X2 - 2X3 - X4
- 8X5 ≥ -25
- 10X5 ≥ -25
Karena variabel X1, X2, X3, X4 dan X5 pada fungsi objektif memiliki nilai koefisien negatif maka didefinisikan: Y1 = 1 – X1 atau X1 = 1- Y1 Y2 = 1 – X2 atau X2 = 1- Y2 Y3 = 1 – X3 atau X3 = 1- Y3
22 Y4 = 1 – X4 atau X4 = 1- Y4 Y5 = 1 – X5 atau X5 = 1- Y5 Lalu disubstitusikan ke dalam fungsi objektif dan fungsi kendala menjadi: Fungsi objektif: Minimumkan -20(1- Y1) - 40(1- Y2) - 20(1- Y3) – 15(1- Y4)- 30(1- Y5) Fungsi kendala : -5(1- Y1) - 4(1- Y2) - 3(1- Y3) - 7(1- Y4) - 8(1- Y5) ≥ -25 - (1- Y1) - 7(1- Y2) - 9(1- Y3) - 4(1- Y4) - 6(1- Y5) ≥ -25 -8(1- Y1) - 10(1- Y2) - 2(1- Y3) - (1- Y4) - 10(1- Y5) ≥ -25 Sehingga persamaan menjadi : Fungsi objektif : Min 20Y1 + 40Y2 + 20Y3 + 15Y4 + 30Y5 - 125 Angka 125, sesuai dengan langkah 3 dianggap nol sehingga persamaannya menjadi: Fungsi objektif: Min 20Y1 + 40Y2 + 20Y3 + 15Y4 + 30Y5 Fungsi kendala: 5Y1
+ 4Y2 + 3Y3 + 7Y4 + 8Y5 ≥ 2
Y1
+ 7Y2 + 9Y3 + 4Y4 + 6Y5 ≥ 2
8Y1
+ 10Y2 + 2Y3 + Y4 + 10Y5 ≥ 6
Y1, Y2, Y3, Y4, Y5 = 0 , 1 Setelah persamaan disusun ulang sesuai dengan format standar dalam algoritma additive,
maka dapat dicari penyelesaiannya dengan menggunakan algoritma
additive.
Langkah–langkah dalam algoritma additive adalah sebagai berikut.
23 1. Tentukan nilai bantu (helpful index) dari setiap variabel yang ada. Caranya dengan menjumlahkan konstanta variabel-variabel pada semua fungsi kendala. Pada contoh di atas, dapat ditentukan nilai bantu dari masing-masing variabel, yaitu: Y1
=
5
+
1
+
8
= 14
Y2
=
4
+
7
+
10
= 21
Y3 =
3
+
9
+
2
= 14
Y4
=
7
+
4
+
1
= 12
Y5
=
8
+
6
+
10
= 24
2. Definisikan 3 vektor Sj, Vj dan Tj, di mana Sj merupakan himpunan variabel solusi, Vj merupakan himpunan dari fungsi kendala yang tidak terpenuhi karena vektor Sj dan Tj merupakan variabel-variabel pembantu, yang dapat membuat fungsi kendala dalam vektor Vj menjadi feasible. 3. Pada iterasi pertama, dapat ditentukan: S1 = {}, Semua nilai variabel masih dianggap nol. V1 = {1,2,3}, fungsi kendala 1,2,3 tidak terpenuhi. T1 = {1,2,3,4,5}, variabel 1, 2, 3, 4 dan 5 merupakan variabel pembantu yang dapat membuat vektor V1 menjadi feasible. Karena Y5 memiliki nilai bantu yang paling tinggi (nilai bantu Y5 = 24), maka nilai variabel Y5 diubah menjadi sama dengan 1 dan variabel lainnya masih dianggap sama dengan nol. 4. Pada iterasi ke-2 nilai S, V dan T sudah berubah menjadi: S2 = {5}, variabel Y5 = 1. V2 = {}, jika Y5 = 1 dan Y1=Y2 =Y3 =Y4 = 0 semua fungsi kendala terpenuhi.
24 Karena semua fungsi kendala terpenuhi maka ada solusi feasible, di mana nilai Y1 = Y2 = Y3 = Y4 = 0 dan Y5 = 1. Setelah nilai dari variabel–variabel tadi disubstitusikan dalam fungsi objektif maka akan diperoleh nilai Z = 30. Saat ini solusi ini adalah solusi feasible terbaik. Jika diperoleh solusi feasible maka dilakukan backtracking. 5. Waktu dilakukan backtracking, nilai variabel pada vektor S yang tadinya dianggap bernilai satu diubah menjadi nol (diindikasikan dengan tanda minus pada variabel yang dibacktrack). Variabel vektor S dibacktrack dari kanan, Variabel di sebelah kanan yang nilainya dibacktrack, dapat keluar dari vektor S (dapat masuk kembali ke dalam vektor T). 6. Pada contoh di atas, pada vektor S2 terdapat satu variabel yaitu Y5 yang tadinya nilainya satu diubah menjadi nol, sehingga pada iterasi ke-3 nilai S,V dan T menjadi sebagai berikut. S3 = {-5}, tanda minus mengindikasikan bahwa variabel Y5 = 0. V3 = {1,2,3}, fungsi kendala 1,2,3 tidak terpenuhi karena nilai dari vektor S3. T3 = {1,2,3,4}, variabel Y5 tidak dapat dimasukkan dalam vektor T karena nilainya telah dianggap nol. Dipilih lagi nilai bantu yang lain. Setelah Y5, nilai bantu yang paling tinggi adalah Y2 (nilai bantu Y2 = 21) . 7. Pada iterasi ke-4 nilai S, V dan T sudah berubah menjadi sebagai berikut. S4 = {-5,2}, variabel Y5 = 0 dan Y2 = 1. V4 = {}, jika Y2 = 1 dan Y1=Y3 =Y4 =Y5 = 0 semua fungsi kendala terpenuhi. Karena semua fungsi kendala terpenuhi maka diperoleh solusi feasible, di mana nilai Y1 = Y3 = Y4 = Y5 = 0 dan Y2 = 1. Setelah disubstitusikan nilai variabel–variabel tadi ke dalam fungsi objektif maka akan diperoleh nilai Z = 40. Akan tetapi solusi
25 feasible terbaik yang dimiliki saat ini adalah pada iterasi ke -2 (Z = 30), karena Z =
30 lebih kecil daripada Z = 40. Jika diperoleh solusi feasible maka dilakukan backtracking.
8. Pada iterasi ke-5 nilai S, V dan T sudah berubah menjadi: S5 = {-5,-2} V5 = {1,2,3} T5 = {1,3,4} Dipilih lagi nilai bantu, yaitu variabel Y3 (dapat juga dipilih variabel Y1, karena nilai bantunya sama). 9. Pada iterasi ke-6 nilai S, V dan T sudah berubah menjadi: S6 = {-5,-2,3} V6 = {3} T6 = {1,4} Karena belum menghasilkan solusi feasible dan masih terdapat variabel pembantu yang lain maka dipilih lagi nilai bantu yang masih tersisa, yaitu variabel Y1. 10. Pada iterasi ke-7 nilai S,V dan T sudah berubah menjadi: S7 = {-5,-2,3,1} V7 = {} Karena semua fungsi kendala terpenuhi maka diperoleh solusi feasible, di mana nilai Y5 = Y2 = 0 dan Y3 = Y1 = 1. Setelah nilai variabel–variabel tadi disubstitusikan ke dalam fungsi objektif maka akan diperoleh nilai Z = 40. Akan tetapi solusi feasible terbaik yang dimiliki saat ini adalah pada iterasi ke-2 (Z = 30), karena Z = 30 lebih kecil daripada Z = 40. Jika diperoleh solusi feasible maka dilakukan backtracking. 11. Pada iterasi ke-8 nilai S, V dan T sudah berubah menjadi:
26 S8 = {-5,-2,3,-1} V8 = {3} T8 = {} Variabel yang tersisa yaitu Y4 tidak dapat membantu fungsi kendala 3 terpenuhi, oleh karena itu dilakukan backtracking. 12. Pada iterasi ke-9 nilai S, V dan T sudah berubah menjadi : S9 = {-5,-2,-3} V9 = {1,2,3} T9 = {1,4} Nilai bantu yang paling baik adalah Y1, sehingga nilai Y1 = 1. 13. Pada iterasi ke-10 nilai S, V dan T sudah berubah menjadi: S10 = {-5,-2,-3,1} V10 = {2} T10 = {4} Nilai bantu yang tersisa adalah Y4 ,sehingga nilai Y4 = 1. 14. Pada iterasi ke-11 nilai S, V dan T sudah berubah menjadi: S11 = {-5,-2,-3,1,4} V11 = {} Karena semua fungsi kendala terpenuhi maka diperoleh solusi feasible, di mana nilai Y2 = Y5 = Y3 = 0 dan Y1 = Y4 = 1. Setelah nilai variabel–variabel tadi disubstitusikan ke dalam fungsi objektif maka akan diperoleh nilai Z = 35. Akan tetapi solusi feasible terbaik yang dimiliki saat ini adalah pada iterasi ke-2 ( Z = 30 ), karena Z =
30 lebih kecil daripada Z = 35. Jika diperoleh solusi feasible dilakukan backtracking. 15. Pada iterasi ke-12 nilai S, V dan T sudah berubah menjadi:
27 S12 = {-5,-2,-3,1,-4} V12 = {2} T12 = {} Fungsi kendala 2 tidak dapat terpenuhi sehingga harus dilakukan backtracking. 16. Pada iterasi ke-13 nilai S, V dan T sudah berubah menjadi: S13 = {-5,-2,-3,-1} V13 = {1,2,3} T13 = {4} Nilai bantu yang paling tersisa adalah Y4 , sehingga nilai Y4 = 1. 17. Pada iterasi ke-14 nilai S, V dan T sudah berubah menjadi: S14 = {-5,-2,-3,-1,4} V14 = {3} T14 = {} Fungsi kendala 3 tidak dapat terpenuhi sehingga harus dilakukan backtracking. 18. Pada iterasi ke-15 nilai S, V dan T sudah berubah menjadi: S15 = {-5,-2,-3,-1,-4} V15 = {1,2,3} T15 = {} Karena tidak ada kemungkinan backtracking lagi maka iterasi dihentikan. 19. Solusi feasible terbaik adalah dengan Y5 = 1 dan Y1=Y2 =Y3 =Y4 = 0 yang menghasilkan Z = 30. Setelah diperoleh nilai optimum dalam bentuk variabel Y, ubah kembali menjadi X sehingga menjadi : X1 = 1- Y1 = 1 X2 = 1- Y2 = 1
28 X1 = 1- Y3 = 1 X1 = 1- Y4 = 1 X5 = 1- Y5 = 0 Setelah disubstitusikan ke dalam persamaan Z maksimum awal, maka nilai Z adalah: 20 x 1 + 40 x 1 + 20 x 1 + 15 x 1 + 30 x 0 = 95
2.9
Rekayasa Perangkat Lunak
Rekayasa perangkat lunak adalah sebuah teknologi yang meliputi sebuah proses, serangkaian metode, dan seperangkat alat. Karakteristik perangkat lunak: •
Perangkat lunak dibangun dan dikembangkan, tidak dibuat dalam bentuk yang klasik
•
Perangkat lunak tidak pernah usang
•
Sebagian besar perangkat lunak dibuat secara custom-built, serta tidak dapat dirakit dari komponen yang sudah ada.
Elemen–elemen perangkat lunak: a. Proses Proses–proses membatasi kerangka kerja untuk serangkaian area proses kunci yang harus dibangun demi keefektifan penyampaian teknologi pengembangan perangkat lunak. b. Metode Metode–metode rekayasa perangkat lunak memberikan teknik untuk membangun perangkat lunak. Metode – metode itu menyangkut serangkaian tugas yang luas yang
29 menyangkut analisis kebutuhan, konstruksi program, desain, pengujian dan pemeliharaan. c. Alat Bantu Tool–tool rekayasa perangkat lunak memberikan topangan yang otomatis atau pun
semi otomatis pada proses–proses dan metode–metode yang ada. Tool–tool diintegrasikan sehingga informasi yang diciptakan oleh satu tool dapat digunakan oleh yang lain, Sistem untuk menopang perkembangan perangkat lunak yang disebut Computer-Aided Software Engineering (CASE).
2.9.1
Model Sekuensial Linier
Merupakan model proses yang dipergunakan dalam penulisan skripsi ini. Model ini biasa disebut juga model “air terjun” (waterfall). Model ini mengusulkan sebuah pendekatan kepada perkembangan perangkat lunak yang sistematik dan sekuensial yang mulai pada tingkat dan kemajuan sistem pada seluruh analisis, desain, kode, pengujian dan pemeliharaan. Urutan kerjanya disajikan dalam gambar di bawah:
Gambar 2.1 Waterfall Model Sumber: HTTP://www.vcustomer.com/images/waterfall-model.jpg
30
1. Analisis
Proses pengumpulan kebutuhan diintensifkan dan difokuskan, khususnya pada perangkat lunak. Kebutuhan baik untuk sistem maupun perangkat lunak didokumentasikan dan dilihat lagi dengan pelanggan. 2. Desain
Proses desain menerjemahkan syarat/kebutuhan ke dalam sebuah representasi perangkat lunak yang dapat diperkirakan demi kualitas sebelum dimulai pemunculan kode. 3. Pengkodean dan Pengembangan
Desain harus dapat diterjemahkan ke dalam bentuk bahasa mesin yang bisa dibaca. 4. Implementasi dan Pengujian
Sekali kode dibuat, pengujian program dimulai. Proses pengujian berfokus pada logika internal perangkat lunak, memastikan bahwa semua pernyataan sudah diuji, dan pada eksternal fungsional – yaitu mengarahkan pengujian untuk menemukan kesalahan – kesalahan dan memastikan bahwa input yang dibatasi akan memberikan hasil aktual yang sesuai dengan hasil yang dibutuhkan. 5. Pemeliharaan
Perangkat lunak akan mengalami perubahan setelah disampaikan kepada pelanggan. Pemeliharaan perangkat lunak mengapliksikan lagi setiap fase program sebelumnya dan tidak membuat yang baru lagi.
31 2.9.2 State Transition Diagram (STD) State Transition Diagram merupakan sebuah modeling tool yang digunakan
untuk mendeskripsikan sistem yang memiliki ketergantungan terhadap waktu. STD merupakan suatu kumpulan keadaan atau atribut yang mencirikan suatu keadaan pada waktu tertentu. Komponen-komponen utama STD adalah: 1.
State, disimbolkan dengan State merepresentasikan reaksi yang ditampilkan ketika suatu tindakan
dilakukan. Ada dua jenis state yaitu: state awal dan state akhir. State akhir dapat berupa beberapa state, sedangkan state awal tidak boleh lebih dari satu. 2.
Arrow, disimbolkan dengan Arrow sering disebut juga dengan transisi state yang diberi label dengan ekspresi
aturan, label tersebut menunjukkan kejadian yang menyebabkan transisi terjadi. 3.
Condition dan Action, disimbolkan dengan Condition Action
State 1
State 2
Untuk melengkapi STD diperlukan 2 hal lagi yaitu condition dan action. Condition adalah suatu event pada lingkungan eksternal yang dapat dideteksi
oleh sistem, sedangkan action adalah yang dilakukan oleh sistem bila terjadi perubahan state atau merupakan reaksi terhadap kondisi. Aksi akan menghasilkan keluaran atau tampilan.
32 2.9.3
Interaksi Manusia dan Komputer dalam Program Aplikasi
Pengertian dari Interaksi Manusia dengan Komputer (Human-Computer Interaction) adalah disiplin ilmu yang berhubungan dengan perancangan , evaluasi
implementasi sistem komputer interaktif yang digunakan oleh manusia serta studi fenomena-fenomena besar yang berhubungan dengannya ( Shneiderman,1992,p8). Suatu program aplikasi komputer penting sekali untuk didukung oleh sistem interaksi manusia komputer yang baik. User harus merasa tidak dipersulit dalam menggunakan aplikasi tersebut. Jika perancangan program aplikasi kurang baik, maka hal tersebut dapat menimbulkan rasa enggan pada pengguna untuk menggunakannnya. Hal ini dapat mengakibatkan tujuan program aplikasi tersebut menjadi tidak tercapai. Menurut Shneiderman (1992, pp15-18), ada lima kriteria yang harus dipenuhi oleh suatu sistem yang user friendly, yaitu : 1.
Waktu belajar yang tidak lama
2.
Kecepatan penyajian informasi yang tepat dan jelas
3.
Tingkat kesalahan pengguna yang rendah
4.
Penghapalan sesudah melampaui jangka waktu yang tidak lama
5.
Kepuasan pribadi.
Menurut Shneiderman (1992, pp72-73), Untuk merancang sebuah sistem interaksi manusia dan komputer yang baik ada delapan aturan yang harus diperhatikan, yaitu : 1.
Bertahan untuk konsisten
2.
Memperbolehkan pengguna yang rutin untuk menggunakan jalan pintas
3.
Umpan balik yang interaktif untuk setiap aksi.
33 4.
Pengorganisasian yang baik.
5.
Penanganan kesalahan yang sederhana
6.
Memperbolehkan pengguna mengulangi atau memperbaiki suatu aksi yang telah dilakukannya
7.
Menguasai sistem dan sistem akan memberikan balasan atas aksinya.
8.
Mengurangi penghapalan dengan memperhatikan kaidah ingatan manusia yang terbatas, yaitu tujuh ditambah dua informasi.
