TEKNIK RISET OPERASI

Download Sebelumnya kita telah mengerjakan soal : Sebuah perusahaan membuat 2 buah macam sepatu. Sepatu yang dibuat terdiri atas 2 macam yaitu: • Me...

0 downloads 508 Views 134KB Size
Teknik Riset & Operasi - P3

Subarono – 12111089

---------------------------------------------------------------------------------------------------------------------------------->>>Take From: onnosbarono.wordpress.com

TEKNIK RISET OPERASI METODE SIMPLEX DALAM LINIER PROGRAMMING Sebelumnya kita telah mengerjakan soal : Sebuah perusahaan membuat 2 buah macam sepatu. Sepatu yang dibuat terdiri atas 2 macam yaitu: • Merk I1 dengan sol karet • Merk I2 dengan sol kulit Dan dikerjakan dengan mesin yang masing-masing mesin mempunyai peruntukkan sendirisendiri yaitu: • Mesin 1 membuat sol dari karet • Mesin 2 membuat sol dari kulit • Mesin 3 membuat bagian atas sepatu dan alas sol Beban kerja untuk setiap mesin dan proses pengerjaan sebagai berikut: • Tiap lusin merk I1 dikerjakan dengan mesin 1 selama 2 jam lalu mesin 3 selama 6 jam • Tiap lusin merk I2 dikerjakan dengan mesin 2 selama 3 jam lalu mesin 3 selama 5 jam Jam kerja untuk masing-masing mesin adalah: • Mesin 1 memiliki jam kerja: 8 jam • Mesin 2 memiliki jam kerja: 15 jam • Mesin 3 memiliki jam kerja: 30 jam Laba setiap lusinnya: Merk I1 sebanyak Rp. 30.000; dan Merk I2 sebanyak Rp. 50.000; Berapa lusinkan yang harus diproduksi untuk mencapai laba maksimum? Dengan menggunakan metode linier programming maka dalam pertemuan kedua digunakan Metode Simplex dalam Linier Programming. Langkah-langkah dengan metode ini adalah: 1. Mengubah fungsi tujuan dan batasan a) Semua nilai C(Koefisien),Xn digeser ke kiri untuk fungsi tujuan b) semua fungsi batasan yang mempunyai tanda “≤“ harus diubah menjadi “=” dengan menambahkan variabel slack yaitu Xn+1, Xn+2,........Xn+m 2. Menyusun Tabel Variabel Dasar

Z

X1

X2

...Xn+m

Nk

Z

1

-C1

C2

-Cn+1

0

Xn+1

0

a11

a12

......

b

…..

…..

…...

an1

am2

am+n

….. Xn+m

0

bm

3. Memilih kolom kunci Kolom kunci adalah kolom yang digunakan untuk merubah tabel. Yaitu dengan cara memilih kolom yang mempunyai nilai pada fungsi tujuan(Z) bernilai angka negatif paling besar. 4. Memilih baris kunci • Cari indeks tiap baris dengan menggunakan rumus sebagai berikut: Index = Nk/Nilai kolom kunci •

Pilih baris yang mempunyai indeks positif dan terkecil

5. Mengubah nilai baris kunci

Teknik Riset & Operasi - P3

Subarono – 12111089

---------------------------------------------------------------------------------------------------------------------------------->>>Take From: onnosbarono.wordpress.com

6. Mengubah nilai-nilai selain baris kunci Baris baru = Baris lama – ((koefisien pada kolom kunci) x Nilai baru baris kunci) 7. Mengulangi langkah 3 s/d 6 sampai tidak ada lagi nilai negatif di fungsi tujuan (Z) Penyelesaian: Diketahui fungsi tujuan: Z = 3x1 + 5x2 Fungsi batasan(kendala) : • • •

2x1 + 0 ≤ 8 0 + 3x2 ≤ 15 6x1 + 5x2 ≤ 30

…......................... persamaan (1) …......................... persamaan (2) …......................... persamaan (3)

Langkah 1: a) Semua nilai C,Xn digeser ke kiri untuk fungsi tujuan sehingga akan menjadi: Z - 3x1 - 5x2 = 0 b) semua fungsi batasan yang mempunyai tanda “≤“ harus diubah menjadi “=” dengan menambahkan variabel slack yaitu Xn+1, Xn+2,........Xn+m 2x1 + x3 = 8 3x2 + x4 = 15 6x1 + 5x2 +x5 = 30 Langkah 2: Membuat tabel Var. Dasar Z

