Optimisasi-2.pdf

Teori dan aplikasi optimisasi Firmanto Hadi

RENCANA MATERI KULIAH • Pendahuluan • Linear Programing – Solusi Grafis – Solusi Matematis

• • • • •

Assignment Problem Transportation Problem Integer Programing Non-Linear Programing Project Management Selasa, 16 Februari 2016

Sistem Penilaian UAS

30%

UTS

30%

Tugas

20%

miniproject

20%

2

Pendahuluan • Pengertian Metode Optimisasi (Riset Operasi) – Optimisasi adalah suatu metode yang digunakan sebagai alat bantu dalam proses pegambilan keputusan. – Tujuan metode ini adalah untuk mencari alternatif terbaik (optimum) dengan menerapkan model matematis atas suatu permasalahan dengan memperhatikan batasan-batasan tertentu – Bagian terpenting dari metode ini adalah menerjemahkan permasalahan ke dalam model matematis.  (art and science)

• Proses pengambilan keputusan: – – – – – –

Defining the problem Determining the objective Exploring the alternatives Predicting consequences Making a choice Performing sensitivity analysis

Selasa, 16 Februari 2016

3

Pendahuluan • Contoh: – Seorang manajer pabrik harus mengambil keputusan untuk membeli mesin otomatis atau semi-otomatis untuk proses produksi di pabriknya. Informasi biaya untuk kedua alternatif mesin tersebut adalah sebagai seperti tabel di bawah. Keputusan yang harus diambil, mesin jenis manakah yang harus di beli? Cost in Dollar semi-automatic automatic Set up cost 20 50 Unit variable cost 0.6 0.4

Selasa, 16 Februari 2016

4

Pendahuluan • Untuk memformulasikan persoalan tersebut, maka: – Identifikasi alternatif solusi yang tersedia – Menentukan kriteria untuk mengevaluasi kelayakan masing-masing alternatif – Menggunakan kriteria tersebut sebagai dasar untuk menentukan pilihan terbaik

• Tujuan yang diinginkan – biaya produksi minim

• Alternatif yang tersedia: – Membeli mesin otomatis – Membeli mesin semi otomatis Selasa, 16 Februari 2016

5

Pendahuluan • Untuk mengevaluasi kedua alternatif tersebut, maka digunakan kriteria biaya produksi (yang terdiri atas biaya tetap, dan biaya variabel) dengan tujuan untuk meminimalisasi biaya produksi • Misalkan, x adalah jumlah produksi dalam satu batch, maka formulasi perhitungan biaya produksi adalah sebagai berikut: – Biaya produksi = setup cost + (variable cost)x = 50 + 0,4 x  mesin otomatis = 20 + 0,6x  mesin semiotomatis Selasa, 16 Februari 2016

6

• Tahap berikutnya adalah mengambil keputusan, yang dilakukan dengan break-even chart seperti berikut 160

Breakeven point

140

Biaya Produksi

120 100 80 60 40 20

Buy semiautomatic

Buy automatic

0 0

50

100

150

200

250

Jumlah Produksi Otomatis Semiotomatis Selasa, 16 Februari 2016

7

Pendahuluan • Contoh sebelumnya mengasumsikan bahwa production rate dari kedua jenis mesin tersebut adalah sama. • Bagaimana jika production rate keduanya tidak sama? (agar lebih realistis) • Informasi tambahan, production rate mesin otomatis adalah 25 unit/jam dan semiotomatis adalah 15 unit/jam. Pabrik beroperasi hanya 8 jam sehari (satu shift) dan permintaan atas hasil produksi mesin ini adalah 100 unit/hari dan ada kemungkinan meningkat menjadi 150 unit/hari.

Selasa, 16 Februari 2016

8

Pendahuluan 140

Feasible range for automatic

Biaya Produksi

120

Feasible range for semiautomatic

Infeasible range

100 80 60 Do not buy either machine

40

Buy semiautomatic

Buy automatic

20 20

40

60

80

100

120

140

160

180

200

220

240

Jumlah Produksi Otomatis Semiotomatis Selasa, 16 Februari 2016

9

LINEAR PROGRAMMING

Selasa, 16 Februari 2016

10

Contoh Persoalan LP Sederhana • Sebuah pabrik cat memproduksi 2 jenis cat (exterior dan interior). Untuk memproduksi cat tersebut dibutuhkan material A dan B. Jumlah material A yang tersedia maksimum adalah 6 ton/hari dan material B 8 ton/hari. Jumlah kebutuhan material yang dibutuhkan untuk menghasilkan cat tersebut adalah sebagai berikut: Kebutuhan material Jml Maksimum untuk 1 ton cat Material yang Exterior Interior tersedia Material A 1 2 6 Material B 2 1 8

• Hasil survei menunjukkan bahwa perbedaan permintaan antara cat interior dan exterior tidak lebih dari 1 ton per hari, sedangkan permintaan untuk cat interior sendiri adalah 2 ton per hari. Harga jual untuk cat exterior adalah $3.000 dan cat interior adalah $2.000 per ton. Berapakah jumlah cat interior dan exterior yang harus diproduksi oleh pabrik tersebut sedmikian sehingga pendapatan pabrik semaksimum mungkin. Selasa, 16 Februari 2016

11

Menyusun Model • Variabel – Apakah yang ingin dicari (tidak diketahui)  jumlah cat interior dan ekterior yang harus diproduksi • xE = jumlah cat exterior yang harus diproduksi • xI = jumlah cat interior yang harus diproduksi

• Objective Function (fungsi tujuan) – Berapa cat interior dan ekterior yang harus diproduksi sedemikian sehingga pendapatan maksimum •Z

= 3xE + 2xI

Selasa, 16 Februari 2016

12

Menyusun Model • Constraint (batasan) – Batasan ketersediaan material • xE + 2xI ≤ 6  Material A • 2xE + xI ≤ 8  Material B

– Batasan kondisi pasar • xI – xE ≤ 1 • xI ≤ 2

 Selisih demand interior dan ekterior  kebutuhan cat interior

– Batasan Non-negatif • xI ≥ 0 • xE ≥ 0

Selasa, 16 Februari 2016

13

Menyusun Model • Stadard penulisan model optimisasi maximize z  3 x E  2 x I subject to : xE  2 xI  6

Selasa, 16 Februari 2016

1

2 xE  xI  8

2

 xE  xI  1

3

xI  2

4

xE  0

5

xI  0

6

14

Solusi Grafis • Contoh model di atas dapat diselesaikan secara grafis (karena terdiri atas 2 variabel) • Penyelesaian model dengan 3 atau lebih variabel akan sangat sulit dilakukan • Meskipun dalam praktek penyelesaian persoalan, penggunaan metode grafis jarang dilakukan, namun pemahaman atas metode ini menjadi penting agar anda dapat membayangkan bagaimana proses ini berjalan • Langkah pertama dalam metode grafis adalah mengambar feasible solution yaitu yang memenuhi semua constraint yang telah ditentukan

Selasa, 16 Februari 2016

15

Gambar Solusi Grafis 9

Garis Objective Function Z=9

8

Solusi Optimum xE = 10/3 xI = 4/3 Z = 38/3

7

5 6

2

5 4

3

3

4

2

E

1

F

-1

Selasa, 16 Februari 2016

C

feasible region

A

0 -2

D

0

1 B

1

2

3

4

5

6

6

7 16

Analisis Sensitivitas • Analisis ini dilakukan setelah hasil optimum diperoleh • Berguna untuk mengetahui seberapa sensitif hasil optimum tadi jika terjadi perubahan data atau informasi pada model – Bagaimana jika harga jual berubah – Bagaimana jika ketersediaan material berubah – Bagaimana jika kebutuhan pasar berubah, dll

• Analisis sensivitas adalah bagian yang tidak terpisahkan dalam proses optimisasi – Mampu menjawab what-if scenario Selasa, 16 Februari 2016

17

Analisis Sensitivitas • Sensitivitas 1 – Seberapa banyak material dapat ditingkatkan untuk meningkatkan pendapatan dari hasil optimum? – Seberapa banyak material dapat dikurangi tanpa mengurangi pendapatan dari hasil optimum?

• Sensitivitas 2 – Material manakah yang merupakan prioritas utama jika kondisi budget terbatas

• Sensitivitas 3 – Seberapa besar koefisien objective function dapat diubah (dinaik/turunkan) tanpa merubah titik optimum  harga Selasa, 16 Februari 2016

18

Sensitivitas 1 • Terdapat 2 jenis constraint dalam LP – Binding  adalah constraint yang melewati titik optimum – Non-binding  constraint yang tidak melewati titik optimum

