LINEAR PROGRAMMING: ANO ITO PARA SA, MGA MODELO, PAGPILIT, APPLICATION - MGA MATEMATIKA - 2025

Ang linear programming ay isang pamamaraan ng matematika na ginagamit upang ma-optimize (i-maximize o i-minimize kung naaangkop) isang function na ang mga variable ay pinigilan, hangga't ang pag-andar at paghihigpit ay magkatulad na mga variable na umaasa.

Kadalasan, ang pag-andar na mai-optimize na mga modelo ng isang praktikal na sitwasyon, tulad ng kita ng isang tagagawa na ang mga input, paggawa o makinarya ay limitado.

Larawan 1. Ang linear programming ay malawakang ginagamit upang mai-optimize ang kita. Pinagmulan: Mga Piqsel.

Ang isa sa mga pinakasimpleng kaso ay ang isang linear function na mai-maximize, na nakasalalay lamang sa dalawang variable, na tinatawag na mga variable variable. Maaari itong maging form:

Z = k ₁ x + k ₂ y

Sa k ₁ at k ₂ pare-pareho. Ang function na ito ay kilala bilang ang function na layunin. Siyempre, may mga sitwasyon na nagkakahalaga ng higit sa dalawang variable para sa pag-aaral, na mas kumplikado:

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +….

At ang mga hadlang ay na-modelo din sa matematika ng isang sistema ng mga equation o hindi pagkakapantay-pantay, pantay na linear sa x at y.

Ang hanay ng mga solusyon sa sistemang ito ay tinatawag na magagawa solusyon o magagawa puntos. At kabilang sa mga magagawa na puntos mayroong hindi bababa sa isa, na nag-optimize sa layunin na pag-andar.

Ang linear programming ay independiyenteng binuo ng Amerikanong pisiko at matematiko na si George Dantzig (1914-2005) at ang Russian matematiko at ekonomista na si Leonid Kantorovich (1912-1986) ilang sandali matapos ang Ikalawang Digmaang Pandaigdig.

Ang paraan ng paglutas ng problema na kilala bilang ang simpleng pamamaraan ay ang utak ng Dantzig, na nagtrabaho para sa US Air Force, Berkeley University, at Stanford University.

Larawan 2. Mga Matematika na si George Dantzig (kaliwa) at Leonid Kantorovich (kanan). Pinagmulan: F. Zapata.

Linya ng mga modelo ng pag-programming

Ang mga elemento na kinakailangan upang maitaguyod ang isang linear na modelo ng programming, na angkop para sa isang praktikal na sitwasyon, ay:

-Pag-andar ng Pag-andar

-Mga variable variable

-Mga Salaysay

Sa function na layunin na iyong tinukoy kung ano ang nais mong makamit. Halimbawa, ipagpalagay na nais mong i-maximize ang mga kita na ginawa mula sa paggawa ng ilang mga produkto. Pagkatapos ang "profit" function ay itinatag, ayon sa presyo kung saan ibinebenta ang mga produkto.

Sa mga term na pang-matematika, ang pagpapaandar na ito ay maaaring maipahayag na pinaikling gamit ang notasyon ng pagtatapos:

Z = ∑k _i x _i

Sa equation na ito, k _i ay coefficients at x _ako ang mga variable variable.

Ang mga variable na desisyon ay ang mga elemento ng system na ang kontrol ay mayroon at ang kanilang mga halaga ay positibong tunay na numero. Sa iminungkahing halimbawa, ang mga variable ng desisyon ay ang dami ng bawat produkto na gagawin upang makuha ang maximum na kita.

Sa wakas, mayroon kaming mga hadlang, na kung saan ay magkakasunod na mga equation o hindi pagkakapareho sa mga tuntunin ng mga variable na desisyon. Inilarawan nila ang mga limitasyon sa problema, na kilala at maaaring maging, halimbawa, ang halaga ng hilaw na materyal na magagamit sa paggawa.

Mga uri ng mga paghihigpit

Maaari kang magkaroon ng isang bilang ng mga limitasyon, simula sa j = 1 hanggang j = M. Matematika ang mga paghihigpit ay may tatlong uri:

