metode simpleks dalam bentuk tabel simplex method in ... · ②pemecahan untuk masalah minimisasi...

2/11/2008

1

TI2231 Penelitian Operasional I 1

Metode Simpleks dalam Bentuk Tabel

(Simplex Method in Tabular Form)

Kuliah 04


Materi Bahasan

① Metode simpleks dalam bentuk tabel

② Pemecahan untuk masalah minimisasi

③ Masalah-masalah komputasi dalam metode

simpleks

④ Penentuan basis layak

2/11/2008

2


① Metode simpleks dalam Bentuk Tabel


Contoh Rumusan Masalah PL

Memaksimumkan Z = 3x1 + 2x2

dengan pembatas-pembatas:

x1 + 2x2 6

2x1 + x2 8

– x1 + x2 1

x2 2

x1 ≥ 0, x2 ≥ 0

2/11/2008

3


Bentuk Kanonik



x1 + 2x2 + x3 = 6

2x1 + x2 + x4 = 8

– x1 + x2 + x5 = 1

x2 + x6 = 2

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0,


Representasi Tabel

untuk Solusi Basis Layak Awal

cB

3 2 0 0 0 0

Konstanta

x1 x2 x3 x4 x5 x6

0 x3 1 2 1 0 0 0 6

0 x4 2 1 0 1 0 0 8

0 x5 -1 1 0 0 1 0 1

0 x6 0 1 0 0 0 1 2

Basis

cj

c Baris

2/11/2008

4


Nilai Fungsi Tujuan

konstantadan vektor dariproduct inner BcZ

0

2

1

8

6

0,0,0,0

Z


Pemeriksaan Optimalitas

kanonik sistem dalam dengan berkaitan

yang kolomdan dari

j

B

jj x

cuctinner prodcc

Nilai fungsi tujuan relatif (profit relatif /ongkos relatif )

untuk variabel non basis:

Kondisi optimal terjadi apabila semua nilai koefisien

fungsi tujuan relatif untuk variabel non basis adalah tak

positif [untuk masalah maksimisasi]

2/11/2008

5


Nilai Fungsi Tujuan Relatif untuk

Variabel Non Basis

3

0

1

2

1

0,0,0,031

c

2

1

1

1

2

0,0,0,022

c


Tabel 1 (awal)

cB

3 2 0 0 0 0

Konstanta

x1 x2 x3 x4 x5 x6

0 x3 1 2 1 0 0 0 6

0 x4 2 1 0 1 0 0 8

0 x5 -1 1 0 0 1 0 1

0 x6 0 1 0 0 0 1 2

3 2 0 0 0 0 Z = 0

Basis

cj

c Baris

2/11/2008

6


Penentuan variabel yang masuk (entering

variable)

• Variabel non basis yang dipilih untuk masuk

ke basis (entering variable) variabel yang

memberikan peningkatan per unit pada Z yang

terbesar., yaitu variabel non basis yang

mempunyai nilai fungsi tujuan relatif terbesar

(paling positif untuk masalah maksimasi).



variable)

cB

3 2 0 0 0 0

Konstanta

x1 x2 x3 x4 x5 x6

0 x3 1 2 1 0 0 0 6

0 x4 2 1 0 1 0 0 8

0 x5 -1 1 0 0 1 0 1

0 x6 0 1 0 0 0 1 2

3 2 0 0 0 0 Z = 0

Basis

cj

c Baris

2/11/2008

7


Penentuan variabel yang keluar (leaving

variable)

• Untuk menentukan variabel basis yang akan

diganti (leaving variable), aturan rasio

minimum (minimum ratio rule) digunakan

untuk menentukan limit bagi tiap pembatas.



variable)

Nomor baris Variabel basisBatas atas bagi

x1

1 x3 6/1 = 6

2 x4 8/2 = 4 (minimum)

3 x5

4 x6

2/11/2008

8



variable)

cB

3 2 0 0 0 0

Konstanta

x1 x2 x3 x4 x5 x6

0 x3 1 2 1 0 0 0 6

0 x4 2 1 0 1 0 0 8

