Program Integer Riset Operasi TIP – FTP – UB
Model Pemrograman Integer Tipe Model Total Integer Model: Semua variabel keputusan diharuskan mempunyai nilai solusi integer. 0–1 Integer Model: Semua variabel keputusan mempunyai nilai integer 0 atau 1. Biner / Binary Boolean dan True/False Mixed Integer Model: Beberapa variabel keputusan (tetapi tidak semua) diharuskan mempunyai solusi integer.
2
Model Total Integer (1 of 2) Toko mesin ingin membeli mesin pencetak dan mesin bubut baru Keuntungan marjinal: mesin cetak $100/hari; mesin bubut $150/hari. Batasan sumberdaya: $40,000, tempat tersedia 200 ft2. Biaya pembelian mesin dan kebutuhan ruang: Mesin
Kebutuhan Ruang ( ft2)
Harga beli
Pencetak
15
$8,000
Bubut
30
4,000 3
Model Total Integer (2 of 2) Integer Programming Model: Memaksimalkan Z = $100x1 + $150x2 dengan kendala: 8,000x1 + 4,000x2 $40,000 15x1 + 30x2 200 ft2 x1, x2 0 dan integer x1 = jumlah mesin pencetak x2 = jumlah mesin bubut
4
Model Integer 0-1 (1 of 2) Pemilihan fasilitas rekreasi untuk memaksimalkan penggunaan harian warga. Batasan sumberdaya: anggaran $120,000; tanah 12 acres. Batasan tambahan: salah satu dari kolam renang atau lapangan tenis. Data: Fasilitas Rekreasi
Penggunaan (orang/hari)
Biaya ($)
Kebutuhan Tanah (acres)
Kolam renang Lapangan tenis Lapangan atletik Gymnasium
300 90 400 150
35,000 10,000 25,000 90,000
4 2 7 3
5
Model Integer 0-1 (2 of 2) Integer Programming Model: Memaksimalkan Z = 300x1 + 90x2 + 400x3 + 150x4 dengan kendala: $35,000x1 + 10,000x2 + 25,000x3 + 90,000x4 $120,000 4x1 + 2x2 + 7x3 + 3x4 12 acres x1 + x2 1 fasilitas x1, x2, x3, x4 = 0 atau 1 x1 = pendiriian sebuah kolam renang x2 = pendirian sebuah lapangan tenis x3 = pendirian sebuah lapangan atletik x4 = pendirian sebuah gymnasium 6
Model Integer Campuran (1 of 2) Anggaran $250,000 tersedia untuk inverstasi dengan pengembalian terbesar setelah setahun. Data: Harga villa $50,000/unit, $9,000 keuntungan jika dijual setelah satu tahun. Harga tanah $12,000/acre, $1,500 keuntungan jika dijual setelah setahun. Harga obligasi $8,000/bond, $1,000 keuntungan jika dijual setalah setahun. Tersedia hanya 4 villa, 15 acres tanah, dan 20 obligasi.
7
A Mixed Integer Model (2 of 2) Integer Programming Model: Memaksimalkan Z = $9,000x1 + 1,500x2 + 1,000x3 dengan kendala: 50,000x1 + 12,000x2 + 8,000x3 $250,000 x1 4 villa x2 15 acres x3 20 bond x2 0 x1, x3 0 dan integer x1 = villa yang dibeli x2 = acre tanah yang dibeli x3 = obligasi yang dibeli 8
Solusi Grafis Pemrograman Integer Pembulatan solusi non-integer ke atas (ke bawah) dapat menghasilkan solusi tak layak Sebuah solusi layak mungkin ditemukan dengan pembulatan tetapi tidak optimal (sub-optimal). Apakah sebuah variabel dibulatkan ke atas atau ke bawah tergantung pada hasil dan kendala yang ada.
9
Contoh Pemrograman Integer Solusi Grafis Model Maksimasi Maximize Z = $100x1 + $150x2 subject to: 8,000x1 + 4,000x2 $40,000 15x1 + 30x2 200 ft2 x1, x2 0 dan integer Solusi Optimal: Z = $1,055.56 x1 = 2.22 pencetak x2 = 5.55 bubut Kedua nilai ini dapat diperoleh dengan pembualatan, tetapi nilai setiap fungsi tetap perlu dicek ulang
Feasible Solution Space with Integer Solution Points
10
Branch and Bound Method Pendekatan tradisional untuk pemecahan masalah pemrograman integer. Berdasarkan prinsip bahwa kumpulan solusi layak total dapat dipecah menjadi sub-kumpulan solusi yang lebih kecil. Sub-kumpulan yang lebih kecil dievaluasi sampai solusi terbaik ditemukan. Metode ini sangat melelahkan dan sering kali meliputi proses matematis yang kompleks. Penggunaan alat bantu dapat dipakai (Excel and QM for Windows).
11
Ringkasan Metode Branch and Bound 1. Dapatkan solusi simpleks optimal dari PL dg batasan integer 2. Tentukan solusi simpleks relaxed sebagai batas atas sedangkan solusi hasil pembulatan ke bawah sebagai batas bawah pada node 1 3. Pilih variabel dengan bagian pecahan terbesar untuk percabangan. Ciptakan dua batasan baru untuk variabel ini yang mencerminkan pembagian nilai integer berupa batasan ≤ dan ≥ 4. Ciptakan node baru, satu batasan ≤ dan satu batasan ≥ 5. Selesaikan model PL relaxed dengan batasan baru yang ditambahkan pada tiap node 6. Solusi simpleks relaxed adalah batas atas tiap node, dan solusi integer maksimum yang ada (pada node mana saja) adalah batas bawah 7. Jika solusi integer layak dengan nilai batas atas terbesar dihasilkan, maka solusi integer optimal tercapai. Jika solusi integer belum ada, lakukan percabangan dari node dengan batas atas terbesar 8. Ulangi langkah 3. 12
13
Computer Solution of IP Problems 0–1 Model with Excel (1 of 5) Recreational Facilities Example: Maximize Z = 300x1 + 90x2 + 400x3 + 150x4 subject to: $35,000x1 + 10,000x2 + 25,000x3 + 90,000x4 $120,000 4x1 + 2x2 + 7x3 + 3x4 12 acres x1 + x2 1 facility x1, x2, x3, x4 = 0 or 1
14
Computer Solution of IP Problems 0–1 Model with Excel (2 of 5)
Exhibit 9.2
15
Computer Solution of IP Problems 0–1 Model with Excel (3 of 5)
Instead, one could just specify $C$12:$C$15 as “binary” (= ‘0’ or ‘1’). Exhibit 9.3
16
Computer Solution of IP Problems 0–1 Model with Excel (4 of 5)
To constrain a range of variables to be integers, enter:
Exhibit 9.4
Instead, specify the “bin” what optionyou (= ‘0’put or ‘1’), … and one notecould thatjust it doesn’t matter in thus the side additional, 0” and “≤ 1”not constraints. the avoiding right-hand field,“≥but it must be empty.
17
Computer Solution of IP Problems 0–1 Model with Excel (5 of 5)
Exhibit 9.5
18
