Daerah Solusi Layak

Daerah solusi layak (DSL) (juga himpunan solusi layak, Ingg. Feasible region, feasible set) — dalam riset operasi, optimisasi, dan pemodelan matematika adalah himpunan semua solusi yang mungkin (kumpulan nilai variabel) yang memenuhi semua batasan yang dikenakan pada masalah tersebut.

DSL merupakan subruang tempat dilakukannya pencarian solusi optimal. Setiap solusi yang berada di luar daerah ini dianggap tidak layak.

Definisi dan Pembentukan

Daerah solusi layak dibentuk sebagai irisan himpunan-himpunan yang didefinisikan oleh masing-masing batasan masalah. Batasan-batasan tersebut dapat dinyatakan dalam bentuk:

• Pertidaksamaan: Menetapkan batas atas atau batas bawah untuk nilai variabel atau kombinasinya (misalnya, "penggunaan sumber daya A tidak boleh melebihi 100 unit", "jumlah produk yang dihasilkan harus tidak kurang dari 50 buah").
• Persamaan: Mensyaratkan pemenuhan kondisi secara tepat (misalnya, "total volume pengiriman harus sama dengan 1000 ton", "keseimbangan aliran masuk dan keluar sama dengan nol").
• Kondisi tanda variabel: Seringkali variabel harus bernilai non-negatif, bilangan bulat, atau termasuk dalam himpunan diskret tertentu.

Sebuah titik (atau vektor nilai variabel) termasuk dalam DSL jika dan hanya jika titik tersebut secara bersamaan memenuhi semua batasan tersebut.

Interpretasi Geometris

DSL seringkali memiliki interpretasi geometris yang intuitif, terutama pada masalah dengan jumlah variabel yang sedikit:

• Dalam ruang dua dimensi (2 variabel): Setiap batasan pertidaksamaan linear mendefinisikan sebuah setengah bidang. DSL merupakan irisan dari setengah-setengah bidang tersebut — berupa poligon cembung (yang mungkin tidak terbatas atau kosong).
• Dalam ruang tiga dimensi (3 variabel): Setiap batasan pertidaksamaan linear mendefinisikan sebuah setengah ruang. DSL merupakan irisan dari setengah-setengah ruang tersebut — berupa polihedral cembung (poliedron).
• Dalam ruang berdimensi tinggi: DSL yang didefinisikan oleh batasan-batasan linear merupakan polihedral cembung (politop).

Dalam kasus batasan nonlinear, DSL dapat memiliki bentuk yang lebih kompleks dan tidak bersifat cembung.

Peran dalam Optimisasi

Daerah solusi layak memainkan peran fundamental dalam optimisasi:

1. Mendefinisikan ruang pencarian: Solusi optimal suatu masalah (jika ada) selalu berada di dalam DSL atau pada batasnya. Algoritma optimisasi mencari ekstremum fungsi tujuan tepat di daerah ini. 2. Memeriksa keberadaan solusi: Jika DSL merupakan himpunan kosong (yaitu batasan-batasannya saling bertentangan), maka masalah tersebut tidak memiliki solusi layak, dan akibatnya juga tidak memiliki solusi optimal. 3. Pengaruh terhadap solusi optimal: Bentuk dan ukuran DSL secara langsung memengaruhi kemungkinan pencapaian ekstremum fungsi tujuan serta nilai ekstremum tersebut.

Sifat-Sifat DSL (dalam Masalah Pemrograman Linear)

Dalam masalah pemrograman linear (PL), di mana semua batasan dan fungsi tujuan bersifat linear, DSL memiliki sifat-sifat penting:

• Kecembungan: Jika dua titik termasuk dalam DSL, maka seluruh segmen yang menghubungkan kedua titik tersebut juga termasuk dalam DSL. Sifat ini menjamin bahwa solusi optimal (jika ada dan tunggal) akan berada di salah satu titik sudut polihedral DSL.
• Ketertutupan: DSL mencakup batas-batasnya (karena pertidaksamaan tidak ketat ≤, ≥ dan persamaan).

DSL dapat berupa:

• Terbatas: Memiliki ukuran yang terhingga.
• Tidak terbatas: Membentang tak hingga dalam satu atau beberapa arah.
• Kosong: Tidak mengandung satu pun titik.

Literatur

• Ventzel E. S. Riset operasi: masalah, prinsip, metodologi. — Moskow: Nauka, 1988.
• Akof R., Sasieni M. Dasar-dasar riset operasi. — Moskow: Mir, 1971.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)

Lihat Pula

• Riset operasi
• Optimisasi
• Model matematika
• Batasan
• Solusi layak
• Solusi optimal
• Fungsi tujuan
• Pemrograman linear
• Himpunan cembung