Metode Simpleks Kasus Minimisasi
Penyimpangan-penyimpangan dari Bentuk Standar 1. Minimisasi • Fungsi tujuan dari permasalahan linear programming yang bersifat minimisasi, harus diubah menjadi maksimisasi, agar sesuai dengan bentuk standar, yaitu maksimisasi. Caranya adalah dengan mengganti tanda positif dan negatif pada fungsi tujuan, sebagai berikut:
Minimisasi
menjadi
Batasan dengan tanda “sama dengan” • Kalau suatu batasan memakai tanda kesamaan, maka cara mengatasinya dengan menambahkan variabel buatan (artificial variable). • Bila batasan tersebut bertanda “=” untuk dapat dikerjakan dengan metode simpleks harus ditambahkan satu variabel lagi, karena pada batasan itu belum ada variabel yang bisa merupakan variabel dasar pada tabel pertama. Variabel itu adalah variabel buatan yang bersifat tidak negatif. • Karena adanya variabel buatan, maka fungsi tujuan harus disesuaikan dengan menambahkan bilangan M. • Bilangan M bernilai sangat besar tetapi tidak tak terhingga, sehingga nilai Z maksimum bisa diperoleh.
Fungsi pembatas bertanda = • Bila suatu fungsi pembatas bertanda =, maka harus diubah menjadi = dan akhirnya menjadi = agar dapat diselesaikan dengan metode simpleks. • Contoh : • 4X1 + 3X2 = 200 dikalikan (-1), menjadi • -4X1 – 3X1 = -200 ditambahkan Variabel X5, menjadi • -4X1 – 3X2 + X5 = -200
Bagian kanan persamaan bertanda negatif •
Bila bagian kanan persamaan bertanda negatif maka harus diubah menjadi positif. Caranya dengan mengubah tanda positif negatif dari tiap-tiap koefisien, kemudian ditambah dengan variabel buatan.
•
Contoh :
•
-4X1 – 3X2 + X5 = -200 dikalikan (-1), menjadi
•
4X1 + 3X2 – X5 = 200
•
Persamaan diatas sudah bertanda kesamaan dan dibagian kanan bertanda positif , tetapi slack variabel (X5) bertanda negatif (dalam hal ini slack variabel sering disebut pula surplus variabel) . Hal ini tidak memungkinkan penggunaan metode simpleks. Oleh karena itu harus ditambahkan satu variabel buatan X6, yang akan menjadi variabel dasar dalam tabel permulaan, sehingga menjadi sbb :
•
4X1 + 3X2 – X5 + X6 = 200
Langkah selanjutnya • Setelah kita lakukan perubahan-perubahan pada fungsi tujuan dan fungsi batasan dengan bentuk non standar, persamaan tujuan diatas tidak memungkinkan penggunaan metode simpleks tabel, sebab nilai setiap variabel dasar pada persamaan ini harus sebesar 0, padahal Xn merupakan variabel dasar pada tabel permulaan. Oleh karena itu diubah dengan cara menguranginya dengan M dikalikan dengan baris batasan yang bersangkutan.
Contoh Soal : • Perusahaan bakso Echo membuat 2 macam bakso, yaitu bakso enak dan bakso eco, yang setiap bungkusnya ukuran 1 kg dijual seharga Rp 30.000,- dan Rp 50.000,-. Dalam setiap adonan disediakan daging sapi paling banyak 6 kg, daging ayam paling sedikit 2 kg, dan tepung sebanyak 2 kg. Untuk membuat bakso enak membutuhkan daging sapi 2 kg, daging ayam 2 kg, dan tepung 1 kg. Sedangkan untuk membuat bakso eco dibutuhkan daging sapi 3 kg, daging ayam 1 kg, dan tepung 2 kg. Berapakah bakso enak dan bakso eco yang harus dibuat jika diketahui laba masing-masing Rp 5.000,- agar diperoleh biaya pembuatan paling murah ?
• Perusahaan bakso Echo membuat 2 macam bakso, yaitu bakso enak dan bakso eco (Keluaran) • yang setiap bungkusnya ukuran 1 kg dijual seharga Rp 30.000,- dan Rp 50.000,-. (Tingkat kegiatan) • Dalam setiap adonan disediakan daging sapi paling banyak 6 kg, daging ayam paling sedikit 2 kg, dan tepung sebanyak 2 kg. (Kapasitas sumber) • Untuk membuat bakso enak membutuhkan daging sapi 2 kg, daging ayam 2 kg, dan tepung 1 kg. Sedangkan untuk membuat bakso eco dibutuhkan daging sapi 3 kg, daging ayam 1 kg, dan tepung 2 kg. (Keluaran sumber) • Berapakah bakso enak dan bakso eco yang harus dibuat jika diketahui laba masing-masing Rp 5.000,- agar diperoleh biaya pembuatan paling murah ?
Produk
BAKSO ENAK
BAKSO ECO
Kapasitas
Sumber DAGING SAPI
2
3
6
DAGING AYAM
2
1
2
TEPUNG
1
2
2
HARGA
30.000
50.000
• Variabel : Bakso enak = X1 dan bakso eco = X2 • Fungsi Tujuan : Minimalkan Zmin = 30.000X1 + 50.000X2 Zmin = 3X1 + 5X2 (dalam satuan Rp.10.000,-) • Batasan : 2X1 + 3X2 ≤ 6 2X1 + X2 ≥2 X1 + 2X2 =2 X1, X2 ≥ 0
Contoh Soal : • Variabel : Bakso enak = X1 dan bakso eco = X2 • Fungsi Tujuan : Minimalkan Zmin = 30.000X1 + 50.000X2 • Batasan : 2X1 + 3X2
≤6
2X1 + X2
≥2
X1 + 2X2
=2
X1, X2 ≥ 0
Langkah 1. Mengubah Fungsi Tujuan dan Batasan • Untuk kasus minimal, yang diubah adalah fungsi batasan terlebih dahulu, dikarenakan ada pengaruh terhadap fungsi tujuan. • Fungsi batasan : • a) 2X1 + 3X2
≤ 6 menjadi
• b) 2X1 + X2
≥2
2X1 + 3X2 + X3 = 6
• Tanda (≥) diubah menjadi (≤), tetapi tidak bisa dibalik begitu saja. Caranya adalah dengan dikalikan -1.
Mengubah Batasan dengan tanda (≥) -2X1 - X2
≤ -2
• Tanda (≤) diubah menjadi (=) dengan ditambahkan slack variabel. • -2X1 - X2 + X4
= -2
• Setelah tanda (=) tidak boleh bernilai negatif (-), maka dikalikan -1. • 2X1 + X2 - X4
=2
• Slack pada X4 tidak boleh bernilai negatif (-), atau dikatakan surplus variabel. Sehingga tidak bisa dijadikan variabel dasar. Maka perlu ditambahkan variabel buatan untuk dijadikan variabel dasar. • 2X1 + X2 - X4 + X5 = 2
Menyesuaikan fungsi tujuan dengan menambah bilangan M • Batasan kedua menjadi : • 2X1 + X2 - X4 + X5 = 2 • Maka fungsi tujuan harus disesuaikan dengan menambahkan bilangan M • Bilangan M bernilai sangat besar tetapi tidak tak terhingga, sehingga nilai Z maksimum bisa diperoleh. • Menjadi : Z = 3X1 + 5X2 + MX5
Menyesuaikan batasan yang ketiga • C) X1 + 2X2
=2
• Tanda (=) ditambahkan variabel buatan untuk dijadikan variabel dasar. • X1 + 2X2 + X6
=2
• Maka fungsi tujuan kembali disesuaikan dengan menambahkan bilangan M. • Menjadi : Z = 3X1 + 5X2 + MX5 + MX6
Mengubah fungsi tujuan • Minimalkan
Z = 3X1 + 5X2 + MX5 + MX6
• Diubah menjadi maksimalkan dengan mengganti dari tanda positif (+) menjadi tanda negatif(-) atau sebaliknya. • Maksimalkan -Z = -3X1 - 5X2 - MX5 - MX6 • Kemudian diubah menjadi fungsi implisit (setelah tanda = digeser ke kiri) • -Z + 3X1 + 5X2 + MX5 + MX6 = 0 • Persamaan tersebut belum bisa diinputkan ke dalam tabel persamaan dikarenakan MX5 dan MX6 sebagai variabel dasar pada fungsi tujuan harus bernilai nol (0).
Mengenalkan bilangan M • Menggunakan batasan yang memuat X5 dan X6 yaitu batasan ke-2 dan ke-3 Z
X1
X2
X3
X4
X5
X6
NK
Fungsi tujuan
-1
3
5
0
0
M
M
0
Batasan 2
0
2
1
0
-1
1
0
2
Batasan 3
0
1
2
0
0
0
1
2
Fungsi tujuan
-1 (3-3M) (5-3M)
0
M
0
0
-4M
Mengenolkan M
xM
Langkah 2. Menyusun persamaan ke dalam tabel Variabel Dasar
Z
X1
X2
X3
X4
X5
X6
NK
Z
-1
(-3M+3)
(-3M+5)
0
M
0
0
-4M
X3
0
2
3
1
0
0
0
6
X5
0
2
1
0
-1
1
0
2
X6
0
1
2
0
0
0
1
2
Langkah 3. Memilih kolom kunci Variabel Dasar
Z
X1
X2
X3
X4
X5
X6
NK
Z
-1
(-3M+3)
(-3M+5)
0
M
0
0
-4M
X3
0
2
3
1
0
0
0
6
X5
0
2
1
0
-1
1
0
2
X6
0
1
2
0
0
0
1
2
Jika suatu tabel sudah tidak memiliki nilai negatif pada baris fungsi tujuan (Z), berarti tabel itu tidak bisa dioptimalkan lagi (sudah optimal)
Langkah 4. Memilih baris kunci Variabel Dasar
Z
X1
X2
X3
X4
X5
X6
NK
Z
-1
(-3M+3)
(-3M+5)
0
M
0
0
-4M
X3
0
2
3
1
0
0
0
6
6/2 = 3
X5
0
2
1
0
-1
1
0
2
2/2 = 1
X6
0
1
2
0
0
0
1
2
2/1 = 2
Indeks
Pilihlah baris yang mempunya indeks positif dengan angka terkecil. Titik perpotongan kolom kunci dengan baris kunci adalah : Angka Kunci
Langkah 5. Mengubah nilai-nilai baris kunci Variabel Dasar
Z
X1
X2
X3
X4
X5
X6
NK
Z
-1
(-3M+3)
(-3M+5)
0
M
0
0
-4M
X3
0
2
3
1
0
0
0
6
6/2 = 3
X5
0
2
1
0
-1
1
0
2
2/2 = 1
X6
0
1
2
0
0
0
1
2
2/1 = 2
1
1/2
0
-1/2
1/2
0
1
Z X3 X1 X6
Indeks
Nilai baris kunci baru = Nilai Baris kunci lama Angka kunci
Nilai Baris kunci lama
X5 X1
0
2
1
0
-1
1
0
2
2
2
2
2
2
2
2
2
0
1/2
1
0
1/2
0
2
2/2=1
Gantilah variabel dasar pada baris yang terpilih dengan variabel yang terdapat di bagian atas kolom kunci.
Angka kunci= 2 (pertemuan angka negatif z dengan angka indeks positif terkecil Titik perpotongan kolom kunci dengan baris kunci adalah : Angka Kunci
Langkah 6. Mengubah nilai-nilai selain pada baris kunci • Baris Z
NK
(-3M+3)
(-3M+3) 1 0
(-3M+5)
0
M
0
0
½
0
-½
½
0
(-3/2M+7/2)
0
(-½ M+ 3/2) (3/2M-3/2)
0
• Baris X3 (2)
-4M 1
NBBK
(-M-3) NK
2
3
1
0
0
0
6
1
½
0
-½
½
0
1
0
2
1
1
-1
0
4
NBBK
Langkah 6. Mengubah nilai-nilai selain pada baris kunci • Baris X6 (1)
NK
1
2
0
0
0
1
2
1
½
0
-½
½
0
1
0
½
-½
1
1
0
3/2
NBBK
Tabel pertama nilai lama dan Tabel kedua nilai baru Variabel Dasar
Z
X1
X2
X3
X4
X5
X6
NK
Z
-1
(-3M+3)
(-3M+5)
0
M
0
0
-4M
X3
0
2
3
1
0
0
0
6
6/2 = 3
X5
0
2
1
0
-1
1
0
2
2/2 = 1
X6
0
1
2
0
0
0
1
2
2/1 = 2
Z
-1
0
(-3/2M+7/2)
0
(-1/2M+3/2)
(3/2M-3/2)
0
-M-3
X3
0
0
2
1
1
-1
0
4
X1
0
1
1/2
0
-1/2
1/2
0
1
X6
0
0
3/2
0
1/2
-1/2
1
1
Indeks
Tabel kedua nilai baru Variabel Dasar
Z
X1
X2
X3
X4
X5
X6
NK
Z
-1
0
(-3/2M+7/2)
0
(-1/2M+3/2)
(3/2M-3/2)
0
-M-3
X3
0
0
2
1
1
-1
0
4
X1
0
1
1/2
0
-1/2
1/2
0
1
X6
0
0
3/2
0
1/2
-1/2
1
1
Syarat optimal adalah Z tidak ada nilai negatif. Apakah masih ada nilai negatif pada baris Z ? Bila ada maka ulangi lagi langkah-langkahnya . . .
Menentukan kolom kunci lagi Variabel Dasar
Z
X1
X2
X3
X4
X5
X6
NK
Z
-1
0
(-3/2M+7/2)
0
(-1/2M+3/2)
(3/2M-3/2)
0
-M-3
X3
0
0
2
1
1
-1
0
4
X1
0
1
1/2
0
-1/2
1/2
0
1
X6
0
0
3/2
0
1/2
-1/2
1
1
Langkah 3 lagi . . .
3
2
Memilih baris kunci lagi Variabel Dasar
Z
X1
X2
X3
X4
X5
X6
NK
Z
-1
0
(-3/2M+7/2)
0
(1/2M+3/2)
(3/2M-3/2)
0
-M-3
X3
0
0
2
1
1
-1
0
4
4/2=2
X1
0
1
1/2
0
-1/2
1/2
0
1
1/½=2
X6
0
0
3/2
0
1/2
-1/2
1
1
1/ 3 2 = 2 3
Langkah 4 lagi . . .
INDEKS
Mengubah nilai-nilai baris kunci lagi Variabel Dasar
Z
X1
X2
X3
X4
X5
X6
NK
Z
-1
0
(-3/2M+7/2)
0
(-1/2M+3/2)
(3/2M-3/2)
0
-M-3
X3
0
0
2
1
1
-1
0
4
4/2=2
X1
0
1
1/2
0
-1/2
1/2
0
1
1/½=2
X6
0
0
3/2
0
1/2
-1/2
1
1
3
0
1
0
1/3
-1/3
2/3
Z X3 X1 X2
Indeks
1 2
= 23
Mengubah nilai-nilai selain pada baris kunci lagi • Baris Z
(-3/2M+7/2)
NK 0
(-3/2M+7/2)
0
(-½ M+ 3/2)
0
1
0
1/3
0
0
0
1/3
(3/2M-3/2)
0
(-M-3)
-1/3
2/3
2/3
(M-1/3) (M-7/3)
• Baris X3
(2)
NBBK
-16/3 NK
0
2
1
1
-1
0
4
0
1
0
1/3
-1/3
2/3
2/3
0
0
1
-1/3
1/3
-4/3
8/3
NBBK
Mengubah nilai-nilai selain pada baris kunci lagi • Baris X1 (½ )
NK
1
½
0
-½
½
0
1
0
1
0
1/3
-1/3
2/3
2/3
1
0
0
-1/3
1/3
-1/3
2/3
NBBK
Tabel pertama nilai lama dan Tabel kedua nilai baru Variabel Dasar
Z
X1
X2
X3
X4
X5
X6
NK
Z
-1
0
(-3/2M+7/2)
0
(-1/2M+3/2)
(3/2M-3/2)
0
-M-3
X3
0
0
2
1
1
-1
0
4
4/2=2
X1
0
1
1/2
0
-1/2
1/2
0
1
1/½=2
X6
0
0
3/2
0
1/2
-1/2
1
1
=
Z
-1
0
0
0
1/3
(M-1/3)
(M-7/3)
-16/3
X3
0
0
0
1
-1/3
1/3
-4/3
8/3
X1
0
1
0
0
-1/3
1/3
-1/3
2/3
X2
0
0
1
0
1/3
-1/3
2/3
2/3
Indeks
Tabel kedua nilai baru Variabel Dasar
Z
X1
X2
X3
X4
X5
X6
NK
Z
-1
0
0
0
1/3
(M-1/3)
(M-7/3)
-16/3
X3
0
0
0
1
-1/3
1/3
-4/3
8/3
X1
0
1
0
0
-1/3
1/3
-1/3
2/3
X2
0
0
1
0
1/3
-1/3
2/3
2/3
Syarat optimal adalah Z tidak ada nilai negatif. Apakah masih ada nilai negatif pada baris Z ? Bila sudah tidak ada, maka perhitungan sudah optimal.
Tabel hasil Variabel Dasar
Z
X1
X2
X3
X4
X5
X6
NK
Z
-1
0
0
0
1/3
(M-1/3)
(M-7/3)
-16/3
X3
0
0
0
1
-1/3
1/3
-4/3
8/3
X1
0
1
0
0
-1/3
1/3
-1/3
2/3
X2
0
0
1
0
1/3
-1/3
2/3
2/3
Kesimpulan : Maka bakso enak dibuat 2/3 kg dan bakso eco dibuat 2/3 kg dengan biaya pembuatan paling murah 16/3 x Rp. 10.000,- = Rp. 53.333,33
Referensi Bernard W. Taylor III. 1993. Sains Manajemen Pendekatan Matematika untuk Bisnis Buku 1. Jakarta : Salemba Empat. Hamdy A Taha. 1993. Riset Operasi Edisi Kelima Jilid 1. Jakarta : Binarupa Aksara. Jong Jek Siang. 2011. Riset Operasi Dalam Pendekatan Algoritmis.Yogyakarta : Andi Offset. Johannes Supranto. 1988. Riset Operasi Untuk Pengambilan Keputusan. Universitas Indonesia. Minarwati. 2015. Bahan Ajar RO. STMIK AMIKOM YOGYAKARTA. Riski Aditya. 2015. Modul 2 LP Simplek. STMIK AMIKOM YOGYAKARTA. Modul RO STMIK AMIKOM PURWOKERTO.
Terima Kasih . . . ^_^