• Dalam solusi grafis terlihat bahwa constraint 1 dan 2 adalah yg melewati titik optimum  binding • Jika suatu constraint adalah binding, maka dapat dikatakan sebagai scarce resource karena seluruh yang tersedia terpakai habis • Sebaliknya, constraint yang nonbinding  abundant resource  tidak habis terpakai • Oleh karena itu: – Binding constraint  seberapa besar scarce resource itu dapat ditingkatkan untuk meningkatkan hasil optimum – Nonbinding constraint  seberapa besar kita dapat mengurangi abundant resource tanpa menurunkan hasil optimum Selasa, 16 Februari 2016

19

Sensitivitas 1 • Hasil optimisasi  material A dan B termasuk binding constraint

Pers. garis 1 (constraint material A=6 ton) digeser sejajar hingga menyentuh Perpotongan antara constraint 4 dan 2 (titik K), ketika titik K tercapai, maka constraint 2 dan 4 menjadi binding dan constraint 1 menjadi nonbinding, dan feasible region menjadi ABKEF. Titik optimum menjadi K, yang merupakan perpotongan antaran constraint 2 dan 4 2xE + xI = 8 xI = 2

xE = 3 dan xI = 2 Substitusi ke pers. Constraint 1 xE + 2xI = 3 + 2(2) = 7 ton

K E

4

D 1

3 F 5 A

C 2

6

Selasa, 16 Februari 2016

B

C: (10/3,4/3)  Z = 38/3 K: (2,3)  Z = 13

20

Sensitivitas 1 • Constraint Material B dapat dilakukan dg cara yang sama Dengan cara yang sama seperti pada material A, maka material B dapat ditingkatkan hingga 12 ton (perpotongan antaran constraint 1 dan 6  titik J)

C: (10/3,4/3)  Z = 38/3 J: (6,0)  Z = 18 E

4

D 1

3 F 5 A

C 2

6

B

J Selasa, 16 Februari 2016

21

Sensitivitas 1 • Mengurangi nonbinding constraint (constraint 4 dan 3) – Constraint 4 dapat dikurangi maksimum hingga melewati titik optimum (C) tanpa mengurangi nilai optimum  karena C (10/3,4/3), maka maksimum pengurangan demand untuk cat interior adalah hingga 4/3 ton  xI ≤ 4/3 – Constraint 3 dpt dilakukan dengan menggeser pers 3 sejajar hingga melewati titik C tanpa mengurangi nilai optimum  -xE + xI = (-10/3) + (4/3) = - 2  xE- xI ≥ 2  yang berarti bahwa solusi optimum tidak akan berubah jika permintaan cat exterior melebihi cat interior hingga 2 ton

E

4

D 1

3 F 5 A

C 2

6

Selasa, 16 Februari 2016

B

22

Sensitivitas 1 • Summary Perubaham Max Constraint Tipe pd nilai constraint 1 Binding 7 - 6 = +1 2 Binding 12 - 8 = +4 3 Nonbinding -2 - 1 = -3 4 Nonbinding 4/3 - 2 = -2/3

Selasa, 16 Februari 2016

Perubahan Max pd nilai optimum 13 - 38/3 = +1/3 18 - 38/3 = +16/3 38/3 - 38/3 =0 38/3 - 38/3 =0

23

Sensitivitas 2 • Berguna untuk menjawab material manakah yang memiliki prioritas tertinggi (budget terbatas) – Hal ini dilakukan dengan cara menambahkan satu satuan pada scarce resource dan bagaimana perubahan terhadap objective function – Scarce resource yang memberikan nilai perubahan pada objective function lebih tinggi memiliki prioritas yang lebih tinggi maksimum perubahan pada nilai optimum – Rumus umumnya : y  i

maksimum perubahan pada masing - masing resource

– Misalnya material A  dari tabel summary pada sensitivitas sebelumnya: 13  12 23 1 – Material A memiliki nilai $ 1/3 ribu per ton yi   76 3 – Dengan cara yang dilakukan untuk constraint-constraint yang lain Constraint Tipe 1 Binding

Nilai Yi y1 = 1/3

2

Binding

3

Nonbinding

y3 = 0

4

Nonbinding

y4 = 0

Selasa, 16 Februari 2016

y2 = 4/3

Material B memiliki prioritas tertinggi

24

Sensitivitas 3 • Berguna untuk mengetahui seberapa besar koefisien objective function dapat diubah • Perubahan koefisien pada objective function berakibat pada berubahnya slope persamaan objective function, oleh karena itu sensitivitas ini berhubungan dengan: – Seberapa besar koefisien objective function dapat berubah tanpa merubah titik optimum – Seberapa besar perubahan koefisien objective function yang akan menyebabkan constraint yang tadinya binding menjadi nonbinding atau sebaliknya

• Misal cE dan cI masing-masing adalah pendapatan per ton dari cat exterior dan interior, maka objective function dapat ditulis sebagai : z = c Ex E + c I x I • Sensitivitas ini berkaitan dengan bagaimana jika nilai cE dan cI dibesarkan atau dikecilkan  pers. Objective function akan berputar dengan tumpuan titik optimum (C) Selasa, 16 Februari 2016

25

Sensitivitas 3 • Nilai optimum (C) tidak akan berubah sepanjang slope pers z tersebut bervariasi antara constraint 1 dan 2. – Ketika slope z sama dengan pers. 1, kita memiliki alternative optima yaitu pada C dan D – Ketika slope z sama dengan pers. 2, kita memiliki alternative optima yaitu pada B dan C Misal nilai cI = 2 (nilai asal)  cE akan membesar sampai z berhimpit dengan pers. 2 dan akan mengecil sampai z berhimpit dengan pers. 1 Dengan demikian, variasi nilai maksimum dan minimum perubahan pada cE dapat dicari dengan menyamakan slope z dengan slope 2 dan 1 Decrease cE or increase cI

E

4

D 1

3 F 5 A

C 2

6

B Increase cE or decrease cI

Selasa, 16 Februari 2016

26

Sensitivitas 3 • Karena slope z = cE/2 dan slope 1 dan 2 masing-masing adalah ½ dan 2, maka nilai minimum cE dapat ditentukan dengan cara: • c E 1 nilai minimu cE = 1  2 2 • Dengan cara yang sama, maka nilai maksimum cE = 4 • Dengan kata lain 1 < cE < 4 – Jika cE = 1, maka titik optimum terjadi di C atau D dan jika cE dibawah 1, maka titik optimum menjadi D – Jika cE = 4, maka titik optimum terjadi di C atau B dan jika cE diatas 4, maka titik optimum menjadi B

• Jika cE dibawah 1  resource 2 menjadi abundant dan resource 4 menjadi scarce  jika revenue per ton dari cat exterior turun dibawah $1000, maka lebih menguntungkan untuk memproduksi cat interior hingga batas maksimumnya • Dengan cara yang sama, maka bila cE diatas 4  lebih menguntungkan memproduksi cat exterior • Variasi cI dapat dilakukan dengan cara sama dengan membuat nilai cE fixed (anda dapat mencoba sendiri!!)

Selasa, 16 Februari 2016

27

Tugas 1-a • A small plant makes two types of automobile parts. It buys castings that are machined, bored, and polished. The data shown in table below Part A Part B Machining Capacity 25 per hour 40 per hour Boring Capacity 28 per hour 35 per hour Polishing Capacity 35 per hour 25 per hour • Casting for part A cost $2 each; for part B they cost $3 each. They sell for $5 and $6 respectively. The three machines have running costs of $20, $14 and $17.5. Assuming that any combination of parts A and B can be sold, what product mix maximizes profit?

Selasa, 16 Februari 2016

28

Tugas 1-b • A company makes desk organizers. The standard model requires 2 hours of the cutter’s and 1 hour of the finisher’s time. The deluxe model requires 1 hour of the cutter’s time and 2 hours of the finisher’s time. The cutter has 104 hours of time available for this work per month, while the finisher has 76 hours of time available for work. The standard model brings a profit of $6 per unit, while the deluxe one brings a profit of $11 per unit. The company, of course, whishes to make the most profit. Assuming they can sell whatever is made, how much of each model should be made in each month?

Selasa, 16 Februari 2016

29

