teknik riset operasi pertemuan 6

Teknik Riset Operasi

Oleh : A. AfrinaRamadhani H. 13.12.11

1


PERTEMUAN 6 13.12.11

2


13.12.11 Teknik Riset Operasi

3

METODE SIMPLEKS

• Penentuan solusi optimal menggunakan simpleks didasarkan pada

teknik eliminasi Gauss Jordan.

• Penentuan solusi optimal dilakukan dengan memeriksa titik

ekstrim (ingat kembali solusi grafik) satu per satu dengan cara

perhitungan iteratif.

• Penentuan solusi optimal dengan simpleks dilakukan tahap demi

tahap yang kita sebut dengan iterasi.

• Iterasi ke-i hanya tergantung dari iterasi sebelumnya (i-1).


4

Bentuk Baku

Ada beberapa hal yang harus diperhatikan dalam membuat bentuk

baku/standar, yaitu:

1. Fungsi kendala dengan pertidaksamaan ≤ dalam bentuk umum,

dirubah menjadi persamaan (=) dengan menambahkan satu variabel

slack.

2. Fungsi kendala dengan pertidaksamaan ≥ dalam bentuk umum,

dirubah menjadi persamaan (=) dengan mengurangkan satu variabel

surplus.

3. Fungsi kendala dengan persamaan dalam bentuk umum, ditambahkan

satu artificial variable (variabel buatan).


5

Perhatikan kasus berikut:

Minimumkan z = 2 x1 + 5.5 x2

Kendala: x1 + x2 = 90

0.001x1 + 0.002x2 ≤ 0.9

0.09x1 + 0.6x2 ≥ 27

0.02x1 + 0.06x2 ≤ 4.5

x1, x2 ≥ 0


6

Bentuk sebelumnya adalah bentuk umum pemrograman linearnya.

Kedalam bentuk baku/standar, model matematik tersebut akan berubah

menjadi:

Minimumkan z = 2 x1 + 5.5 x2

Terhadap: x1 + x2 + s1 = 90

0.001x1 + 0.002x2 + s2 = 0.9

0.09x1 + 0.6x2 - s3 = 27

0.02x1 + 0.06x2 + s4 = 4.5

x1, x2, s1, s2, s3, s4 ≥ 0


7

Fungsi kendala pertama mendapatkan variabel buatan (s1), karena

bentuk umumnya sudah menggunakan bentuk persamaan. Fungsi

kendala kedua dan keempat (s2 dan s4) mendapatkan variabel slack

karena bentuk umumnya menggunakan pertidaksamaan ≤, sedangkan

fungsi kendala ketiga mendapatkan surplus variabel (s3) karena bentuk

umumnya menggunakan pertidaksamaan ≥.


8

Perhatikan juga kasus berikut:

Maksimumkan z = 2x1 + 3x2

Terhadap : 10x1 + 5x2 ≤ 600

6x1 + 20x2 ≤ 600

8x1 + 15x2 ≤ 600

x1, x2 ≥ 0

Perubahan kedalam bentuk baku hanya membutuhkan variabel slack,

karena semua fungsi kendala menggunakan bentuk pertidaksamaan ≤

dalam bentuk umumnya.


9

Maka bentuk bakunya adalah sebagai berikut:

Maksimumkan z = 2x1 + 3x2 + 0s1 + 0s2 + 0s3

Terhadap :

10x1 + 5x2 + s1 = 600

6x1 + 20x2 + s2 = 600

8x1 + 15x2 + s3 = 600

x1, x2, s1, s2, s3 ≥ 0

s1, s2, s3 merupakan variabel slack.


10

Pembentukan Tabel Simpleks

Kita gunakan kasus sebelumnya, maka tabel awal simpleksnya adalah :


11

Langkah-langkah Penyelesaian

1. Periksa apakah tabel layak atau tidak. Kelayakan tabel simpleks

dilihat dari solusi (nilai kanan). Jika solusi ada yang bernilai negatif,

maka tabel tidak layak.

2. Tentukan kolom pivot. Penentuan kolom pivot dilihat dari koefisien

fungsi tujuan (nilai di sebelah kanan baris z) dan tergantung dari

bentuk tujuan. Jika tujuan berupa maksimisasi, maka kolom pivot

adalah kolom dengan koefisien negatif terbesar. Jika tujuan

minimisasi, maka kolom pivot adalah kolom dengan koefisien positif

terkecil.


12

3. Tentukan baris pivot. Baris pivot ditentukan setelah membagi nilai

solusi dengan nilai kolom pivot yang bersesuaian (nilai yang terletak

dalam satu baris). Dalam hal ini, nilai negatif dan 0 pada kolom pivot

tidak diperhatikan. Baris pivot adalah baris dengan rasio pembagian

terkecil.

4. Tentukan elemen pivot. Elemen pivot merupakan nilai yang terletak

pada perpotongan kolom dan baris pivot.


13

5. Bentuk tabel simpleks baru. Tabel simpleks baru dibentuk dengan

pertama sekali menghitung nilai baris pivot baru. Baris pivot baru

adalah baris pivot lama dibagi dengan elemen pivot. Baris baru

lainnya merupakan pengurangan nilai kolom pivot baris yang

bersangkutan dikali baris pivot baru dalam satu kolom terhadap baris

lamanya yang terletak dalam satu kolom juga.

6. Periksa apakah tabel sudah optimal. Keoptimalan tabel dilihat dari

koefisien fungsi tujuan (nilai pada baris z) dan tergantung dari bentuk

tujuan.


14

Kita selesaikan kasus sebelumnya.


15

Iterasi 1


16

Tabel sudah optimal, sehingga perhitungan iterasi dihentikan!


17

Ada beberapa hal yang bisa dibaca dari tabel optimal :

1. Solusi optimal variabel keputusan.

2. Status sumber daya.

3. Harga bayangan (dual/shadow prices).

Menggunakan tabel optimal di atas:


18

Solusi optimal : x1 = 42.857; x2 = 17.1329 dan z = 94.2857

Status sumber daya : sumber daya pertama dilihat dari keberadaan

variabel basis awal dari setiap fungsi kendala pada tabel optimal.

• s1 = 85.7155. Sumber daya ini disebut berlebih (abundant)

• s2 = s3 = 0. Kedua sumber daya ini disebut habis terpakai (scarce).

Harga bayangan : harga bayangan dilihat dari koefisien variabel slack

atau surplus pada baris fungsi tujuan.

Q & A

Sekian dan Terima Kasih 13.12.11 Teknik Riset Operasi

19

teknik riset operasi pertemuan 6

Documents