berapa banyak solusi basis yang terjadi ?!!!
DESCRIPTION
Sambungan metode simplex…. Berapa banyak solusi basis yang terjadi ?!!!. Kemungkinan Banyaknya Solusi Basis Yg Dapat Dibuat. Mis. n = jumlah variabel m = jumlah kendala Sesudah penambahan variabel slack , terdapat :. (n + m)! - PowerPoint PPT PresentationTRANSCRIPT
Emirul Bahar - Riset Operasional 1 1
Berapa banyak solusi basis yang terjadi ?!!!
Sambungan metode simplex…
Emirul Bahar - Riset Operasional 1 2
Mis. n = jumlah variabel m = jumlah kendala
Sesudah penambahan variabel slack, terdapat :
(n + m)! n! m! cara untuk mendapatkan kemungkinan solusi basis.
Contoh: Jika n = 2 dan m = 3, maka 5!/(2! 3!) = 10.
Kemungkinan Banyaknya Solusi Basis Yg Dapat Dibuat
Emirul Bahar - Riset Operasional 1 3
Beberapa Istilah
• Solusi Augmented : solusi masalah sesudah variabel slack ditambahkan.
• Solusi Basis : solusi titik sudut augmented dengan mengatur sejumlah menjadi nol dan menyelesaikan sisa variabel lainnya.
• Solusi Layak Basis (SLB) : solusi basis yang layak menjadi kandidat solusi optimal
• Variabel Basis : variabel yang diselesaikan dalam solusi basis
• Variabel Non-Basis : Variabel yg sama dengan nol pada solusi basis
Emirul Bahar - Riset Operasional 1 4
Outline Algoritma Simplex
• Mulai pada Solusi Layak Basis (SLB) / basic feasible solution (BFS) (biasanya pd titik asal)
• Pindah ke SLB yg lebih baik
– Mengembangkan fungsi tujuan
• Berhenti ketika bertemu SLB yg lebih baik dibandingkan seluruh SLB yg ada
– Solusi Optimal ditemukan
Ketemu…!
Emirul Bahar - Riset Operasional 1 5
Tabel Simplex
VarPers. Basis z x1 x2 x3 x4 x5 Solusi
0 z 1 -6 -4 0 0 0 0
1 x3 0 1 1 1 0 0 12
2 x4 0 1 -2 0 1 0 6
3 x5 0 0 1 0 0 1 8
Max z - 6x1 - 4x2 = 0Subj. to:
x1 + x2 + x3 = 12 x1 - 2x2 + x4 = 6
x2 + x5 = 8
Emirul Bahar - Riset Operasional 1 6
VarPers. Basis z x1 x2 x3 x4 x5 Solusi0 z 1 -6 -4 0 0 0 0
1 x3 0 1 1 1 0 0 12
2 x4 0 1 -2 0 1 0 6
3 x5 0 0 1 0 0 1 8
Algoritma Simplex
Step 1: Pilih sebuah variabel baru untuk masuk basis.
Pilihlah variabel non-basis yg punya nilai negatif terbesar
z = 6x1 + 4x2
Emirul Bahar - Riset Operasional 1 7
VarPers. Basis z x1 x2 x3 x4 x5 Solusi
0 z 1 -6 -4 0 0 0 0
1 x3 0 1 1 1 0 0 12
2 x4 0 1 -2 0 1 0 6
3 x5 0 0 1 0 0 1 8
Step 2a: Pilih sebuah variabel basis untuk meninggalkan basis
Emirul Bahar - Riset Operasional 1 8
VarPers. Basis z x1 x2 x3 x4 x5 Solusi0 z 1 -6 -4 0 0 0 0
1 x3 0 1 1 1 0 0 12
2 x4 0 1 -2 0 1 0 6
3 x5 0 0 1 0 0 1 8
Step 2b: Pilih sebuah variabel basis untuk meninggalkan basis
Pilihlah variabel basis yg punya rasio paling kecil pd pembagian solusi terhadap koefisien positif dari variabel non-basis yg akan masuk
Ratio
12/1
6/1
Emirul Bahar - Riset Operasional 1 9
VarPers. Basis z x1 x2 x3 x4 x5 Solusi
0 z 1 -6 -4 0 0 0 0
1 x3 0 1 1 1 0 0 12
2 x4 0 1 -2 0 1 0 6
3 x5 0 0 1 0 0 1 8
Step 2c: Select a basic variable to leave the basis.
Pilihlah variabel basis yg punya rasio paling kecil pd pembagian solusi terhadap koefisien positif dari variabel non-basis yg akan masuk
Ratio
12/1
6/1
pivot point
1x1 - 2x2 + x4 = 6
Emirul Bahar - Riset Operasional 1 10
VarPers. Basis z x1 x2 x3 x4 x5 Solusi0 z
1 x3
2 x1
3 x5
VarPers. Basis z x1 x2 x3 x4 x5 Solusi0 z 1 -6 -4 0 0 0 0
1 x3 0 1 1 1 0 0 12
2 x4 0 1 -2 0 1 0 6
3 x5 0 0 1 0 0 1 8
Step 3e: Gunakan operasi baris untuk menentukan solusi basis yg baru.
0 1 -2 0 1 0 6
0 0 1 0 0 1 8
0 0 3 1 -1 0 6
1 0 -16 0 6 0 36
Emirul Bahar - Riset Operasional 1 11
(4,8)8
12
12
-3
(10,2)z
z
Max z = 6x1 + 4x2
Subj. to:
x1 + x2 <= 12 x1 -2x2 <= 6
x2 <= 8
6x1
x2
Emirul Bahar - Riset Operasional 1 12
VarPers. Basis z x1 x2 x3 x4 x5 Solusi
0 z 1 0 -16 0 6 0 36
1 x3 0 0 3 1 -1 0 6
2 x1 0 1 -2 0 1 0 6
3 x5 0 0 1 0 0 1 8
Iterasi selanjutnyaz = 6x1 + 4x2
Sekarang kamu ambil lagi variabel baru yang akan
masuk basis !
Emirul Bahar - Riset Operasional 1 13
VarPers. Basis z x1 x2 x3 x4 x5 Solusi0 z 1 0 -16 0 6 0 36
1 x3 0 0 3 1 -1 0 6
2 x1 0 1 -2 0 1 0 6
3 x5 0 0 1 0 0 1 8
Iterasi selanjutnya
Pilihlah variabel non-basis yg punya nilai negatif terbesar.
z = 6x1 + 4x2
Emirul Bahar - Riset Operasional 1 14
VarPers. Basis z x1 x2 x3 x4 x5 Solusi
0 z 1 0 -16 0 6 0 36
1 x3 0 0 3 1 -1 0 6
2 x1 0 1 -2 0 1 0 6
3 x5 0 0 1 0 0 1 8
Iterasi selanjutnya z = 6x1 + 4x2
Ratio
6/3
8/1
Tentukan rasio minimum
Emirul Bahar - Riset Operasional 1 15
VarPers. Basis z x1 x2 x3 x4 x5 Solusi
0 z 1 0 -16 0 6 0 36
1 x3 0 0 3 1 -1 0 6
2 x1 0 1 -2 0 1 0 6
3 x5 0 0 1 0 0 1 8
Iterasi selanjutnya z = 6x1 + 4x2
Ratio
6/3
8/1
Find minimum ratio
Pivot point
Emirul Bahar - Riset Operasional 1 16
VarPers. Basis z x1 x2 x3 x4 x5 Solusi0 z
1 x2
2 x1
3 x5
VarPers. Basis z x1 x2 x3 x4 x5 Solusi
0 z 1 0 -16 0 6 0 36
1 x3 0 0 3 1 -1 0 6
2 x1 0 1 -2 0 1 0 6
3 x5 0 0 1 0 0 1 8
0 1 0 2/3 1/3 0 10
0 0 0 -1/3 1/3 1 6
0 0 1 1/3 -1/3 0 2
1 0 0 16/3 2/3 0 68
Iterasi selanjutnya
Emirul Bahar - Riset Operasional 1 17
VarPers. Basis z x1 x2 x3 x4 x5 Solusi0 z
1 x2
2 x1
3 x5
0 1 0 2/3 1/3 0 10
0 0 0 -1/3 1/3 1 6
0 0 1 1/3 -1/3 0 2
1 0 0 16/3 2/3 0 68
Iterasi selanjutnyaJelas, bahwa
solusinya sudah optimal…
Apa sih yang anda maksud dengan
optimal?
Emirul Bahar - Riset Operasional 1 18
(4,8)8
12
12
-3
(10,2)z
z
Max z = 6x1 + 4x2
Subj. to:
x1 + x2 <= 12 x1 -2x2 <= 6
x2 <= 8
6x1
x2
Pd x1 = 10 & x2 = 2, nilai optimalnya adalah 68
Ini lho... Gambaran optimalmya…
19Emirul Bahar - Riset Operasional 1
Selanjutnya… ?Gampaaanng!, Berani latihan, berani bertanya
Nantikan materi
berikutnya…!
Emirul Bahar - Riset Operasional 1 20
Gitu aja kok dipikirin !