Oleh: suhartoumm | Maret 23, 2011

Linear Programming Simplex

 

Linear Programing Metode Simplex

 

Sebuah home industri yang bergerak di bidang kerajinan, akan membuat tiga macam bentuk kerajinan tangan dalam bentuk tasbih, patung, dan catur. Kerajinan tersebut dibuat dari bahan kayu. Untuk patung, pembentukan diperlukan waktu selama 8 jam kerja, tidak membutuh pewarnaan dan pengamplasan, tapi membutuhkan waktu 2 jam untuk pemvernisan. Untuk catur sendiri, tidak membutuhkan pembentukan dan pewarnaan, tapi dibutuhkan waktu pengamplasan 5 jam dan 2 jam untuk pemvernisan. Untuk tasbih sendiri, tidak memerlukan pembentukan, pengamplasan dan pemvernisan, tapi memerlukan waktu 5 jam untuk pewarnaan. Sumbangan laba untuk Patung yaitu Rp 10.000/buah. Catur Rp 8.000/buah, dan untuk tasbih Rp 5.000/buah. Sedangkan kapasitas maksimum dalam proses pembentukan selama 16 jam. Pengamplasan membutuhkan waktu selama 10 jam. Dan pengecatannya sendiri tersedia 20 jam. Sedangkan  pemvernisan 10 jam.

Berapa jumlah produk yang harus dibuat dari ketiganya untuk memperoleh laba maksimum ?

 

Jawab:

  Produk  

Kapasitas maksimum
Proses Patung Catur Tasbih
Pembentukan 8 0 0 16
Pengamplasan 0 5 0 10
Pewarnaan 0 0 5 20
Pemvernisan 2 2 0 10
Laba 10 8 5  

 

Batasan-batasan

 

1) 8X1 … … … ≤ 16 menjadi 8X1 … … … = 16
2) … 5X2 … … ≤ 10 menjadi … 5X2   … = 10
3) … … 5X3 … ≤ 20 menjadi … … 5X3 … = 20
4) 2X1 2X2 … … ≤ 10 menjadi 2X1 2X2 … … = 10

 

Berdasarkan perubahan persamaan-persamaan di atas, dapat disusun formulasi yang dirubah sebagai berikut:

Tujuan Mamaksimumkan: Z  – 10X1 – 8X2 – 5X3

1) 8 X1 …. …. +X4 …. …. …. = 16
2) …. 5X2 …. …. + X5 …. …. = 10
3) …. …. 5X3 …. …. + X6 …. = 20
4) 2X1 2X2 … …. …. …. + X7 = 10

 

Menyusun persamaan-persamaan dalam tabel

 

Var.Dsr Z X1 X2 X3 X4 X5 X6 X7 NK
Z 1 –10 –8 –5 0 0 0 0  
X4 0 8 0 0 1 0 0 0 16
X5 0 0 5 0 0 1 0 0 10
X6 0 0 0 5 0 0 1 0 20
X7 0 2 2 0 0 0 0 1 10

 

Memilih kolom kunci

Kolom kunci adalah kolom yang mempunyai nilai pada baris Z bernilai negatif dengan angka besar

 

Var.Dsr Z X1 X2 X3 X4 X5 X6 X7 NK
Z 1 –10 –8 –5 0 0 0 0  
X4 0 8 0 0 1 0 0 0 16
X5 0 0 5 0 0 1 0 0 10
X6 0 0 0 5 0 0 1 0 20
X7 0 2 2 0 0 0 0 1 10

 

Memilih baris kunci

 

…………>Nilai kanan (NK)

Indek =  ———————–

…………>Nilai kolom kunci

 

Baris Kunci adalah baris yang mempunyai index terkecil

 

Var. Dsr Z X1 X2 X3 X4 X5 X6 X7 NK Ket
Z 1 –10 –8 –5 0 0 0 0   ~
X4 0 8 0 0 1 0 0 0 16 16 : 8 = 2
X5 0 0 5 0 0 1 0 0 10 ~
X6 0 0 0 5 0 0 1 0 20 ~
X7 0 2 2 0 0 0 0 1 10 10 : 2 = 5

 

