modul 3 simplek
TRANSCRIPT
Riset Operasi Prayudi Modul 3 : Metode Simplek 1
Bentuk standart programa linier (primal) mempunyai sifat-sifat sebagai berikut :
Modul III : Metode Simpleks
1. Semua batasan adalah persamaan (dengan sisi kanan non negatif, jika model tersebut dipecahkan dengn metode simpleks primal)
2. Semua variabel adalah non negatif3. Fungsi tujuan dapat berupa maksimum atau minimum
Metode simpleks primal dimulai dari pemecahan dasar yang layak (titik ekstrim) dan berlanjut berulang melalui pemecahan dasar layak berikutnya sampai diperoleh titik optimum
Metode simpleks untuk kasus minimum dapat diselesaikan dengan metode Teknik M (atau metode pinalti), dan metode dua tahap (dua fasa)
Riset Operasi Prayudi Modul 3 : Metode Simplek 2
Langkah-langkah metode simpleks primal adalah sebagai berikut :1. Ubahlah bentuk batasan model pertidaksamaan menjadi persamaan,
dengan menambahkan variabel slack pada setiap batasan. 2. Bentuklah tabel awal simplek untuk solusi fisibel dasar dengan jumlah
kolom sebanyak jumlah variabel (termasuk variabel slack) ditambah tiga, dan jumlah kolom sebanyak jumlah batasan ditambah tiga baris.
3. Memilih variabel non dasar masuk (EV) yakni kolom yang memiliki nilai koefisien z negatif terbesar.
4. Memilih variabel dasar keluar (LV) dengan cara membagi nilai ruas kanan dengan nilai kolom EV dan memilih baris dg rasio nonnegatif terkecil.
5. Menghitung nilai baris pemutar (persamaan pivot) dengan rumus : pers pivot baru=pers pivot lama / elemen pivot6. Menghitung nilai baris persamaan baru dengan rumus : pers baru=pers lama –(koef kolom EV) x (pers pivot baru)7. Menentukan apakah solusi sudah optimum. Tabel dikatakan optimum,
bilamana semua koefisien fungsi tujuan z semuanya positip. Jika masih tedapat yang negatif ulangi kembali langkah 3 s.d 6.
Riset Operasi Prayudi Modul 3 : Metode Simplek 3
Contoh :Maksimumkan, z = 150x1+120x2Batasan model : 2x1+ 3x2 ≤ 210 2x1 + 6x2 ≤ 360 6x1 + 2x2 ≤ 420 x1 ≤ 65 x2 ≤ 55
Bentuk persamaan awal model metode simplek adalah :
(0) z – 150 x1 – 120 x2 – 0 s1 – 0 s2 – 0 s3 – 0 s4 – 0 s5 = 0(1) 2 x1 + 3 x2 + s1 = 210(2) 2 x1 + 6 x2 + s2 = 360(3) 6 x1 + 2 x2 + s3 = 420(4) x1 + s4 = 65(5) x2 + s5 = 55
Riset Operasi Prayudi Modul 3 : Metode Simplek 4
Variabel Basis
Koefisien dariRuas Kanan
Rasioz x1 x2 s1 s2 s3 s4 s5
z 1 -150 -120 0 0 0 0 0 0
s1 0 2 3 1 0 0 0 0 210 105
s2 0 2 6 0 1 0 0 0 360 180
s3 0 6 2 0 0 1 0 0 420 70
s4 0 1 0 0 0 0 1 0 65 65
s5 0 0 1 0 0 0 0 1 55
Tabel awal simpleks : Iterasi pertama
EV = x1LV = s4
Solusi : z=0 x1=0 ; s1=210 ; s3=420 x2=0 ; s2=180 ; s4=65 ; s5=55
Uji optimasi : Terdapat nilai koefisien z negatif, tabel belum optimum
Riset Operasi Prayudi Modul 3 : Metode Simplek 5
Operasi elementer iterasi kedua :
(i) Persamaan pivot (s4/x1) :
(ii) Persamaan fungsi tujuan (z) :
(iii) Persamaan batasan (s1) :
(iv) Persamaan batasan (s2) :
(v) Persamaan batasan (s3) :
(vi) Persamaan batasan (s5) :
1)L(H
(B)H 44
(L)H1
150(L)H(B)H 400
(L)H12
-(L)H(B)H 411
(L)H12
-(L)H(B)H 422
(L)H16
-(L)H(B)H 433
(L)H10
-(L)H(B)H 455
Riset Operasi Prayudi Modul 3 : Metode Simplek 6
Variabel Basis
Koefisien dariRuas Kanan
Rasioz x1 x2 s1 s2 s3 s4 s5
z 1 0 -120 0 0 0 150 0 9750
s1 0 0 3 1 0 0 -2 0 80 26,67
s2 0 0 6 0 1 0 -2 0 230 38,33
s3 0 0 2 0 0 1 -6 0 30 15
x1 0 1 0 0 0 0 1 0 65 -
s5 0 0 1 0 0 0 0 1 55 55
Hasil iterasi kedua :
Solusi : z=9750 x1=65 ; s1=80 ; s3=30 x2=0 ; s2=230; s4=0 ; s5=55
Uji optimasi : Terdapat nilai koefisien z negatif, tabel belum optimum
EV = x2LV = s3
Riset Operasi Prayudi Modul 3 : Metode Simplek 7
Operasi elementer iterasi ketiga :
(i) Persamaan pivot (s3/x2) :
(ii) Persamaan fungsi tujuan (z) :
(iii) Persamaan batasan (s1) :
(iv) Persamaan batasan (s2) :
(v) Persamaan batasan (s4/x1) :
(vi) Persamaan batasan (s5) :
3)L(H
(B)H 33
(L)H2
120(L)H(B)H 300
(L)H23
-(L)H(B)H 311
(L)H26
-(L)H(B)H 322
(L)H20
-(L)H(B)H 344
(L)H21
-(L)H(B)H 355
Riset Operasi Prayudi Modul 3 : Metode Simplek 8
Variabel Basis
Koefisien dariRuas Kanan
Rasioz x1 x2 s1 s2 s3 s4 s5
z 1 0 0 0 0 60 -210 0 11.550
s1 0 0 0 1 0 -3/2 7 0 35 5
s2 0 0 0 0 1 -3 16 0 140 8.75
x2 0 0 1 0 0 ½ -3 0 15
x1 0 1 0 0 0 0 1 0 65 65
s5 0 0 0 0 0 -1/2 3 1 40 13.33
Hasil iterasi ketiga
Solusi : z=11.550 x1=65 ; s1=35 ; s3=0 x2=30 ; s2=140 ; s4=0 ; s5=40
Uji optimasi : Terdapat nilai koefisien z negatif, tabel belum optimum
EV = s4LV = s1
Riset Operasi Prayudi Modul 3 : Metode Simplek 9
Operasi elementer iterasi keempat :
(i) Persamaan pivot (s1/s4) :
(ii) Persamaan fungsi tujuan (z) :
(iii) Persamaan batasan (s2) :
(iv) Persamaan batasan (s3/x2) :
(v) Persamaan batasan (s4/x1) :
(vi) Persamaan batasan (s5) :
7)L(H
(B)H 11
(L)H7
210(L)H(B)H 100
(L)H7
16-(L)H(B)H 122
(L)H73
(L)H(B)H 133
(L)H71
-(L)H(B)H 144
(L)H73
-(L)H(B)H 155
Riset Operasi Prayudi Modul 3 : Metode Simplek 10
Variabel Basis
Koefisien dariRuas Kanan
Rasioz x1 x2 s1 s2 s3 s4 s5
z 1 0 0 30 0 15 0 0 12.600
s4 0 0 0 0.14 0 -0.21 1 0 5
s2 0 0 0 -2.28 1 0.42 0 0 60
x2 0 0 1 0.42 0 -0.14 0 0 30
x1 0 1 0 -0.14 0 0.21 0 0 60
s5 0 0 0 -0.42 0 0.14 0 1 25
Hasil iterasi keempat
Solusi : z=12.600 x1=60 ; s1=0 s3=0 x2=30 ; s2=60 s4=5 ; s5=25
Uji optimasi : Semua nilai koefisien z positip, tabel optimum
Riset Operasi Prayudi Modul 3 : Metode Simplek 11
Langkah-langkah metode M adalah sebagai berikut :
1. Ubahlah batasan model pertidaksamaan menjadi persamaan, dengan menambahkan variabel slack (s) dan variabel buatan pada setiap batasan, dan ubah fungsi tujuan yang memuat variabel buatan (R).
2. Bentuklah tabel awal simplek untuk solusi fisibel dasar dengan jumlah kolom sebanyak jumlah variabel (termasuk variabel slack dan buatan) ditambah tiga, dan kolom sebanyak jumlah batasan ditambah tiga baris.
3. Memilih variabel non dasar masuk (EV) yakni kolom yang memiliki nilai koefisien z positip terbesar.
4. Memilih variabel dasar keluar (LV) dengan cara membagi nilai ruas kanan dengan nilai kolom EV dan memilih baris dg rasio nonnegatif terkecil.
5. Menghitung nilai baris pemutar (persamaan pivot) dengan rumus : pers pivot baru=pers pivot lama / elemen pivot6. Menghitung nilai baris persamaan baru dengan rumus : pers baru=pers lama –(koef kolom EV) x (pers pivot baru)7. Menentukan apakah solusi sudah optimum. Tabel optimum, jika semua
koefisien fungsi tujuan z semuanya negatif. Jika masih tedapat yang positip ulangi kembali langkah 3 s.d 6.
Riset Operasi Prayudi Modul 3 : Metode Simplek 12
Contoh : Teknik Metode M
Minimumkan, z = 80x1+100x2Batasan model : 4x1+ 2x2 ≥ 258 5x1 + 4x2 ≥ 420 2x1 + 4x2 ≥ 240 x1 ≥ 0 x2 ≥ 0
Bentuk persamaan awal model metode simplek adalah :
(0) z+(11M– 80)x1 +(10M–100)x2–Ms1–Ms2–Ms3+0A1+0A2+ 0A3 =918M(1) 4 x1 + 2 x2 – 1 s1 + A1 = 258(2) 5 x1 + 4 x2 – 1 s2 + A2 = 420(3) 2 x1 + 4 x2 – 1 s3 + A3 = 240
Riset Operasi Prayudi Modul 3 : Metode Simplek 13
Variabel Basis
Koefisien dariRuas Kanan
Rasiox1 x2 s1 s2 s3 A1 A2 A3
z11M-
8010M-100
-M -M -M 0 0 0 918M
A1 4 2 -1 0 0 1 0 0 258 64.5
A2 5 4 0 -1 0 0 1 0 420 85
A3 2 4 0 0 –1 0 0 1 240 120
Tabel Awal : Iterasi pertama
Solusi : z=918M x1=0 ; s1=0 ; s3=0 ; A2=420 x2=0 ; s2=0 ; A1=258 ; A3=240
Uji optimasi : Terdapat nilai koefisien z positip, tabel belum optimum
Riset Operasi Prayudi Modul 3 : Metode Simplek 14
(i) Persamaan pivot (A1/x1) :
(ii) Persamaan fungsi tujuan (z) :
(iii) Persamaan batasan (A2) :
(iv) Persamaan batasan (A3) :
Operasi elementer iterasi kedua :
EV = x1, LV = A1
4)L(H
(B)H 11
(L)H4
80-11M-(L)H(B)H 100
(L)H45
-(L)H(B)H 122
(L)H42
-(L)H(B)H 133
Riset Operasi Prayudi Modul 3 : Metode Simplek 15
Vari abel Basis
Koefisien dariRuas Kanan
Rasiox1 x2 s1 s2 s3 A1 A2 A3
z 04,5M -
601,75M - 20 -M -M
-2,75M +20 0 0
208,5M + 5.160
x1 1 0,5 -0,25 0 0 0,25 0 0 64,5 129
A2 0 1,5 1,25 -1 0 -1,25 1 0 97,5 65
A3 0 3 0,5 0 –1 -0,5 0 1 111 37
Tabel Awal : Iterasi kedua
Solusi : z=208,5M+5.160 x1=64,5 ; s1=0 ; s3=0 ; A2=97,5 x2=0 ; s2=0 ; A1=0 ; A3=111
Uji optimasi : Terdapat nilai koefisien z positip, tabel belum optimum
Riset Operasi Prayudi Modul 3 : Metode Simplek 16
(i) Persamaan pivot (A3/x2) :
(ii) Persamaan fungsi tujuan (z) :
(iii) Persamaan batasan (x1) :
(iv) Persamaan batasan (A2) :
Operasi elementer iterasi ketiga :
EV = x2, LV = A3
3
)L(H(B)H 3
3
(L)H3
60-4,5M-(L)H(B)H 300
(L)H3
0,5-(L)H(B)H 311
(L)H3
1,5-(L)H(B)H 322
Riset Operasi Prayudi Modul 3 : Metode Simplek 17
Vari abel Basis
Koefisien dariRuas Kanan
Rasiox1 x2 s1 s2 s3 A1 A2 A3
z 0 0 M-10 -M0,5M-
20-2M +10 0
-1,5M +20
42M + 7380
x1 1 0 -1/3 0 1/6 1/3 0 -1/6 46
A2 0 0 1 -1 1/2 -1 1 -1/2 42 42
x2 0 1 1/6 0 –1/3 -1/6 0 1/3 37 222
Tabel Awal : Iterasi ketiga
Solusi : z=42 M + 7.380 x1=46 ; s1=0 ; s3=0 ; A2=42 x2=37 ; s2=0 ; A1=0 ; A3=0
Uji optimasi : Terdapat nilai koefisien z positip, tabel belum optimum
Riset Operasi Prayudi Modul 3 : Metode Simplek 18
(i) Persamaan pivot (A2/s1) :
(ii) Persamaan fungsi tujuan (z) :
(iii) Persamaan batasan (x1) :
(iv) Persamaan batasan (A2) :
Operasi elementer iterasi keempat :
EV = s1, LV = A2
1)L(H
(B)H 22
(L)H1
10-2M-(L)H(B)H 200
(L)H1
1/3(L)H(B)H 211
(L)H1
1/6-(L)H(B)H 222
Riset Operasi Prayudi Modul 3 : Metode Simplek 19
Vari abel Basis
Koefisien dariRuas Kana
n
Rasiox1 x2 s1 s2 s3 A1 A2 A3
z 0 0 0 -10 -15 -M -M+10 -M+15 7800
x1 1 0 0 -1/3 1/3 0 1/3 -1/3 60
s1 0 0 1 -1 1/2 -1 1 -1/2 42
x2 0 1 0 1/6 –2,5/6 0 -1/6 2,5/6 30
Tabel Awal : Iterasi keempat
Solusi : z=7800 x1=60 ; s1=42 ; s3=0 ; A2=0 x2=30 ; s2=0 ; A1=0 ; A3=0
Uji optimasi : Semua nilai koefisien z negatip, tabel sudah optimum
Riset Operasi Prayudi Modul 3 : Metode Simplek 20
Kasus-kasus dalam metode Simpleks : Degenerasi.
Degenerasi terjadi, jika dalam menentukan variabel keluar (LV), terdapat dua baris yang memiliki rasio minimum yang sama, atau EV (ada dua nilai yang sama.
Optimasi alternatif (tak berhingga banyak).
Kasus ini terjadi bilamana fungsi tujuan sejajar dengan salah satu batasan yang memenuhi solusi optimal, fungsi tujuan akan memiliki nilai optimal yang sama di lebih salah satu titik.
Solusi yang tidak dibatasi.
Kasus ini terjadi,daerah fisibel tidak terbatas (unbounded), akibatnya nilai variabel dan fungsi tujuan akan meningkat (maksimisasi) atau menurun (minimisasi).
Pemecahan tidak layak
Kasus ini terjadi, bilamana daerah fisibel tidak dipenuhi secara simultan.
Nilai ruas kanan (kuantitas) yang negatif.