metode simpleks ”riset operasional” pertemuan...

Metode simpleks”riset operasional”

Pertemuan 6

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

2

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

3

BentukRumus Umum LP:

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

4

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

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

6

iterasi

7

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

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

2.ITERASI

Mulailah iterasi pertama beruparencana dasar awal denganmenggunakan table dasar

simpleks

10

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

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

4.Melakukan subtitusi

Dengan menambah dua barisdalam table.

13

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.

5.Pengembangan pemecahanMenentukan variable mana yang

akan menambah laba terbesar→berarti variabel M meningkat $8

pada kolom Cj – Zj

15

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

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.

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

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

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

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

𝒁𝒋 =

𝒊=𝟏

𝒏

𝒃𝒊𝑪𝒋

iterasi

22

1.Menentukan variable laba

terbesarMenentukan variabel mana yang akan

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

23

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

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.

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

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

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

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𝒁𝒋 =

𝒊=𝟏

𝒏

𝒃𝒊𝑪𝒋

“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

Latihansoal!

31

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

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

THANKS!34