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.
- Sifat yang pertama adalah semua batasan adalah persamaan (dengan tidak ada nilai negatif pada sisi kanan)
- Sifat yang kedua adalah semua variabel tidak ada yang bernilai negatif.
- 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
