integer programing -...

INTEGER

PROGRAMING

CONTOH SOAL !Sebuah perusahaan jus buah curah

“JASJUS TAMBUNAN” memproduksi 2 jenis produk,

yaitu jus jeruk dan jus jambu. Masing-masing

produk tersebut membutuhkan 2 tahapan produksi,

yaitu ekstraksi dan penyaringan. Waktu ekstraksi

adalah 2 jam untuk jus jeruk dan 3 jam untuk jus jambu.

Sedangkan waktu penyaringan adalah 6 jam untuk jus

jeruk dan 5 jam untuk jus jambu. Perusahaan

tersebut hanya mempunyai waktu untuk ekstraksi

12 jam, dan waktu untuk penyaringan 30 jam kerja

per minggu. Jus jeruk memberikan keuntungan

70.000 per liternya sedangkan jus jambu 60.000

per liternya, tentukan banyaknya jus jeruk dan jus jambu

yang sebaiknya diproduksi untuk mendapatkan

keuntungan yang maksimal!

TENTUKAN MODEL MATEMATISNYA !

• Jika: x1 = jus jeruk

x2 = jus jambu

• Maksimisasi profit: 7x1 + 6x2

• Ditujukan pada: 2x1 + 3x2 ≤ 12

6x1 + 5x2 ≤ 30

x1, x2 ≥ 0

SELESAIKAN DENGAN METODE

GRAFIS !

1

2

4

3

5

6

X2

7

1 2 3 4 5 6 7 X1

6x1 + 5x2 ≤ 30

2x1 + 3x2 ≤ 12

Optimal LP Solution:

x1 = 3¾ ; x2 = 1½

Keuntungan maksimal

= 7x1 + 6x2

= 7 (3¾) + 6 (1½)

= 35,25

Dari hasil ini dapat diketahui pabrik harus

memproduksi 3¾ kilo liter jus jeruk dan 1½ kilo liter

jus jambu untuk mencapai keuntungan maksimal

Perhitungan ini tidak masalah karena produk dapat

dijual dengan jumlah pecahan

Lalu bagaimana jika produknya berbeda?

CONTOH SOAL !Sebuah perusahaan mesin pengolah pangan

“ESEMKA” memproduksi 2 jenis produk, yaitu

drumdryer dan spraydryer. Masing-masing

produk tersebut membutuhkan 2 tahapan

produksi, yaitu kelistrikan dan perakitan. Waktu

kelistrikan adalah 2 jam untuk drumdryer dan 3 jam

untuk spraydryer. Sedangkan waktu perakitan adalah 6

jam untuk drumdryer dan 5 jam untuk spraydryer.

Perusahaan tersebut hanya mempunyai waktu

untuk kelistrikan 12 jam, dan waktu untuk perakitan 30

jam kerja per minggu. Drumdryer memberikan

keuntungan 70 juta per unitnya, sedangkan

spraydryer 60 juta per unitnya, tentukan banyaknya

drumdryer dan spraydryer yang sebaiknya

diproduksi untuk mendapatkan keuntungan yang

maksimal!

Dengan cara yang sama (Linear Programing / LP), akandiperoleh jawaban, perusahaan akan memperoleh

keuntungan maksimal apabila memproduksi

x1 = drumdryer = 3¾ unit

x2 = spraydryer = 1½ unit

TETAPI........

Siapa yang mau

membeli alat yang

tidak utuh???

INTEGER PROGRAMING...

• Integer programing (pemrograman bulat) digunakan

untuk memodelkan permasalahan yang variabelnya

tidak mungkin berupa bilangan tidak bulat

• Cara penyelesaian :

– Metode Round Off

– Metode Branch and Bound (Algoritma percabangan)

– Metode Gomory / Cutting Plane (Algoritma pemotongan)

METODE ROUND OFF

Pemecahan paling mudah dari contoh soal di atas adalah

pembulatan (Metode Round Off). Dari solusi optimal kita

lakukan pembulatan menjadi :

x1 = drumdryer = 4 unit ; x2 = spraydryer = 2 unit

TETAPI TIDAK MUNGKIN !

(karena berada diluar area lihat gambar)

Sehingga yang paling memungkinkan

x1 = drumdryer = 4 unit ; x2 = spraydryer = 1 unit

Solusi optimal

Integer programing

Solusi optimal

Round Off

Drumdryer

(x1)

Spraydryer

(x2)

Keuntungan

(7x1 + 6x2)

0 0 0

1 0 7

2 0 14

3 0 21

4 0 28

5 0 35

0 1 6

1 1 13

2 1 20

3 1 27

4 1 34

0 2 12

1 2 19

2 2 26

3 2 33

0 3 18

1 3 25

0 4 24

Dari persoalan di atas telah didapatkan hasil

x1 = 3¾ ; x2 = 1½ ; profit = 35,25

Karena x1 = 3¾ (tidak bulat), maka dicabangkan jadi dua:

METODE PERCABANGAN

CABANG A

Maksimisasi profit: 7x1 + 6x2

Ditujukan pada: 2x1 + 3x2 ≤ 12

6x1 + 5x2 ≤ 30

x1 ≥ 4

Dengan LP sederhana:

x1 = 4 maka x2 = 1,2 ; profit = 35,2

CABANG B



6x1 + 5x2 ≤ 30

x1 ≤ 3


x1 = 3 maka x2 = 2 ; profit = 33BELUM FEASIBLE ! SUDAH FEASIBLE !

Dari percabangan A:

x1 = 4 maka x2 = 1,2 ; profit = 35,2

Karena x2 = 1,2 (tidak bulat), maka dicabangkan jadi dua:

CABANG C



6x1 + 5x2 ≤ 30

x1 ≥ 4

x2 ≥ 2

LIHAT DI GAMBAR! Syarat x1 ≥ 4

dan x2 ≥ 2 di luar area, maka tidak

fesible, maka percabangan

dihentikan !

CABANG D



6x1 + 5x2 ≤ 30

x1 ≥ 4

x2 ≤ 1


x2 = 1 maka x1 = 4 ¼ ; profit = 35,16

BELUM FEASIBLE !

LANJUTKAN !

Dari percabangan D didapatkan:

x2 = 1 maka x1 = 4 ¼ ; profit = 35,16

Karena x1 = 4 ¼ (tidak bulat), maka dicabangkan jadi dua:

CABANG E



6x1 + 5x2 ≤ 30

x1 ≥ 4

x2 ≤ 1

x1 ≤ 4


x1 = 4 maka x2 = 1 ; profit = 34

CABANG F



6x1 + 5x2 ≤ 30

x1 ≥ 4

x2 ≤ 1

x1 ≥ 5


x1 = 5 maka x2 = 0 ; profit = 35

SUDAH FEASIBLE ! SUDAH FEASIBLE !

x1 = 3¾

x2 = 1½

Π = 35,25

A

x1 = 4

x2 = 1,2

Π = 35,2

B

x1 = 3

x2 = 2

Π = 33

C

Tidak dapat

memenuhi

syarat

D

x1 = 4,1

x2 = 1

Π = 35,12

E

x1 = 4

x2 = 1

Π = 34

D

x1 = 5

x2 = 0

Π = 35

Iterasi 1 Iterasi 2 Iterasi 3

x1 ≥ 4

x1 ≤ 3

x2 ≥ 2

x2 ≤ 1

x1 ≤ 4

x1 ≥ 5

Feasible,

integer solution

Feasible,

integer solution

OPTIMAL SOLUTION !

Feasible,

integer solution

Hasil dari integer programming tidak akan pernah

melebihi nilai keuntungan optimal dari solusi LP

Pada kasus di atas keuntungan dari LP adalah

35,25 ; sedangkan keuntungan dari integer

programming hanya 35

16

METODE BRANCH DAN BOUND

Maksimumkan Z = 3 X1 + 5 X2

Dengan syarat 2 X1 + 4 X2 ≤ 25 X1 ≤ 8 2 X2 ≤ 10 X1 ; X2 non

negatif integer

TUGAS

PENYELESAIAN SOAL TUGAS

X1 = 8

X2 = 2

Z = 34

0

Solusi bulat optimum

X1 = 8

X2 = 2,25

Z = 35,25

2

Tak layak

X1 = 6,5

X2 = 3

Z = 34,5

inferior

inferior

X1 = 6

X2 = 3,25

Z = 34,25


JAWABAN:

19



Dengan syarat 2 X1 + 4 X2 ≤ 25 X1 ≤ 8 2 X2 ≤ 10 X1 ; X2 non negatif integer

Solusi optimum kontinyu masalah ini adalah X1 = 8, X2 =

2,26 dan Z = 35,25.

Solusi ini menunjukkan batas atas awal.

20

Batas bawah adalah solusi yang dibulatkan ke bawah X1 = 8, X2 = 2 dan Z = 34. Dalam metode Branch dan Bound, masalah itu dibagi ke dalam dua bagian untuk mencari nilai solusi bulat yang mungkin bagi X1 dan X2.

Variabel dengan nilai solusi pecah terbesar dipilih. Karena pada solusi ini hanya X2 yang memiliki bagian pecah, ia dipilih. Untuk menghilangkan bagian pecah dari nilai X2 = 2,25, dua kendala baru dibuat.

Kendala-kendala ini mewakili dua bagian baru dari masalah itu. Dua nilai bulat terdekat terhadap 2,25 adalah 2 dan 3. Sehingga diperoleh dua masalah baru melalui dua kendala mutually exclusive, X2 ≤ 2 dan X2 ≥ 3, yang akan diuraikan berikut ini se-bagai bagian A dan B. Kendala-kendala ini secara efektif menghi-langkan semua nilai pecah yang mungkin bagi X2, antara 2 dan 3. Pengaruhnya mereka mengurangi ruang solusi layak sehingga angka solusi bulat yang dievaluasi pada masalah ini makin sedikit



