INTEGER PROGRAMMING Widha Kusumaningdyah, ST., MT 2012
INTEGER PROGRAMMING
INTRODUCTION
INTEGER PROGRAMMING (IP) • Untuk permasalahan optimasi dengan beberapa atau semua variabel keputusan bernilai bulat(integer). • Tidak dapat diselesaikan langsung dengan metode simpleks karena adanya beberapa atau semua variable yang berupa bilangan bulat melanggar salah satu asumsi metode simpleks (semua variable keputusan adalah bilangan real / tidak harus bulat).
KLASIFIKASI IP Integer programming dapat diklasifikasikan menjadi empat (berdasarkan banyaknya variable keputusan yang bernilai bulat): 1) Pure Integer Programming semua variable keputusan harus bernilai bilangan bulat 2) Mixed Integer Programming (MIP) tidak semua variable keputusan berupa bilangan bulat 3) Binary Integer Programming (BIP) semua variable keputusan memiliki nilai berupa bilangan biner (0 atau 1). 4) Mixed Binary Integer Programming (MBIP) Jika beberapa variable keputusan memiliki nilai biner, beberapa variable keputusan memiliki nilai integer dan sisanya memiliki nilai real (boleh pecahan).
PROBLEM IP Permasalahan yang mengharuskan variabel keputusan bernilai integer diantaranya adalah Investasi Multiperiode Budgeting Routing Knapsack Vehicle Loading Set Covering Scheduling Mixed Product Location Distribution Assignment Transportasi ….
CONTOH PROBLEM IP
1. PENJADWALAN PEKERJA (SCHEDULING) •
Bank Swasta buka mulai jam 9 pagi sampai dengan jam 5 sore. Banyaknya konsumen yang datang ke bank cukup bervariasi sehingga banyaknya teller yang diperlukan pada setiap jam juga berbeda. Teller merupakan tenaga outsourcing, pihak bank bisa menentukan pada jam berapa teller tersebut harus mulai bekerja. Setiap teller bekerja selama 5 jam sehari. Tentukan banyaknya setiap teller yang harus masuk pada setiap jam supaya biaya yang dikeluarkan bank minimal !
Periode
Jumlah teller yang diperlukan
9 – 10
10
10 – 11
12
11 – 12
14
12 – 1
16
1–2
18
2-3
17
3–4
15
4–5
10
Xi: banyaknya teller yang mulai masuk kerja pada jam ke i
X1 X2
X3 X4
X5 9
10
11
12
13
14
15
16
17
18
2. CAPITAL BUDGETING • Punya uang utk investasi Rp 14.000.000. • Ada 4 jenis kesempatan investasi : – Investasi 1 : butuh Rp 5.000.000 , akan berkembang mjd Rp 8.000.000 – Investasi 2 : butuh Rp 7.000.000 , akan berkembang mjd Rp 11.000.000 – Investasi 3 : butuh Rp 4.000.000 , akan berkembang mjd Rp 6.000.000 – Investasi 4 : butuh Rp 3.000.000 , akan berkembang mjd Rp 4.000.000
FORMULASI : Capital Budgeting Model ILP : xi : investasi ke i , i=1,2,3,4 xi = 0 jika tidak mengambil investasi i = 1 jika mengambil investasi i Maksimasi : Z = 8x1 + 11x2 + 6x3 + 4x4 Kendala : 5x1 + 7x2 + 4x3 + 3x4 ≤ 14 xi {0,1} , i = 1,2,3,4
3. CONTOH & FORMULASI : Capital Budgeting • Apabila ditambah kendala : – Kita hanya dapat membuat paling banyak dua investasi – Jika investasi 2 diambil, maka investasi 4 juga diambil – Jika investasi 1 diambil, maka investasi 3 tidak dapat diambil
• Model matematikanya : Maksimasi : Z = 8x1 + 11x2 + 6x3 + 4x4 Kendala : 5x1 + 7x2 + 4x3 + 3x4 ≤ 14 x 1 + x2 + x 3 + x4 ≤ 2 x2 – x4 ≤ 0 x1 + x3 ≤ 1 xi {0,1} , i = 1,2,3,4
3. KNAPSACK PROBLEM • Terdapat 7 jenis barang, setiap jenis barang mempunyai ukuran dan keuntungan yang berbeda sbb : Barang ke-
1
2
3
4
5
6
7
Ukuran
5
7
4
3
4
3
7
Nilai
8
11
6
4
6
5
6
• Alat angkut hanya mampu mengangkut 40 m3, barang manakah yang seharusnya diangkut?
4. PEMILIHAN LOKASI PABRIK •
•
•
•
Perusahaan berencana untuk mendirikan satu atau beberapa pabrik untuk memenuhi permintaan produk pada berbagai daerah (pasar). Terdapat 4 lokasi dimana pabrik dapat dibangun dan terdapat 12 pasar yang harus dipenuhi oleh perusahaan. Produk akan langsung dikirim dari pabrik ke pasar. Biaya untuk mendirikan pabrik dan kapasitas pabrik di masing-masing lokasi adalah sebagai berikut: A B C D Biaya Investasi
1000
1500
700
400
Kapasitas
2000
4000
1000
900
Biaya untuk mengirim barang dari suatu pabrik ke pasar adalah sebagai berikut 1
2
3
4
5
6
7
8
9
10
11
12
A
3
4
1
2
3
5
5
2
3
4
5
5
B
6
6
4
5
7
3
4
1
2
4
4
4
C
4
2
3
5
4
5
4
3
6
5
4
3
D
5
5
2
3
4
5
5
6
2
3
5
5
Permintaan 500 200 400 600 dan 400berapa 200pabrik 250yang 200 300 220 Tentukan dimanakah pabrik harus100 dibangun harus dibangun??
100
5. DIET PROBLEM Kebutuhan : energy(2000kcal), protein(55g), calcium(800mg) Serving
Energy
Protein
Calcium
Price per
Max serving
size
(kcal)
(g)
(mg)
serving (cents)
allowed
Oatmeal
28g
110
4
2
3
4
Chicken
100g
205
32
12
24
3
Eggs
2 large
160
13
54
13
2
Wholemilk
237cc
160
8
285
9
8
Cherry pie
170g
420
4
22
20
2
Pork with beans
260g
260
14
80
19
2
Food
Formulasi : DIET PROBLEM Minimisasi : 3x1 24 x2 13x3 9 x4 20 x5 19 x6 Pembatas:
0 x1 4 0 x2 3 0 x3 2 0 x4 8 0 x5 2 0 x6 2
110 x1 205 x2
160 x3
160 x4
420 x5
260 x6
2000
4 x1
32 x2
13x3
8 x4
4 x5
14 x6
55
2 x1
12 x2
54 x3
285 x4
22 x5
80 x6
800
6. BLENDING •
Perusahaan eaglefood akan memproduksi cereal dalam kemasan sebesar 2 pound. Cereal yang diproduksi harus memenuhi kebutuhan gizi dalam sehari. Kebutuhan gizi dalam sehari dapat dilihat dalam tabel berikut ini: Grain
• •
A
B
C
Harga per pound
3300
4700
3800
Minimum Daily Requirement
Protein per pound
22
28
21
3
Riboflavin per pound
16
14
25
2
Phosphorus per pound
8
7
9
1
Magnesium per pound
5
0
6
0.425
Terdapat tiga alternatif bahan baku yang dapat digunakan, bahan baku tersebut bisa dicampur untuk memproduksi cereal. Tentukan bagaimana perbandingan(komposisi) bahan baku A, B dan C dalam cereal sehingga biaya untuk memproduksi cereal minimum!
FORMULASI : MODEL Variabel keputusan • xi = jumlah mobil tipe ke-i yang diproduksi • yi = 1 jika mobil tipe ke-i diproduksi, dan yi=0 jika tidak Formulasi : Maks z = 2 x1 + 3 x2 + 4 x3 Subject to: x1 ≤ M y1 x2 ≤ M y2 x3 ≤ M y3 1000 – x1 ≤ M (1 – y1) 1000 – x2 ≤ M (1 – y2) 1000 – x3 ≤ M (1 – y3) 1.5 x1 + 3 x2 + 5 x3 ≤ 6000 30 x1 + 25 x2 + 40 x3 ≤ 60000 x1, x2, x3 ≥ 0 dan integer y1, y2, y3 = 0 atau 1
7. SET COVERING PROBLEM • •
•
•
•
Propinsi sukolilo mempunyai 6 kota Pemerintah berencana untuk membangun kantor pusat pemadam kebakaran. Pada kantor pusat pemadam kebakaran akan ditempatkan kendaraan pemadam kebakaran, peralatan pemadam kebakaran dan personelnya, sehingga jika ada kebakaran maka petugas akan berangkat dari kantor pusat pemadam kebakaran menuju lokasi kebakaran. Petugas tidak boleh mencapai lokasi kebakaran lebih dari 15 menit (waktu tempuh) dari stasiun pemadam kebakaran. Waktu yang dibutuhkan dari kota yang satu ke kota yang lain adalah sebagai berikut. Kota ke-
1
2
3
4
5
6
1
0
10
20
30
30
20
2
10
0
25
35
20
10
3
20
25
0
15
30
20
4
30
35
15
0
15
25
5
30
20
30
15
0
14
6
20
10
20
25
14
0
Tentukan dimanakah kantor pusat pemadam kebakaran harus dibangun supaya banyaknya kantor yang harus dibangun tidak banyak(minimal) sehingga dana APBD bisa dihemat untuk dialokasikan pada bidang lain?
7. SET COVERING PROBLEM (CONT’D) • •
Sebuah kota dapat dicover oleh stasiun pemadam kebakaran jika jarak tempuhnya tidak lebih dari 15 menit Covering set untuk setiap kota Kota
Covering sets (15 menit)
1
1,2
2
1,2,6
3
3,4
4
3,4,5
5
4,5,6
6
2,5,6
FORMULASI SET COVERING PROBLEM Variabel keputusan : xi = 1 jika dibangun stasiun pemadam kebakaran pada kota-i = 0 jika TIDAK dibangun stasiun pemadam kebakaran pada kota-i Fungsi tujuan : Minimum Z= x1+ x2+ x3+ x4+ x5 + x6 Fungsi pembatas: x1+x2 ≥ 1 x1+x2 + x6 ≥ 1 x3+x4 ≥ 1 x3+x4+x5 ≥ 1 x4+x5+x6 ≥ 1 x2+x5+x6 ≥ 1
8. ASSIGNMENT (PENUGASAN) Pak Ali harus menugaskan stafnya untuk mengerjakan tugas-tugas pada divisinya. Pak Ali memiliki 5 staf yaitu Rita, Tari, Rani, Nira, Tara. Divisi pak ALi harus menyelesaikan 5 tugas. Pak Ali menemui kesulitan dalam menugaskan kelima stafnya karena Rita tidak mempunyai keahlian dalam mengerjakan tugas 2 sedangkan Tari tidak mampu mengerjakan tugas 1. Biaya menugaskan setiap staff adalah berbeda beda karena untuk bisa menyelesaikan tugas dengan baik, staff seringkali harus mendapatkan pelatihan dan biaya akomodasi yang berbeda beda. Biaya menugaskan setiap staff untuk mengerjakan satu tugas adalah sebagai berikut:
Staff Rita Tari Rani Nira Tara
1 4 3 4 8
2 5 5 2 8
Tugas 3 10 1 8 7 2
4 6 5 4 1 10
5 5 10 7 10 5
Bagaimanakah cara menugaskan kelima staff tersebut supaya biaya yang harus dikeluarkan perusahaan minimal?
INTEGER PROGRAMMING
METODE CUTTING PLANE
IP SOLVING: ALGORITMA CUTTING-PLANE • Temukan solusi optimal untuk Linier Problem (menggunakan prosedur standar). • Tambahkan fungsi pembatas khusus (disebut cuts) untuk menghasilkan titik ekstrim optimal integer. • Cuts tidak menghilangkan titik feasible integer asal. • The cuts must through at least one feasible or infeasible integer point • Number of cuts is independent of the size of the problem
IP SOLVING: ALGORITMA CUTTING-PLANE • Contoh permasalahan ILP:
IP SOLVING: ALGORITMA CUTTING-PLANE
PENDEKATAN GRAFIS • Solusi:
IP SOLVING: ALGORITMA CUTTING-PLANE
PENDEKATAN ALJABAR • Tabel Optimal LP:
• Buat cuts – Dengan asumsi bahwa semua variable (termasuk slacks) adalah integer.
IP SOLVING: ALGORITMA CUTTING-PLANE
PENDEKATAN ALJABAR • Langkah untuk membuat cuts: – Pilih ‘baris sumber’ – Faktorkan baris sumber – Buat cuts dari faktor baris sumber – Buat persamaan dari cuts • Selesaikan problem dari fraksi pecahan – Tambahkan fungsi pembatas pada tabel simples optimal – Gunakan dual simplex untuk menyelesaikan permasalahan, jika tabel optimal tidak feasible. – Buat fraksi selanjutnya hingga semua variable integer.
1. MEMBUAT CUTS Pilih baris sumber
Faktorkan baris sumber Faktor baris sumber – x2 Buat cuts dari faktor baris sumber
Buat persamaan dari cuts
2. SELESAIKAN DENGAN SIMPLEX • Table baru :
• Selesaikan dengan dual simplex – Hasil:
• Buat cut selanjutnya hingga semua variabel integer • Final Result:
LATIHAN
• References: – Eunike, Agustina. Materi Ajar Penelitian Operasional 1. PSTI – Universitas Brawijaya. 2012 – Frederick Hillier and Gerald J. Lieberman. Introduction to Operations Research. 7th ed. The McGraw-Hill Companies, Inc, 2001. – Hamdy A. Taha. Operations Research: An Introduction. 8th Edition. Prentice-Hall, Inc, 2007
