Laman

AddThis Smart Layers

6.8. Pemrograman linear


Mengoptimalkan Resources Limited Anda


Manfaatkan sumber daya yang tersedia.


Jika Anda hanya punya sumber daya yang terbatas yang Anda inginkan, maka itu membantu untuk menghitung bagaimana cara terbaik untuk memaksimalkan sumber daya - apakah itu waktu, uang, atau ruang.

Katakanlah, misalnya, bahwa Anda memiliki 50 sq.ft ruang kantor digunakan untuk penyimpanan.

Anggaran Anda adalah $ 2000, dan ada berbagai jenis dan ukuran lemari dari yang untuk memilih. Bagaimana Anda mengoptimalkan ruang yang telah tersedia, dan tetap dalam anggaran yang diberikan?

Atau misalkan Anda memiliki tiga truk pengiriman, dan 10 drop-off poin. Bagaimana Anda merencanakan rute yang paling efisien dan jadwal untuk truk ini?

Atau menganggap bahwa Anda memproduksi tiga produk menggunakan bahan baku dasar yang sama. Namun, seperti setiap produk menggunakan jumlah dari materi yang berbeda, beberapa lebih mahal untuk diproduksi daripada yang lain. Beberapa bahan-bahan mudah rusak, dan perlu digunakan dengan cepat. Berapa banyak produk masing-masing harus Anda memproduksi untuk meminimalkan biaya Anda? Dan bagaimana kombinasi yang menghasilkan limbah yang sedikit?

Pertanyaan seperti ini mungkin tampak sangat kompleks. Dengan begitu banyak variabel dan kendala untuk mempertimbangkan, bagaimana Anda memutuskan apa yang harus dilakukan? Jawabannya adalah dengan menggunakan linear programming (LP).

Pemrograman linier adalah teknik matematika yang menentukan cara terbaik untuk menggunakan sumber daya yang tersedia. Manajer menggunakan proses untuk membantu membuat keputusan tentang penggunaan yang paling efisien sumber daya yang terbatas - seperti uang, waktu, bahan, dan mesin.

Catatan: Anda dapat menggunakan pemrograman linear hanya jika ada hubungan linear diantara variabel-variabel yang Anda cari. Hubungan adalah linear jika unit perubahan terhubung dengan jumlah konstan perubahan unit2 lainnya. Pada grafik, hubungan linear ditampilkan sebagai garis lurus.

Teknik Pemrograman Linear

Pemrograman linear sering merupakan topik favorit bagi dosen dan mahasiswa. Kemampuan untuk memperkenalkan LP menggunakan pendekatan grafis, kemudahan relatif dari metode solusi, ketersediaan luas paket perangkat lunak LP, dan berbagai aplikasi membuat LP diakses bahkan untuk siswa dengan latar belakang matematika yang relatif lemah. Selain itu, LP memberikan kesempatan yang baik untuk memperkenalkan gagasan "bagaimana-jika" analisis, karena alat-alat canggih untuk pasca-optimalitas analisis yang dikembangkan untuk model LP.

Linear Programming (LP) adalah prosedur matematika untuk menentukan alokasi optimal sumber daya yang langka. LP adalah suatu prosedur yang telah menemukan aplikasi praktis di hampir semua aspek bisnis, dari iklan untuk perencanaan produksi. Transportasi, distribusi, dan masalah-masalah perencanaan produksi agregat adalah objek paling khas dari analisis LP. Dalam industri perminyakan, misalnya pengolahan data manajer di sebuah perusahaan minyak besar baru ini memperkirakan bahwa dari 5 sampai 10 persen waktu komputer perusahaan dikhususkan untuk pengolahan LP dan LP-seperti model.

