Metode Dua Fase

-Metode Simpleks-
-Linear Programming-
Penyelesaian Program Linear

Semua persamaan pada

Metode Simpleks
fungsi kendala
Sederhana/Biasa
bertanda ≤

Program Linear
Metode Big M
Terdapat minimal satu
persamaan pada fungsi
kendala yang
bertanda ≥ atau =
Metode Dua Phase
Pendahuluan
• Metode Dua Fase digunakan pada variable basis awal yang terdiri dari variabel
buatan.
• Pada metode ini proses optimasi dilakukan dalam dua tahap.
• Tahap pertama merupakan proses optimasi variabel buatan,
• Tahap kedua adalah proses optimasi variabel keputusan
• Karena variabel buatan sebenarnya tidak ada (hanya ada di atas kertas), maka
tahap pertama dilakukan untuk memaksa variabel buata bernilai 0
Fase 1
• Menentukan apakah permasalahan mempunyai solusi fisible atau tidak dengan
cara meminimasikan variabel artificial.
• Fungsi tujuan diganti dengan meminimumkan jumlah variabel artifisialnya.
• Jika nilai yang diperoleh pada fungsi tujuan baru mempunyai harga nol/negatif,
berarti solusi fisible (persoalan fisible) & dapat dilanjutkan ke phase 2. (r=0)
• Jika mempunyai nilai positif persoalan tidak fisibel sehingga pemecahan masalah
dihentikan untuk phasa pertama ini.(r>0)
• Berlaku bagi kedua fungsi tujuan baik maksimasi maupun minimasi
Fase 2
• Mengembalikan fungsi tujuan ke fungsi tujuan semula dengan fungsi pembatas
yang baru untuk pemecahan masalah selanjutnya diselesaikan dengan metode
simpleks biasa.
• Fungsi pembatas baru, diperoleh dari tabel terakhir dari perhitungan phasa 1
dengan menghilangkan variabel artificial yang sudah minimum.
Contoh kasus Maksimasi
- Metode Dua Fase-
Contoh Kasus Maksimasi
• Bentuk Umum Ubah ke bentuk Standar/Kanonik
𝑍𝑚𝑎𝑥 = 3𝑋1 + 5𝑋2 Fungsi Kendala :
𝑋1 + 𝑆1 = 4
Fungsi Kendala Definisikan nilai A3
2𝑋2 + 𝑆2 = 12
𝑋1 ≤ 4 3𝑋1 + 2𝑋2 + 𝐴3 = 18 𝐴3 = 18 − 3𝑋1 − 2𝑋2
2𝑋2 ≤ 12
𝑋1 , 𝑋2 . 𝑆1 , 𝑆2 , 𝐴3 ≥ 0
3𝑋1 + 2𝑋2 = 18
𝑋1 , 𝑋2 ≥ 0 Fungsi Tujuan :
𝑍𝑚𝑎𝑥 = 3𝑋1 + 5𝑋2 + 0𝑆1 + 0𝑆2
Contoh Kasus Maksimasi
Fase 1 : Fungsi tujuan meminimumkan variable artifisial
Fungsi Tujuan : Fungsi Tujuan :
𝑍𝑚𝑎𝑥 = 3𝑋1 + 5𝑋2 + 0𝑆1 + 0𝑆2 𝑟𝑚𝑖𝑛 = 𝐴3
𝑟𝑚𝑖𝑛 = 18 − 3𝑋1 − 2𝑋2
Fungsi Kendala :
𝑟 + 3𝑋1 + 2𝑋2 = 18
𝑋1 + 𝑆1 = 4
2𝑋2 + 𝑆2 = 12
3𝑋1 + 2𝑋2 + 𝐴3 = 18
𝑋1 , 𝑋2 . 𝑆1 , 𝑆2 , 𝐴3 ≥ 0

