MATEMATIKA: PROGRAM LINEAR

NABILLAH ANJUNI (23)

Materi Program Linear – Pengertian, Rumus, Contoh Soal

Program linear ialah suatu program yang digunakan sebagai metode yang umumnya digunakan untuk memecahkan suatu masalah seperti pengalokasian sumber daya dengan tujuan akhir yaitu menentukan nilai minimum atau maksimum.

Pengertian Program Linear

Program linear merupakan suatu program yang digunakan sebagai metode penentuan nilai optimum dari suatu persoalan linear. Nilai optimum (maksimal atau minimum) dapat diperoleh dari nilai dalam suatu himpunan penyelesaiaan persoalan linear.

Di dalam persoalan linear tersebut terdapat fungsi linear yang bisa disebut sebagai fungsi objektif. Persyaratan, batasan, dan kendala dalam persoalan linear adalah merupakan sistem pertidaksamaan linear.

Perhatikan tabel persoalan maksimum dan minimum dibawah berikut:

Model Matematika Program Linear

Persoalan dalam program linear yang masih dinyatakan dalam kalimat-kalimat pernyataan umum, kemudian diubah kedalam sebuah model matematika.

Model matematika adalah pernyataan yang menggunakan peubah dan notasi matematika.

Sebagai gambaran:

Sebuah produsen sepatu membuat 2 model sepatu menggunakan 2 bahan yang berbeda. Komposisi model yang pertama terdiri dari 200 gr bahan pertama dan bahan kedua 150 gr. Sedangkan komposisi model kedua tersebut terdiri dari 180 gr bahan pertama dan 170 gr bahan kedua. Persediaan di gudang bahan pertama 76 kg dan persediaan digudang untuk bahan kedua 64 kg. Harga model pertama ialah Rp. 500.000,00 dan untuk model kedua harganya Rp. 400.000,00.

Apabila disimpulkan atau disederhanakan ke dalam bentuk tabel akan menjadi sebagai berikut:

Dengan peubah dari jumlah optimal model 1 ialah x dan model 2 ialah y, serta hasil penjualan optimal ialah f(x, y) = 500.000x + 400.000y. Dengan beberapa syarat:

Apabila jumlah maksimal bahan 1 yaitu 72.000 gr, maka 200x + 150y ≤ 72.000.
Apabila jumlah maksimal bahan 2 yaitu 64.000 gr, maka 180x + 170y ≤ 64.000
Masing-masing dari setiap model harus terbuat.

Model matematika untuk mendapatkan jumlah penjualan yang maksimum yaitu:

Nilai Optimum Fungsi Objektif

Fungsi objektif yaitu fungsi linear dan batasan-batasan pertidaksamaan linear yang memiliki sebuah himpunan penyelesaian. Himpunan penyelesaian yang ada ialah berupa titik-titik dalam diagram cartesius yang apabila koordinatnya disubstitusikan kedalam fungsi linear maka dapat memenuhi persyaratan yang ditentukan.

Nilai optimum fungsi objektif dari suatu persoalan linear bisa ditentukan dengan menggunakan metode grafik. Dengan melihat grafik dari fungsi objektif dan batasan-batasannya, maka kita bisa tentukan letak titik yang menjadi nilai optimum.

Langkah-langkahnya yaitu sebagai berikut :

Menggambar himpunan penyelesaian dari semua batasan syarat yang ada pada cartesius.
Menentukan titik-titik ekstrim yang merupakan perpotongan pada garis batasan dengan garis batasan yang lainnya. Titik-titik ekstrim tersebut adalah himpunan penyelesaian dari batasannya dan memiliki suatu kemungkinaan besar akan membuat fungsi menjadi optimum.
Meneliti nilai optimum fungsi objektif dengan dua acara, yaitu :

Menggunakan garis selidik, dan
Membandingkan nilai fungsi objektif pada tiap titik ekstrim.

1. Menggunakan Garis Selidik

Garis selidik dapat diperoleh dari fungsi objektif f(x, y) = ax + by yang mana garis selidiknya ialah:

ax + by = Z

Nilai Z diberikan sembarang nilai.

Garis ini dibuat setelah grafik himpunan penyelesaian pertidaksamaannya juga dibuat.

Garis selidik awal dibuat di area himpunan penyelesaian awal. Lalu kemudian dibuat garis-garis yang sejajar dengan garis selidik awal.

Berikut adalah pedoman untuk mempermudah penyelidikian nilai fungsi optimum:

Cara 1 (syarat a > 0), yaitu:

Apabila maksimum, maka dibuat garis yang sejajar garis selidik awal sehingga membuat himpunan penyelesaian berada di kiri garis tersebut. Titik yang dilalui garis tersebut ialah titik maksimum.

Apabila minimum, maka dibuatlah garis yang sejajar garis selidik awal sehingga akan membuat suatu himpunan penyelesaian berada di kanan garis tersebut.

Titik yang dilalui garis tersebut ialah titik minimum.

