Tentang Linear Programming

LINEAR PROGRAMMING

Formulasi Model LP

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

Pembentukan model bukanlah suatu ilmu pengetahuan tetapi lebih bersifat seni dan akan menjadi dimengerti terutama karena praktek.

Contoh 1 : Masalah Kombinasi Produk

Sebuah perusahaan ingin menentukan berapa banyak masing-masing dari tiga produk yang berbeda yang akan dihasilkan dengan tersedianya sumber daya yang terbatas agar diperoleh keuntungan maksimum. Kebutuhan buruh dan bahan mentah dan sumbangan keuntungan masing-masing produk adalah sebagai berikut :

 

Tersedia 240 jam kerja dan bahan mentah sebanyak 400 Kg. Masalahnya adalah menentukan jumlah masing-masing produk agar keuntungan maksimum. Rumusan model LP-nya adalah :

A.    Variabel Keputusan

Tiga variabel dalam masalah ini adalah produk A, B dan C yang harus dihasilkan. Jumlah ini dapat dilambangkan sebagai :

X₁ = jumlah produk A

X₂ = jumlah produk B

X₃ = jumlah produk C

B.     Fungsi tujuan

Tujuan masalah kombinasi produk adalah memaksimumkan keuntungan total. Jelas bahwa keuntungan adalah jumlah keuntungan yang diperoleh dari masing-masing produk. Keuntungan dari produk A adalah perkalian antara jumlah produk A dengan keuntungan per unit (Rp 3,-). Keuntungan produk B dan C ditentukan dengan cara serupa. Sehingga keuntungan total Z, dapat ditulis :

Z = 3 X₁ + 5 X₂ + 2 X₃

C.    Sistem kendala

Dalam masalah ini kendalanya adalah jumlah buruh dan bahan mentah yang terbatas. Masing-masing produk membutuhkan baik buruh maupun bahan mentah. Produk A, buruh yang dibutuhkan untuk menghasilkan tiap unit adalah 5 jam, sehingga buruh yang dibutuhkan untuk produk A adalah 5 X₁ jam. Dengan cara yang serupa produk B membutuhkan 2 X₂ jam buruh, dan produk C butuh 4 X₃ jam, sementara jumlah jam buruh yang tersedia adalah 240 jam. Sehingga dapat ditulis :

5 X₁ + 2 X₂ + 4 X₃ ≤ 240

Kendala bahan mentah dirumuskan dengan cara yang sama, yaitu untuk produk A butuh bahan mentah sebanyak 4 kg per unit, produk B membutuhkan 6 kg per unit dan produk C butuh 3 kg per unit. Karena yang tersedia adalah sebanyak 400 kg bahan mentah, maka dapat ditulis :

4 X₁ + 6 X₂ + 3 X₃ ≤ 400

Kita juga membatsi masing-masing variabel hanya pada nilai positif, karena tidak mungkin untuk menghasilkan jumlah produk negatif. Kendala-kendala ini dikenal dengan non negativity constraints dan secara matematis dapat ditulis :

X₁ ≥ 0, X₂ ≥ 0, X₃ ≥ 0 atau X₁, X₂, X₃ ≥ 0

Pertanyaan yang timbul adalah mengapa kendala dituliskan dengan tanda pertidak-samaan ( ≤ ), bukannya persamaan ( = ). Persamaan secara tidak langsung mengatakan bahwa seluruh kapasitas sumber daya digunakan, sementara dalam pertidaksamaan memperbolehkan penggunaan kapasitas secara penuh maupun penggunaan sebagian kapasitas. Dalam beberapa kasus suatu solusi dengan mengizinkan adanya kapasitas sumberdaya yang tak terpakai akan memberikan solusi yang lebih baik, yang berarti keuntungan lebih besar, dari pada penggunaan seluruh sumber daya. Jadi, pertidaksamaan menunjukkan keluwesan.

Dari masalah diatas, formulasi LP secara lengkap dapat ditulis :

Maksimumkan Z = 3 X₁ + 5 X₂ + 2 X₃

Dengan syarat         5 X₁ + 2 X₂ + 4 X₃ ≤ 240

 4 X₁ + 6 X₂ + 3 X₃ ≤ 400

    X₁, X₂, X₃ ≥ 0

Contoh 2 : Masalah Diet

Untuk menjaga kesehatan, seseorang harus memenuhi kebutuhan minimum perhari akan beberapa zat makanan. Misalkan hanya ada tiga jenis zat makanan yang dibutuhkan yaitu kalsium, protein, dan vitamin A. Sementara makanan yang tersedia ada tiga jenis juga yaitu, makanan A, B dan C yang harganya, zat-zat yang tekandung didalamnya, dan kebutuhan minimum perhari akan zat-zat makanan tersebut dapat dilihat pada tabel berikut :

 

