makalah cutting plane

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


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


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


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


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


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


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


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


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


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


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


12

makalah cutting plane

Documents