Metode Simpleks

in Matsi 2

    Bila melibatkan lebih dari dua kegiatan maka metode grafik tidak dapat digunakan lagi, sehingga diperlukan metode simpleks. Metode simpleks merupakan suatu cara yang lazim dipakai untuk menentukan kombinasi optimal dari tiga variable atau lebih.

    Bila variable keputusan yang dikandungkan tidak terlalu banyak, masalah tersebut dapat diselesaikan dengan suatu algorithma yang biasanya sering disebut metode simpleks table.

LANGKAH-LANGKAH METODE SIMPLEKS TABEL

Langkah 1 : Mengubah fungsi tujuan dan batasan-batasan

    Fungsi tujuan diubah menjadi fungsi implisit, artinya semua CjXij kita geser ke kiri.

Misalanya fungsi tujuan pada contoh Z =3X1 + 5X2 dibuah menjadi Z – 3X1 – 5X2 = 0.

    Pada bentuk standar, semua batasan mempunyai tanda ≤. Ketidak samaan ini harus diubah menjadi kesamaan. Caranya dengan menambah slack variable. Slack variable adalah variable tambahan yang mewakili tingkat pengangguran atau kapasitas yang merupakan batasan. Karena tingkat atau hasil kegiatan-kegiatan yang ada diwakili oleh X1 dan X2, maka variable slack dimulai dari X3, X4 dan seterusnya sebagai berikut  :

 Batasan-batasan :

X3	2X1		+ X3			= 8
X4		3X2		+ X4		= 15
X5	6X1	+ 5X2			+ X5	= 30

Langkah 2 : Menyusun persamaan – persamaan di dalam table

    Setelah formulasi diubah kemudian disusun ke dalam table, dalam bentuk symbol seperti tampak table 1.1.

Variabel 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

Tabel 1.1

    Setelah data disusun di dalam table di atas kemudian diadakan perubahan-perubahan agar dapat mencapai titik optimal, dengan langkah – langkah berikutnya.

Langkah 3 : Memilih kolom kunci

    Kolom kunci  adalah kolom yang merupakan dasar untuk mengubah table di atas. Pilihlah kolom yang mempunyai nilai pada garis fungsi tujuan yang bernilai negative dengan angka terbesar. Dalam hal ini kolom X2 dengan nilai pada baris persamaan tujuan -5. Berikan tanda segi empat pada kolom X2, seperti pada table 1.2. jika suatu table sudah tidak memiliki nilai negative pada baris fungsi tujuan berarti table itu tidak bisa dioptimalkan lagi ( sudah optimal ).

Variabel Dasar	Z	X1	X2	X3	X4	X5	NK	Keterangan
Z	1	-3	-5	0	0	0	0
X3	0	2	0	1	0	0	8
X4	0	0	3	0	1	0	15	15/3 = 5 ( minimum )
X5	0	6	5	0	0	1	30	30/5 = 6

Tabel 1.2. Pemilihan kolom kunci pada table pertama

Langkah 4 : Memilih baris kunci

     Baris kunci  adalah baris yang merupakan dasar untuk mengubah table tersebut di atas. Carilah indeks tiap-tiap baris dengan rumus berikut :

Indeks = Nilai kolom NK / Nilai kolom kunci

( lihat kolom “keterangan” pada table 3.5 )

Untuk baris batasan 1 besarnya indeks : 8/0 = ~

Untuk baris batasan 2 besarnya indeks : 15/3 = 5

Untuk baris batasan 3 besarnya indeks: 30/5 = 6

Pilihlah baris yang mempunyai indeks positif dengan angka terkecil. Dalam hal ini batasan ke 2 yang terpilih sebagai baris kunci. Berilah tanda segi empat pada baris kunci itu, seperti terlihat pada table 1.3 bagian atas. Nilai yang masuk dalam kolom kunci dan juga termasuk dalam baris kunci disebut angka kunci.

Variabel 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
Z
X3
X2	0	0	1	0	1/3	0	5
X5

Tabel 1.3. Cara mengubah nilai baris kunci

