1

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

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 1B

(matriks yang diperoleh dari

koefisien variabel-variabel slack untuk baris ke-i, mi ...,,2,1

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 ( jj cz ) 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 njx j ...,,2,1, .

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 ()(xf memaksimumkan Sxxf )),( atau biasa

ditulis dengan min )(xf (maks Sxxf )),( .

Bukti:

Dimisalkan terdapat suatu program linear bilangan bulat dengan fungsi

tujuan f dan himpunan kendala S. Ambil fungsi g, dengan Sxxfxg ),()( .

a. Jika SySx

sehingga )()()()()()( ygxgyfxfyxf ,

maka tidak ada nilai minimum fungsi f dan tidak ada nilai maksimum fungsi g.

Pada keadaan ini didefinisikan )(min xf dan maksimum ))((min xg .

b. Jika )()()()( maka )()(dan xgygxfyfyfxfSxSy

10

jadi )(min xf = )(yf

= ))(( yf

= )(( yg )

= ( maks )])([ xg

= ( maks )])([ xf

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 nnj xcxcxcxz ...)( 2211 ,

terhadap kendala:

.,...,2,1,0

,),,(...

,),,(...

,),,(...

2211

22222121

11212111

njx

bxaxaxa

bxaxaxa

bxaxaxa

j

mnmnmm

nn

nn

(Akbar Sutawijaya: 1)

Koefisien-koefisien dalam jj cxz ),( dinamakan koefisien ongkos, jx dinamakan

peubah keputusan dan ija dinamakan koefisien teknis. Jika perumusan program

linear telah diaplikasikan dalam bentuk soal maka z

disebut fungsi sasaran,

kendala-kendala disebut kendala utama dan 0jx 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 is untuk kendala ke-i dan ditambahkan

kendala misi ...,,2,1,0 .

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) it pada

kendala ke-i dan ditambahkan kendala miti ...,,2,1,0 .

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 miqi ...,,2,1,0 .

12

Contoh 2.1

Memaksimumkan 321321 868),,( xxxxxxz

terhadap kendala:

122 321 xxx (2.1)

462 321 xxx (2.2)

82 321 xxx (2.3)

0,, 321 xxx

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 0s , kendala menjadi

0,122 321 ssxxx (2.4)

sehingga pada kendala (2.14) variabel basis adalah s , dengan kata lain

321 ,, xxx menjadi variabel nonbasis yang nilainya adalah nol. Jadi kendala

memberikan nilai 12s .

2. Kendala (2.2) ditambahkan variabel surplus pada ruas kanan yaitu 0t ,

kendala menjadi

0,462 321 ttxxx (2.5)

selanjutnya variabel t

dipindah ke ruas kiri, menjadi

0,462 321 ttxxx . (2.6)

Jika pada kendala (2.4) s

dianggap variabel basisnya 0 , sedangkan

321 ,, xxx menjadi variabel nonbasis yang nilainya adalah nol, maka pada

kendala (2.6) nilainya menjadi 4atau 4 tt .

13

Perlu diingat bahwa syarat awal persoalan program linear yaitu

mibi ...,,2,1,0 . Karena 4t 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 1q dengan 01q , sehingga pada (2.6) menjadi

0,,462 11321 qtqtxxx .

Jika txxx dan ,, 321 adalah variabel nonbasis yang nilainya nol, maka 41q .

3. Kendala (2.3) sudah berbentuk persamaan tetapi belum memuat variabel basis,

maka ditambahkan variabel semu misal 02q . Sehingga kendala menjadi

0,82 22321 qqxxx .

Nilai 82q .

Karena setiap kendala sudah berbentuk persamaan, maka rumusan program linear

dalam bentuk kanonik adalah

Memaksimumkan 2132121321 00868),,,,,,( qMMqtsxxxqqtsxxxz

terhadap kendala:

. 0,,,,,,

82

462

122

21321

2321

1321

321

qqtsxxx

qxxx

qtxxx

sxxx

(2.7)

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 byaxa 1211 , maka

persamaan ini dinamakan persamaan linear dalam variabel yx dan . Secara

umum pesamaan linear dalam n variabel nxxx ...,,, 21 , dapat dinyatakan dalam

bentuk bxaxaxa nn...2211 , dengan baaa n dan ...,,, 21 adalah konstanta

real; real, yx . Contoh 2.3 berikut ini merupakan contoh persamaan linear.

Contoh 2.2

(i) 732 yx (ii) 632 4321 xxxx .

Solusi persamaan linear bxaxaxa nn...2211 adalah urutan dari n

bilangan nsss ...,,, 21 sehingga persamaan tersebut dipenuhi bila bilangan-bilangan

nsss ...,,, 21 disubstitusikan terhadap nn sxsxsx ...,,, 2211 . 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

tytx3

2

3

7, .

Sebuah himpunan berhingga dari persamaan-persamaan linear dalam

vaiabel nxxx ...,,, 21 disebut sistem persamaan linear (SPL) atau sistem linear.

Sebuah urutan bilangan-bilangan nsss ...,,, 21 disebut solusi dari SPL, jika untuk

setiap nsss ...,,, 21 memenuhi nxxx ...,,, 21 .

Misal diberikan SPL,

.493

,134

321

321

xxx

xxx

SPL di atas mempunyai banyak solusi karena terdiri atas dua persamaan dengan

tiga variabel. Salah satu solusi solusinya adalah 1,2,1 321 xxx karena

nilai-nilai ini memenuhi kedua persamaan tersebut.

Tidak semua SPL mempunyai solusi, misal diberikan SPL,

622

4

yx

yx

jika persamaan kedua dari SPL dikalikan dengan 2

1 maka SPL menjadi

.3

,4

yx

yx

Jelas bahwa SPL tidak mempunyai solusi, karena untuk ( yx, ) yang memenuhi

persamaan pertama, nilai 6842)(222 yxyx , 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:

)0,(

)0,(

22222

11111

bacybxa

bacybxa

Grafik dari persamaan-persamaan di atas merupakan garis; misal kedua garis ini

dinamakan 21 dan ll . Titik ),( yx terletak pada garis 1l atau 2l jika dan hanya jika

yx dan memenuhi persamaan garis 21 atau ll , maka solusi sistem persamaan

akan bersesuaian dengan titik perpotongan dari garis 21 atau ll .

Terdapat tiga kemungkinan solusi system pesamaan yang diperoleh seperti

diperlihatkan pada Gambar 2.1 berikut:

y y y

x x x

1l 2l 1l 1l dan 2l

2l

(a) 1l sejajar 2l (b) 1l dan 2l berpotongan di satu titik (c) 1l dan 2l berhimpit

Gambar 2.1 Tiga kemungkinan solusi SPL

Pada Gambar 2.1 (a) garis 1l sejajar dengan garis 2l , maka sistem persamaan

tidak mempunyai solusi. Gambar 2.1 (b) garis 1l berpotongan dengan garis 2l ,

maka sistem persamaan tepa t mempunyai satu solusi. Gambar 2.1 (c) garis 1l

berhimpit dengan garis 2l , 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:

mnnnmm

nn

nn

bxaxaxa

bxaxaxa

bxaxaxa

...

...

...

...

2211

22222121

11212111

(2.8)

Kuantitas-kuantitas ija (untuk njmi ...,,2,1;...,,2,1 ) disebut koefisien. Nilai

koefisien-koefisien ija dan ruas kanan ib pada setiap persamaan diketahui.

Kuantitas-kuantitas ix 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 nm

jika matriks tersebut

memiliki m baris dan n kolom. Matriks biasanya dinyatakan dengan huruf besar

,, BA . Entri-entri dalam matriks dinyatakan dengan huruf kecil yang berkaitan

dan diberi dua indeks. Jadi matriks nm

yang umum dapat dituliskan sebagai

nmijb

mnmm

n

n

abb

abb

bbb

atau

21

22221

11211

B .

18

Misalkan n bilangan asli. Kumpulan terurut yang terdiri dari n bilangan

ditulis sebagai )...,,,( 21 nxxx . Himpunan dari semua kumpulan terurut

)...,,,( 21 nxxx disebut ruang nR

(Wono Setya Budhi, 1995: 164). Elemen dari

nR

disebut titik atau vektor. Vektor biasanya ditulis dengan huruf kecil dan notasi

tebal atau diberi garis di atasnya. Komponen ke-i dari )...,,,( 21 nxxxx disebut

koordinat ke-i dari vektor atau titik x.

Sistem persamaan (2.8) jika ditulis dalam bentuk matriks: bAx ,

dengan A adalah matriks :nm

mnmm

n

n

aaa

aaa

aaa

21

22221

11211

A ,

x dan b adalah vektor dengan n-komponen:

nn b

b

b

x

x

x

2

1

2

1

dan bx .

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:

mmnmm

n

n

baaa

baaa

baaa

21

222221

111211

bA .

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, ijR (baris ke-i ditukar dengan baris ke-j) dari suatu

SPL.

2) Mengalikan sebuah baris dengan konstanta tidak nol k, ikR (baris ke-i

dikali dengan konstanta tidak nol k).

3) Menambah suatu baris dengan kelipatan baris yang lain, ji kRR

(baris

ke-i ditambah k kali baris ke-j).

1. Jenis-jenis matriks

1) Matriks kuadrat atau matriks persegi adalah sebuah matriks yang berorder

nm

atau matriks yang berorder nn .

2) Matriks identitas adalah sebuah matriks kuadrat yang semua elemen

diagonal bernilai satu dan semua elemen di luar diagonal bernilai nol;

yaitu 1ija , untuk ji

dan 0ija , untuk ji .

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 TA

disebut transpose dari A jika elemen ija dalam A adalah sama

dengan elemen jia dari TA

untuk semua i dan j.

Misal,

20

63

52

41

A maka 654

321TA .

Secara umum, TA

diperoleh dengan menukar baris dan kolom dari A.

Akibatnya, jika A memiliki order nm , TA

memiliki order mn .

6) Matriks 0B

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 ijaA dan ijbB , dikatakan matriks yang sama

jika dan hanya jika keduanya memiliki order yang sama dan setiap elemen

