METODE SIMPLEKS
NAMA : AHMAD SOFIYAN
KELAS : 2TA05
NPM : 10315366
A. Pengertian
Metode
simpleks adalah salah satu teknik penyelesaian dalam program linear yang
dipakai untuk teknik pengambilan keputusan dalam permasalahan yang berhubungan
dengan pengalokasian sumberdaya secara optimal. Metode simpleks digunakan umtuk
mencari nilai optimal dari program linear yang melibatkan banyak constraint
(pembatas) dan banyak variabel. Penemuan metode ini merupakan lompatan besar
dalamriset operasi dan digunakan sebagai prosedur penyelesaian dari setiap
program komputer.
B. Pendahuluan
Metode
penyelesaian program linier dengan metode simpleks pertamakali dikemukakan oleh
George Dantzig pada tahun 1947. Metode ini menjadi terkenal ketika diketemukan
alat hitung elektronik dan menjadi popular ketika munculnya computer. Proses
perhitungan metode ini dengan melakukan iterasi berulang-ulang sampai tercapai
hasil optimal dan proses perhitungan ini menjadi mudah dengan komputer.
Selanjutnya
berbagai alat dan metode dikembangkan untuk menyelesaikan masalah program
linear bahkan sampai pada masalah riset operasi hingga tahun 1950an seperti
pemrogaman dinamik, teori antrian, dan persediaan.
Program
Linier merupakan metode matematik dalam mengalokasikan sumber daya yang langka
untuk mencapai tujuan tunggal seperti memaksimumkan atau meminimumkan biaya.
Program linier banyak diterapkan dalam membantu menyelesaikan masalah ekonomi,
industri, militer, social, dan lain-lain.
Karakteristik
persoalan dalam program linier adalah sebagai berikut :
- Ada tujuan yang ingin dicapai
- Tersedia beberapa alternatif
untuk mencapai tujuan
- Sumberdaya dalam keadaan
terbatas
- Dapat dirumuskan dalam bentuk
matematika (persaman/ketidaksamaan)
C. Langkah-langkah
- 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.
- MENGUBAH FUNGSI BATASAN KE
BENTUK KANONIK (SLACK VARIABLE)
a11x1 +
a12x2 ≤ b1 → a11x1 + a12x2 + s1 = b1
a21x1 +
a22x2 ≤ b2 → a21x1 + a22x2 + s2 = b2
- 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
|
- 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
|
- 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
|
- MENENTUKAN ANGKA KUNCI
Angka
kunci merupakan pertemuan antara kolom kunci dengan baris kunci. Jadi, kita
memperoleh a22 sebagai angka kunci.
- 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
|
- 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
- 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.
Contoh
Soal :
Selesaikan
kasus berikut ini menggunakan metode simpleks :
Maksimum z
= 8 x1 + 9 x2 + 4x3
Kendala :
x1 +
x2 + 2x3 ≤ 2
2x1 +
3x2 + 4x3 ≤ 3
7x1 +
6x2 + 2x3 ≤ 8
x1,x2,x3 ≥
0
PENYELESAIAN
:
Bentuk
bakunya adalah :
Maksimum z
= 8 x1 + 9 x2 + 4x3 + 0s1 +
0s2 + 0s3 atau
z – 8 x1 –
9 x2 – 4x3 + 0s1 + 0s2 +
0s3 = 0
KENDALA
:
x1 +
x2 + 2x3 + s1 = 2
2x1 +
3x2 + 4x3 + s2 = 3
7x1 +
6x2 + 2x3 + s3 = 8
x1,x2,x3 ,s1 ,
s2 , s3 ≥ 0
SOLUSI
/ TABLE AWAL SIMPLEKS :
VB
|
X1
|
X2
|
X3
|
S1
|
S2
|
S3
|
NK
|
Rasio
|
Z
|
-8
|
-9
|
-4
|
0
|
0
|
0
|
0
|
|
S1
|
1
|
1
|
2
|
1
|
0
|
0
|
2
|
|
S2
|
2
|
3
|
4
|
0
|
1
|
0
|
3
|
|
S3
|
7
|
6
|
2
|
0
|
0
|
1
|
8
|
Karena
nilai negative terbesar ada pada kolom X2, maka kolom X2 adalah
kolom pivot dan X2 adalah variabel masuk. Rasio pembagian nilai
kanan dengan kolom pivot terkecil adalah 1 bersesuaian dengan
baris s2, maka baris s2 adalah baris pivot dan s2 adalah
varisbel keluar. Elemen pivot adalah 3.
VB
|
X1
|
X2
|
X3
|
S1
|
S2
|
S3
|
NK
|
Rasio
|
Z
|
-8
|
-9
|
-4
|
0
|
0
|
0
|
0
|
|
S1
|
1
|
1
|
2
|
1
|
0
|
0
|
2
|
2
|
S2
|
2
|
3
|
4
|
0
|
1
|
0
|
3
|
1
|
S3
|
7
|
6
|
2
|
0
|
0
|
1
|
8
|
8/6
|
ITERASI
1
Nilai
pertama yang kita miliki adalah nilai baris pivot baru (baris x2). Semua
nilai pada baris s2 pada tabel solusi awal dibagi dengan 3
(elemen pivot).
VB
|
X1
|
X2
|
X3
|
S1
|
S2
|
S3
|
NK
|
Rasio
|
Z
|
||||||||
S1
|
||||||||
x2
|
2/3
|
1
|
4/3
|
0
|
1/3
|
0
|
1
|
|
S3
|
Perhitungan
nilai barisnya :
BARIS Z
:
-8
-9
-4
0
0
0 0
-9
( 2/3
1
4/3
0 1/3
0 1
) –
-2
0 8
0 3
0 9
BARIS S1 :
1
1
2
1
0
0 2
1
(2/3
1
4/3
0
1/3 0
1 ) –
1/3
0
2/3
1
-1/3 0
1
BARIS
S3 :
7
6
2 0
0
1 8
6
( 2/3
1 4/3
0
1/3
0 1 ) –
3
0
-6
0
-2
1 2
Maka tabel
iterasi 1 ditunjukkan tabel di bawah. Selanjutnya kita periksa apakah tabel
sudah optimal atau belum. Karena nilai baris z di bawah variabel x1 masih
negatif, maka tabel belum optimal. Kolom dan baris pivotnya ditandai pada
tabel di bawah ini :
VB
|
X1
|
X2
|
X3
|
S1
|
S2
|
S3
|
NK
|
Rasio
|
Z
|
-2
|
0
|
8
|
0
|
3
|
0
|
9
|
–
|
S1
|
1/3
|
0
|
2/3
|
1
|
-1/3
|
0
|
1
|
3
|
X2
|
2/3
|
1
|
4/3
|
0
|
1/3
|
0
|
1
|
3/2
|
S3
|
3
|
0
|
-6
|
0
|
-2
|
1
|
2
|
2/3
|
Variabel
masuk dengan demikian adalah X1 dan variabel
keluar adalah S3 .Hasil perhitungan iterasi ke 2 adalah
sebagai berikut :
ITERASI
2 :
VB
|
X1
|
X2
|
X3
|
S1
|
S2
|
S3
|
NK
|
Rasio
|
Z
|
0
|
0
|
4
|
0
|
5/3
|
2/3
|
31/3
|
|
S1
|
0
|
0
|
4/3
|
1
|
-1/9
|
-1/9
|
7/9
|
|
X2
|
0
|
1
|
8/3
|
0
|
7/9
|
-2/9
|
5/9
|
|
X1
|
1
|
0
|
-2
|
0
|
-2/3
|
1/3
|
2/3
|
Tabel
sudah optimal, sehingga perhitungan iterasi dihentikan !
Perhitungan
dalam simpleks menuntut ketelitian tinggi, khususnya jika angka yang
digunakan adalah pecahan. Pembulatan harus diperhatikan dengan baik.
Disarankan jangan menggunakan bentuk bilangan desimal, akan lebih teliti jika
menggunakan bilangan pecahan. Pembulatan dapat menyebabkan iterasi lebih
panjang atau bahkan tidak selesai karena ketidaktelitian dalam melakukan
pembulatan.
Perhitungan
iteratif dalam simpleks pada dasarnya merupakan pemeriksaan satu per satu
titik-titik ekstrim layak pada daerah penyelesaian. Pemeriksaan dimulai dari
kondisi nol (dimana semua aktivitas/variabel keputusan bernilai nol). Jika
titik ekstrim berjumlah n, kemungkinan terburuknya kita akan melakukan
perhitungan iteratif sebanyak n kali.
sumber:
Tidak ada komentar:
Posting Komentar