Mengubah nilai-nilai baris kunci

Dengan cara membaginya dengan angka kunci

Baris baru kunci = baris kunci : angka kunci

 

Var.dsr Z X1 X2 X3 X4 X5 X6 X7 NK  

 

Nilai

Minimum
Z 1                
X1 0 1 0 0 1/8 0 0 0 2
X5 0                
X6 0                
X7 0                

 

Mengubah nilai-nilai selain kunci sehingga nilai-nilai kolom kunci (selain baris Kunci) = 0

 

Baris Z                    
Baris Lama   [–10 –8 –5 0 0 0 0 0 ]  
NBBK –10 [  1 0 0 1/8 0 0 0 2 ] –
Baris baru   0 –8 –5 10/8 0 0 0 20  

 

Nilai pada baris 2 dan 3 tidak berubah karena nilai pada kolom kunci = 0

 

Baris Z                    
Baris Lama   [  2 2 0 0 0 0 1 10 ]  
NBBK 2 [  1 0 0 1/8 0 0 0 2  ] –
Baris baru   0 2 0 –2/8 0 0 1 6  

 

Nilai baru dalam tabel

 

Var.Dsr Z X1 X2 X3 X4 X5 X6 X7 NK
Z 1 0 –8 –5 10/8 0 0 0 20
X4 0 1 0 0 1/8 0 0 0 2
X5 0 0 5 0 0 1 0 0 10
X6 0 0 0 5 0 0 1 0 20
X7 0 0 2 0 –2/8 0 0 1 6

 

Memilih kolom kunci

Kolom kunci adalah kolom yang mempunyai nilai pada baris Z bernilai negatif dengan angka besar

 

 

Var.Dsr Z X1 X2 X3 X4 X5 X6 X7 NK
Z 1 0 –8 –5 10/8 0 0 0 20
X4 0 1 0 0 1/8 0 0 0 2
X5 0 0 5 0 0 1 0 0 10
X6 0 0 0 5 0 0 1 0 20
X7 0 0 2 0 –2/8 0 0 1 6

 

Memilih baris kunci

 

……….>Nilai kanan (NK)

Indek =  ———————–

……….>Nilai kolom kunci

 

Baris Kunci adalah baris yang mempunyai index terkecil

 

Var.Dsr Z X1 X2 X3 X4 X5 X6 X7 NK Ket
Z 1 0 –8 –5 10/8 0 0 0 20 ~
X4 0 1 0 0 1/8 0 0 0 2 ~
X5 0 0 5 0 0 1 0 0 10 10:5 = 2
X6 0 0 0 5 0 0 1 0 20 ~
X7 0 0 2 0 –2/8 0 0 1 6 6:2 = 3

 

Mengubah nilai-nilai baris kunci

Dengan cara membaginya dengan angka kunci

Baris baru kunci = baris kunci : angka kunci

 

Var.Dsr Z X1 X2 X3 X4 X5 X6 X7 NK  

 

Nilai Minimum
Z                  
X1                  
X2 0 0 1 0 0 1/5 0 0 2
X6                  
X7                  

 

Baris Z                    
Baris lama   [  0 –8 –5 10/8 0 0 0 20 ]  
NBBK –8 [  0 1 0 0 1/5 0 0 2  ] –
Baris baru   0 0 –5 0 8/5 0 0 36  

 

Nilai pada baris 2 dan 4 tidak berubah karena nilai pada kolom kunci = 0

 

Baris Z                    
Baris Lama   [  0 2 0 –2/8 0 0 1 6  ]  
NBBK 2 [  0 1 0 0 1/5 0 0 2  ] –
Baris baru   0 0 1 –2/8 –2/5 0 1 2  

 

Nilai baru dalam tabel

 

