KASUS MINIMISASI

Kasus meminimumkan nilai fungsi tujuan (minimisasi) dalam programasi linear

dapat dilakukan dengan dua cara :

1. Mengubah aturan yang digunakan pada kasus maksimisasi.

Kalau pada kasus maksimisasi, variabel yang kita pilih sebagai variabel dasar adalah

variabel yang mempunyai nilai Cj – Zj terbesar, maka pada kasus minimisasi kita pilih

variabel yang mempunyai nilai Cj – Zj yang paling besar negatifnya. Hal ini berarti pula

bahwa penyelesaian optimal akan tercapai kalau semua nilai pada baris Cj – Zj tidak

negatif.

2. Menggunakan logika matematika, yaitu bila kita ingin meminimumkan fungsi tujuan Z

dengan sejumlah kendala berarti pula kita memaksimumkan –Z dengan kendala yang

sama. Dengan demikian, meminimumkan Z = memaksimumkan (-Z).

Dengan cara memaksimumkan –Z dalam memecahkan kasus minimisasi, berarti kita

dapat pula mengikuti prosedur penyelesaian seperti pada kasus maksimisasi. Hanya kita perlu

mengalikan fungsi tujuan dengan (-1) sebelum membuat bentuk standar persamaan. Sebagai

contoh :

meminimumkan X1 + 2X2

kendala 1X1 + 3X2 > 11

2X1 + 1X2 > 9

X1, X2 > 0

Langkah pertama dalam menyelesaikan kasus di atas adalah mengubah kasus

minimisasi tersebut menjadi kasus maksimisasi dengan cara mengalikan fungsi tujuan dengan

(-1), sehingga kita memperoleh :

memaksimumkan –X1 – 2X2

kendala 1X1 + 3X2 > 11

2X1 + 1X2 > 9

X1, X2 > 0

Bentuk standar sistem persamaan di atas setelah dikurangi variabel surplus adalah

memaksimumkan –X1 – 2X2 + 0S1 + 0S2

kendala 1X1 + 3X2 – 1S1 = 11

2X1 + 1X2 – 1S2 = 9

X1, X2, S1, S2 > 0

Dengan menambah variabel artificial (karena kendala >) kita mendapatkan bentuk

tabel sistem persamaan tersebut sebagai berikut :

memaksimumkan –X1 – 2X2 + 0S1 – Ma1 – Ma2

kendala 1X1 + 3X2 – 1S1 + a1 = 11

2X1 + 1X2 – 1S2 + a2 = 9

X1, X2, S1, S2, a1, a2 > 0

Tabel simpleks awal yang diturunkan dari sistem persamaan di atas adalah

Kombinasi

ProdukCj -1X1 -2X2 0S1 0S2 -Ma1 -Ma2 Kuantitas

a1

a2

-M

-M

1

2

3

1

-1

0

0

-1

1

0

0

1

11

9

Zj

Cj - Zj

-3M

-1+3M

-4M

-2+4M

M

-M

M

-M

-M

0

-M

0

-20M

Hasil iterasi pertama :

Kombinasi

ProdukCj -1X1 -2X2 0S1 0S2 -Ma1 -Ma2 Kuantitas

a1

X1

-M

-M

0

1

5/2

1/2

-1

0

1/2

-1/2

1

0

-1/2

1/2

13/1

9/2

Zj

Cj - Zj

-1

0

-1/2-5/2M

-3/2+5/2M

M

-M

M

-M

-M

0

-1/2+1/2M

½-3/2M

-9/2-13/2M

Hasil iterasi kedua

Kombinasi

ProdukCj -1X1 -2X2 0S1 0S2 -Ma1 -Ma2 Kuantitas

X2

X1

-2

-1

0

1

1

0

-2/5

1/5

1/5

-3/5

2/5

-1/5

-1/5

3/5

13/5

16/5

Zj

Cj - Zj

-1

0

-2

0

3/5

-3/5

1/5

-1/5

-3/5

-M+3/5

1

-M-1

42/5

Karena semua nilai pada baris evaluasi neto Cj – Zj < 0 dan semua variabel artificial

sudah hilang berarti penyelesaian yang diperoleh sudah merupakan penyelesaian optimal,