Kesepakatan pemrograman linear dengan kelas masalah pemrograman di mana kedua fungsi tujuan yang akan dioptimalkan adalah linier dan semua hubungan antara variabel-variabel yang sesuai dengan sumber daya adalah linear. Masalah ini pertama kali dirumuskan dan diselesaikan pada akhir 1940-an. Jarang memiliki teknik matematika baru ditemukan seperti berbagai macam bisnis praktis, perdagangan, dan aplikasi industri dan sekaligus menerima begitu menyeluruh perkembangan teoritis, dalam periode waktu yang singkat. Hari ini, teori ini sedang berhasil diterapkan untuk masalah penganggaran modal, desain diet, konservasi sumber daya, strategi permainan, prediksi pertumbuhan ekonomi, dan sistem transportasi. Dalam waktu yang sangat terakhir, teori pemrograman linier juga membantu menyelesaikan dan menyatukan aplikasi banyak beredar.

Hal ini penting bagi pembaca untuk menghargai, di awal, bahwa "program" dalam Pemrograman Linear adalah sebuah rasa yang berbeda dari "pemrograman" dalam Pemrograman Komputer. Dalam kasus mantan, itu berarti untuk merencanakan dan mengatur seperti dalam "Dapatkan dengan program!", Itu program Anda dengan solusinya. Sementara dalam kasus yang terakhir, itu berarti untuk menulis kode untuk melakukan perhitungan. Pelatihan satu jenis pemrograman memiliki relevansi langsung sangat sedikit untuk yang lain. Bahkan, "pemrograman linier" Istilah ini diciptakan sebelum kata "pemrograman" menjadi erat terkait dengan perangkat lunak komputer. Kebingungan ini kadang-kadang dihindari dengan menggunakan optimasi linier istilah sebagai sinonim untuk pemrograman linear.

Masalah LP terdiri dari sebuah fungsi objektif dan satu set kendala. Dalam kebanyakan kasus, kendala datang dari lingkungan di mana Anda bekerja untuk mencapai tujuan Anda. Bila Anda ingin mencapai tujuan yang diinginkan, Anda akan menyadari bahwa lingkungan adalah pengaturan beberapa kendala (yaitu, kesulitan, pembatasan) dalam memenuhi keinginan Anda atau tujuan. Inilah sebabnya mengapa agama-agama seperti Buddha, antara lain, meresepkan menjalani hidup hemat. Tidak ada keinginan, tidak sakit. Bisakah Anda mengambil nasihat ini sehubungan dengan tujuan bisnis Anda?

fungsi: adalah hal yang melakukan sesuatu. Sebagai contoh, mesin penggiling kopi adalah fungsi yang mengubah biji kopi menjadi bubuk. Peta fungsi (tujuan) dan menerjemahkan domain masukan (disebut daerah layak) ke kisaran output, dengan dua nilai akhir yang disebut maksimum dan nilai minimum.
Ketika Anda merumuskan masalah pengambilan keputusan sebagai program linier, Anda harus memeriksa kondisi berikut:
  1. Fungsi objektif harus linier. Artinya, memeriksa apakah semua variabel yang memiliki kekuatan 1 dan mereka ditambahkan atau dikurangi (tidak dibagi atau dikalikan)
  2. Tujuannya harus baik memaksimalkan atau minimisasi fungsi linear. Tujuan harus menggambarkan tujuan dari pembuat keputusan-
  3. Kendala juga harus linear. Selain itu, kendala harus menjadi bentuk berikut (£, ³, atau =, yaitu LP-kendala yang selalu tertutup).
Sebagai contoh, masalah berikut bukan LP: Max X, tunduk ke X <1. Ini masalah yang sangat sederhana tidak memiliki solusi.

Seperti biasa, kita harus berhati-hati dalam mengkategorikan masalah optimasi sebagai masalah LP. Berikut adalah pertanyaan untuk Anda. Apakah masalah berikut masalah LP?
Max X2
tunduk pada:
X1 + X2 £ 0
X1 2 - 4 £ 0
Meskipun kendala kedua tampak "seolah-olah" itu adalah kendala nonlinier, kendala ini ekuivalen dapat ditulis sebagai:
X1 ³ -2, dan X2 £ 2.
Oleh karena itu, masalah di atas memang masalah LP.

