Penyelesaian Program Linear Dengan Metode Grafik

Metode grafik merupakan salah satu teknik pemecahan program linear. Jadi program linear yang telah diformulasikan baru dapat dipecahkan dengan metode grafik ini. Untuk lebih jelasnya tentang program linear dapat dilihat pada  Program Linear

images-34 Penyelesaian Program Linear Dengan Metode Grafik

Metode Grafik

Metode grafik dapat digunakan untuk pemecahan masalah program linear yang yang hanya memiliki 2 variabel.
Sesuai dengan namanya, pemecahan program linear ini dilakukan dengan membuat grafik dari persamaan program linear yang telah diformulasikan, sehingga akan didapatkan titik-titik dari perpotongan garis garis dalam grafik tersebut untuk mengetahui outputnya.
Hanya saja, jika dalam suatu program linear terdapat lebih dari 2 variabel, misalnya X1, X2, dan X3. Maka metode grafik ini tidak dapat dipakai.Oleh karena itu, diperlukan metode satu lagi yaitu metode simpleks yang efektif digunakan untuk menyelesaikan program linear yang memiliki 3 variabel atau lebih.

Langkah-Langkah Pemecahan Dengan Metode Grafik

Langkah-langkah penyelesaian dengan metode grafik adalah sebagai berikut :
    1. Gambarkan garis-garis kendala pada sumbu koordinat. Anggap kendalanya sebagai suatu persamaan
    2. Tentukan daerah dalam bidang koordinat yang memenuhi semua kendala (daerah feasible), kemudian tentukan semua titik daerah feasible tersebut.
    3. Hitung nilai fungsi tujuan untuk semua titik sudut daerah layak. Untuk keputusanya, pilih koordinat titik yang memberikan nilai terbesar untuk fungsi tujuan maksimasi, dan nilai fungsi terkecil untuk tujuan minimasi.
Untuk lebih jelasnya berikut adalah contoh soal dari pemecahan program linear dengan metode grafik.

Contoh Metode Grafik

PT. Tatikucant memproduksi 2 macam produk yang dikerjakan secara manual. Setiap unit produk I memerlukan waktu 20 menit pada proses 2 dan 24 menit pada proses 3, sedangkan setiap unit produk II memerlukan waktu 15 menit pada proses 1, 16 menit proses 2, dan 30 menit proses 3. Produk I memberikan keuntungan sebesar Rp.170/unit dan Rp.190/unit untuk produk II. Jam kerja per hari yang tersedia untuk proses 1, 2, dan proses 3 masing-masing 1050 menit, 1600 menit, dan 2400 menit. Berapakah jumlah produk I dan II harus diproduksi agar keuntungan maksimal ?

Penyelesaian :

Persoalan tersebut dapat ditabulasikan sebagai berikut:
Proses Produk I Produk II Kapasitas (menit)
1 15 1050
2 20 16 1600
3 24 30 2400
Keuntungan/unit 170 190

 

  • Langkah 1 : Formulasikan
Sehingga dari hasil formulasi didapatkan persamaan berikut :
 
Maksimumkan : Z = 170 X1 + 190 X2
Dengan kendala :
15 X2 ≤ 1050
20 X1 + 16 X2 ≤ 1600
24 X1 + 30 X2 ≤ 2400
X1, X2 ≥ 0
  • Langkah 2 : Buatlah grafiknya
Untuk menggambarkan grafiknya, cara paling mudah adalah dengan menemukan nilai suatu variabel saat variabel lain bernilai nol.Maksudnya, kita membuat 2 titik pada sumbu X (dimana nilai Y = 0) dan di sumbu Y (dimana nilai X = 0) kemudian menghubungkan 2 titik tersebut dengan garis. Sehingga didapatkan persamaan garis lurus suatu kendala. Jika terdapat 3 kendala, maka otomatis akan terdapat 3 garis juga.

Jadi persamaan yang didapat adalah :
  • 15 X2 = 1050
    X2 = 70
  • 20 X1 + 16 X2 = 1600
    X1 = 0 ⇾ X2 = 100 → F(0,100)
    X2 = 0 ⇾ X1 = 80 → D(80,0)
  • 24 X1 + 30 X2 = 2400
    X1 = 0 ⇾ X2 = 80 → E(0,80)
    X2 = 0 ⇾ X1 = 100 → H(100,0)