ija adalah sama dengan ijb yang bersesuaian untuk semua i dan j.

21

2. Matriks elementer

Sebuah matriks nn

dinamakan matriks elementer jika matriks tersebut

dapat diperoleh dari matriks satuan (identitas) nn

yakni nI dengan melakukan

sebuah operasi baris elementer tunggal (Anton. H, 1987: 40).

Contoh 2.3

Diberikan matriks 3I :

100

010

001

3I .

Misalkan dilakukan OBE dengan menambahkan lima kali baris ketiga dari 3I

pada baris pertama, maka diperoleh matriks elementer E:

100

010

501

E .

Misal diberikan matriks A:

0441

6312

3201

A .

Pada matriks A dilakukan OBE yang sama dengan 3I (Contoh 2.3), diperoleh

0441

6312

322206'A .

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 mI dan

jika A adalah matriks nm , 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 0...,,0,0 21 nxxx 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 langkah-

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

langkah 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

31153

3552

132

321

321

321

xxx

xxx

xxx

(2.9)

Akan dicari solusi SPL (2.9) menggunakan eliminasi Gauss.

Penyelesaian

SPL (2.9) ditulis dalam bentuk matriks diperbesar menjadi:

21153

3552

1321

(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 21a dan 31a dengan cara menambahkan baris ke-2

dengan )2(

kali baris pertama dan baris ke-3 dengan )3(

kali baris

pertama, menghasilkan

1210

5110

1321

(2.11)

3) Membuat nol elemen 32a pada (2.11) dengan cara menambahkan baris ke-

3 dengan baris ke-2, menghasilkan

6100

5110

1321

(2.12)

(2.12) merupakan matriks eselon dan dengan substitusi mundur diperoleh solusi

SPL (2.9) yaitu 6dan 11,31 321 xxx .

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 23a pada (2.12) dengan cara menambahkan baris ke-

2 dengan baris ke-3, menghasilkan

6100

11010

1321

(2.13)

2) Membuat nol elemen 13a pada (2.13) dengan cara menambahkan baris ke-

1 dengan )3(

kali baris ke-3, menghasilkan

6100

11010

19021

(2.14)

3) Membuat nol elemen 12a pada (2.14) dengan cara menambahkan baris ke-

1 dengan )2(

kali baris ke-2, menghasilkan

6100

11010

31001

Pada langkah ke-3 diperoleh matriks eselon tereduksi, sehingga solusi dari

SPL (2.9) dapat dibaca pada kolom terakhir, yaitu T)6,11,31(x .

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 ijaA dan ijbB dapat ditambahkan atau

dikurangkan jika keduanya memiliki order yang sama, misalnya nm .

Jumlah BAD

diperoleh dengan menambahkan elemen-elemen yang

bersesuaian. Jadi nmijbija

nmijd .

2) Perkalian matriks

Dua matriks ijaA dan ijbB dapat dikalikan dalam urutan AB

jika dan hanya jika jumlah kolom A adalah sama dengan jumlah baris B,

yaitu, jika A memiliki order rm , maka B harus memiliki order nr ,

dengan m dan n order sebarang.

Misal ABD . Maka D memiliki urutan nm , dan elemen ijd diketahui:

kj

r

kikij bad

1

, untuk semua i dan j.

27

Contoh 2.5

maka ,086

975dan

42

31BA

)04()92()84()72()64()52(

)03()91()83()71()63()51(

086

975

42

31D

184634

93123.

Jika diperhatikan, secara umum BAAB

sekalipun BA didefinisikan.

6. Invers matriks

Invers suatu matriks persegi A dilambangkan dengan 1A

adalah matriks

yang memenuhi IAAAA 11 .

Invers ini ada jika A tidak singular.

Jika diketahui matriks nnA

nnnn

n

n

aaa

aaa

aaa

21

22221

11211

A , maka

)adj( )det(

11 AA

A

TCA)adj( dan C adalah matriks kofaktor A, dengan

nnnn

n

n

CCC

CCC

CCC

21

22221

11211

C

dengan ijj

ijC M1)1( dan ijM minor matriks A.

28

7. Hasil perkalian matriks

Sebagian besar perhitungan pada metode simpleks direvisi adalah

mengenai penggantian 1B

dari satu tabel ke tabel berikutnya. Hasil dari invers ini

akan digunakan untuk mempermudah perhitungan 1B

yang baru. Diasumsikan

bahwa kx akan masuk menjadi basis, uji rasio menunjukkan bahwa kx menjadi

basis pada baris ke-r, dengan Tmkrkkkk aaaax 21 .

Didefinisikan matriks mmE sebagai berikut:

1000

0100

001

00

0010

0001

)1(

2

1

rk

mk

rk

km

rk

rk

k

rk

k

a

aa

a

a

a

aa

a

E

E adalah matriks identitas ( mmI ) dengan kolom ke-r nya diganti dengan vektor

kolom T

rk

mk

rk

km

rkrk

k

rk

k

a

a

a

a

aa

a

a

a )1(21 1 .

Selanjutnya didefinisikan iE sebagai matriks elementer E yang berkaitan dengan

iterasi simpleks ke-i. Hasil kali invers (invers product) secara umum dapat

ditulis: 01211 EEEEB kkk (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 nnj xcxcxcxz ...)( 2211

terhadap kendala:

,...,,2,1;)...,,2,1(1atau 0

...2211

minjx

bxaxaxa

j

nmn

(2.15)

dengan jc adalah manfaat yang dapat diperoleh apabila barang ke-j dipilih, b

adalah jumlah sumber yang tersedia dan ia 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 jx akan menghasilkan

30

cabang 1dan 0 jj xx . 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 i

j

a

c. Untuk melihat hal ini maka nilai

i

j

a

c

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 i

j

a

c terbesar dan barang yang terburuk adalah barang yang

memiliki nilai i

j

a

c tekecil.

Untuk menyelesaikan setiap subpersoalan yang dihasilkan dari suatu

persoalan ransel, dihitung seluruh rasio nilai i

j

a

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

tidak

ya

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.

mulai

data masukan

berhenti

iterasi

Hasil Optimal

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 ),( yx 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 jj cz

negatif terbesar. Untuk

persoalan meminimumkan dicari variabel basis baru dengan memilih

kolom pivot, yaitu kolom dengan nilai jj cz

positif terbesar.

33

b. Dicari nilai iR , yaitu ib dibagi unsur-unsur pada kolom pivot yang bernilai

positif ( positif, ikik

ii a

a

bR ). Selanjutnya dipilih iR terkecil.

c. Baris dengan iR 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 jj cz

nonnegatif untuk setiap j .

Adapun tabel simpleks, disajikan dalam Tabel 2.1 berikut.

34

Tabel 2.1 Metode Simpleks

jc 1c 2c 3c

nc

ic ji xx \

1x 2x 3x

nx ib iR

1c 1x 11a 12a 13a

na1 1b 1R

2c 2x 21a 22a 23a

na2 2b 2R

3c 3x 31a 32a 33a

na3 3b 3R

mc mx 1ma 2ma 3ma

mna mb mR

jz 1z 2z 3z

nz Z

jj cz

11 cz

22 cz

33 cz

nn cz

Z

keterangan:

jc : koefisien biaya untuk variabel jx

ic : koefisien biaya untuk variabel ix ,

ix : variabel yang menjadi basis dalam tabel yang ditinjau,

jx : variabel-variabel lengkap,

ib : suku tetap (tak negatif),

iR : rasio,

ija : koefisien teknis,

jz : ij

m

i

iac1

(hasil kali dari ic dengan ija ),

Z : i

m

i

ibc1

(hasil kali dari ic dengan ib ),

jj cz

: selisih jz dengan jc .

35

Contoh 2.6

Memaksimumkan 321321 203060),,( xxxxxxz

terhadap kendala:

0,,

5

821

23

3

2023

24

4868

321

2

321

321

321

xxx

x

xxx

xxx

xxx

(2.16)

Penyelesaian

1) Tambahkan variabel slack 4,3,2,1, isi pada kendala (2.16), menjadi

Memaksimumkan 4321321321 0000645),,,( ssssxxxsxxxz i

terhadap kendala:

0,,,,,,

5000

800021

23

3

2000023

24

4800068

4321321

43212

4321321

4321321

4321321

ssssxxx

ssssx

ssssxxx

ssssxxx

ssssxxx

2) Membuat Tabel Awal simpleks

36

Tabel 2.2 Tabel Awal Simpleks

jc 60 30 20 0 0 0 0

ic ji xx \ 1x 2x 3x 1s 2s 3s 4s ib iR

0 1s 8 6 1 1 0 0 0 48 6

848

0 2s 4 2

23 0 1 0 0 20 5

420

0 3s 2 2

3 2

1 0 0 1 0 8 42

8

0 4s 0 1 0 0 0 0 1 5

jz 0 0 0 0 0 0 0 0

jj cz

60

30

20

0 0 0 0 0

Langkah-langkah uji optimum tabel (Tabel 2.2):

(a) Memilih kolom jj cz

terbesar (negatif) adalah 60 , jadi 1x merupakan

variabel masuk,

(b) Memilih rasio terkecil:

428

31

3

a

b , jadi 3s variabel keluar,

(c) Membagi baris ke-3 dengan 31a ,

(d) Membuat Tabel Antara, yaitu:

37

Tabel 2.3 Tabel Simpleks Antara

jc 60 30 20 0 0 0 0

ic j

xix \ 1x 2x 3x 1s 2s 3s 4s ib

0 1s 8 6 1 1 0 0 0 48 R1

0 4 2 2

3 0 1 0 0 20 R2

0 3s 1

43

41 0 0

21 0 4 R3

0 4s 0 1 0 0 0 0 1 5 R4

jz 0 0 0 0 0 0 0 0

jj cz

60

30

20

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

jc 60 30 20 0 0 0 0

ic j

xix \ 1x 2x 3x 1s 2s 3s 4s ib iR

0 1s 0 0 1

1 0 4

0 16 16

116

0 2s 0 1

21 0 1 2

0 4 8

21

4

60 1x 1

43

41 0 0

