operations research

Operations Research

Industrial Engineering

2

Analisa Sensitivitas

3

Pengaruh Perubahan Perubahan yang mempengaruhi optimalitas

Perubahan koefisien tujuan Perubahan dalam penggunaan sumber daya

dalam kegiatan Penambahan kegiatan baru (penambahan

variabel) Perubahan yang mempengaruhi kelayakan

Perubahan RHS Penambahan batasan baru

Perubahan yang mempengaruhi optimalitas dan kelayakan Perubahan koefisien tujuan dan RHS secara

simultan

4

Analisa Sensitivitas: Simpleks

5

Informasi dari Tabel Optimal Simpleks Solusi Optimal Status Sumber Daya Shadow Price Reduced Cost Sensitivitas dari hasil solusi optimal terhadap

perubahan ketersediaan sumber atau perubahan koefisien fungsi tujuan

6

Contoh Soal Reddy Mikks Company memiliki sebuah pabrik kecil yang

menghasilkan cat, baik untuk interior maupun eksterior untuk didistribusikan kepada para grosir. Dua bahan baku, A dan B, dipergunakan untuk membuat cat tersebut. Ketersediaan A maksimum adalah 6 ton satu hari; ketersediaan B adalah 8 ton satu hari. Kebutuhan harian akan bahan baku per ton cat interior dan eksterior diringkaskan dalam tabel 1. Sebuah survey pasar telah menetapkan bahwa permintaan harian akan cat interior tidak akan lebih dari 1 ton lebih tinggi dibandingkan permintaan akan cat eksterior. Survey tersebut juga memperlihatkan bahwa permintaan maksimum akan cat interior adalah terbatas pada 2 ton per hari. Harga grosir per ton adalah $3000 untuk cat eksterior dan $2000 untuk cat interior. Berapa banyak cat interior dan eksterior yang harus dihasilkan perusahaan tersebut setiap hari untuk memaksimumkan pendapatan kotor?

7

Contoh Soal (Tabel 1)Ton Bahan baku per Ton

CatKetersediaan maksimum

(ton)Eksterior Interior

A 1 2 6

B 2 1 8

8

Contoh Soal X1 = cat eksterior yang harus diproduksi X2 = cat interior yang harus diproduksi

Fungsi Tujuan: maksimumkan pendapatan kotormax z = 3000 X1 + 2000 X2

Batasan bahan baku Bahan baku A maksimum 6 ton per hari

X1 + 2 X2 ≤ 6 Bahan baku B maksimum 8 ton per hari

2 X1 + X2 ≤ 8

9

Contoh Soal Batasan permintaan harian

Permintaan harian cat interior tidak akan lebih dari 1 ton lebih tinggi dari cat eksteriorX2 – X1 ≤ 1

Permintaan maksimum harian cat interior adalah 2 tonX2 ≤ 2

Batasan non negativitas X1 ≥ 0 X2 ≥ 0

10

Contoh Soalmax z = 3000 X1 + 2000 X2

Subject To:1) X1 + 2 X2 ≤ 62) 2 X1 + X2 ≤ 83) X2 – X1 ≤ 14) X2 ≤ 25) X1 ≥ 06) X2 ≥ 0

11

Contoh Soal: Bentuk Standarmax z = 3 X1 + 2 X2 + 0 s1 + 0 s2 + 0 s3 + 0 s4

atau

max z - 3 X1 - 2 X2 - 0 s1 - 0 s2 - 0 s3 - 0 s4 = 0

Subject To:

X1 + 2 X2 + s1 = 6

2 X1 + X2 + s2 = 8

– X1 + x2 + s3 = 1

X2 + s4 = 2

X1, X2, s1, s2, s3, s4 ≥ 0

12

Variabel Slack s1 = sisa bahan baku A s2 = sisa bahan baku B s3 = kelebihan selisih permintaan cat interior