Perhatikan grafik dibawah:

Cara ke- 2 (syarat b > 0), yaitu:

Apabila maksimum: maka dibuat garis yang sejajar garis selidik awal sehingga membuat himpunan penyelesaian berada di bawah garis tersebut. Titik yang dilalui garis tersebut ialah titik maksimum.
Apabila minimum: maka dibuat garis yang sejajar garis selidik awal sehingga membuat himpunan penyelesaian berada di atas garis tersebut. Titik yang dilalui garis tersebut ialah titik minimum.

· Bagi nilai a < 0 dan b < 0 maka berlaku sebuah kebalikan dari kedua cara yang dijelaskan di atas.

· 2. Membandingkan Nilai Fungsi Tiap Titik Ekstrim

· Menyelidiki nilai optimum dari fungsi objektif juga dapat dilaksanakan dengan terlebih dahulu menentukan titik-titik potong dari suatu garis-garis batas yang ada. Titik-titik potong tersebut merupakan nilai ekstrim yang berpotensi memiliki nilai maksimum pada salah satu titiknya.

· Berdasarkan titik-titik tersebut, maka dapat ditentukan nilai masing-masing fungsinya, yakni kemudian dibandingkan.

· Nilai terbesar merupakan nilai maksimum dan nilai terkecil adalah merupakan nilai minimum.

· Contoh Soal Program Linear dan Pembahasan

· Contoh Soal 1:

· Tentukanlah sebuah nilai minimum dari: f(x, y) = 9x + y pada daerah yang telah dibatasi oleh 2 ≤ x ≤ 6, dan 0 ≤ y ≤ 8 serta x + y ≤ 7.

Pembahasan 1:

Langkah 1 yaitu menggambar grafiknya terlebih dahulu:

Langkah ke-2 menentukan titik-titik ekstrimnya:

Maka berdasarkan gambar diatas, ada 4 titik ekstrim, yaitu: A, B, C, D dan himpunan penyelesaiannya ada di area yang telah diarsir.

Langkah yang ke-3, yaitu menyelidiki nilai optimum:

Berdasarkan grafik diatas dapat diketahui titik A dan B mempunyai nilai y = 0, sehingga kemungkinan menjadi nilai minimum.

Kedua titik disubstitusikan kedalam f(x, y) = 9x + y untuk dibandingkan.

Dengan membandingkan tersebut,maka bisa disimpulkan bahwa titik A memiliki nilai minimum 18.

Contoh Soal 2:

Tentukanlah dimana nilai maksimum fungsi f(x, y) = 4x + 5y yang akan dicapai pada pada grafik ini!

Pembahasan 2:

Titik ekstrim pada gambar ialah:

A tidak mungkin maksimum karena titik A paling kiri.
B(3, 6)
C(8, 2)
D(8, 0)

Nilai tiap titik ekstrim ialah:

Sehingga dapat diketahui hasilnya bahwa nilai maksimumnya berada pada titik yang melalui garis BC dengan nilai maksimum 42.

Contoh Soal 3

Pedagang buah memiliki modal Rp. 1.000.000,00 untuk membeli apel dan pisang untuk dijual kembali. Harga beli tiap kg apel Rp 4000,00 dan pisang Rp 1.600,00. Tempatnya hanya bisa menampung 400 kg buah. Tentukan jumlah apel dan pisang agar kapasitas maksimum.

Pembahasan 3:

Diketahui:

Dengan syarat:

§ Kapasitas tempat: x + y ≤ 400

§ Modal: 4.000x + 1.600y ≤ 1.000.000 $5x + 2y \le 1.250$

§ x ≥ 0

§ y ≥ 0

Diagramnya:

Titik ekstrim:

§ A(0, 400) bukan optimum karena tidak ada apel

§ C(250, 0) bukan optimum karena tidak ada pisang

§ dengan metode eliminasi 2 persamaan diatas diperoleh:

Sehingga jumlah masimum:

§ Apel: 150 kg

§ Pisang: 250 kg

Contoh Soal 4

Himpunan penyelesaian sistem pertidaksamaan

5x + y ≥ 10

2x + y ≤ 8

y ≥ 2

ditunjukkan oleh daerah . . .

Pembahasan 4 :

Terlihat pada gambar bahwa A adalah persamaan garis 5x + y = 10 titik potong dengan sumbu x jika y = 0

x = 2 → titik (2,0)

titk potong dengan sumbu y jika x = 0

y = 10 → titik (0,10)

daerah 5x + y ≥ 10 berada pada garis persamaan tersebut dan di atas garis (I, II,III, V) —(a)

B adalah persamaan garis 2x + y = 8 titik potong dengan sumbu x jika y=0 x = 4 → (4,0)

titik potong dengan sumbu y jika x = 0 y = 8 → (0,8)

daerah 2x + y ≤ 8 berada pada garis persamaan tersebut dan di bawah garis (III, V) ….(b)