𝐴3 = 18 − 3𝑋1 − 2𝑋2
Contoh Kasus Maksimasi
Fase 1 : Membuat table simpleks
Fungsi Tujuan : Fungsi Tujuan :
𝑍𝑚𝑎𝑥 = 3𝑋1 + 5𝑋2 + 0𝑆1 + 0𝑆2 𝑟 + 3𝑋1 + 2𝑋2 = 18
Fungsi Kendala :
𝑋1 + 𝑆1 = 4
2𝑋2 + 𝑆2 = 12
Var
3𝑋1 + 2𝑋2 + 𝐴3 = 18 r X1 X2 S1 S2 A3 RHS Rasio
Basis
𝑋1 , 𝑋2 . 𝑆1 , 𝑆2 , 𝐴3 ≥ 0 r 1 3 2 0 0 0 18
Kendala 1 S1 0 1 0 1 0 0 4
Kendala 2 S2 0 0 2 0 1 0 12
Kendala 3 A3 0 3 2 0 0 1 18
Contoh Kasus Maksimasi
Fase 1 : Periksa ke-optimalan table simpleks [ Iterasi-0 ]

Var Apakah table simpleks sudah

r X1 X2 S1 S2 A3 RHS Rasio
Basis optimal? (baris r sudah tidak ada
r 1 3 2 0 0 0 18 nilai positif?)
S1 0 1 0 1 0 0 4
Masih ada baris r yang bernilai
S2 0 0 2 0 1 0 12 positif. Oleh karena itu lakukan
A3 0 3 2 0 0 1 18 iterasi yang berikutnya
Contoh Kasus Maksimasi
Fase 1 : Identifikasi kolom kunci [ Iterasi-1]

Var Karena kasus minimasi (rmin)

r X1 X2 S1 S2 A3 RHS Rasio
Basis maka kolom kunci adalah nilai
r 1 3 2 0 0 0 18 positif tertinggi
S1 0 1 0 1 0 0 4 Jika terdapat dua nilai tertinggi,
S2 0 0 2 0 1 0 12
maka pilih salah satu

A3 0 3 2 0 0 1 18

Entering
variable (EV)
 Contoh Kasus Maksimasi
Fase 1 : Identifikasi baris kunci [ Iterasi-1 ]

Var Baris kunci adalah baris yang

r X1 X2 S1 S2 A3 RHS Rasio
Basis memiliki nilai rasio positif
r 1 3 2 0 0 0 18 - terkecil
S1 0 1 0 1 0 0 4 4/1=4 𝑅𝐻𝑆
𝑅𝑎𝑠𝑖𝑜 =
S2 0 0 2 0 1 0 12 12/0=- 𝑘𝑜𝑙𝑜𝑚 𝑘𝑢𝑛𝑐𝑖
A3 0 3 2 0 0 1 18 18/3=6 Jika kolom kunci bernilai 0 atau
negatif, bisa diabaikan
Leaving Entering
variable (LV) variable (EV)
Jika terdapat nilai rasio terkecil
yang sama, pilih salah satu
 Contoh Kasus Maksimasi
Fase 1 : Cari nilai / angka kunci [ Iterasi-1 ]

Var Nilai yang terdapat pada

r X1 X2 S1 S2 A3 RHS Rasio
Basis persilangan / pertemuan kolom
r 1 3 2 0 0 0 18 - kunci dan baris kunci
S1 0 1 0 1 0 0 4 4/1=4
S2 0 0 2 0 1 0 12 12/0=-
A3 0 3 2 0 0 1 18 18/3=6
Nilai kunci yang didapatkan = 1
Leaving Entering
variable (LV) variable (EV)
 Contoh Kasus Maksimasi
Fase 1 : Mengubah nilai baris kunci [ Iterasi-1 ]

Var Var
r X1 X2 S1 S2 A3 RHS Rasio r X1 X2 S1 S2 A3 RHS Rasio
Basis Basis
r 1 3 2 0 0 0 18 - r
S1 0 1 0 1 0 0 4 4/1=4 X1 0 1 0 1 0 0 4
S2 0 0 2 0 1 0 12 12/0=- S2
A3 0 3 2 0 0 1 18 18/3=6 A3

• Variabel basis pada baris kunci diganti dengan Nilai kunci yang didapatkan = 1
variable pada kolom kunci.
• Membagi masing-masing nilai baris dengan nilai
kunci
 Contoh Kasus Maksimasi
Fase 1 : Mengubah nilai baris kunci [ Iterasi-1 ]

Var Var
r X1 X2 S1 S2 A3 RHS Rasio r X1 X2 S1 S2 A3 RHS Rasio
Basis Basis
r 1 3 2 0 0 0 18 - r
S1 0 1 0 1 0 0 4 4/1=4 X1 0 1 0 1 0 0 4
S2 0 0 2 0 1 0 12 12/0=- S2
A3 0 3 2 0 0 1 18 18/3=6 A3

