Buong-bilang na programming

From Systems analysis Wiki
Jump to navigation Jump to search

Buong Numerong Programa (BNP; Ingles integer programming, IP) — ito ay isang sangay ng mathematical optimization kung saan pinag-aaralan ang mga problema na ang ilan o lahat ng variable ay dapat na magkuha lamang ng buong numerong halaga[1].

Ang pinaka-pinag-aralan na espesyal na kaso ay ang buong numerong linear na programa (BNLP; Ingles integer linear programming, ILP), kung saan ang objective function at mga hadlang ay linear. Hindi tulad ng linear programming, kung saan ang mga variable ay maaaring magkuha ng anumang tunay na halaga, ang kinakailangan ng buong numero ay nagpapahirap nang malaki sa paglutas ng mga problema ng BNP[2].

Ang buong numerong programa ay malawakang ginagamit sa ekonomiya, logistika, pagpaplano ng produksyon, at iba pang larangan kung saan ang mga variable ay likas na discrete (halimbawa, ang bilang ng mga yunit ng produktong ginawa o ang bilang ng mga manggagawa)[3].

Kahulugan at Terminolohiya

Ang pangkalahatang problema ng buong numerong linear na programa ay maaaring isulat tulad ng sumusunod:

Hanapin ang vector x, na:

nagpapalaki (o nagpapaliit) ng cTx

sa mga kondisyon:

Ax≤b
x≥0
x∈ℤn (lahat ng bahagi ng vector x ay buong numero)

kung saan ang x — vector ng mga variable, c at b — mga vector, at A — matrix ng mga koepisyente[4].

Batay sa mga kinakailangan sa mga variable, nakikilala ang mga sumusunod na uri ng mga problema:

  • Ganap na buong numerong programa: lahat ng variable ay dapat na buong numero.
  • Halo-halong buong numerong programa (Ingles mixed-integer programming, MIP): tanging bahagi lamang ng mga variable ang dapat na buong numero.
  • Boolean (0-1) na programa: ang mga variable ay nagkukuha lamang ng halagang 0 o 1, na nagbibigay-daan sa pagmomodelo ng mga lohikal na desisyon na uri ng "oo/hindi".

Mga Pangunahing Katangian at Kumplikasyon

Computational Complexity - Kumplikasyon ng Pagkalkula

Ang problema ng buong numerong linear na programa sa pangkalahatang kaso ay NP-hard[5]. Ibig sabihin nito, walang kilalang algorithm na kayang mahanap ang eksaktong pinakamainam na solusyon para sa anumang problema ng BNP sa polynomial na oras. Ang kumplikasyon ay dulot ng kombinatoryong kalikasan ng problema, dahil ang bilang ng mga posibleng buong numerong solusyon ay maaaring lumago nang exponential habang dumadami ang mga variable.

Kaugnayan sa Linear Programming (LP-relaxation)

Para sa anumang problema ng BNP, maaaring buuin ang nito linear na relaxation — isang problema ng linear programming (LP), kung saan tinanggal ang kinakailangan ng buong numero ng mga variable. Ang solusyon ng LP-relaxation ay may dalawang mahahalagang katangian:

  1. Maaari itong mahanap nang mas mabilis (sa polynomial na oras).
  2. Ang pinakamainam na halaga ng objective function ng LP-relaxation ay nagbibigay ng pagtatantya (itaas na hangganan para sa problema ng pagpapalaki at ibabang hangganan para sa pagpapaliit) para sa pinakamainam na halaga ng orihinal na buong numerong problema[2].

Gayunpaman, ang simpleng pag-ikot ng fractional na solusyon ng LP-relaxation sa pinakamalapit na buong numero, sa karanasan, ay hindi humahantong sa pinakamainam o maging katanggap-tanggap na solusyon ng buong numerong problema[1].

Katangian ng Ganap na Unimodularity

Mayroong mahalagang klase ng mga problema ng BNLP na nalulutas nang kasingdali ng kanilang mga LP-relaxation. Ito ang mga problema kung saan ang matrix ng mga hadlang na A ay ganap na unimodular (iyon ay, ang determinant ng anumang parisukat na submatrix nito ay katumbas ng 0, +1, o −1). Kung ang matrix A ay ganap na unimodular, at ang vector b ay buong numero, kung gayon ang lahat ng vertex ng polyhedron ng mga katanggap-tanggap na solusyon ng LP-relaxation ay awtomatikong magiging buong numero. Kaya naman, ang solusyon na nahanap ng simplex method ay magiging buong numero[4]. Ang mga halimbawa ng ganitong mga problema ay ang transportation problem at ang assignment problem.

