Metode Simplex Toha Ardi Nugraha
Pendahuluan • Metode simpleks merupakan salah satu teknik penyelesaian dengan 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).
Metode Simplex • Ubah seluruh pertidaksamaan menjadi persamaan dengan menambahkan variabel slack pada kendala <= , dan mengurangi variabel slack dari kendala >= . Contoh : Pengubahan :
ak1X1 + ak2X2 + … + aknXn <= bk ak1X1 + ak2X2 + … + aknXn + Sk = bk
Contoh : Pengubahan :
ak1X1 + ak2X2 + … + aknXn >= bk ak1X1 + ak2X2 + … + aknXn - Sk = bk
Contoh Kasus MAX: 350X1 + 300X2 S.T.: 1X1 + 1X2 + S1 = 200 9X1 + 6X2 + S2 = 1566 12X1 + 16X2 + S3 = 2880 X1, X2, S1, S2, S3 >= 0
} keuntungan } pompa } jam kerja } pipa } nonnegatif
• Jika terdapat n variabel pd sebuah sistem dengan m persamaan (dimana n>m), kita dapat memilih beberapa variabel m dan menyelesaikan persamaan tsb. (mengatur sisa n-m variabel menjadi nol.)
Langkah Umum Metode Simplex 1. Identifikasi beberapa solusi layak basis (titik-titik
ekstrim) untuk sebuah PL, kemudian berpindah pd titik ekstrim yang berdekatan, jika perpindahan tsb. betul-betul meningkatkan nilai f. tujuan. 2. Perpindahan titik ekstrim tsb. Terjadi dgn mengganti sebuah variabel basis dgn sebuah var non-basis untuk membuat sebuah solusi layak basis yang baru. 3. Ketika tak ada lagi titik-titik ekstrim yg berdekatan mempunyai nilai f. tujuan yg lebih baik, proses dihentikan – berarti titik ekstrim terakhir adalah solusi optimal.
Proses Pencarian Kenungkinan Solusi Layak Basis Variabel Variabel Nilai Basis Non-Basis Solusi Tujuan 1 S1, S2, S3 X1, X2 X1=0, X2=0, S1=200, S2=1566, S3=2880 0 2
X1, S1, S3
X2, S2
X1=174, X2=0, S1=26, S2=0, S3=792
60,900
3
X1, X2, S3
S1, S2
X1=122, X2=78, S1=0, S2=0, S3=168
66,100
4
X1, X2, S2
S1, S3
X1=80, X2=120, S1=0, S2=126, S3=0
64,000
5
X2, S1, S2
X1, S3
X1=0, X2=180, S1=20, S2=486, S3=0
54,000
6* X1, X2, S1
S2, S3
X1=108, X2=99, S1=-7, S2=0, S3=0
67,500
7* X1, S1, S2
X2, S3
X1=240, X2=0, S1=-40, S2=-594, S3=0
84,000
8* X1, S2, S3
X2, S1
X1=200, X2=0, S1=0, S2=-234, S3=480
70,000
9* X2, S2, S3
X1, S1
X1=0, X2=200, S1=0, S2=366, S3=-320
60,000
10* X2, S1, S3
X1, S2
X1=0, X2=261, S1=-61, S2=0, S3=-1296 78,300
* Solusi tak layak (mengandung nilai negatif)
Solusi Layak Basis & Titik-Titik Ekstrim X2
Solusi Layak Basis 1 X1=0, X2=0, S1=200, S2=1566, S3=2880
250
2 X1=174, X2=0, S1=26, S2=0, S3=792 3 X1=122, X2=78, S1=0, S2=0, S3=168
5
200
4 X1=80, X2=120, S1=0, S2=126, S3=0 5 X1=0, X2=180, S1=20, S2=486, S3=0
150
4
100
3
50 1
2
0
0
50
100
150
200
250
X1
Sambungan metode simplex… Berapa banyak solusi basis yang terjadi ?!!!
Kemungkinan Banyaknya Solusi Basis Yg Dapat Dibuat Mis. n = jumlah variabel m = jumlah kendala Sesudah penambahan variabel slack, terdapat : (n + m)! n! m!
cara untuk mendapatkan kemungkinan solusi basis.
Contoh: Jika n = 2 dan m = 3, maka 5!/(2! 3!) = 10.
Beberapa Istilah • Solusi Augmented : solusi masalah sesudah variabel slack ditambahkan. • Solusi Basis : solusi titik sudut augmented dengan mengatur sejumlah menjadi nol dan menyelesaikan sisa variabel lainnya. • Solusi Layak Basis (SLB) : solusi basis yang layak menjadi kandidat solusi optimal • Variabel Basis : variabel yang diselesaikan dalam solusi basis • Variabel Non-Basis : Variabel yg sama dengan nol pada solusi basis 10
Outline Algoritma Simplex • Mulai pada Solusi Layak Basis (SLB) / basic feasible solution (BFS) (biasanya pd titik asal) • Pindah ke SLB yg lebih baik – Mengembangkan fungsi tujuan • Berhenti ketika bertemu SLB yg lebih baik dibandingkan seluruh SLB yg ada – Solusi Optimal ditemukan
Tabel Simplex
Max
z - 6x1 - 4x2
=0
Subj. to:
x1 + x2 + x3 = 12 x1 - 2x2 + x4 = 6 x2 + x5 = 8
Var Pers. Basis
z
x1
x2
x3
x4
x5
Solusi
0
z
1
-6
-4
0
0
0
0
1
x3
0
1
1
1
0
0
12
2
x4
0
1
-2
0
1
0
6
3
x5
0
0
1
0
0
1
8
z = 6x1 + 4x2
Algoritma Simplex
Step 1: Pilih sebuah variabel baru untuk masuk basis. Pilihlah variabel non-basis yg punya nilai negatif terbesar
Var Pers. Basis 0
z
z 1
x1 -6
x2 -4
x3 0
x4 0
x5 0
Solusi 0
1
x3
0
1
1
1
0
0
12
2
x4
0
1
-2
0
1
0
6
3
x5
0
0
1
0
0
1
8
Step 2a: Pilih sebuah variabel basis untuk meninggalkan basis
Var Pers. Basis
z
x1
x2
x3
x4
x5
0
z
1
-6
-4
0
0
0
0
1
x3
0
1
1
1
0
0
12
2
x4
0
1
-2
0
1
0
6
3
x5
0
0
1
0
0
1
8
Solusi
Step 2b: Pilih sebuah variabel basis untuk meninggalkan basis Pilihlah variabel basis yg punya rasio paling kecil pd pembagian solusi terhadap koefisien positif dari variabel non-basis yg akan masuk
Var Pers. Basis
x1 -6
x2 -4
x3 0
x4 0
x5 0
Solusi 0
Ratio
0
z
z 1
1
x3
0
1
1
1
0
0
12
12/1
2
x4
0
1
-2
0
1
0
6
6/1
3
x5
0
0
1
0
0
1
8
Step 2c: Select a basic variable to leave the basis. Pilihlah variabel basis yg punya rasio paling kecil pd pembagian solusi terhadap koefisien positif dari variabel non-basis yg akan masuk
1x1 - 2x2
+ x4
= 6
Var Pers. Basis
z
x1
x2
x3
x4
x5
0
z
1
-6
-4
0
0
0
0
1
x3
0
1
1
1
0
0
12
12/1
2
x4
0
1
-2
0
1
0
6
6/1
3
x5
0
0
1
0
0
1
8
Solusi
Ratio
pivot point
16
Step 3e: Gunakan operasi baris untuk menentukan solusi basis yg baru.
Var Pers. Basis 0
z
z 1
1
x3
0
1
1
1
0
0
12
2
x4
0
1
-2
0
1
0
6
3
x5
0
0
1
0
0
1
8
z
x1
x2
x3
x4
x5
Solusi
1
0
-16
0
6
0
36
0
0
3
1
-1
0
6
0
1
-2
0
1
0
6
0
0
1
0
0
1
8
Var Pers. Basis 0 1 2 3
x1 -6
x2 -4
x3 0
x4 0
x5 0
Solusi 0
z x3 x1 x5
Max z = 6x1 + 4x2
x2
Subj. to:
12
8
x1 + x2 <= 12 x1 -2x2 <= 6 x2 <= 8
(4,8)
z
z
(10,2)
6 -3
12
x1
Iterasi selanjutnya
z = 6x1 + 4x2
Sekarang kamu ambil lagi variabel baru yang akan masuk basis !
Var Pers. Basis
z
x1
x2
x3
x4
x5
Solusi
0
z
1
0
-16
0
6
0
36
1
x3
0
0
3
1
-1
0
6
2
x1
0
1
-2
0
1
0
6
3
x5
0
0
1
0
0
1
8
19
Iterasi selanjutnya z = 6x1 + 4x2 Pilihlah variabel non-basis yg punya nilai negatif terbesar.
Var Pers. Basis 0
z
z 1
x1 0
x2 -16
x3 0
x4 6
x5 0
Solusi 36
1
x3
0
0
3
1
-1
0
6
2
x1
0
1
-2
0
1
0
6
3
x5
0
0
1
0
0
1
8
Iterasi selanjutnya
z = 6x1 + 4x2
Tentukan rasio minimum
Var Pers. Basis
z
x1
x2
x3
x4
x5
0
z
0
0
-16
0
6
0
6
1
x3
0
0
3
1
-1
0
6
2
x1
0
1
-2
0
1
0
6
3
x5
0
0
1
0
0
1
8
Solusi
Ratio
6/3
8/1
Iterasi selanjutnya
z = 6x1 + 4x2 Find minimum ratio
Var Pers. Basis
z
x1
x2
x3
x4
x5
0
z
1
0
-16
0
6
0
36
1
x3
0
0
3
1
-1
0
6
2
x1
0
1
-2
0
1
0
6
3
x5
0
0
1
0
0
1
8
Pivot point
Solusi
Ratio
6/3
8/1
Iterasi selanjutnya
Var Pers. Basis
z
x1
x2
x3
x4
x5
0
z
1
0
-16
0
6
0
36
1
x3
0
0
3
1
-1
0
6
2
x1
0
1
-2
0
1
0
6
3
x5
0
0
1
0
0
1
8
z
x1
x2
x3
x4
x5
1
0
0
16/3
2/3
0
68
0
0
1
1/3
-1/3
0
2
0
1
0
2/3
1/3
0
10
0
0
0
-1/3
1/3
1
6
Var Pers. Basis 0 1 2 3
Solusi
Solusi
z x2 x1 x5
Iterasi selanjutnya
Var Pers. Basis 0
z
1
x2
2 3
z
x1
x2
x3
x4
x5
Solusi
1
0
0
16/3
2/3
0
68
0
0
1
1/3
-1/3
0
2
0
1
0
2/3
1/3
0
10
0
0
0
-1/3
1/3
1
6
x1 x5
Ini lho... Gambaran optimalmya…
Max z = 6x1 + 4x2
Subj. to: x1 + x2 <= 12 x1 -2x2 <= 6 x2 <= 8
x2
12
8
(4,8) Pd x1 = 10 & x2 = 2, nilai optimalnya adalah 68
(10,2)
6 -3
12
x1
25
