LINEAR PROGRAMMING

TUGAS PAPER

RISET OPERASIONAL

“LINEAR PROGRAMMING”

Oleh :

FRIDA MASLIKHAH (101710101064)

Kelas A

 

JURUSAN TEKNOLOGI HASIL PERTANIAN

FAKULTAS TEKNOLOGI PERTANIAN

UNIVERSITAS JEMBER

TAHUN 2012

I.         Riset  Operasional

Riset Operasional adalah metode untuk memformulasikan dan  merumuskan permasalahan  sehari-hari  baik mengenai  bisnis,  ekonomi,  sosial maupun bidang lainnya ke dalam pemodelan matematis untuk mendapatkan solusi yang optimal.

II.      Linear programming

Linear Programming adalah suatu metode matematika yang dirancang agar dapat membantu manajer dalam merencanakan dan membuat keputusan dalam mengalokasikan sumber daya yang terbatas untuk mencapai tujuan perusahaan.

Pada dasarnya suatu perusahaan ingin mencapai tujuan yang telah ditetapkan sesuai dengan keterbatasan sumberdaya yang ada. Oleh karena itu digunakanlah linear programming sebagai teknik pengambilan keputusan dalam permasalahan yang berhubungan dengan pengalokasian sumberdaya secara optimal.

Penggunaan sumber daya manufakturing (seperti: mesin, tenaga kerja, modal, waktu, dan bahan baku digunakan dalam kombinasi tertentu yang paling optimum untuk menghasilkan produk yakni barang atau jasa) harus lebih efektif dan efisien. Disinilah linear programming dipergunakan untuk membantu manajer untuk merencanakan dan membuat keputusan mengenai pengalokasian sumber daya yang optimum. Berikut ini adalah beberapa contoh penggunaan linear programing yang telah diaplikasikan pada industri:

    a.       Menentukan diversifikasi produk yang terbaik dalam menggunakan kapasitas mesin, tenaga kerja, dan modal yang tersedia agar memaksimumkan keuntungan perusahaan (maksimisasi keuntungan).

   b.      Menentukan campuran bahan baku dalam pabrik pengolahan makanan untuk menghasilkan produk obat atau makanan yang meminimumkan biaya produksi (minimisasi biaya produksi).

     c.       Menentukan sistem distribusi yang akan meminimumkan ongkos total transportasi dari beberapa gudang ke beberapa lokasi pasar (minimisasi biaya transportasi).

Semua masalah linear programming pada dasarnya memiliki lima karakteristik utama, yakni :

1. Masalah linear programming berkaitan dengan upaya memaksimumkan keuntungan atau meminimumkan biaya. Upaya optimasi (maksimum atau minimum) disebut sebagai fungsi tujuan dari linear programming yang terdiri dari variabel-variabel keputusan.

2.  Terdapat kendala-kendala atau keterbatasan yang membatasi pencapaian tujuan yang dirumuskan dalam linear programming. Kendala-kendala dirumuskan dalam fungsi kendala yang terdiri dari variabel-variabel keputusan yang menggunakan sumber daya yang terbatas. Dengan demikian yang akan diselesaikan dalam linear programming adalah mencapai fungsi tujuan (maksimum keuntungan atau minimum biaya) dengan memperhatikan fungsi kendala (keterbatasan atau kendala)  sumber-sumber daya yang ada.

3. Sifat Linearitas. berlaku untuk semua fungsi tujuan dan fungsi kendala. Misalnya : apabila satu unit produk A dapat menghasilkan keuntungan Rp 3000, maka apabila kita memproduksi dua unit produk A akan memberikan keuntungan Rp 6000 (2 x Rp 3000) dst. Demikian pula untuk penggunaan sumber daya. Misalnya untuk sumber daya tenaga kerja, untuk memproduksi satu unit produk A membutuhkan 2 jam kerja, maka untuk menghasilkan dua unit produk A akan membutuhkan 4 jam kerja (2 unit produk x 2 jam kerja/unit produk) dst.

4. Sifat Homogenitas. berkaitan dengan kehomogenan sumber-sumber daya yang digunakan dalam proses produksi, misalnya semua produk A dihasilkan oleh mesin-mesin yang identik, tenaga kerja yang berketerampilan sama dll.

5. Sifat Divisibility. diperlukan karena linear programming mengasumsikan bahwa nilai dari variabel-variabel keputusan maupun penggunaan sumber-sumber daya dapat dibagi ke dalam pecahan-pecahan. Jika pembagian ini tidak mungkin dilakukan terhadap variabel keputusan, misalnya dalam industri mobil, furniture, dan lain-lain, karena nilai kuantitas produksi diukur dalam bilangan bulat, maka modifikasi terhadap  linear programming harus dilakukan. Bentuk modifikasi dari linear programming ini disebut sebagai integer programming.

Dalam menyelesaikan permasalahan dengan menggunakan Linear Programming, terdapat dua pendekatan yang dapat digunakan, yakni :

1.    Metode grafik bisa digunakan untuk menyelesaikan permasalahan dimana terdapat dua variabel keputusan.

A.      Masalah Maksimisasi (Maksimisasi dapat berupa memaksimalkan keuntungan atau hasil). Contoh:

PT. LUNATEKSTIL memiliki sebuah pabrik yang akan memproduksi 2 jenis  produk, yaitu kain sutera dan kain wol. Untuk  memproduksi  kedua produk  diperlukan bahan baku benang sutera, bahan baku benang wol dan tenaga  kerja. Maksimum penyediaan benang sutera adalah 60 kg per  hari, benang wol 30 kg per hari dan tenaga kerja 40 jam per hari. Kebutuhan setiap unit produk akan bahan baku dan  jam  tenaga kerja dapat dilihat dalam  tabel berikut:

Kedua jenis produk memberikan keuntungan  sebesar Rp  40  juta  untuk  kain sutera dan Rp 30 juta untuk kain wol. Masalahnya adalah bagaimana menentukan jumlah unit setiap jenis produk yang akan diproduksi setiap hari agar keuntungan yang diperoleh bisa maksimal?

Langkah-langkah: 

1)      Tentukan variabel

X₁=kain sutera

X₂=kain wol

2)      Fungsi tujuan

Zmax= 40X₁ + 30X₂

3)  Fungsi kendala / batasan

1.  2X₁ + 3X₂ ≤ 60 (benang sutera)

2.             2X₂  ≤ 30 (benang wol)

3.  2X₁ +  X₂   ≤  40 (tenaga kerja)

4)  Membuat grafik

1.  2X₁ + 3 X ₂=60

X₁=0,  X₂ =60/3 = 20

X₂=0,  X₁= 60/2 = 30

2. 2X₂ ≤  30

X₂= 15

3.  2X₁ + X₂ ≤ 40

X₁=0,  X₂ = 40

X₂=0,  X₁= 40/2 = 20

Cara mendapatkan solusi optimal:

1. Dengan mencari nilai Z setiap titik ekstrim.

Titik A 

X₁=0, X₂=0

masukkan nilai X₁ dan X₂ ke Z

Z = 40 . 0 + 30 . 0 = 0

Titik B

X₁=20, X₂=0

masukkan nilai X₁ dan X₂ ke Z

Z = 40 . 20 + 30 . 0 = 800

Titik C

Mencari titik potong (1) dan (3)

2X₁ + 3X₂ = 60

2X₁ + X₂   = 40   -

            2X₂=20      X₂=10

Masukkan X₂ ke kendala (1)

2X₁ + 3X₂ = 60

2X₁ + 3 . 10 = 60

2X₁ + 30 = 60

2X₁ = 30  X₁ = 15

masukkan nilai X₁ dan X₂ ke Z

40X₁ + 30X₂ = 40 . 15 + 30 . 10 = 600 + 300 = 900   (optimal)

Titik D

2X₂ = 30

  X₂ = 15

masukkan X₂ ke kendala (1)

2X₁ + 3 . 15 = 60

2X₁ + 45 = 60

2X₁ = 15  X₁ = 7,5

masukkan nilai X₁ dan X₂ ke Z

Z = 40 . 7,5 + 30 . 15 = 300 + 450 = 750

Titik E

X₂ = 15

X₁ = 0

masukkan nilai X₁ dan X₂ ke Z

Z = 40 . 0 + 30 .15 = 450

Kesimpulan : 

Untuk memperoleh keuntungan optimal, maka X₁ = 15 dan X₂ = 10 dengan keuntungan sebesar Rp 900 juta.

2. Dengan cara menggeser garis fungsi tujuan.

Solusi  optimal  akan  tercapai  pada  saat  garis  fungsi  tujuan menyinggung  daerah feasible (daerah yang diliputi oleh semua kendala) yang terjauh dari titik origin. Pada gambar, solusi optimal tercapai pada titik C yaitu persilangan garis kendala (1) dan (3).

B . Masalah Minimisasi  (Meminimumkan biaya produksi). Solusi optimal tercapai pada saat garis fungsi tujuan menyinggung daerah fasible yang  terdekat dengan titik origin. Contoh :

Perusahaan makanan ROYAL merencanakan untuk membuat dua jenis makanan yaitu Royal Bee dan Royal Jelly. Kedua jenis makanan tersebut mengandung vitamin dan protein. Royal Bee paling sedikit diproduksi 2 unit dan Royal Jelly paling sedikit diproduksi 1 unit. Tabel berikut menunjukkan jumlah vitamin dan protein dalam setiap jenis makanan:

Bagaimana  menentukan  kombinasi  kedua  jenis  makanan  agar  meminimumkan

biaya produksi.

Langkah – langkah:

1.  Tentukan variabel

X₁ = Royal Bee

X₂ = Royal Jelly

2.  Fungsi tujuan

Zmin = 100X₁ + 80X₂

3.  Fungsi kendala

1)  2X₁ + X₂ ≥  8    (vitamin)

2)  2X₁ + 3X₂ ≥ 12  (protein)

3)  X₁ ≥ 2

4)  X₂ ≥1

4.  Membuat grafik

1)  2X₁ + X₂ = 8

X₁ = 0,  X₂ = 8

X₂ = 0,  X₁ = 4

2)  2X₁ + 3X₂ = 12

X₁ = 0,  X₂ = 4

X₂ = 0,  X₁ = 6

3)  X₁ = 2

4)  X₂ = 1

Solusi  optimal  tercapai  pada  titik  B  (terdekat  dengan  titik  origin),  yaitu

persilangan garis kendala (1) dan (2).

2X₁ +   X₂ =   8

2X₁ + 3X₂ = 12   -

          -2X₂ = -4     <-->  X₂ = 2

masukkan X2 ke kendala  (1)

2X₁ + X₂ = 8

2X₁ + X₂ = 8   -

2 X₁ = 6     <-->  X₁ = 3

masukkan nilai X₁ dan X₂ ke Z

Z min = 100X₁ + 80X₂ = 100 . 3 + 80 . 2 = 300 + 160 = 460  

Kesimpulan :

Untuk meminimumkan biaya produksi, maka X₁ = 3 dan X₂ = 2 dengan biaya produksi 460 ribu rupiah.

2.    Metode simpleks bisa digunakan untuk menyelesaikan permasalahan dimana terdapat dua variabel keputusan atau lebih.

Beberapa ketentuan yang perlu diperhatikan, antara lain:

1.  Nilai kanan (NK / RHS) fungsi tujuan harus nol (0).

2.  Nilai kanan (RHS) fungsi kendala harus positif. Apabila negatif, nilai tersebut harus dikalikan –1.

3.  Fungsi kendala dengan tanda “≤” harus diubah ke bentuk “=” dengan menambahkan variabel slack/surplus. Variabel slack/surplus disebut  juga variabel dasar.

4.  Fungsi kendala dengan tanda “≥” diubah ke bentuk “≤” dengan cara mengalikan dengan –1, lalu diubah ke bentuk persamaan dengan ditambahkan variabel slack. Kemudian karena RHS-nya negatif, dikalikan lagi dengan –1 dan ditambah artificial variabel (M).

5.  Fungsi kendala dengan tanda “=” harus ditambah artificial variabel (M).

Contoh :

Suatu perusahaan menghasilkan dua produk, meja dan kursi yang diproses melalui dua bagian fungsi: perakitan dan pemolesan. Pada bagian perakitan tersedia 60 jam kerja, sedangkan pada bagian pemolesan hanya 48 jam kerja. Untuk menghasilkan 1 meja diperlukan 4 jam kerja perakitan dan 2 jam kerja pemolesan, sedangkan untuk menghasilkan 1 kursi diperlukan 2 jam kerja perakitan dan 4 jam kerja pemolesan, Laba untuk setiap meja dan kursi yang dihasilkan masing-masing Rp 80.000 dan Rp 60.000 . Berapa jumlah meja dan kursi yang optimal dihasilkan?

Langkah 1 :

4M + 2K + S1  = 60     atau S1 = 60 – 4M – 2K

2M + 4K + S2  = 48     atau S2 = 48 – 2M – 4K

S1 adalah variabel slack (waktu tak terpakai) dalam perakitan

S2 adalah variabel slack (waktu tak terpakai) dalam pemolesan

·         Semua variabel yang tidak mempengaruhi kesamaan ditulis dengan koefisien nol.

Maks Laba = 8M + 6K + 0S1 + 0S2

Dengan kendala:

4M + 2K + S1 + 0S2 = 60

2M + 4K + 0S1 + S2 = 48

M ≥ 0;  K ≥ 0

·         Variabel dibagi menjadi non-basic variables dan basic variables.

 Non-basic variables ⇒ variabel yang tidak keluar sebagai solusi pada setiap iterasi, nilainya sama dengan nol.

 basic variables ⇒ variabel yang keluar sebagai solusi pada setiap iterasi.

Langkah 2: Membuat tabel simpleks awal

Langkah 3: Penentuan baris dan kolom kunci sebagai dasar Iterasi

·      Kolom kunci ditentukan oleh nilai baris Z negatif terbesar, yaitu pada kolom M

·      Baris kunci ditentukan dari nilai rasio CV/Kolom kunci terkecil, yaitu baris S1.

Langkah 4: Iterasi

Variabel yang masuk sebagai basic variable (BV) adalah M dan variabel yang keluar dari BV adalah S. M masuk sebagai BV menggantikan S1 (baris kedua).

Untuk melakukan iterasi, digunakan metode perhitungan Gauss-Jordan sebagai berikut:

·         Persamaan Pivot:

Persamaan pivot baru = Persamaan pivot lama : elemen pivot

·         Persamaan lainnya, termasuk Z:

Persamaan baru = (Persamaan lama) – (Koef kolom masuk) x (persamaan pivot baru)

Hasil iterasi 1:

Hasil iterasi 2:

Karena nilai-nilai pada baris Z sudah non-negatif, berarti iterasi selesai dan solusi yang diperoleh adalah:

M = 12,  K = 6  dan  Z (laba) = 132.

Dari tabel akhir iterasi diatas juga diperoleh informasi mengenai nilai Reduced Costs dan Dual (shadow) prices. Selain itu, dgn sedikit perhitungan juga dapat dilakukan analisis sensitivitas.