BAB 2 LANDASAN TEORI
2.1 Perencanaan Produksi Produksi yang dalam bahasa inggris disebut production adalah keseluruhan proses yang dilakukan untuk menghasilkan produk atau jasa. Produk yang dihasilkan sebagai output dari proses tersebut dapat berupa produk akhir (finished product) yang sering disebut juga produk jadi, produk setengah jadi (work-in-process) atau bahan baku (raw materials) yang semuanya bersifat tangible (berwujud fisik). Jasa (services) adalah output yang bersifat intangible (berwujud non-fisik).
Aktifitas produksi sebagai suatu bagian dari fungsi organisasi perusahaan bertanggung jawab terhadap pengolahan bahan baku menjadi produk jadi yang dapat dijual. Untuk melaksanakan fungsi produksi tersebut diperlukan rangkaian kegiatan yang akan membentuk suatu sistim produksi.
Sistim produksi merupakan kumpulan dari sub-sistim yang saling berinteraksi dengan tujuan mentransformasi input produksi menjadi output produksi. Input produksi ini dapat berupa bahan baku, mesin, tenaga kerja, modal dan informasi sedangkan output produksi merupakan produk yang dihasilkan berikut hasil sampingannya seperti limbah, informasi, dan sebagainya. Sub-sistim dari sistim produksi tersebut antara lain adalah perencanaan dan pengendalian produksi, pengendalian kualitas, penentuan standar-standar operasi, penentuan fasilitas produksi, perawatan fasilitas produksi dan penentuan harga pokok produksi.
Tujuan akhir dari suatu perusahaan adalah untuk memperoleh keuntungan disamping tercapainya kelanjutan dan pengembangan usaha. Salah satu fungsi yang terpenting dalam mendukung usaha untuk mencapai tujuan tersebut adalah perencanaan produksi. Perencanaan produksi dapat didefinisikan sebagai proses untuk merencanakan aliran material yang masuk, mengalir dan keluar dari sistim
8
produksi atau operasi sehingga permintaan pasar dapat dipenuhi dengan jumlah yang tepat.
The American Production and Inventory Control Society mendefinisikan perencanaan produksi sebagai suatu kegiatan yang berkenaan dengan penentuan apa yang harus diproduksi, berapa banyak diproduksi, kapan diproduksi, dan apa sumber daya yang dibutuhkan untuk mendapatkan produk yang telah ditetapkan (Sinulingga, 2009).
Perencanaan produksi dilakukan dengan tujuan menentukan arah awal dari tindakan-tindakan yang harus dilakukan di masa mendatang, apa yang harus dilakukan, berapa banyak melakukannya, dan kapan harus melakukan. Karena perencanaan ini berkaitan dengan masa mendatang, maka perencanaan disusun atas dasar perkiraan yang dibuat berdasarkan data masa lalu dengan menggunakan beberapa asumsi.
Kegunaan dari pelaksanaan perencanaan produksi adalah: 1.
Suatu perencanaan meliputi usaha untuk menetapkan tujuan yang dipilih untuk dicapai sehingga dengan adanya perencanaan produksi dapat memberikan arah bagi setiap kegiatan produksi. Dengan adanya kejelasan arah tersebut maka kegiatan akan dapat dilaksanakan dengan efektif.
2.
Dengan perencanaan produksi yang berisi formulasi tujuan yang hendak dicapai maka akan memungkinkan untuk mengetahui apakah tujuan tersebut telah tercapai atau tidak. Dengan demikian, koreksi-koreksi terhadap penyimpangan dari tujuan yang telah ditetapkan dapat diketahui secepatnya sehingga pemborosan dan usaha yang tidak menunjang pencapaian tujuan dapat dihindari.
3.
Memudahkan pelaksanaan kegiatan untuk mengidentifikasi hambatanhambatan yang mungkin muncul dalam usaha pencapaian tujuan tersebut.
4.
Menghindarkan pertumbuhan dan perkembangan yang tidak terkendali. Misalnya dalam pengembangan usaha selalu ada kecenderungan untuk
9
selalu menambah jumlah dan jenis tenaga kerja yang sudah dimiliki untuk memperbaiki mutu serta jumlah output.
2.2 Program Linier Konsep linear programming ditemukan dan diperkenalkan pertama kali oleh George Dantzig. Program linier merupakan suatu metode untuk membuat keputusan di antara berbagai aternatif kegiatan dibatasi oleh kendala tertentu. Keputusan yang diambil dinyatakan sebagai fungsi tujuan sedangkan kendalakendala yang dihadapi dalam membuat keputusan tersebut dinyatakan dalam bentuk fungsi-fungsi kendala. Fungsi tujuan dan fungsi kendala tersebut berupa fungsi linier, baik dalam bentuk persamaan maupun pertidaksamaan pada variabel-variabel keputusannya.
Bentuk umum dari permasalahan LP adalah: Maximum ππ ππ π₯π₯
Kendala: π΄π΄π΄π΄ β€ ππ
2.1
Beberapa contoh aplikasi LP yang telah berhasil diterapkan dalam bidang militer, industri, dan sosial adalah: 1.
Mengembangkan jadwal produksi yang bertujuan memuaskan konsumen terhadap produk yang dikonsumsikan dan pada saat yang sama dapat meminimalisasi biaya produksi dan persediaan.
2.
Penentuan kombinasi produk (product-mix), yaitu menentukan produk mana dari sejumlah alternatif kemungkinan produksi yang dapat memaksimalkan keuntungan.
3.
Penentuan sistim distribusi yang akan meminimalisasi biaya total pengiriman dengan menggunakan mobil box dari gudang ke berbagai pasar.
4.
Menganalisis portofolio investasi dari berbagai alternatif investasi dalam saham dan obligasi sehingga seorang investor dapat menentukan portofolio yang dapat memaksimumkan pengembalian investasi.
10
5.
Menentuan penjadwalan untuk melakukan aktifitas produksi bagi tenaga kerja di perusahaan.
2.2.1 Unsur β Unsur Program Linier Adapun unsur-unsur dalam program linier adalah: a.
Variabel Keputusan Variabel keputusan adalah variabel yang menguraikan secara lengkap keputusan-keputusan yang akan dibuat. Variabel keputusan ini tidak negatif.
b.
Fungsi Tujuan Adapun tujuan dalam program linier adalah masalah optimasi yakni tujuan memaksimumkan atau meminimumkan sesuatu di mana tingkat pencapaian tujuan ini dibatasi oleh kendala yang mencerminkan keterbatasan yang dimiliki.
c.
Kendala Tujuan Kendala merupakan batasan-batasan yang harus diperhatikan dalam penyelesaian program linier. Kendala tersebut dibuat dalam fungsi linier.
2.2.2 Asumsi Dasar Program Linier Dalam model program linier terdapat asumsi-asumsi yang harus dipenuhi agar permasalahan program linier menjadi absah, adapun asumsi program linier adalah sebagai berikut: 1.
Asumsi kesebandingan (proposionality) a.
Kontribusi setiap variabel keputusan terhadap fungsi tujuan adalah sebanding dengan nilai variabel keputusan.
b.
Kontribusi suatu variabel keputusan terhadap ruas kiri dari setiap pembatas juga sebanding dengan nilai variabel keputusan itu.
2.
Asumsi penambahan (additivity) a.
Kontribusi setiap variabel keputusan terhadap fungsi tujuan tidak bergantung pada nilai dari variabel keputusan yang lain.
11
b.
Kontribusi suatu variabel keputusan terhadap ruas kiri dari setiap pembatas bersifat tidak bergantung pada nilai dari variabel keputusan yang lain.
3.
Asumsi pembagian (divisibility) Dalam persoalan program linier, variabel keputusan boleh diasumsikan berupa bilangan pecahan.
4.
Asumsi kepastian (certainty) Setiap parameter, yaitu koefisien fungsi tujuan, ruas kanan, dan koefisien teknologi, diasumsikan dapat diketahui secara pasti.
2.3 Program Bilangan Bulat Linier Program bilangan bulat linier (Integer Linear Programming / ILP) adalah bentuk khusus dari permasalahan program linier di mana pada solusi optimalnya beberapa atau seluruh variabelnya dibatasi harus berupa bilangan bulat (integer) tak negatif. ILP digunakan untuk memodelkan permasalahan yang mengandung variabel keputusan yang harus bernilai integer, misalnya variabel yang menggambarkan jumlah orang atau jumlah unit produk yang akan diproduksi.
Permasalahan di mana seluruh variabelnya dibatasi harus berupa integer tak negatif disebut permasalahan program integer linier murni (Pure Integer Linear Programming / PILP). Jika hanya beberapa variabel saja yang harus bernilai integer, permasalahan ini disebut sebagai permasalahan integer linier campuran (Mixed Integer Linear Programming / MILP). Dalam suatu kondisi khusus di mana seluruh variabel keputusan dalam suatu masalah harus bernilai 0 atau 1 maka permasalahan tersebut disebut Binary Integer Linear Programming (BILP).
Bentuk umum dari ILP adalah: ππππππππ ππππππππ ππππππ βΆ
ππ = οΏ½
ππ
ππ =1
ππππ π₯π₯ππ
12
πΎπΎπΎπΎπΎπΎπΎπΎπΎπΎπΎπΎπΎπΎ:
οΏ½
ππ
ππ =1
π₯π₯ππ β₯ 0
ππππππ π₯π₯ππ = ππππ
π₯π₯ππ β ππ + keterangan: ππ = Fungsi tujuan π₯π₯ππ
ππ = 1,2,3, β¦ , ππ;ππ = 1,2,3, β¦ , ππ
2.2
= Variabel keputusan j
ππππ
= Koefisien dari variabel keputusan j
ππππ
= Sumber daya yang tersedia dalam kendala ke-i
ππππππ = Koefisien dari variabel keputusan dalam kendala ke-i Banyak permasalahan yang dapat dimodelkan sebagai program integer, misalnya dalam ilmu pengetahuan, teknologi, bisnis dan lingkungan, oleh karena itu tidak mengherankan bahwa banyak metode penyelesaian dan kode yang muncul untuk menyelesaikan program integer. Beberapa metode dapat digunakan
untuk seluruh tipe ILP dan beberapa metode hanya diperuntukkan untuk menyelesaikan suatu masalah ILP tertentu.
Pada dasarnya, solusi integer optimal berada dekat dengan solusi program linier. Titik-titik yang berada dalam daerah fisibel (feasible region) berupa titiktitik yang fisibel sebagai koordinat yang bernilai integer disebut integer lattice points. Pemecahan persoalan LP biasa terletak pada batas luar dari daerah fisibelnya, khususnya pada titik-titik ekstrimnya yang disebut vertex.
Misalkan daerah fisibel tersebut dapat diciutkan menjadi convex hull of the feasible lattice points, di mana convex hull merupakan daerah convex terkecil yang memuat semua titik-titik lattice. Convex hull diperoleh sebagai hasil modifikasi dari persoalan asli dengan jalan menambahkan kendala linier baru. Persoalan baru ini mencakup dua aspek berikut:
13
1.
Mencakup setiap pemecahan integer yang fisibel terhadap persoalan asli. Jadi pemecahan yang menghasilkan bilangan-bilangan bulat atau integer masih merupakan penyelesaian dari persoalan LP yang asli.
2.
Setiap pemecahan dasar dari persoalan baru merupakan pemecahan integer. Pemecahan dasar optimal dari persoalan yang baru juga merupakan pemecahan optimal dari permasalahan LP yang asli namun berupa integer.
Dalam prakteknya sukar untuk memotong daerah fisibel menjadi convex hull of the feasible lattice points sehingga diperlukan metode yang terdiri dari urutan langkah-langkah dengan jalan selalu menambahkan kendala baru terhadap persoalan asli sebagai kelanjutan dari hasil perhitungan sebelumnya. Konsep inilah yang diterapkan dalam metode branch and bound, cutting plane dan metode branch and cut.
2.4 Metode Simpleks Masalah program linier berkembang pesat setelah ditemukan suatu metode penyelesaian program linier yaitu metode simpleks yang ditemukan oleh George Dantzig pada tahun 1947. Permasalahan linier sederhana yang mengandung dua atau tiga variabel dapat diselesaikan dengan menggunakan metode grafik. Namun untuk masalah program linier yang mengandung lebih dari tiga variabel, metode grafik tidak dapat digunakan sehingga diperlukan metode yang dapat digunakan untuk menyelesaiakan masalah program linier yang rumit. Metode simpleks adalah metode yang dapat menyelesaiakan masalah program linier dengan jumlah variabel yang besar.
Penyelesaian model program linier dengan menggunakan metode simpleks memerlukan pengubahan model formulasi ke dalam bentuk standar dengan syarat sebagai berikut: 1.
Semua kendala berbentuk pertidaksamaan yang dibatasi oleh kendala lebih kecil dari (β€) diubah ke dalam bentuk persamaan dengan menambahkan slack
14
variable. Untuk pertidaksamaan yang dibatasi oleh tanda lebih besar (β₯) diubah ke dalam bentuk persamaan dengan menambahkan surplus variable. 2.
Nilai ruas kanan setiap kendala bertanda positif, jika nilai ruas kanan dari suatu kendala bertanda negative maka harus diubah menjadi positif dengan mengalikan pertidaksamaan dengan -1.
3.
Semua variabel keputusan bernilai nonnegatif.
Ada beberapa istilah yang sangat sering digunakan dalam metode simpleks, di antaranya: 1.
Iterasi adalah tahapan perhitungan di mana nilai dalam perhitungan itu tergantung dari nilai tabel sebelumnya.
2.
Variabel nonbasis adalah variabel yang nilainya diatur menjadi nol pada sembarang iterasi. Dalam terminologi umum, jumlah variabel nonbasis selalu sama dengan derajat bebas dalam sistim persamaan.
3.
Variabel basis merupakan variabel yang nilainya bukan nol pada sembarang iterasi. Pada solusi awal, variabel basis merupakan variabel slack (jika fungsi kendala merupakan pertidaksamaanβ€
) atau variabel buatan (jika fungsi
kendala menggunakan pertidaksamaan β₯ atau =). Secara umum, jumlah variabel basis selalu sama dengan jumlah fungsi pembatas (tanpa fungsi non negatif). 4.
Solusi atau nilai kanan merupakan nilai sumber daya pembatas yang masih tersedia. Pada solusi awal, nilai kanan atau solusi sama dengan jumlah sumber daya pembatas awal yang ada, karena aktivitas belum dilaksanakan.
5.
Variabel slack adalah variabel yang ditambahkan ke model matematika kendala untuk mengkonversikan pertidaksamaan β€ menjadi persamaan (=). Penambahan variabel ini terjadi pada tahap inisialisasi. Pada solusi awal, variabel slack akan berfungsi sebagai variabel basis.
6.
Variabel surplus adalah variabel yang dikurangkan dari model matematika kendala untuk mengkonversikan pertidaksamaan β₯ menjadi persamaan (=). Penambahan ini terjadi pada tahap inisialisasi. Pada solusi awal, variabel surplus tidak dapat berfungsi sebagai variabel basis.
15
7.
Variabel buatan adalah variabel yang ditambahkan ke model matematika kendala dengan bentukβ₯ atau = untuk difungsikan sebagai variab el basis awal. Penambahan variabel ini terjadi pada tahap inisialisasi. Variabel ini harus bernilai 0 pada solusi optimal, karena kenyataannya variabel ini tidak ada. Variabel hanya ada di atas kertas.
8.
Kolom pivot (kolom kerja) adalah kolom yang memuat variabel masuk. Koefisien pada kolom ini akan menjadi pembagi nilai kanan untuk menentukan baris pivot (baris kerja).
9.
Baris pivot (baris kerja) adalah salah satu baris dari antara variabel basis yang memuat variabel keluar.
10. Elemen pivot (elemen kerja) adalah elemen yang terletak pada perpotongan kolom dan baris pivot. Elemen pivot akan menjadi dasar perhitungan untuk tabel simpleks berikutnya.
2.4.1 Langkah-Langkah Metode Simpleks Algoritma metode simpleks untuk persoalan maksimasi: 1.
Konversikan formulasi model program linier ke dalam bentuk standar.
2.
Cari Solusi Basis Feasible (BFS).
3.
Jika seluruh variabel nonbasis (NBV) mempunyai koefisien nonnegatif (artinya berharga positif atau nol) pada baris fungsi tujuan [baris persamaan ππ
yang biasa disebut baris 0 atau baris (ππππ β πΆπΆππ )], maka BFS sudah optimal. Jika pada baris 0 masih ada variabel dengan koefisien negatif, pilihlah salah satu variabel yang mempunyai paling negatif pada baris 0 itu. Variabel ini akan memasuki status variabel basis, karena itu variabel ini disebut sebagai variabel yang masuk basis (entering variable, disingkat EV). 4.
Hitung rasio dari ruas kanan atau (koefisien EV) pada setiap baris di mana EV mempunyai koefisien positif. Variabel basis pada baris pembatas dengan rasio positif terkecil akan berubah status menjadi variabel nonbasis. Variabel ini kemudian disebut sebagai variabel yang meninggalkan basis (leaving variable, disingkat LV).
16
5.
Lakukan operasi baris elementer (ERO) untuk membuat koefisien EV pada baris dengan rasio positif terkecil ini menjadi bernilai 1 dan bernilai 0 pada baris-baris lainnya.
6.
Kembali ke langkah 3.
2.5 Metode Dual Simpleks Apabila pada suatu iterasi diperoleh persoalan program linier yang sudah optimum (berdasarkan kondisi optimalitas), tetapi belum fisibel (ada pembatas nonnegatif yang tidak terpenuhi), maka persoalan tersebut harus diselesaikan dengan menggunakan metode dual Simpleks. Syarat digunakannya metode ini adalah bahwa seluruh pembatas harus merupakan ketidaksamaan yang bertanda (β€), sedangkan fungsi tujuan bisa berupa maksimasi atau minimasi. Pada dasarnya metode dual Simpleks ini menggunakan tabel yang sama seperti metode simpleks pada primal, tetapi leaving dan entering variable-nya ditentukan sebagai berikut: 1.
Leaving variable (kondisi fisibilitas) Yang menjadi leaving variable pada dual Simpleks adalah variabel basis yang memiliki harga negatif terbesar. Jika semua variabel basis telah berharga positif atau nol, berarti keadaan fisibel telah tercapai.
2.
Entering variable (kondisi optimalitas) a.
Tentukan perbandingan (rasio) antara koefisien persamaan z dengan koefisien persamaan leaving variable. Abaikan penyebut yang positif atau nol. Jika semua penyebut berharga positif atau nol, berarti persoalan yang bersangkutan tidak memiliki solusi fisibel.
b.
Untuk persoalan minimasi, entering variable adalah variabel dengan rasio terkecil, sedangkan persoalan maksimasi, entering variable adalah variabel dengan rasio absolut terkecil.
17
2.6 Metode Branch and Bound Metode branch and bound pertama kali dkembangkan pada tahun 1960 oleh Land dan G. Doig yang digunakan untuk menyelesaikan masalah mixed integer linear programming dan pure integer linear programming secara umum. Selanjutnya pada tahun 1965 E. Balas mengembangkan algoritma tambahan untuk menyelesaiakan masalah binary integer linear programming.
Metode branch and bound awalnya hanya digunakan untuk menyelesaikan masalah program integer. Setelah diteliti lebih lanjut, ternyata metode ini juga dapat digunakan untuk menyelesaikan masalah lainnya seperti traveling salesman problem, scheduling dan sebagainya. Ide mendasar dari metode ini adalah membagi daerah layak menjadi beberapa sub-bagian yang mengandung titk-titik fisibel dengan koordinat integer dengan menambahkan kendala tambahan kemudian menyelesaikannya.
Untuk
menyelesaikan
suatu
masalah
program
integer
dengan
menggunakan metode branch and bound, langkah pertama adalah mengabaikan kendala integer dari permasalahan awal sehingga terbentuk permasalahan LP relaksasi kemudian diselesaikan. Banyak metode yang dapat digunakan untuk menyelesaiakan permasalahan LP relaksasi. Namun, metode yang umum digunakan adalah metode simpleks. Jika permasalahan tersebut tidak mempunyai penyelesaian optimum yang bernilai integer, maka dua kendala baru dibentuk. Kendala tersebut adalah batas atas dan bawah dari variabel yang dibatasi harus bernilai integer namun belum bernilai integer.
Konsep dasar dari metode branch and bound adalah pengamatan terhadap tiap-tiap nilai π₯π₯ππ , di mana π₯π₯ππ adalah variabel yang dibatasi harus bernilai integer. Jika nilai π₯π₯ππ belum integer, maka masalah awal dibagi menjadi dua masalah baru
dengan menambahkan dua kendala baru yaitu, οΏ½π₯π₯ππ οΏ½ β€ π₯π₯ππ dan π₯π₯ππ β€ οΏ½π₯π₯ππ οΏ½ + 1 di
mana οΏ½π₯π₯ππ οΏ½ adalah integer terdekat yang lebih kecil dari π₯π₯ππ . Proses inilah yang dinamakan branching (pencabangan). Dalam kasus maksimasi, solusi awal dijadikan sebagai batas atas (upper bound). Penambahan pertidaksamaan sebagai
18
pencabangan masalah akan mengakibatkan berkurangnya nilai fungsi tujuan pada solusi optimal.
Sebagai salah satu hasil pencabangan variabel yang belum integer pada setiap cabang, satu dari dua kejadian berikut akan terjadi. Yang pertama, solusi yang diperoleh tidak memenuhi syarat integer dari variabel yang dicabangkan, dan memperoleh nilai fungsi objektif yang kurang sesuai dibandingkan dengan pencabangan lain yang semua solusinya sudah integer, dalam kasus ini pencabangan dilanjutkan. Yang kedua, mungkin diperoleh solusi lain yang sudah memenuhi syarat integer, dalam kasus ini pencabangan dihentikan.
Terdapat dua tahap yang dipakai dalam algoritma branch and bound, yaitu: 1.
Pencabangan, yaitu mempartisi masalah tersebut menjadi beberapa submasalah dengan cara menambahkan kendala yang merupakan syarat perlu untuk mencari solusi integer fisibel tanpa mengubah himpunan solusi integer semula.
2.
Pembatasan, yaitu nilai fungsi objektif dari suatu sub-masalah yang mempunyai solusi integer dipakai sebagai batas nilai fungsi objektif dari submasalah lainnya.
Branch and bound adalah algoritma yang paling umum digunakan untuk menyelesaikan masalah integer programming. Algoritma branch and bound juga telah banyak digunakan sebagai kode program computer, misalnya OSL, LAMPU, dan LINDO.
Berikut
ini
adalah
langkah-langkah
penyelesaian
suatu
masalah
maksimisasi dengan metode branch and bound: 1.
Selesaikan masalah program linier relaksasi dengan metode simpleks.
2.
Teliti solusi optimalnya, jika variabel keputusan yang diharapkan adalah integer, solusi optimum integer telah tercapai. Jika satu atau lebih variabel keputusan yang diharapkan ternyata bukan integer, lanjutkan ke langkah 3.
19
3.
Jadikan solusi pada penyelesaian langkah 1 menjadi batas atas dan untuk batas bawahnya merupakan solusi yang variabel keputusannya telah dibulatkan (roundedβdown).
4.
Pilih variabel yang mempunyai nilai pecahan terbesar (artinya bilangan desimal terbesar) dari masing-masing variabel untuk dijadikan pencabangan ke dalam sub-masalah. Tujuannya adalah untuk menghilangkan solusi yang tidak memenuhi persyaratan integer dalam masalah itu. Pencabangan itu dilakukan secara mutually exclusive untuk memenuhi persyaratan integer dengan jaminan tidak ada solusi fisibel (layak) yang diikutsertakan.
5.
Untuk setiap sub-masalah, nilai optimum fungsi tujuan ditetapkan sebagai batas atas. Solusi optimum yang dibulatkan menjadi batas bawah (solusi yang sebelumnya tidak bulat kemudian dibulatkan). Sub-masalah yang memiliki batas atas kurang dari batas bawah yang ada, tidak diikutsertakan pada analisa selanjutnya. Suatu solusi integer fisibel (layak) adalah sama baik atau lebih baik dari batas atas untuk setiap sub-masalah yang dicari. Jika solusi yang demikian terjadi, suatu sub-masalah dengan batas atas terbaik dipilih untuk dicabangkan. Kembali ke langkah 4.
2.7 Metode Cutting Plane Metode cutting plane yang digunakan untuk menyelesaikan masalah secara umum, pertama kali dikemukakan oleh Gomory (1963). Metode cutting plane merupakan metode yang digunakan untuk menyelesaikan program integer linier, baik integer murni maupun campuran dengan penambahan batasan baru yang disebut gomory. Batasan gomory diberikan jika nilai dari variabel keputusan belum integer (bernilai pecahan). Batasan-batasan tersebut secara efektif akan menyingkirkan beberapa ruang penyelesaian yang tidak berisi titik integer yang layak, tetapi tidak pernah menyingkirkan satupun titik integer yang layak (Taha, 1996).
Langkah-langkah prosedur gomory diringkas seperti berikut:
20
1.
Selesaikan masalah program integer dengan menggunakan metode simpleks. Masalah sederhana dapat diselesaikan dengan pendekatan grafik, sehingga pendekatan gomory kurang efisien.
2.
Periksa solusi optimum. Jika semua variabel basis memiliki nilai integer, solusi optimum integer telah diperoleh dan proses solusi telah berakhir. Jika satu atau lebih variabel basis masih meiliki nilai pecah, teruskan ke tahap 3.
3.
Buatlah suatu batasan gomory dan cari solusi optimum melalui prosedur dual Simpleks. Kembali ke tahap 2 (Taha, 1996).
Misalnya diberikan sebuah permasalahan integer programming berikut:
Tabel 2.1 Tabel Optimum Masalah Program Linier Basis π§π§ π₯π₯1 . . . π₯π₯ππ . . . π₯π₯ππ
π₯π₯1 0 1 . . . 0 . . . 0
β¦ β¦ β¦ . . . β¦ . . . β¦
π₯π₯ππ 0 0 . . . 1 . . . 0
π₯π₯ππ 0 0 . . . 0 . . . 1
β¦ β¦ β¦ . . . β¦ . . . β¦
π€π€1 πποΏ½1 πΌπΌ11 . . . πΌπΌππ1 . . . 1 πΌπΌππ
β¦ β¦ β¦ . . . β¦ . . . β¦
π€π€ππ πποΏ½ππ ππ πΌπΌ1 . . . ππ πΌπΌππ . . . ππ πΌπΌππ
β¦ β¦ β¦ . . . β¦ . . . β¦
π€π€ππ ππππ οΏ½οΏ½οΏ½ πΌπΌ1ππ . . . πΌπΌππππ . . . ππ πΌπΌππ
Hasil π½π½0 π½π½1 . . . π½π½ππ . . . π½π½ππ
Tentukan baris sumber dengan menentukan baris variabel keputusan yang
akan dibulatkan. Jika lebih dari satu, dipilih nilai pecahan terbesar. ππ
misalkan:
ππ
π₯π₯ππ = π½π½ππ β οΏ½ πΌπΌππ π€π€ππ ; ππ =1
π½π½ππ tidak integer
π½π½ππ = [π½π½ππ ] + ππππ
di mana:
ππ
ππ
πΌπΌππ = οΏ½πΌπΌππ οΏ½ + ππππππ
[π½π½ππ ] adalah integer terbesar sehingga [π½π½ππ ] β€ π½π½ππ . ππ
ππ
ππ
οΏ½πΌπΌππ οΏ½ adalah integer terbesar sehingga οΏ½πΌπΌππ οΏ½ β€ πΌπΌππ .
2.3
21
Disimpulkan bahwa 0 < ππππ < 1 dan 0 < ππππππ < 1, yang mana ππππ dan ππππππ
adalah pecahan positif, sehingga: ππ
ππ
π₯π₯ππ = π½π½ππ β οΏ½ πΌπΌππ π€π€ππ ππ =1
ππ
ππ
π₯π₯ππ = [π½π½ππ ] + ππππ β οΏ½οΏ½οΏ½πΌπΌππ οΏ½ + ππππππ οΏ½π€π€ππ ππ =1 ππ
ππ
π₯π₯ππ = [π½π½ππ ] + ππππ β οΏ½οΏ½πΌπΌππ οΏ½π€π€ππ + ππππππ π€π€ππ ππ
ππ =1
ππ
ππ
ππππ β οΏ½ ππππππ π€π€ππ = π₯π₯ππ β [π½π½ππ ] + οΏ½οΏ½πΌπΌππ οΏ½π€π€ππ ππ =1
ππ =1
2.4
Agar semua variabel π₯π₯ππ dan π€π€ππ adalah integer, maka sisi kanan dari
Persamaan 2.4 haruslah integer yang berakibat sisi kiri juga harus integer. Karena ππππππ β₯ 0 dan π€π€ππ β₯ 0 untuk semua i dan j maka: ππ
akibatnya,
οΏ½ ππππππ π€π€ππ β₯ 0 ππ =1 ππ
ππππ β οΏ½ ππππππ π€π€ππ β€ ππππ β€ 1 ππ =1
karena ππππ β βππππ=1 ππππππ π€π€ππ harus bernilai integer, satu kondisi untuk memenuhi sifat integer ini menjadi:
ππ
ππππ β οΏ½ ππππππ π€π€ππ β€ 0 ππ
ππ =1
ππππ β οΏ½ ππππππ π€π€ππ + ππππ ππ = 0 ππ =1
batasannya dapat ditulis dalam bentuk: ππ
ππππ ππ = οΏ½ ππππππ π€π€ππ β ππππ ππ =1
2.5
22
atau, ππ
ππππ ππ β οΏ½ ππππππ π€π€ππ = βππππ
2.6
ππ =1
Tabel 2.2 Setelah Penambahan Pemotongan Fraksional Basis π§π§ π₯π₯1 . . . π₯π₯ππ . . . π₯π₯ππ ππππ ππ
π₯π₯1 0 1 . . . 0 . . . 0 0
β¦ β¦ β¦ . . . β¦ . . . β¦ β¦
π₯π₯ππ 0 0 . . . 1 . . . 0 0
β¦ β¦ β¦ . . . β¦ . . . β¦ β¦
π₯π₯ππ 0 0 . . . 0 . . . 1 0
π€π€1 πποΏ½1 πΌπΌ11 . . . πΌπΌππ1 . . . 1 πΌπΌππ βππππ1
β¦ β¦ β¦ . . . β¦ . . . β¦ β¦
π€π€ππ πποΏ½ππ ππ πΌπΌ1 . . . ππ πΌπΌππ . . . ππ πΌπΌππ βππππππ
β¦ β¦ β¦ . . . β¦ . . . β¦ β¦
π€π€ππ ππππ οΏ½οΏ½οΏ½ πΌπΌ1ππ . . . πΌπΌππππ . . . ππ πΌπΌππ βππππππ
ππππ ππ 0 0 . . . 0 . . . 1 1
Hasil π½π½0 π½π½1 . . . π½π½ππ . . . π½π½ππ βππππ
di mana ππππππ adalah variabel slack nonnegatif yang berdasarkan definisinya haruslah integer. Persamaan batasan ini mendefinisikan pemotong fraksional. Dari Tabel 2.2 π€π€ππ = 0 dan ππππππ = βππππ tidak layak. Ini berarti bahwa batasan baru
tersebut tidak dipenuhi oleh solusi yang diberikan. Metode dual Simpleks dapat dipergunakan untuk mengatasi ketidaklayakan ini yang setara dengan memotong bidang solusi ke arah solusi integer optimal.
Jika solusi baru (setelah menerapkan metode dual Simpleks) adalah integer, proses berakhir. Jika tidak, sebuah gomory baru ditambahkan dari tabel yang dihasilkan dan metode dual Simpleks kembali digunakan untuk mengatasi ketidaklayakan. Prosedur ini dilakukan sampai solusi integer dicapai. Jika di salah satu iterasi metode dual Simpleks menunjukkan bahwa tidak ada solusi layak, berarti masalah itu tidak memiliki solusi integer yang layak (Taha, 1996).
23
2.8 Metode Branch and Cut Banyak permasalahan optimisasi dapat diformulasikan sebagai masalah Integer Linear Programming (ILP). Masalah tersebut dapat diselesaikan dengan metode branch and bound dan metode branch and cut. Algoritma metode branch and cut dibuat dari kombinasi metode cutting-plane dengan metode branch and bound. Prosedur metode branch and cut adalah menyelesaikan rangkaian relaksasi program linier dari masalah integer linear programming. Metode cutting plane memperbaharui relaksasi dari masalah untuk lebih mendekati penyelesaian berupa integer, dan metode branch and bound memproses dengan membagi dan menyelesaikan (devide and conquer) masalah. Misalkan bahwa titik π₯π₯ β adalah solusi layak untuk linear programming. Jika
π₯π₯ β berada pada daerah integral, maka ππ merupakan solusi optimal untuk integer
linear programming sudah diperoleh. Jika tidak, maka nilai fungsi objektif merupakan batas atas dari nilai optimum, tetapi dibutuhkan penyelesaian lebih lanjut untuk memperoleh nilai optimum berupa integer. Dengan penambahan bidang pemotongan (cutting plane) atau membagi masalah tersebut menjadi bagian-bagian masalah (branch).
Mitchell (1999) menjelaskan bahwa secara umum algoritma branch and cut adalah sebagai berikut: 1.
Inisialisasi: nyatakan persoalan awal ke dalam bentuk ILP0 dan titik-titik aktif menjadi πΏπΏ = {πΌπΌπΌπΌπΌπΌ0 }. Tetapkan batas bawah menjadi π§π§ = ββ. Tetapkan
2.
π§π§ππ = +β untuk sebuah persoalan ππ β πΏπΏ.
Penghentian proses: jika πΏπΏ = β
maka solusi π₯π₯ β yang menghasilkan nilai π§π§
objektif yang terbaik merupakan solusi optimal. Jika tidak ditemukan π₯π₯ β 3. 4.
(misalnya, π§π§ = ββ) maka ILP tidak layak.
Pemilihan masalah: pilih dan hilangkan masalah πΌπΌπΌπΌπΌπΌππ dari L.
Relaksasi: selesaikan relaksasi program linier dari πΌπΌπΌπΌπΌπΌππ . Jika relaksasi tidak layak, tetapkan π§π§ππ = ββ dan lanjut ke langkah 6. Misalkan π§π§ merupakan nilai
objektif optimal dari relaksasi dan misalkan π₯π₯ ππππ merupakan jawaban optimal. Jika relaksasinya layak tetapkan π§π§ππ = π§π§.
24
5.
Tambahkan bidang pemotongan: jika diinginkan carilah bidang pemotongan yang akan memenuhi π₯π₯ ππππ , jika sudah ditemukan, tambahkan bidang
pemotongan tersebut pada relaksasi dan kembali ke langkah 4. 6.
Pengukuran dan pemangkasan: Jika π§π§ππ β€ π§π§ kembali ke langkah 2.
a.
Jika π§π§ππ > π§π§ dan π₯π₯ ππππ adalah integer yang layak, perbaharui nilai π§π§ dengan
b.
melakukan teknik rounded down berdasarkan nilai π§π§ππ , kemudian buang
7.
dari L seluruh masalah di mana π§π§ππ β€ π§π§, dan lanjut ke langkah 2. ππ =ππ
Pemilihan: misalkan οΏ½ππππππ οΏ½ππ =1 adalah partisi dari kumpulan kendala ππ ππ dari ππ =ππ
masalah πΌπΌπΌπΌπΌπΌππ . Tambahkan permasalahan οΏ½πΌπΌπΌπΌπΌπΌππππ οΏ½ππ =1 ke dalam L, di mana
πΌπΌπΌπΌπΌπΌππππ adalah πΌπΌπΌπΌπΌπΌππ dengan daerah layak yang terbatas pada ππππππ dan π§π§ππππ di mana
ππ = 1, β¦ , ππ ditetapkan ke dalam nilai π§π§ππ untuk permasalahan induk. di mana: ILP0
= Bentuk ILP dari permasalahan awal
πΌπΌπΌπΌπΌπΌππ
L
= Bentuk ILP dari sebuah permasalahan l β L
π§π§ππ
= Batas atas dari nilai fungsi tujuan suatu sub-masalah l β L
x*
= Solusi dari suatu sub-masalah
π₯π₯ ππππ
= Solusi optimal dari suatu sub-masalah
= Himpunan titik-titik aktif dari persoalan ILP
z
ππ ππ
= Batas bawah dari nilai fungsi tujuan
J=k
οΏ½S Lj οΏ½J=1 πΌπΌπΌπΌπΌπΌππππ
= Kendala dari masalah πΌπΌπΌπΌπΌπΌππ
= Partisi dari kumpulan kendala ππ ππ Dari masalah πΌπΌπΌπΌπΌπΌππ
= πΌπΌπΌπΌπΌπΌππ dengan daerah layak yang terbatas pada ππππππ dan π§π§ππππ di mana j = 1, β¦ , k
Pada algoritma branch and cut, diberikan L yang merupakan himpunan titik aktif pada pencabangan branch and cut. Nilai objektif terbaik yang diperoleh dari titik layak dinotasikan sebagai π§π§. Lebih lanjut, π§π§ππ adalah batas atas nilai
optimal dari sub-masalah. Nilai dari sub-masalah tersebut digunakan untuk
25
memperbaharui π§π§ππ . Dalam beberapa kondisi, sejumlah cutting plane ditemukan
pada langkah 5, biasanya cutting plane yang diperoleh dipilah dan yang ditambahkan pada persamaan adalah subsetnya. Sub-masalah yang terbentuk pada langkah 7 disebut sub-masalah anak dan sub-masalah pada node sebelumnya sebagai
sub-masalah
induknya.
Biasanya
pembagian
masalah
tersebut
menggunakan bentuk dari variabel penghubung π₯π₯ππ β€ ππ dan π₯π₯ππ β₯ ππ untuk suatu variabel π₯π₯ππ dan a merupakan integer. Kendala-kendala tersebut dapat diselesaikan
dengan berbagai metode untuk ILP. Secara khusus pada langkah awal
diselesaikan dengan metode simpleks, jawaban berikutnya diperoleh dengan metode dual Simpleks. Solusi dual untuk jawaban sub-masalah akhir adalah layak untuk sub-masalah awal. Lebih lanjut, ketika pemotongan (cut) ditambahkan pada langkah 5, juga memanfaaatkan iterasi dual Simpleks untuk mendapatkan solusi optimal yang integer. Cutting plane yang ditambahkan pada salah satu vertex dari pohon branch and cut mungkin tidak berlaku untuk sub-masalah lain. Dalam hal ini cut ini disebut cut lokal.