…........ persamaan (1) menambahkan variabel slack X3 …........ persamaan (2) menambahkan variabel slack X4 …........ persamaan (3) menambahkan variabel slack X5

X1

X2

X3

X4

X5

Nk

Z

1

-3

-5

0

0

0

0

X3

0

2

0

1

0

0

8

X4

0

0

3

0

1

0

15

X5

0

6

5

0

0

1

30

Langkah 3: Mencari kolom kunci dari tabel di atas dan terlihat pada saat Z=-5 yaitu kolom yang mempunyai nilai pada fungsi tujuan(Z) bernilai angka negatif paling besar. Kolom kunci

Var. Dasar

Z

X1

X2

X3

X4

X5

Nk

Z

1

-3

-5

0

0

0

0

X3

0

2

0

1

0

0

8

X4

0

0

3

0

1

0

15

X5

0

6

5

0

0

1

30

Langkah 4: • Mencari baris kunci dengan menghitung indeks terlebih dahulu dengan menggunakan rumus: Index = Nk/Nilai kolom kunci

Teknik Riset & Operasi - P3

Subarono – 12111089

---------------------------------------------------------------------------------------------------------------------------------->>>Take From: onnosbarono.wordpress.com

dengan hasilnya: Z ------------> 0/5 = 0 X3 ------------> 8/0 = ∞ X4 ------------> 15/3 = 5 X5 ------------> 30/5 = 6 •

Pilih baris yang mempunyai indeks positif dan terkecil yaitu pada saat: X4 ------------> 15/3 = 5 Var. Dasar

Z

X1

X2

X3

X4

X5

Nk

Indeks

Z

1

-3

-5

0

0

0

0

0

X3

0

2

0

1

0

0

8



X4

0

0

3

0

1

0

15

5

X5

0

6

5

0

0

1

30

6

Baris kunci

Langkah 5: Mengubah nilai “Baris Kunci” dengan pembagian nilai baris kunci awal/nilai potong Dimana Nilai potong = “3” sehingga menjadi: Kolom kunci

Var. Dasar

Z

X1

X2

X3

X4

X5

Nk

Z

1

-3

-5

0

0

0

0

X3

0

2

0

1

0

0

8

X2

0

0/3

3/3

0/3

1/3

0/3

15/3

X5

0

6

5

0

0

1

30

Baris Kunci

Langkah 6: Mengubah nilai selain “Baris Kunci” dengan rumus: Baris baru = Baris lama – ((koefisien pada kolom kunci) x Nilai baru baris kunci) maka: Untuk nilai baris Z :

-5 x

[

-3

-5

0

0

0

0

]

[

0

1

0

1/3

0

5

]

[

-3

-5

0

0

0

0

]

[

0

-5

0

-5/3

0

-25

]

[

-3

0

0

5/3

0

25

]

(-) Baris Baru untuk Z

Untuk nilai baris X3 :

0x

[

2

0

1

0

0

8

]

[

0

1

0

1/3

0

5

]

[

2

0

1

0

0

8

]

[

0

0

0

0

0

0

]

[

2

0

1

0

0

8

]

(-) Baris Baru untuk X3

Teknik Riset & Operasi - P3

Subarono – 12111089

---------------------------------------------------------------------------------------------------------------------------------->>>Take From: onnosbarono.wordpress.com

Untuk nilai baris X5 :

5x

[

6

5

0

0

1

30

]

[

0

1

0

1/3

0

5

]

[

6

5

0

0

1

30

]

[

0

5

0

5/3

0

25

]

[

6

0

0

-5/3

1

5

]

(-) Baris Baru untuk X5

Tabel baru menjadi: Var. Dasar

Z

X1

X2

X3

X4

X5

Nk

Z

1

-3

0

0

5/3

0

25

X3

0

2

0

1

0

0

8

X2

0

0

1

0

1/3

0

5

X5

0

6

0

0

-5/3

1

5

Karena pada fungsi tujuan(Z) masih mengandung nilai negatif maka diulang kembali mencari kolom dan baris kunci yang lain. Var. Dasar

