Pemodelan Programasi Linier dan Solusi Manual Model Assignment week 08 W. Rofianto, ST, MSi
Model Transportasi Kota 1
2
3
Supply max (ton)
4
Pabrik 1
$ 2 /ton
$ 3 /ton
$ 1.5 /ton $ 2.5 /ton 900
Pabrik 2
$ 4 /ton
$ 3.5 /ton $ 2.5 /ton $ 3 /ton
Demand (ton)
300
450
500
750
350
Tujuan : Meminimumkan biaya untuk memenuhi permintaan di 4 kota. Model Programasi Linier Minimisasi : z = 2x11 + 3x12 + 1.5x13 + 2.5x14+ 4x21+ 3.5x22+ 2.5x23+ 3x24 Dgn Syarat : x11 + x12 + x13 + x14 ≤ 900
x11 + x21 = 300
x21 + x22 + x23 + x24 ≤ 750
x12 + x22 = 450
x11 , x12 , x13 , x14 , 21 , x22 , x23 , x24 ≥ 0
x13 + x23 = 500 x14 + x24 = 350 xij adalah jumlah barang yang dikirim dari pabrik i ke kota j (dalam ton)
Model Blending x11
Bahan 1 x13
x12
x21
x22
Bahan 2
Campuran 2
x23 x31 Bahan 3
x33 x41
Bahan 4
Campuran 1
x32 x42 x43
xij adalah jumlah bahan i pada campuran j (dalam liter)
Campuran 3
Tujuan : Mencari kombinasi bahan yang tepat agar diperoleh profit maksimum Catatan : 1. Diasumsikan pada pencampuran tidak ada loss. 2. Harga masing-masing bahan adalah $0.15; $0.18; $ 0.12 dan $0.14 per liter 3. Harga jual masing-masing campuran adalah $0.26; $0.22 dan $0.20 per liter 4. Total campuran yang ingin diproduksi adalah 5.000.000 liter 5. Kandungan bahan 2 di campuran 1 tidak boleh melebihi 40%, 6. Kandungan bahan 3 di campuran 2 minimal 25%, 7. Kandungan bahan 1 di campuran 3 harus tepat 30% 8. Kandungan total bahan 2 dan bahan 4 di campuran 1 minimum 60% 9. Ketersediaan bahan 2 hanya 1.500.000 liter 10.Ketersediaan bahan 3 hanya 1.000.000 liter 11.Campuran 1 yang harus diproduksi minimal 2.000.000 liter
Model Blending x11
Bahan 1 x13
x12
x21
x22
Bahan 2
Campuran 2
x23 x31 Bahan 3
x33 x41
Bahan 4
Campuran 1
x32 x42
Campuran 3
Tujuan : Mencari kombinasi bahan yang tepat agar diperoleh profit maksimum Catatan : 1. Diasumsikan pada pencampuran tidak ada loss. 2. Harga masing-masing bahan adalah $0.15; $0.18; $ 0.12 dan $0.14 per liter 3. Harga jual masing-masing campuran adalah $0.26; $0.22 dan $0.20 per liter
x43
Model Programasi Linier Maksimisasi : z = 0.26(x11 + x21+ x31 + x41) + 0.22 (x12 + x22+ x32 + x42) + 0.2(x13 + x23+ x33 + x43) – 0.15(x11 + x12 + x13) – 0.18 (x21+ x22+ x23) – 0.12(x31 + x32 + x33) – 0.14(x41 + x42+ x43)
Model Blending x11
Bahan 1 x13
x12
x21
x22
Bahan 2
Campuran 2
x23 x31 Bahan 3
x33 x41
Bahan 4
Campuran 1
x32 x42 x43
Campuran 3
Catatan : 4. Total campuran yang ingin diproduksi adalah 5.000.000 liter 5. Kandungan bahan 2 di campuran 1 tidak boleh melebihi 40%, 6. Kandungan bahan 3 di campuran 2 minimal 25%, 7. Kandungan bahan 1 di campuran 3 harus tepat 30% 8. Kandungan total bahan 2 dan bahan 4 di campuran 1 minimum 60% 9. Ketersediaan bahan 2 hanya 1.500.000 liter 10.Ketersediaan bahan 3 hanya 1.000.000 liter 11.Campuran 1 yang harus diproduksi minimal 2.000.000 liter
Dgn syarat : x11 + x12 + x13 + x21+ x22+ x23+ x31 + x32 + x33 + x41 + x42+ x43 = 5.000.000 x21 ≤ 0.4(x11 + x21+ x31 + x41) x32 ≥ 0.25(x12 + x22+ x32 + x42) x13 = 0.3(x13 + x23+ x33 + x43) x21 + x41 ≥ 0.6(x11 + x21+ x31 + x41)
x21 + x22 + x23 ≤ 1.500.000 x31 + x32 + x33 ≤ 1.000.000 x11 + x21+ x31 + x41 ≥ 2.000.000
x11 , x12 , x13 , x21 , x22 , x23 , x31 , x32 , x33 , x41 , x42 , x43 ≥ 0
Model Blending Maksimisasi : z = 0.11x11 + 0.07x12 + 0.05x13 + 0.08x21 + 0.04x22 + 0.02x23 + 0.13x31 + 0.1x32 + 0.08x33 + 0.12x41 + 0.08x42 + 0.06x43 Dgn syarat : x11 + x12 + x13 + x21+ x22+ x23+ x31 + x32 + x33 + x41 + x42+ x43 = 5.000.000 -0.4x11 + 0.6x21 - 0.4 x31 - 0.4 x41 ≤ 0 -0.25x12 - 0.25 x22 + 0.75x32 - 0.25 x42 ≥ 0 0.7x13 - 0.3 x23 - 0.3 x33 - 0.3 x43 = 0 -0.6x11 + 0.4x21- 0.6 x31 + 0.4x41 ≥ 0 x21 + x22 + x23 ≤ 1.500.000 x31 + x32 + x33 ≤ 1.000.000 x11 + x21+ x31 + x41 ≥ 2.000.000 x11 , x12 , x13 , x21 , x22 , x23 , x31 , x32 , x33 , x41 , x42 , x43 ≥ 0
Pemodelan Penempatan Sumber Daya (Assignment Model) Model ini berguna untuk menempatkan n sumber daya pada n tugas agar diperoleh hasil optimal. Asumsi 1 Tiap sumber daya hanya dialokasikan pada satu tugas Asumsi 2 Tiap tugas hanya dikerjakan oleh satu sumber daya Asumsi 3 Agar memudahkan pencarian solusi, jumlah sumber daya harus sama dengan jumlah tugas Salah satu metode yang populer untuk menyelesaikan persoalan assignment model adalah Hungarian method.
Solusi Assignment Model Misalkan pada suatu perusahaan diketahui data lamanya waktu yang dibutuhkan masing-masing pekerja dalam menyelesaikan satu jenis pekerjaan (dalam satuan hari). Tujuan yang ingin dicapai adalah penempatan pekerja pada pekerjaan untuk meminimumkan total waktu yang diperlukan untuk menyelesaikan semua pekerjaan. Pekerjaan Pekerja
1
2
3
4
1
14
13
17
14
2
16
15
16
15
3
18
14
20
17
4
20
13
15
18
Hungarian Method STEP 1 Tentukan tabel opportunity cost Opportunity Cost Table
Row-Reduced Cost Table
Pekerjaan
Pekerjaan
Pekerja
1
2
3
4
Pekerja
1
2
3
4
1
1
0
4
1
1
0
0
3
1
2
1
0
1
0
2
0
0
0
0
3
4
0
6
3
3
3
0
5
3
4
7
0
2
5
4
6
0
1
5
Hungarian Method STEP 2 Tentukan apakah penempatan optimal sudah diperoleh? (Jumlah garis = jumlah baris/jumlah kolom) Opportunity Cost Table
Pekerjaan Pekerja
1
2
3
4
1
0
0
3
1
2
0
0
0
0
3
3
0
5
3
4
6
0
1
5
Hungarian Method STEP 3 Lakukan revisi terhadap tabel opportunity cost lalu lakukan kembali langkah 2 Opportunity Cost Table
Pekerjaan Pekerja
1
2
3
4
1
0
1
3
1
2
0
1
0
0
3
2
0
4
2
4
5
0
0
4
Hungarian Method Penempatan Optimal Opportunity Cost Table Pekerjaan Pekerja
Penempatan
Waktu
0
Pekerja 1 – pekerjaan 1 Pekerja 2 – pekerjaan 4 Pekerja 3 – pekerjaan 2 Pekerja 4 – pekerjaan 3
14 15 14 15
4
2
Total waktu
58
0
4
1
2
3
4
1
0
1
3
1
2
0
1
0
3
2
0
4
5
0
Latihan Pekerjaan
Pekerjaan
Pekerja
1
2
3
4
Pekerja
1
2
3
4
1
8
20
15
17
1
0
12
7
9
2
15
16
12
10
2
5
6
2
0
3
22
19
16
30
3
6
3
0
14
4
25
15
12
9
4
16
6
3
0
Pekerjaan
Pekerjaan
Pekerja
1
2
3
4
Pekerja
1
2
3
4
1
0
9
7
11
1
0
9
7
9
2
3
1
0
0
2
5
3
2
0
3
6
0
0
16
3
6
0
0
14
4
14
1
1
0
4
16
3
3
0
Hungarian Method (Maksimisasi) Utuk menyelesaikan persoalan maksimisasi assignment model dengan hungarian method, caranya sama hanya saja pada saat melakukan reduksi baris pilih nilai terbesar untuk diselisihkan. Sales Rep.
Sales District 1
2
3
4
1
25
10
60
0
2
20
10
40
25
3
125
15
25
0
4
30
50
10
0
Kondisi Tidak Seimbang (Penambahan Dummy) Pekerjaan
Pekerjaan
Pekerja
1
2
3
4
Pekerja
1
2
3
4
1
14
13
17
14
1
14
13
17
14
2
16
15
16
15
2
16
15
16
15
3
18
14
20
17
3
18
14
20
17
4
0
0
0
0
Pekerjaan
Pekerjaan
Pekerja
1
2
3
Pekerja
1
2
3
4
1
14
13
17
1
14
13
17
0
2
16
15
16
2
16
15
16
0
3
18
14
20
3
18
14
20
0
4
20
13
15
4
20
13
15
0