yaitu X1 = 13/5 dan X2 = 16/5 dengan nilai fungsi tujuan sebesar 42/5.

KASUS KHUSUS

Kasus-kasus khusus yang dijumpai dalam menggunakan metode simpleks meliputi

hal-hal berikut :

1. Ketidaklayakan (infeasibility)

Kasus ini muncul bila tidak ada penyelesaian yang memenuhi semua kendala dan syarat

negativity, yaitu bila kriteria penghentian iterasi telah dicapai (semua nilai baris C j – Zj

< 0) tetapi masih terdapat satu atau lebih variabel artificial yang bernilai positif.

2. Ketidakterbatasan (unboundedness)

Kalau nilai fungsi tujuan yang diperoleh, khususnya dalam kasus maksimisasi,

sedemikian besar tetapi tetap memenuhi kendala, maka kasus demikian disebut

ketidakterbatasan. Dalam hal ini pasti terjadi kesalahan dalam memformulasikan masalah

dan metode simpleks pasti dapat menyingkapkan hal ini sebelum tabel simpleks terakhir

diperoleh. Hal ini dapat terjadi karena adanya ketidakterbatasan akan menyebabkan

aturan penentuan variabel yang dihilangkan tidak bekerja.

Misal, kita mempunyai tabel simpleks awal dari suatu kasus maksimisasi seperti terlihat

di bawah ini :

3. Alternate Optima

Alternate optima terjadi kalau terdapat dua atau lebih penyelesaian optimal. Hal ini baru

dapat diketahui setelah tabel simpleks terakhir diperoleh. Misal, tabel simpleks terakhir

dari suatu kasus adalah seperti terlihat di bawah ini. Karena nilai semua variabel pada

baris evaluasi neto lebih kecil atau sama dengan nol, berarti penyelesaian optimal sudah

tercapai : X1 = 15, X2 = 25, S2 = 12. Tetapi nilai variabel non dasar S3 adalah nol pada

baris evaluasi neto. Hal ini menunjukkan bahwa S3 dapat dimasukkan sebagai variabel

dasar tanpa merubah nilai penyelesaian optimal atau nilai fungsi tujuan yang diperoleh.

Dengan kata lain terjadi alternate optima.

Kombinasi

ProdukCj 1X1 2X2 0S1 0S2 -Ma1 Kuantitas

S1

S2

1

0

1

0

0

1

-1

0

0

1

1

0

5

2

Zj

Cj - Zj

1

0

0

-2

-1

1

0

0

1

-M-1

5

4. Degenerasi

Programasi linear dikatakan mengalami degenerasi bila satu atau lebih variabel dasar

bernilai nol. Misal, suatu kasus mempunyai tabel simpleks seperti di bawah ini :

Kombinasi

ProdukCj 10X1 9X2 0S1 0S2 0S3 0S4 Kuantitas Rasio Ri

S1

S2

X1

S4

0

0

10

0

0

0

1

0

16/30

1/2

12/3

22/120

1

0

0

0

0

1

0

0

-7/10

-1/2

1

-1/10

0

0

0

1

134,4

126

708

64,8

134,4(16/30)=252

126(1/2)=252

708(2/3)=1062

64,2(22/120)=350,2

Zj

Cj - Zj

10

0

20/3

7/3

0

0

0

0

10

-10

0

0

7080

Kita lihat bahwa hasil perhitungan rasio Ri menunjukkan bahwa rasio pertama dan kedua

hasilnya sama besar 252. Hal ini menunjukkan adanya degenerasi pada iterasi

berikutnya.

Hasil iterasi di atas menunjukan bahwa ketika variabel X2 dimasukkan kedalam

penyelesaian dan menghasilkan X2 sebesar 252 unit, kita tidak saja mengeluarkan S1 tetapi

juga membuat S2 sama dengan nol yang sekaligus berarti menghasilkan satu variabel dasar

Kombinasi

ProdukCj 1X1 2X2 0S1 0S2 -Ma1 Kuantitas

X1

S2

X2

7

0

10

1

0

0

0

0

1

1/3

-1/3

2/3

4/3

-2/3

6/3

0

1

0

15

12

25

Zj

Cj - Zj

7

0

10

0

