Metode Simpleks Dengan Tabel Tabel metode simpleks Tabel metode simpleks bentuk standar
Pendahuluan Pada pembahasan ini akan dibahas mekanisme metode
simpleks yang diformulasikan dengan sebuah tabel. Tabel tersebut akan merepresentasikan setiap corner point dan
nilai fungsi tujuan yang bersangkutan Dengan menggunakan tabel: Dapat diselesaikan program linier skala kecil tanpa
menggunakan alat bantu komputer
Algoritma metode simpleks Fase pertama (1) : tentukan titik intial yang merupakan sebuah basic
feasible solution.
Jika ada, iterasi dilanjutkan. Jika tidak ada, maka model program linier dikatakan infeasibel. Iterasi
dihentikan.
Fase kedua (2): iterasi sampai keadaan untuk menghentikan iterasi
ditemui (keadaan optimum tercapai)
2.1: apakah sudah optimum? Jika masih terdapat entering basic variable, maka keadaan belum optimum dan iterasi dilanjutkan. Jika tidak ada entering basic variable, iterasi dihentikan dengan penyelesaian di titik basic feasible solution tersebut sebagai titik optimum dengan nilai fungsi tujuan di titik tersebut sebagai nilai optimumnya. 2.2: Tentukan entering basic variable Tentukan nonbasic variable yang memberikan pengaruh terbesar pada perubahan fungis tujuan 2.3: Tentukan leaving basic variable menggunakan minimum ratio test (MRT) 2.4: Update persamaan-persamaan, untuk berpindah ke basic feasibel solution
yang baru. 2.5: Kembali ke langkah 2.1.
Table Simpleks (1) 4 3
4
2
x1
Basic Var
Eqn. no.
Z
X1
X2
s1
s2
s3
RHS
MRT
Z s1 s2 s3
0 1 2 3
1 0 0 0
-15 1 0 1
-10 0 1 1
0 1 0 0
0 0 1 0
0 0 0 1
0 2 3 4
never
Table Simpleks (2) Table di atas merupakan tabel untuk basic feasible solution di
titik origin, yaitu (0,0,2,3,4). Kolom basic variable, berisi basic variable yang terjadi bersesuaian dengan masing-masing persamaan fungsi kendala. Kolom kedua, No. Eq., merupakan label untuk masingmasing fungsi kendala Label 0 untuk fungsi tujuan, dan 1 sampai 3 untuk fungsi-fungsi
kendala.
Kolom RHS, berisi nilai-nilai RHS untuk masing-masing
fungsi kendala. Kolom MRT, diisi dengan hasil perhitungan MRT dan akan dilakukan pada saat memulia metode simpleks.
Proper form table Sebelum iterasi metode simpleks dijalankan, tabel yang
dihasilkan harus dalam bentuk proper table. Proper table memiliki karakteristik: Memiliki sebuah basic variable untuk setiap persamaan
Koefisien basic variable adalah 1, dan koefisien di atas dan di
bawah basic variable dalam kolom yang sama adalah 0. Fungsi tujuan, Z, selalu dianggap sebagai basic variable
(persamaan no. 0).
Fungsi Proper form table Jika tabel dalam bentuk proper table, nilai untuk semua
variable dan nilai fungsi tujuan dapat langsung dibaca dari tabel tersebut, Hal ini disebabkan karena hanya ada satu basic variable di setiap
baris dan memiliki koefisien 1. Variable-variable yang lain dalam satu baris merupakan
nonbasic variable, Dengan demikian, nilai-nilai suatu variable dapat dibaca pada
kolom RHS.
2.1. Apakah sudah optimal? Keadaan optimum tercapai jika tidak ada lagi entering basic
variable, Hal ini dapat diketahui dengan memperhatikan baris fungsi
tujuan. Jika pada baris fungsi tujuan tidak terdapat nilai yang negatif, maka keadaan sudah optimum. Jika pada baris fungsi tujuan masih terdapat nilai yang negatif, maka keadaan belum optimum dan metode simpleks dilanjutkan.
2.2. Menentukan entering basic variable (1) Entering basic variable merupakan nonbasic variable di baris
fungsi tujuan (pers. No. 0) yang bernilai paling negatif. Pilihlah variable di baris fungsi tujuan yang paling negatif sebagai
entering basic variable Dalam contoh model linier tersebut, x1 memiliki koefisien -15 sedangkan x2 memiliki koefisen -10. Dengan demikian, x1 merupakan entering basic variable. Kolom untuk entering basic variable disebut sebagai pivot column.
2.2. Menentukan entering basic variable (2) Basic Var
Eqn. no.
Z
X1
X2
s1
s2
s3
RHS
MRT
Z s1 s2 s3
0 1 2 3
1 0 0 0
-15 1 0 1
-10 0 1 1
0 1 0 0
0 0 1 0
0 0 0 1
0 2 3 4
never
2.3. Menentukan leaving basic variable (1) Minimum ratio test digunakan untuk menentukan leaving
basic variable. Nilai MRT ditentukan dengan cara: (RHS)/(koefisien entering basic variable)
Terdapat dua keadaan khusus untuk nilai MRT: Jika koefisien entering basic variable NOL, MRT diberi nilai
dengan no limit, Jika koefisien entering basic variable NEGATIF, MRT diberi nilai dengan no limit. Catatan: MRT tidak diterapkan pada fungsi tujuan.
2.3. Menentukan leaving basic variable (2) Leaving basic variable adalah pada baris yang memiliki MRT
paling kecil Baris leaving basic variable disebut dengan pivot row. Basic Var
Eqn. no.
Z
X1
X2
s1
s2
s3
RHS
MRT
Z
0
1
-15
-10
0
0
0
0
Never
s1
1
0
1
0
1
0
0
2
2
s2
2
0
0
1
0
1
0
3
No limit
s3
3
0
1
1
0
0
1
4
4
2.4. Meng-udpate table (1) Setelah entering dan leaving basic variable ditentukan, langkah
selanjutnya adalah meng-update nilai-nilai yang ada di dalam tabel, dengan cara: 2.4.1: pada kolom basic variable, ganti leaving basic variable
dengan sebagai pivot row dengan entering basic variable. 2.4.2: element table di mana pivot column dan pivot row berpotongan disebut dengan pivot element, Nilai pivot element harus sama dengan 1.
2.4.3: semua elemen pivot column dieleminasi kecuali pivot
element. Hal ini dilakukan dengan operasi eleminiasi gauss, (new row k)=(row k)-(pivot column coefficient in row k) x
(pivot row)
2.4. Meng-udpate table (2) Hasil proses meng-update table adalah sebagai berikut: Basic Var
Eqn. no.
Z
X1
X2
s1
s2
s3
RHS
MRT
Z x1 s2 s3
0 1 2 3
1 0 0 0
0 1 0 0
-10 0 1 1
15 1 0 -1
0 0 1 0
0 0 0 1
30 2 3 2
never
Table di atas menghasilkan basic feasible solution kedua (atau
sebagai corner point jika dari sudut pandang secara grafik), yaitu: Basic feasible solution yang baru: (2,0,0,3,2) Dengan nilai Z sebesar: 30
Penyelesaian program linier (1) Dari tabel terakhir di atas, masih terdapat koefisien yang
negatif di baris fungsi tujuan (pers. No. 0), dengan demikian keadaan belum optimum. Jadi, proses penyelesaian masih terus dilakukan untuk iterasi selanjutnya, sebagai berikut: Langkah 2.2: x2 sebagai entering basic variable Langkah 2.3: hasil dari MRT diperoleh s3 sebagai leaving basic
variable Langkah 2.4: meng-update table dalam bentuk proper form
Penyelesaian program linier (2) Entering basic variable: x2 Leaving basic variable: s3 Basic Var
Eqn. no.
Z
X1
X2
s1
s2
s3
RHS
MRT
Z
0
1
0
-10
15
0
0
30
never
x1
1
0
1
0
1
0
0
2
No limit
s2
2
0
0
1
0
1
0
3
3
s3
3
0
0
1
-1
0
1
2
2
Tabel dalam keadaan optimum Basic Var
Eqn. no.
Z
X1
X2
s1
s2
s3
RHS
MRT
Z
0
1
0
0
5
0
10
50
never
x1
1
0
1
0
1
0
0
2
s2
2
0
0
0
1
1
-1
1
x2
3
0
0
1
-1
0
1
2
Tidak terdapat koefisien negatif di baris fungsi tujuan
Penyelesaiaanya adalah: Di titik (2,2,0,1,0) Dengan nilai Z = 50
Keadaan khusus dalam manipulasi table (1) Entering basic variable
memiliki nilai yang sama, Contoh: Zmaks =
15x1+15x2 Untuk menyelesaikan masalah ini, entering basic variable dipilih secara acak.
Keadaan khusus dalam manipulasi table (2) Leaving basic variable memiliki nilai MRT yang sama, Pilihlah leaving basic variable secara acak
Untuk MRT semua bernilai no limit, berarti bahwa
pergerakana entering basic variable tidak terbatas, Dengan demikian, model program linier tersebut merupakan
model unbounded Pada keadaan optimum, jika terdapat nonbasic variabel bernilai
NOL di baris fungsi tujuan, maka: Pemilihan nonbasic variable sebagai entering basic variable akan
menghasilkan kenaikan nilai Z dengan rate NOL. Tidak ada efek ke pada perubahan nilai Z, dan menghasilkan nilai Z yang sama pada basic feasible solution yang berbeda.
