06/10/2014
METODE SIMPLEKS Angga Akbar Fanani, ST., MT.
SPL Nonhomogen dengan penyelesaian tunggal (unique) Cari penyelesaian dari sistem : x1 – 2x2 + x3 = -5 3x1 + x2 – 2x3 = 11 -2x1 + x2 + x3 = -2 Metode Gauss-Jordan : lakukan OBE, bawa (A G) menjadi bentuk echelon baris tereduksi.
1 (A G) = 3 2 1 ~ 0 0
2 1 5 1 2 1 5 1 2 11 ~ 0 7 5 26 0 3 3 12 1 1 2 2 1 5 1 2 1 5 7 5 26 ~ 0 1 1 4 0 7 5 26 1 1 4
1 2 1 5 1 2 1 5 ~ 0 1 1 4 ~ 0 1 1 4 0 0 2 2 0 0 1 1
1 2 0 4 ~ 0 1 0 3 0 0 1 1 1 0 0 2 ~ 0 1 0 3 0 0 1 1
r(A) = 3 r(A G) = 3 n=3
Persamaan terakhir menjadi: x1 = 2 x2 = 3 x3 = -1
Jadi penyelesaiannya : {(2, 3, -1)}.
1
06/10/2014
METODE SIMPLEK Metode geometrik untuk menyelesaikan permasalahan linier programming. Metode grafik hanya dapat digunakan untuk menyelesaikan permasalahan dengan 2 variabel dan dengan sedikit fungsi pembatas. Apa yang dapat dilakukan dengan permasalahan dengan variabel keputusan lebih dari dua?
Digunakan metode aljabar yang disebut metode simplek, yang diekmbangkan oleh George B. Dantzig (1914-2005) pada tahun 1947 ketika bertugas di Angkatan Udara Amerika.
SIMPLEX METHOD
langkah-1 Tulis persamaan ke dalam bentuk persamaan standar optimasi, tentukan slack variabel.
langka h-2 Buat tabel standar simplek
langkah 3 apakah terdapat indikator negatif pada baris Zj?
STOP Solusi optimal telah didapatkan
langka h-3 Pilih kolom pivot
langkah 4 Apakah terdapat elemen positif pada kolom pivot, diatas garis tebal?
langkah5 Pilih elemen pivot dan lakukan operasi pivot.
STOP Permasalahan linier programming tidak memiliki solusi optimal
Algoritma simplek untuk permasalahan standar maksimasi.
2
06/10/2014
Untuk menyelesaikan permasalahan linier programming dalam bentuk standar, terapkan langkah berikut: 1- Rubah pertidaksamaan dalam fungsi tujuan menjadi sebuah persamaan dengan menambahkan slack variables. 2- Buat tabel awal simplek. 3- Pilih pivot column. ( kolom dengan nilai negatif terbesar pada baris Zj) 4- Pilih pivot row. (baris dengan nilai non negatif terkecil ketika besaran dari ruas kanan dibagi dengan elemen dari kolom pivot.) 5-Lakukan operasi baris elementer untuk menghitung nilai baru dari baris pivot sehingga pivot bernilai 1 (membagi setiap anggota baris dengan pivot number.) 6- Lakukan operasi baris elementer untuk membuat semua angka pada pivot kolom bernilai 0 kecuali pivot number. Jika semua nilai pada baris Zj ernilai positif atau nol, maka ini merupakan tabel akhir. Jika tidak kembali ke langkah 3. 7- jika sudah diperoleh tabel akhir, maka linier programing telah mendapatkan solusi optimal yaitu terletak pada sudut kanan baris Zj.
Indeks Pivot Column: kolom dari tabel yang merepresentasikan variabel yang dimasukan kedalam tabel solusi.
Pivot Row: Baris dari tabel yang merepresentasikan variabel yang dikeluarkan dari tabel solusi.
Pivot Number: Element pertemuan antara pivot column dan the pivot row.
Slack Variabel: merepresentasikan sumber daya yang tidak digunakan
3
06/10/2014
Tebel Simplek Sebagian besar permasalahan pada dunia nyata seringkali terlalu kompleks untuk diselesaikan dengan metode grafik. Permasalahan tersebut memiliki banyak titik untuk dievaluasi dan pengerjaan aljabar akan panjang. Tabel simplek merupakan langkah yang sistematis untuk mengevaluasi gabungan dari bebrapa variebel dalam rangka untuk mendapatkan slusi terbaik.
Initial Simplex Tableau Semua variabel
Variabel basis
solusi
koefisien
0
4
06/10/2014
Contoh soal Perusahaan furnitur ABC memproduksi meja dan kursi. Setiap meja membutuhkan 4 jam kerja dari tukang kayu dan dua jam kerja dari bagian finishing. Sedangkan setiap kursi membutuhkan 3 jam tukang kayu dan 1 jam finishing. Dalam 1 minggu tersedia 240 jam tukang kayu dan 100 jam jam finishing. Setiap meja menghasilkan keuntungan Rp. 70,- dan setiap kursi menghasilkan keuntungan Rp. 50,-. Berapakah kursi dan meja yang harus diproduksi?
Langkah 1 Semua informasi terkait contoh soal Sumber daya Meja ( x1 )
Kursi ( x2 )
batasan
Tukang kayu (jam)
4
3
240
Finishing (jam)
2
1
100
keuntungan
70
50
Fungsi tujuan
P 70 x1 50x2
Batasan tukang kayu
4 x1 3x2 240
Batasan finishing
2 x1 1x2 100
Batasan non negatif
x1 , x2 0
5
06/10/2014
Langkah pertama metode simplek adalah merubah pertidaksamaan menjadi persamaan. Tanda kurang dari (≤) atau lebih dari (≥) dirubah menjadi sama dengan menambahkan slack variabel. Asumsikan s1 sebagai jam tukang kayu dan s2 sebagai jam finishing yang belum digunakan dalam 1 minggu. Fungsi batasan akan menjadi; 4 x1 3x2 s1 240 2 x1 x2 s2 100
atau
4 x1 3 x2 s1 0 s2 240 2 x1 x2 0 s1 s2 100
Sumber daya yang tidak digunakan tidak menghasilkan keuntungan, slack variabel dapat dimasukan dalam fungsi objektif dengan koefisien nol (0) : P 70 x1 50 x2 0s1 0s2 P 70 x1 50 x2 0s1 0s2 0
Permasalahan tersebut dapat diselesaikan sebagai 3 persamaan linier dengan 5 variabel x1, x2 , s1 , s2 , P dengan P merupakan nilai maximum;
4 x1 3 x2 s1 0 s2 240 2 x1 x2 0 s1 s2 100 P 70 x1 50 x2 0 s1 0 s2 0
Kemudian, sisetm persamaan linier dapat ditulis dalam sebuah matik berukuran 3x6. Tabel awal adalah sebagai berikut;
6
06/10/2014
Langkah 2 Basic variabel
x1
x2
S1
S2
P
Right Hand Side
S1
4
3
1
0
0
240
S2
2
1
0
1
0
100
P
-70
-50
0
0
1
0
Solusi berdasarkan tabel awal;
x1 0, x2 0, s1 240, s2 100, P 0 Pada tabel awal simplek variabel S1 and S2 masuk kedalam solusi. Solusi awal menggunakan asumsi bahwa semua sumber daya jam kerja belum digunakan. Dengan demikian slack variabel memiliki nilai terbesar.
Variabel yang berada pada tabel solusi disebut variabel basis (basic variabel). Setiap variabel basis bernilai sesuai dengan nilai pada RHS (right hand side). Sedangkan semua variabel selain variabel basis bernilai nol (0). Pada proses simplek, variabel basis pada tabels solusi digantikan oleh variabel lain yang tidak berada pada tabel solusi. Nilai dari variabel yang keluar dari tabel solusi nilainya menjadi nol (0).
7
06/10/2014
Langkah 3 Pilih kolom pivot (tentukan variabel yang akan masuk ke dalam tabel solusi). Pilih kolom dengan nilai negatif paling besar pada baris fungsi tujuan. variabel basis
x1
x2
S1
S2
P
Right hand side
S1
4
3
1
0
0
240
S2
2
1
0
1
0
100
P
-70
-50
0
0
1
0
Pivot column
x1 seharusnya masuk ke tabel solusi dikarenakan setiap unit x1 (meja) berkontribusi keuntungan sebesar 70 lebih besar dari kursi yaitu sebesar 50.
Langkah 4 Dikarenakan nilai fungsi tujuan untuk pivot kolom bernilai negatif. Dapat dilanjutkan pada langkah 5.
8
06/10/2014
langkah 5 Pilih baris pivot (variabel yang akan dikeluarkan dari tabel solusi). Bagi elemen Right hand side (RHS) untuk setiap baris dengan elemen dari olom pivot. Baris pivot adalah baris dengan hasil pembagian yang bernilai non negatif paling kecil. masuk
keluar
variabel basis
x1
x2
S1
S2
P
Right hand side
S1
4
3
1
0
0
240
240 / 4 60
S2
2
1
0
1
0
100
100 / 2 50
P
-70
-50
0
0
1
0 Pivot row
Pivot column Pivot number
Masukan x1 pada menjadi variabel basis. 60 meja dapat diproduksi berdasarkan batasan 240 jam kerja tukang kayu, namun hanya 50 meja yang dapat diproduksi berdasarkan batasan 100 jam kerja finishing. Sehingga Langkah selanjutnya adalah menghitung nilai baru dari baris pivot, yaitu dengan membagi setiap elemen dengan pivot number.
variabel basis
x1
x2
S1
S2
P
Right hand side
S1
4
3
1
0
0
240
x1
1
1/2
0
1/2
0
50
P
-70
-50
0
0
1
0
R2 2
9
06/10/2014
Lakukan operasi baris elementer sehingga semua elemen dari kolom pivot menjadi nol (0) kecuali pivot number yang harus bernilai satu (1).
variabel basis
x1
x2
S1
S2
P
Right hand side
S1
0
1
1
-2
0
40
x1
1
1/2
0
1/2
0
50
P
0
-15
0
35
1
3500
4.R2 R1 70.R2 R3
Dikarenakan 50 meja diproduksi sehingga jam kerja tukang kayu yang belum digunakan berkurang sebesar 200 (4 jam/meja dikalikan 50), sehingga akan bernilai 40 dari sebelumnya 240. memproduksi 50 meja akan menghasilkan keuntungan sebesar 3500.
Sehingga solusi baru , x1 50, x2 0, s1 40, s2 0, P 3500 Selanjutnya ulangi langkah hingga semua nilai pada baris fungsi tumenjadi variabel basis. Pilih kolom pivot baru. Masukan x2 should enter into the solution mix. Pilih baris pivot baru, keluarkan S1 dari variabel basis,ganti dengan x2. Enter
Exit
variabel basis
x1
x2
S1
S2
P
Right hand side
S1
0
1
1
-2
0
40
40 /1 40
x1
1
1/2
0
1/2
0
50
50 / 0,5 100
P
0
-15
0
35
1
3500
New pivot column
New pivot row
10
06/10/2014
Hitung nilai baru bagi baris pivot. Dikarenakan pivot number sudah bernilai 1, semua nilai pada baris pivot tetap. Lakukan operasi baris elementer sehingga semua elemen dari kolom pivot menjadi nol (0) kecuali pivot number yang harus bernilai satu (1).
variabel basis
x1
x2
S1
S2
P
Right hand side
x2
0
1
1
-2
0
40
x1
1
0
-1/2
3/2
0
30
1 .R1 R2 2
P
0
0
15
5
1
4100
15.R1 R3
Jumlah kursi yang diproduksi adalah 40 , sehingga jumlah meja yang diproduks turun 20 (1/2 meja/kursi dikalikan 40). Jumlah meja yang diproduksi turun dari 50 menjadi 30. penurunan 20 meja digantIf 40 chairs are made, then the number of tables are redukan 40 kursi berdampak pada kenaikan keuntungan sebesar 600. keuntungan total berubah dari 3500 menjadi 4100. Pada tabel hasil iterasi kedua didapatkan bahwa semua elemenya bernilai positif semua, dengan demikian solusi tersebut merupakan nilai fungsi tujuan yang maksimum.
11
06/10/2014
Hasil Tabel simplek merepresentasikan solusi optimal untuk permasalahan LP, dengan kombinasi variabelkeputusan sebagai berikut: x1 30,
x2 40,
s1 0,
s2 0
dan fungsi keuntungan atau P= 4100 Solusi optimal (keuntungan maksimal yang mungkin dihasilkan) adalah dengan memproduksi 30 meja dan 40 kursi dengan keuntungan sebesar 4100.
12
