Pemrograman Linier

Pemrograman linier berasal dari kata pemrograman dan linier. Pemrograman disini mempunyai arti kata perencanaan dan linier ini berarti bahwa fungsi-fungsi yang digunakan merupakan fungsi linier.

Secara umum arti pemrograman linier adalah suatu teknik perencanaan yang bersifat analitis yang analisis-analisisnya memakai model matematika, dengan tujuan menemukan beberapa kombinasi alternative pemecahan masalah; kemudian dipilih yang terbaik diantaranya dalam rangka menyusun strategi dan langkah-langkah kebijaksanaan lebih lanjut tentang alokasi sumber daya dan dana yang terbatas guna mencapai tujuan dan sasaran yang diinginkan secara optimal.

Contoh dari suatu masalah pemrograman linier dapat dilihat pada contoh masalah (Metode Grafik)

Untuk merumuskan suatu masalah kedalam bentuk model pemrograman linier, harus dipenuhi syarat-syarat berikut:

• Tujuan masalah tersebut harus jelas dan tegas.

Pada contoh masalah, tujuan masalah tersebut jelas, yaitu ingin mendapatkan keuntungan yang maksimal.

• Harus ada sesuatu atau beberapa alternative yang ingin membandingkan.

Pada contoh masalah, alternative perbandingannya adalah kombinasi jumlah produksi dan keuntungan yang diperoleh.

• Adanya sumber daya yang terbatas.

Pada contoh masalah, sumber daya yang terbatas adalah waktu untuk subassembly, assembly dan inspeksi.

• Bisa dilakukan perumusan kuantitatif.

Fungsi tujuan dan kendala harus dapat dirumuskan secara kuantitatif.

• Adanya keterkaitan peubah.

Adanya hubungan keterkaitan antara peubah-peubah yang membentuk fungsi tujuan dan kendala.

Untuk membentuk suatu model pemrograman linier perlu diterapkan asumsi-asumsi berikut:

• Linearty

Fungsi obyektif dan kendala haruslah merupakan fungsi linier dan variabel keputusan. Hal ini akan mengakibatkan fungsi bersifat proposional dan additive, misalnya untuk memproduksi 1 kursi dibutuhkan waktu 5 jam, maka untuk memproduksi 2 kursi dibutuhkan 10 jam.

• Divisibility

Nilai variabel keputusan dapat berupa bilangan pecahan. Apabila diinginkan solusi berupa bilangan bulat (integer), maka harus digunakan metode untuk integer programming.

• Nonnegativity

Nilai variabel keputusan haruslah nonnegative(=>0).

• Certainty

Semua konstanta (parameter) yaitu cj, aij, dan bi diasumsikan mempunyai nilai yang pasti (sudah tertentu). Bila nilai-nilai parameternya probabilistic, maka harus digunakan formulasi pemrograman masalah stokastik.

Walaupun ada beberapa batasan asumsi yang harus ada, namun pemrograman linier ini dapat digunakan untuk memecahkan masalah-masalah pengalokasian sumber daya yang terbatas guna mendapatkan hasil yang optimal.

Beberapa metode digunakan untuk menyelesaikan masalah pemrograman linier ini. Berikut ini akan dibahas dua metode yang umum digunakan, yaitu metode grafik dan metode simpleks.

Metode Grafik

Tujuan dari metode grafik adalah untuk memberikan dasar-dasar dari konsep yang digunakan dalam teknik SIMPLEKS. Prosedur umumnya adalah untuk mengubah suatu situasi deskriptif kedalam bentuk masalah pemrograman linier dengan menentukan variabel-variabelnya, konstantanya, fungsi obyektifnya dan batasan-batasannya, sehingga masalah tersebut dapat disajikan dalam bentuk grafik dan diinterpretasikan solusinya, untuk menggunakan metode grafika, dilalui tahapan-tahapan berikut:

• Identifikasi variabel keputusan
• Identifikasi fungsi obyektif
• Identifikasi kendala-kendala
• Menggambarkan bentuk grafik dari semua kendala
• Identifikasi daerah solusi yang layak pada grafik
• Menggambarkan bentuk grafik dari fungsi obyektif dan menentukan titik yang memberikan nilai obyektif optimal pada daerah solusi yang layak
• Mengartikan solusi yang diperoleh

Metode Simpleks

Algoritma simpleks ini adalah suatu prosedur matematis untuk mencari solusi optimal dari suatu masalah pemrograman linier yang didasarkan pada proses iterasi. Jadi pada prinsipnya prosedur ini diawali dengan penentuan suatu solusi awal yang secara terus-menerus diperbaiki hingga diperoleh solusi yang optimal.

Ada tiga cirri utama suatu bentuk baku pemrograman  linier untuk algoritma simpleks. Ciri pertama adalah semua kendala harus berada dalam bentuk persamaan dengan nilai kanan tidak negative. Ciri kedua adalah semua variabel tidak yang terlibat tidak dapat bernilai negative. Dan cirri terakhir adalah fungsi obyektif dapat berupa maksimisasi maupun minimisasi. Untuk memenuhi ciri-ciri tersebut, maka dibuat beberapa aturan pengubahan bentuk yang tidak memenuhi bentuk baku kedalam bentuk baku.

Sumber: Diktat Kuliah Pengantar Riset Operasional Universitas Gunadarma