Linear programing merupakan teknik matematis yang digunakan untuk memudahkan pengguna dalam proses pengambilan keputusan yang tepat. Penggunaan teknik ini adalah dengan mendapatkan maksimisasi atau minimisasi. linear programming digunakan hanya untuk satu tujuan saja, sedangkan untuk 2 tujuan atau lebih harus menggunakan Goal programming.
Linear programing berkaitan dengan pengalokasian sumber daya-sumber daya yang digunakan. Semua sumber daya pada umumnya jumlahnya sangat terbatas. Maka itu pengalokasian sumber daya tersebut harus dilaksanakan dengan cara yang terbaik agar mendapatkan hasil yang optimal.
Linear programing berkaitan dengan pengalokasian sumber daya-sumber daya yang digunakan. Semua sumber daya pada umumnya jumlahnya sangat terbatas. Maka itu pengalokasian sumber daya tersebut harus dilaksanakan dengan cara yang terbaik agar mendapatkan hasil yang optimal.
Dalam Memecahkan masalah melalui linear programming kita harus mengenal dan menggunakan model matematis. Fungsi-fungsi matematis yang dimaksud dan yang disajikan adalah fungsi-fungsi linear .
Linear programming adalah metode matematis yang dapat digunakan untuk membantu penggunanya dalam mengambil keputusan, seperti:
a. Produc mix
Menentukan banyak unit setiap produk, yang bertujuan agar dapat meminimalkan biaya yang dikeluarkan dan memaksimalkan keuntungan yang didapatkan. Dalam memutuskan sebuah keputusan yang tepat perlu diperhatikan kendala-kendala, seperti jumlah permintaan, kapasitas produksi, dlln.
b. Investasi
Menentukan banyak dana yang akan dikeluarkan. Dalam hal ini yang perlu diperhatikan adalah kemampuan organisasi dalam mengeluarkan biaya.
c. Produksi dan persediaan
Menentukan banyak produk akan diproduksi setiap periode waktu tertentu agar permintaan konsumen dapat terpenuhi secara maksimal. Hal yang harus diperhatikan adalah biaya penyimpanan dan biaya lainnya.
d. Promosi dan iklan
Menentukan banyak dana yang akan dikeluarkan untuk memperkenalkan produk pada konsumen. Hal yang harus diperhatikan dalam hal ini adalah tujuan pemasaran, anggaran promosi, batas dana yang akan dikeluarkan.
e. distribusi dan transportasi
membahas biaya yang akan dikeluarkan untuk transportasi dari tempat produksi sampai ke tujuan.
Dalam merumuskan model linear programming , kita harus melakukan beberapa langkah-langkah berikut ini:
1. Menentukan variabel keputusan yang dicari dan memberi notasi dalam bentuk matematis karena untuk menggunakan linear programming harus menggunakan fungsi-fungsi linear .
2. Menentukan objective function untuk menggambarkan tujuan dalam permasalahan linear programing yang berkaitan dengan pengaturan secara optimal sumber daya yang digunakan agar memperoleh kuntungan maksimal dan biaya yang dikeluarkan sedikit.
Fungsi yang digunakan adalah:
Z=C1X1+C2X2+C3X3+............+CnXn
3. Menentukan constraints dari variabel keputusan. Lalu dituliskan dalam bentuk persamaan dan pertidaksamaan linear . Fungsi batasan terdiri dari 2 macam yaitu:
a. Fungsi batasan fungsional:
- a11x1 + a12x2 + a13x3 +.....+ a1nxn = b1
- a21x1 + a22x2 + a23x3 +......+ a2nxn = b2
- am1x1 + am2x2 + am3x3 +......+ amnxn = bm
b. fungsi batasan non negatif:
x1,x2,x3.....xn =0
dalam memecahkan masalah melalui linear programming bisa menggunakan metode grafik yang pada umumnya mempunyai 2 variabel keputusan. Metode grafik ini menggambarkan bagian yang layak didefinisikan sebagai ruang yang diliputi oleh batasan-batasan.
Langkah-langkah penyelesaian metode ini adalah:
a. menentukan fungsi tujuan dan diformulasikan dalam bentuk matematis
b. indentifikasi batasan-batasan yang berlaku dan diformulasikan dalam bentuk matematis
c. menggambarkan semua batasan kedalam sistem salib sumbu
d. mencari titik optimal yang dihubungkan dengan fungsi tujuan
Dalam metode grafik ini terdapat beberapa istilah yang harus diketahui, yaitu:
a. minimisasi
permasalahan maksimisasi yakni tujuan yang ingin dicapai yaitu keuntungan yang maksimal. Jika fungsi tujuan adalah minimisasi maka gambar fungsi Z harus digeser kekiri pada grafik. Bila membandingkan nilai Z dengan alternatif nilai Z terendah adalah alternatif optimal.
b. Ruang yang layak (feasible area)
Penyelesaian yang tidak melanggar batasan-batas yang ada
c. Bukan ruang yang layak ( no feasible area)
Artinya Tidak ada ruang yang feasible yang terjadi ketika batasan-batasan yang ada tidak menghasilkan daerah yang feasible.
d. Optimal solution
Feasible solution yang mempunyai nilai Z yang dioptimalkan, bisa maksimum atau minimum
e. MOS (multiple optimal solution)
Dapat terjadi apabila terdapat beberapa alternatif dalam masalah optimal solution.
f. Boundary equation
Jika suatu batasan “=” maka akan terjadi daerah feasible yang terletak disepanjang garis.
g. Corner point feasible solution
Feasible solution yang terletak pada sudut perpotongan antara 2 garis.
h. Corner point infeasible solution
Titik yang terletak pada perpotongan 2 garis tetapi di luar daerah feasible.
i. No optimal solution
Terjadi apabila suatu permasalahan tidak mempunyai jawaban atau penyelesaian optimal.
Metode simplex adalah perkembangan metode aljabar yang hanya menguji sebagian dari jumlah solusi yang layak dalam bentuk tabel. Metode simplex merupakan merupakan metode yang lebih efisien untuk menghadapi persoalan linear programing yang memiliki variabel keputusan lebih dari 2.
Secara manual untuk membuat tabel simplex, terlebih dahulu membuat bentuk standar terlebih dahulu, yaitu,
a. Mengubah Nilai ruas kanan setiap kendala non negative.
Apabila nilai ruas kanan negatif maka kalikan dengan -1.
Contoh: 2X1+3X2 = -30,
di ubah menjadi: -2X1-3X2 = 30
b. Semua kendala harus berbentuk persamaan, kecuali kendala non negatif.
Apabila kendala berbentuk (=) harus diubah dengan cara menambahkannya dengan slack variabel.
Contoh: 2X1+3X2 = 30
Diubah menjadi: 2X1+3X2+S1= 30
Apabila kendala berbentuk (=) harus diubah dengan mengurangkannya dengan surplus variabel.
Contoh: 2X1+3X2 =30
Diubah menjadi: 2X1+3X2 -S2 =30
c. Semua nilai variabel keputusan harus non negatif.
d. Fungsi tujuan harus berbentuk maksimum.
Bila berbentuk minimum harus diubah menjadi maksimum dengan mengalikannya dengan (-1):
Contoh: Zmin = 2X1+3X2
Diubah menjadi: -Zmak= -2X1-3X2
Langkah-langkah dalam metode simplex tabel:
1. Ubah masalah linear programming kedalam bentuk standar.
2. Memeriksa apakah setiap kendala memiliki variabel basis .
Yaitu variabel yang memiliki koefisien satu, sedangkan pada kendala lain nilainya nol. Jika seandainya tidak, tambahkan dengan catu variabel buatan yang bertindak sebagai variabel basis. misalnya Q1 yang jumlahnya sesuai dengan kebutuhan.
3. Masukan semua nilai fungsi kendala ke dalam tabel simplex.
4. Masukan nilai koefisien fungsi tujuan pada baris Zj – Cj
Rumus yang digunakan pada awal tabel simplex: Zj-Cj = CByj- Cj
5. Tentukan kolom kunci
Yaitu kolom yang memiliki nilai negatif terbesar pada baris Zj-Cj. Jika terdapat dua nilai terbesar yang sama dapat dipilih salah satu.
6. Tentukan baris kunci,
Nilai yang memiliki angka index terkecil dan bukan negatif
7. Angka kunci
Angka yang terdapat pada persilangan bari kunci dan kolom kunci. Cari angka baru yang terdapat pada baris kunci dengan membagi semua angka yang terdapat pada baris kunci dengan baris kunci.
8. Mencari angka baru pada baris lain
Rumus : angka baru = nilai pada baris lama dikurangi dengan perkalian koefisien pada kolom kunci dengan angka bari baris kunci.
9. Apabila solusi optimal belum ditemukan maka ulangi dengan menentukan kolom kunci pada langkah kelima diatas, sehingga nilai yang terdapat pada baris Zj – Cj = 0
Catatan untuk linear programming:
a. Metode grafik digunakan apabila masalah linear programming hanya memiliki 2 variabel dengan langkah: menggambarkan grafik kendala dan tentukan daerah feasible, menggambarkan garis fungsi tujuan, menggeser garis fungsi tujuan, tentukan solusi optimumnya.
b. Dalam beberapa kasus terkadang penyelesaian linear programming dengan menggunaka metode grafik bisa terjadi beberapa hal berikut: multiple optimal solution, no feasible solution, no optimal solution.
c. Metode simplex digunakan apabila pada linear programming variabel keputusan lebih dari dua variabel maka penyelesaian dengan menggunakan metode simplex.