Dalam memecahkan dan menyelesaikan
masalah linier programming diperlukan alternatif yang terbaik mengenai alokasi
sumber daya yang terbatas dalam proses produksi untuk menghasilkan kombinasi
jumlah produk yang optimal agar dapat menghasilkan keuntungan yang maksimal.
Menurut Tjutju Tarliah Dimyati dan Ahmad Dimyati dalam bukunya “Operation
Research” (2003,38) untuk menyelesaikan masalah linier programming terbagi
dalam dua metode yaitu metode umum dan metode khusus.
Adapun penyelesaian metode linier programming secara umum adalah:
a.
Metode Grafik
Metode grafik hanya diterapkan untuk memecahkan
masalah-masalah linier programming yagn menyangkut dua variabel keputusan (atau
tiga variabel dengan grafik tiga dimensi). Terdapat lima langkah dalm
menyelesaikan permasalahan linier programming dengan menggunakan metode grafik
(Handoko, 2000:), yaitu:
1) Merumuskan masalah dalam bentuk matematikal (maksimumkan
atau minimumkan).
2) Menggambarkan persamaan-persamaan batasan.
3) Menentukan daerah fisibel (feasible area).
4) Menggambarkan fungsi tujuan
5) Mencari titik optimum.
Daerah fisibel (feasible area) dari programa linier
adalah set dari seluruh titik yang memenuhi seluruh pembatas, termasuk pembatas
tanda. Untuk persoalan maksimasi, solusi optimal dari persoalan program linier
adalah suatu titik pada daerah fisibel dengan nilai fungsi tujuan terbesar. Pada
persoalan minimasi, solusi optimal adalah suatu titik pada daerah fisibel
dengan nilai fungsi tujuan terkecil (Dimyati dan Dimyati, 2003).
b.
Metode Simpleks
Metode simpleks adalah suatu prosedur aljabar, yang melalui
serangkaian operasi-operasi berulang, dapat memecahkan suatu masalah yang
terdiri dari tiga variabel atau lebih.Untuk masalah-masalah dengan empat
variabel keputusan atau empat persamaan batasan, perhitungan nyata sebaiknya
menggunakan program komputer “QS3” (Quantitative
System Three).
Taha (2003), mengemukakan pendapatnya mengenai metode
simpleks sebagai berikut : The simplex
method is an iterative process that starts at a feasible corner point, normally
the origin and systematically moves from one feasible extreme point to another
until the optimum point is eventually reaced. Artinya, metode simpleks
adalah suatu proses berulang-ulang yang dimulai dari sudut daerah fisibel,
secara beraturan dan sistematis yang bergerak dari satu titik daerah fisibel ke
daerah lainnya sampai titik yang paling optimal.
Langkah-langkah penyelesaian dengan menggunakan metode
simpleks (Pangestu , Marwan dan Handoko, 2000), yaitu:
1)
Merubah fungsi
tujuan dan batasan-batasan.
Fungsi tujuan
diubah menjadi fungsi implisit, artinya semua CjXij bergeser
ke kiri. Pada bentuk standar, semua batasan mempunyai tanda ≤ ketidaksamaan ini
harus diubah menjadi kesamaan dengan menambah slack variabel (Xn+1,
Xn+2,…..Xn+m).
2)
Menyusun
persamaan-persamaan ke dalam tabel.
Setelah formulasi dirubah, kemudian disusun kedalam tabel.
3)
Memilih kolom kunci.
Kolom kunci
adalah kolom yang mempunyai dasar untuk mengubah tabel.Pilihlah kolom yang
mempunyai nilai pada garis fungsi tujuan yang bernilai negatif dengan angka
terbesar. Jika suatu tabel tidak memiliki nilai negatif pada baris fungsi
tujuan, maka tabel tersebut tidak bisa dioptimalkan lagi ( sudah optimal).
4)
Memilih baris
kunci.
Baris kunci
adalah merupakan baris dasar untuk merubah tabel. Untuk itu carilah dahulu
indek tiap-tiap baris dengan cara membagi nilai-nilai pada kolom NK dengan
nilai yang sebaris pada kolom kunci.
Index =
Nilai baris
kunci dirubah dengan cara membagi dengan angka kunci. Kemudian gantilah
variabel dasar pada baris itu dengan variabel yang terdapat dibagian atas kolom
kunci.
5)
Merubah
nilai-nilai baris kunci.
Nilai baris
kunci diubah dengan cara membaginya dengan angka kunci.
6)
Merubah
nilai-nilai selain pada baris kunci
Nilai-nilai
baris yang lain, selain pada baris kunci dapat diubah dengan rumus sebagai
berikut :
Baris baru =
baris lama – (koefisien pada kolom kunci) x nilai baru baris kunci.
7)
Melanjutkan
perbaikan-perbaikan/perubahan-perubahan.
Ulangi
langkah-langkah perbaikan mulai langkah 3 sampai langkah 6 untuk memperbaiki
tabel-tebel yang telah diubah/diperbaiki nilainya.Perubahan baru berhenti
setelah pada baris pertama (fungsi tujuan) tidak ada yang bernilai negatif.
c.
Metode Penalty (Teknik M)
Untuk menyelesaikan persoalan linear programming
dengan pembatas bertanda ≥ dan atau =, diperlukan adanya variabel dummy
(variabel palsu) yang disebut variabel artifisial, sehingga variabel basis awal
bisa tetap ada. Variabel artifisial ini hanya digunakan untuk memulai solusi,
dan harus dihilangkan pada akhir solusi. Untuk menghilangkannya harus diberikan
penalty M (M bilangan positif yang sangat besar) pada setiap variabel
artifisial dalam fungsi tujuannya dengan menggunakan teknik M (Dimyati dan
Dimyati, 2003)
d.
Metode Aljabar
Program linier dengan
dengan metode aljabar yaitu menyelesaikan permasalahan dalam perhitungan
matematika agar mendapatkan nilai yang optimum (maksimum atau minimum). Secara
umum model matematika yang diselesaikan merupakan pertidaksamaan dan metode
yang digunakan umtuk mengubah ketaksamaan menjadi kesamaan yaitu metode
aljabar. Adapun langkah-langkah dalam metode aljabar dengan melakukan
standarisasi ketidaksamaan menjadi kesamaan, yaitu: 1. Memasukkan unsur
variable semua ke ruas kiri fungsi kendala. 2. Unsur fungsi kendala bertanda ≤
dilakukan dengan penambahan slack variables. Slack variables yaitu suatu
variable yang ditambahkan disebelah kiri tanda ketidaksamaan agar ketidaksamaan
menjadi persamaan. 3. Unsur fungsi kendala bertanda ≥ dilakukan dengan pengurangan
atau surplus variables. Surplus variables yaitu variable yang dikurangkan di
dalam suatu ketidaksamaan agar supaya menjadi persamaan.