Metode SimpleksKasus Minimisasi

1. Minimisasi

• Fungsi tujuan dari permasalahan linearprogramming yang bersifatminimisasi, harusdiubah menjadi maksimisasi, agar sesuaidengan bentuk standar, yaitu maksimisasi.Caranya adalah dengan mengganti tandapositif dan negatif pada fungsi tujuan, sebagaiberikut:

Penyimpangan-penyimpangan dariBentuk Standar

menjadi

Minimisasi

• Kalau suatu batasan memakai tanda kesamaan, maka caramengatasinya dengan menambahkan variabel buatan (artificialvariable).

• Bila batasan tersebut bertanda “=” untuk dapat dikerjakan denganmetode simpleks harus ditambahkan satu variabel lagi, karena padabatasan itu belum ada variabel yang bisa merupakan variabel dasarpada tabel pertama. Variabel itu adalah variabel buatan yangbersifat tidak negatif.

• Karena adanya variabel buatan, maka fungsi tujuan harus disesuaikandengan menambahkan bilangan M.

• Bilangan M bernilai sangat besar tetapi tidak tak terhingga, sehingganilai Z maksimum bisa diperoleh.

Batasan dengan tanda “samadengan”

• Bila suatu fungsi pembatas bertanda =, maka harus diubahmenjadi = dan akhirnya menjadi = agar dapat diselesaikandengan metode simpleks.

• Contoh :

• 4X1 + 3X2 = 200 dikalikan (-1), menjadi

• -4X1 – 3X1 = -200 ditambahkan Variabel X5, menjadi

• -4X1 – 3X2 + X5 = -200

Fungsi pembatas bertanda =

• Bila bagian kanan persamaan bertanda negatif maka harus diubah menjadi positif.Caranya dengan mengubah tanda positif negatif dari tiap-tiap koefisien, kemudianditambah 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 , tetapislack variabel (X5) bertanda negatif (dalam hal ini slack variabel sering disebut pula surplusvariabel) . Hal ini tidak memungkinkan penggunaan metode simpleks. Oleh karena ituharus ditambahkan satu variabel buatan X6, yang akan menjadi variabel dasar dalamtabel permulaan, sehingga menjadi sbb :

• 4X1 + 3X2 – X5 + X6 = 200

Bagian kanan persamaan bertandanegatif

• Setelah kita lakukan perubahan-perubahan pada fungsi tujuandan fungsi batasan dengan bentuk non standar, persamaantujuan diatas tidak memungkinkan penggunaan metodesimpleks tabel, sebab nilai setiap variabel dasar padapersamaan ini harus sebesar 0, padahal Xn merupakan variabeldasar pada tabel permulaan. Oleh karena itu diubah dengancara menguranginya dengan M dikalikan dengan baris batasanyang bersangkutan.

Langkah selanjutnya

• Perusahaan bakso Echo membuat 2 macam bakso, yaitu baksoenak dan bakso eco, yang setiap bungkusnya ukuran 1 kg dijualseharga Rp 30.000,- dan Rp 50.000,-. Dalam setiap adonandisediakan daging sapi paling banyak 6 kg, daging ayam palingsedikit 2 kg, dan tepung sebanyak 2 kg. Untuk membuat baksoenak membutuhkan daging sapi 2 kg, daging ayam 2 kg, dantepung 1 kg. Sedangkan untuk membuat bakso eco dibutuhkandaging sapi 3 kg, daging ayam 1 kg, dan tepung 2 kg.Berapakah bakso enak dan bakso eco yang harus dibuat jikadiketahui laba masing-masing Rp 5.000,- agar diperoleh biayapembuatan paling murah ?

Contoh Soal :

• Perusahaan bakso Echo membuat 2 macam bakso, yaitu bakso enakdan bakso eco (Keluaran)

• yang setiap bungkusnya ukuran 1 kg dijual seharga Rp 30.000,- dan Rp50.000,-. (Tingkat kegiatan)

• Dalam setiap adonan disediakan daging sapi paling banyak 6 kg,daging ayam paling sedikit 2 kg, dan tepung sebanyak 2 kg. (Kapasitassumber)

• Untuk membuat bakso enak membutuhkan daging sapi 2 kg, dagingayam 2 kg, dan tepung 1 kg. Sedangkan untuk membuat bakso ecodibutuhkan daging sapi 3 kg, daging ayam 1 kg, dan tepung 2 kg.(Keluaran sumber)