27/3

-27/3

88/3

-88/3

0

0

355

Kombinasi

ProdukCj 10X1 9X2 0S1 0S2 0S3 0S4 Kuantitas

S1

S2

X1

S4

9

0

10

0

0

0

1

0

1

0

0

0

30/16

-15/16

-20/16

-11/32

0

1

0

0

-210/160

25/160

300/160

45/320

0

0

0

1

252

0

540

18

Zj

Cj - Zj

10

0

9

0

70/16

-70/16

0

0

111/16

-111/16

0

0

7668

yang bernilai nol. S2= 0 tidak akan terjadi bila penyelesaian optimal tercapai pada kendala ini.

Tetapi bila keadaan ini terjadi sebelum penyelesaian optimal tercapai, secara teoritis memang

dimungkinkan bagi algoritma metode simpleks untuk diulang. Artinya algoritma

memungkinkan terdapatnya beberapa alternatif di antara beberapa titik tak optimal pada

setiap iterasi dan karenanya tidak pernah akan tercapai penyelesaian optimal. Pengulangan

demikian sangat sulit dilakukan. Oleh karenanya kita tidak menyarankan langkah-langkah

dalam algoritma untuk menghilangkan kemungkinan degenerasi sejauh kita berpegangan

pada rasio Ri yang minimum untuk menentukan baris kunci.

RINGKASAN

Metode simpleks dapat digunakan untuk memecahkan kasus pengambilan keputusan

dengan banyak variabel. Proses penyusunan model matematika untuk fungsi tujuan dan

fungsi kendala sama seperti pada metode grafik. Sedang penentuan penyelesaian optimal

dilakukan dengan cara iterasi, yaitu proses perhitungan secara berulang.

Adapun langkah penyelesaian pengambilan keputusan dengan metode simpleks

meliputi :

1. Mengubah bentuk ketidaksamaan fungsi kendala menjadi bentuk standar dengan cara

menambah variabel slack atau variabel surplus.

2. Mengubah bentuk persamaan kendala di atas ke dalam suatu tabel yaitu tabel simpleks

untuk mendapatkan penyelesaian dasar awal.

3. Mengulangi penyelesaian dasar yang sstu ke penyelesaian dasar yang lain hingga

diperoleh penyelesaian dasar yang optimal. Penyelesaian optimal kasus maksimisasi

tercapai bila semua nilai pada baris evaluasi neto Cj- Zj lebih kecil atau sama dengan nol.

Syarat penyelesaian dengan metode simpleks adalah bahwa nilai sisi kanan fungsi

kendala harus bertanda positif. Fungsi kendala yang nilai sisi kanannya negatif harus diubah

dulu menjadi positif dengan cara mengalikan kedua sisi dengan (-1) dan sebagai akibatnya

mengubah arah tanda ketidaksamaan.

Kalau nilai penyelesaian dasar yang dihasilkan adalah negatif, maka harus

ditambahkan variabel artificial, ai, untuk dapat penyelesaian sistem persamaan kendala yang

ada. Adanya variabel artificial dalam penyelesaian menimbulkan kesulitan dalam

menginterpretasikan hasil, namun proses iterasi akan dapat menghilangkan variabel artificial

ini dari penyelesaian.

Penyelesaian kasus minimisasi dapat dilakukan dengan dua cara, yaitu mengubah

aturan yang digunakan pada kasus maksimisasi dan menggunakan logika matematika. Pada

cara pertama, penyelesaian optimal tercapai apabila baris C j - Zj tidak negatif. Hal ini

merupakan kebalikan dari penyelesaian kasus maksimisasi yang menyatakan bahwa

penyelesaian optimal tercapai apabila baris Cj - Zj negatif atau sama dengan 0. Sedang pada

cara kedua, digunakan logika bahwa meminimumkan Z adalah identik dengan

memaksimumkan –Z, sehingga aturan penyelesaian kasus maksimisasi dapat diterapkan

disini.

Kasus-kasus khusus yang dijumpai dalam menggunakan metode simpleks adalah

sama dengan yang terdapat pada metode grafik, yaitu meliputi ketidaklayakan (infeasibility),

ketidakterbatasan (unboundedness), alternate optimal dan degenerasi.