Panimula
Ang modernong yugto ng pag-unlad ng tao ay iba dahil ang siglo ng enerhiya ay pinapalitan ng edad ng informatics. Mayroong masinsinang pagpapakilala ng mga bagong teknolohiya sa lahat ng larangan ng aktibidad ng tao. Mayroong isang tunay na problema ng paglipat sa lipunan ng impormasyon, kung saan ang pag-unlad ng edukasyon ay dapat maging isang priyoridad. Nagbabago rin ang istruktura ng kaalaman sa lipunan. Ang pangunahing kaalaman na nag-aambag sa malikhaing pag-unlad ng indibidwal ay nagiging lalong mahalaga para sa praktikal na buhay. Ang constructiveness ng nakuha na kaalaman, ang kakayahang buuin ito alinsunod sa layunin ay mahalaga din. Sa batayan ng kaalaman, nabuo ang mga bagong mapagkukunan ng impormasyon ng lipunan. Ang pagbuo at pagkuha ng bagong kaalaman ay dapat na nakabatay sa isang mahigpit na pamamaraan ng isang sistematikong diskarte, kung saan ang isang hiwalay na lugar ay inookupahan ng isang modelong diskarte. Ang mga posibilidad ng diskarte sa pagmomodelo ay lubhang magkakaibang pareho sa mga tuntunin ng mga pormal na modelong ginamit at sa mga paraan ng pagpapatupad ng mga pamamaraan ng pagmomodelo. Ginagawang posible ng pisikal na pagmomodelo na makakuha ng maaasahang mga resulta para sa medyo simpleng mga sistema.
Sa kasalukuyan, imposibleng pangalanan ang isang lugar ng aktibidad ng tao kung saan, sa isang antas o iba pa, ang mga pamamaraan ng pagmomolde ay hindi gagamitin. Ito ay totoo lalo na para sa pamamahala ng iba't ibang mga sistema, kung saan ang mga pangunahing ay mga proseso ng paggawa ng desisyon batay sa impormasyong natanggap.
1. Paglalahad ng suliranin
minimum na layunin ng pag-andar
Lutasin ang problema sa paghahanap ng pinakamaliit na layunin ng function para sa sistema ng mga hadlang na tinukoy ng polygon ng desisyon alinsunod sa opsyon No. 16 ng gawain. Ang polygon ng desisyon ay ipinapakita sa Figure 1:
Figure 1 - Polygon ng mga solusyon sa problema
Ang sistema ng mga hadlang at ang layunin ng pag-andar ng problema ay ipinakita sa ibaba:
Ito ay kinakailangan upang malutas ang problema gamit ang mga sumusunod na pamamaraan:
Graphical na paraan para sa paglutas ng mga problema sa LP;
Algebraic na paraan para sa paglutas ng mga problema sa LP;
Simplex na paraan para sa paglutas ng mga problema sa LP;
Paraan para sa paghahanap ng isang magagawang solusyon sa mga problema sa LP;
Paglutas ng problema sa dalawahang LP;
Ang paraan ng "mga sanga at hangganan" para sa paglutas ng mga problema sa integer LP;
Pamamaraan ni Gomory para sa paglutas ng mga problema sa integer LP;
Paraan ng Balash para sa paglutas ng mga problema sa Boolean LP.
Ihambing ang mga resulta ng solusyon sa pamamagitan ng iba't ibang pamamaraan upang makagawa ng angkop na konklusyon sa gawain.
2. Graphical na solusyon ng linear programming problem
Ang graphical na paraan para sa paglutas ng mga problema sa linear programming ay ginagamit sa mga kaso kung saan ang bilang ng mga hindi alam ay hindi lalampas sa tatlo. Ito ay maginhawa para sa isang husay na pag-aaral ng mga katangian ng mga solusyon at ginagamit kasabay ng iba pang mga pamamaraan (algebraic, branch at bound, atbp.). Ang ideya ng pamamaraan ay batay sa graphical na solusyon ng isang sistema ng mga linear na hindi pagkakapantay-pantay.
kanin. 2 Graphical na solusyon ng problema sa LP
Mababang punto
Equation ng isang tuwid na linya na dumadaan sa dalawang puntos na A1 at A2:
AB: (0;1); (3;3)
Araw: (3;3); (4;1)
CD: (4;1); (3;0)
EA: (1;0); (0;1)
CF: (0;1); (5;2)
may mga paghihigpit:
Paglutas ng isang linear programming problem sa pamamagitan ng algebraic simplex method
Ang aplikasyon ng algebraic method para sa paglutas ng problema ay nangangailangan ng generalization ng representasyon ng LP problem. Ang orihinal na sistema ng mga hadlang na ibinigay sa anyo ng mga hindi pagkakapantay-pantay ay na-convert sa karaniwang notasyon kapag ang mga hadlang ay ibinigay sa anyo ng mga pagkakapantay-pantay. Ang pag-convert ng isang sistema ng mga hadlang sa isang karaniwang anyo ay kinabibilangan ng mga sumusunod na hakbang:
Baguhin ang mga hindi pagkakapantay-pantay sa paraang ang mga variable at libreng miyembro ay nasa kaliwa, at 0 sa kanan, i.e. na ang kaliwang bahagi ay mas malaki sa o katumbas ng zero;
Ipakilala ang mga karagdagang variable, ang bilang nito ay katumbas ng bilang ng mga hindi pagkakapantay-pantay sa sistema ng mga paghihigpit;
Ang pagpapakilala ng mga karagdagang paghihigpit sa di-negatibiti ng mga idinagdag na variable, palitan ang mga palatandaan ng hindi pagkakapantay-pantay na may mahigpit na pantay na mga palatandaan.
Kapag nilulutas ang problema sa LP sa pamamagitan ng algebraic na pamamaraan, ang isang kundisyon ay idinagdag: ang layunin ng function ay dapat na may pinakamababa. Kung ang kundisyong ito ay hindi matugunan, ito ay kinakailangan upang naaangkop na baguhin ang layunin function (multiply sa pamamagitan ng -1) at lutasin ang minimization problema. Matapos mahanap ang solusyon, palitan ang mga halaga ng mga variable sa orihinal na function at kalkulahin ang halaga nito.
Ang solusyon ng problema gamit ang algebraic na pamamaraan ay itinuturing na pinakamainam kapag ang mga halaga ng lahat ng mga pangunahing variable ay hindi negatibo, at ang mga coefficient para sa mga libreng variable sa layunin na equation ng function ay hindi rin negatibo. Kung ang mga kundisyong ito ay hindi matugunan, ito ay kinakailangan upang baguhin ang sistema ng hindi pagkakapantay-pantay, pagpapahayag ng ilang mga variable sa mga tuntunin ng iba (pagbabago ng libre at pangunahing mga variable) upang makamit ang mga paghihigpit sa itaas. Ang halaga ng lahat ng mga libreng variable ay ipinapalagay na zero.
Ang algebraic na pamamaraan para sa paglutas ng mga problema ng linear programming ay isa sa mga pinaka-epektibong pamamaraan para sa paglutas ng mga problema ng maliliit na dimensyon nang manu-mano. hindi nangangailangan ng malaking bilang ng mga kalkulasyon ng aritmetika. Ang pagpapatupad ng makina ng pamamaraang ito ay mas kumplikado kaysa, halimbawa, para sa simplex na paraan, dahil ang algorithm para sa paglutas ng algebraic na pamamaraan ay sa ilang lawak ay heuristic at ang bisa ng solusyon ay higit na nakasalalay sa personal na karanasan.
mga libreng variable
St. lane - idagdag. kit
Ang mga kondisyon na hindi negatibo ay nasiyahan, samakatuwid, ang pinakamainam na solusyon ay natagpuan.
3. Paglutas ng linear programming problem gamit ang simplex table
Solusyon: Dalhin natin ang problema sa isang karaniwang form para sa paglutas gamit ang isang simplex table.
Binabawasan namin ang lahat ng equation ng system sa anyo:
Bumubuo kami ng isang simplex na talahanayan:
Sa itaas na sulok ng bawat cell ng talahanayan ipinasok namin ang mga coefficient mula sa sistema ng mga equation;
Pinipili namin ang maximum na positibong elemento sa hilera F, maliban sa ito ang magiging pangkalahatang hanay;
Upang mahanap ang pangkalahatang elemento, bumuo kami ng isang relasyon para sa lahat ng mga positibo. 3/3; 9/1;- pinakamababang ratio sa linya x3. Samakatuwid - pangkalahatang string at =3 - pangkalahatang elemento.
Nahanap namin ang =1/=1/3. Dinadala namin ang ibabang sulok ng cell, kung saan matatagpuan ang pangkalahatang elemento;
Sa lahat ng hindi napunan na mas mababang sulok ng pangkalahatang linya, ipinapasok namin ang produkto ng halaga sa itaas na sulok ng cell sa pamamagitan ng;
Piliin ang itaas na sulok ng pangkalahatang linya;
Sa lahat ng mas mababang sulok ng pangkalahatang hanay ipinapasok namin ang produkto ng halaga sa itaas na sulok sa pamamagitan ng - at piliin ang mga resultang halaga;
Ang natitirang mga cell ng talahanayan ay napunan bilang mga produkto ng kaukulang mga napiling elemento;
Pagkatapos ay bumuo kami ng isang bagong talahanayan kung saan ang mga pagtatalaga ng mga cell ng mga elemento ng pangkalahatang haligi at hilera ay baligtad (x2 at x3);
Sa itaas na sulok ng dating pangkalahatang hilera at haligi, ang mga halaga na dati ay nasa ibabang sulok ay nakasulat;
Ang kabuuan ng mga halaga ng itaas at ibabang sulok ng mga cell na ito sa nakaraang talahanayan ay nakasulat sa itaas na sulok ng natitirang mga cell
4. Paglutas ng problema sa linear programming sa pamamagitan ng paghahanap ng isang magagawang solusyon
Hayaang magbigay ng isang sistema ng mga linear algebraic equation:
Maaari nating ipagpalagay na ang lahat, kung hindi, i-multiply natin ang katumbas na equation sa -1.
Ipinakilala namin ang mga auxiliary variable:
Ipinakilala din namin ang isang pantulong na function
I-minimize namin ang system sa ilalim ng mga hadlang (2) at kundisyon.
PANUNTUNAN PARA SA PAGHAHANAP NG FEASIBLE NA SOLUSYON: Upang makahanap ng isang magagawang solusyon sa system (1), binabawasan namin ang form (3) sa ilalim ng mga hadlang (2), dahil ang mga libreng hindi alam ay ginagamit namin ang xj bilang mga pangunahing.
Kapag nilulutas ang isang problema sa pamamagitan ng simplex na pamamaraan, maaaring lumitaw ang dalawang kaso:
min f=0, kung gayon ang lahat ng i ay dapat na katumbas ng zero. At ang mga resultang halaga xj ay magiging isang magagawang solusyon sa system (1).
min f>0, ibig sabihin. ang orihinal na sistema ay walang wastong solusyon.
Source system:
Ginagamit ang kondisyon ng suliranin ng nakaraang paksa.
Magdagdag tayo ng mga karagdagang variable:
Ang isang tinatanggap na solusyon sa orihinal na problema ay natagpuan: x1 = 3, x2 = 3, F = -12. Batay sa nakuha na magagawang solusyon, nakita namin ang pinakamainam na solusyon sa orihinal na problema gamit ang simplex na paraan. Upang gawin ito, bubuo kami ng isang bagong simplex na talahanayan mula sa talahanayan na nakuha sa itaas sa pamamagitan ng pagtanggal ng hilera at ang hilera na may target na function ng auxiliary na gawain:
Sa pagsusuri sa itinayong simplex na talahanayan, nakita namin na ang pinakamainam na solusyon para sa orihinal na problema ay natagpuan na (ang mga elemento sa hilera na naaayon sa layunin ng pag-andar ay negatibo). Kaya, ang magagawang solusyon na natagpuan kapag nilulutas ang pantulong na problema ay tumutugma sa pinakamainam na solusyon ng orihinal na problema:
6. Ang dalawahang problema ng linear programming
Ang paunang sistema ng mga hadlang at ang layunin ng pag-andar ng problema ay ipinapakita sa figure sa ibaba.
may mga paghihigpit:
Solusyon: Dinadala namin ang sistema ng mga paghihigpit sa karaniwang anyo:
Ang gawaing dalawa sa isang ito ay magiging ganito:
Ang dalawahang problema ay malulutas sa pamamagitan ng simplex na pamamaraan.
Ibahin natin ang layunin ng function upang malutas ang problema sa minimization at isulat ang sistema ng mga hadlang sa karaniwang anyo para sa paglutas sa pamamagitan ng simplex na pamamaraan.
y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)
y7 = 5 - (-3y1 - y2 + y3 + y4)
Ф = 0 - (3y1 + 9y2 + 3y3 + y4) ??min
Buuin natin ang paunang simplex tableau para sa paglutas ng dual LP na problema.
Ang ikalawang hakbang ng simplex na pamamaraan
Kaya, sa ikatlong hakbang ng simplex na paraan, ang pinakamainam na solusyon ng problema sa minimization ay natagpuan sa mga sumusunod na resulta: y2 = -7 /8, y1 = -11/8, Ф = 12. Upang mahanap ang halaga ng ang layunin ng pag-andar ng dalawahang problema, pinapalitan namin ang mga nahanap na halaga ng pangunahing at libreng mga variable sa pag-andar ng pag-maximize:
Фmax = - Фmin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12
Dahil ang halaga ng layunin ng pag-andar ng direkta at dalawahang problema ay pareho, ang solusyon sa direktang problema ay matatagpuan at katumbas ng 12.
Fmin \u003d Fmax \u003d -12
7. Paglutas ng problema ng integer linear programming gamit ang "branchs and bounds" na pamamaraan
Ibahin natin ang orihinal na problema sa paraang hindi nasiyahan ang kundisyon ng integer kapag nilulutas sa pamamagitan ng mga karaniwang pamamaraan.
Ang paunang polygon ng mga solusyon sa isang problema sa integer programming.
Bumuo tayo ng bagong sistema ng mga hadlang para sa binagong solusyon polygon.
Isinulat namin ang sistema ng mga hadlang sa anyo ng mga pagkakapantay-pantay, para sa paglutas sa pamamagitan ng algebraic na pamamaraan.
Bilang resulta ng solusyon, natagpuan ang pinakamainam na plano ng gawain: x1 = 9/4, x2 = 5/2, F = -41/4. Ang solusyong ito ay hindi nakakatugon sa integrality condition na itinakda sa problema. Hinahati namin ang orihinal na polygon ng solusyon sa dalawang rehiyon, hindi kasama ang rehiyon 3 mula dito Binago ang polygon ng mga solusyon sa problema Bumuo tayo ng mga bagong sistema ng mga paghihigpit para sa mga nabuong rehiyon ng polygon ng solusyon. Ang kaliwang bahagi ay isang quadrilateral (trapezoid). Ang sistema ng pagpilit para sa kaliwang rehiyon ng polygon ng solusyon ay ipinakita sa ibaba. Sistema ng paghihigpit para sa kaliwang rehiyon Ang kanang rehiyon ay kumakatawan sa punto C. Ang sistema ng mga hadlang para sa tamang lugar ng pagpapasya ay ipinakita sa ibaba. Ang mga bagong constraint system ay dalawang subsidiary na problema na kailangang lutasin nang hiwalay sa isa't isa. Lutasin natin ang problema ng integer programming para sa kaliwang rehiyon ng solusyon polygon. Bilang resulta ng solusyon, natagpuan ang pinakamainam na plano ng gawain: x1 = 3, x2 = 3, F = -12. Natutugunan ng planong ito ang kundisyon ng mga variable na integer sa problema at maaaring kunin bilang pinakamainam na reference plan para sa orihinal na problema sa integer linear programming. Walang saysay na isagawa ang solusyon para sa tamang rehiyon ng solusyon. Ang figure sa ibaba ay nagpapakita ng pag-unlad ng paglutas ng isang integer linear programming na problema sa anyo ng isang puno. Ang kurso ng paglutas ng isang integer linear programming problem sa pamamagitan ng Gomory method. Sa maraming praktikal na aplikasyon, ang problema ng integer programming ay may malaking interes, kung saan ang isang sistema ng mga linear na hindi pagkakapantay-pantay at isang linear na anyo ay ibinibigay. Kinakailangang maghanap ng integer na solusyon ng system (1) na nagpapaliit sa layunin ng function F, at ang lahat ng mga coefficient ay mga integer. Ang isa sa mga pamamaraan para sa paglutas ng problema sa integer programming ay iminungkahi ni Gomori. Ang ideya ng pamamaraan ay ang paggamit ng mga pamamaraan ng tuluy-tuloy na linear programming, sa partikular, ang simplex na paraan. 1) Gamit ang simplex na paraan, ang solusyon sa problema (1), (2) ay tinutukoy, kung saan ang pangangailangan na ang solusyon ay integer ay inalis; kung ang solusyon ay lumabas na integer, ang nais na solusyon sa problema ng integer ay matatagpuan din; 2) Kung hindi, kung ang ilang coordinate ay hindi isang integer, ang nakuha na solusyon ng problema ay sinusuri para sa posibilidad ng pagkakaroon ng isang integer na solusyon (ang pagkakaroon ng mga integer na puntos sa isang tinatanggap na polyhedron): kung sa anumang linya na may isang fractional na libreng miyembro, ang lahat ng iba pang mga coefficient ay naging mga integer, kung gayon walang mga integer, mga puntos sa isang tinatanggap na polyhedron, at ang problema ng integer programming ay walang solusyon; Kung hindi, ang isang karagdagang linear na hadlang ay ipinakilala, na pinuputol mula sa tinatanggap na polyhedron ang isang bahagi na hindi maaasahan para sa paghahanap ng solusyon sa isang problema sa integer programming; 3) Para makabuo ng karagdagang linear constraint, piliin ang l-th row na may fractional free member at isulat ang karagdagang constraint kung saan at ay, ayon sa pagkakabanggit, ang mga fractional na bahagi ng mga coefficient at libre miyembro. Ipakilala natin ang isang auxiliary variable sa pagpilit (3): Tukuyin natin ang mga coefficient at kasama sa pagpilit (4): kung saan at ang pinakamalapit na mas mababang integer para sa at, ayon sa pagkakabanggit. Pinatunayan ni Gomory na ang isang may hangganang bilang ng mga naturang hakbang ay humahantong sa isang linear programming problem na ang solusyon ay integer at, samakatuwid, ang nais. Solusyon: Binabawasan namin ang sistema ng mga linear na hadlang at ang layunin ng function sa canonical form: Alamin natin ang pinakamainam na solusyon ng sistema ng mga linear na hadlang, pansamantalang itinatapon ang kondisyon ng integer. Ginagamit namin ang simplex na paraan para dito. Ang mga talahanayan sa ibaba ay sunud-sunod na nagpapakita ng paunang solusyon ng problema, at ang mga pagbabago ng orihinal na talahanayan ay ibinigay upang makuha ang pinakamainam na solusyon sa problema: Paglutas ng mga problema sa Boolean LP sa pamamagitan ng paraan ng Balash. Independiyenteng bumuo ng isang variant para sa problema ng integer linear programming na may Boolean variable, na isinasaalang-alang ang mga sumusunod na panuntunan: ang problema ay gumagamit ng hindi bababa sa 5 variable, hindi bababa sa 4 na mga paghihigpit, ang mga coefficient ng mga paghihigpit at ang layunin ng function ay pinili nang arbitraryo, ngunit sa ganoong isang paraan na ang sistema ng mga paghihigpit ay magkatugma. Ang gawain ay lutasin ang ZCLP gamit ang mga Boolean variable gamit ang Balash algorithm at tukuyin ang pagbawas sa computational complexity kaugnay ng paglutas ng problema sa pamamagitan ng kumpletong paghahanap. Pagpapatupad ng mga paghihigpit halaga ng F Pagpipilit sa filter: Pagpapasiya ng Pagbawas ng Pagkalkula Ang solusyon ng problema sa pamamagitan ng kumpletong paraan ng paghahanap ay 6*25=192 kalkuladong expression. Ang solusyon ng problema sa pamamagitan ng paraan ng Balash ay 3*6+(25-3)=47 mga kalkuladong expression. Ang kabuuang pagbawas sa pagiging kumplikado ng mga kalkulasyon na may kaugnayan sa paglutas ng problema sa pamamagitan ng kumpletong paraan ng paghahanap ay. Konklusyon Ang proseso ng pagdidisenyo ng mga sistema ng impormasyon na nagpapatupad ng bagong teknolohiya ng impormasyon ay patuloy na pinagbubuti. Ang lalong kumplikadong mga sistema ay nagiging pokus ng atensyon ng mga inhinyero ng system, na nagpapahirap sa paggamit ng mga pisikal na modelo at nagpapataas ng kahalagahan ng mga modelo ng matematika at simulation ng computer ng mga system. Ang pagmomodelo ng makina ay naging isang epektibong tool para sa pananaliksik at disenyo ng mga kumplikadong sistema. Ang kaugnayan ng mga modelo ng matematika ay patuloy na tumataas dahil sa kanilang kakayahang umangkop, kasapatan sa mga tunay na proseso, mababang halaga ng pagpapatupad batay sa mga modernong PC. Parami nang parami ang mga pagkakataon na ibinibigay sa gumagamit, ibig sabihin, isang espesyalista sa mga sistema ng pagmomodelo sa pamamagitan ng teknolohiya ng computer. Ang paggamit ng pagmomodelo ay lalong epektibo sa mga unang yugto ng pagdidisenyo ng mga automated system, kapag ang halaga ng mga maling desisyon ay pinakamahalaga. Ang mga modernong tool sa pag-compute ay naging posible upang makabuluhang taasan ang pagiging kumplikado ng mga modelo na ginamit sa pag-aaral ng mga system, naging posible na bumuo ng pinagsama, analytical at simulation na mga modelo na isinasaalang-alang ang buong iba't ibang mga kadahilanan na nagaganap sa mga tunay na system, ibig sabihin, ang paggamit ng mga modelo na mas sapat sa mga phenomena na pinag-aaralan. Panitikan: 1. Lyashchenko I.N. Linear at non-linear programming / I.N. Lyashchenko, E.A. Karagodova, N.V. Chernikova, N.Z. Shor. - K .: "Mataas na Paaralan", 1975, 372 p. 2. Mga patnubay para sa pagpapatupad ng proyekto ng kurso sa disiplina na "Applied Mathematics" para sa mga mag-aaral ng specialty na "Computer Systems and Networks" full-time at part-time na mga anyo ng edukasyon / Compiled by: I.A. Balakireva, A.V. Skatkov - Sevastopol: SevNTU Publishing House , 2003. - 15 p. 3. Mga patnubay para sa pag-aaral ng disiplina na "Applied Mathematics", seksyong "Mga paraan ng pandaigdigang paghahanap at one-dimensional minimization" / Comp. A.V. Skatkov, I.A. Balakireva, L.A. Litvinova - Sevastopol: SevGTU Publishing House, 2000. - 31s. 4. Mga alituntunin para sa pag-aaral ng disiplina na "Applied Mathematics" para sa mga mag-aaral ng specialty na "Computer Systems and Networks" Seksyon "Paglutas ng Integer Linear Programming Problems" ng full-time at mga form ng pagsusulatan ng edukasyon / Compiled by: I.A. Balakireva, A.V. Skatkov - Sevastopol : SevNTU Publishing House, 2000. - 13 p. 5. Akulich I.L. Mathematical programming sa mga halimbawa at gawain: 6. Proc. allowance para sa ekonomiya ng mag-aaral. espesyalista. unibersidad.-M.: Mas mataas. paaralan, 1986.- 319s., may sakit. 7. Andronov S.A. Pinakamainam na paraan ng disenyo: Text ng lecture / SPbGUAP. SPb., 2001. 169 p.: may sakit. Algorithm para sa paglutas ng mga problema sa linear programming sa pamamagitan ng simplex na pamamaraan. Pagbuo ng isang mathematical model ng isang linear programming problem. Paglutas ng problema sa linear programming sa Excel. Paghahanap ng tubo at pinakamainam na plano sa produksyon. term paper, idinagdag noong 03/21/2012 Graphical na paglutas ng problema. Pag-drawing ng isang mathematical model. Pagtukoy sa pinakamataas na halaga ng layunin ng function. Solusyon sa pamamagitan ng isang simplex na pamamaraan na may artipisyal na batayan ng isang canonical linear programming problem. Sinusuri ang pinakamainam ng solusyon. pagsubok, idinagdag noong 04/05/2016 Teoretikal na batayan ng linear programming. Mga problema ng linear programming, mga pamamaraan ng solusyon. Pagsusuri ng pinakamainam na solusyon. Solusyon ng single-index linear programming problem. Pahayag ng problema at data entry. Pagbuo ng modelo at mga hakbang sa solusyon. term paper, idinagdag noong 12/09/2008 Konstruksyon ng isang mathematical model. Pagpili, pagbibigay-katwiran at paglalarawan ng pamamaraan para sa paglutas ng direktang problema ng linear programming sa pamamagitan ng simplex method, gamit ang isang simplex table. Pagbubuo at solusyon ng dalawahang problema. Pagsusuri ng modelo para sa pagiging sensitibo. term paper, idinagdag noong 10/31/2014 Pagbuo ng isang mathematical na modelo upang mapakinabangan ang kita ng negosyo, isang graphical na solusyon sa problema. Paglutas ng problema gamit ang SOLVER add-on. Pagsusuri ng mga pagbabago sa mga reserbang mapagkukunan. Pagpapasiya ng mga limitasyon ng pagbabago sa mga coefficient ng layunin ng function. term paper, idinagdag noong 12/17/2014 Pagprograma ng matematika. Linear programming. Mga problema sa linear programming. Graphical na pamamaraan para sa paglutas ng isang linear programming problem. Pang-ekonomiyang pagbabalangkas ng problema ng linear programming. Konstruksyon ng isang mathematical model. term paper, idinagdag noong 10/13/2008 Paglutas ng isang linear na problema sa programming sa pamamagitan ng isang graphical na pamamaraan, ang pagpapatunay nito sa MS Excel. Pagsusuri ng panloob na istraktura ng solusyon sa problema sa programa. Pag-optimize ng plano sa produksyon. Solusyon sa problema sa pamamagitan ng simplex method. Multichannel queuing system. pagsubok, idinagdag noong 05/02/2012 Paglutas ng problema ng linear programming sa pamamagitan ng simplex na pamamaraan: pagtatakda ng problema, pagbuo ng modelong pang-ekonomiya at matematika. Solusyon ng problema sa transportasyon sa pamamagitan ng paraan ng mga potensyal: pagtatayo ng paunang plano ng sanggunian, pagpapasiya ng pinakamainam na halaga nito. pagsubok, idinagdag noong 04/11/2012 Pahayag ng problema ng nonlinear programming. Pagpapasiya ng mga nakatigil na puntos at ang kanilang uri. Konstruksyon ng mga linya ng antas, isang three-dimensional na graph ng layunin ng function at mga paghihigpit. Graphical at analytical na solusyon ng problema. Manual ng gumagamit at scheme ng algorithm. term paper, idinagdag noong 12/17/2012 Pagsusuri ng solusyon ng isang linear programming problem. Simplex method gamit ang simplex tables. Pagmomodelo at solusyon ng mga problema sa LP sa isang computer. Pang-ekonomiyang interpretasyon ng pinakamainam na solusyon ng problema. Ang pagbabalangkas ng matematika ng problema sa transportasyon. Hinahati namin ang ikatlong hilera ng pangunahing elemento na katumbas ng 5, nakuha namin ang ikatlong hilera ng bagong talahanayan. Ang mga base na column ay tumutugma sa mga solong column. Pagkalkula ng natitirang mga halaga ng talahanayan: "BP - Pangunahing Plano": ; "x1": "x5": Ang mga halaga ng hilera ng index ay hindi negatibo, samakatuwid makuha namin ang pinakamainam na solusyon: , ; Sagot: ang pinakamataas na kita mula sa pagbebenta ng mga produktong gawa, katumbas ng 160/3 na mga yunit, ay sinisiguro sa pamamagitan ng pagpapalabas ng mga produkto lamang ng pangalawang uri sa halagang 80/9 na mga yunit. Ang problema ng nonlinear programming ay ibinigay. Hanapin ang maximum at minimum ng layunin ng function gamit ang isang graph-analytical na pamamaraan. Buuin ang Lagrange function at ipakita na ang sapat na minimum (maximum) na mga kondisyon ay nasiyahan sa mga extremum point. kasi ang huling digit ng cipher ay 8, pagkatapos ay A=2; B=5. kasi ang penultimate digit ng cipher ay 1, pagkatapos ay dapat mong piliin ang numero ng gawain 1. Desisyon: 1) Iguhit natin ang lugar na tinutukoy ng sistema ng hindi pagkakapantay-pantay. Ang lugar na ito ay isang tatsulok na ABC na may mga coordinate ng vertices: A(0; 2); B(4; 6) at C(16/3; 14/3). Ang mga antas ng layunin ng function ay mga bilog na nakasentro sa punto (2; 5). Ang mga parisukat ng radii ay ang mga halaga ng layunin ng function. Pagkatapos ay ipinapakita ng figure na ang pinakamababang halaga ng layunin ng function ay naabot sa punto H, ang pinakamataas na halaga ay alinman sa punto A o sa punto C. Ang halaga ng layunin ng function sa punto A: ; Ang halaga ng layunin ng function sa punto C: ; Nangangahulugan ito na ang pinakamataas na halaga ng function ay naabot sa puntong A(0; 2) at katumbas ng 13. Hanapin natin ang mga coordinate ng punto H. Upang gawin ito, isaalang-alang ang system: Ang isang linya ay padaplis sa isang bilog kung ang equation ay may natatanging solusyon. Ang isang quadratic equation ay may natatanging solusyon kung ang discriminant ay 0. 2) Bumuo ng Lagrange function upang mahanap ang pinakamababang solusyon: Sa x 1
=2.5;
x 2
=4.5
makuha namin: Ang sistema ay may solusyon para sa , ibig sabihin. nasiyahan ang sapat na matinding kondisyon. Binubuo namin ang Lagrange function para sa paghahanap ng maximum na solusyon: Sapat na mga kondisyon para sa isang extremum: Sa x 1
=0;
x 2
=2
makuha namin: Ang sistema ay mayroon ding solusyon, i.e. nasiyahan ang sapat na matinding kondisyon. Sagot: ang minimum ng layunin ng function ay naabot sa Dalawang negosyo ang inilalaan ng pondo sa halaga d mga yunit. Kapag inilaan sa unang enterprise para sa isang taon x mga yunit ng pondo na nagbibigay ng kita k 1
x mga yunit, at kapag inilalaan sa pangalawang negosyo y mga yunit ng pondo, nagbibigay ito ng kita k 1
y mga yunit. Ang balanse ng mga pondo sa katapusan ng taon para sa unang negosyo ay katumbas ng nx, at para sa pangalawa ang aking. Paano ipamahagi ang lahat ng pondo sa loob ng 4 na taon upang ang kabuuang kita ay ang pinakamalaking? Lutasin ang problema sa pamamagitan ng dynamic na programming. i=8, k=1. A=2200; k 1 =6; k2=1; n=0.2; m=0.5. Desisyon: Ang buong panahon ng 4 na taon ay nahahati sa 4 na yugto, ang bawat isa ay katumbas ng isang taon. Bilangin natin ang mga yugto simula sa unang taon. Hayaang X k at Y k ang mga pondong inilaan ayon sa pagkakabanggit sa mga negosyo A at B sa k-th stage. Pagkatapos ang kabuuan X k + Y k =a k ay ang kabuuang halaga ng mga pondong ginamit sa k - na yugto at natitira mula sa nakaraang yugto k - 1. sa unang yugto lahat ng inilalaang pondo ay ginagamit at isang 1 =2200 na yunit. ang kita na matatanggap sa k - na yugto, kapag ang X k at Y k units ay inilaan, ay magiging 6X k + 1Y k . hayaan ang pinakamataas na kita na natanggap sa mga huling yugto simula sa k - ang yugtong iyon ay f k (a k) na mga yunit. Isulat natin ang Bellman functional equation na nagpapahayag ng prinsipyo ng optimality: anuman ang paunang estado at ang paunang solusyon, ang kasunod na solusyon ay dapat na pinakamainam na may paggalang sa estado na nakuha bilang resulta ng paunang estado: Para sa bawat yugto, kailangan mong piliin ang halaga X k , at ang halaga Y k=ak- Xk. Sa pag-iisip na ito, makakahanap tayo ng kita sa k-th stage: Ang functional na Bellman equation ay magiging ganito: Isaalang-alang ang lahat ng mga yugto, simula sa huli. (dahil ang maximum ng linear function ay naabot sa dulo ng segment sa x 4 = a 4); layunin function- real o integer function ng ilang variable, napapailalim sa optimization (minimization o maximization) upang malutas ang ilang problema sa optimization. Ang termino ay ginagamit sa mathematical programming, operations research, linear programming, statistical decision theory at iba pang larangan ng matematika, pangunahin sa isang inilapat na kalikasan, bagama't ang layunin ng optimization ay maaari ding maging solusyon sa isang problema sa matematika mismo. Bilang karagdagan sa layunin ng pag-andar, sa problema sa pag-optimize, ang mga variable ay maaaring sumailalim sa mga paghihigpit sa anyo ng isang sistema ng pagkakapantay-pantay o hindi pagkakapantay-pantay. Sa pangkalahatang kaso, ang mga argumento ng layunin ng function ay maaaring tukuyin sa mga arbitrary na hanay. Ang problema ng paglutas ng anumang sistema ng mga equation ( F 1 (x 1 , x 2 , … , x M) = 0 F 2 (x 1 , x 2 , … , x M) = 0 … F N (x 1 , x 2 , … , x M) = 0 ( \displaystyle \left\((\begin(matrix)F_(1)(x_(1),x_(2),\ldots ,x_(M))=0\\F_(2)(x_(1),x_ (2),\ldots ,x_(M))=0\\\ldots \\F_(N)(x_(1),x_(2),\ldots ,x_(M))=0\end(matrix) )\tama.) ay maaaring formulated bilang isang problema ng pagliit ng layunin function S = ∑ j = 1 N F j 2 (x 1 , x 2 , … , x M) (1) (\displaystyle S=\sum _(j=1)^(N)F_(j)^(2)( x_(1),x_(2),\ldots ,x_(M))\qquad(1)) Kung ang mga pag-andar ay makinis, kung gayon ang problema sa pag-minimize ay maaaring malutas sa pamamagitan ng mga pamamaraan ng gradient. Para sa anumang makinis na layunin ng function, maaaring itumbas ng isa sa 0 (\displaystyle 0) ang mga partial derivatives na may kinalaman sa lahat ng variable. Ang pinakamainam na function na layunin ay magiging isa sa mga solusyon sa naturang sistema ng mga equation. Sa kaso ng function (1) (\displaystyle (1)) ito ay magiging isang sistema ng least squares (LSM) equation. Ang anumang solusyon ng orihinal na sistema ay isang solusyon ng pinakamababang sistema ng mga parisukat. Kung hindi pare-pareho ang orihinal na sistema, ginagawang posible ng LSM system, na laging may solusyon, na makakuha ng tinatayang solusyon ng orihinal na sistema. Ang bilang ng mga equation ng LSM system ay tumutugma sa bilang ng mga hindi alam, na kung minsan ay nagpapadali sa solusyon ng magkasanib na mga paunang sistema. Ang isa pang kilalang halimbawa ng isang layunin na function ay isang linear function na nangyayari sa mga problema sa linear programming. Sa kaibahan sa quadratic objective function, ang pag-optimize ng isang linear function ay posible lamang kung may mga paghihigpit sa anyo ng isang sistema ng linear equalities o inequalities. Ang isang tipikal na halimbawa ng isang combinatorial objective function ay ang layunin ng function ng naglalakbay na problema sa salesman. Ang function na ito ay katumbas ng haba ng Hamiltonian cycle sa graph. Ito ay ibinibigay sa permutation set n − 1 (\displaystyle n-1) ng graph vertices at tinutukoy ng edge length matrix ng graph. Ang eksaktong solusyon sa naturang mga problema ay madalas na bumababa sa pag-iisa ng mga opsyon. Ang linear programming ay isang sangay ng mathematical programming na nag-aaral ng mga pamamaraan para sa paglutas ng mga matinding problema na nailalarawan sa pamamagitan ng isang linear na relasyon sa pagitan ng mga variable at isang linear na pamantayan. Ang ganitong mga gawain ay nakakahanap ng malawak na aplikasyon sa iba't ibang larangan ng aktibidad ng tao. Ang isang sistematikong pag-aaral ng mga problema ng ganitong uri ay nagsimula noong 1939–1940. sa mga gawa ni L.V. Kantorovich. Ang mga problema sa matematika ng linear programming ay kinabibilangan ng pag-aaral ng mga tiyak na sitwasyon sa produksyon at pang-ekonomiya, na sa isang anyo o iba pa ay binibigyang kahulugan bilang mga problema ng pinakamainam na paggamit ng limitadong mga mapagkukunan. Ang hanay ng mga problemang nalutas gamit ang mga linear programming method ay medyo malawak. Ito ay, halimbawa: ang problema ng pinakamainam na paggamit ng mga mapagkukunan sa pagpaplano ng produksyon; ang problema ng mga mixtures (pagpaplano ng komposisyon ng mga produkto); ang problema sa paghahanap ng pinakamainam na kumbinasyon ng iba't ibang uri ng mga produkto para sa imbakan sa mga bodega (pamamahala ng imbentaryo o); mga gawain sa transportasyon (pagsusuri ng lokasyon ng negosyo, paggalaw ng mga kalakal). Ang linear programming ay ang pinaka-binuo at malawakang ginagamit na seksyon ng mathematical programming (bilang karagdagan, kabilang dito ang: integer, dynamic, non-linear, parametric programming). Ito ay ipinaliwanag tulad ng sumusunod: Ang mga modelo ng matematika ng isang malaking bilang ng mga problema sa ekonomiya ay linear na may paggalang sa mga kinakailangang variable; ang ganitong uri ng mga problema ay kasalukuyang pinaka-pinag-aaralan. Para sa kanya, ang mga espesyal na pamamaraan ay binuo sa tulong kung saan nalutas ang mga problemang ito, at ang kaukulang mga programa sa computer; maraming mga problema ng linear programming, na nalutas, ay natagpuan ang malawak na aplikasyon; ilang mga problema na hindi linear sa orihinal na pormulasyon, pagkatapos ng ilang karagdagang mga paghihigpit at pagpapalagay, ay maaaring maging linear o maaaring bawasan sa ganoong anyo na maaari silang malutas sa pamamagitan ng mga linear programming method. Ang modelong pang-ekonomiya at matematika ng anumang problema sa linear programming ay kinabibilangan ng: isang layunin na function, ang pinakamainam na halaga kung saan (maximum o minimum) ay dapat matagpuan; mga paghihigpit sa anyo ng isang sistema ng mga linear na equation o hindi pagkakapantay-pantay; kinakailangan ng di-negatibiti ng mga variable. Sa pangkalahatan, ang modelo ay nakasulat tulad ng sumusunod: layunin function (1.1) sa ilalim ng mga paghihigpit Ang problema ay upang mahanap ang pinakamainam na halaga ng function (1.1) na napapailalim sa mga hadlang (1.2) at (1.3). Ang sistema ng mga hadlang (1.2) ay tinatawag na functional constraints ng problema, at ang constraints (1.3) ay tinatawag na direct constraints. Ang isang vector na nakakatugon sa mga hadlang (1.2) at (1.3) ay tinatawag na isang magagawang solusyon (plano) ng isang linear na problema sa programming. Ang plano kung saan naabot ng function (1.1) ang maximum (minimum) na halaga nito ay tinatawag na optimal. Ang simplex na paraan ay binuo at unang inilapat upang malutas ang mga problema noong 1947 ng American mathematician na si J. Dantzig. Ang mga problema sa two-dimensional na linear programming ay graphical na nalutas. Para sa kaso N=3, maaari nating isaalang-alang ang isang three-dimensional na espasyo at ang layunin ng function ay maaabot ang pinakamainam na halaga nito sa isa sa mga vertices ng polyhedron. Ang isang tinatanggap na solusyon (isang tinatanggap na plano) ng isang problema sa LP na ibinigay sa karaniwang anyo ay isang nakaayos na hanay ng mga numero (x1, x2, ..., xn) na nakakatugon sa mga hadlang; ay isang punto sa n-dimensional na espasyo. Ang hanay ng mga tinatanggap na solusyon ay bumubuo sa lugar ng mga tinatanggap na solusyon (SDR) ng problema sa LP. Ang ODR ay isang convex polyhedron (polygon). Sa pangkalahatang mga termino, kapag ang N-unknowns ay kasangkot sa problema, maaari nating sabihin na ang lugar ng mga posibleng solusyon na tinukoy ng sistema ng paglilimita ng mga kondisyon ay kinakatawan ng isang convex polyhedron sa n-dimensional na espasyo at ang pinakamainam na halaga ng layunin. ang function ay nakakamit sa isa o higit pang mga vertex. Ang isang solusyon ay tinatawag na basic kung ang lahat ng mga libreng variable ay katumbas ng zero. Ang isang reference na solusyon ay isang pangunahing di-negatibong solusyon. Ang solusyon sa suporta ay maaaring hindi mabulok at mabulok. Ang isang solusyon sa suporta ay tinatawag na non-degenerate kung ang bilang ng mga non-zero na coordinate nito ay katumbas ng ranggo ng system, kung hindi man ito ay degenerate. Ang isang magagawa na solusyon, kung saan ang layunin ng pag-andar ay umabot sa matinding halaga nito, ay tinatawag na pinakamainam at tinutukoy Napakahirap lutasin ang mga problemang ito nang grapiko kapag ang bilang ng mga variable ay higit sa 3. Mayroong isang unibersal na paraan upang malutas ang mga problema sa linear programming, na tinatawag na simplex method. Ang simplex na paraan ay isang unibersal na pamamaraan para sa paglutas ng mga problema sa LP, na isang umuulit na proseso na nagsisimula sa isang solusyon at, sa paghahanap ng pinakamahusay na opsyon, gumagalaw sa mga sulok na punto ng lugar ng mga magagawang solusyon hanggang sa maabot nito ang pinakamainam na halaga. . Maaari itong magamit upang malutas ang anumang problema sa linear programming. Ang simplex na paraan ay batay sa ideya ng sunud-sunod na pagpapabuti ng resultang solusyon. Ang geometric na kahulugan ng simplex na pamamaraan ay ang sunud-sunod na paglipat mula sa isang vertex ng constraint polyhedron patungo sa kalapit na isa, kung saan ang layunin ng function ay tumatagal ng pinakamahusay (o hindi bababa sa hindi ang pinakamasama) na halaga hanggang sa ang pinakamainam na solusyon ay natagpuan - ang vertex kung saan ang pinakamainam na halaga ay naabot ang layunin ng pag-andar (kung ang problema ay may hangganan na pinakamabuting kalagayan). Kaya, ang pagkakaroon ng isang sistema ng mga hadlang na nabawasan sa canonical form (lahat ng functional na mga hadlang ay nasa anyo ng mga pagkakapantay-pantay), ang isa ay nakakahanap ng anumang pangunahing solusyon ng sistemang ito, na nag-iingat lamang upang mahanap ito nang simple hangga't maaari. Kung ang unang nahanap na pangunahing solusyon ay naging magagawa, pagkatapos ito ay nasuri para sa pinakamainam. Kung ito ay hindi pinakamainam, pagkatapos ay ang isang paglipat ay ginawa sa isa pa, kinakailangang tanggapin, pangunahing solusyon. Ginagarantiyahan ng simplex na paraan na, gamit ang bagong solusyon na ito, ang layunin na pag-andar, kung hindi nito maabot ang pinakamabuting kalagayan, pagkatapos ay nilalapitan ito (o hindi bababa sa hindi lumalayo dito). Sa isang bagong tinatanggap na pangunahing solusyon, ang parehong ay ginagawa hanggang sa isang solusyon ay natagpuan na pinakamainam. Ang proseso ng paglalapat ng simplex na pamamaraan ay nagsasangkot ng pagpapatupad ng tatlong pangunahing elemento nito: isang paraan para sa pagtukoy ng ilang paunang magagawa na pangunahing solusyon sa problema; ang panuntunan ng paglipat sa pinakamahusay (mas tiyak, hindi ang pinakamasama) solusyon; criterion para masuri ang pinakamainam ng nahanap na solusyon. Ang simplex na paraan ay may kasamang ilang hakbang at maaaring bumalangkas bilang isang malinaw na algorithm (isang malinaw na pagtuturo upang magsagawa ng mga sunud-sunod na operasyon). Ito ay nagpapahintulot sa iyo na matagumpay na mag-program at ipatupad ito sa isang computer. Ang mga problema sa isang maliit na bilang ng mga variable at mga hadlang ay maaaring malutas sa pamamagitan ng simplex na pamamaraan nang manu-mano. Pag-optimize. Bahagi 1 Binibigyang-daan ka ng mga paraan ng pag-optimize na piliin ang pinakamahusay na opsyon sa disenyo mula sa lahat ng posibleng opsyon. Sa mga nagdaang taon, maraming pansin ang binayaran sa mga pamamaraang ito, at bilang isang resulta, ang isang bilang ng mga napakahusay na algorithm ay binuo na ginagawang posible upang mahanap ang pinakamainam na pagpipilian sa disenyo gamit ang isang digital na computer. Binabalangkas ng kabanatang ito ang mga batayan ng teorya ng pag-optimize, isinasaalang-alang ang mga prinsipyong pinagbabatayan ng pagbuo ng mga algorithm para sa pinakamainam na solusyon, inilalarawan ang pinakakilalang mga algorithm, at sinusuri ang kanilang mga pakinabang at disadvantages. Ang terminong "optimization" sa literatura ay tumutukoy sa isang proseso o pagkakasunud-sunod ng mga operasyon na nagbibigay-daan sa iyo upang makakuha ng isang pinong solusyon. Bagama't ang pinakalayunin ng pag-optimize ay upang mahanap ang pinakamahusay, o "pinakamainam" na solusyon, ang isa ay karaniwang dapat maging kontento sa pagpapabuti ng mga kilalang solusyon sa halip na gawing perpekto ang mga ito. Samakatuwid, ang pag-optimize ay mas malamang na mauunawaan bilang ang pagtugis ng pagiging perpekto, na, marahil, ay hindi makakamit. Isinasaalang-alang ang ilang di-makatwirang sistema na inilarawan ng m equation na may n hindi alam, maaari nating makilala ang tatlong pangunahing uri ng mga problema. Kung m=n , ang problema ay tinatawag na algebraic. Ang ganitong problema ay karaniwang may isang solusyon. Kung m>n, ang problema ay muling tukuyin at, bilang panuntunan, ay walang solusyon. Sa wakas, para sa m Bago magpatuloy sa talakayan ng mga isyu sa pag-optimize, ipinakilala namin ang ilang mga kahulugan. Mga parameter ng disenyo
Ang terminong ito ay nagsasaad ng mga independiyenteng variable na parameter na ganap at malinaw na tumutukoy sa problema sa disenyo na nireresolba. Ang mga parameter ng disenyo ay hindi kilalang dami, ang mga halaga nito ay kinakalkula sa panahon ng proseso ng pag-optimize. Anumang basic o derivative na dami na nagsisilbing quantitatively na naglalarawan sa system ay maaaring magsilbi bilang mga parameter ng disenyo. Kaya, maaari itong hindi kilalang mga halaga ng haba, masa, oras, temperatura. Ang bilang ng mga parameter ng disenyo ay nagpapakilala sa antas ng pagiging kumplikado ng problemang ito sa disenyo. Karaniwan ang bilang ng mga parameter ng disenyo ay tinutukoy ng n, at ang mga parameter ng disenyo mismo ng x na may kaukulang mga indeks. Kaya, ang n mga parameter ng disenyo ng problemang ito ay ilalarawan ng layunin function
Ito ang expression na ang halaga ay hinahangad ng engineer na i-maximize o i-minimize. Ang layunin ng function ay nagbibigay-daan sa iyo upang quantitatively ihambing ang dalawang alternatibong solusyon. Mula sa isang mathematical point of view, ang layunin ng function ay naglalarawan ng ilang (n + 1) - dimensional na ibabaw. Ang halaga nito ay tinutukoy ng mga parameter ng disenyo M=M(x 1 , x 2 ,...,x n). Ang mga halimbawa ng layunin na pag-andar, na madalas na nakatagpo sa pagsasanay sa engineering, ay ang gastos, timbang, lakas, sukat, kahusayan. Kung mayroon lamang isang parameter ng disenyo, kung gayon ang layunin ng function ay maaaring katawanin ng isang curve sa isang eroplano (Larawan 6.1). Kung mayroong dalawang mga parameter ng disenyo, ang target na function ay kakatawanin ng isang ibabaw sa espasyo ng tatlong dimensyon (Larawan 6.2). Sa tatlo o higit pang mga parameter ng disenyo, ang mga ibabaw na tinukoy ng layunin ng function ay tinatawag na hypersurfaces at hindi maaaring ilarawan. zheniya conventional na paraan. Ang mga topological na katangian ng ibabaw ng layunin ng function ay may mahalagang papel sa proseso ng pag-optimize, dahil ang pagpili ng pinaka mahusay na algorithm ay nakasalalay sa kanila. Ang layunin na pag-andar sa ilang mga kaso ay maaaring magkaroon ng mga hindi inaasahang anyo. Halimbawa, hindi laging posible na ipahayag ito sa Fig. 1. One-dimensional na layunin na function. Fig.6.2.Two-dimensional layunin function. saradong mathematical form, sa ibang mga kaso maaari itong maging isang piecewise smooth function. Ang isang layunin na function ay maaaring minsan ay nangangailangan ng isang teknikal na talahanayan ng data (halimbawa, isang talahanayan ng estado ng singaw) o maaaring kinakailangan upang magsagawa ng isang eksperimento. Sa ilang mga kaso, ang mga parameter ng disenyo ay kumukuha lamang ng mga halaga ng integer. Ang isang halimbawa ay ang bilang ng mga ngipin sa isang gear o ang bilang ng mga bolts sa isang flange. Minsan ang mga parameter ng disenyo ay may dalawang halaga lamang - oo o hindi. Ang mga husay na parameter, tulad ng kasiyahan ng customer, pagiging maaasahan, aesthetics, ay mahirap isaalang-alang sa proseso ng pag-optimize, dahil halos imposible silang mabilang. Gayunpaman, sa anumang anyo ang layunin ng pag-andar ay ipinakita, ito ay dapat na isang solong halaga ng pag-andar ng mga parameter ng disenyo. Sa isang bilang ng mga problema sa pag-optimize, ang pagpapakilala ng higit sa isang layunin na function ay kinakailangan. Minsan ang isa sa kanila ay maaaring hindi tugma sa isa pa. Ang isang halimbawa ay ang disenyo ng sasakyang panghimpapawid, kapag kinakailangan na magbigay ng pinakamataas na lakas, pinakamababang timbang at pinakamababang gastos sa parehong oras. Sa ganitong mga kaso, ang taga-disenyo ay dapat magpakilala ng isang sistema ng mga priyoridad at magtalaga ng ilang dimensyon na multiplier sa bawat layunin ng function. Bilang resulta, lumilitaw ang isang "compromise function", na nagpapahintulot sa isang composite objective function na magamit sa proseso ng pag-optimize. Paghahanap ng minimum at maximum
Ang ilang mga algorithm sa pag-optimize ay iniangkop para sa paghahanap ng maximum, ang iba ay para sa paghahanap ng pinakamababa. Gayunpaman, anuman ang uri ng matinding problema na nalutas, ang isa ay maaaring gumamit ng parehong algorithm, dahil ang problema sa pag-minimize ay madaling maging isang maximum na problema sa pamamagitan ng pagbabago ng tanda ng layunin ng function sa kabaligtaran. Ang pamamaraan na ito ay inilalarawan sa Figure 6.3. Disenyo ng espasyo
Ito ang pangalan ng lugar na tinukoy ng lahat ng n mga parameter ng disenyo. Ang espasyo sa disenyo ay hindi kasing laki ng tila, dahil karaniwan itong limitado sa isang bilang mga kondisyon na nauugnay sa pisikal na kakanyahan ng problema. Ang mga hadlang ay maaaring maging napakalakas na ang gawain ay hindi magkakaroon ng anuman Fig.6.3 Pagbabago ng tanda ng layunin ng function sa kabaligtaran Ang pinakamataas na gawain ay nagiging pinakamababang gawain. kasiya-siyang solusyon. Ang mga hadlang ay nahahati sa dalawang pangkat: mga hadlang - mga pagkakapantay-pantay at mga hadlang - mga hindi pagkakapantay-pantay. Mga hadlang - pagkakapantay-pantay
Mga hadlang - pagkakapantay-pantay - ito ang pagtitiwala sa pagitan ng mga parameter ng disenyo na dapat isaalang-alang kapag naghahanap ng solusyon. Sinasalamin ng mga ito ang mga batas ng kalikasan, ekonomiya, mga karapatan, umiiral na panlasa at ang pagkakaroon ng mga kinakailangang materyales. Ang bilang ng mga paghihigpit - ang mga pagkakapantay-pantay ay maaaring anuman. Magkamukha sila C 1 (x 1 , x 2 ,...,x n)=0, C 2 (x 1 , x 2 ,...,x n)=0, .................. C j (x 1 , x 2 ,...,x n)=0. Kung ang alinman sa mga ugnayang ito ay maaaring malutas nang may paggalang sa isa sa mga parameter ng disenyo, kung gayon ito ay nagpapahintulot sa iyo na ibukod ang parameter na ito mula sa proseso ng pag-optimize. Binabawasan nito ang bilang ng mga sukat ng espasyo sa disenyo at pinapasimple ang solusyon ng problema. Mga hadlang - hindi pagkakapantay-pantay
Ito ay isang espesyal na uri ng pagpilit na ipinahayag ng mga hindi pagkakapantay-pantay. Sa pangkalahatang kaso, maaaring mayroong anumang bilang ng mga ito, at lahat ng mga ito ay may anyo z 1 r 1 (x 1 , x 2 ,...,x n) Z 1 z 2 r 2 (x 1 , x 2 ,...,x n) Z 2 ....................... z k r k (x 1 , x 2 ,...,x n) Z k Dapat tandaan na napakadalas, dahil sa mga limitasyon, ang pinakamainam na halaga ng layunin ng pag-andar ay hindi nakakamit kung saan ang ibabaw nito ay may zero gradient. Kadalasan ang pinakamahusay na solusyon ay nasa isa sa mga hangganan ng domain ng disenyo. Lokal na pinakamabuting kalagayan
Ito ang pangalan ng punto sa espasyo ng disenyo kung saan ang layunin ng pag-andar ay may pinakamalaking halaga kumpara sa mga halaga nito sa lahat ng iba pang mga punto sa agarang kapitbahayan nito. Fig.6.4 Ang isang arbitrary layunin function ay maaaring magkaroon ng ilang lokal na optima. Sa fig. Ipinapakita ng Figure 6.4 ang isang one-dimensional na layunin na function na mayroong dalawang lokal na optima. Kadalasan ang espasyo ng disenyo ay naglalaman ng maraming lokal na optima at dapat gawin ang pag-iingat na huwag magkamali sa una para sa pinakamainam na solusyon sa problema. Global Optimum
Ang pandaigdigang pinakamainam ay ang pinakamainam na solusyon para sa buong espasyo ng disenyo. Ito ay mas mahusay kaysa sa lahat ng iba pang mga solusyon na naaayon sa lokal na optima, at ito ang hinahanap ng taga-disenyo. Posible ang kaso ng ilang pantay na global optima na matatagpuan sa iba't ibang bahagi ng espasyo ng disenyo. Kung paano ipinoproblema ang problema sa pag-optimize ay pinakamahusay na inilalarawan ng isang halimbawa. Halimbawa 6.1
Hayaang kailanganin na magdisenyo ng isang hugis-parihaba na lalagyan na may volume na 1 m , na idinisenyo upang maghatid ng hindi naka-pack na hibla. Ito ay kanais-nais na ang maliit na materyal hangga't maaari ay ginugol sa paggawa ng naturang mga lalagyan (ipagpalagay na ang isang pare-pareho ang kapal ng pader, nangangahulugan ito na ang ibabaw na lugar ay dapat na minimal), dahil ito ay magiging mas mura. Upang gawing maginhawa ang pagkuha ng lalagyan na may forklift, ang lapad nito ay dapat na hindi bababa sa 1.5 m. Bumuo tayo ng problemang ito sa isang form na maginhawa para sa paglalapat ng optimization algorithm. Mga parameter ng disenyo: x 1 , x 2 , x 3 . Ang layunin ng pag-andar (na kailangang mabawasan) ay ang lugar ng gilid na ibabaw ng lalagyan: A=2(x 1 x 2 +x 2 x 3 +x 1 x 3), m2. Constraint - pagkakapantay-pantay: Dami \u003d x 1 x 2 x 3 \u003d 1m3. Limitasyon - hindi pagkakapantay-pantay: Linear Programming (LP) ay isa sa mga seksyon ng mathematical programming - isang disiplina na nag-aaral ng extremal (optimization) na mga problema at bumubuo ng mga pamamaraan para sa paglutas ng mga ito. Problema sa pag-optimize ay isang problema sa matematika na binubuo sa paghahanap ng pinakamainam (i.e., maximum o minimum) na halaga ng layunin na pag-andar, at ang mga halaga ng mga variable ay dapat kabilang sa isang tiyak na lugar ng mga tinatanggap na halaga (ODV). Sa pangkalahatan, ang pagbabalangkas ng isang matinding problema ng mathematical programming ay binubuo sa pagtukoy ng pinakamalaki o pinakamaliit na halaga ng function, na tinatawag na layunin function, sa ilalim ng mga kundisyon (paghihigpit) , kung saan at binibigyan ng mga function, at binibigyan ng mga constant. Kasabay nito, ang mga paghihigpit sa anyo ng mga pagkakapantay-pantay at hindi pagkakapantay-pantay ay tumutukoy sa hanay (rehiyon) ng mga magagawang solusyon (ODS), at tinatawag na mga parameter ng disenyo. Depende sa uri ng mga function at mga problema ng mathematical programming ay nahahati sa isang bilang ng mga klase (linear, non-linear, convex, integer, stochastic, dynamic programming, atbp.). AT pangkalahatang pananaw Ang problema sa LP ay may sumusunod na anyo: , kung saan ang , , ay binibigyan ng mga pare-pareho. Function (5.1) ay tinatawag na layunin function; system (5.2), (5.3) - sa pamamagitan ng isang sistema ng mga hadlang; kondisyon (5.4) ay ang kondisyon ng hindi negatibong mga parameter ng disenyo. Ang hanay ng mga parameter ng disenyo na nakakatugon sa mga hadlang (5.2), (5.3) at (5.4) ay tinatawag katanggap-tanggap na solusyon o plano. Ang pinakamainam na solusyon o pinakamainam na plano Ang problema sa LP ay tinatawag na feasible solution , kung saan ang layunin ng function (5.1) ay kumukuha ng pinakamainam (maximum o minimum) na halaga. Karaniwang gawain Ang LP ay tinatawag na problema sa paghahanap ng maximum (minimum) na halaga ng layunin ng function (5.1) sa ilalim ng kondisyon (5.2) at (5.4), kung saan , , i.e. mga. ang mga paghihigpit lamang sa anyo ng mga hindi pagkakapantay-pantay (5.2) at lahat ng mga parameter ng disenyo ay nakakatugon sa hindi negatibong kondisyon, at walang mga kundisyon sa anyo ng mga pagkakapantay-pantay: Canonical (pangunahing) gawain Ang LP ay tinatawag na problema sa paghahanap ng maximum (minimum) na halaga ng layunin ng function (5.1) sa ilalim ng kondisyon (5.3) at (5.4), kung saan , , i.e. mga. ang mga paghihigpit lamang sa anyo ng mga pagkakapantay-pantay (5.3) at lahat ng mga parameter ng disenyo ay nakakatugon sa kondisyong hindi negatibo, at walang mga kundisyon sa anyo ng mga hindi pagkakapantay-pantay: Ang problema sa canonical LP ay maaari ding isulat sa matrix at vector form. Ang matrix form ng canonical LP problem ay may sumusunod na anyo: Vector form ng canonical LP na problema. Kung mayroon lamang isang salik na naglilimita (halimbawa, isang kakaunting makina), ang solusyon ay matatagpuan gamit ang mga simpleng formula (tingnan ang link sa simula ng artikulo). Kung mayroong ilang mga naglilimita sa mga kadahilanan, ang linear programming method ay ginagamit. Linear programming ay ang pangalang ibinigay sa kumbinasyon ng mga tool na ginagamit sa agham ng pamamahala. Ang pamamaraang ito ay nilulutas ang problema ng paglalaan ng mga kakaunting mapagkukunan sa mga nakikipagkumpitensyang aktibidad upang ma-maximize o mabawasan ang ilang numerical na halaga, tulad ng mga marginal na kita o gastos. Sa negosyo, maaari itong gamitin sa mga lugar tulad ng pagpaplano ng produksyon upang mapakinabangan ang kita, pagpili ng mga bahagi upang mabawasan ang mga gastos, pagpili ng portfolio ng pamumuhunan upang mapakinabangan ang kita, pag-optimize ng transportasyon ng mga kalakal upang mabawasan ang mga distansya, paglalaan ng mga tauhan upang mapakinabangan ang kahusayan sa trabaho, at pag-iskedyul ng trabaho sa para makatipid ng oras. Mag-download ng tala sa , mga drawing sa format Kasama sa linear programming ang pagbuo ng isang modelo ng matematika ng problemang isinasaalang-alang. Pagkatapos nito, ang solusyon ay makikita sa graphically (tinalakay sa ibaba), gamit ang Excel (ituturing nang hiwalay) o mga espesyal na programa sa computer. Marahil ang pagbuo ng isang modelo ng matematika ay ang pinakamahirap na bahagi ng linear programming, na nangangailangan ng pagsasalin ng problemang isinasaalang-alang sa isang sistema ng mga variable, equation at hindi pagkakapantay-pantay - isang proseso na sa huli ay nakasalalay sa mga kasanayan, karanasan, kakayahan at intuwisyon ng compiler ng modelo. Isaalang-alang ang isang halimbawa ng pagbuo ng isang mathematical model ng linear programming Si Nikolai Kuznetsov ay nagpapatakbo ng isang maliit na mekanikal na halaman. Sa susunod na buwan, plano niyang gumawa ng dalawang produkto (A at B), kung saan ang tiyak na marginal na tubo ay tinatantya sa 2,500 at 3,500 rubles, ayon sa pagkakabanggit. Ang paggawa ng parehong mga produkto ay nangangailangan ng gastos ng machining, hilaw na materyales at paggawa (Larawan 1). Para sa paggawa ng bawat yunit ng produkto A, 3 oras ng pagproseso ng makina, 16 na yunit ng hilaw na materyales at 6 na yunit ng paggawa ang inilaan. Ang kaukulang mga kinakailangan para sa yunit B ay 10, 4, at 6. Hinulaan ni Nikolai na sa susunod na buwan ay makakapagbigay siya ng 330 oras ng machining, 400 yunit ng hilaw na materyales, at 240 na yunit ng paggawa. Ang teknolohiya ng proseso ng produksyon ay tulad na hindi bababa sa 12 mga yunit ng produkto B ang dapat gawin sa anumang partikular na buwan. kanin. 1. Paggamit at pagbibigay ng mga mapagkukunan Nais ni Nikolai na bumuo ng isang modelo upang matukoy ang bilang ng mga yunit ng mga produkto A at B na dapat niyang gawin sa susunod na buwan upang mapakinabangan ang marginal na kita. Ang linear na modelo ay maaaring itayo sa apat na hakbang. Stage 1. Kahulugan ng mga variable Mayroong isang target na variable (tukuyin natin itong Z) na kailangang i-optimize, iyon ay, i-maximize o i-minimize (halimbawa, kita, kita o gastos). Hinahangad ni Nikolay na i-maximize ang marginal na kita, samakatuwid, ang target na variable ay: Z = kabuuang marginal na kita (sa rubles) na natanggap sa susunod na buwan bilang resulta ng paggawa ng mga produkto A at B. Mayroong isang bilang ng mga hindi kilalang mga variable (ipahiwatig natin ang mga ito x 1, x 2, x 3, atbp.), na ang mga halaga ay dapat matukoy upang makuha ang pinakamainam na halaga ng layunin ng function, na, sa aming kaso, ay ang kabuuang marginal na tubo. Ang margin ng kontribusyon na ito ay nakasalalay sa dami ng mga produktong A at B na ginawa. Ang mga halaga ng mga dami na ito ay dapat kalkulahin, at samakatuwid ang mga ito ang nais na mga variable sa modelo. Kaya't tukuyin natin: x 1 = ang bilang ng mga yunit ng produkto A na ginawa sa susunod na buwan. x 2 = bilang ng mga yunit ng produkto B na ginawa sa susunod na buwan. Napakahalaga na malinaw na tukuyin ang lahat ng mga variable; bigyang-pansin ang mga yunit ng pagsukat at ang tagal ng panahon kung saan tinutukoy ng mga variable. Yugto. 2. Konstruksyon ng layunin ng function Ang layunin ng function ay isang linear equation na dapat na maximize o minimize. Naglalaman ito ng target na variable na ipinahayag sa mga tuntunin ng nais na mga variable, ie Z na ipinahayag sa mga tuntunin ng x 1 , x 2 ... bilang isang linear equation. Sa aming halimbawa, ang bawat manufactured na produkto A ay nagdadala ng 2500 rubles. marginal na tubo, at sa paggawa ng x 1 unit ng produkto A, ang marginal na tubo ay magiging 2500 * x 1. Katulad nito, ang marginal na kita mula sa pagmamanupaktura x 2 unit ng produkto B ay magiging 3500 * x 2. Kaya, ang kabuuang marginal na tubo na natanggap sa susunod na buwan dahil sa produksyon ng x 1 unit ng produkto A at x 2 unit ng produkto B, iyon ay, ang target na variable Z ay magiging: Z = 2500 * x 1 + 3500 * x 2 Hinahangad ni Nikolay na i-maximize ang indicator na ito. Kaya, ang layunin ng pag-andar sa aming modelo ay: I-maximize ang Z = 2500 * x 1 + 3500 * x 2 Yugto. 3. Kahulugan ng mga paghihigpit Ang mga hadlang ay isang sistema ng mga linear na equation at/o mga hindi pagkakapantay-pantay na naglilimita sa laki ng mga kinakailangang variable. Mathematically sinasalamin nila ang pagkakaroon ng mga mapagkukunan, teknolohikal na mga kadahilanan, mga kondisyon sa marketing at iba pang mga kinakailangan. Ang mga hadlang ay maaaring may tatlong uri: "mas mababa sa o katumbas", "mas malaki kaysa sa o katumbas", "mahigpit na katumbas". Sa aming halimbawa, ang mga produkto A at B ay nangangailangan ng oras ng pagproseso, mga hilaw na materyales, at paggawa upang makagawa, at ang mga mapagkukunang ito ay limitado sa kakayahang magamit. Ang dami ng produksyon ng dalawang produktong ito (i.e. ang mga halaga x 1 ng 2) ay magiging limitado sa katotohanan na ang halaga ng mga mapagkukunang kinakailangan sa proseso ng produksyon ay hindi maaaring lumampas sa kung ano ang magagamit. Isaalang-alang ang sitwasyon sa oras ng pagproseso ng makina. Ang produksyon ng bawat yunit ng produkto A ay nangangailangan ng tatlong oras ng pagpoproseso ng makina, at kung x 1 unit ang ginawa, 3 * x 1 oras ng mapagkukunang ito ang gagastusin. Ang produksyon ng bawat yunit ng produkto B ay nangangailangan ng 10 oras at, samakatuwid, kung x 2 produkto ang ginawa, 10 * x 2 oras ang kakailanganin. Kaya, ang kabuuang halaga ng oras ng makina na kinakailangan upang makagawa ng x 1 unit ng produkto A at x 2 unit ng produkto B ay 3 * x 1 + 10 * x 2 . Ang kabuuang oras ng makina na ito ay hindi maaaring lumampas sa 330 oras. Sa matematika, ito ay nakasulat bilang mga sumusunod: 3 * x 1 + 10 * x 2 ≤ 330 Ang mga katulad na pagsasaalang-alang ay nalalapat sa mga hilaw na materyales at paggawa, na nagpapahintulot sa dalawa pang paghihigpit na maisulat: 16 * x 1 + 4 * x 2 ≤ 400 6 * x 1 + 6 * x 2 ≤ 240 Sa wakas, dapat tandaan na mayroong isang kundisyon ayon sa kung saan hindi bababa sa 12 mga yunit ng produkto B ang dapat gawin: Stage 4. Pagsulat ng mga kondisyon ng non-negatibiti Ang mga kinakailangang variable ay hindi maaaring mga negatibong numero, na dapat isulat bilang mga hindi pagkakapantay-pantay x 1 ≥ 0 at x 2 ≥ 0. Sa aming halimbawa, ang pangalawang kundisyon ay kalabisan, dahil natukoy sa itaas na ang x 2 ay hindi maaaring mas mababa sa 12. Ang kumpletong modelo ng linear programming para sa problema sa produksyon ni Nikolai ay maaaring isulat bilang: I-maximize: Z = 2500 * x 1 + 3500 * x 2 Sa kondisyon na: 3 * x 1 + 10 * x 2 ≤ 330 16 * x 1 + 4 * x 2 ≤ 400 6 * x 1 + 6 * x 2 ≤ 240 Isaalang-alang ang isang graphical na paraan para sa paglutas ng isang linear na problema sa programming. Ang pamamaraang ito ay angkop lamang para sa mga problema na may dalawang kinakailangang variable. Ang modelong binuo sa itaas ay gagamitin upang ipakita ang pamamaraan. Ang mga axes sa graph ay kumakatawan sa dalawang hindi kilalang mga variable (Larawan 2). Hindi mahalaga kung aling variable ang ilalagay sa kahabaan ng aling axis. Mahalagang pumili ng sukat na sa huli ay magbibigay-daan sa iyo na bumuo ng visual na diagram. Dahil ang parehong mga variable ay dapat na hindi negatibo, ang 1st quadrant lamang ang iguguhit. kanin. 2. Linear Programming Graph Axes Isaalang-alang, halimbawa, ang unang hadlang: 3 * x 1 + 10 * x 2 ≤ 330. Inilalarawan ng hindi pagkakapantay-pantay na ito ang lugar sa ibaba ng linya: 3 * x 1 + 10 * x 2 = 330. Nag-intersect ang linyang ito sa x-axis 1 sa x 2 \u003d 0, iyon ay, ang equation ay ganito ang hitsura: 3 * x 1 + 10 * 0 \u003d 330, at ang solusyon nito: x 1 \u003d 330 / 3 \u003d 110 Katulad nito, kinakalkula namin ang mga punto ng intersection sa x 1 at x 2 axes para sa lahat ng mga kondisyon ng pagpilit: Sa graphically, ang unang limitasyon ay ipinapakita sa Fig. 3. kanin. 3. Pagbubuo ng domain ng mga magagawang solusyon para sa unang hadlang Ang anumang punto sa loob ng napiling tatsulok o sa mga hangganan nito ay susunod sa hadlang na ito. Ang nasabing mga punto ay tinatawag na wasto, at ang mga punto sa labas ng tatsulok ay tinatawag na hindi wasto. Katulad nito, ipinapakita namin ang natitirang mga paghihigpit sa tsart (Larawan 4). Ang mga halagang x 1 at x 2 sa o sa loob ng may kulay na lugar na ABCDE ay susunod sa lahat ng mga hadlang sa modelo. Ang nasabing rehiyon ay tinatawag na domain ng mga tinatanggap na solusyon. kanin. 4. Ang lugar ng mga magagawang solusyon para sa modelo sa kabuuan Ngayon, sa lugar ng mga magagawang solusyon, kinakailangan upang matukoy ang mga halaga ng x 1 at x 2 na nagpapalaki sa Z. Upang gawin ito, sa equation ng layunin ng function: Z = 2500 * x 1 + 3500 * x 2 hinahati namin (o i-multiply) ang mga coefficient bago ang x 1 at x 2 sa parehong numero, upang ang mga resultang halaga ay nasa loob ng saklaw na ipinapakita sa graph; sa aming kaso, ang naturang saklaw ay mula 0 hanggang 120; kaya ang mga coefficient ay maaaring hatiin ng 100 (o 50): Z = 25x 1 + 35x 2 pagkatapos ay magtalaga ng Z ng isang halaga na katumbas ng produkto ng mga coefficient bago ang x 1 at x 2 (25 * 35 = 875): 875 = 25x 1 + 35x 2 at, sa wakas, hanapin ang mga punto ng intersection ng linya na may mga axes x 1 at x 2: I-plot natin ang target na equation na ito sa graph sa parehong paraan tulad ng mga hadlang (Larawan 5): kanin. 5. Paglalapat ng layunin ng function (itim na tuldok na linya) sa lugar ng mga magagawang solusyon Ang halaga ng Z ay pare-pareho sa buong linya ng layunin ng function. Upang mahanap ang mga halaga ng x 1 at x 2 na nagpapalaki sa Z, kailangan mong magkatulad na ilipat ang linya ng layunin ng function sa isang punto sa loob ng mga hangganan ng lugar ng mga tinatanggap na solusyon, na matatagpuan sa maximum. distansya mula sa orihinal na linya ng layunin ng function pataas at sa kanan, iyon ay, sa punto C (Larawan 6). kanin. 6. Ang linya ng layunin ng function ay umabot na sa pinakamataas nito sa loob ng rehiyon ng mga magagawang solusyon (sa punto C) Maaari itong tapusin na ang pinakamainam na solusyon ay matatagpuan sa isa sa mga matinding punto ng lugar ng desisyon. Sa alin, ito ay depende sa slope ng layunin ng function at sa kung anong problema ang aming nilulutas: pag-maximize o pagliit. Kaya, hindi kinakailangan na gumuhit ng isang layunin na pag-andar - ang kailangan lang ay upang matukoy ang mga halaga ng x 1 at x 2 sa bawat isa sa mga matinding puntos sa pamamagitan ng pagbabasa mula sa diagram o sa pamamagitan ng paglutas ng kaukulang pares ng mga equation. Ang mga nahanap na halaga ng x 1 at x 2 ay pagkatapos ay pinapalitan sa layunin ng pag-andar upang makalkula ang katumbas na halaga ng Z. Ang pinakamainam na solusyon ay ang isa kung saan ang pinakamataas na halaga ng Z ay nakuha kapag nilutas ang problema sa pag-maximize, at ang pinakamababa kapag nilulutas ang problema sa minimization. Tukuyin natin, halimbawa, ang mga halaga ng x 1 at x 2 sa punto C. Tandaan na ang punto C ay nasa intersection ng mga linya: 3x 1 + 10x 2 = 330 at 6x 1 + 6x 2 = 240. Ang Ang solusyon sa sistemang ito ng mga equation ay nagbibigay ng: x 1 = 10, x 2 = 30. Ang mga resulta ng pagkalkula para sa lahat ng vertices ng lugar ng mga posibleng solusyon ay ibinibigay sa talahanayan: Kaya, dapat planuhin ni Nikolai Kuznetsom ang paggawa ng 10 item A at 30 item B para sa susunod na buwan, na magpapahintulot sa kanya na makatanggap ng marginal na kita na 130 libong rubles. Sa madaling sabi, ang kakanyahan ng graphical na pamamaraan para sa paglutas ng mga problema sa linear programming ay maaaring maibuod tulad ng sumusunod: KONTROL ANG GAWAIN SA DISIPLINA: "MGA PARAAN NG MGA OPTIMAL NA SOLUSYON" Opsyon numero 8 1.
Lutasin ang isang linear programming problem gamit ang isang graphical na paraan. Hanapin ang maximum at minimum ng function sa ilalim ng ibinigay na mga hadlang: Desisyon Ito ay kinakailangan upang mahanap ang pinakamababang halaga ng layunin ng pag-andar at ang maximum, sa ilalim ng sistema ng mga paghihigpit: 9x1 +3x2 ≥30, (1) X 1 + x 2 ≤4, (2) x 1 + x 2 ≤8, (3) Buuin natin ang domain ng mga tinatanggap na solusyon, i.e. lutasin nang grapiko ang sistema ng mga hindi pagkakapantay-pantay. Upang gawin ito, binubuo namin ang bawat tuwid na linya at tukuyin ang kalahating eroplano na ibinigay ng mga hindi pagkakapantay-pantay (ang kalahating eroplano ay minarkahan ng isang prime). Ang intersection ng kalahating eroplano ay ang lugar, ang mga coordinate ng mga punto kung saan nasiyahan ang kondisyon ng mga hindi pagkakapantay-pantay ng sistema ng mga hadlang ng problema. Tukuyin natin ang mga hangganan ng rehiyon ng polygon ng solusyon. Bumuo tayo ng isang tuwid na linya na tumutugma sa halaga ng function F = 0: F = 2x 1 +3x 2 = 0. Ang gradient vector na binubuo ng mga coefficient ng objective function ay nagpapahiwatig ng direksyon ng minimization ng F(X). Ang simula ng vector ay ang punto (0; 0), ang dulo ay ang punto (2; 3). Ilipat natin ang linyang ito sa parallel na paraan. Dahil interesado kami sa pinakamababang solusyon, samakatuwid, inililipat namin ang tuwid na linya hanggang sa unang pagpindot sa itinalagang lugar. Sa graph, ang linyang ito ay ipinapahiwatig ng isang tuldok na linya. Diretso Nang malutas ang sistema ng mga equation, nakukuha natin ang: x 1 = 3.3333, x 2 = 0. Saan natin mahahanap ang pinakamababang halaga ng layunin ng function: . Isaalang - alang ang layunin ng function ng problema . Bumuo tayo ng isang tuwid na linya na tumutugma sa halaga ng function F = 0: F = 2x 1 +3x 2 = 0. Ang gradient vector na binubuo ng mga coefficient ng objective function ay nagpapahiwatig ng direksyon ng pag-maximize ng F(X). Ang simula ng vector ay ang punto (0; 0), ang dulo ay ang punto (2; 3). Ilipat natin ang linyang ito sa parallel na paraan. Dahil interesado kami sa maximum na solusyon, inililipat namin ang tuwid na linya hanggang sa huling pagpindot sa itinalagang lugar. Sa graph, ang linyang ito ay ipinapahiwatig ng isang tuldok na linya. Diretso Saan natin mahahanap ang pinakamataas na halaga ng layunin ng function: . Sagot: 2
.
Lutasin ang isang linear programming problem gamit ang simplex method: Desisyon Lutasin natin ang direktang problema ng linear programming sa pamamagitan ng simplex method, gamit ang simplex table. Tukuyin natin ang pinakamababang halaga ng layunin ng function Upang mabuo ang unang reference na plano, binabawasan namin ang sistema ng mga hindi pagkakapantay-pantay sa isang sistema ng mga equation sa pamamagitan ng pagpapakilala ng mga karagdagang variable. Sa unang hindi pagkakapantay-pantay ng kahulugan (≥), ipinakilala namin ang pangunahing variable x 3
na may minus sign. Sa ika-2 hindi pagkakapantay-pantay ng kahulugan (≤), ipinakilala namin ang pangunahing variable x 4
. Sa ika-3 kahulugan ng hindi pagkakapantay-pantay (≤), ipinakilala namin ang pangunahing variable x 5 . Ipakilala natin ang mga artipisyal na variable Upang itakda ang gawain para sa pinakamababa, isinusulat namin ang layunin ng function bilang mga sumusunod: . Para sa paggamit ng mga artipisyal na variable na ipinakilala sa layunin ng pag-andar, isang tinatawag na parusa ng M ang ipinapataw, isang napakalaking positibong numero, na karaniwang hindi tinukoy. Ang resultang batayan ay tinatawag na artipisyal, at ang paraan ng solusyon ay tinatawag na paraan ng artipisyal na batayan. Bukod dito, ang mga artipisyal na variable ay hindi nauugnay sa nilalaman ng gawain, ngunit pinapayagan ka nitong bumuo ng isang panimulang punto, at pinipilit ng proseso ng pag-optimize ang mga variable na ito na kumuha ng mga zero na halaga at tiyakin ang pagiging matanggap ng pinakamainam na solusyon. Mula sa mga equation nagpapahayag kami ng mga artipisyal na variable: x 6 \u003d 4-x 1 -x 2 +x 3, na pinapalitan namin sa layunin ng function: o. Coefficient Matrix Lutasin natin ang sistema ng mga equation na may paggalang sa mga pangunahing variable: x 6
, x 4
, x 5.
Ipagpalagay na ang mga libreng variable ay 0, nakukuha namin ang unang baseline: X1 = (0,0,0,2,10,4) Ang isang pangunahing solusyon ay tinatawag na tinatanggap kung ito ay hindi negatibo. x 1
x 2
x 3
x 4
x 5
x 6
x 6
x 4
x 5
Ang kasalukuyang baseline ay hindi optimal dahil may mga positibong coefficient sa index row. Pipiliin natin ang column na tumutugma sa variable x 2 bilang nangunguna, dahil ito ang pinakamalaking koepisyent. Kalkulahin ang mga halaga D i Samakatuwid, ang 2nd line ay nangunguna. Ang elemento ng paglutas ay katumbas ng (2) at matatagpuan sa intersection ng nangungunang column at ng nangungunang hilera. x 1
x 2
x 3
x 4
x 5
x 6
x 6
x 4
x 5
Binubuo namin ang susunod na bahagi ng simplex table. Sa halip na x 4 variable, ang x 2 variable ay papasok sa plan 1. Ang linya na tumutugma sa variable na x 2 sa plan 1 ay nakuha sa pamamagitan ng paghahati sa lahat ng elemento ng linya x 4 ng plan 0 sa pamamagitan ng enabling element na RE=2. Sa lugar ng elemento ng paglutas, nakakakuha kami ng 1. Sa natitirang mga cell ng x 2 column, nagsusulat kami ng mga zero. Kaya, sa bagong plano ay napunan ang 1 hilera x 2 at haligi x 2. Ang lahat ng iba pang elemento ng bagong plan 1, kabilang ang mga elemento ng index row, ay tinutukoy ng rectangle rule. x 1
x 2
x 3
x 4
x 5
x 6
x 6
x 2
x 5
1 1 / 2 +1 1 / 2 M Ang kasalukuyang baseline ay hindi optimal dahil may mga positibong coefficient sa index row. Pipiliin natin ang column na tumutugma sa variable x 1 bilang nangunguna, dahil ito ang pinakamalaking koepisyent. Kalkulahin ang mga halaga D i sa pamamagitan ng mga hilera bilang isang quotient ng dibisyon: Samakatuwid, ang unang linya ay nangunguna. Ang elemento ng paglutas ay katumbas ng (1 1 / 2) at matatagpuan sa intersection ng nangungunang column at ng nangungunang hilera. x 1
x 2
x 3
x 4
x 5
x 6
x 6
1
1
/
2
x 2
x 5
-1
1
/
2
+1
1
/
2
M Binubuo namin ang susunod na bahagi ng simplex table. Sa halip na variable x 6 , isasama ang variable x 1 sa plan 2. Kumuha kami ng bagong simplex table: x 1
x 2
x 3
x 4
x 5
x 6
x 1
x 2
x 5
Wala sa mga value ng index row ang positibo. Samakatuwid, tinutukoy ng talahanayang ito ang pinakamainam na plano ng gawain. Ang huling bersyon ng simplex table: x 1
x 2
x 3
x 4
x 5
x 6
x 1
x 2
x 5
Dahil walang mga artipisyal na variable sa pinakamainam na solusyon (katumbas sila ng zero), ang solusyon na ito ay magagawa. Ang pinakamainam na plano ay maaaring isulat tulad ng sumusunod: x 1 \u003d 2, x 2 \u003d 2:. Sagot: 3.
Ang kumpanya na "Three fat men" ay nakikibahagi sa paghahatid ng de-latang karne mula sa tatlong bodega na matatagpuan sa iba't ibang bahagi ng lungsod hanggang sa tatlong tindahan. Ang mga stock ng de-latang pagkain na magagamit sa mga bodega, pati na rin ang dami ng mga order mula sa mga tindahan at mga rate ng paghahatid (sa maginoo na mga yunit ng pananalapi) ay ipinakita sa talahanayan ng transportasyon. Maghanap ng plano sa transportasyon na nagbibigay ng pinakamababang halaga ng pera (gawin ang orihinal na plano sa transportasyon gamit ang paraan ng "northwest corner"). Desisyon Suriin natin ang kinakailangan at sapat na kondisyon para sa pagkalutas ng problema: Ang kondisyon ng balanse ay natutugunan. Mga stock pantay na pangangailangan. Samakatuwid, ang modelo ng problema sa transportasyon ay sarado. Ilagay natin ang paunang data sa talahanayan ng pamamahagi. Pangangailangan Gamit ang paraan ng hilagang-kanlurang sulok, gagawin namin ang unang pangunahing plano ng gawain sa transportasyon. Nagsisimulang punan ang plano mula sa kaliwang sulok sa itaas. Ang gustong elemento ay 4. Para sa elementong ito, ang mga stock ay 300, ang mga pangangailangan ay 250. Dahil ang minimum ay 250, ibawas natin ito: . 300 - 250 = 50
250 - 250 = 0
Ang gustong elemento ay 2. Para sa elementong ito, ang mga stock ay 50, ang mga pangangailangan ay 400. Dahil ang minimum ay 50, ibawas natin ito: . 50 - 50 = 0
400 - 50 = 350
Ang gustong elemento ay 5. Para sa elementong ito, ang mga stock ay 300, ang mga pangangailangan ay 350. Dahil ang minimum ay 300, ibawas namin ito: 300 - 300 = 0
350 - 300 = 50
Ang gustong elemento ay 3. Para sa elementong ito, ang mga stock ay 200, ang mga pangangailangan ay 50. Dahil ang minimum ay 50, ibawas namin ito: 200 - 50 = 150
50 - 50 = 0
Ang gustong elemento ay 6. Para sa elementong ito, ang mga stock ay 150, ang mga pangangailangan ay 150. Dahil ang minimum ay 150, ibinabawas namin ito: 150 - 150 = 0
150 - 150 = 0
Pangangailangan
Mga Katulad na Dokumento
;
; 
;
; 
.
.
Gawain bilang 2
ó
ó 
Pagkatapos 
; ; 
- ang pinakamababang halaga ng function.
ó 
ó 
ó 
; ; ang pinakamataas na layunin function ay naabot kapag 
; .
Gawain bilang 3
Mga halimbawa
Makinis na mga function at sistema ng mga equation
Linear programming
Kombinatoryal na pag-optimize
Kabanata 1. Pahayag ng pangunahing problema ng linear programming
Linear programming
(1.2) hindi-negatibong mga kinakailangan
(1.3) kung saan x j– mga variable (hindi alam);
- mga coefficient ng problema sa linear programming.1.2. Simplex na paraan para sa paglutas ng mga problema sa linear programming
.6.1 Panimula
6.2 Mga Batayan ng teorya ng pag-optimize
X1, x2, x3,...,xn.
Mga problema sa linear programming
, (5.1)
, , (5.2)
, (5.3) , , , (5.5)
. ,
.
Katanggap-tanggap na saklaw
Limitasyon ng mga pinapayagang halaga
Intersection sa x-axis 1
Intersection sa x-axis 2
3 * x 1 + 10 * x 2 ≤ 330
3 * x 1 + 10 * x 2 = 330
x 1 = 110; x 2 = 0
x 1 = 0; x 2 = 33
16 * x 1 + 4 * x 2 ≤ 400
16 * x 1 + 4 * x 2 = 400
x 1 = 25; x 2 = 0
x 1 = 0; x 2 = 100
6 * x 1 + 6 * x 2 ≤ 240
6 * x 1 + 6 * x 2 = 240
x 1 = 40; x 2 = 0
x 1 = 0; x 2 = 40
x 2 ≥ 12
x 2 = 12
hindi tumatawid; tumatakbo parallel sa x-axis 1
x 1 = 0; x 2 = 12
Dot
Halaga x 1
Halaga x 2
Z \u003d 2500x 1 + 3500x 2
PERO
22
12
97 000
AT
20
20
120 000
Sa
10
30
130 000
D
0
33
115 500
E
0
12
42 000
,
.
nag-intersect sa rehiyon sa punto C. Dahil ang punto C ay nakuha bilang resulta ng intersection ng mga linya (4) at (1), kung gayon ang mga coordinate nito ay nakakatugon sa mga equation ng mga linyang ito: 
.
nag-intersect sa rehiyon sa punto B. Dahil nakuha ang punto B bilang resulta ng intersection ng mga linya (2) at (3), kung gayon ang mga coordinate nito ay natutugunan ang mga equation ng mga linyang ito: 
.
at 
.
.
sa ilalim ng mga sumusunod na kundisyon-paghihigpit: 
.
: sa unang pagkakapantay-pantay ay ipinakilala namin ang isang variable x 6
;
Ang sistemang ito ng mga equation ay may anyo: 
.
at piliin ang pinakamaliit sa kanila: min(4: 1 , 2: 2 , 10: 2) = 1.
at mula sa kanila pinipili namin ang pinakamaliit: min (3: 1 1 / 2, -, 8: 2) = 2.
,
.
=
300 + 300 + 200 = 800 .
=
250 + 400 + 150 = 800.