dan cat eksterior (X2 – X1) terhadap batas maksimum selisih yang ditentukan

s4 = selisih batas maksimum permintaan cat interior (X2) terhadap produksinya

13

Penyelesaian dengan SimpleksDasar z x1 x2 s1 s2 s3 s4 RHS

z 1 -3 -2 0 0 0 0 0s1 0 1 2 1 0 0 0 6s2 0 2 1 0 1 0 0 8s3 0 -1 1 0 0 1 0 1s4 0 0 1 0 0 0 1 2

Dasar z x1 x2 s1 s2 s3 s4 RHSz 1 -3 -2 0 0 0 0 0

s1 0 1 2 1 0 0 0 6 6s2 0 2 1 0 1 0 0 8 4s3 0 -1 1 0 0 1 0 1 -1s4 0 0 1 0 0 0 1 2 ~

Dasar z x1 x2 s1 s2 s3 s4 RHSz 1 0 -1/2 0 3/2 0 0 12

s1 0 0 3/2 1 -1/2 0 0 2 4/3x1 0 1 1/2 0 1/2 0 0 4 8s3 0 0 3/2 0 1/2 1 0 5 10/3s4 0 0 1 0 0 0 1 2 2

Dasar z x1 x2 s1 s2 s3 s4 RHSz 1 0 0 1/3 4/3 0 0 12 2/3

x2 0 0 1 2/3 -1/3 0 0 4/3x1 0 1 0 -1/3 2/3 0 0 10/3s3 0 0 0 -1 1 1 0 3s4 0 0 0 -2/3 1/3 0 1 2/3

Rasio

Rasio

14

Tabel Optimal Simpleks

Dasar z x1 x2 s1 s2 s3 s4 RHS

z 1 0 0 1/3 4/3 0 0 12 2/3

x2 0 0 1 2/3 -1/3 0 0 4/3

x1 0 1 0 -1/3 2/3 0 0 10/3

s3 0 0 0 -1 1 1 0 3

s4 0 0 0 -2/3 1/3 0 1 2/3

15

Solusi OptimalVariabel Keputusan

Nilai Optimal

Keputusan

X1 3 1/3 Harus memproduksi 3 1/3 ton cat eksterior

X2 1 1/3 Harus memproduksi 1 1/3 ton cat interior

Z 12 2/3 Keuntungan maksimum adalah $12.667


x2 0 0 1 2/3 -1/3 0 0 4/3x1 0 1 0 -1/3 2/3 0 0 10/3s3 0 0 0 -1 1 1 0 3s4 0 0 0 -2/3 1/3 0 1 2/3

16

Status SumberSumber Slack Status Sumber

Bahan A s1 = 0(NBV)

Langka, tidak ada sisa (bahan A habis terpakai) sehingga untuk menaikkan nilai Z, bahan A dapat ditambah

Bahan B s2 = 0(NBV)

Langka, tidak ada sisa (bahan A habis terpakai) sehingga untuk menaikkan nilai Z, bahan A dapat ditambah

kelebihan cat interior dibandingkan cat eksterior

s3 = 3 Melimpah, selisih maksimum (X2 – X1) adalah 1, tetapi hasil optimal menunjukkan selisih kurang dari 1

batas maksimum permintaan cat interior

s4 = 2/3

Melimpah, permintaan cat interior maksimum adalah 2, tetapi hasil optimal menunjukkan X2 kurang dari 2


x2 0 0 1 2/3 -1/3 0 0 4/3x1 0 1 0 -1/3 2/3 0 0 10/3s3 0 0 0 -1 1 1 0 3s4 0 0 0 -2/3 1/3 0 1 2/3

17

Shadow Price Shadow Price hanya berlaku untuk sumber

daya yang nilai variabel slacknya 0.

y1 = 1/3; untuk setiap penambahan 1 ton bahan A, nilai Z akan bertambah $1/3ribu

