Asumsi-asumsi Dasar Program Linier (skripsi dan tesis)

Salah satu ciri khas model program linier ini ialah bahwa ia
didukung oleh lima macam asumsi yang menjadi tulang punggung model
tersebut. Asumsi-asumsi tersebut adalah sebagai berikut:
a. Linearitas
Asumsi ini menginginkan agar perbandingan antara input yang
satu dengan input lainnya, atau untuk suatu input dengan output
besarnya tetap dan terlepas (tidak tergantung) pada tingkat produksi.
Jika fungsi tujuan, cjxj, bersifat nonlinear, maka teknik program linier
ini tidak dapat dipakai.
b. Proporsionalitas
Asumsi ini menyatakan bahwa jika peubah pengambilan
keputusan, xj, berubah maka dampak perubahannya akan menyebar
dalam proporsi yang sama terhadap fungsi tujuan, cjxj, dan juga pada
kendalanya, aijxj. Misalnya, jika kita naikkan nilai xj dua kali, maka
secara proporsional (seimbang dan serasi) nilai-nilai aijxj-nya juga akan
menjadi dua kali lipat. Implikasi asumsi ini ialah bahwa dalam model
program linier yang bersangkutan tidak berlaku hukum kenaikan yang
semakin menurun.
c. Aditivitas
Asumsi ini menyatakan bahwa nilai parameter suatu kriteria
optimasi (koefisien peubah pengambilan keputusan dalam fungsi
tujuan) merupakan jumlah dari nilai individu-individu cj dalam model
program linier tersebut. Dampak total terhadap kendala ke-i
merupakan jumlah dampak individu terhadap peubah pengambilan
keputusan xj.
d. Divisibilitas
Asumsi ini menyatakan bahwa peubah-peubah pengambilan
keputusan xj, jika diperlukan dapat dibagi ke dalam pecahan-pecahan,
yaitu bahwa nilai-nilai xj tidak perlu integer (hanya 0 dan 1 atau
bilangan bulat), tapi boleh noninteger (missal ½; 0,58; 38,987, dan
sebagainya).
e. Deterministik
Asumsi ini menghendaki agar semua parameter dalam model
program linier (yaitu nilai-nilai cj, aij, dan bi) tetap dan diketahui atau
di tentukan secara pasti (Nasendi, 1985).
4. Macam-macam solusi program linier
Setelah persoalan program linier diidentifikasikan variabel
keputusan, fungsi tujuan, dan pembatasannya yang diformulasikan ke
dalam bentuk matematika, maka persoalan tersebut dapat dipecahkan
menggunakan beberapa metode seperti metode grafik, metode substitusi,
dan metode simpleks.
a. Metode Grafik
Pemecahan persoalan program linier menggunakan metode grafik
terdiri dari dua fase yaitu (Ruminta, 2009):
1) Menentukan ruang/daerah penyelesaian (solusi) yang feasible
yaitu menemukan nilai variabel keputusan di mana semua
pembatasan bertemu.
2) Menentukan solusi optimal dari semua titik di ruang/ daerah
feasible
b. Metode Substitusi
Penyelesaian program linier dengan metode substitusi
mempunyai beberapa tahapan yaitu (Ruminta, 2009):
1) Mengubah ketidaksamaan pembatasan menjadi persamaan
pembatasan dengan cara menambahkan variabel slack (Surplus)
untuk persoalan maksimum (minimum).
2) Tentukan seluruh pemecahan dasar dari persamaan pembatasan dan
tentukan pemecahan yang memenuhi semua syarat pembatasan
(solusi feasible).
3) Tentukan salah satu dari solusi feasible tersebut yang memenuhi
syarat fungsi tujuan atau solusi optimum.
c. Metode simpleks
Metode simpleks adalah suatu teknik penyelesaian program
linier secara iterasi. Metode simpleks mencari suatu penyelesaian dasar
feasible ke penyelesaian dasar feasible yang lainnya dilakukan
berulang-ulang sehingga akhirnya tercapi suatu penyelesaian optimum
(Ruminta, 2009).
Pada metode simpleks persoalan program linier selalu diubah
menjadi persoalan program linier standar, dimana setiap
ketidaksamaan pembatasan diekspresikan dalam bentuk persamaan
pembatasan dengan menambah variabel slack atau surplus.
Menurut Siringoringo (2005) ada beberapa istilah yang sangat
sering digunakan dalam metode simpleks, diantaranya :
1) Iterasi adalah tahapan perhitungan dimana nilai dalam perhitungan
itu tergantung dari nilai tabel sebelumnya.
2) Variabel non basis adalah variabel yang nilainya diatur menjadi
nol pada sembarang iterasi.
3) Variabel basis merupakan variabel yang nilainya bukan nol pada
sembarang iterasi. Pada solusi awal, variabel basis merupakan
variabel slack (jika fungsi kendala merupakan pertidaksamaan ≤ )
atau variabel buatan (jika fungsi kendala menggunakan
pertidaksamaan ≥ atau =). Secara umum, jumlah variabel basis
selalu sama dengan jumlah fungsi pembatas (tanpa fungsi non
negatif).
4) Solusi atau nilai kanan merupakan nilai sumber daya pembatas
yang masih tersedia. Pada solusi awal, nilai kanan atau solusi
sama dengan jumlah sumber daya pembatas awal yang ada,
karena aktivitas belum dilaksanakan.
Model Optimalisasi Kebutuhan..., Elia Zubaedah, FKIP UMP, 2013
16
5) Variabel slack adalah variabel yang ditambahkan ke model
matematik kendala untuk mengkonversikan pertidaksamaan ≤
menjadi persamaan (=). Penambahan variabel ini terjadi pada
tahap inisialisasi. Pada solusi awal, variabel slack akan berfungsi
sebagai variabel basis.
6) Variabel surplus adalah variabel yang dikurangkan dari model
matematik kendala untuk mengkonversikan pertidaksamaan ≥
menjadi persamaan (=). Penambahan ini terjadi pada tahap
inisialisasi. Pada solusi awal, variabel surplus tidak dapat
berfungsi sebagai variabel basis.
7) Variabel buatan adalah variabel yang ditambahkan ke model
matematik kendala dengan bentuk ≥ atau = untuk difungsikan
sebagai variabel basis awal. Penambahan variabel ini terjadi pada
tahap inisialisasi.
8) Kolom pivot (kolom kerja) adalah kolom yang memuat variabel
masuk. Koefisien pada kolom ini akan menjadi pembagi nilai
kanan untuk menentukan baris pivot (baris kerja).
9) Baris pivot (baris kerja) adalah salah satu baris dari antara
variabel basis yang memuat variabel keluar.
10) Elemen pivot (elemen kerja) adalah elemen yang terletak pada
perpotongan kolom dan baris pivot. Elemen pivot akan menjadi
dasar perhitungan untuk tabel simpleks berikutnya.
11) Variabel masuk adalah variabel yang terpilih untuk menjadi
variabel basis pada iterasi berikutnya. Variabel masuk dipilih satu
dari antara variabel non basis pada setiap iterasi. Variabel ini pada
iterasi berikutnya akan bernilai positif.
12) Variabel keluar adalah variabel yang keluar dari variabel basis
pada iterasi berikutnya dan digantikan oleh variabel masuk.
Variabel keluar dipilih satu dari antara variabel basis pada setiap
iterasi. Variabel ini pada iterasi berikutnya akan bernilai nol.
Sebelum melakukan perhitungan iteratif untuk menentukan
solusi optimal, pertama sekali bentuk umum pemrograman linier
dirubah ke dalam bentuk baku terlebih dahulu. Bentuk baku dalam
metode simpleks tidak hanya mengubah persamaan kendala ke dalam
bentuk sama dengan, tetapi setiap fungsi kendala harus diwakili oleh
satu variabel basis awal. Variabel basis awal menunjukkan status
sumber daya pada kondisi sebelum ada aktivitas yang dilakukan.
Dalam kasus minimalisasi yang berfungsi sebagai variabel basis adalah
variabel buatan / artificial variable. Perumusannya dalam fungsi tujuan
memiliki koefisien sebesar +M. Pendekatan ini disebut juga sebagai ”
metode M besar ”. Nilai koefisien peubah artifisial itu sendiri adalah
sebenarnya tak terhingga.
Dalam perhitungan iteratif, kita akan bekerja menggunakan
tabel. Bentuk baku yang sudah diperoleh, harus dibuat ke dalam
bentuk tabel.
Langkah-langkah penyelesaian adalah sebagai berikut :
a. Merubah model program linier menjadi model persamaan linier.
b. Menyusun tabel simpleks awal.
c. Menghitung nilai Zj pada setiap kolom variabel.
d. Menghitung nilai (Cj-Zj) pada setiap kolom variabel.
e. Periksa nilai-nilai (Cj-Zj), jika (Cj-Zj) ≤ 0 (untuk tujuan
memaksimumkan) maka ke langkah (l) atau jika (Cj-Zj) ≥ 0 (untuk
tujuan meminimumkan) maka ke langkah (l).
f. Tentukan kolom kunci berdasarkan nilai (Cj-Zj). Kolom kunci
terletak pada kolom variabel yang nilai (Cj-Zj) positif terbesar jika
tujuannya memaksimumkan, sebaliknya kolom kunci terletak pada
kolom variabel yang nilai (Cj-Zj) negatif terbesar jika tujuannya
meminimumkan.
g. Tentukan baris kunci berdasarkan nilai (bi / akk) positif terkecil.
h. Tentukan angka kunci (ak), yaitu angka yang terletak pada kolom
kunci dan baris kunci.
i. Ganti variabel yang terletak pada baris kunci dengan variabel yang
terletak pada kolom kunci.
j. Lakukan transformasi setiap baris yang dimulai dengan baris kunci
dengan rumus transformasi sebagai berikut:
Bk baru = (Bk lama) / ak
Bi baru = Bi – ai,kk * Bk baru
k. Kembali ke langkah (c)
l. Solusi optimal diperoleh, dimana nilai variabel basis untuk masingmasing
baris terletak pada kolom bi.