21 0 4

16

41

4

0 4s 0 1 0 0 0 0 1 5

05

jz 60 45 15 0 0 30 0 240

jj cz

0 15 5

0 0 30 0 240

38

3) Pada langkah ini sama dengan langkah 2 (a sampai e), dengan memperhatikan

Tabel 2.4,

(a) jj cz

terbesar (negatif) adalah 5 , jadi 3x merupakan variabel masuk,

(b) Memilih rasio terkecil:

84

14

32

2

a

b , jadi 2s variabel keluar,

(c) Membagi baris ke-2 dengan 23a ,

(d) Membuat Tabel Antara, yaitu:

Tabel 2.5 Tabel Simpleks Antara

jc 60 30 20 0 0 0 0

ic ji xx \ 1x 2x 3x 1s 2s 3s 4s ib

0 1s 0 0 1

1 0 4

0 16 R1

'

20 3x

0 1

21

0 1 2

0 8 R2'

60 1x

1 43

41

0 0 21

0 4 R3'

0 4s 0 1 0 0 0 0 1 5

R4'

jz 60 45 15 0 0 30 0 240

jj cz

0 15 5

0 0 30 0 240 Rz

'

(e) Melakukan Operasi Baris Elemeter (OBE), dengan menolkan elemen yang

diberi tanda persegi panjang. (Diperoleh Tabel 2.6)

2zz

233

211

R5RR

R31RR

RRR

'

'

'

39

Tabel 2.6 Tabel Ketiga Simpleks

jc 60 30 20 0 0 0 0

ic ji xx \ 1x 2x 3x 1s 2s 3s 4s ib

0 1s 0 2

0 1 2 8

0 24

20 3x 0 2

1 0 2 4

0 8

60 1x 2

45 0 0

21

21

0 2

0 4s 0 1 0 0 0 0 1 5

jz 60 35 20 0 10 10 0 280

jj cz

0 5 0 0 10 10 0 280

Karena 0jj cz untuk setiap j, maka tabel sudah optimal dengan nilai

fungsi sasaran 280z , solusi layak basisnya

)5,0,0,24,8,0,2(),,,,,,( 4321321 ssssxxx .

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 ,cxz

terhadap kendala: bAx ),,(

dan 0x

(2.17)

dengan:

nccc ,...,, 21c merupakan vektor baris,

0

0

0

,, 2

1

2

1

0bx

mn b

b

b

x

x

x

merupakan vektor-vektor kolom,

A merupakan matriks nm :

mnmm

n

n

aaa

aaa

aaa

21

22221

11211

A .

Untuk memperoleh persoalan program linear bentuk kanonik dalam bentuk

matriks maka pada (2.17) ditambahkan variabel slack:

ns

s

s

2

1

s ,

sehingga (2.17) dalam bentuk kanonik menjadi:

41

Memaksimumkan scxcsxz NBVBVB),(

terhadap kendala:

0s

xb

s

xIA dan , ,

dengan

VBc

koefisien-koefisien fungsi tujuan yang berkaitan dengan Bx

VBx

variabel basis

NBc

koefisien-koefisien fungsi tujuan yang berkaitan dengan s

s

variabel slack

I

matriks identitas nm .

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 bs

xIA , , memiliki m

persamaan dan n

variabel

yang tidak diketahui, dengan Tnxxx )...,,,( 21x dan T

nsss )...,,,( 21s adalah

variabel slack; suatu solusi layak basis diperoleh dengan menetapkan mn

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 bBxVB ,

42

dengan

m

2

1

VB

VB

VB

VB

x

x

x

x

merupakan vektor kolom variabel basis, diperoleh dengan menghilangkan

variabel-variabel nonbasis dari s

x,

mmmm

m

m

BBB

BBB

BBB

21

22221

11211

B

merupakan matriks basis yang diperoleh dengan mengeliminasi kolom-kolom

yang berkaitan dengan kofisien- kofisien variabel basis dari IA, .

Metode simpleks memperkenalkan hanya variabel-variabel basis

sedemikian sehingga B adalah nonsingular, sehingga 1B

akan selalu ada. Oleh

karena itu, untuk menyelesaikan bBxVB , kedua ruas harus dikalikan terlebih

dahulu dengan 1B , sehingga diperoleh

bBBxB 1VB

1 .

Karena IBB 1 , maka solusi yang diharapkan untuk variabel-variabel basis

adalah

bBx 1VB .

43

Misal VBc adalah vektor yang unsur-unsurnya merupakan koefisien-koefisien

fungsi tujuan (termasuk nol untuk variabel-variabel slack) yang berkaitan dengan

VBx , maka nilai fungsi tujuan untuk solusi basisnya adalah

bBcxc 1VBVBVBz .

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

Jordan 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 VBc .

Adapun langkah-langkah metode simpleks direvisi adalah:

1. Menetapkan bahwa kolom 1B

yang bersangkutan akan selalu dibaca IB 1

pada awalnya.

44

2. Menghitung 1VBBc 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 nkxk ...,,2,1, .

4. Untuk menentukan dalam baris mana kx menjadi basis masuk, hitung kolom

kx dari tabel bersangkutan )( 1kxB dan hitung sisi kanan dari tabel

bersangkutan )( 1bB . Kemudian digunakan test rasio untuk menentukan

dimana baris kx seharusnya masuk menjadi basis, sehingga diperoleh

himpunan variabel basis untuk tabel baru (menggunakan OBE).

5. Gunakan kolom kx dalam tabel bersangkutan untuk menentukan aturan atau

langkah ini pada 1B

yang bersangkutan untuk memperoleh 1B

baru.

Kembali ke langkah 1.

Contoh 2.7

Memaksimumkan 2121 53),( xxxxz

terhadap kendala:

bulat.bilangan dan 0,

1823

6

4

21

21

2

1

xx

xx

x

x

(2.18)

45

Penyelesaian

1. Persoalan (2.18) diubah ke bentuk program linear kanonik dengan

menambahkan variabel slack menjadi:

Memaksimumkan 3212132121 00053),,,,( sssxxsssxxz

terhadap kendala:

bulatbilangan dan 0,,,,

1823

6

4

32121

321

22

11

sssxx

sxx

sx

sx

atau ditulis dalam bentuk tabel, yaitu:

1823 3 Baris

6 2 Baris

4 1 Baris

53 0 Baris

0 Tabel

321

22

11

21

sxx

sx

sx

xxz

dengan 21321 ,VNB(0)dan ,,VB(0) xxsss .

Kolom 10B terbaca awalnya yaitu IB 1

0

100

010

001

01

0 IBB .

2. Menentukan variabel nonbasis yang akan masuk menjadi variabel basis

dengan menghitung koefisien dari tiap-tiap variabel nonbasis dalam baris 0,

diperoleh

000VBc , sehingga

000

100

010

001

00010VBBc

46

3. Dari langkah (2) diperoleh nilai dari tiap-tiap variabel nonbasis adalah:

55

2

1

0

000

33

3

0

1

000

221

0VB2

111

0VB1

cac

cac

Bc

Bc

( 0, 21 cc , maka basis belum optimal), dicari variabel nonbasis kx yang

mempunyai koefisien negatif terbesar dari baris 0 dalam Tabel 0 yang menjadi

variabel basis masuk . Karena 2x mempunyai koefisien negatif terbesar dalam

baris 0, maka 2x variabel basis masuk menggantikan variabel basis keluar 2s .

4. Kolom untuk 2x dalam tabel bersangkutan:

2

1

0

2

1

0

100

010

001

21

02 aa B

Sisi kanan tabel bersangkutan

18

6

4

18

6

4

100

010

0011

0 bB

Selanjutnya digunakan test rasio untuk menentukan 2x masuk ke dalam baris

yang mana, yaitu:

9218,3 Baris

terkecil)rasiotest (616,2 Baris

efinisitidak terd04,1 Baris

2

2

2

x

x

x

Jadi 2x 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

sudah bernilai nol. (baris '1 )

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

63 3' Baris

6 2' Baris

4 ' 1 Baris

3053 0' Baris

1 Tabel

31

22

11

21

sx

sx

sx

sxz

dengan 21321 ,VNB(1)dan ,,VB(1) sxsxs .

6. Melakukan OBE pada 10B dengan langkah seperti pada langkah (5) (a

sampai c), diperoleh:

120

010

0011

1B

7. 050

120

010

001

05011VBBc

8. Dari langkah (7) diperoleh nilai dari tiap-tiap variabel nonbasis 21, sx :

50

0

1

0

0500

0

1

0

33

3

0

1

050

10VB2

111

1VB1

Bc

Bc

s

cac

48

Tabel belum optimal, karena masih terdapat jc yang negatif, yaitu 01c ; 1x

mempunyai koefisien negatif terbesar dalam baris 0 dari Tabel 1, sehingga 1x

masuk sebagai basis dalam Tabel 1.

9. Kolom untuk 1x pada Tabel 1 yaitu:

3

0

1

3

0

1

120

010

001

11

1 aB

Sisi kanan pada Tabel 1

6

6

4

18

6

4

120

010

0011

1 bB

Test rasio:

terkecil)rasio(test 236,3 Baris

efinisitidak terd06,2 Baris

414,1 Baris

1

1

1

x

x

x

Dari test rasio terlihat bahwa 1x masuk sebagai basis dalam baris 3.

10. Dari langkah (9) dibentuk Tabel 2 dengan OBE:

a) Menambahkan baris ke-1 Tabel 1 dengan )3