Mga Paraan ng Paglutas

Para sa paglutas ng mga pangkalahatang problema ng BNP na walang katangian ng ganap na unimodularity, binuo ang mga eksaktong pamamaraan batay sa mga ideya ng implicit enumeration.

  • Paraan ng Branch and Bound (Ingles Branch and Bound) — ang pangunahing eksaktong pamamaraan, batay sa sistematikong paghahati ng hanay ng mga katanggap-tanggap na solusyon sa mga subset (branching) at pagtatanggal ng mga subset na tiyak na hindi naglalaman ng pinakamainam na solusyon. Para sa pagsusuri ng pananaw ng mga subset, ginagamit ang LP-relaxation[6].
  • Paraan ng Cutting Plane (pamamaraan ni Gomory; Ingles Cutting Plane Method) — isang iterative na diskarte na sunud-sunod na nagdadagdag ng mga bagong linear na hadlang ("mga hiwa") sa problema. Ang mga hiwa na ito ay "nagtatanggal" ng mga fractional na solusyon ng LP-relaxation, nang hindi naaapektuhan ang kahit isang katanggap-tanggap na buong numerong solusyon, na unti-unting inilalapit ang lugar ng mga katanggap-tanggap na solusyon ng LP-relaxation sa convex hull ng mga buong numerong solusyon[6].

Ang mga modernong solver, sa pangkalahatan, ay gumagamit ng mga hybrid na algorithm, tulad ng pamamaraan ng Branch and Cut (Ingles Branch and Cut), na pinagsasama ang mga pakinabang ng parehong diskarte.

Mga Halimbawa at Larangan ng Paggamit

Ang buong numerong programa ay nagbibigay-daan sa pagmomodelo ng maraming klasikong problema ng combinatorial optimization.

  • Problema ng Mochila (Knapsack Problem): isang klasikong problema ng 0-1 na programa, kung saan kailangan ang pumili ng hanay ng mga bagay na may pinakamataas na kabuuang halaga, nang hindi lalampas sa limitasyon ng kabuuang timbang.
  • Problema ng Traveling Salesman: isang problema ng paghahanap ng pinakamaikling ruta na dumadaan sa isang tinukoy na hanay ng mga lungsod. Maaari itong buuin bilang isang problema ng buong numerong programa, kung saan ang mga variable ay responsable para sa pagsasama ng mga gilid ng graph sa panghuling ruta.

Dahil sa kakayahan nitong iakma, ang BNP ay isa sa pinaka-sinasamantalahing kasangkapan sa operations research at ginagamit sa mga larangang tulad ng:

  • Logistika at pamamahala ng supply chain: pag-optimize ng mga ruta ng transportasyon, paglalagay ng mga bodega, pamamahala ng imbentaryo.
  • Pagpaplano ng produksyon: paggawa ng mga iskedyul ng produksyon, pamamahagi ng mga mapagkukunan, paggamit ng kagamitan.
  • Pananalapi at ekonomiya: pagbuo ng portfolio ng pamumuhunan, budgeting ng kapital.
  • Telekomunikasyon at enerhiya: pagdidisenyo ng mga network ng komunikasyon, pagpaplano ng operasyon ng mga power unit.

Tingnan Din

  • Linear programming
  • Paraan ng Branch and Bound

Mga Tala

[1] [2] [3] [4] [5] [6] </references>

  1. ↑ 1.0 1.1 1.2 "Целочисленное программирование". Википедия. [1]
  2. ↑ 2.0 2.1 2.2 Wolsey, Laurence A. (2020). Integer Programming (2nd ed.). John Wiley & Sons.
  3. ↑ 3.0 3.1 Писарук Н.Н. (2010). Модели и методы смешанного целочисленного программирования. Минск: БГУ.
  4. ↑ 4.0 4.1 4.2 Conforti, M., Cornuéjols, G., & Zambelli, G. (2014). Integer Programming. Springer.
  5. ↑ 5.0 5.1 Karp, Richard M. (1972). "Reducibility among Combinatorial Problems". In: Complexity of Computer Computations. Springer.
  6. ↑ 6.0 6.1 6.2 "Integer programming". Wikipedia. [2]
Retrieved from "https://systems-analysis.info/int/index.php?title=Buong-bilang_na_programming&oldid=823"