Dengan syarat 2 X1 + 4 X2 ≤ 25 X1 ≤ 8 2 X2 ≤ 10 X2 ≤ 2 X1 ; X2 ≥ 0

(berlebih)


Dengan syarat 2 X1 + 4 X2 ≤ 25 X1 ≤ 8 2 X2 ≤ 10 X2 ≥ 3 X1 ; X2 ≥ 0

Bagian A :

Bagian B :


Bagian A dan B diselesaikan tanpa pembatasan bilangan

bulat dengan metode simpleks. Solusi simpleksnya adalah :

Bagian A : X1 = 8, X2 = 2 dan Z = 34

Bagian B : X1 = 6,5, X2 = 3 dan Z = 34,5

Bagian A menghasilkan suatu solusi yang semuanya bulat.

Untuk bagian A batas atas dan bawah adalah Z = 34. Solusi

pecah bagian B membenarkan pencarian lebih lanjut karena

menghasilkan nilai fungsi tujuan yang lebih besar dari batas

atas bagian A. Sangat mungkin bahwa pencarian lebih lanjut

dapat menghasilkan suatu solusi yang semuanya bulat

dengan nilai fungsi tujuan melebihi batas atas bagian A = 34.

Bagian B dicabangkan ke dalam dua sub bagian, B1 dan B2,

pertama dengan kendala X1 ≤ 6 dan yang lain dengan X2 ≥ 7.



Dengan syarat 2 X1 + 4 X2 ≤ 25 X1 ≤ 8 2 X2 ≤ 10 X2 ≥ 3 X1 ≤ 6 X1 ; X2 ≥ 0


Dengan syarat 2 X1 + 4 X2 ≤ 25 X1 ≤ 8 2 X2 ≤ 10 X2 ≥ 3 X1 ≥ 7 X1 ; X2 ≥ 0


Sub Bagian B1 :

Sub Bagian B2 :

(berlebih)

Solusi simpleksnya adalah :

Sub-bagian B1 : X1 = 6, X2 = 3,25 dan Z = 34,25

Sub-bagian B2 : tidak layak.

Karena sub-bagian B1 menghasilkan nilai fungsi tujuanyang lebih besar dari 34 (batas atas bagian A), makaharus dica-bangkan lagi ke dalam dua sub masalah, dengan kendala X2 ≤ 3 dan X2 ≥ 4. Kedua kendala sub masalah diberi nama bagian B1a dan B2b.



Dengan syarat 2 X1 + 4 X2 ≤ 25 X1 ≤ 8 2 X2 ≤ 10 X2 ≥ 3 X2 ≥ 4 X1 ≤ 6 X1 ; X2 ≥ 0


Dengan syarat 2 X1 + 4 X2 ≤ 25 X1 ≤ 8 2 X2 ≤ 10 X2 ≥ 3 X2 ≤ 3 X1 ≤ 6 X1 ; X2 ≥ 0

Bagian B1a :

Bagian B1b :

(berlebih)

(berlebih)


26


Solusi optimum dengan metode simpleks adalah :

Sub-bagian B1a : X1 = 6, X2 = 3 dan Z = 33

Sub-bagian B1b : X1 = 4,25, X2 = 4 dan Z = 33,5

Kedua solusi itu memiliki batas atas ( Z = 33 dan Z =

33,5) yang lebih buruk dibanding dengan solusi yang

dihasilkan oleh bagian A. Karena itu, solusi bulat

optimum adalah X1 = 8, X2 = 2 dan Z = 34 yang

dihasilkan oleh bagian A.

Jika pencarian telah diselesaikan, solusi bulat dengan

fungsi tujuan tertinggi (dalam masalah maksimasi)

dipilih sebagai solusi optimum.

Kelemahan dasar dari metode ini adalah bahwa

diperlukan pemecahan masalah LP untuk setiap

pencabangan. Dalam masalah yang besar dapat

memakan banyak waktu. Karena itu dalam prosedur

pencabangan dan pencarian, analisa selanjutnya

dihentikan jika :

1.Hasil dari sub-problem lebih jelek dibanding dengan

batas atas yang sudah diidentifikasi

2.Pencabangan selanjutnya menghasilkan solusi tak

layak.


X1 = 8

X2 = 2

Z = 34

0

Solusi bulat optimum

X1 = 8

X2 = 2,25

Z = 35,25

2

Tak layak

X1 = 6,5

X2 = 3

Z = 34,5

inferior

inferior

X1 = 6

X2 = 3,25

Z = 34,25


Seluruh prosedur Branch dan Bound untuk contoh yang

lalu dapat digambarkan seperti berikut :

TERIMA KASIH

integer programing -...

Documents