19/11/2013
Lecture 9
PENELITIAN OPERASIONAL I (TIN 4109)
INTEGER LINEAR PROGRAMMING
Lecture 9 (Part 1) • Outline: – Integer Linear Programming: Introduction
• References: – 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. – Sriram, Sankaranarayanan. Computer Science, University of Colorado, Boulder. Http/www.coursera.org. – Winston, Wayne L. Operations Research: Applications and Algorithms. 3rd edition. Wadsworth Inc.1994.
Integer Linear Programming (ILP) • 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).
INTEGER PROGRAMMING
INTRODUCTION
Integer Linear Programming Integrality Constraint
Feasible Region: Z-Polyhedron (n dimensional)
1
19/11/2013
Integer Linear Program
Linear Programming Relaxation
• Feasibility of ILP: – Integer feasible solution.
• Unbounded ILP: – Integer feasible solutions can achieve arbitrarily large values for the objective. Q: What happens to the answer if we take away the integrality constraints?
Feasible Regions
Case-1: Both LP and ILP are feasible. Opt. Solution of LP relaxation
ILP feasible region
LP feasible region
Case-I
Opt. Solution of ILP
Case-II: LP relaxation is feasible, ILP is infeasible.
Optimal Objective of ILP ≤ Optimal solution of LP relaxation.
ILP is infeasible. LP relaxation has optimal solution: 0.5
Opt. Solution of ILP 0.3
0
0.5
1
2
19/11/2013
Case III: ILP is infeasible, LP is unbounded. Example:
ILP outcomes vs. LP relaxation outcomes
ILP is infeasible. LP relaxation is unbounded
Integer Linear Program (ILP)
LP Relaxation
0.3
Infeasible
Unbounded Optimal
Possible
Impossible
Impossible
Unbounded Possible
Possible
Possible (*)
Optimal
Impossible
Possible
Infeasible
Possible
0.5
(*) Impossible if ILP has rational coefficients
Klasifikasi ILP
Integer linear Programming
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).
Permasalahan yang mengharuskan variabel keputusan bernilai integer diantaranya adalah
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
Investasi Multiperiode Budgeting Routing Knapsack Vehicle Loading Set Covering Scheduling Mixed Product Location Distribution Assignment Transportasi ….
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
3
19/11/2013
Penjadwalan Pekerja (Scheduling) •
• •
Pengelola obyek wisata pantai sedang merencanakan untuk melakukan perekrutan lifeguard. Lifeguard bertugas untuk membantu pengunjung obyek wisata yang mengalami kesulitan misalnya kecelakan yang membahayakan jiwa, menjadi korban tindak kejahatan, kehilangan barang, terpisah dari keluarga dan lain-lain. Pada hari-hari libur pantai selalu ramai dikunjungi oleh wisatawan sedangkan pada hari-hari kerja pantai realtif tidak ramai. Hal ini menyebabkan banyaknya lifeguard yang diperlukan juga berbeda. senin
Selasa
rabu
Kamis
Jumat
sabtu
Minggu
5
4
4
6
6
9
12
Capital Budgeting • Punya uang utk investasi Rp 14.000.000. • Ada 4 jenis kesempatan investasi : – Investasi 1 : butuh – Investasi 2 : butuh 11.000.000 – Investasi 3 : butuh – Investasi 4 : butuh
Rp 4.000.000 , akan berkembang mjd Rp 6.000.000 Rp 3.000.000 , akan berkembang mjd Rp 4.000.000
Lifeguard bekerja lima hari dalam seminggu Tentukanlah banyaknya lifeguard yang harus direkrut!
Capital Budgeting
Capital Budgeting • Apabila ditambah kendala :
Model ILP : xi = investasi ke i , i=1,2,3,4 xi = 0 jika tidak mengambil investasi i = 1 jika mengambil investasi i
– 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 + x 2 + x3 + x 4 ≤ 2 x2 – x4 ≤ 0 x1 + x3 ≤ 1 xi {0,1} , i = 1,2,3,4
Maksimasi : Z = 8x1 + 11x2 + 6x3 + 4x4 Kendala : 5x1 + 7x2 + 4x3 + 3x4 ≤ 14 xi {0,1} , i = 1,2,3,4
Knapsack Problem
Multiperiod Capital Budgeting •
Rp 5.000.000 , akan berkembang mjd Rp 8.000.000 Rp 7.000.000 , akan berkembang mjd Rp
Terdapat 4 pilihan investasi yaitu investasi 1,2,3 dan 4. Dana yang dibutuhkan dan laba yang dihasilkan oleh masing-masing investasi adalah sebagai berikut: Dana yang dibutuhkan Investasi
A
B
C
D
Periode 1
7
8
7
4
Periode 2
5
11
4
4
Periode 3
6
6
4
4
Total Laba
15
20
13
12
•
Dana yang dimiliki oleh perusahaan dalam tiga periode ke depan adalah 30,35 dan
•
40. Investasi manakan yang seharusnya dipilih?
• Terdapat 7 jenis barang, setiap jenis barang mempunyai ukuran dan keuntungan yang berbeda sbb : Barang ke-
1
Ukuran Nilai
2
3
4
5
6
7
5
7
4
3
4
3
7
8
11
6
4
6
5
6
• Alat angkut hanya mampu mengangkut 40 m3, barang manakah yang seharusnya diangkut?
4
19/11/2013
Vehicle Loading
Pemilihan Lokasi Pabrik •
•
Alat angkut (truck) memiliki batas maksimal muatan yang bisa diangkut. Batas maksimal muatan dibatasi oleh volume dan berat. Jika truck digunakan mengangkut benda dengan berat jenis yang relatif kecil maka batas angkutan akan ditentukan oleh volume dan sebaliknya.
•
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
Item
• •
1
2
3
4
5
6
Laba
$15,500
$14,400
$10,350
$14,525
$13,000
$9,625
Berat(kg)
500
450
300
350
400
350
Volume(m3)
125
64
144
218
280
180
•
Berat maksimal yang bisa diangkut oleh truck adalah 2000 kg dan volume 1000 m3 Tentukan produk mana yang seharusnya diangkut oleh truck supaya mendapatkan laba maksimal! •
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 400 berapa 200 pabrik 250yang200 300 220 Tentukan dimanakah pabrik harus100 dibangun harus dibangun??
100
Formulasi
Diet
Minimisasi : 3x1 24 x2 13x3 9 x4 20 x5 19 x6
Kebutuhan : energy(2000kcal), protein(55g), calcium(800mg)
Pembatas:
Serving size
Energy (kcal)
Protein (g)
Calcium (mg)
Price per serving (cents)
Max serving allowed
28g
110
4
2
3
4
0 x2 3
Chicken
100g
205
32
12
24
3
Eggs
2 large
160
13
54
13
2
0 x3 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 Oatmeal
0 x1 4
0 x4 8 0 x5 2 0 x6 2
110 x1 205 x2
160 x3
160 x4
420 x5
260 x6
4 x1
32 x2
13x3
8 x4
4 x5
14 x6
2000
55
2 x1
12 x2
54 x3
285 x4
22 x5
80 x6
800
Either-Or Constrains
Blending • •
Biaya Investasi
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!
• • •
Perusahaan Dorian automotif memproduksi 3 tipe model mobil yaitu ; compact (kecil), midsize (menengah), dan large (besar). Ada 6 ton baja dan 60,000 jam kerja tersedia Jika suatu tipe mobil diproduksi, maka mobil itu harus diproduksi paling sedikit 1,000 unit mobil Data produksi seperti terlihat di tabel bawah ini:
Kebutuhan baja Kebutuhan jam tenaga kerja Profit •
Formulasikan permasalahan memaksimumkan profit.
Compact 1.5 ton 30 jam $2000
Midsize 3 ton 25 jam $3000
perencanaan
produksi
Large 5 ton 40 jam $4000 tersebut
untuk
5
19/11/2013
Set Covering
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
• •
• •
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?
Set Covering • •
Set Covering
Sebuah kota dapat dicover oleh stasiun pemadam kebakaran jika jarak tempuhnya tidak lebih dari 15 menit Covering set untuk setiap kota Kota
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
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
Assignment (Penugasan)
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: Tugas Staff 1 2 3 4 5 Rita 4 10 6 5 Tari 5 1 5 10 Rani 3 5 8 4 7 Nira 4 2 7 1 10 Tara 8 8 2 10 5 Bagaimanakah cara menugaskan kelima staff tersebut supaya biaya yang harus dikeluarkan perusahaan minimal?
•
•
PT. Jaya Selalu membeli tiga buah mesin baru. Tiga mesin tersebut dapat ditempatkan pada empat lokasi yang tersedia dalam pabrik. Penempatan mesin-mesin tersebut harus mempertimbangkan workflow (aliran produk dalam proses pengerjaan) mesin-mesin tersebut dengan stasiun kerja lain. Sebagai manajer produksi anda harus menentukan penempatan mesin-mesin tersebut yang bisa meminimalkan biaya material handling. Biaya penempatan masing-masing mesin pada setiap lokasi adalah sebagai berikut. Mesin 2 tidak boleh ditempatkan pada lokasi 2, karena lokasi 2 dengan tangki bahan bakar dan mesin dua merupakan mesin Oven yang selalu bersuhu tinggi. Lokasi Assignee (Mesin)
1
2
3
4
1
13
16
12
11
2
15
-
13
20
3
5
7
10
6
6
19/11/2013
Cutting Stock(1)
Cutting Stock(2)
PT. Kayubagus menjual kayu batangan untuk berbagai keperluan. Kayu batangan yang dijual oleh PT.Kayubagus memiliki panjang 4 meter, 6 meter dan 8 meter. Perusahaan yang memasok kayu ke PT.Kayubagus mengirimkan kayu dengan panjang 18 meter sehingga sebelum dijual kayu-kayu tersebut harus dipotong terlebih dahulu. Dalam memotong kayu-kayu tersebut PT.Kayubagus menetapkan 7 pola pemotongan sebagai berikut:
PT.Kayubagus menerima order dari berbagai konsumen dengan panjang dan jumlah yang berbeda-beda, misalnya jika PT.kayubagus menerima order 100 batang dengan panjang 4 meter, 50 batang dengan panjang 6 meter, dan 25 batang dengan panjang 8 meter. Berapa banyaknya batangan kayu (yang memiliki panjang 18 meter) yang harus dipotong dengan pola pemotongan 1? Pola pemotongan 2? Pola pemotongan 3? dan seterusnya supaya banyaknya sisa pemotongan(limbah) sesedikit mungkin. Pemilihan kombinasi pola pemotongan akan menentukan banyaknya sisa pemotongan(limbah kayu) yang dibuang atau dengan kata lain pola pemotongan harus dipilih sedemikian rupa sehingga sisa pemotongan (limbah kayu) menjadi sesedikit mungkin.
Pola Pemotongan 1 2 3 4 5 6 7
4 meter 4 3 2 1 1 0 0
6 meter 0 1 0 2 1 3 0
8 meter 0 0 1 0 1 0 2
Sisa (limbah) 2 0 2 2 0 0 2
Jika misalnya PT.kayubagus menerima satu order saja dan order tersebut meminta 100 batang kayu dengan panjang 6 meter maka PT.Kayubagus akan memotong persediaan kayunya yang memiliki panjang 18 meter dengan pola pemotongan 6 sehingga tidak ada limbah sama sekali (tidak ada sisa kayu yang harus dibuang).
Distribusi •
• •
•
Latihan 1
Sebuah perusahaan Air Cargo memiliki 8 pesawat tipe 1, 15 pesawat tipe 2, dan sebelas pesawat tipe 3. Pesawat tipe 1 mampu mengangkut barang seberat 45 ton, pesawat tipe 2 mampu mengangkut barang seberat 7 ton dan pesawat tipe 3 hanya mampu mengangkut 5 ton. Hari ini perusahaan harus mengirim barang seberat 20 ton ke kota A dan 28 ton ke kota B. Setiap pesawat hanya bisa terbang sekali dalam sehari. Biaya menerbangkan pesawat dari terminal (bandara) ke kota A dan B adalah sebagai berikut: Pesawat 1
Pesawat 2
Pesawat 3
Kota A
23
15
2
Kota B
58
20
3
Pesawat manakah yang harus terbang? Dan kemanakah tujuannya?
Perusahaan A adalah perusahaan yang bergerak pada bisnis rumah makan cepat saji (fast food). Perusahaan ini berkembang dengan pesat sehingga berencana untuk membuka cabang baru di beberapa kota besar di Indonesia termasuk Surabaya. Di kota Surabaya terdapat delapan lokasi potensial yang dapat dipilih oleh perusahaan. Lokasi cabang yang dipilih harus bisa memastikan bahwa jika ada konsumen yang memesan maka pesanan harus sudah sampai ke konsumen tidak lebih dari 30 menit setelah pesanan diterima.Diperlukan 10 menit untuk menyiapkan pesanan konsumen. Perusahaan berusaha untuk membuka cabang sesedikit mungkin namun bisa mengcover semua permintaan di kota Surabaya. Berikut data lokasi dan waktu tempuh ke setiap daerah. ke1 2 3 4 5 6 7
1 0 10 20 12 20 15 14
2 10 0 25 35 20 10 23
3 20 25 0 15 15 20 17
4 12 35 15 0 15 25 20
5 20 20 15 15 0 14 25
6 15 10 20 25 14 0 24
7 14 23 17 20 25 24 0
Modelkan masalah tersebut!
Latihan 2 Selain waktu tempuh, perusahaan juga memilih lokasi berdasarkan besarnya kapasitas cabang dan besarnya permintaan pada setiap lokasi. Kapasitas cabang yang bisa didirikan disetiap daerah dan permintaan adalah sebagai berikut: Lokasi Kapasitas Permintaan 1 2 3 4 5 6 7
2000 1500 3000 2000 2500 2000 1000
4000 3000 1000 1000 1500 2000 1000
a) Modifikasi model anda! b) Tentukan nilai-nilai parameter yang bisa anda coba untuk melakukan validasi! c) Tentukan solusi dari nilai-nilai parameter yang anda cobakan tadi berdasarkan intuisi anda!
Solving ILPs Solve LP relaxation of the ILP. Case-1: LP relaxation solution satisfies integrality constraint.
Case-2: LP relaxation solution does not satisfy the integrality constraint.
7
19/11/2013
Dealing with Case-2 Branch and Bound
Cutting Plane Method.
1
2
8
