Program Linear

1. Definisi Pemrograman Linear

Setiap perusahaan atau organisasi memiliki keterbatasan atas sumber dayanya, baik keterbatasan dalam jumlah bahan baku, mesin dan peralatan, ruang tenaga kerja, jam kerja, maupun modal. Dengan keterbatasan ini, perusahaan perlu merencanakan strategi yang dapat mengoptimalkan hasil yang ingin dicapai, baik itu berupa keuntungan maksimal atau biaya minimal. Berbagai cara lain telah ditemukan untuk tujuan itu, salah satu diantaranya pemrograman linear (Eddy, 2008).

Pemrograman Linear merupakan metode  matematik dalam mengalokasikan sumber daya yang terbatas untuk mencapai suatu tujuan seperti memaksimumkan keuntungan dan meminimumkan biaya. Pemrograman Linear banyak diterapkan dalam masalah ekonomi, industri, militer, sosial dan lain-lain. Pemrograman Linear berkaitan dengan penjelasan suatu kasus dalam dunia nyata sebagai suatu model matematik yang terdiri dari sebuah fungsi tujuan linear dengan beberapa kendala linear (Siringoringo, 2005).

1.1.Sejarah Singkat Pemrograman Linear

Pemrograman linear sebetulnya sudah lahir pada tahun 1939 oleh ide seorang ahli matematika Rusia bernama L. V. Kantorovich dengan metode yang terbatas. Akan tetapi, di Rusia ide ini tidak berkembang. Kemudian pada tahun 1947 seorang ahli matematika dari Amerika Serikat yaitu George B. Dantzig mengembangkan dan menemukan cara memecahkan pemrograman linear tersebut dengan “metode simpleks” (Supranto,1983).

1.2. Sifat Dasar Pemrograman Linear