• Variabel basis pada baris kunci diganti dengan Nilai kunci yang didapatkan = 1
variable pada kolom kunci.
• Membagi masing-masing nilai baris dengan nilai
kunci
 Contoh Kasus Maksimasi
Fase 1 : Mengubah nilai baris lain (selain baris kunci) [ Iterasi-1 ]

Var Var
r X1 X2 S1 S2 A3 RHS Rasio r X1 X2 S1 S2 A3 RHS Rasio
Basis Basis
r 1 3 2 0 0 0 18 - r 1 0 2 -3 0 0 6
S1 0 1 0 1 0 0 4 4/1=4 X1 0 1 0 1 0 0 4
S2 0 0 2 0 1 0 12 12/0=- S2 0 0 2 0 1 0 12
A3 0 3 2 0 0 1 18 18/3=6 A3 0 0 2 -3 0 1 6

Baris Baru = Lakukan untuk setiap barisnya

Nilai lama – (nilai baru basis kunci × nilai kolom kunci)
Contoh Kasus Maksimasi
Fase 1 : Periksa ke-optimalan table simpleks [ Iterasi-1 ]

Var Karena kasus minimasi (rmin), periksa kembali

r X1 X2 S1 S2 A3 RHS Rasio
Basis apakah masih terdapat nilai positif pada baris r.
r 1 0 2 -3 0 0 6
Jika masih terdapat nilai positif, maka lakukan
X1 0 1 0 1 0 0 4 iterasi kembali sampai baris r tidak ada yang
S2 0 0 2 0 1 0 12 bernilai positif

A3 0 0 2 -3 0 1 6

Apakah table simpleks sudah optimal? (baris r sudah tidak ada nilai positif?)
Masih ada baris r yang bernilai positif. Oleh karena itu lakukan iterasi yang berikutnya
Contoh Kasus Maksimasi
Fase 1 : Pilih kolom, baris dan nilai kunci [ Iterasi-2 ]

Var
r X1 X2 S1 S2 A3 RHS Rasio
Basis
r 1 0 2 -3 0 0 6 -
X1 0 1 0 1 0 0 4 -
S2 0 0 2 0 1 0 12 12/2=6
A3 0 0 2 -3 0 1 6 6/2=3

Leaving Entering
variable (LV) variable (EV)
Contoh Kasus Maksimasi
Fase 1 : Mengubah nilai baris kunci [ Iterasi-2 ]

Var Var
r X1 X2 S1 S2 A3 RHS Rasio r X1 X2 S1 S2 A3 RHS Rasio
Basis Basis
r 1 0 2 -3 0 0 6 - r 1 0 2 -3 0 0 6
X1 0 1 0 1 0 0 4 - X1 0 1 0 1 0 0 4
S2 0 0 2 0 1 0 12 12/2=6 S2 0 0 2 0 1 0 12
A3 0 0 2 -3 0 1 6 6/2=3 X3 0 0 1 -3/2 0 1/2 3
Contoh Kasus Maksimasi
Fase 1 : Mengubah nilai baris lain (selain baris kunci) [ Iterasi-2 ]

Var Var
r X1 X2 S1 S2 A3 RHS Rasio r X1 X2 S1 S2 A3 RHS Rasio
Basis Basis
r 1 0 2 -3 0 0 6 - r 1 0 0 0 0 -1 0
X1 0 1 0 1 0 0 4 - X1 0 1 0 1 0 0 4
S2 0 0 2 0 1 0 12 12/2=6 S2 0 0 0 3 1 -1 6
A3 0 0 2 -3 0 1 6 6/2=3 X3 0 0 1 -3/2 0 1/2 3
Contoh Kasus Maksimasi
Fase 1 : Periksa ke-optimalan table simpleks [ Iterasi-2 ]

Var Karena kasus minimasi (rmin), periksa kembali

r X1 X2 S1 S2 A3 RHS apakah masih terdapat nilai positif pada baris r.
Basis
r 1 0 0 0 0 -1 0 Jika masih terdapat nilai positif, maka lakukan
X1 0 1 0 1 0 0 4 iterasi sampai baris r tidak ada yang bernilai
positif
S2 0 0 0 3 1 -1 6
X2 0 0 1 -3/2 0 1/2 3

