Tutorial Linear programming merupakan suatu panduan tools yang dapat memberikan solusi saat anda berhadapan dengan linear programming. Linear programming digunakan karena otak manusia terbatas untuk memikirkan beberapa kendala dalam waktu yang bersamaan. Jika anda salah satu yang merasa bingung dengan rumus dalam linear programming, simak baik – baik penjelasan dan tutorial linear progamming pada artikel ini.
Sebagai langkah awal saya memberikan sebagai ilustrasi : jika anda memiliki uang sejumlah 1000. Kemudian ada pilihan produk yang akan anda beli; yakni produk A dengan harga 100 dan produk B dengan harga 200. Berapa produk A dan B yang harus anda beli jika anda menginginkan membeli dalam jumlah yang banyak? Tentu anda akan membeli produk A sejumlah 10 buah. Jawabannya akan berbeda jika ada syarat tambahan bahwa minimal produk B adalah 2 buah.
Permasalahan tersebut pada dasarnya masih sangat sederhana, dan mampu segera diatasi dengan mudah. Namun, jika kita menjumpai nilai produknya diatas 10 variabel, dengan masing masing variabel memiliki batas kendala masing – masing, tentunya kita harus menggunakan alat bantuan unttuk menyelesaikannya. Salah satu alat yang sering digunakan adalah linear programming.
Linear programming dapat digunakan dalam berbagai institusi. Misalnya perusahaan yang ingin memaksimalkan laba, perusahaan yang ingin menekan biaya, pemerintah yang ingin menambah luas tanam, berapa nilai harga jual optimal dari sebuah produk, dan lain – lain.
Konsep dasar
Konsep dasar permasalahan linear programming sebenarnya sudah diberikan saat kita mengikuti bangku sekolah pada tingkat Sekolah Menengah Atas. Anda tentu pernah mendengar pertidaksamaan matematika dengan variabel X dan Y bukan? Misalnya saja:
Tentukan nilai x yang bersesuaian dengan pertidaksamaan berikut:
X2 + x -2 >0, jawabnya adalah:
X2 + x -2 >0
(x+2) (X-1) >0
X = -2, x = 1
-2<x<1
Masih banyak lagi contoh yang lain yang tidak perlu saya bahas disini. Contoh soal diatas merupakan pertidaksamaan matematika yang sering tidak dipahami oleh siswa selama sekolah apa manfaatnya. Karena terlalu fokus memikirkan bagaimana cara penyelesainnya. Padahal, setelah kuliah justru alasan mengapa menggunakan pertidaksamaan menjadi lebih penting karena perhitungan detilnya sudah dibantu oleh alat hitung atau komputer.
Konsep dasar lainnya yang menurut saya sangat erat dengan linear programming adalah grafik. Pada dasarnya jawaban suatu masalah linear programming merupakan suatu titik yang paling optimal dari beberapa grafik yang saling bersinggungan. Grafik – grafik yang bersinggungan tersebut membentuk suatu daerah yang diarsir. Daerah tersebut merupakan pilihan – pilihan dari nilai Y yang sesuai dengan batasan – batasan masalah.
Perhatikan grafik berikut:
Grafik pertidaksamaan
Pada gambar 1 terlihat bahwa terdapat sebuah garis y <3. Daerah yang bersesuaian dengan pertidaksamaan tersebut adalah daerah yang diarsir. Daerah yang diarsir ini masih luas jika dipanjangkan terus ke samping kanan dan kiri
Daerah yang diarsir pada gambar 1 mulai dibatasi oleh pertidaksamaan yang kedua dengan pertidaksamaan x < 5. Daerah yang diarsir menjadi sedikit lebih sempit. Namun, pilihan – pilihan yang bersesuaian dengan kedua pertidaksamaan masih sangat banyak. Misalnya saja titk (1,1), (2,2) (1,2), (2,1) dsb yang masih didalam daerah yang diarsir.
Pada gambar ketiga, mulailah terlihat titik yang dimaksud, karena pada gambar ini terdapat sebuah grafik pertidaksamaan yang ketiga yakni X< Y. daerah yang diarsir pun semakin sempit. Daerah yang diarsir tersebut merupakan jawaban dari ketiga pertidaksamaan matematika. Sekarang tergantung goal atau tujuan dari permasalahan; apakah ingin memaksimalkan nilai Y ataukah ingin memaksimalkan nilai X.
Jika goal atau tujuan dari ketiga pertidaksamaan tersebut adalah ingin memaksimalkan nilai X maka titik B dan C merupakan titik batas atas yang bisa memaksimalkan nilai X. namun, jika tujuannya adalah ingin memaksimalkan nilai Y maka titi A dan B merupakan pilihan dari batas atas untuk memaksimalkan nilai Y sesuai tujuan.
Jika anda mengerti terhadap ilustrasi contoh permasalahan diatas, maka saya yakin anda akan mengerti bagaimana cara kerja linear programming dalam menyelesaikan masalah. Benar. Linear programming sesuai namanya selalu menggunakan garis lurus. Garis – garis lurus tersebut membatasi suatu daerah yang diarsir, kemudian LP (linear programming) menentukan mana titik yang paling ideal sesuai dengan tujuan yang kita inginkan.
Syarat – syarat Program linear programming
LP memiliki sebuah syarat agar permasalahan dapat diselesaikan dengan baik. Syarat syarat tersebut adalah:
Tujuan masalah harus jelas
Tentukan tujuan masalah sejelas mungkin. LP biasanya mempunyai 2 pilihan tujuan yakni Max dan Min. Max adalah singkatan dari maximal artinya anda menginginkan nilai maksimal dari batasan – batasan yang anda miliki. Min dari singkatan minimal artinya anda menginginkan nilai minimal dari batasan yang anda miliki. Contoh paling mudah adalah maksimalkan keuntungan atau minimalkan biaya.
Memiliki beberapa alternatif
Jika anda memiliki tujuan memaksimalkan keuntungan, maka anda perlu memiliki beberapa produk sebagai pilihan untuk meningkatkan keuntungan tersbeut. LP tidak akan berjalan baik jika anda menginginkan keuntungan hanya dari sebuah produk saja. Tentu jawabnnya “silahkan anda menjual sebanyak-banyaknya”.
LP memerlukan sebuah kombinasi. Contoh paling simple adalah pada intro diatas. Anda memiliki uang 1000 dan ingin membeli 2 produk. 2 produk ini merupakan alternatif. Misal pada contoh minimalisasi biaya. Alternatif yag anda perlukan adalah jumlah tenaga kerja, jumlah bahan yang harus dibeli atau jumlah barang yang akan diproduksi sesuai dengan HPP masing – masing.
Ada batasan sumber daya
Setelah ada alternatf dan tujuan, anda harus merumuskan batasan. Batasan yang saya maksudkan adalah pertidaksamaan – pertidaksamaan yang seperti contoh sudah saya jelaskan. Biasanya, saya perhatikan jika tujuan anda adalah memaksimalkan, maka pertidaksamaan didominasi oleh tanda kurang dari atau lebih kecil dari ..
Contoh : maksimalkan laba dari tiga produk (x,y,z) . x memberikan keuntungan 300, y memberikan keuntungan 400/produk, dan z memberikan keuntungan 500/produk. Maka pertidaksamaan bisa diawali dengan berapa batas maksimal X, Y, dan Z yang harus dijual. Karena, jika anda tidak mengatur batas maksimal ini, LP akan memberi masukan maksimalkan laba dengan nilai keuntungan paling tinggi dari ketiga produk tersebut, yakni LP pasti akan memberikan saran menjual produk z sebanyak – bnayaknya. Bahkan nilai x dan y bisa kemungkinan akan 0.
Namun jika anda memberi batasan bahwa nilai z tidak boleh melebihi angka tertentu karena kapastias produksi dan produk x dan y juga harus diproduksi karena keberlangsungan produk dan adanya perjanjian kerjasama misalnya, maka LP akan memberikan hasil yang lebih bervariasi. Pada akhir artikel ini seperti biasa kita akan berlatih bersama.
Note : batas maksimal berarti Z < konstanta (tanda lebih kecil atau kurang dari)
Selanjutnya, jika tujuan yag anda miliki merupakan tujuan minimalisasi, maka sebaiknya anda memperbanyak pertidak samaan dengan tanda lebih dari atau lebih besar dari …
Sebagai contoh: minimalkan biaya. Maka pertidaksamaan yang harus anda pikirkan pertama kali adalah berapa minimal setiap faktor produksi yag anda gunakan. Karena jika tidak ada batas minimal, pastinya LP tidak berjalan baik karena LP akan memberikan masukan 0 setiap faktor produksi.
Note : batas minimal bererti x > konstanta (tanda lebih besar atau lebih dari).
Pahami trik pembuatan batasan sumber daya ini, karena banyak sekali problem LP dari kurang baiknya membuat batasan sumberdaya.
Ada keterkaitan peubah
Alternatif alternatif yang sudah disiapkan diatas harus memiliki hubungan. Anda tidak perlu kuatir tentang masalah multikolinearitas seperti yang dibahas pada regresi dalam uji asumsi klasik, karena semua hal itu tidak digunakan di LP.
Sebagai contoh misalnya x = 2Y; X+Y >15; dan lain – lain. Alternatif alternatif yang telah disebutkan tadi selain memiliki batasan juga harus memiliki hub satu sama lain, sehingga terdapat nilai yang dapat dijelaskan oleh LP.
Dapat dibuat persamaan atau pertidaksamaan
LP merupakan salah satu analisis kuantitatif. Jadi, semua permasalahan, tujuan dan batas – batas masalah harus dapat dijelaskan secara kuantitatif. Dalam LP tidak diperbolehkan adanya pernyataan setuju, tidak setuju atau ragu – ragu. Trik untuk mengatasi ini adalah gunakan batas lebih besar atau lebih kecil atau range tertentu jika anda tidak bisa memastikan berapa nilai batas sebuah alternatif.
Permasalah Utama LP
Saat anda kuliah atau sedang sekolah, biasanya anda diberi sebuah soal cerita, kemudian anda merangkumnya menjadi sebuah persamaan dan menyelesaikannya. Atau bahkan soal sudah dalam bentuk pertidaksamaan dan persamaan kemudian anda ditugaskan untuk menyelesaikannya.
Permasalahan utama saat anda menghadapi dunia yang sebenarnya adalah menemukan cerita dan mengkonversinya menjadi sebuah persamaan. Saat anda memutuskan untuk meneliti, maka tidak ada satu kata pun yang sudah siap anda baca. Anda akan dihadapkan oleh kondisi kenyataan yang tidak merespon jika anda tidak mengajukan pertanyaannya.
Disinilah hal yang paling sulit dari LP. Bagaimana kemampuan anda merekam suatu peristiwa dengan mata telinga dan panca indera lainnya untuk menjadikannya sebuah tujuan dan permasalahan dalam beberapa pertidaksamaan. Masalah perhitungan dan penyelesaian pertidaksamaan tersebut dapat dipercayakan oleh bantuan komputer yang akan membantu anda menghitung tanpa ada kesalahan.
Lalu bagaimana tips untuk menghadapi permasalahn tersebut? Mulailah dari syarat- syarat yang diajukan dan sudah saya jabarkan diatas. Apa tujuan peneliian, sebutkan alternatif – alternatifnya, tentukan batasan – batasan alternatif, apa hubungan antara alternatif, dan buat dalam bentuk persamaan atau pertidaksamaan.
Latihan dan Tutorial Linear Programming
Saya rasa cukup untuk penjelasan LP. Mari kita latihan linear programming. Saya menggunakan sebuah software Lindo versi 6.1. Simak baik baik contoh soal pada tutorial linear programming berikut
Perusahaan AGUNGMASUKSURGA ingin memaksimalkan keuntungan. Produk yang dihasilkan ada 5 item. a, b, c, d, dan e. keuntungan masing masing produk adalah 200, 150, 180, 300, dan 100. Jika a dan b diproduksi harus bersamaan dengan outputnya a 2 kali lebih banyak dibanding b. Karena faktor bahan baku, produk c dan d (gabungan) tidak bisa melebihi 200. Permasalahan yang sama untuk produk a yang tidak bisa melebihi 150. Jumlah e pasti sama dengan a karena produk e merupakan hasil sampingan dari produk a. karena ada kesepakatan konsumen, harus membuat produk c minimal 10.
Tentukan nilai berapa produk yang harus dibuat oleh perusahaan AGUNGMASUKSURGA?
Mari kita bedah satu persatu.
- Maksimalkan keuntungan : tujuan
- keuntungan masing masing produk adalah 200, 150, 180, 300, dan 100, model tujuan yakni 200a + 150 b + 180c + 300d + 100e
- a outputnya 2 kali dari b, artinya a -2b =0
- faktor bahan baku, c dan d tidak lebih dari 200; artinya c+d < 200
- faktor bahan baku, a tidak bisa melebihi 150, artinya a <150
- e harus sama dengan a, artinya e = a atau e – a = 0
- kesepakatan konsumen, c minimal 10, artinya c > 10
- bilangan yang dimaksud pastinya bilangan bulat, sehingga perlu ditambahkan a >0, b > 0, d > 0, e >0.
Coba perhatikan contoh diatas sebelum kita memasukkan kedalam lindo, untuk memaksimalkan tujuan, kita memerlukan batasan atau constrain yang dalam hal ini adalah keterbatasan bahan baku. Pertidaksamaan yang membatasi umumnya bertanda lebih kecil dari seperti yang saya jelaskan sebelumnya. Ini trik yang harus anda perhatikan.
Mari kita buka lindo
Tampilan awal Lindo
Kemudian kita tulis perintahnya:
max
200a + 150b + 180c + 300d + 100e
subject to
a>0
b>0
c>10
d>0
e>0
a-2b=0
c+d<200
e-a=0
a<150
end
kata max menjelaskan tujuan, subject to merupakan kumpulan constraint dan end menyatakan perintah sudah diakhiri.
perintah dalam lindo
Kemudian pilih solve – solve. Ketika anda ditanya “do range analysis?” Klik saja yes
klik solve
Tunggu hingga keluar outputnya. Berikut output yang dihasilkan
hasil lindo
Dari gambar diatas dapat ditentukan bahwa LP memberikan saran kepada perusahaan:
- nilai laba maksimal yang dapat diperoleh adalah 115.050.
- nilai tersebut diperoleh dengan memproduksi a = 150 unit, b = 75 unit, c = 10 unit, D = 190 unit, dan E = 150 unit.
- reduced cost bernilai 0 : artinya jika nilai pengurangan maksimalisasi = 0 jika dilakukan pengurangan pada variabel. Pada contoh ini tidak dapat saya jelaskan detil karena semua bernilai 0. Pada prinsipnya reduced cost pada maksimisasi adalah pengurangan yang harus dibayar akbat mengurangi value satu satuan. Pada minimisasi dalah penambahan yang harus diterima akibat mengurangi value satu satuan
- slack atau surplus. Cara membaca slck or surplus adalah : nilai lebih atau kurang constrain yang diberikan dengan hasil. misalnya pada contoh ini a constrain atau batasnya adalah 0, b = 0, c = 10, d = 0, e = 0. Karena yang dihasilkan adalah a = 150, b = 75, c = 10, d = 190, dan E = 150, maka semua variabel selain c bernilai surplus sejumlah nilai value. Sedangkan variabel c bernilai 0 karena sesuai dengan batasnya, artinya LP mengambil sesuai dengan batas yang ditentukan.
- Dual prices : berapa tambahan funsi tujuan jika kendala atau constrain di naikkan satu satuan. Pada dual price kali ini terlihat pada variabel c sejumlah -120. Artinya jika kita naikkan constrain variabel c satu satuan , menjadi C > 11, maka akan kehilangan keuntungan sebesar 120 satuan.
Tidak berhenti sampai disitu saja, LP pada lindo ini juga memberi saran berapa nilai koefisien dalam hal ini adalah keuntungan /produk yang bisa diubah. Terlihat bahwa LP menghendaki adanya kenaikan keuntungan di semua produk kecuali variabel atau produk C. produk C karena paling kecil keuntungannya justru lindo menyarankan untuk menurunkan (allowable decrease). Seperti yang kita tahu, bahwa lindo mengeluarkan 10 satuan untuk C karena constrains yang mengharuskannya ( C < 10 )
RHS atau biasa disebut Right hand Side merupakan istilah dari nilai masing – masing constraint pada tabel paling bawah. Termasuk range atau nilai perubahan yang masih dibenarkan untuk naik (allowable increase) atau turun (allowable decrease). Jika memiliki keterangan infinity, berarti constraint tersebut bisa berubah angkanya berapa saja.
Demikian penjelasan saya tentang tutorial Linear Programming, lain kali semoga saya bisa membuat contoh untuk minimisasi.
Terima Kasih sudah berkunjung