Solusi Matematis • Jika persoalan optimisasi memiliki variable 3 atau lebih, maka solusi secara grafis sulit untuk diterapkan  perlu solusi matematis • Solusi matematis untuk LP yang paling umum digunakan akan METODE SIMPLEX • Metode ini menyelesaikan persoalan optimisasi secara iterasi (perhitungan yang sama dilakukan berulang-ulang) sampai titik optimum diketemukan • Karena sifatnya yang iteratif  penggunaan software akan sangat membantu  banyak software yang dirancang untuk menyelesaikan persoalan LP ini • Metode Simplex ini adalah contoh yang paling mudah untuk dipahami bagaimana logika percarian titik optimum dalam persoalan LP Selasa, 16 Februari 2016

30

Bentuk Standar LP Model • Pada contoh sebelumnya, kita berhadapan dengan constraint dalam bentuk ≤,= dan ≥ • Untuk menyelesaikan LP secara matematis, maka ada suatu format khusus yang harus dipenuhi yang disebut dengan Bentuk Standar LP Model. Bentuk standar tersebut harus memenuhi hal-hal sebagai berikut: – Semua constraint harus berbentuk persamaan (=) dan ruas kanan harus berbentuk non-negative – Semua variabel harus non-negative – Objective function harus berbentuk maximumkan atau minimumkan

• Bagaimana menuliskan persoalan optimisasi kita dalam bentuk Standard LP Model sehingga bisa diselesaikan secara matematis?

Selasa, 16 Februari 2016

31

Bentuk Standar LP Model • Constraint  merubah constraint dari pertidak-samaan menjadi persamaan – Constraint berbentuk ≤ dapat diubah menjadi bentuk = dengan jalan menambahkan slack variabel pada ruas kiri persamaan

x1  2 x2  6

x1  2 x2  s1  6;

s1  0

– Constraint berbentuk ≥ dapat diubah menjadi bentuk = dengan jalan mengurangi dengan surplus variabel pada ruas kiri persamaan

3x1  2 x2  3x3  5

3x1  2 x2  3x3  s2  5; s2  0

• Ruas kanan harus non-negative  dapat dilakukan dengan mengalikan kedua ruas dengan -1 2 x1  3x2  7 x3  5  2 x1  3x2  7 x3  5 • Tanda pertidak-samaan akan berganti arah ketika dikalikan dengan -1

2 x1  x2  5 Selasa, 16 Februari 2016

 2 x1  x2  5 32

Bentuk Standar LP Model • Variable – Unrestricted variable yi  dapat dinyatakan dalam bentuk dua non-negative variabel dengan menggunakan subsitusi  yi=yi’-yi” dimana yi’ dan yi” nonnegative – Substitusi ini harus berlaku untuk semua constraint dan objective function

• Objective function – Objective function berbentuk maximumkan atau minimumkan – Namun, jika diperlukan maka bentuk maximumkan dapat dikonversikan menjadi bentuk minimumkan dengan jalan mengalikan fungsi tersebut dengan -1

maksimumka n z  5x1  2 x2  3x3 Minimumkan  z  5x1  2 x2  3x3

Selasa, 16 Februari 2016

33

Bentuk Standar LP Model Contoh • Ubah persamaan LP berikut dalam bentuk standar minimumkan z  2 x1  3 x2 subject to : x1  x2  10  2 x1  3 x2  5 7 x1  4 x2  6 x1  unrestricted x2  0

1. Constraint 2  kalikan dengan -1 dan kurangi dengan surplus variable s2 pada ruas kirinya 2. Constraint 3  tambahkan slack variable s3 pada ruas kirinya 3. Substitusikan x1 = x1’ – x1” dimana x1’, x1” ≥ 0 pada pers. Objective function dan semua constraint

minimumkan z  2 x1'  2 x1"  3x2 subject to : x1'  x1"  x2  10 2 x1'  2 x1"  3 x2  s2  5 7 x1'  7 x1"  4 x2  s3  6 x1' , x1" , x2 , x3 , s2 , s3  0

Selasa, 16 Februari 2016

34

Metode Simplex • Ingat penyelesaian secara grafis  titik optimum selalu berada pada titik ekstrem dari feasible region  metode simplex menggunaka logika ini untuk mencari titik optimum • Pencarian titik optimum pada metode simplex selalu diawali dari titik origin (0,0) untuk dilakukan pengujian apakah titik optimum sudah tercapai, kemudian pindah ke titik ekstrem lainnya selanjutnya dilakukan pengujian, demikian seterusnya hingga titik optimum tercapai

4 3

E

D

1 C

F

2

A

B

5

Titik A (origin) sebagai starting solution, kemudian pindah ke titik terdekat berikutnya (bisa F atau B). Pilihan berikunya F atau B tergantung pada koefisien dalam Objective function. Karena koefisien xE lebih besar dari xI dan persoalan kita maksimumkan, maka pilihan berikutnya adalah titik B

6

Selasa, 16 Februari 2016

35

Metode Simplex • Pada contoh sebelumnya, jika persoalan diubah menjadi bentuk standard, maka: maximize z  3 xE  2 xI  0s1  0s2  0s3  0s4 subject to : xE  2 xI  s1  6 2 x E  x I  s2  8  xE  xI  s3  1 x1  s4  2

Ada 4 persamaan dengan 6 yang tidak diketahui Secara umum, dalam bentuk standar, model LP akan memiliki m persamaan dengan n yang tidak diketahui dimana m < n.

xE , xI , s1 , s2 , s3 , s4  0

• Hal-hal yang harus diingat pada metode simplex – – – – – – – –

Buat n-m variabel sama dengan nol, dan selesaikan variabel lainnya Dengan memasukkan n-m variabel sama dengan nol, maka variabel lainnya harus non-negative Dalam contoh sebelumnya  titik A ketika xE=xI=0 menghasilkan s1=6, s2=8, s3=1 dan s4=2 Secara matematis hasil yang diperoleh dari m-n variabel sama dengan nol disebut dengan BASIC SOLUTION Jika basic solution ini memenuhi kriteria non-negative maka disebut FEASIBLE BASIC SOLUTION Variabel yang diset sama dengan nol disebut dengan NON-BASIC VARIABLES, sedangkan sisanya disebut dengan BASIC VARIABLES. Metode simplex hanya bekerja dengan feasible basic solution ketika bergerak dari satu titik ke titik lainnya. Penyelesaian untuk satu basic solution disebut satu kali iterasi, sehingga jumlah iterasi maksimum tidak akan melebihi jumlah basic solution dari bentuk standard  max iterasi Cmn 

Selasa, 16 Februari 2016

n! m!(n  m)! 36

Metode Simplex • Pada contoh sebelumnya, berikut adalah daftar basic variables and non-basic variables Extreme Non-basic (zero) Point Variable A x E, x I B

s2, x I

Basic Variable s1, s2, s3, s4 s1, x I , s3, s4

– Titik B dapat diperoleh dari A dengan jalan melakukan pertukaran variable  non-basic xE diganti dengan basic s2 sehingga pada titik B, s2 berubah menjadi non-basic variable dan xE menjadi basic variable – Konsep pertukaran variable ini membawa kita pada 2 kelompok istilah: • Entering variable  non-basic variable yang “masuk” menjadi basic variable • Leaving variable  basic variable yang “keluar” menjadi non-basic variable

– Dalam contoh kita pergerakan dari titik A ke titik B  xE adalah entering variable dan s2 adalah leaving variable

Selasa, 16 Februari 2016

37

Metode Simplex • Langkah-langkahnya: 1. 2.

3. 4.

Tentukan basic feasible solution awal dengan membuat n-m variabel (non-basic variable) sama dengan nol Pilih entering variable dari non-basic variable yang jika nilainya ditambah (di atas nol) akan meningkatkan nilai objective function saat ini. Jika tidak ada maka berarti sudah optimum. Hentikan perhitungan. Jika belum maka, lanjutkan ke langkah 3 Pilih leaving variable dari basic variable saat ini dan harus di set sama dengan nol ketika entering variable “masuk” menjadi basic variable Tentukan basic feasible solution yang baru dengan membuat entering variable menjadi basic variable dan leaving variable menjadi non-basic variable. Kembali ke langkah 2 Objective function z  3 xE  2 xI  0 xE  2 xI  s1  6 2 x E  x I  s2  8

Pers. Constraint

 xE  xI  s3  1 x I  s4  2 Selasa, 16 Februari 2016

38

Metode Simplex Starting feasible solution m-n = 6-4 = 2 variable diset = 0  xE = xI = 0  s1=6, s2=8, s3=1 dan s4=2 Solusi  z = 0 Entering variable

Basic z s1

z 1 0

xE -3 1

xI -2 2

s1 0 1

s2 0 0

s3 0 0

s4 0 0

Solution 0 6

s2

0

2

1

0

1

0

0

8

s3

0

-1

1

0

0

1

0

1

s4

