Modul 8. PENELITIAN OPERASIONAL
INTEGER PROGRAMMING
Oleh : Eliyani
PROGRAM KELAS KARYAWAN PROGRAM STUDI TEKNIK INDUSTRI FAKULTAS TEKNOLOGI INDUSTRI UNIVERSITAS MERCU BUANA http://www.mercubuana.ac.id JAKARTA 2007
2
PENDAHULUAN
Salah satu asumsi teknik LP adalah divisibility atau fractionality, yaitu setiap variabel dapat terjadi pada nilai non negatif atau kontinyu. Pada beberapa kasus, asumsi ini tidak realistik dan tak dapat diterima. Misalnya suatu solusi menunjukkan bahwa banyaknya mesin yang harus dibuat adalah 3,35 mesin. Tentu saja solusi ini tidak bermakna praktis. Yang harus dibuat bisa 3 atau 4 mesin. Atau solusi yang diharapkan adalah yang bernilai 1 atau 0 di mana angka 1 mewakili setuju dan angka 0 berarti pekerjaan tidak diteruskan. Pendekatan pembulatan dari solusi nilai pecah dari LP dapat tidak memenuhi semua kendala dan menyimpang cukup jauh dari solusi bulat yang tepat. Integer programming merupakan teknik LP dengan tambahan persyaratan semua atau beberapa variabel bernilai bulat non negatif tetapi tidak perlu bahwa parameter model juga bernilai bulat. Terdapat 3 jenis integer programming: 1. Pure (all) integer programming Jika model mengharapkan semua variabel basis bernilai integer (bulat positif atau nol) 2. Mixed integer programming Jika model hanya mengharapkan variabel-variabel tertentu bernilai bulat. 3. Zero one integer programming Jika model hanya mengharapkan nilai 0 atau 1 untuk variabelnya. Terdapat beberapa solusi pendekatan integer programming, dua di antaranya adalah metode branch and bound dan metode cutting plane (algoritma bidang pemotong).
METODE BRANCH AND BOUND
Metode ini menjadi kode komputer standar untuk integer programming dan lebih efisien dibandingkan dengan metode cutting plane. Metode ini pertama kali dikembangkan oleh Land and Doig kemudian dilanjutkan oleh peneliti lain. Teknik ini dapat diterapkan untuk pure maupun mixed integer programming,
http://www.mercubuana.ac.id
3
Langkah-langkah Agar lebih mudah dipahami, perhatikan penyelesaian masalah berikut:
Maksimumkan
Z = 3X1 + 5X2
Dengan syarat :
2X1 + 4X2 25 X1 2X2
8 10
X1, X2 non negatif integer
1. Selesaikan dengan metode LP baik grafik maupun simpleks, diperoleh solusi optimum kontinyu X1 = 8, X2 = 2,25 dan Z = 35,25. Perhatikan bahwa syarat yang harus dipenuhi adalah kedua variabel X 1 dan X2 bernilai bulat positif. Solusi optimum kontinyu tersebut dijadikan sebagai batas atas awal 2. Tetapkan batas bawah, yaitu solusi yang dibulatkan ke bawah, sehingga X1 = 8, X2 = 2 dan Z = 34 (nilai Z diperoleh dengan memasukkan nilai X 1 dan X2 yang baru). 3. Pilih nilai solusi pecah yang akan dicabangkan menjadi sub-sub masalah, dalam kasus ini yaitu X2 yang bernilai 2,25. 4. Untuk menghilangkan bagian pecah dari X2, dibuat dua kendala baru, yaitu : dua nilai bulat terdekat terhadap 2,25, yaitu 2 dan 3 sehingga dipunyai dua kendala baru yaitu X2 2 dan X3 3. Kendala ini untuk menghilangkan kemungkinan solusi nilai di antara 2 dan 3. Sehingga masalah dipecahkan menjadi dua bagian: Bagian A Maksimumkan
Z = 3X1 + 5X2
Dengan syarat :
2X1 + 4X2 25 X1 2X2 X2
8 10 (berlebih) 2
X1, X2 0
http://www.mercubuana.ac.id
4
Bagian B Maksimumkan
Z = 3X1 + 5X2
Dengan syarat :
2X1 + 4X2 25 X1 2X2 X2
8 10 3
X1, X2 0 5. Selesaikan bagian A maupun B dengan metode-metode LP tanpa pembatasan bilangan bulat. Diperoleh solusi : Bagian A : X1 = 8, X2 = 2 dan Z = 34 Bagian B : X1 = 6,5, X2 = 3 dan Z = 34,5 6. Walaupun solusi bagian A telah semuanya bulat, namun tetap perlu dilakukan pencarian lebih lanjut karena nilai fungsi tujuan pada bagian B lebih besar. Untuk itu, bagian B dibagi ke dalam dua sub bagian menjadi B1 dan B2 dengan X1 6 dan X2 7. Sub Bagian B1 Maksimumkan
Z = 3X1 + 5X2
Dengan syarat :
2X1 + 4X2 25 X1 2X2
8 (berlebih) 10
X2
3
X1
6
X1, X2 0
Sub Bagian B2 Maksimumkan
Z = 3X1 + 5X2
Dengan syarat :
2X1 + 4X2 25 X1 2X2
8 10
X2
3
X1
7
X1, X2 0
http://www.mercubuana.ac.id
5
7. Selesaikan sub bagian B1 maupun B2 dengan metode-metode LP tanpa pembatasan bilangan bulat. Diperoleh solusi : Sub Bagian B1 : X1 = 6, X2 = 3,25 dan Z = 34,25 Sub Bagian B2 : tidak layak 8. Karena sub bagian B1 menghasilkan nilai fungsi tujuan yang lebih besar dari 34 (batas atas bagian A) maka bagian B1 dapat dicabangkan lagi menjadi sub sub bagian B1a dan B1b dengan kendala masing-masing X2 3 dan X2 4. Sub Sub Bagian B1a
Maksimumkan
Z = 3X1 + 5X2
Dengan syarat :
2X1 + 4X2 25 X1 2X2
8 10 (berlebih)
X2
3
X1
6
X1, X2 0 Sub Sub Bagian B1b Maksimumkan
Z = 3X1 + 5X2
Dengan syarat :
2X1 + 4X2 25 X1 2X2
8 10
X2
4
X1
6
X1, X2 0
9. Selesaikan sub bagian B1a maupun B1b dengan metode-metode LP tanpa pembatasan bilangan bulat. Diperoleh solusi : Sub Sub Bagian B1a : X1 = 6, X2 = 3 dan Z = 33 Sub Sub Bagian B1b : X1 = 4,25, X2 = 4 dan Z = 33,5
10. Kedua solusi menghasilkan Z yang nilainya lebih kecil daripada nilai Z pada bagian A sehingga percabangan dihentikan atau proses pencarian
http://www.mercubuana.ac.id
6
solusi optimum selesai. Jadi solusi optimum untuk masalah ini dihasilkan oleh bagian A, yaitu : X1 = 8, X2 = 2 dan Z = 34.
Algoritma Pemotongan
Algoritma Pemotongan disebut juga dengan metode cutting plane. Salah satu tekniknya yang biasa diterapkan untuk pure integer programming adalah metode Gomory atau disebut juga metode Fraksional.
Langkah-langkah Untuk lebih mudah memahami langkah-langkah penyelesaian metode Gomory, perhatikan langkah-langkah penyelesaian contoh berikut:
Maksimumkan Z = 7X1 + 9X2 Dengan syarat: -X1 + 3X2 6 7X1 + X2 35 X1, X2 non negative integer Dengan metode simpleks, diperoleh solusi kontinyu optimumnya seperti pada Tabel 1.
Tabel 1. Solusi Kontinyu Optimum Basis
X1
X2
S1
S2
Solusi
Z
0
0
28/11
15/11
63
X2
0
1
7/22
1/22
7/2
X1
1
0
-1/22
3/22
9/2
1. Lihat apakah semua variabel basis (X1 dan X2) sudah bulat. Bila belum, seperti pada contoh ini, tambahkan kendala Gomory yang berupa variabel slack (Sg).
2. Sg diperoleh dengan rumus: Sg -fij W j = -fi di mana: fij = koefisien variabel non basis ke-j W j = variabel non basis ke-j
http://www.mercubuana.ac.id
7
fi
= bagian pecah variabel basis ke-i
Jadi, variabel basis Xi dapat dipecah menjadi bagian bulat dan bagian pecah. Contoh: X1 = 9/2 = 4 ½ sehingga f1 = ½ X2 = 7/2 = 3 ½ sehingga f2 = ½
Persamaan variabel basis yang dipilih sebagai kendala Gomory adalah persamaan basis yang memiliki nilai fi maksimum. Karena pada kasus ini nilai f1 dan f2 sama, maka bisa dipilih sembarang. Misalkan saja kita pilih X 2 sebagai Sg, maka : Sg – 7/22 S1 – 1/22 S2 = -1/2
Berdasarkan Tabel 1., persamaan untuk X2 adalah : X2 + 7/22 S1 + 1/22 S2 = 7/2
3. Susun tabel simpleks dengan penambahan kendala Gomory. Untuk kasus ini, disajikan pada Tabel 2.
Tabel 2. Tabel Simpleks dengan Penambahan Kendala Gomory Basis
X1
X2
S1
S2
Sg1
Sisi kanan
Z
0
0
28/11
15/11
0
63
X2
0
1
7/22
1/22
0
7/2
X1
1
0
-1/22
3/22
0
9/2
Sg1
0
0
-7/22
-1/22
1
-1/2
4. Gunakan metode dual simpleks untuk menghasilkan solusi atas masalah dengan kendala Gomory. Untuk kasus ini, hasilnya disajikan pada Tabel 3.
Tabel 3. Tabel Hasil Dual Simpleks Basis
X1
X2
S1
S2
Sg1
Solusi
Z
0
0
0
1
8
59
X2
0
1
0
0
1
3
X1
1
0
0
1/7
-1/7
32/7
S1
0
0
1
1/7
-22/7
11/7
http://www.mercubuana.ac.id
8
5. Karena solusi baru masih pecah, maka tambahkan lagi kendala Gomory baru. Persamaan X1 memiliki nilai f1 = 4/7, lebih besar dibandingkan f2 sehingga dijadikan kendala Gomory kedua, sehingga: Sg2 – 1/7 S2 – 6/7 Sg1 = -4/7
Nilai 6/7 Sg1 diperoleh dari: Pada Tabel 3. diperoleh : -1/7 = -1 + 6/7
6. Susun tabel simpleks dengan penambahan kendala Gomory kedua. Hasilnya disajikan pada Tabel 4.
Tabel 4. Tabel Simpleks dengan Penambahan Kendala Gomory Kedua
Basis
X1
X2
S1
S2
Sg1
Sg2
Sisi kanan
Z
0
0
0
1
8
0
59
X2
0
1
0
0
1
0
3
X1
1
0
0
1/7
-1/7
0
32/7
Sg1
0
0
1
1/7
-22/7
0
11/7
Sg2
0
0
0
-1/7
-6/7
1
-4/7
7. Gunakan metode dual simpleks untuk menghasilkan solusi atas masalah dengan kendala Gomory kedua. Untuk kasus ini, hasilnya disajikan pada Tabel 5.
Tabel 5.
http://www.mercubuana.ac.id
Tabel Hasil Dual Simpleks dengan Penambahan Kendala Gomory Kedua
Basis
X1
X2
S1
S2
Sg1
Sg2
Solusi
Z
0
0
0
0
2
7
55
X2
0
1
0
0
1
0
3
X1
1
0
0
0
-1
1
4
Sg1
0
0
1
0
-4
1
1
Sg2
0
0
0
1
6
-7
4
9
8. Tabel 5. menunjukkan bahwa solusi optimum bulat telah tercapai sehingga solusi untuk masalah tersebut yaitu : X1 = 4, X2 = 3 dan Z = 55..
http://www.mercubuana.ac.id