1. Isang _j = ∑ isang _ij . x _i
2. B _j ≥ ∑ b _ij . x _i
3. C _j ≤ ∑ c _ij . x _i

Ang unang paghihigpit ay sa uri ng paghahambing sa guhit at nangangahulugan na ang halaga A _j , na kilala, ay dapat igalang.

Ang dalawang natitirang mga hadlang ay magkatulad na pagkakapareho at nangangahulugan ito na ang mga kilalang halaga B _j at C _j ay maaaring iginagalang o lalampas, kapag ang simbolo na lilitaw ay ≥ (higit sa o katumbas ng) o iginagalang o hindi lalampas, kung ang simbolo ay ≤ (mas mababa sa o katumbas ng).

Halimbawa ng modelo

Ang mga patlang ng aplikasyon ay napaka magkakaibang, mula sa pangangasiwa ng negosyo hanggang sa nutrisyon, ngunit upang maunawaan ang pamamaraan, isang simpleng modelo ng isang praktikal na sitwasyon na may dalawang variable ay iminungkahi sa ibaba.

Kilala ang isang lokal na patisserie para sa dalawang specialty: black forest cake at sa scriptantine cake.

Sa paghahanda nito ay nangangailangan sila ng mga itlog at asukal. Para sa itim na kagubatan kailangan mo ng 9 mga itlog at 500 g ng asukal, habang para sa sacripantine kailangan mo ng 8 itlog at 800 g ng asukal. Ang kaukulang mga presyo ng pagbebenta ay $ 8 at $ 10.

Ang problema ay: Gaano karaming mga cake ng bawat uri ang dapat gawin ng panaderya upang ma-maximize ang kita nito, alam na mayroon itong 10 kilo ng asukal at 144 na mga itlog?

Mga variable na desisyon

Ang mga variable ng desisyon ay "x" at "y", na kumukuha ng mga tunay na halaga:

-x: ang bilang ng mga black cake cake

-y: cake ng uri ng bibilhin.

Mga Paghihigpit

Ang mga paghihigpit ay ibinibigay ng katotohanan na ang bilang ng mga cake ay isang positibong dami at may mga limitadong dami ng hilaw na materyal upang ihanda ang mga ito.

Samakatuwid, sa form na matematiko, ang mga paghihigpit na ito ay kumuha ng form:

1. x ≥ 0
2. at ≥0
3. 9x + 8y ≤ 144
4. 0.5 x + 0.8y ≤ 10

Ang mga hadlang 1 at 2 ay bumubuo ng kondisyon ng hindi negatibiti na dati nang nakalantad, at ang lahat ng mga hindi pagkakapareho na nakataas ay magkakasunod. Sa mga paghihigpit 3 at 4 ay ang mga halagang hindi dapat lumagpas: 144 mga itlog at 10 kg ng asukal.

Pag-andar ng Layunin

Sa wakas, ang layunin na function ay ang kita na nakuha kapag ang paggawa ng "x" na dami ng mga black cake cake kasama ang "y" na dami ng mga script. Ito ay itinayo sa pamamagitan ng pagpaparami ng presyo sa pamamagitan ng dami ng mga cake na ginawa at pagdaragdag para sa bawat uri. Ito ay isang guhit na pag-andar na tatawagin namin ang G (x, y):

G = 8x + 10y

Mga pamamaraan ng solusyon

Ang iba't ibang mga pamamaraan ng solusyon ay may kasamang mga graphical na pamamaraan, ang simplex algorithm, at ang paraan ng interior point, upang pangalanan ang iilan.

- Paraan ng grapiko o geometric

Kung mayroon kang isang dalawang-variable na problema tulad ng isa sa nakaraang seksyon, ang mga hadlang ay matukoy ang isang polygonal na rehiyon sa xy eroplano, na tinatawag na magagawa na rehiyon o posibilidad na may posibilidad.

Larawan 3. Ang magagawa na rehiyon, kung saan matatagpuan ang solusyon ng problema sa pag-optimize. Pinagmulan: Wikimedia Commons.