Var.Dsr Z X1 X2 X3 X4 X5 X6 X7 NK
Z 1 0 0 –5 10/8 8/5 0 0 36
X1 0 1 0 0 1/8 0 0 0 2
X2 0 0 1 0 0 1/5 0 0 2
X6 0 0 0 5 0 0 1 0 20
X7 0 0 0 0 –2/8 –2/5 0 1 2

 

Kolom kunci.

Kolom kunci adalah kolom yang mempunyai nilai pada baris Z bernilai negatif dengan angka besar

 

Var.Dsr Z X1 X2 X3 X4 X5 X6 X7 NK
Z 1 0 0 –5 10/8 8/5 0 0 36
X1 0 1 0 0 1/8 0 0 0 2
X2 0 0 1 0 0 1/5 0 0 2
X6 0 0 0 5 0 0 1 0 20
X7 0 0 0 0 –2/8 –2/5 0 1 2

 

Memilih baris kunci

 

……….>Nilai kanan (NK)

Indek =  ———————–

……….>Nilai kolom kunci

 

Baris Kunci adalah baris yang mempunyai index terkecil

 

Var.Dsr Z X1 X2 X3 X4 X5 X6 X7 NK Ket
Z 1 0 0 –5 10/8 8/5 0 0 36 ~
X1 0 1 0 0 1/8 0 0 0 2 ~
X2 0 0 1 0 0 1/5 0 0 2 ~
X6 0 0 0 5 0 0 1 0 20 20:5 = 4
X7 0 0 0 0 –2/8 –2/5 0 1 2 ~

 

Mengubah nilai-nilai baris kunci

Dengan cara membaginya dengan angka kunci

Baris baru kunci = baris kunci : angka kunci

 

Var.Dsr Z X1 X2 X3 X4 X5 X6 X7 NK  

 

Nilai Minimum
Z                  
X1                  
X2                  
X3 0 0 0 1 0 0 1/5 0 4
X7                  

 

Baris Z                    
Baris lama   [  0 0 –5 10/8 8/5 0 0 36   ]  
NBBK –5 [  0 0 1 0 0 1/5 0 4   ] –
Baris baru   0 0 0 10/8 8/5 1 0 56  

 

Baris ke 2, 3 dan 5 tidak tidak berubah karen nilai pada kolom kunci = 0

 

Nilai dalam tabel

 

Var.Dsr Z X1 X2 X3 X4 X5 X6 X7 NK
Z 1 0 0 0 10/8 8/5 1 0 56
X1 0 1 0 0 1/8 0 0 0 2
X2 0 0 1 0 0 1/5 0 0 2
X3 0 0 0 1 0 0 1/5 0 4
X7 0 0 0 0 –2/8 –2/5 0 1 2

 

Bila pada baris pertama (Z) tidak ada nilai negatif, berarti pnghitungan sudah mencapai titik optimal.

Maksud dari tabel tersebut yaitu

X1 (Patung) memproduksi 2 buah dengan keuntungan Rp 10.000/buah total keuntungan dari pembuatan patung adalah Rp Rp 20.000

X2 (Catur) memproduksi  2 buah dengan keuntungan Rp 8.000/buah total keuntungan dari pembuatan catur adalah Rp 16.000

X3 (tasbih) memproduksi 4 buah dengan keuntungan Rp 5.000/buah total keuntungan dari pembuatan tasbih adalah Rp 20.000

Z maksimum adalah 56 artinya jumlah keuntungan maksimum dari semua produk yaitu, patung, catur dan tasbih adalah Rp 56.000 setiap harinya

Atau bila dimasukkan dalam rumus adalah sebagai berikut:

Z = 2 (10.000) + 2 ( 8000) + 4 (5000) = 56.000

 

 

Ditulis dalam Uncategorized

«
»

Tinggalkan Balasan

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out / Ubah )

Twitter picture

You are commenting using your Twitter account. ( Log Out / Ubah )

Facebook photo

You are commenting using your Facebook account. ( Log Out / Ubah )

Batal

Connecting to %s

Kategori

Ikuti

Get every new post delivered to your Inbox.