Jumat, 28 Oktober 2011

METODE SIMPLEKS

METODE SIMPLEKS

A. Pengertian metode simpleks
Penemu metode simpleks adalah George Bernard Dantzig. Dantzig adalah matematikawan Amerika yang lahir di Oregon pada 8 November 1914 dan wafat pada 13 Mei 2005. Beliau adalah Profesor Emiritus Ilmu Transportasi dan Profesor Riset Operasi dan Ilmu Komputer di Stanford. Pada tahun 1974, beliau memperoleh penghargaan John Von Neumann Theory Prize dan pada tahun 1975 mendapat penghargaan National Medal of Science.
Metode simpleks menjadi teknik standard untuk menyelesaikan masalah PL sejak tahun 1947. Metode simpleks adalah suatu prosedur perhitungan yang berulang-ulang dengan bilangan terbatas yang dimulai dari suatu penyelesaian dasar fisibel (PDF). Apabila PDF bukan PO, maka metode simpleks akan mencari PDF lain yang lebih baik sehingga diperoleh PDF yang optimal (jika ada). Metode simpleks didasarkan atas prinsip bahwa PO dari masalah PL selalu dapat ditemukan pada PDF. Secara geometris metode simpleks melangkah dari titik-titik ekstrem daerah penyelesaian fisibel dan secara cepat meningkatkan nilai fungsi tujuan sampai menemukan PO atau menegaskanbahwa tidak ada PO. Titik ekstrem daerah penyelesaian fisibel perpadanan dengan PDF. Oleh karena itu langkah pertama metode simpleks adalah mengupayakan adanya PDF.
Menentukan PDF
Salah satu langkah dalam metode grafik adalah menggambar garis-garis pembatas untuk menemukan titik-titik ekstrim. Dalam metode simpleks agar supaya dapat ditemukan PDF.Langkah pertama adalah mengubah pertidaksamaan linier pada pembatas menjadi suatu persamaan linier. Pertidaksamaan yang bertanda “≤” agar menjadi persamaan harus ditambah dengan suatu variable baru yang tidak negative. Variable baru ini disebut variable slack. Pertidaksamaan bertanda “≥” agar menjadi persamaan harus ditambah dengan variable baru non negative. Variable ini disebut variable surplus. Jadi, variable slack adalah variable non negative yang ditambahkan pada ruas kiri dari pertidaksamaan yang bertanda “≤” agar diperoleh suatu persamaan. Variable surplus adalah varable non negative yang dimasukkan sebagai pengurang pada ruas kiri pada pertidaksamaan yang bertanda “≥” agar supaya diperoleh suatu persamaan. Kedua macam variable itu biasa diberi symbol “S”.
Perhatikan masalah yang dihadapi oleh perusahaan meubel “Tekun Belajar” pada BAB I dengan model matematika:
Maks: Z= 8000X +6000Y (3.1)
X +Y ≤ 25 ……...(3.2)
3X +2Y ≤ 60 …...(3.3)
X, Y ≥ 0 ……(3.4)
Langkah pertama adalah pembatas dari pertidaksamaan linier menjadi persamaan linier. Pembatas dari model matematik yang baru menjadi:
Maks: Z= 8000X +6000Y +0 S1 +0 S2 ……(3.1a)
X + Y + S1 = 25 …………………..(3.2a)
3X +2Y +S2 = 60 …………………(3.3a)
X, Y, S1, S2 ≥ 0……………………(3.4a)
S1 dan S2 bukan hasil produksi, oleh karena itu mereka tidak member laba atau labanya nol rupiah. Oleh karena itu c3 koefisien dari S1 dan c4 koefisien dari S2 diberi nilai nol. Penyelesaian dasar dari system persamaan dengan komponen (3.2a) dan (3.3a) adalah (0, 0,25, 60), (0, 25, 0 10), (0.30, -5, 0),
(25, 0, 0, -15), (20, 0, 5, 0) dan (10, 15, 0, 0).