makalah cutting plane
Post on 22-Oct-2015
379 Views
Preview:
TRANSCRIPT
INTEGER PROGRAMMING WITH CUTTING PLANE METHOD
Disusun Oleh :
Arina Noviani 118100010
Fathurahman Alhikmah 118100027
Ali Hasym 118100029
INTEGER PROGRAMMING WITH CUTTING PLANE METHOD 2012
KATA PENGANTAR
Puji dan syukur kami panjatkan kehadirat Alloh SWT, atas limpahan rahmat
dan hidayah-Nya kami dapat menyelesaikan tugas ini yang berjudul “Integer
Programming with Cutting Plane”
Makalah ini dibuat guna memenuhi salah satu tugas Mata Kuliah Riset
Operasi . Pada kesempatan kali ini kami mengucapkan terima kasih yang sebesar –
besarnya kepada pihak yang telah mebantu terselesaikannya tugas ini ,terutama
kepada dosen yang telah memberikan materi tentang tugas ini ,juga kepada orang
tua kami yang telah memberikan dorongan dan do’a kepada kami sehingga dapat
terselesaikanya tugas ini dengan baik. Semoga apa yang telah mereka berikan
mendapat balasan dari Alloh SWT.
Kami menyadari sepenuhnya bahwa makalah ini masih banyak kekurangan
dan kesalahan.Oleh karena itu dengan segala kerendahan hati , kami meminta
uluran saran dan kritiknya yang bersifat mebangun demi perbaikan tugas ini.
Akhir kata kami berharap makalah ini dapat memenuhi tugas yang telah
ditentukan, dan semoga karya tulis ini dapat menambah wawasan bagi pembaca .
atas segala perhatiannya kami ucapkan banyak terima kasih.
Bandung, Desember 2012
Penyusun
1
INTEGER PROGRAMMING WITH CUTTING PLANE METHOD 2012
PENDAHULUAN
Suatu permasalahan perencanaan linier biasanya menuntut solusi yang optimum
agar diperoleh kondisi optimal yang di inginkan. Biasanya suatu permasalahan perencanaan
linier ,menginginkan variabel keputusanya berupa integer , agar jawaban menjadi realistik.
Integer Programming adalah bentuk lain dari program linier dengan variabel-variabel
keputusanya bertipe integer .Jika variabel keputusan yang dihadapi berkaitan dengan
jumlah orang,mesin- mesin , kendaraan dan lain-lain, akan terasa janggal jika menyelesaikan
pekerjaan itu diperlukan 3,5 mesin dan 7,5 orang, sebaliknya jika pekerjaan memerlukan 4
atau 5 mesin dan 8 orang , maka keputusan akan terasa realistik dan lebih mudah.
Permasalahan Integer Programming mencakup permasalahan semua integer.
Permasalahan semua integer adalah permasalahan integer programming dengan variabel
keputusan dan kendala dibatasi berupa bilangan integer. Terdapat dua metode untuk
menyelesaikan masalah integer Programming. Dengan metode ini akan dibuat batasan-
batasan khusus yang akan memaksa pemecahan optimum dari masalah program linier
untuk bergerak ke arah pemecahan integer yang diinginkan, metode itu adalah
1. Metode Cutting Plane
2. Metode Branch and Bound
Pada Makalah ini akan membahas satu metode saja , yaitu metode Cutting Plane.
Dalam metode cutting plane dibuat kendala tambahan yang memmotong daerah
penyelesaian yang layak dari persoalan masalah integer , sehingga dapat
mengeliminasi penyelesaian yang bukan integer. Proses pemotongan pada daerah
penyelesaian yang diinginkan.
LANDASAN TEORI
2
INTEGER PROGRAMMING WITH CUTTING PLANE METHOD 2012
Pemrograman bulat (1nteger programming) dibutuhkan ketika keputusan harus dilakukan
dalam bentuk bilangan bulat (bukan pecahan yang sering terjadi bila kita gunakan metode
simpleks). Model matematis dari pemrograman bulat sebenarnya sama dengan model
linear programming, dengan tambahan
batasan bahwa variabelnya harus bilangan bulat. Terdapat 3 macam permasalahan dalam
pemrograman bulat, yaitu:
Pemrograman bulat murni, yaitu kasus dimana semua variabel keputusan harus
berupa bilangan bulat.
Pemrograman bulat campuran, yaitu kasus dimana beberapa, tapi tidak semua,
variabel keputusan harus berupa bilangan bulat
Pemrograman bulat biner, kasus dengan permasalahan khusus dimana semua
variabel
keputusan harus bernilai 0 dan 1
Banyak aplikasi kegunaan dari integer programming, misalnya dalam penghitungan
produksi sebuah perusahaan manufaktur, dimana hasil dari perhitungannya haruslah
bilangan bulat, karena perusahaan tidak dapat memproduksi produknya dalam bentuk
setengah jadi. Misal perusahaan perkitan mobil tidak bisa merakit 5,3 mobil A dan 2,5 mobil
B perhari, tetapi haruslah bilangan bulat, dengan metode pembulatan, bisa kita hasilkan
misalnya 5 mobil A dan 2 mobil B per hari, tetapi apakah metode pembulatan ini efisien?
Kita lihat pada penjelasan selanjutnya.
Model pemrograman bulat dapat juga digunakan untuk memecahkan masalah
dengan jawaban ya atau tidak (yes or decision) untuk model ini dibatasi menjadi dua, misal 1
dan 0, jadi keputusan ya atau tidak diwakili oleh variabel, katakanlah xj, menjadi:
xj = 1, untuk keputusan ya
xj = 0, untuk keputusan tidak
3
INTEGER PROGRAMMING WITH CUTTING PLANE METHOD 2012
Model ini seringkali disebut sebagai model pemrograman bulat biner.
PERMASALAH KASUS
Perusahaan Maman Catering akan memproduksi tiga jenis Gorengan yaitu Bakwan, Mendoan, dan Pisang goreng dengan keuntungan tiap jenis produksi Rp. 400, Rp.600, Rp.200 , ketiga jenis gorengan memerlukan pemrosesan tiga kali yaitu penyiapan bahan, penggorengan, finishng , seperti pada tabel berikut ini
4
INTEGER PROGRAMMING WITH CUTTING PLANE METHOD 2012
Pemrosesan Jenis Roti Penyediaan Max
Bakwan Mendoan Pisang Goreng
Penyiapan Bahan 4 -4 0 5 Penggorengan -1 6 0 5 Finishing -1 1 1 5
Proses Penyiapan Bahan memiliki paling banyak 5kg, penggorengan memiliki paling banyak 5L dan finishing paling banyak memiliki 5 bungkus
1. Jika menyiapkan bahan 4kg bakwan maka harus menyiapkan bahan 4kg juga untuk mendoan2. Jika melakukan penggorenga membutuhkan minyak sayur 6L untuk Mendoan maka harus menyiapkan 1L minyak sayur untuk bakwan3. Jika dalam pembungkusan mendoan membutuhkan 1 bungkus dan Pisang Goreng 1 Bungkus maka dibutuhkan 1 bungkus untuk bakwan
Tentukan kombinasi terbaik dari jumlah Bakwan, Mendoan, Pisang Goreng yang harus
diproduksi agar menghasilkan laba maksimum.
Max Z =4x1+6x2+2x3
Kendala :4x1 - 4x2 <= 56x2 - x1 <=5x2 + x3 -x1 <=5
Bentuk Standar nya :Maks Z - 4x1 - 6x2 - 2x3 - 0S1 - 0S2 - 0S3=0
Kendala4x1 - 4x2 + S1 = 56x2 - x1 + S2 = 5x2 + x3 -x1 + S3 = 5
Var Dasar
Z x1 x2 x3 S1 S2 S3 NK
Z 1 -4 -6 -2 0 0 0 0 S1 0 4 -4 0 1 0 0 5
5
INTEGER PROGRAMMING WITH CUTTING PLANE METHOD 2012
S2 0 -1 6 0 0 1 0 5 S3 0 -1 1 1 0 0 1 5 Z 1 -5 0 -2 0 1 0 5
S1 0 3 1/3 0 0 1 2/3 0 8 1/3 x2 0 - 1/6 1 0 0 1/6 0 5/6 S3 0 - 5/6 0 1 0 - 1/6 1 4 1/6 Z 1 0 0 -2 1 1/2 2 0 17 1/2
x1 0 1 0 0 3/10 1/5 0 2 1/2 x2 0 0 1 0 1/20 1/5 0 1 1/4 S3 0 0 0 1 1/4 0 1 6 1/4 Z 1 0 0 0 2 2 2 30
x1 0 1 0 0 3/10 1/5 0 2 1/2 x2 0 0 1 0 1/20 1/5 0 1 1/4 x3 0 0 0 1 1/4 0 1 6 1/4
Dari tabel optimum diatas didapatkan persamaan berikut
x1 + 3/10 S1 + 1/5 S2 =5/2x2 + 1/20 S1 + 1/5 S2 = 5/4 Diambil sebagai dasar untuk menambah kendala baru dan yang diambil
hanya dalam bentuk pecahannya saja
X3 + 1/4 S1 + S3 = 25/4
Yang diambil bentuk pecahan saja maka persamaanya menjadi
1/20 S1 + 1/5 S2 = 5/4(0 + 1/20) S1 + (0 + 1/5) S2 = (1 + 1/4)
Program(2)
Z = 4x1 +6x2 +2x3St:4x1 - 4x2 <= 56x2 - x1 <=5x2 + x3 -x1 <=51/20 S1 + 1/5 S2 = 1/4
Bentuk Standar1/20 S1 + 1/5 S2 - S4 + A4 = 1/4
x1 x2 x3 S1 S2 S3 S4 A4 NK
6
INTEGER PROGRAMMING WITH CUTTING PLANE METHOD 2012
0 0 0 2 2 2 0 M 30 *(-M) 0 0 0 1/20 1/5 0 -1 1 1/4 +
0 0 0 2 - 5M/20 2 - 1M/5 2 1 0 30 - 1M/4
Var Dasar
Z x1 x2 x3 S1 S2 S3 S4A4
NK
Z 1 0 0 0 2 - 5M/20
2 - 1M/5 2 1 0 30 - 1M/4
x1 0 1 0 0 3/10 1/5 0 0 0 2 1/2 x2 0 0 1 0 1/20 1/5 0 0 0 1 1/4 x3 0 0 0 1 1/4 0 1 0 0 6 1/4 A4 0 0 0 0 1/20 1/5 0 -1 1 1/4 Z 1 0 0 0 1 1/2 0 0 11-M M-10 27 1/2 x1 0 1 0 0 1/4 0 0 1 -1 2 1/4 x2 0 0 1 0 0 0 0 1 -1 1 x3 0 0 0 1 1/4 0 1 0 0 6 1/4 A4 0 0 0 0 1/4 1 0 -5 5 1 1/4
Program (3)
Z = 4X1 + 6 X2 + 2X3
St : X1+1/4S1+S4=9/4 Diambil sebagai dasar untuk menambah kendala baru dan yang diambil
hanya dalam bentuk pecahannya saja
Yang diambil bentuk pecahan saja maka persamaanya menjadi
1/4S1= 9/4 atau (0+1/4 S1)= 2 + 1/4
St : X2 + S4 = 1
St : X3 + ¼ S1 + S3 = 25/4
St: ¼ S1 = ¼
Bentuk standar nya adalah ¼ S1 – S5 +A5 = ¼
7
INTEGER PROGRAMMING WITH CUTTING PLANE METHOD 2012
Solusi Optimal nya :
X1 = 2
X2 = 1
X3 = 6
A4 = 1
A5 = 1
TUJUAN PEMBAHANSAN
Pembahasan Makalah ini bertujuan untuk menentukan nilai optimal dari
suatu fungsi objektif dalam program linier dengan variabel keputusan bernilai
integer dengan menggunakan metode cutting plane
8
INTEGER PROGRAMMING WITH CUTTING PLANE METHOD 2012
MANFAAT PEMBAHASAN
Penulisan makalah ini diharapkan dapat memberikan sumbangan baik kepada
penulis sendiri maupun bagi pembaca dalam meyelesaikan masalah perencanaan
integer programming menggunakan metode cutting plane
KESIMPULAN
Berdasarkan pembahasan diatas dapat disimpulkan bahwa metode Cutting Plane
dapat digunakan untuk menentukan penyelesaian optimal dalam masalah
perencanaan linier integer dengan membuat pembatas yang memotong daerah
penyelesaian layak , sehingga penyelesaian untuk masalah ini menjadi integer
programming.
9
INTEGER PROGRAMMING WITH CUTTING PLANE METHOD 2012
Untuk masalah yang cukup banyak , tabel simpleks bertambah panjang dan
lebar , tetapi jumlah kendala tambahan tidak melebihi jumlah semua variabel asli
(n+m) dengan n banyak variabel dan m banyak persamaan.
SARAN
Adapun saran yang di kemukakan sehubungan dengan pembuatan Makalah ini
adalah penggunaan metode Cutting Plane dalam menyelesaikan masalah perencanaan linier
integer membutuhkan waktu yang panjang, maka diharapkan pengkajian selanjutnya dapat
menggunakan metode lain dalam menyelesaikan perencanaan integer programming untuk
mengefisiensikan waktu dalam menentukan penyelesaian optimal.
10
INTEGER PROGRAMMING WITH CUTTING PLANE METHOD 2012
DAFTAR PUSTAKA
1. Anton,h,1987, Elementary Linier Algebra Fifth Edition . anton Textbooks inc,
Newyork
2. Aprilia, S, 2005 aplikasi Algoritma Cutting Plane untuk meyelesaikan integer
Programmin , Lab ilmu dan rekayasa Komputasi. Departmen Teknik Informatika
Institut Teknologi Bandung
3. Bronsn , R 1996 , Teori dan Soal – soal Operation Research Erlangga jakarta
4. Dimyati, T.T , dan Dimyati . A 1994. Operation Research Model-model pengambilan
keputusan , sinar Baru, Algendinso, Bandung
11
INTEGER PROGRAMMING WITH CUTTING PLANE METHOD 2012
12
top related