bab 2 landasan teori -...

5

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 sendiri-

sendiri 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

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 langkah-

langkah 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 + X3 = 8

2) 3X2 + X4 = 15

3) 6X1 + 5X2 +X5 = 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

Xn+1

Xn+2

Xn+m

1

0

0

0

-C1 -C2 ……... -Cn 0 0 …………. 0

a11 a12 …….. a1n 1 0 ………….. 0

a21 a22 ……… a2n 0 1 ………….. 0

am1 am2 ……... amn 0 0 …………. 1

0

b1

b2

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 X1 X2 X3 X4 X5 NK

Z 1 -3 -5 0 0 0 0 X3 0 2 0 1 0 0 8 X4 0 0 3 0 1 0 15 X5 0 6 5 0 0 1 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 X1 X2 X3 X4 X5 NK Keterangan

Z 1 -3 -5 0 0 0 0 X3 0 2 0 1 0 0 8 X4 0 0 3 0 1 0 15 15/3 = 15 (minimum) X5 0 6 5 0 0 1 30 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:

kunci kolom NilaiNK kolom NilaiIndeks =

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.


Variabel

Dasar Z X1 X2 X3 X4 X5 NK

Z 1 -3 -5 0 0 0 0 X3 0 2 0 1 0 0 8 X4 0 0 3 0 1 0 15 X5 0 6 5 0 0 1 30 Z 1 X3 0 X2 0 0 1 0 1/3 0 5 X5 0

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 0 0, 0 ]

(-5) [ 0 1 0 1/3 0, 5 ] ( - )

nilai baru = [ -3 0 0 5/3 0, 5 ]

Baris ke-2 (kendala 1):

[ 2 0 1 0 0, 8 ]

0 [ 0 1 0 1/3 0, 5 ] ( - )

nilai baru = [ 2 0 1 0 0, 8 ]

Baris ke-4 (kendala 3):

[ 6 5 0 0 1, 30 ]

5 [ 0 1 0 1/3 0, 5 ] ( - )

nilai baru = [ 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


Variabel

dasar Z X1 X2 X3 X4 X5 NK

Z 1 -3 -5 0 0 0 0 X3 0 2 0 1 0 0 8 X4 0 0 3 0 1 0 15 X5 0 6 5 0 0 1 30 Z 1 -3 0 0 5/3 0 25 X3 1 -3 0 0 5/3 0 25 X2 0 0 1 0 1/3 0 5 X5 0 6 0 0 -5/3 1 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.


Variabel dasar Z X1 X2 X3 X4 X5 NK

Z 1 -3 0 0 5/3 0 25 X3 0 2 0 1 0 0 8 8/2 = 4 X4 0 0 1 0 1/3 0 5 X5 0 6 0 0 -5/3 1 5 5/6 = 5/6 (minimum) Z 1 X3 0 X2 0 X5 0 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 ] (-)

Nilai baru: [ 0 0 0 5/6 1/2, 27½ ]

Baris ke-2:

[ 2 0 1 0 0, 8 ]

2 [ 1 0 0 -5/18 1/6, 5/6 ]

Nilai baru: [ 0 0 1 5/9 -1/3, 6⅓ ]

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.



Z 1 0 0 0 5/6 1/2 27½ X3 0 0 0 1 5/9 -1/3 6⅓ X2 0 0 1 0 1/3 0 5 X1 0 1 0 0 -5/18 1/6 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.



Z 1 -3 -5 0 0 0 0 X3 0 2 0 1 0 0 8 X4 0 0 3 0 1 0 15 X5 0 6 5 0 0 1 30 Z 1 -3 0 0 5/3 0 25 X3 0 2 0 1 0 0 8 X2 0 0 1 0 1/3 0 5 X5 0 6 0 0 -5/3 1 5 Z 1 0 0 0 5/6 1/2 27½ X3 0 0 0 1 5/9 -1/3 6⅓ X2 0 0 1 0 1/3 0 5 X1 0 1 0 0 -5/18 1/6 5/6

2.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 1AjXj

Fungsi kendala :

CiBjiXj1

≤∑ =

N

j

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

[2] X2 ≤ 2

[3] X1 + X2 ≤ 3,5

[4] X1, X2 ≥ 0 dan integer

2. Mixed Integer Programming (MIP), yaitu jika beberapa variabel keputusan

berbentuk integer.

Optimumkan (maksimum atau minimum)

Z = 4X1 + 3X2


[1] 2X1 + 2X2 ≤ 2

18

[2] X2 ≤ 1

[3] X1 + X2 ≤ 1

[4] X1, 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


[1] 4X1 + 2X2 ≤ 100

[2] 2X1 + X2 ≤ 50

[3] X1, X2 = 0 atau 1

2.8.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 - 8X5 ≥ -25

- X1 - 7X2 - 9X3 - 4X4 - 6X5 ≥ -25

-8X1 - 10X2 - 2X3 - X4 - 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= 1-

Yj. 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 - 8X5 ≥ -25

- X1 - 7X2 - 9X3 - 4X4 - 6X5 ≥ -25

-8X1 - 10X2 - 2X3 - X4 - 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.


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).


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 = {}


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.


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.


S10 = {-5,-2,-3,1}

V10 = {2}

T10 = {4}

Nilai bantu yang tersisa adalah Y4 ,sehingga nilai Y4 = 1.


S11 = {-5,-2,-3,1,4}

V11 = {}


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.


27

S12 = {-5,-2,-3,1,-4}

V12 = {2}

T12 = {}

Fungsi kendala 2 tidak dapat terpenuhi sehingga harus dilakukan backtracking.


S13 = {-5,-2,-3,-1}

V13 = {1,2,3}

T13 = {4}

Nilai bantu yang paling tersisa adalah Y4 , sehingga nilai Y4 = 1.


S14 = {-5,-2,-3,-1,4}

V14 = {3}

T14 = {}

Fungsi kendala 3 tidak dapat terpenuhi sehingga harus dilakukan backtracking.


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

State 1 State 2

Condition

Action

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.

bab 2 landasan teori -...

Documents