Program Linier lengkap

Program linier merupakan bagian dari matematika terapan yang sering dijumpai pada bidang riset operasi. Seperti yang telah dibahas di banyak artikel bahwa program linier adalah suatu metode atau cara untuk mencari nilai maksimum dan minimum bentuk linier (yang disebut bentuk objektif) pada daerah yang dibatasi oleh suatu system pertidaksamaan linier. Dari daerah yang membatasi system pertidaksamaan itu terdapat sebuah penyelesaian yang memberikan hasil terbaik (yang disebut penyelesaian optimum).

Definisi

DEFINISI: Program Linier
Program linier  adalah metode atau cara yang dapat digunakan sebagai solusi masalah optimasi, yaitu memaksimumkan atau meminimumkan suatu bentuk objektif atau fungsi sasaran dengan kendala-kendala berupa sistem pertidaksamaan linier.

Dalam perkembangannya, program linier menjadi sangat penting dalam berbagai bidang, terutama bidang industri atau usaha, seperti produksi barang dan penjualan barang.

Misalkan seorang pengusaha ingin menentukan suatu teknik produksi yang harus digunakan untuk memenuhi permintaan pasar dengan meminimuman biaya atau ongkos produksi. Untuk menyelesaikan masalah ini, kita harus mengetahui kendala-kendala apa saja yang terdapat dalam produksi barang tersebut, misalnya jumlah bahan baku yang tersedia, jumlah pegawai atau kendala lainya. Selanjutnya dengan fungsi objektif atau fungsi sasaran yang kita inginkan kita dapat memutuskan teknik produksinya.

Untuk itu kalau kita menguasai program linier ini, tentunya kita nantinya dapat menyelesaikan masalah yang berkaitan dengan memaksimumkan atau meminimumkan.

Program Linier dan Model Matematika

Pada artikel ini kita akan sistem pertidaksamaan linier dua variabel, model matematika, pengertian bentuk objektif, menentukan nilai optimum bentuk objektif, serta menyelesaikan soal-soal yang berkaitan dengan program linier.

Baca JugaSistem Pertidaksamaan Linier Dua Variabel

Untuk memecahkan suatu masalah program linier kita harus menerjemahkan terlebih dahulu masalah tersebut dalam Bahasa matematika. Rumusan matematis yang diperoleh itu disebut pula model matematika. Rumusan matematis secara garis besar dibagi dua bagian, yaitu:

  1. Persyaratan atau kendala-kendala (system pertidaksamaan)
  2. Bentuk fungsi objektif (fungsi sasaran)

Membuat Model Matematika

Contoh Soal 1

Seorang pedagang sepatu mempunyai modal Rp 8.000.000,-. Ia merencanakan membeli dua jenis sepatu, sepatu pria dan sepatu wanita. Harga  beli sepatu pria adalah Rp 20.000,- per pasang dan sepatu wanita harga belinya Rp 16.000,- per pasang. Keuntungan dari penjualan sepatu pria dan wanita berturut-turut adalah Rp 6.000,- dan Rp 5.000,-. Mengingat kapasitas kiosnya, ia akan membeli sebanyak-banyaknya 450 pasang sepatu. Buatlah model matematika yang sesuai dengan persoalan ini.

Pembahasan:

Misalkan sepatu pria =$x$ dan sepatu wanita = $y$. Persoalan diatas dapat dinyatakan dengan tabel sebagai berikut.

Sepatu pria Sepatu wanita Kapasitas/modal
Banyak x y 450
Harga beli 20.000x 16.000y 8.000.000
Keuntungan 6.000x 5.000y

Karena kapasitas kios tidak lebih dari 450 pasang sepatu dan pedagang itu hanya memiliki modal Rp 8.000.000,-, maka didapat pertidaksamaan:

$ x+y \leq 450 $

$ 20.000x+ 16.000y \leq 8.000.000 $, sehingga diperoleh

$ 5x + 4y \leq 2.000 $

$x$ dan $y$ menyatakan banyaknya sepatu, sehingga nilainya tidak mungkin negatif maupun pecahan. Jadi $x$ dan $y$ merupakan bilangan cacah (C). Dengan demikian pertidaksamaannya:

$x \geq 0$ dan $y \geq 0 $ , $x$ dan $y$ ∈ C

