Lugar ng mga Katanggap-tanggap na Solusyon

Lugar ng mga katanggap-tanggap na solusyon (LKS) (kilala rin bilang hanay ng mga katanggap-tanggap na solusyon, Ingles: Feasible region, feasible set) — sa pananaliksik ng mga operasyon, optimisasyon, at matematikal na pagmomodelo, ito ang hanay ng lahat ng posibleng solusyon (mga set ng halaga ng mga variable) na nagtatugon sa lahat ng mga limitasyong ipinataw sa problema.

Ang LKS ay kumakatawan sa isang subespasyo kung saan hinahanap ang pinakamainam na solusyon. Anumang solusyon na nasa labas ng lugar na ito ay hindi katanggap-tanggap.

Kahulugan at Pagbuo

Ang lugar ng mga katanggap-tanggap na solusyon ay nabubuo bilang interseksyon ng mga hanay na tinukoy ng bawat indibidwal na limitasyon ng problema. Ang mga limitasyon ay maaaring ipahayag sa anyo ng:

• Mga di-pagkakapantay: Nagtatakda ng itaas o ibabang hangganan para sa mga halaga ng mga variable o sa kanilang mga kumbinasyon (halimbawa, "ang paggamit ng rekurso A ay hindi dapat lumampas sa 100 yunit", "ang dami ng nabuong produkto ay dapat na hindi bababa sa 50 piraso").
• Mga pagkakapantay: Nangangailangan ng eksaktong katuparan ng kondisyon (halimbawa, "ang kabuuang dami ng transportasyon ay dapat katumbas ng 1000 tonelada", "ang balanse ng mga papasok at papalabas na daloy ay katumbas ng zero").
• Mga kondisyon sa tanda ng mga variable: Kadalasan ang mga variable ay dapat na hindi negatibo, integer, o kabilang sa isang tiyak na discrete na hanay.

Ang isang punto (o vector ng mga halaga ng variable) ay kabilang sa LKS kung at saka lamang kung sabay-sabay nitong tinutugunan ang lahat ng mga limitasyong ito.

Heometrikal na Interpretasyon

Ang LKS ay kadalasang may malinaw na heometrikal na interpretasyon, lalo na sa mga problema na may maliit na bilang ng mga variable:

• Sa dalawang-dimensyonal na espasyo (2 variable): Ang bawat linear na limitasyong di-pagkakapantay ay nagtatakda ng kalahating eroplano. Ang LKS ay kumakatawan sa interseksyon ng mga kalahating eroplano na ito — isang convex na poligono (maaaring walang hangganan o walang laman).
• Sa tatlong-dimensyonal na espasyo (3 variable): Ang bawat linear na limitasyong di-pagkakapantay ay nagtatakda ng kalahating espasyo. Ang LKS ay interseksyon ng mga kalahating espasyong ito — isang convex na polyhedron.
• Sa multidimensyonal na espasyo: Ang LKS na tinukoy ng mga linear na limitasyon ay isang convex na polyhedron (polytope).

Sa kaso ng mga nonlinear na limitasyon, ang LKS ay maaaring magkaroon ng mas kumplikadong anyo at hindi maging convex.

Papel sa Optimisasyon

Ang lugar ng mga katanggap-tanggap na solusyon ay gumaganap ng pundamental na papel sa optimisasyon:

1. Pagtukoy ng espasyo ng paghahanap: Ang pinakamainam na solusyon ng problema (kung mayroon) ay palagi na nasa loob ng LKS o sa hangganan nito. Ang mga algorithm ng optimisasyon ay naghahanap ng extremum ng objective function nang tiyak sa lugar na ito. 2. Pagsusuri ng pag-iral ng mga solusyon: Kung ang LKS ay walang laman na hanay (ibig sabihin, ang mga limitasyon ay magkasalungat), ang problema ay walang katanggap-tanggap na solusyon, at samakatuwid, walang pinakamainam na solusyon. 3. Impluwensya sa pinakamainam na solusyon: Ang hugis at sukat ng LKS ay direktang nakaka-impluwensya sa posibilidad ng pagkamit ng extremum ng objective function at sa halaga ng extremum na iyon.

Mga Katangian ng LKS (sa mga problema ng linear programming)

Sa mga problema ng linear programming (LP), kung saan ang lahat ng limitasyon at objective function ay linear, ang LKS ay nagtataglay ng mahahalagang katangian:

• Convexity: Kung ang dalawang punto ay kabilang sa LKS, kung gayon ang buong segment na nagkokonekta sa mga puntong ito ay kabilang din sa LKS. Tinitiyak ng katangiang ito na ang pinakamainam na solusyon (kung mayroon at natatangi) ay matatagpuan sa isa sa mga vertex ng polyhedron ng LKS.
• Pagsasara: Isinasama ng LKS ang mga hangganan nito (dahil sa mga hindi mahigpit na di-pagkakapantay ≤, ≥ at mga pagkakapantay).

Ang LKS ay maaaring maging:

• May hangganan: May natapos na sukat.
• Walang hangganan: Nagpapalawak nang walang katapusan sa isa o maraming direksyon.
• Walang laman: Hindi naglalaman ng kahit isang punto.

Mga Sanggunian

• Ventzel, E. S. Pananaliksik ng mga Operasyon: mga problema, prinsipyo, metodolohiya. — Moscow: Nauka, 1988.
• Ackoff, R., Sasieni, M. Mga Pundasyon ng Pananaliksik ng mga Operasyon. — Moscow: 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)

Tingnan Din

• Pananaliksik ng mga operasyon
• Optimisasyon
• Matematikal na modelo
• Mga limitasyon
• Katanggap-tanggap na solusyon
• Pinakamainam na solusyon
• Objective function
• Linear programming
• Convex na hanay