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