TENTUKAN MODEL MATEMATISNYA!

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 !

X2

Keuntungan maksimal = 7x1 + 6x2 = 7 (3¾) + 6 (1½) = 35,25

7

6

6x1 + 5x2 ≤ 30

5 4 3

Optimal LP Solution: x1 = 3¾ ; x2 = 1½

2

2x1 + 3x2 ≤ 12

1

1

2

3

4

5

6

7

X1

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), akan diperoleh 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

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

1 1

6 13

2

1

20

3

1

27

4

1

34

0 1

2 2

12 19

2

2

26

3

2

33

0

3

18

1

3

25

Solusi optimal Integer programing

Solusi optimal Round Off

METODE PERCABANGAN Dari persoalan di atas telah didapatkan hasil x1 = 3¾ ; x2 = 1½ ; profit = 35,25 Karena x1 = 3¾ (tidak bulat), maka dicabangkan jadi dua: CABANG A

CABANG B

Maksimisasi profit: 7x1 + 6x2


Ditujukan pada: 2x1 + 3x2 ≤ 12 6x1 + 5x2 ≤ 30 x1 ≥ 4

Ditujukan pada: 2x1 + 3x2 ≤ 12 6x1 + 5x2 ≤ 30 x1 ≤ 3

Dengan LP sederhana: x1 = 4 maka x2 = 1,2 ; profit = 35,2 BELUM FEASIBLE !

Dengan LP sederhana: x1 = 3 maka x2 = 2 ; profit = 33 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

CABANG D



Ditujukan pada: 2x1 + 3x2 ≤ 12 6x1 + 5x2 ≤ 30 x1 ≥ 4 x2 ≥ 2

Ditujukan pada: 2x1 + 3x2 ≤ 12 6x1 + 5x2 ≤ 30 x1 ≥ 4 x2 ≤ 1

LIHAT DI GAMBAR! Syarat x1 ≥ 4 dan x2 ≥ 2 di luar area, maka tidak fesible, maka percabangan dihentikan !

Dengan LP sederhana: 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

CABANG F



Ditujukan pada: 2x1 + 3x2 ≤ 12 6x1 + 5x2 ≤ 30 x1 ≥ 4 x2 ≤ 1 x1 ≤ 4

Ditujukan pada: 2x1 + 3x2 ≤ 12 6x1 + 5x2 ≤ 30 x1 ≥ 4 x2 ≤ 1 x1 ≥ 5

Dengan LP sederhana: x1 = 4 maka x2 = 1 ; profit = 34

Dengan LP sederhana: x1 = 5 maka x2 = 0 ; profit = 35

SUDAH FEASIBLE !

SUDAH FEASIBLE !

Iterasi 1

Iterasi 2

Iterasi 3

C Tidak dapat memenuhi syarat

E x1 = 4

x2 ≥ 2

A x1 = 4 x1 ≥ 4

x1 = 3¾ x2 = 1½ Π = 35,25

x1 ≤ 4

x2 = 1,2 Π = 35,2 x2 ≤ 1

x1 ≤ 3

Feasible, integer solution

B x1 = 3 x2 = 2 Π = 33

Feasible, integer solution

D x1 = 4,1 x2 = 1 Π = 35,12

x2 = 1 Π = 34

D x1 = 5 x1 ≥ 5

x2 = 0 Π = 35

Feasible, integer solution OPTIMAL 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

METODE BRANCH DAN BOUND

TUGAS Maksimumkan Dengan syarat

Z =

3 X1 +

5 X2

2 X1 + X1

4 X2 ≤ 25 ≤ 8 negatif integer 2 X2 ≤ 10 X2 non

X1 ;

16

PENYELESAIAN SOAL TUGAS


JAWABAN:

0

Solusi bulat optimum X1 = 8 X2 = 2 Z = 34 2 X1 = 6 X2 = 3,25 Z = 34,25

X1 = 8 X2 = 2,25 Z = 35,25 X1 = 6,5 X2 = 3 Z = 34,5

Tak layak

inferior

inferior


Maksimumkan Dengan syarat

Z =

3 X1 +

5 X2

2 X1 + X1

4 X2 ≤ 25 ≤ 8 2 X2 ≤ 10 X2 non negatif integer

X1 ; 

Solusi optimum kontinyu masalah ini adalah X1 = 8, X2 = 2,26 dan Z = 35,25.



Solusi ini menunjukkan batas atas awal.

19

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


Bagian A : Maksimumkan

Z =

Dengan syarat

3 X1 +

5 X2

2 X1 + X1

4 X2 ≤ ≤ 2 X2 ≤ X2 ≤ X2 ≥

X1 ;

25 8 10 (berlebih) 2 0

Bagian B : Maksimumkan Dengan syarat

Z =

3 X1 +

5 X2

2 X1 + X1

4 X2 ≤ ≤ 2 X2 ≤ X2 ≥ X2 ≥

X1 ;

25 8 10 3 0

METODE BRANCH DAN BOUND  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.


Sub Bagian B1 : Maksimumkan

Z

Dengan syarat

=

3 X1 +

5 X2

2 X1 + X1

4 X2 ≤ ≤ 2 X2 ≤ X2 ≥ ≤ X2 ≥

X1 X1 ;

Sub Bagian B2 : Maksimumkan Dengan syarat

Z =

3 X1 +

5 X2

2 X1 + X1

4 X2 ≤ ≤ 2 X2 ≤ X2 ≥ ≥ X2 ≥

X1 X1 ;

25 8 10 3 7 0

25 8 (berlebih) 10 3 6 0


 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 tujuan yang lebih besar dari 34 (batas atas bagian A), maka harus 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.


Bagian B1a : Maksimumkan

Z

=

Dengan syarat

3 X1

+

5 X2

2 X1 X1

+

4 X2 2 X2 X2 X2

X1 X1

;

X2

3 X1

+

5 X2

2 X1 X1

+

4 X2

≤ ≤ ≤ ≥ ≤ ≤ ≥

25 8 10 3 3 6 0

≤ ≤ ≤ ≥ ≥ ≤ ≥

25 8 10 3 (berlebih) 4 6 0

(berlebih)

Bagian B1b : Maksimumkan Dengan syarat

Z

=

X1 X1

2 X2 X2 X2 ;

X2


 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. 26


 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.


Seluruh prosedur Branch dan Bound untuk contoh yang lalu dapat digambarkan seperti berikut :

0

Solusi bulat optimum X1 = 8 X2 = 2 Z = 34 2 X1 = 6 X2 = 3,25 Z = 34,25

X1 = 8 X2 = 2,25 Z = 35,25 X1 = 6,5 X2 = 3 Z = 34,5

Tak layak

inferior

inferior

TERIMA KASIH

TENTUKAN MODEL MATEMATISNYA!

Recommend Documents