Uboreshaji hukusaidia kupata matokeo bora zaidi ambayo huleta faida, kupunguza gharama, au kuweka vigezo vinavyosababisha kushindwa kwa mchakato wa biashara.
Mchakato huu pia huitwa upangaji wa kihesabu. Inasuluhisha shida ya kuamua usambazaji wa rasilimali ndogo muhimu ili kufikia lengo lililowekwa na mkuu wa shida ya uboreshaji. Kati ya chaguzi zote zinazowezekana, inahitajika kupata ile inayoongeza (au kupunguza) paramu ya kudhibiti, kwa mfano, faida au gharama. Miundo ya uboreshaji pia huitwa maagizo au kanuni kwa sababu inatafuta kutafuta mbinu inayowezekana ya biashara.
Historia ya Maendeleo
Upangaji programu (LP) hufanya kazi na aina ya matatizo ya uboreshaji ambapo vikwazo vyote ni mstari.
Inawasilisha historia fupi ya maendeleo ya LP:
- Mnamo 1762, Lagrange ilitatua matatizo rahisi ya uboreshaji yenye vikwazo vya usawa.
- Mnamo 1820, Gauss aliamuamfumo wa mstari wa milinganyo kwa kutumia kuondoa.
- Mnamo 1866, Wilhelm Jordan aliboresha mbinu ya kupata makosa ya miraba angalau kama kigezo cha kufaa. Hii sasa inaitwa mbinu ya Gauss-Jordan.
- Kompyuta ya kidijitali ilionekana mwaka wa 1945.
- Danzig alivumbua mbinu rahisi mwaka wa 1947.
- Mnamo 1968, Fiacco na McCormick walianzisha mbinu ya Inside Point.
- Mnamo 1984, Karmarkar alitumia mbinu ya mambo ya ndani kutatua programu laini, akiongeza uchanganuzi wake wa kiubunifu.
LP imethibitishwa kuwa zana yenye nguvu sana ya kuiga matatizo ya ulimwengu halisi na kama nadharia inayotumika sana ya hisabati. Hata hivyo, matatizo mengi ya kuvutia ya uboreshaji si ya mstari.
Nini cha kufanya katika kesi hii? Utafiti wa matatizo kama haya unahusisha mchanganyiko mbalimbali wa aljebra ya mstari, calculus multivariate, uchambuzi wa nambari, na mbinu za computational. Wanasayansi wanatengeneza algoriti za kukokotoa, ikiwa ni pamoja na mbinu za mambo ya ndani kwa ajili ya upangaji wa mstari, jiometri, uchanganuzi wa seti na utendakazi mbonyeo, na uchunguzi wa matatizo yaliyopangwa mahususi kama vile upangaji programu wa quadratic.
Uboreshaji usio wa mstari hutoa uelewa wa kimsingi wa uchanganuzi wa hisabati na hutumiwa sana katika nyanja mbalimbali kama vile uhandisi, uchanganuzi wa urejeshaji nyuma, usimamizi wa rasilimali, uchunguzi wa kijiofizikia na uchumi.
Uainishaji wa matatizo ya uboreshaji
Hatua muhimuMchakato wa uboreshaji ni uainishaji wa miundo, kwa kuwa algoriti zao za utatuzi hubadilishwa kwa aina fulani.
1. Matatizo ya uboreshaji wa kipekee na unaoendelea. Baadhi ya miundo huwa na maana ikiwa tu viwezo vinachukua thamani kutoka kwa kikundi kidogo cha nambari kamili. Nyingine zina data ambayo inaweza kuchukua thamani yoyote halisi. Kawaida ni rahisi kutatua. Maboresho ya algoriti, pamoja na maendeleo ya teknolojia ya kompyuta, yameongeza kwa kiasi kikubwa ukubwa na utata wa tatizo la uboreshaji wa upangaji wa mstari.
2. Uboreshaji usio na kikomo na mdogo. Tofauti nyingine muhimu ni kazi ambapo hakuna kikwazo kwa vigezo. Inaweza kuanzia kwa wakadiriaji rahisi hadi mifumo ya usawa na ukosefu wa usawa ambayo ni mfano wa uhusiano changamano kati ya data. Matatizo kama haya ya uboreshaji yanaweza kuainishwa zaidi kulingana na asili ya vitendakazi (mstari na zisizo na mstari, mbonyeo na laini, zinazoweza kutofautishwa na zisizotofautiana).
3. Kazi za upembuzi yakinifu. Lengo lao ni kupata thamani zinazobadilika zinazokidhi vikwazo vya modeli bila lengo maalum la uboreshaji.
4. Kazi za kukamilishana. Zinatumika sana katika teknolojia na uchumi. Lengo ni kutafuta suluhu inayokidhi masharti ya ukamilishano. Katika mazoezi, kazi zilizo na malengo kadhaa mara nyingi hubadilishwa kuwa lengo moja.
5. Kuamua dhidi ya uboreshaji wa stochastic. Uboreshaji dhabiti huchukulia kuwa data yakazi ni sahihi kabisa. Hata hivyo, kuhusu masuala mengi ya mada hayawezi kujulikana kwa sababu kadhaa.
Ya kwanza inahusiana na hitilafu rahisi ya kipimo. Sababu ya pili ni ya msingi zaidi. Inatokana na ukweli kwamba baadhi ya data inawakilisha taarifa kuhusu siku zijazo, kwa mfano, mahitaji ya bidhaa au bei ya muda ujao. Wakati wa kuboresha chini ya hali ya uboreshaji stochastic, kutokuwa na uhakika kunajumuishwa katika muundo.
Vipengele Vikuu
Lengo la kukokotoa ndilo la kupunguzwa au kuongezwa. Aina nyingi za shida za uboreshaji zina kazi ya lengo moja. Ikiwa sivyo, mara nyingi zinaweza kubadilishwa ili kufanya kazi.
Vighairi viwili kwa sheria hii:
1. Kazi ya utafutaji inayolengwa. Katika maombi mengi ya biashara, meneja anataka kufikia lengo maalum huku akitosheleza vizuizi vya mfano. Mtumiaji hataki sana kuboresha kitu, kwa hivyo haina mantiki kufafanua utendakazi wa lengo. Aina hii kwa kawaida hujulikana kama tatizo la kutosheka.
2. Vipengele vingi vya lengo. Mara nyingi, mtumiaji angependa kuboresha malengo kadhaa tofauti mara moja. Kwa kawaida haziendani. Vigezo vinavyoboresha lengo moja huenda visiwe bora kwa wengine.
Aina za vijenzi:
- Ingizo linalodhibitiwa ni mkusanyiko wa vigeu vya uamuzi vinavyoathiri thamani ya chaguo la kukokotoa la lengo. Katika kazi ya uzalishaji, vigezo vinaweza kujumuisha usambazaji wa rasilimali mbalimbali zilizopo au kazi inayohitajikakila kitendo.
- Vikwazo ni uhusiano kati ya viambatisho vya maamuzi na vigezo. Kwa tatizo la uzalishaji, haina maana kutumia muda mwingi kwenye shughuli yoyote, kwa hivyo punguza vigeu vyote "vya muda".
- Suluhu zinazowezekana na mojawapo. Thamani ya uamuzi kwa vigezo, ambayo vikwazo vyote vinatimizwa, inaitwa kutosheleza. Algorithms nyingi huipata kwanza, kisha jaribu kuiboresha. Mwishowe, wanabadilisha vigeu kutoka kwa suluhisho moja linalowezekana hadi lingine. Utaratibu huu unarudiwa hadi kazi ya lengo ifikie kiwango cha juu au cha chini. Matokeo haya yanaitwa suluhu bora zaidi.
Algorithms ya matatizo ya uboreshaji iliyoundwa kwa ajili ya programu zifuatazo za hisabati hutumika sana:
- Convex.
- Inatenganishwa.
- Quadratic.
- Jiometri.
Google Linear Solvers
Uboreshaji wa laini au upangaji programu ni jina linalotolewa kwa mchakato wa kukokotoa wa kutatua tatizo kikamilifu. Imeundwa kama seti ya uhusiano wa kimstari ambao hujitokeza katika taaluma nyingi za kisayansi na uhandisi.
Google inatoa njia tatu za kutatua matatizo ya uboreshaji wa mstari:
- Glop maktaba ya chanzo huria.
- Nongeza ya Uboreshaji wa Linear kwa Majedwali ya Google.
- Huduma ya Uboreshaji Linear katika Hati ya Google Apps.
Glop imeundwa ndani ya Googlekisuluhishi cha mstari. Inapatikana katika chanzo wazi. Unaweza kufikia Glop kupitia kanga ya kisuluhishi ya mstari ya OR-Tools, ambayo ni kanga ya Glop.
Sehemu ya uboreshaji laini ya Majedwali ya Google hukuruhusu kutekeleza kauli ya mstari ya tatizo la uboreshaji kwa kuingiza data kwenye lahajedwali.
Programu za Quadratic
Mfumo wa Premium Solver hutumia toleo lililopanuliwa la LP/Quadratic la mbinu ya Simplex yenye vikomo vya kuchakata matatizo ya LP na QP ya hadi vigeu 2000 vya maamuzi.
SQP Solver kwa matatizo makubwa hutumia utekelezwaji wa kisasa wa mbinu amilifu iliyowekwa na uchache kutatua matatizo ya programu ya quadratic (QP). Injini ya XPRESS Solver hutumia kiendelezi asili cha "Interior Point" au mbinu ya Newton Barrier kutatua matatizo ya QP.
MOSEK Solver inatumika "Ndani ya Pointi" iliyopachikwa na mbinu za uwili otomatiki. Hii ni nzuri sana kwa shida za QP zilizounganishwa kwa urahisi. Inaweza pia kutatua matatizo ya Scale Quadratic Constraint (QCP) na Second Order Cone Programming (SOCP).
Hesabu za operesheni nyingi
Zimetumika kwa mafanikio kwa matumizi ya vipengele vya Microsoft Office, kwa mfano, kutatua matatizo ya uboreshaji katika Excel.
Katika jedwali hapo juu, alama ni:
- K1 - K6 - wateja wanaohitaji kutoa bidhaa.
- S1 - S6 ni tovuti zinazowezekana za utayarishaji ambazo zinaweza kutengenezwa kwa hili. Inaweza kuundwa1, 2, 3, 4, 5 au maeneo yote 6.
Kuna gharama zisizobadilika kwa kila kituo kilichoorodheshwa katika safu wima ya I (Rekebisha).
Ikiwa eneo halitabadilisha chochote, halitahesabiwa. Kisha hakutakuwa na gharama zisizobadilika.
Tambua maeneo yanayoweza kupatikana ili kupata gharama ya chini zaidi.
Katika hali hizi, eneo linaweza kuthibitishwa au la. Majimbo haya mawili ni: "KWELI - UONGO" au "1 - 0". Kuna majimbo sita kwa maeneo sita, kwa mfano, 000001 imewekwa kuwa ya sita tu, 111111 imewekwa kwa yote.
Katika mfumo wa nambari jozi, kuna chaguo 63 tofauti kabisa kutoka 000001 (1) hadi 111111 (63).
L2-L64 inapaswa sasa isomeke {=MULTIPLE OPERATION (K1)}, haya ni matokeo ya suluhu zote mbadala. Kisha thamani ya chini ni=Min (L) na mbadala sambamba ni INDEX (K).
CPLEX Integer Programming
Wakati mwingine uhusiano wa mstari hautoshi kufikia kiini cha tatizo la biashara. Hii ni kweli hasa wakati maamuzi yanahusisha chaguo tofauti, kama vile kufungua au kutofungua ghala katika eneo fulani. Katika hali hizi, upangaji programu kamili lazima utumike.
Ikiwa tatizo linahusisha chaguo moja kwa moja na lisilobadilika, ni mpango kamili uliochanganywa. Inaweza kuwa na matatizo ya mstari, mbonyeo wa quadratic na vikwazo sawa vya mpangilio wa pili.
Programu kamili ni ngumu zaidi kuliko programu za mstari, lakini zina programu muhimu za biashara. ProgramuProgramu ya CPLEX hutumia mbinu changamano za hisabati kutatua matatizo kamili. Mbinu zake zinahusisha kutafuta kwa utaratibu michanganyiko iwezekanayo ya vigeu bainifu kwa kutumia ulegezaji wa programu laini au wa pande nne ili kukokotoa mipaka juu ya thamani ya suluhisho mojawapo.
Pia hutumia LP na mbinu zingine za utatuzi wa matatizo ili kukokotoa vikwazo.
Standard Microsoft Excel Solver
Teknolojia hii hutumia utekelezaji msingi wa mbinu kuu ya Simplex kutatua matatizo ya LP. Ni mdogo kwa vigezo 200. "Premium Solver" hutumia mbinu ya msingi iliyoboreshwa iliyo na mipaka ya pande mbili kwa vigeu. Jukwaa la Premium Solver hutumia toleo lililopanuliwa la LP/Quadratic Simplex Solver kutatua tatizo la uboreshaji na hadi vigeu 2000 vya maamuzi.
€ refactoring matrices, nyingi na sehemu ya bei na mzunguko, na kwa ajili ya kushinda kuzorota. Injini hii inapatikana katika matoleo matatu (yenye uwezo wa kushughulikia hadi 8,000, 32,000, au vigezo na vikomo visivyo na kikomo).
MOSEK Solver inajumuisha simplex ya msingi na mbili, mbinu ambayo pia hutumia uchache na hutumia mikakati ya kina kusasisha matrix na "kusasisha upya". Inasuluhisha shida za saizi isiyo na kikomo, ilikuwaimejaribiwa kwa matatizo ya programu ya mstari na mamilioni ya vigezo vya maamuzi.
Mfano wa hatua kwa hatua katika EXCEL
Ili kufafanua muundo wa tatizo la uboreshaji katika Excel, fanya hatua zifuatazo:
- Panga data ya tatizo katika lahajedwali kwa njia ya kimantiki.
- Chagua kisanduku ili kuhifadhi kila kigezo.
- Unda katika kisanduku fomula ya kukokotoa muundo lengwa wa hisabati wa tatizo la uboreshaji.
- Unda fomula ili kukokotoa upande wa kushoto wa kila kikwazo.
- Tumia vidadisi katika Excel kumwambia Kisuluhishi kuhusu vigeu vya maamuzi, shabaha, vikwazo, na mipaka inayotakikana kwenye vigezo hivyo.
- Endesha "Solver" ili kupata suluhisho mojawapo.
- Unda laha ya Excel.
- Panga data ya tatizo katika Excel ambapo fomula ya utendakazi lengwa na kizuizi imekokotolewa.
Katika jedwali lililo hapo juu, visanduku B4, C4, D4, na E4 vimehifadhiwa ili kuwakilisha vigezo vya maamuzi X 1, X 2, X 3, na X 4. Mifano ya maamuzi:
- Muundo wa mchanganyiko wa bidhaa ($450, $1150, $800, na faida ya $400 kwa kila bidhaa) uliingizwa katika visanduku B5, C5, D5 na E5, mtawalia. Hii inaruhusu lengo kukokotwa katika F5=B5B4 + C5C4 + D5D4 + E5E4 au F5:=SUMPRODUCT (B5: E5, B4: E4).
- Katika B8 weka kiasi cha rasilimali zinazohitajika ili kutengeneza kila aina ya bidhaa.
- Mfumo wa F8:=SUMPRODUCT(B8:E8, $B$4:$E$4).
- Nakili hiifomula katika F9. Ishara za dola katika $B$4:$E$4 zinaonyesha kuwa safu hii ya seli haibadilika.
- Katika G8 weka kiasi kinachopatikana cha rasilimali za kila aina, zinazolingana na thamani za vizuizi vilivyo upande wa kulia. Hii hukuruhusu kuzieleza kama hii: F11<=G8: G11.
- Hii ni sawa na viwango vinne F8<=G8, F9 <=G9, F10 <=G10 na F11=0
Nyumba za matumizi ya vitendo ya mbinu
Uboreshaji wa laini una matumizi mengi ya vitendo kama mfano wa tatizo la uboreshaji:
Kampuni inaweza kutengeneza bidhaa kadhaa kwa ukingo unaojulikana wa mchango. Uzalishaji wa kitengo cha kila kitu unahitaji kiasi kinachojulikana cha rasilimali chache. Jukumu ni kuunda mpango wa uzalishaji ili kubainisha ni kiasi gani cha kila bidhaa kinapaswa kuzalishwa ili faida ya kampuni iongezwe bila kukiuka vikwazo vya rasilimali.
Matatizo ya kuchanganya ndiyo suluhu la matatizo ya uboreshaji yanayohusiana na kuchanganya viungo kwenye bidhaa ya mwisho. Mfano wa hii ni shida ya lishe iliyochunguzwa na George Danzig mnamo 1947. Malighafi kadhaa hupewa, kama vile shayiri, nyama ya nguruwe na mafuta ya alizeti, pamoja na maudhui yake ya lishe, kama vile protini, mafuta, vitamini A, na bei yake kwa kilo. Changamoto ni kuchanganya bidhaa moja au zaidi kutoka kwa malighafi kwa gharama ya chini kabisa huku ukizingatia viwango vya chini na vya juu zaidi vya thamani yake ya lishe.
Utumizi wa kawaida wa tatizo la uboreshaji wa mstari ni kubainisha uelekezaji wa mahitajitrafiki katika mawasiliano ya simu au mitandao ya usafiri. Wakati huo huo, mtiririko lazima upitishwe kwenye mtandao kwa njia ambayo mahitaji yote ya trafiki yanatimizwa bila kukiuka masharti ya kipimo data.
Katika nadharia ya hisabati, uboreshaji wa mstari unaweza kutumika kukusanya mikakati bora katika michezo isiyo na sifuri kwa watu wawili. Katika kesi hii, mgawanyo wa uwezekano kwa kila mshiriki hukokotolewa, ambayo ni mgawo wa mchanganyiko wa nasibu wa mikakati yake.
Hakuna mchakato wa biashara wenye mafanikio duniani unaowezekana bila uboreshaji. Kuna algorithms nyingi za uboreshaji zinazopatikana. Njia zingine zinafaa tu kwa aina fulani za shida. Ni muhimu kuweza kutambua sifa zao na kuchagua mbinu inayofaa ya utatuzi.