0

0

1

0

0

0

1

2

Check optimality: Check kondisi z equation, koefisien pada xE dan xI masih bertanda negatif Oleh karena masih ada yang bertanda negatif  belum optimal  harus memilih entering variable Optimum tercapai jika semua nilai non-basic variable pada pers. Z adalah non-negative Entering variable dipilih dari koefisien yang memiliki nilai negatif terbesar  xE

Selasa, 16 Februari 2016

39

Metode Simplex •

• • •

Selanjutnya memilih leaving variable (dari basic variable saat ini; s1,s2,s3 dan s4) yang akan berfungsi sebagai leaving variable yang akan digantikan oleh entering variable Leaving variable dipilih salah satu dari basic variable saat ini yang akan mencapai nilai nol tercepat ketika entering variable mencapai harga maksimum Hal ini dapat dilakukan dengan menghitung ratio antara ruas kanan persamaan constraint dengan nilai positif dari koefisien yang ada pada kolom entering Yang terpilih sebagai leaving variable adalah yang memiliki ratio terkecil Entering column

Leaving Variable

Basic z z 1 s1 0

xE -3 1

xI -2 2

s1 0 1

s2 0 0

s3 0 0

s4 Solution ratio 0 0 0 6 6

s2

0

2

1

0

1

0

0

8

4

s3

0

-1

1

0

0

1

0

1

-

s4

0

0

1

0

0

0

1

2

-

Diabaikan krn ≤ 0 Selasa, 16 Februari 2016

Pivot Equation

Pivot Element 40

Metode Simplex • Setelah menentukan entering dan leaving variable, maka langkah selajutnya dilakukan operasi baris (row operation) dengan menggunakan metode Gauss-Jordan – Tipe 1  pivot equation  new pivot equation = old pivot equation / pivot elemen – Tipe 2  semua pers. termasuk z : • New equation = old equation – (its entering column coefficient) x new pivot equation

• Operasi tipe 1  membuat pivot elemen = 1 pada new pivot equation • Operasi tipe 2  membuat koefisien (selain elemen pivot) menjadi nol pada entering column.

Selasa, 16 Februari 2016

41

Metode Simplex • Feasible solution iterasi ke-2 Entering variable s1 s2 0 1 1/2 1 - 1/2

Basic z s1

z 1 0

xE 0 0

xI - 1/2 1 1/2

xE

0

1

1/2

0

s3

0

0

1 1/2

s4

0

0

s3 0 0

s4 0 0

Solution 12 2

1/2

0

0

4

0

1/2

1

0

5

1

0

0

0

1

2

Check optimality !!! Basic z s1

z 1 0

xE 0 0

xI - 1/2 1 1/2

s1 0 1

s2 1 1/2 - 1/2

s3 0 0

s4 0 0

Solution 12 2

xE

0

1

1/2

0

1/2

0

0

4

8

s3

0

0

1 1/2

0

1/2

1

0

5

3 1/3

s4

0

0

1

0

0

0

1

2

2

Selasa, 16 Februari 2016

ratio 1 1/3

42

Metode Simplex • Feasible solution iterasi ke-3 Basic z xI

z 0

xE 0 0

xI 0 1

s1 1/3 2/3

s2 1 1/3 - 1/3

xE

0

1

0

- 1/3

2/3

s3

0

0

0

-1

s4

0

0

0

- 2/3

1

s3

s4

Solution 12 2/3 1 1/3

0

0

3 1/3

1

1

0

3

1/3

0

1

2/3

0 0

0 0

– Check optimality  sdh tidak ada variable yang berharga negatif pada z equation  kondisi optimum tercapai

• Solusi: – xI = 1 1/3 – xE = 3 1/3 – Z = 12 2/3

Selasa, 16 Februari 2016

43

Metode Simplex • INGAT!!! – Memilih entering variable: • Persoalan maksimum  dipilih yang paling negatif pada z equation • Persoalan minimumkan  dipilih yang paling positif pada z equation

– Memilih leaving variable: • Baik pada persoalan maksimumkan maupun minimumkan, leaving variable dipilih dari ratio yang terkecil

– Kondisi optimum: • Persoalan maksimumkan  jika semua non-basic coefficient berharga non-negative • Persoalan minimumkan  jika semua non-basic coefficient berhaga nonpositive

Selasa, 16 Februari 2016

44

Metode Simplex – Artificial Starting Solution • Dalam contoh sebelumnya, kita menggunakan slack variable sebagai starting solution • Namun jika constraint yg kita miliki berbentuk ≥ atau = maka kita tidak memiliki starting solution • Perhatikan contoh berikut minimize z  4 x1  x2 subject to : 3x1  x2  3 4 x1  3 x2  6

Bentuk standard

minimize z  4 x1  x2 Kita memiliki 3 pers. Dg 4 subject to : variable  hanya 1 variable yang dapat menjadi non3x1  x2  3 basic variable 4 x  3x  x  6 1

2

3

x1  2 x2  4

x1  2 x2  x4  4

x1 , x2  0

x1 , x2 , x3 , x4  0

Dengan hanya 1 variable sebagai non-basic variable kita tidak dapat yakin bahwa dengan membuat vairable tersebut = 0 akan menghasilkan basic variable yang non-negative. Kita bisa menggunakan jalan trial and error, namun cara ini kurang efektif. Oleh karena itu perlu ada metode khusus yang dapat menangani kasus seperti ini dengan menggunakan artificial variable.

Selasa, 16 Februari 2016

45

Metode Simplex – Artificial Starting Solution • Dilakukan dengan menambahkan non-negative variable pada ruah kiri persamaan yang tidak memiliki starting basic variable. • Variable yang ditambahkan tersebut akan berfungsi sebagai slack variable dalam starting basic variable. • Namun karena variable ini tidak memiliki arti fisik dalam soal, maka persedur hanya valid jika variabel ini dipaksa untuk menjadi nol ketika titik optimum tercapai • Dengan kata lain, kita hanya menggunakan variable tersebut pada starting solution dan harus dipaksa menjadi nol pada solusi akhir, jika tidak maka hasilanya akan infeasible • Hal ini dilakukan dengan memberikan “penalti” pada variable tersebut pada objective function. Dua metode yang sering digunakan: – Metode Penalti (M-Technique) – Two-phase Technique

Selasa, 16 Februari 2016

46

Metode Simplex – Metode Penalti • Perhatikan contoh sebelumnya

minimize z  4 x1  x2 Pers. 1 dan 2 tidak memiliki subject to : variable yg dpt berfungsi sebagai slack  perlu 3x1  x2  3 adanya artificial variable, 4 x1  3 x2  x3  6 misalnya dinotasikan R1 dan x1  2 x2  x4  4 R2 x1 , x2 , x3 , x4  0

3x1  x2  R1  3 4 x1  3x2  x3  R 2  6 Kita dapat mem”penalti” R1 dan R2 dalam objective function dengan jalan memberikan very large positive coefficient

minimize z  4 x1  x2  MR1  MR2 Kita memiliki 3 pers dg 6 variabel  ada 3 variable yang = 0 subject to : Misalnya x1,x2 dan x3 kita nol kan, maka kita akan dapatkan R1=3, R2=6 dan x4=4  starting feasible solution 3x1  x2  R1  3 Untuk dapat menyelesaikan persoalan ini dg table simplex, 4 x1  3x2  x3  R2  6 maka hal ini dapat dilakukan dengan menghilangkan x1  2 x2  x4  4 komponen R dalam objective function x1 , x2 , x3 , R1 , R2 , x4  0 R1  3  3x1  x2 R2  6  4 x1  3x2  x3

Dengan mensubstitusikan pers ini dalam objective function

Selasa, 16 Februari 2016

z  4  7M x1  1  4M x2  Mx3  9M z  4  7M x1  1  4M x2  Mx3  9M 47

Metode Simplex – Metode Penalti

optimum

Basic z R1

z 1 0

x1 -4+7M 3

x2 -1+4M 1

x3 -M 0

R1 0 0

R2 0 0

x4 0 0

Solution 9M 3

ratio

R2

0

4

3

-1

0

1

1

6

1.5

x4

0

1

2

0

0

0

1

4

4

Basic z x1

z 1 0

x1 0 1

x2 (-1+5M)/3 1/3

x3 -M 0

R1 (4-7M)/3 1/3

R2 0 0

x4 0 0

Solution 4+2M 1

ratio

R2

0

0

5/3

-1

-4/3

1

0

2

1.2

x4

0

0

5/3

0

-1/3

0

1

3

1.8

Basic z x1

z 1 0

x1 0 1

