METODE SIMPLEKS DAN PENGAPLIKASIANNYA

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 simpleks biasanya digunakan untuk  memecahkan setiap permasalahan pada program linier yang  kombinasi variabelnya terdiri dari tiga variabel atau lebih.

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.
3. Sifat yang ketiga adalah fungsi tujuan dapat berupa minimisasi atau maksimisasi.

           Sebelum menyelesaikan  permasalahan dengan menggunakan metode simpleks. Terlebih dahulu masalah tersebut harus diubah kedalam bentuk formulasi model linear programing. Setelah berbentuk suatu model linear programming, maka model tersebut harus diubah terlebih dahulu ke dalam bentuk baku, dimana semua batasan diekspresikan sebagai persamaan dengan menambahkan variabel slack atau surplus sebagaimana diperlukan, maka dapat diterapkan prosedur penyelesaian dengan menggunakan metode simpleks.

 B. Contoh Pengaplikasian Metode Simpleks

                 PT Yummy food memiliki sebuah pabrik yang akan memproduksi dua jenis produk yaitu vanilla dan violette. Untuk memproduksi kedua produk tersebut diperlukan bahan baku A, bahan baku B dan jam tenaga kerja. Maksimum pengerjaan bahan baku A adalah 60kg per hari, bahan baku B 30kg per hari dan tenaga kerja 40jam per hari. Kedua jenis produk memberikan sumbangan keuntungan sebesar Rp40,00 untuk vanilla dan Rp30,00 untuk violette. Masalah yang dihadapi adalah bagaimana menentukan jumlah unit setiap produk yang akan diproduksi setiap hari. Kebutuhan setiap unit produk akan bahan baku dan jam tenaga kerja dapat dilihat pada tabel berikut ini:

 

Jenis bahan baku dan tenaga kerja	Kg bahan baku dan jam tenaga kerja		Maksimum Penyediaan
	Vanilla	Violette
Bahan baku A	2	3	60Kg
Bahan baku B	-	2	30Kg
Tenaga Kerja	2	1	40jam
Sumbangan keuntungan	Rp40,00	Rp30,00

          Penyelesaian:

          Z = Rupiah keuntungan per hari

          X1 = Jumlah vanilla yang diproduksi/perhari

          X2 = jumlah violette yang diproduksi/hari

         Langkah 1

         Formulasi LP (bentuk standar)

Fungsi tujuan              è Zmax = 40X1 + 30X2

Fungsi kendala            è I.  2X1 + 3X2 ≤ 60

                                        II.  2X2 ≤ 30

                                        III. 2X1 + 1X2 ≤ 40

                                        IV. X1,X2 ≥ 0

Diubah menjadi:

2X1 + 3X2 + S1 + 0S2 + 0S3 = 60

            2X2 + 0S1 + S2 + 0S3 = 30

2X1 + 1X2 + 0S1 + 0S2 + S3 = 40

40X1 + 30X2 + 0S1 + 0S2 + 0S3

C1 = 40, C2 = 30, C3 = 0, C4= 0, C5 = 0     

Langkah 2

Tabel simplex awal masalah PT Yummy Food

	Cj	40	30	0	0	0
Ci	BV	X1	X2	S1	S2	S3	Bi
0	S1	2	3	1	0	0	60
0	S2	0	2	0	1	0	30
0	S3	2	1	0	0	1	40
	Zj	0	0	0	0	0	0
Cj-ZJ		40	30	0	0	0

Langkah 3

Apakah tabel tersebut sudah optimal?

Belum, karena tabel optimal bila nilai yang terdapat pada baris Cj – Zj ≤ 0

Langkah 4

Penyelesaian dengan cara iterasi

1.    Menentukan kolom kunci, yaitu kolom yang memiliki nilai Cj-Zj terbesar yaitu kolom x1. Dengan demikian x1 akan masuk dalam basis

2.    Menentukan baris kunci, yaitu baris yang memiliki angka indeks terkecil dan bukan negatif. Dalam hal ini baris s3. Dengan demikian s3 akan keluar dari basis dan tempatnya akan digantikan oleh x1

3.    Menetukan angka kunci. Angka kunci adalah angka yang terdapat pada persilangan kolom kunci dengan baris kunci, dalam hal ini angka kunci = 2

4.    Mencari angka baru yang terdapat pada baris kunci, dengan cara membagi semua angka yang terdapat pada baris kunci dengan angka kunci

            Angka baru = 40/2, 2/2, ½, 0/2, 0/2, ½

            Atau = 20, 1, ½, 0,0 ½

5.    Mencari angka baru pada baris lain, yaitu :

            Baris S1

            Angka lama                       = [ 60 2 3 1 0 0 ]

            Angka baru                        = [ 20 1 ½ 0 0 ½] (2)

            Angka baru                        = [20 0 2 0 0 -1]

          Baris S2

           Angka lama                       = [ 30 0 2 0 1 0]

           Angka baru                        = [ 20 1 ½ 0 0 1/2] (0)

           Angka baru                        = [ 30 0 2 0 1 0]

Hasil perhitungan di atas, akan nampak pada tabel baru simplex yaitu tabel yang merupakan hasil iterasi pertama.

	Cj	40	30	0	0	0
Ci	BV	X1	X2	S1	S2	S3	Bi
0	S1	0	2	1	0	-1	20
0	S2	0	2	0	1	0	30
40	X1	1	½	0	0	½	20
	Zj	40	20	0	0	20
Cj-ZJ		0	10	0	0	0

Tabel iterasi 1 belum optimal sehingga harus diulang langkah di atas dan akan di dapat tabel iterasi 2:

	Cj	40	30	0	0	0
Ci	BV	X1	X2	S1	S2	S3	Bi
30	X1	0	1	½	0	-1/2	10
0	S2	0	0	-1	1	1	10
40	S3	1	0	-1/4	0	¾	15
	Zj	40	30	5	0	15
Cj-ZJ		0	0	-5	0	-15	900

Solusi optimum tabel iterasi 2 menunjukan bahwa total nilai Z = 900 dengan masing-masing variabel keputusan X1 = 15 dan X2 = 10.

Variabel basis	Koefisien fungsi tujuan	Nilai variabel basis
X2	30	10	300
S2	0	10	0
X1	40	15	600
		JUMLAH	900

KESIMPULAN:

1.    Pada tabel iterasi 2 merupakan tabel akhir simplex, dengan solusi optimal adalah :

X1 (vanilla)                 = 15 unit

X2 (violette)                = 10 unit

Z (keuntungan)           = Rp 900,00

2.    Kendala kedua (bahan baku B) masih tersisa sebanyak 10 Kg yang ditunjukan oleh nilai S2 =10, pada tabel optimal

3.    Kendala 1 dan 3 tidak ada sisa (full capacity), yang ditunjukan oleh nilai S1 = S3 = 0  (variabel nonbasis). Hal ini juga dapat dibuktikan dengan memasukan nilai S1 dan S2 ke dalam kendala 1 dan 3

           Kendala 1 : 2X1 + 3X2 = 60

2 (15) + 3 (10) = 60

                                60 = 60

           Bahan baku yang digunakan = yang tersedia

           Kendala 3 :             2X1 + 1X2 = 40

                        2 (15) + 1(10) = 40

                                    40 = 40

          Jam kerja yang digunakan = yang tersedia