Hal-Hal yang Berkaitan dalam Metode Grafik Program Linier

    Masalah minimisasi

Pada contoh di atas tampak bahwa permasalahan yang dihadapi adalah permasalahan maksimisasi. Artinya tujuan yang ingin di capai adalah laba (dalam hal ini) semaksimal mungkin. Kalau fungsi tujuan bersifat minimisasi maka alternatif yang optimal adalah alternatif yang dapat meminimumkan nilai Z. Bila ditempuh cara yang menggunakan gambar fungsi Z pada grafik maka untuk mendapatkan titik optimal garis Z harus digeser ke kiri. Bila ditempuh cara membandingkan nilai Z pada setiap alternatif maka alternatif yang mempunyai nilai Z terendah adalah alternatif yang optimal.

   Fungsi batasan bertanda “lebih besar atau sama dengan” ( ≥ )

Apabila fungsi batasan tidak bertanda ≤  melainkan bertanda ≥  maka arah daerah feasible akan berada di sebelah kanan atas garis batas tersebut.

Umpama : Batasan ketiga pada permasalahan di atas (6X₁ + 5X₂ ≤ 30) diubah tanda ketaksamaannya sehingga menjadi 6X₁ + 5X₂ ≥ 30 sedangkan batasan-batasan lain tetap, maka daerah feasible yang terjadi seperti yang tampak pada gambardi bawah ini, yakni pada segitiga ABC.

   Fungsi batasan bertanda “sama dengan” ( = )

Apabila fungsi batasan bertanda = , maka daerah feasible akan terletak pada garis yang memiliki tanda tersebut. Umpama batasan ketiga pada permasalahan perusahaan sepatu “IDEAL” di ubah tandanya menjadi 6X₁ + 5X₂ = 30, sedangkan batasan-batasan yang lain tetap seperti semula, maka daerah feasible yang baru terletak pada garis 6X₁ + 5X₂ = 30 antara titik A dan B, seperti tampak pada gambar di bawah ini :

 

Beberapa Pengertian dalam Linear Programming

Beberapa pengertian yang sering kita jumpai, sebagai berikut :

º    Solution (penyelesaian)

Solution adalah jawaban akhir dari suatu masalah.

º    Feasible Solution

  Feasible solution adalah penyelesaian yang tidak melanggar batasan-batasan yang ada. Misalnya dalam contoh metode grafik di depan, yang disebut daerah feasible adalah AOBCD

º    No Feasible Solution

No feasible solution berarti tidak ada daerah feasible. Artinya apabila sifat atau letak batasan-batasan sedemikian sehingga tidak memungkinkan terdapatnya daerah atau alternatif-alternatif yang feasible. Sebagai contoh batasan ke-3 (6X₁ + 5X₂ ≤ 15) pada Gambar 2.2 diubah menjadi 3X₁ + 5X₂ ≥ 60 maka grafiknya sperti tampak pada Gambar 2.10. Pada gambar itu batasan 2X₁ ≤ 8 menyatakan bahwa daerah feasible mulai garis

X = 4 ke kiri, batasan 3X₂ ≤ 15 menyatakan bahwa daerah feasible mulai garis X₂ = 5

ke bawah dan batasan 3X₁ + 5X₂ ≥ 60 menyatakan bahwa daerah feasible mulai garis 3X₁ + 5X₂ = 60 ke kanan atas. Akibatnya tidak ada daerah yang tidak melanggar salah satu dari ketiga batasan itu.

º    Optimal Solution

Optimal solution adalah feasible solution yang mempunyai nilai tujuan (nilai Z dalam fungsi tujuan) yang optimal atau terbaik (maksimum atau minimum).

Misalnya pada contoh di depan, dimana fungsi tujuan memaksimumkan Z = 3X₁ + 5X₂, maka nilai X₁, X₂, dan Z pada alternatif-alternatif atau titik-titik A,B,C dan D pada Gambar 2.2 pada metode grafik. Hasilnya seperti pada Tabel 2.3.

Tabel 2.3. Nilai Z pada alternatif A,B,C dan D untuk memilih titik yang optimal.

