teknik riset operasi pertemuan 9

Click here to load reader

Post on 20-Jun-2015

1.610 views

Category:

Documents

2 download

Embed Size (px)

TRANSCRIPT

  • 1. Teknik Riset OperasiOleh : A. AfrinaRamadhani H. 1Teknik Riset Operasi 13.12.11

2. PERTEMUAN 9 2Teknik Riset Operasi 13.12.11 3. SIMPLEKS YANG DIREVISIBentuk Persamaan Linear Dalam Bentuk MatriksFormulasi PL dalam bentuk matriks dimana :adalah sebagai berikut :C adalah vektor baris ,C = [c1, c2,,cn]Maksimumkan /minimumkan X dan b adalah vektor kolom :Z = CX TerhadapAX b dan X 03 Teknik Riset Operasi13.12.11 4. Dan A adalah matriks : Kita partisi vektor X menjadi Xi dan Xii , dimana XII adalah elemen X yangmenjadi variabel basis awal, dengan demikian XI adalah elemen X lainnya.Kita partisi juga vektor C menjadi CI dan CII sesuai dengan cara membuatpartisi X. Matriks A terdiri dari vektor kolom P1, P2, , Pn. 4 Teknik Riset Operasi 13.12.11 5. Iterasi Simpleks Dalam Bentuk MatriksVariabelXI XIINilai Kanan BasisZ CBB-1A - CI CB-1 - CII CBB-1b XBB-1AB-1 B-1bSelama iterasi, nilai-nilai vektor dan matriks di atas tidak berubah kecualinilai matriks B-1 . XB dan CB akan berubah pada setiap iterasi tergantungdari vektor masuk dan keluar. 5 Teknik Riset Operasi 13.12.11 6. Contoh Kasus Maksimumkan z = 2x1 + x2 + 2x3 Terhadap 4x1 + 3x2 + 8x3 12 4x1 + x2 + 12x3 8 4x1 - x2 + 3x3 8 x1, x2, x3 0 6 Teknik Riset Operasi 13.12.11 7. Contoh Kasus : Bentuk BakuMaksimumkan z = 2x1 + x2 + 2x3 + 0x4 + 0x5 + 0x6Terhadap4x1 + 3x2 + 8x3 + x4 = 124x1 + x2 + 12x3 + x5 = 84x1 - x2 + 3x3 + x6 = 8x1, x2, x3, x4, x5, x6 0 7 Teknik Riset Operasi13.12.11 8. Matriks dan vektor dari formulasi PL tersebut adalah: 8Teknik Riset Operasi13.12.11 9. 9Teknik Riset Operasi 13.12.11 10. Contoh 2 Minimumkan z = 2x1 + x2 Terhadap3x1 + x2 = 34x1 + 3x2 62x1 + x2 3x1, x2 010Teknik Riset Operasi 13.12.11 11. Bentuk bakunya adalah: minimumkan z = 2x1 + x2 + 0x3 + Mx4 + Mx5 + 0x6 Terhadap 3x1 + x2 + x4 = 3 4x1 + 3x2 x3 + x5 = 6 2x1 + x2 + x6 = 3 x1, x2, x3, x4, x5, x6 0 11Teknik Riset Operasi 13.12.11 12. Matriks dan vektor dari formulasi PL tersebut adalah: 12 Teknik Riset Operasi 13.12.11 13. 13Teknik Riset Operasi 13.12.11 14. Langkah-Langkah Penyelesaian Penentuan vektor masuk (Pj) sekaligus pemeriksaan optimalitasHitung Y = CBB-1 Untuk setiap vektor Pj non basis, hitungzj cj = Ypj cjSolusi optimal sudah diperoleh jika (zj cj ) 0 untuk fungsi tujuanmaksimasi , atau(zj cj ) 0 untuk minimasi 14 Teknik Riset Operasi 13.12.11 15. Solusi optimalnya adalah : XB = B-1 b dan z = CB XB Jika belum optimal, maka vektor keluar adalah vektor dengan nilai (zj cj ) negatif terbesar untuk fungsi tujuan maksimasi atau positif terbesar untuk minimasi. Penentuan vektor keluar , PrUntuk vektor masuk yang sudah ditentukan pada langkah 1, hitung : Nilai variabel basis saat itu : XB = B-1 b Koefisien pembatas variabel masuk : j = B-1Pj Vektor keluar baik untuk maksimasi maupun minimasi diberikanoleh :15Teknik Riset Operasi 13.12.11 16. Penentuan basis berikutnya : Diberikan basis saat ini adalah B-1, hitung : B-1next = EB-1 E adalah matriks identitas (B-1awal) dengan elemen kolom Prdiganti oleh nilai . 16Teknik Riset Operasi13.12.11 17. Kembali ke langkah 1 17Teknik Riset Operasi 13.12.11 18. Tugas... Maksimumkan z = 3x1+2x2 Terhadap x1+2x2 6 2 x1+x2 8 - x1+x2 1 x2 2 x1,x2 018Teknik Riset Operasi 13.12.11 19. Q&ASekian dan Terima Kasih 19Teknik Riset Operasi13.12.11