y2 = 4/3; untuk setiap penambahan 1 ton bahan B, nilai Z akan bertambah $4/3ribu

isumber an ketersedia maksimumperubahan

isumber perubahan disebabkan yang Znilai maksimumperubahan iy


x2 0 0 1 2/3 -1/3 0 0 4/3x1 0 1 0 -1/3 2/3 0 0 10/3s3 0 0 0 -1 1 1 0 3s4 0 0 0 -2/3 1/3 0 1 2/3

18

Shadow Price

19

Shadow Price

20

Reduced Cost Hanya berlaku untuk variabel yang bernilai 0 Pada kasus Reddy Mikks X1 dan X2 tidak nol

sehingga tidak ada informasi reduced cost

21

Contoh Reduced Costmax z = 8 X1 + 2 X2 + 0 s1 + 0 s2 + 0 s3 + 0 s4

atau

max z - 8 X1 - 2 X2 - 0 s1 - 0 s2 - 0 s3 - 0 s4 = 0

Subject To:

X1 + 2 X2 + s1 = 6

2 X1 + X2 + s2 = 8

– X1 + x2 + s3 = 1

X2 + s4 = 2

X1, X2, s1, s2, s3, s4 ≥ 0

22

Contoh Reduced Cost

Dari tabel optimal, X2 sebagai non basic variable, sehingga bernilai 0 (cat interior tidak diproduksi sama sekali)

Reduced cost X2 + 2 = 0 (atau reduced cost X2 = -2); setiap pemaksaan produksi 1 ton X2 akan mengurangi keuntungan sebanyak $2000

Dasar z x1 x2 s1 s2 s3 s4 RHSz 1 0 2 0 4 0 0 32

s1 0 0 1,5 1 -0,5 0 0 2x1 0 1 0,5 0 0,5 0 0 4s3 0 0 1,5 0 0,5 1 0 5s4 0 0 1 0 0 0 1 2

23

Contoh Reduced Cost

24

Contoh Reduced Cost

25

Analisa Sensitivitas dari Kelayakan:Perubahan Ketersediaan Sumber Daya (RHS) s1 = 0, bahan A bisa ditambah/dikurangi

D1 > 0 (positif) jika bahan A ditambah D1 < 0 (negatif) jika bahan A dikurangi

s2 = 0, bahan B bisa ditambah/dikurangi D2 > 0 (positif) jika bahan B ditambah D2 < 0 (negatif) jika bahan B dikurangi

26

Analisa Sensitivitas dari Kelayakan:Perubahan Ketersediaan Sumber Daya

Dasar z x1 x2 s1 s2 s3 s4 RHSz 1 -3 -2 0 0 0 0 0

s1 0 1 2 1 0 0 0 6 + D1 6 + D1s2 0 2 1 0 1 0 0 8 4s3 0 -1 1 0 0 1 0 1 -1s4 0 0 1 0 0 0 1 2 ~

Dasar z x1 x2 s1 s2 s3 s4 RHSz 1 0 -1/2 0 3/2 0 0 12

s1 0 0 3/2 1 -1/2 0 0 2 + D1 4/3 + 2/3 D1x1 0 1 1/2 0 1/2 0 0 4 8s3 0 0 3/2 0 1/2 1 0 5 10/3s4 0 0 1 0 0 0 1 2 2

Dasar z x1 x2 s1 s2 s3 s4 RHSz 1 0 0 1/3 4/3 0 0 12 2/3 + 1/3 D1

x2 0 0 1 2/3 -1/3 0 0 4/3 + 2/3 D1x1 0 1 0 -1/3 2/3 0 0 10/3 - 1/3 D1s3 0 0 0 -1 1 1 0 3 - 1 D1s4 0 0 0 -2/3 1/3 0 1 2/3 - 2/3 D1

Rasio

Rasio

27

Analisa Sensitivitas dari Kelayakan:Perubahan Ketersediaan Sumber Daya Perubahan nilai bi (nilai ruas kanan) di tabel