Alternatif	Nilai X1	Nilai X2	Nilai Z	Keterangan
A B C D	4 4 5/6 0	0 6/5 5 5	12 18 27,50 25	Maksimum, optimal

º    Multiple Optimal Solution

Multiple optimal solutions berarti terdapatnya beberapa alternatif optimal dalam suatu masalah. Misalnya bila fungsi tujuan dari contoh di depan diubah menjadi maksimumkan nilai Z = 6X₁ + 5X₂ maka fungsi tujuan ini bila digambarkan akan sejajar dengan batasan ke-3 (6X₁ + 5X₂ ≤ 30), Akibatnya gambar dari fungsi tujuan akan sejajar dengan batasan ke-3 itu, sehingga bila garis itu digeser ke kanan atas, maka yang feasible dan paling optimal akan berhimpit dengan batasan ke-3. Oleh sebab itu titik B dan titik C serta titik-titik yang berada di sepanjang garis itu semuanya mempunyai nilai Z sama dan optimal, dengan Z = 30.

º    Boundary Equation

Boundary equation terjadi apabila suatu batasan dengan tanda “sama dengan”. Misal bila batasan pertama (2X₁ ≤ 8) diubah tandanya menjadi “sama dengan” (2X₁ = 8), maka daerah feasible terletak sepanjang garis X₁ = 4 yang tidak melebihi batasan kedua dan ketiga. Dalam Gambar 2.8 terletak disepanjang garis antara titik A dan B.

º    Corner Point Feasible Solutions

Coner point feasible solution adalah feasible solution yang terletak pada sudut (perpotongan) antara 2 garis. Dalam Gambar 2.9 adalah titik-titik (4,0); (4,6/5); (5/6,5); (0,5) dan (0,0).

º    Corner Point Infeasible Solutions

Titik ini adalah titik yang terletak pada perpotongan 2 garis tetapi di luar daerah feasible. Pada Gambar 2.9 adalah titik-titik E,F dan G.

º    No Optimal Solutions

No optimal solutions terjadi apabila suatu masalah tidak mempunyai jawaban atau penyelesaian optimal. Hal ini bisa disebabkan oleh faktor-faktor sebagai berikut :

                           1.     Tidak ada feasible solutions

                           2.     Ada batasan yang tidak membatasi besar nilai Z.

Faktor ke-2 terjadi misalnya suatu masalah adalah sebagai berikut :

Fungsi tujuan :

            Maksimumkan : Z = 3X₁ + 5X₂

Batasan-batasan :        (1)  2X₁ ≤ 8

                                    (2)  X₁ ≤ 5

                                    (3)  X₁ ≥ 0 ; X₂ ≥ 0

Batasan-batasan itu dapat kita gambarkan seperti pada Gambar 2.12.

Karena tidak adanya batasan yang membatasi X₂, maka nilai Z dapat ditambah (digeser ke kanan atas) terus tanpa nilai maksimum.

Ketentuan – Ketentuan atau Sifat Linear Programming

            Dalam bagian ini akan dibahas beberapa ketentuan yang terdapat pada linear programming. Ketentuan – ketentuan berikut ini akan dipakai sebagai pedoman di dalam analisa berikut.

Ketentuan 1 :

               (i).            Kalau hanya ada satu optimal solution, pasti berupa corner point feasible solution.

             (ii).            Kalau multiple solutions maka terdapat lebih dari 2 titik optimal yang terletak pada garis yang menghubungkan 2 corner solutions.

Ketentuan 2 :

Corner point feasible solutions jumlahnya terbatas. Dalam contoh di depan hanya ada 5 titik, yaitu O, A, B, C, D.

Ketentuan 3 :

Kalau suatu corner point feasible solution baik dari 2 corner point feasible solutions yang terdekat, maka titik itu merupakan titik optimal atau terbaik diantara semua corner point feasible solutions. Dalam contoh di depan nilai Z pada titik C lebih besar dari nilai-nilai pada titik B dan titik D, maka titik C pasti mempunyai nilai Z terbesar di antara titik-titik O, A, B, D. Selama tujuan dari masalah itu memaksimumkan nilai Z, maka titik C merupakan titik optimal.

BACA JUGA : Program Linier Penyelesaian Menggunakan Metode Grafik