Programa Linier

PROGRAMA LINIER

Konsep Dasar

Konsep dasar Programa Linier, dapat ditinjau dari dua sudut pandang, yaitu secara sistematis dan secara praktis. Secara Matematis, yaitu mencari kondisi optimal dari sebuah fungsi (tujuan) linier berdasarkan satu atau beberapa fungsi pembatas linier.  Sedangkan, secara Praktis, yaitu alokasi sumber daya terbatas untuk mencapai sebuah tujuan optimal. Yang dimaksud optimal di dalam hal ini adalah keputusan terbaik, yang dapat berupa minimum ongkos/biaya atau maksimum laba/pendapatan, yang sesuai dengan keterbatasan yang ada. 

Formulasi

Misal, akan dibuat n jenis produk dengan menggunakan m buah sumber, dimana satu unit produk j (j = 1,2,…., n) membutuhkan sumber i (i =1,2,.., m) sebanyak a_ij, dan masing-masing sumber yang tersedia maksimum sebanyak b_i (i = 1,2,...,m). Laba (cost) produk ke j adalah C_j (-C_j ).

Jika X_j adalah jumlah produk j yang harus dibuat, berapa X_j agar diperoleh total laba maksimum atau total biaya minimum, tapi sumber yang tersedia dapat mencukupi?

Jika persoalan tersebut dinyatakan dalam model matematis (disebut bentuk umum programa linier), akan berbentuk:

Fungsi tujuan       : Max./Min. Z = ∑ C_jX_j untuk C_j > 0 atau C_j < 0 dengan

Fungsi pembatas                 :               ∑ C_jX_j  ≤ b_i

atau    ³ b_i ; untuk i = 1,2,…, m

atau    = b_i

X_j  ³ 0 untuk j = 1,2,…, n

Asumsi

Berdasarkan formulasi tersebut diatas, maka asumsi-asumsi di dalam programa linier adalah : linier, aditif, proporsional, ruas kanan fungsi pembatas dan variabel keputusannya (X_j) tidak negatif.

Solusi

Permasalahan programa linier dapat diselesaikan dengan dua cara, yaitu metoda grafis dan metoda simplex. Metoda grafis hanya dapat digunakan untuk persoalan dengan dua variabel, sedangkan metoda simplex dapat digunakan untuk persoalan dengan dua variabel atau lebih.

Metoda Grafis

Menyelesaikan program linier dengan metoda grafis, dilakukan dengan langkah

1.       Buat sistem koordinat salib sumbu (Kuadran I saja )

2.       Gambarkan fungsi pembatas untuk memperoleh daerah fisibel dan titik-titik fisibelnya

3.       Subtitusikan koordinat masing-masing titik fisibel ke dalam fungsi tujuan, dan pilih yang terbesar (maksimasi) atau  terkkecil (minimasi), atau

4.       Gunakan garis selidik dengan menggambarkan  garis fungsi tujuan. Jika garis selidik digambar di luar daerah fisibel, maka titik optimalya adalah titik yang pertama kali tersentuh garis tersebut (maksimasi) atau yang terakhir tersentuh (minimasi), kecuai titik nol (0,0)

Metoda Simplex

Menyelesaikan programa linier dengan metoda simplex, dilakukan dengan langkah

1.       Mengubah bentuk umum ke bentuk standar, tyaitu formuulasi programa linier dengan fungsi pembatas bertanda sama dengan (“=”). Cara mengubahnya adalah dengan menambah slack variabel (S) pada kiri fungsi pembatas bertanda £ dan mengurangi ruas kiri fungsi pembatasa bertanda ³ dengan surplus variabel (U). Variabel U dan S bernilai ≥ 0.

2.       Berdasarkan bentuk standar, dibuat Tabel Solusi Awal (TSA). Liahat Tabel 2.2 !

3.       Melakukan iterasi/algoritma simplex, yaitu :

§  Pilih entering variabel, yaitu nbv dengan Cj paling negatif (maksimasi) atau Cj paling positif (minimasi). Jika ada lebih dari satu, pilih lah satuny. Dan perhatikan nilai-nilai aij> 0 di kolom variabel ini, sebut aij. Jika semua ais £ 0, stop (unbounded solution) ® kondisi/isyarat optimal

§  Pilih leaving variabel, yaitu bv pada baris dengan Min. {b_i/a_is; a_is > 0 }. Jika ada lebih dari satu, pillih salah satunya ® kondisi syarat fisibel

§  Persamaan pivot baru baru (ppb), yaitu baris pivot dibagi dengan elemen pivot (elemen pada sel irisan antara baris leaving variabel dan klom entering variable)

§  Buat tabel solusi baru dengan elemen awal ppb

§  Misal, ppb berasal dari baris r dan entering variable ada pada kolom s. Maka, baris lain pada tabel baru dihitung, dengan formula :

(2.3)…Z baru   = (Z lama) – (C_s) x ppb

(2.4)…bv baru = (bv lama) – (a_is) x ppb ; untuk i ¹ s

§  Jika Cj pada kolom nbv semuanya positif (maksimasi) atau semuanya negatif (minimasi, selesai (solusi sudah optimal). Jika masih ada yang negatif (maksimasi) atau masih ada yang positif (minimasi), kembali ke langkah1 !