2. Program Linier a. Defenisi Program linier adalah metode untuk

Contoh : UMPTN 1991. Seorang anak diharuskan makan dua jenis tablet setiap hari. Tablet pertama mengandung 5 unit vitamin A dan 3 unit vitamin B, seda...

20 downloads 608 Views 4MB Size
 

2. Program  Linier     a. Defenisi     Program  linier  adalah  metode  untuk  mendapatkan  penyelesaian  optimum   dari  suatu  fungsi  sasaran  yang  mengandung  kendala  atau  batasan  yang   dapat  dibuat  dalam  bentuk  sistem  pertidaksamaan  linier     Diantara  himpunan  penyelesaian  dari  sistem  pertidaksamaan  linier  ada   satu  penyelesaian  terbaik  yang  disebut  penyelesaian  optimum  yang  dapat   merupakan  nilai  maksimum  atau  minimum  dari  fungsi  sasaran  yang  biasa   disebut  fungsi  tujuan  atau  fungsi  objektif       Permasalahan  yang  akan  diselesaikan  harus  dijabarkan  dalam  bahasa   matematika  yang  disebut  model  matematika     Untuk  memudahkan  membuat  model  matematika  sebaiknya  permasalahan   dibuatkan  dalam  bentuk  tabel     Contoh  :       UMPTN  1991     Seorang  anak  diharuskan  makan  dua  jenis  tablet  setiap  hari.  Tablet   pertama  mengandung  5  unit  vitamin  A  dan  3  unit  vitamin  B,  sedangkan   tablet  kedua  mengandung  10  unit  vitamin  A  dan  1  unit  vitamin  B.  Dalam   sehari  anak  membutuhkan  20  unit  vitamin  A  dan  5  unit  vitamin  B.  Jika   harga  tablet  pertama  Rp  4,00/biji  dan  tablet  kedua  Rp  8,00/biji,  maka   pengeluaran  minimum  untuk  pembelian  tablet  per  hari     Permasalahan  di  atas  dalam  bentuk  tabel       Tablet  I   𝑥   Tablet  II   𝑦   Batasan   Vitamin  A   5   10   Minimal  20   Vitamin  B   3   1   Minimal  5   Harga/Biji   4   8       Tabel  di  atas  diterjemahkan  kedalam  model  matematika  sebagai  berikut     Vitamin  A 5𝑥 + 10𝑦 ≥ 20     Vitamin  B 3𝑥 + 𝑦 ≥5   Tambahan  batasan  adalah  anak  diharuskan  makan  kedua  jenis  tablet  setiap   hari  dan  model  matematikanya  adalah     𝑥 ≥ 0  dan  𝑦 ≥ 0    

 

Fungsi  objektifnya  adalah  meminimalkan  pengeluaran  untuk  pembelian   tablet  model  matematikanya  adalah     𝑓!"#"!$! 𝑥, 𝑦 = 4𝑥 + 8𝑦       Secara  keseluruhan  model  matematikanya  adalah     5𝑥 + 10𝑦 ≥ 20 3𝑥 + 𝑦 ≥5     𝑥 ≥0 𝑦 ≥0   𝑓!"#"!$!   𝑥, 𝑦 = 4𝑥 + 8𝑦       Himpunan  penyelesaiannya  gunakan  cara  pada  bagian  1.b  dan  1.c     Gambar  garis  5𝑥 + 10𝑦 = 20  dan  garis  3𝑥 + 𝑦 = 5    

    Ambil  titik  uji   0,0  dan  subtitusikan  ke  dalam  pertidaksamaan     5𝑥 + 10𝑦 ≥ 20 3𝑥 + 𝑦 ≥5 5 0 + 10 0 ≥ 20       3 0 + 0 ≥ 5       0+0 ≥ 20 0+0 ≥5 0 ≥ 20 0 ≥5   Pertidaksamaan  salah         Pertidaksamaan  salah   Daerah  5𝑥 + 10𝑦 ≥ 20       Daerah  3𝑥 + 𝑦 ≥ 5   Di  atas  garis  5𝑥 + 10𝑦 = 20       Di  atas  garis  3𝑥 + 𝑦 = 5     Untuk  daerah  𝑥 ≥ 0  terletak  di  sebelah  kanan  sumbu  Y     Untuk  daerah  𝑦 ≥ 0  terletak  di  atas  sumbu  Y     Irisannya  atau  himpunan  penyelesaiannya  adalah  daerah  yang  berwarna   gelap  yang  merupakan  kumpulan  pasangan  titik  titik  yang  memenuhi  ke   empat  pertidaksamaan  linier  di  atas      Untuk  mencari  titik  optimum  digunakan  metode  titik  sudut  dan  garis   selidik  

 

b. Metode  Titik  Sudut     Nilai  optimum  (maksimum/minimum)  fungsi  terletak  pada  titik  sudut   daerah  yang  diarsir     Titik  sudut  adalah  perpotongan  antara  garis  pembatas  himpunan   penyelesaiannya     Untuk  mencari  titik  sudut  atau  perpotongan  dua  garis  bisa  digunakan   metode  subtitusi,  metode  eliminasi  pada  pelajaran  sistem  persamaan   linier  atau  menggunakan  motode  determinan  ,  metode  invers  pada   pelajaran  matriks    

    Dengan  menggunakan  salah  satu  metode  di  atas  akan  didapatkan  titik  titik   sudut  daerah  yang  diarsir       ! ! Titik   ! , !  adalah  perpotongan  garis  5𝑥 + 10𝑦 = 20  dan  3𝑥 + 𝑦 = 5     Titik   0,5  adalah  perpotongan  garis  3𝑥 + 𝑦 = 5  dan  sumbu  Y     Titik     4,0  adalah  perpotongan  garis  5𝑥 + 10𝑦 = 20  dan  sumbu  X     Masukkan  nilai   𝑥, 𝑦  dari  titik  titik  sudut  tersebut  dan  bandingkan  nilainya       ! !