x2 0 0

x3 1/5 1/5

R1 8/5-M 3/5

R2 -1/5-M -1/5

x4 0 0

Solution 18/5 3/5

ratio

x2

0

0

1

-3/5

-4/5

3/5

0

6/5

-2

x4

0

0

0

1

1

-1

1

1

1

Basic z x1

z 1 0

x1 0 1

x2 0 0

x3 0 0

R1 7/5-M 2/5

R2 -M 0

x4 -1/5 -1/5

Solution 17/5 2/5

x2

0

0

1

0

-1/5

0

-3/5

9/5

x3

0

0

0

1

1

-1

1

1

Selasa, 16 Februari 2016

1

3

3

48

Metode Simplex – Kasus2 Spesial • Degeneracy – Ingat, cara menentukan leaving variable  memilih ratio terkecil – Bagaimana jika nilai ratio yang terkecil lebih dari satu?  satu atau lebih variable akan bernilai nol pada iterasi berikutnya – Kondisi demikian disebut dengan degeneracy – Contoh: maximize z  3 x1  9 x2 Dg menggunakan x3 dan x4 sbg subject to : x1  4 x2  8 x1  2 x2  4 x1 , x2  0

slack variable maka:

Pada iterasi 0  terdapat 2 leaving variable (x3 dan x4)  x4 akan bernilai 0 pada iterasi 1  degeneracy  optimum tercapai pada iterasi 1 meskipun msh terdapat koefisien z berharga negative

Selasa, 16 Februari 2016

Iteration 0 x2 enter x3 leave 1 x1 enter x4 leave 2 optimum

Basic z x3 x4 z x2 x4 z x2 x1

x1 -3 1 1 -0.75 0.25 0.5 0 0 1

x2 -9 4 2 0 1 0 0 1 0

x3 0 1 0 2.25 0.25 -0.5 1.5 0.5 -1

x4 0 0 1 0 0 1 1.5 -0.5 2

Solution 0 8 4 18 2 0 18 2 0

49

ratio 2 2 8 0

Metode Simplex – Kasus2 Spesial • Degeneracy – Apakah implikasi dari problem degeneracy ini dalam prakteknya? – Perhatikan garfik di bawah  tiga garis melalui titik optimum  salah satu constraint bersifat redundant. – Sayangnya kita tidak dapat mengetahui constraint yang redundant dari table simplex 4.5

x2

4

const. 1

3.5

Const. 2

3

obj.function

2.5 2 1.5 1 0.5 0 0

2

4

Selasa, 16 Februari 2016

6

8

10

12

x1

14

50

Metode Simplex – Kasus2 Spesial • Degeneracy – Secara teoritis, degeneracy memiliki 2 implikasi: • Terjadinya fenomena cycling atau circling  jika anda lihat iterasi 1 dan 2 pada tabel simplex sebelumnya, maka nilai objective function tidak berubah (z=18)  prosedur simplex akan melakukan iterasi yang sama dan tidak akan meningkatkan nilai optimum dari objective function  perhitungan tidak akan berhenti (khususnya jika dilakukan dengan menggunakan program/software) • Oleh karena itu biasanya dalam program komputer ada teknik untuk tidak memasukkan kondisi cycling ini yaitu pencarian nilai optimum akan dihentikan jika ditemui kondisi degeneracy meskipun pada pers z masih terdapat nilai koefisien yang masih negatif (untuk maksimumkan) atau positif (untuk minimumkan)

Selasa, 16 Februari 2016

51

Metode Simplex – Kasus2 Spesial • Alternative Optima – Terjadi jika persamaan objective function paralel dengan binding constraint – Pada kondisi demikian  kondisi optimum terjadi pada lebih dari satu titik – Contoh: maximize z  2 x1  4 x2 subject to : x1  2 x2  5

5 4.5

Optimal basic soulution

4 3.5

x1  x2  4

3

x1 , x2  0

2.5

const. 1

const. 2 obj. function

2 1.5

1 0.5 0 0

Selasa, 16 Februari 2016

2

4

6

8

10

52

Metode Simplex – Kasus2 Spesial • Alternative Optima – Secara matematis Iteration 0 x2 enter x3 leave 1 x1 enter x4 leave 2 alternative optima

Basic z x3 x4 z x2 x4 z x2 x1

x1 -2 1 1 0 0.5 0.5 0 0 1

x2 -4 2 1 0 1 0 0 1 0

x3 0 1 0 2 0.5 -0.5 2 1 -1

x4 0 0 1 0 0 1 0 -1 2

Solution 0 5 4 10 2.5 1.5 10 1 3

ratio 2.5 4 5 3

– Pada iterasi 1 terlihat bhw titik optimum (x1=0, x2=2.5, z=10) titik B (pada gambar) – Bagaimana kita mengetahui adanya alternative optima pada tabel? – Lihat koefisien non-basic variable pada pers. Z pada iterasi 1  koefisien dari non-basic x1 =0 yang mengindikasikan bahwa x1 dpt masuk menjadi basic variable tanpa merubah nilai optimum – Iterasi ke 2 hanya berfungsi untuk merubah x1 menjadi basic variable dan menggantikan x4 tanpa merubah nilai optimum dan ini merupakan titik C pada gambar (x1=3, x2=1, z=10) Selasa, 16 Februari 2016

53

Metode Simplex – Kasus2 Spesial • Unbounded Solution – Kadang-kadang persoalan LP memiliki variable yang memiliki nilai meningkat tak terhingga solution space menjadi tak terhingga – Hal ini menyebabkan objective function akan meningkat terus (kasus maksimukan) atau menurun terus (kasus minimumkan) tak terhingga – Oleh karena itu, pada kasus demikian dikatakan bahwa nilai optimum adalah tak terhingga (unbounded solution) – Jika kita berhadapan pada kondisi yang unbounded solution, maka kita harus waspada apakah hal ini disebabkan karena model kita yang salah atau memang persoalan ini adalah unbounded solution Selasa, 16 Februari 2016

54

Metode Simplex – Kasus2 Spesial • Unbounded Solution

80

maximize z  2 x1  x2

70 const. 1

60

subject to : x1  x2  10

const. 2

50

obj. fuction

40 30

2 x1  40

20

10

x1 , x2  0

0 -10

0

5

10

15

20

25

30

35

40

-20

– Secara Matematis • Pada iterasi 0, x1 dan x2 merupakan kandidat entering variable, namun karena x1 paling negative, maka seharusnya dipilih sbg entering var. • Seharusnya x1 menggantikan x3, namun perhatikan koefisien dibawah x2 yang semuanya bernilai negatif dan nol  x2 dapat meningkat tak terhingga  yang meningkatkan z juga tak terhingga • Kesimpulannya  unbounded solution Basic z x3 x4 Selasa, 16 Februari 2016

x1 -2 1 2

x2 -1 -1 0

x3 0 1 0

x4 0 0 1

Solution 0 10 40

ratio 10 20 55

Metode Simplex – Kasus2 Spesial • Unbounded Solution – Secara umum untuk mengetahui bahwa model kita unbounded solution: • Jika dalam setiap iterasi koefisien constraint dari non-basic variable adalah non-positive maka adalah merupakan unbounded solution • Jika koefisien objective function adalah negatif (dalam kasus maksimumkan) atau positif (dalam kasus minimumkan) maka nilai optimumnya juga tak terhingga

Selasa, 16 Februari 2016

56

Metode Simplex – Kasus2 Spesial • Infeasible Solution – Terjadi jika constraint-constraint tidak dapat dipenuhi secara bersamaan  no feasible solution (infeasible solution) – Situasi ini tidak akan pernah terjadi jika seluruh constraint berbentuk ≤ (dg asumsi sisi ruas kanan adalah konstan dan non-negative)  karena slack variabel akan selalu memberikan feasible solution

Selasa, 16 Februari 2016

57

Analisis Sensitivitas dg Metode Simplex • Iterasi terakhir dari metode simplex, disamping berguna untuk mengetahui nilai optimum, juga berguna untuk analisis sensitivitas • Ingat !! – Sensitivitas 1 • Seberapa banyak material dapat ditingkatkan untuk meningkatkan pendapatan dari hasil optimum? • Seberapa banyak material dapat dikurangi tanpa mengurangi pendapatan dari hasil optimum?

– Sensitivitas 2 • Material manakah yang merupakan prioritas utama jika kondisi budget terbatas

– Sensitivitas 3 • Seberapa besar koefisien objective function dapat diubah (dinaik/turunkan) tanpa merubah titik optimum  harga

