Kamis, 10 April 2014

PROGRAM LINEAR


A. PROGRAM LINEAR
Pemrograman linear ialah teknik optimasi yang melibatkan variabel-variabel linear. Dalam model pemrograman linear dikenal dua macam fungsi, yaitu fungsi objektif (objective function) dan fungsi kendala (constraint function) yang linear.
  1. Sistem pertidaksamaan linear dau variabel
a)      Menentukan persamaan garis lurus
Persamaan garis lurus yang sangat berkaitan dengan program linear ini adalah   :
  • Garis lurus yang melalui dua titik






  • Garis lurus yang memotong sumbu X dititik (a,0) dan memotong sumbu Y di (0,b) mempunyai persamaan bx + ay = ab.
Contoh:
Tentukan persamaan garis yang melalui titik (2,2) dan (5,-2)
Jawab  :












Jadi, persamaan garis yang melalui titik (2,2) dan (5,-2) adalah 4x + 3y – 14 = 0
  • Melukis garis lurus yang diketahui persamaanya
Sebuah garis yang diketahui persamaannya dapat dilukiskan dalam sebuah system koordinat kartesius dengan terlebih dahulu menentukan 2 titik yang dilaluinya. Hal ini dapat dituliskan dalam bentuk tabel.
Misalkan : garis dengan persamaan : ax +by = c
Tabel         :
X
0
c
a
Y
c
b
0
Nampak bahwa garis dengan persamaan : ax + by = c adalah garis yang melalui titik



Sehingga dapat dituliskan sbb :
Contoh      :
Gambarlah garis dalam sebuah bidang koordinat kartesius!
2x + 3y = 6
Jawab        :
Garis dengan persamaan : 2x + 3y = 6
X
0
3
Y
2
0
Sehingga garis : 2x + 3y = 6 adalah garis yang melalui titik (0,2) dan (3,0)
b)      Persamaan linear dua peubah
Bentuk umum dari pertidaksamaan linear dua peubah adalah sbb:
-          ax + by < c
-          ax + by > c
-          ax + by  ≤ c
-          ax + by ≥ c
dari keempat bentuk tersebut yang sering digunakan dalam program linear adalah
-          ax + by  ≤ c
-          ax + by ≥ c
contoh pertidaksamaan     :
  • 2x + 3y  ≤ 6
  • x – y ≥ 4
  • 3x + 5y -15 < 0
  • ½ x – y > 4
  1. Menyelesaikan pertidaksamaan linear dua variabel
Untuk menyelesaikan pertidaksamaan linear dua peubah seperti diatas digunakan langkah – langkah sbb:
  1. Menggambar daris lurus dengan persamaan : ax + by = c
  2. Menentukan daerah yang memenuhi pertidaksamaan tersebut, dengan cara mengarsir daerah yang tidak memenuhi atau daerah yang memenuhi tatap bersih. Untuk dapat menentukan suatu daerah memenuhi atau tidak maka dapat diuji pada salah satu daerah yang di batasi oleh garis yang sudah di buat tadi.
Contoh      :
Tentukan dengan gambar, himpunan penyelesaian dari : 2x + 3y  ≤ 6
Jawab  :
Buat garis dengan persamaan 2x + 3y = 6
X
0
3
Y
2
0
Sehingga garis : 2x + 3y = 6 adalah garis yang melalui titik (0,2) dan (3,0)
Untuk menggujinya disubtitusikan salah satu titik misalnya (0,0) ke dalam pertidaksamaan : 2x + 3y  ≤ 6
Sehingga         : 2.0 + 3.0  ≤ 6
0 ≤ 6 (B)
Jadi, daerah yang memuat titik adalah dareah penyelesaian dari pertidaksamaan, kemudian diasir daerah yang bukan penyelesaian atau tidak memuat.
  1. Menentukan himpunan penyelesaian dari system pertidaksamaan linear dua variabel.
