Program Integer
A. Model Program Linear Pada model program linear sebelumnya sering terjadi solusi yang menghasilkan bilangan pecahan. Misal :23,73 mangkok dan 8,51 cangkir. Pada saat metode simpleks menghasilkan nilai noninteger, kadang diasumsikan bahwa nilai solusi bisa dibulatkan ke nilai terdekat. Misal : x1 = 7000,4 paku dibulatkan menjadi x1 = 7000 paku. Tetapi bila kasus x1 nya adalah kapal selam maka pembulatan mempengaruhi keuntungan bermiliar2 dolar. Pada materi ini dipelajari pendekatan pemecahan yang menghasilkan bilangan integer optimal. Tiga jenis model program linear integer : (1) model total integer, (2) model 0-1 integer, (3) model integer campuran. Pada (1) semua solusi harus menghasilkan nilai integer, pada (2) solusi berupa nilai integer 0 atau 1, pada (3) beberapa nilai peubah keputusan mempunyai nilai integer.
1.
Contoh Model Total Integer
Pemilik toko merencanakan membeli mesin pencetak dan mesin bubut. Pemilik memprediksi setiap mesin pencetak akan menaikan keuntungan sebesar $100 per hari dan mesin bubut menaikan keuntungan $150 per hari. Luas tempat dan harga masing-masing sebagai berikut: Mesin
Luat tempat (ft) Harga Beli ($)
Pencetak
15
8000
Bubut
30
4000
Anggran pembelian mesin adalah $40.000 sedangkan tempat tersedia 200 feet persegi. Pemilik ingin mengetahui berapa banyak mesin yang dapat dibeli supaya keuntungan maksimum. Dalam hal ini tidak diperbolehkan menghasilkan solusi yang pecahan.
Model Linearnya adalah sebagai berikut:
Maksimumkan Z = 100x1 + 150x2 Batasan 8000 x1 + 4000x2 ≤ 40.000 15x1 + 30x2 ≤ 200
x1, x2 ≤ 0 dan integer Diketahui : x1 = jumlah mesin pencetak x2 = jumlah mesin bubut 2. Contoh Model Integer 0 – 1 Bapeda sebuah kota merencanakan untuk membangun fasilitas rekreasi., yaitu : kolam renang, lapangan tenis,
lapangan atletik, dan gelanggang olah raga. Pengguna, biaya dan lahan yang diperlukan disajikan pada tabel berikut :
Tabel data contoh integer 0-1 Fasilitas Rekreasi
Banyaknya Pengguna (orang/ hari)
Biaya ($)
Luas Lahan ( acre)
Kolam renang
300
35.000
4
Lapangan tenis
90
10.000
2
Lapangan atletik
400
25.000
7
Gelanggan Olah Raga
150
90.000
3
Anggaran yang disediakan $120.000 dan luas lahan 12 acre.
Karena ada pada lahan yang sama, lahan kolam renang atau lapangan tenis hanya akan didirikan salahsatu saja. Bapeda ingin mengetahui fasilitas mana saja yang harus didirikan agar pengguna menjadi maksimum.
Formulasi Model PL :
Maksimumkan Z = 300x1 + 90x2 + 400x3 + 150x4 Batasan 35.000x1 + 10.000x2 + 25.000x3 + 90.000x4 ≤120.000 4x1 + 2x2 + 7x3 + 3x4 ≤ 12 x1 + x2 ≤ 1 x1, x2, x3, x4 = 0 atau 1 x1 = pendirian 1 kolam renang; x2 = pendirian 1 lapangan tenis; x3 = pendirian 1 lapangan atletik; x4 = pendirian 1 gelanggang olah raga
Nilai 1 artinya perlu didirikan, nilai 0 artinya tidak perlu didirikan
3. Contoh Model Integer Campuran Seorang pengusaha memiliki kelebihan uang $250.000 dan akan di investasikan pada 3 alternatif, yaitu : kondominium, tanah, dan obligasi. Dia ingin menginvestasikan uangnya dengan tujuan pengembalian terbesar diperoleh pada akhir tahun. Data jenis investasi: Jenis Investasi
Harga
Ketersedia n
Keuntungan per tahun
Kondominium
$50.000/ unit
4 unit
$9.000
Tanah
$12.000/ acre
15 acre
$1.500
Obligasi
$ 8.000/ obligasi
20 obligasi
$1.000
Model PL nya:
Maksimumkan Z = 9.000x1+1.500x2+1.000x3 Batasan : 50.000x1 + 12.000x2 + 8.000x3 ≤ 250.000 x1≤ 4 x2 ≤ 15 x3 ≤ 20 x2 ≥ 0 x1, x3 ≥ 0 dan integer x1 = # kondominium yang dibeli x2 = # acre tanah yang dibeli x3 = # obligasi yang dibeli x1 dan x3 harus integer, sedangkan x2 bilangan real
B. Solusi Model Program Integer
Ada beberapa cara untuk menyelesaikan program linear dan yang paling mudah adalah metode pembulatan. Contoh untuk persoalan banyaknya mesin yang ingin di beli.
Maksimumkan Z = 100x1 + 150x2 Batasan 8000 x1 + 4000x2 ≤ 40.000 15x1 + 30x2 ≤ 200 x1, x2 ≤ 0 dan integer Diketahui : x1 = jumlah mesin pencetak x2 = jumlah mesin bubut
Hasil pecahan untuk model ini dapat dilihat pada tabel simpleks.
Solusi Simpleks Optimal 100
150
0
0
x1
X2
s1
s2
cj
Variabel Dasar
100
x1
2,22
1
0
0,00016
-0,022
150
x2
5,55
0
1
-0,00008
0,044
zj
1.054,5
100
150
0,004
4,4
0
0
-0,004
-4,4
cj - zj
Kuantitas
Solusi berdasarkan tabel simpleks
x1 = 2,22 dan x2 = 5,55 bulatkan pada bilangan yang terdekat, sehingga x1 = 2 dan x2 = 6 akan tetapi bila dimasukan nilai-nilainya ke batasan 2 maka nilainya 15(2) + 30(6) ≤ 200 210 ≤ 200 tidak feasibel. Jika semua batasan berisi ≤ dan koefisien batasan positif, maka pembulatan ke bawah akan menjamin feasible sehingga x1 = 2 dan x2 = 5. Diperoleh Z = $950. Cara ini mempunyai resiko, yaitu tidak ditemukan bilangan integer yang optimal. Perhatikan gambar berikut: 11 10
9 8 7 6
Anggaran
5
Tempat
4 3 2 1 0 0
1
2
3
4
5
6
7
8
9
10 11 12 13 14
Perhatikan pada grafik x1 = 1 dan x2 = 6 menghasilkan Z = $1000, yang lebih besar dari Z yang dihasilkan oleh x1= 2 dan x2 = 5.
1.
Metode Branch and Bound
Metode ini untuk memecahkan persoalan program integer digabungkan bersama-sama dengan metode simpleks. Contoh : Model dengan batasan integer dilepaskan. Maksimumkan Z = 100x1 + 150x2 Batasan 8000 x1 + 4000x2 ≤ 40.000 15x1 + 30x2 ≤ 200 x1, x2 ≥ 0 Solusi Simpleks “Relaxed/ batasan integer dilepaskan” Optimal 100
150
0
0
x1
x2
s1
s2
cj
Variabel Dasar
100
x1
2,22
1
0
0,00016
-0,022
150
x2
5,55
0
1
-0,00008
0,044
zj
1.054,5
100
150
0,004
4,4
0
0
-0,004
-4,4
Kuantitas
cj - zj
Node pertama dalam diagram branch and bound adalah sbb: 1 1.054,5
Node pertama berisi nilai optimal dari tabel simpleks relaxed. Node ini mempunyai batas atas dan batas bawah berikut: BA = 1.054,50 ( x1 = 2,22; x2 = 5,55 ) BB = 950 ( x1 = 2, x2 = 5 )
Hasil optimal tidak boleh kurang dari BB dan tidak akan lebih dari BA.
Dari
x1=2,22
dan
x2=5,55
perhatikan
peubah
yang
mempunyai pecahan paling besar. 0,55 dari 5,55 adalah pecahan yang paling besar sehingga x2 peubah yang diberi cabang. Mengingat x2 harus bernilai integer dalam solusi maka batasan berikut dapat dikembangkan. x2 ≤ 5 dan x2 ≥6
Solusi pada node 2 didapat dengan cara memecahkan model dengan batasan x2 ≤ 5 berikut ini.
Subset solusi untuk x2 dan x3 1 1.054,5 x2≤5
x2≥6
2
3
Solusi pada node 2 didapat dengan memecahkan PL ditambahkan batasan x2≤5.
Maksimumkan Z = 100x1 + 150x2 Batasan 8000 x1 + 4000x2 ≤ 40.000 15x1 + 30x2 ≤ 200 x2 ≤ 5 x1, x2 ≥ 0 Solusi “Relaxed” Optimal pada Node 2 Variabel Dasar
cj
Kuantitas
100
150
0
0
x1
x2
s1
s2
S3
100
x1
2,5
1
0
0,000125
0
-0,5
0
s2
12,5
0
0
0,001875
1
-22,5
150
x2
5
0
2
0
0
1
zj
1.000
100
150
0,0125
0
100
0
0
-0,0125
0
-100
cj - zj
Solusi pada node 3 didapat dengan memecahkan PL ditambahkan batasan x2 ≥ 6.
Maksimumkan Z = 100x1 + 150x2 Batasan 8000 x1 + 4000x2 ≤ 40.000 15x1 + 30x2 ≤ 200 x2 ≥ 6 x1, x2 ≥ 0
Solusi “Relaxed” Optimal pada Node 3 Variabel Dasar
cj
Kuantitas
100
150
0
0
x1
x2
s1
s2
S3
0
s1
5,352
0
0
1
-533,30
266,6
100
x1
1,33
1
0
0
0,067
2
150
x2
6
0
1
0
0
-1
zj
1.033
100
150
0
6,7
50
0
0
0
-6,7
-50
cj - zj
Diagram branch and bound dengan batas bawah dan atas pada node 2 dan 3 1 1.054,5
2 (1.000) BA=1.000 (x1=2,5; x2=5) BB=950 (x1=2, x2=5)
BA=1.054,5 (x1=2,22; x2=5,55) BB=950 (x1=2, x2=5)
3 (1.033) BA=1.033 (x1=1,33; x2=6) BB=1000 (x1=1, x2=6)
Subset solusi untuk x1 BA=1.054,5 (x1=2,22; x2=5,55) BB=950 (x1=2, x2=5)
1 1.054,5 x2≤5
x2≥6
BA=1.033 (x1=1,33; x2=6) BB=1000 (x1=1, x2=6)
2 (1.000)
3 (1.033)
BA=1.000 (x1=2,5; x2=5) BB=950 (x1=2, x2=5)
x1≤1
4
x1≥2
5
Karena nilai maksimum node 3 lebih besar dibandingkan node 2 maka buat percabangan di node 3.
Solusi pada node 4 didapat dengan memecahkan PL pada
node 3 ditambahkan batasan x1≤ 1. Maksimumkan Z = 100x1 + 150x2 Batasan 8000 x1 + 4000x2 ≤ 40.000 15x1 + 30x2 ≤ 200 x2 ≥ 6 x1 ≤ 1 x1, x2 ≥ 0
Solusi “Relaxed” Optimal pada Node 4 Variabel Dasar
cj
Kuantitas
100
150
0
0
0
0
x1
x2
s1
s2
s3
s4
0
s1
7.333,33
0
0
1
-133,3
0
-6.000
0
s3
0,17
0
0
0
0,033
1
-0,50
150
x2
6,17
0
1
0
0,033
0
-0,50
100
x1
1
1
0
0
0
0
1
zj
1.033
100
150
0
5
0
25
0
0
0
-5
0
-25
cj - zj
Solusi pada node 5 didapat dengan memecahkan PL pada
node 3 ditambahkan batasan x1≥ 2 Maksimumkan Z = 100x1 + 150x2 Batasan 8000 x1 + 4000x2 ≤ 40.000 15x1 + 30x2 ≤ 200 x2 ≥ 6 x1 ≥ 2 x1, x2 ≥ 0
Solusi “Relaxed” Optimal pada Node 5 Variabel Dasar
cj
Kuantitas
100
150
0
0
0
0
x1
x2
s1
s2
s3
s4
0
s1
5.360
0
0
1
-4.000
0
0
100
x1
1,33
1
0
0
2
0
0
150
x2
6
0
1
0
-1
0
0
-M
A2
0,77
0
0
0
-2
-1
1
zj
900-0,77M
100
150
0
50+2M
M
-M
0
0
0
-50-2M
-M
0
cj - zj
Karena masih terdapat peubah artifisial artinya solusi tersebut tidak feasibel maka pada node 5 tidak terdapat solusi.
Diagram branch and bound dengan batas atas dan bawah pada node 4 dan 5 BA=1.054,5 (x1=2,22; x2=5,55) BB=950 (x1=2, x2=5)
1 1.054,5 x2≤5
x2≥6
BA=1.033 (x1=1,33; x2=6) BB=1000 (x1=1, x2=6)
2 (1.000)
3 (1.033)
BA=1.000 (x1=2,5; x2=5) BB=950 (x1=2, x2=5)
x1≤1
4 (1.025,5) BA=1.025,5 (x1=1; x2=6,17) BB=1.000 (x1=1, x2=6)
x1≥2
5
(tdk layak)
Subset solusi untuk x2 BA=1.054,5 (x1=2,22; x2=5,55) BB=950 (x1=2, x2=5)
1 1.054,5 x2≤5
x2≥6
BA=1.033 (x1=1,33; x2=6) BB=1000 (x1=1, x2=6)
2 (1.000)
3 (1.033)
BA=1.000 (x1=2,5; x2=5) BB=950 (x1=2, x2=5)
BA=1.025,5 (x1=1; x2=6,17) BB=1.000 (x1=1, x2=6)
x1≤1
5
4 (1.025,5)
x1≤6
6
x1≥2
(tdk layak) x1≥7
7
Solusi pada node 6 didapat dengan memecahkan PL pada
node 5 ditambahkan batasan x2≤ 6 Maksimumkan Z = 100x1 + 150x2 Batasan 8000 x1 + 4000x2 ≤ 40.000 15x1 + 30x2 ≤ 200 x2 ≥ 6 x1 ≥ 2 x2≤ 6 x1, x2 ≥ 0
Solusi “Relaxed” Optimal pada Node 6 cj
Variabe l Dasar
Kuantita s
100
150
0
0
x1
x2
s1
s2
s3
0
0
s4
s5
0
s1
8.000
0
0
1
0
0
-8.000
-4.000
0
s2
5
0
0
0
1
0
-15
30
150
x2
6
0
1
0
0
0
0
1
100
x1
1
1
0
0
0
0
1
0
0
s3
0
0
0
0
0
1
0
1
zj
1.000
100
150
0
0
0
100
150
0
0
0
0
0
-100
-150
cj - zj
Solusi pada node 7 didapat dengan memecahkan PL pada
node 5 ditambahkan batasan x2 ≥ 7 Maksimumkan Z = 100x1 + 150x2 Batasan 8000 x1 + 4000x2 ≤ 40.000 15x1 + 30x2 ≤ 200 x2 ≥ 6 x1 ≥ 2 x2≥ 7 x1, x2 ≥ 0
Solusi “Relaxed” Optimal pada Node 7 Vari abel Das ar
cj
Kuantit as
100
150
0
0
x1
x2
s1
s2
s3
0
0
s4
s5
A2
0
s1
13,33
6.000
0
1
-133,33
0
0
0
0
0
s2
0,67
0,50
0
0
0,033
1
0
0
0
150
x2
6,67
0,50
1
0
0,033
0
0
0
0
0
s4
1
1
0
0
0
0
1
0
0
-M
A2
0,33
0,50
0
0
-0,033
0
0
-1
1
zj
1.000,5
75+0,5M
150
0
49,5+0,033M
0
0
M
-M
25-0,5M
0
0
-49,5-0,033M
0
0
-M
0
cj - zj
Diagram branch and bound dengan solusi optimal di node 6 BA=1.054,5 (x1=2,22; x2=5,55) BB=950 (x1=2, x2=5)
1 1.054,5 x2≤5
x2≥6
BA=1.033 (x1=1,33; x2=6) BB=1000 (x1=1, x2=6)
2 (1.000)
3 (1.033)
BA=1.000 (x1=2,5; x2=5) BB=950 (x1=2, x2=5)
BA=1.025,5 (x1=1; x2=6,17) BB=1.000 (x1=1, x2=6)
x1≤1
x1≥2
5
4 (1.025,5)
x1≤6
(tdk layak) x1≥7
BA=1.000 (x1=1; x2=6) BB=1.000 (x1=1, x2=6) 6
7
(tdk layak)
Ringkasan langkah-langkah metode branch and bound dalam menentukan solusi integer optimal untuk model maksimisasi adalah sebagai berikut:
a.
Dapatkan solusi simpleks optimal dari model program linear dengan batasan integer yang dilepaskan.
b.
Tentukan solusi simpleks relaxed sebagai batas atas sedangkan solusi hasil pembulatan ke bawah sebagai batas bawah pada node 1.
c.
Pilih peubah dengan bagian pecahan yang terbesar untuk percabangan. Ciptakan dua batasan baru untuk peubah ini yang mencerminkan pembagian nilai integer. Hasilnya adalah sebuah batasan ≤ dan sebuah batasan ≥.
d.
Ciptakan dengan node baru, satu dengan batasan ≤ dan satu dengan batasan ≥
e.
Selesaikan model program linear relaxed dengan batasan baru yang ditambahkan pada tiap node
f.
Solusi simpleks relaxed adalah merupakan batas atas pada tiap node, dan solusi maksimum integer merupakan batas bawah dari node.
g.
Jika proses ini menghasilkan solusi integer feasibel dengan nilai batas atas terbesar pada akhir node mana saja, maka solusi integer optimal tercapai. Jika tidak muncul suatu solusi integer fisibel, lakukan percabangan dari node dengan batas atas terbesar.
h.
Ulangi langkah c.
Untuk model minimum, solusi relaxed merupakan solusi yang dibulatkan keatas, sedangkan batas atas dan bawahnya merupakan kebalikan dari model maksimumisasi.
2. Solusi Model Integer Campuran. Persoalan
model
integer
campuran
dapat
diselesaikan
menggunakan metode Branch and bound. Perbedaannya adalah (1) hanya variabel integer yang dibulatkan ke bawah untuk mendapatkan batas bawah. (2) dalam menentukan percabangan, dipilih pecahan terbesar hanya diantara variabel-variabel yang harus integer. Langkah lainnya sama. 3. Solusi Model Integer 0-1 Dapat dilakukan metode Branch and Bound dengan perubahan kecil. (1) batasan 0-1 untuk peubah-peubah dicantumkan sebagai batasan model x≤1.
