Linyar na programming

Linear na Programa — ito ay isang sangay ng mathematical programming at isang malawakang ginagamit na pamamaraan ng operations research, na nakatuon sa pagbuo ng teorya at mga pamamaraan ng paglutas ng mga problema sa paghahanap ng ekstremum (maximum o minimum) ng isang linear na function sa ilalim ng mga linear na paghihigpit.

Ang Linear na Programa (LP) ay isa sa mga pinaka-malakas at madalas na ginagamit na kagamitan para sa paglutas ng mga problema sa optimization sa ekonomiya, pamamahala, pagpaplano, logistics at iba pang mga larangan.

Paksa at Layunin

Ang pangunahing gawain ng linear na programa — hanapin ang pinakamainam (optimal) na paraan ng pamamahagi ng limitadong mga mapagkukunan upang makamit ang isang tiyak na layunin, kapag ang parehong layunin at mga paghihigpit sa paggamit ng mga mapagkukunan ay maaaring ipahayag bilang mga linear na relasyon.

• Ang linear na programa ay nagbibigay-daan sa paglutas ng mga ganitong praktikal na gawain, tulad ng:
• Optimal na pagpaplano ng produksyon.
• Optimization ng mga daloy ng transportasyon (problema sa transportasyon).
• Optimal na pamamahagi ng mga investment.
• Optimal na pagputol ng mga materyales. Problema sa mga takdang-gawain.

Matematikal na Pagbabalangkas ng Problema ng LP

Ang pamantayang problema ng linear na programa ay binubuuo sa sumusunod na paraan:

Kinakailangang hanapin ang mga halaga ng mga variable ng solusyon na nagpapalaki o nagpapaliit ng isang linear na objective function. Sa kasong ito, ang mga variable ng solusyon ay napapailalim sa mga paghihigpit sa anyo ng isang sistema ng mga linear na pagkakapantay-pantay at/o linear na pagkakahindi-pantay. Karaniwan, idinaragdag ang kondisyon ng hindi-negatibidad ng mga variable ng solusyon (ang kanilang mga halaga ay dapat na mas malaki kaysa o katumbas ng zero), na madalas na idinidikta ng pisikal o ekonomikong kahulugan ng problema.

Matematikal, nangangahulugan ito ng pagtatrabaho sa mga linear na function at mga sistema ng mga linear na equation/inequality.

Mga Pangunahing Konsepto ng LP

• Mga Variable ng Solusyon (Mga Kontroladong Variable): Mga dami na ang mga halaga ay kailangang matukoy sa proseso ng paglutas ng problema (halimbawa, mga dami ng produksyon ng iba't ibang produkto, dami ng mga mapagkukunan na itinatapon sa iba't ibang layunin).
• Objective Function: Isang linear na function ng mga variable ng solusyon, ang halaga nito ay kinakailangang palakihin o paliitin. Ito ay dami na nagpapahayag ng layunin ng problema (halimbawa, kabuuang kita, kabuuang gastos).
• Mga Paghihigpit: Isang sistema ng mga linear na pagkakapantay-pantay at/o pagkakahindi-pantay na dapat matugunan ng mga variable ng solusyon. Ang mga paghihigpit ay sumasalamin sa mga limitasyon ng mapagkukunan, mga kinakailangan sa teknolohiya, mga planong takdang-gawain at iba pang mga kondisyon ng problema.
• Rehiyon ng Mga Katanggap-tanggap na Solusyon (RKS): Ang hanay ng lahat ng mga set ng mga halaga ng variable ng solusyon na nakakatugon sa lahat ng mga paghihigpit ng problema. Sa geometriko sa multidimensional na espasyo, ang RKS ay kumakatawan sa isang convex na polyhedron (polyhedra), na posibleng walang hangganan o walang laman.
• Katanggap-tanggap na Solusyon: Anumang set ng mga halaga ng variable na kabilang sa RKS.
• Optimal na Solusyon: Isang katanggap-tanggap na solusyon kung saan ang objective function ay umaabot sa kanyang ekstremal (maximum o minimum) na halaga. Kung ang optimal na solusyon ay umiiral, ito ay palaging matatagpuan sa hangganan ng RKS, kahit sa isa sa mga vertex ng convex na polyhedron ng RKS (pangunahing teorema ng LP).

Mga Pamamaraan ng Paglutas ng mga Problema ng LP

Mayroong ilang mga pangunahing pamamaraan para sa paglutas ng mga problema ng linear na programa:

• Grapikal na Pamamaraan: Inilalapat para sa mga problema na may dalawang variable ng solusyon. Nagbibigay-daan itong biswal na ipakita ang RKS at ang objective function sa isang eroplano at hanapin ang optimal na solusyon sa pamamagitan ng pagsusuri ng mga vertex ng RKS o paggalaw ng level line ng objective function.
• Simplex Method: Isang unibersal na iterative algorithm na binuo ni George Dantzig. Ang pamamaraan ay sunud-sunod na lumilipat mula sa isang vertex ng RKS patungo sa katabing vertex, pinapabuti ang halaga ng objective function sa bawat hakbang, hanggang sa mahanap ang optimal na solusyon. Ito ay ang klasikal at pinaka-kilalang pamamaraan ng paglutas ng mga problema ng LP.
• Mga Pamamaraan ng Panloob na Punto: Isang alternatibong klase ng mga algorithm na lumitaw pagkatapos ng simplex method. Sila ay gumagalaw patungo sa optimal na solusyon sa loob ng RKS, at hindi sa kahabaan ng mga hangganan nito. Ang mga pamamaraang ito ay partikular na epektibo para sa paglutas ng mga problema ng LP na may napakalaking dimensyon.

Duality sa Linear na Programa

Sa bawat problema ng linear na programa (tinatawag na primal) maaaring maiugnay ang isa pang problema ng LP, na tinatawag na dual. Ang mga primal at dual na problema ay malapit na magkaugnay:

Ang solusyon ng isang problema ay nagbibigay ng impormasyon tungkol sa solusyon ng isa pa. Ang mga optimal na halaga ng mga objective function sa parehong mga problema ay magkapantay (kung sila ay umiiral). Ang mga variable ng dual na problema ay may mahalagang ekonomikong interpretasyon — sila ay tumutugma sa mga shadow price (o dual na mga pagtatantya) ng mga mapagkukunan, na nagpapakita kung gaano magbabago ang optimal na halaga ng objective function ng primal na problema sa maliit na pagbabago ng paghihigpit sa kaukulang mapagkukunan.

Paglalapat ng LP

Ang linear na programa ay malawakang ginagamit sa:

• Ekonomiya at negosyo (pagpaplano ng produksyon, logistics, pananalapi, marketing).
• Industriya (optimization ng mga prosesong teknolohikal, pamamahala ng mga imbentaryo, pagputol ng mga materyales).
• Transportasyon (optimization ng mga ruta, mga iskedyul). Agrikultura (optimization ng mga lugar ng pagtatanim, mga diyeta ng pagpapakain).
• Enerhiya (optimization ng pagkarga ng mga kapangyarihang naglilikha ng kuryente).

Literaturа

• Dantzig, Dzh. Linear na Programa, ang mga Aplikasyon at Generalizations nito. — M.: Progress, 1966.
• Yudin D. B., Golshtein E. G. Linear na Programa (teorya, mga pamamaraan at mga aplikasyon). — M.: Nauka, 1969.
• 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

• Operations Research
• Optimization
• Objective Function
• Mga Paghihigpit
• Rehiyon ng Mga Katanggap-tanggap na Solusyon
• Optimal na Solusyon