BAB VIProgram Linear Bilangan Bulat

Permasalahan program linear bilangan bulat muncul ketika kita harus memutuskan jumlah

barang yang kita perlukan berbentuk bilangan bulat, seperti menentukan banyaknya mesin

untuk suatu pabrik, banyaknya foto copy untuk layanan di suatu kantor, banyaknya

komputer di suatu ruangan untuk mengerjakan sejumlah pekerjaan, banyaknya orang yang

mengerjakan suatu proyek, dan sebagainya. Tidaklah mungkin banyaknya mesin giling

padi di suatu pabrik 2,38 buah untuk menggiling padi di suatu wilayah tertentu, keputusan

akan menjadi 3 buah, atau 2 buah dengan kerja lembur, dan sebagainya.

Program linear bilangan bulat dikatakan pure integer programming (program linear

bilangan bulat murni) apabila semua variabel adalah bilangan bulat. Ada kalanya sebagian

variabel bukan bilangan bulat, bisa jadi sebagian variabel bilangan real. Bilamana

variabelnya bilangan bulat dan bilangan biner (nol, satu), maka masalah program linear ini

disebut mix integer programming (program linear bilangan bulat campuran) atau program

linear bilangan bulat nol satu (zero one integer programming). Masalah zero one integer programming biasanya digunakan untuk pengambilan keputusan. Bernilai 1 bila harus

melakukan suatu pekerjaan (menerima keputusan) dan bernilai 0 berarti harus menolak

suatu pekerjaan (keputusan).

Untuk lebih jelasnya marilah kita lihat beberapa contoh masalah berikut:

Masalah 1

Maksimumkan

Dengan pembatas:

149

Masalah 2

Minimumkan

Dengan pembatas:

Masalah 3

Maksimumkan

Selanjutnya apabila kita hitung dengan metode simpleks dengan bilangan real,

maka kita peroleh:

Masalah 1 Masalah 2 Masalah 3

Misalnya kita diminta untuk menjawab dengan bilangan bulat, kemudian kita bulatkan

begitu saja, misalnya menjadi:

Masalah 1 Masalah 2 Masalah 3

Pembulatan yang dilakukan begitu saja, akan mengakibatkan solusi tidak optimal, bahkan

dapat menghasilkan jawaban yang tak layak (tidak masuk dalam jawaban yang mungkin).

Oleh karena itu pembulatan pada program linear bilangan bulat tidak sesederhana

membulatkan menjadi bilangan bulat. Sebab beberapa persyaratan mesti dipenuhi.

150

Pada masalah diatas bila kita lakukan dengan program linear bilangan bulat akan

menghasilkan jawaban:

Masalah 1 Masalah 2 Masalah 3

Bagaimana cara menentukan solusi program linear bilangan bulat?

Ada beberapa cara untuk menentukan (menghitung) solusi program linear bilangan bulat,

antara lain: metode grafik, metode cutting plan algorithm, metode branch and bound, dan

penyelesaian dengan program komputer. Pada kajian di sini hanya akan dibahas dua cara

yaitu metode branch and bound, dan penyelesaian dengan program komputer.

1. Metode Branch and BoundMetode branch and bound mempunyai beberapa langkah:

1. Selesaikan masalah program linear dengan metode biasa (simpleks) yaitu dengan

bilangan real (biasa).

2. Teliti solusi optimumnya. Apabila variabel basis yang diharapkan berbentuk

bilangan bulat, maka pekerjaan telah selesai. Solusi itu adalah solusi optimum.

Tetapi bila solusinya bukan bilangan bulat, maka lakukan langkah selanjutnya.

3. Nilai solusi yang tidak bulat yang layak dicabangkan ke dalam sub-sub masalah,

dengan tujuan untuk menghilangkan solusi yang tidak memenuhi persyaratan

bilangan bulat. Pencabangan ini dilakukan dengan kendala-kendala mutually exclusive yang perlu untuk memenuhi persyaratan bulat.

4. Untuk setiap sub masalah, nilai solusi optimum kontinu (tak bulat) fungsi tujuan

dijadikan sebagai batas atas. Solusi bulat terbaik menjadi batas bawah (pada

awalnya ini adalah solusi kontinu yang dibulatkan kebawah). Sub-sub masalah

yang mempunyai batas atas kurang dari batas bawah yang ada tidak diikut

sertakan dalam analisis selanjutnya. Suatu solusi bulat, layak adalah sama baik

atau lebih baik dari batas atas untuk semua sub masalah yang dicari. Jika solusi

151

demikian ada, suatu sub masalah dengan batas atas terbaik dipilih untuk

dicabangkan, kemudian kembali ke langkah 3.

Untuk melihat lebih jelas, kita perhatikan contoh berikut:

Maksimumkan

Dengan pembatas:

Dengan metode simpleks biasa atau metode grafik, maka diperoleh.

Masalah diatas dicabang menjadi 3 bagian yaitu:

Bagian 1. Bagian 2. Bagian 3.

152

Nampak disamping bahwa semua solusi bilangan pecah (tidak

bulat) maka harus kita lakukan pencabangan.

Perhatikan grafik berikut.

Bagian 1

Pada bagian 1 memberikan batas bawah (7,6) dengan Z = 150 7 + 175 6 = 2100

Bagian 2

Pada bagian 2 memberikan batas atas (8,5) dengan Z = 1508 + 1755=2075 (dibawah batas bawah).

Bagian 3

153

Pada bagian 3 memberikan batas atas (7,7) dan (0,12) yang memberikan nilai

Dari perhitungan diatas, terlihat bahwa nilai maksimum tercapai pada titik (7,7) dengan

nilai Z = 2170.

Jadi solusi program linear bilangan bulat diatas adalah

.

2. Penyelesaian Program Linear Bilangan Bulat dengan Program LindoUntuk menyelesaikan masalah diatas dengan komputer, dalam hal ini kita

gunakan program lindo, maka masalah tersebut kita tuliskan pada papan lindo sebagai

berikut:

Apabila masalah program linear yang tidak harus bilangan bulat kita tuliskan dengan,Max 150x1+175x2Subject to 6x1+8x2<=99 8x1+4x2<=87End

Sedangkan untuk masalah program linear bilangan bulat, kita tambahkan gin x1 dan gin x2

untuk memberitahu bahwa x1 adalah bilangan bulat, dan x2 juga bilangan bulat. Atau

langsung ditulis dengan gin 2. Sehingga program menjadi:Max 150x1+175x2Subject to 6x1 + 8x2 <= 99 8x1 + 4x2 <= 87EndGin x1Gin x2

atau cukup ditulis denganmax 150x1+175x2subject to6x1+8x2<=998x1+4x2<=87endgin 2

Maka setelah program Lindo dijalankan akan diperoleh hasil keluaran seperti berikut:

154

LP OPTIMUM FOUND AT STEP 0 OBJECTIVE VALUE = 2306.25000

NEW INTEGER SOLUTION OF 2275.00000 AT BRANCH 0 PIVOT 2BOUND ON OPTIMUM: 2275.000ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 2

LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION...

OBJECTIVE FUNCTION VALUE 1) 2275.000

VARIABLE VALUE REDUCED COST X1 7.000000 -150.000000 X2 7.000000 -175.000000

ROW SLACK OR SURPLUS DUAL PRICES 2) 1.000000 0.000000 3) 3.000000 0.000000

NO. ITERATIONS= 2 BRANCHES= 0 DETERM.= 1.000E 0

Dari hasil diatas dapat dilihat bahwa, solusi tercapai dengan Z = 2.275, dengan X1 = 7,

dan X2 = 7.

3. Penyelesaian Program Linear Bilangan Bulat dengan Program SolverUntuk menyelesaikan Masalah program linear bilangan bulat Dengan solver prinsipnya

sama dengan penyelesaian program linear, hanya ditambah syarat (constrain) yaitu sel

banyaknya barang adalah bilangan bulat (integer), maka program awal yang kita isikan ke

dalam Excel adalah sebagai berikut.

155

Program awal pada lembar kerja Excel.

Setelah menjalankan Solver dengan mengisi Parameter Solver berikut.

Maka akan diperoleh hasil berikut ini.

156

Tabel Kebutuhan Bahan

Barang (Variabel)

PembatasBarang 1 Barang 2

Bahan 1 6 8 99

Bahan 2 8 4 87

Koef. fungsi

Tujuan 150 175

Banyaknya 7 7

Bahan yang dipakai

Barang

Barang 1 Barang 2 Dipakai

Bahan 1 42 56 98

Bahan 2 56 28 84

Fungsi Tujuan 2275

Hasil di atas menunjukkan bahwa Z optimal terjadi pada x1 = 7, dan x2 = 7 dengan Z =

2275.

Pengerjaan dengan program Lingo diserahkan kepada pembaca.

Pengerjaan dengan cara konvensional memerlukan waktu yang cukup lama dan cukup

sukar, apalagi apabila banyaknya variabel banyak. Sebagai contoh perhatikan masalah

berikut.

Sebuah Home Industri “Dynamics Bag Collection” membuat lima macam barang, yaitu Tas

Remaja, Tas Ibu-ibu, Tas Sekolah, Dompet Wanita, dan Dompet Pria. Kebutuhan bahan,

harga bahan, harga jual, biaya tenaga setiap harinya adalah sebagai berikut:

Tabel Kebutuhan Bahan, Persediaan bahan dan Harga Barang

157

Bahan - bahan

Tas Remaja

Tas Ibu-ibu

Tas Sekolah