C adalah garis y = 2

daerah di atas garis y = 2 adalah I, II, III, IV …(b)

dari (a) , (b) dan (c) :

1. I II III V
2. III V
3. I II III IV

Yang memenuhi ketiga-tiganya adalah daerah III

Contoh Soal 5

Seorang tukang roti mempunyai bahan A,B dan C masing-masing sebanyak 160 kg, 110 kg dan 150 kg.

Roti I memerlukan 2 kg bahan A, 1 kg bahan B dan 1 Kg bahan C
Roti II memerlukan 1 kg bahan A, 2 kg bahan B dan 3 Kg bahan C

Sebuah roti I dijual dengan harga Rp.30.000 dan sebuah roti II dijual dengan harga Rp.50.000, pendapatan maksimum yang dpat diperoleh tukang roti tersebut adalah…

Pembahasan 5 :

Buat persamaan :

Misal roti I = x dan roti II = y didapat persamaan sbb:

2x + y ≤ 160 …..(1)

x + 2y ≤ 110 …..(2)

x + 3y ≤ 150 ….(3)

buat sketsa grafiknya:

“Sketsa grafik diperlukan untuk melihat daerah himpunan penyelesaian dan titik-titik ekstrim, dibutuhkan skala yang tepat untuk mendapatkan grafik yang optimum (benar atau mendekati kebenaran) untuk memudahkan penyelesaian”

Daerah yang diarsir adalah himpunan penyelesaian dari tiga grafik tsb. Didapat 4 titik ekstrim yaitu (0,50), (80,0), titik A dan titik B

perpotongan (1) dan (2) →titik B

Contoh Soal 6

Daerah yang diarsir merupakan himpunan penyelesaian dari sistem pertidaksamaan linear…

Pembahasan 6 :

karena daerah arsiran dibawah persamaan garis maka

x + 2y ≤ 8 ….(2)

Arsiran di atas sumbu x dan di kanan sumbu y maka x ≥ 0 dan y≥ 0 ….(3) dan (4)

sehingga daerah penyelesaiannya adalah:

(1), (2), (3) dan (4)

3x + 2y ≤ 12, x + 2y ≤ 8 dan x≥ 0, y≥ 0

Contoh Soal 7

Luas daerah parkir 360 m². Luas rata-rata sebuah mobil 6 m² dan luas rata – rata bus 24 m². Daerah parkir tersebut dapat memuat paling banyak 30 kendaraan roda empat (mobil dan bus). Jika tarif parkir mobil Rp2.000,00 dan tarif parkir bus Rp5.000,00 maka pendapatan terbesar yang dapat diperoleh adalah …

x = banyak mobil

y = banyak bus

Pembahasan 7 :

Perhatikan tabel di bawah!

Diperoleh dua persamaan:

§ x + y ≤ 30

§ 6x + 24y ≤ 360 → x + 4y ≤ 60

Menentukan daerah yang memenuhi pertidaksamaan:

Akan ditentukan nilai maksimum dengan metode titik sudut.

Titik koordinat O, A, dan C dapat diperoleh dengan melihat gambar, yaitu O(0,0), A(0, 15), dan C(30,0). Untuk koordinat B dapat diperoleh dengan menggunakan eliminasi dan substitusi.

Substitusi nilai y = 10 pada persamaan x + y = 30 untuk mendapatkan nilai x.

x + y = 30
x + 10 = 30
x = 30 – 10 = 20

Koordinat titik B adalah (20, 10)

Perhitungan keuntungan maksimal yang dapat diperoleh:

Contoh Soal 8

Biaya produksi satu buah payung jenis A adalah Rp20.000,00 per buah, sedangkan biaya satu buah produksi payung jenis B adalah Rp30.000,00. Seorang pengusaha akan membuat payung A dengan jumlah tidak kurang dari 40 buah. Sedangkan banyaknya payung jenis B yang akan diproduksi minimal adalah dari 50 buah. Jumlah maksimal produksi kedua payung tersebut adalah 100 buah. Biaya minimum yang dikeluarkan untuk melakukan produksi kedua payung sesuai ketentuan tersebut adalah ….

Pembahasan 8 :

Pemisalan:

§ x = banyak payung A

§ y = banyak payung B

Model matematika dari permasalahan tersebut adalah:

Fungsi tujuan: meminimumkan f(x,y) = 20.000x + 30.000y

Fungsi kendala:

§ x ≥ 40

§ y ≥ 50

§ x + y ≤ 100

Daerah penyelesaian yang memenuhi permasalahan:

Nilai minimum akan diperoleh melalui titik koordinat yang dilalui garis selidik yang pertama kali, yaitu titik A(40, 50).

Sehingga, biaya produksi minimum adalah

f(40,50) = 20.000(40) + 30.000(50)
f(40,50) = 800.000 + 1.500.000
f(40,50) = 2.300.000

MATEMATIKA

Minggu, 02 Agustus 2020

PROGRAM LINEAR