0 x5 -1 1 0 0 1 0 1

0 x6 0 1 0 0 0 1 2

3 2 0 0 0 0 Z = 0

Basis

cj

c Baris


Tabel 2

cB

3 2 0 0 0 0

Konstanta

x1 x2 x3 x4 x5 x6

0 x3 0 3/2 1 -1/2 0 0 2

3 x1 1 1/2 0 1/2 0 0 4

0 x5 0 3/2 0 1/2 1 0 5

0 x6 0 1 0 0 0 1 2

0 1/2 0 -3/2 0 0 Z = 12

Basis

cj

c Baris

2/11/2008

9



variable)

cB

3 2 0 0 0 0

Konstanta

x1 x2 x3 x4 x5 x6

0 x3 0 3/2 1 -1/2 0 0 2

3 x1 1 1/2 0 1/2 0 0 4

0 x5 0 3/2 0 1/2 1 0 5

0 x6 0 1 0 0 0 1 2

0 1/2 0 -3/2 0 0 Z = 12

Basis

cj

c Baris



variable)

cB

3 2 0 0 0 0

Konstanta

x1 x2 x3 x4 x5 x6

0 x3 0 3/2 1 -1/2 0 0 2

3 x1 1 1/2 0 1/2 0 0 4

0 x5 0 3/2 0 1/2 1 0 5

0 x6 0 1 0 0 0 1 2

0 1/2 0 -3/2 0 0 Z = 12

Basis

cj

c Baris

2/11/2008

10


Tabel 3 (Optimal)

cB

3 2 0 0 0 0

Konstanta

x1 x2 x3 x4 x5 x6

2 x2 0 1 2/3 -1/3 0 0 4/3

3 x1 1 0 -1/3 2/3 0 0 10/3

0 x5 0 0 -1 1 1 0 3

0 x6 0 0 -2/3 1/3 0 1 2/3

0 0 -1/3 -4/3 0 0 Z = 122/3

Basis

cj

c Baris


Output Tabel Simpleks dengan Software

(WinQSB) (1)

2/11/2008

11



(WinQSB) (2)


② Pemecahan untuk masalah minimisasi

2/11/2008

12


Masalah minimisasi

(Minimization problem)

• Koefisien fungsi tujuan relatif memberikan

informasi perubahan dalam nilai Z per satu

unit peningkatan variabel non basis.

• Nilai yang negatif pada koefisien fungsi tujuan

relatif untuk suatu variabel non basis

mengindikasikan bahwa jika variabel non basis

dinaikkan justru akan menyebabkan penurunan

pada nilai Z.


Masalah minimisasi

(Minimization problem))

• Oleh karena itu, untuk masalah minimasi, hanya variabel non basis yang mempunyai koefisien fungsi tujuan relatif yang negatif saja yang memenuhi syarat sebagai calon variabel yang masuk basis (entering variable).

• Variabel yang masuk basis (entering variable) adalah variabel yang mempunyai koefisien fungsi tujuan relatif paling negatif.

• Sehingga kondisi optimalitas pada masalah minimasi terjadi apabila semua nilai koefisien fungsi tujuan relatif variabel non basis adalah tak negatif.

2/11/2008

13


Masalah minimisasi


• Alternatif lain untuk memecahkan masalah

minimasi adalah dengan mengkonversikannya

menjadi masalah maksimasi dengan

memecahkan dengan metoda simpleks untuk

masalah maksimasi..

• Konversi dilakukan dengan mengalikan fungsi

tujuan untuk masalah minimasi dengan minus

satu.


Masalah minimisasi


Meminimumkan Z = 4x1 + x2


3x1 + x2 = 3

4x1 + 3x2 ≥ 6

x1 + 2x2 4

x1 ≥ 0, x2 ≥ 0

2/11/2008

14


Masalah minimisasi


Memaksimumkan Z’ = -4x1 - x2


3x1 + x2 = 3

4x1 + 3x2 ≥ 6

x1 + 2x2 4

x1 ≥ 0, x2 ≥ 0


Masalah Minimisasi


Solusi optimal kedua permasalahan akan sama,

