METODE SIMPLEKS

Metode Simpleks

A.      Pengertian

Metode simpleks merupakan salah satu teknik penyelesaian dalam program linier yang digunakan sebagai teknik pengambilan keputusan dalam permasalahan yang berhubungan dengan pengalokasian sumberdaya secara optimal.Metode penyelesaian program linier dengan metode simpleks pertama kalidikemukakan oleh George Dantzig pada tahun 1947. Metode simpleks digunakan untuk mencari nilai optimal dari program linier yang melibatkan banyak constraint (pembatas) dan banyak variabel (lebih dari dua variabel).

Penemuan metode ini merupakan lompatan besar dalam riset operasi. Metode ini menjadi terkenal ketika diketemukan alat hitung elektronik dan menjadi popular ketika munculnya komputer. Proses perhitungan metode ini dengan melakukan iterasi berulang-ulang sampai tercapai hasil optimal dan proses perhitungan ini menjadi mudah dengan komputer.

Ada tiga sifat dari bentuk baku linear programing untuk metode simpleks ini, diantaranya:

1.                 Sifat yang pertama adalah semua batasan adalah persamaan (dengan tidak ada nilai negatif pada sisi kanan) 

2.                 Sifat yang kedua adalah semua variabel tidak ada yang bernilai negatif, dan

3.                 Sifat yang ketiga adalah fungsi tujuan dapat berupa minimisasi atau maksimisasi.

B.       Pengaplikasian Metode Simpleks pada Kehidupan Sehari-hari

Dalam kehidupan sehari-hari manusia cenderung untuk hidup berprinsipkan ekonomi, dengan usaha sesedikit mungkin dapat memperoleh hasil sebanyak mungkin. Oleh karena itu, manusia melakukan berbagai daya dan upaya untuk dapat memaksimalkan atau meminimalkan sesuatu sedemikian hingga menguntungkan bagi dirinya. Banyak hal yang dicari nilai optimumnya, misalnya:

1.                 Pendapatan yang maksimum,

2.                 Ongkos yang minimum,

3.                 Hidup yang paling nyaman, dsb.

Perihal diatas merupakan salah satu yang mendasari terciptanya program linear. Program linear menjadi satu dari banyak materi di pelajaran matematika yang banyak diterapkan dalam kehidupan sehari-hari, khususnya terapan ke bidang-bidang sosial dan manajemen.

C.      Langkah-langkah

1.        Mengubah fungsi tujuan

F = a1x1 + . . . + anxn →             F – a1x1 – . . . – anxn = 0

Dengan kata lain, kita menegatifkan konstanta dari variabel-variabel tersebut sehingga hasilnya sama dengan nol.

2.        Mengubah fungsi batasan ke bentuk kanonik (slack variable)

a11x1 + a12x2 ≤ b1 → a11x1 + a12x2 + s1 = b1

a21x1 + a22x2 ≤ b2 → a21x1 + a22x2 + s2 = b2

3.        Mengisi tabel simpleks

Tabel simpleks berbentuk seperti berikut :

VB	X1	X2	S1	S2	S3	NK
F	-a1	-a2	0	0	0	0
S1	a11	a12	1	0	0	b1
S2	A21	A22	0	1	0	b2
S3	a31	a32	0	0	1	b3

4.        Menentukan kolom kunci

Kolom kunci ditentukan dengan cara mencari nilai yang kolom paling kecil dari F. Kita misalkan X2 adalah nilai yang paling terkecil, jadi tabelnya akan berbentuk seperti berikut :

VB	X1	X2	S1	S2	S3	NK
F	-a1	-a2	0	0	0	0
S1	a11	a12	1	0	0	B1
S2	a21	a22	0	1	0	B2
S3	a31	a32	0	0	1	B3

5.        Menentukan baris kunci

Pertama, kita harus menentukan index dengan cara membagi NK dengan kolom kunci (NK/kolom kunci). Setelah itu, cari nilai dari index tersebut yang terkecil. Maka kita akan memperoleh baris kunci. Kita misalkan S2.

VB	X1	X2	S1	S2	S3	NK	INDEX
F	-a1	-a2	0	0	0	0	0/-a2
S1	a11	a12	1	0	0	b1	b1/a12
S2	a21	a22	0	1	0	b2	b2/a22
S3	a31	a32	0	0	1	b3	b3/a32

6.        Menentukan angka kunci

Angka kunci merupakan pertemuan antara kolom kunci dengan baris kunci. Jadi, kita memperoleh a22 sebagai angka kunci.

7.        Membuat baris kunci baru

Baris kunci bari diperoleh dengan cara membagi baris S2 dengan angka kunci. Seperti pada tabel berikut :

VB	X1	X2	S1	S2	S3	NK
F	-a1	-a2	0	0	0	0
S1	a11	a12	1	0	0	b1
X1	a21/ a22	1	0/ a22	1/ a22	0/ a22	b2/ a22
S3	a31	a32	0	0	1	b3

