operations research lecture 5 problem of simplex method and special cases of lp

Operations ResearchMAM1627

Semester Genap tahun 2013/2014

M. Ziaul Arif

[email protected]

Jurusan Matematika - FMIPA

Lecture 5 : Problem of Simplex method and

Special cases of LP

Universitas Jember 2013-2014 Operation Research 1

Masalah dalam metode Simpleks

1.Terdapat lebih dari 1 kolom pivot : terdapat

kolom yang mempunyai nilai Zj-Cj paling

negatif yang sama

– Solusi : Pilih salah satu secara Sembarang kolom

yang akan di pakai kolom pivot.

– Hasil : Akan menghasilkan fungsi tujuan dan

variable keputusan yang sama


Masalah dalam metode Simpleks

2. Terdapat lebih dari 1 baris pivot : terdapat

lebih dari 1 baris yang mempunyai rasio yang

sama

– Solusi : Pilih salah satu secara Sembarang baris

yang akan di pakai untuk menentukan pivot.

– Hasil : Akan menghasilkan fungsi tujuan dan

variable keputusan yang sama


Contoh

Fungsi tujuan : Maksimumkan

3 1 9 2

F. Kendala

1 4 2 8

1 2 2 4

1, 2 0

Z x x

x x

x x

x x

= +

+ ≤

+ ≤

≥


Kasus Khusus dalam metode Simpleks

• Multiple optimal solution

• Solusi fungsi tujuan takterbatas

• Degenerasi

• Solusi tak layak


Multiple optimal solution

• Jika fungsi tujuan sejajar/berimpit dengan

suatu kendala, maka akan terjadi nilai optimal

yang sama pada lebih dari satu titik solusi

Contoh :

02,1

421

5221

Kendala F.

2412

tujuanFungsi

≥

≤+

≤+

+=

xx

xx

xx

xxZ


x1 2 3 4 5

y

1

2

3

4

5

Point of Intersection

( 3 , 1 )

2x+4y=10

x+2y<=5


Multiple Optimum solution pada simpleks

• Untuk Mengetahui masalah tersebutmempunyai multiple optimum solution atautidak, dapat dilihat pada tabel terakhir.Apabila dalam tablo tersebut terdapatvariable nonbasis yang mempunyai nilai Zj-Cj=0, Maka ada pilihan variable keputusanyang lain.

• Cara : dengan memasukkan variable nonbasistersebut ke dalam variable basis.


Contoh

CBCj 2 4 0 0 RHS

Rasio

Basis x1 x2 S1 S2

0 S1 1 2 1 0 5 2.5

0 S2 1 1 0 1 4 4

Zj-Cj -2 -4 0 0 0

CBCj 2 4 0 0 RHS

RasioBasis x1 x2 S1 S2

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

0 S2 1/2 0 - 1/2 1 1 1/2 3

Zj-Cj 0 0 2 0 10


Contoh

CBCj 2 4 0 0 RHS

Basis x1 x2 S1 S2

4 x2 0 1 1 -1 1

2 x1 1 0 -1 2 3

Zj-Cj 0 0 2 0 10


Multiple Optimum solution pada simpleks

• Pengetahuan akan optimum alternatif sangat

bermanfaat karena akan memberikan

kesempatan untuk memilih solusi yang paling

cocok dengan situasi yang dihadapi


Solusi F. Tujuan Tak terbatas

• Terjadi jika memiliki daerah feasible yang tak

terbatas, akibatnya nilai fungsi tujuan dapat

bertambah tanpa pernah mencapai batas

kendala.

• Sebab ketidakterbatasan : Karena model PL

yang salah

• Satu atau lebih kendala tidak diikut sertakan

• Parameter tidak diduga dengan benar


Solusi Fungsi tujuan Tak terbatas

• Contoh


2 1 2

F. Kendala

1 2 10

2 1 40

1, 2 0

Z x x

x x

x

x x

= +

− ≤

≤

≥


Solusi Tak terbatas

x10 20 30 40

y

2

4

6

8

10

12

14


Solusi F. tujuan tak terbatas dalam Simpleks

• Untuk mengetahui solusi fungsi tujuan

takterbatas dalam simplek, jika ditandai

dengan tidak adanya Rasio yang positif (tidak

ada yang bisa dipilih)

• Hentikan!! (Terjadi Kesalahan)


Contoh

CBCj 2 1 0 0 RHS


0 S1 1 -1 1 0 10 10

0 S2 2 0 0 1 40 20

Zj-Cj -2 -1 0 0 0

CBCj 2 1 0 0 RHS


2 x1 1 0 0 1/2 20 -

1 x2 0 1 -1 1/2 10 -

Zj-Cj 0 0 -1 1 1/2 50


Degenerasi

• Dalam penerapan feasible condition, jika

terjadi rasio kembar, maka pilih secara

sembarang. Jika ini terjadi, satu atau lebih

variable basis akan sama dengan nol (b=0)

pada iterasi berikutnya. Dalam kasus ini solusi

mengalami degenerasi.

• Solusi : lanjutkan sampai memenuhi syarat

kondisi optimal


Implikasi degenerasi

• Fenomena perputaran (cycling) : dengan

melanjutkan iterasi, nilai Z tidak akan

membaik.

• Memberikan nilai identik pada variable

keputusan


Contoh


3 1 9 2

F. Kendala

1 4 2 8

1 2 2 4

1, 2 0

Z x x

x x

x x

x x

= +

+ ≤

+ ≤

≥


Contoh

CBCj 3 9 0 0 RHS


0 S1 1 4 1 0 8 2

0 S2 1 2 0 1 4 2

Zj-Cj -3 -9 0 0 0

CBCj 3 9 0 0 RHS


9 x2 1/4 1 1/4 0 2 8

0 S2 1/2 0 -1/2 1 0 0

Zj-Cj -3/4 0 9/4 0 18


Contoh

CBCj 3 9 0 0 RHS


9 x2 0 1 1/2 -1/2 2 -

3 x1 1 0 -1 2 0 -

Zj-Cj 0 0 3/2 3/2 18


operations research lecture 5 problem of simplex method and special cases of lp

Documents