Bentuk Umum Dan Penyelesaian Solusi Layak Dasar

𝕸𝖆𝖘 𝕬𝖓𝖉𝖞 𝕯𝖎𝖌𝖎𝖙𝖆𝖑 𝕸𝖊𝖉𝖎𝖆

2 min read

·

Apr 06, 2025

47

Share

Bentuk Umum dan Penyelesaian Solusi Layak Dasar

Dalam dunia matematik dan pengaturcaraan, menyelesaikan masalah seringkali melibatkan pencarian solusi yang memenuhi kriteria tertentu. Konsep "solusi layak dasar" (basic feasible solution - BFS) memainkan peranan penting dalam menyelesaikan masalah pengaturcaraan linear, khususnya dengan menggunakan kaedah Simplex. Artikel ini akan meneroka bentuk umum BFS dan bagaimana ia diselesaikan.

Memahami Solusi Layak Dasar

Sebelum menyelami penyelesaian, mari kita fahami pengertian solusi layak dasar. Dalam konteks pengaturcaraan linear, solusi layak adalah penyelesaian yang memenuhi semua kekangan masalah. "Dasar" merujuk kepada penyelesaian yang hanya menggunakan sejumlah pembolehubah yang sama dengan bilangan kekangan bebas (independent constraints). Ini bermakna, beberapa pembolehubah akan mempunyai nilai sifar.

Ciri-ciri utama BFS:

• Layak: Memenuhi semua kekangan masalah.
• Dasar: Menggunakan hanya bilangan pembolehubah yang sama dengan bilangan kekangan bebas.
• Optimum (tidak semestinya): BFS mungkin merupakan penyelesaian optimum, tetapi tidak semestinya.

Bentuk Umum Solusi Layak Dasar

Bentuk umum BFS boleh diwakilkan dalam bentuk matriks. Katakan kita mempunyai masalah pengaturcaraan linear dengan m kekangan dan n pembolehubah (dengan n > m). BFS boleh dinyatakan sebagai:

Ax = b

di mana:

• A ialah matriks pekali (koefisien) berukuran m x n.
• x ialah vektor pembolehubah berukuran n x 1.
• b ialah vektor sisi kanan (right-hand side) berukuran m x 1.

Untuk mendapatkan BFS, kita perlu memilih m pembolehubah (pemilih asas - basic variables) dan menetapkan nilai baki n - m pembolehubah kepada sifar (pemboilihubah bukan asas - non-basic variables). Kemudian, kita selesaikan sistem persamaan linear untuk mencari nilai pembolehubah asas.

Kaedah Penyelesaian: Kaedah Simplex

Kaedah Simplex merupakan kaedah yang paling umum digunakan untuk mencari BFS dan penyelesaian optimum bagi masalah pengaturcaraan linear. Kaedah ini secara iteratif bergerak dari satu BFS ke BFS yang lain, meningkatkan nilai fungsi objektif sehingga mencapai penyelesaian optimum.

Langkah-langkah umum dalam Kaedah Simplex:

1. Bentuk Standard: Ubah masalah pengaturcaraan linear kepada bentuk standard.
2. Matriks Simplex: Bina matriks Simplex.
3. Pilih Pembolehubah Masuk: Pilih pembolehubah yang akan dimasukkan ke dalam asas berdasarkan nilai pekali dalam fungsi objektif.
4. Pilih Pembolehubah Keluar: Pilih pembolehubah yang akan dikeluarkan daripada asas berdasarkan nisbah ujian (ratio test).
5. Operasi Baris: Lakukan operasi baris (row operation) untuk mengubah matriks Simplex.
6. Ulang: Ulang langkah 3-5 sehingga penyelesaian optimum dijumpai.

Contoh Ringkas

Bayangkan masalah pengaturcaraan linear ringkas dengan dua kekangan dan tiga pembolehubah. Kaedah Simplex akan membantu kita mencari BFS dan akhirnya penyelesaian optimum. Proses ini melibatkan manipulasi matriks dan pengiraan berulang untuk mencapain penyelesaian. Penjelasan terperinci tentang contoh ini memerlukan ruang yang lebih luas dan mungkin memerlukan ilustrasi grafik.

Kesimpulan

Pemahaman tentang bentuk umum dan penyelesaian solusi layak dasar adalah kunci kepada menyelesaikan masalah pengaturcaraan linear. Kaedah Simplex merupakan alat yang berkuasa untuk mencari BFS dan seterusnya penyelesaian optimum. Walaupun penjelasan terperinci tentang kaedah ini memerlukan ruang yang lebih luas, semoga artikel ini memberikan asas pemahaman yang kukuh mengenai konsep penting ini. Penggunaan contoh berangka dan ilustrasi visual boleh membantu meningkatkan pemahaman lanjut.