tetapi nilai optimalnya berbeda dalam hal tanda.

Dengan kata lain:

Nilai minimum dari Z = - (Nilai maksimum dari Z’)

2/11/2008

15


③ Masalah-masalah komputasi dalam

metode simpleks


Masalah-masalah komputasi

• Nilai yang sama pada koefisien fungsi tujuan relatif yang terbesar Pilih variabel non basis yang akan masuk (entering variable) secara sebarang.

• Nilai yang sama pada rasio minimum untuk dua atau lebih pembatas

– Pilih variabel yang akan keluar (leaving variable) secara sebarang.

– Implikasi dari nilai yang sama ini adalah akan menghasilkan solusi yang degenerate.

2/11/2008

16


Masalah-masalah komputasi

• Solusi optimal alternatif (alternate optimal

solution)

• Solusi yang tak terbatas (unbounded solution)


Solusi optimum alternatif

(Alternate optimum solution)



x1 + 2x2 5

x1 + x2 4

x1 ≥ 0, x2 ≥ 0

2/11/2008

17


Bentuk kanonik



x1 + 2x2 + x3 = 5

x1 + x2 + x4 = 4

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0


Tabel 1

cB

2 4 0 0

Konstanta

x1 x2 x3 x4

0 x3 1 2 1 0 5

0x4 1 1 0 1 4

2 4 0 0 Z = 0

Basis

cj

c Baris

2/11/2008

18


Tabel 2 (Optimal)

cB

2 4 0 0

Konstanta

x1 x2 x3 x4

4 x2 1/2 1 1/2 0 5/2

0x4 1/2 0 -1/2 1 3/2

0 0 -2 0 Z = 10

Basis

cj

c Baris


Tabel 3 (Optimal alternatif)

cB

2 4 0 0

Konstanta

x1 x2 x3 x4

4 x2 0 1 1 -1 1

2x1 1 0 -1 2 3

0 0 -2 0 Z = 10

Basis

cj

c Baris

2/11/2008

19


Solusi secara grafis

x1

x2


Catatan

• Solusi optimal alternatif dalam tabel simpleks dapat diidentifikasi dengan melihat apakah terdapat koefisien fungsi tujuan relatif yang nol untuk variabel non basis pada tabel optimal.

• Dalam praktek, pengetahuan tentang optima alternatif adalah berguna karena ini memberikan manajemen untuk memilih solusi yang terbaik yang cocok dengan situasi tanpa terjadinya penurunan pada nilai fungsi tujuan.

2/11/2008

20


Solusi tak terbatas

(Unbounded solution)



x1 – x2 2

-3x1 + x2 3

x1 ≥ 0, x2 ≥ 0


Bentuk kanonik



x1 – x2 + x3 = 2

-3x1 + x2 + x4 = 3

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0

2/11/2008

21


Tabel 1

cB

2 3 0 0

Konstanta

x1 x2 x3 x4

0 x3 1 -1 1 0 2

0x4 -3 1 0 1 3

2 3 0 0 Z = 0

Basis

cj

c Baris


Tabel 2

cB

2 3 0 0

Konstanta

x1 x2 x3 x4

0 x3 -2 0 1 1 5

3x2 -3 1 0 1 3

11 0 0 -3 Z = 9

Basis

cj

c Baris

2/11/2008

22


Catatan

• Tabel 2 belum optimal

• Variabel non basis x1 dapat menjadi basis (entering variable) untuk menaikkan Z.

• Tetapi, aturan rasio minimum gagal karena tidak ada elemen positif pada kolom x1.

• Dengan kata lain, jika x1 meningkat maka kedua variabel basis x3 dan x2 juga meningkat sehingga tidak akan pernah mencapai nol sebagai batas peningkatan x1.


Catatan

• Ini berarti bahwa x1 dapat dinaikkan secara tak terbatas.

• Karena tiap peningkatan satu unit x1 akan meningkatkan Z sebesar 11 unit, maka fungsi tujuan dapat dinaikkan tak terbatas.

• Oleh karena itu, solusi bagi masalah LP adalah solusi tak terbatas (unbounded solution).

