Anda tahu apa artinya mengoptimalkan sistem untuk mendapatkan hasil terbaik jika Anda seorang mahasiswa teknik atau insinyur.
Mengoptimalkan solusi adalah kunci sukses dalam segala hal mulai dari membangun jembatan hingga membuat perangkat lunak.
Gagasan tentang solusi dasar yang layak masuk pada titik ini.
Ini adalah ide dasar dalam pemrograman linier yang memungkinkan Anda mengetahui mana dari serangkaian solusi yang mungkin adalah yang terbaik.
Tapi mengapa itu sangat penting? Pada artikel ini, saya akan berbicara tentang solusi dasar yang layak dan bagaimana mereka dapat digunakan untuk memecahkan masalah teknik di dunia nyata.
Saya akan berbicara tentang cara menemukannya, terbuat dari apa, dan mengapa itu penting.
Jadi, apakah Anda seorang insinyur berpengalaman atau pelajar yang baru memulai, ikutlah bersama kami saat saya menyelami dunia solusi dasar yang layak dan menunjukkan kepada Anda cara menggunakan kekuatan pemrograman linier.
Memahami Dasar Solusi yang Layak
Definisi formal:
Solusi dasar untuk model program linier yang semua variabelnya tidak negatif.
Solusi layak dasar (BFS) adalah ide kunci dalam pemrograman linier yang membantu menemukan solusi terbaik.
BFS adalah solusi dengan jumlah variabel bukan nol sekecil mungkin.
Ini adalah sudut polihedron dari solusi yang layak.
Dengan kata lain, BFS adalah solusi dasar yang memenuhi kendala non-negatif dan berada di wilayah yang layak atau area masalah.
Menemukan Solusi Layak Dasar yang Optimal
Untuk menemukan BFS terbaik, kita perlu melakukan hal berikut:
- Tulis program dalam bentuk standar untuk urutan linier.
- Ubah sistem ketidaksetaraan menjadi matriks yang diperbesar.
- Cari tahu mana variabel dasar dan mana yang tidak.
- Cari tahu apa variabel dasar dalam kaitannya dengan variabel lain.
- Masukkan ekspresi ini ke dalam fungsi tujuan untuk mendapatkan fungsi hanya dari variabel yang tidak mendasar.
- Temukan variabel non-dasar yang dapat ditingkatkan tanpa melanggar batasan apa pun dan yang akan membuat fungsi tujuan menjadi lebih baik.
Variabel ini sekarang menjadi variabel dasar, dan salah satu variabel dasar lainnya tidak lagi menjadi variabel dasar.
Jika ada solusi optimal, itu harus di salah satu ujung, atau simpul, dari wilayah di mana solusi dimungkinkan.
Jadi, jika sebuah LP memiliki solusi optimal, ia memiliki solusi optimal pada titik ekstrim dari himpunan layak.
Juga, selalu ada BFS optimal jika ada solusi optimal.
Menggunakan Metode Simpleks untuk Menemukan BFS yang Optimal
Metode Simplex adalah algoritma untuk memecahkan masalah dalam pemrograman linier.
Itu berpindah dari satu BFS ke BFS "berdekatan" dengan menggunakan prosedur pivot.
Dalam prosedur pivot, variabel non-basis dipilih untuk menjadi variabel dasar, dan kemudian BFS saat ini digunakan untuk memecahkan variabel dasar yang baru.
Ketika tidak ada variabel non-dasar yang dapat diubah untuk membuat fungsi tujuan menjadi lebih baik, algoritme selesai.
Mengapa Solusi Dasar yang Layak Sangat Penting untuk Memecahkan Masalah Teknik yang Kompleks
Masih sulit dimengerti? Biarkan saya mengubah sudut pandang sedikit:
Siapa yang butuh jawaban yang sederhana dan bisa diterapkan? Lemparkan saja semuanya dan berharap yang terbaik.
Lagi pula, siapa yang butuh pengoptimalan saat kekacauan jauh lebih menyenangkan? Selamat datang di dunia variabel nonnegatif, di mana semuanya hanyalah sugesti dan kegagalan hampir pasti.
Atau itu?
Mari kita jelajahi mengapa konsep yang tampaknya mendasar dari solusi layak dasar sama sekali tidak mendasar dan mengapa mereka mungkin hanya menjadi kunci untuk memecahkan masalah teknik yang paling kompleks sekalipun.
Oke, itu hanya lelucon yang dibuat agar terlihat seperti iklan TV.
Sekarang mari kita kembali ke penjelasannya.
Menemukan Solusi Dasar yang Layak
Solusi layak dasar (BFS) adalah solusi untuk masalah optimisasi linier yang memenuhi semua kendala dan memiliki jumlah variabel bukan nol paling sedikit.
Setiap BFS adalah sudut polihedron dari solusi yang layak dari sudut pandang geometris.
Jika ada solusi terbaik, juga harus ada langkah pertama yang terbaik.
Pada artikel ini, kita akan berbicara tentang cara menemukan solusi layak dasar awal, cara menemukan semua solusi layak dasar, dan cara menemukan solusi layak dasar tanpa variabel kendur.
Menemukan Solusi Kelayakan Dasar Awal
Kita dapat menggunakan metode yang berbeda, bergantung pada bagaimana masalah diatur, untuk menemukan solusi dasar awal yang berfungsi untuk masalah optimisasi linier.
Salah satu caranya adalah dengan menambahkan variabel slack ke batasan pertidaksamaan dan menyetel semua variabel lainnya ke nol.
Variabel slack menjadi variabel dasar, dan sisanya menjadi variabel non dasar.
Metode Simplex dua fase adalah cara lain untuk memecahkan masalah.
Metode ini melibatkan pemecahan masalah program linier ekstra untuk menemukan solusi basis awal yang layak.
Setelah solusi layak dasar awal ditemukan, Metode Simpleks dapat digunakan untuk berpindah dari satu solusi layak dasar ke solusi berikutnya dan kemudian ke solusi terbaik.
Menemukan Semua Solusi Dasar yang Layak
Mungkin ada lebih dari satu solusi dasar yang berfungsi untuk program linier.
Kita dapat mengubah sistem dengan menambahkan variabel slack dan kemudian menggunakan sistem baru untuk menemukan semua solusi dasar yang layak untuk program linier.
Kemudian, solusi layak dasar ini digunakan untuk menemukan solusi layak dasar untuk masalah awal.
Menemukan Solusi Dasar yang Layak dengan Variabel No Slack
Kita perlu menggunakan variabel slack untuk menghilangkan kendala less-than sehingga kita dapat menemukan solusi dasar yang bekerja tanpa variabel slack.
Variabel slack hanyalah perbedaan antara sisi kanan kendala dan sisi kiri.
Misalnya, untuk kendala pertama, kita mendefinisikan variabel kendur x4 = 14 - 2x1 - x2 - x3. Dalam hal variabel baru ini, batasan pertama setara dengan x4 ≥ 0, yang merupakan batasan positif untuk x4.
Ketika kita menjumlahkan variabel-variabel slack ini, kita mendapatkan program linier yang sama dengan yang asli, kecuali bahwa semua batasannya adalah persamaan atau batasan yang menyatakan bahwa sesuatu adalah positif.
Himpunan variabel dasar, yang memiliki nilai selain nol dalam solusi dasar, disebut basis.
Variabel yang memiliki nilai nol dalam solusi dasar bukanlah variabel dasar.
Untuk menemukan solusi terbaik, kita perlu mencari vektor x yang memenuhi semua aturan dan mendapatkan nilai terbesar atau terkecil untuk tujuan tersebut.
Tetapi menemukan solusi terbaik membutuhkan lebih banyak langkah daripada sekadar menemukan solusi yang berfungsi dan tidak memiliki variabel kendur.
Tidak selalu mungkin untuk menemukan solusi dasar tanpa variabel kendur, terutama untuk masalah dengan kendala kurang dari.
Untuk menemukan solusi dasar yang layak, Anda perlu menggunakan metode simpleks atau algoritma pemrograman linier lainnya untuk mencari solusi yang memenuhi semua batasan dan memiliki variabel bukan nol paling sedikit.
Properti dan Signifikansi Dasar Solusi yang Layak
Properti Solusi Kelayakan Dasar
Solusi layak dasar memiliki paling banyak m variabel yang tidak nol dan setidaknya nm variabel yang nol, di mana n adalah jumlah variabel keputusan dan m adalah jumlah kendala.
BFS adalah sudut polihedron dari solusi yang mungkin, dan setiap BFS memiliki n kendala aktif yang bebas linier.
Jika ada solusi terbaik, juga harus ada langkah pertama yang terbaik.
Hal terpenting tentang solusi layak dasar adalah bahwa mereka adalah ujung dari himpunan solusi konveks untuk masalah pemrograman linier.
Untuk menemukan jawaban terbaik, algoritma simpleks melewati serangkaian BFS.
Algoritma Simplex mencari melalui semua solusi dasar yang mungkin dengan cara yang terorganisir untuk menemukan yang terbaik.
Signifikansi Dasar Solusi yang Layak
Menemukan solusi dasar yang mungkin adalah penting karena membantu menemukan jawaban terbaik untuk masalah pemrograman linier.
Ini juga memberikan algoritma yang kompleks tempat untuk memulai dan dapat digunakan untuk mencari tahu apakah program linier itu mungkin atau tidak.
Untuk menemukan semua solusi layak dasar untuk program linier, Anda dapat mengubah sistem dengan menambahkan variabel slack dan kemudian menggunakan sistem yang diubah untuk menemukan semua solusi layak dasar.
Kemudian, solusi layak dasar ini digunakan untuk menemukan solusi layak dasar untuk masalah awal.
Video: Solusi Dasar yang Layak
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: | BFS dapat digunakan untuk membagi sumber daya yang terbatas di antara beberapa proyek sehingga yang paling banyak dapat dilakukan dengan yang paling sedikit. Metode ini dapat digunakan di berbagai bidang, seperti transportasi, pertanian, dan keuangan. |
| Optimalisasi Jaringan: | BFS dapat digunakan untuk membuat jaringan komunikasi, transportasi, dan logistik bekerja lebih baik. BFS dapat membantu menemukan rute terbaik untuk barang dan jasa, mengurangi waktu dan uang yang dihabiskan untuk transportasi, serta mempercepat dan melakukan pengiriman yang lebih akurat. |
| Perencanaan Produksi: | BFS dapat digunakan untuk merencanakan produksi sehingga sumber daya seperti tenaga kerja, bahan baku, dan peralatan digunakan sebaik mungkin untuk mendapatkan hasil maksimal. BFS dapat membantu menurunkan biaya produksi, mengurangi limbah, dan meningkatkan efisiensi. |
| Perencanaan keuangan: | Dalam perencanaan keuangan, BFS dapat digunakan untuk mengoptimalkan portofolio investasi, menurunkan risiko, dan mendapatkan uang kembali yang paling banyak. BFS dapat membantu menemukan cara terbaik untuk membagi aset, menurunkan biaya transaksi, dan menghasilkan lebih banyak uang. |
| Manajemen Rantai Pasokan: | BFS dapat digunakan untuk meningkatkan aliran barang dan jasa dari pemasok ke pelanggan sebagai bagian dari manajemen rantai pasokan. BFS dapat membantu mengetahui jumlah stok terbaik yang harus dimiliki, mempersingkat waktu tunggu, dan meningkatkan layanan pelanggan. |
Kesimpulan
Saat melihat solusi dasar yang layak ini hampir selesai, jelas bahwa ini adalah alat penting bagi setiap insinyur atau mahasiswa teknik.
Dari memikirkan cara terbaik untuk membangun sistem yang rumit hingga memaksimalkan sumber daya yang tersedia, solusi dasar yang layak menyediakan kerangka kerja untuk mendapatkan hasil terbaik.
Tapi lebih dari sekedar berguna, mereka menunjukkan betapa elegan dan indahnya matematika.
Sungguh menakjubkan bahwa Anda dapat meringkas masalah rumit menjadi satu set persamaan sederhana dan kemudian menggunakan persamaan tersebut untuk menyelesaikan masalah di dunia nyata.
Ini adalah pengingat yang baik bahwa teknik adalah tentang memecahkan masalah, dan dengan menggunakan kekuatan matematika, kita dapat menemukan jawaban yang sebelumnya dianggap mustahil.
Jadi, saat Anda mempelajari lebih lanjut tentang teknik, ingatlah apa yang telah Anda pelajari tentang solusi sederhana yang berhasil dan gunakan solusi tersebut untuk membuat dunia menjadi tempat yang lebih baik dan lebih efisien.
Tautan dan referensi
Buku:
- Pemrograman Linier: Fondasi dan Ekstensi
- Pemrograman Linear: Teori dan Aplikasi
Bagikan pada…
