...

Pemrograman Linier (5) - Kasus khusus dalam metode simpleks

by user

on
Category: Documents
1

views

Report

Comments

Transcript

Pemrograman Linier (5) - Kasus khusus dalam metode simpleks
Pemrograman Linier (5)
Kasus khusus dalam metode simpleks
Ahmad Sabri
Universitas Gunadarma, Indonesia
Terdapat empat kasus khusus dalam metode simpleks:
1
Degeneracy
2
Alternate optima
3
Solusi tak berbatas
4
Tidak ada solusi layak
2
Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (5)
2 / 14
Degeneracy
Degeneracy terjadi jika terdapat variabel basis dengan rasio minimum yang
sama, sehingga pada iterasi berikutnya, paling sedikit sebuah variabel basis
bernilai nol.
Akibat:
cycling atau circling
kendala redundant (kendala berlebih)
3
Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (5)
3 / 14
Degeneracy
Degeneracy terjadi jika terdapat variabel basis dengan rasio minimum yang
sama, sehingga pada iterasi berikutnya, paling sedikit sebuah variabel basis
bernilai nol.
Akibat:
cycling atau circling
kendala redundant (kendala berlebih)
3
Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (5)
3 / 14
Contoh
Maks Z = 3x1 + 9x2
Dengan kendala:
x1 + 4x2
≤ 8
x1 + 2x2
≤ 4
x1 , x2 ≥ 0
Tentukan solusi optimalnya dengan metode simpleks.
4
Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (5)
4 / 14
Tabel simpleks lengkap
Berikut ini adalah tabel simpleks untuk seluruh iterasi yang dilakukan:
Itr.
0
1
2
No.
(0)
(1)
(2)
(0)
(1)
(2)
(0)
(1)
(2)
Basis
Z
s1
s2
Z
x2
s2
Z
x2
x1
Z
1
0
0
1
0
0
1
0
0
x1
-3
1
1
− 34
1
4
1
2
0
0
1
x2
-9
4
2
0
1
0
0
1
0
s1
0
1
0
9
4
1
4
−1
2
3
2
1
2
−1
s2
0
0
1
0
0
1
3
2
− 12
2
Solusi
0
8
4
18
2
0
18
43
0
Rasio
5
Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (5)
5 / 14
6
Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (5)
6 / 14
Alternate optima
Alternate optima terjadi jika fungsi objektif paralel dengan salah satu
kendala binding dan non redundant, sehingga hal ini mengakibatkan
diperolehnya beberapa solusi optimal.
Pada tabel simpleks optimal, keberadaan alternate optima ditunjukkan
dengan adanya variabel non basis x yang bernilai nol. Jika iterasi
dilanjutkan dengan menjadikan x sebagai variabel masuk, maka akan
didapat solusi lain yang memberikan nilai Z yang sama.
7
Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (5)
7 / 14
Alternate optima
Alternate optima terjadi jika fungsi objektif paralel dengan salah satu
kendala binding dan non redundant, sehingga hal ini mengakibatkan
diperolehnya beberapa solusi optimal.
Pada tabel simpleks optimal, keberadaan alternate optima ditunjukkan
dengan adanya variabel non basis x yang bernilai nol. Jika iterasi
dilanjutkan dengan menjadikan x sebagai variabel masuk, maka akan
didapat solusi lain yang memberikan nilai Z yang sama.
7
Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (5)
7 / 14
Contoh
Maks Z = 2x1 + 4x2
Dengan kendala:
x1 + 2x2
≤ 5
x1 + x2
≤ 4
x1 , x2 ≥ 0
Tentukan solusi optimalnya dengan metode simpleks.
8
Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (5)
8 / 14
Tabel simpleks lengkap
Berikut ini adalah tabel simpleks untuk seluruh iterasi yang dilakukan:
Itr.
0
1
2
No.
(0)
(1)
(2)
(0)
(1)
(2)
(0)
(1)
(2)
Basis
Z
s1
s2
Z
x2
s2
Z
x2
x1
Z
1
0
0
1
0
0
1
0
0
x1
-2
1
1
0
1
2
1
2
0
0
1
x2
-4
2
1
0
1
0
0
1
0
s1
0
1
0
0
1
2
− 12
2
1
−1
s2
0
0
1
2
0
1
0
-1
2
Solusi
0
5
4
10
Rasio
5
2
3
2
10
1
3
9
Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (5)
9 / 14
10
Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (5)
10 / 14
Solusi tak berbatas
Solusi tak berbatas terjadi jika nilai dari variabel-variabel dapat diperbesar
tanpa melanggar satupun kendala. Hal ini berarti bahwa daerah solusi
tidak berbatas unbounded.
11
Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (5)
11 / 14
Contoh
Maks Z = 2x1 + x2
Dengan kendala:
x1 − x2
≤ 10
2x1
≤ 40
x1 , x2 ≥ 0
Tentukan solusi optimalnya dengan metode simpleks.
12
Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (5)
12 / 14
Solusi tak layak
Terjadi jika model PL memiliki kendala yang tidak konsisten.
13
Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (5)
13 / 14
Contoh
Maks Z = 3x1 + 2x2
Dengan kendala:
2x1 + x2
≤ 2
3x1 + 4x2 ≥ 12
x1 , x2 ≥ 0
Tentukan solusi optimalnya dengan metode simpleks.
14
Ahmad Sabri (Universitas Gunadarma, Indonesia)
Pemrograman Linier (5)
14 / 14
Fly UP