BAB VI Program 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
Masalah 2 Minimumkan Z = 200 x1 + 400 x2
Maksimumkan Z = 100 x1 + 90 x2
Dengan pembatas:
Dengan pembatas:
10 x1 + 25 x2 ≥ 100
10 x1 + 7 x2 ≤ 70
3 x1 + 2 x2 ≥ 12
5 x1 + 10 x2 ≤ 50
x1 ≥ 0, x2 ≥ 0
x1 ≥ 0, x2 ≥ 0
149
150
Masalah 3 Maksimumkan Z = 80 x1 + 100 x2 4 x1 + 2 x 2 ≤ 15 x1 + 5 x 2 ≤ 16 x1 ≥ 0, x 2 ≥ 0
x1 + 5 x 2 ≤ 16
Selanjutnya apabila kita hitung dengan metode simpleks dengan bilangan real, maka kita peroleh: Masalah 1
Masalah 2
Masalah 3
x1 = 5.38
x1 = 1.82
x1 = 2.388889
x2 = 2.31
x2 = 3.27
x 2 = 2.722222
Z = 746.15
Z = 1,672.73
Z = 463.3333
Misalnya kita diminta untuk menjawab dengan bilangan bulat, kemudian kita bulatkan begitu saja, misalnya menjadi: Masalah 1
Masalah 2
Masalah 3
x1 = 5
x1 = 2
x1 = 2
x2 = 2
x2 = 3
x2 = 3
Z = 680
Z = tak layak
Z = tak layak
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.
Pada masalah diatas bila kita lakukan dengan program linear bilangan bulat akan menghasilkan jawaban:
151
Masalah 1
Masalah 2
Masalah 3
x1 = 7
x1 = 3, x2 = 3 atau
x1 = 1
x2 = 0
x1 = 5, x2 = 2
x2 = 3
Z = 700
Z = 1,800
Z = 360
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 Bound Metode 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
152
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 Z = 150 x1 + 175 x2 Dengan pembatas: 6 x1 + 8 x2 ≤ 99 8 x1 + 4 x2 ≤ 87 x1 ≥ 0, x2 ≥ 0 Dengan metode simpleks biasa atau metode grafik, maka diperoleh. x1 = 7.5
Nampak disamping bahwa semua solusi bilangan pecah (tidak
x2 = 6.75
bulat) maka harus kita lakukan pencabangan.
Z = 2205
Perhatikan grafik berikut.
Masalah diatas dicabang menjadi 3 bagian yaitu: Bagian 1.
Bagian 2.
Bagian 3.
x1 ≤ 7
x1 ≥ 8, x 2 ≥ 0
x1 ≥ 0, x 2 ≥ 7
x2 ≤ 6
8 x1 + 4 x 2 ≤ 87
6 x1 + 8 x 2 ≤ 99
x1 ≥ 0, x2 ≥ 0
153
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 = 150•8 + 175•5=2075 (dibawah batas bawah).
Bagian 3
154
Pada bagian 3 memberikan batas atas (7,7) dan (0,12) yang memberikan nilai
Z1 = 150 . 7 + 175 . 7 = 2170, Z 2 = 150 . 0 + 175 . 12 = 2100 Dari perhitungan diatas, terlihat bahwa nilai maksimum tercapai pada titik (7,7) dengan nilai Z = 2170. Jadi
solusi
program
linear
bilangan
bulat
diatas
adalah
x1 = 7, x 2 = 7, dengan Z = 2.170 .
2. Penyelesaian Program Linear Bilangan Bulat dengan Program Lindo Untuk 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+175x2 Subject to 6x1+8x2<=99 8x1+4x2<=87 End
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+175x2 Subject to 6x1 + 8x2 <= 99 8x1 + 4x2 <= 87 End Gin x1 Gin x2
atau cukup ditulis dengan max 150x1+175x2 subject to 6x1+8x2<=99 8x1+4x2<=87 end gin 2
155
Maka setelah program Lindo dijalankan akan diperoleh hasil keluaran seperti berikut: LP OPTIMUM FOUND AT STEP 0 OBJECTIVE VALUE = 2306.25000 NEW INTEGER SOLUTION OF 2275.00000 AT BRANCH 2 BOUND ON OPTIMUM: 2275.000 ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 2
0 PIVOT
LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION... OBJECTIVE FUNCTION VALUE 1) 2275.000 VARIABLE X1 X2
ROW 2) 3)
VALUE 7.000000 7.000000
SLACK OR SURPLUS 1.000000 3.000000
NO. ITERATIONS= 2 BRANCHES= 0 DETERM.=
1.000E
REDUCED COST -150.000000 -175.000000
DUAL PRICES 0.000000 0.000000
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 Solver Untuk 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.
156
Program awal pada lembar kerja Excel. Setelah menjalankan Solver dengan mengisi Parameter Solver berikut.
Maka akan diperoleh hasil berikut ini.
157
Tabel Kebutuhan Bahan Barang (Variabel) Barang 1
Barang 2
Pembatas
Bahan 1
6
8
99
Bahan 2
8
4
87
150
175
7
7
Koef. fungsi Tujuan Banyaknya
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:
158
Tabel Kebutuhan Bahan, Persediaan bahan dan Harga Barang Bahan bahan
Tas Remaja
Tas Ibuibu
Tas Sekolah
Imitasi
4m
5m
6m
1m
1m
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
2,5 m
7m
0
1,25 m
1m
34 m
36 buah
24 buah
0
10 buah
0
198 buah
Karton
5 lbr
1 lbr
0
0
0
20 lembar
Busa
3m
5m
0
0
0
30 m
Furing Asesoris
Dompet Wanita
Dompet Pria
Persediaan
Harga jual 276.000 300.000 276.000 144.000 123.000 (rupiah) .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
Tas
Dompet Dompet
Remaja Tas Ibu-ibu Sekolah
Wanita
Pria
Persediaan
Imitasi
4
5
6
1
1
65
Benang
2
3
3
1
1
25
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
Resliting
159
Karton
5
1
0
0
0
20
Busa
3
5
0
0
0
30
276
300
276
144
123
2
0
3
12
0
Harga jual (rupiah) Banyaknya
Bahan yang terpakai
Bahan -
Tas
Tas
Tas
Dompet Dompet
bahan
Remaja
Ibu-ibu
Sekolah
Wanita
Pria
Sisa Digunakan
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
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
Furing
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.
160
Misalkan benang kita tambah menjadi 50 dan Lem PC kita tambah menjadi 7, maka apabila kita selesaikan akan menghasilkan pendapatan yang cukup melonjak.
Bahan keperluan Tas Bahan -
Tas
Ibu-
Tas
Dompet Dompet
bahan
Remaja
ibu
Sekolah
Wanita
Pria
Persediaan
Imitasi
4
5
6
1
1
65
Benang
2
3
3
1
1
50
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
276
300
276
144
123
0
0
6
19
9
Resliting
Harga jual (rupiah) Banyaknya
161
Bahan yang terpakai
Tas Bahan -
Tas
Ibu-
Tas
Dompet Dompet
bahan
Remaja
ibu
Sekolah
Wanita
Pria
Sisa Digunakan 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
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
Latex
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.
162
Dari Parameter di atas, maka akan diperoleh hasil sebagai berikut.
163
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-soal 1. 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.
164
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: Jenis barang
Meja
dan bahan
Setrika
Alumunium □ 1” x 1”
Jemuran
Jemuran
handuk
handuk
sayap
engkel
650 cm
Alumunium □
3/4” x 3/4” Alumunium ○ 3/8” Alumunium ○ 3/4”
80 cm
756 cm
75 cm
27 cm
570 cm
25 x 25
360 cm
360 cm
640 cm
640 cm
400 cm
4 bh
O 2800 cm2
4 bh
Persediaan
24000 cm
12000 cm
36000 cm
60000 cm
2540 cm
60000 cm
60000 cm
400 cm
4 bh
Karet Sepatu
Partikel
1386 cm
2214 cm
Lis M 1”
Karet Sepatu
1780 cm
298 cm
Alumunium
Karet Plane
Pakaian
639 cm
5/8”
Lis M 3/4”
Piring
654 cm
Alumunium ○
Alumunium
Jemuran
234 cm
1” x ½ ” Alumunium □
Rak
30000 cm
660 cm
640 cm
30000 cm
660 cm
640 cm
70000 cm
4 bh
4 bh
250 bh
250 bh 60000 cm2
165
Busa Kain Tripek Melamin
2800 cm2
24000 cm2
2800 cm2
50000 cm2
6000 cm2
60000 cm2
Alumunium
20 cm
Gate Rel Alumunium Rel
21 cm
600 cm
Alumunium U
162 cm
3/8” Plat Alumunium Spigot Harga satuan Barang
500 cm
157.000
125.000
100000
315.000
3000 cm
90 cm
1000 cm
130 cm
3000 cm
270.000
Tentukan banyaknya masing-masing barang agar diperoleh pendapatan terbesar?.
