Download - Program Linear
![Page 1: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/1.jpg)
Program Linear :Penyelesaian GrafikDisusun oleh Diana Rosadi
065109318
copyright © diana_rosadi 2012 All Rights reserved
![Page 2: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/2.jpg)
Model Program LinearCiri-ciri masalah yang dapat diselesaikan dengan model program linear Semua variabel penyusunya bernilai tidak
negatifFungsi objektif dapat dinyatakan sebagai
fungsi linear variabel-variabelnya.Kendala dapat dinyatakan sebagai suatu
sistem persamaan linear
copyright © diana_rosadi 2012 All Rights reserved
![Page 3: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/3.jpg)
• 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
![Page 4: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/4.jpg)
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 X2
2.
copyright © diana_rosadi 2012 All Rights reserved
![Page 5: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/5.jpg)
Telitilah mana diantara model-model berikut yang dapat diselesaikan dengan program linearsoal
Jwb Model linear, tampak bahwa baik fungsi maupun kedua kendala merupakan bentuk fungsi linear dalam x1 dan x2.
Contoh Soal
copyright © diana_rosadi 2012 All Rights reserved
![Page 6: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/6.jpg)
Langkah-langkah pembuatan model program linear
1
2
3
Tentukan variabel-variabel keputusanTentukan variabel-variabel keputusan
Buatlah fungsi sasaran (yang akan dioptimumkan)Buatlah fungsi sasaran (yang akan dioptimumkan)
Tentukan kendala berdasarkan keterbatasan sumber dayaTentukan kendala berdasarkan keterbatasan sumber daya
copyright © diana_rosadi 2012 All Rights reserved
![Page 7: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/7.jpg)
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
![Page 8: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/8.jpg)
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
![Page 9: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/9.jpg)
• Jika dibuat dalam bentuk tabel
• 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
Bahan Cairan jenis Superior
Cairan Jenis Standar
Pasokan Maksimum
A 1 2 20
B 3 1 20
Untung 30.000 20.000
copyright © diana_rosadi 2012 All Rights reserved
![Page 10: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/10.jpg)
Penyelesaian GrafikMetode
Titik interiorMetode Simpleks
Metode Grafik
Menggunakan grafik kendala sebagai alat untuk mencari titik optimum
Metode ini terbatas untuk 2 kendala
Mencari titik optimal dengan menyelidiki titik sudut bidang datar
Pencarian dilakukan secara numerik sehingga berapapun jumlah variabel bisa dilakukan.
Memulai iterasinya dari titik dalam bidang datar
Secara iteratif menuju pada titik sudut yang optimum
copyright © diana_rosadi 2012 All Rights reserved
![Page 11: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/11.jpg)
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
![Page 12: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/12.jpg)
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
![Page 13: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/13.jpg)
Mencari titik sudut• x1 + 2x2 ≤ 20, (x1 , x2 ) =(B,A)= (20,10)
• 3x1 + x2 ≤ 20; (x1 , x2 ) = (D,C)=(20/3,20)
• x1 , x2 ≥ 0
x1
x2
B(20,0)
A(0,10)
C(0,20)
D(20/3,0)
E
3x1 + x2 =20x1 + 2x2 =20
copyright © diana_rosadi 2012 All Rights reserved
![Page 14: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/14.jpg)
• 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
![Page 15: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/15.jpg)
• Menentukan nilai fungsi di titik-titik sudut daerah visible
Titik sudut daerah fisible Nilai Fungsi = f (x1,x2)= 3x1+ 2 x2
O(0,0) 3(0)+2(0)=0
A(0,10) 3(0)+2(10)=20
E(4,8) 3(4)+2(8)=28
D(20/3,20) 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
![Page 16: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/16.jpg)
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
![Page 17: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/17.jpg)
PenyelesaianMaksimumkan f (x1,x2)=30.000 x1 +10.000 x2= 3x1+ x2 (puluhan ribu)
Kendala x1 + 2x2 ≤ 20
3x1 + x2 ≤ 20; x1 , x2 ≥ 0Titik sudut daerah fisible Nilai Fungsi = f (x1,x2)= 3x1+ x2
O(0,0) 3(0)+(0)=0
A(0,10) 3(0)+(10)=10
E(4,8) 3(4)+(8)=20
D(20/3,20) 3(20/3)+(0)=20
copyright © diana_rosadi 2012 All Rights reserved
![Page 18: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/18.jpg)
• 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
![Page 19: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/19.jpg)
Daerah fisible tak terbatas• Daerah fisible adalah daerah yang memenuhi
semua kendala.• Contoh :
Minimumkan f (x1,x2)= 2x1+ 3 x2
Kendala x1 + x2 ≥ 3
x1 - 2 x2 ≤ 4
x1 , x2 ≥ 0
copyright © diana_rosadi 2012 All Rights reserved
![Page 20: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/20.jpg)
f(A)=f(0,3)=2(0)+3(3)=9f(B)=f(3,0)=2(3)+3(0)=6f(C)=f(4,0)=2(4)+3(0)=8Nilai min=5 pada titik B(3,0) daerah fisible tak terbatas
x2
B(3,0)
A(0,3)
C(0,-2)D(4,0)
x1 + x2 =3
x1 - 2x2 =4
x1
• PenyelesaianTitik sudut yang terbentuk adalah A(0,3). B(3,0) dan D(4,0)
copyright © diana_rosadi 2012 All Rights reserved
![Page 21: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/21.jpg)
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 + x2 ≥ 3
x1 - 2 x2 ≤ 4
x1 , x2 ≥ 0
copyright © diana_rosadi 2012 All Rights reserved
![Page 22: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/22.jpg)
f(A)=f(0,3)=2(0)+3(3)=9f(B)=f(3,0)=2(3)+3(0)=6f(C)=f(4,0)=2(4)+3(0)=8F(N)=f(5,0)=2(5)+3(0)=10…Nilai max= tak berhingga
x2
B(3,0)
A(0,3
C(0,-2)D(4,0)
x1 + x2 =3
x1 - 2x2 =4
x1
• PenyelesaianTitik sudut yang terbentuk adalah A(0,3). B(3,0) dan D(4,0)
copyright © diana_rosadi 2012 All Rights reserved
![Page 23: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/23.jpg)
Soal tak Fisible• Kasus di mana daerah fisible tidak ada.• Contoh :
maksimumkan f (x1,x2)= 4x1+ 3 x2
Kendala x1 + x2 ≤ 3
2x1 - x2 ≤ 3
x1 ≥ 4
x1 , x2 ≥ 0
copyright © diana_rosadi 2012 All Rights reserved
![Page 24: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/24.jpg)
• Penyelesaian
x2
D(3,0)
A(0,3
C(0,-3)
E(4,0)
x1 + x2 =32x1 - x2 =3
x1B(1.5,0)
x1 =4
• OBFA adalah daerah yang memenuhi kendala.
• Irisan daerah yang berarsir x1 ≥ 4 himpunan kosong
• Soalnya tidak fisible dan tidak memiliki penyelesaian
copyright © diana_rosadi 2012 All Rights reserved
![Page 25: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/25.jpg)
Soal Redundant (kelebihan)• Terdapat satu/lebih kendala yang tidak
berpengaruh terhadap daerah fisiblenya.• Contoh :
copyright © diana_rosadi 2012 All Rights reserved
![Page 26: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/26.jpg)
• 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
![Page 27: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/27.jpg)
y1F(4,0)
A(0,1.5)
D(0.5,0)
3y1 + 2y2 =3y1 + 4x2 =4
y2
E(0,1)
C(0,1/3)B(1,0)
2y1 + 3y2 =1
G
copyright © diana_rosadi 2012 All Rights reserved
![Page 28: Program Linear](https://reader031.vdokumen.com/reader031/viewer/2022012305/55721180497959fc0b8f1046/html5/thumbnails/28.jpg)
Sekian dan Terima kasih
copyright © diana_rosadi 2012 All Rights reserved