1( kali baris ke-3. (baris "1 )

b) Baris ke-2 tetap, karena 1x pada baris 2 sudah nol. (baris "2 )

c) Mengalikan baris ke-3 dengan 31 . (baris "3 )

d) Menambahkan baris ke-0 dengan baris ke-3. (baris "0 )

Diperoleh Tabel 2:

49

2 3" Baris

6 2" Baris

2 " 1 Baris

365 0" Baris

2

Tabel

31

22

1

32

sx

sx

s

ssz

dengan 23121 ,VNB(2)dan ,,VB(2) ssxxs .

11. Melakukan OBE pada 11B seperti pada langkah (10) (a sampai c), sehingga

diperoleh:

3320

01033

21

1

1

12B

12. 130

3320

01033

21

3501

1

12VBBc

13. Dari langkah (12) diperoleh nilai variabel nonbasis 23, ss adalah

30

0

1

0

1300

0

1

0

10

1

0

0

1300

1

0

0

10VB2

10VB3

Bc

Bc

s

s

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

6

2

18

6

4

3320

01033

21

1

1

12 bB

Sehingga 121 ,,VB(2) xxs

dan solusi layak basisnya adalah

0,

2

6

2

32

1

2

1

ss

x

x

s

Jadi diperoleh tabel optimal untuk nilai z yaitu:

36

18

6

4

13012VB bBc .

Jadi nilai fungsi sasaran yaitu 36z , solusi layak basisnya

)0,0,2,6,2(),,,,( 32121 sssxx .

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 variabelnya adalah anggota himpunan

,...2,1,0),,...,,(, 21 jj xxxxxbAxxS . 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:

Memaksimumkan atau meminimumkan: f = j

n

jj xc

1

,

terhadap kendala:

mibxabxabxa ij

n

jijij

n

jijij

n

jij ,...,2,1,atau ,atau ,

111

njxx jj ,...,2,1,,...2,1,0,0 ,

dengan iij ba , dan ic adalah konstanta, jx 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

Memaksimumkan atau meminimumkan: f = j

n

jj xc

1

,

terhadap kendala:

nkkjx

njx

byaxa

j

j

ik

t

kikj

n

jij

;...,,2,1bulat;bilangan

...,,2,1,0

,11

dengan iij ba , dan ic adalah konstanta, kjx j ...,,2,1;

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 1),( Sxxf

P2: memaksimumkan 2),( Sxxf

dan 21 SS , maka jika 0x adalah

suatu penyelesaian optimal dalam P1 dan *x adalah suatu penyelesaian optimal

dalam P2, maka berlaku )()( *0 xfxf .

Bukti:

Diketahui 0x adalah penyelesaian optimal P1, dengan persoalan

memaksimumkan, berlaku 10 ),()( Sxxfxf . Karena 21 SS

dan 12 SS

53

sehingga 20 ),()( Sxxfxf . Karena variabel *x merupakan suatu

penyelesaian optimal dalam 2P maka *x elemen dari 2S , sehingga

)()( *0 xfxf .

Akibat Sifat 2.2

Jika 20 Sx , maka 0x 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 0x (suatu penyelesaian optimal

dalam program linear P1) bernilai bulat, maka menurut sifat di atas 0x 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 kx adalah suatu variabel bilangan bulat. Jika nilai optimal adalah *kx

berupa bilangan pecahan, maka 1**k

xxk

x k tidak mungkin memuat

penyelesaian bilangan bulat yang layak (dengan A mendefinisikan bilangan

bulat terbesar A ). Jadi 1**k

xxk

x k harus disingkirkan. Akibatnya

Suatu nilai bilangan bulat kx yang layak harus memenuhi salah satu kondisi

*k

xxk atau 1*k

xxk .

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 *k

xxk atau 1*k

xxk 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:

ya

tidak

Gambar 2.3 Diagram alir metode cabang dan batas

Rumuskan dan selesaikan persoalan dengan metode simpleks. Tentukan batas atas solusi bulat yang layak

Buat pencabangan dengan memasukkan fungsi kendala

*k

xxk dan 1*k

xxk , dengan kx

mendefinisikan bilangan bulat terbesar kx

Selesaikan penyelesaian optimal dengan metode simpleks untuk masing-masing cabangnya

Tentukan batas bawah solusi bulat yang layak

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

Batas atas sama dengan batas

bawah

Optimal (solusi bulat yang

layak=batas bawah)

57

Contoh 2.8

Misal diberikan persoalan knapsack:

Memaksimumkan 43214321 8122216),,,( xxxxxxxxz

terhadap kendala

).4,3,2,1(;1atau 0

143475 4321

jx

xxxx

j

Penyelesaian

Penyelesaian persoalan knapsack di atas diawali dengan menghitung rasio i

j

a

c dan

menentukan peringkat setiap variabel berdasarkan besarnya rasio ini (peringkat 1

menyatakan variabel terbaik). Hasilnya adalah sebagai berikut:

Barang ke-

i

j

a

c Peringkat

1

5

16 1

2

7

22 2

3

4

12 3

4

3

8 4

Langkah selanjutnya yaitu menjadikan persoalan knapsack sebagai persoalan

program linear relaksasi. Dari peringkat dipilih 11x kemudian 12x serta

04x sehingga solusi program linear relaksasinya adalah 44)12(212216z ,

dengan 0dan 21,1 4321 xxxx . Selanjutnya dilakukan proses pencabangan

dan pembatasan.

58

Pada proses pencabangan dan pembatasan dihasilkan sub-subpersoalan.

Subpersoalan 1 diperoleh dengan menjadikan persoalan knapsack sebagai

persoalan program linear relaksasi. Solusinya adalah 1,44 21 xxz ,

0dan 2

143 xx . Jadi nilai optimal z

untuk persoalan knapsack

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 )4,3,2,1(;1atau 0 jx j maka jx hanya boleh

bernilai 0 atau 1. Nilai 421 dan , xxx sudah sesuai dengan syarat kendala sehingga

pencabangan dikenakan pada 3x , diperoleh subpersoalan 2 dan 3. Selanjutnya

setiap subpersoalan diselesaikan (dicari solusinya) berdasarkan kendala-kendala

pada setiap subpersoalan.

Subpersoalan 2 diselesaikan, solusinya adalah 3

139z , 121 xx ,

32

0 43 xx . Berikutnya subpersoalan 3 diselesaikan, diperoleh solusi 7

306z ,

.0,75

,1 4231 xxxx 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 1 0,1,36 4231 xxxxz . Karena seluruh

variabel keputusan telah berharga 0 atau 1, maka solusi dari subpersoalan 4

merupakan calon solusi. Untuk subpersoalan 5 solusinya adalah

0 1,53

,5

2184221 xxxxz . Karena subpersoalan 4 tidak memberikan

solusi fisibel selain 0 atau 1 dengan 36z , maka pencabangan dari subpersoalan

4 tidak akan memberikan informasi baru mengenai solusi optimal persoalan

knapsack.

Nilai 36z dari subpersoalan 4 dijadikan sebagai batas bawah atau lower

bound (LB) pada subpersoalan 5. Selanjutnya subpersoalan 5 dicabangkan dengan

,36LB

diperoleh subpersoalan 6 dan subpersoalan 7. Masing-masing

subpersoalan diselesaikan. Solusi dari subpersoalan 6 yaitu ,42z

1 ,0 4231 xxxx . Karena nilai seluruh variabel keputusan telah berharga 0

atau 1, maka solusi dari subpersoalan 6 adalah juga calon solusi. Calon solusi ini

memiliki nilai ,42z yang berarti lebih besar dari batas bawah, sehingga

subpersoalan 7 diselesaikan dengan .42LB

Subpersoalan 7 solusinya adalah

0 ,1,50 4321 xxxxz . 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

.42LB Hasil dari pencabangan ini yaitu subpersoalan 8 dan subpersoalan 9.

Kemudian setiap subpersoalan diselesaikan. Subpersoalan 8 solusinya adalah

.0 ,1,38 4321 xxxxz Nilai z

subpersoalan 8 tidak lebih besar dari

,42LB

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 .42LB

Solusinya adalah 7

300z ,

.0,5

218 ,1 4241 xxxx Nilai z

pada subpersoalan ini juga tidak

memberikan nilai yang lebih besar dari ,42LB

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 1 ,0,42 4321 xxxxz dan hal ini dinyatakan dengan

mencantumkan tanda ( ) di dekat kotak subpersoalan 6.

Ringkasan proses pencabangan dan pembatasan disajikan dalam gambar

pohon cabang dan batas berikut. (Gambar 2.4)

62

03x 13x

04x 14x 02x 12x

01x 11x

Gambar 2.4 Pohon cabang dan batas persoalan knapsack 0-1

Subpersoalan 2

3

130

3;0

1

24

2

3

1

z

xx

xx

LB=42

Subpersoalan 3

7

306

0

7

5

1

4

2

31

z

x

x

xx

Subpersoalan 8

38

0

1

43

21

z

xx

xx

LB=42

Subpersoalan 9

7

;

300

07

6

1

32

41

z

xx

xx

LB=42

Subpersoalan 5

5

218

0;1

5

3

432

1

z

xxx

x

LB=36

Subpersoalan 4

36

1

0

1

4

2

31

z

x

x

xx

calon solusi

Subpersoalan 7

LB=42

tidak fisibel

Subpersoalan 6

42

1

0

432

1

z

xxx

x

LB=36

calon solusi

Subpersoalan 1

442

1

13

21

z

x

xx

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

pola 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 s2 meter

Gambar 3.1 Pola Pemotongan

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 ass 21, meter, a meter adalah

panjang minimum pesanan dan 1s adalah sisa pemotongan Pola 2 sedangkan 2s

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

positif.bulat bilangan ;...,,2,1, batang ii wmiw Berikut ini adalah contoh

kombinasi yang dapat digunakan:

1. Memotong balok kayu dengan panjang L meter sebanyak 1w batang

menggunakan Pola 1 dan 2w batang menggunakan Pola 2.

2. Memotong balok kayu dengan panjang L meter sebanyak 3w batang

menggunakan Pola 1 dan 4w batang menggunakan Pola 3.

3. Memotong balok kayu dengan panjang L meter sebanyak 5w batang

menggunakan Pola 3 dan 6w 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 : meter. meter 12 xsw

Kombinasi II : meter. meter 24 ysw

Kombinasi III : meter. meter) (meter) ( 1625 zswsw

positif realbilangan ,, zyx .

Selanjutnya setiap produksi surplus dengan panjang a, b dan c meter harus

dipertimbangkan dalam perhitungan sebagai sisa pemotongan.

Pada Kombinasi I, Pola 1 menghasilkan 1f batang panjang a meter dan 2f

batang panjang b meter, dengan jumlah batang 21 ff

karena pemotongan

dengan Pola 1 menghasilkan 2 batang panjang a meter dan 2 batang panjang b

meter. Sehingga positif. realbilangan ,dan 2 21121 ffwff Untuk Pola 2

menghasilkan 1g batang panjang a meter dan 2g batang panjang b meter, dengan

jumlah batang 21 w2g

dan jumlah batang 22 w1g

karena pemotongan

balok menggunakan Pola 2 menghasilkan 2 batang panjang a meter dan 1 batang

panjang c meter dan positifbulat bilangan , 21 gg .

Pada Kombinasi II, Pola 1 menghasilkan 1h batang panjang a meter dan

2h batang panjang b meter, dengan jumlah batang 21 hh

karena pemotongan

dengan Pola 1 menghasilkan 2 batang panjang a meter dan 2 batang panjang b

66

meter. Sehingga positif. realbilangan ,;2 21321 hhwhh Sementara Pola 3

menghasilkan 1i batang panjang a meter, 2i batang panjang b meter dan 3i batang

panjang c meter, dengan jumlah batang 321 iii

karena pemotongan dengan

Pola 3 menghasilkan 1 batang panjang a meter, 1 batang b meter dan 1 batang

panjang c meter. Sehingga 4321 ),,( wiii

(1 batang a meter, 1 batang b meter, 1

batang c meter) dan positif.bulat bilangan ,, 321 iii

Pada Kombinasi III, Pola 3 menghasilkan 1j batang panjang a meter, 2j

batang panjang b meter dan 3j batang panjang c meter, dengan jumlah batang

321 jjj

karena pemotongan dengan Pola 3 menghasilkan 1 batang panjang a

meter, 1 batang b meter dan 1 batang panjang c meter. Sehingga 5321 ),,( wjjj

(1 batang a meter, 1 batang b meter, 1 batang c meter) dan

positif realbilangan ,, 321 jjj . Sementara Pola 2 menghasilkan 1k batang

panjang a meter dan 2k batang panjang c meter, dengan jumlah batang 61 2 wk

dan jumlah batang 62 1 wk

karena pemotongan balok menggunakan Pola 2

menghasilkan 2 batang panjang a meter dan 1 batang panjang c meter dan

positif.bulat bilangan , 21 kk

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

Pola

(j)

Jumlah panjang pesanan yang dihasilkan (batang) Jumlah yang

dipesan

(batang)

Kombinasi I Kombinasi II Kombinasi III

a

(m)

b

(m)

c

(m)

a

(m)

b

(m)

c

(m)

a

(m)

b

(m)

c

(m)

a

(m)

b

(m)

c

(m)

1 1f 2f -

1h 2h - - - -

A B C 2 1g -

2g - - - 1k 2k

3 - - - 1i 2i 3i 1j 2j 3j

Selanjutnya bagaimana produksi surplus diperoleh, hal ini diperhatikan pada

masing-masing kombinasi.

Kombinasi I, produksi surplus panjang a meter diperoleh jika A.)( 11 gf

Kombinasi II, produksi surplus panjang a meter diperoleh jika A)( 11 ih ;

produksi surplus panjang b meter diperoleh jika B.)( 22 ih

Kombinasi III, produksi surplus panjang a meter diperoleh jika A)( 11 jk ;

produksi surplus panjang c meter diperoleh jika C)( 32 jk

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

meter 7L dan menginginkan sisa pemotongan seminimum mungkin. Pesanan

disajikan dalam Tabel 3.2 sebagai berikut:

Tabel 3.2 Jumlah Pesanan

Pesanan

(i)

Panjang yang diinginkan

(meter)

Jumlah yang dipesan

(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 5,1a meter merupakan panjang awal yang diketahui.

Pola 1, membagi balok kayu panjang 7 meter dengan 2a dan 2b, maka:

meter 3

meter

5,122a

b merupakan panjang yang diinginkan, berdasarkan Pola 1, maka:

panjang yang diinginkan

balok kayu panjang 7 meter – 3 meter, sehingga:

meter 2

meter 42

meter 3meter 72

b

b

b

Jadi panjang meter 2b .

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

meter3

meter5,3meter5,6

meter ,56) 3,5(

meter 6,5)2(1,5

meter5,0meter 7)(

c

c

c

c

cba

Jadi panjang meter3c , 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:

meter.1

meter76

meter7)33(

meter 7kayu balok panjang )2(

s

s

s

sca

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 : meter. 15meter115

Kombinasi II : meter. 5,7meter5,015

Kombinasi III : meter. 13)meter 13()meter 5,020(

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: meter. 305,125

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: meter. 1025

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: meter 24meter 38 .

Jadi, total sisa pemotongan adalah:

Kombinasi I : meter.45meter 30meter15

Kombinasi II : meter 5,17meter10meter5,7 .

Kombinasi III : meter 5,38meter24meter5,1meter13 .

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 1B , harga

akhir ( jj cz ), 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,

jx

jumlah balok kayu dengan panjang L meter yang dipotong menurut pola

njj ...,,2,1, ,

ija = jumlah potongan balok kayu panjang iK dengan pola njj ...,,2,1, ;

mi ...,,2,1 ,

ib = banyaknya pesanan untuk panjang miKi ...,,2,1, ,

jc = koefisien fungsi tujuan nj ...,,2,1 ,

maka bentuk umum persoalan pemotongan balok kayu dalam upaya

meminimumkan sisa pemotongan adalah:

Meminimumkan nn xxxxxxz ...)...,,,( 2121

terhadap kendala:

....,,2,1bulat,bilangan dan 0

,...,,2,1

...2211

njx

mi

bxaxaxa

j

iijiniiii

(3.1)

Dalam bentuk umum persoalan program linear, (3.1) dapat ditulis:

Meminimumkan j

n

jjj xcxz

1

)( ,

terhadap kendala :

,...,,2,1

,1

mi

bxa iij

n

jij

(3.2)

. setiapuntuk 1;...,,2,1bulat;bilangan dan 0dengan jcnjx jj

Dalam bentuk matriks, persoalan (3.2) dapat ditulis:

74

Meminimumkan cxx)(z

terhadap kendala: bAx

(3.3)

bulatbilangan dan 0x ,

dengan

c

vektor baris berdimensi n ,

x

vektor kolom berdimensi n ,

b

vektor kolom berdimensi m ,

A

matriks berordo nm .

Dalam bentuk kanonik, bentuk (3.3) bentuk terakhir ditulis sebagai:

Meminimumkan NBNBVBVBNBVB ),( xcxcxxz ,

terhadap kendala: bNB NBVB xx ,

bulatbilangan dan 0, NBVB xx ,

dengan

VBc

Koefisien-koefisien fungsi tujuan yang bersesuaian dengan VBx ,

VBx

variabel basis,

NBc

Koefisien-koefisien fungsi tujuan yang bersesuaian dengan NBx ,

NBx

variabel nonbasis,

B

matriks yang berkaitan dengan variabel VBx ,

N

matriks yang berkaitan dengan variabel NBx ,

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

tiap 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 miKi ...,,2,1,

meter.

Oleh karena itu dapat didefinisikan nyyy ...,,, 21 , dengan njy j ...,,2,1,

adalah

jumlah balok kayu miKi ...,,2,1,

meter yang dihasilkan dari pemotongan satu

batang balok kayu panjang L meter berdasarkan pola yang diberikan.

Harga akhir ( jj cz ) dengan teknik pembangkit kolom diperoleh dengan

cara:

1VB jjj ycz 1Bc , dengan 02

1

n

j

y

y

y

y

dan bilangan bulat, nj ,...,2,1 .

76

Telah dijelaskan bahwa njy j ...,,2,1,

adalah jumlah balok kayu

miKi ...,,2,1,

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 jy harus memenuhi persamaan:

,,...,2,1,bulatbilangan dan 0;,...,2,1,0

...2211

njymiK

LyKyKyK

ji

nm

dengan

L

panjang balok kayu (meter)

iK

panjang balok kayu yang dipesan (meter); miLKi ...,,2,1, .

Karena teknik pembangkit kolom adalah suatu teknik yang dapat

memberikan nilai jj cz

terbaik (positif pada persoalan meminimumkan) maka

berdasarkan Sifat 2.1 (Bab II. A) ekuivalen dengan menyelesaikan subpersoalan:

Memaksimumkan 1)(1

j

n

jjj yyw

terhadap kendala:

bulat,bilangan dan 0

,1

j

j

n

ji

y

LyK (3.4)

,...,,2,1,...,,2,1 minj

dengan koefisien j

merupakan elemen ke- j

dari 1VB Bc . Dengan kata lain

subpersoalan (3.4) dinamakan persoalan knapsack, yaitu persoalan program linear

dengan sebuah kendala. Dari teori program linear (Taha 1996) j

disebut juga

nilai dual (dual prices).

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 njy j ...,,2,1,

ke

pola njj ...,,2,1,

dan variabel kx . Selanjutnya ditentukan variabel nonbasis

nkxk ...,,2,1,

yang akan masuk menjadi variabel basis dalam baris k

menggunakan metode simpleks direvisi. Nilai kx dihitung dengan menggunakan

bB 1kx 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 1VB

1 dan BcB dalam tabel bersangkutan yaitu:

10

1 BIB pada tabel awal, untuk 1B

berikutnya dihitung dengan

menggunakan bentuk hasil kali invers. Untuk menghitung 1VBBc , ditentukan

terlebih dahulu koefisien-koefisien variabel basis ( VBc ) yang bersesuaian,

misal 10VBBc , VBc diperoleh berdasarkan tabel awal, berikutnya 1

1VBBc , VBc ,

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 jy yaitu:

1))...(((1 21VBVB nj yyyy 11 BcBc .

78

5. Mencari harga akhir pola yang efisien, diperoleh dengan menyelesaikan

persoalan knapsack:

Memaksimumkan 1)(1

j

n

jjj yyw

terhadap kendala:

bulat,bilangan dan 0

,1

j

j

n

ji

y

LyK

....,,2,1,...,,2,1 minj

6. Hasil perhitungan persoalan knapsack menggunakan metode cabang dan batas

akan memberikan solusi optimal untuk program linear, hasil ini akan

berkorespondensi dengan njy j ...,,2,1,

ke pola njj ...,,2,1,

dan

variabel kx .

7. Dari langkah (6) dapat diperoleh variabel nonbasis yang akan menjadi variabel

basis, diperoleh dengan cara menghitung jy1B dan B-1b kemudian digunakan

test rasio untuk menentukan dalam baris mana kx masuk sebagai variabel

basis.

8. Teknik pembangkit kolom akan menghasilkan solusi optimal jika penyelesaian

persoalan knapsack dengan metode cabang dan batas menghasilkan fungsi

tujuan 0w 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

(j)

Jumlah panjang 1,5 meter

(batang)

Jumlah panjang 2 meter

(batang)

Jumlah panjang 3 meter

(batang)

Sisa

(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 jx jumlah balok kayu panjang 7 meter yang dipotong menurut

pola j; .8...,,2,1j 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 87654321 xxxxxxxx

Sisa pemotongan (meter): 5,12577777777 87654321 xxxxxxxx ,

maka fungsi tujuan adalah:

Meminimumkan 5,12577777777z 87654321 xxxxxxxx

Tanpa mempengaruhi optimasi, maka fungsi tujuan dapat ditulis sebagai:

Meminimumkan .87654321 xxxxxxxxz (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:

54321 2234 xxxxx .

Maka kendala 1 menjadi 252234 54321 xxxxx (3.6)

Dengan cara yang sama, diperoleh kendala 2 dan kendala 3 :

kendala 2 : 20232 76532 xxxxx (3.7)

kendala 3 : 152 8754 xxxx (3.8)

Perlu diingat bahwa koefisien jx 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 jx harus diperlukan untuk mengasumsikan

nilai-nilai bilangan bulat.

Dari persamaan (3.5) sampai (3.8) diperoleh persamaan persoalan program linear

sebagai berikut:

82

Meminimumkan 87654321821 )...,,,( xxxxxxxxxxxz

terhadap kendala :

bulat.bilangan dan 8,...,2,1;0

152

20232

252234

8754

76532

54321

jx

xxxx

xxxxx

xxxxx

j

(3.9)

2. Merubah persoalan program linear meminimumkan ke bentuk program linear

kanonik.

Dari bentuk persoalan program linear meminimumkan diperoleh bahwa 1x

hanya terjadi dalam kendala 1,5 meter (karena pola 1 hanya menghasilkan balok

kayu 1,5 meter), 6x hanya terjadi dalam kendala 2 meter (karena pola 6 hanya

menghasilkan balok kayu 2 meter) dan 8x hanya terjadi dalam kendala 3 meter

(karena pola 8 hanya menghasilkan balok kayu 3 meter). Ini berarti 61, xx dan 8x

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 ii txxxxxxxxtxxxz 0),...,,,( 87654321821

terhadap kedala:

152

20232

252234

38754

276532

154321

txxxx

txxxxx

txxxxx

(3.10)

)8,...,2,1(;0;)8,...,2,1(;0 itjx ij dan bilangan bulat.

Dari persamaan bentuk kanonik diperoleh 861 ,,VB xxx

dan

75432 ,,,,VNB xxxxx .

83

3. Menghitung 10VB

10 dan BcB

,

00

00

00

,

200

030

004

2

13

14

1

100 BB

maka

2

1

3

1

4

1

2

13

14

1

0VB

00

00

00

1111Bc.

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 21, yy dan 3y dengan jy 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, 5x dinyatakan oleh 1dan 1,1 321 yyy .

Untuk basis tertentu, suatu pola dinyatakan oleh 21, yy dan 3y akan ditentukan

nilai jj cz

nya sebagai:

11 32

123

114

1

3

2

1

VB yyy

y

y

y

cz jj1Bc .

Karena 21, yy dan 3y yang dipilih tidak boleh melebihi panjang balok kayu 7

meter serta 21, yy dan 3y harus bilangan bulat positif, sehingga untuk sebarang

84

pola 21, yy dan 3y harus memenuhi:

bulat.bilangan dan 0,,y

732y 1,5

321

321

yy

yy

4. Mencari harga akhir pola yang efisien

Untuk mencari pola yang paling efisien , dicari dengan menyelesaikan

persoalan knapsack sebagai berikut:

Memaksimumkan 1( 32

123

114

1321 ),, yyyyyyw

terhadap kendala:

732y 1,5 321 yy (3.11)

bulatbilangan dan 0,, 321 yyy

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 i

j

K

dan peringkat

No

i

j

K

Peringkat

1

6

1

23

41

1

2

6

1

2

31

2

3

6

1

32

1

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 1y , karena

memiliki peringkat yang sama. Dalam hal ini yang dipilih adalah 1y , sehingga

32 dan yy ditentukan sama dengan nol. Jadi solusinya adalah

314

,0,61

132 yxyw . Langkah berikutnya adalah memilah daerah fisibel

dari soal program linear relaksasi yaitu dengan memilih variabel yang benilai

pecahan (noninteger). Solusi 1y benilai noninteger dan setiap titik pada persoalan

knapsack akan benilai 5atau 4 11 yy maka dilakukan pencabangan dari

variabel 1y sehingga diperoleh dua subpersoalan tambahan yaitu subpersoalan 2

dan 3, dengan

subpersoalan 2 subpersoalan 1 ditambahkan kendala 41y

subpersoalan 3 subpersoalan 1 ditambahkan kendala 51y .

Karena subpersoalan 2 dan 3 dibangun dengan cara menambahkan kendala yang

berkaitan dengan 1y , maka dapat dikatakan bahwa subpersoalan 2 dan 3 dibangun

dengan melakukan pencabangan pada 1y .

Selanjutnya dipilih salah satu subpersoalan yang belum diselesaikan. Misalkan

dipilih subpersoalan 2. Dengan mensubstitusi variabel-variabel yang diketahui,

diperoleh solusi optimal subpersoalan 2 yaitu 3

1,0,4,

6

1321 yyyw .

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 3y

noninteger dan setiap titik pada persoalan knapsack akan benilai 1atau 0 33 yy

maka dilakukan pencabangan pada variabel 3y sehingga diperoleh subpersoalan 4

dan 5, dengan

subpersoalan 4 subpersoalan 2 ditambahkan kendala 03y

subpersoalan 5 subpersoalan 2 ditambahkan kendala 13y .

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 3

10,1,0,

6

1123 yyyw . Untuk

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

3

7,0,1,

6

1233 yyyw .

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 1y noniteger

sehingga setiap titik pada persoalan knapsack akan benilai 4atau 3 11 yy dan

dilakukan pencabangan pada variabel 1y diperoleh subpersoalan 6 dan 7, dengan

subpersoalan 6 subpersoalan 5 ditambahkan kendala 22y

subpersoalan 7 subpersoalan 5 ditambahkan kendala 32y .

Menggunakan aturan LIFO, dipilih subpersoalan 7 untuk diselesaikan.

Dengan mensubstitusi variabel-variabel yang diketahui, diperoleh solusi

subpersoalan 7 yaitu 3

2,0,3,

6

1132 yyyw . Solusi pada subpersoalan 7

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 2,0,2,6

1132 yyyw .

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

variabel yang diketahui, diperoleh solusi subpersoalan 3 yaitu ,5,12

91yw

6

1,0 32 yy . Salah satu solusi subpersoalan 3 berharga negatif, sehingga

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 2,2, 216

1yyw dan 03y .

Dari uraian di atas dapat di digambarkan dalam gambar pohon cabang dan

batas berikut. (Gambar 3.2)

89

41y 51y

03y 13y

32y 22y

Gambar 3.2 Pohon cabang dan batas persoalan awal

Subpersoalan 1

6

1

3

14

0

1

32

w

y

yy

Subpersoalan 2

6

13

1

0

4

3

2

1

w

y

y

y Subpersoalan 3

51y

tidak fisibel

Subpersoalan 4

6

1

1

0

3

101

2

3

w

y

y

y Subpersoalan 5

6

1

3

0

1

72

1

3

w

y

y

y

Subpersoalan 7

6132

0

3

1

3

2

w

y

y

y Subpersoalan 6

6

1

2

0

2

1

3

2

w

y

y

y

90

5. Nilai solusi optimal untuk persoalan knapsack (3.11) berkorespondensi dengan

Pola 3. Jadi nilai 6

1adalah 33 cz , dan dengan memasukkan 3x 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 3x ke dalam basis maka dibentuk ruas kanan dari tabel

bersangkutan dan kolom 3x dari tabel bersangkutan.

Kolom 3x dari tabel bersangkutan:

00

2

2

00

00

00

0

2

2

3

22

1

2

13

14

1

10B .

Ruas kanan tabel bersangkutan:

2

153

204

25

2

13

14

1

10

15

20

25

00

00

00

bB

Test rasio: efinisitidak terd215

,10

32

320

,2

25

21

425

0.

Dari test rasio, rasio terkecil pada baris ke-2, sehingga 3x masuk basis pada

baris ke-2. Variabel basis yang baru 831 ,,VB(1) xxx .

91

7. Kembali ke langkah 3.

Untuk menghitung 11B maka digunakan bentuk hasil kali invers, yaitu:

2

12

14

1

4

1

2

13

14

1

2

34

3

100

11

00

00

0

00

00

00

100

00

01

BEB

.

00

00

0

1112

1

4

1

4

1

2

12

14

1

4

1

11VBBc

Kemudian digunakan teknik pembangkit kolom untuk menentukan pola

yang akan masuk basis. Untuk nilai dual ( 11VBBc ), suatu pola yang dinyatakan

oleh 321 dan , yyy ditentukan nilai jj cz

menjadi:

11 32

124

114

1

3

2

1

2

1

4

1

4

111VB yyy

y

y

y

cycz jjjj Bc .

Selanjutnya untuk tabel bersangkutan, teknik pembangkit kolom menghasilkan

persoalan knapsack:

Memaksimumkan 1( 32

124

114

1321 ),, yyyyyyw

terhadap kendala: 732y 1,5 321 yy , (3.12)

bulatbilangan dan 0,, 321 yyy

Dengan metode cabang dan batas diperoleh penyelesaian persoalan (3.12):

92

1. Menentukan rasio i

j

K

dan peringkat

No

i

j

K

Peringkat

1

6

1

23

41

2

2

8

1

24

1

3

3

6

1

32

1

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 3y , sehingga 21 dan yy ditentukan

sama dengan nol. Solusi yang diperoleh adalah 37

,0,61

321 yxyw .

Langkah berikutnya adalah memilah daerah fisibel dari soal program linear

relaksasi yaitu dengan memilih variabel yang benilai pecahan (noninteger). Solusi

3y benilai noninteger dan setiap titik pada persoalan knapsack akan benilai

3atau 2 33 yy sehingga dilakukan pencabangan pada variabel 3y sehingga

diperoleh dua subpersoalan tambahan yaitu subpersoalan 2 dan 3, dengan

subpersoalan 2 subpersoalan 1 ditambahkan kendala 23y

subpersoalan 3 subpersoalan 1 ditambahkan kendala 33y .

93

Karena subpersoalan 2 dan 3 dibangun dengan cara menambahkan kendala yang

berkaitan dengan 3y , maka dapat dikatakan bahwa subpersoalan 2 dan 3 dibangun

dengan melakukan pencabangan pada 3y .

Selanjutnya dipilih salah satu subpersoalan yang belum diselesaikan.

Misalkan dipilih subpersoalan 2. Dengan mensubstitusi variabel-variabel yang

diketahui, diperoleh solusi optimal subpersoalan 2 yaitu ,8

1w

2

1,0 21 yy .

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 2y

noninteger dan setiap titik pada persoalan knapsack akan benilai 1atau 0 22 yy

maka dilakukan pencabangan pada variabel 2y sehingga diperoleh subpersoalan 4

dan 5, dengan

subpersoalan 4 subpersoalan 2 ditambahkan kendala 02y

subpersoalan 5 subpersoalan 2 ditambahkan kendala 12y .

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 3

10,0,1,

12

1132 yyyw .

Variabel 1y 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, diperoleh solusi optimal subpersoalan 4 yaitu

3

8,1,0,

6

1132 yyyw .

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 1y noniteger sehingga setiap titik pada persoalan knapsack

akan benilai 3atau 2 11 yy maka dilakukan pencabangan pada variabel 1y

sehingga diperoleh subpersoalan 6 dan 7, dengan

subpersoalan 6 subpersoalan 4 ditambahkan kendala 21y

subpersoalan 7 subpersoalan 4 ditambahkan kendala 31y .

Menggunakan aturan LIFO, dipilih subpersoalan 7 untuk diselesaikan.

Dengan mensubstitusi variabel-variabel yang diketahui, diperoleh solusi

subpersoalan 7 yaitu 4

5,0,3,

16

1231 yyyw . Nilai fungsi tujuan tidak lebih

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

95

2,0,2 132 yyy . 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

3,1,0,4

1321 yyyw . 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 0,2,2,0 321 yyyw . Nilai w optimal untuk persoalan

knapsack (3.12) diperoleh 0w , 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.

23y 33y

12y 02y

21y 31y

Gambar 3.3 Pohon cabang dan batas persoalan kedua

Subpersoalan 1

61

37

0

3

21

w

y

yy

Subpersoalan 2

8

1

02

1

2

1

2

3

w

y

y

y Subpersoalan 3

33y

tidak fisibel

Subpersoalan 5

12

310

1

0

1

1

3

2

w

y

y

y Subpersoalan 4

6

1

1

0

38

1

3

2

w

y

y

y

Subpersoalan 6

0

2

0

2

2

3

1

w

y

y

y Subpersoalan 7

16145

2

3 0

31

w

y

y

y

97

Untuk mendapatkan nilai-nilai variabel basis VB(1) pada solusi optimal, dicari

nilai ruas kanan sebagai berikut:

2

15

4

5

2

12

14

1

4

1

11 10

15

20

25

00

00

0

bB .

Jadi solusi optimal untuk persoalan pemotongan balok kayu diberikan

sebagai berikut:

215

dan 10,45

831 xxx .

Untuk mendapatkan suatu solusi fisibel bilangan bulat maka dilakukan dengan

cara pembulatan ke atas nilai-nilai 81 dan xx , sehingga akan menghasilkan solusi

bilangan bulat 8dan 10,2 831 xxx .

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

meter. 140

)8(7)10(7)2(7

777

)(7

831

831

xxx

xxx

Sisa pemotongan: meter 14,5meter5,125meter 1405,125777 831 xxx .

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 jc adalah koefisien biaya kolom ke-j

,...,,2,1 nj ijy adalah koefisien kolom ke-j pada baris ke-i untuk

mi ...,,2,1 , dan id adalah harga dual baris ke-i. Selanjutnya dibentuk kolom

j yang baru sedemikian sehingga

0...2211 mjmjjj ydydydc .

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 jy

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 , nj yyy ...,,,P 21

merupakan suatu pola dengan

elemen jy di dalamnya, nj ...,,2,1 . Selanjutnya yang diminimumkan adalah

total balok kayu panjang 7 meter yang akan dipotong.

Dengan memperhatikan Tabel 3.3, maka 4P1

untuk panjang 1,5 meter, 3P2

untuk panjang 2 meter dan 2P3

untuk panjang 3 meter.

Dengan menggunakan LINDO, formulasi program linearnya adalah:

MIN P1+P2+P3

SUBJECT TO

2) 4P1>=25 3) 3P2>=20 (3.13) 4) 2P3>=15

END Tampilan solusinya adalah :

OBJECTIVE FUNCTION VALUE

1) 20.41667

VARIABLE VALUE REDUCED COST

P1 6.250000 0.000000 P2 6.666667 0.000000 P3 7.500000 0.000000

101

ROW SLACK OR SURPLUS DUAL PRICES

2) 0.000000 -0.250000 3) 0.000000 -0.333333 4) 0.000000 -0.500000

