A.     Definisi Pemprograman Linier

          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).

Pemprograman linier adalah metode matematik dalam mengalokasikan sumber daya yang terbatas untuk mencapai suatu tujuan seperti memaksimalkan keuntungan atau meminimumkan biaya. Program linier berkaitan dengan penjelasan suatu kasus dalam dunia nyata sebagai suatu model matematik yang terdiri dari sebuah fungsi tujuan linier dengan beberapa kendala linier (Taha, 1993).

Program linier banyak digunakan untuk menyelesaikan masalah optimal didalam industri, perbankan, pendidikan, dan masalah-masalah lain yang dapat dinyatakan dalam bentuk linier.

B.     Sifat Dasar / Karakteristik Pemprograman Linier

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

1. Sifat linieritas suatu kasus dapat ditentukan dengan menggunakan beberapa cara. Secara statistik, cara ini dapat diperiksa kelinearan menggunakan grafik (diagram pencar).
2. Sifat proposional dipenuhi jika kontribusi setiap variabel pada fungsi tujuan atau penggunaan sumber daya yang membatasi proposional 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.
3. Sifat additivitas mengasumsikan bahwa tidak ada bentuk perkalian silang diantara berbagai aktivitas, sehingga tidak dapat 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.
4. Sifat divisiabel berarti unit aktivitas dapat dibagi dalam sembarang level fraksional, sehingga nilai variabel keputusan non integer dimungkinkan.
5. Sifat kepastian menunjukkan bahwa semua parameter model berupa konstanta. Artinya koefisien fungsi tujuan maupun fungsi pembatas merupakan suatu nilai pasti, bukan merupakan nilai dengan peluang tertentu.

C.     Model Pemprograman Linier

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 :

 

 

 

 

 

 

 

 

 

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 (Aminudin, 2005):

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.

D.     Formulasi Permasalahan

• Masalah keputusan yang sering dihadapi analisis adalah alokasi optimum sumber daya.
• Sumber daya dapat berupa uang, tenaga kerja, bahan mentah, kapasitas mesin, waktu, ruangan atau teknologi.
• Tugas analisis adalah mencapai hasil terbaik dengan keterbatasan sumber daya itu.
• Setelah masalah diidentifikasikan, tujuan ditetapkam, langkah selanjutnya adalah formulasi model matematika.
• Formulasi model matematika ada 3 tahap :

1. Tentukan variabel yang tidak diketahui dan dinyatakan dalam simbol.
2. Membentuk fungsi tujuan yang ditunjukkan sebagai suatu hubungan linier dari variabel keputusan.
3. Menentukan semua kendala masalah tersebut dan mengekspresikannya dalam persamaan atau pertidaksamaan.

Contoh kasus yang diselesaikan :

1.  Seorang pengrajin menghasilkan satu tipe meja dan satu tipe kursi. Proses yang dikerjakan hanya merakit meja dan kursi. Dibutuhkan waktu 2 jam untuk merakit 1 unit meja dan 30 menit untuk merakit 1 unit kursi. Perakitan dilakukan oleh 4 orang karyawan dengan waktu kerja 8 jam perhari. Pelanggan pada umumnya membeli paling banyak 4 kursi untuk 1 meja. Oleh karena itu pengrajin harus memproduksi kursi paling banyak empat kali jumlah meja. Harga jual per unit meja adalah Rp 1,2 juta dan per unit kursi adalah Rp 500 ribu. Formulasikan kasus tersebut ke dalam model matematiknya !

Solusi :

Hal pertama yang harus dilakukan adalah mengidentifikasi tujuan, alternatif keputusan dan sumber daya yang membatasi. Berdasarkan informasi yang diberikan pada soal, tujuan yang ingin dicapai adalah memaksimumkan pendapatan. Alternatif keputusan adalah jumlah meja dan kursi yang akan diproduksi. Sumber daya yang membatasi  adalah waktu kerja karyawan dan perbandingan jumlah kursi dan meja yang harus diproduksi (pangsa pasar ).

Langkah berikutnya adalah memeriksa sifat proporsionalitas, additivitas, divisibilitas dan kepastian. Informasi di atas tidak menunjukkan adanya pemberian diskon, sehingga harga jual per meja maupun kursi akan sama meskipun jumlah yang dibeli semakin banyak. Hal ini mengisyaratkan bahwa total  pendapatan yang diperoleh pengrajin proposional terhadap jumlah produk yang terjual. Penggunaan sumber daya yang membatasi , dalam hal ini waktu kerja karyawan dan pangsa pasar juga proporsional terhadap jumlah meja dan kursi yang diproduksi. Dengan  demikian dapat dinyatakan sifat proporsionalitas dipenuhi. Total pendapatan pengrajin merupakan jumlah pendapatan dari keseluruhan meja dan kursi yang terjual. Penggunaan sumber daya ( waktu kerja karyawan dan pangsa pasar) merupakan penjumlahan waktu yang digunakan untuk memproduksi meja dan kursi. Maka dapat dinyatakan juga sifat additivitas dipenuhi. Sifat divisibilitas dan kepastian juga dipenuhi.

Ada dua variabel keputusan dan dua sumber daya yang membatasi. Fungsi tujuan merupakan maksimisasi, karena semakin besar pendapatan akan semakin disukai oleh pengrajin. Fungsi kendala pertama (batasan waktu) menggunakan pertidaksamaan ≤, karena waktu yang tersedia dapat digunakan sepenuhnya atau tidak, tapi tidak mungkin melebihi waktu yang ada. Fungsi kendala yang kedua bisa menggunakan ≤ atau ≥ tergantung dari pendefinisianvariabelnya.