• Dengan demikian, kegagalan dalam aturan rasio minimum mengindikasikan bahwa masalah LP mempunyai solusi yang tak terbatas.

2/11/2008

23



x1

x2


Degenerasi (Degeneracy)

• Jika terjadi nilai yang sama pada rasio

minimum, maka pemilihan variabel yang

keluar basis (leaving variable) dapat dilakukan

sebarang.

• Akibatnya, satu atau lebih variabel basis akan

mempunyai nilai nol pada iterasi berikutnya.

• Dalam kasus ini, masalah LP dikatakan

mempunyai solusi yang degenerate.

2/11/2008

24


Degenerasi (Degeneracy)



x1 + 4x2 8

x1 + 2x2 4

x1 ≥ 0, x2 ≥ 0


Bentuk kanonik



x1 + 4x2 + x3 = 8

x1 + 2x2 + x4 = 4

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0

2/11/2008

25


Tabel 1

cB

3 9 0 0

Konstanta

x1 x2 x3 x4

0 x3 1 4 1 0 8

0x4 1 2 0 1 4

3 9 0 0 Z= 0

Basis

cj

c Baris


Tabel 2

cB

3 9 0 0

Konstanta

x1 x2 x3 x4

9 x2 1/4 1 1/4 0 2

0x4 1/2 0 -1/2 1 0

3/4 0 -9/4 0 Z = 18

Basis

cj

c Baris

2/11/2008

26


Tabel 3 (Optimal)

cB

3 9 0 0

Konstanta

x1 x2 x3 X4

9 x2 0 1 ½ -1/2 2

0x1 1 0 -1 2 0

0 0 -3/2 -3/2 Z = 18

Basis

cj

c Baris


Catatan

• Implikasi praktek dari degenerasi?

– Terdapat pembatas yang redundan.

2/11/2008

27



x1

x2


Catatan

• Dari sudut pandang teoritis, degenerasi

mempunyai implikasi:

– Fenomena cycling atau circling prosedur

simpleks mengulangi iterasi yang sama tanpa

memperbaiki nilai fungsi tujuan dan tanpa pernah

berhenti.

2/11/2008

28


④ Penentuan Basis Layak


Pendekatan untuk mendapatkan

solusi basis layak awal

• Trial-and-Error

– Variabel basis dipilih sebarang untuk tiap

pembatas

– Tidak efisien

• Penggunaan variabel semu (artificial variable)

2/11/2008

29


Contoh masalah LP



3x1 + x2 = 3

4x1 + 3x2 ≥ 6

x1 + 2x2 4

x1 ≥ 0, x2 ≥ 0


Bentuk standar



3x1 + x2 = 3

4x1 + 3x2 – x3 = 6

x1 + 2x2 + x4 = 4

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0

2/11/2008

30


Penambahan variabel semu

3x1 + x2 + x5 = 3

4x1 + 3x2 – x3 +x6 = 6

x1 + 2x2 + x4 = 4

x1, x2, x3, x4, x5, x6 ≥ 0

Variabel semu : x5, x6


Ide penggunaan variabel semu

• Variabel semu merupakan variabel tak negatif yang ditambahkan pada ruas kiri untuk tiap persamaan yang tidak mempunyai solusi basis awal.

• Variabel semu ini berperan sebagai variabel sisipan (slack variable) untuk memberikan solusi basis awal.

• Variabel semu tidak mempunyai arti fisik pada permasalahan awal.

2/11/2008

31


Ide penggunaan variabel semu

• Prosedur memaksa variabel semu untuk

bernilai nol jika kondisi optimal tercapai.

• Cara yang logis adalah memberikan penalti

pada variabel semu dalam fungsi tujuan.

• Pendekatan

– Metoda big M

– Metoda dua fasa


Metode Big M

• Variabel semu diberikan suatu penalti dengan suatu bilangan yang besar sekali pada fungsi tujuan.

• Metode simplex mencoba untuk memperbaiki fungsi tujuan dengan cara membuat variabel semu tidak ekonomis lagi untuk dipertahankan sebagai variabel basis dengan nilai yang positif.

