Pemrograman Linier (3) Metode Big-M
Ahmad Sabri Universitas Gunadarma, Indonesia
Pada model PL di mana semua kendala memiliki relasi ≤, variabel basis pada solusi awal (tabel simpleks awal) adalah Z dan semua variabel slack. Namun tidak demikian halnya untuk model PL yang memiliki kendala = atau ≥. Prosedur simpleks untuk menyelesaikan model PL yang memiliki kendala = atau ≥ dapat menggunakan salah satu metode di bawah ini: Metode Big M, atau Metode dua fase
2 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
2 / 19
Pada model PL di mana semua kendala memiliki relasi ≤, variabel basis pada solusi awal (tabel simpleks awal) adalah Z dan semua variabel slack. Namun tidak demikian halnya untuk model PL yang memiliki kendala = atau ≥. Prosedur simpleks untuk menyelesaikan model PL yang memiliki kendala = atau ≥ dapat menggunakan salah satu metode di bawah ini: Metode Big M, atau Metode dua fase
2 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
2 / 19
Pada model PL di mana semua kendala memiliki relasi ≤, variabel basis pada solusi awal (tabel simpleks awal) adalah Z dan semua variabel slack. Namun tidak demikian halnya untuk model PL yang memiliki kendala = atau ≥. Prosedur simpleks untuk menyelesaikan model PL yang memiliki kendala = atau ≥ dapat menggunakan salah satu metode di bawah ini: Metode Big M, atau Metode dua fase
2 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
2 / 19
Metode Big M : gambaran umum
Dalam bentuk baku, pada kendala dengan relasi ≥ atau = tidak terdapat variabel slack. Pada kedua jenis kendala tersebut, digunakan variabel yang berfungsi seolah-olah sebagai slack. Variabel ini dinamakan variabel artifisial (umumnya dilambangkan sebagai R).
3 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
3 / 19
Metode Big M : gambaran umum
Dalam bentuk baku, pada kendala dengan relasi ≥ atau = tidak terdapat variabel slack. Pada kedua jenis kendala tersebut, digunakan variabel yang berfungsi seolah-olah sebagai slack. Variabel ini dinamakan variabel artifisial (umumnya dilambangkan sebagai R).
3 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
3 / 19
Metode Big M : gambaran umum
Pada tabel awal simpleks, variabel artifisial terdapat pada basis. Namun pada tabel akhir (solusi optimal), semua variabel artifisial harus keluar dari basis (dengan kata lain, harus bernilai 0). (Catatan: hal ini terjadi jika problem memiliki solusi layak.) Untuk ‘memaksa’nya keluar dari basis, setiap variabel artifisial diberi penalti pada fungsi objektif,
4 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
4 / 19
Metode Big M : gambaran umum
Pada tabel awal simpleks, variabel artifisial terdapat pada basis. Namun pada tabel akhir (solusi optimal), semua variabel artifisial harus keluar dari basis (dengan kata lain, harus bernilai 0). (Catatan: hal ini terjadi jika problem memiliki solusi layak.) Untuk ‘memaksa’nya keluar dari basis, setiap variabel artifisial diberi penalti pada fungsi objektif,
4 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
4 / 19
Aturan penalti untuk variabel artifisial
Diberikan M sebagai nilai yang sangat besar (secara matematis, M → ∞). Setiap variabel artifisial diberi penalti pada fungsi objektif, dengan memberinya koefisien sebesar: −M pada masalah maksimisasi, atau +M pada masalah minimisasi
5 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
5 / 19
Contoh Min Z = 4x1 + x2 Dengan kendala: 3x1 + x2 = 3 4x1 + 3x2 ≥ 6 x1 + 2x2 ≤ 4 x1 , x2 ≥ 0
6 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
6 / 19
Bentuk baku: Min Z = 4x1 + x2 Dengan kendala: 3x1 + x2 4x1 + 3x2 −s1 x1 + 2x2 +s2 x1 , x2 , s1 , s2 ≥ 0
= = =
3 6 4
Keterangan: s1 : variabel surplus, s2 : variabel slack
7 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
7 / 19
Bentuk baku: Min Z = 4x1 + x2 + M R1 + M R2 Dengan kendala: 3x1 + x2 + R1 4x1 + 3x2 − s1 + R2 x1 + 2x2 + s2 x1 , x2 , s1 , s2 , R1 , R2 ≥ 0
= = =
3 6 4
Keterangan: R1 dan R2 adalah variabel artifisial. M adalah penalti untuk R1 dan R2 pada fungsi objektif.
8 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
8 / 19
Untuk memudahkan proses komputasi pada komputer, M umumnya disubstitusi dengan bilangan yang sangat besar. Namun pada prakteknya, M tidak perlu sangat besar; namun cukup besar jika dibandingkan dengan koefisien variabel keputusan pada fungsi objektif. Sebagai contoh, koefisien untuk x1 dan x2 pada fungsi objektif adalah 4 dan 1. Oleh karena itu, cukup wajar jika M bernilai 100 (relatif besar terhadap 4 dan 1).
9 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
9 / 19
Untuk memudahkan proses komputasi pada komputer, M umumnya disubstitusi dengan bilangan yang sangat besar. Namun pada prakteknya, M tidak perlu sangat besar; namun cukup besar jika dibandingkan dengan koefisien variabel keputusan pada fungsi objektif. Sebagai contoh, koefisien untuk x1 dan x2 pada fungsi objektif adalah 4 dan 1. Oleh karena itu, cukup wajar jika M bernilai 100 (relatif besar terhadap 4 dan 1).
9 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
9 / 19
Untuk memudahkan proses komputasi pada komputer, M umumnya disubstitusi dengan bilangan yang sangat besar. Namun pada prakteknya, M tidak perlu sangat besar; namun cukup besar jika dibandingkan dengan koefisien variabel keputusan pada fungsi objektif. Sebagai contoh, koefisien untuk x1 dan x2 pada fungsi objektif adalah 4 dan 1. Oleh karena itu, cukup wajar jika M bernilai 100 (relatif besar terhadap 4 dan 1).
9 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
9 / 19
Iterasi ke-0: tabel simpleks awal Itr.
0
No. (0) (1) (2) (3)
Basis Z R1 R2 s2
Z 1 0 0 0
x1 -4 3 4 1
x2 -1 1 3 2
s1 0 0 -1 0
R1 -100 1 0 0
R2 -100 0 1 0
s2 0 0 0 1
Solusi 0 3 6 4
Rasio
Perhatikan bahwa x1 = 0, x2 = 0, R1 = 3, R2 = 6, sehingga Z = 4(0) + (0) + 100(3) + 100(6) = 900. Padahal, dari tabel diperoleh Z = 0 (terdapat inkonsistensi). Untuk mengatasinya, koefisien R1 dan R2 pada baris 0 (baris Z) harus dijadikan 0, dengan cara: (0)baru = (0)lama + (100 × (1) + 100 × (2))
10 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
10 / 19
Iterasi ke-0: tabel simpleks awal Itr.
0
No. (0) (1) (2) (3)
Basis Z R1 R2 s2
Z 1 0 0 0
x1 -4 3 4 1
x2 -1 1 3 2
s1 0 0 -1 0
R1 -100 1 0 0
R2 -100 0 1 0
s2 0 0 0 1
Solusi 0 3 6 4
Rasio
Perhatikan bahwa x1 = 0, x2 = 0, R1 = 3, R2 = 6, sehingga Z = 4(0) + (0) + 100(3) + 100(6) = 900. Padahal, dari tabel diperoleh Z = 0 (terdapat inkonsistensi). Untuk mengatasinya, koefisien R1 dan R2 pada baris 0 (baris Z) harus dijadikan 0, dengan cara: (0)baru = (0)lama + (100 × (1) + 100 × (2))
10 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
10 / 19
Iterasi ke-0: tabel simpleks awal Itr.
0
No. (0) (1) (2) (3)
Basis Z R1 R2 s2
Z 1 0 0 0
x1 -4 3 4 1
x2 -1 1 3 2
s1 0 0 -1 0
R1 -100 1 0 0
R2 -100 0 1 0
s2 0 0 0 1
Solusi 0 3 6 4
Rasio
Perhatikan bahwa x1 = 0, x2 = 0, R1 = 3, R2 = 6, sehingga Z = 4(0) + (0) + 100(3) + 100(6) = 900. Padahal, dari tabel diperoleh Z = 0 (terdapat inkonsistensi). Untuk mengatasinya, koefisien R1 dan R2 pada baris 0 (baris Z) harus dijadikan 0, dengan cara: (0)baru = (0)lama + (100 × (1) + 100 × (2))
10 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
10 / 19
Iterasi ke-0: tabel simpleks awal Itr.
0
No. (0) (1) (2) (3)
Basis Z R1 R2 s2
Z 1 0 0 0
x1 -4 3 4 1
x2 -1 1 3 2
s1 0 0 -1 0
R1 -100 1 0 0
R2 -100 0 1 0
s2 0 0 0 1
Solusi 0 3 6 4
Rasio
Perhatikan bahwa x1 = 0, x2 = 0, R1 = 3, R2 = 6, sehingga Z = 4(0) + (0) + 100(3) + 100(6) = 900. Padahal, dari tabel diperoleh Z = 0 (terdapat inkonsistensi). Untuk mengatasinya, koefisien R1 dan R2 pada baris 0 (baris Z) harus dijadikan 0, dengan cara: (0)baru = (0)lama + (100 × (1) + 100 × (2))
10 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
10 / 19
Iterasi ke-0: tabel simpleks awal termodifikasi
Itr.
0
No. (0) (1) (2) (3)
Basis Z R1 R2 s2
Z 1 0 0 0
x1 696 3 4 1
x2 399 1 3 2
s1 -100 0 -1 0
R1 0 1 0 0
R2 0 0 1 0
s2 0 0 0 1
Solusi 900 3 6 4
Rasio
Solusi dasar awal: x1 = 0, x2 = 0, R1 = 3, R2 = 6, Z = 900.
11 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
11 / 19
Iterasi ke-0: tabel simpleks awal termodifikasi
Itr.
0
No. (0) (1) (2) (3)
Basis Z R1 R2 s2
Z 1 0 0 0
x1 696 3 4 1
x2 399 1 3 2
s1 -100 0 -1 0
R1 0 1 0 0
R2 0 0 1 0
s2 0 0 0 1
Solusi 900 3 6 4
Rasio
Solusi dasar awal: x1 = 0, x2 = 0, R1 = 3, R2 = 6, Z = 900.
11 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
11 / 19
Update tabel: kolom pivot (variabel masuk basis)
Problem minimisasi: kolom pivot adalah kolom dengan koefisien paling positif pada baris (0). No. (0) (1) (2) (3)
Basis Z R1 R2 s2
Z 1 0 0 0
x1 696 3 4 1
x2 399 1 3 2
s1 -100 0 -1 0
R1 0 1 0 0
R2 0 0 1 0
s2 0 0 0 1
Solusi 900 3 6 4
Rasio
12 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
12 / 19
Update tabel: menghitung rasio
No. (0) (1) (2) (3)
Basis Z R1 R2 s2
Z 1 0 0 0
x1 696 3 4 1
x2 399 1 3 2
s1 -100 0 -1 0
R1 0 1 0 0
R2 0 0 1 0
s2 0 0 0 1
Solusi 900 3 6 4
Rasio 1 1,5 4
13 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
13 / 19
Update tabel: baris pivot (variabel keluar basis)
No. (0) (1) (2) (3)
Basis Z R1 R2 s2
Z 1 0 0 0
x1 696 3 4 1
x2 399 1 3 2
s1 -100 0 -1 0
R1 0 1 0 0
R2 0 0 1 0
s2 0 0 0 1
Solusi 900 3 6 4
Rasio 1 1,5 4
Elemen pivot = 3 Masuk basis: x1 Keluar basis: R1
14 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
14 / 19
Iterasi ke-1
Itr.
1
No. (0) (1) (2) (3)
Basis Z x1 R2 s2
Z 1 0 0 0
x1 0 1 0 0
x2 167 1 3 5 3 5 3
s1 -100 0 -1 0
R1 -232 1 3 - 43 - 13
R2 0 0 1 0
s2 0 0 0 1
Solusi 204 1 2 3
Rasio
x1 = 1, x2 = 0, Z = 204 (Belum optimal)
15 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
15 / 19
Update tabel: kolom pivot
No. (0) (1) (2) (3)
Basis Z x1 R2 s2
Z 1 0 0 0
x1 0 1 0 0
x2 167 1 3 5 3 5 3
s1 -100 0 -1 0
R1 -232 1 3 - 43 - 13
R2 0 0 1 0
s2 0 0 0 1
Solusi 204 1 2 3
Rasio
16 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
16 / 19
Update tabel: menghitung rasio
No. (0) (1) (2) (3)
Basis Z x1 R2 s2
Z 1 0 0 0
x1 0 1 0 0
x2 167 1 3 5 3 5 3
s1 -100 0 -1 0
R1 -232 1 3 - 43 - 13
R2 0 0 1 0
s2 0 0 0 1
Solusi 204 1 2 3
Rasio 3 6 5 9 5
17 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
17 / 19
Update tabel: baris pivot No. (0) (1) (2) (3)
Basis Z x1 R2 s2
Z 1 0 0 0
x1 0 1 0 0
x2 167 1 3 5 3 5 3
s1 -100 0 -1 0
R1 -232 1 3 - 43 - 13
R2 0 0 1 0
s2 0 0 0 1
Solusi 204 1 2 3
Rasio 3 6 5 9 5
Elemen pivot = 53 Variabel masuk: x2 Variabel keluar: R2 Perhatikan bahwa pada tahap ini, variabel artifisial R1 dan R2 sudah keluar dari basis. Dibutuhkan dua iterasi lagi untuk mencapai optimal, yaitu: x1 = 25 , x2 = 95 , dan Z = 17 5 (Harap diperiksa!!)
18 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
18 / 19
Update tabel: baris pivot No. (0) (1) (2) (3)
Basis Z x1 R2 s2
Z 1 0 0 0
x1 0 1 0 0
x2 167 1 3 5 3 5 3
s1 -100 0 -1 0
R1 -232 1 3 - 43 - 13
R2 0 0 1 0
s2 0 0 0 1
Solusi 204 1 2 3
Rasio 3 6 5 9 5
Elemen pivot = 53 Variabel masuk: x2 Variabel keluar: R2 Perhatikan bahwa pada tahap ini, variabel artifisial R1 dan R2 sudah keluar dari basis. Dibutuhkan dua iterasi lagi untuk mencapai optimal, yaitu: x1 = 52 , x2 = 95 , dan Z = 17 5 (Harap diperiksa!!)
18 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
18 / 19
Update tabel: baris pivot No. (0) (1) (2) (3)
Basis Z x1 R2 s2
Z 1 0 0 0
x1 0 1 0 0
x2 167 1 3 5 3 5 3
s1 -100 0 -1 0
R1 -232 1 3 - 43 - 13
R2 0 0 1 0
s2 0 0 0 1
Solusi 204 1 2 3
Rasio 3 6 5 9 5
Elemen pivot = 53 Variabel masuk: x2 Variabel keluar: R2 Perhatikan bahwa pada tahap ini, variabel artifisial R1 dan R2 sudah keluar dari basis. Dibutuhkan dua iterasi lagi untuk mencapai optimal, yaitu: x1 = 52 , x2 = 95 , dan Z = 17 5 (Harap diperiksa!!)
18 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
18 / 19
Contoh Min Z = 4x1 + 5x2 Dengan kendala: 3x1 + x2 ≤ 27 5x1 + 5x2 = 6 6x1 + 4x2 ≥ 6 x1 , x2 ≥ 0 Temukan solusi optimalnya dengan menggunakan metode simpleks Big M.
19 Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (3)
19 / 19
