Download - Metode simplex 1
Maksimasi : f = 60 x1 + 30 x2 + 20x3
dengan kendala:
8x1 + 6x2 + x3 ≤ 40
4x1 + 2x2 + 1,5x3 ≤ 20
2x1 + 1,5x2 + 0,5x3 ≤ 8
x2 ≤ 5
x1, x2, x3 ≥ 0
Tahap-tahap:
1. Transformasikan permasalahan menjadi bentuk standar. Bentuk standar dihasilkan dengan mengubah semua tanda pada fungsi kendala menjadi bertanda sama dengan.
Maksimasi:
f= 60 x1+ 30 x2+ 20x3+ 0S1+0S2+0S3+0S4
dengan kendala:
8x1 + 6x2 + x3+ S1 = 40
4x1 + 2x2 + 1,5x3 + S2 = 20
2x1 + 1,5x2 + 0,5x3 + S3 = 8
x2 + S4 = 5
2. Susun persamaan bentuk standar ke dalam Tabel. Tambahkan satu baris pada bagian bawah dan isi dengan koefisien fungsi tujuan. Tabel tersebut merupakan kondisi awal permasalahan atau iterasi ke-0
Tabel : Iterasi ke-0
No 1 2 3 4 5 6 7 8 9 10
1
CB
Cj
Basis
x1 x2 x3 S1 S2 S3 S4
KRK 2 60 30 20 0 0 0 0
3 0 S1 8 6 1 1 0 0 0 40
4 0 S2 4 2 1,5 0 1 0 0 20
5 0 S3 2 1,5 0,5 0 0 1 0 8
6 0 S4 0 1 0 0 0 0 1 5
7 CRj 60 30 20 0 0 0 0 f=0
3. Menentukan EB dan LB. EB terpilih x1. Hitung Rasio =KRK/koefisien pada kolom EB yang bersesuaian.
- baris 3: 40/8 = 5
- baris 4: 20/4 = 5
- baris 5: 8/2 = 4 (terkecil)
- baris 6: 5/0 = ∞
Terpilih baris 5 sebagai LB
Tabel : Iterasi ke-1
No 1 2 3 4 5 6 7 8 9 10
1
CB
Cj
Basis
x1 x2 x3 S1 S2 S3 S4
KRK 2 60 30 20 0 0 0 0
3 0 S1 8 6 1 1 0 0 0 40
4 0 S2 4 2 1,5 0 1 0 0 20
5 0 S3 2 1,5 0,5 0 0 1 0 8
6 0 S4 0 1 0 0 0 0 1 5
7 CRj 60 30 20 0 0 0 0 f=0
EB
Tabel : Iterasi ke-1
No 1 2 3 4 5 6 7 8 9 10
1
CB
Cj
Basis
x1 x2 x3 S1 S2 S3 S4
KRK 2 60 30 20 0 0 0 0
3 0 S1 8 6 1 1 0 0 0 40
4 0 S2 4 2 1,5 0 1 0 0 20
5 0 S3 2 1,5 0,5 0 0 1 0 8
6 0 S4 0 1 0 0 0 0 1 5
7 CRj 60 30 20 0 0 0 0 f=0
EB
LB
4. Jadikan 1 koefisien pada sel perpotongan kolom EB dengan baris LB dengan cara dikalikan dengan ½ dan sesuaikan koefisien lain pada baris LB. Pada kolom Basis, S3 diganti x1 dan pada kolom CB pada baris LB diisi dengan koefisien fungsi tujuan dari x1
Tabel : Iterasi ke-1
No 1 2 3 4 5 6 7 8 9 10
1
CB
Cj
Basis
x1 x2 x3 S1 S2 S3 S4
KRK 2 60 30 20 0 0 0 0
3 0 S1 8
4 0 S2 4
5 60 x1 1 0,75 0,25 0 0 0,5 0 4
6 0 S4 0
7 CRj 60 f=0
EB
LB
5. Nolkan koefisien lain pd kolom EB, sesuaikan koefisien lain dimasing-masing baris.
Utk baris 3: baris 5 dikali (−8) kemudian ditambah baris 3
Utk baris 4: baris 5 dikali (−4) kemudian ditambah baris 4
Utk baris 6: tetap karena koefisien pada sel tersebut sudah bernilai 0
Utk baris 7: baris 5 dikali (−60) kemdian ditambah baris 6
Hasilnya:
Tabel : hasil Iterasi ke-1
No 1 2 3 4 5 6 7 8 9 10
1
CB
Cj
Basis
x1 x2 x3 S1 S2 S3 S4
KRK 2 60 30 20 0 0 0 0
3 0 S1 0 0 −1 1 0 −4 0 8
4 0 S2 0 −1 0,5 0 1 −2 0 4
5 60 x1 1 0,75 0,25 0 0 0,5 0 4
6 0 S4 0 1 0 0 0 0 1 5
7 CRj 0 −15 5 0 0 −30
0 f=240
Iterasi ke-2 menentukan EB dan LB
No 1 2 3 4 5 6 7 8 9 10
1
CB
Cj
Basis
x1 x2 x3 S1 S2 S3 S4
KRK 2 60 30 20 0 0 0 0
3 0 S1 0 0 −1 1 0 −4 0 8
4 0 S2 0 −1 0,5 0 1 −2 0 4
5 60 x1 1 0,75 0,25 0 0 0,5 0 4
6 0 S4 0 1 0 0 0 0 1 5
7 CRj 0 −15 5 0 0 −30
0 f=240
EB
Iterasi ke-2 menentukan EB dan LB
No 1 2 3 4 5 6 7 8 9 10
1
CB
Cj
Basis
x1 x2 x3 S1 S2 S3 S4
KRK 2 60 30 20 0 0 0 0
3 0 S1 0 0 −1 1 0 −4 0 8
4 0 S2 0 −1 0,5 0 1 −2 0 4
5 60 x1 1 0,75 0,25 0 0 0,5 0 4
6 0 S4 0 1 0 0 0 0 1 5
7 CRj 0 −15 5 0 0 −30
0 f=240
EB
LB
Iterasi ke-2 menentukan solusi
No 1 2 3 4 5 6 7 8 9 10
1
CB
Cj
Basis
x1 x2 x3 S1 S2 S3 S4
KRK 2 60 30 20 0 0 0 0
3 0 S1 −1
4 0 S2 0 −2 1 0 2 −4 0 8
5 60 x1 0,25
6 0 S4 0
7 CRj 5 f=240
EB
LB
Hasil Iterasi ke-2
No 1 2 3 4 5 6 7 8 9 10
1
CB
Cj
Basis
x1 x2 x3 S1 S2 S3 S4
KRK 2 60 30 20 0 0 0 0
3 0 S1 0 −2 0 1 2 −8 0 16
4 20 x3 0 −2 1 0 2 −4 0 8
5 60 x1 1 1,25 0 0 −0,5 1,5 0 2
6 0 S4 0 1 0 0 0 0 1 5
7 CRj 0 −5 0 0 −10 −10 0 f=280
Optimal
PROBLEM MINIMASI
Contoh:
Minimasi: f = 2x1 – 3x2
dengan kendala:
x1 + x2 ≤ 4
x1 – x2 ≤ 6
x1, x2 ≥ 0
Dapat diselesaikan dengan 2 cara:
1. Cara 1: mengubah fungsi tujuan menjadi berbentuk maksimasi: −f = −2x1 + 3x2 kemudian diselesaikan dengan cara seperti sebelumnya
2. Cara 2: dengan memodifikasi langkah 3 yaitu EB dipilih yang paling negatif. Solusi optimal jika semua koefisien CRj bernilai positif
No 1 2 3 4 5 6 7
1 CB
Cj
Basis
- 2 3 0 0 KRK
2 x1 x2 S1 S2
3 0 S1 1 1 1 0 4
4 0 S2 1 −1 0 1 6
5 CRj −2 3 0 0 -f=0
Cara 1: Iterasi ke-0
No 1 2 3 4 5 6 7
1 CB
Cj
Basis
- 2 3 0 0 KRK
2 x1 x2 S1 S2
3 0 S1 1 1 1 0 4
4 0 S2 1 −1 0 1 6
5 CRj −2 3 0 0 -f=0
Cara 1: Iterasi ke-1: menentukan EB da LB EB
LB
No 1 2 3 4 5 6 7
1 CB
Cj
Basis
- 2 3 0 0 KRK
2 x1 x2 S1 S2
3 3 x1 1 1 1 0 4
4 0 S2 0
5 CRj 0 -f=0
Cara 1: Iterasi ke-1: menentukan solusi optimal EB
LB
No 1 2 3 4 5 6 7
1 CB
Cj
Basis
- 2 3 0 0 KRK
2 x1 x2 S1 S2
3 3 x2 1 1 1 0 4
4 0 S2 2 0 2 2 10
5 CRj −5 0 −3 0 -f=12
Cara 1: Iterasi ke-1: menentukan solusi optimal EB
LB
Solusi Optimal
No 1 2 3 4 5 6 7
1 CB
Cj
Basis
2 - 3 0 0 KRK
2 x1 x2 S1 S2
3 0 S1 1 1 1 0 4
4 0 S2 1 −1 0 1 6
5 CRj 2 −3 0 0 f=0
Iterasi ke-0
No 1 2 3 4 5 6 7
1 CB
Cj
Basis
2 - 3 0 0 KRK
2 x1 x2 S1 S2
3 0 S1 1 1 1 0 4
4 0 S2 1 −1 0 1 6
5 CRj 2 −3 0 0 f=0
Iterasi ke-1
No 1 2 3 4 5 6 7
1 CB
Cj
Basis
2 - 3 0 0 KRK
2 x1 x2 S1 S2
3 -3 X2 1 1 1 0 4
4 0 S2 2 0 1 1 10
5 CRj 5 0 3 0 f=-12
Iterasi ke-1
optimal
Contoh lain:
Minimasi: f = – x1 – x2
dengan kendala:
x1 + x2 ≤ 2
x1 – x2 ≤ 1
x1, x2 ≥ 0