LINEAR PROGRAMING
METODE SIMPLEKS
PENGANTAR
Apabila suatu masalah LP hanya mengandung 2 kegiatan
(atau variabel2 keputusan) maka akan dapat diselesaikan
dengan metode grafik. Tetapi apabila melibatkan lebih dari
dua kegiatan maka metode grafik akan sulit untuk digunakan
lagi, sehingga diperlukan metode simpleks. Metode ini
merupakan cara yang lazim digunakan untuk menentukan
kombinasi optimal dari tiga variabel/lebih.
Bila variabel keputusan yang dikandung tidak terlalu banyak
masalah tersebut dapat diselesaikan dengan metode
simpleks tabel, karena kombinasi variabel keputusan yang
optimal dicari menggunakan tabel-tabel.
Langkah 1. Mengubah fungsi tujuan dan
batasan.
Fungsi tujuan diubah menjadi fungsi implisit,
artinya semua CjXij digeser ke kiri. Semua
batasan yang mempunyai tanda .
Ketidaksamaan ini harus diubah menjadi
kesamaan. Caranya dengan menambah slack
variable ( variabel tambahan yang mewakili
tingkat pengangguran/kapasitas yang
merupakan batasan). Karena tingkat atau
hasil kegiatan2 yang ada diwakili oleh X1 dan
X2, maka variabel slack dimulai dari X3, X4
dan seterusnya.
Langkah 2. Setelah formulasi diubah
kemudian disusun dalam tabel.
Tabel Simpleks dalam Bentuk Simbol
Var. Z X1 X2 ........................... N
Dsr Xn K
Z 1 - C1 - C2 ................................ 0
Xn + 1 0 - Cn b1
Xn + 2 0 a11 a12 ................................ B2
a1n
a21 a22 ................................
NK adalah nilai
a2n
kanan persamaan, yaitu nilai di
belakang tanda sama dengan (=).
Variabel dasar adalah variabel yang nilainya
sama dengan sisi kanan dari
persamaan.
Langkah 3. Memilih kolom kunci
Kolom kunci adalah kolom yang
merupakan dasar untuk mengubah
tabel. Pilihlah kolom yang
mempunyai nilai pada garis fungsi
tujuan yang bernilai negatif dengan
angka yang terbesar. Kemudian
berilah tanda segi empat pada kolom
kunci tersebut.
Langkah 4. Memilih baris kunci.
Baris kunci adalah baris yang merupakan dasar
untuk mengubah tabel. Carilah indeks tiap-
tiap baris dengan cara membagi nilai-nilai
pada kolom NK dengan nilai yang sebaris
pada kolom kunci.
Nilai kolom NK
Indeks =
Nilai kolom kunci
Pilihlah baris yang mempunyai indeks positif
dengan nilai angka yang terkecil.
Kemudian berilah tanda segi empat pada
baris kunci.
Langkah 5. Mengubah nilai-nilai baris
kunci
Gantilah nilai baris kunci dengan cara
membaginya dengan angka kunci.
Gantilah variabel dasar pada baris itu dengan
variabel yang terdapat di bagian atas kolom
kunci.
Langkah 6. Mengubah nilai-nilai selain
pada baris kunci
Nilai-nilai baris yang lain, selain pada baris
kunci dapat diubah dengan rumus :
Baris baru = baris lama – (koefisien pada
kolom kunci x nilai baru baris
kunci)
Nilai-nilai baru dipakai untuk melengkapi isi
tabel di bawahnya lagi.
Langkah 7. Melanjutkan perbaikan/
perubahan
Ulangi langkah perbaikan untuk
memperbaiki tabel yang telah
diubah/diperbaiki nilainya. Perubahan baru
berhenti setelah pada baris pertama (fungsi
tujuan) tidak ada yang bernilai negatif.
Perusahan sepatu “AMIR” membuat 2 macam sepatu,
macam yang pertama merk IDEAL dengan sol dari
karet, dan sepatu kedua dengan merk IDOLA dengan
sol dari kulit. Untuk membuat sepatu-sepatu ini
perusahaan memiliki 3 macam mesin. Mesin A khusus
membuat sol dari karet, mesin B khusus membuat sol
dari kulit, dan mesin C membuat bagian atas sepatu
dan melakukan assembling bagian atas dengan sol.
Setiap lusin sepatu merk IDEAL mula-mula dikerjakan
di mesin A selama 2 jam, kemudian tanpa melalui
mesin B terus dikerjakan di mesin C selama 6 jam.
Sedang untuk sepatu merk IDOLA tidak diproses di
mesin A, tetapi pertama kali dikerjakan di mesin B
selama 3 jam kemudian di mesin C selama 5 jam. Jam
kerja maksimum setiap hari untuk mesin A = 8 jam,
Mesin B = 15 jam, dan mesin C = 30 jam. Sumbangan
terhadap laba untuk setiap lusin sepatu merk IDEAL =
Rp. 30.000, sedang merk IDOLA = Rp. 50.000. Berapa
lusin sebaiknya sepatu merk IDEAL dan IDOLA yang
dibuat agar bisa memaksimumkan laba?
DATA DARI PERUSAHAAN SEPATU AMIR
MESIN IDEAL IDOLA KAPSITAS
MAKS
A 2 0 8
B 0 3 15
C 6 5 30
Z (Rp. 0,000) 3 5