metode simpleks.pdf
TRANSCRIPT
![Page 1: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/1.jpg)
RISET OPERASIONALRISET OPERASIONAL
Mikhratunnisa, S.Si.,M.Si.Email: [email protected], S.Si.,M.Si.Email: [email protected]
JURUSAN TEKNOLOGI INDUSTRI PERTANIAN
FAKULTAS TEKNOLOGI PERTANIAN
UNIVERSITAS TEKNOLOGI SUMBAWA
![Page 2: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/2.jpg)
METODE SIMPLEKSMETODE SIMPLEKS
Persoalan program linier tidak selalu sederhana karenamelibatkan banyak kendala dan banyak variabel, sehinggatidak mungkin diselesaikan dengan metode grafik. Olehkarena itu serangkaian prosedur matematik (aljabarlinier) diperlukan untuk mencari solusi dari persoalanyang rumit tersebut. Prosedur yang paling luas digunakanadalah metode simpleks.
Persoalan program linier tidak selalu sederhana karenamelibatkan banyak kendala dan banyak variabel, sehinggatidak mungkin diselesaikan dengan metode grafik. Olehkarena itu serangkaian prosedur matematik (aljabarlinier) diperlukan untuk mencari solusi dari persoalanyang rumit tersebut. Prosedur yang paling luas digunakanadalah metode simpleks.
![Page 3: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/3.jpg)
Bentuk standar
Maksimumkan/minimumkan:
Fungsi Pembatas/kendala:
nnXCXCXCXCZ ...
332211
Bentuk standar
Maksimumkan/minimumkan:
Fungsi Pembatas/kendala:
mnmnmmm
nn
nn
bXaXaXaXa
bXaXaXaXa
bXaXaXaXa
...
...
...
332211
22323222121
11313212111
![Page 4: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/4.jpg)
Kendala utama masalah program linier dapat berbentukatau atau
Kendala yang berbentuk pertidaksamaan diubah menjadi persamaansebagai berikut:
1). . Dalam ruas kiri disisipkan sedemikian
hingga dipenuhi : dengan
2). . Dalam ruas kanan disisipkan sedemikian
hingga atau dengan
Dimana dan disebut peubah/variabel pengetat (slack
variable).
p
jijij bxa
1
p
jijij bxa
1
p
jijij bxa
1
p
jijij bxa
1is
p
jiijij bSxa
10is
Kendala utama masalah program linier dapat berbentukatau atau
Kendala yang berbentuk pertidaksamaan diubah menjadi persamaansebagai berikut:
1). . Dalam ruas kiri disisipkan sedemikian
hingga dipenuhi : dengan
2). . Dalam ruas kanan disisipkan sedemikian
hingga atau dengan
Dimana dan disebut peubah/variabel pengetat (slack
variable).
p
jiijij bSxa
10is
p
jijij bxa
1it
p
jiijij tbxa
1
p
jiijij btxa
10it
is it
![Page 5: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/5.jpg)
Tabel Simpleks
![Page 6: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/6.jpg)
Peubah/ variabel lengkap
koefisien teknis
suku tetap (tak negatif)
Koefisien ongkos
Peubah/variabel yang menjadi basis dalam tabel yang
ditinjau
Koefisen ongkos milik peubah/variabel basis
(hasil kali dengan kolom )
(hasil kali dengan )
selisih dengan
:j
x:
ija
:i
b
:i
x
Keterangan :
:j
c
Peubah/ variabel lengkap
koefisien teknis
suku tetap (tak negatif)
Koefisien ongkos
Peubah/variabel yang menjadi basis dalam tabel yang
ditinjau
Koefisen ongkos milik peubah/variabel basis
(hasil kali dengan kolom )
(hasil kali dengan )
selisih dengan
ic
ix:
jc
m
i ijijacz
1:
ija
m
i iibcZ
1: i
ci
b
:jj
cz j
zj
c
![Page 7: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/7.jpg)
Apabila tabel bersangkutan belum optimum dan terpilih sebagaibasis baru maka disusun kolom yang diperoleh dengan:
hanya untuk
Langkah – langkah Simpleks:1. Menyusun tabel awal dengan matriks tersusut Gauss-Jordan dan
2. Menguji keoptimuman Tabel. Bila belum optimum lanjut ke langkah3.
3. Memperbaiki tabel. Dalam hal ini memilih peubah/variabel baruyang masuk menjadi basis, dan memilih peubah/variabel lama yangharus keluar (diganti).
4. Selanjutnya kembali ke langkah-2 dst. Sampai diperoleh penyelesaianoptimum.
kx
iR
ik
i
i a
bR 0
ika
ija
0i
b
Apabila tabel bersangkutan belum optimum dan terpilih sebagaibasis baru maka disusun kolom yang diperoleh dengan:
hanya untuk
Langkah – langkah Simpleks:1. Menyusun tabel awal dengan matriks tersusut Gauss-Jordan dan
2. Menguji keoptimuman Tabel. Bila belum optimum lanjut ke langkah3.
3. Memperbaiki tabel. Dalam hal ini memilih peubah/variabel baruyang masuk menjadi basis, dan memilih peubah/variabel lama yangharus keluar (diganti).
4. Selanjutnya kembali ke langkah-2 dst. Sampai diperoleh penyelesaianoptimum.
0i
b
![Page 8: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/8.jpg)
Contoh 1 (pola maksimum baku):Sekelompok petani transmigran mendapatkan 6 ha yang dapatditanami padi, jagung, dan palawija lain. Karena keterbatasansumberdaya petani harus menentukan berapa bagian yangharus ditanami padi dan berapa yang harus ditanami jagung,sedang palawija lain ternyata tidak menguntungkan. Dalamsatu masa tanam tenaga yang tersediahanya 1590 jam-orang,pupuk juga terbatas, tidak lebih dari 480 kg, sedangkan airdan sumber daya lainnya dianggap cukup tersedia. Diketehuipula bahwa untuk menghasilkan 1 kuintal padi diperlukan 12jam-orang tenaga dan 4 kg pupuk, dan untuk 1 kuintal jagungdiperlukan 9 jam-orang tenaga dan 2 kg pupuk. Kondisi tanahmemungkinkan menghasilkan 20 kuintal padi per ha atau 50kuintal jagung per ha. Pendapatan patani 1 kuintal padi adalahRp32.000 sedang 1 kuintal janggung Rp20.000, dan dianggapbahwa semua hasil tanamnya selalu habis terjual. Masalah bagipetani ialah bagaimanakah rencana (program) produksi yangmemaksimumkan pendapatan total?
Contoh 1 (pola maksimum baku):Sekelompok petani transmigran mendapatkan 6 ha yang dapatditanami padi, jagung, dan palawija lain. Karena keterbatasansumberdaya petani harus menentukan berapa bagian yangharus ditanami padi dan berapa yang harus ditanami jagung,sedang palawija lain ternyata tidak menguntungkan. Dalamsatu masa tanam tenaga yang tersediahanya 1590 jam-orang,pupuk juga terbatas, tidak lebih dari 480 kg, sedangkan airdan sumber daya lainnya dianggap cukup tersedia. Diketehuipula bahwa untuk menghasilkan 1 kuintal padi diperlukan 12jam-orang tenaga dan 4 kg pupuk, dan untuk 1 kuintal jagungdiperlukan 9 jam-orang tenaga dan 2 kg pupuk. Kondisi tanahmemungkinkan menghasilkan 20 kuintal padi per ha atau 50kuintal jagung per ha. Pendapatan patani 1 kuintal padi adalahRp32.000 sedang 1 kuintal janggung Rp20.000, dan dianggapbahwa semua hasil tanamnya selalu habis terjual. Masalah bagipetani ialah bagaimanakah rencana (program) produksi yangmemaksimumkan pendapatan total?
![Page 9: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/9.jpg)
Tabel Produksi Tani
SumberPer kuintal Batas
Sumber SatuanPadi Jagung
tanah 0,02 0,05 6 ha
Tenaga 12 9 1590 Jam-orang
pupuk 4 2 480 kg
pendapatan 32 20 Rp 1000pendapatan 32 20 Rp 1000
Misalkan x : banyak kuintal padi yang diproduksiy : banyak kuintal jagung yang diproduksi
![Page 10: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/10.jpg)
Mencari x dan y yang memenuhi:
dan memaksimumkan
0
0
2402
53034
60052
y
x
yx
yx
yx
Mencari x dan y yang memenuhi:
dan memaksimumkan
0
0
2402
53034
60052
y
x
yx
yx
yx
yxf 2032
![Page 11: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/11.jpg)
Penyelesaian :
Dengan menambah tiga peubah/variabel pengetat r, s, dan tsoal akan menjadi berbentuk kanonik sbb:2x + 5y + r = 6004x + 3y + s = 5302x + y + t = 240
Penyelesaian :
Dengan menambah tiga peubah/variabel pengetat r, s, dan tsoal akan menjadi berbentuk kanonik sbb:2x + 5y + r = 6004x + 3y + s = 5302x + y + t = 240
0;0;0;0;0 tsryx
tsryxf 0002032
![Page 12: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/12.jpg)
TabelTabel awalawal
32 20 0 0 0
000
rst
242
531
100
010
001
600530240
0 0 0 0 0 Z=0
ic j
c
jixx \
ox y r s t
ib
iR
jz 0 0 0 0 0 Z=0
-32 -20 0 0 0 Z=0j
z
jjcz
Menguji keoptimuman:Bila masih ada yang negatif maka tabel belum maksimum.
jjcz
Tabel sudah maksimum bila untuk semua j0jj
cz
Belumoptimum
![Page 13: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/13.jpg)
Memperbaiki tabel
Pilih k dengan yang paling kecil, makaterpilih untuk masukmenjadi basis
0kk
czk
x
Pilih p dengan yang terkecil, maka terpilih untukkeluar dari basis
pR p
x
![Page 14: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/14.jpg)
32 20 0 0 0
0032
rsx
001
41
1/2
100
010
-1-21/2
36050120
9050240
32 16 0 0 16 Z=3840
ic j
c
jixx \ x y r s t
ib
iR
jz 32 16 0 0 16 Z=3840
0 -4 0 0 16 Z=3840j
z
jjcz
311
322
33
2
421
EEE
EEE
EE
![Page 15: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/15.jpg)
32 20 0 0 0
02032
ryx
001
010
100
-41
-1/2
7-23/2
1605095
32 20 0 4 8 Z=4040
ic j
c
jixx \
ox y r s t
ib
iR
jz 32 20 0 4 8 Z=4040
0 0 0 4 8 Z=4040j
z
jjcz
233
211
21
4
EEE
EEE
Sehingga(x,y)=(95,50) dengannilai f maks =4040
![Page 16: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/16.jpg)
Peubah SemuContoh 2:Menentukan x, y, z tak negatif yang memenuhi
dan memaksimumkanDengan menyisipkan dua peubah pengetat a dan b diperolehbentuk kanonik dari soal tersebut sbb:x + y + 2z + a = 122x – 6y – z - b = 4Agar tabel awal sudah memuat penyelesaian basis yang layakmaka pada persamaan kedua disisipkan lagi satu peubah c(peubah semu), sehingga kendala utama berbunyi:
462
122
zyx
zyx
zyxf 868
Peubah SemuContoh 2:Menentukan x, y, z tak negatif yang memenuhi
dan memaksimumkanDengan menyisipkan dua peubah pengetat a dan b diperolehbentuk kanonik dari soal tersebut sbb:x + y + 2z + a = 122x – 6y – z - b = 4Agar tabel awal sudah memuat penyelesaian basis yang layakmaka pada persamaan kedua disisipkan lagi satu peubah c(peubah semu), sehingga kendala utama berbunyi:
![Page 17: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/17.jpg)
x + y + 2z + a = 122x – 6y – z - b + c = 4 dengan 0c
Syarat perlu agar soal asli mempunyai penyelesaian optimumialah: “Dalam tabel optimum peubah semu c harusbernilai nol”
Agar peubah semu c segera bernilai nol maka disusun fungsitujuan baru dengan bentuk:
dengan M bilangan positif yang cukup besar.Maff
![Page 18: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/18.jpg)
Jadi untuk contoh 2, fungsi tujuan menjadi :
Tabel simpleks untuk contoh 2 sbb:Mabazyxf 00868
![Page 19: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/19.jpg)
Pola MinimumDalam soal yang berpola minimum fungsi tujuan akan makindiperkecil menuju ke nilai minimumnya, maka beberapapetunjuk akan berlawanan dengan petunjuk dalamsola berpolamaksimum.
Tabel Awal : penyisipan peubah pengetat dan peubah semusama dengan pola maksimum, kecuali dalam menyusun fungsitujuan baru bila ada peubah peubah semu yang masuk.
Tabel Awal : penyisipan peubah pengetat dan peubah semusama dengan pola maksimum, kecuali dalam menyusun fungsitujuan baru bila ada peubah peubah semu yang masuk.
Bila ada peubah semu c masuk maka disusun fungsitujuan baru (M posistif besar)Maff
![Page 20: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/20.jpg)
Ciri Optimum: tabel sudah optimum bilauntuk semua j
0jj
cz
PerbaikiTabel: untuk mrmilih peubah yang masukmenjadi basis.Pilih yang paling besar, makaterpilih untuk masuk menjadi basis .
0kk
cz
kx
ik
i
i a
bR
iRMenyusun seperti pada pola maksimum, yaitu
dengan , kemudian untuk memilih
basis yang keluar.
0ik
a
![Page 21: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/21.jpg)
SoalSoal 11Seorang pengusaha mebel memproduksi lemari dan mejadengan bahan-bahan mentah besi, kayu dan paku. Kebutuhanbahan per unit produksi dan batas maksimum persediaanbahan untuk satu masa produksi dan besar laba dari penjualanper unitnya dapat dilihat dalam tabel berikut.
![Page 22: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/22.jpg)
Soal 2
![Page 23: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/23.jpg)
Soal 3
![Page 24: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/24.jpg)
Soal 4
![Page 25: metode simpleks.pdf](https://reader030.vdokumen.com/reader030/viewer/2022033104/563db82e550346aa9a914be1/html5/thumbnails/25.jpg)
Soal 5