Langkah 5 : Mengubah nilai – nilai baris kunci

                Nilai baris kunci diubah dengan cara membaginya dengan angka kunci, seperti terlihat pada Tabel 1.3 bagian bawah. Gantilah variable dasar pada baris itu dengan variable yang terdapat di bagian atas kolom kunci (X2).

X1 : 0/3 = 0

X2 : 3/3 = 1

X3 : 0/3 = 0

X4 : 1/3 = 1/3

X5 : 0/3 = 0

NK : 15/3 = 5

Langkah 6 : Mengubah nilai-nilai baris kunci

Nilai-nilai baris yang lain, selain pada baris kunci dapat diubah dengan rumus sebagai berikut

Baris baru = baris lama – (koefisien pada kolom kunci) x nilai baru baris kunci

Untuk data diatas.

Nilai baris ke-1 (Z) :

		-3	-5	0	0	0	0
	(-5)	0	1	0	1/3	0	5	(-)
Nilai baru	=	-3	0	0	5/3	0	25

Nilai baris ke-2 ( batasan 1) :

		2	0	1	0	0	8
	0	0	1	0	1/3	0	5	(-)
Nilai baru	=	2	0	1	0	0	8

Nilai baris ke-3 ( batasan 2 ) :

		6	5	0	0	1	30
	5	0	1	0	1/3	0	5	(-)
Nilai baru	=	6	0	0	-5/3	1	5

Nilai-nilai baru di atas dipakai untuk melengkapi isi Tabel 1.3 bagian bawah, hasilnya terlihat pada table 1.4

Variabel 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
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

Tabe1.3.Tabel pertama nilai lama dan table kedua nilai baru

Langkah 7: Melanjutkan perbaikan-perbaikan / perubahan-perubahan

    Ulangilah langkah-langkah perbaikan mulai langkah 3 sampai langkah ke 6 untuk memperbaiki table-tabel yang telah diubah/diperbaiki nilainya. Perubahan baru berhenti setelah pada baris pertama (fungsi tujuan) tidak ada yang bernilai negative. Kalau table kedua (hasil perubahan) pada bagian bawah dari table 1.3 itu kita ubah lagi, maka kolom dan baris kuncinya seperti terlihat pada table 1.4.

Variabel Dasar	Z	X1	X2	X3	X4	X5		NK
Z	1	-3	0	0	5/4	0		25
X3	0	2	0	1	0	0		8 > 8/2 = 4
X2	0	0	1	0	1/3	0		5
X5	0	6	0	0	-5/3	1		5 > 5/6 = 5/6 (minimum)
Z	1
X3	0
X2	0
X1	0	1	0	0	-5/18		1/6	5/6

Tabel 1.4. kolom dan baris dari table hasil perbaikan pertama, dan nilai baru baris kunci hasil perbaikan kedua,

Untuk data diatas.

Baris ke-1 (Z) :

		-3	0	0	5/3	0	25
	(-3)	1	0	0	-5/18	1/6	5/6	(-)
Nilai baru	=	0	0	0	5/6	1/2	27/2

Baris Ke-2 (X3) :

		2	0	1	0	0	8
	(2)	1	0	0	-5/18	1/6	5/6	(-)
Nilai baru	=	0	0	1	5/9	-1/3	6/3

Nilai baris ke 3 tidak berubah, karenan nilai pada kolom kunci = 0.

Jika hasil perubahan di atas kita masukkan ke dalam table 1.4 bagian bawah, hsilnya seperti terlihat pada table 1.5

Variabel Dasar	Z	X1	X2	X3	X4	X5		NK
Z	1	0	0	0	5/6	½		27/2
X3	0	0	0	1	5/9	-1/3		6/3
X2	0	0	1	0	1/3	0		5
X1	0	1	0	0	-5/18		1/6	5/6

Tabel 1.5 Hasil perubahan/perbaikan kedua

Kalau dilihat baris pertama(Z) pada table 1.5 tidak ada lagi yang bernilai negative, semuanya positif. Berarti table itu tidak dapat dioptimalkan lagi, sehingga hasil dari table tersebut sudah merupakan hasil optimal.

Sumber : DASAR – DASAR OPERATIONS RESEARCH Edisi 2

Klik link dibawah ini untuk mendownload document ini :

Metode Simpleks << Indowebster