6. Program Linier

                                   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 : daerah yang diarsir merupakan daerah penyelesaian 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).

                               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     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)

Fungsi Linier Pada Poligonal Kita bermaksud mencari nilai (khususnya maksimum/minimum) suatufungsi Linier f (x, y) = px + qy  dimana (x,y)', memenuhi syarat-syarat sebagai berikut ax + by £ cdx + ey £ fpx + 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 + Sydengan 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) = -3f(B) = f(3,-1) = 2(3) + 5(-1) = 1f(C) = f (4, 0) = 2(4) + 5(0) = 8f(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     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 £  Titik Ekstrim A(0,23 1/3) ; B(15,0) ; (5,20)f(x,y) = 100x + 125yf(A) = 100(0) + 125(23) = 2875(dalam hal ini roti tidak pecahan)f(B) = 100(15) + 125(0) = 1500f(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 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.                               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.