Untuk masalah LP paling banyak satu bisa memikirkan dua kelas penting dari objek: Yang pertama adalah sumber daya terbatas seperti tanah, kapasitas pabrik, atau ukuran tenaga penjualan, yang kedua, adalah kegiatan seperti "memproduksi baja karbon rendah", "menghasilkan stainless steel" , dan "memproduksi baja karbon tinggi". Setiap kegiatan mengkonsumsi atau mungkin menyumbang jumlah tambahan sumber daya. Harus ada sebuah fungsi objektif, yaitu cara untuk mengetahui buruk dari yang baik, dari keputusan yang lebih baik. Masalahnya adalah untuk menentukan kombinasi terbaik dari tingkat aktivitas, yang tidak menggunakan sumber daya lebih dari yang benar-benar tersedia. Banyak manajer dihadapkan dengan tugas sehari-hari. Untungnya, ketika sebuah model baik dirumuskan adalah input, perangkat lunak pemrograman linier membantu untuk menentukan kombinasi terbaik.

Metode Simplex adalah algoritma solusi banyak digunakan untuk menyelesaikan program linier. Algoritma adalah serangkaian langkah-langkah yang akan menyelesaikan tugas tertentu.



Proses Perumusan Masalah LP dan Aplikasinya

Untuk merumuskan masalah LP, saya sarankan menggunakan panduan berikut setelah membaca pernyataan masalah dengan hati-hati beberapa kali.

Setiap program linier terdiri dari empat bagian: satu set variabel keputusan, parameter, fungsi tujuan, dan satu set kendala. Dalam merumuskan masalah keputusan yang diberikan dalam bentuk matematis, Anda harus berlatih memahami masalah (yaitu, merumuskan model mental) dengan hati-hati membaca dan membaca ulang pernyataan masalah. Ketika mencoba untuk memahami masalah, tanyakan pada diri Anda pertanyaan-pertanyaan umum berikut:
  1. Apa itu variabel keputusan? Artinya, apa input yang dikendalikan? Tentukan variabel keputusan yang tepat, menggunakan nama deskriptif. Ingat bahwa input dikontrol juga dikenal sebagai aktivitas dikontrol, variabel keputusan, dan kegiatan keputusan.
  2. Apa itu parameter? Artinya, input apa yang tak terkendali? Ini biasanya nilai yang diberikan numerik konstan. Tentukan parameter tepat, menggunakan nama deskriptif.
  3. Apa tujuannya? Apakah fungsi obyektif? Juga, apakah pemilik masalah inginkan? Bagaimana tujuannya adalah terkait dengan variabel keputusannya? Apakah masalah maksimisasi atau minimisasi? Tujuan ini merupakan tujuan dari pembuat keputusan.
  4. Apa hambatannya? Artinya, apa persyaratan yang harus dipenuhi? Apakah saya harus menggunakan ketidaksetaraan atau jenis persamaan kendala? Apa hubungan antara variabel? Tuliskan dalam kata-kata sebelum menempatkan mereka dalam bentuk matematika.
Pelajari bahwa daerah layak tidak ada atau sedikit hubungannya dengan fungsi tujuan (min atau max). Kedua bagian dalam setiap formulasi LP kebanyakan berasal dari dua sumber yang berbeda dan berbeda. Fungsi tujuan ditetapkan untuk memenuhi keinginan pembuat keputusan (obyektif), sedangkan kendala yang membentuk daerah layak biasanya berasal dari lingkungan pembuat keputusan menempatkan beberapa pembatasan / kondisi pada pencapaian nya / tujuannya.

Aplikasi LP  umum lainnya

Pemrograman linier adalah alat yang ampuh untuk memilih alternatif dalam masalah keputusan dan, akibatnya, telah diterapkan dalam berbagai pengaturan masalah. Kami akan menunjukkan beberapa aplikasi meliputi bidang fungsional utama dari sebuah organisasi bisnis.