Apakah table simpleks sudah optimal? (baris r sudah tidak ada nilai positif?)
Dalam kasus ini r sudah tidak ada lagi yang bernilai positif, dan r ≤ 0, maka bisa dilanjutkan ke fase 2.
Jika terjadi pengulangan hasil, dan r bernilai positif, maka berhenti di fase 1 saja, dan bisa ditarik
kesimpulan bahwa tidak ada nilai yang optimal.
Contoh Kasus Maksimasi
Fase 2 : Menentukan Fungsi kendala berdasarkan table simpleks pada Fase 1
Fungsi Tujuan Awal:
Var
r X1 X2 S1 S2 A3 RHS 𝑍𝑚𝑎𝑥 = 3𝑋1 + 5𝑋2
Basis
r 1 0 0 0 0 -1 0 Fungsi Kendala Baru: Definisikan nilai X1 dan X2
X1 0 1 0 1 0 0 4 𝑋1 + 𝑆1 = 4 𝑋1 = 4 − 𝑆1
3𝑆1 + 𝑆2 = 6
S2 0 0 0 3 1 -1 6
3 3
X2 0 0 1 -3/2 0 1/2 3 𝑋2 − 𝑆1 = 3 𝑋2 = 3 + 𝑆1
2 2
Contoh Kasus Maksimasi
Fase 2 : Menentukan Fungsi Tujuan baru
Fungsi Tujuan Awal: Fungsi Tujuan Baru:
𝑍𝑚𝑎𝑥 = 3𝑋1 + 5𝑋2 𝑍𝑚𝑎𝑥 = 3𝑋1 + 5𝑋2
3
Fungsi Kendala Baru: 𝑍𝑚𝑎𝑥 = 3 4 − 𝑆1 + 5 3 + 𝑆1
2
𝑋1 + 𝑆1 = 4 𝑋1 = 4 − 𝑆1 15
𝑍𝑚𝑎𝑥 = 12 − 3𝑆1 + 15 + 𝑆1
3𝑆1 + 𝑆2 = 6 2
9
3 3 𝑍𝑚𝑎𝑥 = 27 + 𝑆1
𝑋2 − 𝑆1 = 3 𝑋2 = 3 + 𝑆1 2
2 2 9
𝑍 − 𝑆1 = 27 Fungsi Tujuan baru
2
Contoh Kasus Maksimasi
Fase 2 : Membuat table simpleks
Fungsi Tujuan :
9 Var
𝑍𝑚𝑎𝑥 − 𝑆1 = 27 Z X1 X2 S1 S2 RHS
2 Basis
Fungsi Kendala : Z 1 0 0 -9/2 0 27
𝑋1 + 𝑆1 = 4 Kendala 1 X1 0 1 0 1 0 4
3𝑆1 + 𝑆2 = 6 Kendala 2 S2 0 0 0 3 1 6
3
𝑋2 − 𝑆1 = 3 Kendala 3 X2 0 0 1 -3/2 0 3
2
Contoh Kasus Maksimasi
Fase 2 : Lakukan iterasi
Iterasi 0 Iterasi 1

Var Var
Z X1 X2 S1 S2 RHS Rasio Z X1 X2 S1 S2 RHS Rasio
Basis Basis
Z 1 0 0 -9/2 0 27 - Z 1 0 0 0 3/2 36
X1 0 1 0 1 0 4 4/1=4 X1 0 1 0 0 -1/3 2
S2 0 0 0 3 1 6 6/3=2 S1 0 0 0 1 1/3 2
X2 0 0 1 -3/2 0 3 - X2 0 0 1 0 1/2 6
Contoh Kasus Maksimasi
Fase 2 : Periksa ke-optimalan
Iterasi 1

Var Karena kasus maksimasi (Zmax), periksa kembali apakah masih

Z X1 X2 S1 S2 RHS terdapat nilai negatif pada baris Z.
Basis
Z 1 0 0 0 3/2 36 Jika masih terdapat nilai negatif, maka lakukan iterasi sampai
X1 0 1 0 0 -1/3 2
baris Z tidak ada yang bernilai negatif

S1 0 0 0 1 1/3 2
Apakah table simpleks sudah optimal? (baris Z sudah tidak ada
X2 0 0 1 0 1/2 6 nilai negatif?)