• Bagaimana melakukan analisis sensitivitas ini dg menggunakan tabel simplex?? Selasa, 16 Februari 2016

58

Analisis Sensitivitas dg Metode Simplex • Ingat kembali hasil optimum kita pada contoh pabrik cat Basic z xI

z 0

xE 0 0

xI 0 1

s1 1/3 2/3

s2 1 1/3 - 1/3

xE

0

1

0

- 1/3

2/3

s3

0

0

0

-1

s4

0

0

0

- 2/3

1

s3

s4

Solution 12 2/3 1 1/3

0

0

3 1/3

1

1

0

3

1/3

0

1

2/3

0 0

0 0

Optimum Solution Decision Variable

Optimum Value

Decision

xE

3 1/3 Produce 3 1/3 ton of exterior paint

xI

1 1/3 Produce 1 1/3 ton of interior paint

z

12 2/3 Resulting profit of 12 2/3 thousand dollars

Selasa, 16 Februari 2016

59

Analisis Sensitivitas dg Metode Simplex • Status of Resources Resources Raw Material A Raw Material B

Slack s1 = 0 s2 = 0

Status of Resources Scarce Scarce

Limit on excess of interior over exterior s3 = 3

Abundant

Limit on demand of interior

Abundant

s4 = 2/3

• Unit of Worth of a Resources Basic z

z 1

Selasa, 16 Februari 2016

xE 0

xI 0

s1 1/3

s2 1 1/3

s3 0

s4 0

Solution 12 2/3

60

LP dengan Spreadsheet • Selain dengan metode grafis dan matematis (secara manual), kita dapat menyelesaikan persoalan LP dengan bantuan software – – – – –

Spreadsheet (Ms Excel) dengan add-in solver Tora Lindo MatLab Dll

• Contoh persoalan produksi cat ekterior dan interior

Selasa, 16 Februari 2016

61

LP dengan Spreadsheet Contoh Lain • Sebuah perusahaan memproduksi 4 tipe frame kacamata (tipe 1,2,3 dan 4). Ke-4 tipe tersebut berbeda dari sisi ukuran, bentuk dan material yang digunakan. Masin-masing tipe memerlukan sejumlah tertentu tenga manusia (labor), logam (metal) dan kaca (glass) seperti terlihat pada tabel berikut Frame 1 Frame 2 Frame 3 Frame 4

Labor 2 1 3 2

Metal 4 2 1 2

Glass 6 2 1 2

Selling Price $28.50 $12.50 $29.25 $21.50

• Selama 1 minggu kedepan, perusahaan tersebut mampu membeli (mengadakan) 4.000 jam labor, 6.000 ons metal dan 10.000 ons glass. Unit cost masing-masing resources adalah $8,0 per labor, $0,5 per ons metal dan $0,75 per ons glass. • Dari sisi pasar, dapat diketahui bahwa maksimum permintaan pasar adalah 1.000 frame tipe 1, 2.000 frame tipe 2, 500 frame tipe 3 dan 1.000 frame tipe 4 • Berapakah masing-masing tipe frame kacamata yang harus diproduksi selama minggu depan agar profit maksimum??

Selasa, 16 Februari 2016

62

Contoh Soal LP • The Red Tomato Company operates two plants for canning their tomatoes and has three warehouse for storing the finished products. The company wants to arrange its shipments from the plants to the warehouses so that the requirements of the warehouse are met and show that shipping costs are kept at a minimum. The unit shipping cost is shown at table A. • Each week, plant I can produce up to 850 cases and plant II can produce up to 650 cases of tomatoes. Also, each week warehouse A requires 300 cases, warehouse B requires 400 cases and warehouse C requires 500 cases. If the number of cases shipped from plant I to warehouse A is represented by x1, from plant I to warehouse B by x2, and so on (see table B). Solve this problem.

Plant 1 Plant 2

Table A WH-A WH-B WH-C $ 0.25 $ 0.17 $ 0.18 $ 0.25 $ 0.18 $ 0.14

Selasa, 16 Februari 2016

Plant 1 Plant 2

Table B WH-A WH-B x1 x2 x4 x5

WH-C x3 x6

63

Blending Problem • Chandler oil has 5.000 barrels of crude oil 1 and 10.000 barrels of crude oil 2 available. Chandler sells gasoline and heating oil. These products are produced by blending together the two crude oils. Each barrel of crude oil 1 a “quality level” of 10 and each barrel of crude oil 2 has a “quality level” of 5. gasoline must have an average quality level of at least 8, whereas heating oil must have an average quality level of at least 6. Gasoline sells for $25 per barrels and heating oil sells for $20 per barrel. The advertising cost to sell one barrel of gasoline is $0,20 and the advertising cost to sell one barrel of heating oil is $0,10. Assume that demand for heating oil dan gasoline is unlimited. Chandler wants to maximize its profit

Selasa, 16 Februari 2016

64

Persoalan Jaringan (Network) • Transportation problem – Persoalan transportasi  mencari pola transportasi dari beberapa sumber menuju beberapa tujuan dengan biaya yang paling minim – Umumnya, informasi yang harus ada pada persoalan transportasi adalah: • Jumlah supply pada masing-masing sumber dan jumlah demand pada masing-masing tujuan. • Unit biaya transportasi yang dibutuhkan untuk mengangkut komoditi dari asal tertentu ke tujuan tertentu  seringkali unit biaya transportasi ini harus dicari sendiri

– Bentuk yang paling sederhana  single commodity  tujuan dapat menerima dari satu atau beberapa sumber – Tujuan model transportasi  menentukan berapa yang harus dikirim dari sumber mana ke tujuan mana sedemikian sehingga total biaya pengiriman seminimal mungkin Selasa, 16 Februari 2016

65

Persoalan Jaringan (Network) • Transportation problem (lanjutan) – Asumsi dasar dari persoalan transportasi  biaya transportasi pada satu rute tertentu proporsional dengan jumlah yang diangkut (seringkali tidak realistis, hati-hati!!!) Sources

Destinations

C11 : x11

1

1

b1

a2

2

2

b2 demand

...

...

Units of supply

a1

am

m

n

Units of

bn

Cmn : xmn

Selasa, 16 Februari 2016

66

Persoalan Jaringan (Network) • Transportation problem (lanjutan) – Misalkan xij adalah jumlah yang diangkut dari titik i ketitik j, maka persoalan transportasi dapat dituliskan sebagai berikut: m

n

minimize z   cij xij i 1 j 1

subject to : n

x j 1

ij

m

x i 1

ij

 ai

i  1,2,  m

 bj

j  1,2,  n

xij  0 for all i and j

– Jika kondisi  a   b terpenuhi, maka kondisi ini disebut dengan balanced transportation model  semua constraint berbentuk sama dengan – Pada kondisi unbalanced  perlu dummy variables m

i 1

Selasa, 16 Februari 2016

n

1

j 1

j

67

Persoalan Jaringan (Network) • Transportation problem (lanjutan) – Contoh • Balanced transport problem  sudah kita kerjakan minggu lalu • Unbalanced transport  coba anda kerjakan lagi untuk persoalan yang kita bahas minggu lalu tetapi dengan kondisi supply tidak mencukupi (supply lebih kecil daripada demand) dengan menggunakan konsep penalty cost (demand yang tidak terpenuhi akan muncul biaya penalti)

– Contoh lain  transhipment problem • Sebuah perusahaan memproduksi saus tomat di 3 (tiga) lokasi pabrik yang berbeda. Produk ini dapat dikirim oleh perusahaan tersebut langsung dari masing-masing pabrik ke konsumen, atau dapat dikirim dahulu ke gudang (warehouse) untuk selanjutnya baru dikirim ke konsumen. Perusahaan memiliki 2 (dua) gudang. Terdapat 2 lokasi demand yang harus disupply. Gambar jaringan (network) kasus ini dapat dilihat seperti gambar berikut: Selasa, 16 Februari 2016

68

Persoalan Jaringan (Network) T: 0

4 S: 200

1

S: 300

6

D: 400

7

D: 180

2

3

5

S: 100

ASAL

T: 0

1 2 3 4 5 6 7

1 9.00 0.40 -

2 5.00 8.00 -

TUJUAN 3 4 5 3.00 5.00 5.00 9.00 1.00 1.00 1.00 0.50 1.20 0.80 -

Selasa, 16 Februari 2016

6 20.00 8.00 10.00 2.00 2.00 7.00

7 20.00 15.00 12.00 12.00 12.00 1.00 -

