PROGRAM LINEAR Dasar Matematis 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 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 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. 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) Ket :
1. daerah yang diarsir merupakan daerah penyelesaian 2.
atau menggunakan tanda anak panah (persetujuan) bila pertidaksamaan berbentuk 2x - 3y < -6 (tanpa =), maka garis 2x - 3y = -6 dibuat putus-putus, untuk menunjukkan bahwa titik titik pada garis bukan merupakan daerah penyelesaian.
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).
daerah yang memenuhi adalah daerah yang diarsir
Poligonal dan Titik Ekstrim
POLIGONAL DAN TITIK EKSTRIM 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 tentukan daerahnya. → Cari irisannya yang merupakan suatu poligonal. →Terakhir cari koordinat titik ekstrim poligonal tersebut.
masing- masing
- 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)
Fungsi Linier Pada Poligonal
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).
Model Matematika 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 maka persoalan menjadi :
y buah,
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. 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
Katun Sutera Wool
Model I
Model II
Tersedia
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 → (Catatan : Bentuk persyaratan ≥ )
x + 3y ≥ 9 (3)
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.
Garis Selidik 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 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 :
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.
