Kabanata 1. Ang paksa at mga gawain ng operations research.

§ 1. Ano ang operations research at ano ang ginagawa nito.

§ 2. Mga pangunahing konsepto at prinsipyo ng pagsasaliksik ng operasyon.

§ 3. Mga modelo ng matematika ng mga operasyon.

Kabanata 2. Mga iba't ibang gawain sa pagsasaliksik ng operasyon at mga diskarte sa kanilang solusyon.

§ 4. Direkta at kabaligtaran na mga problema ng pananaliksik sa pagpapatakbo. Mga deterministikong gawain.

§ 5. Ang problema sa pagpili ng solusyon sa ilalim ng mga kondisyon ng kawalan ng katiyakan.

§ 6. Multicriteria na mga problema ng operations research. "System approach".

Kabanata 3. Linear programming.

§ 7. Mga problema ng linear programming.

§ 8. Ang pangunahing problema ng linear programming.

§ 9. Pagkakaroon ng solusyon 03LP at mga paraan ng paghahanap nito.

§ 10. Problema sa transportasyon ng linear programming.

§ 11. Mga problema ng integer programming. Ang konsepto ng non-linear programming.

Kabanata 4. Dynamic Programming.

§ 12. Paraan ng dynamic na programming.

§ 13. Mga halimbawa ng paglutas ng mga dynamic na problema sa programming.

§ 14. Ang problema ng dynamic na programming sa pangkalahatang anyo. Ang prinsipyo ng pinakamainam.

Kabanata 5 Mga random na proseso ng Markov.

§ 15. Ang konsepto ng proseso ng Markov.

§ 16. Daloy ng mga pangyayari.

§ 17. Ang mga equation ni Kolmogorov para sa mga probabilidad ng estado. Mga huling probabilidad ng mga estado.

Kabanata 6

§ 18. Mga gawain ng teorya ng pagpila. Pag-uuri ng mga sistema ng pagpila.

§ 19. Balangkas ng kamatayan at pagpaparami. Maliit na formula.

§ 20. Ang pinakasimpleng sistema ng pagpila at ang kanilang mga katangian.

§ 21. Mas masalimuot na problema sa teorya ng pagpila.

Kabanata 7. Statistical modelling ng mga random na proseso (Monte Carlo method).

§ 22. Ideya, layunin at saklaw ng pamamaraan.

§ 23. Isang lote at mga anyo ng organisasyon nito.

§ 24. Pagtukoy sa mga katangian ng isang nakatigil na random na proseso mula sa isang pagpapatupad.

Kabanata 8

§ 25. Paksa at mga problema ng teorya ng laro.

§ 26. Mga larong antagonistic na matrix.

§ 27. Mga pamamaraan para sa paglutas ng mga larong may hangganan.

§ 28. Mga problema ng teorya ng mga solusyon sa istatistika.

PAKSA AT MGA LAYUNIN NG PANANALIKSIK SA OPERASYON

Mga pangunahing konsepto at prinsipyo ng pagsasaliksik sa pagpapatakbo

Sa seksyong ito, makikilala natin ang terminolohiya, mga pangunahing konsepto at prinsipyo ng agham ng "pananaliksik sa operasyon".

Ang operasyon ay anumang kaganapan (isang sistema ng mga aksyon) na pinagsama ng isang ideya at naglalayong makamit ang ilang layunin (lahat ng mga kaganapan na tinalakay sa mga talata 1 - 8 ng nakaraang talata ay "mga operasyon").

Ang isang operasyon ay palaging isang kinokontrol na kaganapan, iyon ay, ito ay nakasalalay sa amin kung paano pumili ng ilan sa mga parameter na nagpapakilala sa organisasyon nito. Ang "Organisasyon" dito ay nauunawaan sa malawak na kahulugan ng salita, kabilang ang hanay ng mga teknikal na paraan na ginamit sa operasyon.

Anumang tiyak na pagpili ng mga parameter na depende sa atin ay tinatawag na solusyon. Ang mga desisyon ay maaaring maging matagumpay at hindi matagumpay, makatwiran at hindi makatwiran. Ang mga solusyon ay tinatawag na pinakamainam kung sila ay ginustong kaysa sa iba para sa isang kadahilanan o iba pa. Ang layunin ng operations research ay isang paunang dami ng pagbibigay-katwiran ng pinakamainam na solusyon.

Minsan (medyo bihira) bilang isang resulta ng pag-aaral, posible na magpahiwatig ng isang solong mahigpit na pinakamainam na solusyon, mas madalas - upang makilala ang isang lugar ng halos katumbas na pinakamainam (makatuwirang) mga solusyon kung saan ang pangwakas na pagpipilian ay maaaring gawin.

Tandaan na ang mismong paggawa ng desisyon ay lampas sa saklaw ng pag-aaral ng operasyon at nasa loob ng kakayahan ng responsableng tao, mas madalas - isang grupo ng mga tao na binigyan ng karapatang gumawa ng pangwakas na pagpili at responsable para sa pagpipiliang ito. Kapag gumagawa ng isang pagpipilian, maaari nilang isaalang-alang, kasama ang mga rekomendasyon na nagmula sa pagkalkula ng matematika, isang bilang ng mga pagsasaalang-alang (quantitative at qualitative na kalikasan) na hindi isinasaalang-alang ng pagkalkula na ito.

Ang kailangang-kailangan na presensya ng isang tao (bilang ang pangwakas na awtoridad sa paggawa ng desisyon) ay hindi nakansela kahit na sa pagkakaroon ng isang ganap na awtomatikong sistema ng kontrol, na, tila, ay gumagawa ng isang desisyon nang walang pakikilahok ng tao. Hindi natin dapat kalimutan na ang mismong paglikha ng isang control algorithm, ang pagpili ng isa sa mga posibleng opsyon nito, ay isang desisyon din, at isang napaka responsable. Sa pagbuo ng control automata, ang mga pag-andar ng tao ay hindi nakansela, ngunit inilipat lamang mula sa isa, elementarya, antas patungo sa isa pa, mas mataas. Bilang karagdagan, ang isang bilang ng mga awtomatikong sistema ng kontrol ay nagbibigay ng aktibong interbensyon ng tao sa panahon ng kinokontrol na proseso.

Ang mga parameter na iyon, ang kabuuan kung saan bumubuo ng isang solusyon, ay tinatawag na mga elemento ng solusyon. Maaaring lumitaw ang iba't ibang numero, vector, function, pisikal na palatandaan, atbp. bilang mga elemento ng solusyon. Halimbawa, kung ang isang plano ay iginuhit para sa transportasyon ng mga homogenous na kalakal mula sa mga punto ng pag-alis A 1, A 2, ..., A m sa mga destinasyon SA 1,В 2 , ..., В n , kung gayon ang mga elemento ng solusyon ay ang mga numerong x ij , na nagpapakita kung gaano karaming kargamento ang ipapadala mula sa 1st point of departure A i V j-ang destinasyon Sa j . Set ng mga numero x 11 , x 12, …, x 1 n , …, x m 1, x m 2 , …, xmn bumubuo ng solusyon.

Sa pinakasimpleng mga problema ng pagsasaliksik sa pagpapatakbo, ang bilang ng mga elemento ng solusyon ay maaaring medyo maliit. Ngunit sa karamihan ng mga problema na may praktikal na kahalagahan, ang bilang ng mga elemento ng solusyon ay napakalaki, na mapapatunayan ng mambabasa sa pamamagitan ng pagsisikap na independiyenteng piliin at "pangalanan" ang mga elemento ng solusyon sa mga halimbawa 1 - 8 ng nakaraang talata. Para sa pagiging simple, tukuyin namin ang buong hanay ng mga elemento ng solusyon sa pamamagitan ng isang titik x at sabihing "desisyon X".

Bilang karagdagan sa mga elemento ng solusyon na maaari naming itapon, sa ilang lawak, sa anumang gawain ng pagsasaliksik sa pagpapatakbo ay mayroon ding ibinibigay, "pagdidisiplina" na mga kondisyon na naayos mula pa sa simula at hindi maaaring labagin (halimbawa, ang kapasidad ng pagkarga ng makina, ang laki ng nakaplanong gawain;

mga katangian ng timbang ng kagamitan, atbp.). Sa partikular, ang mga naturang kundisyon ay kinabibilangan ng mga paraan (materyal, teknikal, tao) na may karapatan tayong itapon, at iba pang mga paghihigpit na ipinataw sa solusyon. Sa kanilang kabuuan, bumubuo sila ng tinatawag na "set of possible solutions".

Ipahiwatig muli ang set na ito sa pamamagitan ng isang titik x, ngunit ang katotohanan na ang solusyon X kabilang sa set na ito, isusulat namin ito bilang isang formula: X X(basahin: elemento X kasama sa set x).

Ito ay tungkol sa katotohanan na sa dami ng posibleng solusyon X i-highlight ang mga solusyong iyon X(minsan - isa, at mas madalas - isang buong hanay ng mga solusyon), na mula sa isang punto ng view o iba pa ay mas epektibo (mas matagumpay, mas kanais-nais) kaysa sa iba. Upang ihambing ang iba't ibang mga solusyon sa mga tuntunin ng kahusayan, kailangan mong magkaroon ng ilang uri ng quantitative criterion, ang tinatawag na indicator ng kahusayan (ito ay madalas na tinatawag na "objective function"). Ang tagapagpahiwatig na ito ay pinili upang ito ay sumasalamin sa target na oryentasyon ng operasyon. Ang "pinakamahusay" na solusyon ay ituturing na isa na nag-aambag sa pagkamit ng layunin sa pinakamataas na lawak. Upang piliin ang "sabihin ayon sa pangalan" na sukatan ng pagganap W, Una sa lahat, kailangan mong tanungin ang iyong sarili: kung ano ang gusto natin Ano ang ating sinisikap sa pamamagitan ng pagsasagawa ng operasyon? Kapag pumipili ng solusyon, natural na mas gugustuhin natin ang isa na bumabaligtad sa indicator ng kahusayan W maximum (o minimum). Halimbawa, gusto kong i-maximize ang kita mula sa isang operasyon; kung ang mga gastos ay isang tagapagpahiwatig ng kahusayan, ito ay kanais-nais na mabawasan ang mga ito. Kung ito ay kanais-nais na i-maximize ang tagapagpahiwatig ng kahusayan, isusulat namin ito sa form W => max, at kung mababawasan - W => min.

Kadalasan, ang operasyon ay sinamahan ng pagkilos ng mga random na kadahilanan ("whims" ng panahon, pagbabagu-bago sa supply at demand, pagkabigo ng mga teknikal na aparato, atbp.). Sa ganitong mga kaso, kadalasan, hindi ang halaga mismo, na gusto naming i-maximize (i-minimize), ngunit ang average na halaga nito (pang-matematika na inaasahan) ay kinuha bilang isang tagapagpahiwatig ng kahusayan.

Sa ilang mga kaso, nangyayari na ang operasyon, na sinamahan ng mga random na kadahilanan, ay humahabol sa ilang napaka-tiyak na layunin. A, na maaari lamang ganap na makamit o hindi makamit sa lahat ("yes-no" scheme), at hindi kami interesado sa anumang mga intermediate na resulta. Pagkatapos, bilang isang tagapagpahiwatig ng kahusayan, ang posibilidad na makamit ang layuning ito ay pinili. R(A). Halimbawa, kung ang ilang bagay ay pinaputok sa isang kailangang-kailangan na kondisyon upang sirain ito, kung gayon ang tagapagpahiwatig ng kahusayan ay ang posibilidad na masira ang bagay.

Ang maling pagpili ng tagapagpahiwatig ng pagganap ay lubhang mapanganib. Ang mga operasyon na inayos mula sa punto ng view ng isang hindi matagumpay na napiling criterion ay maaaring humantong sa hindi makatarungang mga gastos at pagkalugi (tandaan, halimbawa, ang kilalang "val" bilang pangunahing pamantayan para sa pagtatasa ng aktibidad ng ekonomiya ng mga negosyo).

Upang ilarawan ang mga prinsipyo ng pagpili ng tagapagpahiwatig ng kahusayan, bumalik tayo muli sa mga halimbawa 1 - 8 ng § 1, pumili para sa bawat isa sa kanila ng isang natural na tagapagpahiwatig ng kahusayan at ipahiwatig kung kinakailangan na i-maximize o bawasan ito. Kapag sinusuri ang mga halimbawa, dapat isaisip ng isa na hindi lahat sa kanila ay may pagpipilian ng isang tagapagpahiwatig ng kahusayan na hindi malabo na idinidikta ng pandiwang paglalarawan ng gawain, upang magkaroon ng mga pagkakaiba sa pagitan ng mambabasa at ng may-akda sa isyung ito.

1. Magplano para sa supply ng mga negosyo. Ang gawain ng operasyon ay upang matiyak ang supply ng mga hilaw na materyales na may kaunting gastos sa transportasyon. Tagapagpahiwatig ng pagganap R- ang kabuuang halaga ng pagdadala ng mga hilaw na materyales sa bawat yunit ng oras, halimbawa, isang buwan ( R => min).

2. Konstruksyon ng isang seksyon ng highway. Kinakailangang planuhin ang pagtatayo sa paraang matapos ito sa lalong madaling panahon. Ang isang natural na tagapagpahiwatig ng kahusayan ay ang oras upang makumpleto ang konstruksiyon, kung hindi ito nauugnay sa mga random na kadahilanan (mga pagkabigo ng kagamitan, pagkaantala sa pagganap ng mga indibidwal na gawa). Samakatuwid, bilang isang tagapagpahiwatig ng kahusayan, maaari mong piliin ang average na inaasahang oras T pagkumpleto ng konstruksiyon (T => min).

3. Pagbebenta ng mga pana-panahong kalakal. Bilang tagapagpahiwatig ng kahusayan, maaari nating kunin ang average na inaasahang tubo P mula sa pagbebenta ng mga kalakal para sa season (P => max).

4. Proteksyon ng niyebe sa mga kalsada. Ito ang pinaka-ekonomiko na kapaki-pakinabang na plano sa proteksyon ng snow, samakatuwid, bilang isang tagapagpahiwatig ng kahusayan, maaari mong piliin ang mga average na gastos sa bawat yunit ng oras (halimbawa, bawat taon) R para sa pagpapanatili at pagpapatakbo ng mga kalsada, kabilang ang mga gastos na nauugnay sa parehong pagtatayo ng mga kagamitang proteksiyon at clearance sa kalsada at pagkaantala sa trapiko (R => min).

5. Anti-submarine raid. Dahil ang raid ay may napaka tiyak na layunin A- ang pagkasira ng bangka, pagkatapos bilang isang tagapagpahiwatig ng kahusayan, dapat mong piliin ang posibilidad R(A) na masisira ang bangka.

6. Selective control ng mga produkto. Ang natural na sukat ng pagganap na iminungkahi ng pahayag ng problema ay ang average na inaasahang gastos. R para sa kontrol sa bawat yunit ng oras, sa kondisyon na ang control system ay nagbibigay ng isang naibigay na antas ng kalidad, halimbawa, ang average na porsyento ng mga pagtanggi ay hindi mas mataas kaysa sa tinukoy ( R=> min).

7. Medikal na pagsusuri. Bilang tagapagpahiwatig ng kahusayan, maaari mong piliin ang average na porsyento (bahagi) Q mga pasyente at carrier ng impeksyon na natukoy (Q=> suriin).

8. Serbisyo sa aklatan. Ang ilang kalabuan ay sadyang inamin sa pagbabalangkas ng problema:

hindi malinaw kung ano ang ibig sabihin ng "pinakamahusay na serbisyo sa customer" o "natutugunan ang kanilang mga pangangailangan sa pinakamalawak na posible". Kung ang kalidad ng serbisyo ay hinuhusgahan sa oras na ang subscriber na humiling ng aklat ay naghihintay na matanggap ito, kung gayon ang average na oras ay maaaring kunin bilang isang tagapagpahiwatig ng kahusayan. T mga inaasahan ng aklat ng mambabasa na nag-aplay para dito ( T=> min). Maaari mong lapitan ang isyu mula sa isang bahagyang naiibang pananaw, pagpili ng average na numero bilang isang tagapagpahiwatig ng kahusayan. M mga aklat na inilabas sa bawat yunit ng oras (M => max).

Ang isinasaalang-alang na mga halimbawa ay espesyal na pinili upang maging napakasimple na ang pagpili ng isang tagapagpahiwatig ng kahusayan ay medyo madali at direktang idinidikta ng pandiwang pagbabalangkas ng gawain, ang (halos palaging) hindi malabo na oryentasyon ng target. Gayunpaman, sa pagsasagawa, hindi ito palaging nangyayari. Ang mambabasa ay maaaring kumbinsido dito sa pamamagitan ng pagsubok, halimbawa, upang pumili ng isang tagapagpahiwatig ng kahusayan ng transportasyon sa lunsod. Ano ang dapat kunin bilang isang tagapagpahiwatig? Ang average na bilis ng paggalaw ng mga pasahero sa lungsod? O ang karaniwang bilang ng mga pasaherong dinala? O ang average na bilang ng mga kilometro na kailangang lakarin ng isang tao, na hindi maihatid ng sasakyan sa tamang lugar? May dapat isipin dito!

Sa kasamaang palad, sa karamihan ng mga problema na may praktikal na kahalagahan, ang pagpili ng tagapagpahiwatig ng kahusayan ay hindi simple at nalutas nang hindi maliwanag. Para sa anumang kumplikadong gawain, ang isang sitwasyon ay tipikal kapag ang pagiging epektibo ng isang operasyon ay hindi maaaring ganap na mailalarawan sa pamamagitan ng isang solong numero - kailangan itong isangkot ang iba upang matulungan ito. Makikilala natin ang mga ganitong problema sa "multicriteria" sa § 6.

Mga halimbawa ng paglutas ng mga dynamic na problema sa programming

Sa seksyong ito, isasaalang-alang namin (at kahit na lutasin hanggang sa wakas) ang ilang mga simpleng (sobrang pinasimple) na mga halimbawa ng mga dynamic na problema sa programming

1. Paglalagay ng pinakakapaki-pakinabang na ruta sa pagitan ng dalawang punto. Alalahanin natin ang problema 4 ng nakaraang talata at lutasin ito hanggang sa wakas sa ilalim ng labis (at sadyang) pinasimpleng mga kondisyon. Kailangan nating bumuo ng landas na nagkokonekta

dalawang puntos A At SA, kung saan ang pangalawa ay nasa hilagang-silangan ng una. Para sa pagiging simple, sabihin natin. na ang paglalagay ng landas ay binubuo ng isang serye ng mga hakbang, at sa bawat hakbang ay maaari tayong lumipat sa silangan o sa hilaga; anumang paraan mula sa A V SA ay isang stepped broken line, ang mga segment na kung saan ay parallel sa isa sa mga coordinate axes (Fig. 13.1). Ang mga gastos sa pagtatayo ng bawat isa sa mga segment na ito ay kilala. Kinakailangan na maglatag ng gayong landas mula sa A V SA, kung saan ang kabuuang halaga ay minimal.

Paano ito gagawin? Magagawa mo ang isa sa dalawang paraan: alinman ay dumaan sa lahat ng posibleng pagpipilian sa landas at piliin ang isa kung saan ang mga gastos ay minimal (at sa isang malaking bilang ng mga segment ito ay napaka, napakahirap!); o hatiin ang proseso ng paglipat mula sa A V SA sa mga indibidwal na hakbang (isang hakbang - isang segment) at i-optimize ang kontrol sa pamamagitan ng mga hakbang. Ito ay lumiliko na ang pangalawang paraan ay hindi maihahambing na mas maginhawa! dito, tulad ng sa ibang lugar sa pagsasaliksik sa pagpapatakbo, may mga pakinabang sa may layunin, organisadong paghahanap para sa isang solusyon kaysa sa walang muwang na "bulag" na enumeration.

Ipakita natin kung paano ito ginagawa sa isang partikular na halimbawa. Hatiin ang distansya mula sa A dati SA sa direksyong silangan, sabihin nating, sa 7 bahagi, at sa direksyon sa hilaga - sa 5 bahagi (sa prinsipyo, ang pagkapira-piraso ay maaaring maliit na arbitraryo). Pagkatapos ng anumang landas mula sa A V SA binubuo T\u003d 7 + 5 \u003d= 12 mga segment na nakadirekta sa silangan o hilaga (Larawan 13.2). Ilagay natin sa bawat isa sa mga segment ang isang numero na nagpapahayag (sa ilang mga arbitrary na yunit) ang halaga ng paglalagay ng landas sa kahabaan ng segment na ito. Kinakailangang pumili ng gayong landas mula sa A V SA, kung saan ang kabuuan ng mga numero sa mga segment ay minimal.

Isasaalang-alang namin ang itinayong landas bilang isang kinokontrol na sistema S, gumagalaw sa ilalim ng impluwensya ng kontrol mula sa paunang estado A hanggang sa final SA. Ang estado ng sistemang ito bago magsimula ang bawat hakbang ay mailalarawan ng dalawang coordinate: silangan (X) at hilaga (y), pareho ay integer (0 X 5 7, 0 sa 5). Para sa bawat isa sa mga estado ng system (ang nodal point ng rectangular grid sa Fig. 13.2), kailangan nating hanapin ang conditional na pinakamainam na kontrol: pumunta tayo mula sa puntong ito patungo sa hilaga (kontrol "c") o sa silangan (kontrol). "c"). Pinili ang kontrol na ito upang ang halaga ng lahat ng natitirang hakbang (kabilang ang isang ito) ay minimal. Patuloy naming tatawagin ang gastos na ito bilang "kondisyon na pinakamainam na pakinabang" (bagaman sa kasong ito ito ay hindi isang "pakinabang", ngunit isang "pagkalugi") para sa isang naibigay na estado ng system. S bago simulan ang susunod na hakbang.

Ilalahad namin ang conditional optimization procedure sa kabilang direksyon - mula sa dulo hanggang sa simula. Una sa lahat, nagsasagawa kami ng kondisyonal na pag-optimize ng huling, ika-12 hakbang. Isaalang-alang nang hiwalay ang kanang sulok sa itaas ng aming parihabang grid (Larawan 13.3). Nasaan tayo pagkatapos ng ika-11 hakbang? Tanging

kung saan sa isang (huling) hakbang maaari kang makarating SA, ibig sabihin, sa isa sa mga punto SA 1 o SA 2 . Kung tayo ang nasa punto SA 1, wala tayong pagpipilian (forced control): dapat tayong pumunta sa silangan, at aabutin tayo ng 10 units. Isulat natin ang numerong 10 na ito sa isang bilog malapit sa punto SA 1, at ang pinakamainam na kontrol ay ipapakita ng isang maikling arrow na nagmumula sa SA 1 at itinuro sa silangan. Para sa punto SA 2 pinipilit din ang kontrol (north), ang daloy hanggang sa dulo ay 14, isusulat namin ito sa isang bilog sa punto SA 2 . Kaya, ang conditional optimization ng huling hakbang ay tapos na, at ang conditional optimal gain para sa bawat isa sa mga puntos B 1 , B 2 natagpuan at naitala sa angkop na mug.

Ngayon, i-optimize natin ang penultimate (ika-11) na hakbang. Pagkatapos ng penultimate (ika-10) na hakbang, maaari tayong mapunta sa isa sa mga punto C 1, C 2, C 3(Larawan 13.4). Hanapin natin para sa bawat isa sa kanila ang isang kondisyon na pinakamainam na kontrol at isang kondisyon na pinakamainam na kabayaran. Para sa punto Mula sa 1 sapilitang pamamahala: pumunta sa silangan;

