METODE GRAFIS UNTUK PENYELESAIAN LINEAR PROGRAMMING

Pertemuan ke 3

Istilah-Istilah dalam Program Linier

Solution : jawaban akhir dari suatu masalah PL. Feasible solution : penyelesaian yang memenuhi

(tidak melanggar) batasan-batasan yang ada. No-feasible solution : tidak ada penyelesaian yang

feasible (tidak ada penyelesaian yang memenuhi batasan-batasan yang ada).

Optimal solution : feasible solution yang mempunyai nilai tujuan yang optimal atau terbaik.

Multiple optimal solution : terdapat beberapa alternatif solusi optimal dalam satu masalah.

No- optimal solution : terjadi apabila suatu masalah tidak mempunyai jawaban atau penyelesaian optimal.

Langkah-langkah pemecahan dengan metode grafis : The first step in graphical method is to plot the feasible solutions, or the (feasible) solution space, which satisfies all the constraints simultaneously. Identifikasi harga-harga X1 dan X2 yang

memenuhi masing-masing pembatas. Gambarkan garis-garis pembatas dan

tentukan arah berlakunya harga (X1 dan X2 ), pada masing-masing pembatas, termasuk X1 ≥ 0 dan X2 ≥ 0.

Tentukan bidang yang dibatasi oleh garis –garis pembatas yang memenuhi syarat, yang disebut daerah fisibel.

Lanjutan . . .

The second step : determined the optimum solution. Gambarkan garis FT. Z = C1X1 + C2X2 ;

dengan koefisien arah : tg.α = X2/ X1= C2/ C1 ; dimana α = sudut anatara garis Z dengan sumbu X1.

Buatlah garis lain yang sejajar dengan garis Z sedemikian sehingga garis tersebut dapat melalui titik sudut terjauh dari daerah fisibel, titik ini disebut titik optimum.

Tentuakan harga (X1 , X2) pada titik optimum dengan menentukan titik potong dari garis-garis yang membentuk titik optimum itu.

Contoh Soal : Model LP untuk Persoalan Tabung Panas MAX Z= 350X1 + 300X2 S.T.: X1 + 1X2 ≤ 200 9X1 + 6X2 ≤ 1566 12X1 + 16X2 ≤ 2880 X1, X2 ≥ 0

Pembatas Pertama

Pembatas Kedua

Pembatas Ketiga

Menggambar Garis Fungsi Tujuan

Menggeser Garis Fungsi Tujuan

Menentukan Lokasi Solusi Optimal

Menentukan Nilai Fungsi Tujuan Solusi optimal terjadi pada perpotongan garis pembatas “pompa” dan “waktu”. Kedua garis tersebut adalah: X1 + X2 = 200 (1) dan 9X1 + 6X2 = 1566 (2) Dari (1) diperoleh, X2 = 200 -X1 (3) Substitusi (3) tehadap X2 pada (2) diperoleh, 9X1 + 6 (200 -X1) = 1566 sehingga X1 = 122 Maka solusi optimal adalah: X1=122, X2=200-X1=78 Total Profit = $350*122 + $300*78 = $66,100

Enumerasi Titik-titik Sudut

Kasus Khusus dengan Metode Grafis Contoh soal tadi hanya mempunyai satu solusi optimal. Berikut ini bahwa ada persoalan LP yang mempunyai kasus khusus seperti : Mempunyai solusi optimal yang tidak terbatas, biasa disebut juga mempunyai solusi alternatif atau bersolusi optimal banyak. Contoh : FT. Max. Z = 3X1 + 2X2 s/t (1) 1/40 X1 + 1/60 X2 ≤ 1 (2) 1/50 X1 + 1/50 X2 ≤ 1 X1,X2 ≥ 0 Tidak mempunyai solusi fisibel atau persoalan LP yang infisibel. Contoh : FT. Max. Z = 3X1 + 2X2 s/t (1) 1/40 X1 + 1/60 X2 ≤ 1 (2) 1/50 X1 + 1/50 X2 ≤ 1 (3) X1 ≥ 30 (4) X2 ≥ 30 X1,X2 ≥ 0 Mempunyai ruang solusi yang tidak terbatas. Contoh : FT. Max. Z = 2X1 - X2 s/t (1) X1 - X2 ≤ 1 (2) 2 X1 + X2 ≥ 6 X1,X2 ≥ 0

Solusi Metode Grafik Untuk Kasus Khusus :

Solusi Optimal Banyak Fungsi tujuan : Maks Z = 3 X1 + 2 X2 Fungsi batasan : s/t : 6 X1 + 4 X2 < 240 X1 + X2 < 50 X1 , X2 > 0

Tanpa Solusi Feasible Fungsi tujuan : Maks Z = 3 X1 + 2 X2 Fungsi batasan : 6 X1 + 4 X2 < 240 X1 + X2 < 50 X1 > 30 X2 > 20 X1 , X2 > 0

Solusi Tidak Terbatas Fungsi tujuan : Maks Z = 2 X1 - X2 Fungsi batasan : X1 - X2 < 1 2 X1 + X2 > 6 X1 , X2 > 0

TAKE HOME TEST