• Berapakah bakso enak dan bakso eco yang harus dibuat jika diketahuilaba masing-masing Rp 5.000,- agar diperoleh biaya pembuatan palingmurah ?

ProdukSumber BAKSO ENAK BAKSO ECO Kapasitas

DAGING SAPI 2 3 6DAGING AYAM 2 1 2TEPUNG 1 2 2HARGA 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 ≤ 62X1 + X2 ≥ 2X1 + 2X2 = 2X1, X2 ≥ 0

• 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

Contoh Soal :

• Untuk kasus minimal, yang diubah adalah fungsi batasanterlebih dahulu, dikarenakan ada pengaruh terhadap fungsitujuan.

• Fungsi batasan :

• a) 2X1 + 3X2 ≤ 6 menjadi 2X1 + 3X2 + X3 = 6

• b) 2X1 + X2 ≥ 2

• Tanda (≥) diubah menjadi (≤), tetapi tidak bisa dibalik begitusaja. Caranya adalah dengan dikalikan -1.

Langkah 1. Mengubah Fungsi Tujuandan Batasan

-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 dikatakansurplus variabel. Sehingga tidak bisa dijadikan variabel dasar. Makaperlu ditambahkan variabel buatan untuk dijadikan variabel dasar.

• 2X1 + X2 - X4 + X5 = 2

Mengubah Batasan dengan tanda(≥)

• Batasan kedua menjadi :

• 2X1 + X2 - X4 + X5 = 2

• Maka fungsi tujuan harus disesuaikan dengan menambahkanbilangan M

• Bilangan M bernilai sangat besar tetapi tidak tak terhingga,sehingga nilai Z maksimum bisa diperoleh.

• Menjadi : Z = 3X1 + 5X2 + MX5

Menyesuaikan fungsi tujuan denganmenambah bilangan M

• C) X1 + 2X2 = 2

• Tanda (=) ditambahkan variabel buatan untuk dijadikanvariabel dasar.

• X1 + 2X2 + X6 = 2

• Maka fungsi tujuan kembali disesuaikan dengan menambahkanbilangan M.

• Menjadi : Z = 3X1 + 5X2 + MX5 + MX6

Menyesuaikan batasan yang ketiga

• Minimalkan Z = 3X1 + 5X2 + MX5 + MX6

• Diubah menjadi maksimalkan dengan mengganti dari tandapositif (+) 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 tabelpersamaan dikarenakan MX5 dan MX6 sebagai variabel dasarpada fungsi tujuan harus bernilai nol (0).

Mengubah fungsi tujuan

• Menggunakan batasan yang memuat X5 dan X6 yaitu batasanke-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

Mengenalkan bilangan M

x M

Mengenolkan M

Langkah 2. Menyusun persamaanke dalam tabel

Variabel Dasar Z X1 X2 X3 X4 X5 X6 NK

Z -1 (-3M+3) (-3M+5) 0 M 0 0 -4MX3 0 2 3 1 0 0 0 6X5 0 2 1 0 -1 1 0 2X6 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 -4MX3 0 2 3 1 0 0 0 6X5 0 2 1 0 -1 1 0 2X6 0 1 2 0 0 0 1 2

Jika suatu tabel sudah tidak memiliki nilai negatif pada barisfungsi tujuan (Z), berarti tabel itu tidak bisa dioptimalkan lagi

(sudah optimal)

Langkah 4. Memilih baris kunciVariabel

Dasar Z X1 X2 X3 X4 X5 X6 NK Indeks

Z -1 (-3M+3) (-3M+5) 0 M 0 0 -4MX3 0 2 3 1 0 0 0 6 6/2 = 3X5 0 2 1 0 -1 1 0 2 2/2 = 1X6 0 1 2 0 0 0 1 2 2/1 = 2

Pilihlah baris yang mempunya indeks positif dengan angkaterkecil.

Titik perpotongan kolom kunci dengan baris kunci adalah :Angka Kunci

Langkah 5. Mengubah nilai-nilaibaris kunciVariabel

Dasar Z X1 X2 X3 X4 X5 X6 NK Indeks

Z -1 (-3M+3) (-3M+5) 0 M 0 0 -4MX3 0 2 3 1 0 0 0 6 6/2 = 3X5 0 2 1 0 -1 1 0 2 2/2 = 1X6 0 1 2 0 0 0 1 2 2/1 = 2

ZX3

X1 1 1/2 0 -1/2 1/2 0 1X6

X5 0 2 1 0 -1 1 0 2 2/2=12 2 2 2 2 2 2 2