Ang rehiyon na ito ay itinayo gamit ang mga linya ng paghihigpit, na kung saan ay ang mga linya na nakuha mula sa mga hindi pagkakapantay-pantay ng mga paghihigpit, na gumagana lamang sa pag-sign ng pagkakapantay-pantay.

Sa kaso ng bakery na nais na mai-optimize ang kita, ang mga linya ng pagpilit ay:

1. x = 0
2. y = 0
3. 9x + 8y = 144
4. 0.5 x + 0.8y = 10

Ang lahat ng mga puntos sa rehiyon na nakapaloob sa mga linyang ito ay posibleng mga solusyon, kaya walang hanggan maraming sa kanila. Maliban sa kaso kung saan ang posibilidad na magawang rehiyon ay walang laman, kung saan ang problemang nagmula ay walang solusyon.

Sa kasamaang palad, para sa problema sa pastry na ang magagawa na rehiyon ay hindi walang laman, mayroon kaming ito sa ibaba.

Larawan 4. Ang magagawa na rehiyon ng problema sa pastry. Ang linya na may pakinabang 0 tumatawid sa pinagmulan. Pinagmulan: F. Zapata kasama ang Geogebra.

Ang pinakamainam na solusyon, kung mayroon ito, ay matatagpuan sa tulong ng layunin na pag-andar. Halimbawa, kapag sinusubukan mong hanapin ang maximum na kita G, mayroon kaming mga sumusunod na linya, na tinatawag na linya ng iso-profit:

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

Sa linyang ito nakuha namin ang lahat ng mga pares (x, y) na nagbibigay ng isang naibigay na G, kaya mayroong isang pamilya ng mga linya ayon sa halaga ng G, ngunit ang lahat ay may parehong slope -k ₁ / k ₂ , kaya't sila ay kahanay na linya.

Ang pinakamainam na solusyon

Ngayon, maipakita na ang pinakamainam na solusyon ng isang guhit na problema ay palaging isang matinding punto o pag-vertex ng magagawa na rehiyon. Kaya:

Kung ang linya na pinakamalapit sa pinagmulan ay may isang buong segment na karaniwan sa magagawa na rehiyon, sinasabing mayroong walang katapusang mga solusyon. Ang kasong ito ay nangyayari kung ang slope ng linya ng iso-profit ay katumbas ng alinman sa iba pang mga linya na naglilimita sa rehiyon.

Para sa aming pastry, ang mga kandidato ng vertice ay A, B, at C.

- Paraan ng simplex na pamamaraan ni Dantzig

Ang graphical o geometric na pamamaraan ay naaangkop para sa dalawang variable. Gayunpaman, ito ay mas kumplikado kapag mayroong tatlong variable, at imposible na magamit para sa isang mas malaking bilang ng mga variable.

Kapag nakitungo sa mga problema na may higit sa dalawang variable, ginagamit ang simpleng paraan, na binubuo ng isang serye ng mga algorithm upang ma-optimize ang mga layunin na function. Ang mga matrice at simpleng aritmetika ay madalas na ginagamit upang maisagawa ang mga kalkulasyon.

Ang pamamaraan ng simplex ay nagsisimula sa pamamagitan ng pagpili ng isang magagawa na solusyon at suriin kung ito ay optimal. Kung ito ay, nalutas na natin ang problema, ngunit kung wala ito, nagpapatuloy tayo patungo sa isang solusyon na mas malapit sa pag-optimize. Kung umiiral ang solusyon, nahahanap ito ng algorithm sa ilang mga pagsubok.

Aplikasyon

Ang linear at non-linear programming ay inilalapat sa maraming mga patlang upang makagawa ng pinakamahusay na mga pagpapasya sa mga tuntunin ng pagbabawas ng mga gastos at pagtaas ng kita, na hindi palaging pananalapi, dahil masusukat sa oras, halimbawa, kung nais mong mabawasan ang oras na kinakailangan upang maisagawa ang isang serye ng mga operasyon.

Narito ang ilang mga patlang:

-Sa marketing ito ay ginagamit upang mahanap ang pinakamahusay na kumbinasyon ng media (mga social network, telebisyon, pindutin at iba pa) upang mag-advertise ng isang tiyak na produkto.

