Metode Big M
-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
• Fungsi kendala tidak hanya dibentuk oleh pertidaksamaan ≤ tetapi juga oleh
pertidaksamaan ≥ atau persamaan =.
• Untuk mengubah menjadi persamaan pada fungsi kendala pertidaksamaan ≥,
kurangkanlah dengan variabel surplus.
• Karena variabel surplus tidak bisa menjadi variabel basis awal karena
koefisiennya bertanda negatif, maka harus ditambahkan satu variabel baru yang
berfungsi sebagai variabel basis awal.
• Variabel yang dapat berfungsi sebagai variabel basis awal hanya variabel slack
dan variabel buatan (artificial variables)
Pendahuluan
• Perbedaan antara metode Big M dengan metode Simpleks sederhana terletak
pada tahap mengubah bentuk umum menjadi bentuk standar/kanonik saja.
• Fungsi tujuan dimodifikasi dengan memberikan variable artifisial/buatan dan
koefisien tambahan yang besar (biasanya disebut sebagai M).
• Jika kasus maksimasi variable artifisial pada fungsi tujuan memiliki koefisien –M
• Jika kasus minimasi variable artifisial pada fungsi tujuan memiliki koefisien +M
• Penambahan koefisien ini bertujuan untuk mengeliminasi variabel artifisial dari
solusi optimal, sehingga menghasilkan solusi yang memenuhi kendala asli.
• Variabel artifisial pada solusi optimal harus bernilai 0,
Contoh kasus Maksimasi
- Metode Big-M -
Contoh Kasus Maksimasi
• Bentuk Umum 1. Ubah ke bentuk Standar/Kanonik
𝑍𝑚𝑎𝑥 = 50𝑋1 + 80𝑋2 Fungsi Kendala :
𝑋1 + 𝑆1 = 40
Fungsi Kendala
𝑋2 − 𝑆2 + 𝐴2 = 20
𝑋1 ≤ 40 𝑋1 + 𝑋2 + 𝐴3 = 50
𝑋2 ≥ 20
𝑋1 , 𝑋2 . 𝑆1 , 𝑆2 , 𝐴2 , 𝐴3 ≥ 0
𝑋1 + 𝑋2 = 50
𝑋1 , 𝑋2 ≥ 0 Fungsi Tujuan :
𝑍𝑚𝑎𝑥 = 50𝑋1 + 80𝑋2 + 0𝑆1 − 0𝑆2 − 𝑀𝐴2 − 𝑀𝐴3
Contoh Kasus Maksimasi
1. Ubah ke bentuk Standar/Kanonik
Fungsi Tujuan :
𝑍𝑚𝑎𝑥 = 50𝑋1 + 80𝑋2 + 0𝑆1 − 0𝑆2 − 𝑀𝐴2 − 𝑀𝐴3
Fungsi Kendala : Definisikan nilai A2 dan A3
𝑋1 + 𝑆1 = 40
𝑋2 − 𝑆2 + 𝐴2 = 20 𝐴2 = 20 − 𝑋2 + 𝑆2
𝑋1 + 𝑋2 + 𝐴3 = 50 𝐴3 = 50 − 𝑋1 − 𝑋2
𝑋1 , 𝑋2 . 𝑆1 , 𝑆2 , 𝐴2 , 𝐴3 ≥ 0
Contoh Kasus Maksimasi
1. Ubah ke bentuk Standar/Kanonik
Fungsi Tujuan :
𝑍𝑚𝑎𝑥 = 50𝑋1 + 80𝑋2 + 0𝑆1 − 0𝑆2 − 𝑀𝐴2 − 𝑀𝐴3
Fungsi Kendala : Masukkan nilai A2 dan A3 ke fungsi tujuan
𝑋1 + 𝑆1 = 40 𝑍𝑚𝑎𝑥 = 50𝑋1 + 80𝑋2 + 0𝑆1 − 0𝑆2 − 𝑀𝐴2 − 𝑀𝐴3
𝑋2 − 𝑆2 + 𝐴2 = 20 𝑍𝑚𝑎𝑥 = 50𝑋1 + 80𝑋2 + 0𝑆1 − 0𝑆2 − 𝑀(20 − 𝑋2 + 𝑆2 ) − 𝑀(50 − 𝑋1 − 𝑋2 )
𝑋1 + 𝑋2 + 𝐴3 = 50 𝑍𝑚𝑎𝑥 = 50𝑋1 + 80𝑋2 + 0𝑆1 − 0𝑆2 − 20𝑀 + 𝑀𝑋2 − 𝑀𝑆2 − 50𝑀 + 𝑀𝑋1 + 𝑀𝑋2
𝑋1 , 𝑋2 . 𝑆1 , 𝑆2 , 𝐴2 , 𝐴3 ≥ 0 𝑍𝑚𝑎𝑥 = 𝑀 + 50 𝑋1 + 2𝑀 + 80 𝑋2 + 0𝑆1 − 𝑀𝑆2 − 70𝑀
𝐴2 = 20 − 𝑋2 + 𝑆2 𝑍 − 𝑀 + 50 𝑋1 − 2𝑀 + 80 𝑋2 − 0𝑆1 + 𝑀𝑆2 = −70𝑀
𝐴3 = 50 − 𝑋1 − 𝑋2
Contoh Kasus Maksimasi
2. Membuat table simpleks
Fungsi Tujuan :
𝑍 − 𝑀 + 50 𝑋1 − 2𝑀 + 80 𝑋2 − 0𝑆1 + 𝑀𝑆2 = −70𝑀
Fungsi Kendala :
𝑋1 + 𝑆1 = 40
𝑋2 − 𝑆2 + 𝐴2 = 20
Var
𝑋1 + 𝑋2 + 𝐴3 = 50 Z X1 X2 S1 S2 A2 A3 RHS Rasio
Basis
𝑋1 , 𝑋2 . 𝑆1 , 𝑆2 , 𝐴2 , 𝐴3 ≥ 0 Z 1 −(𝑀 + 50) -(2𝑀 + 80) 0 M 0 0 -70M
Kendala 1 S1 0 1 0 1 0 0 0 40
Kendala 2 A2 0 0 1 0 -1 1 0 20
Kendala 3 A3 0 1 1 0 0 0 1 50
Contoh Kasus Maksimasi
3. Periksa ke-optimalan table simpleks [ Iterasi-0 ]
Var Apakah table simpleks sudah
Z X1 X2 S1 S2 A2 A3 RHS Rasio
Basis optimal? (baris Z sudah tidak
Z 1 -(𝑀 + 50) -(2𝑀 + 80) 0 M 0 0 -70M ada nilai negatif?)
S1 0 1 0 1 0 0 0 40
Masih ada baris Z yang
A2 0 0 1 0 -1 1 0 20 bernilai negatif. Oleh karena
A3 0 1 1 0 0 0 1 50 itu lakukan iterasi yang
berikutnya
Contoh Kasus Maksimasi
4. Identifikasi kolom kunci [ Iterasi-1 ]
Var • Karena kasus maksimasi
Z X1 X2 S1 S2 A2 A3 RHS Rasio
Basis (Zmax) maka kolom kunci
Z 1 -(𝑀 + 50) -(2𝑀 + 80) 0 M 0 0 -70M
adalah nilai negatif tertinggi
S1 0 1 0 1 0 0 0 40 • Jika terdapat dua nilai
tertinggi, maka pilih salah
A2 0 0 1 0 -1 1 0 20 satu
A3 0 1 1 0 0 0 1 50
Entering
variable (EV)
Contoh Kasus Maksimasi
5. Identifikasi baris kunci [ Iterasi-1 ]
Var • Baris kunci adalah baris
Z X1 X2 S1 S2 A2 A3 RHS Rasio
Basis yang memiliki nilai rasio
Z 1 -(𝑀 + 50) -(2𝑀 + 80) 0 M 0 0 -70M -
positif terkecil
S1 0 1 0 1 0 0 0 40 - 𝑅𝐻𝑆
𝑅𝑎𝑠𝑖𝑜 =
𝑘𝑜𝑙𝑜𝑚 𝑘𝑢𝑛𝑐𝑖
A2 0 0 1 0 -1 1 0 20 20
• Jika kolom kunci bernilai 0
A3 0 1 1 0 0 0 1 50 50 atau negatif, bisa diabaikan
Leaving Entering • Jika terdapat nilai rasio
variable (LV) variable (EV) terkecil yang sama, pilih
salah satu
Contoh Kasus Maksimasi
6. Cari angka/nilai kunci [ Iterasi-1 ]
Var • Nilai yang terdapat pada
Z X1 X2 S1 S2 A2 A3 RHS Rasio
Basis persilangan / pertemuan
Z 1 -(𝑀 + 50) -(2𝑀 + 80) 0 M 0 0 -70M -
kolom kunci dan baris kunci
S1 0 1 0 1 0 0 0 40 -
A2 0 0 1 0 -1 1 0 20 20
A3 0 1 1 0 0 0 1 50 50
Nilai kunci yang didapatkan = 1
Leaving Entering
variable (LV) variable (EV)
Contoh Kasus Maksimasi
7. Mengubah nilai baris kunci [ Iterasi-1 ]
Var • Variabel basis pada baris
Z X1 X2 S1 S2 A2 A3 RHS Rasio
Basis kunci diganti dengan
Z 1 -(𝑀 + 50) -(2𝑀 + 80) 0 M 0 0 -70M -
variable pada kolom kunci.
S1 0 1 0 1 0 0 0 40 - • Membagi masing-masing
nilai baris dengan nilai
A2 0 0 1 0 -1 1 0 20 20 kunci
A3 0 1 1 0 0 0 1 50 50
Nilai kunci yang didapatkan = 1
Var
Z X1 X2 S1 S2 A2 A3 RHS Rasio
Basis
Z
S1
X2 0 0 1 0 -1 1 0 20 20
A3
Contoh Kasus Maksimasi
8. Mengubah nilai baris lain (selain baris kunci) [ Iterasi-1 ]
Var
Z X1 X2 S1 S2 A2 A3 RHS Rasio
Basis Baris Baru =
Z 1 -(𝑀 + 50) -(2𝑀 + 80) 0 M 0 0 -70M - Nilai lama – (nilai baru
S1 0 1 0 1 0 0 0 40 - basis kunci × nilai
kolom kunci)
A2 0 0 1 0 -1 1 0 20 20
A3 0 1 1 0 0 0 1 50 50
Lakukan untuk setiap
Var
Z X1 X2 S1 S2 A2 A3 RHS Rasio barisnya
Basis
Z 1 -(𝑀 + 50) 0 0 -(M+80) 2𝑀 + 80 0 -30M+1600
S1 0 1 0 1 0 0 0 40
X2 0 0 1 0 -1 1 0 20
A3 0 1 0 0 1 -1 1 30
Contoh Kasus Maksimasi
9. Periksa ke-optimalan table simpleks [ Iterasi-1 ]
Var
Z X1 X2 S1 S2 A2 A3 RHS Rasio
Basis
Z 1 -(𝑀 + 50) 0 0 -(M+80) 2𝑀 + 80 0 -30M+1600
S1 0 1 0 1 0 0 0 40
X2 0 0 1 0 -1 1 0 20
A3 0 1 0 0 1 -1 1 30
Karena kasus maksimasi (Zmax), periksa kembali apakah masih terdapat nilai negative pada baris Z.
Jika masih terdapat nilai negative, maka lakukan iterasi (ulangi Langkah 4-8) sampai baris Z tidak ada yang
bernilai negatif
Apakah table simpleks sudah optimal? (baris Z sudah tidak ada nilai negatif?)
Masih ada baris Z yang bernilai negatif. Oleh karena itu lakukan iterasi yang berikutnya
Contoh Kasus Maksimasi
4,5,6 Pilih kolom, baris dan nilai kunci [ Iterasi-2 ]
Var
Z X1 X2 S1 S2 A2 A3 RHS Rasio
Basis
Z 1 -(𝑀 + 50) 0 0 -(M+80) 2𝑀 + 80 0 -30M+1600 -
S1 0 1 0 1 0 0 0 40 -
X2 0 0 1 0 -1 1 0 20 -
A3 0 1 0 0 1 -1 1 30 30
Leaving Entering
variable (LV) variable (EV)
Contoh Kasus Maksimasi
7. Mengubah nilai baris kunci [ Iterasi-2 ]
Var
Z X1 X2 S1 S2 A2 A3 RHS Rasio
Basis
Z 1 -(𝑀 + 50) 0 0 -(M+80) 2𝑀 + 80 0 -30M+1600 -
S1 0 1 0 1 0 0 0 40 -
X2 0 0 1 0 -1 1 0 20 -
A3 0 1 0 0 1 -1 1 30 30
Var
Z X1 X2 S1 S2 A2 A3 RHS Rasio
Basis
Z
S1
X2
S2 0 1 0 0 1 -1 1 30
Contoh Kasus Maksimasi
8. Mengubah nilai baris lain (selain baris kunci) [ Iterasi-2 ]
Var
Z X1 X2 S1 S2 A2 A3 RHS Rasio
Basis
Z 1 -(𝑀 + 50) 0 0 -(M+80) 2𝑀 + 80 0 -30M+1600 -
S1 0 1 0 1 0 0 0 40 -
X2 0 0 1 0 -1 1 0 20 -
A3 0 1 0 0 1 -1 1 30 30
Var
Z X1 X2 S1 S2 A2 A3 RHS Rasio
Basis
Z 1 30 0 0 0 M M+80 4000
S1 0 1 0 1 0 0 0 40
X2 0 1 1 0 0 0 1 50
S2 0 1 0 0 1 -1 1 30
Contoh Kasus Maksimasi
9. Periksa ke-optimalan table simpleks [ Iterasi-2 ]
Var • Karena kasus maksimasi (Zmax),
Z X1 X2 S1 S2 A2 A3 RHS Rasio
Basis periksa kembali apakah masih
Z 1 30 0 0 0 M M+80 4000 terdapat nilai negative pada baris Z.
S1 0 1 0 1 0 0 0 40 • Jika masih terdapat nilai negative,
maka lakukan iterasi (ulangi
X2 0 1 1 0 0 0 1 50
Langkah 3-7) sampai baris Z tidak
S2 0 1 0 0 1 -1 1 30 ada yang bernilai negatif
Apakah table simpleks sudah optimal? (baris Z sudah tidak ada nilai negatif?)
Dalam kasus ini Z sudah tidak ada lagi yang bernilai negative, maka sudah optimal.
Lakukanlah penarikan kesimpulan
Contoh Kasus Maksimasi
Kesimpulan
Var Z = 4000
Z X1 X2 S1 S2 A2 A3 RHS
Basis X1 = 0
Z 1 30 0 0 0 M M+80 4000
X2 = 50
S1 = 40
S1 0 1 0 1 0 0 0 40
S2 = 30
X2 0 1 1 0 0 0 1 50 A1 = 0
S2 0 1 0 0 1 -1 1 30 A2 = 0
Kesimpulan : Agar memberikan keuntungan yang maksimal, maka X1 diproduksi sebanyak 0 unit dan X2
diproduksi 50 unit. Sehingga menghasilkan nilai Z sebesar = 4000.
Sumber daya pada kendala pertama terdapat sisa sebesar 40 unit. Sumber daya pada kendala kedua mempunyai
kelebihan 30 unit.
Contoh kasus Minimasi
- Metode Big-M -
Contoh Kasus Minimasi
• Bentuk Umum 1. Ubah ke bentuk Standar/Kanonik
𝑍𝑚𝑖𝑛 = 3𝑋1 + 5𝑋2 Fungsi Kendala :
𝑋1 + 𝑆1 = 4
Fungsi Kendala
2𝑋2 + 𝐴2 =12
𝑋1 ≤ 4 3𝑋1 + 2𝑋2 − 𝑆3 + 𝐴3 = 18
2𝑋2 = 12
𝑋1 , 𝑋2 . 𝑆1 , 𝑆3 , 𝐴2 , 𝐴3 ≥ 0
3𝑋1 + 2𝑋2 ≥ 18
𝑋1 , 𝑋2 ≥ 0
Fungsi Tujuan :
𝑍𝑚𝑖𝑛 = 3𝑋1 + 5𝑋2 + 0𝑆1 − 0𝑆3 + 𝑀𝐴2 + 𝑀𝐴3
Contoh Kasus Minimasi
1. Ubah ke bentuk Standar/Kanonik
Fungsi Tujuan :
𝑍𝑚𝑖𝑛 = 3𝑋1 + 5𝑋2 + 0𝑆1 − 0𝑆3 + 𝑀𝐴2 + 𝑀𝐴3
Fungsi Kendala : Definisikan nilai A2 dan A3
𝑋1 + 𝑆1 = 4
2𝑋2 + 𝐴2 =12 𝐴2 = 12 − 2𝑋2
3𝑋1 + 2𝑋2 − 𝑆3 + 𝐴3 = 18 𝐴3 = 18 − 3𝑋1 − 2𝑋2 + 𝑆3
𝑋1 , 𝑋2 . 𝑆1 , 𝑆2 , 𝐴2 , 𝐴3 ≥ 0
Contoh Kasus Minimasi
1. Ubah ke bentuk Standar/Kanonik
Fungsi Tujuan :
𝑍𝑚𝑖𝑛 = 3𝑋1 + 5𝑋2 + 0𝑆1 − 0𝑆3 + 𝑀𝐴2 + 𝑀𝐴3
Fungsi Kendala : Masukkan nilai A2 dan A3 ke fungsi tujuan
𝑋1 + 𝑆1 = 4 𝑍𝑚𝑖𝑛 = 3𝑋1 + 5𝑋2 + 0𝑆1 − 0𝑆3 + 𝑀𝐴2 + 𝑀𝐴3
2𝑋2 + 𝐴2 =12 𝑍𝑚𝑖𝑛 = 3𝑋1 + 5𝑋2 + 0𝑆1 − 0𝑆3 + 𝑀(12 − 2𝑋2 ) + 𝑀(18 − 3𝑋1 − 2𝑋2 + 𝑆3 )
3𝑋1 + 2𝑋2 − 𝑆3 + 𝐴3 = 18 𝑍𝑚𝑖𝑛 = 3𝑋1 + 5𝑋2 + 0𝑆1 − 0𝑆3 + 12𝑀 − 2𝑀𝑋2 + 18𝑀 − 3𝑀𝑋1 − 2𝑀𝑋2 + 𝑀𝑆3
𝑍𝑚𝑖𝑛 = (3 − 3𝑀)𝑋1 + (5 − 4𝑀)𝑋2 + 0𝑆1 − 0𝑆3 + 30𝑀 + 𝑀𝑆3
𝑋1 , 𝑋2 . 𝑆1 , 𝑆2 , 𝐴2 , 𝐴3 ≥ 0
𝐴2 = 12 − 2𝑋2 𝑍 − 3 − 3𝑀 𝑋1 − 5 − 4𝑀 𝑋2 − 𝑀𝑆3 = 30𝑀
𝐴3 = 18 − 3𝑋1 − 2𝑋2 + 𝑆3
Contoh Kasus Minimasi
2. Membuat table simpleks
Fungsi Tujuan :
𝑍 − 3 − 3𝑀 𝑋1 − 5 − 4𝑀 𝑋2 − 𝑀𝑆3 = 30𝑀
Fungsi Kendala :
𝑋1 + 𝑆1 = 4
2𝑋2 + 𝐴2 =12
Var
3𝑋1 + 2𝑋2 − 𝑆3 + 𝐴3 = 18 Z X1 X2 S1 S3 A2 A3 RHS Rasio
Basis
𝑋1 , 𝑋2 . 𝑆1 , 𝑆2 , 𝐴2 , 𝐴3 ≥ 0 Z 1 −3 + 3𝑀 (−5 + 4𝑀) 0 -M 0 0 30M
Kendala 1 S1 0 1 0 1 0 0 0 4
Kendala 2 A2 0 0 2 0 0 1 0 12
Kendala 3 A3 0 3 2 0 -1 0 1 18
Contoh Kasus Minimasi
3. Periksa ke-optimalan table simpleks [ Iterasi-0 ]
Var Apakah table simpleks sudah
Z X1 X2 S1 S3 A2 A3 RHS Rasio
Basis optimal? (baris Z sudah tidak
Z 1 −3 + 3𝑀 (−5 + 4𝑀) 0 -M 0 0 30M ada nilai positif?)
S1 0 1 0 1 0 0 0 4
Masih ada baris Z yang
A2 0 0 2 0 0 1 0 12 bernilai positif. Oleh karena
A3 0 3 2 0 -1 0 1 18 itu lakukan iterasi yang
berikutnya
Contoh Kasus Minimasi
4,5,6. Identifikasi kolom, baris dan nilai kunci [ Iterasi-1 ]
Var
Z X1 X2 S1 S3 A2 A3 RHS Rasio
Basis
Z 1 −3 + 3𝑀 (−5 + 4𝑀) 0 -M 0 0 30M -
S1 0 1 0 1 0 0 0 4 -
A2 0 0 2 0 0 1 0 12 6
A3 0 3 2 0 -1 0 1 18 9
Leaving Entering
variable (LV) variable (EV)
Contoh Kasus Minimasi
7. Mengubah nilai baris kunci [ Iterasi-1 ]
Var • Variabel basis pada baris
Z X1 X2 S1 S3 A2 A3 RHS Rasio
Basis kunci diganti dengan
Z 1 −3 + 3𝑀 (−5 + 4𝑀) 0 -M 0 0 30M -
variable pada kolom kunci.
S1 0 1 0 1 0 0 0 4 - • Membagi masing-masing
nilai baris dengan nilai
A2 0 0 2 0 0 1 0 12 6 kunci
A3 0 3 2 0 -1 0 1 18 9
Nilai kunci yang didapatkan = 1
Var
Z X1 X2 S1 S3 A2 A3 RHS Rasio
Basis
Z
S1
X2 0 0 1 0 0 1/2 0 6
A3
Contoh Kasus Minimasi
8. Mengubah nilai baris lain (selain baris kunci) [ Iterasi-1 ]
Var
Z X1 X2 S1 S3 A2 A3 RHS Rasio
Basis Baris Baru =
Z 1 −3 + 3𝑀 (−5 + 4𝑀) 0 -M 0 0 30M - Nilai lama – (nilai baru
S1 0 1 0 1 0 0 0 4 - basis kunci × nilai kolom
kunci)
A2 0 0 2 0 0 1 0 12 6
A3 0 3 2 0 -1 0 1 18 9
Lakukan untuk setiap
Var
Z X1 X2 S1 S3 A2 A3 RHS Rasio barisnya
Basis
Z 1 −3 + 3𝑀 0 0 -M (5/2)-2M 0 30+6M
S1 0 1 0 1 0 0 0 4
X2 0 0 1 0 0 ½ 0 6
A3 0 3 0 0 -1 -1 1 6
Contoh Kasus Minimasi
9. Periksa ke-optimalan table simpleks [ Iterasi-1 ]
Var
Z X1 X2 S1 S3 A2 A3 RHS Rasio
Basis
Z 1 −3 + 3𝑀 0 0 -M (5/2)-2M 0 30+6M
S1 0 1 0 1 0 0 0 4
X2 0 0 1 0 0 ½ 0 6
A3 0 3 0 0 -1 -1 1 6
Karena kasus maksimasi (Zmin), periksa kembali apakah masih terdapat nilai positif pada baris Z.
Jika masih terdapat nilai positif, maka lakukan iterasi (ulangi Langkah 4-8) sampai baris Z tidak ada yang
bernilai positif
Apakah table simpleks sudah optimal? (baris Z sudah tidak ada nilai positif?)
Masih ada baris Z yang bernilai positif. Oleh karena itu lakukan iterasi yang berikutnya
Contoh Kasus Minimasi
4,5,6 Pilih kolom, baris dan nilai kunci [ Iterasi-2 ]
Var
Z X1 X2 S1 S3 A2 A3 RHS Rasio
Basis
Z 1 −3 + 3𝑀 0 0 -M (5/2)-2M 0 30+6M -
S1 0 1 0 1 0 0 0 4 -
X2 0 0 1 0 0 ½ 0 6 -
A3 0 3 0 0 -1 -1 1 6 2
Leaving Entering
variable (LV) variable (EV)
Contoh Kasus Minimasi
7. Mengubah nilai baris kunci [ Iterasi-2 ]
Var
Z X1 X2 S1 S3 A2 A3 RHS Rasio
Basis
Z 1 −3 + 3𝑀 0 0 -M (5/2)-2M 0 30+6M -
S1 0 1 0 1 0 0 0 4 -
X2 0 0 1 0 0 ½ 0 6 -
A3 0 3 0 0 -1 -1 1 6 2
Var
Z X1 X2 S1 S2 A2 A3 RHS Rasio
Basis
Z
S1
X2
X1 0 1 0 0 -1/3 -1/3 1/3 2
Contoh Kasus Minimasi
8. Mengubah nilai baris lain (selain baris kunci) [ Iterasi-2 ]
Var
Z X1 X2 S1 S3 A2 A3 RHS Rasio
Basis
Z 1 −3 + 3𝑀 0 0 -M (5/2)-2M 0 30+6M -
S1 0 1 0 1 0 0 0 4 -
X2 0 0 1 0 0 ½ 0 6 -
A3 0 3 0 0 -1 -1 1 6 2
Var
Z X1 X2 S1 S3 A2 A3 RHS Rasio
Basis
Z 1 0 0 0 -1 (3/2)-M (1-M) 36
S1 0 0 0 1 1/3 1/3 -1/3 2
X2 0 0 1 0 0 1/2 0 6
X1 0 1 0 0 -1/3 -1/3 1/3 2
Contoh Kasus Minimasi
9. Periksa ke-optimalan table simpleks [ Iterasi-2 ]
Var • Karena kasus maksimasi (Zmin),
Z X1 X2 S1 S3 A2 A3 RHS
Basis periksa kembali apakah masih
Z 1 0 0 0 -1 (3/2)-M (1-M) 36 terdapat nilai positif pada baris Z.
S1 0 0 0 1 1/3 1/3 -1/3 2 • Jika masih terdapat nilai positif,
maka lakukan iterasi (ulangi
X2 0 0 1 0 0 1/2 0 6
Langkah 3-7) sampai baris Z tidak
X1 0 1 0 0 -1/3 -1/3 1/3 2 ada yang bernilai positif
Apakah table simpleks sudah optimal? (baris Z sudah tidak ada nilai positif?)
Dalam kasus ini Z sudah tidak ada lagi yang bernilai positif, maka sudah optimal.
Lakukanlah penarikan kesimpulan
Contoh Kasus Minimasi
Kesimpulan
Var Z = 36
Z X1 X2 S1 S3 A2 A3 RHS
Basis X1 = 2
Z 1 0 0 0 -1 (3/2)-M (1-M) 36
X2 = 6
S1 = 2
S1 0 0 0 1 1/3 1/3 -1/3 2
A1 = 0
X2 0 0 1 0 0 1/2 0 6 A2 = 0
X1 0 1 0 0 -1/3 -1/3 1/3 2
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