Jadi model matematika untuk permasalahan diatas adalah:

$x \geq 0$ , $y \geq 0 $ , $ x+y \leq 450 $, dan $ 5x + 4y \leq 2.000 $ untuk $x$ dan $y$ ∈ C dengan keuntungan sebesar-besarnya diperoleh dari bentuk $ (6.000x + 5.000y) $

Contoh Soal 2

Seorang peternak ayam setiap harinya membutuhkan dua jenis makanan ayam. Makanan jenis I dam 1 kg mengandung 9 unit bahan A dan 3 unit bahan B, sedangkan makanan jenis II dalam 1 kg mengandung 3 unit bahan A dan 18 unit bahan B. Setiap hari 10 ekor ayam membutuhkan sekurang-kurangnya 27 unit bahan A dan 30 unit bahan B. Jumlah makanan jenis I dan jenis II untuk 10 ekor ayam setiap harinya minimal 5 kg. Harga tiap kilogram makanan jenis I adalah Rp 1.000,- dan makanan jenis II adalah Rp 2.000,-. Buatlah model matematika untuk masalah program linier tersebut, agar biaya makanan ayam jenis I dan jenis II setiap harinya semurah-murahnya.

Pembahasan:

Misalkan makanan jenis I=$x$ dan makanan jenis II=$y$, persoalan diatas dapat dinyatakan dengan tabel sebagai berikut.

Jenis I Jenis II Kapasitas/modal
Banyak makanan setiap hari x y 5
Bahan A 9x 3y 27
Bahan B 3x 18y 30
Biaya 1.000x 2.000y

Karena setiap harinya jumlah makanan kedua jenis minimal 5 kg, dan sekurang-kurangnya 27 unit bahan A dan 30 unit bahan B maka didapat pertidaksamaan:

$ x + y \geq 5 $

$ 9x + 3y \geq 27 $ sehingga disederhanakan menjadi $ 3x + y \geq 9 $

$ 3x + 18y \geq 30 $ sehingga disederhanakan menjadi $ x + 6y \geq 10 $

$x$ dan $y$ menyatakan banyaknya makanan ayam, sehingga nilainya tidak mungkin negatif. Jadi $x$ dan $y$ dapat merupakan bilangan real (R). Dengan demikian pertidaksamaannya adalah :

$x \geq 0$ dan $y\geq 0 $ , $x$ dan $y$ ∈ R

Jadi, model matematika untuk persoalan diatas adalah :

$x \geq 0$, $y\geq 0 $, $ x + y \geq 5 $, $ 3x + y \geq 9 $, dan $ x + 6y \geq 10 $ untuk $x$ dan $y$ ∈ R, dengan bentuk $ (1.000x + 2.000y) $ adalah biaya semurah-murahnya.

Bentuk Fungsi Objektif

Untuk mengenal fungsi objektif, perhatikan kembali contoh 1 dan contoh 2 diatas. Dari kedua contoh tersebut, didalam model matematikanya terdapat bentuk:

$ (6.000x + 5.000y) $ keuntungan sebesar-besarnya

$ (1.000x + 2.000y) $ biaya semurah-murahnya.

Tampak bahwa tujuan yang hendak dicapai dapat dinyatakan dalam bentuk fungsi $ (ax + by) $ yang dioptimumkan (dimaksimumkan atau diminimumkan). Bentuk itulah yang dinamakan bentuk fungsi objektif.

DEFINISI: Bentuk Objektif
Bentuk fungsi $ (ax + by) $ yang dicari nilai maksimum atau minimumnya disebut bentuk fungsi objektif

Misalkan diketahui asalah program linier untuk memaksimalkan $(2x+y)$ dengan syarat:

$ 3x +2y \leq 12 $

$ x +4y \leq 14 $

$x \geq 0 $, $ y \geq 0 $

Titik $(x,y)$ yang memenuhi system pertidaksamaan dapat dilihat pada gambar dibawah ini.

Selanjutnya, kita cari titik $(x,y)$ di daerah arsiran sehingga nilai $(2x+y)$ maksimum.

  • Untuk titik O (0,0),

$x=0$, $y=0$ maka $2x+y=0$

  • Untuk titik (4,0),