Kita definisikan :

x_₁ = jumlah meja yang akan diproduksi

x_₂ = jumlah kursi yang akan diproduksi

Model umum Pemrograman Linier kasus di atas adalah :

Fungsi tujuan :

Maksimumkan z = 1.2 x_₁ + 0.5 x_₂

Kendala : 2x_₁ + 0.5 x_₂≤ 32

x_₁/x_₂ ≥ ¼ atau 4x_₁≥ x_₂ atau 4x_₁– x_₂ ≥ 0

x_₁ , x_₂ ≥ 0

2.  Seorang peternak memiliki 200 kambing yang mengkonsumsi 90 kg pakan khusus setiap harinya. Pakan tersebut disiapkan menggunakan campuran jagung dan bungkil kedelai dengan komposisi sebagai berikut :

Bahan	Kg per kg bahan
	Kalsium	Protein	Serat	Biaya (Rp/kg)
Jagung	0.001	0.09	0.02	2000
Bungkil kedelai	0.002	0.60	0.06	5500

Kebutuhan pakan kambing setiap harinya adalah paling banyak 1% kalsium, paling sedikit 30% protein dan paling banyak 5% serat.

Formulasikan permasalahan di atas kedalam model matematiknya !

Solusi :

Hal pertama yang harus dilakukan adalah mengidentifikasi tujuan , alternative keputusan dan sumber daya yang membatasi. Berdasarkan informasi yang diberikan pada soal, tujuan yang ingin dicapai adalah meminimumkan biaya pembelian bahan pakan. Alternative keputusan adalah jumlah jagung dan bungkil kedelai yang akan digunakan. Sumber daya yang membatasi adalah kandungan kalsium, protein dan serat pada  jagung dan bungkil kedelai, serta kebutuhan jumlah pakan per hari.

Langkah berikutnya adalah memeriksa sifat proporsionalitas, additivitas, divisibilitas dan kepastian. Informasi di atas tidak menunjukkan adanya pemberian diskon, sehingga harga pembelian jagung dan bungkil kedelai per kg tidak berbeda meskipun pembelian dalam jumlah besar. Hal ini mengisyaratkan bahwa total biaya yang harus dikeluarkan peternak proporsional  terhadap jumlah jagung dan  bungkil kedelai yang dibeli. Penggunaan sumber daya yang membatasi, dalam hal ini komposisi jagung dan bungkil kedelai akan serat, protein dan kalsium proporsional terhadap jumlah jagung dan bungkil. Dengan  demikian dapat dinyatakan  sifat proporsionalitas  dipenuhi. Total pengeluaran pembelian bahan pakan  merupakan penjumlahan  pengeluaran untuk jagung dan bungkil kedelai. Jumlah  masing-masing serat, protein dan kalsium yang ada di pakan  khusus merupakan penjumlah serat, protein dan kalsium yang ada pada jagung dan bungkil kedelai. Jumlah pakan khusus yang dihasilkan merupakan penjumlahan jagung dan bungkil kedelai yang digunakan.  Dengan demikian sifat additivitas dipenuhi. Sifat divisibilitas dan kepastian juga dipenuhi.

Ada dua variabel keputusan dan empat sumber daya yang membatasi. Fungsi tujuan merupakan minimisasi, karena semakin kecil biaya akan semakin disukai oleh peternak. Fungsi kendala pertama (batasan jumlah pakan yang dibutuhkan per hari) menggunakan persamaan (=), fungsi kendala kedua (kebutuhan kalsium) dan kendala keempat (kebutuhan serat) menggunakan pertidaksamaan ≤, dan fungsi kendala ketiga (kebutuhan akan protein) menggunakan pertidaksamaan ≥.

Kita definisikan :

x_₁ = jumlah jagung yang akan digunakan

x_₂ = jumlah bungkil kedelai yang akan digunakan

Model umum Pemrograman linier kasus di atas oleh karenanya adalah :

Fungsi tujuan : minimumkan z = 2000 x_₁ + 5500 x_₂

Kendala :

x_₁ + x_₂ = 90

0.001 x_₁ + 0.002 x_₂ ≤ 0.9

0.09 x_₁ + 0.6 x_₂ ≥ 27

0.02 x_₁ + 0.06 x_₂ ≤ 4.5

x_₁, x_₂ ≥ 0

 

E.    Metode Grafik

        Metode grafik adalah satu cara yang dapat digunakan untuk memecahkan masalah optimalisasi dalam programasi linier. Keterbatasan metode ini adalah variabel yang bisa digunakan terbatas (hanya dua), penggunaan 3 variabel akan sangat sulit dilakukan.

Dua macam fungsi Program Linear:

• Fungsi tujuan : mengarahkan analisa untuk mendeteksi tujuan perumusan masalah
• Fungsi kendala : untuk mengetahui sumber daya yang tersedia dan permintaan atas sumber daya tersebut.

Langkah – langkah penyelesaian dengan metode grafik:

1. Buatlah model matematika / kendala
2. Tentukan fungsi sasaran (Z).
3. Menyelesaikan fungsi pertidaksamaan :

• Jadikan setiap kendala menjadi bentuk persamaan,
• Buat grafik untuk setiap kendala dan kemudian tentukan daerah penyelesaian atau HP,
• Setelah grafik dibuat, kemudian tentukan himpunan penyelesaian (HP). Setelah itu, kita menentukan titik – titik terluar yang terdapat didalam grafik tersebut.
• Setelah titik – titik terluar ditentukan, Uji titik – titik terluarnya untuk menentukan nilai maksimumnya.