aabutin tayo ng 21 unit hanggang sa dulo (11 sa hakbang na ito, kasama ang 10, nakasulat sa isang bilog sa SA 1). Ang numero 21 ay nakasulat sa isang bilog sa isang tuldok Mula sa 1. Para sa punto Mula 2 hindi na pinipilit ang pamamahala: maaari tayong pumunta sa silangan at hilaga. Sa unang kaso, gagastos tayo ng 14 na unit sa hakbang na ito at mula SA 2 hanggang dulo - 14 pa, 28 units lang. Kung pupunta tayo sa hilaga, gagastos tayo ng 13 + 10, para sa kabuuang 23 na yunit. Samakatuwid, ang kondisyon na pinakamainam na kontrol sa punto Mula 2 - pumunta sa hilaga (markahan ito ng isang arrow, at isulat ang numero 23 sa isang bilog na malapit C 2), Para sa punto Mula 3 ang kontrol ay muling pinilit ("c"), ito ay nagkakahalaga ng 22 mga yunit hanggang sa dulo (ilagay ang arrow sa hilaga, isulat ang numero 22 sa isang bilog kapag Mula 3).

Katulad nito, ang "pag-atras" mula sa penultimate na hakbang pabalik, makikita natin para sa bawat punto na may integer na coordinate ang conditional optimal control ("c" o "b"), na tinutukoy natin sa pamamagitan ng isang arrow, at ang conditional na pinakamainam na pakinabang (paggasta sa dulo ng landas), na isinusulat namin sa isang bilog. Kinakalkula ito bilang sumusunod: ang daloy ng rate sa isang partikular na hakbang ay idinaragdag sa na-optimize na rate ng daloy, na nakasulat sa bilog kung saan humahantong ang arrow. Kaya, sa bawat hakbang, ang hakbang na ito lang ang aming ino-optimize, at ang mga sumusunod dito ay na-optimize na. Ang huling resulta ng pamamaraan ng pag-optimize ay ipinapakita sa Fig. 13.5.

Kaya, isinagawa na ang conditional optimization: nasaan man tayo, alam na natin kung saan pupunta (arrow) at kung ano ang aabutin natin para maabot ang dulo (numero sa isang bilog). Sa isang bilog sa isang tuldok A ang pinakamainam na kabayaran para sa buong pagtatayo ng landas mula sa A V SA:

W* = 118.

Ngayon ay nananatiling bumuo ng isang walang kundisyong pinakamainam na kontrol - isang tilapon na humahantong mula sa A At SA sa pinakamurang paraan. Upang gawin ito, kailangan mo lamang na "sumunod sa mga shooters", iyon ay, basahin kung ano ang kanilang inireseta na gawin sa bawat hakbang. Ang nasabing isang pinakamainam na tilapon ay minarkahan sa Fig. 13.5 dalawang beses na umikot. Ang kaukulang unconditional na pinakamainam na kontrol ay:

x* =(s, s, s, s, in, in, s, in, in, in, in, in, in),

ibig sabihin, kailangan nating gawin ang unang apat na hakbang sa hilaga, ang susunod na dalawa sa silangan, pagkatapos ay muli ang isa sa hilaga at ang natitirang lima sa silangan. Nalutas ang problema.

Tandaan na sa kurso ng conditional optimization, maaari tayong makatagpo ng kaso kapag ang parehong mga kontrol para sa ilang punto sa eroplano ay pinakamainam, ibig sabihin, humantong sa parehong halaga ng mga pondo mula sa puntong ito hanggang sa dulo. Halimbawa, sa puntong may mga coordinate (5; 1) ang parehong mga kontrol na "c" at "b" ay pinakamainam at nagbibigay ng daloy sa dulo na katumbas ng 62. Arbitraryong pipiliin namin ang alinman sa mga ito (sa aming kaso, pinili namin ang "c"; maaari rin kaming pumili "c"). Ang ganitong mga kaso ng hindi maliwanag na pagpili ng pinakamainam na kontrol ay patuloy na nakatagpo sa dynamic na programming; sa hinaharap, hindi namin espesyal na markahan ang mga ito, ngunit pumili lamang ng arbitraryong alinman sa mga katumbas na opsyon. Siyempre, ang pinakamainam na kontrol sa buong proseso ay maaaring depende sa arbitrariness na ito, ngunit hindi ang pinakamainam na pakinabang. Sa pangkalahatan, sa mga dynamic na problema sa programming (pati na rin sa mga problema sa linear programming), ang solusyon ay malayo sa palaging kakaiba.

At ngayon bumalik tayo sa simula at subukang lutasin ang problema sa isang "walang muwang" na paraan, pagpili sa bawat hakbang, simula sa una, ang pinaka kumikita (para sa hakbang na ito) na direksyon (kung dalawa sa kanila, pipiliin natin anumang). Sa ganitong paraan nagkakaroon tayo ng kontrol

x = (s, s, in, in, in, in, s, in, in, in, s, s).

Kalkulahin natin ang mga gastos para sa trajectory na ito. Magiging pantay sila W=10 +12 +8+10 +11 +13 +15+8 + +10+9+8+14=128, na tiyak na higit pa sa W* = 118. Sa kasong ito ang pagkakaiba ay hindi masyadong malaki, ngunit sa iba ito ay maaaring maging makabuluhan.

Sa problemang nalutas sa itaas, ang mga kondisyon ay sadyang pinasimple hanggang sa sukdulan. Siyempre, walang mangunguna sa riles ng tren "sa mga hakbang", gumagalaw lamang dahil sa hilaga o dahil sa silangan. Gumawa kami ng ganoong pagpapasimple upang pumili lamang mula sa dalawang kontrol sa bawat punto: "mula sa" o "sa". Sa halip na dalawang posibleng direksyon, posibleng ipakilala ang ilan sa mga ito at, bilang karagdagan, gumawa ng mas maliliit na hakbang; ito ay hindi sa pangunahing kahalagahan, ngunit, siyempre, ito complicates at lengthens ang mga kalkulasyon.

Tandaan na ang mga gawain na katulad ng mga isinasaalang-alang sa itaas ay madalas na nakatagpo sa pagsasanay: halimbawa, kapag pumipili ng pinakamabilis na landas sa pagitan ng dalawang punto o ang pinaka-ekonomiko (sa mga tuntunin ng pagkonsumo ng gasolina) ay nakakuha ng bilis at taas ng isang sasakyang panghimpapawid.

Gumawa tayo ng isang pagpasa ng pangungusap. Malamang na napansin ng matulungin na mambabasa na sa aming problema ang mga punto A At SA(simula at wakas) sa prinsipyo ay hindi naiiba sa isa't isa: posible na bumuo ng mga kondisyon na pinakamainam na kontrol hindi mula sa dulo hanggang sa simula, ngunit mula sa simula hanggang sa wakas, at walang kondisyon - sa kabaligtaran ng direksyon. Sa katunayan, ito ay totoo: sa anumang dynamic na problema sa programming, ang "simula" at "katapusan" ay maaaring palitan. Ito ay ganap na katumbas ng naunang inilarawan na pamamaraan sa mga tuntunin ng pagkalkula, ngunit ito ay medyo hindi gaanong maginhawa kapag ipinaliwanag sa salita ang ideya ng pamamaraan: mas madaling makipagtalo, na tumutukoy sa "naitatag na" na mga kondisyon sa simula nito hakbang kaysa sa mga "darating" pa pagkatapos ng hakbang na ito. Sa esensya, ang parehong mga diskarte ay ganap na katumbas.

2. Ang problema sa paglalaan ng mapagkukunan. Ginagawang posible ng dynamic na paraan ng programming na matagumpay na malutas ang maraming problema sa ekonomiya (tingnan, halimbawa, ). Isaalang-alang ang isa sa pinakasimpleng gayong mga problema. Mayroon kaming ilang stock ng mga pondo (mga mapagkukunan) sa aming pagtatapon SA, na dapat ipamahagi sa mga T negosyo P 1 , P 2 , ..., P m . Ang bawat isa sa mga negosyo i kapag namumuhunan dito X bumubuo ng kita batay sa x, ibig sabihin, kumakatawan sa ilang function ( x). Lahat ng function ( x) (i = 1, 2, ..., T) ay ibinigay (siyempre, ang mga function na ito ay hindi bumababa). Ang tanong ay kung paano maglaan ng pondo SA. sa pagitan ng mga negosyo, upang sa kabuuan ay ibinibigay nila ang pinakamataas na kita?

Ang problemang ito ay madaling malutas sa pamamagitan ng dynamic na pamamaraan ng programming. Bagama't sa pormulasyon nito ay hindi ito naglalaman ng pagbanggit ng oras, maaari mo pa ring buksan sa isip ang pagpapatakbo ng pamamahagi ng mga pondo sa ilang pagkakasunud-sunod, isinasaalang-alang ang pamumuhunan ng mga pondo sa enterprise P 1 bilang ang unang hakbang, at sa P 2 atbp.

Pinamamahalaang sistema S sa kasong ito, ang mga pondo o mapagkukunan na ibinahagi. Estado ng sistema S bago ang bawat hakbang ay nailalarawan sa pamamagitan ng isang numero S- ang cash reserve ay hindi pa na-invest. Sa problemang ito, ang "mga hakbang na kontrol" ay ang paraan x 1, x 2, ..., x 3, inilalaan sa mga negosyo. Ito ay kinakailangan upang mahanap ang pinakamainam na kontrol, ibig sabihin, tulad ng isang hanay ng mga numero x 1, x 2, ..., xm, kung saan ang kabuuang kita ay pinakamataas:

(13.1)

Lutasin muna namin ang problemang ito sa pangkalahatan, formulaic form, at pagkatapos - para sa partikular na numerical data. Maghanap para sa lahat i-th step ay ang conditional optimal payoff (mula sa hakbang na ito hanggang sa dulo), kung nilapitan namin ang hakbang na ito na may margin ng mga pondo S. Tukuyin ang kondisyon na pinakamainam na kabayaran W i (S), at ang katumbas na kondisyon na pinakamainam na kontrol ay ang mga pondong namuhunan i negosyo, - x i (S).

Simulan natin ang pag-optimize mula sa huli, T - hakbang. Dumating tayo sa hakbang na ito kasama ang natitirang mga pondo S. Ano ang dapat nating gawin? Malinaw na mamuhunan ang buong halaga S ganap sa negosyo P m. Samakatuwid, ang kondisyon na pinakamainam na kontrol sa m-ika-hakbang: ibigay sa huling negosyo ang lahat ng magagamit na pondo S, i.e.

at ang kondisyon na pinakamainam na kabayaran

W m (S)= (S).

Ibinigay ang isang buong gamut ng mga halaga S(paglalagay ng mga ito nang sapat na malapit), namin para sa bawat halaga S malalaman natin x m (S) At W m (S). Ang huling hakbang ay na-optimize.

Lumipat tayo sa penultimate (T- 1) ika-hakbang. Lumapit tayo sa kanya na may reserbang pondo S. Magpakilala W m -1 (S) kondisyon na pinakamainam na kabayaran sa huling dalawang hakbang: ( m- 1)-m at m-m (na na-optimize na). Kung maglalaan tayo sa ( m- ika-1) hakbang ( m- 1) mga pondo ng negosyo X, pagkatapos ay ang huling hakbang ay S-x. Ang aming kabayaran sa huling dalawang hakbang ay magiging katumbas ng

,

at kailangang hanapin ito X, kung saan ang pakinabang na ito ay pinakamataas:

Ang tanda ay nangangahulugan na ang pinakamataas na halaga ay kinuha sa lahat X, kung ano ang posible (upang mamuhunan ng higit sa S, we can't) from the expression in curly braces. Ang maximum na ito ay ang conditional optimal payoff para sa huling dalawang hakbang, at pagkatapos ay ang halaga X, kung saan naabot ang maximum na ito, ay ang conditional optimal na kontrol sa (T- ika-1) hakbang.

at ang kaukulang kondisyon na pinakamainam na kontrol x i (S) - na halaga X, kung saan naabot ang maximum na ito.

Sa pagpapatuloy sa ganitong paraan, sa wakas ay maabot natin ang 1st enterprise P 1 . Dito hindi natin kailangang baguhin ang mga halaga S; alam nating sigurado na ang stock bago ang unang hakbang ay katumbas ng SA:

Kaya, ang pinakamataas na kita (kita) mula sa lahat ng mga negosyo ay matatagpuan. Ngayon ay nananatili lamang ito sa "basahin ang mga rekomendasyon." Yung meaning X, kung saan naabot ang maximum (13.4), at mayroong pinakamainam na kontrol sa 1st step. Pagkatapos nating i-invest ang mga pondong ito sa 1st enterprise, magkakaroon tayo SA- ."Binabasa" ang rekomendasyon para sa halagang ito S, inilalaan namin ang pinakamainam na halaga ng mga pondo sa pangalawang negosyo:

,

at iba pa hanggang sa dulo.

Ngayon lutasin natin ang isang numerical na halimbawa. Paunang stock ng mga pondo K = 10 (conventional units), at kinakailangan na maipamahagi ito nang husto sa limang negosyo (t = 5). Para sa pagiging simple, ipagpalagay namin na integer na halaga lang ng mga pondo ang ini-invest. mga function ng kita ( X) ay ibinibigay sa Talahanayan 13.1.

Talahanayan 13.1

X
	0,5 1,0 1,4 2,0 2,5 2,8 3,0 3,0	0,1 0,5 1,2 1,8 2,5 2,9 3,5 3,5	0,6 1,1 1,2 1,4 1,6 1,7 1,8 1,8	0,3 0,6 1,3 1,4 1,5 1,5 1,5 1,5	1,0 1,2 1,3 1,3 1,3 1,3 1,3 1,3

Sa bawat hanay, simula sa isang tiyak na halaga ng mga pamumuhunan, ang mga kita ay huminto sa paglaki (sa katotohanan, ito ay tumutugma sa katotohanan na ang bawat negosyo ay magagawang "mag-master" lamang ng isang limitadong halaga ng mga pondo).

Magsagawa tayo ng conditional optimization gaya ng inilarawan sa itaas, simula sa huli, ika-5 hakbang. Sa tuwing darating tayo sa susunod na hakbang, pagkakaroon ng reserbang pondo S, sinusubukan naming maglaan ng isa o ibang halaga ng mga pondo para sa hakbang na ito, kunin ang kita sa hakbang na ito ayon sa talahanayan 13.1, idagdag ito sa na-optimize na kita sa lahat ng mga susunod na hakbang hanggang sa katapusan (isinasaalang-alang na mayroon na tayong mas kaunting mga pondo, lamang sa pamamagitan ng ganoong halaga ng mga pondo, na aming inilaan) at hanapin ang pamumuhunan kung saan ang halagang ito ay umabot sa pinakamataas nito. Ang pamumuhunan na ito ay ang kondisyon na pinakamainam na kontrol sa hakbang na ito, at ang pinakamataas mismo ay ang kondisyon na pinakamainam na pakinabang.

Ipinapakita ng talahanayan 13.2 ang mga resulta ng conditional optimization para sa lahat ng hakbang. Ang talahanayan ay nakaayos tulad ng sumusunod: ang unang hanay ay nagbibigay ng mga halaga ng stock ng mga pondo S, kasama kung saan namin nilapitan ang hakbang na ito. Dagdag pa, ang talahanayan ay nahahati sa limang pares ng mga hanay, na naaayon sa numero ng hakbang. Ang unang column ng bawat pares ay naglalaman ng value

Talahanayan 13.2

S	i=5	i=4	i=3	i=2	i=1
x5(S)	W 5(S)	x4(S)	W4(S)	x 3(S)	W 3(S)	x2(S)	W2(S)	x 1(S)	W 1(S)
		1,0 1,2 1,3 1,3 1,3 1,3 1,3 1,3 1,3 1,3		1,0 1,3 1,6 2,3 2,5 2,6 2,7 2,8 2,8 2,8		1,0 1,6 2,1 2,4 2,9 3,4 3,6 3,7 3,9 4,1		1,0 1,6 2,1 2,4 2,9 3,5 4,1 4,6 5,1 5,6		5,6

kondisyon na pinakamainam na kontrol, sa pangalawang - kondisyon na pinakamainam na kabayaran. Ang talahanayan ay puno mula kaliwa hanggang kanan, itaas hanggang ibaba. Ang desisyon sa ikalimang - huling - hakbang ay pinilit: ang lahat ng mga pondo ay inilalaan;

Sa lahat ng iba pang hakbang, kailangang i-optimize ang solusyon. Bilang resulta ng sunud-sunod na pag-optimize ng ika-5, ika-4, ika-3, ika-2 at ika-1 hakbang, makakakuha kami ng kumpletong listahan ng lahat ng mga rekomendasyon para sa pinakamainam na kontrol at isang walang kundisyong pinakamainam na pakinabang W* para sa buong operasyon - sa kasong ito, ito ay katumbas ng 5.6. Sa huling dalawang hanay ng Talahanayan 13.2, isang linya lamang ang napunan, dahil alam natin nang eksakto ang estado ng system bago magsimula ang unang hakbang:

S0 = K = 10. Ang mga pinakamainam na kontrol sa lahat ng mga hakbang ay naka-frame. Kaya, nakuha namin ang pangwakas na konklusyon: kailangan naming maglaan ng dalawang yunit mula sa sampu sa unang negosyo, limang yunit sa pangalawa, dalawa sa ikatlo, wala sa ikaapat, isang yunit sa ikalima. Sa distribusyon na ito, ang kita ay magiging pinakamataas at katumbas ng 5.6.

Upang maging malinaw sa mambabasa kung paano pinupunan ang talahanayan 13.2, ipapakita namin ito sa isang sample ng pagkalkula. Hayaan, halimbawa, kailangan nating i-optimize ang solusyon x 3(7)- kung ano ang gagawin sa ikatlong hakbang, kung nilapitan natin ito ng may reserbang pondo S= 7, at kung ano ang maximum na maaari nating mapanalunan sa lahat ng natitira

Talahanayan 13.3

x	7 - x		W4(7 - x)	+W 4 (7 - x)
		1,8 1,7 1,6 1,4 1,2 1,1 0,6	1,0 1,3 1,6 2,3 2,5 2,6 2,7	1,8 2,7 2,9 3,0 3,5 3,2 2,7

mga hakbang, kabilang ang pangatlo? Ipagpalagay natin na ang lahat ng mga hakbang pagkatapos ng ikatlo (ika-4 at ika-5) ay na-optimize na, iyon ay, ang unang dalawang pares ng mga hanay ng Talahanayan 13.2 ay napunan na. Hanapin natin x 3 (7) at W 3(7). Upang gawin ito, bubuo kami ng isang pantulong na plato (tingnan ang talahanayan 13.3). Inililista ng unang column ang lahat ng posibleng attachment. X sa ikatlong hakbang, hindi hihigit S = 7. Sa pangalawang hanay - kung ano ang mananatili pagkatapos ng naturang pamumuhunan mula sa stock ng mga pondo S = 7. Sa ikatlong hanay - ang pakinabang sa ikatlong hakbang mula sa pamumuhunan X sa ikatlong enterprise ay napunan ng column (talahanayan 13.1). Sa ika-apat na hanay - ang pinakamainam na kabayaran sa lahat ng natitirang mga hakbang (ika-apat at ikalima), sa kondisyon na nilapitan namin ang ika-apat na hakbang kasama ang natitirang mga pondo (napuno sa hanay ako = 4 na talahanayan 13.2). Sa ikalimang column - ang kabuuan ng dalawang kabayaran: hakbang at mas na-optimize para sa isang partikular na pamumuhunan X sa ikatlong hakbang.

Sa lahat ng mga kabayaran ng huling column, ang pinakamataas na isa ay pinili (sa talahanayan 13.3 ito ay katumbas ng W 3(7) = 3.6, at ang kaukulang kontrol X(7) = 2).

Ang tanong ay lumitaw: paano kung sa auxiliary table ng uri 13.3 ang maximum ay naabot para sa higit sa isa x, at sa dalawa o higit pa? Sagot namin: hindi mahalaga kung alin ang pipiliin; ang pakinabang ay hindi nakasalalay dito. Sa pangkalahatan, sa mga dynamic na problema sa programming, ang solusyon ay hindi dapat natatangi sa lahat (nabanggit na namin ito).

3. Ang problema sa paglo-load ng makina. Gamit ang dynamic na paraan ng programming, maaari mong matagumpay na malutas ang isang bilang ng mga problema sa pag-optimize na inilarawan sa Kabanata 3, sa partikular, ilang mga problema sa integer programming. Tandaan na ang integrality ng mga solusyon, na nagpapahirap sa mga problema sa linear programming, sa kasong ito ay hindi kumplikado, ngunit, sa kabaligtaran, pinapasimple ang pamamaraan (dahil ito ay pinasimple para sa amin ng integrality ng mga pag-embed sa nakaraang problema).

Bilang halimbawa, isaalang-alang ang problema sa pag-load ng makina (nabanggit na natin ito sa nakaraang kabanata): mayroong isang tiyak na hanay ng mga bagay P 1 , P 2 ,..., P n (bawat isa sa isang kopya); ang kanilang mga timbang ay kilala q 1 , q 2 , ..., q n at gastos mula 1, may 2 , ..., may n . Ang kapasidad ng pagkarga ng makina ay Q. Ang tanong ay kung alin sa mga item ang dapat dalhin sa kotse upang ang kanilang kabuuang gastos (na may kabuuang timbang Q) ay ang maximum?

Dapat mong matutunan ang mga pangunahing konsepto at kahulugan ng pananaliksik sa pagpapatakbo.

Ang operasyon ay anumang kinokontrol na aktibidad na naglalayong makamit ang isang layunin. Ang resulta ng operasyon ay nakasalalay sa paraan ng pagpapatupad nito, organisasyon, kung hindi man - sa pagpili ng ilang mga parameter. Anumang tiyak na pagpili ng mga parameter ay tinatawag na solusyon. Ang mga pinakamainam na solusyon ay itinuturing na yaong, para sa isang kadahilanan o iba pa, ay mas kanais-nais kaysa sa iba. Samakatuwid, ang pangunahing gawain ng pananaliksik sa pagpapatakbo ay isang paunang dami ng pagbibigay-katwiran ng mga pinakamainam na solusyon.

Puna 1

Dapat bigyang-pansin ang pagbabalangkas ng problema: ang paggawa ng desisyon mismo ay lumampas sa saklaw ng pagsasaliksik sa pagpapatakbo at nabibilang sa kakayahan ng responsableng tao o grupo ng mga tao, na maaaring isaalang-alang ang iba pang mga pagsasaalang-alang maliban sa mathematically justified.

Puna 2

Kung sa ilang mga gawain ng pagsasaliksik ng mga operasyon ang pinakamainam na solusyon ay ang isa kung saan ang napiling pamantayan ng kahusayan ay tumatagal sa pinakamataas o pinakamababang halaga, kung gayon sa iba pang mga gawain ito ay hindi kinakailangan. Kaya, sa problema maaari naming isaalang-alang ang pinakamainam, halimbawa, tulad ng isang bilang ng mga retail outlet at kawani sa kanila, kung saan ang average na oras ng serbisyo sa customer ay hindi lalampas, halimbawa, 5 minuto, at ang average na haba ng pila sa anumang oras ay hindi hihigit sa 3 tao (1, pahina .10-11).

Ang kahusayan ng produksyon at komersyal na mga aktibidad ay higit na tinutukoy ng kalidad ng mga desisyon na ginawa araw-araw ng mga tagapamahala ng iba't ibang antas. Sa pagsasaalang-alang na ito, ang mga gawain ng pagpapabuti ng mga proseso ng paggawa ng desisyon, na pinahihintulutan ng pagsasaliksik ng operasyon na malutas, ay may malaking kahalagahan. Ang terminong "pananaliksik sa operasyon" ay unang ginamit noong 1939-1940. sa lugar ng militar. Sa panahong ito, ang mga kagamitang militar at ang pamamahala nito ay naging mas kumplikado sa panimula bilang resulta ng rebolusyong siyentipiko at teknolohikal. At samakatuwid, sa simula ng Ikalawang Digmaang Pandaigdig, mayroong isang kagyat na pangangailangan na magsagawa ng siyentipikong pananaliksik sa larangan ng epektibong paggamit ng mga bagong kagamitang militar, pagtatasa ng dami at pag-optimize ng mga desisyon na ginawa ng utos. Sa panahon ng post-war, ang mga tagumpay ng bagong disiplinang pang-agham ay hinihiling sa mga mapayapang lugar: sa industriya, mga aktibidad sa entrepreneurial at komersyal, sa mga institusyon ng gobyerno, at sa mga institusyong pang-edukasyon.

Ang operations research ay isang metodolohiya para sa paglalapat ng mga mathematical quantitative na pamamaraan upang bigyang-katwiran ang mga solusyon sa mga problema sa lahat ng lugar ng may layuning aktibidad ng tao. Nagbibigay-daan sa iyo ang mga pamamaraan at modelo ng operations research na makakuha ng mga solusyon na pinakamahusay na nakakatugon sa mga layunin ng organisasyon.

Ang pananaliksik sa operasyon ay isang agham na may kinalaman sa pagbuo at praktikal na aplikasyon ng mga pamamaraan para sa pinakamabisang (o pinakamainam) na pamamahala ng mga sistema ng organisasyon.

Ang pangunahing postulate ng pananaliksik sa pagpapatakbo ay ang mga sumusunod: ang pinakamainam na solusyon (kontrol) ay isang hanay ng mga halaga ng mga variable na nakakamit ang pinakamainam (maximum o minimum) na halaga ng kriterya ng kahusayan (layunin function) ng operasyon at sinusunod ang tinukoy na mga paghihigpit.

Ang paksa ng pananaliksik sa pagpapatakbo ay ang problema sa paggawa ng pinakamainam na mga desisyon sa isang sistema na may kontrol batay sa isang pagtatasa ng pagiging epektibo ng paggana nito. Ang mga katangiang konsepto ng pagsasaliksik ng operasyon ay: modelo, variable na variable, hadlang, layunin na pag-andar.

Ang paksa ng pananaliksik sa pagpapatakbo sa katotohanan ay ang mga sistema ng pamamahala ng organisasyon (mga organisasyon), na binubuo ng isang malaking bilang ng mga nakikipag-ugnayan na mga departamento, at ang mga interes ng mga departamento ay hindi palaging pare-pareho sa bawat isa at maaaring magkasalungat.

Ang layunin ng pananaliksik sa pagpapatakbo ay upang patunayan sa dami ang mga desisyong ginawa sa pamamahala ng mga organisasyon.

Ang solusyon na pinaka-kapaki-pakinabang para sa buong organisasyon ay tinatawag na pinakamainam na solusyon, at ang solusyon na pinaka-kapaki-pakinabang sa isa o higit pang mga departamento ay magiging suboptimal.

Bilang isang halimbawa ng isang tipikal na gawain ng pamamahala ng organisasyon, kung saan ang magkasalungat na interes ng mga kagawaran ay nagbabanggaan, isaalang-alang ang problema sa pamamahala ng imbentaryo ng isang negosyo.

Ang departamento ng produksyon ay nagsusumikap na makagawa ng maraming produkto hangga't maaari sa pinakamababang halaga. Samakatuwid, siya ay interesado sa pinakamahabang posible at tuluy-tuloy na produksyon, ibig sabihin, sa produksyon ng mga produkto sa malalaking batch, dahil ang naturang produksyon ay binabawasan ang gastos ng muling pag-configure ng mga kagamitan, at samakatuwid ang kabuuang gastos sa produksyon. Gayunpaman, ang paggawa ng mga produkto sa malalaking dami ay nangangailangan ng paglikha ng malalaking dami ng mga stock ng mga materyales, mga bahagi, atbp.

Interesado rin ang departamento ng pagbebenta sa malalaking stock ng mga natapos na produkto upang matugunan ang anumang pangangailangan ng customer sa anumang oras. Sa pagtatapos ng bawat kontrata, ang departamento ng pagbebenta, na nagsusumikap na magbenta ng maraming produkto hangga't maaari, ay dapat mag-alok sa mamimili ng pinakamalawak na posibleng hanay ng mga produkto. Bilang resulta, madalas na may salungatan sa pagitan ng departamento ng produksyon at departamento ng pagbebenta sa hanay ng produkto. Kasabay nito, iginigiit ng departamento ng pagbebenta ang pagsasama sa plano ng maraming mga produkto na ginawa sa maliit na dami, kahit na hindi sila nagdadala ng malaking kita, at hinihiling ng departamento ng produksyon ang pagbubukod ng mga naturang produkto mula sa hanay ng produkto.

Ang departamento ng pananalapi, na naglalayong bawasan ang halaga ng kapital na kinakailangan para sa pagpapatakbo ng negosyo, ay sinusubukan na bawasan ang halaga ng "kaugnay" na kapital na nagtatrabaho. Samakatuwid, interesado siyang bawasan ang mga stock sa pinakamababa. Tulad ng nakikita mo, ang mga kinakailangan para sa laki ng mga stock para sa iba't ibang mga departamento ng organisasyon ay iba. Ang tanong ay lumitaw kung aling diskarte sa imbentaryo ang magiging pinaka-kapaki-pakinabang sa buong organisasyon. Ito ay isang tipikal na gawain ng pamamahala ng organisasyon. Ito ay konektado sa problema ng pag-optimize ng paggana ng system sa kabuuan at nakakaapekto sa magkasalungat na interes ng mga dibisyon nito.

Mga Pangunahing Tampok ng Pananaliksik sa Operasyon:

1. Isang sistematikong diskarte sa pagsusuri ng problemang iniharap. Ang system approach, o system analysis, ay ang pangunahing metodolohikal na prinsipyo ng operations research, na ang mga sumusunod. Anumang gawain, gaano man ito kapribado sa unang tingin, ay isinasaalang-alang mula sa punto ng view ng impluwensya nito sa pamantayan para sa paggana ng buong sistema. Sa itaas, ang sistematikong diskarte ay inilalarawan ng halimbawa ng problema sa pamamahala ng imbentaryo.

2. Karaniwang para sa pagsasaliksik ng operasyon na kapag nilulutas ang bawat problema, parami nang parami ang mga bagong gawain na lumitaw. Samakatuwid, kung ang makitid, limitadong mga layunin ay itinakda sa simula, ang paggamit ng mga pamamaraan sa pagpapatakbo ay hindi epektibo. Ang pinakamalaking epekto ay makakamit lamang sa patuloy na pananaliksik, na tinitiyak ang pagpapatuloy sa paglipat mula sa isang gawain patungo sa isa pa.

3. Isa sa mga mahahalagang katangian ng operations research ay ang pagnanais na mahanap ang pinakamainam na solusyon sa problema. Gayunpaman, ang gayong solusyon ay madalas na lumalabas na hindi matamo dahil sa mga limitasyon na ipinataw ng mga magagamit na mapagkukunan (pera, oras ng computer) o ang antas ng modernong agham. Halimbawa, para sa maraming mga problemang kombinatoryal, sa partikular, mga problema sa pag-iiskedyul na may bilang ng mga makina n > 4, ang pinakamainam na solusyon sa modernong pag-unlad ng matematika ay matatagpuan lamang sa pamamagitan ng isang simpleng enumeration ng mga opsyon. Pagkatapos ay kailangang limitahan ng isa ang sarili sa paghahanap para sa isang "sapat na mabuti" o suboptimal na solusyon. Samakatuwid, tinukoy ng isa sa mga tagalikha nito, si T. Saaty, ang pagsasaliksik sa pagpapatakbo bilang "... ang sining ng pagbibigay ng masasamang sagot sa mga praktikal na tanong na binibigyan ng mas masahol pang mga sagot ng ibang mga pamamaraan."

4. Ang isang tampok ng operational research ay na ito ay isinasagawa sa isang kumplikadong paraan, sa maraming lugar. Isang operational group ang ginagawa para magsagawa ng naturang pag-aaral. Binubuo ito ng mga espesyalista mula sa iba't ibang larangan ng kaalaman: mga inhinyero, mathematician, ekonomista, sosyologo, psychologist. Ang gawain ng paglikha ng naturang mga grupo ng pagpapatakbo ay isang komprehensibong pag-aaral ng buong hanay ng mga kadahilanan na nakakaimpluwensya sa solusyon ng problema, at ang paggamit ng mga ideya at pamamaraan ng iba't ibang mga agham.

Ang bawat operational research ay dumadaan sa mga sumusunod na pangunahing yugto sa pagkakasunud-sunod:

1) paglalarawan ng gawain sa pagpaplano,