Pola baru yang akan ditambahkan dicari dengan menyelesaikan persoalan

knapsack, dengan memperhatikan nilai dual pada output, diperoleh

Meminimumkan 1P5,00.333333PP25,0))P,P,P(( 321321w

terhadap kendala: 7P3P2P 1,5 321 , (3.14)

bulatbilangan dan 0P,P,P 321

Berdasarkan (Sifat 2.1) maka (3.14) dapat dituliskan sebagai

Memaksimumkan 1P5,00.333333PP25,0)P,P,P( 321321w

terhadap kendala: 7P3P2P 1,5 321

(3.15)

bulatbilangan dan 0P,P,P 321

Dengan metode cabang dan batas diperoleh solusi optimal untuk persoalan

knapsack (3.15) adalah 0P,2P,2P 321 . Akan tetapi pada (3.15) nilai fungsi

tujuannya (w) belum nol, sehingga nilai 0P,2P,2P 321

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 4P . Pada LINDO, 4P menjadi kolom baru. Jika kolom

baru ( 4P ) 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 (3.16) 4) 2P3>=15

END

Tampilan solusinya adalah :

OBJECTIVE FUNCTION VALUE

1) 18.75000

VARIABLE VALUE REDUCED COST

P1 1.250000 0.000000 P2 0.000000 0.250000 P3 7.500000 0.000000 P4 10.000000 0.000000