• Asumsikan bahwa biaya untuk memproduksi saus tomat tersebut adalah sama untuk semua pabrik, sehingga tujuan perusahaan adalah meminimumkan biaya pengiriman. • Biaya pengiriman per ton saus tomat diberikan pada tabel di bawah (ribu dolar), tanda “ –” menunjukkan bahwa pengiriman pada rute tersebut tidak mungkin dilakukan, dan diasumsikan maksimum kapasitas pengiriman antar dua titik adalah 200 ton. • Perusahaan ingin menentukan pola distribusi yang memberikan biaya pengiriman yang paling minim

69

Non Linear Programming • Dalam persoalan optimisasi yang komplek, seringkali objective function dan/atau constraint tidak berbentuk persamaan linear. • Persoalan yang demikian disebut dengan NLP (Non Linear Programming) • Persoalan menjadi nonlinear disebabkan oleh beberapa hal antara lain: – Pengaruh dari satu input terhadap output tidak berbentuk linear  contoh, penerapan discount pada pembelian barang jika melebihi jumlah tertentu, persoalan iklan yang memiliki pengaruh besar pada saat awal iklan muncul dsb. – Dalam persoalan ekonomi (bisnis)  maximize revenue (profit)  R = P.Q (P adalah decision variable) Selasa, 16 Februari 2016

70

Basic Idea of NLP • Ketika anda menyelesaikan LP  dijamin solver akan dapat menemukan titik optimumnya, tetapi ketika anda berhadapan dengan NLP  kadang2 solver gagal untuk menemukan titik optimumnya (jika bisa kadang2 titik itu adalah sub optimal). Perhatikan fungsi berikut 4.00

Titik C  local maximum Titik A  global maximum Titik B  local minimum Titik D  global minimum

A

3.00 2.00

C

1.00 -

1.00

2.00

3.00

4.00

5.00

6.00

(1.00) (2.00)

Y=(x-1)(1-2)(x-3)(x-4)(x-5)

B

(3.00) (4.00)

Selasa, 16 Februari 2016

D

71

Convex and Concave Function • Solver dapat juga digunakan untuk menyelesaikan beberapa NLP  perlu pemahaman fungsi convex dan concave Line joining any two points is above the curve

Line joining any two points is below the curve

Selasa, 16 Februari 2016

Line joining any two points is above the curve

Line joining any two points is below the curve

Convex Function

Concave Function

72

Convex and Concave Function • Gambar di atas menunjukkan bahwa solver akan dapat mencari titik minimum jika fungsi berbentuk convex, dan mencari titik maksimum jika fungsi berbentuk concave • Hal ini terjadi karena pada fungsi convex, tidak ada local mimimum, dan pada fungsi concave tidak ada local maximum. • Dengan kata lain – Solver akan dapat mencari titik global maximum jika: • Objective function adalah concave atau logaritma objective function berbentuk concave • Constraint berbentuk linear

– Solver akan dapat mencari titik global minimum jika: • Objective function adalah convex • Constraint berbentuk linear Selasa, 16 Februari 2016

73

Jika asumsi tersebut tidak terpenuhi?? • Seringkali kita tidak dapat mengetahui apakah fungsi kita berbentuk convex atau concave. • Lantas bagaimna solusinya?? • Langkah yang umum digunakan: – Mencoba beberapa nilai awal yang berbeda – Menjalankan solver pada setiap nilai awal yang berbeda – Mengambil solusi terbaik dari hasil running solver tersebut

• Contoh  maximize (x-1)(1-2)(x-3)(x-4)(x-5), subject to x ≥ 1 dan x ≤ 5 Selasa, 16 Februari 2016

74

Contoh Lain – Pricing Model • Sebuah perusahaan memproduksi sesuatu dan menjualnya secara retail. Perusahaan ingin menentukan price yang akan memaksimumkan profit. Unit cost dan biaya marketing adalah $50, maka untuk mendapatkan profit, perusahaan tersebut harus memasang harga paling tidak sebesar $50. Untuk mendapatkan profit yang tinggi, maka perusahaan harus menjual dengan harga yang lebih tinggi, jumlah permintaan akan segera menurun jika harga jual naik karena persaingan. Apa yang harus dilakukan oleh perusahaan tersebut?? Selasa, 16 Februari 2016

75

Pricing Model • Model penyelesaian untuk perusahaan tersebut: – – – – –

Input variable  unit cost, demand function Decision variable  unit price Objective (target cell)  profit Other output variables  revenue, cost Constraints  unit price ≥ unit cost

• Jika perusahaan tersebut memasang tarif sebesar P, maka profitnya adalah (P-50)D dimana D adalah demand (jumlah produk terjual). Persoalannya adalah bahwa D juga tergantung dari P  ketika P naik maka D turun dan sebaliknya. • Oleh karena itu, langkah pertama adalah mengestimasi bagaimana D bervariasi terhadap perubahan P  mengestimasi fungsi demand. • Kita asumsikan bentuk demand memiliki 2 kemungkinan, yaitu linear (D=a-bP) atau demand dengan constant elasticity D=aPb. Selasa, 16 Februari 2016

76

Pricing Model • Ingat ekonomi mikro (PTE)!! – Elastisitas mengukur persentasi perubahan demand akibat perubahan harga sebesar 1% – Semakin tinggi nilai elastisitas, maka demand semakin terpengaruh atas perubahan harga (elastis) – Pada constant elasticity (D=aPb)  nilai elastisitas konstan pada semua variasi P – Pada fungsi demand linear  nilai elastisitas bervariasi

• Tidak tergantung bentuk fungsi demand seperti apa, tetapi yang jelas nilai a dan b pada fungsi tersebut harus diestimasi sebelum menentukan P • Estimasi ini dapat dilakukan dengan menggunakan bantuan excel trend line dengan dasar data historis. Misalnya diketahui ketika P= $70 jumlah D= 400 dan ketika P=$80 jumah D=300 Selasa, 16 Februari 2016

77

Tugas Pricing Model • Sebuah perusahaan memproduksi sesuatu dan menjualnya secara retail. Perusahaan ingin menentukan price yang akan memaksimumkan profit. Unit cost dan biaya marketing adalah $50, maka untuk mendapatkan profit, perusahaan tersebut harus memasang harga paling tidak sebesar $50. Untuk mendapatkan profit yang tinggi, maka perusahaan harus menjual dengan harga yang lebih tinggi, jumlah permintaan akan segera menurun jika harga jual naik karena persaingan. • Misalnya lokasi perusahaan di Amerikan dan market yang dituju adalah Inggris, dan diketahui bahwa demand di Inggris untuk produk ini berbentuk constant elasticity dengan parameter a= 27.556.760 dan b = -2,4 • Jika diketahi bahwa kurs $ terhadap £ (poundsterling) adalah ($/ £)=1,52 • Berapakah harga jual di Inggris yang harus ditetapkan oleh perusahaan tersebut??? Selasa, 16 Februari 2016

78

Persoalan Combinatorial • Adalah merupakan salah satu contoh untuk persoalan yang non-linear • Tujuan dari persoalan ini adalah untuk menentukan kombinasi dari beberapa alternative pilihan yang mungkin yang akan memenuhi fungsi tujuan

Selasa, 16 Februari 2016

79

Persoalan Combinatorial Contoh: • PT. Pertamina mendapat tugas untuk men-supply 3 jenis product oil (Premium, Kerosene, Solar) ke satu lokasi tertentu. • Untuk melakukan pengiriman tersebut Pertamina menggunakan tanker yang memiliki 5 cargo hold yang akan digunakan untuk mengangkut 3 jenis produk tersebut, dimana 1 cargo hold hanya boleh diisi oleh 1 jenis produk oil saja. • Jika diketahui ke-5 cargo hold tersebut memiliki kapasitas sebagai berikut: – CH 1 = 2.700 ton, CH 2 = 2.800 ton, CH 3 = 1.100 ton, CH 4 = 1.800 ton, dan CH 5 = 3.400 ton

• Dan jika diketahui bahwa demand untuk produk oil tersebut adalah sebagai berikut:

• Jika kekurangan melibihi dari yang diijinkan, maka ada penalty cost sebesar Rp. 100 Juta per ton kekurangan. • Bagaimanakah tanker tersebut harus diisi agar total cost (biaya kekurangan dan penalty cost) adalah yang paling minim Selasa, 16 Februari 2016

80

Project Management • What is a project? – Organizations perform work. Work generally involve either operations or projects, although the two may overlap. Operations and projects share many characteristics, for example: • Performed by people • Constrained by limited resources • Planned, executed and controlled