Dalam kasus ini Z sudah tidak ada lagi yang bernilai negatif,
maka bisa ditarik kesimpulan
Contoh Kasus Maksimasi
Kesimpulan

Var
Z X1 X2 S1 S2 RHS Z = 36
Basis
X1 = 2
Z 1 0 0 0 3/2 36
X2 = 6
X1 0 1 0 0 -1/3 2 S1 = 2
S1 0 0 0 1 1/3 2
X2 0 0 1 0 1/2 6

Kesimpulan : Agar memberikan keuntungan yang maksimal, maka X1 diproduksi sebanyak 2 unit dan X2 diproduksi
6 unit. Sehingga menghasilkan nilai Z sebesar = 36

Sumber daya pada kendala pertama terdapat sisa sebesar 2 unit. Sumber daya pada kendala kedua habis terpakai
Contoh kasus Minimasi
- Metode Dua Fase-
Contoh Kasus Minimasi
• Bentuk Umum Ubah ke bentuk Standar/Kanonik
𝑍𝑚𝑖𝑛 = 4𝑋1 + 𝑋2

Fungsi Kendala Fungsi Kendala : Definisikan semua nilai A

3𝑋1 + 𝑋2 = 3 3𝑋1 + 𝑋2 + 𝐴1 = 3 𝐴1 = 3 − 3𝑋1 − 𝑋2
4𝑋1 + 3𝑋2 ≥ 6 4𝑋1 + 3𝑋2 − 𝑆2 + 𝐴2 = 6 𝐴2 = 6 − 4𝑋1 − 3𝑋2 + 𝑆2
𝑋1 + 2𝑋2 ≤ 4 𝑋1 + 2𝑋2 + 𝑆3 = 4
𝑋1 , 𝑋2 ≥ 0 𝑋1 , 𝑋2 . 𝑆2 , 𝑆3 , 𝐴1 , 𝐴2 ≥ 0
Contoh Kasus Minimasi
Fase 1 : Fungsi tujuan meminimumkan variable artifisial
Fungsi Tujuan : Fungsi Tujuan :
𝑍𝑚𝑖𝑛 = 4𝑋1 + 𝑋2 𝑟𝑚𝑖𝑛 = 𝐴1 + 𝐴2
𝑟𝑚𝑖𝑛 = 3 − 3𝑋1 − 𝑋2 + (6 − 4𝑋1 − 3𝑋2 + 𝑆2 )
Fungsi Kendala :
𝑟𝑚𝑖𝑛 = 9 − 7𝑋1 − 4𝑋2 + 𝑆2
3𝑋1 + 𝑋2 + 𝐴1 = 3
4𝑋1 + 3𝑋2 − 𝑆2 + 𝐴2 = 6
𝑟 + 7𝑋1 + 4𝑋2 − 𝑆2 = 9
𝑋1 + 2𝑋2 + 𝑆3 = 4
𝑋1 , 𝑋2 . 𝑆2 , 𝑆3 , 𝐴1 , 𝐴2 ≥ 0

𝐴1 = 3 − 3𝑋1 − 𝑋2
𝐴2 = 6 − 4𝑋1 − 3𝑋2 + 𝑆2
Contoh Kasus Minimasi
Fase 1 : Membuat table simpleks
Fungsi Tujuan : Fungsi Tujuan :
𝑍𝑚𝑖𝑛 = 4𝑋1 + 𝑋2 𝑟 + 7𝑋1 + 4𝑋2 − 𝑆2 = 9
Fungsi Kendala :
3𝑋1 + 𝑋2 + 𝐴1 = 3
Var
4𝑋1 + 3𝑋2 − 𝑆2 + 𝐴2 = 6 r X1 X2 S2 S3 A1 A2 RHS Rasio
Basis
𝑋1 + 2𝑋2 + 𝑆3 = 4
r 1 7 4 -1 0 0 0 9
𝑋1 , 𝑋2 . 𝑆2 , 𝑆3 , 𝐴1 , 𝐴2 ≥ 0 Kendala 1 A1 0 3 1 0 0 1 0 3
𝐴1 = 3 − 3𝑋1 − 𝑋2 Kendala 2 A2 0 4 3 -1 0 0 1 6
𝐴2 = 6 − 4𝑋1 − 3𝑋2 + 𝑆2 Kendala 3 S3 0 1 2 0 1 0 0 4
Contoh Kasus Minimasi
Fase 1 : Periksa ke-optimalan table simpleks [ Iterasi-0 ]