2) pagbuo ng isang modelo ng matematika,

3) paghahanap ng solusyon,

4) pagsuri at pagwawasto sa modelo,

5) pagpapatupad ng nahanap na solusyon sa pagsasanay.

Paglalarawan ng gawain sa pagpaplano:

Mga gawain ng pagpaplano at pamamahala ng network

isaalang-alang ang kaugnayan sa pagitan ng mga deadline para sa pagkumpleto ng isang malaking complex ng mga operasyon (mga gawa) at ang mga sandali ng simula ng lahat ng mga operasyon ng complex. Ang mga gawaing ito ay binubuo sa paghahanap ng pinakamababang tagal ng isang hanay ng mga operasyon, ang pinakamainam na ratio ng gastos at timing ng kanilang pagpapatupad.

Ang mga gawain sa pagpila ay nakatuon sa pag-aaral at pagsusuri ng mga sistema ng pagpila na may mga pila ng mga aplikasyon o mga kinakailangan at binubuo sa pagtukoy ng mga tagapagpahiwatig ng pagganap ng mga system, ang kanilang mga pinakamainam na katangian, halimbawa, sa pagtukoy ng bilang ng mga channel ng serbisyo, oras ng serbisyo, atbp.

Ang mga gawain sa pamamahala ng imbentaryo ay upang mahanap ang pinakamainam na halaga ng mga antas ng imbentaryo (mga punto ng order) at mga laki ng order. Ang kakaiba ng naturang mga gawain ay na sa isang pagtaas sa antas ng mga stock, sa isang banda, ang mga gastos ng kanilang imbakan ay tumaas, ngunit, sa kabilang banda, ang mga pagkalugi dahil sa isang posibleng kakulangan ng stock na produkto ay bumaba.

Ang mga problema sa paglalaan ng mapagkukunan ay lumitaw sa isang tiyak na hanay ng mga operasyon (mga gawa) na dapat gawin nang may limitadong magagamit na mga mapagkukunan, at kinakailangan upang mahanap ang pinakamainam na pamamahagi ng mga mapagkukunan sa pagitan ng mga operasyon o ang komposisyon ng mga operasyon.

Ang mga gawain ng pagkumpuni at pagpapalit ng mga kagamitan ay may kaugnayan dahil sa pagkasira ng kagamitan at ang pangangailangan na palitan ito sa paglipas ng panahon. Ang mga gawain ay nabawasan sa pagtukoy ng pinakamainam na timing, ang bilang ng mga preventive repair at check, pati na rin ang mga sandali ng pagpapalit ng kagamitan sa mga modernized.

Ang mga gawain ng pag-iskedyul (pag-iskedyul) ay upang matukoy ang pinakamainam na pagkakasunud-sunod ng mga operasyon (halimbawa, mga bahagi ng pagproseso) sa iba't ibang uri ng kagamitan.

Ang mga gawain ng pagpaplano at paglalagay ay upang matukoy ang bilang at lokasyon ng mga bagong bagay, na isinasaalang-alang ang kanilang pakikipag-ugnayan sa mga umiiral na bagay at sa kanilang mga sarili.

Ang mga problema sa pagpili ng ruta, o mga problema sa network, ay kadalasang nararanasan sa pag-aaral ng iba't ibang problema sa transportasyon at sa sistema ng komunikasyon at binubuo sa pagtukoy ng pinakamatipid na mga ruta (1, p. 15).

Sa ilalim operasyon ay nauunawaan bilang anumang kaganapan na pinag-isa ng isang ideya at direksyon upang makamit ang isang tiyak na layunin.

Ang isang operasyon ay palaging isang pinamamahalaang kaganapan, i.e. nasa atin na ang pumili ng mga parameter na nagpapakilala sa paraan ng pagkakaayos nito.

Ang anumang tiyak na pagpipilian ng mga parameter depende sa amin ay tatawagin desisyon.

Ang mga pinakamainam na solusyon ay yaong, para sa isang kadahilanan o iba pa, ay mas kanais-nais kaysa sa iba.

Ang pangunahing layunin ng pananaliksik sa pagpapatakbo ay paunang quantitative na pagbibigay-katwiran ng pinakamainam na solusyon. Ang pananaliksik sa pagpapatakbo ay hindi naglalayong ganap na i-automate ang paggawa ng desisyon. Ang desisyon ay palaging ginagawa ng tao. Ang layunin ng operations research ay upang makagawa ng quantitative data at mga rekomendasyon na nagpapadali para sa isang tao na gumawa ng mga desisyon.

Kasama ang pangunahing gawain - pagpapatibay ng pinakamainam na solusyon - Kasama sa saklaw ng pananaliksik sa pagpapatakbo ang iba pang mga gawain:

Paghahambing na pagsusuri ng iba't ibang mga opsyon para sa pag-aayos ng operasyon,

Pagsusuri ng epekto sa pagpapatakbo ng iba't ibang mga parameter,

Pagsisiyasat ng "mga bottleneck", i.e. elemento, ang pagkagambala nito ay may partikular na malakas na epekto sa tagumpay ng operasyon, atbp.

Ang mga pantulong na gawain na ito ay partikular na kahalagahan kapag ang isang naibigay na operasyon ay itinuturing na hindi nakahiwalay, ngunit bilang isang mahalagang elemento ng kabuuan. mga sistema mga operasyon. Ang isang "systemic" na diskarte sa mga gawain ng pananaliksik sa pagpapatakbo ay nangangailangan ng pagsasaalang-alang sa mutual dependence at conditionality ng isang buong hanay ng mga aktibidad, i.e. gawin ang pangwakas na desisyon na isinasaalang-alang ang papel at lugar ng operasyong ito sa system.

Sa ilalim kahusayan Ang operasyon ay nauunawaan bilang ang antas ng pagbagay nito sa pagganap ng gawaing kinakaharap nito.

Upang hatulan ang pagiging epektibo ng isang operasyon at upang ihambing ang pagiging epektibo ng iba't ibang organisadong mga operasyon, ang isa ay dapat magkaroon ng ilang numero. pamantayan sa pagsusuri o tagapagpahiwatig ng pagganap.

Pagkakasunod-sunod ng mga aksyon sa operations research.

1. Nabuo ang layunin ng pag-aaral at nabuo ang paglalahad ng suliranin.

2. Upang mailapat ang mga pamamaraan ng dami sa anumang larangan, palaging kinakailangan na bumuo ng isang modelo ng matematika ng kababalaghan. Batay sa pagsusuri ng mga katangian ng orihinal, ang modelong ito ay binuo.

3. Pagkatapos buuin ang modelo, ang mga resulta ay nakuha dito

4. Ang mga ito ay binibigyang kahulugan sa mga tuntunin ng orihinal at inilipat sa orihinal.

5. Sa tulong ng paghahambing, ang mga resulta ng simulation ay inihambing sa mga resulta na nakuha mula sa isang direktang pag-aaral ng orihinal.

Kung ang mga resulta na nakuha gamit ang modelo ay malapit sa mga resulta na nakuha sa pag-aaral ng orihinal, kung gayon tungkol sa mga katangiang ito, ang modelo ay maaaring ituring na sapat sa orihinal.

Kapag nagdidisenyo at nagpapatakbo ng mga awtomatikong sistema ng kontrol, ang mga gawain ay madalas na lumitaw na may kaugnayan sa pagsusuri ng parehong dami at husay na mga pattern ng kanilang paggana, pagtukoy ng kanilang pinakamainam na istraktura, atbp.

Ang direktang pag-eksperimento sa mga bagay upang malutas ang mga problemang ito ay may ilang makabuluhang disadvantages:

1. Ang itinatag na paraan ng pagpapatakbo ng bagay ay nilabag.

2. Sa isang buong sukat na eksperimento, imposibleng suriin ang lahat ng alternatibong opsyon para sa pagbuo ng isang sistema, atbp.

Maipapayo na lutasin ang mga problemang ito sa isang modelo na hiwalay sa bagay at ipinatupad sa isang computer.

Kapag nagmomodelo ng mga sistema ng impormasyon, ang mga modelo ng matematika ay malawakang ginagamit.

Ang pamamaraan ng pagmomodelo ng matematika ay isang paraan ng pag-aaral ng iba't ibang mga bagay sa pamamagitan ng pagsasama-sama ng angkop na paglalarawan sa matematika at pagkalkula, batay dito, ang mga katangian ng bagay na pinag-aaralan.

Ito ay kinakailangan upang bumuo ng isang mathematical model. Ito ay pormal na sumasalamin sa paggana ng orihinal at inilalarawan ang mga pangunahing pattern ng pag-uugali nito. Sa kasong ito, ang lahat ng pangalawa, hindi gaanong kahalagahan ay hindi kasama sa pagsasaalang-alang.

Ang object ng mathematical modeling ay mga kumplikadong sistema. Ang isang kumplikadong sistema ay isang tiyak na paraan na organisado at may layunin na gumaganang hanay ng isang malaking bilang ng mga elementong nauugnay sa impormasyon at nakikipag-ugnayan sa ilalim ng impluwensya ng mga panlabas na salik.

Mayroong 4 na pangunahing yugto ng mga sistema ng pagmomodelo sa isang computer:

Pagbuo ng isang konseptwal na modelo ng sistema at ang pormalisasyon nito;

Algorithmization ng system model at pagbuo ng isang modeling program;

Pagkuha at pagbibigay-kahulugan sa mga resulta ng paunang simulation;

Sinusuri ang kasapatan ng modelo at sistema; pagsasaayos ng modelo

Ang pangunahing pagkalkula ng mga tagapagpahiwatig ng kalidad ng paggana ng system batay sa mga resulta ng pagmomolde, ang pagpapatupad ng modelo.

Lektura 3. Pangunahing konsepto ng paraan ng mga pagtatasa ng eksperto. Pagbuo ng mga pangkat ng dalubhasa. mga pamamaraan ng botohan. Mga paraan ng pagraranggo, pagpaparis na paghahambing, pagsusuri sa isang relatibong sukat.

1. Pangunahing konsepto ng IO

AT TUNGKOL SA – siyentipikong disiplina, na nakikibahagi sa pagbuo at praktikal na aplikasyon ng mga pamamaraan para sa pinakamabisang pamamahala ng iba't ibang sistema ng organisasyon.

Kasama sa IO ang mga sumusunod na seksyon:

1) programa sa matematika. (pagpapatibay ng mga plano, mga programa ng aktibidad sa ekonomiya); kabilang dito ang mga seksyon: linear program, non-linear program, dynamic na programa

2) ang teorya ng pagpila batay sa teorya ng mga random na proseso;

3) teorya ng laro, na ginagawang posible na patunayan ang mga desisyon na ginawa sa ilalim ng mga kondisyon ng hindi kumpleto ng impormasyon.

Kapag nilulutas ang isang partikular na problema sa kontrol, ang paggamit ng mga pamamaraan ng IO ay kinabibilangan ng:

Pagbuo ng mga modelong pang-ekonomiya at matematika para sa mga problema sa paggawa ng desisyon sa mga kumplikadong sitwasyon o sa mga kondisyon ng kawalan ng katiyakan;

Pag-aaral sa mga ugnayang tumutukoy sa kasunod na paggawa ng desisyon, at pagtatatag ng pamantayan sa pagganap na nagpapahintulot sa pagsusuri ng bentahe ng isa o ibang kurso ng pagkilos.

Pangunahing konsepto at kahulugan ng IO.

Operasyon – anumang kinokontrol na aktibidad na naglalayong makamit ang isang layunin. Ang resulta ng operasyon ay nakasalalay sa paraan ng pagpapatupad nito, organisasyon, kung hindi man - sa pagpili ng ilang mga parameter. Ang isang operasyon ay palaging isang kinokontrol na kaganapan, iyon ay, ito ay nakasalalay sa amin kung paano pumili ng ilan sa mga parameter na nagpapakilala sa organisasyon nito. Ang "Organisasyon" dito ay nauunawaan sa malawak na kahulugan ng salita, kabilang ang hanay ng mga teknikal na paraan na ginamit sa operasyon.

Ang anumang ibinigay na pagpipilian ng mga parameter ay tinatawag desisyon . Ang mga desisyon ay maaaring maging matagumpay at hindi matagumpay, makatwiran at hindi makatwiran. Pinakamainam isaalang-alang ang mga solusyon na, para sa isang kadahilanan o iba pa, ay mas kanais-nais kaysa sa iba. Ang pangunahing gawain ng pananaliksik sa pagpapatakbo ay ang paunang dami ng pagbibigay-katwiran ng mga pinakamainam na solusyon.

Modelo ng operasyon – ito ay isang medyo tumpak na paglalarawan ng operasyon gamit ang mathematical apparatus (iba't ibang uri ng mga function, equation, sistema ng mga equation at hindi pagkakapantay-pantay, atbp.). Ang pagguhit ng isang modelo ng operasyon ay nangangailangan ng pag-unawa sa kakanyahan ng inilarawan na kababalaghan at kaalaman sa mathematical apparatus.

Ang kahusayan ng pagpapatakbo – ang antas ng kakayahang umangkop nito sa katuparan ng gawain ay quantitatively ipinahayag sa anyo ng isang kahusayan criterion - ang layunin function. Ang pagpili ng pamantayan ng kahusayan ay tumutukoy sa praktikal na halaga ng pag-aaral. (Maaaring makasama ang isang maling napiling pamantayan, dahil ang mga operasyong inayos sa ilalim ng gayong pamantayan ng kahusayan ay minsan ay humahantong sa hindi makatarungang mga gastos.)

Mga gawain ng pagpaplano at pamamahala ng network isaalang-alang ang kaugnayan sa pagitan ng mga deadline para sa pagkumpleto ng isang malaking complex ng mga operasyon (mga gawa) at ang mga sandali ng simula ng lahat ng mga operasyon ng complex. Ang mga gawaing ito ay binubuo sa paghahanap ng pinakamababang tagal ng isang kumplikadong mga operasyon, ang pinakamainam na ratio ng gastos at tiyempo ng kanilang pagpapatupad.

Mga Gawain sa Pagpila nakatuon sa pag-aaral at pagsusuri ng mga sistema ng pagpila na may mga pila ng mga aplikasyon o mga kinakailangan at binubuo sa pagtukoy ng mga tagapagpahiwatig ng pagganap ng mga system, ang kanilang mga pinakamainam na katangian, halimbawa, sa pagtukoy ng bilang ng mga channel ng serbisyo, oras ng serbisyo, atbp.

Mga Gawain sa Pamamahala ng Imbentaryo binubuo sa paghahanap ng pinakamainam na halaga ng antas ng stock (muling pag-order ng punto) at laki ng order. Ang kakaiba ng naturang mga gawain ay na sa isang pagtaas sa antas ng mga stock, sa isang banda, ang mga gastos ng kanilang imbakan ay tumaas, ngunit sa kabilang banda, ang mga pagkalugi dahil sa isang posibleng kakulangan ng stock na produkto ay bumaba.

Mga Gawain sa Paglalaan ng Mapagkukunan bumangon sa isang tiyak na hanay ng mga operasyon (mga gawa) na dapat isagawa na may limitadong magagamit na mga mapagkukunan, at ito ay kinakailangan upang mahanap ang pinakamainam na pamamahagi ng mga mapagkukunan sa pagitan ng mga operasyon o ang komposisyon ng mga operasyon.

Mga gawain sa pagkumpuni at pagpapalit ng kagamitan may kaugnayan dahil sa pagkasira ng kagamitan at ang pangangailangang palitan ito sa paglipas ng panahon. Ang mga gawain ay nabawasan sa pagtukoy ng pinakamainam na timing, ang bilang ng mga preventive repair at check, pati na rin ang mga sandali ng pagpapalit ng kagamitan sa mga modernized.

Pag-iiskedyul (pag-iskedyul) ng mga gawain binubuo sa pagtukoy ng pinakamainam na pagkakasunud-sunod ng mga operasyon (halimbawa, mga bahagi ng pagproseso) sa iba't ibang uri ng kagamitan.

Mga gawain sa pagpaplano at paglalagay nia binubuo sa pagtukoy ng pinakamainam na bilang at lokasyon ng mga bagong bagay, na isinasaalang-alang ang kanilang pakikipag-ugnayan sa mga umiiral na bagay at sa kanilang sarili.

Mga gawain sa pagpili ng ruta, o network mga gawain na madalas na nakatagpo sa pag-aaral ng iba't ibang mga gawain sa transportasyon at sa sistema ng komunikasyon at binubuo sa pagtukoy ng mga pinaka-matipid na ruta.

2. Ang pangkalahatang gawain ng isang linear na programa. Pinakamainam na solusyon

Modelong pang-ekonomiya at matematika

Ang LP ay isang lugar ng matematika na bubuo ng teorya at numerical na pamamaraan para sa paglutas ng mga problema sa paghahanap ng extremum (maximum o minimum) ng isang linear na function ng maraming variable sa pagkakaroon ng linear constraints, i.e., pagkakapantay-pantay o hindi pagkakapantay-pantay na nagkokonekta sa mga variable na ito.

Ang mga pamamaraan ng LP ay inilalapat sa mga praktikal na problema kung saan: 1) kinakailangang piliin ang pinakamahusay na solusyon (pinakamainam na plano) mula sa isang hanay ng mga posibleng; 2) ang solusyon ay maaaring ipahayag bilang isang hanay ng mga halaga ng ilang magnitude na mga variable; a) ang mga paghihigpit na ipinataw sa mga magagawang solusyon ng mga tiyak na kondisyon ng problema ay nabuo sa anyo ng mga linear na equation o hindi pagkakapantay-pantay; 4) ang layunin ay ipinahayag bilang isang linear function ng mga pangunahing variable. Ang mga halaga ng layunin ng pag-andar, na nagbibigay-daan sa iyo upang ihambing ang iba't ibang mga solusyon, nagsisilbing isang pamantayan para sa kalidad ng solusyon.

Para sa isang praktikal na solusyon ng isang problemang pang-ekonomiya sa pamamagitan ng mga pamamaraan ng matematika, una sa lahat, dapat itong isulat gamit ang isang modelong pang-ekonomiya-matematika. Economic-mathematical model - isang mathematical na paglalarawan ng sinisiyasat na proseso o bagay sa ekonomiya. Ang modelong ito ay nagpapahayag ng mga pattern ng prosesong pang-ekonomiya sa isang abstract na anyo gamit ang mga mathematical na relasyon.

Pangkalahatang pamamaraan ng pagbuo ng modelo: I

1) ang pagpili ng isang tiyak na bilang ng mga variable, ang pagtatalaga - mga numerong halaga kung saan natatanging tinutukoy ang isa sa mga posibleng estado ng kababalaghan sa ilalim ng pag-aaral;

2) ang pagpapahayag ng mga relasyon na likas sa hindi pangkaraniwang bagay na pinag-aaralan, sa anyo ng mga relasyon sa matematika (mga equation, hindi pagkakapantay-pantay). Ang mga relasyong ito ay bumubuo ng isang sistema ng mga hadlang sa problema;

3) quantitative expression ng napiling criterion ng optimality sa anyo ng isang layunin na function; ako

4) mathematical formulation ng problema bilang isang problema sa paghahanap ng extremum ng layunin function, napapailalim sa mga hadlang na ipinataw sa mga variable.

Pangkalahatang problema ng linear programming mukhang:

Dahil sa isang sistema ng m linear equation at hindi pagkakapantay-pantay na may n variable

at linear function

Kinakailangang maghanap ng ganoong solusyon sa system X=(x1,x2,…,xj,…,xn), kung saan ang linear function na F ay tumatagal ng pinakamainam (i.e. maximum o minimum) na halaga.

Ang system (1) ay tinatawag na constraint system, at ang function F ay tinatawag na linear function, linear form, objective function, o objective function.

Sa madaling sabi, ang pangkalahatang problema sa linear programming ay maaaring katawanin bilang:

na may mga paghihigpit:

Pinakamainam na solusyon (o pinakamainam na plano) Ang problema sa LP ay isang solusyon X=(x1,x2,…,xj,…,xn), ng constraint system (1), na nakakatugon sa kondisyon (3), kung saan ang linear function (2) ay tumatagal ng pinakamainam (maximum o pinakamababa) na halaga.

Sa kondisyon na ang lahat ng mga variable ay hindi negatibo, ang sistema ng mga hadlang (1) ay binubuo lamang ng mga hindi pagkakapantay-pantay - ang naturang problema sa linear programming ay tinatawag na standard (symmetric); kung ang sistema ng mga hadlang ay binubuo lamang ng mga equation, kung gayon ang problema ay tinatawag na canonical.

Ang isang espesyal na kaso ng canonical na problema ay ang problema sa pangunahing anyo, na naiiba sa lahat ng mga coefficient ng constraint vector b ay di-negatibo, at sa bawat equation ay mayroong variable na may coefficient na 1, na hindi kasama sa alinman sa iba pang mga equation. Ang isang variable na may ganitong katangian ay tinatawag na isang base variable.

Ang pamantayan at kanonikal na mga problema ay mga espesyal na kaso ng pangkalahatan. Ang bawat isa sa kanila ay ginagamit sa partikular na lugar nito. Higit pa rito, ang lahat ng tatlong pormulasyon ay katumbas ng isa't isa: anumang linear programming na problema ay maaaring bawasan sa isang kanonikal, pamantayan, o pangkalahatang problema gamit ang mga simpleng pagbabagong matematikal.

4 . Mga elemento ng linear algebra

Ang sistema ng m linear equation na may n variable ay may anyo

o sa madaling salita

Anumang m variable ng isang sistema ng m linear equation na may n variable (m< n) называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Такой определитель часто называют базисным минором матрицы А. Тогда остальные m–n переменных называются неосновными (или свободными).

Upang malutas ang sistema (2.1) sa ilalim ng kondisyon m< n сформулируем утверждение.

Pahayag 2.1. Kung para sa sistemamlinear equation na maynmga variable (m < n) ang ranggo ng matrix ng mga coefficient para sa mga variable ay katumbas ng m, i.e. mayroong hindi bababa sa isang pangkat ng mga pangunahing variable, kung gayon ang sistemang ito ay hindi tiyak, at ang bawat arbitrary na hanay ng mga halaga ng mga hindi pangunahing variable ay tumutugma sa isang solusyon ng system.

Solusyon Ang X=(x1,x2,…,xn) ng system (2.1) ay tinatawag na tinatanggap kung naglalaman lamang ito ng mga di-negatibong bahagi, i.e. xj>=0 para sa anumang j=1,n. Kung hindi, ang solusyon ay tinatawag na hindi wasto.

Kabilang sa walang katapusang hanay ng mga solusyon ng system, ang tinatawag na mga pangunahing solusyon ay nakikilala.

Pangunahing solusyon ang isang sistema ng m linear equation na may n variable ay tinatawag na solusyon kung saan ang lahat ng n–m non-basic na variable ay katumbas ng zero.

Sa mga problema sa linear programming, ang mga tinatanggap na pangunahing solusyon, o, kung tawagin din, mga plano ng suporta, ay partikular na interes. Ang isang pangunahing solusyon kung saan ang hindi bababa sa isa sa mga pangunahing variable ay katumbas ng zero ay tinatawag na degenerate.

Mga convex na hanay ng mga puntos

Ang pangkalahatang pagtukoy ng ari-arian na nakikilala ang isang matambok na polygon mula sa isang hindi matambok ay kung kukuha ka ng alinman sa dalawa sa mga punto nito at ikinonekta ang mga ito sa isang segment, ang buong segment ay magiging kabilang sa polygon na ito. Maaaring kunin ang property na ito bilang kahulugan ng isang convex set ng mga puntos.

Ang hanay ng mga punto ay tinatawag na convex, kung ito, kasama ng alinman sa dalawa sa mga punto nito, ay naglalaman ng buong segment na nagkokonekta sa mga puntong ito.

Ang mga convex set ay may mahalagang ari-arian: ang intersection (karaniwang bahagi) ng anumang bilang ng convex set ay isang convex set.

Kabilang sa mga punto ng isang convex set, maaaring isa-isa ng isa ang panloob, hangganan, at mga sulok na punto.

Ang punto ng set ay tinatawag na panloob, kung ang ilan sa mga kapitbahayan nito ay naglalaman lamang ng mga punto ng set na ito.

Ang punto ng set ay tinatawag na hangganan, kung alinman sa mga kapitbahayan nito ay naglalaman ng parehong mga punto na kabilang sa ibinigay na hanay at mga puntong hindi kabilang dito.

Ang partikular na interes sa mga problema sa linear programming ay mga punto ng sulok. Ang punto ng set ay tinatawag angular(o matinding) kung hindi ito panloob para sa anumang segment na ganap na kabilang sa ibinigay na hanay.

Sa fig. Ang 2.4 ay nagpapakita ng mga halimbawa ng iba't ibang mga punto ng polygon: panloob (punto M), hangganan (punto N) at sulok (punto A, B, C, D, E). Ang point A ay angular, dahil para sa anumang segment na ganap na kabilang sa polygon, halimbawa, segment AP, hindi ito panloob; Ang punto A ay panloob sa segment na KL, ngunit ang segment na ito ay hindi ganap na kabilang sa polygon.

Para sa isang convex set, ang mga corner point ay palaging nag-tutugma sa mga vertices ng polygon (polyhedron), habang ito ay hindi kinakailangan para sa isang non-convex set. Ang isang hanay ng mga punto ay tinatawag na sarado kung kasama nito ang lahat ng mga hangganang punto nito. Ang hanay ng mga puntos ay tinatawag limitado, kung mayroong isang bola (bilog) ng radius na may hangganan ang haba na nakasentro sa anumang punto ng set na ganap na naglalaman ng ibinigay na set; kung hindi, ang hanay ay tinatawag na walang hangganan.

Ang isang matambok na saradong hanay ng mga punto sa isang eroplano na may hangganan na bilang ng mga punto ng sulok ay tinatawag na isang convex polygon kung ito ay may hangganan, at isang matambok na polygonal na rehiyon kung ito ay walang hangganan.

Geometric na kahulugan ng mga solusyon ng hindi pagkakapantay-pantay, mga equation at kanilang mga sistema

Isaalang-alang natin ang mga solusyon sa hindi pagkakapantay-pantay.

Pahayag 1. Ang hanay ng mga solusyon sa hindi pagkakapantay-pantay na may dalawang variable a11x1+a12x2<=b1 является одной из двух полуплоскостей, на которые вся плоскость делится прямой a11x1+a12x2=b1 , включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравен­ства a11x1+a12x2>=b1.

Upang matukoy ang nais na kalahating eroplano (itaas o mas mababa), inirerekumenda na magtakda ng isang di-makatwirang punto ng kontrol na hindi namamalagi sa hangganan nito - ang itinayo na linya. Kung ang hindi pagkakapantay-pantay ay nasiyahan sa isang control point, kung gayon ito ay nasiyahan din sa lahat ng mga punto ng kalahating eroplano na naglalaman ng control point, at hindi nasiyahan sa lahat ng mga punto ng isa pang kalahating eroplano. At kabaligtaran, kung ang hindi pagkakapantay-pantay ay hindi nasiyahan sa control point, hindi ito nasisiyahan sa lahat ng mga punto ng kalahating eroplano na naglalaman ng control point, at nasiyahan sa lahat ng mga punto ng isa pang kalahating eroplano. Bilang isang control point, ito ay maginhawa upang kunin ang pinagmulan ng mga coordinate O (0; 0), na hindi namamalagi sa itinayong linya.

Isaalang-alang ang hanay ng mga solusyon sa mga sistema ng hindi pagkakapantay-pantay.

Assertion 2. Ang hanay ng mga solusyon ng isang katugmang sistema m ng mga linear na hindi pagkakapantay-pantay sa dalawang variable ay isang convex polygon (o isang convex polygonal na rehiyon).

Ang bawat isa sa mga hindi pagkakapantay-pantay, alinsunod sa Pahayag 1, ay tumutukoy sa isa sa mga kalahating eroplano, na isang matambok na hanay ng mga puntos. Ang hanay ng mga solusyon ng magkasanib na sistema ng mga linear na hindi pagkakapantay-pantay ay mga punto na kabilang sa kalahating eroplano ng mga solusyon ng lahat ng hindi pagkakapantay-pantay, i.e. nabibilang sa kanilang intersection. Ayon sa pahayag tungkol sa intersection ng convex set, ang set na ito ay convex at naglalaman ng isang may hangganang bilang ng mga corner point, i.e. ay isang convex polygon (isang convex polygonal area).

Ang mga coordinate ng mga punto ng sulok - ang mga vertices ng polygon ay matatagpuan bilang mga coordinate ng mga intersection point ng mga kaukulang linya.

Kapag nagtatayo ng mga lugar ng mga solusyon para sa mga sistema ng hindi pagkakapantay-pantay, ang iba pang mga kaso ay maaaring mangyari din: ang hanay ng mga solusyon ay isang matambok na polygonal na rehiyon (Larawan 2.9, a); isang punto (Larawan 2.9, b); isang walang laman na hanay kapag ang sistema ng mga hindi pagkakapantay-pantay ay hindi pare-pareho (Larawan 2.9, c).

5 . Geometric na pamamaraan para sa paglutas ng mga problema sa LP

pinakamainam na solusyon sa problema sa LP

Teorama 1. Kung ang problema sa LP ay may pinakamainam na solusyon, kung gayon ang linear function ay tumatagal sa isang maximum na halaga sa isa sa mga sulok na punto ng solusyon polyhedron. Kung ang isang linear na function ay tumatagal ng isang maximum na halaga sa higit sa isang sulok na punto, pagkatapos ay tumatagal ito sa anumang punto na isang convex linear na kumbinasyon ng mga puntong iyon.

Ang teorama ay nagpapahiwatig ng pangunahing paraan ng paglutas ng mga problema sa LP. Sa katunayan, ayon sa teorama na ito, sa halip na pag-aralan ang isang walang katapusang hanay ng mga magagawang solusyon, upang mahanap ang nais na pinakamainam na solusyon sa kanila, kinakailangan na pag-aralan lamang ang isang may hangganang bilang ng mga punto ng sulok ng solusyon na polyhedron.

Ang sumusunod na theorem ay nakatuon sa analytical na pamamaraan para sa paghahanap ng mga punto ng sulok.

Teorama 2. Ang bawat tinatanggap na pangunahing solusyon ng problema sa LP ay tumutugma sa isang sulok na punto ng solusyon na polyhedron, at sa kabaligtaran, sa bawat sulok na punto ng solusyon na polyhedron ay tumutugma sa isang tinatanggap na pangunahing solusyon.

Isang mahalagang corollary kaagad ang sumusunod mula sa Theorems 1 at 2: kung ang isang problema sa LP ay may pinakamainam na solusyon, kung gayon ito ay kasabay ng hindi bababa sa isa sa mga tinatanggap na pangunahing solusyon nito.

Kaya, ang pinakamabuting kalagayan ng linear function ng problema sa LP ay dapat na hanapin sa isang may hangganang bilang ng mga tinatanggap na pangunahing solusyon nito.

Kaya, ang hanay ng mga tinatanggap na solusyon (solusyon polyhedron) ng problema sa LP ay isang convex polyhedron (o convex polyhedral region), at ang pinakamainam na solusyon ng problema ay matatagpuan hindi bababa sa isa sa mga sulok na punto ng solusyon polyhedron.

Isaalang-alang ang isang problema sa karaniwang anyo na may dalawang variable (P = 2).

Hayaang maging polygon ang geometric na representasyon ng constraint system ABCDE(Larawan 4.1). Kinakailangang hanapin sa mga punto ng polygon na ito ang isang punto kung saan kinukuha ng linear function na F=c1x1+c2x2 ang maximum (o minimum) na halaga.

Isaalang-alang ang tinatawag na linya ng antas linear function F, ibig sabihin. linya kung saan ang function na ito ay tumatagal ng parehong nakapirming halaga A, ibig sabihin. F = A, o c1x1+c2x2=a.

Sa polygon ng solusyon, hanapin ang punto kung saan dumadaan ang linya ng antas ng function F na may pinakamalaking (kung ang linear function ay pinalaki) o pinakamaliit (kung ito ay pinaliit) na antas.

Ang equation ng level line ng function na c1x1+c2x2=a ay ang equation ng isang tuwid na linya. Sa iba't ibang antas A ang mga linya ng antas ay magkatulad, dahil ang kanilang mga slope ay tinutukoy lamang ng ratio sa pagitan ng mga coefficient c1 at c2 at, samakatuwid, ay pantay. Kaya ang mga linya ng antas ng tampok F – ito ay mga kakaibang "parallel", kadalasang matatagpuan sa isang anggulo sa mga coordinate axes.

Ang isang mahalagang katangian ng linya ng antas ng isang linear na function ay na sa isang parallel shift ng linya sa isang direksyon, ang antas ay tumataas lamang, at sa isang shift sa kabilang direksyon, ito ay bumababa lamang. Ang vector c=(c1,c2) ​​​​nagsisimula sa pinanggalingan ay nagpapahiwatig ng direksyon ng pinakamabilis na pagtaas ng function F. Ang level line ng linear function ay patayo sa vector c=(c1,c2).

Ang pagkakasunud-sunod ng graphical na solusyon ng problema sa LP:

1. Bumuo ng polygon na solusyon.

2. Bumuo ng vector c = (c1, c2), at gumuhit ng linya ng antas ng linear function para dito F, halimbawa, F=0.

3. Parallel displacement ng tuwid na linya F=0 sa direksyon ng vector c(-c) para mahanap ang point Amax(Bmin), kung saan naabot ng F ang maximum (minimum).

1. Sama-samang paglutas ng mga equation ng mga linyang nagsasalubong sa pinakamainam na punto, hanapin ang mga coordinate nito.

2. Kalkulahin ang Fmax(Fmin).

Magkomento. Ang pinakamababang punto ay ang "entry" point sa decision polygon, at ang pinakamataas na point ay ang "exit" point mula sa polygon.

6. Pangkalahatang ideya ng simplex na pamamaraan. Geometric na interpretasyon

Ang graphical na paraan ay naaangkop sa isang napakakitid na klase ng mga problema sa linear programming: epektibo nitong malulutas ang mga problemang naglalaman ng hindi hihigit sa dalawang variable. Ang mga pangunahing theorems ng linear programming ay isinasaalang-alang, mula sa kung saan ito ay sumusunod na kung ang isang linear na problema sa programming ay may pinakamainam na solusyon, kung gayon ito ay tumutugma sa hindi bababa sa isang sulok na punto ng solusyon polyhedron at nag-tutugma sa hindi bababa sa isa sa mga tinatanggap na pangunahing solusyon ng sistema ng pagpilit. Ang isang paraan upang malutas ang anumang problema sa linear programming ay ipinahiwatig: upang magbilang ng isang tiyak na bilang ng mga magagawa na pangunahing solusyon ng sistema ng mga hadlang at piliin sa kanila ang isa kung saan ang layunin ng pag-andar ay gumagawa ng pinakamainam na desisyon. Geometrically, ito ay tumutugma sa enumeration ng lahat ng mga punto ng sulok ng solusyon polyhedron. Ang ganitong enumeration ay hahantong sa isang pinakamainam na solusyon (kung mayroon man), ngunit ang praktikal na pagpapatupad nito ay nauugnay sa napakalaking kahirapan, dahil para sa mga tunay na problema ang bilang ng mga magagawa na pangunahing solusyon, kahit na may hangganan, ay maaaring maging napakalaki.

Ang bilang ng mga tinatanggap na pangunahing mga solusyon na isasaalang-alang ay maaaring mabawasan kung ang pagbilang ay isinasagawa nang hindi sapalaran, ngunit isinasaalang-alang ang mga pagbabago sa linear function, i.e. naghahanap upang matiyak na ang bawat susunod na solusyon ay "mas mahusay" (o hindi bababa sa "hindi mas masahol pa") kaysa sa nauna sa mga tuntunin ng mga halaga ng linear function (pagtaas nito kapag hinahanap ang maximum, binabawasan ito kapag hinahanap ang minimum) . Ang ganitong enumeration ay nagpapahintulot sa isa na bawasan ang bilang ng mga hakbang sa paghahanap ng pinakamabuting kalagayan. Ipaliwanag natin ito gamit ang isang graphical na halimbawa.

Hayaang ang lugar ng mga magagawang solusyon ay kinakatawan ng isang polygon ABCDE. Ipagpalagay na ang punto ng sulok nito A tumutugma sa orihinal na tinatanggap na pangunahing solusyon. Ang isang random na enumeration ay kailangang subukan ang limang magagawa na pangunahing solusyon na naaayon sa limang sulok na punto ng polygon. Gayunpaman, ang pagguhit ay nagpapakita na pagkatapos ng tuktok A kapaki-pakinabang na pumunta sa susunod na tuktok SA, at pagkatapos ay sa pinakamainam na punto SA. Sa halip na lima, tatlong vertice lang ang binagtas, na patuloy na pinapabuti ang linear function.

Ang ideya ng sunud-sunod na pagpapabuti ng solusyon ay nabuo ang batayan ng isang unibersal na pamamaraan para sa paglutas ng mga problema sa linear programming - simplex na paraan o paraan ng sunud-sunod na pagpapabuti ng plano.

Ang geometric na kahulugan ng simplex na pamamaraan ay binubuo sa isang sequential transition mula sa isang vertex ng constraint polyhedron (tinatawag na paunang isa) sa kalapit na isa, kung saan ang linear function ay tumatagal ng pinakamahusay (hindi bababa sa hindi ang pinakamasama) na halaga na may kaugnayan sa layunin ng problema; hanggang sa matagpuan ang pinakamainam na solusyon - ang vertex kung saan naabot ang pinakamainam na halaga ng function ng layunin (kung ang problema ay may hangganan na pinakamabuting kalagayan).

Ang simplex method ay unang iminungkahi ng American scientist na si J. Danzig noong 1949, ngunit noong 1939 pa, ang mga ideya ng pamamaraan ay binuo ng Russian scientist na si L.V. Kantorovich.

Ang simplex na paraan, na nagbibigay-daan sa paglutas ng anumang problema sa linear programming, ay unibersal. Sa kasalukuyan, ito ay ginagamit para sa mga kalkulasyon ng computer, ngunit ang mga simpleng halimbawa gamit ang simplex na paraan ay maaari ding lutasin nang manu-mano.

Upang ipatupad ang simplex na paraan - sunud-sunod na pagpapabuti ng solusyon - ito ay kinakailangan upang makabisado tatlong pangunahing elemento:

isang paraan para sa pagtukoy ng anumang 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.

Upang magamit ang simplex na paraan, ang problema sa linear programming ay dapat na bawasan sa canonical form, i.e. ang sistema ng mga hadlang ay dapat ipakita sa anyo ng mga equation.

Ang panitikan ay naglalarawan sa sapat na detalye: paghahanap ng paunang plano ng sanggunian (inisyal na magagawa na pangunahing solusyon), gamit din ang paraan ng artipisyal na batayan, paghahanap ng pinakamainam na plano ng sanggunian, paglutas ng mga problema gamit ang mga simplex na talahanayan.

7 . Algorithm ng simplex na pamamaraan.