Masalahnya adalah bagaimana kombinasi ketiga jenis makanan itu akan memenuhi kebutuhan minimum perhari dan memberikan biaya terendah.

A.    Variabel keputusan

Masalah ini terdiri dari tiga variabel yang menunjukkan jumlah masing-masing jenis makanan yang ditempatkan dalam menu, yaitu :

X₁ = jumlah makanan A

X₂ = jumlah makanan B

X₃ = jumlah makanan C 

B.     Fungsi tujuan

Tujuan masalah ini adalah meminimumkan biaya total menu perhari. Biaya total dalam konteks ini adalah jumlah biaya dari masing-masing jenis makanan yang disajikan dalam menu. Sehingga biaya total, Z, ditulis :

Z = 0,5 X₁ + 0,8 X₂ + 0,6 X₃

C.     Sistem kendala

Dalam masalah ini, kendalanya adalah kebutuhan minimum akan zat-zat makanan perhari yang telah ditetapkan. Kendala untuk kalsium ditulis :

5 X₁ + X₂ ≥ 8 

5 X₁ adalah sumbangan kalsium dari makanan A

X₂ adalah sumbangan kalsium dari makanan B

Pada contoh ini digunakan pertidaksamaan “≥” yang menunjukkan jumlah minimum kalsium yang dibutuhkan. Dengan kata lain, sekurang-kurangnya 8 unit kalsium harus dipenuhi.

Kendala untuk protein dan vitamin A dibuat dengan cara yang sama, yaitu :

2 X₁ + 2 X₂ + X₃ ≥ 10 Protein

X₁ + 5 X₂ + 4 X₃ ≥ 22 Vitamin A

Masalah LP secara lengkap dapat ditulis :

Minimumkan Z = 0,5 X₁ + 0,8 X₂ + 0,6 X₃

Dengan syarat         5 X₁ + X₂ ≥ 8

                               2 X₁ + 2 X₂ + X₃ ≥ 10 
                                  X₁ + 5 X₂ + 4 X₃ ≥ 22
                                  X₁ , X₂ , X₃ ≥ 0

BENTUK UMUM MODEL LP

Dari contoh yang sudah ditulis diatas secara mendalam terlihat adanya suatu pola yang khas untuk merumuskan secara umum suatu masalah LP. Pada setiap masalah, ditentukan variabel keputusan, fungsi tujuan, dan sistem kendala, yang bersama-sama membentuk suatu model matematik dari dunia nyata. Bentuk umum model LP itu adalah : n

ΣijMaksimumkan (minimumkan) Z = c _j x_j

Dengan syarat : a_ij x_j (≤ , = , ≥) b_i , untuk semua i (i = 1, 2, …m) semua x_j ≥ 0

Keterangan :

x_j : banyaknya kegiatan j, dimana j = 1, 2, …n, yang berarti terdapat n variabel keputusan

Z : nilai fungsi tujuan

c_j : sumbangan per unit kegiatan j, untuk masalah maksimasi c_j menunjukkan atau penerimaan per unit, sementara dalam kasus minimasi ia menunjukkan biaya per unit.

b_i : jumlah sumberdaya ke i (i = 1, 2, …m), berarti terdapat m jenis sumberdaya.

x_ij : banyaknya sumberdaya i yang dikonsumsi sumberdaya j.

Yang perlu diingat adalah tanda pertidaksamaan tidak harus sama untuk setiap kendala !

ASUMSI MODEL LP

Model LP mengandung asumsi-asumsi implisit tertentu yang harus dipenuhi agar definisinya sebagai suatu masalah LP menjadi absah. Asumsi itu menuntut bahwa hubungan fungsional dalam masalah itu adalah linier dan additif, dapat dibagi dan deterministik.

Linearity dan Additivity

Bahwa fungsi tujuan dan semua kendala harus linier. Dengan kata lain, jika suatu kendala melibatkan dua variabel keputusan, dalam diagram dimensi dua ia akan berupa garis lurus. Begitu juga, suatu kendala yang melibatkan tiga variabel akan menghasilkan suatu bidang datar dan kendala yang melibatkan n variabel akan menghasilkan hyperplane (bentuk geometris yang rata) dalam ruang berdimensi n.

Kata linier secara tidak langsung mengatakan bahwa hubungannya proporsional yang berarti bahwa tingkat perubahan atau kemiringan hubungan fungsional itu adalah konstan dan karena itu perubahan nilai variabel akan mengakibatkan perubahan relatif nilai fungsi tujuan dalam jumlah yang sama.

LP juga mensyaratkan bahwa umlah variabel kriteria dan jumlah penggunaan sumber daya harus bersifat additif. Contohnya, keuntungan total Z yang merupakan variabel kriteria, sama dengan jumlah keuntungan yang diperoleh dari masing-masing kegiatan, c_j x_j. Juga, seluruh sumber daya yang digunakan untuk seluruh kegiatan, harus sama dengan jumlah sumber daya yang digunakan untuk masing-masing kegiatan.

Additif dapat diartikan sebagai tak adanya penyesuaian pada perhitungan variabel kriteria karena terjadinya interaksi. Contohnya, dalam masalah kombinasi produk disebutkan bahwa keuntungan per unit produk A Rp 3,- ,produk B Rp 5,- , dan produk C Rp 2,-. Jika masing-masing produk dijual secara terpisah. Tetapi bisa jadi, kalau dijual secara serentak pada daerah yang sama dapat menyebabkan penurunan keuntungan, sehingga perlu memasukkan penyesuaian interaksi ke dalam variabel kriteria, misalnya saja menjadi :

Z = 3 X₁ + 5 X₂ + 2 X₃ - X₁ X₂ X₃

Model terakhir ini adalah tidak linier, dan metode LP tak dapat menangani masalah demikian !

1.      Divisibility

Asumsi ini berarti bahwa nilai solusi yang diperoleh X_j , tidak harus bilangan bulat. Ini berarti nilai X_j dapat berupa nilai pecah. Karena itu variabel keputusan merupakan variabel kontinyu, sebagai lawan dari variabel diskrit atau bilangan bulat.

2.      Deterministic

Semua parameter model (c_j, a_ij dan b_i) diasumsikan diketahui konstan. LP secara tak langsung mengasumsikan suatu masalah keputusan dalam suatu kerangka statis dimana semua parameter diketahui dengan kepastian. Dalam kenyataannya, parameter model jarang bersifat deterministik, karena mereka mencerminkan kondisi masa depan maupun sekarang, dan keadaan masa depan jarang diketahui secara pasti.

Ada beberapa cara untuk mengatasi ketidakpastian parameter dalam model LP. Analisa sensitivitas adalah suatu teknik yang dikembangkan untuk menguji nilai solusi, bagaimana kepekaannya terhadap perubahan-perubahan parameter.

PENYELESAIAN GRAFIK MODEL LP

Masalah LP dapat diilustrasikan dan dipecahkan secara grafik jika ia hanya memiliki dua variabel keputusan. Meski masalah-masalah dengan dua variabel jarang terjadi dalam dunia nyata, penafsiran geametris dari metode grafik ini sangat bermanfaat. Dari sini, kita dapat menarik kesimpulan yang akan menjadi dasar untuk pembentukan metode pemecahan (solusi) yang umum melalui algoritma simpleks.

Contoh 3 : Kombinasi produksi

Disamping itu, menurut bagian penjualan diramalkan, bahwa permintaan produk 1 tidak akan melebihi 4 unit.

Masalah contoh 3 dapat dirumuskan :

Maksimumkan Z =       4 X₁ + 5 X₂

Dengan syarat                 X₁ + 2 X₂ ≤ 10

6 X₁ + 6 X₂ ≤ 36

   X₁ ≤ 4

   X₁ , X₂ ≥ 0 

Suatu cara sederhana untuk menggambarkan masing-masing persamaan garis adalah dengan menetapkan salah satu variabel dalam suatu persamaan sama dengan nol dan kemudian mencari nilai variabel yang lain. Misalnya pada kendala pertama jika X₁ = 0, maka 5 X₂ = 10 atau X₂ = 5. Dengan cara yang sama X₂ = 0, maka X₁ = 10. Kedua titik ini {(0,5) dan (10,0)} kemudian dihubungkan dengan suatu garis lurus.

Suatu daerah yang secara bersamaan memenuhi ketiga kendala ditunjukkan oleh area yang diarsir yaitu area ABCDE pada gambar grafik. Wilayah ini dinamakan solusi layak atau ruang solusi. Sementara itu, pasangan nilai-nilai (X₁ , X₂) di luar daerah ini bukan merupakan solusi layak, karena menyimpang dari satu atau lebih kendala.

Sementara hasil optimal Z dapat ditunjukkan pada titik terluar pada daerah solusi layak. Ada dua hal yang perlu diperhatikan, kaitannya dengan fungsi tujuan yaitu :

1. Semua garis Z adalah sejajar, atau memiliki kemiringan yang sama sebesar - 4/5 yang diperoleh melalui perhitungan berikut : X₂ = Z/5 – (4/5) X₁

2. Garis Z adalah garis-garis sejajar dalam jumlah tak terbatas.

SUMBER :

peni.staff.gunadarma.ac.id/Downloads/files/7498/Linier+Prog.pdf Linear programing : formulasi masalah dan pemodelan