• Untuk masalah

– Minimiasi : M

– Maksimasi: -M

dimana M adalah bilangan yang sangat besar

2/11/2008

32


Metode big M

Meminimumkan Z = 4x1 + x2 + Mx5 + Mx6


3x1 + x2 + x5 = 3

4x1 + 3x2 – x3 +x6 = 6

x1 + 2x2 + x4 = 4

x1, x2, x3, x4, x5, x6 ≥ 0


cB

4 1 0 0 M M

Konstanta

x1 x2 x3 x4 x5 x6

M x5 3 1 0 0 1 0 3

M x6 4 3 -1 0 0 1 6

0 x4 1 2 0 1 0 0 4

Basis

cj

C Baris

2/11/2008

33


Nilai fungsi tujuan

konstantadan vektor dariproduct inner BcZ

MMMZ 9

4

6

3

0,,


Pemeriksaan optimalitas

kanonik sistem dalam dengan berkaitan

yang kolomdan dari

j

B

jj x

cuctinner prodcc

Nilai fungsi tujuan relatif (profit relatif /ongkos relatif )

untuk variabel non basis:

Kondisi optimal terjadi apabila semua nilai koefisien

fungsi tujuan relatif untuk variabel basis adalah tak

positif [untuk masalah maksimasi] atau tak negatif

[untuk masalah minimasi]

2/11/2008

34


Nilai fungsi tujuan relatif untuk variabel non

basis

MMMc 74

1

4

3

0,,41

MMMc 41

2

3

1

0,,12

MMMc

0

1

0

0,,03


Tabel 1

cB

4 1 0 0 M M

Konstanta

x1 x2 x3 x4 x5 x6

M x5 3 1 0 0 1 0 3

M x6 4 3 -1 0 0 1 6

0 x4 1 2 0 1 0 0 4

4 – 7M 1 – 4M M 0 0 0 Z = 9M

Basis

cj

c Baris

2/11/2008

35


Tabel 2

cB

4 1 0 0 M M

Konstanta

x1 x2 x3 x4 x5 x6

4 x1 1 1/3 0 0 1/3 0 1

M x6 0 5/3 -1 0 -4/3 1 2

0 x4 0 5/3 0 1 -1/3 0 3

0-1/3

-5/3MM 0

-4/3

+7/3M0

Z =

4 + 2M

Basis

cj

c Baris


Tabel 3

cB

4 1 0 0 M M

Konstanta

x1 x2 x3 x4 x5 x6

4 x1 1 0 1/5 0 3/5 -1/5 3/5

1 x2 0 1 -3/5 0 -4/5 3/5 6/5

0 x4 0 0 1 1 1 -1 1

0 0 -1/5 0-8/5

+ M

1/5

+ MZ = 18/5

Basis

cj

c Baris

2/11/2008

36


Tabel 4 (Optimal)

cB

4 1 0 0 M M

Konstanta

x1 x2 x3 x4 x5 x6

4 x1 1 0 0 -1/5 2/5 0 2/5

1 x2 0 1 0 3/5 -1/5 0 9/5

0 x3 0 0 1 1 1 -1 1

0 0 0 1/5-7/5

+ MM Z = 17/5

Basis

cj

c Baris



(WinQSB) (1)

2/11/2008

37



(WinQSB) (2)


Metoda dua-fase (1)

• Fase I

– Mendapatkan solusi basis layak awal pada masalah original.

– Penghilangan variabel semu.

– Fungsi tujuan semu merupakan jumlah dari variabel semu yang diminimasi.

– Jika nilai fungsi tujuan sama dengan nol, maka semua variabel semu bernilai nol dan solusi basis layak diperoleh bagi masalah original.

– Jika nilai minimum fungsi tujuan adalah positif, maka paling sedikit terdapat satu variabel yang positif dan ini berarti masalah original adalah tak layak, dan algoritma berhenti.

2/11/2008

38


Metoda dua-fase (2)

• Fase II

– Solusi basis layak yang diperoleh pada Fase I

dioptimasi terhadap fungsi tujuan origina.

– Tabel akhir pada Fase I menjadi tabel awal pada

