2.1 Linear
Programming
Linear progreming
adalah suatu metode analitik paling terkenal yang merupakan suatu bagian
kelompok teknik-teknik yang disebut programasi matematik. Sebutan “linear”
dalam linear programming berarti
hubungan-hubungan antar factor-faktor adalah bersipat linear atau konstan, atau
fungsi-fungsi matematik yang di sajikan dalam yang di sajikan dalam model
haruslah fungsi-fungsi linear (Handoko,
1984).
Program
linear (Linear Programing) adalah
salah satu teknik OR yang digunakan
paling luas dan di ketahui dengan baik, dan merupakan metode marematik dalam
melokasikan sumberdaya yang langka untuk mencapai tujuan tunggal seperti
memaksimumkan keuntungan atau meminimumkan biaya (Mulyono,
2004).
2.2
Model linear Programming
Masalah linear programming dapat dinyatakan sebagai proses optimasi suatu
fungsi tujuan (objective function)
dalam bentuk : Maksimumkan (minimumkan)Z = C1 X1 + C2
X2 +….+ Cn Xn dengan mengingat
batasan-batasan sumber danya dalam bentuk (Handoko, 1984):
A1]
X1 + A12 X2 + ……………+ A 1 n Xn
≤ B1
A2]
X1 + A22 X2 + ……………+ A 2 n
Xn ≤ B2
Am
1 X1 + Am 2 X2
+ ……………+ A m n Xn ≤ Bm
Dan
X1
≥ 0 , X2 ≥ 0 ……………….. ….Xn ≥ 0
Dimana
Gj , Aij dan Bi adalah masukan-masukan konstan
yang sering di sebut sebagai parameter model.
2.3 Formulasi Model Linear Programming
Masalah
keputusan yang sering dihadapi analis adalah alokasi optimum sumber daya yang
langka. Sumber daya dapat berupa uang, tenaga kerja, bahan mentah, kapasitas
mesin, waktu, ruangan atau teknologi. Tugas analisis adalah mencapai hasil
terbaik yang mungkin dengan keterbatasan
sumber daya itu. Hasil yang diinginkan mungkin di tunjukan sebagai maksimisasi
dari beberapa ukuran seperti profil, penjualan dan kesejahtraan, atau
minimisasi seperti pada biaya, waktu dan jarak. Setelah masalah
diidentifikasikan, tujuan ditetapkan langkah selanjutnya adalah formulasi model
matematik yang meliputi tigatahap seperti berikurt (Mulyono, 2004) :
a. Tentukan
variabel yang tak diketahui (variabel keputusan) dan yatakan dalam simbol
matematis.
b. Membentuk
pungsi tujuan yang di tunjukan sebagai suatu hubungan linear (bukan perkalian)
dari variabel keputusan.
c. Menentukan
semua kendala masalah tersebut dan mengekspresikan dalam persamaan atau
pertidaksamaan yang juga merupakan hubungan linear dari variabel keputusan yang
mencerminkan keterbatasan sumberdanya masalah itu.
2.4 Asumsi-asumsi Linear Programming
Linear
programming dapat diterapkan dalam kehidupan
sehari-hari, karena linear programming dapat
menentukan nilai optimum yang akan dicari dari asumsi-asumsi. Berikut ini
adalah asumsi-asumsi dari linear
programming antara lain (Handoko, 1984):
1. Tujuan
dan persamaan setiap batasan harus linear. Ini mencakup pengertian bahwa
perubahan nilai Z dan penggunaan sumber daya terjadi secara proporsional Fungsi
dengan perubahan tingkat kegiatan (proportional)
; sebagai contoh bila produksi satu unit memerlukan tiga orang, maka di
butuhkan enam orang untuk memproduksi dua unit dalam waktu yang sama.
2. Parameter-parameter
harus di ketahui atau dapat diperkirakan dengan pasti (Deterministic). Dengan kata lain , probabilitas terjadinya setiab
nilai Cj, Aij dan Bi dianggap 1,0.
3. Variabek-variabel
keputusan harus dapat di bagi; ini berarti bahwa suatu penyelesaian “feasible”
dapat berupa bilangan pecahan, missal : ½ X1 atau ¼ X2, dan
sebagainya. (Dalam kenyataannya ,hal ini akan di hilangkan pada situasi-situasi
seperti scheduling penerbangan pesawat udara).
2.5 Metoda Grafik
Metoda grafik hanya dapat di terapkan untuk
memecahkan masalah – masalah linear programming yang menyangkut dua variable
keputusan ( atau tiga variable dengan grafik tiga dimensi. Langkah – langkah
menyelesaikan dengan menggunakan metoda grafik dapat diperinci sebagai berikut
(Handoko, 1984) :
1.
Merumuskan masalah
dalam bentuk matematika.
2. Menggambarkan
persamaan – persamaan batasan.
3. Menentukan
daerah”feasibilitas”.
4. Menggambarkan
fungsi tujuan.
5. Mencari
titik optimum.
2.6 Metoda
Simplex
Metoda
simplex merupakan algoritma untuk memecahkan masalah umum linear programming.
Metoda simplex adalah suatu prosedur
aljabar, yang melalui serangkain oprasi – oprasi berulang, dapat memecahkan
suatu masalah yang terdIri tiga variable atau lebih.(Handoko, 1984)
Metode simplks merupakan prosedur aljabar yang bersifat alternatif, yang
bergerak selangkah demi selangkah, dimulai dari suatu titik ekstrem pada daerah
fisibel (ruang solusi) menuju ketitik ekstrem yang optimum. Untuk dapat lebih
memahami uraian selanjutnya, berikut ini diberikan pengertian dari beberapa
terminologi dasar yang banyak digunakan dalam membicarakan metode simpleks.
Untuk itu, perhatikan kembali programa linier berikut ini
(Dimyati, 1994):
Maks. Atau min. : Z = C1 X1 + C2
X2 +.........+Cn Xn
Berdasarkan : A11 X1 + A12
X2 +.......+A1n Xn = B1
A21 X1 + A22 X2
+.......+A2n Xn = B2
Am1
X1 + Am2 X2+.......+Amn Xn = Bm
Xi ≥ 0 (i = 1, 2, ...., n)
Maka
pembatas dari model tersebut dapat dituliskan kedalam bentuk sistem persamaan
AX = b. Perhatikan suatu sistem AX = b dari m persamaan linier dalam n variabel
(n > m). Definisinya
adalah sebagai berikut (Dimyati, 1994):
1.
Solusi Baris
Solusi
baris untuk ax = b adalah solusi dimana terdapat sebanyak-banyaknya m variabel
berharga bukan nol. Untuk mendapatkan solusi basis dari ax = b maka sebanyak (n-m) variabel harus dinolkan. Variabel-variabel
yang dinolkan ini disebut variabel bukan basis (NBV). Selanjutnya, dapatkan harga dari n – (n-m) = m variabel lainnya yang memenuhi ax = b,
yang disebut variabel basis (bv)
2.
Solusi Basis
Fisibel
Jika
suatu variabel pada suatu solusi basis berharga bukan negatif, maka solusi itu
disebut solusi basis fisibel (BFS).
3.
Solusi Fisibel
Titik Ekstrem
Solusi fisibel
titik ekstrem atau titik sudut adalah solusi fisibel yang tidak terletak pada
suatu segment garis yang menghubungkan dua solusi fisibel lainnya. Jadi titik
(0,0), (0,6), (2,6), (4,3), dan (4,0) adalah solusi-solusi fisibel titik sudut
atau titik ekstrem pada persoalan PT. Indah Gelas. Apabila ada sejumlah n (n
< 3) buah variabel keputusan, maka definisi diatas tidak cocok lagi untuk
mengidentifikasi solusi fisibel titik sudut (titik ekstrem) sehingga
pembuktiannya harus dengan cara aljabar.
2.7 Solusi Simpleks
Solusi Simpleks
merupakan prosedur aljabar yang bersifat iterative, yang bergerak selangkah
demi selangkah, dimulai dari suatu titik ekstrem pada daerah fisibel (ruang
solusi) menuju ke titik ekstrem yang optimum. Solusi
ini pertama kali dikembangkan oleh George B. Dantzig pada tahun 1947, metode
ini digunakan untuk menyelesaikan masalah Pemrograman Linier melalui tahapan
(perhitungan ulang) dimana langkah-langkah perhitungan yang sama diulang sampai
tercapai solusi yang optimal. Tahapan penyelesaian
dalam solusi simpleks (Irawan, 2000) :
1.
Tabulasikan persamaan-persamaan yang diperoleh pada langkah
2.
Menentukan
entering variabel.
3.
Menentukan
leaving variabel.
4.
Menentukan
persamaan pivot baru.
5.
Menentukan persamaan-persamaan baru selain persamaan pivot baru.
6.
Lanjutkan
perbaikan.
Solusi
simpleks terdapat tiga ciri dari suatu bentuk baku pemrograman linier, antara
lain semua kendala harus berada dalam bentuk persamaan dengan nilai kanan tidak
negatif, semua variabel yang tidak terlibat bernilai negatif, dan fungsi obyektif
dapat berupa maksimasi maupun minimasi. (Irawan,2000).
Tidak ada komentar:
Posting Komentar