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