Isaalang-alang natin ang solusyon ng LLP sa pamamagitan ng simplex na pamamaraan at ipakita ito kaugnay ng problema sa pag-maximize.

1. Ayon sa kondisyon ng problema, ang modelo ng matematika nito ay pinagsama-sama.

2. Ang itinayong modelo ay na-convert sa canonical form. Sa kasong ito, ang isang batayan na may paunang plano ng sanggunian ay maaaring lumabas.

3. Ang kanonikal na modelo ng problema ay nakasulat sa anyo ng isang simplex na talahanayan upang ang lahat ng mga libreng termino ay hindi negatibo. Kung napili ang paunang reference plan, pagkatapos ay pumunta sa hakbang 5.

Simplex table: isang sistema ng mga mahigpit na equation at isang layunin na function ay ipinasok sa anyo ng mga expression na nalutas na may paggalang sa paunang batayan. Ang linya kung saan ipinasok ang mga coefficient ng layunin ng function na F ay tinatawag na F-line o ang linya ng layunin ng function.

4. Ang paunang plano ng sanggunian ay matatagpuan sa pamamagitan ng pagsasagawa ng mga pagbabagong simplex na may mga elemento ng positibong resolusyon na tumutugma sa pinakamababang mga ratio ng simplex, at hindi isinasaalang-alang ang mga palatandaan ng mga elemento ng F-row. Kung sa kurso ng mga pagbabagong-anyo mayroong isang 0-hilera, ang lahat ng mga elemento kung saan, maliban sa libreng termino, ay mga zero, kung gayon ang sistema ng mga paghihigpit na equation ng problema ay hindi naaayon. Kung mayroong isang 0-row, kung saan, maliban sa libreng termino, walang iba pang mga positibong elemento, kung gayon ang sistema ng mga paghihigpit na equation ay walang mga di-negatibong solusyon.

Ang pagbabawas ng system (2.55), (2.56) sa isang bagong batayan ay tatawagin simplex na pagbabago . Kung ang isang simplex na pagbabago ay itinuturing bilang isang pormal na algebraic na operasyon, makikita na bilang resulta ng operasyong ito, ang mga tungkulin ay muling ipinamamahagi sa pagitan ng dalawang variable na kasama sa isang tiyak na sistema ng mga linear na function: ang isang variable ay napupunta mula sa umaasa hanggang sa independyente, at ang iba pang kabaligtaran - mula sa independyente hanggang umaasa. Ang operasyong ito ay kilala sa algebra bilang Hakbang sa pag-aalis ng Jordan.

5. Ang nahanap na paunang pangunahing plano ay sinusuri para sa pinakamainam:

a) kung walang negatibong elemento sa F-row (hindi binibilang ang libreng termino), kung gayon ang plano ay pinakamainam. Kung walang mga zero, kung gayon ang pinakamainam na plano ay natatangi; kung mayroong hindi bababa sa isang zero, pagkatapos ay mayroong isang walang katapusang bilang ng mga pinakamainam na plano;

b) kung mayroong hindi bababa sa isang negatibong elemento sa F-row, na tumutugma sa isang haligi ng mga hindi positibong elemento, kung gayon;

c) kung mayroong hindi bababa sa isang negatibong elemento sa F-row, at hindi bababa sa isang positibong elemento sa column nito, maaari tayong lumipat sa isang bagong reference na plano na mas malapit sa pinakamainam. Upang gawin ito, ang tinukoy na hanay ay dapat na italaga bilang paglutas, sa pamamagitan ng pinakamababang ratio ng simplex, hanapin ang hilera ng paglutas at magsagawa ng pagbabagong simplex. Ang nakuhang pangunahing plano ay muling susuriin para sa pinakamainam. Ang inilarawang proseso ay paulit-ulit hanggang sa makuha ang pinakamainam na plano o hanggang sa ang problema ay hindi malulutas.

Ang hanay ng mga coefficient para sa isang variable na kasama sa batayan ay tinatawag na paglutas. Kaya, ang pagpili ng isang variable na ipinakilala sa batayan (o pagpili ng isang paglutas ng column) ng negatibong elemento ng F-row, tinitiyak namin na ang function F ay tumataas. .

Ang isang maliit na mas mahirap ay upang matukoy ang variable na ibubukod mula sa batayan. Upang gawin ito, binubuo nila ang mga ratio ng mga libreng miyembro sa mga positibong elemento ng column ng paglutas (ang mga ganitong relasyon ay tinatawag na simplex) at hanapin ang pinakamaliit sa kanila, na tumutukoy sa hilera (paglutas) na naglalaman ng hindi kasamang variable. Ang pagpili ng isang variable na ibubukod mula sa batayan (o ang pagpili ng isang resolving string) ayon sa pinakamababang simplex ratio ay ginagarantiyahan, gaya ng naitatag na, ang positivity ng mga batayang bahagi sa bagong reference na disenyo.

Sa hakbang 3 ng algorithm, ipinapalagay na ang lahat ng elemento ng column ng mga libreng termino ay hindi negatibo. Ang kinakailangan na ito ay hindi sapilitan, ngunit kung ito ay natutugunan, ang lahat ng kasunod na simplex na pagbabago ay isinasagawa lamang sa mga positibong elemento ng resolusyon, na maginhawa para sa mga kalkulasyon. Kung mayroong mga negatibong numero sa hanay ng mga libreng miyembro, ang elemento ng paglutas ay pipiliin tulad ng sumusunod:

1) tingnan ang linya na naaayon sa ilang negatibong libreng miyembro, halimbawa, isang t-row, at pumili ng anumang negatibong elemento sa loob nito, at ang hanay na naaayon dito ay kinuha bilang nagpapahintulot (ipagpalagay namin na ang mga hadlang ng problema ay magkatugma );

2) bumubuo ng mga ratios ng mga elemento ng column ng mga libreng miyembro sa mga kaukulang elemento ng paglutas ng column na may parehong mga palatandaan (simplex ratios);

3) piliin ang pinakamaliit sa mga ugnayang simplex. Matutukoy nito ang string ng pahintulot. Hayaan ito, halimbawa, R-linya;

4) sa intersection ng paglutas ng mga haligi at hilera, isang elemento ng paglutas ay matatagpuan. Kung ang elemento ng y-string ay lumabas na nagre-resolve, pagkatapos pagkatapos ng simplex transformation ang libreng miyembro ng string na ito ay magiging positibo. Kung hindi, sa susunod na hakbang, ang t-row ay muling tinutugunan. Kung ang problema ay malulutas, pagkatapos pagkatapos ng isang tiyak na bilang ng mga hakbang ay walang mga negatibong elemento sa hanay ng mga libreng termino.

8. Inverse matrix method

Isaalang-alang ang isang LP ng form:

Ang A ay ang constraint matrix;

C=(c1,c2,…,cn)–vector–row;

X=(x1,x2,…,xn) – mga variable;

ay ang vector ng kanang bahagi.

Ipinapalagay namin na ang lahat ng mga equation ay linearly independent, ibig sabihin, ranggo(a)=m. Sa kasong ito, ang batayan ay ang menor de edad ng pagkakasunud-sunod ng matrix A. Iyon ay, mayroong hindi bababa sa isang submatrix B ng pagkakasunod-sunod na |B|<>0. Ang lahat ng hindi alam na nauugnay sa B ay tinatawag na basic. Lahat ng iba ay libre.

Hayaan ang B na maging batayan. Pagkatapos, sa pamamagitan ng pag-permute sa mga column ng matrix A, maaaring palaging dalhin ng isa ang A sa anyo na A=(B|N),

kung saan ang N ay isang submatrix na binubuo ng mga column ng matrix A na hindi kabilang sa batayan. Sa parehong paraan, posibleng hatiin ang vector x sa – ang vector ng mga pangunahing variable at.

Ang anumang solusyon ng problema (1) ay nakakatugon sa kondisyon A*x=b, at, dahil dito, ang sistema ay kumukuha ng sumusunod na anyo:

kasi |B|<>0, pagkatapos ay mayroong isang kabaligtaran na matrix. Ang pagpaparami ng kabaligtaran sa kaliwa, nakukuha natin:

- karaniwang desisyon.

Ang pangunahing solusyon (na may paggalang sa batayan B) ay isang partikular na solusyon sa problema (2) na nakuha sa ilalim ng kundisyon. Pagkatapos ito ay natatangi na tinutukoy.

Ang pangunahing solusyon ay tinatawag mapagtanto, Kung.

Ang batayan na naaayon sa ipinatupad na pangunahing solusyon. tinawag maisasakatuparan na batayan. Ang pangunahing solusyon ay tinatawag na degenerate kung ang vector ay may zero na bahagi.

Ang pangkalahatang solusyon ay naglalaman ng lahat ng mga solusyon na umiiral. Bumalik tayo sa layunin ng function. Ipinakilala namin ang Cb-coefficients sa harap ng mga pangunahing variable, Cn-the rest.

Kaya, nakukuha namin. Pinapalitan namin mula sa pangkalahatang solusyon:

Pahayag. Optimality criterion para sa pangunahing solusyon.

Sabihin nating. Kung gayon ang pangunahing solusyon ay pinakamainam. Kung, kung gayon ang pangunahing solusyon ay hindi pinakamainam.

Doc-in: Hayaan. Isaalang-alang ang pangunahing solusyon, .

Samakatuwid, ay ang halaga ng layunin ng function para sa pangunahing solusyon.

Magkaroon ng isa pang solusyon: (Xb,Xn).

Tapos tumingin kami

Kaya, ang pangunahing solusyon ay min. Hayaan, sa kabaligtaran, huwag hawakan, i.e. umiiral.

Pagkatapos ay mayroong isang solusyon kung saan ang halaga ng layunin ng pag-andar ay magiging mas mababa kaysa sa halaga ng layunin ng pag-andar para sa pangunahing solusyon.

Ang Let ay tumutugma sa isang libreng variable na Xi:Xj, magtalaga ng isang halaga at ipakilala ito sa batayan, at kumuha ng isa pang variable at tawagin itong libre.

Paano matukoy? Ang lahat ng mga libreng variable maliban sa ay 0 pa rin.

Pagkatapos sa pangkalahatang solusyon, kung saan.

Kinukuha namin ang: - isang kinakailangang kondisyon.

Ang isang pangunahing solusyon ay tinatawag na regular kung. Nakukuha namin ang variable mula sa batayan. Sa isang bagong solusyon, bumababa ang layunin ng function, dahil

Algorithm:

1. Problema sa LP sa karaniwang anyo.

2. Iniiwan namin ang mga linearly independent equation.

3. Maghanap ng isang matrix B tulad na |B|<>0 at ang pangunahing solusyon.

Kinakalkula namin:

kung, kung gayon mayroong isang pinakamainam na solusyon - ito ang pangunahing solusyon;

kung, pagkatapos ay nakita namin ang bahagi, ilakip ito, sa gayon ay makakahanap kami ng isa pang solusyon; – kung saan ang isa sa mga pangunahing variable =0. Itapon namin ang variable na ito mula sa batayan, ipasok ang xi. Nakakuha kami ng bagong batayan B2 conjugate sa batayan B1. Pagkatapos ay kalkulahin namin muli.

1. Kung mayroong isang pinakamainam na solusyon, pagkatapos ay pagkatapos ng isang tiyak na bilang ng mga hakbang ay makukuha natin ito.

Sa geometrically, ang pamamaraan ay binibigyang kahulugan bilang isang paglipat mula sa isang sulok na punto patungo sa isang conjugate na sulok na punto sa kahabaan ng hangganan ng set X, ang hanay ng mga solusyon sa problema. kasi mayroong isang tiyak na bilang ng mga punto ng sulok at ang mahigpit na pagbaba ng function na F(x) ay nagbabawal sa pagdaan sa parehong matinding punto ng dalawang beses, kung gayon kung mayroong isang pinakamainam na solusyon, pagkatapos ay pagkatapos ng isang tiyak na bilang ng mga hakbang ay makukuha natin ito.

9. Economic interpretasyon ng problema, ang dalawahang problema ng paggamit ng mga mapagkukunan

Gawain. Para sa paggawa ng dalawang uri ng mga produkto P1 at P2, apat na uri ng mga mapagkukunan S1, S2, S3, S4 ang ginagamit. Dahil sa mga stock ng mga mapagkukunan, ang bilang ng mga yunit ng mga mapagkukunan na ginugol sa paggawa ng isang yunit ng output. Alam ang tubo na natanggap mula sa isang yunit ng produksyon na P1 at P2. Kinakailangan na gumuhit ng isang plano para sa paggawa ng mga produkto kung saan ang kita mula sa pagbebenta nito ay magiging maximum.

Gawainako(orihinal):

F=c1x1+c2x2+…+CnXn->max na may mga paghihigpit:

at ang kundisyong hindi negatibo x1>=0, x2>=0,…,Xn>=0

Bumuo ng naturang plano sa produksyon X=(x1,x2,…,Xn), kung saan ang tubo (kita) mula sa pagbebenta ng mga produkto ay magiging maximum, sa kondisyon na ang pagkonsumo ng mga mapagkukunan para sa bawat uri ng produkto ay hindi lalampas sa magagamit mga stock

GawainII(dalawahan)

Z=b1y1+b2y2+…+BmYm->min

na may mga paghihigpit:

at ang kondisyong hindi negatibo

y1>=0, y2>=0,…,yn>=0.

Maghanap ng isang hanay ng mga presyo (mga pagtatantya) ng mga mapagkukunan Y=(y1,y2,…,yn), kung saan ang kabuuang halaga ng mga mapagkukunan ay magiging minimal, sa kondisyon na ang halaga ng mga mapagkukunan sa produksyon ng bawat uri ng produkto ay magiging hindi bababa sa tubo (kita) mula sa pagbebenta ng mga produktong ito

Sa modelo sa itaas, ang bi(i=1,2,…,m) ay tumutukoy sa stock ng mapagkukunang Si; aij- ang bilang ng mga resource unit na nakonsumo ng Si sa produksyon ng isang yunit ng produksyon Pj(j=1,2,…,n); cj- tubo (kita) mula sa pagbebenta ng isang yunit ng produksyon Pj (o ang presyo ng produksyon Pj) .

Ipagpalagay natin na nagpasya ang ilang organisasyon na bumili ng mga mapagkukunan ng enterprise S1,S2,…,Sm at kinakailangang magtakda ng pinakamainam na presyo para sa mga mapagkukunang ito y1,y2,…,ym. Malinaw na ang organisasyon ng pagbili ay interesado sa katotohanan na ang mga gastos ng lahat ng mga mapagkukunan Z sa dami b1,b2,…,bm sa mga presyong y1,y2,…,ym, ayon sa pagkakabanggit, ay minimal, ibig sabihin. Z=b1,y1+b2y2+…+bmym->min.

Sa kabilang banda, ang isang negosyo na nagbebenta ng mga mapagkukunan ay interesado sa katotohanan na ang natanggap na kita ay hindi bababa sa halaga na maaaring matanggap ng negosyo kapag nagpoproseso ng mga mapagkukunan sa mga natapos na produkto.

A11 units ng resource S1, a21 units ng resource S2,…., aj1 units ng resource Si1 ,……, am1 units ng resource Sm ay ginugugol sa produksyon ng unit ng produkto P1 sa presyong y1,y1,…,yi ,…,ym, ayon sa pagkakabanggit. Samakatuwid, upang matugunan ang mga kinakailangan ng nagbebenta, ang halaga ng mga mapagkukunan na natupok sa paggawa ng isang yunit ng produksyon na P1 ay dapat na hindi bababa sa presyo nito c1, i.e. a11y1+a21y2+…+am1ym>=c1.

Katulad nito, posibleng bumuo ng mga hadlang sa anyo ng mga hindi pagkakapantay-pantay para sa bawat uri ng produkto P1,P2,…Pn. Ang modelong ekonomiko-matematika at makabuluhang interpretasyon ng nakuhang dalawahang suliranin II ay ibinibigay sa kanang bahagi ng talahanayan.

Ang mga presyo ng mapagkukunan y1,y1,…,yi,…,ym ay nakatanggap ng iba't ibang pangalan sa economic literature: accounting, implicit, anino . Ang kahulugan ng mga pangalang ito ay iyon may kondisyon , "pekeng" presyo. Sa kaibahan sa "panlabas" na mga presyo c1,c2,…,cn para sa mga produkto, na kilala, bilang panuntunan, bago magsimula ang produksyon, ang mga presyo ng mga mapagkukunan y1,y2,…,ym ay panloob , dahil hindi sila nakatakda mula sa labas, ngunit direktang tinutukoy bilang isang resulta ng paglutas ng problema, kaya madalas silang tinatawag mga pagtatantya mapagkukunan.

10. Parehong dalawahang problema sa LP at ang kanilang mga katangian

Pormal nating isaalang-alang ang dalawang problema I at II ng linear programming na ipinakita sa talahanayan, na nag-abstract mula sa makabuluhang interpretasyon ng mga parameter na kasama sa kanilang mga modelong pang-ekonomiya at matematika.

Ang parehong mga gawain ay may mga sumusunod ari-arian:

1. Sa isang problema, hinahanap nila ang maximum ng isang linear function, sa isa pa - isang minimum.

2. Ang mga coefficient para sa mga variable sa isang linear function ng isang problema ay mga libreng miyembro ng sistema ng mga hadlang sa isa pa.

3. Ang bawat isa sa mga problema ay ibinibigay sa karaniwang anyo, at sa problema sa pag-maximize ang lahat ng hindi pagkakapantay-pantay ng anyo "<=", а в задаче минимизации – все неравенства вида ">=".

4. Ang mga matrice ng mga coefficient para sa mga variable sa mga sistema ng mga hadlang ng parehong mga problema ay inilipat sa isa't isa.

5. Ang bilang ng mga hindi pagkakapantay-pantay sa sistema ng mga hadlang ng isang problema ay kapareho ng bilang ng mga variable sa isa pang problema.

6. Ang mga kondisyon ng di-negatibiti ng mga variable ay napanatili sa parehong mga problema.

Magkomento. Kung ang kundisyong hindi negatibo ay ipinataw sa j-th variable ng orihinal na problema, kung gayon ang j-th constraint ng dual problem ay magiging isang hindi pagkakapantay-pantay, ngunit kung ang j-th variable ay maaaring tumagal ng parehong positibo at negatibong mga halaga, kung gayon ang j-th constraint ng dual problem ay isang equation; ang mga hadlang ng orihinal na problema at ang mga variable ng dalawahang problema ay magkatulad na magkakaugnay.

Dalawang problema I at II ng linear programming na may ipinahiwatig na mga katangian ay tinatawag na simetriko kapwa dalawahang problema. Sa mga sumusunod, para sa pagiging simple, tatawagin lang natin sila dalawahang gawain.

Ang bawat problema sa LP ay maaaring iugnay sa dalawahang problema nito.

11. Algorithm para sa pag-compile ng dalawahang problema:

1. Dalhin ang lahat ng hindi pagkakapantay-pantay ng constraint system ng orihinal na problema sa parehong kahulugan: kung ang maximum ng isang linear function ay hinahangad sa orihinal na problema, kung gayon ang lahat ng hindi pagkakapantay-pantay ng constraint system ay nabawasan sa anyo "<=", а если минимум – к виду ">=". Para sa mga hindi pagkakapantay-pantay kung saan hindi natutugunan ang pangangailangang ito, i-multiply sa -1.

2. Mag-compile ng isang augmented matrix ng system A, na kinabibilangan ng isang matrix ng coefficients para sa mga variable, isang column ng mga libreng miyembro ng system of restrictions at isang row ng coefficients para sa mga variable sa isang linear function.

3. Hanapin ang matrix na inilipat sa matrix A .

4. Bumuo ng dalawahang problema batay sa resultang matrix at ang mga kondisyon para sa di-negatibiti ng mga variable: bumubuo sa layunin ng pag-andar ng dalawahang problema, na isinasaalang-alang bilang mga koepisyent ng mga variable ang mga libreng miyembro ng sistema ng mga hadlang ng orihinal na problema; bumuo ng isang sistema ng mga hadlang para sa dalawahang problema, ang pagkuha ng mga elemento ng matrix bilang mga coefficient ng mga variable, at ang mga coefficient ng mga variable sa layunin ng pag-andar ng orihinal na problema bilang mga libreng miyembro, at isulat ang mga hindi pagkakapantay-pantay ng kabaligtaran na kahulugan; isulat ang kondisyon ng di-negatibiti ng mga variable ng dual problem.

12. Unang duality theorem

Ang koneksyon sa pagitan ng pinakamainam na solusyon ng dalawahang problema ay itinatag sa tulong ng mga duality theorems.

Isang sapat na tanda ng pagiging mahusay.

Kung X*=(x1*,x2*,…,xn*) At Y*=(y1*,y2*,…,ym*) ay mga tinatanggap na solusyon ng magkabilang dalawahang problema kung saan ang pagkakapantay-pantay ay pinanghahawakan,

pagkatapos ay ang pinakamainam na solusyon ng orihinal na problema I, at ang pinakamainam na solusyon ng dalawahang problema II.

Bilang karagdagan sa isang sapat na pamantayan para sa pinakamainam ng magkabilang dalawahang problema, may iba pang mahahalagang relasyon sa pagitan ng kanilang mga solusyon. Una sa lahat, bumangon ang mga tanong: palaging may sabay-sabay na pinakamainam na solusyon para sa bawat pares ng dalawahang problema; posible bang may solusyon ang isa sa dalawahang problema at ang isa ay wala. Ang mga tanong na ito ay sinasagot ng sumusunod na teorama.

Ang unang (pangunahing) duality theorem. Kung ang isa sa magkabilang dalawahang problema ay may pinakamainam na solusyon, gayon din ang isa, at ang pinakamainam na halaga ng kanilang mga linear na pag-andar ay:

Fmax = Zmin o F(X*)=Z(Y*) .

Kung ang linear function ng isa sa mga problema ay hindi limitado, kung gayon ang mga kondisyon ng iba pang problema ay magkasalungat (ang problema ay walang solusyon).

Magkomento. Ang pahayag na kabaligtaran sa ikalawang bahagi ng pangunahing duality theorem ay hindi totoo sa pangkalahatang kaso, i.e. mula sa katotohanan na ang mga kondisyon ng orihinal na problema ay magkasalungat, hindi ito sumusunod na ang linear na pag-andar ng dalawahang problema ay hindi limitado.

Pang-ekonomiyang kahulugan ng unang duality theorem.

Plano ng produksyon X*=(x1*,x2*,…,xn*) at isang hanay ng mga presyo (mga pagtatantya) ng mga mapagkukunan Y*=(y1*,y2*,…,ym*) magiging pinakamainam kung at kung ang tubo (kita) mula sa produkto, na matatagpuan sa "panlabas" (kilala nang maaga) na mga presyo c1,c2,...,cn, ay katumbas ng halaga ng mga mapagkukunan sa "panloob" (natukoy mula lamang sa solusyon ng problema) mga presyo y1 ,y2,…,ym. Para sa lahat ng iba pang mga plano X At Y parehong mga gawain, ang tubo (kita) mula sa produkto ay palaging mas mababa sa (o katumbas ng) halaga ng mga mapagkukunan.

Ang pang-ekonomiyang kahulugan ng unang duality theorem ay maaari ding bigyang-kahulugan bilang mga sumusunod: ang negosyo ay walang pakialam kung gumawa ng mga produkto ayon sa pinakamainam na plano X*=(x1*,x2*,…,xn*) at makuha ang pinakamataas na tubo ( kita) Fmax o magbenta ng mga mapagkukunan sa pinakamainam na presyo Y* =(y1*,y2*,…,ym*) at ibalik mula sa pagbebenta na katumbas nito ang pinakamababang halaga ng mga mapagkukunan Zmin.

13. Pangalawang duality theorem

