Tinutulungan ka ng pag-optimize na mahanap ang pinakamahusay na resulta na nagdudulot ng kita, nagpapababa ng mga gastos, o nagtatakda ng parameter na nagdudulot ng mga pagkabigo sa proseso ng negosyo.
Ang prosesong ito ay tinatawag ding mathematical programming. Nilulutas nito ang problema ng pagtukoy sa pamamahagi ng mga limitadong mapagkukunan na kinakailangan upang makamit ang layunin na itinakda ng pinuno ng problema sa pag-optimize. Sa lahat ng posibleng opsyon, kanais-nais na hanapin ang isa na nagpapalaki (o nagpapababa) ng parameter ng pagkontrol, halimbawa, kita o gastos. Ang mga modelo ng pag-optimize ay tinatawag ding prescriptive o normative dahil hinahangad nilang makahanap ng isang praktikal na diskarte para sa negosyo.
Kasaysayan ng pag-unlad
Linear programming (LP) ay gumagana sa isang klase ng mga problema sa pag-optimize kung saan ang lahat ng mga hadlang ay linear.
Paglalahad ng maikling kasaysayan ng pagbuo ng LP:
- Noong 1762, nilutas ni Lagrange ang mga simpleng problema sa pag-optimize na may mga hadlang sa pagkakapantay-pantay.
- Noong 1820, nagpasya si Gausslinear system ng mga equation gamit ang elimination.
- Noong 1866, ginawang perpekto ni Wilhelm Jordan ang paraan ng paghahanap ng mga error na hindi bababa sa mga parisukat bilang isang angkop na pamantayan. Tinatawag na itong Gauss-Jordan method.
- Lumataw ang digital computer noong 1945.
- Inimbento ni Danzig ang mga simplex na pamamaraan noong 1947.
- Noong 1968, ipinakilala nina Fiacco at McCormick ang paraan ng Inside Point.
- Noong 1984, ginamit ni Karmarkar ang panloob na pamamaraan upang malutas ang mga linear na programa, idinagdag ang kanyang makabagong pagsusuri.
Ang LP ay napatunayang isang napakalakas na tool para sa pagmomodelo ng mga problema sa totoong mundo at bilang malawakang inilapat na teorya sa matematika. Gayunpaman, maraming kawili-wiling problema sa pag-optimize ang hindi linear.
Ano ang gagawin sa kasong ito? Ang pag-aaral ng naturang mga problema ay nagsasangkot ng iba't ibang pinaghalong linear algebra, multivariate calculus, numerical analysis, at computational na pamamaraan. Gumagawa ang mga siyentipiko ng mga computational algorithm, kabilang ang mga pamamaraan ng interior point para sa linear programming, geometry, pagsusuri ng mga convex set at function, at ang pag-aaral ng mga espesyal na structured na problema gaya ng quadratic programming.
Nonlinear optimization ay nagbibigay ng pangunahing pag-unawa sa mathematical analysis at malawakang ginagamit sa iba't ibang larangan gaya ng engineering, regression analysis, resource management, geophysical exploration at economics.
Pag-uuri ng mga problema sa pag-optimize
Isang mahalagang hakbangAng proseso ng pag-optimize ay ang pag-uuri ng mga modelo, dahil ang kanilang mga algorithm ng solusyon ay iniangkop sa isang partikular na uri.
1. Mga problema sa discrete at tuluy-tuloy na pag-optimize. Ang ilang mga modelo ay may katuturan lamang kung ang mga variable ay kumukuha ng mga halaga mula sa isang discrete subset ng mga integer. Ang iba ay naglalaman ng data na maaaring tumagal sa anumang tunay na halaga. Kadalasan ay mas madaling malutas ang mga ito. Ang mga pagpapahusay sa mga algorithm, na sinamahan ng mga pag-unlad sa teknolohiya ng computer, ay kapansin-pansing nagpalaki sa laki at pagiging kumplikado ng isang linear programming optimization problem.
2. Walang limitasyon at limitadong pag-optimize. Ang isa pang mahalagang pagkakaiba ay ang mga gawain kung saan walang hadlang sa mga variable. Malawak ang saklaw nito mula sa mga simpleng estimator hanggang sa mga sistema ng pagkakapantay-pantay at hindi pagkakapantay-pantay na nagmomodelo ng mga kumplikadong ugnayan sa pagitan ng data. Ang mga ganitong problema sa pag-optimize ay maaaring higit pang uriin ayon sa likas na katangian ng mga function (linear at non-linear, convex at smooth, differentiable at non-differentiable).
3. Mga gawain sa pagiging posible. Ang kanilang layunin ay makahanap ng mga variable na halaga na nakakatugon sa mga hadlang sa modelo nang walang anumang partikular na layunin sa pag-optimize.
4. Mga gawaing pantulong. Malawakang ginagamit ang mga ito sa teknolohiya at ekonomiya. Ang layunin ay upang makahanap ng solusyon na nakakatugon sa mga kondisyon ng complementarity. Sa pagsasagawa, ang mga gawaing may maraming layunin ay madalas na binago sa iisang layunin.
5. Deterministic versus stochastic optimization. Ipinapalagay ng deterministic optimization na ang data para saganap na tumpak ang mga takdang-aralin. Gayunpaman, sa maraming napapanahong isyu, hindi sila malalaman sa maraming dahilan.
Ang una ay may kinalaman sa isang simpleng error sa pagsukat. Ang pangalawang dahilan ay mas pangunahing. Ito ay nakasalalay sa katotohanan na ang ilang data ay kumakatawan sa impormasyon tungkol sa hinaharap, halimbawa, ang demand para sa isang produkto o ang presyo para sa isang hinaharap na yugto ng panahon. Kapag nag-o-optimize sa ilalim ng stochastic na mga kondisyon sa pag-optimize, ang kawalan ng katiyakan ay kasama sa modelo.
Mga Pangunahing Bahagi
Ang layunin ng function ay ang dapat i-minimize o i-maximize. Karamihan sa mga uri ng mga problema sa pag-optimize ay may isang layunin na function. Kung hindi, madalas na reformulated ang mga ito upang gumana.
Dalawang pagbubukod sa panuntunang ito:
1. Target na gawain sa paghahanap. Sa karamihan ng mga aplikasyon sa negosyo, nais ng manager na makamit ang isang partikular na layunin habang natutugunan ang mga hadlang sa modelo. Ang gumagamit ay hindi partikular na nais na i-optimize ang isang bagay, kaya walang saysay na tukuyin ang isang layunin na function. Ang ganitong uri ay karaniwang tinutukoy bilang isang problema sa satisfiability.
2. Maraming mga layunin na tampok. Kadalasan, nais ng isang user na mag-optimize ng ilang magkakaibang layunin nang sabay-sabay. Karaniwan silang hindi magkatugma. Ang mga variable na nag-o-optimize para sa isang layunin ay maaaring hindi ang pinakamahusay para sa iba.
Mga uri ng bahagi:
- Ang isang kinokontrol na input ay isang hanay ng mga variable ng desisyon na nakakaapekto sa halaga ng isang layunin na function. Sa isang gawain sa produksyon, maaaring kabilang sa mga variable ang pamamahagi ng iba't ibang magagamit na mapagkukunan o ang kinakailangang paggawabawat aksyon.
- Ang Constraints ay mga ugnayan sa pagitan ng mga variable at parameter ng desisyon. Para sa problema sa produksyon, hindi makatuwirang gumugol ng maraming oras sa anumang aktibidad, kaya limitahan ang lahat ng "pansamantalang" variable.
- Posible at pinakamainam na solusyon. Ang halaga ng desisyon para sa mga variable, kung saan nasiyahan ang lahat ng mga hadlang, ay tinatawag na satisfiable. Karamihan sa mga algorithm ay unang nahanap ito, pagkatapos ay subukang pagbutihin ito. Sa wakas, binabago nila ang mga variable upang lumipat mula sa isang magagawang solusyon patungo sa isa pa. Ang prosesong ito ay paulit-ulit hanggang ang layunin ng function ay umabot sa maximum o minimum nito. Ang resultang ito ay tinatawag na pinakamainam na solusyon.
Ang mga algorithm ng mga problema sa pag-optimize na binuo para sa mga sumusunod na mathematical program ay malawakang ginagamit:
- Convex.
- Mapaghiwalay.
- Quadratic.
- Geometric.
Google Linear Solvers
Ang Linear optimization o programming ay ang pangalang ibinigay sa proseso ng computational ng mahusay na paglutas ng problema. Ito ay itinulad bilang isang hanay ng mga linear na relasyon na lumitaw sa maraming disiplina sa siyensya at engineering.
Nag-aalok ang Google ng tatlong paraan upang malutas ang mga problema sa linear optimization:
- Glop open source library.
- Linear Optimization add-on para sa Google Sheets.
- Linear Optimization Service sa Google Apps Script.
Ang Glop ay binuo sa Googlelinear solver. Ito ay magagamit sa open source. Maa-access mo ang Glop sa pamamagitan ng OR-Tools linear solver wrapper, na isang wrapper para sa Glop.
Linear optimization module para sa Google Sheets ay nagbibigay-daan sa iyong magsagawa ng linear na pahayag ng problema sa pag-optimize sa pamamagitan ng paglalagay ng data sa isang spreadsheet.
Quadratic programming
Gumagamit ang Premium Solver platform ng pinahabang LP/Quadratic na bersyon ng Simplex method na may mga limitasyon sa pagpoproseso ng problema sa LP at QP na hanggang 2000 na variable ng desisyon.
Ang SQP Solver para sa malalaking problema ay gumagamit ng modernong pagpapatupad ng aktibong set na paraan na may kalat upang malutas ang mga problema sa quadratic programming (QP). Gumagamit ang XPRESS Solver engine ng natural na extension ng "Interior Point" o Newton Barrier na paraan upang malutas ang mga problema sa QP.
Inilalapat ng MOSEK Solver ang naka-embed na "Inside Point" at mga auto-dual na pamamaraan. Ito ay lalong epektibo para sa maluwag na pinagsamang mga problema sa QP. Maaari din nitong lutasin ang mga problema sa Scale Quadratic Constraint (QCP) at Second Order Cone Programming (SOCP).
Multi-operation calculations
Matagumpay na ginagamit ang mga ito sa paggamit ng mga feature ng Microsoft Office, halimbawa, paglutas ng mga problema sa pag-optimize sa Excel.
Sa talahanayan sa itaas, ang mga simbolo ay:
- K1 - K6 - mga customer na kailangang magbigay ng mga kalakal.
- S1 - Ang S6 ay mga potensyal na site ng produksyon na maaaring itayo para dito. Maaaring malikha1, 2, 3, 4, 5 o lahat ng 6 na lokasyon.
May mga nakapirming gastos para sa bawat pasilidad na nakalista sa column I (Ayusin).
Kung walang binago ang lokasyon, hindi ito mabibilang. Pagkatapos ay walang mga nakapirming gastos.
Tukuyin ang mga potensyal na lokasyon upang makuha ang pinakamababang halaga.
Sa mga kundisyong ito, ang lokasyon ay naitatag o hindi. Ang dalawang estadong ito ay: "TAMA - MALI" o "1 - 0". Mayroong anim na estado para sa anim na lokasyon, halimbawa, ang 000001 ay nakatakda sa ikaanim lamang, 111111 ay nakatakda sa lahat.
Sa binary number system, may eksaktong 63 iba't ibang opsyon mula 000001 (1) hanggang 111111 (63).
Ang L2-L64 ay dapat na ngayong basahin ang {=MULTIPLE OPERATION (K1)}, ito ang mga resulta ng lahat ng alternatibong solusyon. Pagkatapos ang minimum na halaga ay=Min (L) at ang katumbas na alternatibo ay INDEX (K).
CPLEX Integer Programming
Minsan ang isang linear na relasyon ay hindi sapat para makarating sa puso ng isang problema sa negosyo. Ito ay totoo lalo na kapag ang mga desisyon ay nagsasangkot ng mga discrete na pagpipilian, gaya ng kung magbubukas o hindi ng isang bodega sa isang partikular na lokasyon. Sa mga sitwasyong ito, dapat gamitin ang integer programming.
Kung ang problema ay nagsasangkot ng parehong discrete at tuloy-tuloy na mga pagpipilian, ito ay isang mixed integer program. Maaari itong magkaroon ng mga linear, convex na quadratic na problema at kaparehong second order constraints.
Ang mga integer program ay mas kumplikado kaysa sa mga linear na programa, ngunit mayroon silang mahahalagang aplikasyon sa negosyo. SoftwareGumagamit ang CPLEX software ng mga kumplikadong pamamaraan ng matematika upang malutas ang mga problema sa integer. Kasama sa kanyang mga pamamaraan ang sistematikong paghahanap para sa mga posibleng kumbinasyon ng mga discrete variable gamit ang linear o quadratic na mga relaxation ng software upang makalkula ang mga hangganan sa halaga ng pinakamainam na solusyon.
Gumagamit din sila ng LP at iba pang paraan ng paglutas ng problema sa pag-optimize para kalkulahin ang mga hadlang.
Standard Microsoft Excel Solver
Ginagamit ng teknolohiyang ito ang pangunahing pagpapatupad ng pangunahing paraan ng Simplex upang malutas ang mga problema sa LP. Ito ay limitado sa 200 variable. Gumagamit ang "Premium Solver" ng pinahusay na paraan ng primary simplex na may dalawang panig na mga hangganan para sa mga variable. Gumagamit ang Premium Solver platform ng pinahabang bersyon ng LP/Quadratic Simplex Solver para lutasin ang isang problema sa pag-optimize na may hanggang 2000 na mga variable ng desisyon.
Ang Large-scale LP para sa Premium Solver platform ay naglalapat ng makabagong pagpapatupad ng simple at double simplex na paraan, na gumagamit ng sparsity sa LP model upang makatipid ng oras at memorya, mga advanced na diskarte para sa pag-update at refactoring matrice, maramihan at bahagyang pagpepresyo at pag-ikot, at para sa pagtagumpayan ng pagkabulok. Available ang makinang ito sa tatlong bersyon (may kakayahang humawak ng hanggang 8,000, 32,000, o walang limitasyong mga variable at limitasyon).
Ang MOSEK Solver ay may kasamang pangunahin at dual simplex, isang paraan na nagsasamantala rin sa sparsity at gumagamit ng mga advanced na diskarte para sa pag-update ng matrix at "refactorization." Nilulutas nito ang mga problema ng walang limitasyong laki, aysinubukan sa mga problema sa linear programming na may milyun-milyong variable ng desisyon.
Hakbang-hakbang na halimbawa sa EXCEL
Upang tukuyin ang modelo ng problema sa pag-optimize sa Excel, gawin ang mga sumusunod na hakbang:
- Ayusin ang data para sa problema sa isang spreadsheet sa lohikal na anyo.
- Pumili ng cell upang iimbak ang bawat variable.
- Gumawa sa cell ng formula para sa pagkalkula ng target na mathematical model ng problema sa pag-optimize.
- Gumawa ng mga formula para kalkulahin ang kaliwang bahagi ng bawat hadlang.
- Gumamit ng mga dialog sa Excel para sabihin sa Solver ang tungkol sa mga variable ng desisyon, target, hadlang, at gustong mga hangganan sa mga parameter na iyon.
- Patakbuhin ang "Solver" upang mahanap ang pinakamainam na solusyon.
- Gumawa ng Excel sheet.
- Ayusin ang data para sa problema sa Excel kung saan kinakalkula ang formula para sa layunin ng function at pagpilit.
Sa talahanayan sa itaas, ang mga cell B4, C4, D4, at E4 ay nakalaan upang kumatawan sa mga variable ng desisyon X 1, X 2, X 3, at X 4. Mga halimbawa ng desisyon:
- Ang modelo ng paghahalo ng produkto ($450, $1150, $800, at $400 na kita bawat produkto) ay inilagay sa mga cell B5, C5, D5, at E5, ayon sa pagkakabanggit. Nagbibigay-daan ito sa target na kalkulahin sa F5=B5B4 + C5C4 + D5D4 + E5E4 o F5:=SUMPRODUCT (B5: E5, B4: E4).
- Sa B8 ipasok ang halaga ng mga mapagkukunang kinakailangan upang gawin ang bawat uri ng produkto.
- Formula para sa F8:=SUMPRODUCT(B8:E8, $B$4:$E$4).
- Kopyahin itoformula sa F9. Ang mga dollar sign sa $B$4:$E$4 ay nagpapahiwatig na ang hanay ng cell na ito ay nananatiling pare-pareho.
- Sa G8 ipasok ang magagamit na halaga ng mga mapagkukunan ng bawat uri, na naaayon sa mga halaga ng mga paghihigpit sa kanan. Binibigyang-daan ka nitong ipahayag ang mga ito nang ganito: F11<=G8: G11.
- Ito ay katumbas ng apat na limitasyon F8<=G8, F9 <=G9, F10 <=G10 at F11=0
Mga larangan ng praktikal na aplikasyon ng pamamaraan
Ang linear optimization ay may maraming praktikal na aplikasyon bilang halimbawa ng problema sa pag-optimize:
Ang isang kumpanya ay maaaring gumawa ng ilang produkto na may kilalang margin ng kontribusyon. Ang produksyon ng isang yunit ng bawat item ay nangangailangan ng kilalang halaga ng limitadong mapagkukunan. Ang gawain ay lumikha ng isang programa sa produksyon upang matukoy kung gaano karami sa bawat produkto ang dapat gawin upang ang kita ng kumpanya ay mapalaki nang hindi lumalabag sa mga hadlang sa mapagkukunan.
Ang mga problema sa paghahalo ay ang solusyon sa mga problema sa pag-optimize na nauugnay sa pagsasama-sama ng mga sangkap sa panghuling produkto. Ang isang halimbawa nito ay ang problema sa diyeta na pinag-aralan ni George Danzig noong 1947. Ang ilang mga hilaw na materyales ay ibinibigay, tulad ng oats, baboy at mirasol na langis, kasama ang kanilang nutritional content, tulad ng protina, taba, bitamina A, at ang kanilang presyo kada kilo. Ang hamon ay paghaluin ang isa o higit pang mga panghuling produkto mula sa mga hilaw na materyales sa pinakamababang posibleng halaga habang iginagalang ang minimum at maximum na mga limitasyon para sa kanilang nutritional value.
Ang isang klasikong aplikasyon ng isang linear na problema sa pag-optimize ay upang matukoy ang pagruruta para sa mga pangangailangantrapiko sa telekomunikasyon o mga network ng transportasyon. Kasabay nito, ang mga daloy ay dapat na iruruta sa network sa paraang ang lahat ng kinakailangan sa trapiko ay natutugunan nang hindi lumalabag sa mga kundisyon ng bandwidth.
Sa mathematical theory, ang linear optimization ay maaaring gamitin upang kalkulahin ang pinakamainam na diskarte sa zero-sum na laro para sa dalawang tao. Sa kasong ito, kinakalkula ang probability distribution para sa bawat kalahok, na siyang coefficient ng random na paghahalo ng kanyang mga diskarte.
Walang matagumpay na proseso ng negosyo sa mundo ang posible nang walang pag-optimize. Mayroong maraming mga optimization algorithm na magagamit. Ang ilang mga pamamaraan ay angkop lamang para sa ilang mga uri ng mga problema. Mahalagang makilala ang kanilang mga katangian at piliin ang naaangkop na paraan ng solusyon.