Gantilah variabel dasar pada baris yang terpilih dengan variabel yang terdapat dibagian atas kolom kunci.

X1 0 1/2 1 0 1/2 0 2

Nilai baris kunci baru = Nilai Baris kunci lama

Angka kunciNilai Baris kunci lama

Angka kunci= 2 (pertemuan angka negatif zdengan angka indeks positif terkecil

Titik perpotongan kolom kunci dengan baris kunci adalah :Angka Kunci

Langkah 6. Mengubah nilai-nilaiselain pada baris kunci• Baris Z NK

(-3M+3) (-3M+5) 0 M 0 0 -4M

(-3M+3) 1 ½ 0 -½ ½ 0 1

0 (-3/2M+7/2) 0 (-½ M+ 3/2) (3/2M-3/2) 0 (-M-3)

• Baris X3 NK

2 3 1 0 0 0 6

(2) 1 ½ 0 -½ ½ 0 1

0 2 1 1 -1 0 4

NBBK

NBBK

• Baris X6 NK

1 2 0 0 0 1 2

(1) 1 ½ 0 -½ ½ 0 1

0 3/2 0 ½ - ½ 1 1

Langkah 6. Mengubah nilai-nilaiselain pada baris kunci

NBBK

Tabel pertama nilai lama dan Tabelkedua nilai baru

VariabelDasar Z X1 X2 X3 X4 X5 X6 NK Indeks

Z -1 (-3M+3) (-3M+5) 0 M 0 0 -4MX3 0 2 3 1 0 0 0 6 6/2 = 3X5 0 2 1 0 -1 1 0 2 2/2 = 1X6 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 4X1 0 1 1/2 0 -1/2 1/2 0 1X6 0 0 3/2 0 1/2 -1/2 1 1

Tabel kedua nilai baruVariabel

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 4X1 0 1 1/2 0 -1/2 1/2 0 1X6 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 lagiVariabel

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 4X1 0 1 1/2 0 -1/2 1/2 0 1X6 0 0 3/2 0 1/2 -1/2 1 1

Langkah 3 lagi . . .

Memilih baris kunci lagiVariabel

Dasar Z X1 X2 X3 X4 X5 X6 NK INDEKS

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=2X1 0 1 1/2 0 -1/2 1/2 0 1 1/½=2X6 0 0 3/2 0 1/2 -1/2 1 1 1/ =

23

23

32

Langkah 4 lagi . . .

Mengubah nilai-nilai baris kunci lagiVariabel

Dasar Z X1 X2 X3 X4 X5 X6 NK Indeks

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=2X1 0 1 1/2 0 -1/2 1/2 0 1 1/½=2X6 0 0 3/2 0 1/2 -1/2 1 1 =

ZX3

X1

X2 0 1 0 1/3 -1/3 2/3

23

1

32

Mengubah nilai-nilai selain padabaris kunci lagi• Baris Z NK

0 (-3/2M+7/2) 0 (-½ M+ 3/2) (3/2M-3/2) 0 (-M-3)

(-3/2M+7/2) 0 1 0 1/3 -1/3 2/3 2/3

0 0 0 1/3 (M-1/3) (M-7/3) -16/3

• Baris X3 NK

0 2 1 1 -1 0 4

(2) 0 1 0 1/3 -1/3 2/3 2/3

0 0 1 -1/3 1/3 -4/3 8/3

NBBK

NBBK

• 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

Mengubah nilai-nilai selain padabaris kunci lagi

NBBK

Tabel pertama nilai lama dan Tabelkedua nilai baru

VariabelDasar Z X1 X2 X3 X4 X5 X6 NK Indeks

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=2X1 0 1 1/2 0 -1/2 1/2 0 1 1/½=2X6 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/3X1 0 1 0 0 -1/3 1/3 -1/3 2/3X2 0 0 1 0 1/3 -1/3 2/3 2/3

Tabel kedua nilai baruVariabel

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/3X1 0 1 0 0 -1/3 1/3 -1/3 2/3X2 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 hasilVariabel

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/3X1 0 1 0 0 -1/3 1/3 -1/3 2/3X2 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 kgdengan biaya pembuatan paling murah 16/3 x Rp. 10.000,- =

Rp. 53.333,33

Bernard W. Taylor III. 1993. Sains Manajemen Pendekatan Matematika untukBisnis Buku 1. Jakarta : Salemba Empat.Hamdy A Taha. 1993. Riset Operasi Edisi Kelima Jilid 1. Jakarta : BinarupaAksara.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.

Referensi

Terima Kasih . . . ^_^