Jika Anda seorang insinyur atau mahasiswa teknik, Anda mungkin tahu apa artinya mengoptimalkan.
Untuk mendapatkan hasil terbaik, penting untuk menemukan cara terbaik untuk melakukan sesuatu.
Dalam pemrograman linier, Anda dapat menggunakan solusi dasar untuk menemukan solusi terbaik.
Tapi apa itu solusi dasar, dan mengapa sangat penting bagi para insinyur untuk mengetahuinya? Dalam artikel ini, saya akan berbicara tentang apa itu solusi dasar, mengapa solusi itu penting dalam teknik, dan bagaimana solusi tersebut dapat digunakan untuk mendapatkan hasil terbaik dalam berbagai situasi.
Jadi kencangkan sabuk pengaman dan bersiaplah untuk terjun ke dunia solusi dasar, di mana saya akan membongkar misterinya dan menunjukkan betapa hebatnya teknik ini.
Solusi Dasar dalam Pemrograman Linear
Definisi formal:
Solusi untuk model program linier yang terdiri dari m persamaan dalam n variabel diperoleh dengan memecahkan m variabel dalam bentuk variabel (nm) yang tersisa dan menyetel variabel (nm) sama dengan nol.
Solusi dasar dalam pemrograman linier adalah cara untuk memecahkan masalah pemrograman linier yang memenuhi persyaratan teknis tertentu.
Secara khusus, vektor x adalah solusi dasar untuk polihedron jika vektor {ai : xi = 0} bebas linier.
Ini berarti bahwa kolom-kolom A yang memiliki variabel xi yang tidak nol adalah bebas linier.
Solusi dasar dengan komponen nonnegatif disebut solusi layak dasar (BFS) (BFS).
BFS memenuhi semua aturan yang mendefinisikan polihedron.
Setiap BFS adalah sudut polihedron dari solusi yang layak dari sudut pandang geometris.
Untuk menemukan solusi dasar, Anda harus mengatur nm variabel yang tidak dasar menjadi nol dan menyelesaikan m variabel yang dasar.
Basis yang berbeda dapat mengarah ke solusi dasar yang sama, yang berarti bahwa mungkin ada lebih dari satu cara untuk menyelesaikan masalah yang sama.
Metode Simplex adalah proses iteratif yang berpindah dari satu BFS ke BFS berikutnya hingga menemukan BFS terbaik.
Setelah menggunakan metode simpleks untuk menemukan BFS, kita dapat mengetahui apakah solusinya adalah yang terbaik dengan melihat apakah ada BFS terdekat yang memberikan nilai yang lebih baik untuk fungsi tujuan.
Jika tidak ada BFS seperti itu, maka BFS saat ini adalah yang terbaik.
Model Pemrograman Linear
Model pemrograman linier melibatkan tiga komponen utama: variabel keputusan, fungsi tujuan, dan kendala.
Baik fungsi tujuan maupun kendala harus merupakan fungsi linier, dan variabel keputusan harus kontinu.
Fungsi tujuan digunakan untuk menambah atau mengurangi angka yang mewakili laba, biaya, jumlah produk yang dibuat, dll.
Kendala adalah batasan atau pembatasan jumlah total sumber daya tertentu yang diperlukan untuk melakukan tugas-tugas yang akan menentukan tingkat keberhasilan dalam variabel keputusan.
Selain itu, beberapa program linier mensyaratkan bahwa semua variabel keputusan tidak negatif.
Dalam model pemrograman linier, Anda juga dapat menggunakan variabel bilangan bulat dan biner.
Variabel biner hanya dapat memiliki nilai 0 atau 1, sehingga hanya dapat memiliki nilai 0 atau 1.
Metode Simpleks
Salah satu cara yang paling sering digunakan untuk menyelesaikan masalah program linier adalah Metode Simpleks.
Solusi dasar penting dalam metode simpleks karena sesuai dengan titik sudut daerah layak, dan metode simpleks berpindah dari satu sudut ke sudut lainnya hingga solusi optimal ditemukan.
Metode simpleks adalah cara cepat untuk menemukan jawaban terbaik untuk masalah pemrograman linier dengan menggunakan sifat-sifat solusi dasar.
Untuk menggunakan metode simpleks untuk menemukan BFS terbaik, kita perlu menemukan basis B untuk matriks kendala A dan menyelesaikan sistem Ax = b dengan semua variabel selain basis yang ditetapkan ke nol.
Nilai yang dihasilkan untuk variabel dasar membentuk BFS.
Jika terdapat solusi optimal, maka terdapat BFS optimal.
Metode Simplex berpindah dari satu BFS ke BFS yang berdekatan hingga mencapai BFS optimal dengan menggunakan prosedur pivot.
Perbandingan antara Solusi Dasar dan Solusi Layak
Perbedaan antara solusi dasar dan solusi layak adalah bahwa solusi dasar tidak harus memenuhi kondisi apa pun.
Secara khusus, ia harus memiliki vektor yang bebas linier dan memiliki nilai bukan nol untuk xi, dan x harus lebih kecil dari 0.
Di sisi lain, solusi yang layak adalah setiap titik yang sesuai dengan batas-batas masalah.
Tetapi tidak semua solusi layak adalah solusi layak dasar.
Solusi layak dasar (BFS) hanya yang cocok dengan sudut polihedron dari solusi layak.
Kembali ke Dasar: Membuka Kunci Kekuatan Solusi Dasar dalam Rekayasa
Masih sulit dimengerti? Biarkan saya mengubah sudut pandang sedikit:
Apakah Anda bosan menggunakan metode dan algoritme yang rumit untuk menyelesaikan masalah yang sulit? Apakah Anda berharap ada cara yang lebih sederhana dan mudah untuk menangani masalah model program linear Anda?
Nah, jangan khawatir, karena jawabannya ada di sini: selesaikan m variabel dalam variabel (nm) yang tersisa, dan atur variabel (nm) ke nol.
Siapa yang butuh algoritme yang terdengar mewah saat Anda bisa kembali ke dasar? Jadi singkirkan kalkulator Anda dan mari mulai belajar tentang solusi sederhana.
Oke, itu hanya lelucon yang dibuat agar terlihat seperti iklan TV.
Sekarang mari kita kembali ke penjelasannya.
Pemrograman Linear Solusi Dasar
Tip: Nyalakan tombol keterangan jika Anda membutuhkannya. Pilih "terjemahan otomatis" di tombol pengaturan, jika Anda tidak terbiasa dengan bahasa lisan. Anda mungkin perlu mengeklik bahasa video terlebih dahulu sebelum bahasa favorit Anda tersedia untuk diterjemahkan.
Kasus penggunaan
| Digunakan dalam: | Keterangan: |
|---|---|
| Alokasi Sumber Daya: | Solusi dasar dapat digunakan dalam masalah alokasi sumber daya, di mana tujuannya adalah membagi sumber daya yang terbatas di antara kebutuhan yang bersaing. Misalnya, sebuah perusahaan mungkin perlu membagi anggarannya di antara departemen atau proyek yang berbeda. Dengan menggunakan solusi dasar, mereka dapat mengetahui cara terbaik untuk menggunakan sumber daya mereka untuk menghasilkan uang paling banyak atau membelanjakan sesedikit mungkin. |
| Perencanaan Produksi: | Dalam perencanaan produksi, solusi dasar dapat digunakan untuk mengetahui campuran produk terbaik yang akan dibuat untuk menghasilkan uang paling banyak. Perusahaan dapat menemukan bauran produksi terbaik yang menghasilkan uang paling banyak dan biaya paling sedikit dengan menggunakan solusi dasar. |
| Penjadwalan: | Solusi dasar dapat digunakan untuk mengetahui cara menjadwalkan tugas atau pekerjaan sehingga dapat dilakukan dengan cara yang paling efisien. Misalnya, sebuah perusahaan mungkin perlu merencanakan jam kerja karyawannya untuk memastikan mereka memiliki cukup pekerja saat bisnis sedang sibuk. Dengan menggunakan solusi dasar, mereka dapat mengetahui cara terbaik untuk menjadwalkan berbagai hal sehingga waktu henti sesedikit mungkin dan sebanyak mungkin pekerjaan diselesaikan. |
| Manajemen Rantai Pasokan: | Dalam manajemen rantai pasokan, tujuannya adalah untuk memastikan bahwa barang dan jasa bergerak semulus mungkin dari pemasok ke pelanggan. Misalnya, sebuah bisnis mungkin perlu mengetahui rute terbaik untuk mengangkut barang sehingga biaya dapat ditekan seminimal mungkin dan barang dikirim tepat waktu. Dengan menggunakan solusi dasar, mereka dapat menemukan rencana terbaik untuk mengelola rantai pasokan yang menekan biaya dan membuat pelanggan senang. |
| Pengoptimalan Portofolio: | Dalam pengoptimalan portofolio, di mana tujuannya adalah menemukan campuran investasi terbaik untuk menghasilkan uang paling banyak sambil mengambil risiko paling kecil, solusi dasar dapat digunakan. Misalnya, sebuah perusahaan investasi mungkin perlu memikirkan campuran terbaik dari saham, obligasi, dan sekuritas lainnya untuk membantu klien mereka mencapai tujuan investasi mereka. Dengan menggunakan solusi sederhana, mereka dapat menemukan cara terbaik untuk memadukan portofolio mereka sehingga mereka mendapatkan pengembalian terbaik sambil mengambil risiko paling sedikit. |
Kesimpulan
Kesimpulannya, ide solusi dasar sangat penting dalam bidang teknik dan dapat digunakan dengan berbagai cara.
Dengan mengetahui apa itu solusi dasar dan apa fungsinya dalam pemrograman linier, kita dapat meningkatkan solusi, memangkas biaya, dan membuatnya lebih efisien.
Namun penting untuk diingat bahwa solusi dasar bukanlah solusi satu ukuran untuk semua, meskipun merupakan alat yang ampuh.
Untuk mendapatkan hasil terbaik, setiap masalah perlu diperhatikan dan dipikirkan dengan cermat.
Sebagai teknisi, kami perlu terus mencari tahu bagaimana solusi dasar dan teknik pengoptimalan lainnya dapat membantu kami membuat kemajuan dan menghasilkan ide baru.
Jadi, mari kenali kekuatan solusi sederhana dan terus dorong batas dari apa yang mungkin dilakukan dengan menggunakan teknik dan strategi baru.
Tautan dan referensi
Buku:
- Pemrograman Linier oleh Vasek Chvatal
- Pemodelan dan Pemecahan Pemrograman Linear dengan R oleh Jose M. Sallan
Bagikan pada…