Keuangan: Masalah investor bisa menjadi masalah seleksi portofolio-campuran. Secara umum, jumlah portofolio yang berbeda dapat jauh lebih besar daripada contoh menunjukkan, lebih banyak jenis dan berbeda dari kendala dapat ditambahkan. Masalah lain yang menentukan keputusan melibatkan campuran dana untuk sejumlah produk ketika lebih dari satu metode pembiayaan yang tersedia. Tujuannya mungkin untuk memaksimalkan keuntungan total, di mana keuntungan untuk produk yang diberikan tergantung pada metode pembiayaan. Sebagai contoh, pendanaan dapat dilakukan dengan dana internal, utang jangka pendek, atau pembiayaan menengah (pinjaman diamortisasi). Mungkin ada batasan pada ketersediaan dari masing-masing opsi pendanaan serta kendala keuangan memerlukan hubungan tertentu antara opsi pendanaan sehingga untuk memenuhi persyaratan pinjaman bank atau pembiayaan menengah. Mungkin juga ada batasan pada kapasitas produksi untuk produk. Variabel keputusan akan menjadi jumlah unit masing-masing produk yang akan dibiayai oleh masing-masing opsi pendanaan.

Manajemen Produksi dan Operasi: Cukup sering dalam proses industri bahan baku tertentu dapat dibuat menjadi berbagai macam produk. Sebagai contoh, dalam industri minyak, minyak mentah disempurnakan menjadi bensin, minyak tanah, minyak pemanas rumah, dan berbagai kelas oli mesin. Mengingat margin keuntungan hadir pada setiap produk, masalah ini adalah untuk menentukan jumlah setiap produk yang harus diproduksi. Keputusan ini tunduk pada pembatasan banyak seperti batas pada kapasitas penyulingan berbagai operasi, ketersediaan bahan baku, permintaan untuk setiap produk, dan setiap pemerintah memaksakan kebijakan-kebijakan pada output dari produk tertentu. Masalah serupa juga ada di industri kimia dan pengolahan makanan.

Sumber Daya Manusia: Personil masalah perencanaan juga dapat dianalisis dengan pemrograman linier. Sebagai contoh, dalam industri telepon, tuntutan untuk layanan dari installer-perbaikan personil musiman. Masalahnya adalah untuk menentukan jumlah personil installer-perbaikan-perbaikan dan garis personil untuk memiliki pada tenaga kerja setiap bulan di mana total biaya perekrutan, PHK, lembur, dan teratur-waktu upah diminimalkan. Set kendala termasuk pembatasan pada tuntutan layanan yang harus dipenuhi, penggunaan waktu lembur, kesepakatan serikat pekerja, dan ketersediaan orang terampil untuk disewa. Contoh ini bertentangan dengan asumsi dibagi, namun karya-kekuatan tingkat untuk setiap bulan biasanya cukup besar sehingga pembulatan ke integer terdekat dalam setiap kasus tidak akan merugikan, asalkan kendala tidak dilanggar.

Pemasaran: pemrograman linear dapat digunakan untuk menentukan campuran yang tepat dari media untuk digunakan dalam kampanye iklan. Misalkan bahwa media yang tersedia adalah radio, televisi, dan surat kabar. Masalahnya adalah untuk menentukan berapa banyak iklan untuk tempat di setiap media. Tentu saja, biaya menempatkan iklan tergantung pada media yang dipilih. Kami ingin meminimalkan total biaya kampanye iklan, tunduk pada serangkaian kendala. Karena setiap media dapat memberikan tingkat yang berbeda dari pemaparan dari populasi sasaran, mungkin ada yang lebih rendah terikat pada pajanan total dari kampanye. Juga, setiap media mungkin memiliki peringkat efisiensi yang berbeda dalam memproduksi hasil yang diinginkan, ada dengan demikian dapat lebih rendah terikat pada efisiensi. Selain itu, mungkin ada batasan pada ketersediaan masing-masing media untuk iklan.

Distribusi: Aplikasi lain dari pemrograman linear di bidang distribusi. Pertimbangkan kasus di mana ada pabrik m yang harus kapal barang ke gudang n. Sebuah pabrik yang diberikan bisa membuat pengiriman ke sejumlah gudang. Mengingat biaya untuk kapal satu unit produk dari pabrik ke gudang masing masing, masalahnya adalah untuk menentukan pola pengiriman (jumlah unit yang masing-masing pabrik kapal ke gudang masing-masing) yang meminimalkan total biaya. Keputusan ini adalah tunduk pada pembatasan bahwa permintaan di pabrik masing-masing tidak dapat mengirimkan produk lebih dari itu memiliki kapasitas untuk memproduksi.