-Para sa pagtatalaga ng sapat na mga gawain sa mga tauhan ng isang kumpanya o pabrika o mga iskedyul sa kanila.

-Sa pagpili ng pinaka masustansiyang pagkain at sa pinakamababang gastos sa mga industriya ng baka at manok.

Malutas na ehersisyo

- Ehersisyo 1

Malikhaing malutas ang graphic linear na modelo ng programming na nakataas sa mga naunang seksyon.

Solusyon

Kinakailangan na i-graph ang hanay ng mga halaga na tinukoy ng sistema ng mga paghihigpit na tinukoy sa problema:

1. x ≥ 0
2. at ≥0
3. 9x + 8y ≤ 144
4. 0.5 x + 0.8y ≤ 10

Ang rehiyon na ibinigay ng mga hindi pagkakapantay-pantay 1 at 2 ay tumutugma sa unang kuwadrante ng eroplano ng Cartesian. Tungkol sa mga hindi pagkakapareho 3 at 4, nagsisimula kami sa pamamagitan ng paghahanap ng mga linya ng paghihigpit:

9x + 8y = 144

0.5 x + 0.8y = 10 → 5x + 8y = 100

Ang magagawa na rehiyon ay isang quadrilateral na ang mga vertice ay mga puntos A, B, C, at D.

Ang minimum na kita ay 0, samakatuwid ang linya 8x + 10y = 0 ay ang mas mababang limitasyon at ang mga linya ng iso-profit ay may slope -8/10 = - 0.8.

Ang halagang ito ay naiiba sa mga dalisdis ng iba pang mga linya ng paghihigpit at dahil ang magagawa na rehiyon ay nakatali, ang natatanging solusyon ay umiiral.

Larawan 5. Ang graphic na solusyon ng ehersisyo 1, na nagpapakita ng magagawa na rehiyon at ang solution point C sa isa sa mga vertice ng nasabing rehiyon. Pinagmulan: F. Zapata.

Ang solusyon na ito ay tumutugma sa isang linya ng slope -0.8 na dumadaan sa alinman sa mga puntos na A, B o C, na ang mga coordinate ay:

A (11; 5.625)

B (0; 12.5)

C (16, 0)

Optimum na solusyon

Kinakalkula namin ang halaga ng G para sa bawat isa sa mga puntong ito:

- (11; 5.625): G _A = 8 x 11 + 10 x 5.625 = 144.25

- (0; 12.5): G _B = 8 x 0 + 10 x 12.5 = 125

- (16, 0): G _C = 8 x 16 + 10 x 0 = 128

Ang pinakamataas na kita ay natagpuan ang pagmamanupaktura ng 11 itim na kagubatan ng kagubatan at 5,625 mga cake ng script. Ang solusyon na ito ay sumasang-ayon sa isang natagpuan sa pamamagitan ng software.

- Ehersisyo 2

Patunayan ang resulta ng nakaraang ehersisyo sa pamamagitan ng paggamit ng Solver function na magagamit sa karamihan ng mga spreadsheet tulad ng Excel o LibreOffice Calc, na isinasama ang Simplex algorithm para sa pag-optimize sa linear programming.

Solusyon

Larawan 6. Detalye ng solusyon mula sa ehersisyo 1 hanggang sa Libre na Pagpapalawak ng Kalakal ng Opisina. Pinagmulan: F. Zapata.

Larawan 7. Detalye ng solusyon mula sa ehersisyo 1 hanggang sa Libre na Pagpapalawak ng Kalakal ng Opisina. Pinagmulan: F. Zapata.

Mga Sanggunian

1. Napakatalino. Pag-Programming ng Linya. Nabawi mula sa: brilliant.org.
2. Eppen, G. 2000. Mga Operasyong Pananaliksik sa Pang-agham na Agham. Ika-5. Edisyon. Prentice Hall.
3. Haeussler, E. 1992. Matematika para sa Pamamahala at Pangkabuhayan. Ika-2. Edisyon. Grupo Editorial Iberoamericana.
4. Hiru.eus. Pag-programming ng linear. Nabawi mula sa: hiru.eus.
5. Wikipedia. Pag-programming ng linear. Nabawi mula sa: es. wikipedia.org.