LINEAR PROGRAMMING

Masalah keputusan yang biasa dihadapi para analis adalah alokasi optimum sumber daya yang langka. Sumber daya dapat berupa modal, tenaga kerja, bahan mentah, kapasitas mesin, waktu, ruangan atau teknologi. Rugas analis adalah mencapai hasil terbaik yang mungkin dengan keterbatasan sumber daya ini. Hasil yang diinginkan mungkin ditunjukkan sebagai maksimasi dari beberapa ukuran seperti profit, penjualan dan kesejahteraan, atau minimasi seperti biaya, waktu dan jarak.
Setelah masalah diidentifikasikan, tujuan diterapkan, langkah selanjutnya adalah formulasi model matematik yang meliputi tiga tahap :
1. Menentukan variabel yang tak diketahui (variabel keputusan) dan menyatakan dalam symbol matematik
2. Membentuk fungsi tujuan yang ditunjukkan sebagai suatu hubungan linier (bukan perkalian) dari variabel keputusan
3. Menentukan semua kendala masalah tersebut dan mengekspresikan dalam persamaan dan pertidaksamaan yang juga merupakan hubungan linier dari variabel keputusan yang mencerminkan keterbatasan sumberdaya masalah itu
Linear programming (program linier) merupakan salah satu teknik penyelesaian riset operasi dalam hal ini adalah khusus menyelesaikan masalah-masalah optimasi (memaksimalkan atau meminimumkan) tetapi hanya terbatas pada masalah-masalah yang dapat diubah menjadi fungsi linier. Demikian pula kendala-kendala yang ada juga berbentuk linier.
Persoalan program linier adalah suatu persoalan untuk menentukan besarnya masing-masing nilai variabel (variable pengambilan keputusan) sedemikian rupa sehingga nilai funsi tujuan atau objektif (objective function) yang linier menjadi optimum (maksimum atau minimum) dengan memperhatikan pembatasan-pembatasan (kendala-kendala) yang ada yaitu pembatasan ini harus dinyatakan dengan ketidaksamaan yang linier (linear inequalities).
Suatu persoalan disebut persoalan program linier apabila memenuhi hal-hal sebagai berikut :
1. Tujuan (objective)
Apa yang menjadi tujuan permasalahan yang dihadapi yang ingin dipecahkan dan dicari jalan keluarnya. Tujuan ini harus jelas dan tegas yang disebut fungsi tujuan (objective function). Fungsi tujuan tersebut dapat berupa dampak positip, manfaat-manfaat, atau dampak negatif.
2. Alternatif perbandingan.
Harus ada sesuatu atau alternatif yang ingin diperbandingkan, misalnya antara kombinasi waktu tercepat dan biaya tertinggi dengan waktu terlambat dan biaya terendah.
3. Sumber Daya
Sumber daya yang dianalisis harus berada dalam keadaan terbatas. Misalnya keterbatasan tenaga, bahanmentah terbatas, modal terbatas, ruangan untuk menyimpan barang terbatas, dan lain-lain.
4. Perumusan Kuantitatif.
Fungsi tujuan dan kendala tersebut harus dapat dirumuskan secara kuantitatif dalam model matematika.

5. Keterikatan Perubah.
Perubah-perubah yang membentuk fungsi tujuan dan fungsi kendala tersebut harus memiliki hubungan keterikatan hubungan keterikatan atau hubungan fungsional.