ROW SLACK OR SURPLUS DUAL PRICES

2) 0.000000 -0.250000 3) 0.000000 -0.250000 4) 0.000000 -0.500000

Dari output (3.16), nilai dual ditulis menjadi subpersoalan knapsack

kembali, yaitu 0P,2P,2P 321

Memaksimumkan 1P50,00.25PP25,0)P,P,P( 321321w

terhadap kendala: 7P3P2P 1,5 321 , (3.17)

bulatbilangan dan 0P,P,P 321 .

Dengan metode cabang dan batas, solusi optimal untuk persoalan knapsack (3.17)

adalah 0P,2P,2P 321 . Nilai fungsi tujuannya adalah nol )0(w , 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 meter.5L

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

(j)

Jumlah panjang 1,5

meter

(batang)

Jumlah panjang 2

meter

(batang)

Jumlah panjang 3 meter

(batang)

Sisa

(meter)

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 54321621 )...,,,( xxxxxxxxz

terhadap kendala :

bulat.bilangan dan 5,...,2,1;0

18

222

3523

43

542

321

jx

xx

xxx

xxx

j

(3.18)

105

Dari bentuk umum persoalan program linear meminimumkan diperoleh

bahwa 1x hanya terjadi dalam kendala 1,5 meter (karena pola 1 hanya

menghasilkan balok kayu 1,5 meter), 5x hanya terjadi dalam kendala 2 meter

(karena pola 5 hanya menghasilkan balok kayu 2 meter). Ini berarti 51 dan , xx

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 6x untuk jumlah

balok kayu yang dipotong sesuai pola 6, sehingga pada (3.18) menjadi:

Meminimumkan 654321621 )...,,,( xxxxxxxxxz

terhadap kendala :

bulat.bilangan dan 6,...,2,1;0

18

222

3523

643

542

321

jx

xxx

xxx

xxx

j

(3.19)

Dengan menambahkan variabel surplus ke dalam kendala pada (3.19) diperoleh

bentuk program linear kanonik, yaitu:

Meminimumkan itxxxxxxz 0654321

terhadap kendala :

bulat.bilangan dan )6,...,2,1(;0);6,...,2,1(;0

18

222

3523

3643

2542

1321

ixjx

txxx

txxx

txxx

ij

3.20)