$x=4$, $y=0$ maka $2x+y=8$

  • Untuk titik (2, 3),

$x=2$, $y=3$ maka $2x+y=7$

  • Untuk titik (0, $3\frac{1}{2}$),

$x=0$, $y=3\frac{1}{2}$ maka $2x+y=3\frac{1}{2}$

Jadi, nilai $(2x+y)$ maksimum diperoleh pada titik (4, 0).

Nilai Fungsi Objektif
Secara umum, fungsi objektif mempunyai nilai maksimum atau minimum di titik pojok daerah himpunan penyelesaian.

Menyelidiki nilai fungsi objektif pada titik-titik pojok himpunan penyelesaian disebut uji titik pojok.

Menentukan Nilai Optimum Fungsi Objektif

Salah satu masalah program linier adalah menentukan nilai optimum suatu fungsi objektif. Langkah-langkah yang dapat dilakukan adalah:

  1. Merumuskan persoalan kedalam model matematika. Dalam model matematika yang diperoleh terbentuk system pertidaksamaan linier dan fungsi objektif $ (ax + by) $.
  2. Menggambar daerah yang memenuhi suatu system pertidaksamaan.
  3. Menganalisa nilai fungsi objektif, dilakukan dengan menggunakan metode uji titik pojok atau metode garis selidik. Dari sini diperoleh nilai optimum yaitu nilai maksimum atau nilai minimum yang mungkin.

Marilah kita lihat kembali contoh 1 diatas.

Contoh Soal 1

Seorang pedagang sepatu mempunyai modal Rp 8.000.000,-. Ia merencanakan membeli dua jenis sepatu, sepatu pria dan sepatu wanita. Harga  beli sepatu pria adalah Rp 20.000,- per pasang dan sepatu wanita harga belinya Rp 16.000,- per pasang. Keuntungan dari penjualan sepatu pria dan wanita berturut-turut adalah Rp 6.000,- dan Rp 5.000,-. Mengingat kapasitas kiosnya, ia akan membeli sebanyak-banyaknya 450 pasang sepatu. Buatlah model matematika yang sesuai dengan persoalan ini. Berapa banyak sepatu pria dan wanita yang harus dibeli agar pedagang tersebut memperoleh keuntungan sebesar-besarnya? Berapa keuntungan terbesar yang dapat diperoleh?

Pembahasan:

Masalah diatas dapat diselesaikan dengan langkah-langkah berikut.

 

  1. Merumuskan persoalan kedalam model matematika.

Pembahasan ini sudah disampaikan diatas silakan lihat kembali dengan bentuk model matematika sebagai berikut.

$x \geq 0$ , $y \geq 0 $ , $ x+y \leq 450 $, dan $ 5x + 4y \leq 2.000 $ untuk $x$ dan $y$ ∈ C dengan keuntungan sebesar-besarnya diperoleh dari bentuk $ (6.000x + 5.000y) $.

 

2. Menggambar daerah yang memenuhi sistem pertidaksamaan.

 

Eliminasi kedua persamaan:

$ x+y=450 $       (x5)  $5x+5y=2.250$

$ 5x+4y=2000 $ (x1)  $5x+4y=2.000$

Diperoleh nilai $y=250$ dan nilai $x=200$

 

 

 

 

Jika Anda belum bisa cara menggambar dan menentukan himpunan penyelesaian di atas, silakan Anda pelajari di bawah ini :

Baca : Cara Menggambar dan Menentukan Himpunan Penyelesaian

Titik potong garis $ x+y =450$ dan garis $5x =4y=2.000$ adalah $(200, 250)$ seperti tampak pada gambar di atas.

 

3. Menganalisa nilai fungsi objektif.

Titik-titik pojok daerah himpunan penyelesaian diatas adalah noktah warna hitam dengan koordinat (0,0), (400,0), (200,250), dan (0,450). Selanjutnya titik-titik tersebut diujikan pada fungsi objektif sebagai berikut.

Titik Pojok 6.000x + 5.000y Nilai
(0,0) 6.000 . 0+ 5.000 . 0 0
(400, 0) 6.000 . 400+5.000 . 0 2.400.000
(200, 250) 6.000 . 200 + 5.000 . 250 2.450.000
(0, 450) 6.000 . 0+ 5.000 . 450 2.250.000