– Operations and projects differ primarily in that operations are ongoing and repetitive while projects are temporary and unique. – Projects has a beginning, an end and one or more well-defined goals. – The project could be the development of a software, building of a new house, building of a new ship and many others – Typically, a team of employees is assigned to a project and one member of the team is designated as a project manager. – The team is assigned to complete the project within a certain time, certain budget, and certain specification. Selasa, 16 Februari 2016

81

Project Management • Management science (operation management) tends to focus on the quantitative tools that have been developed to manage projects. • These go under the twin acronyms of PERT (Program Evaluation and Review Technique) and CPM (Critical Path Method). • These methods were developed independently about a half century ago. • PERT was developed jointly by the U.S. Navy, Lockheed, and the consulting firm of Booz, Allen, and Hamilton in their work on the Polaris nuclear missile • CPM was developed at DuPont and Remington-Rand to improve the construction of new production facilities and the shut-down of existing facilities. • The main difference between PERT and CPM is that CPM was developed for projects with a set of commonly performed tasks, where the task times are fairly well known. • In contrast, PERT was developed for projects with tasks where scien-tists had little experience and could not estimate their times with much certainty.

Selasa, 16 Februari 2016

82

Project Management • Over the years, the two methods have tended to merge, so that people now often speak of PERT/CPM models. In either case, the emphasis is on a project that starts at some point and ends some time later. • The project consists of a number of tasks that must be completed for the project to be completed. • These tasks have durations (the time it takes to complete them, assumed known for CPM, random for PERT), they typically cost money, and they often require nonfinancial resources such as people and facilities. They also have precedence relationships. • For example, task G might not be able to start until tasks B, D, and F are finished. • These precedence relationships put constraints on what can be done when. Selasa, 16 Februari 2016

83

Project Management • Projects have three dimensions: time, resources, and scope. • The usual discussion of PERT/CPM focuses primarily on the time dimension. • How long will the project take to complete if everything goes according to schedule, which tasks form bottlenecks that pre-vent the project from being completed earlier, and which tasks have some slack, in the sense that they can be delayed to some extent without delaying the project? • These questions are the usual focus of PERT/CPM models, and we too focus primarily on the time dimension. However, we also discuss the resource dimension. Selasa, 16 Februari 2016

84

The Basic CPM Model • The basic CPM procedure assumes that we know (1) the activities that comprise the project, (2) the precedence relationships among activities, and (3) the time required to complete each activity. • This time, called the activity duration, is assumed to be known with certainty. • To proceed, we need a list of the activities that make up the project. The project is complete when all of the activities have been completed. • Each activity has a set of activities called its immediate predecessors that must be completed before the activity begins. It also has a set of activities called its immediate successors that cannot start until it has finished. Selasa, 16 Februari 2016

85

The Basic CPM Model • A project network diagram is usually used to represent the precedence relationships among activities. • Two types of diagrams do this, activity-on-node (AON) networks and activity-on-arc (AOA) networks, and proponents of each type have rather strong feelings. • We favor AON networks because we believe they are more intuitive. • In the AON representation of a project, there is a node for each activity. • Then there is an arc from node i to node j if node i is an immediate predecessor of node j. Selasa, 16 Februari 2016

86

The Basic CPM Model • To illustrate this, consider a project that consists of five activities, labeled A, B, C, D, and E. Activities A and B can start immediately. • Activity C cannot start until activity B is finished, activity D cannot start until activity A is finished, and activity E cannot start until activities A and C are both finished. The project is finished when all activities are finished.

Selasa, 16 Februari 2016

87

The Basic CPM Model • The rules for drawing an AON network are as follows: – Include a node for each activity and place its duration next to the node. – Include an arc from node i to node j only if node i is an immediate predecessor of node j. – Include a Start and a Finish node with zero durations. There is an arc from the Start node to each node that has no predecessors. These activities can all start immediately. There is an arc into the Finish node from each node that has no successors. When all of these activities have been finished, the project is finished. Selasa, 16 Februari 2016

88

The Basic CPM Model • Two problems are typically analyzed in project scheduling. In the first, the goals are to find the time to complete the project and locate the bottleneck activities. • In the second, the goal is to find cost-efficient ways to complete the project within a given deadline. • In each of these problems, a key concept is a bottleneck activity, called a critical activity. • More precisely, a critical activity is an activity that, if its duration increases, the time to complete the project necessarily increases. • The set of critical activities is called the critical path. Selasa, 16 Februari 2016

89

The Basic CPM Model • The critical path through a project network is the longest path from the Start node to the Finish node, using the durations as “distances.” • If the project network is not too complex, this longest path can be determined easily. • For example, there are three paths from Start to Finish in previous figure : Start  A  D  Finish; Start  A  E  Finish; and Start B  C  E  Finish. • The lengths of these paths are 8 + 12 = 20, 8 + 6 = 14, and 10 + 3 + 6 = 19, respectively. Therefore, the critical path is the longest path, Start  A  D  Finish, the critical activities are A and D, the time to complete the project is 20, and all activities other than A and D have some slack. • Although this “longest path through a network” approach is appealing and can be implemented fairly easily with Solver, it doesn’t generalize easily to the case where the activity durations are random. Therefore, we do not pursue this approach Selasa, 16 Februari 2016

90

The Basic CPM Model • We first require some basic insights. Let ESj be the earliest time activity j can start, and let EFj be the earliest time activity j can finish. • Clearly, the earliest an activity can finish is the earliest time it can start plus its duration. • For example, if the earliest activity D can start is time 8, and its duration is 12, then the earliest D can finish is time 20. • In general, if dj is the duration of activity j, we have EFj = ESj + dj …. (1) Selasa, 16 Februari 2016

91

The Basic CPM Model • Now, if activity i is an immediate predecessor of activity j, activity j cannot start until activity i finishes. • In fact, activity j cannot start until all of its immediate predecessors have finished, so the earliest time activity j can start is the maximum of the earliest finish times of its immediate predecessors: ESj = max(EFi) … (2) • Here, the maximum is over all immediate predecessors i of activity j. Selasa, 16 Februari 2016

92

The Basic CPM Model • The earliest start time for the Start node is 0—it can start right away. • The earliest start time of the Finish node: Project completion time = ESFinish node …(3) • This calculation of the earliest start and finish times through Equations (1) to (3) is usually called the forward pass of the CPM algorithm. The reason for this term is that the calculations are performed in “forward” chronological order of the activities. Selasa, 16 Februari 2016

93

The Basic CPM Model • To find the critical activities and the critical path, two other equations are required. • Let LSj and LFj be the latest time activity j can start and the latest time it can finish without increasing the project completion time. • Again, analogous to Equation (1), we have • LSj = LFj – dj …(4) • The equation is written in this form because you find LFj first and then use it to find LSj Selasa, 16 Februari 2016

94

The Basic CPM Model • Now suppose activity j is an immediate successor of activity i . Then activity i must be finished before activity j can start. In fact, a bit of thought should convince you that the latest time activity i can finish is the minimum of the latest start times of all its successors: • LFi = min(LSj) …(5) • For example, suppose activity F has two successors, G and H, and you somehow find that the latest start times for G and H are 26 and 30. In this case, the bottleneck, at least for this part of the network, is activity G. The latest it can start without delaying the project is 26; activity H can start later. Therefore, activity G’s predecessor, activity F, has to be finished no later than time 26. Selasa, 16 Februari 2016

95

The Basic CPM Model • You can use Equations (4) and (5) to calculate the latest start times and latest finish times for all activities, beginning with the fact that the latest finish time for the Finish node is the project completion time. • This set of calculations is called the backward pass of the CPM algorithm because you work through the activities in “backward” chronological order. • Then you can calculate the slack of each activity j as the difference between the latest start time and the earliest start time of activity j: • Slack of activity j = LSj – Esj …(6) • The idea behind slack is simple. If an activity has any positive slack, this activity has some room to maneuver—it could start a bit later without delaying the project. In fact, its duration could increase by the amount of its slack without delaying the project. However, if an activity has zero slack, any increase in its duration necessarily delays the project. Therefore, the critical path consists of activities with zero slack.

Selasa, 16 Februari 2016

96

Example - Creating an Office LAN • An insurance company has decided to construct a LAN. The project consists of 15 activities, labeled A through O, as listed in Table below. This table indicates the immediate predecessors and immediate successors of each activity, along with each activity’s expected duration. (At this point these durations are assumed known.) Note that activity A is the only activity that can start right away, and activity O is the last activity to be completed. The company wants to know how long the project will take to complete, and it also wants to know which activities are on the critical path. Selasa, 16 Februari 2016

97

Example - Creating an Office LAN

Selasa, 16 Februari 2016

98

Selasa, 16 Februari 2016

99