Program Linier
Garis Selidik
Matematika Kelas 1 > Program Linier
Masalah Program linier adalah mengenai optimalisasi dengan keterbatasan tertentu. Keterbatasan dan optimalisasi ini harus dibentuk dahulu model matematikanya ;
yang secara garis besar dibagi 2 bagian :
- constraint ( Persyaratan )
- objective Function (Fungsi Tujuan / Sasaran)
Langkah
- Tentukan variabelnya (x=... ; y = ....)
- Buat model matematikanya dari : 1) Fungsi tujuan dan 2) Persyaratan
- Tentukan daerah yang memenuhi persyaratannya
- Tentukan titik esktrim daerah tersebut
- Substitusi koordinat titik ekstrim ke fungsi tujuan
- Bandingkan nilai yang didapat
- Jawaban disesuaikan dengan pertanyaan (maksimum/minimum)
contoh :
MASALAH MAKSIMUM
1. Seorang pedagang akan membuat kue A dan B. Kue A membutuhkan 150 gr tepung dan 50 gr mentega. Kue B membutuhkan 75 gr tepung dan 75 gr mentega. Tepung yang tersedia ada 2250 gr dan mentega yang tersedia ada 1750 gr. Jika kue A memberi keuntungan Rp 100,00 dan kue B Rp 125,00 tiap unitnya. Berapa keuntungan maksimum yang mungkin diperoleh pedagang itu ?
Tabel
Model pakaian I membutuhkan 2 m katun, 1 m sutera dan 1 m wool per unit. Model pakaian II membutuhkan 1 m
katun, 2 m sutera dan 3 m wool per unit.Keuntungan pakaian model I Rp 3.000,00 dan model pakaian II Rp 5.000,00 per unit.
Tentukan berapa banyak masing-masing pakaian harus dibuat agar didapat keuntungan yang sebesar-besarnya ?
Tabel
Misalkan : Banyaknya model I yang dibuat = x
model II yang dibuat = y
Maksimumkan f (x,y) = 3000x + 5000y
ds : 2x + y £ 16 (1)
x + 2y £ 11 (2)
x + 3y £ 15 (3)
x;y ³ 0
Titik Ekstrim
B(7,2) ® TP antara garis (1) dengan (2)
C(3,4) ® TP antara garis (2) dengan (3)
D(0,5) ® TP antara garis (3) dengan sb-y
f (x,y) = 3000x + 5000y
f(A) = f(8,0) = 3000(8) + 5000(0) = 24.000
f (B) = f(7,2) = 3000(7) + 5000(2) = 31.000
f(C) = f(3,4) = 3000(3) + 5000(4) = 29.000
f(D) = f(0,5) = 3000(0) + 5000(5) = 25.000
Jadi keuntungan maksimum adalah Rp 31.000; yaitu dengan membuat 7 buah model pakaian I dan 2 buah model pakaian II.
MASALAH MINIMUM
3)Dalam satu minggu tiap orang membutuhkan paling sedikit 16 unit protein , 24 unit karbohidrat dan 18 unit lemak Makanan A mengandung protein, karbohidrat dan lemak berturut-turut 4, 12 dan 2 unit setiap kg. Makanan B mengandung protein, karbohidrat dan lemak berturut turut 2 , 2 dan 6 unit setiap kg. Berapa kg masing- masing makanan harus dibeli setiap minggunya, agar kebutuhan terpenuhi, tetapi dengan biaya semurah-murahnya, bila 1 kg makanan A harganya Rp 1.700,00 dan 1 kg makanan B harganya Rp 800,00 ?
Tabel
Misalkan : Banyaknya makanan A yang dibeli adalah x kg
Banyaknya makanan B yang dibeli adalah y kg
Minimumkan f (xy) = 1700x + 800y
ds : 4x + 2y ³ 16 ® 2x + y ³ 8 (1)
12x + 2y ³ 24 ® 6x + y ³ 12 (2
2x + 6y ³ 18 ® x + 3y ³ 9 (3)
(Catatan : Bentuk persyaratan ³ )
Titik Ekstrim
B (1, 6) adalah titik potong antara garis (1) dan garis (2).
C (3, 2) adalah titik potong antara garis (1) dan garis (3).
D (9, 0) adalah titik potong antara garis (3) dan sumbu y.
f (x,y) = 1700x + 800y
f(A) = f(0,12) = 1700(0) + 800(12) = 9600
f(B) = f(1, 6) = 1700 (1) + 800( 6 ) = 6500
f(C) = f(3, 2) = 1700(3) + 800( 2 ) = 6700
f(D) = f(9, 0) = 1700(9) + 800( 0 ) = 15300
Jadi biaya minimum adalah Rp 6.500; yaitu dengan membeli 1 kg makanan A dan 6 kg makanan B.
Kita bermaksud mencari nilai (khususnya maksimum/minimum) suatu fungsi Linier f (x, y) = px + qy
dimana (x,y)', memenuhi syarat-syarat sebagai berikut
ax + by £ c
dx + ey £ f
px + qy £ r
Hal di atas sama saja dengan mencari nilai maksimum/minimum suatu fungsi linier suatu poligonal.
DALIL
Jika f adalah suatu fungsi linier yang didefinisikan di atas suatu poligonal terbatas, maka nilai maksimum / minimumnya dicapai pada titik ekstrimnya (atau di sekitar titik ekstrimnya).
Contoh :
Carilah nilai maksimum dan minimum dari f(x,y) = 2x + Sy
dengan syarat : x + 2y £ 4
x- y£ 4
x ³ 1
y ³ -1
Langkah :
® Buatlah poligonalnya dan tentukan titik ekstrimnya.
Sesuai dengan contoh sebelumnya titik ekstrimnya adalah
A(1,-1) ; B(3,-1) ; C(4,0) ; D(1, 3/2 )
®Hitung nilai f(x,y) = 2x + 5y pada masing-masing titik ekstrimnya
f(A) = f(1,-1) = 2(1) + 5(-1) = -3
f(B) = f(3,-1) = 2(3) + 5(-1) = 1
f(C) = f (4, 0) = 2(4) + 5(0) = 8
f(D) = f (1, ; ) = 2(1) + 5( 3/2 ) = 9 1/2
Maka f(x,y) = 2x + Sy dengan batasan di atas mempunyai
- Nilai maksimum = 9 1/2 yang dicapai pada titik D (1, 3/2).
- Nilai minimum = -3 yang dicapai pada titik A (1,-1).
Poligonal dan Titik Ekstrim
Matematika Kelas 1 > Program Linier
Irisan dari sejumlah berhingga penyelesaian pertidaksamaan, membentuk suatu Poligonal.
Titik P disebut Titik Ekstrim dari poligonal, jika P adalah titik potong garis garis yang membatasi poligonal tersebut.
Contoh :
Gambarkan TK x + 2y £ 4 (1)
x - y £ 4 (2)
x ³ 1 (3)
y ³ -1 (4)
Langkah:
® Gambarkan terlebih dahulu keempat garis batasnya dan masing- masing tentukan daerahnya.
® Cari irisannya yang merupakan suatu poligonal.
®Terakhir cari koordinat titik ekstrim poligonal tersebut.
- A adalah titik potong antara garis x = 1 dan y = -1
- B adalah titik potong antara garis y = -1 dan garis x-y =4
- C adalah titik potong antara garis x + 2y = 4 dan garis x-y=4
C (4, 0)
- D adalah titik potong antara x = 1 dan x + 2y = 4.
D (1, 3/2i )
Terbentuk poligonal ABCD dengan 4 titik ekstrimnya, yaitu :
A(1,-1) ; B(3,-1) ; C(4 , 0) ; D(1,3/2)
Dasar Matematis
Matematika Kelas 1 >Program Linier
Matematika Kelas 1 > Program Linier
Untuk menentukan nilai maksimum / minimum dari suatu fungsi dengan syarat tertentu dapat juga dicari tanpa menguji nilai fungsi dari titik-titik ekstrimnya.
Cara lain ini adalah dengan menggunakan Garis Selidik. Garis Selidik yang dimaksud adalah garis yang merupakan fungsi objektifnya.
Andaikan fungsi objektifnya f(x,y) = ax + by
Cara lain ini adalah dengan menggunakan Garis Selidik. Garis Selidik yang dimaksud adalah garis yang merupakan fungsi objektifnya.
Andaikan fungsi objektifnya f(x,y) = ax + by
Garis Selidik ax + by = k
Untuk suatu (x,y) tertentu, k adalah nilai dari fungsi objektif tersebut.
Kemungkinan-kemungkinan
1) k=0 ® ax +by=0
Garis melalui titik pangkal (0,0) memberikan nilai minimum = 0.
2)Garis tersebut digeser sejajar ke kanan (masalah maksimum) / ke kiri (masalah minimum) sehingga menyentuh titik ekstrim terakhir dari poligon yang terbentuk. Pada titik itulah, nilai maksimum / minimum dari fungsi didapat.
contoh :
Kemungkinan-kemungkinan
1) k=0 ® ax +by=0
Garis melalui titik pangkal (0,0) memberikan nilai minimum = 0.
2)Garis tersebut digeser sejajar ke kanan (masalah maksimum) / ke kiri (masalah minimum) sehingga menyentuh titik ekstrim terakhir dari poligon yang terbentuk. Pada titik itulah, nilai maksimum / minimum dari fungsi didapat.
contoh :
Maksimumkan f(x,y) = x + 2y
ds : x + 3y £ 9...(1)
2x + y £ 8...(2)
x ; y ³ 0
Garis putus-putus menunjukkan garis selidik x + 2y = 0 yang bergeser ke kanan dan terakhir mencapai titik ekstrim E.
Maksimum dicapai pada titik E, yaitu f(E) = f(3,2) = 1(3) + 2(2) = 7
Keterangan :
Cara ini baik dilakukan, bila poligonal yang terbentuk banyak terdapat titik ekstrimnya. Tetapi diperlukan ketelitian pada saat menggeser garis fungsi tujuan, terutama jika terdapat titik-titik ekstrim yang saling berdekatan.
ds : x + 3y £ 9...(1)
2x + y £ 8...(2)
x ; y ³ 0
Garis putus-putus menunjukkan garis selidik x + 2y = 0 yang bergeser ke kanan dan terakhir mencapai titik ekstrim E.
Maksimum dicapai pada titik E, yaitu f(E) = f(3,2) = 1(3) + 2(2) = 7
Keterangan :
Cara ini baik dilakukan, bila poligonal yang terbentuk banyak terdapat titik ekstrimnya. Tetapi diperlukan ketelitian pada saat menggeser garis fungsi tujuan, terutama jika terdapat titik-titik ekstrim yang saling berdekatan.
Model Matematika Matematika Kelas 1 > Program Linier |
Masalah Program linier adalah mengenai optimalisasi dengan keterbatasan tertentu. Keterbatasan dan optimalisasi ini harus dibentuk dahulu model matematikanya ;
yang secara garis besar dibagi 2 bagian :
- constraint ( Persyaratan )
- objective Function (Fungsi Tujuan / Sasaran)
Langkah
- Tentukan variabelnya (x=... ; y = ....)
- Buat model matematikanya dari : 1) Fungsi tujuan dan 2) Persyaratan
- Tentukan daerah yang memenuhi persyaratannya
- Tentukan titik esktrim daerah tersebut
- Substitusi koordinat titik ekstrim ke fungsi tujuan
- Bandingkan nilai yang didapat
- Jawaban disesuaikan dengan pertanyaan (maksimum/minimum)
contoh :
MASALAH MAKSIMUM
1. Seorang pedagang akan membuat kue A dan B. Kue A membutuhkan 150 gr tepung dan 50 gr mentega. Kue B membutuhkan 75 gr tepung dan 75 gr mentega. Tepung yang tersedia ada 2250 gr dan mentega yang tersedia ada 1750 gr. Jika kue A memberi keuntungan Rp 100,00 dan kue B Rp 125,00 tiap unitnya. Berapa keuntungan maksimum yang mungkin diperoleh pedagang itu ?
Tabel
Kue A | Kue B | Tersedia | |
Tepung Mentega | 150 50 | 75 75 | 2250 1750 |
KEUNTUNGAN | 100 | 125 |
Misalkan banyaknya kue A yang dibuat x buah dan kue B yang dibuat y buah, maka persoalan menjadi :
Maksimumkan :
f(x,y) = 100x + 125y (fungsi objektif/keuntungan)
dengan syarat (ds):
150x + 75y £ 2250 ® 2x + y £ 30 ...(1)
50 x + 75y £ 1750 ® 2x + 3y £ 70 ...(2)
x,y ³ 0
catatan : bentuk persyaratan £
Maksimumkan :
f(x,y) = 100x + 125y (fungsi objektif/keuntungan)
dengan syarat (ds):
150x + 75y £ 2250 ® 2x + y £ 30 ...(1)
50 x + 75y £ 1750 ® 2x + 3y £ 70 ...(2)
x,y ³ 0
catatan : bentuk persyaratan £
Titik Ekstrim
A(0,23 1/3) ; B(15,0) ; (5,20)
f(x,y) = 100x + 125y
f(A) = 100(0) + 125(23) = 2875
(dalam hal ini roti tidak pecahan)
f(B) = 100(15) + 125(0) = 1500
f(C) = 100(5) + 125(20) = 3000
Jadi keuntungan maksimum pedagang itu adalah Rp 3.000,00 ; yaitu dengan membuat 5 unit kue A dan 20 unit kue B.
2. Seorang penjahit pakaian mernpunyai persediaan barang katun 16 m, sutera 11 m dan wool 15 m.A(0,23 1/3) ; B(15,0) ; (5,20)
f(x,y) = 100x + 125y
f(A) = 100(0) + 125(23) = 2875
(dalam hal ini roti tidak pecahan)
f(B) = 100(15) + 125(0) = 1500
f(C) = 100(5) + 125(20) = 3000
Jadi keuntungan maksimum pedagang itu adalah Rp 3.000,00 ; yaitu dengan membuat 5 unit kue A dan 20 unit kue B.
Model pakaian I membutuhkan 2 m katun, 1 m sutera dan 1 m wool per unit. Model pakaian II membutuhkan 1 m
katun, 2 m sutera dan 3 m wool per unit.Keuntungan pakaian model I Rp 3.000,00 dan model pakaian II Rp 5.000,00 per unit.
Tentukan berapa banyak masing-masing pakaian harus dibuat agar didapat keuntungan yang sebesar-besarnya ?
Tabel
Model I | Model II | Tersedia | |
Katun Sutera Wool | 2 1 1 | 1 2 3 | 16 11 15 |
KEUNTUNGAN | 3000 | 5000 |
Misalkan : Banyaknya model I yang dibuat = x
model II yang dibuat = y
Maksimumkan f (x,y) = 3000x + 5000y
ds : 2x + y £ 16 (1)
x + 2y £ 11 (2)
x + 3y £ 15 (3)
x;y ³ 0
Titik Ekstrim
A(8,0) ® TP antara garis (1) dengan sb-x
B(7,2) ® TP antara garis (1) dengan (2)
C(3,4) ® TP antara garis (2) dengan (3)
D(0,5) ® TP antara garis (3) dengan sb-y
f (x,y) = 3000x + 5000y
f(A) = f(8,0) = 3000(8) + 5000(0) = 24.000
f (B) = f(7,2) = 3000(7) + 5000(2) = 31.000
f(C) = f(3,4) = 3000(3) + 5000(4) = 29.000
f(D) = f(0,5) = 3000(0) + 5000(5) = 25.000
Jadi keuntungan maksimum adalah Rp 31.000; yaitu dengan membuat 7 buah model pakaian I dan 2 buah model pakaian II.
MASALAH MINIMUM
3)Dalam satu minggu tiap orang membutuhkan paling sedikit 16 unit protein , 24 unit karbohidrat dan 18 unit lemak Makanan A mengandung protein, karbohidrat dan lemak berturut-turut 4, 12 dan 2 unit setiap kg. Makanan B mengandung protein, karbohidrat dan lemak berturut turut 2 , 2 dan 6 unit setiap kg. Berapa kg masing- masing makanan harus dibeli setiap minggunya, agar kebutuhan terpenuhi, tetapi dengan biaya semurah-murahnya, bila 1 kg makanan A harganya Rp 1.700,00 dan 1 kg makanan B harganya Rp 800,00 ?
Tabel
A | B | Kebutuhan | |
Protein Karbohidrat Lemak | 4 12 2 | 2 2 6 | 16 24 15 |
HARGA | 1700 | 800 |
Misalkan : Banyaknya makanan A yang dibeli adalah x kg
Banyaknya makanan B yang dibeli adalah y kg
Minimumkan f (xy) = 1700x + 800y
ds : 4x + 2y ³ 16 ® 2x + y ³ 8 (1)
12x + 2y ³ 24 ® 6x + y ³ 12 (2
2x + 6y ³ 18 ® x + 3y ³ 9 (3)
(Catatan : Bentuk persyaratan ³ )
Titik Ekstrim
A (0,12) adalah titik potong antara garis (2) dan sumbu y.
B (1, 6) adalah titik potong antara garis (1) dan garis (2).
C (3, 2) adalah titik potong antara garis (1) dan garis (3).
D (9, 0) adalah titik potong antara garis (3) dan sumbu y.
f (x,y) = 1700x + 800y
f(A) = f(0,12) = 1700(0) + 800(12) = 9600
f(B) = f(1, 6) = 1700 (1) + 800( 6 ) = 6500
f(C) = f(3, 2) = 1700(3) + 800( 2 ) = 6700
f(D) = f(9, 0) = 1700(9) + 800( 0 ) = 15300
Jadi biaya minimum adalah Rp 6.500; yaitu dengan membeli 1 kg makanan A dan 6 kg makanan B.
Fungsi Linier Pada Poligonal Matematika Kelas 1 > Program Linier |
Kita bermaksud mencari nilai (khususnya maksimum/minimum) suatu fungsi Linier f (x, y) = px + qy
dimana (x,y)', memenuhi syarat-syarat sebagai berikut
ax + by £ c
dx + ey £ f
px + qy £ r
Hal di atas sama saja dengan mencari nilai maksimum/minimum suatu fungsi linier suatu poligonal.
DALIL
Jika f adalah suatu fungsi linier yang didefinisikan di atas suatu poligonal terbatas, maka nilai maksimum / minimumnya dicapai pada titik ekstrimnya (atau di sekitar titik ekstrimnya).
Contoh :
Carilah nilai maksimum dan minimum dari f(x,y) = 2x + Sy
dengan syarat : x + 2y £ 4
x- y£ 4
x ³ 1
y ³ -1
Langkah :
® Buatlah poligonalnya dan tentukan titik ekstrimnya.
Sesuai dengan contoh sebelumnya titik ekstrimnya adalah
A(1,-1) ; B(3,-1) ; C(4,0) ; D(1, 3/2 )
®Hitung nilai f(x,y) = 2x + 5y pada masing-masing titik ekstrimnya
f(A) = f(1,-1) = 2(1) + 5(-1) = -3
f(B) = f(3,-1) = 2(3) + 5(-1) = 1
f(C) = f (4, 0) = 2(4) + 5(0) = 8
f(D) = f (1, ; ) = 2(1) + 5( 3/2 ) = 9 1/2
Maka f(x,y) = 2x + Sy dengan batasan di atas mempunyai
- Nilai maksimum = 9 1/2 yang dicapai pada titik D (1, 3/2).
- Nilai minimum = -3 yang dicapai pada titik A (1,-1).
Poligonal dan Titik Ekstrim
Matematika Kelas 1 > Program Linier
Irisan dari sejumlah berhingga penyelesaian pertidaksamaan, membentuk suatu Poligonal.
Titik P disebut Titik Ekstrim dari poligonal, jika P adalah titik potong garis garis yang membatasi poligonal tersebut.
Contoh :
Gambarkan TK x + 2y £ 4 (1)
x - y £ 4 (2)
x ³ 1 (3)
y ³ -1 (4)
Langkah:
® Gambarkan terlebih dahulu keempat garis batasnya dan masing- masing tentukan daerahnya.
® Cari irisannya yang merupakan suatu poligonal.
®Terakhir cari koordinat titik ekstrim poligonal tersebut.
- A adalah titik potong antara garis x = 1 dan y = -1
- B adalah titik potong antara garis y = -1 dan garis x-y =4
- C adalah titik potong antara garis x + 2y = 4 dan garis x-y=4
C (4, 0)
- D adalah titik potong antara x = 1 dan x + 2y = 4.
D (1, 3/2i )
Terbentuk poligonal ABCD dengan 4 titik ekstrimnya, yaitu :
A(1,-1) ; B(3,-1) ; C(4 , 0) ; D(1,3/2)
Dasar Matematis
Matematika Kelas 1 >Program Linier
PROGRAM LINIER adalah suatu teknik optimalisasi dimana variabel-variabelnya linier. Metode ini dipakai pada saat kita dihadapkan pada beberapa pilihan dengan batasan-batasan tertentu, sedangkan di lain pihak kita menghendaki keputusan yang optimum (maksimum/minimum).
DASAR MATEMATIS
DASAR MATEMATIS
Persamaan linier ax + by = c (x,y variabel ; a,b,c konstanta) membagi bidang atas 3 bagian :
1. Titik-titik yang memenuhi persamaan ax + by = c
2. Titik-titik yang memenuhi pertidaksamaan ax + by < c
3. Titik-titik yang memenuhi pertidaksamaan ax + by > c
1. Titik-titik yang memenuhi persamaan ax + by = c
2. Titik-titik yang memenuhi pertidaksamaan ax + by < c
3. Titik-titik yang memenuhi pertidaksamaan ax + by > c
Ket :
® grafik ax + by = c merupakan garis lurus yang berfungsi sebagai garis batas
® Titik-titik yang memenuhi ax + by > c atau ax + by < c merupakan suatu daerah.
® grafik ax + by = c merupakan garis lurus yang berfungsi sebagai garis batas
® Titik-titik yang memenuhi ax + by > c atau ax + by < c merupakan suatu daerah.
contoh :
1. Gambarkan tempat kedudukan (daerah) 2x-3y £ -6
Langkah :
-gambarkan terlebih dahulu garis 2x- 3y = -6
-titik potong dengan sumbu x ® y = 0 dan x = -3 (-3,0)
-titik potong dengan sumbu y ® x =0 dan y = 2 (0,2)
Hubungkan kedua titik potong tersebut
® pilih sembarang titik yang tidak terletak pada garis, misalkan titik (0,0)
Kemudian uji apakah titik tersebut memenuhi syarat
2x - 3y = 2(0) - 3(0) = 0 < -6 (salah)
Ternyata tidak memenuhi syarat . Berarti titik -titik yang memenuhi syarat (yang dimaksud) adalah di pihak lain dari titik (0,0) berada (seperti terlihat pada gambar berikut)
1. Gambarkan tempat kedudukan (daerah) 2x-3y £ -6
Langkah :
-gambarkan terlebih dahulu garis 2x- 3y = -6
-titik potong dengan sumbu x ® y = 0 dan x = -3 (-3,0)
-titik potong dengan sumbu y ® x =0 dan y = 2 (0,2)
Hubungkan kedua titik potong tersebut
® pilih sembarang titik yang tidak terletak pada garis, misalkan titik (0,0)
Kemudian uji apakah titik tersebut memenuhi syarat
2x - 3y = 2(0) - 3(0) = 0 < -6 (salah)
Ternyata tidak memenuhi syarat . Berarti titik -titik yang memenuhi syarat (yang dimaksud) adalah di pihak lain dari titik (0,0) berada (seperti terlihat pada gambar berikut)
Ket :
|
2. Gambarkan daerah yang memenuhi :
x + 3y £ 12
3x + y £ 12
x ³ 0 ; y ³ 0
Langkah :
® gambarkan garis x + 3y = 12 dan tentukan daerah x + 3y £ 12...(1)
gambarkan garis 3x + y = 12 dan tentukan daerah 3x + y £12...(2)
syarat x ³ 0 ; y ³ 0 menunjukkan bahwa daerah yang dimaksud terletak di kuadran I (x dan y positif)
® penyelesaiannya adalah daerah yang memenuhi keempat syarat di atas (merupakan irisan dari penyelesaian persyaratan diatas).
x + 3y £ 12
3x + y £ 12
x ³ 0 ; y ³ 0
Langkah :
® gambarkan garis x + 3y = 12 dan tentukan daerah x + 3y £ 12...(1)
gambarkan garis 3x + y = 12 dan tentukan daerah 3x + y £12...(2)
syarat x ³ 0 ; y ³ 0 menunjukkan bahwa daerah yang dimaksud terletak di kuadran I (x dan y positif)
® penyelesaiannya adalah daerah yang memenuhi keempat syarat di atas (merupakan irisan dari penyelesaian persyaratan diatas).
daerah yang memenuhi adalah daerah yang diarsir |
0 comments:
Posting Komentar