Var
r X1 X2 S2 S3 A1 A2 RHS Rasio Apakah table simpleks sudah
Basis optimal? (baris r sudah tidak ada
r 1 7 4 -1 0 0 0 9 nilai positif?)
A1 0 3 1 0 0 1 0 3
Masih ada baris r yang bernilai
A2 0 4 3 -1 0 0 1 6 positif. Oleh karena itu lakukan
S3 0 1 2 0 1 0 0 4 iterasi yang berikutnya
Contoh Kasus Minimasi
Fase 1 : Identifikasi kolom kunci [ Iterasi-1]

Var
r X1 X2 S2 S3 A1 A2 RHS Rasio Karena kasus minimasi (rmin)
Basis maka kolom kunci adalah nilai
r 1 7 4 -1 0 0 0 9 positif tertinggi
A1 0 3 1 0 0 1 0 3 Jika terdapat dua nilai tertinggi,
A2 0 4 3 -1 0 0 1 6 maka pilih salah satu
S3 0 1 2 0 1 0 0 4

Entering
variable (EV)
 Contoh Kasus Minimasi
Fase 1 : Identifikasi baris kunci [ Iterasi-1 ]

Var
r X1 X2 S2 S3 A1 A2 RHS Rasio Baris kunci adalah baris yang
Basis memiliki nilai rasio positif
r 1 7 4 -1 0 0 0 9 - terkecil
A1 0 3 1 0 0 1 0 3 1 𝑅𝐻𝑆
𝑅𝑎𝑠𝑖𝑜 =
A2 0 4 3 -1 0 0 1 6 6/4 𝑘𝑜𝑙𝑜𝑚 𝑘𝑢𝑛𝑐𝑖
S3 0 1 2 0 1 0 0 4 4 Jika kolom kunci bernilai 0 atau
negatif, bisa diabaikan
Leaving Entering
variable (LV) variable (EV)
Jika terdapat nilai rasio terkecil
yang sama, pilih salah satu
 Contoh Kasus Minimasi
Fase 1 : Cari nilai / angka kunci [ Iterasi-1 ]

Var
r X1 X2 S2 S3 A1 A2 RHS Rasio Nilai yang terdapat pada
Basis persilangan / pertemuan kolom
r 1 7 4 -1 0 0 0 9 - kunci dan baris kunci
A1 0 3 1 0 0 1 0 3 1
A2 0 4 3 -1 0 0 1 6 6/4
S3 0 1 2 0 1 0 0 4 4
Nilai kunci yang didapatkan = 3
Leaving Entering
variable (LV) variable (EV)
 Contoh Kasus Minimasi
Fase 1 : Mengubah nilai baris kunci [ Iterasi-1 ]

Var Var
r X1 X2 S2 S3 A1 A2 RHS Rasio r X1 X2 S2 S3 A1 A2 RHS Rasio
Basis Basis
r 1 7 4 -1 0 0 0 9 - r
A1 0 3 1 0 0 1 0 3 1 X1 0 1 1/3 0 0 1/3 0 1
A2 0 4 3 -1 0 0 1 6 6/4 A2
S3 0 1 2 0 1 0 0 4 4 S3

• Variabel basis pada baris kunci diganti dengan Nilai kunci yang didapatkan = 3
variable pada kolom kunci.
• Membagi masing-masing nilai baris dengan nilai
kunci
 Contoh Kasus Minimasi
Fase 1 : Mengubah nilai baris lain (selain baris kunci) [ Iterasi-1 ]

Var Var
r X1 X2 S2 S3 A1 A2 RHS Rasio r X1 X2 S2 S3 A1 A2 RHS Rasio
Basis Basis
r 1 7 4 -1 0 0 0 9 - r 1 0 5/3 -1 0 -7/3 0 2
A1 0 3 1 0 0 1 0 3 1 X1 0 1 1/3 0 0 1/3 0 1
A2 0 4 3 -1 0 0 1 6 6/4 A2 0 0 5/3 -1 0 -4/3 1 2
S3 0 1 2 0 1 0 0 4 4 S3 0 0 5/3 0 1 -1/3 0 3

Baris Baru = Lakukan untuk setiap barisnya

