Program linear berkembang dan ditemukan oleh beberapa matematikawan pada masa sebelum Perang Dunia ke-II. Pengembangan program linear pada masa tersebut rata – rata didasarkan karena persoalan atau masalah yang sedang berkembang saat itu, yaitu dalam hal industri dan peperangan. Program linear adalah suatu metode atau suatu cara yang digunakan untuk memecahkan masalah menjadi optimal (maksimum atau minimum). Program linear atau juga disebut dengan optimasi linear adalah suatu program yang digunakan untuk memecahkan masalah-masalah optimasi. Dalam program linear, batasan-batasan atau kendala diubah atau diterjemahkan ke dalam bentuk sistem pertidaksamaan linear. Nilai-nilai peubah yang memenuhi sistem pertidaksamaan linear mempunyai berbagai macam kemungkinan penyelesaian. Dari berbagai kemungkinan tersebut terdapat penyelesaian yang memberikan hasil yang terbaik yang disebut dengan penyelesaian optimum (minimum atau maksimum). Sehingga, tergambar jelas jika program linear digunakan untuk menemukan solusi terbaik atau optimum dari suatu ungsi tujuan (fungsi objektif).
Dari uraian di atas, diketahui bahwa program linear sangat erat kaitanya dengan sistem pertidaksamaan linear dua variabel. Selain itu, dalam program linear diperlukan kemampuan dalam menafsirkan permasalahan menjadi kalimat matematika atau yang dikenal dengan model mateematika. Model matematika adalah rumusan matematika yang berupa persamaan, pertidaksamaan, atau fungsi yang diperoleh dari hasil penafsiran atau terjemahan suatu masalah ke dalam bahasa matematika. Sebenarnya model matematika telah diperkenalkan pada materi sistem persamaan linear dua variabel. Pada program linear, kita akan lebih banyak menafsirkan permasalahan menjadi bentuk sistem pertidaksamaan linear. Berikut ini adalah contoh pembuatan model matematika
Pak Ahok membeli 3 buku tulis dan 5 pensil dengan harga Rp11.000 di toko ATK Indonesia. Pada toko yang sama Pak Jokowi juga membeli 4 buku tulis dan sebuah pensil dan mebayar Rp9.000. Jika Pak Prabowo ingin membeli 5 buku tulis dan 5 pensil pada toko tersebut, berapa ia harus membayar?
Dilihat dari pertanyaanya, yang ditanyakan adalah uang yang harus dibayarkan untuk membeli 5 buku tulis dan 5 pensil. Sehingga kita harus tahu berapa harga sebuah buku tulis dan harga sebuah pensil. Untuk memudahkan penulisannya kita misalkan x adalah harga sebah buku tulis dan y adalah harga sebuah pensil.
Dari Pak Ahok kita medapatkan hubungan
3x + 5y = 11000
Sedangkan, dari Pak Jokowi kita mendapat hubungan
4x + y = 9000
dan dari Pak Prabowo
5x + 5y = ....?
Dengan demikian kita mendapatkan model matematikanya
3x + 5y = 11000
4x + y = 9000
Nah, sekarang kita akan membahas model matematika untuk masalah program linear. Berikut adalah contoh permasalahan yang berkaitan dengan program linear.
Seorang pedagang kue mendapat keuntungan Rp500 untuk kue Apem yang harga belinya Rp1.000 per buahdan mendapat keuntungan Rp400 untuk kue Naga Sari yang harga belinya Rp800 per buah. Modal yang dimiliki pedagang tersebut adalah Rp500.000. Sedangkan, kapasitas tempat penjualan kue hanya dapat menampung 550 kue. Berapa banyak kue Apem dan kue Naga Sari yang harus dibeli pedagang agar mendapat keuntungan sebesar-besarnya? dan berapakah keuntungan maksimunya?
Dari soal diperoleh bahwa
Misalkan x = banyak kue apem yang harus dibeli dan y = banyak kue naga sari yang harus dibeli, Kendala-kendala dalam masalah di atas dapat disajikan dalam tabel berikut
Untuk harga kue karena modal yang tersedia hanya Rp500.000, maka tanda yang pas untuk menggambarkan kendala tersebut adalah tanda "kurang dari" atau ≤, sehingga diperoleh pertidaksamaan
1000x + 800y ≤ 500000 atau 5x + 4y ≤ 2500
Sedangkan, daya tampung yang tersedia hanya 550 kg, jadi tanda yang pas digunakan adalah "kurang dari" atau ≤
x + y ≤ 550
Dengan demikan diperoleh model matematika untuk permasalahan di atas adalah
5x + 4y ≤ 2500
x + y ≤ 550
x ≥ 0
y ≥ 0
Dengan fungsi objektif
f(x, y) = 500x + 400y
x ≥ 0 dan y ≥ 0 dikenal sebagai kendala non negatif, karena bisa dibayangkan x yaitu banyak kue Apem dan y yaitu banyak kue Naga Sari tidak mungkin bernilai negatif.
Dari contoh yang terakhir, tentu yang dicari adalah nilai optimum dari fungsi objektif. Untuk menentukan nilai optimumnya kita dapat menggunakan beberapa metode yaitu Metode Uji Titik Pojok, Metode Garis Selidik dan Metode Simpleks. Namun yang akan dibahas pada halaman ini hanya menggunakan Metode Uji Titik Pojok. Pada dasarnya metode apappun yang digunakan hakikatnya adalah mencoba-coba secara manual untuk menentukan nilai optimu dari suatu fungsi objektif. Untuk menggunakan Metode Uji Titik Pojok perhatikan contoh berikut
Contoh 1
Diketahui model matematika dengan sistem pertidaksamaan
x + 4y ≤ 240
x + y ≤ 120
x ≥ 0
y ≥ 0
Fungsi Objektif : 20x + 30y
Tentukan nilai maksimum dari fungsi objektif tersebut!
Penyelesaian
Langkah pertama kita harus menggambar dan menentukan daerah penyelesaian sistem pertidaksamaan di atas. Anda dapat mempelajarai cara menggambar grafik dan menentukan daerah penyelesaiannya pada artikel Sistem Pertidaksamaan Linear Dua Variabel. Namun, kali ini yang menjadi daerah penyelesaian adalah daerah yang diarsir bukan daerah bersih seperti pada artikel Sistem Pertidaksamaan Linear Dua Variabel. Nah, langsung saja berikut adalah gambarnya
Kemudian kita tentukan titik-titik pojok dari daerah penyelesaianya. Untuk menentukan titik potong garis x + 4y = 240 dan x + y = 120, kita dapat menggunakan metode Eliminasi Substitusi
Eliminasi x
Substitusi y = 40 ke persamaan x + y = 120
x + 40 = 120
x = 80
Jadi, titik potongnya (80, 40)
Dengan demikian diperoleh empat titik pojok yaitu (0, 0), (120, 0), (80, 40), dan (0, 60). Kemudian kita cari titik yang menyebabkan fungsi objektif menjadi maksimum
Jadi, nilai maksimum dari fungsi objektif : 20x + 30 y adalah 2800
Contoh 2
Seorang pedagang buah-buahan menggunakan gerobak untuk menjual Apel dan Pisang. Harga pebelian Apel Rp20.000 per kg dan Pisang Rp8.000 per kg. Modal yang tersedia Rp5.000.000. Sedangkan muatan gerobaknya tidak dapat melebihi 400 kg. Keuntungan Apel Rp3.000 per kg sedangkan Pisang Rp2.000. Agar pedagang mendapat keuntungan sebesar-besarnya, berapa banyak Apel dan Pisang yang harus dibeli pedagang?
Penyelesaian:
Misalkan harga 1 kg Apel = x dan harga 1 kg Pisang = y, maka diperoleh
20000x + 8000y ≤ 5000000 atau 5x + 2y ≤ 1250
x + y ≤ 400
x ≥ 0
y ≥ 0
Fungsi Objektif : 3000x + 2000y
Gambar grafik
Dari uraian di atas, diketahui bahwa program linear sangat erat kaitanya dengan sistem pertidaksamaan linear dua variabel. Selain itu, dalam program linear diperlukan kemampuan dalam menafsirkan permasalahan menjadi kalimat matematika atau yang dikenal dengan model mateematika. Model matematika adalah rumusan matematika yang berupa persamaan, pertidaksamaan, atau fungsi yang diperoleh dari hasil penafsiran atau terjemahan suatu masalah ke dalam bahasa matematika. Sebenarnya model matematika telah diperkenalkan pada materi sistem persamaan linear dua variabel. Pada program linear, kita akan lebih banyak menafsirkan permasalahan menjadi bentuk sistem pertidaksamaan linear. Berikut ini adalah contoh pembuatan model matematika
Pak Ahok membeli 3 buku tulis dan 5 pensil dengan harga Rp11.000 di toko ATK Indonesia. Pada toko yang sama Pak Jokowi juga membeli 4 buku tulis dan sebuah pensil dan mebayar Rp9.000. Jika Pak Prabowo ingin membeli 5 buku tulis dan 5 pensil pada toko tersebut, berapa ia harus membayar?
Dilihat dari pertanyaanya, yang ditanyakan adalah uang yang harus dibayarkan untuk membeli 5 buku tulis dan 5 pensil. Sehingga kita harus tahu berapa harga sebuah buku tulis dan harga sebuah pensil. Untuk memudahkan penulisannya kita misalkan x adalah harga sebah buku tulis dan y adalah harga sebuah pensil.
Dari Pak Ahok kita medapatkan hubungan
3x + 5y = 11000
Sedangkan, dari Pak Jokowi kita mendapat hubungan
4x + y = 9000
dan dari Pak Prabowo
5x + 5y = ....?
Dengan demikian kita mendapatkan model matematikanya
3x + 5y = 11000
4x + y = 9000
Nah, sekarang kita akan membahas model matematika untuk masalah program linear. Berikut adalah contoh permasalahan yang berkaitan dengan program linear.
Seorang pedagang kue mendapat keuntungan Rp500 untuk kue Apem yang harga belinya Rp1.000 per buahdan mendapat keuntungan Rp400 untuk kue Naga Sari yang harga belinya Rp800 per buah. Modal yang dimiliki pedagang tersebut adalah Rp500.000. Sedangkan, kapasitas tempat penjualan kue hanya dapat menampung 550 kue. Berapa banyak kue Apem dan kue Naga Sari yang harus dibeli pedagang agar mendapat keuntungan sebesar-besarnya? dan berapakah keuntungan maksimunya?
Dari soal diperoleh bahwa
Misalkan x = banyak kue apem yang harus dibeli dan y = banyak kue naga sari yang harus dibeli, Kendala-kendala dalam masalah di atas dapat disajikan dalam tabel berikut
Untuk harga kue karena modal yang tersedia hanya Rp500.000, maka tanda yang pas untuk menggambarkan kendala tersebut adalah tanda "kurang dari" atau ≤, sehingga diperoleh pertidaksamaan
1000x + 800y ≤ 500000 atau 5x + 4y ≤ 2500
Sedangkan, daya tampung yang tersedia hanya 550 kg, jadi tanda yang pas digunakan adalah "kurang dari" atau ≤
x + y ≤ 550
Dengan demikan diperoleh model matematika untuk permasalahan di atas adalah
5x + 4y ≤ 2500
x + y ≤ 550
x ≥ 0
y ≥ 0
Dengan fungsi objektif
f(x, y) = 500x + 400y
x ≥ 0 dan y ≥ 0 dikenal sebagai kendala non negatif, karena bisa dibayangkan x yaitu banyak kue Apem dan y yaitu banyak kue Naga Sari tidak mungkin bernilai negatif.
Dari contoh yang terakhir, tentu yang dicari adalah nilai optimum dari fungsi objektif. Untuk menentukan nilai optimumnya kita dapat menggunakan beberapa metode yaitu Metode Uji Titik Pojok, Metode Garis Selidik dan Metode Simpleks. Namun yang akan dibahas pada halaman ini hanya menggunakan Metode Uji Titik Pojok. Pada dasarnya metode apappun yang digunakan hakikatnya adalah mencoba-coba secara manual untuk menentukan nilai optimu dari suatu fungsi objektif. Untuk menggunakan Metode Uji Titik Pojok perhatikan contoh berikut
Contoh 1
Diketahui model matematika dengan sistem pertidaksamaan
x + 4y ≤ 240
x + y ≤ 120
x ≥ 0
y ≥ 0
Fungsi Objektif : 20x + 30y
Tentukan nilai maksimum dari fungsi objektif tersebut!
Penyelesaian
Langkah pertama kita harus menggambar dan menentukan daerah penyelesaian sistem pertidaksamaan di atas. Anda dapat mempelajarai cara menggambar grafik dan menentukan daerah penyelesaiannya pada artikel Sistem Pertidaksamaan Linear Dua Variabel. Namun, kali ini yang menjadi daerah penyelesaian adalah daerah yang diarsir bukan daerah bersih seperti pada artikel Sistem Pertidaksamaan Linear Dua Variabel. Nah, langsung saja berikut adalah gambarnya
Eliminasi x
Substitusi y = 40 ke persamaan x + y = 120
x + 40 = 120
x = 80
Jadi, titik potongnya (80, 40)
Dengan demikian diperoleh empat titik pojok yaitu (0, 0), (120, 0), (80, 40), dan (0, 60). Kemudian kita cari titik yang menyebabkan fungsi objektif menjadi maksimum
Jadi, nilai maksimum dari fungsi objektif : 20x + 30 y adalah 2800
Contoh 2
Seorang pedagang buah-buahan menggunakan gerobak untuk menjual Apel dan Pisang. Harga pebelian Apel Rp20.000 per kg dan Pisang Rp8.000 per kg. Modal yang tersedia Rp5.000.000. Sedangkan muatan gerobaknya tidak dapat melebihi 400 kg. Keuntungan Apel Rp3.000 per kg sedangkan Pisang Rp2.000. Agar pedagang mendapat keuntungan sebesar-besarnya, berapa banyak Apel dan Pisang yang harus dibeli pedagang?
Penyelesaian:
Misalkan harga 1 kg Apel = x dan harga 1 kg Pisang = y, maka diperoleh
20000x + 8000y ≤ 5000000 atau 5x + 2y ≤ 1250
x + y ≤ 400
x ≥ 0
y ≥ 0
Fungsi Objektif : 3000x + 2000y
Gambar grafik
Titik potong garis 5x + 2y =1250 dan x + y = 400 dapat ditentukan dengan
Eliminasi x
Substitusi x = 150 ke persamaan x + y = 400
150 + y = 400
y = 250
Jadi, titik potongnya (150, 250)
Sehingga, diperoleh empat titik pojok (0, 0), (250, 0), (150, 250), dan (0, 400).
Dari tabel terlihat bahwa fungsi objektif maksimum sebesar 950000. Dengan kata lain hal itu menunjukkan keuntungan paling besar yang dapat diperoleh pedagang. Jadi, banyak Apel dan Pisang yang harus dibeli agar pedagang mendapat keuntungan mmaksimum berturut-turut adalah 150 kg dan 250 kg.
Demikian tadi mengenai, menyelesaikan masalah program linear dengan menggunakan metode uji titik pojok. Semoga dapat dipahami dan bermanfaat.
Eliminasi x
Substitusi x = 150 ke persamaan x + y = 400
150 + y = 400
y = 250
Jadi, titik potongnya (150, 250)
Sehingga, diperoleh empat titik pojok (0, 0), (250, 0), (150, 250), dan (0, 400).
Dari tabel terlihat bahwa fungsi objektif maksimum sebesar 950000. Dengan kata lain hal itu menunjukkan keuntungan paling besar yang dapat diperoleh pedagang. Jadi, banyak Apel dan Pisang yang harus dibeli agar pedagang mendapat keuntungan mmaksimum berturut-turut adalah 150 kg dan 250 kg.
Demikian tadi mengenai, menyelesaikan masalah program linear dengan menggunakan metode uji titik pojok. Semoga dapat dipahami dan bermanfaat.
