Program Linear : Penyelesaian Grafik
Disusun oleh Diana Rosadi 065109318
copyright diana_rosadi 2012 All Rights reserved
Model Program Linear
Ciri-ciri masalah yang dapat diselesaikan dengan model program linear Semua variabel penyusunya bernilai tidak negatif Fungsi objektif dapat dinyatakan sebagai fungsi linear variabel-variabelnya. Kendala dapat dinyatakan sebagai suatu sistem persamaan linear
copyright diana_rosadi 2012 All Rights reserved
Bentuk standart dari program linear adalah: Mencari X=(x1,x2,,xn) 0 yang memaksimumkan atau meminimumkan f (X)=f (x1,x2,,xn) = c1x1+c2x2++cnxn dengan kendala: a11x1+a12x2++a1nxn=b1 a21x1+a22x2++a2nxn=b2
am1x1+am2x2++amnxn=bm
copyright diana_rosadi 2012 All Rights reserved
Contoh Soal
Telitilah mana diantara model-model berikut yang dapat diselesaikan dengan program linear soal
Jwb Bukan bentuk program linear karena fungsi sasarannya mengandung suku X22.
copyright diana_rosadi 2012 All Rights reserved
Contoh Soal
Telitilah mana diantara model-model berikut yang dapat diselesaikan dengan program linear soal
Jwb Model linear, tampak bahwa baik fungsi maupun kedua kendala merupakan bentuk fungsi linear dalam x1 dan x2.
copyright diana_rosadi 2012 All Rights reserved
Langkah-langkah pembuatan model program linear
1 Tentukan variabel-variabel keputusan
2
Buatlah fungsi sasaran (yang akan dioptimumkan)
3
Tentukan kendala berdasarkan keterbatasan sumber daya
copyright diana_rosadi 2012 All Rights reserved
Contoh Soal 1
Seorang pengusaha bahan kimia membuat 2 macam cairan pembunuh serangga yaitu superior (C1) dan jenis standar (C2). Keduanya terbuat dari 2 macam bahan yang sama yaitu A dan B dengan komposisi yang berbeda. Setiap liter C1 dibuat dari 1 unit bahan A dan 3 unit bahan B. Setiap liter C2 dibuat dari 2 unit bahan A dan 1 unit bahan B. setiap hari hanya memperoleh 20 unit A dan 20 unit bahan B. Untuk setiap liter cairan C1 , keuntungan yang didapat Rp. 30.000,- sedangkan jenis C2 , keuntungannya sebesar Rp.20.000, Jika diasumsikan semua cairan laku terjual, berapa liter cairan masing-masing jenis harus ia buat tiap agar mendapatkan keuntungan maksimum?
copyright diana_rosadi 2012 All Rights reserved
Penyelesaian
Misalkan : x1 = jumlah cairan jenis superior x2 = jumlah cairan jenis standar Maka fungsi sasaran maksimum f (X)=f (x1,x2)=30.000 x1 +20.000 x2
copyright diana_rosadi 2012 All Rights reserved
Jika dibuat dalam bentuk tabel
Bahan Cairan jenis Superior
1 3 30.000
Cairan Jenis Standar
2 1 20.000
Pasokan Maksimum
20 20
A B Untung
Maka model untuk masalah pengusaha kimia tersebut adalah f (x1,x2)=30.000 x1 +20.000 x2 Kendala x1 + 2x2 20 3x1 + x2 20; x1 , x2 0
copyright diana_rosadi 2012 All Rights reserved
Penyelesaian Grafik
Metode Grafik
Menggunakan grafik kendala sebagai alat untuk mencari titik optimum Metode ini terbatas untuk 2 kendala
Metode Simpleks
Mencari titik optimal dengan menyelidiki titik sudut bidang datar
Metode Titik interior
Memulai iterasinya dari titik dalam bidang datar
Pencarian dilakukan secara numerik sehingga berapapun jumlah variabel bisa dilakukan.
Secara iteratif menuju pada titik sudut yang optimum
copyright diana_rosadi 2012 All Rights reserved
Langkah-langkah penyelesaian program linear dengan metode grafik
Buat model yang sesuai dengan masalah yang ada
Gambar grafik kendala-kendalanya
Tentukan daerah fisible
Hitung nilai fungsi di titik-titik sudut segi-n daerah fisible Cari titik yang menghasilkan nilai fungsi yang paling optimal
copyright diana_rosadi 2012 All Rights reserved
Contoh soal
Selesaikan contoh soal 1 Penyelesaian Model yang akan diselesaikan adalah: Maksimumkan
f (x1,x2)=30.000 x1 +20.000 x2= 3x1+ 2 x2 (puluhan ribu)
Kendala
x1 + 2x2 20 3x1 + x2 20; x1 , x2 0
copyright diana_rosadi 2012 All Rights reserved
Mencari titik sudut x1 + 2x2 20, (x1 , x2 ) =(B,A)= (20,10) 3x1 + x2 20; (x1 , x2 ) = (D,C)=(20/3,20) x 1 , x2 0 x2
C(0,20)
A(0,10) E B(20,0) D(20/3,0) 3x1 + x2 =20
x1 + 2x2 =20
x1
copyright diana_rosadi 2012 All Rights reserved
Mencari nilai E.
Dengan mensubstitusikan x1 = 4 ke persamaan x1 + 2 x2 =20 didapatkan x2 =8.
Jadi E= (4,8)
copyright diana_rosadi 2012 All Rights reserved
Menentukan nilai fungsi di titik-titik sudut daerah visible
Titik sudut daerah fisible O(0,0) A(0,10) Nilai Fungsi = f (x1,x2)= 3x1+ 2 x2 3(0)+2(0)=0 3(0)+2(10)=20
E(4,8)
D(20/3,20)
3(4)+2(8)=28
3(20/3)+2(0)=20
Melihat tabel di atas, maka nilai fungsi maksimum terjadi pada titik E (4,8) dengan nilai fungsi 28. Untuk mencapai keuntungan maksimum, pengusaha membuat 4 liter cairan C1 dan 8 liter cairan C2. Keuntungan yang didapat adalah 280.000
copyright diana_rosadi 2012 All Rights reserved
Kejadian Khusus
Alternatif Penyelesaian Jika terdapat dua titik atau lebih yang memiliki nilai optimum yang sama Contoh soal 1, misal keuntungan yang didapat liter cairan C1 adalah 10.000(bukan 20.000), tentukan cairan yang harus dibuat supaya keuntungan maksimum!
copyright diana_rosadi 2012 All Rights reserved
Penyelesaian
Maksimumkan f (x1,x2)=30.000 x1 +10.000 x2= 3x1+ x2 (puluhan ribu) Kendala x1 + 2x2 20 3x1 + x2 20; x1 , x2 0
Titik sudut daerah fisible O(0,0) A(0,10) E(4,8) D(20/3,20) Nilai Fungsi = f (x1,x2)= 3x1+ x2 3(0)+(0)=0 3(0)+(10)=10 3(4)+(8)=20 3(20/3)+(0)=20
copyright diana_rosadi 2012 All Rights reserved
Nilai fungsi adalah 20 yang terletak pada titik E dan D. Alternatif penyelesaian, setiap titik diantara ruas garis DE (persaman garisnya 3x1+ x2 =20 dengan 4 x1 20/3) akan memenuhi nilai fungsi = 20.
copyright diana_rosadi 2012 All Rights reserved
Daerah fisible tak terbatas
Daerah fisible adalah daerah yang memenuhi semua kendala. Contoh : Minimumkan f (x1,x2)= 2x1+ 3 x2 Kendala x1 + x 2 3 x1 - 2 x2 4 x1 , x2 0
copyright diana_rosadi 2012 All Rights reserved
Penyelesaian Titik sudut yang terbentuk adalah A(0,3). B(3,0) dan D(4,0) f(A)=f(0,3)=2(0)+3(3)=9 f(B)=f(3,0)=2(3)+3(0)=6 x2
A(0,3)
f(C)=f(4,0)=2(4)+3(0)=8 Nilai min=5 pada titik B(3,0) daerah fisible tak terbatas
x1 - 2x2 =4 B(3,0) C(0,-2) D(4,0) x1 + x2 =3
copyright diana_rosadi 2012 All Rights reserved
x1
Penyelesaian tak terbatas
Dalam contoh soal sebelumnya, daerah fisiblenya tak terbatas namun titik minimumnya tetap ada. Ada kalanya daerah fisibelnya tak terbatas dan nilai optimumnya juga tak terbatas dalan hal ini soal dikatakan tidak memiliki penyelesaian. Contoh : maksimumkan f (x1,x2)= 2x1+ 3 x2 Kendala x1 + x 2 3 x1 - 2 x2 4 x1 , x2 0
copyright diana_rosadi 2012 All Rights reserved
Penyelesaian Titik sudut yang terbentuk adalah A(0,3). B(3,0) dan D(4,0) f(A)=f(0,3)=2(0)+3(3)=9 f(B)=f(3,0)=2(3)+3(0)=6 x2
A(0,3
f(C)=f(4,0)=2(4)+3(0)=8 F(N)=f(5,0)=2(5)+3(0)=10 Nilai max= tak berhingga
x1 - 2x2 =4 B(3,0) C(0,-2) D(4,0) x1 + x2 =3
copyright diana_rosadi 2012 All Rights reserved
x1
Soal tak Fisible
Kasus di mana daerah fisible tidak ada. Contoh : maksimumkan f (x1,x2)= 4x1+ 3 x2 Kendala x1 + x 2 3 2x1 - x2 3 x1 4 x1 , x2 0
copyright diana_rosadi 2012 All Rights reserved
Penyelesaian
x2
OBFA adalah daerah yang memenuhi kendala. Irisan daerah yang berarsir x1 4 himpunan kosong Soalnya tidak fisible dan tidak memiliki penyelesaian
A(0,3
B(1.5,0) D(3,0) C(0,-3)
E(4,0) x1 + x2 =3 x1 =4
x1
2x1 - x2 =3
copyright diana_rosadi 2012 All Rights reserved
Soal Redundant (kelebihan)
Terdapat satu/lebih kendala yang tidak berpengaruh terhadap daerah fisiblenya. Contoh :
copyright diana_rosadi 2012 All Rights reserved
Penyelesaian : Hasil transformasi model dengan yi= ln(x1) adalah minimumkan g (y1,y2)= 2y1+ 3 y2 Kendala 3y1 + 2y2 3 y1 +4 y2 4 2y1 + 3y2 1 y1 , y2 0
copyright diana_rosadi 2012 All Rights reserved
y2
A(0,1.5) E(0,1)
G F(4,0) B(1,0) 2y1 + 3y2 =1
C(0,1/3) D(0.5,0)
y1
3y1 + 2y2 =3
y1 + 4x2 =4
copyright diana_rosadi 2012 All Rights reserved
Sekian dan Terima kasih
copyright diana_rosadi 2012 All Rights reserved