PERSOALAN LINIER PROGRAMING DAN PENYELESAIANYA DENGAN METODE GRAFIK

2.  LINIER PROGRAMMING METODE GRAFIK

Persoalan L.P dengan dua variabel/peubah dapat diselesaikan dengan pertolongan grafik. Tetapi soal dngan tiga variabel atau lebih harus diselesaikan secara aljabar matrik yaitu menggunakan metode simpleks.

Contoh : soal maksimalisasi

Cari x1, x2

s.r.s  Z = 2,5 x1 + 2 x2 ---à (5) : maksimum

d.k   x1 + 2 x2  £  8     ----à (1)

      3 x1 + 2 x2  £ 9    -----à (2)

        x1, x2 ³ 0          ------à (3), (4)

Jawab:

(1)   x1 + 2 x2  =  8

Jika x1 = 0, maka 2 x2 = 8

                             X2 = 4 --à A (0,4)

Jika x2 = 0, maka   x1  = 8 --à B (8,0)

(2)  3 x1 + 2 x2 = 9

Jika x1 = 0, maka 2 x2 = 9

                            X2 = 4,5 --à C(0;4,5)

Jika x2 = 0, maka 3 x1 = 9

                             X1 = 3 --à D (3,0)

(5) Z = 2,5 x1 + 2 x2

Misal Z = 0 --à 2,5 x1 + 2 x2 = 0

                        X1 = 0 --à 2 x2 = 0

                                            X2 = 0 --à (0,0)

Misal Z = 10 --à 2,5 x1 + 2 x2 = 10

                         X1 = 0 --à 2 x2 = 10

                                             X2 = 5 --à (0,5)

                         X2 = 0 --à 2,5 x1 = 10

                                                X1 = 4 --à (4,0)

Keterangan model :

v  (1) .... (4) disebut ketidaksamaan kendala

v  Kendala (3), (4) disebut kendala tak negatif, yang ditambahkan sendiri, karena x1 < 0 dan x2 < 0 tidak memberi arti.

v  Kendala (1), (2) disebut kendala utama

v  Fungsi Z disebut fungsi sasaran atau tujuan.

Keterangan Grafik :

v  Setiap kendala menghasilkan himpunan penyelesaian (H.P) berupa setengah bidang yang tertutup (artinya batasnya termasuk)

v  Irisan ke empat bidang menghasilkan daerah segi empat OABC beserta batasnya

v  Pasangan (x1,x2) yang memenuhi semua kendala disebut penyelesaian fisibel (P.F) atau Feasible Solution. Pada grafik akan disebut titik fisibel, sehingga daerah OABC merupakan himpunan titik fisibel, disebut daerah fisibel (fesible

    Region)

v  Penyelesaian fisibel yang juga mengoptimalkan fungsi sasaran disebut penyelesaian optimal (P.O). Inilah yang dicari dalam suatu soal L.P. Gambarnya disebut titik optimal (Optimal Solution)

v  Cara mencari titik optimal

(1)   Berikan dua nilai kepada Z misalnya Z = 0 dan Z = 5. Lukis kedua grafiknya. Jadi lukislah garis-garis 2,5 x1 + 2 x2 = 0 dan 2,5 x1 + 2 x2 = 5. Keduanya saling sejajar dan disebut garis selidik atau Iso profit untuk kasus maksimalisasi dan Isocost untuk kasus minimalisasi. Karena dari garis tersebut dapat dilihat kemiringan garis. Z = tetap dan digeser ke arah mana harus digeser supaya tercapai maksimal untuk Z. Titik optimal diperoleh sebagai titik fisibel terakhir yang dilalui oleh garis Z = tetap sebelum keluar dari daerah fisibel yaitu titik B.

(2)  Setelah dihitung diperoleh koordinat B yaitu ( 0,5;3,75) sebagai perpotongan atau persamaan simultan dari batas kendala (1) dan (2) sebagai berikut :

(1)          x1 + 2 x2  =  8      x 3

(2)         3 x1 + 2 x2 = 9     x 1
        3 x1 + 6 x2  =  24
         3 x1 + 2 x2 = 9

4 x2 = 15

x2  = 3,75

(1)          x1 + 2 (3,75)  =  8

                            x1      =  8  - 7,5

                            x1      =  0,5

Dengan demikian penyelesaian Optimal (P.O) nya adalah (x1,x2) = (0,5;3,75)

v  P.O ini akan menghasilkan fungsi sasaran/tujuan sebagai berikut :

Z (0,5;3,75) = 2,5 (0,5) + 2 (3,75)

                    = 8,75

8,75 ini adalah merupakan nilai program yang tidak lain adalah Z maksimal.

v  Contoh soal minimisasi (minimize)

Cari x1, x2

s.r.s : Z = 1,5  x1 + 2,5  x2  : Minimum  ........ (5)

d.p     x1 + 3 x2  ³  3 ..........................................(1)

         x1 +    x2   ³  2 ..........................................(2)

         x1, x2   ³  0  ...............................................(3), (4)

Jawab :

(1)          x1 + 3 x2  =  3

x1 = 0 à 3 x2 = 3

                 x2 =  1 à A (0,1)

x2 = 0 à x1 = 3 à B (3,0)

(2)         x1 + x2  =  2

x1  = 0 à x2 = 2 à C (0,2)

x2  = 0 à x1 = 2 à D (2,0)

(5)  Z = 1,5 x1 + 2,5 x2

0     =  1,5 x1 + 2,5 x2  à x1 = 0 ; x2 = 0 à (0,0)

     7,5  = 1,5 x1 + 2,5 x2 à x1 = 0 à 2,5 x2 = 7,5

                                                               x2 = 3 à (0,3)

                                          x2 = 0 à 1,5 x1 = 7,5

                                                               x1 = 5 à (5,0)

Semua titik jika dituangkan dalam grafik maka akan tampak sebagai berikut :

    

v  Garis selidik (Z) digeser ke kiri terakhir menyentuh titik C. Dengan demikian P.O adalah titik C (0,2) sehingga nilai program yaitu Z minimal = 1,5 x1 + 2,5 x2 = 1,5 (0) + 2,5 (2) = 5.

v  Contoh soal cerita

Perusahaan pengalengan ikan memproduksi dua jenis produk ikan kaleng jenis tengiri dan tongkol. Kedua jenis produk tersebut diproses melalui tiga tahap yaitu pemotongan, pengolahan dan pengkemasan. Rata-rata setiap unit produk ikan kaleng jenis tengiri diproses selama 2 menit pada mesin pemotong, 2 menit pada mesin pengolah, 4 menit pada mesin pengkemas. Sedangkan rata-rata setiap unit produk ikan kaleng jenis tongkol diproses selama 1 menit pada mesin pemotong, 3 menit pada mesin pengolah dan 3 menit pada mesin pengkemas. Kapasitas waktu pengoperasian mesin sangat terbatas, yaitu kapasitas operasi mesin pemotong 300 menit/hari, mesin pengolah 600 menit/hari dan mesin pengkemas 720 menit/hari. Harga jual produk ikan kaleng jenis tengiri dan tongkol masing-masing Rp. 3.000/unit. Dengan kapasitas pengoperasian mesin-mesin yang terbatas, perusahaan ingin memperoleh keuntungan maksimum. Selesaikan dengan metode aljabar.