optimal akibat penambahan ketersediaan bahan A sebesar D1:

bi’ = konstanta + ki Di bi‘ = nilai bi yang baru Konstanta = nilai bi yang lama (dari tabel

optimal asal) ki = koefisien s1 dalam fungsi kendala (s1 =

variabel slack yang berkaitan dengan bahan A)

28


Variabel bi ki bi’

Z 12 2/3 1/3 12 2/3 + 1/3 D1

X2 4/3 2/3 4/3 + 2/3 D1

X1 10/3 -1/3 10/3 – 1/3 D1

S3 3 -1 3 – D1

S4 2/3 -2/3 2/3 – 2/3 D1

Perubahan Ketersediaan untuk Bahan A


x2 0 0 1 2/3 -1/3 0 0 4/3 + 2/3 D1x1 0 1 0 -1/3 2/3 0 0 10/3 - 1/3 D1s3 0 0 0 -1 1 1 0 3 - 1 D1s4 0 0 0 -2/3 1/3 0 1 2/3 - 2/3 D1

29

Analisa Sensitivitas dari Kelayakan:Perubahan Ketersediaan Sumber Daya Agar solusi tetap feasible, RHS harus

nonnegatif sehingga batasan perubahan ketersediaan sumber daya ditentukan:

12 2/3 + 1/3 D1 ≥ 0 D1 ≥ -38 4/3 + 2/3 D1 ≥ 0 D1 ≥ -2 10/3 – 1/3 D1 ≥ 0 D1 ≤ 10 3 – D1 ≥ 0 D1 ≤ 3 2/3 – 2/3 D1 ≥ 0 D1 ≤ 1Sehingga: -2 ≤ D1 ≤ 1 4 ≤ RHS ≤ 7

30


Variabel bi ki bi’

Z 12 2/3 4/3 12 2/3 + 4/3 D2

X2 4/3 -1/3 4/3 - 1/3 D2

X1 10/3 2/3 10/3 + 2/3 D2

S3 3 1 3 + D2

S4 2/3 1/3 2/3 + 1/3 D2

Perubahan Ketersediaan untuk Bahan B


x2 0 0 1 2/3 -1/3 0 0 4/3 - 1/3 D2x1 0 1 0 -1/3 2/3 0 0 10/3 + 2/3 D2s3 0 0 0 -1 1 1 0 3 + 1 D2s4 0 0 0 -2/3 1/3 0 1 2/3 + 1/3 D2

31

Analisa Sensitivitas dari Kelayakan:Perubahan Ketersediaan Sumber Daya Agar solusi tetap feasible, RHS harus

nonnegatif sehingga batasan perubahan ketersediaan sumber daya ditentukan:

12 2/3 + 4/3 D2 ≥ 0 D2 ≥ -19/2 4/3 – 1/3 D2 ≥ 0 D2 ≤ 4 10/3 + 2/3 D2 ≥ 0 D2 ≥ -5 3 + D2 ≥ 0 D2 ≥ -3 2/3 + 1/3 D2 ≥ 0 D2 ≥ -2Sehingga: -2 ≤ D2 ≤ 4 6 ≤ RHS ≤ 12

32

Analisa Sensitivitas dari Kelayakan:Perubahan Ketersediaan Sumber Daya Selisih cat eksterior dan interior

3 + D3 ≥ 0 D3 ≥ -3 RHS ≥ -2 --> RHS >= 0 Permintaan cat interior

2/3 + D4 ≥ 0 D4 ≥ -2/3 RHS ≥ 1 1/3Dasar z x1 x2 s1 s2 s3 s4 RHS

z 1 0 0 1/3 4/3 0 0 12 2/3x2 0 0 1 2/3 -1/3 0 0 4/3x1 0 1 0 -1/3 2/3 0 0 10/3s3 0 0 0 -1 1 1 0 3 + D3s4 0 0 0 -2/3 1/3 0 1 2/3


x2 0 0 1 2/3 -1/3 0 0 4/3x1 0 1 0 -1/3 2/3 0 0 10/3s3 0 0 0 -1 1 1 0 3s4 0 0 0 -2/3 1/3 0 1 2/3 + D4

33


Perubahan secara simultan:

4/3 + 2/3 D1 – 1/3 D2 >= 0 10/3 – 1/3 D1 + 2/3 D2 >= 0 3 – 1 D1 + 1 D2 + 1 D3 >= 0 2/3 – 2/3 D1 + 1/3 D2 + 1 D4 >= 0

34

Analisa Sensitivitas dari Solusi Optimal:Perubahan Koefisien Fungsi Tujuan Berpengaruh hanya pada nilai Z, bukan pada

solusi optimal Penambahan/pengurangan koefisien sebesar

dj untuk tiap variabel Xj

Koefisien X1 d1 > 0 (positif) besarnya koefisien bertambah d1 < 0 (negatif) besarnya koefisien berkurang

Koefisien X2 d2 > 0 (positif) besarnya koefisien bertambah d2 < 0 (negatif) besarnya koefisien berkurang

35

Analisa Sensitivitas dari Solusi Optimal:Perubahan Koefisien Fungsi Tujuan Perubahan koefisien X1 Z = (3 + d1) X1 + 2

X2Dasar z x1 x2 s1 s2 s3 s4 RHS

z 1 0 0 1/3 - 1/3 d1 4/3 + 2/3 d1 0 0 12 2/3 + 10/3 d1x2 0 0 1 2/3 -1/3 0 0 4/3x1 0 1 0 -1/3 2/3 0 0 10/3s3 0 0 0 -1 1 1 0 3s4 0 0 0 -2/3 1/3 0 1 2/3

36

Analisa Sensitivitas dari Solusi Optimal:Perubahan Koefisien Fungsi Tujuan Agar tidak mempengaruhi optimalitas dari

masalahnya, karena kasusnya maksimasi, nilai (baris z) pada tabel optimal harus nonnegatif (kalau kasusnya minimasi, nilai (baris z) pada tabel optimal harus nonpositif)

1/3 – 1/3 d1 ≥ 0 d1 ≤ 1 4/3 + 2/3 d1 ≥ 0 d1 ≥ -2 12 2/3 + 10/3 d1 ≥ 0 d1 ≥ -3 4/5

-2 ≤ d1 ≤ 1 1 ≤ koefisien X1 ≤ 4

37

Analisa Sensitivitas dari Solusi Optimal:Perubahan Koefisien Fungsi Tujuan Perubahan koefisien X2 Z = 3 X1 + (2 + d2)

X2

1/3 + 2/3 d2 ≥ 0 d2 ≥ -1/2 4/3 – 1/3 d2 ≥ 0 d2 ≤ 4 12 2/3 + 4/3 d2 ≥ 0 d2 ≥ -9 1/2

-1/2 ≤ d2 ≤ 4 3/2 ≤ koefisien X2 ≤ 6

Dasar z x1 x2 s1 s2 s3 s4 RHSz 1 0 0 1/3 + 2/3 d2 4/3 - 1/3 d2 0 0 12 2/3 + 4/3 d2

x2 0 0 1 2/3 -1/3 0 0 4/3x1 0 1 0 -1/3 2/3 0 0 10/3s3 0 0 0 -1 1 1 0 3s4 0 0 0 -2/3 1/3 0 1 2/3

38

Analisa Sensitivitas dari Solusi Optimal:Perubahan Koefisien Fungsi Tujuan Perubahan secara simultan:

1/3 – 1/3 d1 + 2/3 d2 >= 0 4/3 + 2/3 d1 – 2/3 d2 >= 0

39

Analisa Sensitivitas: Grafik

40

Penyelesaian dengan Grafik

41

Solusi Optimal Nilai maksimum dicapai pada titik perpotongan garis

1 dan 21) X1 + 2 X2 ≤ 62) 2 X1 + X2 ≤ 8

Dengan substitusi/eliminasi, dapat diperoleh titik perpotongannya: X1 = 10/3 X2 = 4/3

Z = 3000 X1 + 2000 X2 = 12667 Kesimpulan:

Cat eksterior yang harus diproduksi = 10/3 ton per hari Cat interior yang harus diproduksi = 4/3 ton per hari Pendapatan kotor maksimum yang bisa didapatkan =

$12.667

42

Status Sumber Daya Titik Optimal pada perpotongan batasan 1 dan

batasan 2 Batasan 1 ketersediaan bahan mentah A langka

(habis terpakai) Batasan 2 ketersediaan bahan mentah B langka

(habis terpakai) Batasan 3 selisih cat interior dan cat eksterior

melimpah (masih ada sisa jatah) Batasan 4 permintaan cat interior melimpah

(masih ada sisa jatah)

43

Perubahan RHS Pergeseran garis

pembatas 1 sampai pada titik B (penurunan RHS) atau titik K (kenaikan RHS)

Substitusi titik B (4,0) ke batasan 1 4

Substitusi titik K (3,2) ke batasan 1 7

4 ≤ RHS1 ≤ 7 -2 ≤ D1 ≤ 1

44

Perubahan RHSPada titik B X1 = 4 X2 = 0 Z = 12 RHS = 4

Pada titik K X1 = 3 X2 = 2 Z = 13 RHS = 7

Shadow Price

Y1 = (13-12)/(7-4) = 1/3ribu dollar per ton bahan A

45

Perubahan RHS Pergeseran garis

pembatas 2 sampai pada titik D (penurunan RHS) atau titik J (kenaikan RHS)

Substitusi titik D (2,2) ke batasan 2 6

Substitusi titik J (6,0) ke batasan 2 12

6 ≤ RHS2 ≤ 12 -2 ≤ D2 ≤ 4

3

4

6

5

0 1 875 6432

1

2

6

5

4

3

X2

X1

7

8

1

2

D

A

F

E

C

B J

K

2

2

9

12

11

10

46

Perubahan RHSPada titik D X1 = 2 X2 = 2 Z = 10 RHS = 6

Pada titik J X1 = 6 X2 = 0 Z = 18 RHS = 12

Shadow Price

Y2 = (18-10)/(12-6) = 4/3ribu dollar per ton bahan B

47

Perubahan koefisien fungsi tujuan Rotasi garis yang

mewakili Z dan melewati titik optimal menunjukkan pengaruh kenaikan/penurunan koefisien fungsi tujuan mempengaruhi besarnya nilai optimum. Searah jarum jam:

kenaikan koefisien X1/penurunan koefisien X2

Berlawanan arah: kenaikan koefisien X2/penurunan koefisien X1

48

Perubahan koefisien fungsi tujuan Kelayakan tidak akan berubah dan optimal

akan tetap di titik C selama rotasi dilakukan Searah jarum jam sampai menghimpit garis BC Berlawanan arah jarum jam sampai menghimpit

garis CD Bila garis Z menghimpit garis BC atau CD,

akan terjadi optimum alternatif

1/2 ≤ Ce/Ci ≤ 2/1, Ci ≥ 0

49

Perubahan koefisien fungsi tujuan Perubahan Ce saja

Z = (3 + d1) X1 + 2 X21/2 ≤ Ce/2 ≤ 2/1 1 ≤ Ce ≤ 4 -2 ≤ d1 ≤ 1

Perubahan Ci sajaZ = 3 X1 + (2 + d2) X21/2 ≤ 3/Ci ≤ 2/1 3/2 ≤ Ci ≤ 6 -1/2 ≤ d2 ≤ 4

50

End of This Chapter

operations research

Documents