metode simpleks ”riset operasional” pertemuan...

34
Metode simpleks ”riset operasional” Pertemuan 6

Upload: others

Post on 06-Jan-2020

22 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

Metode simpleks”riset operasional”

Pertemuan 6

Page 2: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

Sub Pembahasan:1. Definisi2. bentuk umum3. tahapan penyelesaian4. Contoh soal

2

Page 3: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

SIMpleks!Suatu metode penyelesaian untuk mencari solusioptimal secara iteratif (berulang-ulang) dimulai dari titikdasar awal (sumber daya belum digunakan)

3

Page 4: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

BentukRumus Umum LP:

𝑍 = 𝐶1𝑋1 + 𝐶2𝑋2 +⋯+ 𝐶𝑛𝑋𝑛

4

Kendala:𝑎11𝑥1 + 𝑎12𝑥2 +⋯+ 𝑎1𝑛𝑥𝑛 ≤≥ 𝑏1𝑎21𝑥1 + 𝑎22𝑥2 +⋯+ 𝑎2𝑛𝑥𝑛 ≤≥ 𝑏2

Page 5: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

Suatu perusahaan furniture membuat meja dan kursi yang harus diproses melalui perakitan dan pemolesan. Harga satumeja $8 dan harga satu kursi $6. Untuk merakit satu mejadibutuhkan 4 jam dan untuk satu kursi = 2 jam, maksimal waktutersedia 60 jam. Sedangkan untuk pemolesan satu mejadibutuhkan waktu 2 jam, dan untuk satu kursi 4 jam, denganwaktu tersedia 48 jam. Berapakah jumlah meja dan kursi yang dapat dihasilkan untuk mencapai laba maksimum?

5

Page 6: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

6

Page 7: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

iterasi

7

Page 8: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

1.Persamaan ditambah Menambah

variable slackUbahlah kendala pertidaksamaan menjadi

persamaan dengan menambah variable slack atau variable surplus. Demikian juga fungsi

tujuan diubah sesuai fungsi perubahan kendala. Pada fungsi tujuan koefisien variable basis (S)

adalah nol.

8

Page 9: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

Misal:Fungsi Tujuan:× Max laba = 8M + 6KFungsi kendala:× Perakitan: 4M + 2K ≤ 60 jam× Pemolesan: 2M + 2K ≤ 48 jam

Menjadi:× Z = 8M + 6M + 0S1 + 0S2

Kendala:× 4M + 2K + S1 + 0S2 = 60 jam× 2M + 4K + 0S1 + S2 = 48 jam

Semua variabel ≥ 0

9

Page 10: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

2.ITERASI

Mulailah iterasi pertama beruparencana dasar awal denganmenggunakan table dasar

simpleks

10

Page 11: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

11

Cj Mix Jumlah 8 6 0 0

M K S1 S2

0 S1 60 4 2 1 0

0 S2 48 2 4 0 1

Cj Kolom

(laba/unit)

Kolom

paduan

produk

Kolom

konstanta Kolom variabel

Dua baris

fungsi kendala

Baris variabel

Baris Cj

Slack waktuProduk nyata

Page 12: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

3.Penyelesaian awal

Mulai dengan tidak memproduksimeja dan kursi (titik 0,0 dalam

grafik), dengan Cj=0, berartitersedia jam kerja untuk meja 60

jam serta untuk kursi 48 jam (seperti isi tabel sebelumnya)

12

Page 13: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

4.Melakukan subtitusi

Dengan menambah dua barisdalam table.

13

Page 14: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

14

Cj Mix Jumlah 8 6 0 0

M K S1 S2

0 S1 60 4 2 1 0

0 S2 48 2 4 0 1

Zj 0 0 0 0 0

Cj – Zj 8 6 0 0

𝑍𝑗 =

𝑖=1

𝑛

𝑏𝑖𝐶𝑗

𝟎 = (𝟎 × 𝟔𝟎) + (𝟎 × 𝟒𝟖)

Angka 8 dan 6 pada kolom Cj – Zjmenunjukkan penambahan laba setiappenambahan 1 unit M dan K.

Page 15: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

5.Pengembangan pemecahanMenentukan variable mana yang

akan menambah laba terbesar→berarti variabel M meningkat $8

pada kolom Cj – Zj

15

Page 16: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

6.Menentukan variable yang

digantiMenghitung ratio tiap baris persamaan