Linear Programming merupakan model umum yang dapat digunakan dalam pemecahan masalah pengalokasian sumber-sumber yang terbatas secara optimal. Masalah tersebut timbul apabila seseorang diharuskan untuk memilih atau menentukan tingkat setiap kegiatan yang akan dilakukannya, di mana masing-masing kegiatan membutuhkan sumber yang sama sedangkan jumlahnya terbatas. Secara sederhana, dapat diambil contoh bagian produksi suatu perusahaan yang dihadapkan pada masalah penentuan tingkat produksi masingmasing jenis produk dengan memperhatikan batasan faktor-faktor produksi: mesin, tenaga kerja, bahan mentah, dan sebagainya untuk memperoleh tingkat keuntungan maksimal atau biaya yang minimal.
Pada masa modern sekarang, Linear Programming masih menjadi pilihan dalam upaya untuk memperoleh tingkat keuntungan maksimal atau biaya yang minimal.
Dalam memecahkan masalah di atas, Linear Programming menggunakan model matematis. Sebutan “linear” berarti bahwa semua fungsi matematis yang disajikan dalam model ini haruslah fungsi-fungsi linier. Dalam Linear Programming dikenal dua macam fungsi, yaitu fungsi tujuan (objective function) dan fungsi-fungsi batasan (constraint function). Fungsi tujuan adalah fungsi yang menggambarkan tujuan/sasaran di dalam permasalahan Linear Programming yang berkaitan dengan pengaturan secara optimal sumber daya-sumber daya, untuk memperoleh keuntungan maksimal atau biaya minimal. Pada umumnya nilai yang akan dioptimalkan dinyatakan sebagai Z. Fungsi batasan merupakan bentuk penyajian secara matematis batasan-batasan kapasitas yang tersedia yang akan dialokasikan secara optimal ke berbagai kegiatan.
Pada dasarnya, persoalan Linear Programming dapat dirumuskan sebagai berikut :
Cari x1,x2, …, xj, …, xn.

sedemikian rupa sehingga
Z = c1×1 + c2×2 + … + cjxj + … + cnxn = Optimum (Maksimum atau Minimum)
Dengankendala:

Asumsi-asumsi Linear Programming
Asumsi-asumsi Linear Programming dapat dirinci sebagai berikut.
o Proportionality
Asumsi ini berarti bahwa naik turunnya nilai Z dan penggunaan sumber atau fasilitas yang tersedia akan berubah secara sebanding (proporsional) dengan perubahan tingkat kegiatan.
Z = C1X1 + C2X2 + C3X3 + …..CnXn
Setiap penambahan 1 unit X1 akan menaikkan Z dengan C1. Setiap penambahan 1 unit X2 akan menaikkan Z dengan C2, dan seterusnya.
a11X1 + a12X2 + a13X3 + ….. + anXn ≤ b1
Setiap penambahan 1 unit X1 akan menaikkan penggunaan sumber/fasilitas 1 dengan a11. Setiap penambahan 1 unit X2 akan menaikkan penggunaan sumber/fasilitas 1 dengan a12, dan seterusnya. Asumsinya adalah, setiap ada kenaikan kapasitas riil tidak perlu ada biaya persiapan (set up cost).

o Additivity
Asumsi ini berarti bahwa nilai tujuan tiap kegiatan tidak saling mempengaruhi, atau dalam Linear Programming dianggap bahwa kenaikan dari nilai tujuan (Z) yang diakibatkan oleh kenaikan suatu kegiatan dapat ditambahkan tanpa mempengaruhi bagian nilai Z yang diperoleh dari kegiatan lain.
Z = 3X1 + 5X2 di mana X1 = 10; X2 = 2;
Sehingga Z = 30 + 10 = 40
Jika X1 bertambah 1 unit, maka sesuai dengan asumsi, maka nilai Z menjadi 40 + 3 = 43. Jadi, nilai 3 karena kenaikan X1 dapat langsung ditambahkan pada nilai Z mula-mula tanpa mengurangi bagian Z yang diperoleh dari kegiatan 2 (X2). Dengan kata lain, tidak ada korelasi antara X1 dan X2.

o Divisibility
Asumsi ini menyatakan bahwa keluaran yang dihasilkan oleh setiap kegiatan dapat berupa bilangan pecahan. Demikian pula dengan nilai Z yang dihasilkan.

o Deterministic (certainty)
Asumsi ini menyatakan bahwa semua parameter yang terdapat dalam model Linear Programming (aij, bi, cj) dapat diperkirakan dengan pasti, meskipun jarang dengan tepat.
Apabila suatu masalah Linear Programming hanya mengandung dua kegiatan (variabel-variabel keputusan) saja, maka dapat diselesaikan dengan metode grafik. Bila terdapat lebih dari dua variabel maka metode grafik tidak dapat digunakan lagi, sehingga diperlukan metode simpleks. Metode ini lazim dipakai untuk menentukan kombinasi dari tiga variabel atau lebih.