Memformulasikan persoalan programa bilangan bulat

Persoalan-persoalan praktis dapat diformulasikan sebagai persoalan programa bilangan bulat (IP).

Contoh

Tuan Sugih, memiliki uang tunai 14 miliar rupiah,bermaksud menginvestasikan uangnya dalam beberapa usaha. Lalu ia mendapatkan 4 macam investasi. Investasi akan menghasilkan NPV 16 miliar, sedangkan investasi 2,3, dan 4 masing–masing akan menghasilkan NPV 22 miliar, 12 miliar, dan 8 miliar rupiah. Masing-masing investasi memerlukan pengeluaran awal 5,7,4, dan 3 miliar rupiah untuk investasi 1,2,3, dan 4. formulasikan persoalan di atas ke dalam bentuk persoalan IP sehingga tuan sigih dapat mengetahui bagaimana NPV maksimum dapat diperoleh dari keempat investasi itu.

Jawaban :

Definisikan variable keputusan sebagai berikut:

1, jika investasi j dilakukan

Xj (j= 1,2,3,4) ={

0, jika investasi j tidak dilakukan

Dalam hal ini, X2 = 1, berarti Tuan Sigih menggunakan uangnya pada investasi 2 dan X2 = 0, berarti investasi 2 tidak dilakukan. Total NVP yang dapat diperoleh tuan Sigih (dalam miliar rupiah) adalah 16 x1 + 22 x2 + 12 x3 + 8 x4. Artinya, jika dilakukan investasi 1 dan 4 saja, maka akan diperoleh NPV 16 + 8 = 24 miliar rupiah karena x1 = x4= 1 dan x2 = x3 = 0

Dengan demikian, fungsi tujuan dari persoalan ini adalah:

Maksimumkan: z = 16 x1 + 22 x2 + 12 x3 + 8 x4

Pembatas yang dihadapi adalah bahwa jumlah uang yang dapat diinvestasika tidak lebih dari 14 miliar, sementara total uang yang diperlukan untuk investasi (dalam miliar rupiah) adalah:

5 x1 + 7 x2 + 4 x3 + 3 x4 sehingga pembatasnya adalah:

5 x1 + 7 x2 + 4 x3 + 3 x4 (≤) 14.

Formulasi persoalan selengkapnya adalah:

Maksimumkan: z = 16 x1 + 22 x2 + 12 x3 + 8 x4

Berdasarkan:

5 x1 +7 x2 + 4 x3 + 3 x4 ≤ 14

Xj = 0 atau 1 (j = 1,2,3,4)

Persoalan IP yang hanya mempunyai satu pembatas seperti contoh di ataaaas dikenal sebagai persoalan ransel atau knapsack problem.

Menyelesaikan persoalan IP Murni dengan teknik Branch-And-Bound

Teknik ini mencari solusi optimal dari suatu persoalan IP dengan mengenumerasi titik-titik dalam daerah fisibel dari suatu subpersoalan. Dari suatu persoalan IP, baik murni ataupun campuran, dapat diperoleh bentuk persoalan programa linier relaksasi. Jika solusi dari LP relaksasi ini memiliki seluruh variable yang berharga integer, maka solusi optimal dari persoalan LP relaksasi itu adalah juga solusi optimal dari persoalan IP.

Contoh CV Kayu Indah

Formulasi dari persoalan tersebut adalah:

Maksimumkan: z = 8 x1 + 5 x2

Berdasarkan:

X1 + x2 ≤ 6

9 X1 + 5 x2 ≤ 45

X1, x2 ≥ 0 ; x1, x2 integer

Z = 165/4, x2 = 9/4. (nilai z-optimal untuk IP) ≤ (nilai z-optimal untuk LP relaksasi). Nilai z-optimal untuk persoalan IP tidak mungkin lebih besar daripada 165/4. Berarti, nilai z-optimal untuk LP relaksasi adalah batas atas dari keuntungan CV Kayu Indah.

Langkah berikutnya adalah memilih daerah fisibel dari soal LP relaksasi agar dapat diketahui lokasi dari solusi optimal persoalan LP.

Subpersoalan 2 = subpersoalan 1 + pembatas x1 ≥ 4

Subpersoalan 3 = subpersoalan 1 + pembatas x1 ≤ 3

Subpersoalan 2 dan 3 dibangun dengan cara menambahkan pembatas yang berkaitan dengan x1, maka dapat dikatakan bahwa subpersoalan 2 dan 3 dibangun dengan melakukan pencabangan x1.

Karena solusi optimal dari subpersoalan 2 masih mengandung variable yang tidak integer, maka dari persoalan 2 ini kita buat lagi dua subpersoalan baru, dan lakukan pencabangan dari variable yang belum integer itu. Dari solusi subpersoalan 2 ini, hanya variable x2 yang belum integer. Karena itu, pencabangan dilakukan terhadap x2. Untuk itu bagilah daerah fisibel untuk subpersoalan 2 ke dalam bagian yang memiliki x2 ≤ 1 sehingga diperoleh 2 subpersoalan baru:

Subpersoalan 4 = subpersoalan 1 + pembatas x1 ≥ 4 dan x2 ≥ 2

= subpersoalan 2 + pembatas x2 ≥ 2

Subpersoalan 5 = subpersoalan 1 + pembatas x1 ≥ 4 dan x2 ≤ 2

= subpersoalan 2 + pembatas x2 ≤ 2

Dengan aturan LIFO kita dapat menyelesaikan subpersoalan yang belum diselesaikan dari subpersoalan 3,4, dan 5. Karena subpersoalan 4 tidak fisibel maka tidak dapat memberikan solusi optimal. Juga tidak perlu pencabangan dilakukan. jika pencabangan dari suatu subpersoalan tidak dapat memberikan informasi yang berguna, maka subpersoalan itu disebut fathomed.

Solusi optimal dari subpersoalan 5 adalah titik I, yaitu z = 365/9, x1 = 40/9, x2 = 1. Solusi ini masih mengandung variabel yang tidak integer sehingga kita lakukan pencabangan dari x1.

Subpersoalan 6 = subpersoalan 5 + pembatas x1 ≥ 5

Subpersoalan 7 = subpersoalan 5 + pembatas x1 ≤ 4

Solusi optimal untuk subpersoalan 7 adalah titik H, yaitu z = 37, x1 = 4, x2 = 1. Karena x1 dan x2 berharga integer, maka solusi ini fisibel untuk persoalan IP semula. Suatu solusi yang diperoleh dengan cara menyelesaikan subpersoalan dimana seluruh variabelnya berharga integer disebut sebagai calon solusi. Calon solusi bisa saja optimal, maka kita simpan untuk kemudian kita bandingkan dengan calon solusi yang lain (jika ada).

Karena subpersoalan 7 tidak memberikan solusimfisibel integer denagn z > 37 maka subpersoalan 7 sudah fathomed.

Diperoleh solusi fisibel dari persoalan IP semula, yaitu z = 37, sehingga dapat disimpulkanbahwa nilai z-optimal untuk persoalan IP akan ≥ 37. Untuk menandai batas bawah, cantumkan notasi LB = 37 dalam kotak subpersoalan yang akan diselesaiakn berikutnya, yaitu subpersoalan 6.

Solusi optimal untuk subpersoalan 6 adalah titik A, yaitu z = 40, x1 = 5, x2 = 0. Seluruh variable keputusan telah berharga integer, maka solusi dari subpersoalan 6 juga calon solusi. Calon ini memiliki nilai z = 40, yang berarti lebih besar dari calon sebeelumnya.

Solusi optimal subpersoalan 3 adalah titik F, yaitu z = 39, x1 = x2 = 3. Subpersoalqn ini tidak dapat member nilai z lebih besar. Dengan demikian, solusi optimal dari persoalan IP untuk CV Kayu Indah adalah memproduksi 5 unit meja, dan tidak memproduksi kursi, sehingga akan diperoleh keuntungan sebesar Rp 40.000,00.

Kesimpulan

1. jika pencabangan dari suatu subpersoalan tidak dapat memberikan informasi yang berguna, maka subpersoalan itu disebut fathomed, 3 situasi yang menyebabkan, yaitu:

a. Jika subpersoalan itu tidak fisibel.

b. Jika subpersoalan itu memberikan solusi optimal yang seluruh variabelnya berharga integer.

c. Jika nilai z-optimal untuk subpersoalan itu tidak lebih baik dari nilai z-optimal subpersoalan lain.

2. Suatu subpersoalan dapat diabaikan jika subpersoalan berada dalam situasi berikut:

a. Tidak fisibel

b. Batas bawah atau LB (yang menyatakan nilai z dari calon solusi terbaik) sekurang-kurangnya berharga sama besar dengan nilai z dari subpersoalan yang bersangkutan