Nilai lama – (nilai baru basis kunci × nilai kolom kunci)
Contoh Kasus Minimasi
Fase 1 : Periksa ke-optimalan table simpleks [ Iterasi-1 ]

Var Karena kasus minimasi (rmin), periksa kembali

r X1 X2 S2 S3 A1 A2 RHS Rasio
Basis
apakah masih terdapat nilai positif pada baris r.
r 1 0 5/3 -1 0 -7/3 0 2
Jika masih terdapat nilai positif, maka lakukan
X1 0 1 1/3 0 0 1/3 0 1 iterasi kembali sampai baris r tidak ada yang
A2 0 0 5/3 -1 0 -4/3 1 2 bernilai positif
S3 0 0 5/3 0 1 -1/3 0 3

Apakah table simpleks sudah optimal? (baris r sudah tidak ada nilai positif?)
Masih ada baris r yang bernilai positif. Oleh karena itu lakukan iterasi yang berikutnya
Contoh Kasus Minimasi
Fase 1 : Pilih kolom, baris dan nilai kunci [ Iterasi-2 ]

Var
r X1 X2 S2 S3 A1 A2 RHS Rasio
Basis
r 1 0 5/3 -1 0 -7/3 0 2 -
X1 0 1 1/3 0 0 1/3 0 1 3
A2 0 0 5/3 -1 0 -4/3 1 2 6/5
S3 0 0 5/3 0 1 -1/3 0 3 9/5

Leaving Entering
variable (LV) variable (EV)
Contoh Kasus Minimasi
Fase 1 : Mengubah nilai baris kunci [ Iterasi-2 ]

Var Var
r X1 X2 S2 S3 A1 A2 RHS Rasio r X1 X2 S2 S3 A1 A2 RHS Rasio
Basis Basis
r 1 0 5/3 -1 0 -7/3 0 2 - r
X1 0 1 1/3 0 0 1/3 0 1 3 X1
A2 0 0 5/3 -1 0 -4/3 1 2 6/5 X2 0 0 1 -3/5 0 -4/5 3/5 6/5
S3 0 0 5/3 0 1 -1/3 0 3 9/5 S3
Contoh Kasus Minimasi
Fase 1 : Mengubah nilai baris lain (selain baris kunci) [ Iterasi-2 ]

Var Var
r X1 X2 S2 S3 A1 A2 RHS Rasio r X1 X2 S2 S3 A1 A2 RHS Rasio
Basis Basis
r 1 0 5/3 -1 0 -7/3 0 2 - r 1 0 0 0 0 -1 -1 0
X1 0 1 1/3 0 0 1/3 0 1 3 X1 0 1 0 1/5 0 3/5 -1/5 3/5
A2 0 0 5/3 -1 0 -4/3 1 2 6/5 X2 0 0 1 -3/5 0 -4/5 3/5 6/5
S3 0 0 5/3 0 1 -1/3 0 3 9/5 S3 0 0 0 1 1 1 -1 1
Contoh Kasus Minimasi
Fase 1 : Periksa ke-optimalan table simpleks [ Iterasi-2 ]

Var Karena kasus minimasi (rmin), periksa kembali

r X1 X2 S2 S3 A1 A2 RHS
Basis apakah masih terdapat nilai positif pada baris r.
r 1 0 0 0 0 -1 -1 0 Jika masih terdapat nilai positif, maka lakukan
X1 0 1 0 1/5 0 3/5 -1/5 3/5 iterasi sampai baris r tidak ada yang bernilai
positif
X2 0 0 1 -3/5 0 -4/5 3/5 6/5
S3 0 0 0 1 1 1 -1 1

