pengertian metode simpleks baku(2)

BAB 3

BAB 3Metode Simpleks Baku

PengertianSebelum melakukan perhitungan iterative untuk menentukan solusi optimal, langkah pertama adalah mengubah bentuk umum linear programming ke dalam bentuk baku simpleks terlebih dahulu. Bentuk baku dalam metode simpleks tidak hanya mengubah persamaan kendala ke dalam bentuk sama dengan, tapi setiap fungsi kendala harus diwakili oleh satu variabel basis awal. Variabel basis awal menunjukkan kondisi sebelum ada aktivitas yang dilakukan dan variabel keputusan masih bernilai 0. Ada beberapa hal yg hrs diperhatikan dlm membuat bentuk baku/standar, yaitu :1. Fungsi kendala dg pertidaksamaan dlm bentuk umum, dirubah mjd persamaan (=) dg menambahkan satu variable slack.2. Fungsi kendala dg pertidaksamaan dlm bentuk umum, dirubah mjd persamaan (=) dg mengurangkan satu variable surplus.3. Fungsi kendala dg persamaan (=) dlm bentuk umum, ditambahkan satu variable buatan (artificial variable).

LANGKAH-LANGKAH PENYELESAIAN DENGAN METODE SIMPLEKSDalam menyelesaikan masalah linear programming, dilakukan perhitungan iterasi dengan menggunakan table. Tabel awal yang dibuat berdasarkan model baku matematika yang ada dinamakan Tabel Awal Simpleks selanjutnya dilakukan perhitungan iterasi. Tahap-tahap yang ada yaitu :1. Membuat bentuk baku model matematik.2. Membuat table awal simpleks berdasarkan bentuk baku yang sudah ada.3. Memeriksa kelayakan table awal dg melihat nilai kanan. Bila ada yg bernilai negatif maka tidak layak diselesaikan.4. Menentukan kolom pivot dg cara sebagai berikut :a. Bila fungsi tujuannya maksimisasi maka pilih kolom dg nilai negatif terbesar.b. Bila fungsi tujuannya minimalisasi maka pilih kolom dg nilai positif terkecil.c. Bila nilai-nilai tersebut jumlahnya lebih dari satu, pilih sembarang.Bila kolom pivot ditarik ke atas maka akan ditemukan variabel keluar.1. Menentukan baris pivot dg melihat hasil bagi nilai solusi dg nilai kolom pivot yg bersesuaian. Pilih yg mempunyai nilai bagi terkecil. Bila baris pivot ditarik ke kiri maka akan diperoleh variabel keluar.2. Menentukan elemen pivot dg mencari perpotongan kolom pivot dan baris pivot.3. Lakukan perhitungan-perhitungan untuk membuat iterasi selanjutnya.4. Memeriksa keoptimalan dengan melihat nilai koefisien fungsi tujuan di mana : Bila maksimisasi maka nilai solusi sudah positif atau nol. Bila minimisasi maka nilai solusi sudah negatif atau nol.

Tabel Simpleks BakuCj

Variabel BasisCB HargaBasisRasio

Zj Cj

Rumus : , dimaan = 1, 2,

CONTOH 11. Maksimalkan Dengan kondisi : . (1) (2)

Jawab :

Tabel Awal SimpleksCj4 3 0 0

Variabel BebasCBX1 X2 X3 X4HargaBasisRasio

X303 4 1 012= 4

X407 2 0 114= 2

Zj Cj-4 -3 0 00

Note : : Kunci: Kolom Kunci: Baris Kunci

Zj-Cj : (0 3 + 0 7) 4 = -4 (0 4 + 0 2) 3 = -3 (0 1 + 0 0) 0 = 0 (0 0 + 0 1) 0 = 0

Selanjutnya buat table 2, dimana datang dan pergi. Hitung nilai dan

Cj4 3 0 0


X300 1 6 =

X141 0 2= 7

Zj Cj0 0 8

Note : : Kunci: Kolom Kunci: Baris Kunci Untuk mencari adalah dengan membagi nilai pada baris dengan nilai kunci.1 = 7 = Untuk mencari dengan cara nilai pada baris pada table 1 dikurangi diakalikan nilai , =bilangan asli agar menghasilkan sebagai berikut ;3 = = [ ] Dimana = 3 agar hasil yg didapat 3 = = [ ]Zj Cj : (0 0 + 4 1) 4 = 0 (0 + 4 ) 3 = (0 + 4 ) 0 = 0 (0 + 4 ) 0 =

Harga Basis pada Zj Cj : Z = 4x1 + 3x2 Z = 4(2) + 3()Z = 8

Sekarang buat table 3 dengan cara seperti kita membuat table 2. Dimana datang dan pergi.

Cj4 3 0 0


X230 = END

X141

Zj Cj0 0

Note :: Nilai Maksimum

1 = [ ] = 3 = Dimana = 3 = = [ ]Zj Cj : (3 0 + 4 1) 4 = 0 (3 1 + 4 ) 3 = 0 (3 + 4 ) 0 = (3 + 4 ) 0 = Harga Basis pada Zj Cj : Z = 4x1 + 3x2 Z = 4() + 3()Z = (Maksismum saat X1 = dan X2 = )

Pada Tabel iterasi 3 dapat dilihat bahwa nilai Z sudah tidak ada yang negative sehingga sudah optimal. Dari table tersebut dapat dibaca :1. Nilai optimal (nilai maksimum tujuan) Z = 2. Nilai solusi X1 = 3. Nilai solusi X2 = Latihan.Maksimumkan : Kondisi :

Cari, dan !

Jawab :

Table 1

VariabelBebasHarga BasisRasio

01

0

Yang berwarna biru = 2 merupakan kunci.

=

Selanjutnya memnuat table 2, dimana datang dan P pergi

Table 2


END

1

= Kunci

Untuk mencari

Dimana = 1

=

Selanjutnya memnuat table 3, dimana datang dan Q pergi

Tabel 3


END

Untuk mencari

Dimana =

=

,

(maksimum)Pada Tabel iterasi 3 dapat dilihat bahwa nilai Z sudah tidak ada yang negative sehingga sudah optimal. Dari table tersebut dapat dibaca :1. Nilai optimal (nilai maksimum tujuan) Z = 2. Nilai solusi = 3. Nilai solusi = 5

96

pengertian metode simpleks baku(2)

Documents