Nilai  di  titik  

 

𝑓 𝑥, 𝑦

,

! !

= =

 

               Nilai  di  titik   4,0    

= 4𝑥 + 8𝑦 !

=4

 

 

!" ! !"

!

+

+8 !" !

𝑓 𝑥, 𝑦

! !

                       

= 4𝑥 + 8𝑦 =4 4 +8 0 = 16 + 0   = 16

     Nilai  di  titik   0,5   𝑓 𝑥, 𝑦

     

= 4𝑥 + 8𝑦 =4 0 +8 5 = 0 + 40   = 40

!

= 16

Nilai  minimumnya  adalah  16  karena  ada  dua  titik  yang  memenuhi  maka   nilai  minimum  terletak  pada  garis  5𝑥 + 10𝑦 = 20  yang  memuat  kedua  titik    

 

c. Metode  Garis  Selidik     Fungsi  objektif  suatu  program  linier  berbentuk  𝑓 𝑥, 𝑦 = 𝑎𝑥 + 𝑏𝑦   ! merupakan  persamaan  garis  dengan  gradien  𝑚 = − !       𝑎 𝑚 = −   𝑏   Seperti  diketahui  penyelesaian  optimum  terletak  pada  titik  sudut  atau  titik   potong  antara  garis  pada  daerah  yang  diarsir   𝑥! , 𝑦!     ! Garis  selidik  adalah  garis  dengan  gradien  𝑚 = − !  yang  melalui  titik  sudut   daerah  yang  diarsir   𝑥! , 𝑦!     Persamaan  garis  selidik  adalah    𝑦 − 𝑦! = 𝑚 𝑥 − 𝑥!     𝑦 − 𝑦! = 𝑚 𝑥 − 𝑥! 𝑦 − 𝑦! = 𝑚𝑥 − 𝑚𝑥!     𝑦 = 𝑚𝑥 − 𝑚𝑥! + 𝑦! 𝑦 = 𝑚𝑥 + 𝑦! − 𝑚𝑥!   Kita  ketahui  juga  persamaan  garis  dapat  ditulis  sebagai  𝑦 = 𝑚𝑥 + 𝑐  dimana   𝑐  adalah  ordinat  titik  potong  garis  dengan  sumbu  Y  sehingga     𝑦 = 𝑚𝑥 + 𝑦! − 𝑚𝑥! 𝑚𝑥 + 𝑐 = 𝑚𝑥 + 𝑦! − 𝑚𝑥!     𝑐 = 𝑦! − 𝑚𝑥!   𝑐! = 𝑦! − 𝑚𝑥!     Nilai  maksimum  adalah  garis  selidik  yang  terletak  paling  atas     Nilai  minimum  adalah  garis  selidik  yang  terletak  paling  bawah     Nilai  maksimum  adalah  garis  selidik  dengan  𝑐!  paling  besar     Nilai  minimum  adalah  garis  selidik  dengan  𝑐!  paling  kecil      

 

Pada  contoh  soal  sebelumnya  daerah  yang  diarsir  adalah  himpunan   penyelesaian  dari  model  matamatika       5𝑥 + 10𝑦 ≥ 20 3𝑥 + 𝑦 ≥5     𝑥 ≥0 𝑦 ≥0   ! ! 𝑓!"#"!$!   𝑥, 𝑦 = 4𝑥 + 8𝑦    dimana  𝑚 = − ! = − !    

    Dari  grafik  terlihat  garis  selidik  paling  bawah  (minimum)  melaui  titik   dan   4,0  persamaannya  adalah     𝑦 − 𝑦! = 𝑚 𝑥 − 𝑥! 𝑦−0

! !

,

! !

!

= − ! 𝑥 − 4     !

𝑦 = −!𝑥 + 2   Titik  potongnya  dengan  sumbu  Y  adalah  2  terletak  paing  bawah  sehingga   titik  sudut  yang  dilalui  garis  ini  memberikan  nilai  fungsi  objektif  minimum     Dari  grafi  terlihat  dua  titik  sudut  dilalui  dengan  garis  selidik  yang  sama   ! ! sehingga  dikatakan  nilai  minimum  merupakan  ruas  garis  antara  titik   ! , !   dan   4,0     Hal  ini  terjadi  karena  gradien  garis  5𝑥 + 10𝑦 = 20  sama  dengan  gradien   ! fungsi  objektif  𝑚 = − !     Grafik  hanya  mempunyai  titik  minimum  dan  tidak  mempunyai  titik   maksimum  karena  daerah  yang  diarsir  terbuka  atau  kumpulan  titik  titik   daerah  yang  diarsir  jumlahnya  tak  berhingga     Jika  daerah  yang  diarsir  merupakan  daerah  terbuka  maka  program  linier   mempunyai  hanya  titik  maksimum  atau  titik  minimum  saja     Jika  daerah  yang  diarsir  tertutup  atau  berbentuk  poligon  maka  program   linier  mempunyai  titik  maksimum  dan  titik  minimum