Jadi jika dinyatakan dalam grafik adalah sebagai berikut :
Setelah didapatkan garis-garisnya, untuk mengetahui daerah mana yang diarsir dari suatu persamaan dapat dilihat dari tanda persamaan, seperti :
  • Tanda ≤ berarti bagian sebelah kiri dari persamaan garis yang diarsir.
  • Tanda ≥ berarti bagian sebelah kanan dari persamaan gars yang diarsir.
  • Tanda = berarti hanya pada bagian persamaan garis (hanya garis)
Daerah yang memenuhi persayaran adalah daerah yang terarsir oleh semua kendala yang ada.
Bedasarkan persamaan-persamaan kendala diatas, daerah yang bersamaan memenuhi ketiga kendala ditunjukan oleh area gambar di atas yang di arsir yaitu OABCD. Bagian yang diarsir dinamakan daerah feasible. Bagian OABCD dinamakan daerah feasible karena memenuhi solusi dari semua pembatas yang ada.
  • Langkah 3 : Tentukan outputnya
Untuk mencari titik yang paling menguntungkan dari dearah feasible tersebut adalah titik yang terjauh dari sumbu O untuk masalah maksimasi. Sedangkan untuk kasus minimasi adalah yang paling dekat dengan titik sumbu O.
Pada gambar diatas sebagian titik koordinat dapat diketahui yaitu titik O(0;0), titik D(80;0), titik A(0;70). Sedangkan titik B dan titik C dapat dicari dengan mencari perpotongan antara 2 garis yang saling menyinggung dengan cara subtitusi maupun eliminasi.Jadi koordinat dari titk B dapat didapat dengan mengsubtitusikan kendala (15 X2 = 1050) dengan kendala (20 X1 + 16 X2 = 1600) maka didapatkanlah koordinatnya adalah (12,5;70).

Sedangkan untuk titik C dapat didapatkan dengan cara yang sama antara kendala (20 X1 + 16 X2 = 1600) dengan kendala (24 X1 + 30 X2 = 2400) maka didapatkanlah koordinatnya (400/9;400/9).

Setelah itu lakukan pengujian dari semua koordinat di daerah feasible yang didapat ke persamaan tujuan seperti contoh di atas adalah (Z = 170 X1 + 190 X2) dan carilah hasil terbesar untuk masalah maksimasi dan hasil terkecil untuk masalah minimasi.Karena dalam contoh diatas adalah kasus maksimasi, maka kita cari nilai Z terbesar sebagai outputnya. Sehingga didapatkan :

Titik A :
Z = 170 (0) + 190 (70) = 13.300

Titik D :
Z = 170 (80) + 190 (0) = 13.600

Titik B :
Z = 170 (12,5) + 190 (70) = 15.425

Titik C :
Z = 170 (400/9) + 190 (400/9) = 16.000

Dari hasil pengujian daerah feasible, maka yang memberikan nilai optimum adalah titik C. Jadi maksudnya jumlah produk 1 (X1) yang harus dibuat adalah 400/9 dan jumlah produk 2 (X2) yang harus dibuat adalah 400/9 agar produksi maksimal dengan nilai output sebesar 16.000

 

Pengartian Dalam Program Linear

    1. Feasible Solution
Suatu solusi yang memenuhi seluruh pembatas yang ada pada persoalan tersebut. Pada contoh diatas feasible solutionya adalah OABCD.

 

    1. Infeasible Solution
Suatu solusi dimana tidak ada titik-titk secara serentak memenuhi semua kendala dalam masalah tersebut.

 

    1. Optimal Solution
Feasible solution yang memberikan nilai terbaik bagi fungsi tujuanya. Terbaik diartikan nilai terbesar untuk tujuan maksimasi dan nilai terkecil untuk tujuan minimasi. Pada contoh diatas titik C merupakan optimal solution.
    1. Multiple Optimal Solution
Ini terjadi jika fungsi tujuan terletak pada lebih dari satu titik optimal. Multiple optimal solution akan memberikan keluwesan dalam memilih solusi bagi pengambil keputusan.
    1. Boundary Equation
Ini terjadi apabila ada kendala dengan tanda “sama dengan”, dan terjadi daerah feasible yang terletak pada garis tersebut.
    1. No Optimal Solution
Terjadi jika suatu masalah tidak mempunyai penyelesaian optimal, disebabkan oleh tidak ada feasible solution dan juga disebabkan oleh adanya batasan yang tidak membatasi besar nilai Z.
Tags: