makalah program linear matematika(garis selidik)

BAB I

PENDAHULUAN

LATAR BELAKANG

Di dalam matematika mulai dari SD, SMP, SMA, dan Perguruan Tinggi terdapat berbagai cabang pembahasan yang ada yang dipelajari siswa dalam kegiatan belajar mengajar di sekolah maupun perguruan tinggi. Cabang pelajaran yang ada antara lain: logika matematika, aljabar, ruang dimensi tiga, trigonometri, kalkulus, peluang, dan statistika, Seorang siswa harus memahami setiap pelajaran yang diajarkan oleh gurunya agar ia tidak ketinggalan pelajaran dan bisa mengerti maksud atau kegunaan dari pelajaran tersebut. Selain itu, ia juga harus bisa mengerjakan soal-soal yang berkaitan dengan pelajaran tersebut supaya mendapat nilai yang bagus. Salah satu bab dalam matematika adalah program linear. Dalam program linear terdapat persamaan suatu bilangan karena masih masuk dalam aljabar. Dan mempunyai kegunaan yang penting terutama berhubungan dengan kehidupan sehari-hari. Pelajaran ini membahas beberapa hal atau bagian yang dibatasi oleh syarat-syarat tertentu. Syarat-syarat itu adalah susunan pertidaksaman linear dan tentu di dalamnya masih ada hal-hal lainnya yang saling berkaitan(berkaitan erat).

BAB II

PEMBAHASAN

A.    PROGRAM LINIER

Program linear yaitu suatu metode untuk mencari nilai maksimum atau nilai minimum dari bentuk linear pada daerah yang dibatasi grafik -grafik fungsi linear.

Himpunan penyelesaian dari sistem pertidaksamaan linear dua peubah merupakan suatu himpunan titik-titik (pasangan berurut (x,y)) dalam bidang cartesius yang memenuhi semua pertidaksamaan linear dalam sistem tersebut. Sehingga daerah himpunan penyelesaiannya merupakan irisan himpunan-himpunan penyelesaian dari pertidaksamaan dalam sistem pertidaksamaan linear dua peubah itu. Untuk  lebih mudah dalam memahami daerah penyelesaian dari sistem pertidak-samaan linear dua peubah, perhatikan contoh berikut.

Contoh:
Tentukan daerah  penyelesaian dari sistem pertidaksamaan linear berikut!
3x + 5y  15
x  0
y  0

Penyelesaian:
Gambar garis 3x + 5y =15, x = 0, dan y =0
Untuk 3x + 5y  15
Pilih titik (0,0), kemudian substitusikan ke pertidaksamaan sehingga diperoleh:

3 × 0 + 5× 0  15

0  15 (benar), artinya dipenuhi

Sehingga daerah penyelesaiannya adalah daerah yang memuat titik (0,0)

Untuk x  0, pilih titik (1,1) kemudian disubstitusikan ke pertidaksamaan sehingga diperoleh:
1  0 (benar), artinya dipenuhi. Sehingga daerah penyelesaiannya adalah daerah yang memuat titik (1,1)
Untuk y  0, pilih titik (1,1) kemudian substitusikan ke pertidaksamaan sehingga diperoleh:
1  0 (benar), artinya dipenuhi.
Sehingga himpunan penyelesaiannya adalah daerah yang memuat titik (1,1).

B.     PERTIDAKSAMAAN LINIER DENGAN DUA VARIABEL

A.         Sistem Pertidaksamaan Linear Dua Variabel

Suatu garis dalam bidang koordinat dapat dinyatakan dengan persamaan yang berbentuk:

Persamaan semacam ini dinamakan persamaan linear dalam variabel x dan y (dua variabel).

 Secara umum, dapat didefinisikan sebagai persamaan linear dengan n variabel x1, x2, . . . xn

dengan a1, a2, . . ., an, b adalah konstanta-konstanta real
Jika melibatkan lebih dari satu persamaan, maka disebut dengan sistem persamaan linear.

Untuk saat ini, pembahasan dibatasi menjadi dua variabel saja. Untuk pertidaksamaan linear, tanda “ = ” diganti dengan “ ≤ ”, “ < ”, “ ≥ ”, “ > ”. Sebagai contoh, untuk pertidaksamaan linear dua variabel dijelaskan sebagai berikut.

Garis x + y = 2 membagi bidang koordinat menjadi dua daerah, yaitu daerah x + y < -2 dan daerah x + y > -2.

Sekarang, substitusi titik sembarang, misalnya titik O(0, 0) ke persamaan garis tersebut. Didapat, 0 + 0 = 0 > -2. Ini berarti, titik O(0, 0) berada pada daerah x + y > -2.Daerah x + y > -2 ini diarsir

Daerah yang diarsir berupa daerah segitiga. Tampak bahwa daerah ini merupakan himpunan penyelesaian sistem pertidaksamaan linear x + y ≥ -2, x ≤ 0, dan y ≤ 0.
Untuk selanjutnya, himpunan penyelesaian sistem pertidaksamaan linear ini disebut daerah penyelesaian.

Program Linear: Menggambar Daerah Penyelesaian Sistem Pertidaksamaan Linear Dua Variabel

Sistem pertidaksamaan linear dua variabel berupa beberapa pertidaksamaan linear yang terdiri dari 2 variabel, biasanya x atau y (walaupun jenis variabel lainnya tetap memungkinkan). Pertidaksamaan linear dua variabel memiliki bentuk umum seperti berikut:

ax + by < c, ax + by > c, ax + by ≤ c, atau ax + by ≥ c

Sebelum menggambar daerah penyelesaian sistem pertidaksamaan linear dua variabel, sebaiknya kita tahu terlebih dahulu mengenai himpunan penyelesaian.

 Himpunan penyelesaian merupakan himpunan pengganti nilai variabel sedemikian sehingga menyebabkan sistem pertidaksamaan menjadi pernyataan yang benar.

Daerah penyelesaian yang akan kita gambar merupakan daerah dari himpunan penyelesaian tersebut. Daerah ini berisi himpunan pasangan berurutan (x, y) yang menjadi anggota dari himpunan penyelesaian.

Untuk menggambar daerah penyelesaian sistem pertidaksamaan linear dua variabel, perhatikan contoh soal berikut.

Contoh Soal

Gambarlah daerah penyelesaian dari sistem pertidaksamaan linear berikut untuk x, y anggota bilangan real.

–x + 8y ≤ 80
2x – 4y ≤ 5
2x + y ≥ 12
2x – y ≥ 4
x ≥ 0, y ≥ 0

Pembahasan Contoh Soal

Untuk menggambar daerah penyelesaian dari sitem pertidaksamaan yang dimaksud, lakukan langkah-langkah berikut:

Langkah pertama. Ubahlah pertidaksamaan-pertidaksamaan yang dimaksud menjadi persamaan linear, kemudian gambarkan persamaan linear tersebut pada bidang koordinat. Grafik dari persamaan linear berupa garis lurus. Untuk itu, cari dua titik yang dilewati oleh garis tersebut, kemudian hubungkan kedua titik tersebut menjadi suatu garis lurus. Dua titik ini biasanya dipilih titik pada sumbu-x dan sumbu-y, akan tetapi apabila kurang memungkinkan, pilihlah titik-titik lain.

Sehingga garis –x + 8y = 80 melalui titik-titik (0, 10) dan (16, 12). Dengan cara yang sama, dapat dicari 2 titik yang dilalui persamaan garis lainnya.

Sehingga, garis-garis dari –x + 4y = 80, 2x – 4y = 5, 2x + y = 12, dan 2x – y = 4 dapat digambarkan seperti berikut

Langkah kedua. Arsirlah daerah dari masing-masing pertidaksamaan. Untuk menentukan daerah pertidaksamaan, pilihlah salah satu titik yang terdapat di kanan atau di kiri, atas atau bawah dari garis. Apabila koordinat titik tersebut disubstitusikan ke dalam pertidaksamaan dan menghasilkan pernyataan yang benar, maka daerah titik tersebut merupakan daerah penyelesaian pertidaksamaan tersebut. Arsirlah daerah penyelesaian tersebut.

 Sebaliknya, apabila koordinat titik tersebut disubstitusikan ke dalam pertidaksamaan dan menghasilkan pernyataan yang salah, maka daerah titik tersebut bukan merupakan daerah penyelesaian pertidaksamaan tersebut. Arsirlah daerah yang berseberangan terhadap titik tersebut. Misalkan kita akan menemukan daerah penyelesaian dari pertidaksamaan –x + 8y ≤ 80. Misalkan kita pilih titik (0, 12) yang terletak di atas garis sebagai titik uji. Kita substitusikan ke dalam pertidaksamaan sebagai berikut.

Dengan mensubstitusikan titik (0, 12) ke pertidaksamaan –x + 8y ≤ 80 menghasilkan pernyataan yang salah, sehingga daerah yang memuat titik (0, 12) bukan penyelesaian dari pertidaksamaan tersebut. Sehingga daerah yang berlawanan dengan daerah tersebut, yaitu daerah bawah, yang kita arsir.

Dengan cara yang sama, kita cari daerah penyelesaian dari pertidaksamaan-pertidaksamaan lainnya. Setelah itu kita gambarkan daerahnya seperti pada gambar berikut.

Langkah ketiga. Arsirlah daerah himpunan penyelesaian dari sistem pertidaksamaan yang dimaksud. Himpunan penyelesaian dari sistem pertidaksamaan merupakan irisan dari himpunan penyelesaian dari masing-masing pertidaksamaan.

 Atau secara visual, daerah penyelesaian dari sistem pertidaksamaan merupakan daerah yang terkena arsiran dari semua daerah penyelesaian.

 Sehingga himpunan penyelesaian dari pertidaksamaan

 –x + 8y ≤ 80, 2x – 4y ≤ 5, 2x + y ≥ 12, 2x – y ≥ 4, x ≥ 0, dan

y ≥ 0 dapat digambarkan sebagai berikut.

B.          Model Matematika

Sistem pertidaksamaan linear yang telah dijelaskan sebelumnya dapat diterapkan pada permasalahan sehari-hari dengan memodelkan permasalahan tersebut ke dalam model matematika.

Sebagai ilustrasi perhatikan contoh berikut.

PT. Samba Lababan memproduksi ban motor dan ban sepeda.

Proses pembuatan ban motor melalui tiga mesin, yaitu 2 menit pada mesin I, 8 menit pada mesin II, dan
10 menit pada mesin III.

Adapun ban sepeda diprosesnya melalui dua mesin, yaitu 5 menit pada mesin I dan 4 menit pada mesin II.

Tiap mesin ini dapat dioperasikan 800 menit per hari.

Untuk memperoleh keuntungan maksimum, rencananya perusahaan ini akan mengambil keuntungan Rp40.000,00 dari setiap penjualan ban motor dan Rp30.000,00 dari setiap penjualan ban sepeda.

Berdasarkan keuntungan yang ingin dicapai ini, maka pihak perusahaan merencanakan banyak ban motor dan banyak ban sepeda yang akan diproduksinya dengan merumuskan berbagai kendala sebagai berikut.

Perusahaan tersebut memisalkan banyak ban motor yang diproduksi sebagai x dan banyak ban sepeda yang diproduksi sebagai y, dengan x dan y bilangan asli.

 Dengan menggunakan variabel x dan y tersebut, perusahaan itu membuat rumusan kendala-kendala sebagai berikut :

>> Model Matematikanya:

Pada mesin I : 2x + 5y ≤ 800 …. Persamaan 1
Pada mesin II : 8x + 4y ≤ 800 .… Persamaan 2
Pada mesin III : 10x ≤ 800 .… Persamaan 3
x, y bilangan asli : x ≤ 0, y ≤ 0 .… Persamaan 4

Fungsi tujuan (objektif) yang digunakan untuk memaksimumkan keuntungan adalah f(x, y) = 40.000x + 30.000y. Dalam merumuskan masalah tersebut, PT. Samba Lababan telah membuat model matematika dari suatu masalah program linear.

C.         Nilai Optimum Suatu Fungsi Objektif

Dalam pemodelan matematika masalah produksi ban PT. Samba Lababan, kalian akan mencari nilai x dan y sedemikian sehingga
f(x, y) = 40.000x + 30.000y maksimum.

Bentuk umum dari fungsi tersebut adalah f(x, y) = ax + by. Suatu fungsi yang akan dioptimumkan (maksimum atau minimum). Fungsi ini disebut fungsi objektif. Untuk menentukan nilai optimum fungsi objektif ini, kalian dapat menggunakan dua metode, yaitu metode uji titik pojok dan metode garis selidik.

 Bentuk umum dari fungsi tersebut adalah f(x, y) = ax + by. Suatu fungsi yang akan dioptimumkan (maksimum atau minimum).

Fungsi ini disebut fungsi objektif. Untuk menentukan nilai optimum fungsi objektif ini, kalian dapat menggunakan dua metode, yaitu metode uji titik pojok dan metode garis selidik.

Metode Uji Titik Pojok

Untuk menentukan nilai optimum dengan menggunakan metode uji titik pojok, lakukan langkah-langkah berikut.

1.  Tentukan kendala-kendala dari permasalahan program linear yang dimaksud.

2.  Gambarlah daerah penyelesaian dari kendala-kendala dalam masalah program linear tersebut.

3.  Tentukan titik-titik pojok dari daerah penyelesaian itu.

4.  Substitusikan koordinat setiap titik pojok itu ke dalam fungsi objektif.

5.  Bandingkan nilai-nilai fungsi objektif tersebut. Nilai terbesar berarti menunjukkan nilai maksimum dari fungsi f(x, y), sedangkan nilai terkecil berarti menunjukkan nilai minimum dari fungsi f(x, y).

Untuk lebih memahami dalam menentukan nilai optimum suatu fungsi objektif dengan menggunakan metode uji pojok, perhatikan contoh soal berikut.

Contoh Soal

Ling ling membeli 240 ton beras untuk dijual lagi. Ia menyewa dua jenis truk untuk mengangkut beras tersebut. Truk jenis A memiliki kapasitas 6 ton dan truk jenis B memiliki kapasitas 4 ton. Sewa tiap truk jenis A adalah Rp 100.000,00 sekali jalan dan truk jenis B adalah Rp 50.000,00 sekali jalan. Maka Ling ling menyewa truk itu sekurang-kurangnya 48 buah. Berapa banyak jenis truk A dan B yang harus disewa agar biaya yang
dikeluarkan minimum?

Pembahasan Contoh Soal

Langkah pertama. Tentukan kendala-kendala dari permasalahan program linear yang dimaksud oleh soal. Untuk mengetahui kendala-kendalanya, sebaiknya kita ubah soal tersebut ke dalam tabel sebagai berikut.

Sehingga, kendala-kendalanya dapat dituliskan sebagai berikut.

x + y ≥ 48,

6x + 4y ≥ 240,

x ≥ 0, y ≥ 0, x, y anggota bilangan cacah

Dengan fungsi objektifnya adalah f(x, y) = 100.000x + 50.000y.

Langkah kedua. Gambarkan daerah penyelesaian dari kendala-kendala di atas.

Langkah ketiga. Tentukan titik-titik pojok dari daerah penyelesaian itu. Titik pojok dari daerah penyelesaian di atas adalah titik potong garis 6x + 4y = 240 dengan sumbu-y, titik potong garis x + y = 48 dengan sumbu-x, dan titik potong garis-garis x + y = 48 dan 6x + 4y = 240.

Titik potong garis 6x + 4y = 240 dengan sumbu-y adalah titik (0, 60). Titik potong garis x + y = 48 dengan sumbu-x adalah titik (48, 0). Sedangkan titik potong garis-garis x + y = 48 dan 6x + 4y = 240 dapat dicari dengan menggunakan cara eliminasi berikut ini.

Diperoleh, titik potong garis-garis x + y = 48 dan 6x + 4y = 240 adalah pada titik (24, 24).

Langkah keempat. Substitusikan koordinat setiap titik pojok itu ke dalam fungsi objektif.

Langkah kelima. Bandingkan nilai-nilai fungsi objektif tersebut. Dari ketiga hasil tersebut, dapat diperoleh bahwa agar biaya yang dikeluarkan minimum, Ling ling harus menyewa 60 truk jenis B dan tidak menyewa truk jenis A.

C. 2. Metode Garis Selidik

Untuk menentukan nilai optimum fungsi objektif dengan menggunakan metode garis selidik, lakukanlah langkah-langkah berikut.

Tentukan garis selidik, yaitu garis-garis yang sejajar dengan garis

ax + by = k, a ≥ 0, b ≥ 0, dan k Є R.

Gambarkan garis selidik-garis selidik tersebut pada koordinat Cartesius!

Untuk menentukan nilai maksimum fungsi tujuan maka carilah garis selidik yang jaraknya terbesar terhadap titik pusat O(0, 0) dan berada pada daerah penyelesaian.

 Sedangkan untuk menentukan nilai minimum fungsi tujuan maka carilah garis selidik yang jaraknya terkecil terhadap titik pusat O(0, 0) dan berada pada daerah penyelesaian.

C.     NILAI OPTIMUM PADA PERMASALAHAN PROGRAM LINIER

Untuk menentukan nilai optimum fungsi objektif dengan menggunakan metode garis selidik, lakukanlah langkah-langkah berikut:

1.      Tentukan model pertidaksamaan dari informasi soal dan gambarkan daerah selesaian dari sistem pertidaksamaan tersebut pada bidang koordinat.

2.      Tentukan garis selidik ax + by = k apabila fungsi objektifnya f(x, y) = ax + by,a, b, dan k bilangan real.

3.      Untuk menentukan nilai maksimum fungsi objektif maka carilah garis selidik dengan nilai k terbesar dan melalui titik (-titik) pada daerah selesaian.

Sedangkan untuk menentukan nilai minimum fungsi objektif maka carilah garis selidik dengan nilai k terkecil dan melalui titik (-titik) pada daerah selesaian.

Untuk lebih memahami penerapan langkah-langkah tersebut, perhatikan contoh soal berikut.

Contoh Soal

Seorang peternak ayam petelur harus memberi makanan untuk tiap 50 ekor/hari paling sedikit 150 unit zat A dan 200 unit zat B. Zat-zat tersebut tidak dapat dibeli dalam bentuk murni, melainkan teerdapat dalam makanan ayam M1 dan M2.

Tiap kg makanan ayam M1 mengandung 30 unit zat A dan 20 unit zat B, dan makanan M2 mengandung 20 unit zat A dan 40 unit zat B. Jika harga M1 adalah Rp 225/kg dan harga M2 adalah Rp 250/kg, dan tiap ekor membutuhkan 125 gr makanan/hari.

Berapakah banyaknya makanan M1 dan M2 harus dibeli tiap hari untuk 1000 ekor ayam petelur, supaya harganya semurah-murahnya dan kebutuhan akan zat-zat itu dipenuhi?

Pembahasan Contoh Soal

Langkah pertama:

Ubah permasalahan di atas menjadi model matematika. Misalkan x dan y secara berturut adalah banyaknya makanan M1 dan M2 yang harus dibeli tiap hari untuk 1000 ekor ayam petelur. Karena tiap 50 ekor ayam dalam tiap harinya harus makan paling sedikit 150 unit zat A dan 200 unit zat B, tiap 1.000 ekor ayam dalam tiap harinya harus makan paling sedikit 3.000 unit zat A dan 4.000 unit zat B maka.

 Dan karena tiap ekor membutuhkan 125 gr makanan/hari, maka 1.000 ekor ayam membutuhkan 125.000 gr atau 125 kg makanan tiap harinya. Sehingga permasalahan di atas dapat dimodelkan sebagai berikut.

30x + 20y ≥ 3.000
20x + 40y ≥ 4.000
x + y ≥ 125
x ≥ 0
y≥ 0
x, y bilangan cacah

Fungsi objektif dari permasalahan di atas adalah f(x, y) = 225x + 250y.

 Sebelum menggambar grafiknya, sebaiknya kita daftar titik-titik yang dilalui oleh garis-garis batas dari sistem pertidaksamaan di atas.

Apabila digambarkan, daerah selesaiannya seperti berikut.

Setelah melihat gambar di atas, ternyata garis selidik yang melalui titik (50, 75) yang memiliki nilai k minimum (nilai k bisa dilihat pada sumbu y, semakin tinggi titik potong garis selidik terhadap sumbu y, maka semakin besar pula nilai ktersebut, dan sebaliknya). Untuk x = 50 dan y = 75, diperoleh nilai k-nya adalah 30.000.

Jadi, banyaknya makanan M1 dan M2 harus dibeli tiap hari untuk 1000 ekor ayam petelur supaya harganya semurah-murahnya dan kebutuhan akan zat-zat itu dipenuhi secara berturut-turut adalah 50 kg dan 75 kg.