Hayaang ibigay ang dalawang magkabilang problema. Kung ang bawat isa sa mga problemang ito ay nalutas sa pamamagitan ng simplex na pamamaraan, kung gayon kinakailangan na bawasan ang mga ito sa isang kanonikal na anyo, kung saan kinakailangan na ipakilala sa sistema ng mga hadlang ng problema I (sa maikling notasyon) T di-negatibong mga variable, ngunit sa sistema ng mga hadlang ng problema II () – n mga di-negatibong variable, kung saan ang i(j) ay ang bilang ng hindi pagkakapantay-pantay kung saan ipinakilala ang karagdagang variable.

Ang mga sistema ng mga hadlang para sa bawat isa sa magkabilang dalawahang problema ay kukuha ng anyo:

Magtatag tayo ng isang pagsusulatan sa pagitan ng mga unang variable ng isa sa dalawahang problema at ng mga karagdagang variable ng isa pang problema (talahanayan).

Teorama. Ang mga positibong (nonzero) na bahagi ng pinakamainam na solusyon ng isa sa magkabilang dalawahang problema ay tumutugma sa zero na bahagi ng pinakamainam na solusyon ng iba pang problema, i.e. para sa anumang i=1,2,…,m u j=1,2,…,n: kung X*j>0, kung gayon; Kung , pagkatapos, at katulad nito,

kung, kung gayon ; kung, kung gayon.

Ang isang mahalagang konklusyon ay sumusunod mula sa teorama na ito na ang ipinakilalang pagsusulatan sa pagitan ng mga variable ng magkabilang dalawahang problema sa pag-abot sa pinakamabuting kalagayan (i.e., sa huling hakbang ng paglutas ng bawat problema sa pamamagitan ng simplex na pamamaraan) ay kumakatawan sa isang sulat sa pagitan pangunahing(bilang panuntunan, hindi katumbas ng zero) mga variable ng isa sa mga dalawahang problema at hindi core(katumbas ng zero) mga variable ng isa pang problema kapag bumubuo sila ng mga tinatanggap na pangunahing solusyon.

Ang pangalawang duality theorem. Ang mga bahagi ng pinakamainam na solusyon ng dalawahang problema ay katumbas ng ganap na mga halaga ng mga coefficient sa kaukulang mga variable ng linear function ng orihinal na problema, na ipinahayag sa mga tuntunin ng mga menor de edad na variable ng pinakamainam na solusyon nito.

Magkomento. Kung sa isa sa magkabilang dalawahang problema ang pagiging natatangi ng pinakamainam na solusyon ay nilabag, kung gayon ang pinakamainam na solusyon ng dalawahang problema ay bumababa. Ito ay dahil sa ang katunayan na kung ang pagiging natatangi ng pinakamainam na solusyon ng orihinal na problema ay nilabag, hindi bababa sa isa sa mga pangunahing variable ang nawawala sa pagpapahayag ng linear function ng pinakamainam na solusyon nito sa mga tuntunin ng mga di-basic na variable.

14. Mga pagtatasa na Objectively tinutukoy at ang kanilang kahulugan

Ang mga bahagi ng pinakamainam na solusyon ng dalawahang problema ay tinatawag na pinakamainam (dalawahan) na pagtatantya ng orihinal na problema. Tinawag sila ng Academician L.V. Kantorovich nakakondisyon sa layunin mga pagtatantya ( sa panitikan tinatawag din silang hidden income) .

Mga karagdagang variable ng orihinal na problema I, na kumakatawan sa pagkakaiba sa pagitan ng mga stock bi ng mga mapagkukunan S1,S2,S3,S4 at ang kanilang pagkonsumo, ipahayag natirang mapagkukunan , at karagdagang mga variable ng dual problem II na kumakatawan sa pagkakaiba sa pagitan ng mga gastos ng mga mapagkukunan para sa produksyon ng isang yunit ng output mula sa kanila at ang mga presyo cj ng mga produkto P1,P2 , ipahayag labis na gastos sa presyo.

Kaya, ang mga pagtatantya ng mga mapagkukunan na may layunin ay tumutukoy sa antas ng kakulangan ng mga mapagkukunan: ayon sa pinakamainam na plano ng produksyon, ang mga mahirap (ibig sabihin, ganap na ginagamit) na mga mapagkukunan ay tumatanggap ng mga hindi zero na pagtatantya, at hindi-scarce - mga zero na pagtatantya. Ang halagang y*i ay ang pagtatantya ng i-th na mapagkukunan. Kung mas mataas ang halaga ng pagtatantya y*i, mas mataas ang kakulangan ng mapagkukunan. Para sa isang hindi kakaunting mapagkukunan y*i=0.

Kaya, ang mga cost-effective, hindi kumikitang mga uri ng mga produkto lamang ang maaaring mahulog sa pinakamainam na plano ng produksyon (bagaman ang criterion ng kakayahang kumita dito ay kakaiba: ang presyo ng isang produkto ay hindi lalampas sa mga gastos ng mga mapagkukunang natupok sa paggawa nito, ngunit eksaktong katumbas sa kanila).

Pangatlong duality theorem . Ang mga bahagi ng pinakamainam na solusyon ng dalawahang problema ay katumbas ng mga halaga ng mga bahagyang derivatives ng linear function. Fmax(b1, b2,…, bm)ayon sa kaukulang mga argumento, i.e.

Ang Objectively natukoy na mga pagtatantya ng mga mapagkukunan ay nagpapakita kung gaano karaming mga yunit ng pananalapi ang pinakamataas na kita (kita) mula sa pagbebenta ng mga produkto kapag ang stock ng kaukulang mapagkukunan ay nagbago ng isang yunit.

Ang dalawahang pagtatantya ay maaaring magsilbing tool para sa pagsusuri at paggawa ng mga tamang desisyon sa patuloy na nagbabagong industriya. Kaya, halimbawa, sa tulong ng mga layunin na tinutukoy na mga pagtatantya ng mga mapagkukunan, posible na ihambing ang pinakamainam na mga gastos sa kondisyon at mga resulta ng produksyon.

Ang Objectively natukoy na mga pagtatantya ng mga mapagkukunan ay ginagawang posible upang hatulan ang epekto ng hindi anuman, ngunit medyo maliit na pagbabago lamang sa mga mapagkukunan. Sa mga biglaang pagbabago, ang mga pagtatantya mismo ay maaaring maging iba, na hahantong sa imposibilidad na gamitin ang mga ito para sa pagsusuri ng kahusayan sa produksyon. Ayon sa mga ratios ng mga obhetibong natukoy na pagtatantya, ang mga kinakalkula na pamantayan ng pagpapalit ng mapagkukunan ay maaaring matukoy, kung saan ang patuloy na pagpapalit sa loob ng katatagan ng dalawahang pagtatantya ay hindi nakakaapekto sa kahusayan ng pinakamainam na plano. Konklusyon. Ang dalawahang marka ay:

1. Isang tagapagpahiwatig ng kakapusan ng mga mapagkukunan at produkto.

2. Isang tagapagpahiwatig ng impluwensya ng mga paghihigpit sa halaga ng layunin ng function.

3. Isang tagapagpahiwatig ng kahusayan ng produksyon ng ilang mga uri ng mga produkto mula sa pananaw ng pinakamainam na pamantayan.

4. Isang tool para sa paghahambing ng kabuuang contingent na gastos at resulta.

15. Pahayag ng gawain sa transportasyon ayon sa criterion ng gastos.

TK - ang gawain ng pinaka-ekonomiko na plano para sa transportasyon ng isang homogenous o mapagpapalit na produkto mula sa isang punto ng produksyon (mga istasyon ng pag-alis) hanggang sa mga punto ng pagkonsumo (mga istasyon ng patutunguhan) - ay ang pinakamahalagang pribadong gawain ng LP, na may malawak na praktikal na mga aplikasyon hindi para lamang sa mga problema sa transportasyon.

Ang TK ay nakikilala sa LP sa pamamagitan ng katiyakan ng mga pang-ekonomiyang katangian, ang mga tampok ng modelo ng matematika, ang pagkakaroon ng mga tiyak na pamamaraan ng solusyon.

Ang pinakasimpleng pormulasyon ng TOR sa mga tuntunin ng gastos ay ang mga sumusunod: sa T mga punto ng pag-alis A1,…,Am ay ayon sa pagkakabanggit a1,…,am unit ng magkakatulad na kargamento (mga mapagkukunan) na ihahatid n mga mamimili B1,…,Bn sa dami b1,…,bn units (pangangailangan). Ang gastos sa transportasyon ay Cij ng pagdadala ng isang yunit ng kargamento mula sa i-th point of departure hanggang sa j-th point of consumption ay kilala.

Kinakailangang gumuhit ng plano sa transportasyon, ibig sabihin, alamin kung gaano karaming mga yunit ng kargamento ang dapat ipadala mula sa i-th point of departure hanggang sa j-th point of consumption sa paraan na ang mga pangangailangan ay ganap na nasiyahan at ang kabuuang Ang mga gastos sa transportasyon ay minimal.

Para sa kalinawan, ang mga kondisyon ng TK ay ipapakita sa anyo ng isang talahanayan, na tinatawag na pamamahagi .

Provider	Konsyumer			Stock ng kargamento
Kailangan

Dito, ang halaga ng kargamento na dinala mula sa i-th point of origin hanggang sa j-th destination ay katumbas ng xij, ang stock ng cargo sa i-th point of departure ay tinutukoy ng value ai>=0, at ang Ang demand ng j-th destination sa cargo ay bj>=0 . Ipinapalagay na lahat ng xij>=0.

Ang matrix ay tinatawag matrix ng taripa (mga gastos o gastos sa transportasyon).

Plano ng gawain sa transportasyon ay tinatawag na matrix, kung saan ang bawat bilang na xij ay tumutukoy sa bilang ng mga yunit ng kargamento na dapat ihatid mula sa i-th point ng pag-alis hanggang sa j-th na destinasyon. Ang matrix xij ay tinatawag matrix ng trapiko.

Ang kabuuang kabuuang gastos na nauugnay sa pagpapatupad ng plano sa transportasyon ay maaaring katawanin ng layunin ng function

Dapat matugunan ng mga variable xij ang mga paghihigpit sa mga stock, sa mga consumer at mga kundisyon ng hindi negatibo:

– mga paghihigpit sa mga stock (2);

– mga paghihigpit sa mga mamimili (2);

ay ang mga kondisyon na hindi negatibo (3).

Kaya, sa matematika ang problema sa transportasyon ay nabalangkas tulad ng sumusunod. Ang sistema ng mga hadlang (2) sa ilalim ng kundisyon (3) at ang layunin na function (1) ay ibinigay. Kabilang sa hanay ng mga solusyon ng system (2), kinakailangan na makahanap ng gayong di-negatibong solusyon na nagpapaliit sa function (1).

Ang sistema ng mga hadlang para sa problema (1) - (3) ay naglalaman ng m + n equation na may Tn mga variable. Ipinapalagay na ang kabuuang reserba ay katumbas ng kabuuang pangangailangan, i.e.

16. Tanda ng kalutasan ng problema sa transportasyon

Upang ang problema sa transportasyon ay magkaroon ng katanggap-tanggap na mga plano, kinakailangan at sapat na ang pagkakapantay-pantay

Mayroong dalawang uri ng mga gawain sa transportasyon: sarado , kung saan ang kabuuang dami ng kargamento ng mga supplier ay katumbas ng kabuuang demand ng mga mamimili, at bukas , kung saan ang kabuuang kapasidad ng produksyon ng mga supplier ay lumampas sa demand ng mga consumer o ang demand ng mga consumer ay mas malaki kaysa sa aktwal na kabuuang kapasidad ng mga supplier, i.e.

Ang isang bukas na modelo ay maaaring ma-convert sa isang sarado. Kaya, kung, pagkatapos ay isang kathang-isip (n + 1)-th na destinasyon ay ipinakilala sa matematikal na modelo ng problema sa transportasyon. Upang gawin ito, ang isang karagdagang haligi ay ibinigay sa task matrix, kung saan ang pangangailangan ay katumbas ng pagkakaiba sa pagitan ng kabuuang kapasidad ng mga supplier at ang aktwal na pangangailangan ng mga mamimili:

Ang lahat ng mga taripa para sa paghahatid ng mga kalakal sa puntong ito ay ituturing na katumbas ng zero. Sa ganitong paraan, ang bukas na modelo ng problema ay binago sa isang sarado. Para sa isang bagong problema, ang layunin ng function ay palaging pareho, dahil ang halaga ng karagdagang transportasyon ay zero. Sa madaling salita, hindi nilalabag ng fictitious consumer ang consistency ng constraint system.

Kung, pagkatapos ay isang kathang-isip (m + 1)-th punto ng pag-alis ay ipinakilala, kung saan ang stock ng kargamento ay katumbas ng ay maiugnay.

Ang mga taripa para sa paghahatid ng mga kalakal mula sa fictitious na supplier na ito ay muling ipinapalagay na katumbas ng zero. Ang isang hilera ay idaragdag sa matrix, hindi ito makakaapekto sa layunin ng pag-andar, at ang sistema ng mga hadlang sa problema ay magiging magkatugma, ibig sabihin, magiging posible na mahanap ang pinakamainam na plano.

Ang sumusunod na theorem ay may malaking kahalagahan para sa problema sa transportasyon.

Teorama. Ang ranggo ng matrix ng problema sa transportasyon ay mas mababa ng isa kaysa sa bilang ng mga equation, i.e. r ( a )= m + n -1.

Ito ay sumusunod mula sa theorem na ang bawat reference na disenyo ay dapat magkaroon ng (m-1)(n-1) mga libreng variable na katumbas ng zero at m+n-1 na mga pangunahing variable.

Hahanapin namin ang plano sa transportasyon ng gawain sa transportasyon nang direkta sa talahanayan ng pamamahagi. Ipinapalagay namin na kung ang variable na xij ay kukuha ng isang halaga, pagkatapos ay isusulat namin ang halagang ito sa kaukulang cell (I,j), ngunit kung xij=0, pagkatapos ay iiwan namin ang cell (I,j) nang libre. Isinasaalang-alang ang theorem sa ranggo ng isang matrix sa talahanayan ng pamamahagi dapat kasama sa master plan m+n-1 sinasakop na mga cell at ang iba ay magiging libre.

Ang mga kinakailangan para sa batayang plano ay hindi lamang ang mga ito. Dapat matugunan ng mga base plan ang isa pang kinakailangan na nauugnay sa mga cycle.

Isang hanay ng mga traffic matrix cell kung saan dalawa at dalawang magkalapit na cell lang ang matatagpuan sa isang row o sa isang column at ang huling cell ng set ay nasa parehong row o column kung saan ang una ay tinatawag na closed ikot .

Sa graphically, ang cycle ay isang saradong putol na linya, ang mga vertices nito ay matatagpuan sa okupado na mga cell ng talahanayan, at ang mga link ay matatagpuan lamang sa mga row o column. Bukod dito, sa bawat vertex ng cycle ay may eksaktong dalawang link, ang isa ay nasa isang hilera, at ang isa ay nasa isang haligi. Kung ang polyline na bumubuo sa cycle ay nagsalubong sa sarili nito, kung gayon ang mga punto ng self-intersection ay hindi vertices.

Ang mga sumusunod na mahahalagang katangian ng mga plano sa gawain sa transportasyon ay nauugnay sa hanay ng mga cycle cell:

1) ang isang tinatanggap na plano ng gawain sa transportasyon ay isang sanggunian kung at kung walang cycle na maaaring mabuo mula sa mga cell na inookupahan ng planong ito;

2) kung mayroon tayong pangunahing plano, kung gayon para sa bawat libreng cell posible na bumuo lamang ng isang cycle na naglalaman ng cell na ito at ilang bahagi ng mga sinasakop na cell.

17. Pagbuo ng paunang baseline

Panuntunan sa hilagang-kanlurang sulok.

Upang gumuhit ng isang paunang plano sa transportasyon, maginhawang gamitin ang panuntunan sa sulok sa hilagang-kanluran, na ang mga sumusunod.

Pupunan namin, simula sa kaliwang itaas, na karaniwang tinatawag na "northwest corner", na gumagalaw pa sa linya sa kanan o pababa sa column. Inilalagay namin sa cell (1; 1) ang mas maliit sa mga numerong a1 at b1, ibig sabihin. Kung, kung gayon ang unang hanay ay "sarado", ibig sabihin, ang pangangailangan ng unang mamimili ay ganap na nasiyahan. Nangangahulugan ito na para sa lahat ng iba pang mga cell ng unang column, ang halaga ng kargamento para sa .

Kung, kung gayon ang unang linya ay katulad na "sarado", ibig sabihin, para sa . Nagpapatuloy kami sa pagpuno sa katabing cell (2; 1), kung saan kami pumapasok.

Matapos mapunan ang pangalawang cell (1; 2) o (2; 1), nagpapatuloy kami sa pagpuno sa susunod na ikatlong cell sa pangalawang hilera o sa pangalawang hanay. Ipagpapatuloy namin ang prosesong ito hanggang, sa ilang yugto, ang mga mapagkukunan at ang mga pangangailangan bn ay maubos. Ang huling napunong cell ay nasa huling n-th column at sa huling m-th row.

Ang "minimum na elemento" na panuntunan.

Ang paunang plano ng sanggunian, na binuo ayon sa panuntunang "north-west corner", ay kadalasang lumalabas na napakalayo mula sa pinakamainam, dahil ang mga gastos na cij ay hindi isinasaalang-alang kapag tinutukoy ito. Samakatuwid, sa karagdagang mga kalkulasyon, maraming mga pag-ulit ang kakailanganin upang makamit ang pinakamainam na plano. Ang bilang ng mga pag-ulit ay maaaring bawasan kung ang paunang plano ay binuo ayon sa "minimum na elemento" na panuntunan. Ang kakanyahan nito ay nakasalalay sa katotohanan na sa bawat hakbang ang pinakamataas na posibleng "paggalaw" ng kargamento sa cell ay isinasagawa na may pinakamababang taripa cij. Nagsisimula kaming punan ang talahanayan mula sa cell, na tumutugma sa pinakamaliit na elemento ng cij ng taripa matrix. Ang pinakamaliit sa mga numerong ai o bj ay inilalagay sa cell na may pinakamababang taripa . Pagkatapos, ang hilera na naaayon sa supplier, na ang mga stock ay ganap na naubos, o ang column na naaayon sa consumer, na ang demand ay ganap na nasiyahan, ay hindi kasama sa pagsasaalang-alang. Maaaring lumabas na ang isang hilera at column ay dapat na hindi kasama sa parehong oras kung ang imbentaryo ng supplier ay ganap na naubos at ang demand ng consumer ay ganap na nasiyahan. Pagkatapos, mula sa natitirang mga cell ng talahanayan, ang cell na may pinakamababang taripa ay muling pipiliin at ang proseso ng pamamahagi ng mga stock ay magpapatuloy hanggang sa lahat ng mga ito ay maipamahagi at ang demand ay nasiyahan.

18. Paraan ng mga potensyal

Ang pangkalahatang prinsipyo ng pagtukoy ng pinakamainam na plano ng gawain sa transportasyon sa pamamagitan ng potensyal na pamamaraan ay katulad ng prinsipyo ng paglutas ng problema sa LP sa pamamagitan ng simplex na paraan, ibig sabihin: una, ang pangunahing plano ng gawain sa transportasyon ay natagpuan, at pagkatapos ay sunud-sunod na. napabuti hanggang sa makuha ang pinakamainam na plano.

Ang kakanyahan ng potensyal na pamamaraan ay ang mga sumusunod. Matapos mahanap ang paunang reference na plano sa transportasyon, ang bawat supplier (bawat row) ay bibigyan ng isang tiyak na numero na tinatawag na potensyal ng supplier Ai , at ang bawat consumer (bawat column) ay bibigyan ng isang tiyak na numero na tinatawag na potensyal ng consumer.

Ang halaga ng isang toneladang kargamento sa isang punto ay katumbas ng halaga ng isang toneladang kargamento bago ang transportasyon + ang halaga ng transportasyon nito: .

Upang malutas ang problema sa transportasyon sa pamamagitan ng potensyal na pamamaraan, kinakailangan:

1. Bumuo ng pangunahing plano sa transportasyon ayon sa isa sa mga panuntunang nakabalangkas. Ang bilang ng mga napunong cell ay dapat na m+n-1.

2. Kalkulahin ang mga potensyal at, ayon sa pagkakabanggit, mga supplier at consumer (para sa mga abalang cell): . Ang bilang ng mga napunong cell ay m+n-1, at ang bilang ng mga equation ay m+n. kasi ang bilang ng mga equation ay mas mababa ng isa kaysa sa bilang ng mga hindi alam, kung gayon ang isa sa mga hindi alam ay libre at maaaring tumagal ng anumang numerical na halaga. Halimbawa, . Ang natitirang mga potensyal para sa isang ibinigay na reference na solusyon ay natatanging tinutukoy.

3. Suriin para sa optimality, i.e. para sa mga libreng cell kalkulahin ang mga marka. Kung, kung gayon ang transportasyon ay kapaki-pakinabang at ang plano X ay pinakamainam - isang tanda ng pinakamainam. Kung mayroong hindi bababa sa isang pagkakaiba, pagkatapos ay pumunta sa isang bagong reference plan. Sa pang-ekonomiyang kahulugan nito, ang halaga ay nagpapakilala sa pagbabago sa kabuuang gastos sa transportasyon na magaganap dahil sa pagpapatupad ng iisang supply ng i-th na supplier sa j-th consumer. Kung, kung gayon ang isang solong paghahatid ay hahantong sa pagtitipid sa mga gastos sa transportasyon, kung - sa isang pagtaas sa mga ito. Samakatuwid, kung kabilang sa mga libreng direksyon ng supply ay walang mga direksyon na nakakatipid sa mga gastos sa transportasyon, kung gayon ang nagresultang plano ay pinakamainam.

4. Kabilang sa mga positibong numero, ang maximum ay pinili, na binuo para sa isang libreng cell, kung saan ito ay tumutugma sa ikot ng muling pagkalkula. Matapos mabuo ang cycle para sa napiling libreng cell, dapat kang lumipat sa isang bagong reference plan. Upang gawin ito, kailangan mong ilipat ang mga load sa loob ng mga cell na nauugnay sa libreng cell na ito sa pamamagitan ng ikot ng muling pagkalkula.

a) Ang bawat isa sa mga cell na konektado sa pamamagitan ng isang cycle na may ibinigay na libreng cell ay itinalaga ng isang tiyak na senyales, at ang libreng cell na ito ay "+", at lahat ng iba pang mga cell (vertices ng cycle) ay halili na mga palatandaan "-" at "+" . Tatawagin natin ang mga cell na ito na minus at plus.

b) Sa mga minus na cell ng cycle, makikita natin ang pinakamababang supply, na tinutukoy natin. Ang mas maliit sa mga numerong xij sa mga negatibong selula ay inililipat sa libreng cell na ito. Kasabay nito, ang numerong ito ay idinagdag sa kaukulang mga numero sa mga cell na may tanda na "+" at ibinawas mula sa mga numero sa minus na mga cell. Ang isang cell na dati nang libre ay magiging okupado at papasok sa reference plan; at ang minus cell, kung saan nakatayo ang pinakamababa sa mga numerong xij, ay itinuturing na libre at umalis sa reference plan.

Kaya, natukoy ang isang bagong baseline. Ang paglipat mula sa isang baseline patungo sa isa pang inilarawan sa itaas ay tinatawag na pagbabago sa ikot ng muling pagkalkula. Kapag lumilipat kasama ang ikot ng muling pagkalkula, ang bilang ng mga sinasakop na mga cell ay nananatiling hindi nagbabago, ibig sabihin, ito ay nananatiling katumbas ng m+n-1. Bukod dito, kung mayroong dalawa o higit pang magkaparehong numero na xij sa mga minus na cell, isa lamang sa mga cell na ito ang bakante, at ang iba ay naiwang abala na walang mga supply.