Dompet Wanita

Dompet Pria Persediaan

Imitasi 4 m 5 m 6 m 1 m 1 m 65 m

Benang 2 rol 3 rol 3 rol 1 rol 1 rol 25 rol

Resliting 2,5 m 3,6 m 2,8 m 0,5 m 0,25 m 90 m

Lem Latex 0,75 kg 0,5 kg 0 0,25 kg 0,25 kg 7 kg

Lem PC 0,25 kg 0,2 kg 0 0,2 kg 0,2 kg 3 kg

Furing 2,5 m 7 m 0 1,25 m 1 m 34 m

Asesoris 36 buah 24 buah 0 10 buah 0 198 buah

Karton 5 lbr 1 lbr 0 0 0 20 lembar

Busa 3 m 5 m 0 0 0 30 m

Harga jual (rupiah) 276.000 300.000 276.000 144.000 123.000

.Pengerjaan secara konvensional hampir tidak mungkin dilakukan, karena menyangkut

lima buah variabel.

Masalah ini apabila dikerjakan dengan Solver, maka akan diperoleh hasil berikut.

Bahan keperluan

Bahan -

bahan

Tas

Remaja Tas Ibu-ibu

Tas

Sekolah

Dompet

Wanita

Dompet

Pria Persediaan

Imitasi 4 5 6 1 1 65

Benang 2 3 3 1 1 25

Resliting 2.5 3.6 2.8 0.5 0.25 90

Lem Latex 0.75 0.5 0 0.25 0.25 7

Lem PC 0.25 0.2 0 0.2 0.2 3

Furing 2.5 7 0 1.25 1 34

Asesoris 36 24 0 10 0 198

Karton 5 1 0 0 0 20

Busa 3 5 0 0 0 30

Harga jual 276 300 276 144 123

158

(rupiah)

Banyakny

a

2 0 3 12 0

Bahan yang terpakai

Bahan -

bahan

Tas

Remaja

Tas

Ibu-ibu

Tas

Sekolah

Dompet

Wanita

Dompet

Pria Digunakan

Sisa

bahan

Imitasi 8 0 18 12 0 38 27

Benang 4 0 9 12 0 25 0

Resliting 5 0 8.4 6 0 19.4 70.6

Lem Latex 1.5 0 0 3 0 4.5 2.5

Lem PC 0.5 0 0 2.4 0 2.9 0.1

Furing 5 0 0 15 0 20 14

Asesoris 72 0 0 120 0 192 6

Karton 10 0 0 0 0 10 10

Busa 6 0 0 0 0 6 24

Penghasilan kotor 3108

Hasil ini menunjukkan bahwa Home Industri tersebut harus membuat 2 tas remaja, 3 tas

sekolah, dan 12 dompet wanita. Dengan pendapatan kotor Rp 3.108.000,-.

Apabila kita cermati hasil di atas, khususnya bahan yang tersisa, maka kekurangan bahan

yang menonjol adalah benang dan Lem PC yang kedua bahan tersebut harganya murah

dan mudah di dapat. Oleh karena itu ada baiknya persediaan kedua bahan tersebut

ditambah.

Misalkan benang kita tambah menjadi 50 dan Lem PC kita tambah menjadi 7, maka

apabila kita selesaikan akan menghasilkan pendapatan yang cukup melonjak.

159

Bahan keperluan

Bahan -

bahan

Tas

Remaja

Tas

Ibu-

ibu

Tas

Sekolah

Dompet

Wanita

Dompet

Pria Persediaan

Imitasi 4 5 6 1 1 65

Benang 2 3 3 1 1 50

Resliting 2.5 3.6 2.8 0.5 0.25 90

Lem Latex 0.75 0.5 0 0.25 0.25 7

Lem PC 0.25 0.2 0 0.2 0.2 7

Furing 2.5 7 0 1.25 1 34

Asesoris 36 24 0 10 0 198

Karton 5 1 0 0 0 20

Busa 3 5 0 0 0 30

Harga jual

(rupiah) 276 300 276 144 123

Banyakny

a

0 0 6 19 9

160

Bahan yang terpakai

Bahan -

bahan

Tas

Remaja

Tas

Ibu-

ibu

Tas

Sekolah

Dompet

Wanita

Dompet

Pria

Digunaka

n

Sisa

bahan

Imitasi 0 0 36 19 9 64 1

Benang 0 0 18 19 9 46 4

Resliting 0 0 17 10 2 29 61

Lem

Latex

0 0 0 5 2 7 0

Lem PC 0 0 0 4 2 6 1

Furing 0 0 0 24 9 33 1

Asesoris 0 0 0 190 0 190 8

Karton 0 0 0 0 0 0 20

Busa 0 0 0 0 0 0 30

Penghasilan kotor 5499