Contoh            :
Tentukan himpunan penyelesaian dari system pertidaksamaan sbb:












Buat garis 2x + y = 4
X
0
2
Y
4
0
Sehingga garis : 2x + y = 4 adalah garis yang melalui titik (0,4) dan (2,0)
Kemudian duji dengan menyubsibtusikan titik (0,0) ke dalam pertidaksamaan 2x + y  ≤ 4
(0,0) → 2.0 + 0  ≤ 4
0 ≤ 4 (B)
jadi daerah yang memuat adalah daerah penyelesaian sehingga yang diarsir yang bukan daerah penyelesaian.
Buat garis : x + y = 3
X
0
3
Y
3
0
Sehingga garis : x + y = 3 adalah garis yang melalui titik (0,3) dan (3,0)
Kemudian duji dengan menyubsibtusikan titik (0,0) ke dalam pertidaksamaan x + y  ≤ 3
(0,0) → 0 + 0  ≤ 3
0 ≤ 3 (B)
jadi daerah yang memuat adalah daerah penyelesaian sehingga yang diarsir yang bukan daerah penyelesaian.
Garis x = 0 adalah sumbu Y, daerah x ≥ 0 adalah daerah disebelah kanan sumbu Y atau untuk nilai x positif ( yang diarsir daerah kiri sumbu Y )
Garis y = 0 adalah sumbu X , daerah y ≥ 0 adalah daerah diatas sumbu X atau untuk nilai y positif ( yang diarsir daerah di bawah sumbu X)
Sehingga himpunan penyelesaian dari system pertidaksamaan diatasadalah daerah yang tidak diarsir ( bersih).

  1. MODEL MATEMATIKA PROGRAM LINEAR
    1. Pengertian
Program linear adalah suatu metode atau program yang dapat digunakan untuk memecahkan masalah optimasi. Dalam program linear, kendala dapat diterjemahkan dalam bentuk system pertidaksamaan linear. Sebelum menyelesaikan program linear terlebih dahulu  harus menerjemahkan tersebut dalam bahasa matematika yang disebut model matematika. Model matematika adalah suatu rumusan matematika, baik berupa persamaan, pertidaksamaan atau fungsi yang diperoleh dari hasil penafsiran atau terjemahan masalah dari program linear ke dalam bahasa matematika.
Contoh      :
Ami membeli 3 buku tulis dan 2 pensil di took suka.Ami membayar Rp. 4.000,00. Di toko yang sama gita membeli 4 buku tulis dan 1 pensil dan ia membayar Rp. 4.000,00. Jika harga 1 buku tulis dan satu pensil masing – masing x dan y maka buatlah model matematika dari persoalan diatas!.
Jawab        :
Misalkan    : x adalah harga 1 buah buku tulis
Y adalah harga 1 buah pensil
Berdasarkan informasi diatas maka diperoleh hubungan :
3x + 2y = 4000
4x + y = 4500
x, y ≥ 0 karena  harga buku tulis maupun pensil tidak mungkin negatif
x, y ∊ R karena harga haruslah bilangan real.
Jadi, model matematika dari persoalan diatas adalah       :
3x + 2y = 4000
4x + y = 4500
x, y ≥ 0                              x, y ∊ R
  1. Nilai optimum suatu bentuk objektif
