PROGRAMA BILANGAN
BULAT
Programa bilangan bulat atau integer
programming (IP) adalah bentuk lain dari
programa linier atau linier programming (LP) di
mana asumsi divisibilitasnya melemah atau
hilang sama sekali.
Bentuk ini muncul karena dalam kenyataannya
tidak semua variabel keputusan dapat berupa
bilangan pecahan.
Misalnya, jika variabel keputusan yang
dihadapi adalah jumlah produk yang harus
diproduksi untuk mencapai keuntungan
maksimal, maka jawaban 1 1/2 adalah sangat
tidak mungkin karena kita tidak bisa
memproduksi produk setengah-setengah.
Dalam hal ini haruslah ditentukan
apakah akan memproduksi satu atau
dua produk.
Pendekatan pembulatan dari solusi nilai
pecahan dari programa linier ini tetap
memenuhi semua kendala dan tidak
menyimpang cukup jauh dari solusi
bulat yang tepat.
Integer programming merupakan teknik
dari linier programming dengan
tambahan persyaratan semua atau
beberapa variabel bernilai bulat
nonnegatif.
Pure (all) integer programming (programa
bilangan bulat murni).
Apabila seluruh variabel keputusan dari
permasalahan programa linier harus berupa
bilangan bulat (positif atau nol). Dalam hal ini
asumsi divisibilitas dari programa liniernya hilang
sama sekali.
Minimize Z = 3 X1 + 5 X2
Subject to 2X1 + 4X2 ≥ 4
3X1 + 2X2 ≥ 5
X1, X2 ≥ 0; X1, X2 integer
Mixed integer programming (programa
bilangan bulat campuran).
Apabila hanya terdapat sebagian dari
variabel keputusan dari permasalahan
programa linier yang diharuskan berupa
bilangan bulat (positif atau nol). Dalam
hal ini asumsi divisibilitasnya melemah.
Contoh:
Maximize Z = 6 X1 – 4 X2
Subject to X1 + X 2 ≤ 2
–3X1 – 2X2 ≤ 12
X1, X2 ≥ 0; X2 integer
Zero one integer programming
(programa bilangan bulat nol-satu
Apabila variabel keputusannya diharuskan
berharga 0 (nol) atau 1 (satu). Kondisi ini
ditemukan dalam kasus di mana persoalan
yang dihadapi merupakan persoalan
keputusan “ya” atau “tidak”.
Contoh:
Maximize Z = 40 X1 + 50 X2
Subject to 2X1 + 3X2 ≤ 3.000
4X1 + 2X2 ≤ 2.500
X1, X2 = 0 atau 1
Maksimumkan Z = 100 X1 + 90 X2
Dengan syarat 10 X1 + 7 X2 ≤ 70 Masalah 1
5 X1 + 10 X2 ≤ 50
X1 ; X2 ≥ 0
Minimumkan Z = 200 X1 + 400 X2
Dengan syarat 10 X1 + 25 X2 ≥ 100
3 X1 + 2 X2 ≥ 12
Masalah 2
X1 ; X2 ≥ 0
Maksimumkan Z = 80 X1 + 100 X2
Dengan syarat 4 X1 + 2 X2 ≤ 12
X1 + 5 X2 ≤ 15
Masalah 3
X1 ; X2 ≥ 0
7
Solusi dengan Dgn pembulatan Bulat optimum
Masalah
Metode simpleks terdekat sesungguhnya
1 X1 = 5,38 X1 = 5 X1 = 7
X2 = 2,31 X2 = 2 X2 = 0
Z = 746,15 Z = 680 Z = 700
2 X1 = 1,82 X1 = 2 X1 = 3, X2 = 3
X2 = 3,27 X2 = 3 X1 = 5, X2 = 2
Z = 1.672,73 Z tak layak Z = 1.800
3 X1 = 2,14 X1 = 2 X1 = 0
X2 = 1,71 X2 = 2 X2 = 3
Z = 343 Z tak layak Z = 300
8
Metode Grafis
Metode ini sama seperti metode pemecahan
dalam programa linier dalam bentuk grafis,
namun dengan tambahan pembatas yakni
variabel keputusan—sebagian atau semua—
berupa bilangan bulat.
Metode Pembulatan ( Round Off )
Metode ini memberikan cara konvensional atau
kolot terhadap permasalahan programa bilangan
bulat, yakni melakukan pembulatan (round off)
terhadap solusi optimal bila dimungkinkan
Metode Branch-and-Bound
Metode ini dilakukan dengan mengibaratkan
suatu permasalahan sebagai pohon (tree),
kemudian permasalahan tersebut dibagi atau
dibuat percabangan (branching) ke dalam subset
yang lebih kecil
Maximize Z = 7 X1 + 6 X2
Subject to 2X1 + 3X2 ≤ 12
6X1 + 5X2 ≤ 30
X1, X2 ≥ 0; X1, X2
integer
di mana
X1 = lampu
X2 = kipas angin
Terlihat kalau metode grafis tidak mampu
memberikan solusi yang nyata pada
permasalahan di atas, karena tidak mungkin
perusahaan membuat dan menjual barang
dalam bentuk pecahan.
Hal yang dapat dilakukan adalah menggeser titik
optimal yang masih masuk dalam daerah fisibel,
yakni: titik (4,1) atau (3,2). Titik (4,1) akan
memberikan solusi sebesar 34, sedangkan titik
(3,2) akan memberikan solusi sebesar 33.
Karena titik (4,1) memberikan solusi optimal
yang lebih maksimal, maka diperoleh solusi
optimal sebesar 34, dengan X1 = 4 dan X2 = 1
(perusahaan akan mendapatkan profit sebesar $
34 dengan memproduksi lampu sebanyak 4
buah dan kipas angin sebanyak 1 buah).
Pendekatan ini mudah dan praktis dalam hal
usaha, waktu dan biaya. Pendekatan
pembulatan dapat merupakan cara yang
sangat efektif untuk masalah integer
programming yang besar dimana biaya-biaya
hitungan sangat tinggi atau untuk masalah
nilai-nilai solusi variabel keputusan sangat
besar.
Sebab utama kegagalan pendekatan ini
adalah bahwa solusi yang diperoleh mungkin
bukan solusi integer optimum yang
sesungguhnya. Solusi pembulatan dapat lebih
jelek dibanding solusi integer optimum yang
sesungguhnya atau mungkin merupakan
solusi tak layak.
13
Metode simpleks memberikan solusi
yang sama dengan metode grafis,
yakni: Z = 35,25; X1 = 3,75 ; X2 =
1,5.
Dengan melakukan pembulatan, dengan
mudah kita akan mendapatkan harga
X1 = 4 dan X2 = 2 dan Z = 40.
Namun, ternyata pembulatan tersebut
tidak layak dilakukan karena titik (4,2)
berada di luar daerah fisibel (lihat
grafik).
Langkah-langkahnya sbb :
1. Selesaikan LP dengan metode simpleks biasa
2. Teliti solusi optimumnya. Jika variabel basis yang
diharapkan bulat adalah bulat, solusi optimum bulat telah
tercapai.
3. Nilai solusi pecah yang layak dicabangkan ke dalam sub-
sub masalah. Tujuannya adalah untuk menghilangkan
solusi kontinyu yang tidak memenuhi persyaratan bulat
dalam masalah itu.
4. Untuk setiap sub-masalah, nilai solusi optimum kontinu
fungsi tujuan ditetapkan sebagai batas atas. Solusi bulat
terbaik menjadi batas bawah adalah solusi kontinu yang
dibulatkan ke bawah. Sub-sub masalah yang memiliki
batas atas kurang dari batas bawah yang ada, tidak diikut
sertakan pada analisa selanjutnya. Suatu solusi bulat
layak adalah sama baik atau lebih baik dari batas atas
untuk setiap sub masalah yang dicari. Jika solusi yang
demikian terjadi, suatu sub masalah dengan batas atas
terbaik dipilih untuk dicabangkan. Kembali ke langkah 3.
16
Dari contoh sebelumnya :
Dengan perhitungan menggunakan metode
simpleks, didapatkan solusi optimal Z = 35,25 ;
X1 = 3,75 ; X2 = 1,5.
Karena X1 dan X2 bukan bilangan bulat, maka
solusi ini tidak valid, dan nilai Z (profit) sebesar
35,25 dijadikan sebagai batas atas awal (first
upper bounded). Artinya, solusi optimal nantinya
tidak akan lebih besar dari 35,25.
Kemudian dengan metode pembulatan ke
bawah, kita dapatkan X1 = 3 dan X2 = 1 dengan
Z = 27 dijadikan batas bawah (lower bounded).
Artinya, solusi optimal nantinya harus di atas 27.
Dengan kedua batasan ini, maka solusi optimal
yang akan dicari haruslah berada pada rentang
27 sampai 35,25.
Subset 1
Maximize Z = 7 X1 + 6 X2
Subject to 2X1 + 3X2 ≤ 12
6X1 + 5X2 ≤ 30
X1 ≥ 4
Subset 2
Maximize Z = 7 X1 + 6 X2
Subject to 2X1 + 3X2 ≤ 12
6X1 + 5X2 ≤ 30
X1 ≤ 3
Permasalahan
Z = 35,25
X1 = 3,75
X2 = 1,50
X1 ≥ 4 X1 ≤ 3
Subset 1 Subset 2
Z = 35,2 Z = 33
X1 = 4 X1 = 3
X2 = 1,2 X2 = 2
Calon solusi
Subset 3 Subset 4
Maximize Z = 7 X1 + 6 Maximize Z = 7 X1 + 6 X2
X2
Subject to 2X1 + 3X2 ≤ 12
Subject to 2X1 + 3X2 ≤ 12
6X1 + 5X2 ≤ 30
6X1 + 5X2 ≤ 30
X1 ≥ 4
X1 ≥ 4
X2 ≥ 2 X2 ≤ 1
Permasalahan
Z = 35,25
X1 = 3,75
X2 = 1,50
X1 ≥ 4 X1 ≤ 3
Subset 1 Subset 2
Z = 35,2 Z = 33
X1 = 4 X1 = 3
X2 = 1,2 X2 = 2
Calon solusi
X2 ≥ 2 X2 ≤ 1
Subset 3 Subset 4
Z = 35,16
Infeasible X1 = 4 1/6
X2 = 1
fathomed
Subset 5 Subset 6
Maximize Z = 7X1 + Maximize Z = 7X1 +
6X2 6X2
Subject to 2X1+3X2 ≤ 12 Subject to 2X1+3X2 ≤ 12
6X1+5X2 ≤ 30 6X1+5X2 ≤ 30
X1 ≥ 4 X1 ≥ 4
X2 ≤ 1 X2 ≤ 1
X1 ≥ 5 X1 ≤ 4
Permasalahan
Z = 35,25
X1 = 3,75
X2 = 1,50
X1 ≥ 4 X1 ≤ 3
Subset 1 Subset 2
Z = 35,2 Z = 33
X1 = 4 X1 = 3
X2 = 1,2 X2 = 2
Calon solusi
X2 ≥ 2 X2 ≤ 1
Subset 3 Subset 4
Z = 35,16
Infeasible X1 = 4 1/6
X2 = 1
fathomed
X1 ≥ 5 X1 ≤ 4
Subset 5 Subset 6
Z = 35 Z = 34
X1 = 5 X1 = 4
X2 = 0 X2 = 1
Solusi optimal Calon Solusi
TERIMA
KASIH