Z

X1

X2

X3

X4

X5

Nk

Z

1

-3

0

0

5/3

0

25

X3

0

2

0

1

0

0

8

X2

0

0

1

0

1/3

0

5

X5

0

6

0

0

-5/3

1

5

Langkah 1: Mencari kolom kunci yaitu kolom yang mempunyai nilai negatif terbesar terletak pada kolom X1 sehingga kita tandai:

Var. Dasar

Z

X1

X2

X3

X4

X5

Nk

Z

1

-3

0

0

5/3

0

25

X3

0

2

0

1

0

0

8

X2

0

0

1

0

1/3

0

5

X5

0

6

0

0

-5/3

1

5

Langkah 2: Mencari baris kunci yaitu dengan cara: • Mencari indeks tiap baris dengan cara: Index = Nk/Nilai kolom kunci dengan hasilnya: Z ------------> 8/-3 = -8/3 X3 ------------> 8/2 = 4 X2 ------------> 5/0 = ∞ X5 ------------> 5/6 = 5/6

Teknik Riset & Operasi - P3

Subarono – 12111089

---------------------------------------------------------------------------------------------------------------------------------->>>Take From: onnosbarono.wordpress.com

Mencari nilai indeks yang bernilai Positif Terkecil yaitu pada baris X5 sehingga baris kunci pada X5



Kolom Kunci

Var. Dasar

Z

X1

X2

X3

X4

X5

Nk

Z

1

-3

0

0

5/3

0

25

X3

0

2

0

1

0

0

8

X2

0

0

1

0

1/3

0

5

X5

0

6

0

0

-5/3

1

5

Baris Kunci

Langkah 3: Mencari baris kunci baru dengan cara mengubah nilai “Baris Kunci” dengan pembagian nilai baris kunci awal/nilai potong, dimana Nilai potong = “6” sehingga menjadi: Var. Dasar

Z

X1

X2

X3

X4

X5

Nk

Z

1

-3

0

0

5/3

0

25

X3

0

2

0

1

0

0

8

X2

0

0

1

0

1/3

0

5

X1

0

6/6

0/6

0/6

-5/18

1/6

5/6

Baris Kunci Baru

6/6

0/6

0/6

-5/18

1/6

5/6

Baris Kunci Baru

1

0

0

-5/18

1/6

5/6

Nilai baris kunci baru: X1

Langkah 4: Mengubah nilai selain “Baris Kunci” dengan rumus: Baris baru = Baris lama – ((koefisien pada kolom kunci) x Nilai baru baris kunci) maka: Untuk nilai baris Z :

-3 x

[

-3

0

0

5/3

0

25

]

[

1

0

0

-5/18

1/6

5/6

]

[

-3

0

0

5/3

0

25

]

[

-3

0

0

15/18

-1/2

-15/6

]

[

0

0

0

5/6

1/2

27.5

]

(-) Baris Baru untuk Z

Untuk nilai baris X3 :

2x

[

2

0

1

0

0

8

]

[

1

0

0

-5/18

1/6

5/6

]

[

2

0

1

0

0

8

]

[

2

0

0

-10/18

1/3

10/6

]

[

0

0

1

10/18

-1/3

19/3

]

(-) Baris Baru untuk X3

Teknik Riset & Operasi - P3

Subarono – 12111089

---------------------------------------------------------------------------------------------------------------------------------->>>Take From: onnosbarono.wordpress.com

Untuk nilai baris X2 :

0x

[

0

1

0

1/3

0

5

]

[

1

0

0

-5/18

1/6

5/6

]

[

0

1

0

1/3

0

5

]

[

0

0

0

0

0

0

]

[

0

1

0

1/3

0

5

]

(-) Baris Baru untuk X2

Tabel baru menjadi: Var. Dasar

Z

X1

X2

X3

X4

X5

Nk

Z

1

0

0

0

5/6

1/2

27.5

X3

0

0

0

1

5/9

-1/3

19/3

X2

0

0

1

0

1/3

0

5

X1

0

1

0

0

-5/18

1/6

5/6

Perhitungan dihentikan karena nilai fungsi tujuan(Z) sudah tidak ada yang bernilai negatif.

SELESAI