Fase II dengan perubahan pada fungsi tujuan.


Metoda dua-fase (Fase I)

Meminimumkan W = x5 + x6


3x1 + x2 + x5 = 3

4x1 + 3x2 – x3 +x6 = 6

x1 + 2x2 + x4 = 4

x1, x2, x3, x4, x5, x6 ≥ 0

2/11/2008

39


Tabel 1 [Fase I]

cB

0 0 0 0 1 1

Konstanta

x1 x2 x3 x4 x5 x6

1 x5 3 1 0 0 1 0 3

1 x6 4 3 -1 0 0 1 6

0 x4 1 2 0 1 0 0 4

– 7 – 4 1 0 0 0 W = 9

Basis

cj

c Baris


Tabel 2 [Fase I]

cB

0 0 0 0 1 1

Konstanta

x1 x2 x3 x4 x5 x6

0 x1 1 1/3 0 0 1/3 0 1

1 x6 0 5/3 -1 0 -4/3 1 2

0 x4 0 5/3 0 1 -1/3 0 3

0 -5/3 1 0 7/3 0 W = 2

Basis

cj

c Baris

2/11/2008

40


Tabel 3 [Fase I]

cB

0 0 0 0 1 1

Konstanta

x1 x2 x3 x4 x5 x6

0 x1 1 0 1/5 0 3/5 -1/5 3/5

0 x2 0 1 -3/5 0 -4/5 3/5 6/5

0 x4 0 0 1 1 1 -1 1

0 0 0 0 1 1 W = 0

Basis

cj

c Baris


Tabel 1 [Fase II]

cB

4 1 0 0

Konstanta

x1 x2 x3 x4

4 x1 1 0 1/5 0 3/5

1 x2 0 1 -3/5 0 6/5

0 x4 0 0 1 1 1

0 0 -1/5 0 Z = 18/5

Basis

cj

c Baris

2/11/2008

41


Tabel 2 [Fase II] (Optimal)

cB

4 1 0 0

Konstanta

x1 x2 x3 x4

4 x1 1 0 0 -1/5 2/5

1 x2 0 1 0 3/5 9/5

0 x4 0 0 1 1 1

0 0 0 1/5 Z = 17/5

Basis

cj

c Baris


Solusi tak layak (infeasible solution)

• Dengan metoda big M

– Pada tabel optimal, satu atau lebih variabel semu

tetap sebagai variabel basis

• Dengan metoda dua-fase

– Pada tabel optimal pada fase I, nilai fungsi

tujuannya adalah positif, dimana satu atau lebih

variabel semu sebagai basis)

2/11/2008

42


Contoh masalah LP



2x1 + x2 2

3x1 + 4x2 ≥ 12

x1 ≥ 0, x2 ≥ 0


Bentuk standar



2x1 + x2 + x3 = 2

3x1 + 4x2 - x4 = 12

x1, x2, x3, x4 ≥ 0

2/11/2008

43


Penambahan variabel semu

2x1 + x2 + x3 = 2

3x1 + 4x2 - x4 + x5 = 12

x1, x2, x3, x4, x5 ≥ 0


Metode big M

Memaksimumkan Z = 3x1 + 2x2 – Mx5


2x1 + x2 + x3 = 2

3x1 + 4x2 - x4 + x5 = 12

x1, x2, x3, x4, x5 ≥

2/11/2008

44


Tabel 1

cB

3 2 0 0 -M

Konstanta

x1 x2 x3 x4 x5

0 x3 2 1 1 0 0 2

-M x5 3 4 0 -1 1 12

3 + 3M 2 + 4M 0 -M 0 Z = -12M

Basis

cj

c Baris


Tabel 2

cB

3 2 0 0 -M

Konstanta

x1 x2 x3 x4 x5

0 x4 2 1 1 0 0 2

-M x5 -5 0 -4 -1 1 4

-1 -5M 0 -2 – 4M -M 0Z =

4 – 4M

Basis

cj

c Baris

metode simpleks dalam bentuk tabel simplex method in ... · ②pemecahan untuk masalah minimisasi...

Documents