106

Dari persamaan bentuk kanonik diperoleh 651 ,,VB xxx

dan

432 ,,VNB xxx .

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 jy

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 , nj yyy ...,,,P 21

merupakan suatu pola dengan elemen jy di

dalamnya, nj ...,,2,1 . Selanjutnya yang diminimumkan adalah total balok kayu

panjang 5 meter yang akan dipotong.

Dari Tabel 3.4, maka 3P1

untuk panjang 1,5 meter, 2P2

untuk panjang 2

meter dan 1P3

untuk panjang 3 meter.

Dengan menggunakan LINDO, formulasi program linearnya adalah:

MIN P1+P2+P3

SUBJECT TO 2)3P1>=35 3) 2P2>=22 (3.21) 4) 1P3>=18

END

107

Tampilan solusinya adalah

OBJECTIVE FUNCTION VALUE 1) 40.66667

VARIABLE VALUE REDUCED COST P1 11.666667 0.000000 P2 11.000000 0.000000 P3 18.000000 0.000000

ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 -0.333333 3) 0.000000 -0.500000 4) 0.000000 -1.000000

Pola baru yang akan ditambahkan dicari dengan menyelesaikan persoalan

knapsack, dengan memperhatikan nilai dual pada output, diperoleh

Meminimumkan 1P0.5PP333333,0))P,P,P(( 321321w

terhadap kendala: 5P3P2P 1,5 321 , (3.22)

bulat.bilangan dan 0P,P,P 321

Berdasarkan (Sifat 2.1) maka (3.22) dapat dituliskan sebagai

Memaksimumkan 1PP5,00.333333P)P,P,P( 321321w

terhadap kendala: 5P3P2P 1,5 321

(3.23)

bulat.bilangan dan 0P,P,P 321

Dengan metode cabang dan batas diperoleh solusi optimal untuk persoalan

knapsack (3.23) adalah 1P,1P,0P 321 . Akan tetapi nilai fungsi tujuannya

(w) belum nol yaitu 21

w , sehingga nilai 1P,1P,0P 321

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

21

44 cz dan dengan memasukkan 4x ke dalam basis akan mengurangi sisa

pemotongan.

Untuk mengetahui dalam baris mana 4x masuk menjadi basis maka

dibentuk ruas kanan dari tabel bersangkutan dan kolom 4x dari tabel

bersangkutan.

Jika diketahui:

100

00

00

,

100

020

003

2

13

1

100 BB .

Kolom 4x dari tabel bersangkutan:

1

0

1

1

0

100

00

00

1

1

0

2

1

2

13

1

10B .

Ruas kanan tabel bersangkutan:

18

11

18

22

35

100

00

003

35

2

13

1

10 bB ,

Selanjutnya digunakan test rasio, yaitu: 18,22

21

,efinisitidak terd335

11811

0.

Dari test rasio, rasio terkecil yaitu pada baris ke-3, sehingga 4x masuk basis pada

baris ke-3. Sehingga diperoleh variabel basis yang baru 451 ,,VB(1) xxx .

Untuk menentukan pola yang akan masuk basis digunakan teknik

pembangkit kolom. Dengan menggunakan LINDO, misal pola baru dinamakan

109

.P4 Pada LINDO 4P menjadi kolom baru. Jika kolom baru ( 4P ) ditambahkan ke

dalam formulasi program linear (3.21) formulasinya menjadi:

MIN P1+P2+P3+P4

SUBJECT TO

2) 3P1>=35 3) 2P2+1P4>=22 (3.24) 4) 1P3+1P4>=18