Penyelesaian sistem pertidaksamaan terdapat dalm daerah himpunan penyelesaian. Diantara himpunan penyelsaian tersebut terdapat satu penyelesaian yang terbaik yang disebut penyelesaian optimum. Jadi, tujuan dari program linear adalah mencari penyelesaian optimum yang berupa nilai maksimum atau nilai minimum dari fungsi f. Fungsi f tersebut dinamakan fungsi sasaran atau fungsi tujuan atau fungsi objektif.
Fungsi tujuan dinyatakan dengan : f (x,y) = ax + by
Bentuk ax + by disebut bentuk objektif dimana a,b adalah koefisien – koefisien yang memengaruhi fungsi tujuan.
Contoh      :
Sebuah pabrik sepatu memproduksi 2 jenis sepatu. Dalam satu pabrik itu paling banyak memproduksi 100 pasang sepatu. Dari bagian penjualan diperoleh keterangan bahwa tiap hari terjual tidak lebih dari 80 sepatu A dan 60 sepatu B. pemilik pabrik itu ingin mendapatkan keuntungan yang sebesar – besarnya. Jika keuntungan tiap jenis sepatu A adalah Rp. 10.000,00 dan sepatu B Rp.15.000,00. Buatlah model matematika dan tentukan fungsi objektif dari persoalan diatas.
Jawab        :
Misal         :
Tiap hari sebanyak x pasang sepatu A dan y pasang sepatu B.
Model matematika dari persoalan di atas adalah  :
x + y ≤ 100            x,y ∊ C
x ≤ 80                    fungsi objektif : maksimalkan : f (x,y) = 10.000 x + 15.000 y
y ≤ 60
  1. SOLUSI PROGRAM LINEAR
Ada dua cara yang perlu diketahui dalam penyelesaian program linear.
  1. Dengan uji titik potok
Dengan metode ini nilai optimum dari bentuk objektif z = ax + by ditentuka dengan menghitung nilai – nilai z = ax + by pada tiap – tiap pojok (titik vertex) yang terdapat pada daerah himpunan penyelesaian pertidaksamaan linear dua peubah. Dari beberapa nilai yang kita peroleh kemudian dibandingkan. Nilai yang terbesar merupakan nilai maksimum sedangkan nilai yang terkecil merupakan nilai minimum dari z = ax + by.
Contoh      :
Tentukan nilai optimum dari x + 2y yang memenuhi system pertidaksamaan :
1 ≤ x ≤ 6
2 ≤ y ≤ 5
x,y ∊ B
jawab         :
Dari system pertidaksamaan         :  1 ≤ x ≤ 6
2 ≤ y ≤ 5 , dapat dibuat gambar sbb:
ada 4 titik pojok dari gambar tersebut yaitu : (1,2),(1,5),(6,2),(6,5)
diuji untuk masing – masing titik pojoknya          :
Titik
x+ 2y
Z
(1,2)
1+2.2
5
(1,5)
1+2.5
11
(6.2)
6+2.2
10
(6,5)
6+2.5
16
Jadi, nilai minimumnya = 5 untuk x = 1 dan y = 2
Nilai maksimumnya = 16 untuk x = 6 dan y = 5
  1. Dengan garis selidik
Cara yang lebih sederhana adalah menggunakan garis selidik ax + by = k. terdapat banyak sekali garis selidik dengan gradient yang sama yaitu : m =- a/b  sehingga garis – garis tersebut sejajar. Dari garis yang berada dalam daerah penyelesaian dipilih garis yang menghasilkan nilai optimum.
Garis selidik yang berada paling atas dari daerah himpunan penyelesaian menghasilkan nilai maksimum. Sedangkan garis selidik yang berada paling bawah dari daerah himpunan penyelesaian menghasilkan nilai minimum.
Contoh      :
Tentukan nilai maksimum : x + y dari daerah penyelessaian berikut!
Jawab        :
Buat garis x + y = k dengan k = 0,1,2,3…
Kemudian gambar garis – garis sejajar tersebut dalam daerah penyelesaian.
Yang teratas yang melalui daerah penyelesaian adalah letak dari nilai maksimumnya.
Nampak bahwa nilai maksimum terletak pada garis x + y = 10 yang melalui titik (3,7) dan (4,6).
Jadi, nilai maksimum x + y  dari daerah tersebut adalah 10.

sumber : http://mahasuryaa.wordpress.com/2012/01/08/program-linear/

Tidak ada komentar:

Posting Komentar