Metode Simpleks
dan Pengaplikasinnya dalam kehidupan sehari-hari
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 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 dan digunakan sebagai prosedur penyelesaian dari
setiap program computer.
Salah satu teknik penentuan solusi
optimal yang digunakan dalam pemrograman linier adalah metode simpleks.
Penentuan solusi optimal menggunakan metode simpleks didasarkan pada
teknik eleminasi Gauss Jordan. Penentuan solusi optimal dilakukan dengan memeriksa
titik ekstrim satu per satu dengan cara perhitungan iteratif. Sehingga
penentuan solusi optimal dengan simpleks dilakukan tahap demi tahap yang
disebut dengan iterasi
Ø Ada beberapa istilah yang sangat sering digunakan
dalam metode simpleks, diantaranya yaitu
1.
Iterasi
adalah tahapan perhitungan dimana nilai dalam perhitungan itu tergantung dari
nilai tabel sebelumnya.
2.
Variabel
non basis adalah variabel yang nilainya diatur menjadi nol pada sembarang
iterasi. Dalam terminologi umum, jumlah variabel non basis selalu sama
dengan derajat bebas dalam sistem persamaan.
3.
Variabel
basis merupakan variabel yang nilainya bukan nol pada sembarang iterasi. Pada
solusi awal, variabel basis merupakan variabel slack (jika fungsi kendala
merupakan pertidaksamaan ≤ ) atau variabel buatan (jika fungsi kendala
menggunakan pertidaksamaan ≥ atau =). Secara umum, jumlah variabel basis
selalu sama dengan jumlah fungsi pembatas (tanpa fungsi non negatif).
4.
Solusi
atau nilai kanan merupakan nilai sumber daya pembatas yang masih tersedia. Pada
solusi awal, nilai kanan atau solusi sama dengan jumlah sumber daya pembatas
awal yang ada, karena aktivitas belum dilaksanakan.
5.
Variabel
slack adalah variabel yang ditambahkan ke model matematik kendala untuk
mengkonversikan pertidaksamaan ≤ menjadi persamaan (=). Penambahan
variabel ini terjadi pada tahap inisialisasi. Pada solusi awal, variabel slack
akan berfungsi sebagai variabel basis.
6. Variabel surplus adalah variabel yang
dikurangkan dari model matematik kendala untuk mengkonversikan
pertidaksamaan ≥ menjadi persamaan (=). Penambahan ini terjadi pada tahap
inisialisasi. Pada solusi awal, variabel surplus tidak dapat berfungsi sebagai variabel
basis.
7. Variabel buatan adalah variabel yang
ditambahkan ke model matematik kendala dengan bentuk ≥ atau = untuk difungsikan
sebagai variabel basis awal. Penambahan variabel ini terjadi pada tahap
inisialisasi.Variabel ini harus bernilai 0 pada solusi optimal, karena
kenyataannya variabel ini tidak ada. Variabel hanya ada di atas kertas
8. Kolom
pivot (kolom kerja) adalah kolom yang memuat variabel masuk. Koefisien pada
kolom ini akn menjadi pembagi nilai kanan untuk menentukan baris pivot (baris
kerja).
9. Baris pivot (baris kerja) adalah salah satu
baris dari antara variabel basis yang memuat variabel keluar.
10. Elemen pivot (elemen
kerja) adalah elemen yang terletak pada perpotongan kolom dan baris pivot.
Elemen pivot akan menjadi dasar perhitungan untuk tabel simpleks berikutnya.
11.
Variabel masuk adalah
variabel yang terpilih untuk menjadi variabel basis pada iterasi berikutnya. Variabel masuk
dipilih satu dari antara variabel non basis pada setiap iterasi. Variabel ini
pada iterasi berikutnya akan bernilai positif.
12.
Variabel keluar adalah
variabel yang keluar dari variabel basis pada iterasi berikutnya dan digantikan
oleh variabel masuk. Variabel keluar dipilih satu dari antara variabel basis
pada setiap iiterasi. Variabel ini pada iterasi berikutnya akan bernilai nol.
BENTUK BAKU
Sebelum melakukan
perhitungan iteratif untuk menentukan solusi optimal, pertama sekali bentuk
umum pemrograman linier dirubah ke dalam bentuk baku terlebih dahulu. Bentuk
baku dalam metode simpleks tidak hanya mengubah persamaan kendala ke dalam
bentuk sama dengan, tetapi setiap fungsi kendala harus diwakili oleh satu
variabel basis awal. Variabel basis awal menunjukkan status sumber daya pada
kondisi sebelum ada aktivitas yang dilakukan. Dengan kata lain, variabel
keputusan semuanya masih bernilai nol. Dengan demikian, meskipun fungsi kendala
pada bentuk umum pemrograman linier sudah dalam bentuk persamaan, fungsi
kendala tersebut masih harus tetap berubah.
Ada beberapa hal yang harus diperhatikan dalam membuat
bentuk baku, yaitu :
1.
Fungsi kendala dengan pertidaksamaan ≤ dalam bentuk umum,
dirubah menjadi persamaan (=) dengan menambahkan satu variabel slack.
2.
Fungsi kendala dengan pertidaksamaan ≥ dalam bentuk umum,
dirubah menjadi persamaan (=) dengan mengurangkan satu variabel surplus.
3.
Fungsi kendala dengan persamaan dalam benttuk umum,ditambahkan
satu artificial variabel (variabel buatan).
Langkah-langkah
menyelesaikan metode simpleks secara manual adalah sebagai berikut :
1.
Periksa apakah tabel layak
atau tidak. Kelayakan tabel simpleks dilihat dari solusi (nilai kanan). Jika
solusi ada yang bernilai negatif, maka tabel tidak layak. Tabel yang tidak
layak tidak dapat diteruskan untuk dioptimalkan.
2.
Tentukan kolom kunci.
Penentuan kolom kunci dilihat dari koefisien fungsi tujuan (nilai di sebelah
kanan baris z) dan tergantung dari bentuk tujuan. Jika tujuan berupa maksimisasi,
maka kolom kunci adalah kolom dengan koefisien negatif terbesar. Jika tujuan
minimisasi, maka kolom kunci adalah kolom dengan koefisien positif terbesar.
Perhatikan, kita tidak menggunakan kata-kata nilai terkecil dan terbesar,
karena kita memang tidak memilih nilai terkecil dan terbesar. Jika kolom kunci
ditandai dan ditarik ke atas, maka kita akan mendapatkan variabel keluar. Jika
nilai negatif terbesar (untuk tujuan maksimisasi) atau positif terbesar (untuk
tujuan minimisasi) lebih dari satu, pilih salah satu secara sembarang.
3.
Tentukan
baris kunci. Baris kunci ditentukan setelah membagi nilai kanan dengan nilai
kolom kunci yang bersesuaian (nilai yang terletak dalam satu baris). Dalam hal
ini, nilai negatif dan 0 pada kolom kunci tidak diperhatikan, artinya tidak
ikut menjadi pembagi. Baris kunci adalah baris dengan rasio pembagian terkecil.
Perhatikan, rasio pembagian tidak mungkin bernilai negatif, karena nilai kanan
tidak negatif demikian juga dengan nilai kolom kunci. Jika baris kunci ditandai
dan ditarik ke kiri, maka kita akan mendapatkan variabel keluar. Jika
rasio pembagian terkecil lebih dari satu, pilih salah satu secara sembarang.
4.
Tentukan angka kunci. Angka
kunci merupakan nilai yang terletak pada perpotongan kolom dan baris kunci.
5.
Bentuk tabel simpleks baru.
Tabel simpleks baru dibentuk dengan pertama sekali menghitung nilai baris kunci
baru. Baris kunci baru adalah baris kunci lama dibagi dengan angka kunci. Baris
baru lainnya merupakan pengurangan nilai kolom kunci baris yang bersangkutan
dikali baris kunci baru dalam satu kolom terhadap baris lamanya yang terletak
dalam satu kolom juga.
Contoh Soal :
1. 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.
Contoh Soal :
Maksimumkan Z = 40 X1 + 30 X2 + 50 X3
Dengan syarat : 6X1 + 4X2 + X3
≤ 32.000
6X1 + 7X2
+ 3X3
≤ 16.000
4X1 + 5X2
+ 12 X3 ≤ 24.000
X1 X2 X3 ≥ 0
Bentuk baku masalah LP
itu adalah :
Z -40X1 – 30X2 – 50X3 – 0S1 – 0S2 – 0S3 = 0
6X1 + 4X2 +
X3 + S1 = 32.000
6X1 + 7X2 +
3X3 + S2 =
16.000
4X1 + 5X2 +
12X3 + S3 = 24.000
Solusi dengan
menggunakan tabel simpleks yang lengkap ditunjukan pada tabel berikut.
Penyelesaian
Langkah pertama dalam
menghitung Optimality condition adalah menentukan variabel nonbasis dengan
koefisien negatif terbesar sebagai entering variable, kemudian menentukan
leaving variabel atau variabel basis yang memiliki rasio terkecil yang akan
menentukan pivot elemen dimana pivot elemen adalah perpotongan entering kolom
dengan pivot equation. Pivot elemen ditunjukkan dengan tanda kurung.Tabel 3.6 Tabel
Simpleks Awal.
Perhitungan untuk Iterasi Pertama (1) tabel 3.8
SUMBER :
Tabel 3.8 Tabel Iterasi
Pertama
Pada Iterasi yang kedua
telah tercapai solusi optimum dengan X1 = 2000, X3 = 440.000/3 dan Z =
146.666,67. Pada tabel optimum (Tabel 3.10) S2 dan S3 = 0, artinya pengambil
keputusan akan menggunakan seluruh persediaan sumberdaya kedua dan ketiga
SUMBER :
1.
http://awank38.blogspot.co.id/2015/01/metode-simpleks-dalam-program-linier.html
2. http://farishhantulaut.blogspot.co.id/2011/05/riset-operasi-aplikasi-dalam
kehidupan.html
Tidak ada komentar:
Posting Komentar