5. Ang nagreresultang reference plan ay sinusuri para sa pinakamainam, i.e. ulitin ang lahat ng mga hakbang mula sa talata 2.

19. Ang konsepto ng dynamic na programming.

Ang DP (pagpaplano) ay isang mathematical na pamamaraan para sa paghahanap ng pinakamainam na solusyon sa mga multi-step (multi-stage) na mga problema. Ang ilan sa mga problemang ito ay natural na nahahati sa magkakahiwalay na mga hakbang (yugto), ngunit may mga problema kung saan ang partisyon ay kailangang artipisyal na ipasok upang malutas sa pamamagitan ng pamamaraan ng DP.

Karaniwan, ang mga pamamaraan ng DP ay nag-optimize sa pagpapatakbo ng ilang mga kinokontrol na sistema, ang epekto nito ay tinatantya pandagdag, o multiplicative, layunin function. Additive ay isang function ng ilang variable f(x1,x2,…,xn) na ang value ay kinakalkula bilang kabuuan ng ilang function fj na nakadepende sa isang variable xj: . Ang mga tuntunin ng additive objective function ay tumutugma sa epekto ng mga desisyon na ginawa sa mga indibidwal na yugto ng kinokontrol na proseso.

Prinsipyo ng pagiging optimal ni R. Bellman.

Ang kahulugan ng diskarte na ipinatupad sa dynamic na programming ay namamalagi sa pagpapalit ng solusyon ng orihinal na multidimensional na problema sa isang pagkakasunod-sunod ng mga problema ng mas mababang dimensyon. Mga pangunahing kinakailangan para sa mga gawain:

1. ang layunin ng pananaliksik ay dapat kinokontrol na sistema (bagay) na may ibinigay na wastong estado at tinatanggap mga kagawaran;

2. dapat pahintulutan ng gawain ang interpretasyon bilang isang prosesong maraming hakbang, na ang bawat hakbang ay binubuo ng pag-aampon mga solusyon O pagpili ng isa sa mga tinatanggap na kontrol na humahantong sa pagbabago ng estado mga sistema;

3. ang gawain ay hindi dapat nakadepende sa bilang ng mga hakbang at tukuyin sa bawat isa sa kanila;

4. ang estado ng system sa bawat hakbang ay dapat na inilarawan ng parehong (compositionally) set ng mga parameter;

5. ang kasunod na estado kung saan makikita ng system ang sarili pagkatapos pumili ng solusyon sa k-ika hakbang, ay nakasalalay lamang sa ibinigay na solusyon at ang paunang estado hanggang sa simula k- hakbang. Ang ari-arian na ito ay ang pangunahing isa mula sa punto ng view ng ideolohiya ng dynamic na programming at tinatawag kakulangan ng mga kahihinatnan .

Isaalang-alang ang mga isyu ng paglalapat ng dynamic na modelo ng programming sa isang pangkalahatang anyo. Hayaang magkaroon ng gawain sa pamamahala ng ilang abstract na bagay na maaaring nasa iba't ibang estado. Ang kasalukuyang estado ng bagay ay makikilala gamit ang isang tiyak na hanay ng mga parameter, na ilalarawan sa mga sumusunod ng S at tatawagin vector ng estado. Ipinapalagay na ang set S ng lahat ng posibleng estado ay ibinigay. Ang set ay tinukoy din para sa bagay mga tinatanggap na kontrol(kontrol na pagkilos) x, na, nang walang pagkawala ng pangkalahatan, ay maituturing na isang hanay ng numero. Maaaring isagawa ang mga aksyong kontrol sa mga discrete na punto sa oras, at ang kontrol solusyon binubuo sa pagpili ng isa sa mga kontrol. plano mga gawain o diskarte sa pamamahala ang vector x=(x1,x2,…,xn-1) ay tinatawag, ang mga bahagi nito ay ang mga kontrol na pinili sa bawat hakbang ng proseso. Sa pagtingin sa inaasahan kakulangan ng epekto sa pagitan ng bawat dalawang magkakasunod na estado ng object na Sk at Sk+1, mayroong isang kilalang functional dependence, na kinabibilangan din ng napiling kontrol: . Kaya, ang pagtatakda ng paunang estado ng bagay at pagpili ng isang plano X natatanging tukuyin landas ng pag-uugali bagay.

Ang kahusayan ng pamamahala sa bawat hakbang k depende sa kasalukuyang estado Sk, ang napiling control xk at binibilang gamit ang mga function na fk(xk,Sk), na mga summands additive layunin function , nagpapakilala sa pangkalahatang kahusayan ng pamamahala ng pasilidad. ( Tandaan , na ang kahulugan ng function na fk(xk,Sk) ay kinabibilangan ng hanay ng mga tinatanggap na halaga xk , at ang lugar na ito, bilang panuntunan, ay nakasalalay sa kasalukuyang estado ng Sk). Pinakamainam na Kontrol , para sa isang naibigay na panimulang estado S1, binabawasan ang pagpili ng gayong pinakamainam na plano x* , Kung saan maximum na halaga mga halaga ng fk sa kaukulang tilapon.

Ang pangunahing prinsipyo ng dynamic na programming ay na sa bawat hakbang ay hindi dapat magsikap para sa isang nakahiwalay na pag-optimize ng function fk(xk,Sk), ngunit piliin ang pinakamainam na kontrol x*k sa ilalim ng pagpapalagay na ang lahat ng kasunod na mga hakbang ay pinakamainam. Sa pormal, ang prinsipyong ito ay naisasakatuparan sa pamamagitan ng paghahanap sa bawat hakbang k kondisyon na pinakamainam na kontrol , na nagbibigay ng pinakamataas na kabuuang kahusayan simula sa hakbang na ito, sa pag-aakalang ang kasalukuyang estado ay S.

Tukuyin sa pamamagitan ng (mga) Zk ang pinakamataas na halaga ng kabuuan ng mga function fk sa buong hakbang mula sa k dati P(nakuha sa ilalim ng pinakamainam na kontrol sa isang partikular na segment ng proseso), sa kondisyon na ang bagay sa simula ng hakbang k ay nasa estadong S. Kung gayon ang mga function na Zk(s) ay dapat matugunan ang recursive relation:

Ang ratio na ito ay tinatawag pangunahing ugnayan ng pag-uulit (pangunahing functional equation) dynamic na programming. Ipinapatupad nito ang pangunahing prinsipyo ng dynamic na programming, na kilala rin bilang Prinsipyo ng pagiging pinakamainam ni Bellman :

Ang pinakamainam na diskarte sa pagkontrol ay dapat matugunan ang sumusunod na kondisyon: anuman ang paunang estado sk sa kth na hakbang at ang kontrol na pinili sa hakbang na ito xk, ang mga kasunod na kontrol (mga desisyon sa pamamahala) ay dapat na pinakamainam na may kaugnayan sa cocomo yanyu ,bunga ng desisyong ginawa sa hakbang k .

Ang pangunahing kaugnayan ay nagpapahintulot sa amin na mahanap ang mga function na Zk(s) lamang V pinagsama sa paunang kondisyon na sa aming kaso ay pagkakapantay-pantay.

Ang prinsipyo ng optimality na binabalangkas sa itaas ay naaangkop lamang sa mga bagay na kontrolin kung saan ang pagpili ng pinakamainam na kontrol ay hindi nakasalalay sa prehistory ng kinokontrol na proseso, ibig sabihin, kung paano dumating ang system sa kasalukuyang estado. Ang sitwasyong ito ang nagpapangyari na mabulok ang problema at gawing posible ang praktikal na solusyon nito.

Para sa bawat tiyak na gawain, ang functional equation ay may sariling tiyak na anyo, ngunit tiyak na mapanatili nito ang paulit-ulit na likas na likas sa expression (*) at isinasama ang pangunahing ideya ng prinsipyo ng optimality.

20. Ang konsepto ng mga modelo ng laro.

Ang modelo ng matematika ng isang sitwasyon ng salungatan ay tinatawag laro , mga partidong sangkot sa tunggalian mga manlalaro at ang kinalabasan ng tunggalian panalo.

Para sa bawat pormal na laro, ipinakilala namin mga tuntunin , mga. isang sistema ng mga kondisyon na tumutukoy sa: 1) mga opsyon para sa mga aksyon ng mga manlalaro; 2) ang dami ng impormasyon na mayroon ang bawat manlalaro tungkol sa pag-uugali ng mga kasosyo; 3) ang kabayaran kung saan humahantong ang bawat hanay ng mga aksyon. Karaniwan, ang pakinabang (o pagkalugi) ay maaaring mabilang; halimbawa, maaari mong suriin ang isang pagkawala ng zero, isang panalo ng isa, at isang draw ng 1/2. Ang pagbibilang ng mga resulta ng isang laro ay tinatawag pagbabayad .

Ang laro ay tinatawag silid-pasingawan , kung mayroong dalawang manlalaro na kasangkot, at maramihan , kung ang bilang ng mga manlalaro ay higit sa dalawa. Isasaalang-alang lamang namin ang mga ipinares na laro. Sila ay nilalaro ng dalawang manlalaro A At SA, na ang mga interes ay kabaligtaran, at ang ibig sabihin ng laro ay isang serye ng mga aksyon sa bahagi ng A At SA.

Ang laro ay tinatawag zero sum game o antagonistic si skoy , kung ang nakuha ng isa sa mga manlalaro ay katumbas ng pagkawala ng isa pa, i.e. ang kabuuan ng mga kabayaran ng parehong partido ay zero. Upang makumpleto ang gawain ng laro, ito ay sapat na upang ipahiwatig ang halaga ng isa sa kanila . Kung italaga natin A- manalo ng isa sa mga manlalaro, b – kabayaran ng isa, pagkatapos ay para sa isang zero-sum game b= –A, kaya sapat na upang isaalang-alang, halimbawa A.

Ang pagpili at pagpapatupad ng isa sa mga aksyon na ibinigay ng mga patakaran ay tinatawag gumalaw manlalaro. Ang mga galaw ay maaaring personal At random . personal na galaw – ito ay isang malay na pagpili ng manlalaro ng isa sa mga posibleng aksyon (halimbawa, isang paglipat sa isang laro ng chess). Ang hanay ng mga posibleng opsyon para sa bawat personal na galaw ay kinokontrol ng mga patakaran ng laro at depende sa kabuuan ng mga nakaraang galaw sa magkabilang panig.

Random na galaw – ito ay isang random na piniling aksyon (halimbawa, pagpili ng card mula sa isang shuffled deck). Para matukoy sa matematika ang laro, dapat tukuyin ang mga panuntunan ng laro para sa bawat random na galaw pamamahagi ng posibilidad posibleng resulta.

Ang ilang mga laro ay maaaring binubuo lamang ng mga random na galaw (tinatawag na purong laro ng pagkakataon) o mga personal na galaw lamang (chess, checkers). Karamihan sa mga laro ng card ay nabibilang sa magkahalong uri ng mga laro, iyon ay, naglalaman ang mga ito ng parehong random at personal na mga galaw. Sa mga sumusunod, isasaalang-alang lamang namin ang mga personal na galaw ng mga manlalaro.

Ang mga laro ay inuri hindi lamang sa likas na katangian ng mga galaw (personal, random), kundi pati na rin sa likas na katangian at dami ng impormasyong magagamit ng bawat manlalaro tungkol sa mga aksyon ng iba. Ang isang espesyal na klase ng mga laro ay ang tinatawag na "mga laro na may kumpletong impormasyon". Isang laro na may kumpletong impormasyon Tinatawag ang isang laro kung saan alam ng bawat manlalaro sa bawat personal na galaw ang mga resulta ng lahat ng nakaraang galaw, parehong personal at random. Ang mga halimbawa ng larong may kumpletong impormasyon ay ang chess, checkers, at ang kilalang laro ng tic-tac-toe. Karamihan sa mga larong may praktikal na kahalagahan ay hindi nabibilang sa klase ng mga laro na may kumpletong impormasyon, dahil ang hindi alam tungkol sa mga aksyon ng kalaban ay karaniwang isang mahalagang elemento ng mga sitwasyon ng salungatan.

Isa sa mga pangunahing konsepto ng teorya ng laro ay ang konsepto estratehiya .

diskarte Ang isang manlalaro ay tinatawag na isang hanay ng mga panuntunan na tumutukoy sa pagpili ng kanyang aksyon para sa bawat personal na galaw, depende sa sitwasyon. Karaniwan sa panahon ng laro, sa bawat personal na galaw, ang manlalaro ay gumagawa ng isang pagpipilian depende sa partikular na sitwasyon. Gayunpaman, sa prinsipyo posible na ang lahat ng mga desisyon ay ginawa ng manlalaro nang maaga (bilang tugon sa anumang naibigay na sitwasyon). Nangangahulugan ito na ang manlalaro ay pumili ng isang tiyak na diskarte, na maaaring ibigay sa anyo ng isang listahan ng mga patakaran o isang programa. (Kaya maaari mong i-play ang laro gamit ang isang computer). Ang laro ay tinatawag panghuli , kung ang bawat manlalaro ay may limitadong bilang ng mga diskarte, at walang katapusan .– kung hindi.

Nang sa gayon magpasya laro , o hanapin desisyon ng laro , kinakailangan para sa bawat manlalaro na pumili ng isang diskarte na nakakatugon sa kondisyon pinakamainam , mga. dapat matanggap ng isa sa mga manlalaro maximum na panalo, kapag ang pangalawa ay dumikit sa kanyang diskarte, Kasabay nito, ang pangalawang manlalaro ay dapat magkaroon pinakamababang pagkawala , kung ang una ay sumunod sa diskarte nito. Ang mga ganitong estratehiya ay tinatawag pinakamainam . Ang mga pinakamainam na estratehiya ay dapat ding matugunan ang kondisyon Pagpapanatili , mga. hindi dapat kumikita ang sinuman sa mga manlalaro na talikuran ang kanilang diskarte sa larong ito.

Kung ang laro ay paulit-ulit ng sapat na beses, kung gayon ang mga manlalaro ay maaaring hindi interesado na manalo at matalo sa bawat partikular na laro, A average na panalo (pagkatalo) sa lahat ng partido.

Ang layunin ng teorya ng laro ay upang matukoy ang pinakamainam na diskarte para sa bawat manlalaro.

21. Payment matrix. Mas mababa at mas mataas na presyo ng laro

Tapusin ang laro kung saan ang manlalaro A Mayroon itong T mga diskarte, at ang manlalaro B - p ang mga estratehiya ay tinatawag na m×n game.

Isaalang-alang ang isang m×n na laro ng dalawang manlalaro A At SA("kami" at "kalaban").

Hayaan ang player A may T mga personal na estratehiya, na tinutukoy namin ng A1,A2,…,Am. Hayaan ang player SA magagamit n personal na estratehiya, tinutukoy namin ang mga ito B1,B2,…,Bn.

Hayaan ang bawat panig na pumili ng isang partikular na diskarte; para sa amin ay Ai, para sa kalaban Bj. Bilang resulta ng pagpili ng mga manlalaro ng anumang pares ng mga diskarte Ai at Bj (), ang kinalabasan ng laro ay natatanging tinutukoy, i.e. manalo ng aij player A(positibo o negatibo) at pagkawala (-aij) ng manlalaro SA.

Ipagpalagay na ang mga halaga ng aij ay kilala para sa anumang pares ng mga diskarte (Ai,Bj) . Matrix P=aij , na ang mga elemento ay ang mga kabayaran na naaayon sa mga estratehiyang Ai at Bj, tinawag matrix ng pagbabayad o matrix ng laro. Ang mga hilera ng matrix na ito ay tumutugma sa mga diskarte ng manlalaro A, at ang mga column ay mga diskarte ng manlalaro B. Ang mga estratehiyang ito ay tinatawag na dalisay.

Ang m×n game matrix ay may anyo:

Isaalang-alang ang isang m×n na laro na may matrix at tukuyin ang pinakamahusay sa mga diskarte A1,A2,…,Am . Pagpili ng isang diskarte Ai ang player A dapat asahan ang manlalaro SA sasagutin ito ng isa sa mga diskarte Bj kung saan ang kabayaran para sa manlalaro A minimal (manlalaro SA naghahangad na "manakit" ang manlalaro A).

Tukuyin sa pamamagitan ng pinakamaliit na kabayaran ng manlalaro A kapag pinili niya ang diskarte Ai para sa lahat ng posibleng diskarte ng player SA(pinakamaliit na numero sa i-th row ng payoff matrix), i.e.

Sa lahat ng numero () piliin ang pinakamalaki: .

Tawagin natin ang mas mababang presyo ng laro, o maximum na panalo (maxmin). Ito ang garantisadong kabayaran ng player A para sa anumang diskarte ng player B. Kaya naman,

Ang diskarte na naaayon sa maximin ay tinatawag diskarte sa maximum . Manlalaro SA interesadong bawasan ang kabayaran ng manlalaro A, pagpili ng diskarte Bj, isinasaalang-alang niya ang pinakamataas na posibleng kabayaran para sa A. Magpakilala

Sa lahat ng numero, piliin ang pinakamaliit

at tumawag nangungunang presyo ng laro o minimax na kabayaran(minimax). Ginagarantiyahan ng ego ang pagkawala ng manlalaro B. Samakatuwid,

Ang minimax na diskarte ay tinatawag diskarte sa minimax.

Ang prinsipyo na nagdidikta sa mga manlalaro ng pagpili ng pinaka "maingat" na mga diskarte sa minimax at maximin ay tinatawag prinsipyo ng minimax . Ang prinsipyong ito ay sumusunod mula sa makatwirang pagpapalagay na ang bawat manlalaro ay naglalayong makamit ang kabaligtaran na layunin ng kalaban.

Teorama. Ang mas mababang presyo ng laro ay hindi lalampas sa mataas na presyo ng laro. .

Kung pareho ang nakatataas at mas mababang presyo ng laro, ang kabuuang halaga ng nakatataas at mas mababang presyo ng laro ay tinatawag na ang netong presyo ng laro, o ang presyo ng laro. Ang mga diskarte sa minimax na naaayon sa presyo ng laro ay pinakamainam na estratehiya , at ang kanilang kabuuan pinakamainam na solusyon o desisyon ng laro. Sa kasong ito ang manlalaro A tumatanggap ng pinakamataas na garantisadong (independiyente sa pag-uugali ng manlalaro) SA) panalo v, at ang manlalaro SA nakakamit ang minimum na garantisadong (anuman ang pag-uugali ng manlalaro A) natatalo v. Ang solusyon sa laro ay sinasabing mayroon Pagpapanatili , mga. kung ang isa sa mga manlalaro ay nananatili sa kanyang pinakamainam na diskarte, kung gayon hindi magiging kapaki-pakinabang para sa isa pa na lumihis mula sa kanyang pinakamainam na diskarte.

Kung ang isa sa mga manlalaro (halimbawa A) nananatili sa kanyang pinakamainam na diskarte, at ang iba pang manlalaro (SA) ay lilihis mula sa pinakamainam na diskarte nito sa anumang paraan, kung gayon para sa manlalaro na gumawa ng paglihis, hindi ito maaaring maging kapaki-pakinabang; tulad ng isang paglihis ng player SA maaaring sa pinakamahusay na iwanan ang pakinabang na hindi nagbabago. at sa pinakamasamang kaso, dagdagan ito.

Sa kabaligtaran, kung SA sumusunod sa pinakamainam na diskarte nito, at A lumihis mula sa sarili nito, kung gayon hindi ito maaaring maging kapaki-pakinabang sa anumang paraan A.

Ang isang pares ng mga purong diskarte ay nagbibigay ng pinakamainam na solusyon sa laro kung at kung ang kaukulang elemento lamang ay parehong pinakamalaki sa column nito at pinakamaliit sa row nito. Ang ganitong sitwasyon, kung mayroon man, ay tinatawag power point. Sa geometry, ang isang punto sa ibabaw na may katangian: sabay-sabay na minimum sa isang coordinate at maximum kasama ang isa, ay tinatawag kapangyarihan tuldok, sa pamamagitan ng pagkakatulad ang terminong ito ay ginagamit sa teorya ng laro.

Ang laro kung saan , tinawag laro ng power point. Ang elementong may ganitong katangian ay ang power point ng matrix.

Kaya, para sa bawat laro na may power point, mayroong isang solusyon na tumutukoy sa isang pares ng pinakamainam na diskarte para sa magkabilang panig, na naiiba sa mga sumusunod na katangian.

1) Kung ang magkabilang panig ay nananatili sa kanilang pinakamainam na mga diskarte, kung gayon ang average na kabayaran ay katumbas ng netong halaga ng laro v, na parehong mas mababa at mataas na presyo nito.

2) Kung ang isa sa mga partido ay sumunod sa pinakamainam na diskarte nito, habang ang iba ay lumihis mula sa sarili nito, kung gayon ang lumilihis na partido ay maaari lamang matalo mula dito at sa anumang kaso ay hindi maaaring madagdagan ang pakinabang nito.

Sa teorya ng laro, pinatunayan na, sa partikular, ang bawat laro na may kumpletong impormasyon ay may power point, at, dahil dito, ang bawat laro ay may solusyon, ibig sabihin, mayroong isang pares ng pinakamainam na mga diskarte para sa isang panig at sa isa pa, na nagbibigay ng isang average na kabayaran na katumbas ng presyo ng laro. Kung ang isang laro na may kumpletong impormasyon ay binubuo lamang ng mga personal na galaw, kung gayon, kapag ang bawat panig ay naglapat ng sarili nitong pinakamainam na diskarte, ito ay dapat palaging magtatapos sa isang tiyak na resulta, ibig sabihin, isang kabayarang eksaktong katumbas ng presyo ng laro.

22. Solusyon ng laro sa magkahalong estratehiya.

Sa mga may hangganang laro na may praktikal na kahalagahan, ang mga larong may force point ay medyo bihira; mas karaniwan ay ang kaso kapag ang mas mababa at mas mataas na mga presyo ng laro ay magkaiba. Ang pag-aaral ng mga matrice ng naturang mga laro, dumating kami sa konklusyon na kung ang bawat manlalaro ay bibigyan ng pagpili ng isang solong diskarte, kung gayon, batay sa isang makatwirang kumikilos na kalaban, ang pagpipiliang ito ay dapat na matukoy ng minimax na prinsipyo. Ang pagsunod sa aming maximin na diskarte, para sa anumang pag-uugali ng kalaban, tiyak na ginagarantiyahan namin ang aming sarili ng isang kabayaran na katumbas ng mas mababang presyo ng larong α. pinaghalong estratehiya

pinaghalong diskarte Sa ang manlalaro A ay tinatawag na aplikasyon ng mga purong diskarte A1,A1,…,Ai,…,Am na may probabilities p1,p2,…pi,…pm, at ang kabuuan ng mga probabilidad ay katumbas ng 1: . Ang magkahalong diskarte ng player A ay nakasulat bilang isang matrix

o bilang isang string Sa=(p1,p2,…,pi,…,pm).

Katulad nito, ang magkahalong diskarte ng player B ay tinutukoy ng:

O Sb=(q1,q2,…,qi,…,qn),

kung saan ang kabuuan ng mga probabilidad ng paglitaw ng mga estratehiya ay katumbas ng 1: .

Malinaw, ang bawat purong diskarte ay isang espesyal na kaso ng isang halo-halong isa, kung saan ang lahat ng mga diskarte, maliban sa isa, ay inilapat na may mga zero na frequency (mga probabilidad), at ang isang ito ay inilapat na may dalas (probability) na 1.

