Simplex Method
Prof. Ir. Suparno, MSIE., Ph. D
CONDITION FOR EXISTENCE OF THE INVERSE
CALCULATION OF THE INVERSE
Mencari matriks Invers
2 1 1 1 0 0
AI -1 2 1 0 1 0
1 -1 2 0 0 1
Baris 1 2 1 1 1 0 0
Baris 2 -1 2 1 0 1 0
Baris 3 1 -1 2 0 0 1
2 1
Kolom 1 -1 Akan diubah menjadi 0
1 0
Baris1 dibagi dengan 2 ; hasilnya sebagai berikut:
1 1/2 1/2 1/2 0 0
Kemudian dilanjutkan dengan menghitung baris ke 2 (baru) dan baris ke 3 (baru)
Bisa memakai formula berikut:
Baris 2 baru = baris 2 lama ditambah dengan 1 X baris 1 baru. Hasilnya berikut ini.
1 1/2 1/2 1/2 0 0
0 5/2 3/2 1/2 1 0
Baris 3 baru = baris 3 lama dikurangi dengan 1 X baris 1 baru. Hasilnya berikut ini.
1 1/2 1/2 1/2 0 0
0 5/2 3/2 1/2 1 0
0 -3/2 3/2 -1/2 0 1
Kolom 1 sudah sesuai dengan yang kita inginkan. Selanjutnya akan kita ubah kolom 2
1./2 0
Kolom 2 saat ini: 5/2 Akan diubah menjadi 1
-3/2 0
Kembali ke hasil akhir perhitungan sebelumnya
1 1/2 1/2 1/2 0 0
0 5/2 3/2 1/2 1 0
0 -3/2 3/2 -1/2 0 1
Baris 2 baru = baris 2 lama dibagi 5/2. hasilnya sebagai berikut:
0 1 3/5 1/5 2/5 0
Kemudian dilanjutkan dengan menghitung baris ke 1 (baru) dan baris ke 3 (baru)
Baris 1 baru = baris 1 lama dikurangi dengan 1./2 X baris 2 baru. Hasilnya berikut ini.
1 0 1./5 2/5 -1/5 0
0 1 3/5 1/5 2/5 0
Baris 3 baru = baris 3 lama ditambah dengan 3/2 X baris 2 baru. Hasilnya berikut ini.
1 0 1./5 2/5 -1/5 0
0 1 3/5 1/5 2/5 0
0 0 12/5 -1/5 3/5 1
Terakhir mengubah kolom 3
1./5 0
Kolom 3 saat ini: 3/5 Akan diubah menjadi 0
12/5 1
1 0 1./5 2/5 -1/5 0
0 1 3/5 1/5 2/5 0
0 0 12/5 -1/5 3/5 1
Baris 3 baru = baris 3 lama dibagi 12/5. hasilnya sebagai berikut:
0 0 1 -1/12 3/12 5/12
Saudara lanjutkan untuk menghitung baris 1 baru dan baris 2 baru
Perhitungan matriks invers akan menjadi dasar yang penting dari metode simpleks
3.2 BASIC FEASIBLE SOLUTIONS
In this section we introduce basic feasible solutions and show that they
correspond to extreme points. This characterization will enable us to algebraically
describe the simplex method.
Definition (Basic Feasible Solutions)
Problem linear programming dapat
dituliskan dalam bentuk matriks dan
vector seperti di kana ini
3.3 KEY TO THE SIMPLEX METHOD
The key to the simplex method lies in recognizing the optimality of a
given extreme point solution based on local considerations without
having to (globally) enumerate all extreme points or basic feasible
solutions. Consider the following linear programming problem:
Ubah ke dalam bentuk standard dengan menambahkan slack variable X4,
X5, dan X6.
X1 X2 X3 X4 X5 X6
1 1 2 1 0 0
A = 1
-1
1
1
-1
1
0
0
1
0
0
1
1 0 0 1 1 2
B = 0 1 0 N = 1 1 -1
0 0 1 -1 1 1
Variable yang membentuk matriks identitas adalah X4, X5, X6. maka
sementara ini tersebut merupakan variable basis (variable yang basis yang
mempunyai nilai tertentu. Misalnya pada contoh ini: nilai X4 = 9; X5 = 2 dan
X6 = 4. pada iterasi ini nilai fungsi tujuan (RHS) = 0 (initial objective value)
Semua variable dan parameter akan dimasukkan dalam tabel simpleks,
maka akan diperoleh tabel berikut ini:
Isinya baris ke nol adalah Zj - Cj
Z1 – C1= 1 Z3 – C3 = 4
Baris 0 𝜃 Pada setiap iterasi akan dicek,
bila semua Zj – Cj ≤ 0, maka
9/2
Baris 1 solusi saat ini sudah optimal.
Baris 2 -- Kalau masih ada yang positip,
pilih positip terbesar.
Baris 3 4/1
Diatas ini adalah tabel dari Iterasi 1 X6 ------- digantikan oleh X3
Ditabel iterasi 1: Z3 – C3 = 4 , maka dipilih X3 sebagai entering variable. Artinya
variable X3 akan menggantikan salah satu varibel basis.
Yang dihitung pertama kali adalah baris yang ada pivot elemennya, baris ke 3,
hasilnya sbb.: (baris 3 baru = baris 3 lama dibagi dengan 1)
Z X1 X2 X3 X4 X5 X6 NRK
1 Ө
Z
X4 0
X5 0
X3 0 -1 1 1 0 0 1 4
Selanjutnya menghitung baris 1 baru = baris 1 lama dikurangi 2X baris 3 baru. Baris 2
baru = baris 2 lama ditambah 1X baris 3 baru. Hasilnya sebagai berikut:
Z X1 X2 X3 X4 X5 X6 NRK
1 Ө
Z
X4 0 3 -1 0 1 0 -2 1
X5 0 0 2 0 0 1 1 6
X3 0 -1 1 1 0 0 1 4
Yang terakhir menghitung baris ke 0; Zj – Cj untuk baris ke harus sama dengan 0.
sekarang Z3 – C3 = 4, sehingga rumusnya --- baris 0 baru = baris 0 lama dikurangi
dengan 4X baris 3. hasilnya sbb.
Iterasi 2 Z X1 X2 X3 X4 X5 X6 NRK
1 3 -5 0 0 0 -4 -16 Ө
Z
X4 0 3 -1 0 1 0 -2 1
X5 0 0 2 0 0 1 1 6
X3 0 -1 1 1 0 0 1 4
Demikian seterusnya sehingga diperoleh tabel iterasi-iterasi berikutnya.
Iterasi 3
Pekerjaan rumah. Dikumpulkan paling lambat hari Kamis tanggal 8
Oktober 2020 jam. 24:00 Dari buku Bazaraa
[3.25] Solve the following problem by the simplex method:
Untuk problem LP maximize, kondisi solution optimal tercapai bila Zj – Cj ≥ 0
untuk semua non-basic variables