Berdasarkan tabel diatas terlihat bahwa keuntungan maksimum pedagang tersebut adalah Rp 2.450.000,- yaitu dengan membeli sepatu pria sebanyak 200 pasang dan sepatu wanita sebanyak 250 pasang.

 

Contoh Soal 2

Seorang peternak ayam setiap harinya membutuhkan dua jenis makanan ayam. Makanan jenis I dam 1 kg mengandung 9 unit bahan A dan 3 unit bahan B, sedangkan makanan jenis II dalam 1 kg mengandung 3 unit bahan A dan 18 unit bahan B. Setiap hari 10 ekor ayam membutuhkan sekurang-kurangnya 27 unit bahan A dan 30 unit bahan B. Jumlah makanan jenis I dan jenis II untuk 10 ekor ayam setiap harinya minimal 5 kg. Harga tiap kilogram makanan jenis I adalah Rp 1.000,- dan makanan jenis II adalah Rp 2.000,-.

Buatlah model matematika untuk masalah program linier tersebut, agar biaya makanan ayam jenis I dan jenis II setiap harinya semurah-murahnya. Berapa kilogram kedua jenis makanan yang diperlukan ayam setiap hari agar pengeluaran biaya sekecil mungkin? Tentukan besar biaya minimum setiap harinya.

Pembahasan:

Masalah diatas bisa diselesaikan dengan langkah-langkah berikut.

  1. Merumuskan persoalan kedalam model matematika.

Pembahasan ini sudah disampaikan diatas silakan lihat kembali dengan bentuk model matematika sebagai berikut.

Jadi, model matematika untuk persoalan diatas adalah :

$x \geq 0$, $y\geq 0 $, $ x + y \geq 5 $, $ 3x + y \geq 9 $, dan $ x + 6y \geq 10 $ untuk $x$ dan $y$ ∈ R,

Fungsi objektif $ (1.000x + 2.000y) $ dengan biaya semurah-murahnya (minimum).

 

2. Grafik sistem pertidaksamaan:

Dengan eliminasi setiap persamaan garis diperoleh:

Titik potong garis $ 3x + y = 9 $ dan $ x + y = 5 $ adalah (2,3).

Titik potong garis $ x + y = 5 $ dan $ x + 6y = 10$ adalah (4,1).

Terlihat seperti pada gambar di samping.

 

 

Jika Anda belum bisa cara menggambar dan menentukan himpunan penyelesaian di atas, silakan Anda pelajari di bawah ini :

Baca : Cara Menggambar dan Menentukan Himpunan Penyelesaian

 

3. Titik-titik pojok pada daerah himpunan penyelesaian adalah (10,0), (4,1), (2,3), (0, 9). Selanjutya titik-titik tersebut diujikan pada fungsi objektif seperti pada tabel berikut.

Titik Pojok 1.000x + 2.000y Nilai
(10,0) 1.000 . 10+ 2.000 . 1 10.000
(4, 1) 1.000 . 4+2.000 . 1 6.000
(2, 3) 1.000 . 2 + 2.000 . 3 8.000
(0, 9) 1.000 . 0+ 2.000 . 9 18.000

 

Jadi terlihat jelas pada tabel diatas bahwa biaya minimum peternak tersebut adalah Rp 6.000,- setiap hari, dengan membutuhkan makanan ayam jenis I sebanyak 4 kg dan jenis II sebanyak 1 kg.

Kesimpulan

Program linier  adalah metode atau cara yang dapat digunakan sebagai solusi masalah optimasi, yaitu memaksimumkan atau meminimumkan suatu bentuk objektif atau fungsi sasaran dengan kendala-kendala berupa sistem pertidaksamaan linier.

langkah-langkah menyelesaiakan masalah program linier:

  1. membuat model matematika
  2. menentukan daerah himpunan penyelesaian sistem pertidaksamaan
  3. menguji titik pojok atau menggunakan garis selidik
  4. menentukan nilai maksimum dan minimum

Silakan Anda bisa mendalami contoh-contoh program linier lainya atau aplikasi matematika lainnya di bawah ini :

Baca Juga:

Demikian penjelasan artikel yang sedikit semoga bermanfaat dan silakan share.

Follow This :