Lumalabas na sa pamamagitan ng paglalapat ng hindi lamang puro kundi pati na rin ang magkakahalong estratehiya, posibleng makakuha ng solusyon para sa bawat larong may hangganan, ibig sabihin, isang pares ng ganoon (karaniwang halo-halong) estratehiya na kapag ginamit ng dalawang manlalaro ang mga ito, magiging pantay ang kabayaran. sa presyo ng laro, at kapag ang anumang isang panig na paglihis mula sa pinakamainam na diskarte, ang kabayaran ay maaari lamang magbago sa isang direksyon na hindi kanais-nais para sa lihis. Kaya, batay sa prinsipyo ng minimax, ito ay tinutukoy pinakamainam na solusyon (o solusyon) mga laro: ito ay isang pares ng pinakamainam na diskarte sa pangkalahatang kaso, halo-halong, pagkakaroon ng mga sumusunod na pag-aari: kung ang isa sa mga manlalaro ay sumunod sa kanyang pinakamainam na diskarte, kung gayon hindi ito kumikita para sa isa na lumihis mula sa kanya. Ang kabayaran na naaayon sa pinakamainam na solusyon ay tinatawag sa halaga ng paglalaro ng v . Ang presyo ng laro ay nakakatugon sa hindi pagkakapantay-pantay:

Kung saan ang α at β ay ang mas mababa at matataas na presyo ng laro.

Ang pahayag na ito ang nilalaman ng tinatawag na ang pangunahing teorama ng teorya ng laro. Ang teorama na ito ay unang pinatunayan ni John von Neumann noong 1928. Ang mga kilalang patunay ng teorama ay medyo kumplikado; samakatuwid, ipinakita lamang namin ang pagbabalangkas nito.

Ang bawat may hangganang laro ay may hindi bababa sa isang pinakamainam na solusyon, posibleng kasama ng mga pinaghalong diskarte.

Ito ay sumusunod mula sa pangunahing teorama na ang bawat may hangganan na laro ay may presyo.

Hayaan at – pares ng pinakamainam na estratehiya. Kung ang isang purong diskarte ay kasama sa isang pinakamainam na pinaghalong diskarte na may di-zero na posibilidad, kung gayon ito ay tinatawag aktibo (kapaki-pakinabang) .

Patas aktibong teorama ng diskarte: kung ang isa sa mga manlalaro ay sumunod sa kanyang pinakamainam na pinaghalong diskarte, kung gayon ang kabayaran ay nananatiling hindi nagbabago at katumbas ng halaga ng laro v, kung ang pangalawang manlalaro ay hindi lalampas sa kanyang mga aktibong estratehiya.

Maaaring gamitin ng manlalaro ang alinman sa kanyang mga aktibong diskarte sa kanilang purong anyo, at maaari ring ihalo ang mga ito sa anumang proporsyon.

Ang theorem na ito ay may malaking praktikal na kahalagahan - nagbibigay ito ng mga partikular na modelo para sa paghahanap ng mga pinakamainam na estratehiya sa kawalan ng saddle point.

Pag-isipan 2x2 size na laro, na siyang pinakasimpleng kaso ng isang may hangganang laro. Kung ang naturang laro ay may saddle point, kung gayon ang pinakamainam na solusyon ay isang pares ng mga purong diskarte na naaayon sa puntong ito.

Isang larong walang saddle point, ayon sa pangunahing teorama ng teorya ng laro ang pinakamainam na solusyon ay umiiral at natutukoy sa pamamagitan ng isang pares ng magkahalong diskarte At.

Upang mahanap ang mga ito, ginagamit namin ang theorem sa mga aktibong estratehiya. Kung ang manlalaro A sumusunod sa pinakamainam na diskarte nito , kung gayon ang kanyang average na kabayaran ay magiging katumbas ng presyo ng laro v, kahit anong aktibong diskarte ang ginagamit ng manlalaro SA. Para sa 2v2 game, active ang pure strategy ng kahit sinong kalaban kung walang ssdl point. Panalo ang manlalaro A(pagkatalo ng manlalaro SA)– isang random na variable, ang mathematical na inaasahan (average na halaga) kung saan ay ang presyo ng laro. Samakatuwid, ang average na kabayaran ng isang manlalaro A(pinakamainam na diskarte) ay magiging katumbas ng v para sa parehong 1st at 2nd adversary strategy.

Hayaan ang laro na ibigay ng payoff matrix.

Average na bayad ng manlalaro A, kung gumagamit siya ng pinakamainam na pinaghalong diskarte at ang manlalaro SA - purong diskarte B1 (ito ay tumutugma sa 1st column ng payoff matrix R), katumbas ng presyo ng laro v: .

Ang manlalaro ay tumatanggap ng parehong average na kabayaran A, kung ang 2nd player ay gumagamit ng diskarte B2, i.e. . Dahil doon, nakakakuha kami ng isang sistema ng mga equation para sa pagtukoy ng pinakamainam na diskarte at mga presyo ng laro v:

Ang paglutas ng sistemang ito, makuha namin ang pinakamainam na diskarte

at ang presyo ng laro.

Paglalapat ng aktibong teorema ng diskarte upang mahanap – pinakamainam na diskarte ng manlalaro SA, makuha namin iyon para sa anumang purong diskarte ng manlalaro A (A1 o A2) average na pagkawala ng manlalaro SA katumbas ng presyo ng laro v, ibig sabihin.

Pagkatapos ang pinakamainam na diskarte ay tinutukoy ng mga formula: .

Ang gawain ng paglutas ng laro, kung ang matrix nito ay hindi naglalaman ng saddle point, ay mas mahirap, mas malaki ang halaga m At n. Samakatuwid, sa teorya ng mga laro ng matrix, ang mga pamamaraan ay isinasaalang-alang kung saan ang solusyon ng ilang mga laro ay nabawasan sa solusyon ng iba, mas simple, lalo na, sa pamamagitan ng pagbabawas ng dimensyon ng matrix. Posibleng bawasan ang dimensyon ng isang matrix sa pamamagitan ng pagbubukod Kopyahin at malinaw naman disadvantageous estratehiya.

Kopyahin ay tinatawag na mga diskarte na tumutugma sa parehong mga halaga ng mga elemento sa payoff matrix, i.e. ang matrix ay naglalaman ng parehong mga hilera (columns).

Kung ang lahat ng elemento ng i-th row ng matrix ay mas mababa kaysa sa kaukulang elemento ng k-th row, ang i-th na diskarte para sa player A hindi pinakinabangang (winning mas mababa).

Kung ang lahat ng elemento ng rth column ng matrix ay mas malaki kaysa sa kaukulang elemento ng jth column, kung gayon para sa player SA Ang r-th na diskarte ay hindi kumikita (mas malaki ang pagkawala).

Ang pamamaraan para sa pag-aalis ng duplicative at malinaw na hindi kumikitang mga diskarte ay dapat palaging mauna sa solusyon ng laro.

23. Geometric na interpretasyon ng larong 2×2

Desisyon sa laro 2×2 nagbibigay-daan sa isang malinaw na geometric na interpretasyon.

Hayaang ibigay ang laro ng payoff matrix P=(aij), i, j=1,2.

Sa abscissa (Fig.) Itabi yunit segment A1A2; punto A1 ( X=0) inilalarawan ang diskarte A1, punto A2 ( X=1) inilalarawan ang diskarte A2, at lahat ng intermediate na punto ng segment na ito ay halo-halong diskarte Sa ng unang manlalaro, at ang distansya mula Sa hanggang sa kanang dulo ng segment ay ang probabilidad na p1 ng diskarte A1 , ang distansya sa kaliwang dulo ay ang posibilidad na p2 ng diskarte A2 .

Gumuhit tayo ng dalawang patayo sa x-axis sa pamamagitan ng mga puntos na A1 at A2: axis I-I at axis II-II. Sa I-I axis, ipagpapaliban natin ang mga nadagdag sa ilalim ng diskarte A1; sa axis II-II - mga kabayaran sa ilalim ng diskarte A2.

Kung ang player na A ay gumagamit ng diskarte A1, ang kanyang kabayaran sa ilalim ng diskarte B1 ng player B ay a11, at sa ilalim ng diskarte B2 ito ay a12. Ang mga numerong a11 at a12 sa axis I ay tumutugma sa mga puntos na B1 at B2.

Kung ang manlalaro A ay gumagamit ng diskarte A2, ang kanyang kabayaran sa ilalim ng diskarte B1 ng manlalaro B ay a21, at sa ilalim ng diskarte B2 ito ay katumbas ng a22. Ang mga numerong a21 at a22 ay tumutugma sa mga puntos na B1 at B2 sa axis II.

Ikinonekta namin ang mga puntos na B1 (I) at B1 (II); B2 (I) at B2 (II). Nakakuha ng dalawang tuwid na linya. Tuwid na linya B1B1– kung ang manlalaro A naglalapat ng magkahalong diskarte (anumang kumbinasyon ng mga diskarte A1 at A2 na may probabilities p1 at p2) at inilapat ng player B ang diskarte B1. Panalong manlalaro A tumutugma sa ilang punto sa linyang ito. Ang average na kabayaran na naaayon sa pinaghalong diskarte ay tinutukoy ng formula na a11p1+a21p2 at kinakatawan ng punto M1 sa linya B1B1.

Katulad nito, binubuo namin ang segment na B2B2 na naaayon sa paggamit ng diskarte B2 ng pangalawang manlalaro. Sa kasong ito, ang average na nakuha ay tinutukoy ng formula na a12p1+a22p2 at kinakatawan ng point M2 sa tuwid na linya B2B2.

Kailangan nating makahanap ng pinakamainam na diskarte S*a, ibig sabihin, isa kung saan ang pinakamababang kabayaran (para sa anumang pag-uugali SA) ay magiging maximum. Upang gawin ito, bubuo kami ang mas mababang limitasyon ng pakinabang na may mga diskarte sa B1B2 , ibig sabihin, ang sirang linyang B1NB2 na minarkahan sa Fig. makapal na linya. Ito ang lower bound ay magpapahayag ng pinakamababang kabayaran ng manlalaro A para sa alinman sa mga pinaghalong estratehiya nito; tuldokN , kung saan ang pinakamababang kabayaran na ito ay umabot sa pinakamataas, at tinutukoy ang solusyon (pinakamainam na diskarte) at ang presyo ng laro. Point ordinate N may presyo bang laruin v. Mga coordinate ng punto N nakita namin bilang mga coordinate ng mga punto ng intersection ng mga linya B1B1 at B2B2. Sa aming kaso, ang solusyon ng laro ay tinutukoy ng intersection point ng mga diskarte. Gayunpaman, hindi ito palaging magiging kaso.

Ito ay geometrically posible upang matukoy ang pinakamainam na diskarte bilang isang manlalaro A, pati na rin ang player SA; sa parehong mga kaso, ang prinsipyo ng minimax ay ginagamit, ngunit sa pangalawang kaso, hindi ang mas mababa, ngunit ang itaas na hangganan ng kabayaran ay itinayo, at hindi ang maximum, ngunit ang minimum ay tinutukoy dito.

Kung ang payoff matrix ay naglalaman ng mga negatibong numero, kung gayon para sa isang graphical na solusyon ng problema ay mas mahusay na lumipat sa isang bagong matrix na may mga di-negatibong elemento; upang gawin ito, sapat na upang idagdag ang kaukulang positibong numero sa mga elemento ng orihinal na matrix. Ang desisyon ng laro ay hindi magbabago, ngunit ang presyo ng laro ay tataas ng bilang na ito. Maaaring gamitin ang graphical na paraan upang malutas ang larong 2×n, m×2.

24. Pagbawas ng isang matrix game sa isang linear programming problem

Ang larong m×n sa pangkalahatan ay walang visual na geometric na interpretasyon. Ang solusyon nito ay medyo matrabaho para sa malaki T At n, gayunpaman, wala itong pangunahing mga paghihirap, dahil maaari itong mabawasan sa paglutas ng isang linear na problema sa programming. Ipakita natin.

Hayaang ang m×n na laro ay ibigay ng payoff matrix . Manlalaro A may mga diskarte A1,A2,..Ai,..Am , manlalaro SA - estratehiya B 1,B 2,..B ako,.. B n. Ito ay kinakailangan upang matukoy ang pinakamainam na mga diskarte at kung saan ay ang mga probabilidad ng paglalapat ng kaukulang purong estratehiya Ai,Bj,

Ang pinakamainam na diskarte ay nakakatugon sa sumusunod na kinakailangan. Nagbibigay ito ng manlalaro A average na kabayaran na hindi bababa sa presyo ng laro v, para sa anumang diskarte ng manlalaro SA at isang kabayarang katumbas ng presyo ng laro v, gamit ang pinakamainam na diskarte ng manlalaro SA. Nang walang pagkawala ng pangkalahatan, itinakda namin v> 0; ito ay maaaring makamit sa pamamagitan ng paggawa ng lahat ng elemento . Kung ang manlalaro A naglalapat ng magkahalong diskarte laban sa anumang purong diskarte Bj player SA, pagkatapos ay nakukuha niya average na kabayaran , o matematikal na pag-asa na manalo (ibig sabihin, mga elemento j-Go Ang mga hanay ng payoff matrix ay pinarami ng termino sa pamamagitan ng termino sa mga katumbas na probabilidad ng mga estratehiyang A1,A2,..Ai,..Am at ang mga resulta ay idinagdag).

Para sa isang pinakamainam na diskarte, ang lahat ng average na kabayaran ay hindi mas mababa sa presyo ng laro v, kaya nakakakuha tayo ng sistema ng hindi pagkakapantay-pantay:

Ang bawat isa sa mga hindi pagkakapantay-pantay ay maaaring hatiin sa isang numero. Ipakilala natin ang mga bagong variable: . Pagkatapos ay kinukuha ng system ang form

Layunin ng Manlalaro A- i-maximize ang iyong garantisadong kabayaran, ibig sabihin. presyo ng laro v.

Ang paghahati sa pagkakapantay-pantay, nakuha namin na ang mga variable ay nakakatugon sa kondisyon: . Pag-maximize ng presyo ng laro v ay katumbas ng pagliit ng dami , kaya ang problema ay maaaring mabalangkas tulad ng sumusunod: tukuyin ang mga variable na halaga , maupang matugunan ang mga linear na hadlang(*) At habang ang linear function (2*) naging minimum.

Ito ay isang problema sa linear programming. Ang paglutas ng problema (1*)–(2*), makuha namin ang pinakamainam na solusyon at pinakamainam na diskarte .

Upang matukoy ang pinakamainam na diskarte, dapat itong isaalang-alang na ang player SA naglalayong bawasan ang garantisadong kabayaran, ibig sabihin. hanapin ang max. Ang mga variable ay nagbibigay-kasiyahan sa mga hindi pagkakapantay-pantay

na sumusunod mula sa katotohanan na ang average na pagkawala ng isang manlalaro SA hindi lalampas sa halaga ng laro, kahit anong purong diskarte ang ginagamit ng manlalaro A.

Kung ipahiwatig natin ang (4*) , pagkatapos ay makakakuha tayo ng isang sistema ng hindi pagkakapantay-pantay:

Ang mga variable ay nakakatugon sa kondisyon.

Ang laro ay nabawasan sa susunod na gawain.

Tukuyin ang Variable Values , na nagbibigay-kasiyahan sa sistema ng hindi pagkakapantay-pantay (5*)At i-maximize ang linear function

Ang solusyon ng problema sa linear programming (5*), (6*) ay tumutukoy sa pinakamainam na diskarte. Kasabay nito, ang presyo ng laro. (7*)

Ang pagkakaroon ng pinagsama-samang mga pinahabang matrice para sa mga problema (1*), (2*) at (5*), (6*), tinitiyak namin na ang isang matrix ay nakuha mula sa isa pa sa pamamagitan ng transposisyon:

Kaya, ang mga problema sa linear programming (1*), (2*) at (5*), (6*) ay dalawahan. Malinaw, kapag tinutukoy ang pinakamainam na estratehiya sa mga partikular na problema, dapat pumili ang isa sa magkabilang dalawahang problema, ang solusyon na hindi gaanong matrabaho, at hanapin ang solusyon ng iba pang problema gamit ang duality theorems.

Kapag nilulutas ang isang di-makatwirang laro na may sukat na m×n, inirerekumenda na sumunod sa sumusunod na pamamaraan:

1. Ibukod ang malinaw na hindi kumikitang mga diskarte mula sa payoff matrix kumpara sa iba pang mga diskarte. Ang ganitong mga diskarte para sa manlalaro A

pananaliksik sa pagpapatakbo) - isang medyo bagong lugar, isang maikling kasaysayan kung saan bumalik sa simula ng World War II. Ang eksaktong banig na ito. ang agham ay naglalaman ng isang mahusay na tinukoy na hanay ng mga pangkalahatang prinsipyo, ang to-rye ay nagbibigay sa mga mananaliksik ng isang plano para sa pagpapatupad ng mga operasyon ng siyentipikong pananaliksik. Kabilang dito ang mga sumusunod na yugto. 1. Pagbubuo ng problema. 2. Paggawa ng banig. modelong kumakatawan sa sistemang pinag-aaralan. 3. Pagkuha ng solusyon mula sa modelong ito. 4. Sinusuri ang modelo at ang solusyon na nakuha mula dito. 5. Pagtatatag ng kontrol sa desisyon. 6. Prakt. pagpapatupad ng solusyon: pagpapatupad. Pagbubuo ng problema Kailangang bigyan ng seryosong pansin ang pagtukoy sa pangkalahatang katangian ng problema at, higit sa lahat, ang mga layunin ng pananaliksik. Ang mga layuning ito ay dapat na bumalangkas sa mga tuntunin ng pag-uugali upang mabawasan o maalis ang kalabuan at kawalan ng katiyakan. Dapat ding bigyan ng oras ang tamang pag-priyoridad ng mga layunin na makatotohanang makakamit. Masyadong mahaba ang isang listahan ng mga layunin ay maaaring magdulot ng mga potensyal na paghihirap sa kanilang pagpapatupad, lalo na kung ang mga layuning ito ay hindi malinaw na nakaugnay sa isang lohikal na pagkakasunud-sunod. Pagbuo ng isang modelong matematikal Ang ikalawang yugto ng pananaliksik na may t. sp. At tungkol sa. nagmumungkahi ng paglalarawan ng modelo. Ang layunin ng modelo ay upang kumatawan sa totoong mundo. Sa I. o. ang mga naturang modelo ay simboliko, na ipinahayag sa banig. mga tuntunin. Ang klasikal na equation na E \u003d mc2 ay isang tipikal na halimbawa ng isang banig. mga modelo. Ang mga tradisyunal na anyo para sa gayong mga modelo ay mga algebraic equation, to-rye hindi lamang val. mas matipid kaysa sa mga pormulasyon sa salita, ngunit nangangailangan din ng kumpleto at katumpakan ng depinisyon na kinakailangan para sa isang malinaw na pagpapahayag at pag-unawa sa mga indibidwal na elemento at ang kanilang mga relasyon. Ang pinakamahalagang gawain sa pagbuo ng gayong modelo ay ang malinaw at tumpak na pag-unlad at kahulugan ng layunin na pag-andar. Ang function na ito ay nagpapahayag ng relasyon sa pagitan ng mga independiyente at umaasa na mga variable. Pagkuha ng Solusyon mula sa Ibinigay na Modelo Ang ikatlong yugto ay ang paghahanap ng solusyon. Bilang isang tuntunin, ito ay kanais-nais na makahanap ng isang pinakamainam o mas mahusay na solusyon, ngunit dapat itong isaalang-alang na ang gayong solusyon ay magkakaroon lamang ng halaga sa konteksto ng modelong isinasaalang-alang. Dahil ang modelo ay representasyon lamang ng totoong problema sa mundo, maraming sitwasyon kung saan ang pinakamainam na solusyon ay maaaring hindi nauugnay sa pinakamahusay na pagpipilian. Gayunpaman, kapag ang pinakamainam na solusyon ay pinagsama sa hindi gaanong pinakamainam o mas makatotohanang mga alternatibong solusyon, na may posibilidad ng kanilang kasunod na pagsubok na may kaugnayan sa isang tunay na problema, ang paggamit ng pinakamainam na solusyon ay nangangailangan ng ilang mga benepisyo. Ang isang ganoong benepisyo ay nauugnay sa kahulugan sa pagtatapos ng pag-aaral. ang relatibong distansya sa pagitan ng perpektong solusyong ito at ng tinatanggap na alternatibo. Ang isang by-product ng pamamaraang ito ay ang paggamit ng I. o. ay ang pag-aakala na ang hindi gaanong pinakamainam na mga solusyon ay makikita bilang mga hakbang sa daan patungo sa pagkamit ng layunin. Ang pamamaraang ito ng sunud-sunod na pagtatantya ay maaaring humantong sa mga operations researcher sa mas mabungang mga resulta. Maraming banig. mga pamamaraan para sa pagkuha ng mga solusyon sa I. o. Ang mga pamamaraang ito ay batay sa mga aplikasyon ng teorya ng posibilidad. Ang pagpapatunay ng modelo at ang solusyon na hinango mula dito Ang pagpapatunay ng modelo at ang solusyon ay nauugnay sa pagpapatupad ng dalawang hakbang. Ang una ay binubuo sa isang masusing pagsusuri ng lahat ng mga elemento ng modelo, kasama. muling suriin ang mga algebraic na salik nito para sa pagkakaroon ng mga simplistic cosmetic error, na maaaring makaapekto sa bisa. Sinabi ni Dr. Ang isang mas mahalagang hakbang ay nagsasangkot ng muling pagtukoy sa kaugnayan ng modelo sa mga pagpapalagay na orihinal na ginamit upang bumuo ng modelong ito. Kasama rin sa mas sistematikong plano sa pagsusuri ang paggamit ng ist. data na madaling maipasok sa modelo upang makakuha ng isang prototype na solusyon. Ang mga datos na ito ay dapat na maingat na suriin upang matiyak ang bisa ng tseke sa operations researcher. Dapat pansinin na sa sandaling ang modelong ito ay praktikal na binuo batay sa mga nakaraang mapagkukunan. data at mga pangangailangan, maaari itong maging ibang-iba sa hinaharap. Sinabi ni Dr. isang karaniwang pagkakamali ay ang pagpapakilala ng mga kadahilanan sa modelo, ang to-rye ay hindi ipinakita sa ist. database. Pagtatatag ng kontrol Ang ikalimang yugto, ang pagtatatag ng kontrol sa desisyon, ay lilitaw sa kurso ng paulit-ulit na paggamit ng modelo. Ang kontrol sa modelo ay itinatag kapag pinahihintulutan ng operations researcher ang mga pagkakaiba sa mga halaga ng ist. data at kinikilala na ang mga pagkakaibang ito ay maaaring makaapekto sa mga ugnayan sa pagitan ng mga elemento ng modelo at ang mga resultang solusyon. Sinabi ni Dr. Ang isang mahalagang hakbang ay maaaring ang pagbuo ng mga paghihigpit sa mga napiling base. mga parameter ng modelo upang magtatag ng isang hanay ng mga katanggap-tanggap na halaga batay sa totoong data. Pagpapatupad ng Modelo Ang huling hakbang ay ang pagpasok ng totoong data sa modelo. Prakt. ang pagpapatupad ng modelo ay nauugnay sa malinaw na hakbang ng pagpapakilala ng totoong data at pagkuha ng solusyon sa isang tunay na problema. Bilang karagdagan, mahalaga din na masuri ang kalapitan ng tunay na solusyon sa ist. ang mga solusyon na nakuha nang mas maaga, pati na rin ang mga kahihinatnan ng desisyong ito para sa pagpapabuti ng paraan ng paggamit ng modelo. Ang mga hakbang na ito ay nagbibigay ng mahalagang ugnayan sa pagitan ng banig. kalikasan I. o. at magsanay. resulta ng pananaliksik. Sa huli, ang mga pagpapasyang ito at ang kanilang mga implikasyon sa pamamahala ay ginagamit ng isang may karanasang espesyalista sa AI. upang pinuhin ang modelo para sa posibleng paggamit sa hinaharap. Tingnan din ang Metodolohiya ng (siyentipikong) pananaliksik R. S. Endrulis