8.        OBE tabel

VB	X1	X2	S1	S2	S3	NK
F	-a1	-a2	0	0	0	0
S1	a11	a12	1	0	0	b1
X1	a21/ a22	1	0/ a22	1/ a22	0/ a22	b2/ a22
S3	a31	a32	0	0	1	b3

Baris F ditambah a2 kali baris X1

Baris S1 dikurang a12 kali baris X1

Baris S3 dikurang a32 kali baris X1

9.        Menguji optimasi atau mengecek kepositifan dari baris F

VB	X1	X2	S1	S2	S3	NK
F	-a1	-a2	0	0	0	0
S1	a11	a12	1	0	0	b1
X1	a21/ a22	1	0/ a22	1/ a22	0/ a22	b2/ a22
S3	a31	a32	0	0	1	b3

Jika baris F bernilai positif,maka langkah telah selesai. Tapi,jika masih ada nilai dari baris F yang bernilai negatif, maka ulangi lagi dari langkah 4 yaitu menentukan kolom kunci.

D.      Contoh Pengaplikasian Metode Simpleks

PT Unilever bermaksud membuat 2 jenis sabun, yakni sabun bubuk dan sabun batang. Untuk itu dibutuhkan 2 macam zat kimia, yakni A dan B. jumlah zat kimia yang tersedia adalah A=200Kg dan B=360Kg.

Untuk membuat 1Kg sabun bubuk diperlukan 2 Kg A dan 6 Kg B. untuk membuat 1 Kg sabun batang diperlukan 5 Kg A dan 3 Kg B. bila keuntungan yang akan diperoleh setiap membuat 1Kg sabun bubuk = $3 sedangkan setiap 1 Kg sabun batang = $2, berapa Kg jumah sabun bubuk dan sabun batang yang sebaiknya dibuat ?

JAWABAN

Pemodelan matematika :

Maksimumkan : Z = 3x₁ + 2x₂

Pembatas : 2x₁ + 5x₂ = 200

6x₁ + 3x₂ = 360

Persamaan Tujuan : Z - 3x₁ - 2x₂ = 0 Baris 0

Persamaan Kendala : 2x₁ + 5x₂ + A₁ = 200 Baris 1

6x₁ + 3x₂ + A₂ = 360 Baris 2

Untuk mengarahkan artifisial variabel menjadi nol, suatu biaya yang besar ditempatkan pada A₁, A₂, dan A₃ sehingga fungsi tujuannya menjadi :

Z = 3x₁ - 2X₂ + MA₁ + MA₂

Basis	x1	x2	A1	A2	NK	Rasio
Z	8M-3	8M+2	0	0	560M	-
A1	2	5	1	0	200	200:5=40
A2	6	3	0	1	360	360:3=120

Dari table diatas kita ketahui bahwa semua BFS belum optimal. Hal ini dikarenakan belum seluruhnya NBV mempunyai koefisien yang berharga positif. Oleh karena itu Untuk x₂ terpilih sebagai entry variable karena x₂ memiliki nilai koefisien negatif, dan A₁ menjadi Leaving Variable. Dan yang akan menjadi pivot adalah baris 1 karena memiliki rasio paling kecil.

Langkah-langkah ERO Iterasi Pertama :

ERO 1 : Menjadikan nilai koefisien x₂ berharga 1 pada baris 1

0,4x₁ + x₂ + 0,2A₁ = 40

ERO 2 : Menjadikan nilai koefisien x₂ berharga 0 pada baris 0

Z = 3,8x₁ + [M-0,4]A₁ + MA₂ - 80

ERO 3 : Menjadikan nilai koefisien x₂ berharga 0 pada baris 2

4,8x₁ – 0,6A₁ + A₂ = 240

Konversi bentuk standard iterasi pertama :

Z = 3,8x₁ + [M-0,4]A₁ + MA₂ - 80

0,4x₁ + x₂ + 0,2A₁ = 40

4,8x₁ – 0,6A₁ + A₂ = 240

Basis	x1	x2	A1	A2	NK	Rasio
Z	4,8M-3,8	0	0,4-0,4M	0	240M+80	-
X2	0,4	1	0,2	0	40	-
A2	4,8	0	0,6	1	240	-

Iterasi pertama adalah optimum karena koefisien pada persamaan Z semuanya positif, dengan x₁ = 40, x₂ = 240 dan z=240M+80.

Sumber:

http://dianarahma91.blogspot.co.id/2012/07/v-behaviorurldefaultvmlo.html

http://mathematicissofun.blogspot.co.id/2014/01/metode-simpleks_6.html#.WNcy2sYxXIV

http://rhama-shark4hacking.blogspot.co.id/2010/03/contoh-soal-dengan-menggunakan-metode.html