Kita perhatikan pendapatan menjadi Rp 5.499.000,--. Yaitu dengan membuat 9 tas

sekolah, 19 dompet wanita, dan 9 dompet pria. Sebuah kenaikan penghasilan yang luar

biasa.

Bagaimana kalau Home Industri tersebut sekurang-kurangnya membuat 2 tas wanita dan

3 tas ibu-ibu?

Untuk menyelesaikan masalah ini, cukup menambah pada constrais sel tas remaja >= 2

dan sel tas ibu-ibu >= 3 seperti berikut.

161

Dari Parameter di atas, maka akan diperoleh hasil sebagai berikut.

162

Hasil terakhir menyarankan untuk membuat 2 tas ramaja, 3 tas ibu-ibu, 6 tas sekolah, 4

dompet wanita, dan 2 dompet pria, dengan penghasilan kotor Rp 3.930.000,--.

Penyelesaian masalah dengan Lindo maupun Lingo diserahkan kepada pembaca sebagai

latihan.

Soal-soal1. Seorang Pasien di rumah sakit setiap harinya memerlukan tiga macam zat, sebut

saja zat A, zat B, dan zat C, berturut-turut paling sedikit sebanyak 16 satuan, 18

satuan, dan 17 satuan. Zat-zat tersebut terdapat dalam tiga macam obat yaitu obat P,

obat Q, dan obat R. Setiap obat P mengandung 2 zat A, 1 zat B, dan 2 zat C. Setiap

obat Q mengandung 4 zat A, 1 zat B, dan 1 zat C. Dan setiap obat R mengandung 1

zat A, 3 zat B, dan 2 zat C. Harga obat P, obat Q, dan obat R berturut-turut Rp 1000,

Rp 1500, dan Rp 1250.

Tentukan banyaknya masing-masing obat untuk memenuhi kebutuhan pasien tersebut

agar dicapai biaya minimum.

2. Perusahaan mobil akan mengeksport 400 mobil model A, dan 500 mobil model B.

Mobil model A memerlukan tempat 12 m3 dan mobil model B memerlukan tempat 15

m3. Pada jadwal pelayaran terdapat tiga pengangkutan yaitu pada awal bulan Januari,

pertengahan bulan Februari dan akhir bulan Maret. Ada pengangkutan pertama hanya

membuat mobil model A dengan biaya Rp 450.000,- tiap-tiap mobil. Pada

pengangkutan mobil yang kedua dan ketiga membawa kedua model tersebut dengan

biaya angkut berturut-turut Rp 35.000,- dan Rp 40.000,- tiap meter kubik. Kapasitas

kapal pertama hanya 200 mobil. Pengangkitan kedua dan ketiga berturut-turut

sebesar 4500 dan 6000 meter kubik. Pada pertengahan Februari harus terkirim

sekurang-kurangnya 250 mobil model A, dan 300 mobil model B. Buatlah model

pengangkutan agar diperoleh biaya transportasi minimal.

3. Rapi Alumunium adalah pengusaha kecil yang membuat beberapa barang yang

berbasis alumunium. Kebutuhan bahan dan persediaan, serta harga jual terlihat pada

tabel berikut ini:

163

Jenis barang

dan bahan

Meja

Setrika

Jemuran

handuk

sayap

Jemuran

handuk

engkel

Rak

Piring

Jemuran

PakaianPersediaan

Alumunium □

1” x 1”650 cm 1780 cm 1386 cm 24000 cm

Alumunium □

1” x ½ ”234 cm 12000 cm

Alumunium □

3/4” x 3/4”80 cm 756 cm 654 cm 36000 cm

Alumunium ○

3/8”75 cm 639 cm 60000 cm

Alumunium ○

3/4”27 cm 570 cm 298 cm 2540 cm 60000 cm

Alumunium ○

5/8”2214 cm 60000 cm

Alumunium

Lis M 3/4”360 cm 640 cm 400 cm 30000 cm

Alumunium

Lis M 1”660 cm 640 cm 30000 cm

Karet Plane 360 cm 640 cm 400 cm 660 cm 640 cm 70000 cm

Karet Sepatu

25 x 254 bh 4 bh 4 bh 250 bh

Karet Sepatu

O4 bh 4 bh 250 bh

Partikel 2800 cm2 60000 cm2

Busa 2800 cm2 24000 cm2

Kain 2800 cm2 50000 cm2

Tripek

Melamin6000 cm2 60000 cm2

164

Alumunium

Gate Rel20 cm 500 cm

Alumunium

Rel21 cm 600 cm

Alumunium U

3/8”162 cm 3000 cm

Plat

Alumunium90 cm 1000 cm

Spigot 130 cm 3000 cm

Harga satuan

Barang157.000 125.000 100000 315.000 270.000

Tentukan banyaknya masing-masing barang agar diperoleh pendapatan terbesar?.

165