UMMU KALSUM

UNIVERSITAS GUNADARMA

2016

Menerjemahkan definisi grafik dari titik

ekstrim atau titik sudut menjadi definisi

aljabar

Sehingga sering disebut juga ‘metode

aljabar’

Aturan bentuk LP baku/standar:

Semua batasan/kendala dan

variabelnya ‘non negatif’

Fungsi tujuan dapat berupa maksimasi

dan minimasi

1. Karena semua kendala harus berbentuk persamaan, maka jika ada kendala berbentuk pertidaksamaan harus dikonversikan menjadi persamaan dengan memasukkan variabel semu ‘slack atau surplus’

2. Variabel slack ditambahkan di sisi kiri persamaan

3. Sebuah batasan sisi kanan berharga negatif diubah menjadi positif (dengan mengalikan persamaan dengan -1)

Bentuk LP umum:

Bentuk simpleks:

1. Formulasikan dan standarisasikan modelnya

2. Bentuk tabel awal simpleks berdasarkan

informasi model diatas

3. Tentukan kolom kunci diantara kolom-

kolom variabel yang ada, yaitu:

Kolom yang mengandung nilai (cj – Zj) ‘positif’

paling tinggi kasus ‘maksimasi’

Kolom yang mengandung nilai (cj - Zj) ‘negatif’

paling kecil untuk kasus ‘minimasi’

4. Tentukan baris kunci diantara baris-baris

variabel variabel yang ada, yaitu baris yang

memiliki ‘rasio kuantitas’ dengan nilai positif

terkecil

5. Bentuk tabel berikutnya dengan memasukkan

variabel baru ke kolom variabel dasar, dengan

menggantikan variabel lama, serta lakukan

transformasi baris variabel

6. Lakukan uji optimalitas. Dengan kriteria:

Sudah tidak ada lagi nilai (cj - Zj) yang bernilai

‘positif’ untuk kasus ‘maksimasi’

Sudah tidak ada lagi nilai (cj - Zj) yang bernilai

‘negatif’ untuk kasus ‘minimasi’

Jika kriteria di atas belum terpenuhi, maka ulangi dari

langkah 3 sampai ke 6, hingga kriteria terpenuhi

cj c1 c2 … cn 0 0 0

K x1 x2 … xn s1 s2 sn

Variabel

dasar

tujuan q

s1 0 b1 a11 a11 … a1n 1 0 0

s2 0 b2 a21 a22 … a2n 0 1 0

… … … … … … … … … …

sm 0 bm am1 am2 … amn 0 0 1

Zj 0 0 0 … 0 … … 0

cj - Zj c1 c2 … cn 0 … 0

Maksimumkan

Laba Z = 8x1 + 6x2 + 0s1 + 0s2

Batasan-batasan:

4X1 + 2X2 + 1s1 + 0s2 = 60

2X1 + 4X2 + 0s1 + 1s2 = 48

X1. x2, s1, s2 ≥ 0

Angka kunci

(baris kunci) Angka terbesar

sebagai kolom

kunci

Kolom kunci

Uji optimalitas belum terpenuhi

kriteria maksimasi

sudah tidak ada nilai (cj-zj) yang bernilai positif

(karena maksimasi) diperoleh X1 = 12 dan X2 = 6