Pemrograman Linier
Linear
Programming
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 = C1X1 + 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, karenalinear 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 Bidianggap 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 linearprogramming.
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).
0 komentar:
Posting Komentar