Kung ikaw ay isang engineer o isang mag-aaral ng engineering, maaaring alam mo kung ano ang ibig sabihin ng pag-optimize.
Upang makuha ang pinakamahusay na posibleng resulta, mahalagang hanapin ang pinakamahusay na paraan upang gawin ang mga bagay.
Sa linear programming, maaari kang gumamit ng pangunahing solusyon upang mahanap ang pinakamahusay na solusyon.
Ngunit ano ang pangunahing solusyon, at bakit napakahalagang malaman ng mga inhinyero ang tungkol sa kanila? Sa artikulong ito, pag-uusapan ko kung ano ang mga pangunahing solusyon, kung bakit mahalaga ang mga ito sa engineering, at kung paano magagamit ang mga ito upang makuha ang pinakamahusay na mga resulta sa iba't ibang sitwasyon.
Kaya buckle up at maghanda upang sumisid sa mundo ng mga pangunahing solusyon, kung saan aking sisirain ang mga misteryo at ipapakita sa iyo kung gaano kalakas ang diskarteng ito.
Mga Pangunahing Solusyon sa Linear Programming
Pormal na kahulugan:
Ang isang solusyon sa isang linear na modelo ng programa na binubuo ng m equation sa n variable ay nakuha sa pamamagitan ng paglutas para sa m variable sa mga tuntunin ng natitirang (nm) variable at pagtatakda ng (nm) variable na katumbas ng zero.
Ang isang pangunahing solusyon sa linear programming ay isang paraan upang malutas ang isang linear na problema sa programming na nakakatugon sa ilang mga teknikal na kinakailangan.
Sa partikular, ang isang vector x ay isang pangunahing solusyon para sa isang polyhedron kung ang mga vectors {ai : xi = 0} ay linearly independent.
Nangangahulugan ito na ang mga column ng A na may mga variable na xi na hindi zero ay linearly independent.
Ang isang pangunahing solusyon na may hindi negatibong mga bahagi ay tinatawag na isang pangunahing magagawa na solusyon (BFS) (BFS).
Ang isang BFS ay nakakatugon sa lahat ng mga patakaran na tumutukoy sa isang polyhedron.
Ang bawat BFS ay isang sulok ng polyhedron ng mga magagawang solusyon mula sa isang geometric na punto ng view.
Upang makahanap ng pangunahing solusyon, dapat mong itakda ang mga variable ng nm na hindi basic sa zero at lutasin ang mga m variable na basic.
Posible para sa iba't ibang mga base na humantong sa parehong pangunahing solusyon, na nangangahulugan na maaaring mayroong higit sa isang paraan upang malutas ang parehong problema.
Ang Simplex Method ay isang umuulit na proseso na lumilipat mula sa isang BFS patungo sa susunod na BFS hanggang sa mahanap nito ang pinakamahusay na BFS.
Pagkatapos gamitin ang simplex na paraan upang makahanap ng BFS, malalaman natin kung ang solusyon ay ang pinakamahusay sa pamamagitan ng pag-alam kung ang anumang iba pang BFS sa malapit ay nagbibigay ng mas mahusay na halaga para sa layunin na function.
Kung walang ganoong BFS, kung gayon ang kasalukuyang BFS ay ang pinakamahusay.
Modelo ng Linear Programming
Ang isang linear na modelo ng programming ay nagsasangkot ng tatlong pangunahing bahagi: mga variable ng desisyon, isang layunin na function, at mga hadlang.
Parehong ang layunin ng pag-andar at ang mga hadlang ay dapat na mga linear na pag-andar, at ang mga variable ng desisyon ay dapat na tuluy-tuloy.
Ang layunin ng function ay ginagamit sa alinman sa pagtaas o pagbaba ng isang numero na kumakatawan sa kita, gastos, bilang ng mga produktong ginawa, atbp.
Ang mga hadlang ay mga limitasyon o paghihigpit sa kabuuang halaga ng isang tiyak na mapagkukunan na kailangan upang magawa ang mga gawain na tutukuyin ang antas ng tagumpay sa mga variable ng desisyon.
Bilang karagdagan, ang ilang mga linear na programa ay nangangailangan na ang lahat ng mga variable ng desisyon ay hindi negatibo.
Sa mga linear programming model, maaari mo ring gamitin ang integer at binary variable.
Ang mga binary variable ay maaari lamang magkaroon ng value na 0 o 1, kaya maaari lang silang magkaroon ng value na 0 o 1.
Ang Simplex Method
Ang isa sa mga pinaka ginagamit na paraan upang malutas ang mga problema sa linear programming ay ang Simplex Method.
Mahalaga ang mga pangunahing solusyon sa pamamaraang simplex dahil tumutugma ang mga ito sa mga punto ng sulok ng rehiyon na magagawa, at ang paraan ng simplex ay gumagalaw mula sa isang sulok patungo sa isa pa hanggang sa makahanap ng pinakamainam na solusyon.
Ang simplex na paraan ay isang mabilis na paraan upang mahanap ang pinakamahusay na sagot sa isang linear na problema sa programming sa pamamagitan ng paggamit ng mga katangian ng mga pangunahing solusyon.
Upang magamit ang simplex na paraan upang mahanap ang pinakamahusay na BFS, kailangan nating maghanap ng batayan B para sa constraint matrix A at lutasin ang system Ax = b kasama ang lahat ng mga variable maliban sa batayan na nakatakda sa zero.
Ang mga resultang halaga para sa mga pangunahing variable ay bumubuo ng isang BFS.
Kung mayroong isang pinakamainam na solusyon, pagkatapos ay mayroong isang pinakamainam na BFS.
Ang Simplex Method ay gumagalaw mula sa isang BFS patungo sa isang katabing BFS hanggang sa maabot nito ang pinakamainam na BFS sa pamamagitan ng paggamit ng mga pivot procedure.
Paghahambing sa pagitan ng Mga Pangunahing Solusyon at Mga Magagawang Solusyon
Ang pagkakaiba sa pagitan ng isang pangunahing solusyon at isang magagawa na solusyon ay ang isang pangunahing solusyon ay hindi kailangang matugunan ang anumang mga kundisyon.
Sa partikular, dapat itong may mga vector na linearly independent at may mga non-zero value para sa xi, at ang x ay dapat mas mababa sa 0.
Sa kabilang banda, ang isang magagawang solusyon ay anumang punto na umaangkop sa loob ng mga limitasyon ng problema.
Ngunit hindi lahat ng magagawang solusyon ay mga pangunahing magagawang solusyon.
Ang mga basic feasible solutions (BFSs) ay ang mga tumutugma lamang sa mga sulok ng polyhedron ng mga feasible solution.
Bumalik sa Mga Pangunahing Kaalaman: Pag-unlock sa Kapangyarihan ng Mga Pangunahing Solusyon sa Engineering
Mahirap pa bang intindihin? Hayaan akong baguhin nang kaunti ang pananaw:
Sawa ka na ba sa paggamit ng mga kumplikadong pamamaraan at algorithm upang malutas ang mahihirap na problema? Nais mo bang magkaroon ng isang mas simple, mas tapat na paraan upang harapin ang iyong mga problema sa modelo ng linear program?
Buweno, huwag mag-alala, dahil ang sagot ay narito: lutasin ang mga m variable sa mga tuntunin ng natitirang (nm) na mga variable, at itakda ang (nm) na mga variable sa zero.
Sino ang nangangailangan ng mga algorithm na mukhang magarbong kapag maaari kang bumalik sa mga pangunahing kaalaman? Kaya itabi ang iyong mga calculator at simulan natin ang pag-aaral tungkol sa mga simpleng solusyon.
Okay, joke lang iyon na ginawang parang TV ad.
Ngayon bumalik tayo sa paliwanag.
Basic Solution Linear Programming
Tip: I-on ang caption button kung kailangan mo ito. Piliin ang "awtomatikong pagsasalin" sa button ng mga setting, kung hindi ka pamilyar sa sinasalitang wika. Maaaring kailanganin mong i-click muna ang wika ng video bago maging available ang iyong paboritong wika para sa pagsasalin.
Mga kaso ng paggamit
| Ginamit sa: | Paglalarawan: |
|---|---|
| Paglalaan ng Mga Mapagkukunan: | Maaaring gamitin ang pangunahing solusyon sa mga problema sa paglalaan ng mapagkukunan, kung saan ang layunin ay hatiin ang mga limitadong mapagkukunan sa mga nakikipagkumpitensyang pangangailangan. Halimbawa, maaaring kailanganin ng isang kumpanya na hatiin ang badyet nito sa iba't ibang departamento o proyekto. Sa pamamagitan ng paggamit ng mga pangunahing solusyon, maaari nilang malaman ang pinakamahusay na paraan upang magamit ang kanilang mga mapagkukunan upang kumita ng pinakamaraming pera o gumastos nang kaunti hangga't maaari. |
| Pagpaplano para sa Produksyon: | Sa pagpaplano ng produksyon, ang pangunahing solusyon ay maaaring gamitin upang malaman ang pinakamahusay na halo ng mga produkto na gagawin upang kumita ng pinakamaraming pera. Mahahanap ng mga kumpanya ang pinakamahusay na halo ng produksyon na nagdudulot ng pinakamaraming pera at pinakamababa ang gastos sa pamamagitan ng paggamit ng pangunahing solusyon. |
| Pag-iiskedyul: | Maaaring gamitin ang pangunahing solusyon upang malaman kung paano mag-iskedyul ng mga gawain o trabaho upang magawa ang mga ito sa pinakamabisang paraan. Halimbawa, maaaring kailanganin ng isang kumpanya na planuhin ang mga oras ng trabaho ng mga empleyado nito upang matiyak na mayroon silang sapat na manggagawa kapag abala ang negosyo. Sa pamamagitan ng paggamit ng isang pangunahing solusyon, maaari nilang malaman ang pinakamahusay na paraan upang mag-iskedyul ng mga bagay upang magkaroon ng kaunting downtime hangga't maaari at mas maraming trabaho ang magagawa hangga't maaari. |
| Pamamahala ng Supply Chain: | Sa pamamahala ng supply chain, ang layunin ay tiyakin na ang mga kalakal at serbisyo ay gumagalaw nang maayos hangga't maaari mula sa supplier patungo sa customer. Halimbawa, maaaring kailanganin ng isang negosyo na alamin ang pinakamahusay na mga ruta para sa pagdadala ng mga kalakal upang mapanatiling minimum ang mga gastos at maihatid ang mga kalakal sa oras. Sa pamamagitan ng paggamit ng mga pangunahing solusyon, mahahanap nila ang pinakamahusay na plano para sa pamamahala ng supply chain na nagpapanatili ng mababang gastos at nagpapanatili sa mga customer na masaya. |
| Pag-optimize ng Portfolio: | Sa portfolio optimization, kung saan ang layunin ay upang mahanap ang pinakamahusay na kumbinasyon ng mga pamumuhunan upang kumita ng pinakamaraming pera habang kumukuha ng hindi bababa sa panganib, ang mga pangunahing solusyon ay maaaring gamitin. Halimbawa, maaaring kailanganin ng isang kumpanya ng pamumuhunan na alamin ang pinakamahusay na halo ng mga stock, bono, at iba pang mga mahalagang papel upang matulungan ang kanilang mga kliyente na maabot ang kanilang mga layunin sa pamumuhunan. Sa pamamagitan ng paggamit ng isang simpleng solusyon, mahahanap nila ang pinakamahusay na paraan upang paghaluin ang kanilang mga portfolio upang makuha nila ang pinakamahusay na pagbabalik habang kumukuha ng pinakamababang halaga ng panganib. |
Konklusyon
Sa konklusyon, ang ideya ng isang pangunahing solusyon ay napakahalaga sa larangan ng engineering at maaaring magamit sa maraming iba't ibang paraan.
Sa pamamagitan ng pag-alam kung ano ang isang pangunahing solusyon at kung ano ang ginagawa nito sa linear programming, maaari naming pagbutihin ang mga solusyon, bawasan ang mga gastos, at gawing mas mahusay ang mga ito.
Ngunit mahalagang tandaan na ang pangunahing solusyon ay hindi isang solong sukat na solusyon, kahit na ito ay isang mahusay na tool.
Upang makuha ang pinakamahusay na mga resulta, ang bawat problema ay kailangang maingat na tingnan at pag-isipan.
Bilang mga inhinyero, kailangan nating patuloy na tingnan kung paano makakatulong sa atin ang mga pangunahing solusyon at iba pang diskarte sa pag-optimize na umunlad at makabuo ng mga bagong ideya.
Kaya, kilalanin natin ang kapangyarihan ng mga simpleng solusyon at patuloy na itulak ang mga limitasyon ng kung ano ang posible sa pamamagitan ng paggamit ng mga bagong diskarte at diskarte.
Mga link at sanggunian
Mga Aklat:
- Linear Programming ni Vasek Chvatal
- Pagmomodelo at Paglutas ng Linear Programming sa R ni Jose M. Sallan
Ibahagi sa…
