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.
- Sistem pertidaksamaan linear dau variabel
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.
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
Misalkan : garis dengan persamaan : ax +by = c
Tabel :
|
X
|
0
|
c
a
|
|
Y
|
c
b
|
0
|
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
|
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
- Menyelesaikan pertidaksamaan linear dua variabel
- Menggambar daris lurus dengan persamaan : ax + by = c
- 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.
Tentukan dengan gambar, himpunan penyelesaian dari : 2x + 3y ≤ 6
Jawab :
Buat garis dengan persamaan 2x + 3y = 6
|
X
|
0
|
3
|
|
Y
|
2
|
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.
- Menentukan himpunan penyelesaian dari system pertidaksamaan linear dua variabel.
Tentukan himpunan penyelesaian dari system pertidaksamaan sbb:
Buat garis 2x + y = 4
|
X
|
0
|
2
|
|
Y
|
4
|
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
|
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).
- MODEL MATEMATIKA PROGRAM LINEAR
- Pengertian
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
- Nilai optimum suatu bentuk 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
- SOLUSI PROGRAM LINEAR
- Dengan uji titik potok
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
|
Nilai maksimumnya = 16 untuk x = 6 dan y = 5
- Dengan garis selidik
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