teknik riset operasi pertemuan 9

19
Teknik Riset Operasi Oleh : A. AfrinaRamadhani H. 13.12.11 1 Teknik Riset Operasi

Upload: afrina-ramadhani

Post on 20-Jun-2015

1.619 views

Category:

Documents


2 download

TRANSCRIPT

Page 1: Teknik riset operasi pertemuan 9

Teknik Riset Operasi

Oleh : A. AfrinaRamadhani H. 13.12.11

1

Teknik Riset Operasi

Page 2: Teknik riset operasi pertemuan 9

PERTEMUAN 9 13.12.11

2

Teknik Riset Operasi

Page 3: Teknik riset operasi pertemuan 9

13.12.11 Teknik Riset Operasi

3

SIMPLEKS YANG DIREVISI

Bentuk Persamaan Linear Dalam Bentuk Matriks

Formulasi PL dalam bentuk matriks

adalah sebagai berikut :

Maksimumkan /minimumkan

Z = CX

Terhadap

AX ≤ b

dan X ≥ 0

dimana :

C adalah vektor baris ,

C = [c1, c2,…,cn]

X dan b adalah vektor kolom :

Page 4: Teknik riset operasi pertemuan 9

13.12.11 Teknik Riset Operasi

4

• Dan A adalah matriks :

• Kita partisi vektor X menjadi Xi dan Xii , dimana XII adalah elemen X yang

menjadi variabel basis awal, dengan demikian XI adalah elemen X lainnya.

Kita partisi juga vektor C menjadi CI dan CII sesuai dengan cara membuat

partisi X. Matriks A terdiri dari vektor kolom P1, P2, …, Pn.

Page 5: Teknik riset operasi pertemuan 9

13.12.11 Teknik Riset Operasi

5

Iterasi Simpleks Dalam Bentuk Matriks

Variabel XI XII Nilai Kanan

Basis

Z CBB-1A - CI CB-1 - CII CBB-1b

XB B-1A B-1 B-1b

Selama iterasi, nilai-nilai vektor dan matriks di atas tidak berubah kecuali

nilai matriks B-1 . XB dan CB akan berubah pada setiap iterasi tergantung

dari vektor masuk dan keluar.

Page 6: Teknik riset operasi pertemuan 9

13.12.11 Teknik Riset Operasi

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

Page 7: Teknik riset operasi pertemuan 9

13.12.11 Teknik Riset Operasi

7

Contoh Kasus : Bentuk Baku

Maksimumkan z = 2x1 + x2 + 2x3 + 0x4 + 0x5 + 0x6

Terhadap

4x1 + 3x2 + 8x3 + x4 = 12

4x1 + x2 + 12x3 + x5 = 8

4x1 - x2 + 3x3 + x6 = 8

x1, x2, x3, x4, x5, x6 ≥ 0

Page 8: Teknik riset operasi pertemuan 9

13.12.11 Teknik Riset Operasi

8

Matriks dan vektor dari formulasi PL tersebut adalah:

Page 9: Teknik riset operasi pertemuan 9

13.12.11 Teknik Riset Operasi

9

Page 10: Teknik riset operasi pertemuan 9

13.12.11 Teknik Riset Operasi

10

Contoh 2

Minimumkan z = 2x1 + x2

Terhadap

3x1 + x2 = 3

4x1 + 3x2 ≥ 6

2x1 + x2 ≤ 3

x1, x2 ≥ 0

Page 11: Teknik riset operasi pertemuan 9

13.12.11 Teknik Riset Operasi

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

Page 12: Teknik riset operasi pertemuan 9

13.12.11 Teknik Riset Operasi

12

Matriks dan vektor dari formulasi PL tersebut adalah:

Page 13: Teknik riset operasi pertemuan 9

13.12.11 Teknik Riset Operasi

13

Page 14: Teknik riset operasi pertemuan 9

13.12.11 Teknik Riset Operasi

14

Langkah-Langkah Penyelesaian

• Penentuan vektor masuk (Pj) sekaligus pemeriksaan optimalitas

Hitung Y = CBB-1

Untuk setiap vektor Pj non basis, hitung

zj – cj = Ypj – cj

Solusi optimal sudah diperoleh jika (zj – cj ) ≥ 0 untuk fungsi tujuan

maksimasi , atau

(zj – cj )≤ 0 untuk minimasi

Page 15: Teknik riset operasi pertemuan 9

13.12.11 Teknik Riset Operasi

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 , Pr

Untuk 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 diberikan

oleh :

Page 16: Teknik riset operasi pertemuan 9

13.12.11 Teknik Riset Operasi

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 ξ .

Page 17: Teknik riset operasi pertemuan 9

13.12.11 Teknik Riset Operasi

17

• Kembali ke langkah 1

Page 18: Teknik riset operasi pertemuan 9

13.12.11 Teknik Riset Operasi

18

Maksimumkan z = 3x1+2x2

Terhadap

x1+2x2 ≤ 6

2 x1+x2 ≤ 8

- x1+x2 ≤ 1

x2 ≤ 2

x1,x2 ≥ 0

Tugas...

Page 19: Teknik riset operasi pertemuan 9

Q & A

Sekian dan Terima Kasih 13.12.11 Teknik Riset Operasi

19