`           Sifat-sifat dasar atau Karakteristik Pemrograman Linear adalah sebagai berikut:

• Sifat linearitas suatu kasus dapat ditentukan dengan menggunakan beberapa cara. Secara statistik, cara ini dapat diperiksa kelinearan menggunakan grafik (diagram pencar).
• Sifat proporsional dipenuhi jika kontribusi setiap variabel pada fungsi tujuan atau penggunaan sumber daya yang membatasi proporsional terhadap level nilai variabel. Jika harga per unit produk misalnya adalah sama berapapun jumlah yang dibeli, maka sifat proporsional dipenuhi. Atau dengan kata lain, jika pembelian dalam jumlah besar mendapatkan diskon, maka sifat proporsional tidak dipenuhi. Jika penggunaan sumber daya per unitnya tergantung dari jumlah yang diproduksi, maka sifat proporsionalitas tidak dipenuhi.
• Sifat aditivitas mengasumsikan bahwa tidak ada bentuk perkalian silang di antara berbagai aktivitas, sehingga tidak akan ditemukan bentuk perkalian silang pada model. Sifat aditivitas berlaku baik bagi fungsi tujuan maupun pembatas (kendala). Sifat aditivitas dipenuhi jika fungsi tujuan merupakan penambahan langsung kontribusi masing-masing variabel keputusan.
• Sifat divisibilitas berarti unit aktivitas dapat dibagi ke dalam sembarang level fraksional, sehingga nilai variabel keputusan non integer dimungkinkan.
• Sifat Kepastian menunjukkan bahwa semua parameter model berupa konstan. Artinya koefisien fungsi tujuan maupun fungsi pembatas merupakan suatu nilai pasti, bukan merupakan nilai dengan peluang tertentu.

Kelima asumsi (sifat) ini dalam dunia nyata tidak selalu dapat dipenuhi. Untuk meyakinkan dipenuhinya kelima asumsi ini (Siringoringo, 2005).

1.3. Model Pemrograman Linear

Model matematis perumusan masalah umum pengalokasian sumberdaya untuk berbagai kegiatan, disebut sebagai model pemrograman linear. Model pemrogram linear ini merupakan bentuk dan susunan dalam menyajikan masalah-masalah yang akan dipecahkan dengan teknik pemrogram linear.

Masalah pemrograman linear secara umum dapat ditulis dalam bentuk umum sebagai berikut.

…………………..(2. 1)

dengan kendala,

…………………………..(2.2)

dan

x_j ≥ 0,  j = 1, 2, 3, …., n …………………………………………………………..(2.3)

keterangan:

z = fungsi tujuan

x_j = jenis kegiatan (variabel keputusan)

a_ij = kebutuhan sumberdaya  i untuk menghasilkan setiap unit kegiatan j

b_i = jumlah sumberdaya i yang tersedia

c_j = kenaikan nilai Z jika ada pertambahan satu unit kegiatan j

a, b, dan c, disebut juga sebagai parameter model

m = jumlah sumberdaya yang tersedia

n = jumlah kegiatan.

Persamaan (2. 1) dan (2. 2) bisa dikatakan sebagai model standar dari masalah pemrograman linear. Sebuah formulasi matematika yang sesuai dengan model ini adalah masalah program linier batas normal (Hiller, 1990).

Umumnya terminologi untuk model program linier sekarang dapat diringkas. Fungsi objektif, c₁x₁ + c₂x₂ + … + c_nx_n, dengan kendala sebagai pembatas. Batasan m (dengan fungsi semua variabel a₁₁x₁ + a₁₂x₂ + … + a_1nx_n) kadang-kadang disebut fungsi pembatas. Sama halnya dengan kendala x_j ≥ 0 disebut pembatas non negatif.

Beberapa aturan bentuk program linear baku/standar:

1.      Semua batasan/kendala adalah persamaan (dengan sisi kanan yang non-negatif).

2.      Semua variabel keputusan adalah non-negatif.

3.      Fungsi tujuan dapat berupa maksimasi atau minimasi.

(Aminudin, 2005)

1.4. Beberapa Definisi yang Berkaitan dengan Pemrograman Linear

Definisi berikut akan dibutuhkan nantinya untuk menjelaskan metode penyelesaian permasalahan pemrograman linear.

Definisi 1 : penyelesaian fisibel

Penyelesaian fisibel adalah penyelesaian yang memenuhi persamaan (2. 2) dan (2. 3) pada bentuk standar pemrograman linear di atas. Sedangkan himpunan yang memuat semua penyelesaian fisibel disebut daerah fisibel (F) (Herjanto, E, 2008).

Definisi 2 : variabel basis

variabel basis adalah variabel-variabel yang digunakan di persamaan (2. 1), (2. 2) dan (2. 3) sebanyak m dan bernilai positif (Siswanto, 2007).

Definisi 4 : Penyelesaian optimum

Penyelesaian optimum adalah penyelesaian fisibel yang mengoptimumkan fungsi objektif (memenuhi persamaan (2. 1)), maka penyelesaian basis optimum dan optimum tetapi tidak fisibel dapat didefinisikan (Pusat Pembinaan dan Pengembangan Bahasa, 2003).

Definisi 5 : Penyelesaian basis optimum

Penyelesaian basis optimum adalah penyelesaian fisibel basis untuk membuat fungsi obyektif menjadi optimum (Anonim, 2003).

Definisi 6 : Penyelesaiaan optimum tetapi tidak fisibel

Optimum tetapi tidak fisibel adalah penyelesaian yang terdapat variabel pada penyelesaian basis yang berharga negatif (tidak memenuhi persamaan (2. 3)). yang mengoptimumkan fungsi objektif (memnuhi persamaan (2.1)) (Herjanto, E, 2008).

Definisi 7 : Nilai slack

Nilai slack adalah nilai kelebihan suatu sumberdaya yang digunakan pada kondisi optimum terhadap sumberdaya yang tersedia sebagai kendala (Siswanto, 2007).

Definisi 8 : Primal fisibel

Primal fisibel adalah adalah model standar pemrograman linear memenuhi persamaan (2. 2) dan (2. 3) di atas yang mengoptimumkan fungsi objektif (Herjanto, E, 2008).

Source : Prolin