Daftar isi ;
baca materi sebelumnya C. Linier Programming, Metode Grafik
Metode grafik tidak dapat menyelesaikan persoalan linear program yang memilki variabel keputusan yang cukup besar atau lebih dari dua, maka untuk menyelesaikannya digunakan Metode Simpleks.
Metode simpleks merupakan salah satu teknik penentuan solusi optimal yang digunakan dalam pemograman linear. Penentuan solusi optimal dilakukan dengan memeriksa titik ekstrim satu per satu dengan cara perhitungan iterative sehingga penentuan solusi optimal dengan simpleks dilakukan dengan tahap demi tahap yang disebut iterasi.
Algoritma dalam metode simpleks:
1) Merubah fungsi tujuan dan batasan-batasan 2) Menyusun persamaan-persamaan di dalam tabel 3) Memilih KOLOM KUNCI
4) Memilih BARIS KUNCI
5) Merubah nilai-nilai BARIS KUNCI
6) Merubah nilai-nilai selain pada BARIS KUNCI 7) Melanjutkan perbaikan - perbaikan / perubahan perubahan.
Sebagai contoh, misalkan pada sebuah perusahaan dagang, terdapat model matematis sebagai berikut:
Maksimasi Z = 3 X1 + 5 X2
Kendala: 2 X1 ≤ 8
3 X2 ≤ 15
6 X1 + 5 X2 ≤ 30
Untuk menggunakan metode simpleks, maka fungsi tujuan diubah menjadi fungsi implisit. Misal:
Z = 3 X1 + 5 X2
diubah menjadi:
Z – 3 X1 – 5 X2 = 0
Pada bentuk standar,semua batasan mempunyai tanda ≤. Pertidaksamaan tersebut harus diubah menjadi persamaan. Caranya dengan menambah SLACK VARIABLE (variabel tambahan yang mewakili tingkat pengangguran atau kapasitas yang mempunyai batasan)
Variabel Slack ini adalah Xn+1, Xn+2,…,Xn+m
Fungsi Batasan:
(1) 2 X1 ≤ 8 2 X1 + X3 = 8 (2) 3 X2 ≤ 15 3 x2 + X4 = 15 (3) 6 X1 + 5 X2 ≤ 30 6 X1 + 5 X2 + X5 = 30 Formulasi matematisnya:
Fungsi Tujuan: Maks Z – 3 X1 – 5 X2
Batasan:
(1) 2 X1 + X3 = 8
(2) 3 X2 + X4 = 15 (3) 6 X1 + 5 X2 + X5 = 30
Langkah selanjutnya adalah memilih kolom kunci
• KOLOM KUNCI adalah kolom yang merupakan dasar untuk merubah tabel di atas.
• KOLOM KUNCI adalah Kolom yang mempunyai nilai pada baris fungsi tujuan bernilai NEGATIF TERBESAR
• Kalau suatu tabel sudah tidak memiliki nilai negatif pada baris fungsi TUJUAN, berarti tabel itu tidak bisa dioptimalkan lagi (sudah optimal)
Setelah baris kunci yang baru ditemukan, selanjutnya adalah merubah nilai lain yang terdapat di tabel.
Berikutnya, hal yang harus dilakukan adalah merubah nilai selain baris kunci. Hal tersebut dilakukan dengan rumus:
BARIS BARU = BARIS LAMA – [(KOEFISIEN PADA KOLOM KUNCI) X NILAI BARU BARIS KUNCI]
Nilai-nilai baru di atas digunakan untuk melengkapi isi tabel bagian bawah, sehingga hasilnya terlihat seperti tabel berikut:
Langkah-langkah perbaikan (langkah 3 sampai 6)
dilakukan untuk memperbaiki tabel. Perubahan baru berhenti setelah pada baris pertama (fungsi tujuan) tidak ada yang bernilai negatif.
Bila dilihat dari baris pertama (Z) pada tabel di atas tidak ada lagi yang bernilai negatif, semuanya positif. Berbarti tabel diatas tidak dapat dioptimalkan lagi sehingga hasil dari tabel tersebut sudah merupakan hasil optimal.
Post a Comment