Apakah table simpleks sudah optimal? (baris r sudah tidak ada nilai positif?)
Dalam kasus ini r sudah tidak ada lagi yang bernilai positif, dan r ≤ 0, maka bisa dilanjutkan ke fase 2.
Jika terjadi pengulangan hasil, dan r bernilai positif, maka berhenti di fase 1 saja, dan bisa ditarik
kesimpulan bahwa tidak ada nilai yang optimal.
Contoh Kasus Minimasi
Fase 2 : Menentukan Fungsi kendala berdasarkan table simpleks pada Fase 1
Fungsi Tujuan Awal:
Var
r X1 X2 S2 S3 A1 A2 RHS 𝑍𝑚𝑖𝑛 = 4𝑋1 + 𝑋2
Basis
r 1 0 0 0 0 -1 -1 0 Fungsi Kendala Baru: Definisikan nilai X1 dan X2
X1 0 1 0 1/5 0 3/5 -1/5 3/5 1 3 3 1
𝑋1 + 𝑆2 = 𝑋1 = − 𝑆
X2 0 0 1 -3/5 0 -4/5 3/5 6/5
5 5 5 5 1
3 6
𝑋2 − 𝑆2 = 6 3
S3 0 0 0 1 1 1 -1 1 5 5 𝑋2 = + 𝑆2
5 5
𝑆2 + 𝑆3 = 1
Contoh Kasus Minimasi
Fase 2 : Menentukan Fungsi Tujuan baru
Fungsi Tujuan Awal: Fungsi Tujuan Baru:
𝑍𝑚𝑖𝑛 = 4𝑋1 + 𝑋2 𝑍𝑚𝑖𝑛 = 4𝑋1 + 𝑋2
3 1 6 3
Fungsi Kendala Baru: 𝑍𝑚𝑖𝑛 = 4 − 𝑆 + + 𝑆
1 3 5 5 2 5 5 2
3 1
𝑋1 + 𝑆2 = 𝑋1 = − 𝑆 12 4 6 3
5 5 5 5 2 𝑍𝑚𝑖𝑛 = − 𝑆2 + + 𝑆2
3 6 5 5 5 5
𝑋2 − 𝑆2 = 6 3 18 1
5 5 𝑋2 = + 𝑆2 𝑍𝑚𝑖𝑛 = − 𝑆
5 5 5 5 2
𝑆2 + 𝑆3 = 1

1 18 Fungsi Tujuan baru

𝑍 + 𝑆2 =
5 5
Contoh Kasus Minimasi
Fase 2 : Membuat table simpleks
Fungsi Tujuan :
1 18 Var
𝑍𝑚𝑖𝑛 + 𝑆2 = Z X1 X2 S2 S3 RHS
5 5 Basis
Fungsi Kendala : Z 1 0 0 1/5 0 18/5
1 3 Kendala 1 X1 0 1 0 1/5 0 3/5
𝑋1 + 𝑆2 =
5 5 Kendala 2 X2 0 0 1 -3/5 0 6/5
3 6
𝑋2 − 𝑆2 = Kendala 3 S3 0 0 0 1 1 1
5 5
𝑆2 + 𝑆3 = 1
Contoh Kasus Minimasi
Fase 2 : Lakukan iterasi
Iterasi 0 Iterasi 1

Var Var
Z X1 X2 S2 S3 RHS Rasio Z X1 X2 S2 S2 RHS Rasio
Basis Basis
Z 1 0 0 1/5 0 18/5 - Z 1 0 0 0 -1/5 17/5
X1 0 1 0 1/5 0 3/5 3 X1 0 1 0 0 -1/5 2/5
X2 0 0 1 -3/5 0 6/5 - X2 0 0 1 0 3/5 9/5
S3 0 0 0 1 1 1 1 S2 0 0 0 1 1 1
Contoh Kasus Minimasi
Fase 2 : Periksa ke-optimalan
Iterasi 1

Var Karena kasus maksimasi (Zmin), periksa kembali apakah masih

Z X1 X2 S2 S2 RHS terdapat nilai positif pada baris Z.
Basis
Z 1 0 0 0 -1/5 17/5 Jika masih terdapat nilai positif, maka lakukan iterasi sampai
X1 0 1 0 0 -1/5 2/5
baris Z tidak ada yang bernilai positif

X2 0 0 1 0 3/5 9/5
Apakah table simpleks sudah optimal? (baris Z sudah tidak ada
S2 0 0 0 1 1 1 nilai positif?)

Dalam kasus ini Z sudah tidak ada lagi yang bernilai positif,
maka bisa ditarik kesimpulan
Contoh Kasus Minimasi
Kesimpulan

Var
Z X1 X2 S2 S3 RHS Z = 17/5
Basis
X1 = 2/5
Z 1 0 0 0 -1/5 17/5
X2 = 9/5
X1 0 1 0 0 -1/5 2/5 S2 = 1
X2 0 0 1 0 3/5 9/5
S2 0 0 0 1 1 1