RISET OPERASI

SEMESTER GENAP 2009/2010

UNIVERSITAS JEMBER

Kamis, 24-02-2010

Masalah Minimasi

Untuk menyelesaikan masalah minimasi, dapat dilakukan dengan cara mengubah fungsi tujuan, menjadi masalah maksimasi. (untuk semua kendala bertanda ≤)

Contoh

Fungsi tujuan : Minimumkan

2 1 3 2

F. Kendala

1 2 4

1 2 6

1, 2 0

Z x x

x x

x x

x x

Contoh

Fungsi tujuan : Maksimumkan

2 1 3 2

F. Kendala

1 2 4

1 2 6

1, 2 0

Z x x

x x

x x

x x

CBCj -2 3 0 0 RHS

Rasio

Basis x1 x2 S1 S2 

0 S1 1 1 1 0 4 4

0 S2 1 -1 0 1 6 6

Zj-Cj 2 -3 0 0 0  

CBCj -2 3 0 0

RHS

Rasio

Basis x1 x2 S1 S2 

3 x2 1 1 1 0 4

0 S2 2 0 1 1 10

Zj-Cj 5 0 3 0 12  

Kesimpulan

x2=4, x1=0 Karena –Z=12, maka Z=-12.

Masalah Minimasi

Masalah maksimasi, biasanya memiliki kendala ≤, sekarang akan diterangkan simpleks untuk masalah

minimasi yang biasanya memiliki kendala pertidaksamaan ≥ atau =.

Masalah tsb memiliki langkah-langkah yang sedikit berbeda dengan masalah maksimasi.

Tanda ≥ berarti bahwa kendala harus dikurangi S (surplus)

Penggunaan variable buatan / artificial variable

Penggunaan variable artificial Kebutuhan awal utama metode simpleks

adalah solusi awal yang layak (initial basic feasible solition). Tanpa ini, table simpleks tidak dapat dibuat.

ContohFungsi tujuan : Minimumkan

3 1 2 3

F. Kendala

1 2 2 3 11

4 1 2 2 3 3

2 1 3 1

1, 2, 3 0

Z x x x

x x x

x x x

x x

x x x

Bentuk standarFungsi tujuan : Minimumkan

3 1 2 3 0 1 0 2

F. Kendala

1 2 2 3 1 11

4 1 2 2 3 2 3

2 1 3 1

1, 2, 3, 1, 2 0

Z x x x S S

x x x S

x x x S

x x

x x x S S

Penggunaan variable artificial Karena contoh diatas tidak bisa kita temukan

solusi awal yang layak, agar bisa diselesaikan dengan metode simpleks,maka kita tambahkan variable buatan (Artificial variable dilambangkan dengan R atau A) pada kendala yang tidak mempunyai variable basis (kendala 2 dan 3)

Sehingga akan diperoleh solusi awal yang layak sebagai berikut:

Bentuk standar

F. Kendala

1 2 2 3 1 11

4 1 2 2 3 2 1 3

2 1 3 2 1

1, 2, 3, 1, 2, 1, 2 0

x x x S

x x x S R

x x R

x x x S S R R

Penggunaan variable artificial Karena Artificial variable tidak mempunyai

arti yang nyata, maka dari iterasi demi iterasi mereka harus dijadikan bernilai nol (0),jika tidak maka solusi yang dihasilkan tidak layak.

untuk membuat variable artificial nol, maka harus di berlakukan penalty pada setiap variable artificial dalam fungsi tujuan.

Penalty Artificial variable

Penalty berupa pemberian bilangan (M) positif yang sangat besar dalam fungsi tujuan.

Untuk Masalah Maksimasi : M bertanda negatif (-)

Untuk masalah minimasi : M bertanda positif (+)

Contoh

Fungsi tujuan : Maksimumkan

3 1 5 2

F. Kendala

1 4

2 2 12

3 1 2 2 18

1, 2 0

Z x x

x

x

x x

x x

Fungsi tujuan : Minimumkan

3 1 2 3

F. Kendala

1 2 2 3 11

4 1 2 2 3 3

2 1 3 1

1, 2, 3 0

Z x x x

x x x

x x x

x x

x x x

Contoh Fungsi tujuan : Maksimumkan

3 1 5 2 0 1 0 2 1

F. Kendala

1 1 4

2 2 2 12

3 1 2 2 1 18

1, 2 0

Z x x S S MR

x S

x S

x x R

x x

Fungsi tujuan : Minimumkan

3 1 2 3 0 1 0 2 1 2

F. Kendala

F. Kendala

1 2 2 3 1 11

4 1 2 2 3 2 1 3

2 1 3 2 1

1, 2, 3 0

Z x x x S S MR MR

x x x S

x x x S R

x x R

x x x

Metode Penyelesaian

1. Metode Big-M / Teknik M

2. Metode Dua fase/langkah

Metode BIG-M

M bilangan positif yang sangat Besar Langkah-langkah sama dengan Simpleks

yang sudah dipelajari

Contoh

Fungsi tujuan : Minimumkan

3 1 2 3

F. Kendala

1 2 2 3 11

4 1 2 2 3 3

2 1 3 1

1, 2, 3 0

Z x x x

x x x

x x x

x x

x x x

Contoh

Fungsi tujuan : Minimumkan

3 1 2 3 0 1 0 2 1 2

F. Kendala

F. Kendala

1 2 2 3 1 11

4 1 2 2 3 2 1 3

2 1 3 2 1

1, 2, 3 0

Z x x x S S MR MR

x x x S

x x x S R

x x R

x x x

ContohCB

Cj -3 1 1 0 M M 0 RHSRasio

Basis x1 x2 x3 S1 R1 R2 S2  

0 S1 1 -2 1 1 0 0 0 11  11

M R1 -4 1 2 0 1 0 -1 3 3/2 

M R2 -2 0 1 0 0 1 0 1 1 

Zj-Cj 3-6M M-1 3M-1 0 0 0 -M 4M  

CBCj -3 1 1 0 M M 0 RHS

RasioBasis x1 x2 x3 S1 R1 R2 S2  

0 S1 3 -2 0 1 0 -1 0 10 -

M R1 0 1 0 0 1 -2 -1 1 1

1 X3 -2 0 1 0 0 1 0 1 -

Zj-Cj 1 M-1 0 0 0 1-3M -M M+1  

ContohCB

Cj -3 1 1 0 M M 0 RHSRasio

Basis x1 x2 x3 S1 R1 R2 S2  

0 S1 3 0 0 1 2 -5 0 12 4

1 X2 0 1 0 0 1 -2 -1 1 -

1 X3 -2 0 1 0 0 1 0 1 -

Zj-Cj 1 0 0 0 1-M -2-M -1 2  

CB

Cj -3 1 1 0 M M 0 RHSRasio

Basis x1 x2 x3 S1 R1 R2 S2 

-3 X1 1 0 0 1/3 2/3 -5/3 0 4

1 X2 0 1 0 0 1 -2 -1 1

1 X3 0 0 1 2/3 4/3 -7/3 0 9

Zj-Cj 0 0 0 -1/3 1/3-M 2/3-M -1 -2  

Latihan Selesaikan masalah-masalah berikut

03,2,1

23241

4321

3221 Maks.2

04,3,2,1

23212

342321

243221

432212Min .1

xxx

xxx

xxx

xxxZ

xxxx

xxx

xxxx

xxxx

xxxxZ

04,3,2,1

64733241

54335216

24332215

4533218Min .3

xxxx

xxxx

xxxx

xxxx

xxxxZ

Pelajari

Metode Dua Fase/langkah