END

Tampilan solusinya adalah

OBJECTIVE FUNCTION VALUE 1) 31.66667

VARIABLE VALUE REDUCED COST P1 11.666667 0.000000 P2 2.000000 0.000000 P3 0.000000 0.500000 P4 18.000000 0.000000

ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 -0.333333 3) 0.000000 -0.500000 4) 0.000000 -0.500000

Dari output (3.24), nilai dual ditulis menjadi subpersoalan knapsack

kembali, yaitu:

Memaksimumkan 1P5,00.5PP333333,0)P,P,P( 321321w

terhadap kendala: 5P3P2P 1,5 321 , (3.25)

bulatbilangan dan 0P,P,P 321 .

Dengan metode cabang dan batas, solusi optimal untuk persoalan knapsack (3.25)

adalah 1P,1P,0P 321 . Nilai fungsi tujuannya adalah nol )0(w , 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 18,2,12 451 xxx . 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):

meter. 160

)2(5)18(5)12(5

555

)(5

451

451

xxx

xxx

Sisa pemotongan: meter 9,5meter5,150meter 1605,150555 451 xxx .

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 meter.8L

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

(j)

Jumlah panjang

1,5 meter

(batang)

Jumlah panjang

2 meter

(batang)

Jumlah panjang

2,5 meter

(batang)

Jumlah panjang

3,5 meter

(batang)

Sisa

(meter)

1 5 0 0 0 0,5

2 4 1 0 0 0 3 3 0 1 0 1 4 3 0 0 1 0

5 2 1 1 0 0,5 6 2 2 0 0 1 7 2 0 2 0 1 8 1 3 0 0 0,5 9 1 2 1 0 0

10 1 1 0 1 1 11 0 4 0 0 0 12 0 2 0 1 0,5 13 0 1 2 0 1 14 0 1 1 1 0 15 0 0 3 0 0,5 16 0 0 0 2 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 5P1

untuk panjang 1,5 meter, 4P2

untuk panjang 2 meter, 3P3

untuk panjang 3 meter dan 2P4

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 (3.26) 4) 3P3>=32 5) 2P4>=17

END

Tampilan solusinya adalah

OBJECTIVE FUNCTION VALUE 1) 40.16667

VARIABLE VALUE REDUCED COST P1 11.000000 0.000000 P2 10.000000 0.000000 P3 10.666667 0.000000 P4 8.500000 0.000000

ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 -0.200000 3) 0.000000 -0.250000 4) 0.000000 -0.333333 5) 0.000000 -0.500000

Pola baru yang akan ditambahkan dicari dengan menyelesaikan persoalan

knapsack, dengan memperhatikan nilai dual pada output, diperoleh:

Memaksimumkan 1P5,00,333333PP25,0P2,0)P,P,P,P( 43214321w

terhadap kendala: 8P5,3P3P2P 1,5 4321

(3.27)

bulatbilangan dan 0P,P,P,P 4321

Dengan metode cabang dan batas diperoleh solusi optimal untuk persoalan

knapsack (3.27) yaitu 0P,0P,4P,0P 4321 . Nilai fungsi tujuannya adalah

nol )0(w , 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 11,10,11 15111 xxx dan

916x . 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):

meter. 328

)9(8)11(8)10(8)11(8

8888

)(8

1615111

1615111

xxxx

xxxx

Sisa pemotongan: meter3188888 1615111 xxxx

meter.10

meter318meter328

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:

1x Industri Adiprima Suraprinta; 2x Industri Kali Tengah; 3x Industri

Suparma; 4x Industri Sidomakmur; 5x Industri Gawerejo; 6x Industri

RPH; 7x Industri Tahu Purnomo; 8x Industri Tahu Gunungsari; 9x Industri

Tahu Halim.

Formulasi program linearnya adalah

116

Memaksimumkan 987654321 xxxxxxxxxy

terhadap kendala:

1,190

1627

25

8,19

6,5

7,5

6,774

7638

5,2436

150556,5

150429,0

100953,16

100746,65

5061,16

15010

100156,0

100029,0

100083,0

600041,000041,000041,000041,0

0004,00004,00004,00004,000038,0225,5

600042,000042,000042,000042,0

00041,000041,000041,000041,000039,0334,5

600042,000042,000042,0

00041,000041,000041,000041,000039,0344,5

600042,000042,0

00041,000041,000041,000041,000039,0357,5

600042,0

00042,000041,000041,000041,000039,0378,5

600042,000042,000042,000041,00004,0416,5

600042,000042,000041,00004,0426,5

600042,000041,00004,0445,5

600042,00004,0485,5

600043,0822,5

9

8

7

6

5

4

3

2

1

8

8

7

6

5

4

3

2

1

9876

54321

9876

54321

876

54321

76

54321

6

54321

54321

4321

321

21

1

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

xxxx

xxxxx

xxxx

xxxxx

xxx

xxxxx

xx

xxxxx

x

xxxxx

xxxxx

xxxx

xxx

xx

x

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

miKi ...,,2,1,

dengan pola njj ...,,2,1, . Pemotongan ini akan

menghasilkan potongan balok kayu sebanyak

....,,2,1;...,,2,1, njmiaij

2) Mengkombinasikan njmiaij ...,,2,1;...,,2,1,

sesuai dengan

panjang pesanan miKi ...,,2,1, , dengan syarat sisa pemotongan

kurang dari miKi ...,,2,1, , untuk iK 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 langkah-

langkah sebagai berikut:

1) Perumusan persoalan program linear bentuk meminimumkan.

2) Merubah persoalan program linear meminimumkan ke bentuk program

linear kanonik.

121

3) Menghitung 1VB

1 dan BcB dalam tabel bersangkutan.

4) Menghitung harga akhir pola untuk setiap jy .

5) Mencari harga akhir pola yang efisien, diperoleh dengan

menyelesaikan persoalan knapsack:

Memaksimumkan 1)(1

j

n

jjj yyw

terhadap kendala:

....,,2,1,...,,2,1

bulat,bilangan dan 0

,1

minj

y

LyK

j

j

n

ji

6) Hasil perhitungan persoalan knapsack menggunakan metode cabang

dan batas akan memberikan solusi optimal untuk program linear, hasil

ini akan berkorespondensi dengan njy j ...,,2,1,

ke pola

njj ...,,2,1,

dan variabel kx .

7) Dari langkah (6) dapat diperoleh variabel nonbasis yang akan menjadi

variabel basis, diperoleh dengan cara menghitung jy1B dan B-1b

kemudian digunakan test rasio untuk menentukan dalam baris mana

kx masuk sebagai variabel basis.

8) Teknik pembangkit kolom akan menghasilkan solusi optimal jika

penyelesaian persoalan knapsack dengan metode cabang dan batas

menghasilkan fungsi tujuan 0w 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 jc adalah koefisien biaya kolom ke-j

,...,,2,1 nj ijy adalah koefisien kolom ke-j pada baris ke-i untuk

mi ...,,2,1 , dan id adalah harga dual baris ke-i. Selanjutnya dibentuk

kolom j yang baru sedemikian sehingga

0...2211 mjmjjj ydydydc (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. Topik-

topik 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 Cutting-Stock 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.