BAB I PENDAHULUAN A. Latar Belakang Persoalan Indonesia merupakan salah satu negara yang mempunyai wilayah hutan yang cukup luas dan merupakan negara terpenting penghasil berbagai kayu bulat tropis, kayu gergajian, kayu lapis dan hasil kayu lainnya. Hasil produksi hutan Indonesia mempunyai keunggulan komparatif (comparative advantage) jika dibandingkan dengan negara-negara lain dan sebagian dari produksi hasil hutan diekspor ke negara lain. Selain itu produk kayu juga merupakan penghasil devisa utama dari sektor non migas. Kayu
merupakan
salah
satu
hasil
hutan
yang
dalam
proses
pembaharuannya membutuhkan waktu yang cukup lama, sehingga perlu pengelolaan yang baik, yaitu dengan memperhatikan sistem tebang pilih serta menindak para pembalak liar, agar pemenuhan kayu dalam proses pembangunan, baik bagi perumahan dan infrastruktur lain tidak terhambat. Perusahaan kayu biasanya mengkonversikan kayu bulat menjadi kayu berbentuk balok, papan atau bentuk-bentuk yang sesuai dengan tujuan penggunaannya. Selanjutnya kayu-kayu yang telah berbentuk balok, maupun papan diolah kembali menjadi ukuran-ukuran tertentu sesuai dengan pesanan dari para pemilik usaha dagang (UD) kayu. Dalam praktik, suatu pesanan dipenuhi dengan menyetel pisau pemotong sesuai dengan panjang yang diminta. Biasanya untuk memenuhi pesanan terdapat beberapa cara atau pola pemotongan standar. Adapun pola-pola ini digunakan
1
2
dengan tujuan mengoptimalkan penggunaan balok kayu yang tersedia dengan cara meminimumkan sisa pemotongan. Jika suatu perusahaan kayu mendapatkan pesanan dalam jumlah banyak, misalnya sejumlah m pesanan dengan panjang kayu yang bervariasi, maka dilakukan pola-pola pemotongan yang beraneka ragam untuk memenuhi pesanan tersebut, banyaknya pola pemotongan misal n pola pemotongan. Persoalan yang dihadapi perusahaan kayu tersebut dapat disusun ke dalam persoalan program linear dan dapat dipecahkan atau dicari solusinya menggunakan teknik-teknik penyelesaian dalam program linear. Program linear adalah suatu metode yang dapat digunakan dalam mencari solusi persoalan optimasi dengan merencanakan langkah-langkah yang perlu diambil dengan tujuan memperoleh hasil yang optimal, yaitu hasil yang mencapai tujuan terbaik diantara seluruh hasil yang mungkin. Banyak persoalan yang penyelesaiannya menggunakan program linear, diantaranya persoalan transportasi, persoalan penugasan, program dinamis serta program bilangan bulat. Program linear bilangan bulat merupakan bentuk khusus dari program linear, dengan solusinya harus bernilai bilangan bulat dan sebagian lainnya boleh bernilai pecahan. Persoalan program linear bilangan bulat yang penyelesaian persoalannya hanya sebagian dari variabel solusinya yang harus bernilai bilangan bulat dinamakan persoalan program linear bilangan bulat campuran. Apabila seluruh variabel solusi dari penyelesaian suatu persoalan program linear harus bernilai bilangan bulat maka disebut persoalan bilangan bulat murni. Penyelesaian persoalan program linear bilangan bulat memerlukan suatu metode khusus.
3
Terdapat dua metode yang digunakan, yaitu metode cabang dan batas (branch and bound) dan metode bidang potong (cutting plane). Dalam mencari penyelesaian persoalan program linear, metode yang sering digunakan yaitu metode simpleks. Terdapat teknik lain untuk menyelesaikan persoalan program linear yaitu teknik pembangkit kolom (column generation technique). Salah satu aplikasi dari teknik ini yaitu untuk menyelesaikan persoalan pemotongan stok atau cutting stock problem (CSP). Langkah pertama dalam menyelesaikan persoalan optimasi pemotongan balok kayu yaitu menentukan pola pemotongan yang mungkin kemudian menentukan kombinasi-kombinasi pola pemotongan yang layak. Meskipun menentukan semua pola yang mungkin tidak begitu sulit, namun menentukan kombinasi yang layak merupakan pekerjaan yang berat. Disinilah model program linear memainkan peranan dan teknik pendekatan yang sistematis diperlukan. Langkah selanjutnya yaitu persoalan dibentuk kedalam bentuk program linear baku, bentuk ini kemudian diselesaikan dengan teknik pembangkit kolom. Teknik pembangkit kolom digunakan untuk mengefisiensi metode simpleks direvisi. Sehingga langkah-langkah pengerjaannya banyak mengacu kepada metode simpleks direvisi, mulai dari perhitungan B
1
(matriks yang diperoleh dari
koefisien variabel-variabel slack untuk baris ke-i, i 1, 2, ..., m dari tabel akhir simpleks), harga akhir (price out), penggunaan test rasio untuk menentukan variabel basis, sampai diperoleh penyelesaian optimal. Perbedaan mendasar antara teknik pembangkit kolom dan metode simpleks direvisi terletak pada perhitungan harga akhir ( z j
c j ) variabel non basis yang akan masuk menjadi variabel basis.
4
Perhitungan harga akhir untuk tiap-tiap variabel non basis menjadi variabel basis dalam skala besar pemotongan balok kayu dengan menggunakan metode simpleks direvisi adalah suatu pekerjaan yang tidak efektif dan juga tidak efisien. Untuk mengatasi hal ini maka teknik pembangkit kolom dapat digunakan untuk mencari penyelesaiannya. Ide dasar dari teknik pembangkit kolom adalah untuk mengefisiensi suatu kolom dengan harga akhir yang efisien (positif dalam persoalan minimum). Dalam optimasi pemotongan balok kayu, yang diinginkan adalah sisa pemotongan dan produksi suplus seminimum mungkin. Untuk mendapatkan hasil ini dilakukan dengan mengkombinasikan pola-pola pemotongan berdasarkan panjang pesanan yang diinginkan dengan menerapkan teknik pembangkit kolom. Pola-pola yang paling baik di antara pola-pola yang mungkin dapat diperoleh dengan menggunakan teknik pembangkit kolom. Penyelesaian persoalan program linear dapat diselesaikan dengan cara menghitung secara manual maupun dengan menggunakan bantuan software aplikasi. Jika dalam persoalan program linear telah melibatkan banyak variabel dan kendala (pembatas), maka menyelesaikannya dengan cara manual tentunya akan memerlukan waktu yang lama. Maka disinilah peran software aplikasi untuk menyelesaikannya secara cepat. Dalam penulisan ini contoh persoalan yang disajikan adalah persoalan pemotongan balok kayu dan dibahas juga bagaimana implementasi dari teknik pembangkit kolom untuk mendapatkan solusi yang optimal persoalan pemotongan
5
stok, lebih khusus lagi mengenai pemotongan balok kayu dengan pola pemotongan satu dimensi.
B. Pembatasan Persoalan Persoalan dalam penulisan ini dibatasi hanya pada pemotongan balok kayu untuk pola pemotongan satu dimensi.
C. Rumusan Persoalan Berdasarkan latar belakang persoalan, dapat dirumuskan persoalan sebagai berikut: a. Bagaimana menentukan pola awal dan kombinasi pola paling layak pemotongan balok kayu dengan pola pemotongan satu dimensi ? b. Bagaimana implementasi teknik pembangkit kolom dalam menyelesaikan persoalan pemotongan balok kayu ? c. Bagaimana implementasi software aplikasi dalam mencari solusi optimal pemotongan balok kayu dengan lebih cepat ?
D. Tujuan Penulisan Berdasarkan rumusan persoalan, maka tujuan dari penulisan ini adalah: a. Mendeskripsikan pola dan kombinasi yang layak dari persoalan pemotongan balok kayu. b. Mendeskripsikan
penerapan
teknik
pembangkit
kolom
dalam
menyelesaikan persoalan pemotongan balok kayu. c. Mendeskripsikan penerapan software aplikasi dalam mencari solusi optimal pemotongan balok kayu secara cepat.
6
E. Manfaat Penulisan Adapun manfaat dari penulisan ini yaitu diharapkan dapat memperluas penerapan matematika, khususnya bidang riset operasi pada industri dan perusahaan. Selain itu juga riset-riset atau penelitian-penelitian yang berkenaan dengan pengoptimalan penggunaan dan pemanfaatan sumber daya alam.
7
BAB II LANDASAN TEORI Di dalam membahas optimasi pemotongan balok kayu diperlukan beberapa pengetahuan tentang program linear, sistem persamaan, matriks, persoalan knapsack, metode simpleks, metode simpleks direvisi dan program linear bilangan bulat serta penyelesaiannya menggunakan metode cabang dan batas.
A. Program Linear 1. Definisi Menurut Tjutju Tarliah dan Ahmad Dimyati (1992: 17), program linear diterjemahkan dari Linear Programming (LP) adalah suatu cara untuk menyelesaikan persoalan alokasi sumber-sumber terbatas (misal, tenaga kerja terampil, bahan mentah, lahan subur, mesin, modal) di antara beberapa aktivitas yang bersaing dengan cara seoptimal mungkin. Persoalan pengalokasian ini akan muncul manakala seorang harus memilih tingkat aktivitas-aktivitas tertentu yang bersaing dalam hal penggunaan sumber daya yang dibutuhkan untuk melaksanakan aktivitas-aktivitas tersebut. Beberapa persoalan pengalokasian antara lain persoalan pengalokasian fasilitas produksi, persoalan pengalokasian sumber daya nasional untuk keperluan domestik, penjadwalan produksi, solusi permainan (game), dan pemilihan pola pengiriman. Program linear menurut Frederick S. Hiller and Gerald J. Lieberman (1980: 27), menggunakan suatu model matematis untuk menggambarkan suatu persoalan, aplikasi yang umum adalah mencakup alokasi sumber-sumber daya
8
yang berkaitan dengan memaksimumkan maupun meminimumkan. Kata program merupakan padanan kata perencanaan. Kata sifat linear berarti bahwa semua fungsi matematis dalam model ini harus merupakan fungsi-fungsi linear. Jadi membuat program linear adalah merencanakan kegiatan-kegiatan untuk memperoleh hasil yang optimal, yaitu suatu hasil untuk mencapai tujuan yang ditentukan dengan cara paling baik di antara semua alternatif yang mungkin. Program linear banyak dipakai dalam persoalan ekonomi, industri, militer dan bidang sosial lainnya. Adapun persoalan yang sering dihadapi dalam berbagai bidang tersebut adalah alokasi optimal dari sumber daya tersebut. Manfaat program linear yaitu membuat model matematis dalam mencari solusi terbaik dari persoalan keterbatasan sumber daya untuk mencapai tujuan tertentu. Dalam membangun model matematis dari formulasi persoalan program linear diperlukan karakteristik-karakteristik sebagai berikut: a. Variabel keputusan Variabel keputusan adalah variabel yang menguraikan secara lengkap keputusan-keputusan yang akan dibuat, yang merupakan formulasi dari apa yang dicari dalam persoalan tersebut. Variabel keputusan ini dituliskan dengan x j , j
1, 2, ..., n .
b. Fungsi tujuan Fungsi tujuan merupakan fungsi dari variabel keputusan yang harus dicapai agar penyelesaian optimal dapat ditentukan dari semua nilai-nilai yang layak.
9
c. Fungsi kendala Fungsi kendala merupakan formulasi dari kendala-kendala yang dihadapi dalam menentukan nilai variabel-variabel keputusan. d. Pembatas tanda Pembatas tanda adalah pembatas yang menjelaskan apakah variabel keputusan hanya bernilai nonnegatif atau boleh positif, nol, negatif (tidak terbatas dalam tanda). Terdapat
dua
jenis
keoptimalan
untuk
fungsi
tujuan
yaitu
memaksimumkan dan meminimumkan. Untuk mencari solusi dari suatu persoalan program linear biasanya diselesaikan dengan memaksimumkan fungsi tujuan. Hal ini bukan berarti mengesampingkan persoalan meminimumkan. Karena berdasarkan
sifat,
persoalan
meminimumkan
dapat
diubah
menjadi
memaksimumkan. Sifat 2.1: Meminimumkan f (x) ditulis dengan min f (x)
(maks
( memaksimumkan f ( x)), x
f ( x)), x
S atau biasa
S.
Bukti: Dimisalkan terdapat suatu program linear bilangan bulat dengan fungsi tujuan f dan himpunan kendala S. Ambil fungsi g, dengan g ( x) a. Jika
x
S
y
S sehingga f ( x)
( y)
f ( x)
f ( y)
f ( x), x S . g ( x)
g ( y) ,
maka tidak ada nilai minimum fungsi f dan tidak ada nilai maksimum fungsi g. Pada keadaan ini didefinisikan min f ( x) b. Jika
y
S
x
S dan f ( x)
f ( y ) maka
dan maksimum (min g ( x)) f ( y)
f ( x)
g ( y)
g ( x)
.
10
jadi min f ( x)
= f ( y) = ( f ( y )) = ( g ( y) ) = ( maks [ g ( x)]) = ( maks
[ f ( x)])
2. Bentuk baku atau bentuk umum dan bentuk kanonik program linear Program linear adalah suatu teknik matematis yang bertujuan untuk mendapatkan keputusan optimal dari sebuah fungsi dan dari sejumlah variabel tertentu. Variabel-variabel tersebut terkait pada sekelompok kendala (constraint) yang berbentuk persamaan atau pertidaksamaan. Fungsi kendala dapat berbentuk pertidaksamaan lebih kecil atau sama dengan
( ) , lebih besar atau sama dengan ( ) dan juga berbentuk sama dengan ( ) . Bentuk umum atau bentuk baku program linear yaitu bentuk formulasi yang memiliki sifat-sifat sebagai berikut: a. Semua kendala harus berbentuk persamaan (bertanda =) dengan ruas kanan yang nonnegatif. b. Semua variabel harus merupakan variabel nonnegatif. c. Fungsi tujuannya dapat berupa meminimumkan atau memaksimumkan. Bentuk program linear secara umum dapat dijelaskan sebagai berikut:
11
Memaksimumkan atau meminimumkan z ( x j ) c1 x1 c2 x2 ... cn xn , terhadap kendala: a11 x1 a12 x 2
... a1n x n ( , , ) b1 ,
a21 x1 a22 x 2
... a2 n x n ( , , ) b2 ,
am1 x1 am 2 x 2 ... amn x n ( , , ) bm , xj
0, j
1,2,..., n.
(Akbar Sutawijaya: 1) Koefisien-koefisien dalam z ( x j ), c j dinamakan koefisien ongkos, x j dinamakan peubah keputusan dan aij dinamakan koefisien teknis. Jika perumusan program linear telah diaplikasikan dalam bentuk soal maka z disebut fungsi sasaran, kendala-kendala disebut kendala utama dan x j
0 disebut kendala nonnegatif.
Bentuk kanonik program linear diperoleh dengan cara: a. Jika kendala ke-i suatu program linear adalah suatu persoalan
maka
ditambahkan variabel slack si untuk kendala ke-i dan ditambahkan kendala si
0, i 1, 2, ..., m .
b. Jika kendala ke-i dari suatu program linear adalah persoalan
maka
merubah ke bentuk kanonik program linear yaitu dikurangi dengan suatu variabel yang dinamakan variabel surplus (excess variable) ti pada kendala ke-i dan ditambahkan kendala ti
0, i 1, 2, ..., m .
c. Jika kendala ke-i dari suatu program linear sudah berbentuk persamaan ( ) tetapi belum memuat variabel basis maka merubah ke bentuk kanonik dilakukan dengan menambahkan variabel semu misal qi
0, i 1, 2, ..., m .
12
Contoh 2.1 Memaksimumkan z ( x1 , x2 , x3 )
8 x1 6 x2 8 x3
terhadap kendala: x1
x 2 2 x 3 12
2 x1 6 x2
(2.1)
x3
4
(2.2)
x1 2 x2 x3 x1 , x2 , x3 0
8
(2.3)
Terhadap persoalan di atas, perlu diubah terlebih dahulu kendala-kendala yang ada menjadi bentuk kanonik dengan kendala bertanda sama dengan ( ) yang memuat variabel basis, yaitu 1. Kendala (2.1) ditambahkan variabel slack s x1
x 2 2 x 3 s 12, s
0 , kendala menjadi
0
(2.4)
sehingga pada kendala (2.14) variabel basis adalah s , dengan kata lain x1 , x2 , x3 menjadi variabel nonbasis yang nilainya adalah nol. Jadi kendala memberikan nilai s 12 . 2. Kendala (2.2) ditambahkan variabel surplus pada ruas kanan yaitu t
0,
kendala menjadi 2 x1 6 x2
x3
4 t, t
0
(2.5)
selanjutnya variabel t dipindah ke ruas kiri, menjadi 2 x1 6 x2
x3 t
4, t
0.
(2.6)
Jika pada kendala (2.4) s dianggap variabel basisnya
0 , sedangkan
x1 , x2 , x3 menjadi variabel nonbasis yang nilainya adalah nol, maka pada kendala (2.6) nilainya menjadi
t
4 atau t
4.
13
Perlu bi
diingat
bahwa
syarat
awal
0, i 1, 2, ..., m . Karena t
persoalan
program
linear
yaitu
4 maka t tidak memenuhi syarat. Dengan
kata lain t tidak bisa menjadi variabel basis, sehingga perlu ditambahkan suatu variabel yang dinamakan variabel semu (artificial variable). Misal variabel tersebut adalah q1 dengan q1 0 , sehingga pada (2.6) menjadi 2 x1 6 x2
x3 t q1
4,
t , q1
0.
Jika x1 , x2 , x3 dan t adalah variabel nonbasis yang nilainya nol, maka q1
4.
3. Kendala (2.3) sudah berbentuk persamaan tetapi belum memuat variabel basis, maka ditambahkan variabel semu misal q2 x1 Nilai q2
2 x2
x3
q2
8, q2
0 . Sehingga kendala menjadi
0.
8.
Karena setiap kendala sudah berbentuk persamaan, maka rumusan program linear dalam bentuk kanonik adalah Memaksimumkan z( x1, x2 , x3 , s, t, q1, q2 )
8x1 6x2 8x3 0s 0t Mq1 M q2
terhadap kendala: x1
x 2 2 x3 s
2 x1 6 x2 x1
2 x2
12
x3 t q1
4
x3
8
q2
x1 , x2 , x3 , s, t , q1 , q2
(2.7)
0.
Koefisien fungsi sasaran pada (2.7) untuk variabel semu yaitu
M.
Koefisien fungsi sasaran untuk variabel semu bernilai negatif ( ) jika persoalan program linear adalah memaksimumkan dan bernilai positif ( ) jika persoalan program linear adalah meminimumkan. Dengan M adalah bilangan positif yang besar.
14
B. Sistem Persamaan Suatu persamaan dalam matematika merupakan sebuah ekspresi kesamaan (memuat tanda sama dengan " " ) yang melibatkan konstanta, peubah atau variabel (variable) dan operasi-operasi hitung matematika. Di dalam persamaan, komponen-komponen yang dijumlahkan atau dikurangkan disebut suku. Ekspresi di sebelah kiri tanda " " disebut ruas kiri, sedangkan disebelah kanannya disebut ruas kanan. Jika diberikan suatu persamaan yang berbentuk a1x1 a 2 y1 b , maka persamaan ini dinamakan persamaan linear dalam variabel x dan y . Secara umum pesamaan linear dalam n variabel x1 , x2 , ..., xn , dapat dinyatakan dalam bentuk a1 x1 a2 x2 ... an xn
b , dengan a1 , a2 , ..., an dan b adalah konstanta
real; x, y real . Contoh 2.3 berikut ini merupakan contoh persamaan linear. Contoh 2.2 (i) 2 x 3 y
7
(ii) x1 2 x2 3 x3
Solusi persamaan linear a1 x1 a2 x2 ... an xn
x4
6.
b adalah urutan dari n
bilangan s1 , s2 , ..., sn sehingga persamaan tersebut dipenuhi bila bilangan-bilangan s1 , s2 , ..., sn disubstitusikan terhadap x1
s1 , x2
s2 , ..., xn
sn . Himpunan semua
solusi persamaan dinamakan himpunan solusi. Pada Contoh 2.2.(i), untuk mendapatkan solusinya maka ditetapkan sebarang nilai x dan mencari solusi persamaan untuk y, atau sebaliknya memilih sebarang nilai y dan mencari solusi persamaan untuk x. Misal nilai sebarang untuk x adalah t,
15
maka diperoleh
x
7 3
t, y
2 t. 3
Sebuah himpunan berhingga dari persamaan-persamaan linear dalam vaiabel x1 , x2 , ..., xn disebut sistem persamaan linear (SPL) atau sistem linear. Sebuah urutan bilangan-bilangan s1 , s2 , ..., sn disebut solusi dari SPL, jika untuk setiap s1 , s2 , ..., sn memenuhi x1 , x2 , ..., xn . Misal diberikan SPL, 4 x1
x2 3 x3
1,
3 x1
x2 9 x3
4.
SPL di atas mempunyai banyak solusi karena terdiri atas dua persamaan dengan tiga variabel. Salah satu solusi solusinya adalah x1 1, x2
2, x3
1 karena
nilai-nilai ini memenuhi kedua persamaan tersebut. Tidak semua SPL mempunyai solusi, misal diberikan SPL, x
y
4
2x 2 y
6
jika persamaan kedua dari SPL dikalikan dengan x
y
4,
x
y
3.
1 2
maka SPL menjadi
Jelas bahwa SPL tidak mempunyai solusi, karena untuk ( x, y ) yang memenuhi persamaan pertama, nilai 2 x 2 y
2( x
y)
2 4 8 6 , yang tidak pernah
memenuhi persamaan kedua. Suatu sistem persamaan yang tidak mempunyai solusi disebut takkonsisten (inconsistent). Jika setidak-tidaknya terdapat satu solusi, maka sistem persamaan
16
disebut konsisten (consistent).
Untuk melukiskan kemungkinan-kemungkinan
yang dapat terjadi dalam mencari solusi sistem-sistem persamaan linear, berikut ini diberikan sistem umum dari dua persamaan linear dalam variabel x dan y: a1 x b1 y c1
(a1 , b1
0)
a2 x b2 y c 2
(a2 , b2
0)
Grafik dari persamaan-persamaan di atas merupakan garis; misal kedua garis ini dinamakan l1 dan l2 . Titik ( x, y ) terletak pada garis l1 atau l2 jika dan hanya jika
x dan y memenuhi persamaan garis l1 atau l2 , maka solusi sistem persamaan akan bersesuaian dengan titik perpotongan dari garis l1 atau l2 . Terdapat tiga kemungkinan solusi system pesamaan yang diperoleh seperti diperlihatkan pada Gambar 2.1 berikut: y
y
y
x l1 l2
(a) l1 sejajar l2
x l2
l1
(b) l1 dan l2 berpotongan di satu titik
x l1 dan l2
(c) l1 dan l2 berhimpit
Gambar 2.1 Tiga kemungkinan solusi SPL
Pada Gambar 2.1 (a) garis l1 sejajar dengan garis l2 , maka sistem persamaan tidak mempunyai solusi. Gambar 2.1 (b) garis l1 berpotongan dengan garis l2 , maka sistem persamaan tepa t mempunyai satu solusi. Gambar 2.1 (c) garis l1 berhimpit dengan garis l2 , maka sistem persamaan mempunyai takhingga solusi.
17
Sistem persamaan yang ditinjau di atas hanya dua persamaan dengan dua variabel, akan tetapi hasil yang sama akan berlaku untuk sebarang sistem; yaitu sistem persamaan tidak mempunyai solusi, tepat satu solusi dan tak hingga solusi. Suatu sistem terdiri dari m persamaan linear dan n variabel membentuk SPL sebagai berikut: a11 x1
a12 x 2
...
a1n x n
b1
a 21 x1
a 22 x 2
...
a 2 n xn
b2
(2.8)
... a m1 x1
a m 2 x2
...
a nn x n
bm
Kuantitas-kuantitas aij (untuk i 1, 2, ..., m ; j 1, 2, ..., n ) disebut koefisien. Nilai koefisien-koefisien aij dan ruas kanan bi pada setiap persamaan diketahui. Kuantitas-kuantitas xi disebut variabel, yang nilainya belum diketahui.
C. Matriks Sistem persamaan dapat ditulis dalam bentuk matriks. Matriks adalah jajaran bilangan berbantuk empat persegi panjang. Bilangan-bilangan dalam susunan tersebut dinamakan elemen matriks (Wono Setya Budhi, 1995: 16). Ukuran (order) dari sebuah matriks dikatakan sebesar m n jika matriks tersebut memiliki m baris dan n kolom. Matriks biasanya dinyatakan dengan huruf besar
A , B,
. Entri-entri dalam matriks dinyatakan dengan huruf kecil yang berkaitan
dan diberi dua indeks. Jadi matriks m n yang umum dapat dituliskan sebagai
B
b11 b21
b12 b22
b1n a2 n
bm 1
bm 2
a mn
atau bij
. m n
18
Misalkan n bilangan asli. Kumpulan terurut yang terdiri dari n bilangan ditulis sebagai
( x1 , x2 , ..., xn ) . Himpunan dari semua kumpulan terurut
( x1 , x2 , ..., xn ) disebut ruang R n (Wono Setya Budhi, 1995: 164). Elemen dari R n disebut titik atau vektor. Vektor biasanya ditulis dengan huruf kecil dan notasi tebal atau diberi garis di atasnya. Komponen ke-i dari x
( x1 , x2 , ..., xn ) disebut
koordinat ke-i dari vektor atau titik x. Sistem persamaan (2.8) jika ditulis dalam bentuk matriks: Ax
b,
dengan A adalah matriks m n :
A
a11
a12
a1 n
a 21
a 22
a2n ,
a m1
am 2
a mn
x dan b adalah vektor dengan n-komponen: x1 x
x2
b1 dan b
xn
b2
.
bn
Matriks A disebut matriks koefisien, vektor kolom b disebut vektor konstanta. Gabungan Matriks A dan vektor kolom b disebut matriks diperbesar (augmented matriks), sebagai berikut:
Ab
a11 a21
a12 a22
a1n a2 n
b1 b2
am1
am 2
amn
bm
.
19
Metode dasar untuk mencari solusi sistem persamaan adalah mengganti sistem yang diberikan dengan sistem baru yang mempunyai himpunan solusi yang sama dengan solusi yang lebih mudah. Sistem baru ini umumnya diperoleh dalam beberapa tahapan dengan menerapkan operasi pada matriks diperbesar yang dinamakan operasi baris elementer (OBE), yaitu: 1) Menukar dua baris, Rij (baris ke-i ditukar dengan baris ke-j) dari suatu SPL. 2) Mengalikan sebuah baris dengan konstanta tidak nol k, kRi (baris ke-i dikali dengan konstanta tidak nol k). 3) Menambah suatu baris dengan kelipatan baris yang lain, Ri
kR j (baris
ke-i ditambah k kali baris ke-j). 1. Jenis-jenis matriks 1) Matriks kuadrat atau matriks persegi adalah sebuah matriks yang berorder m n atau matriks yang berorder n n .
2) Matriks identitas adalah sebuah matriks kuadrat yang semua elemen diagonal bernilai satu dan semua elemen di luar diagonal bernilai nol; yaitu aij
1 , untuk i
j dan aij
0 , untuk i
j.
3) Vektor baris adalah sebuah matriks dengan satu baris dan n kolom. 4) Vektor kolom adalah sebuah matriks dengan m baris dan satu kolom. 5) Matriks A T disebut transpose dari A jika elemen aij dalam A adalah sama dengan elemen a ji dari A T untuk semua i dan j. Misal,
20
A
1
4
2
5 maka A
3
6
1 2 3
T
4 5 6
.
Secara umum, A T diperoleh dengan menukar baris dan kolom dari A. Akibatnya, jika A memiliki order m n , A T memiliki order n m . 6) Matriks B
0 disebut matriks nol jika setiap elemen dari B sama dengan
nol. 7) Matriks diagonal adalah matriks kuadrat yang elemen-elemennya bernilai nol kecuali elemen-elemen pada diagonal utama. 8) Matriks eselon Suatu matriks disebut matriks eselon jika memenuhi dua sifat sebagai berikut: a. Setiap baris yang hanya terdiri dari elemen nol terletak di bawah. b. Elemen pivot pada suatu baris terletak di sebelah kanan dari elemen pivot sebelumnya. 9) Matriks eselon tereduksi Matriks eselon tereduksi adalah matriks eselon yang mempunyai sifat: a. Setiap elemen pivotnya bernilai satu. b. Setiap elemen pivot merupakan satu-satunya elemen tidak nol pada kolom tersebut. 10) Dua buah matriks A
aij dan B
bij , dikatakan matriks yang sama
jika dan hanya jika keduanya memiliki order yang sama dan setiap elemen
aij adalah sama dengan bij yang bersesuaian untuk semua i dan j.
21
2. Matriks elementer Sebuah matriks n n dinamakan matriks elementer jika matriks tersebut dapat diperoleh dari matriks satuan (identitas) n n yakni I n dengan melakukan sebuah operasi baris elementer tunggal (Anton. H, 1987: 40). Contoh 2.3 Diberikan matriks I 3 : 1 0 0 I3
0 1 0 . 0 0 1
Misalkan dilakukan OBE dengan menambahkan lima kali baris ketiga dari I 3 pada baris pertama, maka diperoleh matriks elementer E: 1 0 5 E
0 1 0 . 0 0 1
Misal diberikan matriks A:
A
1
0 2 3
2
1 3 6 .
1
4 4 0
Pada matriks A dilakukan OBE yang sama dengan I 3 (Contoh 2.3), diperoleh 6 A'
2 1
20 22 3 1 4
3 4
6 . 0
Hasil dari A ' akan sama persis jika matriks E dikalikan dengan matriks A (EA).
22
Hal ini sesuai dengan teorema berikut ini yang dinyatakan tanpa bukti (Anton. H, 1987: 41). Teorema 2.1 Jika matriks elementer E dihasilkan dengan melakukan sebuah OBE pada I m dan jika A adalah matriks m n , maka hasil kali EA adalah matriks yang dihasilkan bila operasi baris yang sama dilakukan pada A. Jika suatu SPL semua suku konstanta sama dengan nol, maka SPL tersebut dinamakan SPL homogen. Tiap-tiap SPL homogen adalah sistem yang konsisten, karena
x1
0, x2
0, ..., xn
0
selalu
merupakan
solusi.
Solusi
tersebut
dinamakan solusi trivial (trivial solution). Jika terdapat solusi lain, maka solusi tersebut dinamakan solusi tak trivial (nontrivial solution). Metode yang sering digunakan untuk mencari solusi dari suatu SPL yaitu metode eliminasi Gauss dan metode eliminasi Gauss-Jordan. Kedua metode ini langkahlangkah pengerjaannya menggunakan serangkaian OBE. 3. Eliminasi Gauss Metode eliminasi Gauss digunakan untuk menyelesaikan suatu SPL dengan mengubah SPL tersebut ke dalam matriks yang berbentuk matriks eselon. Matriks eselon dapat diselesaikan dengan substitusi mundur (back substitution). Sebarang matriks dapat diubah menjadi matriks eselon dengan melakukan serangkaian OBE. Penggunaan OBE pada suatu SPL tidak akan mengubah solusi SPL. Algoritma untuk mengubah sebarang matriks menjadi matriks eselon dengan
23
menggunakan OBE disebut eliminasi Gauss. Algoritma adalah urutan langkahlangkah logis penyelesaian masalah yang disusun secara sistematis. Algoritma untuk eliminasi Gauss adalah: 1. Cari kolom paling kiri yang memuat unsur tidak nol. 2. Jika elemen pertama yang diperoleh dari langkah-langkah pertama sama dengan nol, tukar baris pertama dari matriks dengan baris yang unsur pada kolom tersebut tidak nol. 3. Setelah elemen pertama dari kolom yang diperoleh pada kolom pertama tidak sama dengan nol, dengan OBE dapat dibuat elemen di bawahnya sama dengan nol. 4. Kembali ke proses 1 sampai dengan 3. Contoh 2.4 Diberikan SPL x1 2 x2
3 x3
1
2 x1 5 x2
5 x3
3
3 x1 5 x2 11x3
3
(2.9)
Akan dicari solusi SPL (2.9) menggunakan eliminasi Gauss. Penyelesaian SPL (2.9) ditulis dalam bentuk matriks diperbesar menjadi: 1 2
3
1
2 5
5
3
3 5 11
2
(2.10)
Pada (2.10) diubah menjadi matriks eselon dengan menggunakan eliminasi Gauss: 1) Kolom paling kiri sudah memuat unsur tidak nol.
24
2) Membuat nol elemen a21 dan a31 dengan cara menambahkan baris ke-2 dengan ( 2) kali baris pertama dan baris ke-3 dengan ( 3) kali baris pertama, menghasilkan 1
2
3
1
0 0
1 1
1 2
5 1
(2.11)
3) Membuat nol elemen a32 pada (2.11) dengan cara menambahkan baris ke3 dengan baris ke-2, menghasilkan 1 2
3
1
0 1
1
5
0 0
1
6
(2.12)
(2.12) merupakan matriks eselon dan dengan substitusi mundur diperoleh solusi SPL (2.9) yaitu x1 31, x 2
11 dan x3
6.
4. Eliminasi Gauss-Jordan Metode eliminasi Gauss-Jordan pada dasarnya hampir sama dengan metode eliminasi Gauss. Pada eliminasi Gauss, dibentuk elemen-elemen matriks A dibawah diagonal utama menjadi nol (matriks eselon). Pada metode eliminasi Gauss-Jordan dibentuk menjadi nol elemen-elemen di bawah maupun di atas diagonal utama matriks A. Hasilnya adalah matriks eselon tereduksi yang berupa matriks diagonal yaitu matriks kuadrat yang elemen-elemennya bernilai nol kecuali elemen-elemen pada diagonal utama. Proses menjadikan suatu matriks A menjadi matriks eselon terduksi disebut eliminasi Gauss-Jordan. Algoritma eliminasi Gauss-Jordan: 1. Ubah matriks menjadi matriks eselon.
25
2. Bagi baris yang mempunyai elemen pivot dengan besarnya elemen pivot (untuk memenuhi sifat matriks eselon tereduksi a ). 3. Dengan OBE, elemen di atas elemen pivot dibuat menjadi nol. Dari Contoh 2.9, solusi SPL dicari dengan menggunakan metode eliminasi Gauss-Jordan. Langkah-langkahnya yaitu setelah langkah ke-3, langkah berikutnya adalah: 1) Membuat nol elemen a23 pada (2.12) dengan cara menambahkan baris ke2 dengan baris ke-3, menghasilkan 1 2 3
1
0 1 0 0 0 1
11 6
(2.13)
2) Membuat nol elemen a13 pada (2.13) dengan cara menambahkan baris ke1 dengan ( 3) kali baris ke-3, menghasilkan 1 2 0
19
0 1 0
11
0 0 1
6
(2.14)
3) Membuat nol elemen a12 pada (2.14) dengan cara menambahkan baris ke1 dengan ( 2) kali baris ke-2, menghasilkan 1 0 0
31
0 1 0 0 0 1
11 6
Pada langkah ke-3 diperoleh matriks eselon tereduksi, sehingga solusi dari SPL (2.9) dapat dibaca pada kolom terakhir, yaitu x
(31, 11, 6)T .
26
Contoh 2.9 merupakan contoh mencari solusi suatu SPL menggunakan metode eliminasi Gauss dan eliminasi Gauss-Jordan. Jika kedua metode ini dibandingkan maka menggunakan eliminsai Gauss-Jordan akan lebih efektif, karena dapat langsung dilihat hasilnya dengan membaca kolom terakhir tanpa harus melakukan substitusi. 5. Operasi matriks Operasi matriks berupa penambahan, pengurangan dan perkalian yang didefinisikan. Pembagian, walaupun tidak didefinisikan digantikan dengan konsep inversi. 1) Penambahan atau pengurangan matriks. Dua matriks
A
aij
dan
B
bij
dapat ditambahkan atau
dikurangkan jika keduanya memiliki order yang sama, misalnya m n . Jumlah D
A B diperoleh dengan menambahkan elemen-elemen yang
bersesuaian. Jadi
dij m n
aij bij . m n
2) Perkalian matriks Dua matriks A
aij
dan B
bij
dapat dikalikan dalam urutan AB
jika dan hanya jika jumlah kolom A adalah sama dengan jumlah baris B, yaitu, jika A memiliki order m r , maka B harus memiliki order r n , dengan m dan n order sebarang. Misal D
AB . Maka D memiliki urutan m n , dan elemen d ij diketahui: r
d ij
aik bkj , untuk semua i dan j. k 1
27
Contoh 2.5 1 3
A
2 4
D
5 7 9
dan B
6 8 0
, maka
1 3 5 7 9
(1 5) (3 6)
2 4 6 8 0 23 31 9 . 34 46 18
(2 5) (4 6) (2 7) (4 8) (2 9) (4 0)
Jika diperhatikan, secara umum AB
(1 7) (3 8)
(1 9) (3 0)
BA sekalipun BA didefinisikan.
6. Invers matriks Invers suatu matriks persegi A dilambangkan dengan A yang memenuhi A 1A
AA
1
1
adalah matriks
I.
Invers ini ada jika A tidak singular. Jika diketahui matriks A n
A
A
1
a11
a12
a1n
a21
a22
a2 n
an1
an 2
ann
, maka
1 adj( A) det( A)
adj( A) CT
C
n
dan
C
C11 C12 C21 C22
C1n C2 n
Cn1 Cn 2
Cnn
dengan Cij
adalah
matriks
kofaktor
( 1)1 j M ij dan M ij minor matriks A.
A,
dengan
28
7. Hasil perkalian matriks Sebagian besar perhitungan pada metode simpleks direvisi adalah mengenai penggantian B
1
dari satu tabel ke tabel berikutnya. Hasil dari invers ini
akan digunakan untuk mempermudah perhitungan B
1
yang baru. Diasumsikan
bahwa xk akan masuk menjadi basis, uji rasio menunjukkan bahwa xk menjadi basis pada baris ke-r, dengan xk Didefinisikan matriks E m
E
1
0
0
1
0
0
0
0
0
0
m
a1k a2 k
ark
amk
T
.
sebagai berikut: a1 k a rk a2k a rk 1 a rk a(m
1) k
a rk a mk a rk
0
0
0
0
0
0
1
0
0
1
E adalah matriks identitas ( I m m ) dengan kolom ke-r nya diganti dengan vektor kolom
a1k ark
a2 k ark
1 ark
a( m
1) k
ark
amk ark
T
.
Selanjutnya didefinisikan Ei sebagai matriks elementer E yang berkaitan dengan iterasi simpleks ke-i. Hasil kali invers (invers product) secara umum dapat ditulis: B k
1
Ek 1 Ek
2
E1 E 0 (Winston 2004).
29
D. Persoalan Knapsack Persoalan knapsack didefinisikan sebagai persoalan yang menyangkut pemilihan objek dengan bobot dan keuntungan tertentu sedemikian sehingga tidak melebihi kapasitas yang telah ditentukan dan keuntungan yang ditargetkan dapat tercapai (Douglas R. Stinson, 1995: 191). Persoalan knapsack atau persoalan ransel adalah persoalan program linear bilangan bulat yang hanya memiliki kendala tunggal (Tjutju Tarliah dan Ahmad Dimyati, 1992: 228). Nilai variabel-variabel kendala pada persoalan knapsack dapat berupa sebarang nilai. Akan tetapi ada juga persoalan knapsack yang seluruh variabelnya harus bernilai 0 atau 1, yang dapat diformulasikan: Memaksimumkan z ( x j )
c1 x1 c2 x2 ... cn xn
terhadap kendala:
a1 x1 a2 x 2 ... amn x n b xj
0 atau 1 ( j 1, 2, ..., n) ; i 1, 2, ..., m,
(2.15)
dengan c j adalah manfaat yang dapat diperoleh apabila barang ke-j dipilih, b adalah jumlah sumber yang tersedia dan ai adalah jumlah sumber yang digunakan oleh barang ke-i. Meskipun secara teoritis persoalan knapsack sulit diselesaikan, namun metode pencabangan dan pembatasan (branch and bound method) cukup efisisen dan praktis untuk menyelesaikannya (Taha 1996; Winston 2004). Pada persoalan (2.15) jika diselesaikan dengan branch and bound, maka ada dua aspek pendekatan dari branch and bound yang disederhanakan. Pertama, karena setiap variabel harus berharga 0 atau 1, maka pencabangan pada x j akan menghasilkan
30
cabang x j
0 dan x j
1 . Kedua, solusi persoalan program linear relaksasi; yaitu
bentuk program linear yang diperoleh dengan mengabaikan kendala (pembatas) bilangan bulat (integer) serta subpersoalan yang lain dapat diselesaikan dengan melakukan pengecekan terhadap nilai
cj ai
. Untuk melihat hal ini maka nilai
cj ai
dapat diinterpretasikan sebagai manfaat yang diperoleh barang ke- j dari setiap unit sumber yang digunakan barang ke- i . Jadi, barang yang terbaik adalah barang yang memiliki nilai
memiliki nilai
cj ai
cj ai
terbesar dan barang yang terburuk adalah barang yang
tekecil.
Untuk menyelesaikan setiap subpersoalan yang dihasilkan dari suatu persoalan ransel, dihitung seluruh rasio nilai
cj ai
. Kemudian barang yang terbaik
dimasukkan ke dalam ransel. Selanjutnya barang kedua terbaik dan seterusnya, hingga ransel terisi dengan sebanyak-banyaknya dari barang-barang ini.
E. Metode Simpleks Metode simpleks merupakan prosedur umum untuk menyelesaikan persoalan-persoalan program linear. Prosedur ini dikembangkan oleh George Dantziq pada tahun 1947. Metode simpleks juga merupakan salah satu metode yang efisien yang digunakan untuk menyelesaikan persoalan program linear skala besar dengan komputer masa kini.
31
Metode simpleks merupakan suatu algoritma, karena dalam menyelesaikan persoalan dengan metode simpleks, prosesnya dilakukan secara iteratif. Setiap prosedur iteratif merupakan suatu algoritma. Suatu algoritma ialah suatu prosedur sistematis diulang-ulang (iterasi) sampai hasil yang diinginkan tercapai. Selain iterasi, algoritma juga mencakup suatu prosedur untuk memulai dan suatu kriteria untuk menentukan kapan berhenti. Bagi kebanyakan algoritma riset operasi, termasuk metode simpleks, hasil yang diinginkan yang tercantum dalam aturan berhenti yaitu penyelesaian pada iterasi tertentu adalah optimal. Dalam hal ini, aturan berhenti sebenarnya merupakan suatu uji optimalitas, dijelaskan dalam diagram alir berikut. mulai
data masukan
iterasi tidak Hasil Optimal ya berhenti Gambar 2.2 Diagram alir metode simpleks Metode simpleks juga merupakan struktur aljabar yang bersifat iteratif, dimulai dari suatu titik ekstrem pada daerah layak atau fisibel (feasible) menuju ke titik ekstrem yang optimum, sehingga diperoleh solusi layak titik ekstrem.
32
Solusi titik ekstrem atau titik sudut pada persoalan dua atau tiga variabel adalah solusi layak yang tidak terletak pada suatu segmen garis yang menghubungkan dua solusi layak lainnya. Untuk mendapatkan solusi layak titik ekstrem ini, kendala-kendala dibuat dalam bentuk grafik. Pasangan ( x, y ) yang memenuhi semua kendala disebut solusi layak. Titik wakilnya dalam bidang koordinat disebut titik layak. Himpunan titik-titik layak disebut daerah layak. Langkah-langkah penyelesaian persoalan program linear dengan metode simpleks adalah sebagai berikut: 1. Menambahkan variabel slack, surplus dan artifisial ke dalam kendala-kendala sehingga kendala-kendala berubah menjadi bentuk kanonik dan mempunyai variabel basis . 2. Persamaan pada ruas kanan fungsi sasaran dipindah ke ruas kiri sehingga fungsi sasaran mempunyai nilai awal nol dan algoritma simpleks berawal dari titik nol. 3. Menyusun tabel awal simpleks, lengkap dengan variabel basisnya. 4. Melakukan uji optimal pada tabel awal tersebut, dengan langkah-langkah sebagai berikut: a. Untuk persoalan memaksimumkan dicari variabel basis baru, dengan memilih kolom pivot, yaitu kolom dengan z j
c j negatif terbesar. Untuk
persoalan meminimumkan dicari variabel basis baru dengan memilih kolom pivot, yaitu kolom dengan nilai z j
c j positif terbesar.
33
b. Dicari nilai Ri , yaitu bi dibagi unsur-unsur pada kolom pivot yang bernilai positif ( Ri
bi , aik positif ). Selanjutnya dipilih Ri terkecil. aik
c. Baris dengan Ri terkecil menjadi baris pivot dengan menunjukkan variabel basis lama yang akan diganti. Perpotongan antara baris pivot dan kolom pivot disebut sebagai elemen pivot. d. Disusun tabel selanjutnya dengan variabel basis baru dan koefisien ongkos menyesuaikan dengan variabel basis baru tersebut. e. Dilakukan Operasi Baris Elementer (OBE) dengan tujuan elemen pivot bernilai 1. 5. Tabel berikutnya sudah siap, dilakukan uji optimal pada tabel tersebut dengan langkah-langkah (a) sampai (e). Tabel dikatakan optimal jika z j
c j nonnegatif untuk setiap j .
Adapun tabel simpleks, disajikan dalam Tabel 2.1 berikut.
34
Tabel 2.1 Metode Simpleks
cj xi \ x j
ci
c1
c2
c3
cn
x1
x2
x3
xn
bi
Ri
c1
x1
a11
a12
a13
a1n
b1
R1
c2
x2
a21
a22
a23
a2 n
b2
R2
c3
x3
a31
a32
a33
a3n
b3
R3
cm
xm
am1
am 2
am 3
amn
bm
Rm
zj
z1
z2
z3
zn
Z
z1 c1
z 2 c2
z3 c3
z n cn
Z
zj keterangan: cj
cj
: koefisien biaya untuk variabel x j
ci
: koefisien biaya untuk variabel x i ,
xi
: variabel yang menjadi basis dalam tabel yang ditinjau,
xj
: variabel-variabel lengkap,
bi
: suku tetap (tak negatif),
Ri
: rasio,
aij
: koefisien teknis,
zj
:
m
c i aij (hasil kali dari c i dengan aij ), i 1
m
Z
c i bi (hasil kali dari c i dengan bi ),
: i 1
zj
c j : selisih z j dengan c j .
35
Contoh 2.6 Memaksimumkan z ( x1 , x2 , x3 )
60 x1 30 x2
20 x3
terhadap kendala: 8 x1 6 x2 4 x1 3 x1
x3
3 x3 20 2 1 x3 8 2 5
2 x2 3 x2 2 x2
x1 , x2 , x3
48
(2.16)
0
Penyelesaian 1) Tambahkan variabel slack si , i 1, 2, 3, 4 pada kendala (2.16), menjadi Memaksimumkan z ( x1 , x2 , x3 , si )
5 x1
4 x2
6 x3
0 s1 0s2
terhadap kendala: 8 x1 6 x2 4 x1 3 x1
2 x2 3 x2 2 x2
x3
s1 0 s2
3 x3 0 s1 s2 0 s3 2 1 x3 0 s1 0s2 s3 2 0 s1 0 s2 0 s3
x1 , x2 , x3 , s1, s2 , s3 , s4 2) Membuat Tabel Awal simpleks
0s3
0
0 s4
48
0 s4
20
0 s4
8
s4
5
0 s3
0 s4
36
Tabel 2.2 Tabel Awal Simpleks
cj
60
30
20
0
0
0
0
ci
xi \ x j
x1
x2
x3
s1
s2
s3
s4
bi
0
s1
8
6
1
1
0
0
0
48
s2
4
s3
2
s4
0
1
0
0
0
0
1
5
zj
0
0
0
0
0
0
0
0
60
30
20
0
0
0
0
0
0 0 0
zj
Ri 48 8
cj
2 3
2
3 1
2 2
0
1
0
0
20
20 4
0
0
1
0
8
8 2
6 5 4
Langkah-langkah uji optimum tabel (Tabel 2.2): (a) Memilih kolom z j
c j terbesar (negatif) adalah
variabel masuk, (b) Memilih rasio terkecil:
b3 a31
8 2
4 , jadi s3 variabel keluar,
(c) Membagi baris ke-3 dengan a31 , (d) Membuat Tabel Antara, yaitu:
60 , jadi x1 merupakan
37
Tabel 2.3 Tabel Simpleks Antara
cj
60
30
20
0
0
0
0
ci
xi \ x j
x1
x2
x3
s1
s2
s3
s4
bi
0
s1
8
6
1
1
0
0
0
48
R1
2
3
0
1
0
0
20
R2
0
0
1
0
4
R3 R4
0
4
0 0
2
s3
1
s4
0
1
0
0
0
0
1
5
zj
0
0
0
0
0
0
0
0
30
20
0
0
0
0
0
3
60
z j cj
1
4
4
2
Rz
(e) Melakukan Operasi Baris Elemeter (OBE), dengan menolkan elemen yang diberi tanda persegi panjang. (Diperoleh Tabel 2.4) R1= R1 – 8R3 R2= R2 – 4R3 Rz= Rz + 60R3 Tabel 2.4 Tabel Kedua Simpleks
cj
60
30
20
0
0
0
0
ci
xi \ x j
x1
x2
x3
s1
s2
s3
s4
bi
0
s1
0
0
1
1
0
4
0
16
s2
0
x1
1
s4
0
1
0
0
0
0
1
5
zj
60
45
15
0
0
30
0
240
z j cj
0
15
5
0
0
30
0
240
0
Ri 16
16
1 1
0
1
1
2
0
4
4
2
8
1 2
60
3
4
0
1
0
4
0
1
4
4
2
16
1 4
0
5 0
38
3) Pada langkah ini sama dengan langkah 2 (a sampai e), dengan memperhatikan Tabel 2.4, (a) z j
c j terbesar (negatif) adalah
5 , jadi x3 merupakan variabel masuk,
(b) Memilih rasio terkecil: b2 a32
4 1 4
8 , jadi s2 variabel keluar,
(c) Membagi baris ke-2 dengan a23 , (d) Membuat Tabel Antara, yaitu: Tabel 2.5 Tabel Simpleks Antara
cj
60
30
20
0
0
0
0
ci
xi \ x j
x1
x2
x3
s1
s2
s3
s4
bi
0
s1
0
0
1
1
0
4
0
16
2
0
1
2
0
8
R2 '
4
0
0
2
0
4
R3 '
x3
20
x1
60 0
1
0
1
1
3
4
1
1
s4
0
1
0
0
0
0
1
5
zj
60
45
15
0
0
30
0
240
z j cj
0
15
5
0
0
30
0
240
R1 '
R4 '
Rz '
(e) Melakukan Operasi Baris Elemeter (OBE), dengan menolkan elemen yang diberi tanda persegi panjang. (Diperoleh Tabel 2.6)
' R R 1 2 ' R3 R3 1 R2 3 R1
Rz
' R 5R z 2
39
Tabel 2.6 Tabel Ketiga Simpleks
cj
60
30
20
0
0
0
0
ci
xi \ x j
x1
x2
x3
s1
s2
s3
s4
bi
0
s1
0
2
0
1
2
8
0
24
20
x3
0
2
1
0
2
4
0
8
60
x1
2
0
0
1
0
2
0
s4
0
1
0
0
0
0
1
5
zj
60
35
20
0
10
10
0
280
0
5
0
0
10
10
0
280
zj
cj
Karena z j
cj
fungsi
sasaran
5
4
2
1
2
0 untuk setiap j, maka tabel sudah optimal dengan nilai
( x1 , x2 , x3 , s1 , s2 , s3 , s4 )
z
280 ,
solusi
layak
basisnya
(2, 0, 8, 24, 0, 0, 5) .
F. Metode Simpleks Direvisi Metode simpleks direvisi merupakan kelanjutan dari metode simpleks. Dalam menyelesaikan persoalan program linear, metode simpleks bukan merupakan suatu prosedur perhitungan yang paling efisien jika diaplikasikan perhitungannya menggunakan komputer. Kode-kode pada komputer tidak secara tepat mengikuti bentuk aljabar atau bentuk tabel dari metode simpleks. Kode-kode ini memakai suatu bentuk matriks yang sesuai dengan komputer. Hal inilah yang mendorong berkembangnya metode simpleks direvisi. Gagasan utama dari metode simpleks direvisi adalah menggunakan inversi basis B-1 (data awal dari persoalan) untuk melakukan perhitungan yang diperlukan
40
untuk menentukan
variabel masuk dan variabel keluar. Metode simpleks
direvisi secara eksplisit memakai manipulasi matriks, maka persoalan harus dinyatakan dalam notasi matriks. Dengan menggunakan matriks, bentuk baku model program linear menjadi: Memaksimumkan z
cx,
terhadap kendala: Ax( , , )b dan x 0
(2.17)
dengan: c
c1 , c2 ,..., cn merupakan vektor baris, x1
x
x2
b1 b2
,b
xn
0 ,0
bm
0
merupakan vektor-vektor kolom,
0
A merupakan matriks m n :
A
a11
a12
a1n
a21
a22
a2 n
am1 am 2
amn
.
Untuk memperoleh persoalan program linear bentuk kanonik dalam bentuk matriks maka pada (2.17) ditambahkan variabel slack:
s
s1 s2
,
sn
sehingga (2.17) dalam bentuk kanonik menjadi:
41
Memaksimumkan z (x, s) c VB x VB
c NBs
terhadap kendala: x
A, I
s
b dan
x s
0,
dengan c VB
koefisien-koefisien fungsi tujuan yang berkaitan dengan x B
x VB
variabel basis
c NB
koefisien-koefisien fungsi tujuan yang berkaitan dengan s
s
variabel slack
I
matriks identitas m
n.
1. Solusi layak basis Pendekatan umum dari metode simpleks dan metode simpleks direvisi adalah memperoleh suatu ururtan solusi-solusi layak basis yang semakin baik sampai tercapai suatu solusi optimal. Salah satu ciri pokok dari metode simpleks direvisi mencakup dengan cara mana setiap solusi layak basis akan diselesaikan, yaitu setelah variabel-variabel basis dan nonbasis diketahui. Jika diketahui A , I
x s
yang tidak diketahui, dengan x
b , memiliki m persamaan dan n variabel
( x1 , x2 , ..., xn ) T dan s ( s1 , s2 , ..., sn )T adalah
variabel slack; suatu solusi layak basis diperoleh dengan menetapkan n m sama dengan nol. Jika n variabel ini dieliminasi dengan membuatnya sama dengan nol maka masih ada suatu himpunan m persamaan dengan m variabel yang tidak diketahui. Himpunan persamaan ini dapat dinyatakan Bx VB
b,
42
dengan xVB1 xVB 2
x VB
xVB m
merupakan vektor kolom variabel basis, diperoleh dengan menghilangkan variabel-variabel nonbasis dari
B
x s
B11
B12
B1m
B21
B22
B2 m
Bm1 Bm 2
Bmm
,
merupakan matriks basis yang diperoleh dengan mengeliminasi kolom-kolom yang berkaitan dengan kofisien- kofisien variabel basis dari A, I . Metode
simpleks
memperkenalkan
hanya
sedemikian sehingga B adalah nonsingular, sehingga B karena itu, untuk menyelesaikan Bx VB
variabel-variabel 1
basis
akan selalu ada. Oleh
b , kedua ruas harus dikalikan terlebih
dahulu dengan B 1 , sehingga diperoleh
B 1Bx VB
B 1b .
Karena B 1B I , maka solusi yang diharapkan untuk variabel-variabel basis adalah
x VB
B 1b .
43
Misal c VB adalah vektor yang unsur-unsurnya merupakan koefisien-koefisien fungsi tujuan (termasuk nol untuk variabel-variabel slack) yang berkaitan dengan x VB , maka nilai fungsi tujuan untuk solusi basisnya adalah
z c VBx VB
c VBB 1b .
Dalam metode simpleks direvisi, iterasi simpleks hanya berbeda dalam definisi basis B menunjukkan keuntungan dalam perhitungan: 1) Dalam persoalan program linear skala besar, penggunaan operasi GaussJordan umumnya mengarah pada kesalahan pembulatan yang tidak dapat dikendalikan sehingga memberikan pengaruh yang merugikan terhadap hasil akhir. Dalam metode simpleks direvisi digunakan B-1 dan data awal dari persoalan. Dengan demikian akurasi perhitungan dapat dikendalikan dengan mengendalikan kesalahan pembulatan dalam perhitungan B-1 saja. 2) Dengan menggunakan manipulasi matriks menunjukkan bahwa tidak perlu menghitung semua entri dari tabel simpleks, untuk ukuran persoalan program linear tertentu kemungkinan memerlukan lebih sedikit perhitungan. 2. Langkah-langkah metode simpleks direvisi Langkah-langkah dari metode simpleks direvisi pada intinya sama dengan metode simpleks. Dengan diketahui basis awal I, ditentukan koefisien tujuan yang berkaitan dengan c VB . Adapun langkah-langkah metode simpleks direvisi adalah: 1. Menetapkan bahwa kolom B pada awalnya.
1
yang bersangkutan akan selalu dibaca B
1
I
44
1
2. Menghitung c VB B
untuk tabel bersangkutan.
3. Menghitung harga akhir (price out) semua variabel nonbasis dalam tabel bersangkutan. Jika harga akhir tiap-tiap variabel nonbasis nonnegatif maka basis bersangkutan adalah optimal. Jika basis bersangkutan tidak optimal maka dimasukkan ke dalam basis yaitu variabel nonbasis yang mempunyai nilai koefisien negatif terbesar dalam baris 0. Misal variabel nonbasis yang masuk menjadi variabel basis didefinisikan dengan xk , k 1, 2, ..., n . 4. Untuk menentukan dalam baris mana xk menjadi basis masuk, hitung kolom xk dari tabel bersangkutan (B 1 xk ) dan hitung sisi kanan dari tabel bersangkutan (B 1b) . Kemudian digunakan test rasio untuk menentukan dimana baris xk seharusnya masuk menjadi basis, sehingga diperoleh himpunan variabel basis untuk tabel baru (menggunakan OBE). 5. Gunakan kolom xk dalam tabel bersangkutan untuk menentukan aturan atau langkah ini pada B
1
yang bersangkutan untuk memperoleh B
1
baru.
Kembali ke langkah 1. Contoh 2.7 Memaksimumkan z ( x1 , x2 ) 3 x1 5 x 2 terhadap kendala:
x1
4 x2
6
3x1 2 x2 18 x1 , x2
0 dan bilangan bulat.
(2.18)
45
Penyelesaian 1. Persoalan (2.18) diubah ke bentuk program linear kanonik dengan menambahkan variabel slack menjadi: Memaksimumkan z ( x1 , x2 , s1 , s2 , s3 ) 3 x1 5 x 2 0s1 0 s2
0 s3
terhadap kendala:
x1
s1 x2
4
s2
3x1 2 x2
6 s3 18
x1, x2 , s1, s2 , s3 0 dan bilangan bulat atau ditulis dalam bentuk tabel, yaitu: Tabel 0 Baris 0 z 3 x1 5 x 2 Baris 1
x1
s1
Baris 2
x2
Baris 3
3 x1 2 x2
dengan VB(0) 1
Kolom B 0
4 s2
6 s3 18
s1 , s2 , s 3 dan VNB(0)
terbaca awalnya yaitu B 0
1
x1, x2 . I
1 0 0 B0
1
B0
I
0 1 0 . 0 0 1
2. Menentukan variabel nonbasis yang akan masuk menjadi variabel basis dengan menghitung koefisien dari tiap-tiap variabel nonbasis dalam baris 0, diperoleh c VB
0 0 0 , sehingga
c VBB 0
1
1 0 0 0 0 0 0 1 0 0 0 1
0 0 0
46
3. Dari langkah (2) diperoleh nilai dari tiap-tiap variabel nonbasis adalah:
1
c1 cVBB 0 a1 c1
1
c 2 c VBB 0 a2 c2
1 0 0 0 0 3 0 0 0 0 1 2
3
3
5
5
( c1 , c 2 0 , maka basis belum optimal), dicari variabel nonbasis xk yang mempunyai koefisien negatif terbesar dari baris 0 dalam Tabel 0 yang menjadi variabel basis masuk . Karena x2 mempunyai koefisien negatif terbesar dalam baris 0, maka x2 variabel basis masuk menggantikan variabel basis keluar s2 . 4. Kolom untuk x2 dalam tabel bersangkutan:
1
a 2 B 0 a2
1 0 0
0
0
0 1 0 0 0 1
1 2
1 2
Sisi kanan tabel bersangkutan 1
B0 b
1 0 0
4
4
0 1 0
6
6
0 0 1 18
18
Selanjutnya digunakan test rasio untuk menentukan x2 masuk ke dalam baris yang mana, yaitu: Baris 1, x2 Baris 2, x2 Baris 3, x2
4
tidak terdefinisi 0 6 6 ( test rasio terkecil) 1 18 9 2
Jadi x2 masuk sebagai basis dalam baris 2. 5. Dari langkah (4) dibentuk Tabel 1 dengan melakukan OBE, sebagai berikut:
47
a) Pada baris ke-1 tetap, karena nilai di atas baris ke-2 kolom 2 dari kiri (baris 1' )
sudah bernilai nol. b) Baris ke-2 tetap.
(baris 2' )
c) Menambahkan baris ke-3 dengan ( 2) kali baris ke-2
(baris 3' )
d) Menambahkan baris ke-0 dengan ( 5 ) kali baris ke-2.
(baris 0' )
Diperoleh tabel baru, misal dinamakan Tabel 1 Tabel 1 Baris 0' z 3 x1 Baris 1 '
5s 2
x1
Baris 2'
s1
4
x2
Baris 3'
s2
3 x1
dengan VB(1)
30 6 s3
6
s1, x 2 , s3 dan VNB(1)
6. Melakukan OBE pada B 0
1
x1 , s 2 .
dengan langkah seperti pada langkah (5) (a
sampai c), diperoleh:
B1
7. c VBB1
1
1
1
0 0
0
1 0
0
2 1
1
0 0
0 5 0 0 0
1 0 2 1
0 5 0
8. Dari langkah (7) diperoleh nilai dari tiap-tiap variabel nonbasis x1 , s 2 :
1 0 5 0 0 3
1
c1 c VBB1 a1 c1
s 2 c VBB 0
1
0 1 0
0
0 0 5 0 1 0
3
3
0 5
48
Tabel belum optimal, karena masih terdapat c j yang negatif, yaitu c1
0 ; x1
mempunyai koefisien negatif terbesar dalam baris 0 dari Tabel 1, sehingga x1 masuk sebagai basis dalam Tabel 1. 9. Kolom untuk x1 pada Tabel 1 yaitu:
1
B1 a1
1
0
0
1
1
0
1
0
0
0
0
2 1
3
3
Sisi kanan pada Tabel 1
1
B1 b
1
0 0
4
4
0 0
1 0 2 1
6 18
6 6
Test rasio:
Baris 1, x1 Baris 2, x1 Baris 3, x1
4
1 6 0 6 3
4 tidak terdefinisi 2 (test rasio terkecil)
Dari test rasio terlihat bahwa x1 masuk sebagai basis dalam baris 3. 10. Dari langkah (9) dibentuk Tabel 2 dengan OBE: a) Menambahkan baris ke-1 Tabel 1 dengan ( 1 ) kali baris ke-3. (baris 1" ) 3
b) Baris ke-2 tetap, karena x1 pada baris 2 sudah nol.
(baris 2" )
c) Mengalikan baris ke-3 dengan 1 . 3
(baris 3" )
d) Menambahkan baris ke-0 dengan baris ke-3.
(baris 0" )
Diperoleh Tabel 2:
49
Tabel 2 Baris0" z
5s 2
Baris1"
s1
Baris2"
x2
Baris3" dengan VB(2)
s3
2 s2
x1
6 s3
s1, x 2 , x1 dan VNB(2) 1
11. Melakukan OBE pada B1
36
2
s3 , s 2 .
seperti pada langkah (10) (a sampai c), sehingga
diperoleh: 2
1 B2
1
1
3 1 2 3
0 0
3 0
1
1
12. c VBB 2
1
0 5 3 0 0
3 2
3 1 2 3
1
3 0
1
0 3 1
3
13. Dari langkah (12) diperoleh nilai variabel nonbasis s3 , s2 adalah
s 3 c VBB 0
1
s 2 c VBB 0
1
0 0 1 0 1 0
0
0 0 3 1 0 1
0 1
0
0 0 3 1 1 0
0 3
Tabel 2 sudah optimal karena setiap koefisien variabel nonbasis dalam baris 0" sudah tidak ada yang negatif.
14. Sisi kanan dari Tabel 2:
50
2
1 1
B2 b
3 1 2 3
0 0
Sehingga VB(2) s1
2
x2 x1
6 , s2 2
1
4
2
1
6 18
6 2
3 0 3
s1 , x 2 , x1 dan solusi layak basisnya adalah
s3
0
Jadi diperoleh tabel optimal untuk nilai z yaitu: 4 1
c VBB 2 b
Jadi
nilai
0 3 1 6 18
fungsi
( x1 , x2 , s1 , s2 , s3 )
36 .
sasaran
yaitu
z 36 ,
solusi
layak
basisnya
(2, 6, 2, 0, 0) .
G. Program Linear Bilangan Bulat Program linear bilangan bulat merupakan bentuk khusus dari program linear, dengan satu atau lebih dari variabel-variabel dalam penyelesaiannya disyaratkan memiliki nilai-nilai bilangan bulat. Dalam program linear kebanyakan variabel yang dilibatkan berupa variabel-variabel bilangan bulat, variabel tersebut hanya diperkenankan untuk memiliki nilai-nilai bilangan bulat yang terletak di antara batas yang tetap. Program linear bilangan bulat adalah program linear dengan beberapa atau semua
S
x Ax
variabelnya
b, x
( x1 , x2 ,..., x j ), x j
adalah
anggota
himpunan
0,1,2,... . Program linear bilangan bulat
51
terdiri dari dua macam, yaitu program linear bilangan bulat murni dan program linear bilangan bulat campuran. Program linear bilangan bulat dikatakan program linear bilangan bulat murni atau campuran bergantung pada beberapa atau semua variabel yang digunakan dibatasi pada nilai-nilai bilangan bulat. 1. Program linear bilangan bulat murni Program linear bilangan bulat murni adalah program linear bilangan bulat yang semua variabelnya dibatasi hanya bernilai bilangan bulat. Dalam model program linear ditulis: n
Memaksimumkan atau meminimumkan: f =
cjxj , j 1
terhadap kendala: n
n
aij x j j 1
xj
bi , atau
n
aij x j
bi , atau
j 1
0, x j
aij x j
bi , i 1,2,..., m
j 1
0,1,2,... , j 1,2,..., n ,
dengan aij , bi dan ci adalah konstanta, x j adalah variabel nonnegatif yang akan dicari nilainya dan dibatasi pada nilai bilangan bulat dan f adalah fungsi tujuan. 2. Program linear bilangan bulat campuran Program linear bilangan bulat campuran adalah program linear bilangan bulat yang hanya beberapa variabelnya bernilai bilangan bulat. Bentuk umum dari persoalan program linear bilangan bulat campuran dengan k variabel yang dibatasi pada bilangan bulat adalah:
52
n
Memaksimumkan atau meminimumkan: f =
cjxj , j 1
terhadap kendala: n
t
aij x j j 1
xj
aik yk
bi ,
k 1
0, j 1, 2, ..., n
x j bilangan bulat; j 1, 2, ..., k ; k
n
dengan aij , bi dan ci adalah konstanta, x j ; j 1, 2, ..., k
adalah variabel
nonnegatif yang dibatasi pada nilai bilangan bulat dan f adalah fungsi tujuan. Program linear bilangan bulat diselesaikan dengan mengabaikan syarat terlebih dahulu, sehingga program linear bilangan bulat dianggap sebagai program linear. Jika di dalam penyelesaian optimal program linearnya diperoleh penyelesaian bulat, maka penyelesaian inipun optimal untuk program linear bilangan bulat. Hal ini didasari sifat berikut. Sifat 2.2 Jika terdapat dua persoalan program linear P1 dan P2 Dengan P1: memaksimumkan f ( x), x S1 P2: memaksimumkan f ( x), x S 2 dan S1
S 2 , maka jika x0 adalah
suatu penyelesaian optimal dalam P1 dan x* adalah suatu penyelesaian optimal dalam P2, maka berlaku f ( x 0 )
f ( x* ) .
Bukti: Diketahui
x0
adalah
penyelesaian
memaksimumkan, berlaku f ( x0 )
optimal
P1,
dengan
f ( x), x S1 . Karena S1
persoalan
S 2 dan S 2
S1
53
sehingga
f ( x0 )
f ( x), x S 2 .
penyelesaian optimal dalam
f ( x0 )
Karena P2 maka
variabel
x*
merupakan
suatu
x* elemen dari S 2 , sehingga
f ( x* ) .
Akibat Sifat 2.2 Jika x0
S 2 , maka x0 juga suatu penyelesaian optimal dalam P2. Jadi bila
diambil P1 sebagai suatu persoalan program linear dan P2 sebagai suatu program linear bilangan bulatnya, maka jika x0 (suatu penyelesaian optimal dalam program linear P1) bernilai bulat, maka menurut sifat di atas x0 adalah suatu penyelesaian optimal untuk program linear bilangan bulat P2.
H. Metode Cabang dan Batas (Branch and Bound Method) Metode cabang dan batas adalah salah satu metode untuk menyelesaikan persoalan program linear bilangan bulat murni dan persoalan program linear bilangan bulat campuran. Metode ini mampu mengadakan perhitungan satu persatu atau mengenumerasi semua nilai variabelnya melalui pencabangan. Dengan mengenumerasi semua variabel tersebut, maka diperoleh suatu penyelesaian optimalnya, yaitu penyelesaian yang meminimumkan atau memaksimumkan fungsi tujuannya. Metode
cabang
dan
batas
merupakan
suatu
pendekatan
untuk
menyelesaikan persoalan yang didasarkan pada pembagian semua penyelesaian layak terhadap sebuah persoalan ke dalam subpersoalan yang lebih kecil. Selanjutnya, subpersoalan ini dapat diselesaikan secara sistematis sampai
54
diperoleh penyelesaian yang optimal. Cara inilah yang kemudian menjadi dasar metode cabang dan batas. Sebelum persoalan diselesaikan dengan menggunakan metode cabang dan batas, terlebih dahulu persoalan dirumuskan sebagai persoalan program linear dan diselesaikan dengan menggunakan metode simpleks. Hal ini dapat dilakukan karena persoalan program linear bilangan bulat merupakan kasus khusus dari program linear. Pertama-tama persoalan diselesaikan dengan menggunakan metode simpleks. Langkah selanjutnya adalah menentukan batasan-batasan untuk menentukan penyelesaian optimal program linear bilangan bulatnya. Dalam program linear bilangan bulat terdapat dua batasan untuk menentukan penyelesaian optimalnya, yaitu batas atas (upper bound) dan batas bawah (lower bound). Penyelesaian program linear yang optimal dengan pembulatan ke atas sebagai batas atas dan pembulatan ke bawah sebagai batas bawah. Penyelesaian program linear bilangan bulat optimal jika batas atas sama dengan batas bawah. Misal xk adalah suatu variabel bilangan bulat. Jika nilai optimal adalah xk* berupa bilangan pecahan, maka
x* k
xk
x* k
1 tidak mungkin memuat
penyelesaian bilangan bulat yang layak (dengan A bulat terbesar
x* k
A ). Jadi
xk
x* k
mendefinisikan bilangan
1 harus disingkirkan. Akibatnya
Suatu nilai bilangan bulat xk yang layak harus memenuhi salah satu kondisi
xk
x* atau xk k
x* k
1.
55
Kedua kondisi ini bila diterapkan pada suatu persoalan program linear bilangan bulat akan didapatkan dua persoalan yang terpisah yang didapatkan dengan memasukkan fungsi kendala
xk
x* k
atau
xk
x* k
1 pada
penyelesaiannya. Pada kasus ini persoalan asli dicabangkan menjadi dua subpersoalan. Kemudian setiap subpersoalan diselesaikan dengan metode simpleks dan menggunakan fungsi tujuan yang sama dari persoalan asli, apabila penyelesaian optimalnya bernilai bilangan bulat dan memenuhi persyaratan bilangan bulat yang ada, maka penyelesaian ini merupakan penyelesaian terbaik dalam subpersoalan tersebut. Jika penyelesaian optimalnya masih bernilai bilangan pecahan dan tidak memenuhi persyaratan bilangan bulat yang ada, maka subpersoalan harus dibagi menjadi dua subpersoalan yaitu dengan memasukkan lagi kondisi bilangan bulat pada salah satu variabel bilangan bulat yang masih mempunyai suatu nilai optimal pecahan. Jika diperoleh penyelesaian bilangan bulat yang lebih baik dari penyelesaian yang sudah ada maka penyelesaian tersebut yang dipakai sebagai penyelesaian optimal. Proses pencabangan berlanjut sampai setiap subpersoalan mendapatkan penyelesaian bilangan bulat atau tidak dapat lagi menghasilkan penyelesaian yang lebih baik. Pada kasus ini diperoleh penyelesaian optimal program linear bilangan bulat. Efisiensi perhitungan dengan konsep pembatasan, jika penyelesaian selanjutnya dari subpersoalan tersebut lebih buruk dari penyelesaian bilangan bulat terbaik yang ada, maka pencabangan pada subpersoalan dihentikan. Dengan
56
kata lain nilai tujuan yang bersesuaian dengan penyelesaian bilangan bulat yang layak dapat digunakan untuk membuang subpersoalan yang tidak perlu. Perlunya menentukan suatu batasan yang tepat pada langkah awal tidak terlalu ditekankan dalam prosedur tersebut di atas. Hal ini tergantung pada urutan subpersoalan yang berbeda yang diturunkan dan diteliti. Persoalan yang dihasilkan tergantung pada variabel yang dipilih untuk menghasilkan pencabangan. Ringkasan langkah-langkah metode cabang dan batas digambarkan dalam diagrap alir sebagai berikut: Rumuskan dan selesaikan persoalan dengan metode simpleks. Tentukan batas atas solusi bulat yang layak
Tentukan batas bawah solusi bulat yang layak
Batas atas sama dengan batas bawah
ya
Optimal (solusi bulat yang layak=batas bawah)
tidak Buat pencabangan dengan memasukkan fungsi kendala
xk
x* k
dan
xk
x* k
1, dengan xk
mendefinisikan bilangan bulat terbesar
xk
Selesaikan penyelesaian optimal dengan metode simpleks untuk masing-masing cabangnya
Hitung batas atas dengan mencari nilai maksimum dari subpersoalan yang tidak mempunyai cabang
Hitung kembali batas bawah sebagai nilai maksimum dari semua solusi bulat yang layak
Gambar 2.3 Diagram alir metode cabang dan batas
57
Contoh 2.8 Misal diberikan persoalan knapsack: Memaksimumkan z ( x1 , x2 , x3 , x4 ) 16 x1 22 x2 12 x3 8 x4 terhadap kendala 5 x1
7 x2
4 x3
3 x4
14
xj
0 atau 1; ( j 1, 2, 3, 4).
Penyelesaian Penyelesaian persoalan knapsack di atas diawali dengan menghitung rasio
cj ai
dan
menentukan peringkat setiap variabel berdasarkan besarnya rasio ini (peringkat 1 menyatakan variabel terbaik). Hasilnya adalah sebagai berikut: Barang ke1 2 3 4
cj
Peringkat
ai 16 5 22 7 12 4 8 3
1 2 3 4
Langkah selanjutnya yaitu menjadikan persoalan knapsack sebagai persoalan program linear relaksasi. Dari peringkat dipilih x1 1 kemudian x2 x4
1 serta
0 sehingga solusi program linear relaksasinya adalah z 16 22 1 (12) 44, 2
dengan x1
x2 1, x3
dan pembatasan.
1 dan x 4 2
0 . Selanjutnya dilakukan proses pencabangan
58
Pada proses pencabangan dan pembatasan dihasilkan sub-subpersoalan. Subpersoalan 1 diperoleh dengan menjadikan persoalan knapsack sebagai persoalan program linear relaksasi. Solusinya adalah
x3
1 dan x4 2
z
44, x1
0 . Jadi nilai optimal z untuk persoalan knapsack
x2
1,
nilai optimal
z program linear relaksasi. Hal ini berarti nilai optimal z untuk persoalan knapsack tidak mungkin lebih besar daripada 44. Dengan kata lain nilai optimal z program linear relaksasi adalah batas atas dari persoalan knapsack. Langkah berikutnya adalah memilah daerah fisibel dari soal program linear relaksasi. Karena nilai x j
0 atau 1; ( j 1, 2, 3, 4) maka x j hanya boleh
bernilai 0 atau 1. Nilai x1 , x2 dan x4 sudah sesuai dengan syarat kendala sehingga pencabangan dikenakan pada x3 , diperoleh subpersoalan 2 dan 3. Selanjutnya setiap subpersoalan diselesaikan (dicari solusinya) berdasarkan kendala-kendala pada setiap subpersoalan. Subpersoalan 2 diselesaikan, solusinya adalah z
x3
0 x4
x1
x3
139 , 3
x1
2 . Berikutnya subpersoalan 3 diselesaikan, diperoleh solusi z 3
1, x2
5 , x4 7
x2
1,
306 , 7
0. Dari solusi yang diperoleh sebenarnya subpersoalan 2
dapat diabaikan, karena nilai z pada subpersoalan 2 lebih kecil nilai z pada subpersoalan 3. Akan tetapi sebagai bukti apakah subpersoalan 2 bukan merupakan solusi yang optimal maka pencabangan akan dilakukan pada
59
subpersoalan 2, tentunya setelah subpersoalan 3 diselesaikan dan cabang-cabang yang dihasilkan juga telah diselesaikan. Pencabangan kembali dikenakan pada subpersoalan 3, sehingga diperoleh subpersoalan 4 dan subpersoalan 5. Selanjutnya setiap subpersoalan diselesaikan. Solusi dari subpersoalan 4 adalah z
36, x1
x3
1, x2
0 x4
1 . Karena seluruh
variabel keputusan telah berharga 0 atau 1, maka solusi dari subpersoalan 4 merupakan
z
calon
218 , x1 5
3 , x2 5
solusi.
x2
Untuk
1 x4
subpersoalan
5
solusinya
adalah
0 . Karena subpersoalan 4 tidak memberikan
solusi fisibel selain 0 atau 1 dengan z
36 , maka pencabangan dari subpersoalan
4 tidak akan memberikan informasi baru mengenai solusi optimal persoalan knapsack. Nilai z
36 dari subpersoalan 4 dijadikan sebagai batas bawah atau lower
bound (LB) pada subpersoalan 5. Selanjutnya subpersoalan 5 dicabangkan dengan
LB 36,
diperoleh subpersoalan 6 dan subpersoalan 7. Masing-masing
subpersoalan x1
0, x3
diselesaikan.
x2
x4
Solusi
dari
subpersoalan
6
yaitu
z
42,
1 . Karena nilai seluruh variabel keputusan telah berharga 0
atau 1, maka solusi dari subpersoalan 6 adalah juga calon solusi. Calon solusi ini memiliki nilai z
42, yang berarti lebih besar dari batas bawah, sehingga
subpersoalan 7 diselesaikan dengan LB 42. Subpersoalan 7 solusinya adalah z
50, x1
x2
x3
1, x4
0 . Karena nilai z pada subpersoalan 7 melebihi
batas atas dari. Jadi subpersoalan 7 tidak fisibel dan hal ini dinyatakan dengan
60
mencantumkan tanda ( ) di dekat kotak subpersoalan 7. Sampai pada langkah ini sudah tidak ada lagi subpersoalan yang dicabangkan. Seperti yang telah diutarakan bahwa subpersoalan 2 dapat diabaikan. Akan tetapi akan dicoba dilakukan pencabangan pada subpersoalan 2 dengan 42. Hasil dari pencabangan ini yaitu subpersoalan 8 dan subpersoalan 9.
LB
Kemudian setiap subpersoalan diselesaikan. Subpersoalan 8 solusinya adalah z
38, x1
x2
1, x3
x4
0. Nilai
z subpersoalan 8 tidak lebih besar dari
LB 42, sehingga pencabangan dari subpersoalan 8 tidak akan memberikan informasi baru mengenai solusi optimal persoalan knapsack dan hal ini dinyatakan dengan mencantumkan tanda ( ) di dekat kotak subpersoalan 8. Berikutnya subpersoalan 9 diselesaikan dengan LB 42. Solusinya adalah
x1
x4
1, x2
218 , x4 5
0.
Nilai
z
z
300 , 7
pada subpersoalan ini juga tidak
memberikan nilai yang lebih besar dari LB
42, sehingga pencabangan dari
subpersoalan 9 tidak akan memberikan informasi baru mengenai solusi optimal persoalan knapsack dan hal ini dinyatakan dengan mencantumkan tanda ( ) di dekat kotak subpersoalan 9. Dari pencabangan untuk subpersoalan 2, terbukti bahwa cabang-cabang yang
dihasilkan
tidak
memberikan
informasi
yang
berguna,
sehingga
pencabangan tidak perlu dikenakan. Dengan kata lain subpersoalan dapat diabaikan, sehingga dalam melakukan perhitungan akan lebih efektif. Karena sudah tidak terdapat subpersoalan yang belum diselesaikan dan hanya subpersoalan 6 yang dapat memberikan solusi optimal terhadap persoalan
61
knapsack maka subpersoalan 6 merupakan solusi optimal untuk persoalan knapsack yaitu z
42, x1
mencantumkan tanda (
0, x2
x3
x4
1 dan hal ini dinyatakan dengan
) di dekat kotak subpersoalan 6.
Ringkasan proses pencabangan dan pembatasan disajikan dalam gambar pohon cabang dan batas berikut. (Gambar 2.4)
62
Subpersoalan 1
x1
x2 x3 z
x3
1
1 2 44
0
x3
Subpersoalan 2
x1
x2
x3
0; x4
z
Subpersoalan 3
1
x1
2 3
x4
130 3
z
0
x4
Subpersoalan 8
x1
x2
1
x3
x4
0
z
38
1
x2
Subpersoalan 9
x1 x2 z
LB=42
x3 x2
LB=42
x4
1
x4
5 7 0 306 7
0
x2
Subpersoalan 4
1
6 ;x 7 3 300
1
x1 0
x3
1
LB=42
x2
0
x4
1
x2
z
36
z
calon solusi
x1
3 5 x3
x1
0
x3
x4
1; x4
218 5 LB=36
0
x1 1
Subpersoalan 6
x2
Subpersoalan 5
x1
7
1
Subpersoalan 7
1
LB=42
z 42 LB=36 calon solusi
tidak fisibel
Gambar 2.4 Pohon cabang dan batas persoalan knapsack 0-1
0
63
BAB III PEMBAHASAN
Dalam bab ini akan dibahas bagaimana menentukan pola dan kombinasi pola yang paling layak dalam pemotongan balok kayu serta implementasi teknik pembangkit kolom dalam optimasi pemotongan balok kayu.
B. Pola Awal dan Kombinasi Pola yang paling layak dalam Pemotongan Balok Kayu Seperti yang telah diuraikan, penggunaan pola pemotongan ini bertujuan untuk meminimumkan sisa pemotongan dengan cara mengkombinasikan polapola pemotongan. Selain itu perlu diperhatikan juga adanya produksi surplus, yaitu hasil produksi melebihi pesanan yang dihasilkan dari kombinasi pola pemotongan. Sebagai gambaran untuk menjelaskan persoalan tersebut, diilustrasikan seperti pada Gambar 3.1 berikut: Pola 1 a meter
a meter
b meter
b meter
Pola 2 a meter
a meter
c meter
s1 meter
Pola 3 a meter
b meter
c meter
Gambar 3.1 Pola Pemotongan
s2 meter
64
Gambar 3.1 tersebut menunjukkan tiga macam pola pemotongan yang mungkin dilakukan pada suatu pesanan. Panjang balok kayu yang akan dipotong adalah sepanjang L meter dan dipotong menurut panjang pesanan a, b dan c meter, dengan a < b < c dan syarat sisa pemotongan s1 , s2
a meter, a meter adalah
panjang minimum pesanan dan s1 adalah sisa pemotongan Pola 2 sedangkan s2 adalah sisa pemotongan Pola 3. Meskipun terdapat pola pemotongan yang lain, sebagai pengantar diilustrasikan pada Gambar 3.1, yaitu untuk Pola 1, 2 dan 3. Contoh 3.1 Suatu perusahaan kayu memperoleh pesanan balok kayu dengan panjang a meter sebanyak A batang, panjang b meter sebanyak B batang dan panjang c meter sebanyak C batang. Untuk memenuhi pesanan dengan panjang a, b dan c meter, ketiga pola dapat dikombinasikan dengan memotong balok kayu panjang L meter sebanyak wi batang , i 1, 2, ..., m ; wi
bilangan bulat positif. Berikut ini adalah contoh
kombinasi yang dapat digunakan: 1. Memotong balok kayu dengan panjang L meter sebanyak w1 batang menggunakan Pola 1 dan w2 batang menggunakan Pola 2. 2. Memotong balok kayu dengan panjang L meter sebanyak w3 batang menggunakan Pola 1 dan w4 batang menggunakan Pola 3. 3.
Memotong balok kayu dengan panjang L meter sebanyak w5 batang menggunakan Pola 3 dan w6 batang menggunakan Pola 2.
65
Dari ketiga kombinasi pola di atas, kombinasi mana yang lebih baik? Pertanyaan tersebut dapat dijawab dengan mempertimbangkan sisa pemotongan. Pada Gambar 3.1, bagian diarsir menunjukkan batang surplus yang tidak cukup panjang untuk memenuhi pesanan. Sisa pemotongan yang dihasilkan dari ketiga kombinasi itu adalah : Kombinasi I
: w2 s1 meter
x meter.
Kombinasi II : w4 s2 meter
y meter.
Kombinasi III : ( w5 s2 meter) ( w6 s1 meter)
x, y , z
z meter.
bilangan real positif . Selanjutnya setiap produksi surplus dengan panjang a, b dan c meter harus
dipertimbangkan dalam perhitungan sebagai sisa pemotongan. Pada Kombinasi I, Pola 1 menghasilkan f1 batang panjang a meter dan f 2 batang panjang b meter, dengan jumlah batang f1
f 2 karena pemotongan
dengan Pola 1 menghasilkan 2 batang panjang a meter dan 2 batang panjang b meter. Sehingga f1
f2
2 w1 dan f1 , f 2
bilangan real positif. Untuk Pola 2
menghasilkan g1 batang panjang a meter dan g 2 batang panjang b meter, dengan jumlah batang g1
2 w2 dan jumlah batang g 2
1 w2 karena pemotongan
balok menggunakan Pola 2 menghasilkan 2 batang panjang a meter dan 1 batang panjang c meter dan g1 , g 2
bilangan bulat positif .
Pada Kombinasi II, Pola 1 menghasilkan h1 batang panjang a meter dan h2 batang panjang b meter, dengan jumlah batang h1
h2 karena pemotongan
dengan Pola 1 menghasilkan 2 batang panjang a meter dan 2 batang panjang b
66
meter. Sehingga h1
h2
2 w3 ; h1 , h2
bilangan real positif. Sementara Pola 3
menghasilkan i1 batang panjang a meter, i2 batang panjang b meter dan i3 batang panjang c meter, dengan jumlah batang i1
i2
i3 karena pemotongan dengan
Pola 3 menghasilkan 1 batang panjang a meter, 1 batang b meter dan 1 batang panjang c meter. Sehingga (i1 , i2 , i3 ) batang c meter) dan i1 , i2 , i3
w4 (1 batang a meter, 1 batang b meter, 1
bilangan bulat positif.
Pada Kombinasi III, Pola 3 menghasilkan j1 batang panjang a meter, j2 batang panjang b meter dan j3 batang panjang c meter, dengan jumlah batang j1
j2
j3 karena pemotongan dengan Pola 3 menghasilkan 1 batang panjang a
meter, 1 batang b meter dan 1 batang panjang c meter. Sehingga ( j1 , j2 , j3 ) (1
batang
j1 , j2 , j3
a
meter,
1
batang
b
meter,
1
batang
c
meter)
w5 dan
bilangan real positif . Sementara Pola 2 menghasilkan k1 batang
panjang a meter dan k 2 batang panjang c meter, dengan jumlah batang k1 dan jumlah batang k 2
2 w6
1 w6 karena pemotongan balok menggunakan Pola 2
menghasilkan 2 batang panjang a meter dan 1 batang panjang c meter dan k1 , k 2
bilangan bulat positif.
Hasil-hasil dari Kombinasi I, Kombinasi II dan Kombinasi III disajikan dalam Tabel 3.1 sebagai berikut:
67
Tabel 3.1 Hasil pesanan Kombinasi I, II dan III Jumlah panjang pesanan yang dihasilkan (batang) Pola
Kombinasi I
Kombinasi II
Jumlah yang dipesan
Kombinasi III
(j)
(batang) a (m)
b
c
a
b
c
a
b
c
(m) (m) (m) (m) (m) (m) (m) (m)
1
f1
f2
-
h1
h2
-
-
2
g1
-
g2
-
-
-
k1
3
-
-
-
i1
i2
i3
j1
-
a
b
c
(m)
(m)
(m)
A
B
C
k2
j3
j2
Selanjutnya bagaimana produksi surplus diperoleh, hal ini diperhatikan pada masing-masing kombinasi. Kombinasi I, produksi surplus panjang a meter diperoleh jika ( f1
g1 )
A.
Kombinasi II, produksi surplus panjang a meter diperoleh jika (h1 i1 ) produksi surplus panjang b meter diperoleh jika (h2
i2 )
B.
Kombinasi III, produksi surplus panjang a meter diperoleh jika (k1 produksi surplus panjang c meter diperoleh jika (k 2
j3 )
A;
j1 )
A;
C
Agar diketahui kombinasi mana yang paling baik digunakan, yang harus dilakukan yaitu membandingkan perhitungan yang didapat pada Kombinasi I, Kombinasi II dan Kombinasi III. Perhitungannya: Kombinasi I
: total sisa pemotongan
x meter + produksi surplus Kombinasi I.
Kombinasi II : total sisa pemotongan
y meter + produksi surplus Kombinasi II.
Kombinasi III : total sisa pemotongan
z meter+produksi surplus Kombinasi III.
68
Dari hasil perhitungan, dapat diketahui kombinasi mana yang paling baik digunakan, dengan melihat hasil sisa pemotongan yang lebih sedikit. Untuk menentukan solusi optimal, pertama perlu untuk menentukan semua pola yang mungkin dan kemudian menentukan semua kombinasi pola yang layak. Meskipun menentukan semua pola yang mungkin tidak begitu sulit, namun menentukan semua kombinasi pola yang layak merupakan suatu pekerjaan yang berat. Apalagi jika telah melibatkan banyak variabel. Disinilah model program linear memainkan peranan dan teknik pendekatan yang sistematis diperlukan. Contoh 3.2 Suatu perusahaan kayu memperoleh pesanan balok kayu dari suatu UD dengan 3 ukuran. Pesanan pertama, panjang 1,5 meter sebanyak 25 batang, yang merupakan panjang minimum. Pesanan kedua, panjang b meter sebanyak 20 batang dan pesanan ketiga panjang c meter sebanyak 15 batang. Perusahaan tersebut harus memenuhi pesanan dengan memotong panjang balok kayu standar, yakni L
7 meter dan menginginkan sisa pemotongan seminimum mungkin. Pesanan
disajikan dalam Tabel 3.2 sebagai berikut: Tabel 3.2 Jumlah Pesanan Pesanan
Panjang yang diinginkan
Jumlah yang dipesan
(i)
(meter)
(batang)
1
1,5
25
2
b
20
3
c
15
Berapa ukuran balok kayu yang dipesan oleh UD untuk pesanan pertama dan kedua, jika sisa pemotongan minimum adalah 0,5 meter?
69
Jika digunakan kombinasi pola pemotongan I, kombinasi pola pemotongan II dan kombinasi pola pemotongan III, manakah kombinasi yang lebih baik? Penyelesaian Untuk mendapatkan nilai dari b dan c pola-pola yang telah dipaparkan dapat dijadikan sebagai acuan. Dari Pola 1, diperoleh nilai a dan b. Nilai a 1,5 meter merupakan panjang awal yang diketahui. Pola 1, membagi balok kayu panjang 7 meter dengan 2a dan 2b, maka:
2a
2 1,5 meter 3 meter
b merupakan panjang yang diinginkan, berdasarkan Pola 1, maka: panjang yang diinginkan
balok kayu panjang 7 meter – 3 meter, sehingga:
2b
7 meter 3 meter
2b b
4 meter 2 meter
Jadi panjang b
2 meter .
Pada Pola 1 tidak diperoleh sisa pemotongan, karena 2a + 2b
0 meter.
Selanjutnya untuk mendapatkan nilai c, akan lebih mudah jika menggunakan Pola 3, karena balok kayu panjang 7 meter dipotong dengan panjang a, b dan c serta sisa, maka: (panjang pesanan 1 + panjang pesanan 2 + panjang pesanan 3)
balok kayu
panjang 7 meter – sisa minimum pemotongan, dengan sisa minimum pemotongannya pada soal adalah 0,5 meter, sehingga:
70
(a b c) (1,5 2 c)
7 meter 0,5 meter 6,5 meter
(3,5 c) c c
6,5 meter 6,5 meter 3,5 meter 3 meter
Jadi panjang c
3 meter , dengan panjang sisa pada Pola 3 adalah 0,5 meter.
Nilai a, b dan c telah diketahui, pada Pola 2, akan diperoleh sisa (s) yang nilainya harus lebih kecil dari panjang minimum pesanan (s < 1,5 meter), yaitu:
( 2a c s )
panjang balok kayu 7 meter
(3 3 s ) 6 s s
7 meter 7 meter 1 meter.
Jadi panjang sisa pada Pola 2
1 meter (memenuhi 1 < 1,5).
Karena panjang pesanan kedua dan ketiga telah diketahui, maka jika digunakan kombinasi pola pemotongan dari Kombinasi I dan Kombinasi II, berikut ini contoh kombinasi yang layak digunakan: 1. Memotong balok kayu dengan panjang 7 meter sebanyak 10 batang menggunakan Pola 1 dan 15 batang menggunakan Pola 2. 2. Memotong balok kayu dengan panjang 7 meter sebanyak 5 batang menggunakan Pola 1 dan 15 batang menggunakan Pola 3. 3. Memotong balok kayu dengan panjang 7 meter sebanyak 20 batang menggunakan Pola 3 dan 3 batang menggunakan Pola 2. Dari ketiga pola di atas, kombinasi mana yang lebih baik? Pertanyaan tersebut dapat dijawab dengan mempertimbangkan sisa pemotongan. Sebagai berikut:
71
Pada Gambar 3.1, bagian diarsir menunjukkan batang surplus yang tidak cukup panjang untuk memenuhi pesanan. Sisa pemotongan yang dihasilkan dari kedua kombinasi itu adalah : Kombinasi I
: 15 1 meter 15 meter.
Kombinasi II : 15 0,5 meter
7,5 meter.
Kombinasi III : (20 0,5 meter) (3 1 meter) 13 meter. Selanjutnya setiap produksi surplus dengan panjang 1,5, 2 dan 3 meter harus dipertimbangkan dalam perhitungan sebagai sisa pemotongan. Pada Kombinasi I, Pola 1 menghasilkan 20 batang panjang 1,5 meter dan 10 batang panjang 2 meter. Untuk Pola 2 menghasilkan 30 batang panjang 1,5 meter dan 15 batang panjang 3 meter. Produksi surplus yang dihasilkan dari kombinasi 1 sebanyak 25 batang dengan panjang 1,5 meter. Karena produksi surplus diperhitungkan sebagai sisa pemotongan, sehingga total panjang produksi surplus adalah: 25 1,5 30 meter. Pada Kombinasi II, Pola 1 menghasilkan 10 batang panjang 1,5 meter dan 10 batang panjang 2 meter. Sementara Pola 3 menghasilkan 15 batang panjang 1,5 meter, 15 batang panjang 2 meter dan 15 batang panjang 3 meter. Jadi, pada Kombinasi II terdapat produksi surplus untuk panjang 2 meter sebanyak 5 batang, sehingga produksi surplus: 5 2 10 meter. Pada Kombinasi III, Pola 3 menghasilkan 20 batang panjang 1,5 meter, 20 batang panjang 2 meter dan 20 batang panjang 3 meter, sementara Pola 2 menghasilkan 6 batang panjang 1,5 meter dan 3 batang panjang 3 meter. Jadi pada Kombinasi II
72
terjadi produksi surplus untuk panjang 1,5 meter sebanyak 1 batang dan panjang 3 meter sebanyak 8 batang, sehingga produksi surplus: 8 3 meter
24 meter .
Jadi, total sisa pemotongan adalah: Kombinasi I
: 15 meter 30 meter
45 meter.
Kombinasi II : 7,5 meter 10 meter 17,5 meter . Kombinasi III : 13 meter 1,5 meter 24 meter
38,5 meter .
Jadi Kombinasi II adalah kombinasi yang paling lebih baik karena menghasilkan sisa pemotongan paling sedikit (minimum) yaitu sebesar 17,5 meter. Contoh 3.2 merupakan contoh kasus persoalan pemotongan kayu menggunakan 3 pola pemotongan dan kombinasi dari ketiga pola. Bagaimana jika suatu perusahaan kayu mendapatkan m pesanan dengan panjang yang bervariasi, juga banyaknya n pola pemotongan yang berukuran besar. Disinilah model program linear memainkan peranan dan teknik pendekatan yang sistematis diperlukan.
C. Implementasi Teknik Pembangkit Kolom dalam Optimasi Pemotongan Balok Kayu Teknik pembangkit kolom digunakan untuk mengefisiensi metode simpleks direvisi. Oleh karena itu langkah-langkah pengerjaannya banyak mengacu kepada metode simpleks direvisi, mulai dari perhitungan B 1 , harga akhir ( z j
c j ), penggunaan test rasio untuk menentukan variabel nonbasis yang
akan masuk menjadi variabel basis, sampai diperoleh solusi optimal. Namun perbedaan mendasar antara kedua metode ini terletak pada perhitungan harga akhir setiap variabel nonbasis yang akan masuk menjadi variabel basis.
73
Misalkan: n
banyaknya pola pemotongan yang mungkin,
xj
jumlah balok kayu dengan panjang L meter yang dipotong menurut pola
j , j 1, 2, ..., n , aij
= jumlah potongan balok kayu panjang K i dengan pola j , j 1, 2, ..., n ;
i 1, 2, ..., m , bi
= banyaknya pesanan untuk panjang K i , i 1, 2, ..., m ,
cj
= koefisien fungsi tujuan j 1, 2, ..., n ,
maka bentuk umum persoalan pemotongan balok kayu dalam upaya meminimumkan sisa pemotongan adalah: Meminimumkan z ( x1 , x2 , ..., xn )
x1
x2 ... xn
terhadap kendala: ai1 xi1
ai 2 xi 2 ... ain xij
bi
(3.1)
i 1, 2, ..., m, x j 0 dan bilangan bulat, j 1, 2, ..., n.
Dalam bentuk umum persoalan program linear, (3.1) dapat ditulis: n
Meminimumkan z ( x j )
c jxj , j 1
terhadap kendala : n
a ij xij
bi ,
j 1
(3.2)
i 1, 2, ..., m,
dengan x j
0 dan bilangan bulat; j 1, 2, ..., n ; c j
Dalam bentuk matriks, persoalan (3.2) dapat ditulis:
1 untuk setiap j.
74
Meminimumkan z (x) cx terhadap kendala: Ax b
x
(3.3)
0 dan bilangan bulat ,
dengan c
vektor baris berdimensi n ,
x
vektor kolom berdimensi n ,
b
vektor kolom berdimensi m ,
A
matriks berordo m n .
Dalam bentuk kanonik, bentuk (3.3) bentuk terakhir ditulis sebagai: Meminimumkan z ( xVB , xNB ) terhadap kendala: BxVB
cVB xVB
NxNB
xVB , xNB
cNB xNB ,
b,
0 dan bilangan bulat ,
dengan cVB
Koefisien-koefisien fungsi tujuan yang bersesuaian dengan xVB ,
xVB
variabel basis,
cNB
Koefisien-koefisien fungsi tujuan yang bersesuaian dengan xNB ,
xNB
variabel nonbasis,
B
matriks yang berkaitan dengan variabel xVB ,
N
matriks yang berkaitan dengan variabel xNB ,
b
vektor kolom berdimensi m.
75
Ada dua faktor yang menyebabkan rumusan persoalan pemotongan balok kayu atau persoalan pemotongan stok tidak praktis (Gilmore and Gomory 1961; Dyckhoff 1982). Pertama banyaknya n pola pemotongan bisa berukuran besar dan banyaknya m pesanan berjumlah besar. Jika persoalan ini diselesaikan menggunakan metode simpleks direvisi maka perhitungan harga akhir untuk tiaptiap variabel nonbasis menjadi variabel basis merupakan pekerjaan yang tidak efisien. Kedua, pembatasan terhadap bilangan bulat, yaitu apakah kendala disyaratkan untuk bilangan bulat murni ataukah ada yang bernilai bilangan bulat campuran. Oleh karena itu disinilah diperlukan teknik pembangkit kolom. Ide dasar dari teknik pembangkit kolom adalah untuk mengefisiensi suatu kolom dengan harga akhir yang efisien (positif dalam persoalan meminimumkan). Dalam persoalan optimasi pemotongan balok kayu, masing-masing kolom mewakili suatu pola pemotongan balok kayu panjang K i , i 1, 2, ..., m meter. Oleh karena itu dapat didefinisikan y1 , y2 , ..., yn , dengan y j , j 1, 2, ..., n adalah jumlah balok kayu K i , i 1, 2, ..., m meter yang dihasilkan dari pemotongan satu batang balok kayu panjang L meter berdasarkan pola yang diberikan. Harga akhir ( z j
c j ) dengan teknik pembangkit kolom diperoleh dengan
cara:
z j c j c VBB 1 y j 1 , dengan y j
y1 y2 yn
0 dan bilangan bulat, j 1,2,..., n .
76
Telah
dijelaskan
bahwa
y j , j 1, 2, ..., n
adalah
jumlah
balok
kayu
K i , i 1, 2, ..., m meter yang dihasilkan dari pemotongan satu batang balok kayu panjang L meter, dengan kata lain balok-balok kayu yang dihasilkan tidak boleh lebih dari L meter, sehingga untuk sebarang y j harus memenuhi persamaan: K1 y1 Ki
K 2 y2 ... K m yn
L
0, i 1, 2, . . . , m ; y j
0 dan bilangan bulat, j 1, 2, . . . , n,
dengan
L
panjang balok kayu (meter)
Ki
panjang balok kayu yang dipesan (meter); K i
L, i 1, 2, ..., m .
Karena teknik pembangkit kolom adalah suatu teknik yang dapat memberikan nilai z j
c j terbaik (positif pada persoalan meminimumkan) maka
berdasarkan Sifat 2.1 (Bab II. A) ekuivalen dengan menyelesaikan subpersoalan: n
Memaksimumkan w( y j )
j
yj 1
j 1
terhadap kendala: n
Kiyj
L,
(3.4)
j 1
yj
0 dan bilangan bulat,
j 1, 2, ..., n, i 1, 2, ..., m, dengan koefisien
j
merupakan elemen ke- j dari c VB B 1 . Dengan kata lain
subpersoalan (3.4) dinamakan persoalan knapsack, yaitu persoalan program linear dengan sebuah kendala. Dari teori program linear (Taha 1996) nilai dual (dual prices).
j
disebut juga
77
Salah satu metode yang dapat digunakan untuk menyelesaikan persoalan knapsack yaitu metode cabang dan batas. Hasil perhitungan menggunakan metode cabang dan batas pada (3.4) akan berkorespondensi dengan y j , j 1, 2, ..., n ke pola j , j 1, 2, ..., n dan variabel xk . Selanjutnya ditentukan variabel nonbasis xk , k 1, 2, ..., n yang akan masuk menjadi variabel basis dalam baris k menggunakan metode simpleks direvisi. Nilai xk dihitung dengan menggunakan
xk
B 1b dalam tabel bersangkutan. Langkah-langkah teknik pembangkit kolom:
1. Perumusan persoalan program linear bentuk meminimumkan. 2. Merubah persoalan program linear meminimumkan ke bentuk program linear kanonik. 3. Menghitung B 1 dan c VBB B
1
I
B0
1
1
dalam tabel bersangkutan yaitu:
pada tabel awal, untuk B
1
berikutnya
dihitung dengan
menggunakan bentuk hasil kali invers. Untuk menghitung c VBB 1 , ditentukan terlebih dahulu koefisien-koefisien variabel basis ( c VB ) yang bersesuaian, 1
1
misal c VBB 0 , c VB diperoleh berdasarkan tabel awal, berikutnya c VBB1 , c VB , diperoleh dari tabel yang bersangkutan dan dari test rasio untuk mencari variabel nonbasis yang masuk menjadi variabel basis. 4. Menghitung harga akhir pola untuk setiap y j yaitu: c VBB 1 y j 1 ((c VBB 1 ( y1
y2 ...
yn )) 1 .
78
5. Mencari harga akhir pola yang efisien, diperoleh dengan menyelesaikan persoalan knapsack: n
Memaksimumkan w( y j )
j
yj 1
j 1
terhadap kendala: n
Ki yj
L,
j 1
yj
0 dan bilangan bulat,
j 1, 2, ..., n, i 1, 2, ..., m. 6. Hasil perhitungan persoalan knapsack menggunakan metode cabang dan batas akan memberikan solusi optimal untuk program linear, hasil ini akan berkorespondensi dengan
y j , j 1, 2, ..., n ke pola
j , j 1, 2, ..., n dan
variabel xk . 7. Dari langkah (6) dapat diperoleh variabel nonbasis yang akan menjadi variabel basis, diperoleh dengan cara menghitung B 1 y j dan B-1b kemudian digunakan test rasio untuk menentukan dalam baris mana
xk masuk sebagai variabel
basis. 8. Teknik pembangkit kolom akan menghasilkan solusi optimal jika penyelesaian persoalan knapsack dengan metode cabang dan batas menghasilkan fungsi tujuan
w 0
yang berarti bahwa tidak ada lagi suatu pola yang
menguntungkan bila dimasukkan ke dalam variabel basis. Untuk mendapatkan nilai-nilai variabel basis dalam solusi optimal diperoleh dengan cara B-1b. Hasil dari B-1b menghasilkan sebuah solusi optimal bilangan bulat bila dilakukan dengan cara membulatkan tiap-tiap nilai x ke atas.
79
Untuk mengetahui bagaimana implementasi teknik pembangkit kolom dalam menyelesaikan persoalan pemotongan balok kayu, diberikan contoh soal berikut. Contoh 3.3 Berdasarkan Contoh 3.2, jika ditulis secara ringkas: Suatu perusahaan kayu memperoleh pesanan dari suatu UD. Adapun banyak dan ukuran balok kayu yang dipesan : 1) 25 batang ukuran 1,5 meter. 2) 20 batang ukuran 2 meter. 3) 15 batang ukuran 3 meter. Perusahaan harus memenuhi permintaan itu dengan memotong balok kayu dengan panjang standar 7 meter dan menginginkan sisa seminimum mungkin. Gunakan teknik pembangkit kolom untuk menyelesaikan persoalan program linear perusahaan kayu tersebut. Penyelesaian 1.
Perumusan persoalan ke bentuk program linear. Langkah awal perumusan ke bentuk program linear adalah membuat pola
pemotongan. Banyak kemungkinan untuk membuat pola pemotongan, namun dari banyak kemungkinan dapat dirangkum dalam pola sederhana, seperti disajikan pada Tabel 3.3 berikut (sisa pemotongan harus lebih kecil dari 1,5 meter).
80
Tabel 3.3 Pola Pemotongan Balok Kayu Pola
Jumlah panjang 1,5 meter
Jumlah panjang 2 meter
Jumlah panjang 3 meter
Sisa
(j)
(batang)
(batang)
(batang)
(meter)
1
4
0
0
1
2
3
1
0
0,5
3
2
2
0
0
4
2
0
1
1
5
1
1
1
0,5
6
0
2
0
1
7
0
3
1
0
8
0
0
2
1
Jika didefinisikan x j jumlah balok kayu panjang 7 meter yang dipotong menurut pola j; j 1, 2, ..., 8. Dalam persoalan program linear dirumuskan sebagai berikut: Sisa pemotongan + total permintaan pelanggan
total panjang balok kayu 7
meter yang dipotong. Total permintaan pelanggan (meter): 25(1,5) + 20(2)+ 15(3)
122,5,
Total panjang balok kayu yang dipotong (meter): 7( x1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 ) Sisa pemotongan (meter): 7 x1 7 x 2 7 x 3 7 x 4 7 x 5 7 x 6 7 x 7 7 x 8 125,5 , maka fungsi tujuan adalah: Meminimumkan z
7 x1 7 x 2 7 x 3 7 x 4 7 x 5 7 x 6 7 x 7 7 x 8 125,5
Tanpa mempengaruhi optimasi, maka fungsi tujuan dapat ditulis sebagai: Meminimumkan z
x1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 .
(3.5)
81
Hal ini berarti bahwa sisa pemotongan bisa diminimumkan dengan cara meminimumkan jumlah balok kayu panjang 7 meter yang dipotong. Selanjutnya terdapat tiga kendala atau pembatas (constraint) sebagai berikut : a. Kendala 1 sedikitnya 25 batang panjang 1,5 meter harus dipotong, b. Kendala 2 sedikitnya 20 batang panjang 2 meter harus dipotong, c. Kendala 3 sedikitnya 15 batang panjang 3 meter harus dipotong. Karena jumlah total panjang 1,5 meter harus dipotong diberikan oleh: 4 x1 3 x2
2 x3
2 x4
x5 .
Maka kendala 1 menjadi 4 x1 3 x2
2 x3 2 x 4
x5
25
(3.6)
Dengan cara yang sama, diperoleh kendala 2 dan kendala 3 : kendala 2 : x2
2 x3
kendala 3 : x4
x5
x5 3 x 6 x7
2 x8
2 x7 15
20
(3.7) (3.8)
Perlu diingat bahwa koefisien x j dalam kendala untuk balok kayu k meter, yaitu jumlah balok kayu k yang hanya dihasilkan jika suatu balok kayu dipotong berdasarkan pola j , oleh karena itu x j harus diperlukan untuk mengasumsikan nilai-nilai bilangan bulat. Dari persamaan (3.5) sampai (3.8) diperoleh persamaan persoalan program linear sebagai berikut:
82
Meminimumkan z ( x1, x 2 , ..., x8 )
x1 x 2 x 3 x 4 x 5 x 6 x 7 x8
terhadap kendala : 4 x1 3 x2 x2
2 x3 2 x4
x5
2 x3
x5 3 x6 x4
xj
25 2 x7
x5
20
x7
2 x8
(3.9)
15
0 ; j 1, 2, ... , 8 dan bilangan bulat.
2. Merubah persoalan program linear meminimumkan ke bentuk program linear kanonik. Dari bentuk persoalan program linear meminimumkan diperoleh bahwa x1 hanya terjadi dalam kendala 1,5 meter (karena pola 1 hanya menghasilkan balok kayu 1,5 meter), x6 hanya terjadi dalam kendala 2 meter (karena pola 6 hanya menghasilkan balok kayu 2 meter) dan x8 hanya terjadi dalam kendala 3 meter (karena pola 8 hanya menghasilkan balok kayu 3 meter). Ini berarti x1 , x6 dan x8 dapat digunakan sebagai variabel basis awal untuk kendala panjang 1,5, 2 dan 3 meter. Selanjutnya (3.9) diubah ke bentuk program linear kanonik menjadi: Meminimumkan z ( x1, x 2 , ..., x 8 , ti )
x1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 0ti
terhadap kedala: 4 x1 3x2 2 x3 2 x4 x2 2 x3
Dari VNB
persamaan
x5
0 ; ( j 1, 2, ... , 8) ; ti bentuk
x2 , x3 , x4 , x5 , x7 .
t1
x5 3x6 2 x7 x4
xj
x5
kanonik
x7
25 t2
2 x8
20 t3
(3.10)
15
0 ; (i 1, 2, ... , 8) dan bilangan bulat. diperoleh
VB
x1 , x6 , x8
dan
83
1
3. Menghitung B 0 dan c VB B 0 4 0 0 B0
0 3 0 , B0
1
0 0 2
1
1 4
0 0
0
1 3
0 0
0 , 1 2
maka 1 4
c VB B 0
0 0 1 1 1 0 13 0 . 0 0 12
1
1 4
1 3
1 2
Telah dijelaskan bahwa pada persoalan pemotongan balok kayu, setiap kolom menunjukkan sebuah pola pemotongan balok kayu panjang L meter. Pada (3.10), sebuah variabel dinyatakan oleh y1 , y2 dan y3 dengan y j adalah jumlah potongan berturut-turut dengan panjang 1,5, 2 dan
3 meter yang dihasilkan dari
pemotongan balok kayu panjang 7 meter sesuai dengan pola yang diberikan. Sebagai contoh, x5 dinyatakan oleh y1 1, y2
1 dan y3 1 .
Untuk basis tertentu, suatu pola dinyatakan oleh y1 , y2 dan y3 akan ditentukan nilai z j
c j nya sebagai: y1 zj
cj
c VBB
1
y2
1
1 4
y1
1 3
y2
1 2
y3
1.
y3
Karena y1 , y2 dan y3 yang dipilih tidak boleh melebihi panjang balok kayu 7 meter serta y1 , y2 dan y3 harus bilangan bulat positif, sehingga untuk sebarang
84
pola y1 , y2 dan y3 harus memenuhi: 1,5 y1
2 y2
y1 , y2 , y3
3 y3
7
0 dan bilangan bulat.
4. Mencari harga akhir pola yang efisien Untuk mencari pola yang paling efisien , dicari dengan menyelesaikan persoalan knapsack sebagai berikut: Memaksimumkan w( y1 , y2 , y3 )
1 4
1 3
y1
y2
1 2
y3
1
terhadap kendala: 1,5 y1
2 y2
y1 , y2 , y3
3 y3
7
(3.11)
0 dan bilangan bulat
Secara teoritis persoalan knapsack sulit diselesaikan. Oleh karena itu perlu suatu metode untuk menyelesaikannya. Salah satu metode untuk mencari penyelesaiannya yaitu dengan menggunakan metode cabang dan batas (Taha 1996; Winston 2004). Dengan metode cabang dan batas diperoleh penyelesaian persoalan (3.11): 1. Menentukan rasio No
j
Ki
Peringkat
j
Ki 1
1 4 3 2
2
1
3
3 2 1 2 3
dan peringkat
1
1
6 1
2
6
1 6
3
85
2. Pohon cabang dan batas Dengan
metode
cabang
dan
batas
dihasilkan
sub-subpersoalan.
subpersoalan 1 diperoleh dari penyelesaian program linear relaksasi. Solusi program linear relaksasi diperoleh dengan memilih sebarang variabel y1 , karena memiliki peringkat yang sama. Dalam hal ini yang dipilih adalah y1 , sehingga y2 dan y3
w
1 , y2 6
ditentukan
x3
0, y1
sama
dengan
nol.
Jadi
solusinya
adalah
14 . Langkah berikutnya adalah memilah daerah fisibel 3
dari soal program linear relaksasi yaitu dengan memilih variabel yang benilai pecahan (noninteger). Solusi y1 benilai noninteger dan setiap titik pada persoalan knapsack akan benilai y1
4 atau y1
5 maka dilakukan pencabangan dari
variabel y1 sehingga diperoleh dua subpersoalan tambahan yaitu subpersoalan 2 dan 3, dengan subpersoalan 2
subpersoalan 1 ditambahkan kendala y1
4
subpersoalan 3
subpersoalan 1 ditambahkan kendala y1
5.
Karena subpersoalan 2 dan 3 dibangun dengan cara menambahkan kendala yang berkaitan dengan y1 , maka dapat dikatakan bahwa subpersoalan 2 dan 3 dibangun dengan melakukan pencabangan pada y1 . Selanjutnya dipilih salah satu subpersoalan yang belum diselesaikan. Misalkan dipilih subpersoalan 2. Dengan mensubstitusi variabel-variabel yang diketahui, diperoleh solusi optimal subpersoalan 2 yaitu w
1 , y1 6
4, y2
0, y3
1 . 3
Karena solusi optimal dari subpersoalan 2 masih memuat variabel noninteger,
86
maka dari subpersoalan 2 dibuat dua subpersoalan baru dan dilakukan pencabangan dari variabel yang noninteger tersebut. Pada subpersoalan 2, nilai y3 noninteger dan setiap titik pada persoalan knapsack akan benilai y3
0 atau y3 1
maka dilakukan pencabangan pada variabel y3 sehingga diperoleh subpersoalan 4 dan 5, dengan subpersoalan 4
subpersoalan 2 ditambahkan kendala y3
subpersoalan 5
subpersoalan 2 ditambahkan kendala y3 1 .
0
Sub-subpersoalan yang belum diselesaikan terdiri atas subpersoalan 3, 4 dan 5. Selanjutnya dipilih salah satu subpersoalan yang akan diselesaikan. Dengan menggunakan aturan LIFO (Last in First Out) yaitu menyelesaikan subpersoalan yang dibuat paling akhir. Dengan kata lain, subpersoalan yang harus diselesaikan selanjutnya adalah subpersoalan 4 atau subpersoalan 5. Misalkan dipilih subpersoalan
4.
Dengan mensubstitusi variabel-variabel yang diketahui,
diperoleh solusi optimal subpersoalan 5 yaitu w
1 , y3 6
0, y2
1, y1
10 . Untuk 3
mengefisiensi perhitungan dalam menetapkan subpersoalan mana yang akan dicabangkan maka subpersoalan 5 juga diselesaikan. Dengan mensubstitusi variabel-variabel yang diketahui, diperoleh solusi subpersoalan 5 yaitu
w
1 , y3 1, y3 6
0, y2
7 . 3
Karena nilai fungsi tujuan subpersoalan 4 dan 5 bernilai sama, maka dipilih salah satu subpersoalan yang ingin dicabangkan sehingga salah satu subpersoalan dapat diabaikan. Misal subpersoalan 4 diabaikan dan hal ini
87
dinyatakan dengan mencantumkan tanda ( ) di dekat kotak subpersoalan 4. Sehingga subpersoalan 4 yang dipilih untuk dicabangkan. Variabel y1 noniteger sehingga setiap titik pada persoalan knapsack akan benilai y1
3 atau y1
4 dan
dilakukan pencabangan pada variabel y1 diperoleh subpersoalan 6 dan 7, dengan subpersoalan 6
subpersoalan 5 ditambahkan kendala y2
2
subpersoalan 7
subpersoalan 5 ditambahkan kendala y2
3.
Menggunakan aturan LIFO, dipilih subpersoalan 7 untuk diselesaikan. Dengan mensubstitusi variabel-variabel yang diketahui, diperoleh solusi subpersoalan 7 yaitu w
1 , y2 6
3, y3
0, y1
2 . Solusi pada subpersoalan 7 3
masih memuat variabel noninteger. Selanjutnya untuk membandingakan subpersoalan mana yang akan dicabangkan maka subpersoalan 6 juga diselesaikan. Dengan mensubstitusi variabel-variabel yang diketahui, diperoleh solusi subpersoalan 6 yaitu w
1 , y2 6
2, y3
0, y1
2.
Karena solusi subpersoalan 6 sudah berharga integer, maka solusi pada subpersoalan 6 merupakan solusi optimal untuk persoalan knapsack. Oleh karena itu pada subpersoalan 7 tidak perlu dilakukan pencabangan dan dinyatakan dengan mencantumkan tanda ( ) di dekat kotak subpersoalan 7. Selanjutnya tinggal subpersoalan 3 yang belum diselesaikan. Dengan mensubstitusi variabelvariabel yang diketahui, diperoleh solusi subpersoalan 3 yaitu w
y2
0, y3
9 , y1 12
5,
1 . Salah satu solusi subpersoalan 3 berharga negatif, sehingga 6
88
solusi pada subpersoalan 3 bukan merupakan solusi yang fisibel. Oleh karena itu di dekat kotak subpersoalan 3 diberi tanda ( ). Penyelesaian subpersoalan telah menghasilkan solusi integer dan tidak ada lagi subpersoalan yang menghasilkan solusi yang lebih baik maka subpersoalan 6 menghasilkan solusi optimal untuk persoalan knapsack (3.11) dan hal ini dinyatakan dengan mencantumkan tanda (
) di dekat kotak subpersoalan 6. Jadi
hasil cabang dan batas memberikan solusi optimal untuk persoalan knapsack (3.11) adalah w
1 6
, y1
2, y2
2 dan y3
0.
Dari uraian di atas dapat di digambarkan dalam gambar pohon cabang dan batas berikut. (Gambar 3.2)
89
Subpersoalan 1
y2
y3
y1 w
y1
0
14 3 1 6
4
y1
Subpersoalan 2
y1
4
y2
0
y3 w
y3
Subpersoalan 3
y1
5
1 3 1
tidak fisibel
6
0
y3 1
Subpersoalan 4
Subpersoalan 5
y3
0
y3
1
y2
1
y1
0
y1
10 3
y2
w
5
1
w
6
y2
3
Subpersoalan 7
7 3 1 6
y2
2
Subpersoalan 6
y2
3
y2
2
y3
0
y3
0
2 3 1 6
y1
2
y1 w
w
1 6
Gambar 3.2 Pohon cabang dan batas persoalan awal
90
5. Nilai solusi optimal untuk persoalan knapsack (3.11) berkorespondensi dengan Pola 3. Jadi nilai z3
1
c3 adalah
6
, dan dengan memasukkan x3 ke dalam
basis akan mengurangi sisa pemotongan balok kayu. 6. Menentukan variabel nonbasis yang akan menjadi variabel basis . Pada langkah 6 ini, langkah-langkah yang digunakan yaitu menggunakan metode simpleks direvisi. Untuk memasukkan x3 ke dalam basis maka dibentuk ruas kanan dari tabel bersangkutan dan kolom x3 dari tabel bersangkutan. Kolom x3 dari tabel bersangkutan:
B0
1
2
1 4
0 0
2
2
0
1 3
0
2
1 2 2 3
0 0
1 2
0
0
0
.
Ruas kanan tabel bersangkutan:
1
B0 b
1 4
0 0
25
0
1 3
0
20
0 0
1 2
15
25
Test rasio:
4 1 2
25 2
25 4 20 3 15 2
20 ,
15 3
2 3
10,
2
0
tidak terdefinisi .
Dari test rasio, rasio terkecil pada baris ke-2, sehingga x3 masuk basis pada baris ke-2. Variabel basis yang baru VB(1)
x1 , x3 , x8 .
91
7. Kembali ke langkah 3. Untuk menghitung B1
B1
E0B 0
1
0
0 0
0 1 4
c VBB1
1
maka digunakan bentuk hasil kali invers, yaitu:
3 4 3 2
1 1
1
1 1 1 0 0
1 4
0 0
1 4
0
0
1 3
0
1
0 0
1 2
1 4 1 2
0
0
1 2
1 4
0
1 4
0
0
1 4 1 2
0
0
1 2
1 2
0
.
Kemudian digunakan teknik pembangkit kolom untuk menentukan pola 1
yang akan masuk basis. Untuk nilai dual ( c VBB1 ), suatu pola yang dinyatakan oleh y1 , y2 dan y3 ditentukan nilai z j c j menjadi: y1 1
z j c j c VBB1 y j
cj
1 4
1 4
1 2
y2 y3
1
1 4
y1
1 4
y2
1 2
y3 1 .
Selanjutnya untuk tabel bersangkutan, teknik pembangkit kolom menghasilkan persoalan knapsack: Memaksimumkan w( y1 , y2 , y3 )
1 4
y1
1 4
y2
1 2
y3
1
terhadap kendala: 1,5 y1 2 y2 3 y3 7 , y1 , y2 , y3 0 dan bilangan bulat Dengan metode cabang dan batas diperoleh penyelesaian persoalan (3.12):
(3.12)
92
1. Menentukan rasio No
j
Ki
dan peringkat
Peringkat
j
Ki 1
1 4 3 2
2
1
3
4 2 1 2 3
1 6
1 8 1 6
2
3 1
2. Pohon cabang dan batas Dengan
metode
cabang
dan
batas
dihasilkan
sub-subpersoalan.
subpersoalan 1 diperoleh dari penyelesaian program linear relaksasi. Solusi program linear relaksasi diperoleh dengan memilih variabel berdasarkan peringkat. Dalam hal ini yang dipilih adalah y3 , sehingga y1 dan y2 ditentukan sama dengan nol. Solusi yang diperoleh adalah w
1 , y1 6
x2
7 . 3
0, y3
Langkah berikutnya adalah memilah daerah fisibel dari soal program linear relaksasi yaitu dengan memilih variabel yang benilai pecahan (noninteger). Solusi y3 benilai noninteger dan setiap titik pada persoalan knapsack akan benilai y3
2 atau y3
3 sehingga dilakukan pencabangan pada variabel y3 sehingga
diperoleh dua subpersoalan tambahan yaitu subpersoalan 2 dan 3, dengan subpersoalan 2
subpersoalan 1 ditambahkan kendala y3
2
subpersoalan 3
subpersoalan 1 ditambahkan kendala y3
3.
93
Karena subpersoalan 2 dan 3 dibangun dengan cara menambahkan kendala yang berkaitan dengan y3 , maka dapat dikatakan bahwa subpersoalan 2 dan 3 dibangun dengan melakukan pencabangan pada y3 . Selanjutnya dipilih salah satu subpersoalan yang belum diselesaikan. Misalkan dipilih subpersoalan 2. Dengan mensubstitusi variabel-variabel yang diketahui, diperoleh solusi optimal subpersoalan 2 yaitu w
1 , y1 8
1 . 2
0, y2
Karena solusi optimal dari subpersoalan 2 masih memuat variabel noninteger, maka dari subpersoalan 2 dibuat dua subpersoalan baru dan dilakukan pencabangan dari variabel yang noninteger tersebut. Pada subpersoalan 2, nilai y2 noninteger dan setiap titik pada persoalan knapsack akan benilai y2
0 atau y2 1
maka dilakukan pencabangan pada variabel y2 sehingga diperoleh subpersoalan 4 dan 5, dengan subpersoalan 4
subpersoalan 2 ditambahkan kendala y2
subpersoalan 5
subpersoalan 2 ditambahkan kendala y2 1 .
0
Sub-subpersoalan yang belum diselesaikan terdiri atas subpersoalan 3, 4 dan 5. Selanjutnya dipilih salah satu subpersoalan yang akan diselesaikan. Seperti pada Gambar 3.2, digunakan aturan LIFO untuk menyelesaikannya. Misalkan dipilih subpersoalan 5. Dengan mensubstitusi variabel-variabel yang diketahui, diperoleh solusi optimal subpersoalan 5 yaitu w Variabel
1 , y2 12
1, y3
0, y1
10 . 3
y1 bernilai noninteger. Untuk mengefisiensi perhittungan dalam
menentukan subpersoalan mana yang akan dicabangkan kembali, maka
94
subpersoalan 4 juga diselesaikan. Dengan mensubstitusi variabel-variabel yang diketahui,
w
1 , y2 6
diperoleh
0, y3 1, y1
solusi
optimal
subpersoalan
4
yaitu
8 . 3
Karena nilai fungsi tujuan pada subpersoalan 4 lebih besar dari subpersoalan 5 maka subpersoalan 5 dapat diabaikan. Subpersoalan 5 diabaikan karena pencabangan pada subpersoalan ini tidak akan memberikan solusi optimal yang lebih baik. Untuk hal ini ini dapat dinyatakan dengan mencantumkan tanda ( ) di dekat kotak subpersoalan 5. Sehingga subpersoalan 4 yang dipilih untuk dicabangkan. Variabel y1 noniteger sehingga setiap titik pada persoalan knapsack akan benilai y1
2 atau y1
3 maka dilakukan pencabangan pada variabel y1
sehingga diperoleh subpersoalan 6 dan 7, dengan subpersoalan 6
subpersoalan 4 ditambahkan kendala y1
2
subpersoalan 7
subpersoalan 4 ditambahkan kendala y1
3.
Menggunakan aturan LIFO, dipilih subpersoalan 7 untuk diselesaikan. Dengan mensubstitusi variabel-variabel yang diketahui, diperoleh solusi subpersoalan 7 yaitu w
1 , y1 16
3, y3
0, y2
5 . Nilai fungsi tujuan tidak lebih 4
besar dari subpersoalan semula yaitu subpersoalan 4, maka subpersoalan 7 dapat diabaikan meskipun masih memuat variabel noninterger. Untuk hal ini ini dapat dinyatakan dengan mencantumkan tanda ( ) di dekat kotak subpersoalan 7. Selanjutnya subpersoalan 6 diselesaikan. Dengan mensubstitusi variabel-varibel yang diketahui, diperoleh solusi optimal subpersoalan 6 yaitu
w 0,
95
y2
2, y3
0, y1
2 . Karena solusinya telah berharga interger, maka solusi ini
fisibel untuk persoalan knapsack. Suatu solusi yang diperoleh dengan cara menyelesaikan subpersoalan dengan seluruh variabelnya berharga integer disebut calon solusi. Karena calon solusi ini dapat menjadi optimal maka disimpan untuk kemudian dibandingkan dengan calon solusi lain (jika ada). Subpersoalan yang belum diselesaikan adalah subpersoalan 3. Dengan mensubstitusi variabel-variabel yang diketahui, solusi yang diperoleh yaitu
w
1 , y1 4
0, y2
1, y3
3 . Karena solusi subpersoalan 3 memuat variabel
negatif, jelas bahwa solusi pada subpersoalan 3 bukan merupakan solusi yang fisibel. Untuk hal ini dinyatakan dengan mencantumkan tanda ( ) di dekat kotak subpersoalan 3. Karena sudah tidak ada lagi subpersoalan yang akan diselesaikan maka subpersoalan yang menghasilkan solusi integer merupakan solusi optimal untuk persoalan knapsack. Solusi optimal pada subpersoalan 6 bernilai integer, nilai fungsi tujuan juga telah bernilai nol, sehingga subpersoalan 6 menghasilkan solusi optimal persoalan knapsack (3.11) dan hal ini dinyatakan dengan mencantumkan tanda (
) di dekat kotak subpersoalan 6. Hasil dari cabang dan batas solusi optimal untuk persoalan knapsack
(3.12) adalah w 0, y1
2, y2
2, y3
0 . Nilai w optimal untuk persoalan
knapsack (3.12) diperoleh w 0 , ini berarti tidak ada lagi pola yang dapat menghasilkan harga akhir yang lebih baik. Oleh karena itu, penyelesaian basis bersangkutan harus suatu penyelesaian optimal.
96
Hasil dari proses cabang dan batas dapat digambarkan dalam Gambar 3.3 berikut. Subpersoalan 1
y1
y2
0 7 3
y3 w y3
1 6
2
y3
Subpersoalan 2
y3
Subpersoalan 3
2 1
y2
y3
2 0
y1
1
w
3
tidak fisibel
8
y2 1
y2
Subpersoalan 5
0
Subpersoalan 4
y2
1
y2
0
y3
0
y3
1
y1
10 3
y1
8 3
w
3
1
w
12 y1
1 6
2
Subpersoalan 6
y1
3
Subpersoalan 7
y1
2
y1
3
y3
0
y3
0
y2
2
w
0
y2 w
5 4 1 16
Gambar 3.3 Pohon cabang dan batas persoalan kedua
97
Untuk mendapatkan nilai-nilai variabel basis VB(1) pada solusi optimal, dicari nilai ruas kanan sebagai berikut: 1 4 1
B1 b
1 4 1 2
0
25
0
20
0
1 2
15
0 0
5 4
10 . 15 2
Jadi solusi optimal untuk persoalan pemotongan balok kayu diberikan sebagai berikut:
x1
5 , x3 10 dan x8 4
15 . 2
Untuk mendapatkan suatu solusi fisibel bilangan bulat maka dilakukan dengan cara pembulatan ke atas nilai-nilai x1 dan x8 , sehingga akan menghasilkan solusi bilangan bulat x1
2, x3 10 dan x8
8.
Jadi pesanan dari UD yaitu sebanyak 25 batang dengan panjang 1,5 meter, 20 batang dengan panjang 2 meter dan 15 batang dengan panjang 3 meter dapat dipenuhi oleh perusahaan kayu dengan memotong balok kayu panjang 7 meter sebanyak 2 batang dipotong menggunakan Pola 1, 10 batang dipotong menggunakan Pola 3 dan 8 batang dipotong menggunakan Pola 8. Berdasarkan Tabel 3.3, dengan teknik pembangkit kolom, jumlah potongan yang dihasilkan oleh perusahaan untuk memenuhi pesanan yaitu: a. Pola 1 menghasilkan 8 potong balok kayu dengan panjang 1,5 meter, b. Pola 3 menghasilkan 20 potong balok kayu dengan panjang 1,5 meter dan 20 potong balok kayu dengan panjang 2 meter, c. Pola 8 menghasilkan 16 potong balok kayu dengan panjang 3 meter
98
Telah dijelaskan bahwa optimasi persoalan pemotongan balok kayu bertujuan memenuhi pesanan balok kayu dengan ukuran dan jumlah tertentu dengan membuat sisa pemotongan semiminimum mungkin. Dari Contoh 3.3, persoalan dirumuskan kedalam program linear sebagai berikut: Total permintaan pelanggan (meter): 25(1,5) + 20(2)+ 15(3)
122,5.
Total panjang balok kayu yang dipotong (meter): 7( x1
x3
x8 )
7 x1 7 x3
7 x8
7(2) 7(10) 7(8) 140 meter. Sisa pemotongan: 7 x1 7 x 3 7 x 8 125,5 140 meter 125,5 meter 14,5 meter . Jadi perusahaan dalam memenuhi pesanan sisa minimum pemotongan balok kayu pajang 7 meter yang dihasilkan sebanyak 14,5 meter, dengan produksi surplus panjang 1,5 meter sebanyak 3 batang dan panjang 3 meter sebanyak 1 batang.
D. Implementasi Sofware Aplikasi dalam Mencari
Solusi Optimal
Pemotongan Balok Kayu Perkembangan teknologi yang sedemikian pesat, memungkinkan setiap persoalan yang mencakup skala besar dapat diselesaikan dengan cepat dengan bantuan komputer. Demikian juga persoalan program linear, mengacu kepada metode simpleks direvisi, maka berkembanglah piranti (software) komputer yang dapat menyelesaikan persoalan program linear yang melibatkan kendala fungsional serta variabel dalam jumlah besar. Misalnya GAMS/MINOS, LINDO, LINGO, TORA dan lan-lain.
99
Salah satu implementasi software yang akan digunakan dalam penulisan ini adalah implementasi LINDO. LINDO (Linear Interactive and Discrete Optimizer) adalah software komputer yang digunakan untuk menyelesaikan persoalan program linear, interger dan program kuadratik. Pada penulisan ini, akan dibahas bagaimana menggunakan teknik pembangkit kolom dalam menyelesaikan persoalan pemotongan balok kayu dengan bantuan LINDO. Untuk menggunakan teknik pembangkit kolom dengan bantuan LINDO, ide dasarnya dijelaskan dengan langkah-langkah sebagai berikut (Scharge 1981): 1. Bentuk dan selesaikan program linear awal yang memiliki semua baris dari model yang terdefinisikan secara utuh, tetapi dengan sejumlah kecil kolom yang dinyatakan secara eksplisit. 2. Dengan nilai dual solusi yang bersangkutan, dibentuk kolom (pola) yang menguntungkan, yaitu jika j
1, 2, ..., n, yij
cj
adalah koefisien biaya kolom ke-j
adalah koefisien kolom ke-j pada baris ke-i untuk
i 1, 2, ..., m , dan d i adalah harga dual baris ke-i. Selanjutnya dibentuk kolom
j yang baru sedemikian sehingga
c j d 1y1 j d 2y 2 j ... d my mj 0 . Jika tidak ada kolom j yang baru maka berhenti. 3. Selesaikan program linear dengan kolom baru yang telah ditambahkan. 4. Kembali ke langkah (2) Dari Contoh 3.2. Pada Tabel 1, balok kayu panjang 7 meter dipotong paling banyak menjadi 3 jenis panjang yang berbeda, dengan perincian sebagai
100
berikut, 25 batang panjang 1,5 meter, 20 batang panjang 2 meter dan 15 batang panjang 3 meter. Proses selanjutnya diawali dengan mendefinisikan sebarang 3 pola pemotongan yang murni. Sebuah pola murni hanya menghasilkan satu jenis panjang saja. Misalkan y j
jumlah potongan balok kayu dengan panjang 1,5, 2
dan 3 meter yang dihasilkan dari pemotongan balok kayu panjang 7 meter yang dipotong menurut Pola j , P j
y1 , y2 , ..., yn
merupakan suatu pola dengan
elemen y j di dalamnya, j 1, 2, ..., n . Selanjutnya yang diminimumkan adalah total balok kayu panjang 7 meter yang akan dipotong. Dengan memperhatikan Tabel 3.3, maka P1 untuk panjang 2 meter dan P3
4 untuk panjang 1,5 meter, P2
3
2 untuk panjang 3 meter.
Dengan menggunakan LINDO, formulasi program linearnya adalah: MIN P1+P2+P3 SUBJECT TO 2) 4P1>=25 3) 3P2>=20 4) 2P3>=15
(3.13)
END Tampilan solusinya adalah : OBJECTIVE FUNCTION VALUE 1)
20.41667
VARIABLE P1 P2 P3
VALUE 6.250000 6.666667 7.500000
REDUCED COST 0.000000 0.000000 0.000000
101
ROW
SLACK OR SURPLUS
2) 3) 4)
0.000000 0.000000 0.000000
DUAL PRICES -0.250000 -0.333333 -0.500000
Pola baru yang akan ditambahkan dicari dengan menyelesaikan persoalan knapsack, dengan memperhatikan nilai dual pada output, diperoleh Meminimumkan w( (P1 , P2 , P3 )) terhadap kendala: 1,5 P1
2P2
P1 , P2 , P3
0,25P1 0.333333P2
3P3
0,5P3 1
7,
(3.14)
0 dan bilangan bulat
Berdasarkan (Sifat 2.1) maka (3.14) dapat dituliskan sebagai Memaksimumkan w(P1 , P2 , P3 ) terhadap kendala: 1,5 P1
2P2
P1 , P2 , P3
0,25P1 0.333333P2 3P3
7
0,5P3 1 (3.15)
0 dan bilangan bulat
Dengan metode cabang dan batas diperoleh solusi optimal untuk persoalan knapsack (3.15) adalah P1
2, P2
2, P3
0 . Akan tetapi pada (3.15) nilai fungsi
tujuannya (w) belum nol, sehingga nilai P1
2, P2
2, P3
0 dimisalkan suatu
pola baru yaitu pola dengan memotong balok kayu panjang 7 meter sebanyak 2 batang untuk panjang 1,5 meter dan sebanyak 2 batang untuk panjang 2 meter. Misal pola ini dinamakan P4 . Pada LINDO, P4 menjadi kolom baru. Jika kolom baru ( P4 ) ditambahkan ke dalam formulasi program linear (3.13) formulasinya menjadi:
102
MIN P1+P2+P3+P4 SUBJECT TO 2) 4P1+2P4>=25 3) 3P2+2P4>=20 4) 2P3>=15
(3.16)
END Tampilan solusinya adalah : OBJECTIVE FUNCTION VALUE 1)
18.75000
VARIABLE
VALUE
P1 P2 P3 P4
REDUCED COST
1.250000 0.000000 7.500000 10.000000
0.000000 0.250000 0.000000 0.000000
ROW
SLACK OR SURPLUS
2) 3) 4)
0.000000 0.000000 0.000000
DUAL PRICES -0.250000 -0.250000 -0.500000
Dari output (3.16), nilai dual ditulis menjadi subpersoalan knapsack kembali, yaitu P1
2, P2
2, P3
0
Memaksimumkan w(P1 , P2 , P3 )
0,25P1 0.25P2
0,50P3 1
terhadap kendala: 1,5 P1 2P2 3P3 7 , P1 , P2 , P3 0 dan bilangan bulat .
(3.17)
Dengan metode cabang dan batas, solusi optimal untuk persoalan knapsack (3.17) adalah P1
2, P2
2, P3
0 . Nilai fungsi tujuannya adalah nol (w
0) , hal ini
berarti tidak ada lagi pola yang dapat menghasilkan harga akhir yang lebih baik.
103
Solusi optimal diperoleh dengan melakukan pembulatan yang layak pada output nilai (value). Sehingga solusi optimalnya adalah: 1. Memotong balok kayu panjang 7 meter sebanyak 2 batang masing-masing menjadi 4 batang dengan panjang 1,5 meter. 2. Memotong 10 batang balok kayu panjang 7 meter masing-masing menjadi 2 batang dengan panjang 1,5 meter dan 2 batang dengan panjang 2 meter. 3. Memotong 8 batang balok kayu panjang 7 meter masing-masing menjadi 2 batang dengan panjang 3 meter. Dari perhitungan secara manual (B) dan dengan bantuan LINDO (C), implementasi teknik pembangkit kolom dalam menyelesaikan persoalan pemotongan balok kayu ternyata memberikan hasil yang sama. Dari segi keefektifan pengerjaannya, tentu saja dengan bantuan LINDO menjadi lebih cepat, meskipun dalam penyelesaian subpersolan knapsack diselesaikan dengan metode cabang dan batas secara manual, karena persoalan knapsack tidak dapat diselesaikan dengan LINDO. Contoh 3.4 Pada Contoh 3.4 ini, misal panjang balok kayu yang akan dipotong ukurannya kurang dari panjang standar 7 meter, misal berukuran L 5 meter. Misal suatu perusahaan kayu mendapatkan pesanan dari suatu UD. Adapun banyak dan ukuran balok kayu yang dipesan : 1) 35 batang ukuran 1,5 meter. 2) 22 batang ukuran 2 meter. 3) 18 batang ukuran 3 meter.
104
Perusahaan harus memenuhi permintaan itu dengan memotong balok kayu panjang 5 meter dan menginginkan sisa seminimum mungkin. Gunakan teknik pembangkit kolom untuk menyelesaikan persoalan program linear perusahaan kayu tersebut. Penyelesaian Langkah awal perumusan ke bentuk program linear adalah membuat pola pemotongan. Banyak kemungkinan untuk membuat pola pemotongan, namun dari banyak kemungkinan dapat dirangkum dalam pola sederhana, seperti disajikan pada Tabel 3.4 berikut (sisa pemotongan harus lebih kecil dari 1,5 meter). Tabel 3.4 Pola Pemotongan Balok Kayu Pola
Jumlah panjang 1,5
Jumlah panjang 2
Jumlah panjang 3 meter
Sisa
(j)
meter
meter
(batang)
(meter)
(batang)
(batang)
1
3
0
0
0,5
2
2
1
0
0
3
1
0
1
0,5
4
0
1
1
0
5
0
2
0
1
Analog pada Contoh 3.3, diperoleh bentuk umum persamaan persoalan program linear sebagai berikut: Meminimumkan z ( x1 , x 2 , ..., x 6 )
x1 x 2 x 3 x 4 x 5
terhadap kendala : 3 x1
2 x2
x3
x2
x4 x3
xj
35 x4
2 x5
22 18
0 ; j 1, 2, ... , 5 dan bilangan bulat.
(3.18)
105
Dari bentuk umum persoalan program linear meminimumkan diperoleh bahwa x1 hanya terjadi dalam kendala 1,5 meter (karena pola 1 hanya menghasilkan balok kayu 1,5 meter), x5 hanya terjadi dalam kendala 2 meter (karena pola 5 hanya menghasilkan balok kayu 2 meter). Ini berarti x1 , dan x5 dapat digunakan sebagai variabel basis awal untuk kendala panjang 1,5 dan 2 meter. Pada kendala 3 meter tidak mempunyai variabel basis. Untuk memperoleh solusi basis awal serta menghindari adanya penambahan variabel semu pada kendala 3 meter maka didefinisikan pola 6 yaitu pola pemotongan yang hanya menghasilkan panjang balok kayu 3 meter, serta didefinisikan x6 untuk jumlah balok kayu yang dipotong sesuai pola 6, sehingga pada (3.18) menjadi: Meminimumkan z ( x1, x 2 , ..., x 6 )
x1 x 2 x 3 x 4 x 5 x 6
terhadap kendala : 3 x1
2 x2
x3
35
x2
x4 x3
xj
2 x5
x4
22 x6
(3.19)
18
0 ; j 1, 2, ... , 6 dan bilangan bulat.
Dengan menambahkan variabel surplus ke dalam kendala pada (3.19) diperoleh bentuk program linear kanonik, yaitu: Meminimumkan z
x1 x 2 x 3 x 4 x 5 x 6 0ti
terhadap kendala : 3x1 2 x2 x3 x2
t1 x4 2 x5
x3 x4 xj
0 ; ( j 1, 2, ... , 6); xi
35 t2
x6
22 t3
18
0; (i 1, 2, ... , 6) dan bilanganbulat.
3.20)
106
Dari VNB
persamaan
bentuk
kanonik
diperoleh
VB
x1 , x5 , x6
dan
x2 , x3 , x4 . Langkah selanjutnya adalah menyelesaikan persoalan program linear
(3.20). Iterasi-iterasi penyelesaian (3.20) menggunakan metode simpleks direvisi dan teknik pembangkit kolom dan akan menghasilkan suatu subpersoalan yang dinamakan persoalan knapsack. Dari Tabel 3.4, maka menggunakan teknik pembangkit kolom dengan bantuan LINDO prosesnya adalah: Proses diawali dengan mendefinisikan sebarang 3 pola pemotongan yang murni.. Misalkan y j
jumlah potongan balok kayu dengan panjang 1,5, 2 dan 3 meter
yang dihasilkan dari pemotongan balok kayu panjang 5 meter yang dipotong menurut Pola j , P j
y1 , y2 , ..., yn merupakan suatu pola dengan elemen y j di
dalamnya, j 1, 2, ..., n . Selanjutnya yang diminimumkan adalah total balok kayu panjang 5 meter yang akan dipotong. Dari Tabel 3.4, maka P1
3 untuk panjang 1,5 meter, P2
2 untuk panjang 2
meter dan P3 1 untuk panjang 3 meter. Dengan menggunakan LINDO, formulasi program linearnya adalah: MIN P1+P2+P3 SUBJECT TO 2)3P1>=35 3) 2P2>=22 4) 1P3>=18 END
(3.21)
107
Tampilan solusinya adalah
1)
OBJECTIVE FUNCTION VALUE 40.66667
VARIABLE P1 P2 P3
VALUE 11.666667 11.000000 18.000000
REDUCED COST 0.000000 0.000000 0.000000
ROW SLACK OR SURPLUS 2) 0.000000 3) 0.000000 4) 0.000000
DUAL PRICES -0.333333 -0.500000 -1.000000
Pola baru yang akan ditambahkan dicari dengan menyelesaikan persoalan knapsack, dengan memperhatikan nilai dual pada output, diperoleh Meminimumkan w( (P1 , P2 , P3 )) terhadap kendala: 1,5 P1
2P2
P1 , P2 , P3
0,333333P1 0.5P2
3P3
P3 1
5,
(3.22)
0 dan bilangan bulat.
Berdasarkan (Sifat 2.1) maka (3.22) dapat dituliskan sebagai Memaksimumkan w(P1 , P2 , P3 ) terhadap kendala: 1,5 P1
2P2
P1 , P2 , P3
0.333333P1 0,5P2 3P3
5
P3 1 (3.23)
0 dan bilangan bulat.
Dengan metode cabang dan batas diperoleh solusi optimal untuk persoalan knapsack (3.23) adalah P1 (w) belum nol yaitu w
0, P2
1, P3 1 . Akan tetapi nilai fungsi tujuannya
1 , sehingga nilai P1 2
0, P2
1, P3 1 dimisalkan suatu
pola baru yaitu pola dengan memotong balok kayu panjang 5 meter sebanyak 1 batang untuk panjang 2 meter dan sebanyak 1 batang untuk panjang 3 meter, pola baru ini pada Tabel 3.4 bersesuaian dengan Pola 4. Sehingga nilai
108
z4
c4
1 dan dengan memasukkan x4 ke dalam basis akan mengurangi sisa 2
pemotongan. Untuk mengetahui dalam baris mana x4 masuk menjadi basis maka dibentuk ruas kanan dari tabel bersangkutan dan kolom
x4 dari tabel
bersangkutan. Jika diketahui: 3 0 0 B0
1
0 2 0 , B0 0 0 1
1 3
0 0
0
1 2
0 .
0 0 1
Kolom x4 dari tabel bersangkutan: 1 3
0 B0
1
1 1
0 0
0
0
1 2
1 1
1 2
0 0 0 0 1
.
1
Ruas kanan tabel bersangkutan: 1 3
1
B0 b
0 0 0 12 0
35 22
0 0 1
18
35 3
11 , 18 35
Selanjutnya digunakan test rasio, yaitu:
3
0
tidak terdefinisi,
11 1 2
22,
18 18 . 1
Dari test rasio, rasio terkecil yaitu pada baris ke-3, sehingga x4 masuk basis pada baris ke-3. Sehingga diperoleh variabel basis yang baru VB(1)
x1 , x5 , x4 .
Untuk menentukan pola yang akan masuk basis digunakan teknik pembangkit kolom. Dengan menggunakan LINDO, misal pola baru dinamakan
109
P4 . Pada LINDO P4 menjadi kolom baru. Jika kolom baru ( P4 ) ditambahkan ke
dalam formulasi program linear (3.21) formulasinya menjadi: MIN P1+P2+P3+P4 SUBJECT TO 2) 3P1>=35 3) 2P2+1P4>=22 4) 1P3+1P4>=18
(3.24)
END Tampilan solusinya adalah OBJECTIVE FUNCTION VALUE 1) 31.66667 VARIABLE P1 P2 P3 P4 ROW 2) 3) 4)
VALUE 11.666667 2.000000 0.000000 18.000000
REDUCED COST 0.000000 0.000000 0.500000 0.000000
SLACK OR SURPLUS 0.000000 0.000000 0.000000
DUAL PRICES -0.333333 -0.500000 -0.500000
Dari output (3.24), nilai dual ditulis menjadi subpersoalan knapsack kembali, yaitu: Memaksimumkan w(P1 , P2 , P3 )
0,333333P1 0.5P2
0,5P3 1
terhadap kendala: 1,5 P1 2P2 3P3 5 , P1 , P2 , P3 0 dan bilangan bulat .
(3.25)
Dengan metode cabang dan batas, solusi optimal untuk persoalan knapsack (3.25) adalah P1
0, P2
1, P3 1 . Nilai fungsi tujuannya adalah nol (w
0) , hal ini
110
berarti tidak ada lagi pola baru yang dapat menghasilkan harga akhir yang lebih baik. Untuk mendapatkan solusi optimal nilai-nilai variabel basis, pada output (3.24) diperlihatkan di value. Value yang bernilai pecahan di bulatkan ke atas untuk menghindari kekurangan dalam memenuhi pesanan. Jadi nilai variabel-variabel basis adalah x1 12, x5
2, x4
18 . Sehingga
pesanan UD yaitu sebanyak 35 batang dengan panjang 1,5 meter, 22 batang dengan panjang 2 meter dan 18 batang dengan panjang 3 meter dipenuhi oleh perusahaan dengan memotong balok kayu panjang 5 meter sebanyak 12 batang dipotong menggunakan Pola 1, 18 batang dipotong menggunakan Pola 4 dan 2 batang dipotong menggunakan Pola 5. Karena persoalan pemotongan balok kayu bertujuan untuk mencari sisa pemotongan seminimum mungkin maka dengan teknik pembangkit kolom diperoleh: Total permintaan pelanggan (meter): 35(1,5) + 22(2)+ 18(3)
150,5 meter.
Total panjang balok kayu yang dipotong (meter): 5( x1
x5
x4 )
5 x1 5 x5
5 x4
5(12) 5(18) 5(2) 160 meter. Sisa pemotongan: 5 x1 5 x 5 5 x 4 150,5 160 meter 150,5 meter
9,5 meter .
Jadi perusahaan dalam memenuhi pesanan, sisa minimum pemotongan balok kayu pajang 5 meter yang dihasilkan sebanyak 9,5 meter, dengan produksi surplus panjang 1,5 meter sebanyak 1 batang.
111
Contoh 3.5 Pada Contoh 3.4 ini, misal panjang balok kayu yang akan dipotong ukurannya melebihi panjang standar, misal berukuran L 8 meter. Misalkan suatu perusahaan kayu mendapatkan pesanan dari suatu UD. Adapun banyak dan ukuran balok kayu yang dipesan : 1) 55 batang ukuran 1,5 meter. 2) 40 batang ukuran 2 meter. 3) 32 batang ukuran 2,5 meter. 4) 17 batang ukuran 3,5 meter Perusahaan harus memenuhi permintaan itu dengan memotong balok kayu panjang 8 meter dan menginginkan sisa seminimum mungkin. Gunakan teknik pembangkit kolom untuk menyelesaikan persoalan program linear perusahaan kayu tersebut. Penyelesaian Langkah awal perumusan ke bentuk program linear adalah membuat pola pemotongan. Banyak kemungkinan untuk membuat pola pemotongan, namun dari banyak kemungkinan dapat dirangkum dalam pola sederhana, seperti disajikan pada Tabel 3.5 berikut (sisa pemotongan harus lebih kecil dari 1,5 meter).
112
Tabel 3.5. Pola Pemotongan Balok Kayu Pola
Jumlah panjang
Jumlah panjang
Jumlah panjang
Jumlah panjang
Sisa
(j)
1,5 meter
2 meter
2,5 meter
3,5 meter
(meter)
(batang)
(batang)
(batang)
(batang)
5 4 3 3 2 2 2 1 1 1 0 0 0 0 0 0
0 1 0 0 1 2 0 3 2 1 4 2 1 1 0 0
0 0 1 0 1 0 2 0 1 0 0 0 2 1 3 0
0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
0,5 0 1 0 0,5 1 1 0,5 0 1 0 0,5 1 0 0,5 1
Analog pada Contoh 3.4, persoalan langsung diselesaikan dengan LINDO. Dari Tabel 3.4, maka menggunakan teknik pembangkit kolom dengan bantuan LINDO, prosesnya adalah: Proses diawali dengan mendefinisikan sebarang 4 pola pemotongan yang murni. Dengan memperhatikan Tabel 3.5, maka P1 untuk panjang 2 meter, P3
5 untuk panjang 1,5 meter, P2
3 untuk panjang 3 meter dan P4
4
2 untuk panjang
3,5 meter. Dengan menggunakan LINDO, formulasi program linearnya adalah:
113
MIN P1+P2+P3+P4 SUBJECT TO 2) 5P1>=55 3) 4P2>=40 4) 3P3>=32 5) 2P4>=17
(3.26)
END Tampilan solusinya adalah OBJECTIVE FUNCTION VALUE 1) 40.16667 VARIABLE P1 P2 P3 P4 ROW 2) 3) 4) 5)
VALUE 11.000000 10.000000 10.666667 8.500000
REDUCED COST 0.000000 0.000000 0.000000 0.000000
SLACK OR SURPLUS 0.000000 0.000000 0.000000 0.000000
DUAL PRICES -0.200000 -0.250000 -0.333333 -0.500000
Pola baru yang akan ditambahkan dicari dengan menyelesaikan persoalan knapsack, dengan memperhatikan nilai dual pada output, diperoleh: Memaksimumkan w(P1 , P2 , P3 , P4 ) terhadap kendala: 1,5 P1
2P2
P1 , P2 , P3 , P4
0,2P1 0,25P2 0,333333P3 0,5P4 1
3P3
3,5P4
8
(3.27)
0 dan bilangan bulat
Dengan metode cabang dan batas diperoleh solusi optimal untuk persoalan knapsack (3.27) yaitu P1 nol (w
0, P2
4, P3
0, P4
0 . Nilai fungsi tujuannya adalah
0) , karena nilai fungsi tujuan persoalan knapsack (3.27) sudah nol hal ini
berarti tidak ada lagi pola baru yang dapat menghasilkan harga akhir yang lebih
114
baik. Untuk mendapatkan solusi optimal nilai-nilai variabel basis, pada output (3.26) diperlihatkan di value. Value yang bernilai pecahan di bulatkan ke atas untuk menghindari kekurangan dalam memenuhi pesanan. Jadi nilai variabel-variabel basis adalah x1 11, x11 10, x15 11 dan x16
9 . Sehingga pesanan UD yaitu sebanyak 55 batang dengan panjang 1,5
meter, 40 batang dengan panjang 2 meter, 32 batang dengan panjang 2,5 meter dan 17 batang dengan panjang 3,5 meter dipenuhi oleh perusahaan dengan memotong balok kayu panjang 8 meter sebanyak 11 batang dipotong menggunakan Pola 1, 10 batang dipotong menggunakan Pola 11, 11 batang dipotong menggunakan Pola 15 dan 9 batang dipotong menggunakan Pola 16. Karena persoalan pemotongan balok kayu bertujuan untuk mencari sisa pemotongan seminimum mungkin maka dengan teknik pembangkit kolom diperoleh: Total permintaan pelanggan (meter): 55(1,5) + 40(2)+32(3)+17(3,5)
318 meter.
Total panjang balok kayu yang dipotong (meter): 8( x1
x11
x15
x16 )
8 x1 8 x11 8 x15 8 x16 8(11) 8(10) 8(11) 8(9) 328 meter. Sisa pemotongan:
8 x1 8 x11 8 x15 8 x16 318 meter
328 meter 318 meter 10 meter. Jadi perusahaan dalam memenuhi pesanan, sisa minimum pemotongan balok kayu panjang 8 meter yang dihasilkan sebanyak 10 meter, dengan produksi surplus panjang 2,5 meter sebanyak 1 batang dan panjang 3,5 meter sebanyak 1 batang.
115
Contoh 3.6 Contoh berikut ini adalah contoh implementasi LINDO dalam menyelesaikan persoalan program linear secara umum. Misal diberikan persoalan program linear yang melibatkan variabel dan kendala yang cukup banyak. Persoalan program linear dalam contoh ini merupakan formulasi yang meminimumkan biaya pengolahan atau meminimumkan besarnya penurunan beban pencemaran atau dapat juga dituliskan sebagai memaksimumkan beban pencemaran yang dibuang ke sungai. Adapun variabel-variabel di dalam formulasi menyatakan sumber pencemaran yang dihasilkan oleh industri-industri (pabrik) yaitu: x1
Industri Adiprima Suraprinta; x2
Suparma; x4 RPH; x7
Industri Kali Tengah; x3
Industri
Industri Gawerejo; x6
Industri
Industri Tahu Gunungsari; x9
Industri
Industri Sidomakmur; x5
Industri Tahu Purnomo; x8
Tahu Halim. Formulasi program linearnya adalah
116
Memaksimumkan y
x1
x2
x3
x4
x5
x6
x7
x8
x9
terhadap kendala: 5,822 0,00043 x1
6
5,485 0,0004 x1 0,00042 x2
6
5,445 0,0004 x1 0,00041x2
0,00042 x3
6
5,426 0,0004 x1 0,00041x2
0,00042 x3 0,00042 x4
6
5,416 0,0004 x1 0,00041x2
0,00042 x3 0,00042 x4
0,00042 x5
0,00041x3 0,00041x4
0,00042 x5
5,378 0,00039 x1 0,00041x2 0,00042 x6
6
5,357 0,00039 x1 0,00041x2 0,00042 x6
0,00042 x7 0,00042 x7 0,00041x7
0,083 x1
100
0,029 x2
100
0,156 x3
100
10 x4
150
16,61x5
50
65,746 x6
100
16,953x7
100
0,429 x8
150
5,556 x8
150
x1
2436,5
x2
7638
x3
774,6
x4
5,7
x5
5,6
x6
19,8
x7
25
x8
1627
x9
190,1
0,00041x3 0,00041x4
0,00041x5
0,00042 x8
6
0,00041x3 0,00041x4
0,00042 x8
5,225 0,00038 x1 0,0004 x2 0,00041x6
0,00041x5 6
5,334 0,00039 x1 0,00041x2 0,00042 x6
0,00041x3 0,00041x4
0,00042 x7
5,344 0,00039 x1 0,00041x2 0,00042 x6
6
0,00042 x9
0,0004 x3 0,0004 x4
0,00041x8
0,00041x5
0,00041x9
6 0,0004 x5 6
117
Persoalan program linear di atas akan diselesaikan menggunakan LINDO. Tampilan input data pada LINDO:
Tampilan output datanya adalah:
118
119
Untuk solusi dan pembahasan lain dianalisa dari output yang ditampilkan pada LINDO.
120
BAB IV PENUTUP
E. Kesimpulan a. Penentuan pola awal dan kombinasi pola yang paling layak pada optimasi pemotongan balok kayu dengan pola pemotongan satu dimensi, diperoleh dengan cara: 1) Memotong balok kayu panjang L meter berdasarkan panjang pesanan
K i, i 1, 2, ..., m dengan pola j, j 1, 2, ..., n . Pemotongan ini akan menghasilkan
potongan
balok
kayu
sebanyak
aij , i 1, 2, ..., m ; j 1, 2, ..., n. 2) Mengkombinasikan
aij , i 1, 2, ..., m ; j 1, 2, ..., n
sesuai
dengan
panjang pesanan K i, i 1, 2, ..., m , dengan syarat sisa pemotongan kurang dari K i, i 1, 2, ..., m , untuk K i dengan panjang minimum. 3) Menyelesaikan perumusan program linear pemotongan balok kayu sehingga diperoleh kombinasi pola yang paling layak dengan menggunakan teknik pembangkit kolom. b. Implementasi teknik pembangkit kolom dalam menyelesaikan persoalan pemotongan balok kayu, diterapkan dengan menggunakan langkahlangkah sebagai berikut: 1) Perumusan persoalan program linear bentuk meminimumkan. 2) Merubah persoalan program linear meminimumkan ke bentuk program linear kanonik.
121
3) Menghitung B 1 dan c VBB
1
dalam tabel bersangkutan.
4) Menghitung harga akhir pola untuk setiap y j . 5) Mencari
harga
akhir
pola
yang
efisien,
diperoleh
dengan
menyelesaikan persoalan knapsack: n
Memaksimumkan w( y j )
j
yj 1
j 1
terhadap kendala: n
Kiyj
L,
j 1
yj
0 dan bilangan bulat,
j 1, 2, ..., n, i 1, 2, ..., m. 6) Hasil perhitungan persoalan knapsack menggunakan metode cabang dan batas akan memberikan solusi optimal untuk program linear, hasil ini
akan
berkorespondensi
dengan
y j , j 1, 2, ..., n
ke
pola
j , j 1, 2, ..., n dan variabel xk . 7) Dari langkah (6) dapat diperoleh variabel nonbasis yang akan menjadi variabel basis, diperoleh dengan cara menghitung B 1 y j dan B-1b kemudian digunakan test rasio untuk menentukan dalam baris mana xk masuk sebagai variabel basis. 8) Teknik pembangkit kolom akan menghasilkan solusi optimal jika penyelesaian persoalan knapsack dengan metode cabang dan batas menghasilkan fungsi tujuan w 0 yang berarti bahwa tidak ada lagi suatu pola yang menguntungkan bila dimasukkan ke dalam variabel basis. Untuk mendapatkan nilai-nilai variabel basis dalam solusi
122
optimal diperoleh dengan cara B-1b. Hasil dari B-1b menghasilkan sebuah solusi optimal bilangan bulat bila dilakukan dengan cara membulatkan tiap-tiap nilai x ke atas. c. Implementasi software aplikasi dalam mencari solusi optimal pemotongan balok kayu dengan lebih cepat. Adapun Software yang digunakan yaitu LINDO (Linear Interactive and Discrete Optimizer). Untuk menyelesaikan persoalan pemotongan balok kayu dengan menggunakan LINDO langkah-langkah yang dilakukan 1) Bentuk dan selesaikan program linear awal yang memiliki semua baris dari model yang terdefinisikan secara utuh, tetapi dengan sejumlah kecil kolom yang dinyatakan secara eksplisit. 2) Dengan nilai dual solusi yang bersangkutan, dibentuk kolom (pola) yang menguntungkan, yaitu jika c j adalah koefisien biaya kolom ke-j j
1, 2, ..., n, yij adalah koefisien kolom ke-j pada baris ke-i untuk
i 1, 2, ..., m , dan d i adalah harga dual baris ke-i. Selanjutnya dibentuk
kolom j yang baru sedemikian sehingga
c j d 1y1 j d 2y 2 j ... d my mj 0
(i)
Jika tidak ada kolom (i) maka berhenti 3) Selesaikan program linear dengan kolom baru (i) yang telah ditambahkan. 4) Kembali ke langkah (2)
123
F. Saran Teknik pembangkit kolom dapat diimplementasikan pada berbagai persoalan dalam program linear. Pada persoalan pemotongan balok kayu, pola pemotongan dapat dilakukan dengan pola pemotongan satu dimensi, dua dimensi dan juga tiga dimensi. Oleh karena keterbatasan penulis, maka hanya dibahas implementasi teknik pembangkit kolom pada persoalan pemotongan balok kayu dengan pola pemotongan satu dimensi. Kajian yang lain dari implementasi teknik pembangkit kolom yaitu pada persoalan pemotongan balok kayu dengan pola pemotongan dua dimensi maupun tiga dimensi. Untuk persoalan lain
teknik pembangkit kolom juga dapat
diimplementasikan pada persoalan metode dekomposisi Dantziq-Wolfe. Topiktopik ini dapat menjadi topik yang menarik jika pembaca berminat untuk mendalami terapan dari program linear. Dalam persoalan pemotongan balok kayu, setelah persoalan dibentuk ke dalam persoalan program linear kanonik, maka pada proses selanjutnya muncul subpersoalan yang dinamakan persoalan knapsack. Salah satu metode yang cukup praktis untuk menyelesaikan persoalan knapsack adalah metode cabang dan batas. Akan tetapi jika pada persoalan pemotongan balok kayu, jumlah pesanan semakin banyak (dalam model matematis
jumlah baris semakin banyak) maka semakin
banyak pula variabel dalam persoalan knapsack. Akibatnya semakin berat dalam menyelesaikannya. Oleh karena itu perlu dicari alternatif metode lain yang lebih mudah dan sistematis daripada metode cabang dan batas.
124
DAFTAR PUSTAKA
Anton, Howard. 1987. Aljabar Linear Elementer. Jakarta: Erlangga. Budhi, W. S. 1995. Aljabar Linear. Jakarta: Gramedia Pustaka Utama. Dyckhoff, H. 1982. ”A New Linear Programming Approach to the Cutting-Stock Problem”. Operations Research, p. 1092-1104. Douglass, Stinson. R. 1995. Cryptography, Theory and Practice. California: Chapman and Hall/CRC. Gilmore, P. C. & Gomori, P. E. 1961. ”A linear Programming to the CuttingStock Problem”. Operations Research, p. 849-869. Gullen, C. P. 1993. Aljabar Linear dengan Penerapannya. Jakarta: Gramedia. Hiller, Frederick. S & Lieberman, Gerald. 1980. Introduction to Operations Research. California: Holden Day Inc. Schrage, L. 1981. LINDO. Text and software. San Francisco: Scientific Press. Siagian, P. 1987. Penelitian Operasional. Teori dan Praktik. Jakarta: Universitas Indonesia. Simarmata, Dj. A. 1981. Operations Research. Sebuah Pengantar. Jakarta: Gramedia. Susanta, B. 1994. Program Linear. Jakarta: Departemen Pendidikan dan Kebudayaan Dirjen Dikti. Sutawijaya, Akbar & Sudirman. 2004. Program Linear. Malang: FMIPA Universitas Negeri Malang. Taha, H. A. 1996. Riset Operasi. Suatu Pengantar. Jilid 1. Jakarta: Binarupa Aksara. Tarliah, Tjutju & Dimyati, Ahmad. 1992. Operations Research. Model-Model Pengambilan Keputusan. Bandung: Sinar Baru Algesindo. Winston, W. L. 2004. Operations Research. Aplications and Algorithm. Fourth Edition. California: Brooks/Cole Thomson Learning.
