Pangunahing konsepto ng pananaliksik sa pagpapatakbo. Pananaliksik sa pagpapatakbo Solusyon sa laro sa magkahalong diskarte
SA. Slinkin
Textbook para sa mga mag-aaral ng mga unibersidad ng pedagogical
majoring sa Informatics
Shadrinsk, 2003
Slinkina I.N.
Pananaliksik sa pagpapatakbo. Tulong sa pagtuturo. - Shadrinsk: publishing house ng Shadrinsk State Pedagogical Institute, 2002. - 106 p.
Slinkina I.N. - kandidato ng pedagogical sciences
Ang aklat-aralin ay nagpapakita ng teoretikal na bahagi ng kursong "Pananaliksik sa Operasyon". Ito ay inilaan para sa mga mag-aaral ng full-time at part-time na mga departamento ng faculties na nagpapatupad ng specialty na "Informatics".
© Shadrinsky State Pedagogical Institute
© Slinkina I.N., 2002
Mga tanong sa mga bloke sa kursong "Pananaliksik sa Operasyon" 5
1.1. Ang paksa at layunin ng operations research 7
1.2. Pangunahing konsepto at prinsipyo ng operations research 8
1.3. Mga modelong matematikal ng mga operasyon 10
1.4. Pag-unawa sa Linear Programming 12
1.5. Mga halimbawa ng mga problemang pang-ekonomiya ng linear programming. Ang problema ng pinakamahusay na paggamit ng mga mapagkukunan 13
1.6. Mga halimbawa ng mga problemang pang-ekonomiya ng linear programming. Ang problema sa pagpili ng pinakamainam na teknolohiya 15
1.7. Mga halimbawa ng mga problemang pang-ekonomiya ng linear programming. Problema sa timpla 16
1.8. Mga halimbawa ng mga problemang pang-ekonomiya ng linear programming. Gawain sa transportasyon 17
1.9. Mga pangunahing uri ng pagsulat ng mga problema sa linear programming 19
1.10. Mga paraan ng conversion 21
1.11. Transition sa canonical form 22
1.12. Paglipat sa simetriko na notasyon 25
2.1. Geometric na interpretasyon ng isang linear programming problem 28
2.2. Paglutas ng mga Problema sa Linear Programming sa Graphic na paraan 29
2.3. Mga Katangian ng Mga Solusyon sa Problema sa Linear Programming 34
2.4. Pangkalahatang ideya ng simplex na pamamaraan 35
2.5. Pagbuo ng isang paunang sangguniang plano para sa paglutas ng mga problema sa linear programming gamit ang simplex na pamamaraan 36
2.6. Isang tanda ng pagiging mahusay ng pangunahing plano. Simplex na mga talahanayan 40
2.7. Paglipat sa isang hindi pinakamasamang reference na plano. 44
2.8. Mga pagbabagong simplex 46
2.9. Alternatibong pinakamabuting kalagayan (isang tanda ng kawalang-hanggan ng hanay ng mga sangguniang plano) 51
2.10. Ang tanda ng walang hangganan ng layuning pag-andar 52
2.11. Ang konsepto ng pagkabulok. Monotonicity at finiteness ng simplex method. Pag-looping 53
2.12. Ang konsepto ng duality para sa simetriko linear programming problema 54
3.1. Asymmetric Dual Problema 57
3.2. Bukas at saradong mga modelo ng problema sa transportasyon 61
3.3. Konstruksyon ng paunang pangunahing plano. Northwest Corner Rule 63
3.4. Konstruksyon ng paunang pangunahing plano. Minimum na tuntunin ng elemento 64
3.5. Konstruksyon ng paunang pangunahing plano. Paraan ng Vogel 64
3.6. Potensyal na paraan 65
3.7. Paglutas ng mga Problema sa Transportasyon na may Mga Limitasyon sa Bandwidth 69
3.8. Mga halimbawa ng mga problema sa discrete programming. Ang problema sa transportasyon ng lalagyan. Problema sa takdang-aralin 71
3.9. Ang kakanyahan ng mga discrete optimization na pamamaraan 72
3.10. Problema sa Convex Programming 74
3.11. Paraan ng Lagrange multiplier 75
3.12. Mga pamamaraan ng gradient 77
4.1. Mga pamamaraan ng parusa at mga gawaing hadlang 78
4.2. Dynamic na programming. Pangunahing konsepto. Kakanyahan ng mga pamamaraan ng solusyon 79
4.3. Stochastic programming. Pangunahing konsepto 81
4.4. Zero-sum matrix na laro 83
4.5. Dalisay at halo-halong estratehiya at ang kanilang mga katangian 85
4.6. Mga katangian ng dalisay at pinaghalong estratehiya 88
4.7. Pagbawas ng isang matrix game sa ZLP 92
4.8. Mga gawain ng teorya ng pagpila. Pag-uuri ng mga sistema ng pagpila 94
4.9. Mga stream ng kaganapan 96
4.10. Scheme ng kamatayan at pagpaparami 97
4.11. Maliit na Formula 99
4.12. Ang pinakasimpleng sistema ng pagpila 101
Mga tanong sa mga bloke sa kursong "Pananaliksik sa Operasyon"
Block 1
1. Paksa at mga gawain ng pananaliksik sa pagpapatakbo.
2. Pangunahing konsepto at prinsipyo ng operations research.
3. Mga modelong matematikal ng mga operasyon.
4. Ang konsepto ng linear programming.
5. Mga halimbawa ng mga problemang pang-ekonomiya ng linear programming. Gawain
6. Mga halimbawa ng mga problemang pang-ekonomiya ng linear programming. Ang problema sa pagpili ng pinakamainam na teknolohiya.
7. Mga halimbawa ng mga problemang pang-ekonomiya ng linear programming. Problema sa timpla.
8. Mga halimbawa ng mga problemang pang-ekonomiya ng linear programming. gawain sa transportasyon.
9. Mga pangunahing uri ng pagsulat ng mga problema sa linear programming.
10. Paraan ng pagbabago.
11. Transition sa canonical form.
12. Transition sa simetriko notasyon.
Block 2
1. Geometric na interpretasyon ng linear programming problem.
2. Paglutas ng mga problema ng linear programming sa pamamagitan ng graphical na pamamaraan.
3. Mga katangian ng mga solusyon sa isang linear na problema sa programming.
4. Pangkalahatang ideya ng simplex na paraan.
5. Konstruksyon ng paunang pangunahing plano para sa paglutas ng mga problema ng linear programming sa pamamagitan ng simplex na pamamaraan.
6. Tanda ng pinakamainam ng pangunahing plano. Simplex na mga talahanayan.
7. Paglipat sa isang hindi pinakamasamang reference na plano.
8. Mga pagbabagong simplex.
9. Alternatibong pinakamabuting kalagayan (isang tanda ng kawalang-hanggan ng hanay ng mga sangguniang plano).
10. Tanda ng unboundedness ng layunin function.
11. Ang konsepto ng pagkabulok. Monotonicity at finiteness ng simplex method. Looping.
12. Ang konsepto ng duality para sa simetriko linear programming problema.
Block 3
1. Asymmetric dual problema.
2. Bukas at saradong mga modelo ng problema sa transportasyon.
3. Konstruksyon ng paunang pangunahing plano. Panuntunan sa hilagang-kanlurang sulok.
4. Konstruksyon ng paunang pangunahing plano. Minimum na panuntunan ng elemento.
5. Konstruksyon ng paunang pangunahing plano. Paraan ng Vogel.
6. Paraan ng mga potensyal.
7. Paglutas ng mga problema sa transportasyon na may limitadong bandwidth.
8. Mga halimbawa ng mga problema sa discrete programming. Ang problema sa transportasyon ng lalagyan. Takdang-aralin.
9. Kakanyahan ng mga discrete optimization method.
10. Ang problema ng convex programming.
11. Paraan ng Lagrange multipliers.
12. Mga pamamaraan ng gradient.
Block 4
1. Paraan ng mga pagpapaandar ng parusa at hadlang.
2. Dynamic na programming. Pangunahing konsepto. Kakanyahan ng mga pamamaraan ng solusyon.
3. Stochastic programming. Pangunahing konsepto.
4. Matrix laro na may zero sum.
5. Puro at halo-halong estratehiya.
6. Mga katangian ng dalisay at halo-halong estratehiya.
7. Pagbawas ng larong matrix sa LLP
8. Mga problema ng teorya ng pagpila. Pag-uuri ng mga sistema ng pagpila.
9. Daloy ng mga pangyayari.
10. Scheme ng kamatayan at pagpaparami.
11. Maliit na formula.
12. Ang pinakasimpleng sistema ng pagpila.
Block 1.
Ang paksa at layunin ng pananaliksik sa pagpapatakbo
Ang kasalukuyang estado ng agham at teknolohiya, lalo na, ang pag-unlad ng mga tool sa computer para sa pagkalkula at pagpapatibay ng matematika ng mga teorya ay naging posible upang makabuluhang pasimplehin ang solusyon ng maraming mga problema na ibinabanta sa iba't ibang sangay ng agham. Marami sa mga problema ay bumaba sa paglutas ng isyu ng pag-optimize ng produksyon, pinakamainam na kontrol sa proseso.
Ang mga pangangailangan ng pagsasanay ay nagbigay-buhay sa mga espesyal na pang-agham na pamamaraan, na maginhawang pinagsama-sama sa ilalim ng pangalang "pananaliksik sa operasyon".
Kahulugan: Sa pamamagitan ng pagsasaliksik ng operasyon mauunawaan natin ang paggamit ng mga pamamaraang matematikal at dami upang bigyang-katwiran ang mga desisyon sa lahat ng larangan ng may layuning aktibidad ng tao.
Hayaang gumawa ng ilang aksyon upang makamit ang isang tiyak na layunin. Ang tao (o grupo ng mga tao) na nag-aayos ng kaganapan ay palaging may ilang kalayaan sa pagpili: maaari itong ayusin sa isang paraan o iba pa. Ang desisyon ay ilang pagpipilian mula sa ilang mga opsyon na magagamit ng organizer.
Ang pangangailangang gumawa ng mga desisyon at subukan ang iminungkahing hypothesis ng desisyon ay mathematically na nakumpirma ng mga sumusunod na halimbawa:
Gawain 1. Tungkol sa pinakamahusay na paggamit ng mga mapagkukunan.
Ang kumpanya ay gumagawa ng ilang uri ng mga produkto. Para sa kanilang paggawa, ang ilang mga mapagkukunan ay ginagamit (kabilang ang tao, enerhiya, atbp.). Kinakailangang kalkulahin kung paano planuhin ang gawain ng negosyo upang ang halaga ng mga mapagkukunan ay minimal at ang kita ay maximum.
Gawain 2. Tungkol sa mga mixtures.
Ito ay kinakailangan upang maghanda ng isang halo na may ilang mga katangian. Upang gawin ito, maaari mong gamitin ang ilang "mga produkto" (para sa pagkalkula ng mga diyeta - pagkain, para sa mga pinaghalong feed - pagkain para sa mga hayop, para sa mga teknikal na mixtures - mga haluang metal, mga likido para sa mga teknikal na layunin). ang gawain ay piliin ang pinakamainam na halaga ng mga produkto (para sa presyo) upang makuha ang pinakamainam na halaga ng pinaghalong.
Gawain 3. gawain sa transportasyon.
Mayroong isang network ng mga negosyo na gumagawa ng parehong uri ng mga produkto ng parehong kalidad at isang network ng mga mamimili ng mga produktong ito. Ang mga mamimili at mga supplier ay konektado sa pamamagitan ng komunikasyon (mga kalsada, mga linya ng tren, mga linya ng hangin). Natutukoy ang mga taripa sa transportasyon. Kinakailangang kalkulahin ang pinakamainam na plano para sa transportasyon ng mga produkto upang ang mga gastos sa transportasyon ay minimal, ang mga kahilingan ng lahat ng mga mamimili ay nasiyahan, at ang lahat ng mga kalakal ay na-export mula sa mga supplier.
Sa bawat isa sa mga halimbawa sa itaas, pinag-uusapan natin ang ilang uri ng kaganapan na humahabol sa isang partikular na layunin. Ang ilang mga kondisyon ay ibinigay na nagpapakilala sa sitwasyon (sa partikular, ang mga paraan na maaaring itapon). Sa loob ng balangkas ng mga kundisyong ito, kinakailangan na gumawa ng ganoong desisyon na ang nakaplanong kaganapan ay magiging mas kumikita.
Alinsunod sa mga pangkalahatang tampok na ito, ang mga pangkalahatang pamamaraan para sa paglutas ng mga naturang problema ay binuo din, na magkakasamang bumubuo sa pamamaraan ng pamamaraan at kagamitan ng pananaliksik sa operasyon.
Sa kasalukuyan, malawakang ginagamit ang mga automated control system (ACS) batay sa paggamit ng teknolohiya ng computer. Ang paglikha ng isang awtomatikong sistema ng kontrol ay imposible nang walang paunang pagsusuri sa kinokontrol na proseso sa pamamagitan ng mga pamamaraan ng pagmomolde ng matematika. Sa paglaki ng sukat at pagiging kumplikado ng mga kaganapan, ang mga pamamaraan ng matematika para sa pagbibigay-katwiran sa mga desisyon ay lalong nagiging mahalaga.
Mga pangunahing konsepto at prinsipyo ng pagsasaliksik sa pagpapatakbo
Kahulugan: Ang operasyon ay anumang kaganapan (sistema ng mga aksyon) na pinagsama ng isang plano at nakadirekta sa pagkamit ng ilang layunin.
Ang isang operasyon ay palaging isang kinokontrol na kaganapan, i.e. depende ito sa mga kalkulasyon kung paano pipiliin ang 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.
Kahulugan: Anumang tiyak na pagpipilian depende sa mga parameter ng desisyon ay tinatawag na isang desisyon.
Kahulugan: Ang mga pinakamainam na solusyon ay ang mga mas gusto kaysa sa iba para sa isang kadahilanan o iba pa.
Layunin ng Operations Research– preliminary quantitative substantiation ng pinakamainam na solusyon.
Minsan, bilang isang resulta ng pag-aaral, posible na magpahiwatig ng isang solong, mahigpit na tinukoy na solusyon; mas madalas, posible na tukuyin ang isang lugar ng halos katumbas na pinakamainam na mga solusyon sa loob kung saan ang isang pangwakas na pagpipilian ay maaaring gawin.
Ang mismong paggawa ng desisyon ay lumalampas sa saklaw ng pagsasaliksik sa pagpapatakbo at kabilang sa kakayahan ng isang responsableng tao, mas madalas isang grupo ng mga tao na binibigyan ng karapatang gumawa ng pangwakas na pagpili at kung sino ang may pananagutan sa pagpili na ito.
Kahulugan: Ang mga parameter, 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. Para sa pagiging simple, ang buong hanay ng mga elemento ng solusyon ay ilalarawan ng x.
Bilang karagdagan sa mga elemento ng solusyon sa anumang gawain ng pananaliksik sa operasyon, mayroon ding mga ibinigay na kondisyon na naayos sa kondisyon ng problema at hindi maaaring labagin. Sa partikular, ang mga naturang kundisyon ay kinabibilangan ng mga paraan (materyal, teknikal, tao) na maaaring itapon, at iba pang mga paghihigpit na ipinataw sa solusyon. Sa kanilang kabuuan, bumubuo sila ng tinatawag na "set of possible solutions". Tukuyin natin itong set X, at ang katotohanan na ang solusyon x ay kabilang sa set na ito, isusulat natin: хОХ.
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 performance indicator (objective function). Ang tagapagpahiwatig na ito ay pinili upang ito ay sumasalamin sa target na oryentasyon ng operasyon. Ang pinakamahusay na solusyon ay isasaalang-alang ang isa na nag-aambag sa pagkamit ng layunin sa pinakamataas na lawak. Upang piliin ang tagapagpahiwatig ng pagganap Z, kailangan mo munang matukoy kung ano ang dapat humantong sa solusyon ng problema. Kapag pumipili ng solusyon, ibinibigay ang kagustuhan sa isa na nagpapalit ng tagapagpahiwatig ng kahusayan ng Z sa 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.
Kadalasan, ang operasyon ay sinamahan ng pagkilos ng mga random na kadahilanan: "whims" ng kalikasan, 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 (pang-matematika na inaasahan) ay kinuha bilang isang tagapagpahiwatig ng kahusayan.
Ang gawain ng pagpili ng isang tagapagpahiwatig ng pagganap ay malulutas para sa bawat problema nang paisa-isa.
Gawain 1. Tungkol sa pinakamahusay na paggamit ng mga mapagkukunan.
Ang gawain ng operasyon ay upang makabuo ng maximum na dami ng mga kalakal. Ang tagapagpahiwatig ng kahusayan Z ay ang kita mula sa pagbebenta ng mga kalakal sa pinakamababang halaga ng mga mapagkukunan (max Z).
Gawain 2. Tungkol sa mga mixtures.
Ang isang natural na tagapagpahiwatig ng kahusayan, na iminungkahi ng pagbabalangkas ng problema, ay ang presyo ng mga produkto na kinakailangan para sa pinaghalong, sa kondisyon na ang mga tinukoy na katangian ng pinaghalong (min Z) ay dapat na mapanatili.
Gawain 3. gawain sa transportasyon.
Ang gawain ng operasyon ay upang matiyak ang supply ng mga kalakal sa mga mamimili sa kaunting gastos sa transportasyon. Ang tagapagpahiwatig ng kahusayan Z ay ang kabuuang halaga ng pagdadala ng mga kalakal sa bawat yunit ng oras (min Z).
1. Ang paksa at layunin ng pag-aaral ng mga operasyon sa ekonomiya. Mga pangunahing konsepto ng teorya ng pananaliksik sa pagpapatakbo.
Ang paksa ng pananaliksik sa pagpapatakbo ay mga sistema ng pamamahala ng organisasyon o mga organisasyon na binubuo ng malaking bilang ng mga nakikipag-ugnayang unit na hindi palaging pare-pareho sa isa't isa at maaaring magkasalungat.
Ang layunin ng pananaliksik sa pagpapatakbo ay upang patunayan ang dami ng mga desisyong ginawa sa pamamahala ng mga organisasyon
Ang solusyon na lumalabas na pinaka-kapaki-pakinabang para sa buong organisasyon ay tinatawag na pinakamainam, at ang solusyon na pinaka-kapaki-pakinabang sa isa o higit pang mga departamento ay magiging suboptimal.
Ang pananaliksik sa operasyon ay isang agham na tumatalakay sa pagbuo at praktikal na aplikasyon ng mga pamamaraan para sa pinakamainam na pamamahala ng mga sistema ng organisasyon.
Ang operasyon ay anumang kaganapan (sistema ng mga aksyon) na pinagsama ng isang plano at nakadirekta sa pagkamit ng ilang layunin.
Ang layunin ng operations research ay isang paunang dami ng pagbibigay-katwiran ng pinakamainam na solusyon.
Anumang tiyak na pagpili ng mga parameter na depende sa atin ay tinatawag na solusyon. Ang mga solusyon ay tinatawag na pinakamainam kung sila ay ginustong kaysa sa iba para sa isang kadahilanan o iba pa.
Ang mga parameter, ang kabuuan kung saan bumubuo ng isang solusyon, ay tinatawag na mga elemento ng solusyon.
Ang hanay ng mga tinatanggap na solusyon ay binibigyan ng mga kundisyon na naayos at hindi maaaring labagin.
Performance indicator - isang quantitative measure na nagbibigay-daan sa iyo upang ihambing ang iba't ibang mga solusyon sa mga tuntunin ng kahusayan.
2. Ang konsepto ng pagpaplano at pamamahala ng network. Modelo ng network ng proseso at mga elemento nito.
Ang paraan ng pagtatrabaho sa mga network graph - pagpaplano ng network - ay batay sa teorya ng graph. Isinalin mula sa Griyego, ang isang graph (grafpho - sinusulat ko) ay kumakatawan sa isang sistema ng mga puntos, na ang ilan ay konektado sa pamamagitan ng mga linya - mga arko (o mga gilid). Ito ay isang topological (matematika) na modelo ng mga sistemang nakikipag-ugnayan. Sa tulong ng mga graph, posible na malutas hindi lamang ang mga problema sa pagpaplano ng network, kundi pati na rin ang iba pang mga problema. Ang paraan ng pagpaplano ng network ay ginagamit kapag nagpaplano ng isang kumplikadong mga magkakaugnay na gawain. Ito ay nagbibigay-daan sa iyo upang mailarawan ang organisasyonal at teknolohikal na pagkakasunud-sunod ng trabaho at itatag ang relasyon sa pagitan nila. Bilang karagdagan, pinapayagan ka nitong i-coordinate ang mga operasyon na may iba't ibang antas ng pagiging kumplikado at tukuyin ang mga operasyon kung saan nakasalalay ang tagal ng buong trabaho (i.e. kaganapan sa organisasyon), pati na rin tumuon sa napapanahong pagkumpleto ng bawat operasyon.
Ang batayan ng pagpaplano at pamamahala ng network ay ang modelo ng network (SM), na nagmomodelo ng isang hanay ng mga magkakaugnay na aktibidad at kaganapan na sumasalamin sa proseso ng pagkamit ng isang tiyak na layunin. Maaari itong ipakita sa anyo ng isang graph o isang talahanayan.
Mga pangunahing konsepto ng modelo ng network:
Kaganapan, trabaho, paraan.
Ang mga kaganapan ay ang mga resulta ng pagsasagawa ng isa o higit pang mga aktibidad. Wala silang extension sa oras.
Ang isang landas ay isang hanay ng trabaho na sumusunod sa isa't isa, na nag-uugnay sa paunang at panghuling mga vertex.
Ang tagal ng isang landas ay tinutukoy ng kabuuan ng mga tagal ng mga bumubuo nitong gawa.
3. Pagbuo at pag-order ng network diagram.
Ang isang modelo ng network ay ginagamit bilang isang modelo na sumasalamin sa mga teknolohikal at pang-organisasyong interrelasyon ng proseso ng pagtatayo at pag-install ng mga gawain sa pagpaplano ng network at mga sistema ng pamamahala (SPU).
Ang isang modelo ng network ay isang graphical na representasyon ng mga proseso, ang pagpapatupad nito ay humahantong sa pagkamit ng isa o higit pang mga layunin, na nagpapahiwatig ng itinatag na mga relasyon sa pagitan ng mga prosesong ito. Ang network diagram ay isang modelo ng network na may mga kalkuladong parameter ng oras.
Ang istraktura ng network diagram, na tumutukoy sa mutual dependence ng trabaho at mga kaganapan, ay tinatawag na topology nito.
Ang trabaho ay isang proseso ng produksyon na nangangailangan ng oras, paggawa at materyal na mapagkukunan, na, kapag ginanap, ay humahantong sa pagkamit ng ilang mga resulta.
Ang pag-asa (fictitious work) na hindi nangangailangan ng oras ay inilalarawan ng isang tuldok na arrow. Ginagamit ang dummy work sa isang network diagram upang ipakita ang mga ugnayan sa pagitan ng mga kaganapan at aktibidad.
Sa iskedyul ng network, oras, gastos at iba pang mga katangian ng trabaho ang ginagamit.
Tagal ng trabaho - ang oras ng pagpapatupad ng gawaing ito sa mga araw ng trabaho o iba pang mga yunit ng oras, pareho para sa lahat ng trabaho sa network. Ang tagal ng trabaho ay maaaring alinman sa isang tiyak (deterministic) o isang random na variable na tinukoy ng batas ng pamamahagi nito.
Ang halaga ng trabaho ay ang mga direktang gastos na kinakailangan para sa pagpapatupad nito, depende sa tagal at kondisyon ng gawaing ito.
Ang mga mapagkukunan ay nailalarawan sa pamamagitan ng pangangailangan para sa mga pisikal na yunit na kinakailangan upang maisagawa ang gawaing ito.
Ang kalidad, pagiging maaasahan at iba pang mga tagapagpahiwatig ng trabaho ay nagsisilbing mga karagdagang katangian ng trabaho.
Ang kaganapan ay ang katunayan ng pagkumpleto ng isa o higit pang mga trabaho, kinakailangan at sapat para sa pagsisimula ng isa o higit pang mga kasunod na trabaho. Ang bawat kaganapan ay itinalaga ng isang numero, na tinatawag na isang code. Ang bawat trabaho ay tinutukoy ng dalawang kaganapan: isang code ng panimulang kaganapan, na tinutukoy ng i, at isang code ng pagtatapos ng kaganapan, na tinutukoy ng j.
Ang mga kaganapang walang mga nakaraang aktibidad ay tinatawag na mga paunang kaganapan; mga kaganapan na walang kasunod - pangwakas.
1 Ang direksyon ng pagbuo ng isang network ay maaaring magkaiba. Maaaring buuin ang isang network graph mula sa paunang kaganapan hanggang sa pangwakas at mula sa pangwakas hanggang sa inisyal (inisyal), gayundin mula sa alinman sa mga kaganapan hanggang sa una o panghuling isa.
2 Kapag bumubuo ng isang network, ang mga sumusunod na katanungan ay malulutas:
Anong gawain (trabaho) ang kailangang gawin upang simulan ang gawaing ito;
Anong gawain ang dapat gawin kasabay ng gawaing ito;
3 Ang paunang iskedyul ng network ay binuo nang hindi isinasaalang-alang ang tagal ng mga aktibidad na bumubuo sa network.
4 Ang anyo ng graph ay dapat na simple at madaling makita.
5 Sa pagitan ng dalawang kaganapan ay maaari lamang magkaroon ng isang gawain. Sa panahon ng pagtatayo ng mga gusali at istruktura, ang trabaho ay maaaring isagawa nang sunud-sunod, kahanay o sabay-sabay, ang ilan sa serye at ang ilan ay kahanay, bilang isang resulta kung saan ang iba't ibang mga dependency ay nabuo sa pagitan ng mga indibidwal na gawa.
Isinasagawa ang pagnunumero (coding) ng mga kaganapan pagkatapos makumpleto ang pagtatayo ng network, simula sa paunang kaganapan hanggang sa huling kaganapan.
4. Kritikal na landas ng network diagram. Mga reserbang oras. Maaga at huli na mga petsa ng mga kaganapan at aktibidad sa network diagram.
Sa isang network diagram, maaaring mayroong maraming mga landas sa pagitan ng mga kaganapan sa pagsisimula at pagtatapos. Ang landas na may pinakamahabang tagal ay tinatawag na kritikal na landas. Tinutukoy ng kritikal na landas ang kabuuang tagal ng mga aktibidad. Ang lahat ng iba pang mga landas ay may mas maikling tagal, at samakatuwid ang gawaing isinagawa sa kanila ay may mga reserbang oras.
Ang kritikal na landas ay ipinahiwatig sa diagram ng network sa pamamagitan ng makapal o dobleng linya (mga arrow).
Dalawang konsepto ang partikular na kahalagahan kapag gumuhit ng isang network diagram:
Maagang pagsisimula ng trabaho - ang panahon bago ito imposibleng simulan ang gawaing ito nang hindi lumalabag sa tinatanggap na teknolohikal na pagkakasunud-sunod. Ito ay tinutukoy ng pinakamahabang landas mula sa pagsisimula ng kaganapan hanggang sa pagsisimula ng gawaing ito.
Ang huling pagtatapos ay ang pinakahuling petsa ng pagtatapos para sa isang trabaho na hindi nagpapataas sa kabuuang tagal ng trabaho. Ito ay tinutukoy ng pinakamaikling landas mula sa isang naibigay na kaganapan hanggang sa pagkumpleto ng lahat ng gawain.
Ang maagang pagtatapos ay ang huling araw kung saan hindi matatapos ang trabaho. Ito ay katumbas ng maagang pagsisimula kasama ang tagal ng gawaing ito.
Late na pagsisimula - ang panahon pagkatapos kung saan imposibleng simulan ang gawaing ito nang hindi nadaragdagan ang kabuuang tagal ng konstruksiyon. Ito ay katumbas ng late finish na binawasan ang tagal ng ibinigay na trabaho.
Kung ang kaganapan ay ang pagtatapos ng isang trabaho lamang (iyon ay, isang arrow lamang ang nakadirekta dito), kung gayon ang maagang pagtatapos ng trabahong ito ay tumutugma sa maagang pagsisimula ng susunod.
Ang kabuuang (buong) reserba ay ang pinakamataas na oras kung saan ang pagsasagawa ng gawaing ito ay maaaring maantala nang hindi nadaragdagan ang kabuuang tagal ng trabaho. Ito ay tinutukoy ng pagkakaiba sa pagitan ng huli at maagang pagsisimula (o huli at maagang pagtatapos - na pareho).
Pribadong (libre) na reserba - ito ang pinakamataas na oras kung saan maaari mong antalahin ang pagsasagawa ng gawaing ito, nang hindi binabago ang maagang pagsisimula ng susunod. Ang fallback na ito ay posible lamang kapag ang kaganapan ay may kasamang dalawa o higit pang aktibidad (dependencies), i.e. dalawa o higit pang mga arrow (solid o tuldok) ang nakaturo dito. Pagkatapos ay isa lamang sa mga trabahong ito ang magkakaroon ng maagang pagtatapos na kasabay ng maagang pagsisimula ng kasunod na trabaho, habang para sa iba ay iba ang mga halaga nito. Ang pagkakaibang ito para sa bawat trabaho ay magiging pribadong reserba nito.
5. Dynamic na programming. Prinsipyo ni Bellman sa pagiging optimal at kontrol.
Ang dinamikong programming ay isa sa pinakamakapangyarihang mga diskarte sa pag-optimize. Ang mga gawain ng paggawa ng mga nakapangangatwiran na desisyon, pagpili ng pinakamahusay na mga pagpipilian, pinakamainam na kontrol ay hinarap ng mga espesyalista ng iba't ibang mga profile. Ang dinamikong programming ay sumasakop sa isang espesyal na posisyon sa mga pamamaraan ng pag-optimize. Ang pamamaraang ito ay lubhang kaakit-akit dahil sa pagiging simple at kalinawan ng pangunahing prinsipyo nito - ang prinsipyo ng pinakamainam. Ang saklaw ng aplikasyon ng prinsipyo ng optimality ay lubos na malawak, ang hanay ng mga problema kung saan maaari itong mailapat ay hindi pa ganap na nakabalangkas. Sa simula pa lang, ang dynamic na programming ay gumaganap bilang isang paraan ng praktikal na solusyon ng mga problema sa pag-optimize.
Bilang karagdagan sa prinsipyo ng pinakamainam, ang pangunahing pamamaraan ng pananaliksik, isang mahalagang papel sa aparato ng dynamic na programming ay nilalaro ng ideya ng paglubog ng isang tiyak na problema sa pag-optimize sa isang pamilya ng mga katulad na problema. Ang pangatlong tampok nito, na nagpapaiba nito sa iba pang mga paraan ng pag-optimize, ay ang anyo ng panghuling resulta. Ang aplikasyon ng prinsipyo ng optimality at ang prinsipyo ng paglulubog sa multi-step, discrete na mga proseso ay humahantong sa paulit-ulit na functional equation na may paggalang sa pinakamainam na halaga ng kalidad na pamantayan. Ang mga resultang equation ay ginagawang posible na sunud-sunod na isulat ang pinakamainam na mga kontrol para sa orihinal na problema. Ang kalamangan dito ay ang gawain ng pagkalkula ng kontrol para sa buong proseso ay nahahati sa isang bilang ng mga mas simpleng gawain ng pagkalkula ng kontrol para sa mga indibidwal na yugto ng proseso.
Ang pangunahing disbentaha ng pamamaraan ay, sa mga salita ni Bellman, ang "sumpa ng dimensionality" - ang pagiging kumplikado nito ay tumataas nang sakuna sa pagtaas ng dimensionality ng problema.
6. Ang problema ng pamamahagi ng mga pondo sa pagitan ng mga negosyo.
Masasabi na ang pamamaraan para sa pagbuo ng isang pinakamainam na kontrol sa pamamagitan ng dynamic na pamamaraan ng programming ay nahahati sa dalawang yugto: paunang at pangwakas. Sa paunang yugto, para sa bawat hakbang, ang SOC ay tinutukoy depende sa estado ng system (nakamit bilang resulta ng mga nakaraang hakbang), at ang kondisyon na pinakamainam na pakinabang sa lahat ng natitirang hakbang, simula sa isang ito, ay nakasalalay din sa estado. Sa huling yugto, ang (walang kondisyon) na pinakamainam na kontrol para sa bawat hakbang ay tinutukoy. Ang paunang (kondisyon) na pag-optimize ay isinasagawa nang hakbang-hakbang sa reverse order: mula sa huling hakbang hanggang sa una; final (unconditional) optimization - sa pamamagitan din ng mga hakbang, ngunit sa natural na pagkakasunud-sunod: mula sa unang hakbang hanggang sa huli. Sa dalawang yugto ng pag-optimize, ang una ay hindi maihahambing na mas mahalaga at nakakaubos ng oras. Matapos ang pagtatapos ng unang yugto, ang pagpapatupad ng pangalawang yugto ay hindi nagpapakita ng kahirapan: ang natitira lamang ay "basahin" ang mga rekomendasyong inihanda na sa unang yugto.
7. Pahayag ng problema ng linear programming.
Ang linear programming ay isang tanyag na tool para sa paglutas ng mga problemang pang-ekonomiya na nailalarawan sa pagkakaroon ng isang criterion (halimbawa, upang mapakinabangan ang kita mula sa produksyon sa pamamagitan ng pinakamainam na pagpili ng isang programa sa produksyon, o, halimbawa, upang mabawasan ang mga gastos sa transportasyon, atbp.) . Ang mga gawaing pang-ekonomiya ay nailalarawan sa pamamagitan ng mga hadlang sa mapagkukunan (materyal at/o pinansyal). Ang mga ito ay isinulat bilang isang sistema ng mga hindi pagkakapantay-pantay, kung minsan bilang mga pagkakapantay-pantay.
Mula sa punto ng view ng pagtataya ng mga katanggap-tanggap na agwat ng presyo (o mga dami ng benta) sa loob ng balangkas ng isang pangkalahatang non-parametric na pamamaraan, ang paggamit ng linear programming ay nangangahulugang:
Ang criterion ay ang MAX na presyo ng susunod na produkto mula sa grupo ng interes f.
Ang kinokontrol na mga variable ay ang mga presyo ng lahat ng mga produkto mula sa pangkat f.
Ang mga limitasyon sa aming problema sa pagtataya gamit ang pangkalahatang nonparametric na pamamaraan ay:
a) isang sistema ng hindi pagkakapantay-pantay (mga hadlang sa pagiging makatwiran ng pag-uugali ng mamimili) (tingnan ang 4.2. Pagtataya sa loob ng balangkas ng isang pangkalahatang non-parametric na pamamaraan);
b) ang pangangailangan ng di-negatibiti ng mga kinokontrol na variable (sa aming problema sa pagtataya, kakailanganin namin na ang mga presyo para sa mga produkto mula sa pangkat f ay hindi bababa sa 80% ng mga presyo sa huling punto ng oras);
c) hadlang sa badyet sa anyo ng pagkakapantay-pantay - ang pangangailangan na ang halaga ng mga gastos para sa pagbili ng mga produkto mula sa pangkat f ay pare-pareho (isinasaalang-alang ang 15% inflation, halimbawa).
8. Graphical na paraan para sa paglutas ng mga problema sa linear programming.
Ang graphical na pamamaraan ay batay sa geometric na interpretasyon ng isang linear na problema sa programming at pangunahing ginagamit sa paglutas ng mga problema ng dalawang-dimensional na espasyo at ilang mga problema lamang ng tatlong-dimensional na espasyo, dahil ito ay medyo mahirap na bumuo ng isang solusyon na polytope na nabuo bilang resulta ng intersection ng kalahating espasyo. Ang gawain ng isang espasyo ng mga dimensyon na higit sa tatlo ay hindi maaaring katawanin sa graphic na paraan.
Hayaang maibigay ang problema sa linear programming sa isang dalawang-dimensional na espasyo, ibig sabihin, ang mga hadlang ay naglalaman ng dalawang variable.
Hanapin ang pinakamababang halaga ng isang function
(2.1) Z = С1х1+С2х2
a11x1 + a22x2 b1
(2.2)a21x1 + a22x2 b2
aM1x1 + aM2x2 bM
(2.3) x1 0, x2 0
Ipagpalagay natin na ang system (2.2) sa ilalim ng kondisyon (2.3) ay pare-pareho at ang polygon ng solusyon nito ay may hangganan. Ang bawat isa sa mga hindi pagkakapantay-pantay (2.2) at (2.3), tulad ng nabanggit sa itaas, ay tumutukoy sa isang kalahating eroplano na may mga hangganang linya: ai1x1 + ai2x2 + ai3x3 = bi,(i = 1, 2, ..., n), x1=0 , x2=0 . Ang linear function (2.1) para sa mga nakapirming halaga ng Z ay ang equation ng isang tuwid na linya: C1x1 + C2x2 = const. Bumuo tayo ng polygon ng mga solusyon sa constraint system (2.2) at isang graph ng linear function (2.1) para sa Z = 0 (Fig. 2.1). Pagkatapos ang ibinigay na problema ng linear programming ay maaaring ibigay ang sumusunod na interpretasyon. Hanapin ang punto ng solusyon polygon kung saan ang tuwid na linya C1x1 + C2x2 = const ay ang linya ng suporta at ang Z function ay umabot sa isang minimum.
Ang mga halaga ng Z = C1x1 + C2x2 ay tumaas sa direksyon ng vector N = (C1, C2), kaya inililipat namin ang linya Z = 0 parallel sa sarili nito sa direksyon ng vector X. Mula sa fig. 2.1 sumusunod na ang linyang dalawang beses ay nagiging sanggunian na may kinalaman sa polygon ng mga solusyon (sa mga puntong A at C), at ang pinakamababang halaga ay nasa punto A. Ang mga coordinate ng puntong A (x1, x2) ay matatagpuan sa pamamagitan ng paglutas ng sistema ng mga equation ng mga linyang AB at AE.
Kung ang polygon ng desisyon ay isang walang hangganang polygonal na lugar, posible ang dalawang kaso.
Kaso 1. Ang tuwid na linya na C1x1 + C2x2 = const, na gumagalaw sa direksyon ng vector N o sa tapat nito, ay patuloy na nagsasalubong sa polygon ng solusyon at hindi ito isang sanggunian sa anumang punto. Sa kasong ito, ang linear function ay walang hangganan sa solusyon polygon sa itaas at sa ibaba (Larawan 2.2).
Kaso 2. Ang tuwid na linya, gumagalaw, gayunpaman ay nagiging isang suporta na may kaugnayan sa polygon ng mga solusyon (Larawan 2.2, a - 2.2, c). Pagkatapos, depende sa uri ng lugar, ang isang linear na function ay maaaring bounded mula sa itaas at unbounded mula sa ibaba (Fig. 2.2, a), bounded mula sa ibaba at unbounded mula sa itaas (Fig. 2.2, b), o bounded pareho mula sa ibaba at mula sa itaas (Larawan 2.2, c).
9. Simplex na paraan.
Ang simplex na paraan ay ang pangunahing isa sa linear programming. Ang solusyon ng problema ay nagsisimula sa pagsasaalang-alang ng isa sa mga vertices ng mga kondisyon polyhedron. Kung ang vertex sa ilalim ng pag-aaral ay hindi tumutugma sa maximum (minimum), pagkatapos ay lumipat sila sa kalapit na isa, pinatataas ang halaga ng function ng layunin kapag nilutas ang problema sa maximum at bumababa kapag nilutas ang problema sa pinakamaliit. Kaya, ang paglipat mula sa isang vertex patungo sa isa pa ay nagpapabuti sa halaga ng function ng layunin. Dahil ang bilang ng mga vertices ng polyhedron ay limitado, pagkatapos ay sa isang tiyak na bilang ng mga hakbang ay ginagarantiyahan na mahanap ang pinakamainam na halaga o maitatag ang katotohanan na ang problema ay hindi malulutas.
Ang paraang ito ay unibersal, naaangkop sa anumang problema sa linear programming sa canonical form. Ang sistema ng mga hadlang dito ay isang sistema ng mga linear na equation kung saan ang bilang ng mga hindi alam ay mas malaki kaysa sa bilang ng mga equation. Kung ang ranggo ng system ay r, maaari tayong pumili ng r hindi alam, na ipapahayag natin sa mga tuntunin ng natitirang mga hindi alam. Para sa katiyakan, ipinapalagay namin na ang unang magkakasunod na hindi alam na X1, X2, ..., Xr ay pinili. Kung gayon ang aming sistema ng mga equation ay maaaring isulat bilang
Ang simplex method ay nakabatay sa isang theorem na tinatawag na fundamental theorem ng simplex method. Kabilang sa mga pinakamainam na plano para sa isang linear na problema sa programming sa canonical form, mayroong kinakailangang solusyon sa sanggunian sa sistema ng mga hadlang nito. Kung ang pinakamainam na plano ng problema ay natatangi, kung gayon ito ay kasabay ng ilang sanggunian na solusyon. Mayroong tiyak na maraming iba't ibang mga solusyon sa suporta para sa sistema ng pagpilit. Samakatuwid, ang solusyon ng problema sa canonical form ay maaaring hanapin sa pamamagitan ng pag-enumerate ng mga sangguniang solusyon at pagpili sa kanila ng isa kung saan ang halaga ng F ang pinakamalaki. Ngunit, una, ang lahat ng mga solusyon sa sanggunian ay hindi alam at kailangan nilang matagpuan, at, pangalawa, sa mga totoong problema mayroong maraming mga solusyon na ito at ang direktang enumeration ay halos hindi posible. Ang simplex na paraan ay isang tiyak na pamamaraan ng nakadirekta na enumeration ng mga reference na solusyon. Batay sa ilang naunang nahanap na reference na solusyon gamit ang isang tiyak na algorithm ng simplex na paraan, kinakalkula namin ang isang bagong reference na solusyon kung saan ang halaga ng layunin na function F ay hindi mas mababa kaysa sa luma. Pagkatapos ng isang serye ng mga hakbang, nakarating kami sa isang reference na solusyon, na siyang pinakamainam na plano.
10. Pahayag ng problema sa transportasyon. Mga pamamaraan para sa pagtukoy ng mga batayang plano.
Mayroong m punto ng pag-alis ("mga supplier") at n punto ng pagkonsumo ("mga mamimili") ng ilang magkatulad na produkto. Para sa bawat item ay tinukoy:
ai - dami ng produksyon ng i-th supplier, i = 1, …, m;
вj - demand ng j-th consumer, j= 1,…,n;
cij - ang halaga ng transportasyon ng isang yunit ng produksyon mula sa point Ai - ang i-th supplier, hanggang point Bj - ang j-th consumer.
Para sa kalinawan, ito ay maginhawa upang ipakita ang data sa anyo ng isang talahanayan, na tinatawag na talahanayan ng mga gastos sa transportasyon.
Kinakailangang maghanap ng plano sa transportasyon na ganap na makakatugon sa pangangailangan ng lahat ng mga mamimili, habang magkakaroon ng sapat na mga supply ng mga supplier at ang kabuuang gastos sa transportasyon ay magiging minimal.
Sa ilalim ng plano sa transportasyon ay nauunawaan ang dami ng trapiko, i.e. ang dami ng mga kalakal na dadalhin mula sa i-th supplier patungo sa j-th consumer. Upang makabuo ng mathematical model ng problema, kinakailangang maglagay ng m n variables хij, i= 1,…, n, j= 1, …, m, bawat variable хij ay tumutukoy sa dami ng trapiko mula sa point Ai hanggang point Bj. Ang hanay ng mga variable na X = (xij) ang magiging plano na kailangang hanapin batay sa pahayag ng problema.
Ito ay isang kondisyon para sa paglutas ng mga closed at open transport task (ZTZ).
Malinaw, para sa kakayahang malutas ang problema 1, kinakailangan na ang kabuuang demand ay hindi lalampas sa dami ng produksyon mula sa mga supplier:
Kung ang hindi pagkakapantay-pantay na ito ay mahigpit na natutugunan, kung gayon ang problema ay tinatawag na "bukas" o "hindi balanse", ngunit kung , kung gayon ang problema ay tinatawag na "sarado" na problema sa transportasyon, at magkakaroon ng form (2):
Kondisyon ng balanse.
Ito ay isang kondisyon para sa paglutas ng mga closed transport task (ZTZ).
11. Algorithm para sa paglutas ng problema sa transportasyon.
Ang aplikasyon ng algorithm ay nangangailangan ng pagsunod sa isang bilang ng mga kinakailangan:
1. Dapat malaman ang halaga ng pagdadala ng isang yunit ng produkto mula sa bawat punto ng produksyon patungo sa bawat destinasyon.
2. Dapat malaman ang stock ng mga produkto sa bawat punto ng produksyon.
3. Dapat malaman ang mga pangangailangan ng pagkain sa bawat punto ng pagkonsumo.
4. Ang kabuuang supply ay dapat na katumbas ng kabuuang demand.
Ang algorithm para sa paglutas ng problema sa transportasyon ay binubuo ng apat na yugto:
Stage I. Pagtatanghal ng data sa anyo ng isang karaniwang talahanayan at paghahanap para sa anumang katanggap-tanggap na paglalaan ng mga mapagkukunan. Ang isang katanggap-tanggap na pamamahagi ng mga mapagkukunan ay tulad na natutugunan nito ang lahat ng pangangailangan sa mga destinasyon at inaalis ang buong supply ng mga produkto mula sa mga lugar ng produksyon.
Stage 2. Sinusuri ang nakuhang resource allocation para sa optimality
Stage 3. Kung ang resultang pamamahagi ng mga mapagkukunan ay hindi optimal, pagkatapos ay ang mga mapagkukunan ay muling ipinamamahagi, na binabawasan ang gastos ng transportasyon.
Stage 4. Muling suriin ang pinakamainam ng nakuha na paglalaan ng mapagkukunan.
Ang umuulit na prosesong ito ay paulit-ulit hanggang sa makuha ang pinakamainam na solusyon.
12. Mga modelo ng pamamahala ng imbentaryo.
Sa kabila ng katotohanan na ang anumang modelo ng pamamahala ng imbentaryo ay idinisenyo upang sagutin ang dalawang pangunahing tanong (kailan at magkano), mayroong isang malaking bilang ng mga modelo na gumagamit ng iba't ibang mga tool sa matematika upang bumuo.
Ang sitwasyong ito ay ipinaliwanag sa pamamagitan ng pagkakaiba sa mga paunang kondisyon. Ang pangunahing batayan para sa pag-uuri ng mga modelo ng pamamahala ng imbentaryo ay ang likas na pangangailangan para sa mga nakaimbak na produkto (tandaan na, mula sa punto ng view ng isang mas pangkalahatang gradasyon, isinasaalang-alang lamang natin ang mga kaso na may independiyenteng pangangailangan).
Kaya, depende sa likas na katangian ng demand, ang mga modelo ng pamamahala ng imbentaryo ay maaaring
deterministiko;
probabilistiko.
Sa turn, ang deterministic na demand ay maaaring maging static, kapag ang intensity ng pagkonsumo ay hindi nagbabago sa paglipas ng panahon, o dynamic, kapag ang maaasahang demand ay maaaring magbago sa paglipas ng panahon.
Ang probabilistikong demand ay maaaring nakatigil, kapag ang probability density ng demand ay hindi nagbabago sa paglipas ng panahon, at non-stationary, kung saan nagbabago ang probability density function sa paglipas ng panahon. Ang pag-uuri sa itaas ay inilalarawan sa figure.
Ang pinakasimple ay ang kaso ng isang deterministikong static na demand para sa mga produkto. Gayunpaman, ang ganitong uri ng pagkonsumo ay medyo bihira sa pagsasanay. Ang pinaka-kumplikadong mga modelo ay mga modelo ng hindi nakatigil na uri.
Bilang karagdagan sa likas na pangangailangan para sa mga produkto, kapag bumubuo ng mga modelo ng pamamahala ng imbentaryo, maraming iba pang mga kadahilanan ang dapat isaalang-alang, halimbawa:
mga tuntunin ng pagpapatupad ng mga utos. Ang tagal ng panahon ng pagkuha ay maaaring pare-pareho o maging isang random na variable;
proseso ng muling pagdadagdag. Maaaring madalian o ipamahagi sa paglipas ng panahon;
ang pagkakaroon ng mga paghihigpit sa kapital na nagtatrabaho, espasyo sa imbakan, atbp.
13. Queueing system (QS) at mga tagapagpahiwatig ng kanilang pagiging epektibo.
Ang mga queuing system (QS) ay mga sistema ng isang espesyal na uri na nagpapatupad ng paulit-ulit na pagpapatupad ng mga gawain ng parehong uri. Ang ganitong mga sistema ay may mahalagang papel sa maraming larangan ng ekonomiya, pananalapi, produksyon at pang-araw-araw na buhay. Bilang mga halimbawa ng mga CMO sa pananalapi at pang-ekonomiya; Sa globo, ang mga bangko ng iba't ibang uri (komersyal, pamumuhunan, mortgage, makabagong, pagtitipid), mga organisasyon ng seguro, kumpanya ng joint-stock ng estado, kumpanya, kumpanya, asosasyon, kooperatiba, inspektor ng buwis, serbisyo sa pag-audit, iba't ibang sistema ng komunikasyon (kabilang ang mga palitan ng telepono ), loading at unloading complexes (ports, freight stations), gas station, iba't ibang negosyo at organisasyon sa service sector (mga tindahan, information desk, hairdresser, ticket office, currency exchange office, repair shop, ospital). Ang mga sistema tulad ng mga network ng computer, mga sistema para sa pagkolekta, pag-iimbak at pagproseso ng impormasyon, mga sistema ng transportasyon, mga automated na site ng produksyon, mga linya ng produksyon, iba't ibang mga sistema ng militar, sa partikular na air defense o mga missile defense system, ay maaari ding ituring bilang isang uri ng QS.
Kasama sa bawat QS sa istraktura nito ang isang tiyak na bilang ng mga aparato ng serbisyo, na tinatawag na mga channel ng serbisyo (mga aparato, linya). Ang papel ng mga channel ay maaaring gampanan ng iba't ibang device, mga taong nagsasagawa ng ilang partikular na operasyon (mga cashier, operator, tagapag-ayos ng buhok, nagbebenta), mga linya ng komunikasyon, kotse, crane, repair team, riles, gasolinahan, atbp.
Ang mga sistema ng pagpila ay maaaring single-channel o multi-channel.
Ang bawat QS ay idinisenyo upang maghatid (magpatupad) ng isang tiyak na daloy ng mga aplikasyon (mga kinakailangan) na dumarating sa input ng system para sa karamihan hindi regular, ngunit sa mga random na oras. Ang mga kahilingan sa paglilingkod, sa kasong ito, ay tumatagal din hindi isang pare-pareho, alam na oras, ngunit isang random na oras, na depende sa maraming random, minsan hindi alam sa amin, mga dahilan. Pagkatapos ibigay ang kahilingan, ilalabas ang channel at handa nang tanggapin ang susunod na kahilingan. Ang random na katangian ng daloy ng mga kahilingan at ang oras ng kanilang serbisyo ay humahantong sa hindi pantay na karga ng trabaho ng QS: sa ibang pagkakataon, ang mga hindi naihatid na kahilingan ay maaaring maipon sa input ng QS, na humahantong sa labis na karga ng QS, at kung minsan, na may mga libreng channel, walang hihilingin sa input ng QS, na hahantong sa underload ng QS, i.e. e. upang idle ang mga channel nito. Ang mga application na nag-iipon sa pasukan ng QS ay maaaring "makapasok" sa pila, o, dahil sa imposibilidad ng karagdagang pananatili sa pila, iwanan ang QS na hindi naseserbisyuhan.
Mga tagapagpahiwatig ng pagganap para sa paggana ng pares na "QS - consumer", kung saan ang consumer ay nauunawaan bilang ang buong hanay ng mga application o ilan sa kanilang pinagmulan (halimbawa, ang average na kita na dinadala ng QS bawat yunit ng oras, atbp.). Ang pangkat ng mga tagapagpahiwatig na ito ay kapaki-pakinabang sa mga kaso kung saan ang ilang kita na natanggap mula sa mga kahilingan sa serbisyo at mga gastos sa serbisyo ay sinusukat sa parehong mga yunit. Ang mga tagapagpahiwatig na ito ay karaniwang may napaka-espesipikong katangian at tinutukoy ng mga detalye ng QS, ang mga kahilingang inihatid, at ang disiplina sa serbisyo.
14. Mga equation ng dynamics para sa probabilistic states (mga equation ni Kolmogorov). Limitahan ang mga probabilidad ng mga estado.
Pormal na pinagkaiba ang Kolmogorov–Chapman equation na may kinalaman sa s at s = 0, nakuha natin ang direktang Kolmogorov equation:
Pormal na pinagkaiba ang Kolmogorov-Chapman equation na may paggalang sa t at t = 0, nakuha namin ang inverse Kolmogorov equation
Dapat itong bigyang-diin na para sa mga walang katapusang-dimensional na espasyo, ang operator ay hindi na kinakailangang tuluy-tuloy, at maaaring hindi tukuyin sa lahat ng dako, halimbawa, upang maging isang differential operator sa espasyo ng mga distribusyon.
Kung sakaling ang bilang ng mga estado ng system S ay may hangganan at posible na pumunta mula sa bawat estado (para sa isa o isa pang bilang ng mga hakbang) patungo sa isa't isa, kung gayon ang paglilimita ng mga probabilidad ng mga estado ay umiiral at hindi rin nakasalalay sa ang paunang estado ng system.
Sa fig. ay nagpapakita ng graph ng mga estado at mga transition na nakakatugon sa kundisyon: mula sa anumang estado, ang system ay maaaring maaga o huli pumunta sa anumang ibang estado. Hindi matutupad ang kundisyon kapag nabaligtad ang direksyon ng arrow 4-3 sa graph sa Fig.
Ipagpalagay natin na ang nakasaad na kondisyon ay nasiyahan, at, samakatuwid, ang mga marginal na probabilidad ay umiiral:
Ang paglilimita sa mga probabilidad ay ilalarawan ng parehong mga titik bilang ang mga probabilidad ng mga estado, habang ang ibig sabihin ng mga ito ay mga numero, hindi mga variable (mga function ng oras).
Malinaw na ang paglilimita ng mga probabilidad ng mga estado ay dapat magdagdag ng hanggang sa pagkakaisa: Dahil dito, ang isang tiyak na paglilimita sa nakatigil na mode ay itinatag sa system sa: hayaan ang system at baguhin ang sarili nitong mga estado nang sapalaran, ngunit ang posibilidad ng bawat isa sa mga estado na ito ay hindi nakasalalay. sa oras at ang bawat isa sa kanila ay isinasagawa na may ilang pare-parehong posibilidad, na siyang average na kamag-anak na oras na ginugugol ng system sa estadong ito.
15. Ang proseso ng kamatayan at pagpaparami.
Sa pamamagitan ng proseso ng kamatayan at pagpaparami ng Markov na may tuluy-tuloy na oras, ang ibig naming sabihin ay isang s.p. na maaaring tumagal lamang ng mga hindi negatibong halaga ng integer; ang mga pagbabago sa prosesong ito ay maaaring mangyari sa anumang oras t, habang sa anumang oras maaari itong tumaas ng isa o manatiling hindi nagbabago.
Ang multiplication flows λi(t) ay ang Poisson flows na humahantong sa pagtaas ng function X(t). Alinsunod dito, ang μi(t) ay mga daloy ng kamatayan na humahantong sa pagbaba sa function na X(t).
Buuin natin ang mga equation ng Kolmogorov ayon sa graph:
Kung ang isang thread na may limitadong bilang ng mga estado:
Ang sistema ng mga equation ng Kolmogorov para sa proseso ng kamatayan at pagpaparami na may limitadong bilang ng mga estado ay may anyo:
Ang proseso ng purong pagpaparami ay tulad ng isang proseso ng kamatayan at pagpaparami, kung saan ang intensity ng lahat ng daloy ng kamatayan ay katumbas ng zero.
Ang proseso ng purong kamatayan ay tulad ng isang proseso ng kamatayan at pagpaparami, kung saan ang intensity ng lahat ng daloy ng pagpaparami ay katumbas ng zero.
16. Mga sistema ng pagpila na may mga pagkabigo.
Ang pinakasimpleng problema na isinasaalang-alang sa balangkas ng teorya ng pagpila ay ang modelo ng isang solong channel na QS na may mga pagkabigo o pagkalugi.
Dapat tandaan na sa kasong ito ang bilang ng mga channel ay 1 (). Ang channel na ito ay tumatanggap ng isang Poisson na daloy ng mga kahilingan, ang intensity nito ay katumbas ng . Nakakaapekto ang oras sa intensity:
Kung ang isang aplikasyon ay dumating sa isang channel na kasalukuyang hindi libre, ito ay tatanggihan at hindi na nakalista sa system. Ang mga aplikasyon ay sineserbisyuhan sa random na oras , ang pamamahagi nito ay naisasakatuparan alinsunod sa exponential law na may parameter na :
17. Mga sistema ng pagpila na may paghihintay.
Ang isang kahilingan na dumarating sa oras na ang channel ay abala ay nakapila at naghihintay ng serbisyo.
Isang system na may limitadong haba ng pila. Ipagpalagay muna natin na ang bilang ng mga upuan sa pila ay limitado sa bilang na m, ibig sabihin, kung dumating ang isang customer sa oras na mayroon nang m customer sa pila, iniiwan nito ang system na hindi naseserbisyuhan. Sa hinaharap, kung ang m ay may posibilidad na infinity, makukuha namin ang mga katangian ng isang solong channel na QS nang walang mga paghihigpit sa haba ng pila.
Bibilangin namin ang mga estado ng QS ayon sa bilang ng mga kahilingan sa system (parehong naserbisyuhan at naghihintay ng serbisyo):
— ang channel ay libre;
— abala ang channel, walang pila;
— abala ang channel, isang kahilingan ang nasa pila;
— ang channel ay abala, k - 1 ang mga kahilingan ay nasa pila;
- ang channel ay abala, tonelada ng mga application ay nasa pila.
18. Mga paraan ng paggawa ng desisyon sa mga kondisyon ng salungatan. Mga larong matrix. Puro at halo-halong diskarte na laro.
Ang matrix game ay isang zero-sum final game ng dalawang manlalaro, kung saan ang kabayaran ng player 1 ay ibinibigay sa anyo ng isang matrix (ang hilera ng matrix ay tumutugma sa bilang ng inilapat na diskarte ng player 2, ang column ay tumutugma sa bilang ng inilapat na diskarte ng player 2; sa intersection ng row at column ng matrix ay ang kabayaran ng player 1, na nauugnay sa mga inilapat na diskarte).
Para sa mga larong matrix, napatunayan na ang alinman sa mga ito ay may solusyon at madali itong mahahanap sa pamamagitan ng pagbabawas ng laro sa isang linear programming problem.
Ang two-player zero-sum matrix game ay maaaring tingnan bilang ang sumusunod na abstract two-player game.
Ang unang manlalaro ay may m estratehiya i = 1,2,...,m, ang pangalawa ay may n estratehiya j = 1,2,...,n. Ang bawat pares ng mga diskarte (i, j) ay itinalaga ng isang numero aij, na nagpapahayag ng kabayaran ng manlalaro 1 sa gastos ng manlalaro 2, kung tinanggap ng unang manlalaro ang kanyang i-th na diskarte, at 2 - ang kanyang j-th na diskarte.
Ang bawat isa sa mga manlalaro ay gumagawa ng isang galaw: pipiliin ng manlalaro 1 ang kanyang i-th na diskarte (i=), 2 - ang kanyang j-th na diskarte (j=), pagkatapos kung saan ang manlalaro 1 ay makakatanggap ng kabayaran na aij sa gastos ng manlalaro 2 (kung aij
Ang bawat diskarte ng player i=; j = ay madalas na tinatawag na purong diskarte.
Kahulugan. Ang pinaghalong diskarte ng isang manlalaro ay ang kumpletong hanay ng mga probabilidad ng paglalapat ng kanyang mga purong diskarte.
Kaya, kung ang manlalaro 1 ay may m purong estratehiya 1,2,...,m, kung gayon ang kanyang pinaghalong diskarte x ay isang set ng mga numero x = (x1,..., xm) na nagbibigay-kasiyahan sa mga relasyon
xi³ 0 (i= 1,m), =1.
Katulad nito, para sa manlalaro 2, na mayroong n purong diskarte, ang pinaghalong diskarte na y ay ang hanay ng mga numero
y = (y1, ..., yn), yj ³ 0, (j = 1,n), = 1.
Dahil sa bawat oras na gumagamit ang isang manlalaro ng isang purong diskarte ay hindi kasama ang paggamit ng isa pa, ang mga purong diskarte ay hindi magkatugma na mga kaganapan. Isa pa, sila lang ang posibleng mangyari.
Ang purong diskarte ay isang espesyal na kaso ng pinaghalong diskarte. Sa katunayan, kung sa isang halo-halong diskarte ang anumang i-th purong diskarte ay inilapat na may posibilidad na 1, kung gayon ang lahat ng iba pang mga purong diskarte ay hindi inilalapat. At ang i-th pure strategy na ito ay isang espesyal na kaso ng pinaghalong diskarte. Upang mapanatili ang pagiging lihim, inilalapat ng bawat manlalaro ang kanyang sariling mga diskarte anuman ang pagpili ng ibang manlalaro.
19. Geometric na pamamaraan para sa paglutas ng isang matrix na laro.
Ang solusyon ng mga laro na may sukat na 2xn o nx2 ay nagbibigay-daan sa isang malinaw na geometric na interpretasyon. Ang ganitong mga laro ay maaaring malutas sa graphically.
Sa XY plane, kasama ang abscissa, nagtabi kami ng isang segment na A1A2 (Larawan 5.1). Ang bawat punto ng segment ay nauugnay sa ilang pinaghalong diskarte U = (u1, u2). Bukod dito, ang distansya mula sa ilang intermediate point U hanggang sa kanang dulo ng segment na ito ay ang posibilidad na u1 ng pagpili ng diskarte A1, ang distansya sa kaliwang dulo ay ang posibilidad na u2 ng pagpili ng diskarte A2. Ang punto A1 ay tumutugma sa purong diskarte A1, ang punto A2 ay tumutugma sa purong diskarte A2.
Sa mga puntong A1 at A2, ibinabalik namin ang mga perpendicular at ipagpaliban ang mga kabayaran ng mga manlalaro sa kanila. Sa unang perpendicular (kasabay ng OY axis), ipinapakita namin ang kabayaran ng player A kapag gumagamit ng diskarte A1, sa pangalawa - kapag gumagamit ng diskarte A2. Kung ang manlalaro A ay gumagamit ng diskarte A1, ang kanyang kabayaran sa diskarte B1 ng manlalaro B ay 2, at sa diskarte B2 ito ay 5. Ang mga numero 2 at 5 sa OY axis ay tumutugma sa mga puntos na B1 at B2. Katulad nito, sa pangalawang patayo makikita natin ang mga puntos B "1 at B" 2 (mga kabayaran 6 at 4).
Ang pagkonekta ng mga puntos na B1 at B"1, B2 at B"2, nakakakuha tayo ng dalawang tuwid na linya, ang distansya mula sa kung saan patungo sa axis ng OX ay tumutukoy sa average na kabayaran para sa anumang kumbinasyon ng mga kaukulang estratehiya.
Halimbawa, ang distansya mula sa anumang punto ng segment na B1B"1 hanggang sa axis na OX ay tumutukoy sa average na kabayaran ng player A para sa anumang kumbinasyon ng mga diskarte A1 at A2 (na may probabilities u1 at u2) at diskarte B1 ng player B.
Tinutukoy ng mga ordinate ng mga puntos na kabilang sa putol na linyang B1MB"2 ang pinakamababang kabayaran ng manlalaro A kapag gumamit siya ng anumang magkahalong diskarte. Ang pinakamababang halagang ito ang pinakamalaki sa puntong M, samakatuwid, ang puntong ito ay tumutugma sa pinakamainam na diskarte U* = (,), at ang ordinate nito ay katumbas ng presyo ng laro v.
Nahanap namin ang mga coordinate ng punto M bilang mga coordinate ng punto ng intersection ng mga linya B1B"1 at B2B"2.
Upang gawin ito, kailangan mong malaman ang mga equation ng mga linya. Maaari kang bumuo ng mga naturang equation gamit ang formula para sa equation ng isang tuwid na linya na dumadaan sa dalawang punto:
Buuin natin ang mga equation ng mga linya para sa ating problema.
Linya B1B"1: = o y = 4x + 2.
Direktang B2B "2: = o y = -x + 5.
Nakukuha namin ang system: y = 4x + 2,
Lutasin natin ito: 4x + 2 = -x + 5,
x = 3/5, y = -3/5 + 5 = 22/5.
Kaya U = (2/5, 3/5), v = 22/5.
20. Mga larong Bimatrix.
Ang larong bimatrix ay isang may hangganang laro ng dalawang manlalaro na may hindi zero na kabuuan, kung saan ang mga kabayaran ng bawat manlalaro ay ibinibigay ng mga matrice nang hiwalay para sa katumbas na manlalaro (sa bawat matrix, ang hilera ay tumutugma sa diskarte ng manlalaro 1, ang column tumutugma sa diskarte ng player 2, sa intersection ng row at column sa unang matrix ay ang kabayaran ng player 1, sa pangalawang matrix - ang kabayaran ng player 2.)
Para sa mga larong bimatrix, ang teorya ng pinakamainam na pag-uugali ng mga manlalaro ay binuo din, ngunit ang paglutas ng mga naturang laro ay mas mahirap kaysa sa maginoo na mga laro ng matrix.
21. Mga larong istatistika. Mga prinsipyo at pamantayan para sa paggawa ng desisyon sa ilalim ng mga kondisyon ng kumpleto at bahagyang kawalan ng katiyakan.
Sa pagsasaliksik sa pagpapatakbo, kaugalian na makilala sa pagitan ng tatlong uri ng kawalan ng katiyakan:
kawalan ng katiyakan ng mga layunin;
ang kawalan ng katiyakan ng ating kaalaman tungkol sa kapaligiran at ang mga salik na kumikilos sa hindi pangkaraniwang bagay na ito (kawalan ng katiyakan ng kalikasan);
ang kawalan ng katiyakan ng mga aksyon ng isang aktibo o passive na kasosyo o kalaban.
Sa pag-uuri sa itaas, ang uri ng mga kawalan ng katiyakan ay isinasaalang-alang mula sa pananaw ng isa o ibang elemento ng modelo ng matematika. Kaya, halimbawa, ang kawalan ng katiyakan ng mga layunin ay makikita sa pagbabalangkas ng problema sa pagpili ng alinman sa mga indibidwal na pamantayan, o ang buong vector ng isang kapaki-pakinabang na epekto.
Sa kabilang banda, ang iba pang dalawang uri ng kawalan ng katiyakan ay pangunahing nakakaapekto sa pagbabalangkas ng layunin na pag-andar ng mga equation ng pagpilit at ang paraan ng pagpapasya. Siyempre, ang pahayag sa itaas ay medyo may kondisyon, tulad ng, sa katunayan, anumang pag-uuri. Ipinakita lang namin ito upang i-highlight ang ilan pang mga tampok ng mga kawalan ng katiyakan na dapat tandaan sa proseso ng paggawa ng desisyon.
Ang katotohanan ay bilang karagdagan sa pag-uuri sa itaas ng mga kawalan ng katiyakan, dapat isaalang-alang ng isa ang kanilang uri (o "uri") mula sa punto ng view ng kanilang kaugnayan sa randomness.
Sa batayan na ito, ang isang tao ay maaaring makilala sa pagitan ng stochastic (probabilistic) na kawalan ng katiyakan, kapag ang hindi kilalang mga kadahilanan ay matatag sa istatistika at samakatuwid ay mga ordinaryong bagay ng teorya ng posibilidad - mga random na variable (o mga random na function, mga kaganapan, atbp.). Sa kasong ito, ang lahat ng kinakailangang istatistikal na katangian (mga batas sa pamamahagi at ang kanilang mga parameter) ay dapat malaman o matukoy kapag nagtatakda ng problema.
Ang isang halimbawa ng naturang mga gawain ay maaaring, sa partikular, isang sistema para sa pagpapanatili at pagkumpuni ng anumang uri ng kagamitan, isang sistema para sa pag-aayos ng pagnipis, atbp.
Ang isa pang matinding kaso ay maaaring hindi stochastic na kawalan ng katiyakan (ayon kay E.S. Wentzel - "masamang kawalan ng katiyakan"), kung saan walang mga pagpapalagay tungkol sa stochastic na katatagan. Sa wakas, maaari nating pag-usapan ang tungkol sa isang intermediate na uri ng kawalan ng katiyakan, kapag ang isang desisyon ay ginawa batay sa ilang mga hypotheses tungkol sa mga batas ng pamamahagi ng mga random na variable. Kasabay nito, dapat isaisip ng gumagawa ng desisyon ang panganib ng isang pagkakaiba sa pagitan ng kanyang mga resulta at mga tunay na kondisyon. Ang panganib ng mismatch na ito ay ginawang pormal sa tulong ng mga risk coefficient.
Ang paggawa ng desisyon sa peligro ay maaaring batay sa isa sa mga sumusunod na pamantayan:
inaasahang criterion ng halaga;
mga kumbinasyon ng inaasahang halaga at pagkakaiba;
kilalang antas ng limitasyon;
malamang na kaganapan sa hinaharap.
operasyon anumang kaganapan (sistema ng mga aksyon), na pinagsama ng isang plano at nakadirekta sa pagkamit ng isang tiyak na layunin, ay tinatawag. Ang operasyon ay palaging pinamamahalaan kaganapan, i.e. posible na itapon ang paraan ng pagpili ng ilang mga parameter na nagpapakilala sa organisasyon nito. Ang mga opsyon na ito ay tinatawag mga variable ng kontrol.
Ang anumang tiyak na pagpipilian ng naturang mga variable ay tinatawag desisyon. Ang mga desisyon ay maaaring maging matagumpay at hindi matagumpay, makatwiran at hindi makatwiran. Pinakamainam pangalanan ang mga naturang solusyon na, ayon sa ilang pamantayan, ay mas kanais-nais kaysa sa iba.
Ang layunin ng operations research ay isang paunang dami ng pagbibigay-katwiran ng pinakamainam na solusyon, kung saan maaaring mayroong higit sa isa. Ang pangwakas na pagpili ng isang desisyon ay lampas sa saklaw ng operations research at ginagawa sa pamamagitan ng tinatawag na decision theory.
Anumang gawain ng pagsasaliksik sa pagpapatakbo ay may mga paunang "disciplinary" na mga kondisyon, i.e. tulad ng paunang data na naayos mula pa sa simula at hindi maaaring labagin. Magkasama, bumubuo sila ng tinatawag na hanay ng mga posibleng solusyon.
Upang ihambing ang pagiging epektibo ng iba't ibang mga solusyon, kailangan mong magkaroon ng tinatawag na quantitative criterion tagapagpahiwatig ng pagganap(o layunin ng function). Ang indicator na ito ay pinili upang ipakita ang target na oryentasyon ng operasyon.
Kadalasan ang operasyon ay sinamahan ng pagkilos ng mga random na kadahilanan. Pagkatapos, hindi ang halaga mismo na gusto naming i-optimize ang kinuha bilang isang indicator ng kahusayan, ngunit ang average na halaga nito (o mathematical na inaasahan).
Minsan ang isang operasyon na sinamahan ng mga random na kadahilanan ay humahabol sa gayong layunin. A, na maaaring ganap na makamit o hindi makamit sa lahat (tulad ng "oo - hindi"). Pagkatapos ang posibilidad na makamit ang layuning ito ay pinili bilang isang tagapagpahiwatig ng kahusayan. p(A). (Kung p(A) = 0 o 1, pagkatapos ay makarating tayo sa kilalang problema sa "black box" sa cybernetics.)
Ang maling pagpili ng tagapagpahiwatig ng pagganap ay lubhang mapanganib. Ang mga operasyong inayos ayon sa isang hindi matagumpay na napiling pamantayan ay maaaring humantong sa hindi makatarungang mga gastos at pagkalugi. (Halimbawa, ang "shaft" bilang pangunahing criterion para sa pagsusuri sa aktibidad ng ekonomiya ng isang negosyo.)
1.3. Pangkalahatang pahayag ng gawain ng pananaliksik sa pagpapatakbo
Ang mga gawain sa pagsasaliksik ng operasyon ay nahahati sa dalawang kategorya: a) direkta at b) kabaligtaran.
Mga direktang gawain sagutin ang tanong: ano ang magiging indicator ng kahusayan Z kung nasa ilalim ng mga ibinigay na kondisyon y Y ilang desisyon ang gagawin x X. Upang malutas ang gayong problema, ang isang modelo ng matematika ay binuo na nagbibigay-daan sa pagpapahayag ng tagapagpahiwatig ng kahusayan sa pamamagitan ng mga ibinigay na kondisyon at isang solusyon, katulad:
saan 
ibinigay na mga kadahilanan (paunang data),
mga variable ng kontrol (solusyon),
Z- tagapagpahiwatig ng pagganap (layunin function),
F– functional dependence sa pagitan ng mga variable.
Ang pag-asa na ito sa iba't ibang mga modelo ay ipinahayag sa iba't ibang paraan. Relasyon sa pagitan 
At 
karaniwang ipinahayag bilang mga limitasyon sa 
Kung ang uri ng dependency F kilala, pagkatapos ay ang tagapagpahiwatig Z ay matatagpuan sa pamamagitan ng direktang pagpapalit 
At 
sa functionality na ito.
Baliktad na mga Problema sagutin ang tanong: paano, sa ilalim ng mga ibinigay na kondisyon 
pumili ng solusyon 
upang ang tagapagpahiwatig ng pagganap Z naging maximum (minimum). Ang ganitong problema ay tinatawag na problema sa pag-optimize ng solusyon.
Hayaang malutas ang direktang problema, i.e. ang modelo ng pagpapatakbo ay nakatakda at ang uri ng pagtitiwala F sikat. Pagkatapos ay ang kabaligtaran na problema (iyon ay, ang problema sa pag-optimize) ay maaaring mabalangkas tulad ng sumusunod.
Nais mahanap ganyang desisyon 
kung saan ang tagapagpahiwatig ng kahusayan Z
= opt:
Ang formula na ito ay nagbabasa ng ganito: Z mayroong pinakamainam na halaga 
kinuha ang lahat ng mga solusyon na kasama sa hanay ng mga posibleng solusyon X.
Ang paraan ng paghahanap para sa extremum ng indicator ng kahusayan Z at ang nauugnay na pinakamainam na solusyon 
dapat palaging piliin batay sa mga katangian ng function F at ang uri ng mga hadlang na ipinataw sa solusyon. (Halimbawa, isang klasikong problema sa linear programming.)
Pananaliksik sa pagpapatakbo- isang agham na tumatalakay sa pag-unlad at praktikal na aplikasyon ng matematika, dami ng mga pamamaraan upang bigyang-katwiran ang mga desisyon sa lahat ng mga lugar ng may layunin na aktibidad ng tao (epektibong pamamahala ng organisasyon).
Mga Karaniwang Tampok ng Operations Research
Sa bawat gawain, pinag-uusapan natin ang ilang uri ng kaganapan na humahabol sa isang tiyak na layunin.
Nakatakda ang ilang kundisyon na nagpapakita ng sitwasyon (kabilang ang mga paraan na maaari nating itapon).
Sa loob ng balangkas ng mga kundisyong ito, kinakailangan na gumawa ng ganoong desisyon na ang nakaplanong kaganapan ay sa ilang mga kahulugan ang pinaka kumikita.
Mga Tampok ng Operations Research
Ang isang sistematikong diskarte sa pagsusuri ng problema na ibinibigay ay nangangahulugan na ang isang partikular na gawain ay dapat isaalang-alang mula sa punto ng view ng impluwensya nito sa criterion para sa paggana ng buong sistema.
Ang pinakamalaking epekto ay makakamit lamang sa patuloy na pananaliksik, na nagsisiguro ng pagpapatuloy sa paglipat mula sa isang gawain patungo sa isa pa, na nagmumula sa kurso ng paglutas ng nauna.
Bagama't ang layunin ng pagsasaliksik sa pagpapatakbo ay upang mahanap ang pinakamainam na solusyon, ngunit dahil sa pagiging kumplikado ng pag-compute ng mga kombinatoryal na problema, ang mga ito ay limitado sa paghahanap ng isang "sapat na mabuti" na solusyon.
Ang pagsasaliksik sa pagpapatakbo ay isinasagawa sa isang kumplikado, sa maraming lugar. Upang maisagawa ang pag-aaral, ang mga pangkat ng pagpapatakbo ay nilikha:
Pangunahing Konsepto ng Operations Research
OPERATION - anumang kinokontrol (iyon ay, depende sa pagpili ng mga parameter) na kaganapan, pinagsama ng isang solong plano at naglalayong makamit ang ilang layunin.
SOLUSYON - anumang tiyak na pagpipilian ng mga parameter depende sa amin.
OPTIMAL SOLUTIONS - ang mga desisyon para sa isang kadahilanan o iba pa ay mas kanais-nais kaysa sa iba.
ANG LAYUNIN NG PAG-AARAL NG OPERASYON ay isang paunang quantitative substantiation ng pinakamainam na solusyon.
MGA ELEMENTO NG SOLUSYON - mga parameter, ang kabuuan nito ay bumubuo ng isang solusyon.
Ang PERFORMANCE INDICATOR (TARGET FUNCTION) ay isang quantitative criterion na nagbibigay-daan sa paghahambing ng iba't ibang solusyon sa mga tuntunin ng kahusayan at sumasalamin sa target na oryentasyon ng operasyon (W => max o W => min).
Ang pinakamahusay na solusyon ay ang isa na nag-aambag sa pagkamit ng layunin sa pinakamataas na lawak.
Ang konsepto ng isang mathematical model ng isang operasyon
Isang eskematiko, pinasimpleng paglalarawan ng isang operasyon gamit ang isa o isa pang mathematical apparatus, na sumasalamin sa pinakamahalagang katangian ng operasyon, lahat ng mahahalagang salik kung saan ang tagumpay ng operasyon ay pangunahing nakasalalay.
Direkta at kabaligtaran na mga problema ng pananaliksik sa pagpapatakbo
DIREKTAONG PROBLEMA sinasagot ang tanong kung ano ang mangyayari kung, sa ilalim ng mga ibinigay na kundisyon, gagawa tayo ng ilang desisyon x X, i.e. ano ang magiging tagapagpahiwatig ng kahusayan W (o isang bilang ng mga tagapagpahiwatig).
Upang malutas ang gayong problema, ang isang banig ay itinayo. isang modelo na nagbibigay-daan sa iyong ipahayag ang isa o higit pang mga tagapagpahiwatig ng pagganap sa pamamagitan ng mga ibinigay na kundisyon at mga elemento ng solusyon.
INVERSE PROBLEMS sagutin ang tanong kung paano pumili ng solusyon x upang ang indicator ng kahusayan na W ay maging maximum (minimum).
Ang mga gawaing ito ay mas mahirap. Ang mga ito ay malulutas sa pamamagitan ng isang simpleng enumeration ng mga solusyon sa mga direktang problema.
Ngunit kapag ang bilang ng mga solusyon ay malaki, ang mga nakadirekta na pamamaraan ng enumeration ay ginagamit, kung saan ang pinakamainam na solusyon ay matatagpuan sa pamamagitan ng pagsasagawa ng sunud-sunod na "mga pagsubok" o mga pagtatantya, na ang bawat isa ay naglalapit sa atin sa nais na pinakamainam.
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 mga 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 mga 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 ng praktikal na kahalagahan, ang pagpili ng isang 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 mga 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 upang 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 hanggang sa dulo na katumbas ng 62. Arbitraryo kaming pumili ng alinman sa mga ito (sa aming kaso, pinili namin ang "c"; maaari rin kaming magkaroon pinili "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) ibig sabihin 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?
