arisgunaryati.files.wordpress.com · web viewoleh karena itu pembulatan pada program linear...
TRANSCRIPT
PROGRAM LINEAR BILANGAN BULAT
3 EA 11
Di Susun Oleh :
Amelia ( 15209886 )
Chandra Kurniawan ( 12209771 )
Desti dirnaeni ( 12209257 )
Irma yulia Dewi ( 11209622 )
Irwo Sasongko ( 16209467 )
M. Ridwan Setyawan ( 10209964 )
Tedy Gustaman ( 11209117 )
Yuanita Anggreini ( 14209375 )
UNIVERSITAS GUNADARMA2012
1
Program Linear Bilangan BulatProgram Linear Bilangan Bulat
Permasalahan program linear bilangan bulat muncul ketika kita harus
memutuskan masalah 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:
2
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 :
3
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 demikian ada, suatu sub masalah dengan
4
batas atas terbaik dipilih untuk dicabangkan, kemudian kembali ke langkah
3.
Untuk melihat lebih jelas, kita perhatikan contoh berikut:
Maksimumkan 150 X1 + 175 X 2 Z = x + x
Dengan pembatas:
5
6
Pada bagian 3 memberikan batas atas (7,7) dan (0,12) yang memberikan nilai
Z1 =150 7. +175 7. = 2170, Z2 =150 0. +175 12. = 2100
Dari perhitungan diatas, terlihat bahwa nilai maksimum tercapai pada titik (7,7)
dengan
Z = 2170.
Jadi solusi program linear bilangan bulat diatas adalah :
X1 = 7, X2 = 7, nilai Z = 2170
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
6x1+8x2<=99
8x1+4x2<=87
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:
7
Max 150x1+175x
6x1 + 8x2 <= 99
8x1 + 4x2 <= 87
atau cukup ditulis dengan
max 150x1+175x2
6x1+8x2<=99
8x1+4x2<=87
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:
8
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.
9
10
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
11
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 luarbiasa. 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.
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
12
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:
13
Tentukan banyaknya masing-masing barang agar diperoleh pendapatan terbesar?.
14