kendala dengan rumus (jumlah jam tersedia dibagi jam pada kolom M →

yang terkecil harus diganti→ berarti S1

(leaving variable) harus diganti denganM (entering variable)

16

Page 17: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

17

Cj Mix Jumlah 8 6 0 0

RatioM K S1 S2

0 S1 60 4 2 1 0 60:4=15

0 S2 48 2 4 0 1 48:2=24

Zj 0 0 0 0 0

Cj – Zj 8 6 0 0

Angka 4 pada perpotongan kolom masuk dan baris keluar disebut Pivot Element.

Page 18: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

7.Perbaikan

Merubah baris S1 menjadi M, menggantiangka kolom Cj dari 0 menjadi 8, serta

menghitung persamaan baru M denganrumus (yang lama dibagi dengan pivot

element).

18

Page 19: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

8.baris lainnya

Untuk baris lainnya (S2), Cj tetap 0, dan persamaan baru dihitung dengan

rumus (elemen baris lama – (koefisienbaris lama x elemen baris baru M)

19

Page 20: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

20

Cj Mix Jumlah 8 6 0 0

M K S1 S2

8 M 15 4/4=1 2/4=1/2 1/4 0

0 S2 48-(2x15)=18 2-(2x1)=0 4-(2x1/2)=3 0-(2x1/4)=-1/2 1-(2x0)=1

Page 21: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

Hasil Iterasi pertamaTabel Simpleks

21

Cj Mix Jumlah 8 6 0 0

RatioM K S1 S2

8 M 15 1 1/2 1/4 0

0 S2 18 0 3 -1/2 1

Zj 120 8 4 2 0

Cj – Zj 0 2 -2 0

Masih ada peluang untuk meningkatkan laba, karena angka 2 pada baris Cj –Zj, kolom K menunjukkan penambahan lama dengan peningkatan variabel K →berarti dapat dilakukan kembali iterasi

𝒁𝒋 =

𝒊=𝟏

𝒏

𝒃𝒊𝑪𝒋

Page 22: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

iterasi

22

Page 23: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

1.Menentukan variable laba

terbesarMenentukan variabel mana yang akan

menambah laba terbesar→ berarti variable K →meningkat $2 pada kolom Cj – Zj

23

Page 24: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

2.Menentukan variable diganti

Menghitung ratio tiap baris persamaan kendaladengan rumus (jumlah dibagi jam tersedia) pada kolom K → yang terkecil haris diganti→ berarti

S2 (leaving variable) harus diganti dengan K (entering variable)

24

Page 25: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

25

Cj Mix Jumlah 8 6 0 0

RatioM K S1 S2

8 M 15 1 1/2 1/4 0 10:1/2=30

0 S2 18 0 3 -1/2 1 18:3=6

Zj 120 8 4 2 0

Cj – Zj 0 2 -2 0

Angka 3 pada perpotongan kolom masuk dan baris keluar disebut Pivot Element.

Page 26: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

3.Perbaikan

Mengubah baris S2 menjadi K, mengganti angkakolom Cj dari 0 menjadi 6, dan menghitung

persamaan baru K dengan rumus (yang lama dibagi dengan pivot element)

26

Page 27: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

4.Baris lainnya

Untuk baris lainnya (S2), Cj dari M tetap 8, dan persamaan baru dihitung dengan rumus

(elemen baris lama – (koefisien baris lama x elemen baris baru)

27

Page 28: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

28

Cj MIx Jumlah 8 6 0 0

M K S1 S2

8 M 15-(1/2x6)=12 1-

(1/2x0)=1

½-(1/2x1)=0 ¼-(1/2x-

1/6)=1/3

0-

(1/2x1/3)=-

1/6

6 K 18:3 = 16 0:3=0 3:3=1 -1/2:3=-1/6 1:3=1/3

Page 29: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

Hasil Iterasi keduaTabel Simpleks

29

Cj Mix Jumlah 8 6 0 0

RatioM K S1 S2

8 M 15 1 0 1/3 1/6

6 K 6 0 1 -1/6 1/3

Zj 132 8 6 5/3 2/3

Cj – Zj 0 0 -5/3 -2/3

Nilai selisih Cj – Zj pada variabel M dan K sudah 0, berarti tidak ada lagi peluanguntuk meningkatkan laba→ SUDAH OPTIMUM𝒁𝒋 =

𝒊=𝟏

𝒏

𝒃𝒊𝑪𝒋

Page 30: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

“Laba maksimum sebesar $132 diperoleh dengan kombinasi

produk meja sebanyak 12 unit dan kursi sebanyak 6 unit.

30

× Total jam kerja perakitan:

4 (12) + 2 (6) = 60 jam

× Total jam kerja pemolesan:

2 (12) + 4 (6) = 48 jam

kesimpulan

Page 31: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

Latihansoal!

31

Page 32: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

Persamaan matematis suatu program linear sebagai berikut:Maksimisasi: Z = 3X1 + 2X2

Dengan pembatas:4X1 + 5X2 ≤ 602X1 + 2X2 ≤ 30X1, X2 ≥ 0Carilah X1, X2 dan Z

32

Page 33: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

PT. Agro Persada bermaksud membuat 2 jenis pupuk, yakni pupukpadat dan pupuk cair. Untuk itu dibutuhkan 2 macam zat kimia, yaitu A dan B. Jumlah zat kimia tersedia adalah A = 200 kg dan B = 360 kg.Untuk membuat 1 kg pupuk padat dibutuhkan 2 kg A dan 6 kg B.Untuk membuat 1 liter pupuk cair dibutuhkan 5 kg A dan 3 jg B.Bila keuntungan yang diperoleh dari setiap membuat 1 kg pupukpadat = $3, sedangkan dari setiap 1 liter pupuk cair = $2, berapajumlah kg pupuk padat dan pupuk cair sebaiknya diproduksiuntuk mendapat keuntungan maksimum.

33

Page 34: Metode simpleks ”riset operasional” Pertemuan 6danjunisme.com/.../2019/10/Pertemuan-6-Metode-Simpleks.pdfDua baris fungsi kendala Baris variabel Baris Cj Produk nyata Slack waktu

THANKS!34