Concepte de bază ale cercetării operaționale. Cercetare operațională Soluție de joc în strategii mixte

ÎN. Slinkin

Manual pentru studenții universităților pedagogice

specializarea în Informatică

Shadrinsk, 2003

Slinkina I.N.

Cercetare operațională. Ajutor didactic. - Shadrinsk: editura Institutului Pedagogic de Stat Shadrinsk, 2002. - 106 p.

Slinkina I.N. – candidat la științe pedagogice

Manualul prezintă partea teoretică a cursului „Cercetare operațională”. Este destinat studenților din departamentele cu frecvență și cu frecvență parțială ale facultăților care implementează specialitatea „Informatică”.

© Institutul Pedagogic de Stat Shadrinsky

© Slinkina I.N., 2002

Întrebări la blocurile din cursul „Cercetare operațională” 5

1.1. Subiectul și obiectivele cercetării operaționale 7

1.2. Concepte și principii de bază ale cercetării operaționale 8

1.3. Modele matematice ale operațiilor 10

1.4. Înțelegerea programării liniare 12

1.5. Exemple de probleme economice de programare liniară. Problema utilizării optime a resurselor 13

1.6. Exemple de probleme economice de programare liniară. Problema alegerii tehnologiilor optime 15

1.7. Exemple de probleme economice de programare liniară. Problema amestecului 16

1.8. Exemple de probleme economice de programare liniară. Sarcina de transport 17

1.9. Tipuri de bază de scriere a problemelor de programare liniară 19

1.10. Metode de conversie 21

1.11. Trecerea la forma canonică 22

1.12. Trecerea la notația simetrică 25

2.1. Interpretarea geometrică a unei probleme de programare liniară 28

2.2. Rezolvarea grafică a problemelor de programare liniară 29

2.3. Proprietățile soluțiilor la o problemă de programare liniară 34

2.4. Ideea generală a metodei simplex 35

2.5. Construirea unui plan de referință inițial pentru rezolvarea problemelor de programare liniară folosind metoda simplex 36

2.6. Un semn al optimității planului de bază. Tabele simplex 40

2.7. Trecerea la un plan de referință care nu este cel mai rău. 44

2.8. Transformări simplex 46

2.9. Optim alternativ (un semn al infinitității setului de planuri de referință) 51

2.10. Semnul de nelimitare al funcției obiectiv 52

2.11. Conceptul de degenerare. Monotonitatea și caracterul finit al metodei simplex. Buclă 53

2.12. Conceptul de dualitate pentru probleme de programare liniară simetrică 54

3.1. Probleme duale asimetrice 57

3.2. Modele deschise și închise ale problemei transportului 61

3.3. Construirea planului de bază inițial. Colțul de nord-vest Regula 63

3.4. Construirea planului de bază inițial. Regula elementului minim 64

3.5. Construirea planului de bază inițial. Metoda Vogel 64

3.6. Metoda potențială 65

3.7. Rezolvarea problemelor de transport cu limite de lățime de bandă 69

3.8. Exemple de probleme de programare discretă. Problema transportului containerelor. Problema de atribuire 71

3.9. Esența metodelor de optimizare discretă 72

3.10. Problema de programare convexă 74

3.11. Metoda multiplicatorilor Lagrange 75

3.12. Metode de gradient 77

4.1. Metode de sancționare și funcții de barieră 78

4.2. Programare dinamică. Noțiuni de bază. Esența metodelor de rezolvare 79

4.3. Programare stocastică. Concepte de bază 81

4.4. Jocuri cu matrice cu sumă zero 83

4.5. Strategii pure și mixte și proprietățile lor 85

4.6. Proprietățile strategiilor pure și mixte 88

4.7. Reducerea unui joc matrice la ZLP 92

4.8. Sarcini ale teoriei cozilor de aşteptare. Clasificarea sistemelor de așteptare 94

4.9. Fluxuri de evenimente 96

4.10. Schema morții și a reproducerii 97

4.11. Mica Formula 99

4.12. Cele mai simple sisteme de așteptare 101

Întrebări la blocurile din cursul „Cercetare operațională”

Blocul 1

1. Subiectul și sarcinile cercetării operaționale.

2. Concepte și principii de bază ale cercetării operaționale.

3. Modele matematice ale operaţiilor.

4. Conceptul de programare liniară.

5. Exemple de probleme economice de programare liniară. Sarcină

6. Exemple de probleme economice de programare liniară. Problema alegerii tehnologiilor optime.

7. Exemple de probleme economice de programare liniară. Problema amestecului.

8. Exemple de probleme economice de programare liniară. sarcina de transport.

9. Tipuri de bază de scriere a problemelor de programare liniară.

10. Metode de transformare.

11. Trecerea la forma canonică.

12. Trecerea la notația simetrică.

Blocul 2

1. Interpretarea geometrică a problemei de programare liniară.

2. Rezolvarea problemelor de programare liniară printr-o metodă grafică.

3. Proprietăţi ale soluţiilor unei probleme de programare liniară.

4. Ideea generală a metodei simplex.

5. Construirea planului de bază inițial pentru rezolvarea problemelor de programare liniară prin metoda simplex.

6. Semnul optimității planului de bază. Tabele simplex.

7. Tranziția către un plan de referință care nu este cel mai rău.

8. Transformări simplex.

9. Optim alternativ (un semn al infinitității setului de planuri de referință).

10. Semn de nelimitare a funcției obiectiv.

11. Conceptul de degenerare. Monotonitatea și caracterul finit al metodei simplex. Buclă.

12. Conceptul de dualitate pentru probleme de programare liniară simetrică.

Blocul 3

1. Probleme duale asimetrice.

2. Modele deschise și închise ale problemei transportului.

3. Construirea planului de bază inițial. Regula colțului de nord-vest.

4. Construirea planului de bază inițial. Regula elementului minim.

5. Construirea planului de bază inițial. metoda Vogel.

6. Metoda potenţialelor.

7. Rezolvarea problemelor de transport cu lățime de bandă limitată.

8. Exemple de probleme de programare discretă. Problema transportului containerelor. Sarcina de atribuire.

9. Esenţa metodelor de optimizare discretă.

10. Problema programării convexe.

11. Metoda multiplicatorilor Lagrange.

12. Metode de gradient.

Blocul 4

1. Metoda de penalizare și funcții de barieră.

2. Programare dinamică. Noțiuni de bază. Esența metodelor de rezolvare.

3. Programare stocastică. Noțiuni de bază.

4. Jocuri cu matrice cu sumă zero.

5. Strategii pure și mixte.

6. Proprietățile strategiilor pure și mixte.

7. Reducerea jocului matricial la LLP

8. Probleme ale teoriei cozilor. Clasificarea sistemelor de aşteptare.

9. Fluxuri de evenimente.

10. Schema morții și reproducerii.

11. Mică formulă.

12. Cele mai simple sisteme de așteptare.

Blocul 1.

Subiectul și obiectivele cercetării operaționale

Starea actuală a științei și tehnologiei, în special, dezvoltarea instrumentelor informatice de calcul și fundamentare matematică a teoriilor a făcut posibilă simplificarea semnificativă a soluționării multor probleme puse diferitelor ramuri ale științei. Multe dintre probleme se rezumă la rezolvarea problemei optimizării producției, controlului optim al procesului.

Nevoile practicii au adus la viață metode științifice speciale, care sunt grupate convenabil sub denumirea de „cercetare operațională”.

Definiție: Prin cercetare operațională vom înțelege aplicarea metodelor matematice, cantitative pentru a justifica deciziile în toate domeniile activității umane cu scop.

Să se ia unele măsuri pentru a atinge un anumit scop. Persoana (sau grupul de persoane) care organizează evenimentul are întotdeauna o oarecare libertate de alegere: poate fi organizat într-un fel sau altul. Decizia este o alegere dintr-un număr de opțiuni disponibile organizatorului.

Necesitatea de a lua decizii și de a testa ipoteza de decizie propusă este confirmată matematic de următoarele exemple:

Sarcina 1. Despre cea mai bună utilizare a resurselor.

Compania produce mai multe tipuri de produse. Pentru fabricarea lor se folosesc unele resurse (inclusiv umane, energetice etc.). Este necesar să se calculeze modul de planificare a activității întreprinderii, astfel încât costul resurselor să fie minim și profitul să fie maxim.

Sarcina 2. Despre amestecuri.

Este necesar să se pregătească un amestec cu anumite proprietăți. Pentru a face acest lucru, puteți folosi câteva „produse” (pentru calcularea dietelor - alimente, pentru amestecuri de hrană pentru animale - alimente pentru animale, pentru amestecuri tehnice - aliaje, lichide pentru scopuri tehnice). sarcina este de a alege cantitatea optimă de produse (pentru preț) pentru a obține cantitatea optimă de amestec.

Sarcina 3. sarcina de transport.

Există o rețea de întreprinderi care produc același tip de produse de aceeași calitate și o rețea de consumatori ai acestor produse. Consumatorii și furnizorii sunt conectați prin mijloace de comunicare (drumuri, linii de cale ferată, linii aeriene). Se stabilesc tarifele de transport. Este necesar să se calculeze planul optim pentru transportul produselor, astfel încât costurile de transport să fie minime, cererile tuturor consumatorilor să fie satisfăcute și toate mărfurile să fie exportate de la furnizori.

În fiecare dintre exemplele de mai sus, vorbim despre un fel de eveniment care urmărește un scop specific. Sunt date unele condiții care caracterizează situația (în special, mijloacele de care se pot dispune). În cadrul acestor condiții, este necesar să se ia o astfel de decizie încât evenimentul planificat să fie într-un anumit sens mai profitabil.

În conformitate cu aceste trăsături generale, sunt dezvoltate și metode generale de rezolvare a unor astfel de probleme, care alcătuiesc împreună schema metodologică și aparatul de cercetare operațională.

În prezent, sistemele de control automatizat (ACS) bazate pe utilizarea tehnologiei informatice sunt utilizate pe scară largă. Crearea unui sistem de control automat este imposibilă fără o examinare preliminară a procesului controlat prin metodele de modelare matematică. Odată cu creșterea amplorii și complexității evenimentelor, metodele matematice de justificare a deciziilor devin din ce în ce mai importante.

Concepte și principii de bază ale cercetării operaționale

Definiție: O operațiune este orice eveniment (sistem de acțiuni) unit printr-un singur plan și îndreptat spre atingerea unui scop.

O operațiune este întotdeauna un eveniment controlat, de exemplu. depinde de calcule modul de alegere a parametrilor care caracterizează organizarea acestuia. „Organizare” aici este înțeleasă în sensul larg al cuvântului, inclusiv ansamblul mijloacelor tehnice utilizate în operațiune.

Definiție: Orice alegere definită în funcție de parametrii de decizie se numește decizie.

Definiție: Soluțiile optime sunt cele care sunt preferate altora dintr-un motiv sau altul.

Scopul cercetării operaționale– fundamentarea cantitativă prealabilă a soluţiilor optime.

Uneori, în urma studiului, se poate indica o singură soluție, strict definită; mult mai des, este posibil să se identifice o zonă de soluții optime practic echivalente în cadrul căreia se poate face o alegere finală.

Luarea deciziei în sine depășește sfera cercetării operaționale și ține de competența unei persoane responsabile, de cele mai multe ori a unui grup de persoane cărora li se acordă dreptul de a face o alegere finală și care sunt responsabile pentru această alegere.

Definiție: Parametrii, a căror totalitate formează o soluție, se numesc elemente ale soluției.

Ca elemente ale soluției pot apărea diverse numere, vectori, funcții, semne fizice etc. Pentru simplitate, întregul set de elemente ale soluției va fi notat cu x.

Pe lângă elementele de soluție în orice sarcină de cercetare operațională, există și condiții date care sunt fixate în starea problemei și nu pot fi încălcate. În special, astfel de condiții includ mijloacele (materiale, tehnice, umane) care pot fi eliminate și alte restricții impuse soluției. În totalitatea lor, ele formează așa-numitul „set de soluții posibile”. Să notăm această mulțime X, iar faptul că soluția x aparține acestei mulțimi, vom scrie: хОХ.

Pentru a compara diferite soluții în ceea ce privește eficiența, trebuie să aveți un fel de criteriu cantitativ, așa-numitul indicator de performanță (funcția obiectivă). Acest indicator este ales astfel încât să reflecte orientarea țintă a operației. Cea mai bună soluție va fi considerată cea care contribuie la atingerea scopului în măsura maximă. Pentru a alege indicatorul de performanță Z, trebuie mai întâi să determinați la ce ar trebui să ducă soluția problemei. Atunci când alegeți o soluție, se acordă preferință uneia care transformă indicatorul de eficiență Z la maximum sau la minim. De exemplu, aș dori să maximizez venitul dintr-o operațiune; dacă costurile sunt un indicator al eficienței, este de dorit să le minimizeze.

Foarte des, operațiunea este însoțită de acțiunea unor factori aleatori: „capricii” naturii, fluctuații ale cererii și ofertei, defecțiuni ale dispozitivelor tehnice etc. În astfel de cazuri, de obicei, nu valoarea în sine, pe care am dori să o maximizăm (minimizat), ci valoarea medie (așteptările matematice) este luată ca indicator al eficienței.

Sarcina de a alege un indicator de performanță este rezolvată pentru fiecare problemă în mod individual.

Sarcina 1. Despre cea mai bună utilizare a resurselor.

Sarcina operațiunii este de a produce cantitatea maximă de mărfuri. Indicatorul de eficiență Z este profitul din vânzarea mărfurilor la costul minim al resurselor (max Z).

Sarcina 2. Despre amestecuri.

Un indicator natural al eficienței, sugerat de formularea problemei, este prețul produselor necesare amestecului, cu condiția ca proprietățile specificate ale amestecului (min Z) să fie păstrate.

Sarcina 3. sarcina de transport.

Sarcina operațiunii este de a asigura furnizarea de bunuri către consumatori la costuri minime de transport. Indicatorul de eficiență Z este costul total al transportului mărfurilor pe unitatea de timp (min Z).

1. Subiectul și obiectivele studiului operațiunilor din economie. Concepte de bază ale teoriei cercetării operaționale.

Subiectul cercetării operaționale îl reprezintă sistemele de management organizațional sau organizațiile care constau dintr-un număr mare de unități care interacționează care nu sunt întotdeauna consecvente între ele și pot fi opuse.

Scopul cercetării operaționale este de a fundamenta cantitativ deciziile luate cu privire la managementul organizațiilor

Soluția care se dovedește a fi cea mai benefică pentru întreaga organizație se numește optimă, iar soluția care este cea mai benefică pentru unul sau mai multe departamente va fi suboptimă.

Cercetarea operațională este o știință care se ocupă cu dezvoltarea și aplicarea practică a metodelor pentru cel mai optim management al sistemelor organizaționale.

O operațiune este orice eveniment (sistem de acțiuni) unit printr-un singur plan și îndreptat spre atingerea unui scop.

Scopul cercetării operaționale este o justificare cantitativă preliminară a soluțiilor optime.

Orice alegere definită a parametrilor în funcție de noi se numește soluție. Soluțiile sunt numite optime dacă sunt preferate altora dintr-un motiv sau altul.

Parametrii, a căror totalitate formează o soluție, se numesc elemente ale soluției.

Setul de soluții admisibile sunt date condiții care sunt fixe și nu pot fi încălcate.

Indicator de performanță - o măsură cantitativă care vă permite să comparați diferite soluții din punct de vedere al eficienței.

2. Conceptul de planificare și management al rețelei. Model de rețea al procesului și elementelor acestuia.

Metoda de lucru cu graficele de rețea - planificarea rețelei - se bazează pe teoria grafurilor. Tradus din greacă, un graf (grafpho - scriu) reprezintă un sistem de puncte, dintre care unele sunt legate prin linii - arce (sau muchii). Acesta este un model topologic (matematic) al sistemelor care interacționează. Cu ajutorul graficelor, este posibil să se rezolve nu numai problemele de planificare a rețelei, ci și alte probleme. Metoda de planificare a rețelei este utilizată la planificarea unui complex de lucrări interconectate. Vă permite să vizualizați succesiunea organizațională și tehnologică a muncii și să stabiliți relația dintre acestea. În plus, vă permite să coordonați operațiuni de diferite grade de complexitate și să identificați operațiunile de care depinde durata întregii lucrări (adică evenimentul organizațional), precum și să vă concentrați pe finalizarea la timp a fiecărei operațiuni.

Baza planificării și managementului rețelei este modelul de rețea (SM), care modelează un set de activități și evenimente interconectate care reflectă procesul de realizare a unui obiectiv specific. Poate fi prezentat sub forma unui grafic sau a unui tabel.

Concepte de bază ale modelului de rețea:

Eveniment, muncă, cale.

Evenimentele sunt rezultatele executării uneia sau mai multor activități. Nu au prelungire în timp.

O cale este un lanț de lucru care urmează unul după altul, conectând vârfurile inițiale și finale.

Durata unei căi este determinată de suma duratelor lucrărilor sale constitutive.

3. Construirea și ordonarea diagramei de rețea.

Un model de rețea este utilizat ca model care reflectă interrelațiile tehnologice și organizaționale ale procesului de lucrări de construcție și instalare în sistemele de planificare și management al rețelei (SPU).

Un model de rețea este o reprezentare grafică a proceselor, a cărei implementare duce la atingerea unuia sau mai multor obiective, indicând relațiile stabilite între aceste procese. Diagrama de rețea este un model de rețea cu parametri de timp calculati.

Structura diagramei de rețea, care determină dependența reciprocă a muncii și a evenimentelor, se numește topologia sa.

Munca este un proces de producție care necesită timp, forță de muncă și resurse materiale, care, atunci când este efectuată, duce la obținerea unor rezultate.

Dependența (operă fictivă) care nu necesită timp este reprezentată de o săgeată punctată. Munca simulată este folosită într-o diagramă de rețea pentru a arăta relațiile dintre evenimente și activități.

În programul de rețea se utilizează timpul, costul și alte caracteristici ale muncii.

Durata lucrării - timpul de execuție a acestei lucrări în zile lucrătoare sau alte unități de timp, același pentru toate lucrările din rețea. Durata lucrării poate fi fie o anumită (deterministă) fie o variabilă aleatoare specificată de legea distribuției sale.

Costul lucrării reprezintă costurile directe necesare implementării acesteia, în funcție de durata și condițiile acestei lucrări.

Resursele se caracterizează prin necesitatea unităților fizice necesare pentru realizarea acestei lucrări.

Calitatea, fiabilitatea și alți indicatori ai muncii servesc ca caracteristici suplimentare ale muncii.

Un eveniment este faptul de finalizare a unuia sau mai multor joburi, necesare si suficiente pentru inceperea unuia sau mai multor joburi ulterioare. Fiecărui eveniment i se atribuie un număr, numit cod. Fiecare job este definit de două evenimente: un cod de eveniment de început, notat cu i, și un cod de eveniment de final, notat cu j.

Evenimentele care nu au activități anterioare se numesc evenimente inițiale; evenimente care nu au ulterioare – finale.

1 Direcția de construire a unei rețele poate fi de altă natură. Un grafic de rețea poate fi construit de la evenimentul inițial la cel final și de la cel final la inițial (inițial), precum și de la oricare dintre evenimente la cel inițial sau final.

2 La construirea unei rețele, sunt rezolvate următoarele întrebări:

Ce lucrare (lucrare) trebuie făcută pentru a începe această lucrare;

Ce lucrare ar trebui făcută în paralel cu această lucrare;

3 Orarul inițial al rețelei se construiește fără a ține cont de durata activităților care alcătuiesc rețeaua.

4 Forma graficului trebuie să fie simplă și ușor de perceput vizual.

5 Între două evenimente nu poate exista decât o singură lucrare. În timpul construcției clădirilor și structurilor, lucrările se pot executa secvențial, în paralel sau simultan, unele în serie și altele în paralel, în urma cărora se formează diverse dependențe între lucrările individuale.

Numerotarea (codificarea) evenimentelor se realizează după finalizarea construcției rețelei, începând de la evenimentul inițial până la cel final.

4. Calea critică a diagramei de rețea. Rezerve de timp. Datele timpurii și târzii ale evenimentelor și activităților în diagrama de rețea.

Într-o diagramă de rețea, pot exista mai multe căi între evenimentele de început și de sfârșit. Calea cu cea mai mare durată se numește cale critică. Calea critică determină durata totală a activităților. Toate celelalte căi au o durată mai scurtă și, prin urmare, munca efectuată în ele are rezerve de timp.

Calea critică este indicată pe diagrama rețelei prin linii îngroșate sau duble (săgeți).

Două concepte sunt de o importanță deosebită atunci când se elaborează o diagramă de rețea:

Începutul timpuriu al lucrării - perioada înainte de care este imposibil să începeți această lucrare fără a încălca secvența tehnologică acceptată. Este determinată de calea cea mai lungă de la evenimentul inițiator până la începutul acestei lucrări.

Terminare tardivă este cea mai recentă dată de încheiere pentru un job care nu mărește durata totală a jobului. Este determinată de calea cea mai scurtă de la un eveniment dat până la finalizarea tuturor lucrărilor.

Terminarea timpurie este termenul până la care lucrarea nu poate fi finalizată. Este egal cu începerea timpurie plus durata acestei lucrări.

Început târziu - perioada după care este imposibil să începeți această lucrare fără a crește durata totală a construcției. Este egal cu terminarea târzie minus durata lucrării date.

Dacă evenimentul este sfârșitul unui singur job (adică doar o săgeată este direcționată către acesta), atunci sfârșitul timpuriu al acestui job coincide cu începutul timpuriu al celui următor.

Rezerva totală (plină) este timpul maxim pentru care execuția acestei lucrări poate fi amânată fără creșterea duratei totale a lucrării. Este determinată de diferența dintre începutul târziu și devreme (sau sfârșitul târziu și devreme - care este același).

Rezerva privata (gratuita) - acesta este timpul maxim pentru care puteti intarzia executarea acestei lucrari, fara a modifica inceperea anticipata a celei urmatoare. Această alternativă este posibilă numai atunci când evenimentul include două sau mai multe activități (dependențe), de ex. două sau mai multe săgeți (solide sau punctate) indică spre ea. Apoi, doar unul dintre aceste locuri de muncă va avea o terminare timpurie care coincide cu o începere timpurie a postului următor, în timp ce pentru celelalte acestea vor fi valori diferite. Această diferență pentru fiecare lucrare va fi rezerva sa privată.

5. Programare dinamică. Principiul lui Bellman al optimității și controlului.

Programarea dinamică este una dintre cele mai puternice tehnici de optimizare. Sarcinile de luare a deciziilor raționale, alegerea celor mai bune opțiuni, control optim sunt tratate de specialiști de diverse profiluri. Programarea dinamică ocupă o poziţie specială printre metodele de optimizare. Această metodă este extrem de atractivă datorită simplității și clarității principiului său de bază - principiul optimității. Domeniul de aplicare al principiului optimității este extrem de larg, gama de probleme la care poate fi aplicat nu a fost încă pe deplin conturată. Încă de la început, programarea dinamică acționează ca un mijloc de soluționare practică a problemelor de optimizare.

Pe lângă principiul optimității, principala metodă de cercetare, un rol important în aparatul de programare dinamică îl joacă ideea de a scufunda o anumită problemă de optimizare într-o familie de probleme similare. A treia caracteristică, care o deosebește de alte metode de optimizare, este forma rezultatului final. Aplicarea principiului optimității și a principiului imersiunii în procese discrete în mai multe etape conduc la ecuații funcționale recurente în ceea ce privește valoarea optimă a criteriului de calitate. Ecuațiile rezultate fac posibilă scrierea secvenţială a controalelor optime pentru problema originală. Avantajul aici este că sarcina de calculare a controlului pentru întregul proces este împărțită într-un număr de sarcini mai simple de calculare a controlului pentru etapele individuale ale procesului.

Principalul dezavantaj al metodei este, în cuvintele lui Bellman, „blestemul dimensionalității” - complexitatea acesteia crește catastrofal odată cu creșterea dimensionalității problemei.

6. Problema repartizării fondurilor între întreprinderi.

Se poate spune că procedura de construire a unui control optim prin metoda programării dinamice este împărțită în două etape: preliminară și finală. În etapa preliminară, pentru fiecare pas, SOC se determină în funcție de starea sistemului (realizat ca urmare a pașilor anteriori), iar câștigul optim condiționat la toate etapele rămase, începând de la acesta, este și el dependent de stat. În etapa finală, se determină controlul optim (necondiționat) pentru fiecare pas. Optimizarea preliminară (condițională) se realizează pas cu pas în ordine inversă: de la ultimul pas la primul; optimizare finală (necondiționată) - tot pe trepte, dar într-o ordine firească: de la primul pas la ultimul. Dintre cele două etape de optimizare, prima este incomparabil mai importantă și consumatoare de timp. După încheierea primei etape, implementarea celei de-a doua etape nu prezintă nicio dificultate: nu mai rămâne decât să „citești” recomandările deja pregătite în prima etapă.

7. Enunțarea problemei programării liniare.

Programarea liniară este un instrument popular pentru rezolvarea problemelor economice care se caracterizează prin prezența unui criteriu (de exemplu, pentru a maximiza veniturile din producție prin alegerea optimă a unui program de producție sau, de exemplu, pentru a minimiza costurile de transport etc.) . Sarcinile economice sunt caracterizate de constrângeri de resurse (materiale și/sau financiare). Ele sunt scrise ca un sistem de inegalități, uneori ca egalități.

Din punctul de vedere al prognozării intervalelor de preț acceptabile (sau volumelor de vânzări) în cadrul unei metode neparametrice generalizate, utilizarea programării liniare înseamnă:

Criteriul este prețul MAX al următorului produs din grupul de interes f.

Variabilele controlate sunt prețurile tuturor produselor din grupa f.

Limitările problemei noastre de prognoză folosind metoda neparametrică generalizată sunt:

a) un sistem de inegalități (constrângeri asupra raționalității comportamentului consumatorului) (vezi 4.2. Prognoza în cadrul unei metode neparametrice generalizate);

b) cerința de nenegativitate a variabilelor controlate (în problema noastră de previziune, vom cere ca prețurile pentru produsele din grupa f să nu scadă sub 80% din prețurile la ultimul moment);

c) constrângere bugetară sub formă de egalitate - cerința ca valoarea costurilor pentru achiziționarea produselor din grupa f să fie constantă (ținând cont de inflația de 15%, de exemplu).

8. Metodă grafică de rezolvare a problemelor de programare liniară.

Metoda grafică se bazează pe interpretarea geometrică a unei probleme de programare liniară și este utilizată în principal în rezolvarea problemelor de spațiu bidimensional și doar a unor probleme de spațiu tridimensional, deoarece este destul de dificil să se construiască un politop de soluție care se formează ca rezultat al intersectării semispatiilor. Sarcina unui spațiu de dimensiuni mai mari de trei nu poate fi reprezentată grafic deloc.

Să fie dată problema de programare liniară într-un spațiu bidimensional, adică constrângerile conțin două variabile.

Găsiți valoarea minimă a unei funcții

(2.1) Z = С1х1+С2х2

a11x1 + a22x2 b1

(2.2)a21x1 + a22x2 b2

aM1x1 + aM2x2 bM

(2.3) x1 0, x2 0

Să presupunem că sistemul (2.2) în condiția (2.3) este consistent și poligonul său soluție este mărginit. Fiecare dintre inegalitățile (2.2) și (2.3), așa cum s-a menționat mai sus, definește un semiplan cu linii de limită: ai1x1 + ai2x2 + ai3x3 = bi,(i = 1, 2, ..., n), x1=0 , x2=0 . Funcția liniară (2.1) pentru valori fixe ale lui Z este ecuația unei drepte: C1x1 + C2x2 = const. Să construim un poligon de soluții ale sistemului de constrângeri (2.2) și un grafic al funcției liniare (2.1) pentru Z = 0 (Fig. 2.1). Atunci problemei date de programare liniară i se poate da următoarea interpretare. Aflați punctul poligonului soluție în care dreapta C1x1 + C2x2 = const este linia de sprijin și funcția Z atinge un minim.

Valorile Z = C1x1 + C2x2 cresc în direcția vectorului N = (C1, C2), așa că mutam linia Z = 0 paralel cu ea însăși în direcția vectorului X. Din fig. 2.1 rezultă că linia de două ori devine o referință față de poligonul soluțiilor (în punctele A și C), iar valoarea minimă este în punctul A. Coordonatele punctului A (x1, x2) se găsesc prin rezolvarea sistem de ecuații ale dreptelor AB și AE.

Dacă poligonul de decizie este o zonă poligonală nemărginită, atunci sunt posibile două cazuri.

Cazul 1. Linia dreaptă C1x1 + C2x2 = const, care se deplasează în direcția vectorului N sau opus acestuia, intersectează constant poligonul soluție și nu este o referință la acesta în niciun punct. În acest caz, funcția liniară este nemărginită pe poligonul soluție atât deasupra cât și dedesubt (Fig. 2.2).

Cazul 2. Linia dreaptă, în mișcare, devine totuși un suport relativ la poligonul soluțiilor (Fig. 2.2, a - 2.2, c). Apoi, în funcție de tipul de zonă, o funcție liniară poate fi mărginită de sus și nemărginită de jos (Fig. 2.2, a), mărginită de jos și nemărginită de sus (Fig. 2.2, b), sau mărginită atât de jos, cât și de dedesubt. de sus (Fig. 2.2, c).

9. Metoda simplex.

Metoda simplex este cea principală în programarea liniară. Rezolvarea problemei începe cu luarea în considerare a unuia dintre vârfurile poliedrului de condiții. Dacă vârful studiat nu corespunde maximului (minimului), atunci se deplasează la cel învecinat, crescând valoarea funcției de obiectiv la rezolvarea problemei la maxim și scăzând la rezolvarea problemei la minim. Astfel, trecerea de la un vârf la altul îmbunătățește valoarea funcției obiectiv. Deoarece numărul de vârfuri ale poliedrului este limitat, atunci într-un număr finit de pași se garantează găsirea valorii optime sau stabilirea faptului că problema este de nerezolvat.

Această metodă este universală, aplicabilă oricărei probleme de programare liniară în formă canonică. Sistemul de constrângeri aici este un sistem de ecuații liniare în care numărul de necunoscute este mai mare decât numărul de ecuații. Dacă rangul sistemului este r, atunci putem alege r necunoscute, pe care le vom exprima în termenii necunoscutelor rămase. Pentru certitudine, presupunem că sunt alese primele necunoscute consecutive X1, X2, ..., Xr. Atunci sistemul nostru de ecuații poate fi scris ca

Metoda simplex se bazează pe o teoremă numită teorema fundamentală a metodei simplex. Printre planurile optime pentru o problemă de programare liniară în formă canonică, există în mod necesar o soluție de referință la sistemul său de constrângeri. Dacă planul optim al problemei este unic, atunci acesta coincide cu o soluție de referință. Există foarte multe soluții de suport diferite pentru sistemul de constrângeri. Asadar, rezolvarea problemei in forma canonica ar putea fi cautata prin enumerarea solutiilor de referinta si alegerea dintre ele pe cea pentru care valoarea lui F este cea mai mare. Dar, în primul rând, toate soluțiile de referință sunt necunoscute și trebuie găsite și, în al doilea rând, în problemele reale există o mulțime de aceste soluții și enumerarea directă este cu greu posibilă. Metoda simplex este o anumită procedură de enumerare direcționată a soluțiilor de referință. Pe baza unei soluții de referință găsite anterior folosind un anumit algoritm al metodei simplex, calculăm o nouă soluție de referință pe care valoarea funcției obiectiv F nu este mai mică decât pe cea veche. După o serie de pași, ajungem la o soluție de referință, care este planul optim.

10. Enunțarea problemei transportului. Metode de determinare a planurilor de bază.

Există m puncte de plecare („furnizori”) și n puncte de consum („consumatori”) ale unui produs identic. Pentru fiecare articol sunt definite:

ai - volumele de producție ale furnizorului i, i = 1, …, m;

вj - cererea consumatorului j, j= 1,…,n;

cij - costul transportului unei unități de producție de la punctul Ai - al i-lea furnizor, la punctul Bj - al j-lea consumator.

Pentru claritate, este convenabil să prezentați datele sub forma unui tabel, care se numește tabelul costurilor de transport.

Este necesar să se găsească un plan de transport care să satisfacă pe deplin cererea tuturor consumatorilor, în timp ce ar exista suficiente provizii de furnizori, iar costurile totale de transport ar fi minime.

În planul de transport se înțelege volumul de trafic, adică. cantitatea de mărfuri care urmează să fie transportată de la al-lea furnizor la al-lea consumator. Pentru a construi un model matematic al problemei, este necesar să introduceți m n variabile хij, i= 1,…, n, j= 1, …, m, fiecare variabilă хij desemnând volumul de trafic din punctul Ai către punctul Bj. Setul de variabile X = (xij) va fi planul care trebuie găsit pe baza enunțului problemei.

Aceasta este o condiție pentru rezolvarea sarcinilor de transport închise și deschise (ZTZ).

Evident, pentru rezolvarea problemei 1, este necesar ca cererea totală să nu depășească volumul producției de la furnizori:

Dacă această inegalitate este îndeplinită strict, atunci problema se numește „deschisă” sau „dezechilibrată”, dar dacă , atunci problema se numește o problemă de transport „închisă” și va avea forma (2):

Stare de echilibru.

Aceasta este o condiție pentru rezolvarea sarcinilor de transport închise (ZTZ).

11. Algoritm pentru rezolvarea problemei transportului.

Aplicarea algoritmului necesită respectarea unui număr de cerințe preliminare:

1. Costul transportului unei unități de produs din fiecare punct de producție la fiecare destinație trebuie să fie cunoscut.

2. Trebuie cunoscut stocul de produse la fiecare punct de producție.

3. Trebuie cunoscute cerințele alimentare în fiecare punct de consum.

4. Oferta totală trebuie să fie egală cu cererea totală.

Algoritmul pentru rezolvarea problemei transportului constă din patru etape:

Etapa I. Prezentarea datelor sub forma unui tabel standard și căutarea oricărei alocări acceptabile de resurse. O distribuție acceptabilă a resurselor este astfel încât să satisfacă întreaga cerere la destinații și să elimine întreaga ofertă de produse din punctele de producție.

Etapa 2. Verificarea optimității alocării resurselor obținute

Etapa 3. Dacă distribuția rezultată a resurselor nu este optimă, atunci resursele sunt redistribuite, reducând costul transportului.

Etapa 4. Reverificarea optimității alocării resurselor obținute.

Acest proces iterativ se repetă până când se obține o soluție optimă.

12. Modele de gestionare a stocurilor.

În ciuda faptului că orice model de gestionare a stocurilor este conceput pentru a răspunde la două întrebări de bază (când și cât de mult), există un număr semnificativ de modele care utilizează o varietate de instrumente matematice pentru a construi.

Această situație se explică prin diferența dintre condițiile inițiale. Baza principală pentru clasificarea modelelor de gestionare a stocurilor este natura cererii de produse depozitate (remintim că, din punctul de vedere al unei gradații mai generale, acum luăm în considerare doar cazurile cu cerere independentă).

Deci, în funcție de natura cererii, modelele de gestionare a stocurilor pot fi

determinat;

probabilistică.

La rândul său, cererea deterministă poate fi statică, când intensitatea consumului nu se modifică în timp, sau dinamică, când cererea sigură se poate modifica în timp.

Cererea probabilistică poate fi staționară, atunci când densitatea de probabilitate a cererii nu se modifică în timp, și nestaționară, când funcția de densitate de probabilitate se modifică în timp. Clasificarea de mai sus este ilustrată în figură.

Cel mai simplu este cazul unei cereri statice deterministe de produse. Cu toate acestea, acest tip de consum este destul de rar în practică. Cele mai complexe modele sunt modele de tip non-staționar.

Pe lângă natura cererii de produse, atunci când se construiesc modele de gestionare a stocurilor, trebuie luați în considerare mulți alți factori, de exemplu:

termenii de executare a comenzilor. Durata perioadei de recoltare poate fi constantă sau poate fi o variabilă aleatorie;

procesul de reaprovizionare. Poate fi instantaneu sau distribuit în timp;

prezența restricțiilor privind capitalul de lucru, spațiul de depozitare etc.

13. Sisteme de așteptare (QS) și indicatori ai eficienței acestora.

Sistemele de așteptare (QS) sunt sisteme de tip special care implementează executarea repetată a sarcinilor de același tip. Astfel de sisteme joacă un rol important în multe domenii ale economiei, finanțelor, producției și vieții de zi cu zi. Ca exemple de OCM în domeniul financiar și economic; În sferă, bănci de diferite tipuri (comerciale, de investiții, ipotecare, inovatoare, de economii), organizații de asigurări, societăți de stat pe acțiuni, societăți comerciale, firme, asociații, cooperative, inspectorate fiscale, servicii de audit, diverse sisteme de comunicații (inclusiv centrale telefonice). ), complexe de încărcare și descărcare (porturi, stații de marfă), benzinării, diverse întreprinderi și organizații din sectorul serviciilor (magazine, birouri de informații, coafor, case de bilete, case de schimb valutar, ateliere de reparații, spitale). Ca un fel de QS pot fi considerate și sisteme precum rețelele de calculatoare, sistemele de colectare, stocarea și prelucrarea informațiilor, sistemele de transport, site-urile de producție automatizate, liniile de producție, diverse sisteme militare, în special sistemele de apărare antiaeriană sau antirachetă.

Fiecare QS include în structura sa un anumit număr de dispozitive de serviciu, care sunt numite canale de serviciu (dispozitive, linii). Rolul canalelor poate fi jucat de diverse aparate, persoane care efectuează anumite operațiuni (casieri, operatori, coafor, vânzători), linii de comunicații, mașini, macarale, echipe de reparații, căi ferate, benzinării etc.

Sistemele de așteptare pot fi cu un singur canal sau multicanal.

Fiecare QS este conceput pentru a servi (executa) un anumit flux de aplicații (cerințe) care ajung la intrarea sistemului în cea mai mare parte nu în mod regulat, ci în momente aleatorii. Solicitările de service, în acest caz, durează, de asemenea, nu un timp constant, cunoscut, ci un timp aleatoriu, care depinde de multe motive aleatorii, uneori necunoscute nouă. După deservirea cererii, canalul este eliberat și este gata să primească următoarea solicitare. Natura aleatorie a fluxului de cereri și timpul serviciului acestora duce la o încărcare inegală a QS-ului: alteori, cererile neservite se pot acumula la intrarea QS-ului, ceea ce duce la o supraîncărcare a QS-ului și, uneori, cu canale libere, nu va exista nicio solicitare la intrarea QS-ului, ceea ce duce la o subîncărcare a QS-ului, adică de ex. pentru a-și opri canalele. Aplicațiile care se acumulează la intrarea în QS fie „intră” în coadă, fie, din cauza imposibilității de a rămâne în continuare în coadă, lasă QS-ul neservit.

Indicatori de performanță pentru funcționarea perechii „QS – consumator”, unde consumatorul este înțeles ca întregul set de aplicații sau o parte din sursa acestora (de exemplu, venitul mediu adus de QS pe unitatea de timp etc.). Acest grup de indicatori este util în cazurile în care unele venituri primite din cererile de servicii și costurile serviciilor sunt măsurate în aceleași unități. Acești indicatori sunt de obicei destul de specifici și sunt determinați de specificul QS, cererile de servicii și disciplina de serviciu.

14. Ecuații de dinamică pentru stări probabiliste (ecuațiile lui Kolmogorov). Limitarea probabilităților stărilor.

Diferențiând formal ecuația Kolmogorov–Chapman în raport cu s la s = 0, obținem ecuația Kolmogorov directă:

Diferențiând formal ecuația Kolmogorov-Chapman în raport cu t la t = 0, obținem ecuația inversă a lui Kolmogorov

Trebuie subliniat că pentru spațiile cu dimensiuni infinite, operatorul nu mai este neapărat continuu și poate să nu fie definit peste tot, de exemplu, să fie un operator diferențial în spațiul distribuțiilor.

În cazul în care numărul de stări ale sistemului S este finit și este posibil să se treacă de la fiecare stare (pentru unul sau altul număr de pași) la o altă stare, atunci probabilitățile limită ale stărilor există și, de asemenea, nu depind de starea inițială a sistemului.

Pe fig. prezintă un grafic al stărilor și tranzițiilor care îndeplinesc condiția: din orice stare, sistemul poate trece mai devreme sau mai târziu în orice altă stare. Condiția nu va fi îndeplinită atunci când direcția săgeții 4-3 de pe graficul din fig. este inversată.

Să presupunem că condiția enunțată este îndeplinită și, prin urmare, există probabilitățile marginale:

Probabilitățile limită vor fi notate cu aceleași litere ca și probabilitățile stărilor, în timp ce ele înseamnă numere, nu variabile (funcții de timp).

Este clar că probabilitățile limită ale stărilor ar trebui să se adună la unitate: în consecință, un anumit mod staționar limitator este stabilit în sistem la: lăsați sistemul și schimba propriile stări aleatoriu, dar probabilitatea fiecăreia dintre aceste stări nu depinde la timp și fiecare dintre ele se realizează cu o probabilitate constantă, care este timpul relativ mediu pe care sistemul îl petrece în această stare.

15. Procesul morții și al reproducerii.

Prin un proces Markov de moarte și reproducere cu timp continuu înțelegem un s.p. care poate lua numai valori întregi nenegative; modificări în acest proces pot apărea în orice moment t, în timp ce în orice moment poate fie să crească cu unul, fie să rămână neschimbat.

Fluxurile de multiplicare λi(t) sunt fluxurile Poisson care conduc la o creștere a funcției X(t). În consecință, μi(t) sunt fluxuri de moarte care conduc la o scădere a funcției X(t).

Să compunem ecuațiile lui Kolmogorov conform graficului:

Dacă un fir cu un număr finit de stări:

Sistemul de ecuații Kolmogorov pentru procesul de moarte și reproducere cu un număr limitat de stări are forma:

Procesul de reproducere pură este un astfel de proces de moarte și reproducere, în care intensitățile tuturor fluxurilor morții sunt egale cu zero.

Procesul morții pure este un astfel de proces de moarte și reproducere, în care intensitățile tuturor fluxurilor de reproducere sunt egale cu zero.

16. Sisteme de așteptare cu defecțiuni.

Cea mai simplă dintre problemele luate în considerare în cadrul teoriei stării de așteptare este modelul unui QS cu un singur canal cu defecțiuni sau pierderi.

Trebuie remarcat faptul că în acest caz numărul de canale este 1 (). Acest canal primește un flux Poisson de cereri, a cărui intensitate este egală cu . Timpul afectează intensitatea:

Dacă o aplicație ajunge pe un canal care în prezent nu este gratuit, este respinsă și nu mai este listată în sistem. Aplicațiile sunt deservite în timp aleatoriu, a cărui distribuție este realizată în conformitate cu legea exponențială cu parametrul:

17. Sisteme de asteptare cu asteptare.

O solicitare care sosește într-un moment în care canalul este ocupat este pusă în coadă și așteaptă serviciul.

Un sistem cu o lungime limitată la coadă. Să presupunem mai întâi că numărul de locuri în coadă este limitat de numărul m, adică dacă un client sosește într-un moment în care există deja m clienți în coadă, acesta lasă sistemul neservit. În viitor, dacă m tinde spre infinit, obținem caracteristicile unui QS cu un singur canal fără restricții privind lungimea cozii.

Vom numerota stările QS în funcție de numărul de solicitări din sistem (atât deservite, cât și în așteptare):

— canalul este liber;

— canalul este ocupat, nu există coadă;

— canalul este ocupat, o cerere este în coadă;

— canalul este ocupat, k - 1 cereri sunt în coadă;

- canalul este ocupat, tone de aplicații sunt în coadă.

18. Metode de luare a deciziilor în condiţii de conflict. Jocuri Matrix. Jocuri de strategie pure și mixte.

Un joc cu matrice este un joc final cu sumă zero de doi jucători, în care câștigul jucătorului 1 este dat sub forma unei matrice (rândul matricei corespunde numărului strategiei aplicate a jucătorului 2, coloana corespunde la numărul strategiei aplicate a jucătorului 2; la intersecția rândului și coloanei matricei este câștigul jucătorului 1, relevant pentru strategiile aplicate).

Pentru jocurile cu matrice, se dovedește că oricare dintre ele are o soluție și poate fi găsită cu ușurință prin reducerea jocului la o problemă de programare liniară.

Jocul cu matrice cu sumă zero pentru doi jucători poate fi văzut ca următorul joc abstract pentru doi jucători.

Primul jucător are m strategii i = 1,2,...,m, al doilea are n strategii j = 1,2,...,n. Fiecărei perechi de strategii (i, j) i se atribuie un număr aij, care exprimă profitul jucătorului 1 în detrimentul jucătorului 2, dacă primul jucător acceptă strategia sa a I-a, iar 2 - a-a strategie.

Fiecare dintre jucători face o mișcare: jucătorul 1 își alege a-a strategie (i=), 2 - a-a strategie (j=), după care jucătorul 1 primește câștigul aij în detrimentul jucătorului 2 (dacă aij

Fiecare strategie a jucătorului i=; j = este adesea numit o strategie pură.

Definiție. Strategia mixtă a unui jucător este setul complet de probabilități de aplicare a strategiilor sale pure.

Astfel, dacă jucătorul 1 are m strategii pure 1,2,...,m, atunci strategia sa mixtă x este un set de numere x = (x1,..., xm) care satisfac relațiile

xi³ 0 (i= 1,m), =1.

În mod similar, pentru jucătorul 2, care are n strategii pure, strategia mixtă y este mulțimea de numere

y = (y1, ..., yn), yj ³ 0, (j = 1,n), = 1.

Deoarece de fiecare dată când un jucător folosește o strategie pură exclude utilizarea alteia, strategiile pure sunt evenimente incompatibile. De asemenea, acestea sunt singurele evenimente posibile.

Strategia pură este un caz special de strategie mixtă. Într-adevăr, dacă într-o strategie mixtă se aplică orice i-a strategie pură cu probabilitatea 1, atunci toate celelalte strategii pure nu sunt aplicate. Și această strategie pură este un caz special de strategie mixtă. Pentru a păstra secretul, fiecare jucător își aplică propriile strategii, indiferent de alegerea celuilalt jucător.

19. Metoda geometrică de rezolvare a unui joc matricial.

Soluția jocurilor de dimensiunea 2xn sau nx2 permite o interpretare geometrică clară. Astfel de jocuri pot fi rezolvate grafic.

Pe planul XY, de-a lungul abscisei, punem deoparte un singur segment A1A2 (Figura 5.1). Fiecare punct al segmentului este asociat cu o strategie mixtă U = (u1, u2). Mai mult, distanța de la un punct intermediar U până la capătul drept al acestui segment este probabilitatea u1 de a alege strategia A1, distanța până la capătul din stânga este probabilitatea u2 de a alege strategia A2. Punctul A1 corespunde strategiei pure A1, punctul A2 corespunde strategiei pure A2.

La punctele A1 și A2, restabilim perpendicularele și amânăm câștigurile jucătorilor pe ele. Pe prima perpendiculară (coincidând cu axa OY), arătăm câștigul jucătorului A atunci când folosește strategia A1, pe a doua - când folosește strategia A2. Dacă jucătorul A folosește strategia A1, atunci câștigul său cu strategia B1 a jucătorului B este 2, iar cu strategia B2 este 5. Numerele 2 și 5 de pe axa OY corespund punctelor B1 și B2. În mod similar, pe a doua perpendiculară găsim punctele B „1 și B” 2 (retribuții 6 și 4).

Conectând punctele B1 și B"1, B2 și B"2, obținem două linii drepte, distanța de la care până la axa OX determină profitul mediu pentru orice combinație a strategiilor corespunzătoare.

De exemplu, distanța de la orice punct al segmentului B1B"1 la axa OX determină câștigul mediu al jucătorului A pentru orice combinație de strategii A1 și A2 (cu probabilități u1 și u2) și strategia B1 a jucătorului B.

Ordonatele punctelor aparținând liniei întrerupte B1MB"2 determină câștigul minim al jucătorului A atunci când folosește orice strategii mixte. Această valoare minimă este cea mai mare în punctul M, prin urmare, acest punct corespunde strategiei optime U* = (,), iar ordonata sa este egală cu prețul jocului v .

Găsim coordonatele punctului M ca fiind coordonatele punctului de intersecție a dreptelor B1B"1 și B2B"2.

Pentru a face acest lucru, trebuie să cunoașteți ecuațiile liniilor. Puteți compune astfel de ecuații folosind formula pentru ecuația unei linii drepte care trece prin două puncte:

Să compunem ecuațiile de linii pentru problema noastră.

Linia B1B"1: = sau y = 4x + 2.

B2B direct „2: = sau y = -x + 5.

Obținem sistemul: y = 4x + 2,

Să rezolvăm: 4x + 2 = -x + 5,

x = 3/5, y = -3/5 + 5 = 22/5.

Deci U = (2/5, 3/5), v = 22/5.

20. Jocuri Bimatrix.

Un joc bimatrix este un joc finit de doi jucători cu o sumă diferită de zero, în care plățile fiecărui jucător sunt date prin matrice separat pentru jucătorul corespunzător (în fiecare matrice, rândul corespunde strategiei jucătorului 1, coloana corespunde strategiei jucătorului 2, la intersecția rândului și coloanei din prima matrice este câștigul jucătorului 1, în a doua matrice - câștigul jucătorului 2.)

Pentru jocurile bimatrice s-a dezvoltat și teoria comportamentului optim al jucătorilor, dar rezolvarea unor astfel de jocuri este mai dificilă decât cele convenționale cu matrice.

21. Jocuri statistice. Principii și criterii pentru luarea deciziilor în condiții de incertitudine totală și parțială.

În cercetarea operațională, se obișnuiește să se facă distincția între trei tipuri de incertitudini:

incertitudinea obiectivelor;

incertitudinea cunoștințelor noastre despre mediu și factorii care acționează în acest fenomen (incertitudinea naturii);

incertitudinea acțiunilor unui partener sau adversar activ sau pasiv.

În clasificarea de mai sus, tipul de incertitudini este considerat din punctul de vedere al unuia sau altui element al modelului matematic. Deci, de exemplu, incertitudinea obiectivelor se reflectă în formularea problemei în alegerea fie a criteriilor individuale, fie a întregului vector al unui efect util.

Pe de altă parte, celelalte două tipuri de incertitudini afectează în principal formularea funcției obiective a ecuațiilor de constrângere și metoda deciziei. Desigur, afirmația de mai sus este mai degrabă condiționată, ca, într-adevăr, orice clasificare. O prezentăm doar pentru a evidenția câteva trăsături suplimentare ale incertitudinilor care trebuie reținute în procesul decizional.

Cert este că, pe lângă clasificarea de mai sus a incertitudinilor, trebuie să se țină cont de tipul (sau „tipul”) lor din punctul de vedere al relației lor cu aleatorietatea.

Pe această bază, se poate distinge între incertitudinea stocastică (probabilistă), când factorii necunoscuți sunt stabili statistic și, prin urmare, sunt obiecte obișnuite ale teoriei probabilităților - variabile aleatoare (sau funcții aleatoare, evenimente etc.). În acest caz, toate caracteristicile statistice necesare (legile de distribuție și parametrii acestora) trebuie cunoscute sau determinate la stabilirea problemei.

Un exemplu de astfel de sarcini poate fi, în special, un sistem de întreținere și reparare a oricărui tip de echipament, un sistem de organizare a răririi etc.

Un alt caz extrem poate fi incertitudinea non-stohastică (după E.S. Wentzel - „incertitudine proastă”), în care nu există ipoteze despre stabilitatea stocastică. În sfârșit, putem vorbi despre un tip intermediar de incertitudine, atunci când o decizie este luată pe baza unor ipoteze despre legile de distribuție a variabilelor aleatoare. În același timp, decidentul trebuie să țină cont de pericolul unei discrepanțe între rezultatele sale și condițiile reale. Acest risc de nepotrivire este formalizat cu ajutorul coeficienților de risc.

Luarea deciziilor de risc se poate baza pe unul dintre următoarele criterii:

criteriul valorii așteptate;

combinații de valoare așteptată și varianță;

nivelul limită cunoscut;

cel mai probabil eveniment în viitor.

Operațiune se numeste orice eveniment (sistem de actiuni), unit printr-un singur plan si indreptat spre atingerea unui scop anume. Operația este întotdeauna controlat eveniment, adică se poate dispune de metoda de alegere a unor parametri care caracterizează organizarea acesteia. Aceste opțiuni sunt numite variabile de control.

Orice alegere definită a unor astfel de variabile este numită decizie. Deciziile pot fi de succes și nereușite, rezonabile și nerezonabile. Optimal numiți astfel de soluții care, după unele criterii, sunt de preferat altora.

Scopul cercetării operaționale este o justificare cantitativă preliminară a soluțiilor optime, dintre care pot fi mai multe. Alegerea finală a unei decizii depășește sfera cercetării operaționale și se face prin intermediul așa-numitei teorii a deciziei.

Orice sarcină de cercetare operațională are condiții inițiale „disciplinare”, adică. astfel de date inițiale care sunt fixate de la bun început și nu pot fi încălcate. Împreună, ele formează așa-numitul set de soluții posibile.

Pentru a compara eficacitatea diferitelor soluții, trebuie să aveți un criteriu cantitativ numit indicator de performanta(sau funcție obiectivă). Acest indicator este ales pentru a reflecta orientarea țintă a operațiunii.

Adesea operația este însoțită de acțiunea unor factori aleatori. Apoi, nu valoarea în sine pe care am dori să o optimizăm este luată ca indicator al eficienței, ci valoarea sa medie (sau așteptarea matematică).

Uneori, o operație însoțită de factori aleatori urmărește un astfel de scop. A, care poate fi atins complet sau deloc (cum ar fi „da – nu”). Apoi probabilitatea atingerii acestui obiectiv este aleasă ca indicator al eficienței. p(A). (Dacă p(A) = 0 sau 1, apoi ajungem la binecunoscuta problemă „cutie neagră” în cibernetică.)

Alegerea greșită a indicatorului de performanță este foarte periculoasă. Operațiunile organizate după un criteriu ales fără succes pot duce la costuri și pierderi nejustificate. (De exemplu, „ax” ca principal criteriu de evaluare a activității economice a unei întreprinderi.)

1.3. Declarație generală a sarcinii de cercetare operațională

Sarcinile de cercetare operațională se împart în două categorii: a) directe și b) inverse.

Sarcini directe răspunde la întrebarea: care va fi indicatorul de eficiență Z daca in conditii date y  Y se va lua o decizie X  X. Pentru a rezolva o astfel de problemă se construiește un model matematic care permite exprimarea indicatorului de eficiență prin condiții date și o soluție și anume:

Unde
factori dați (date inițiale),

variabile de control (soluție),

Z– indicator de performanță (funcție obiectivă),

F– dependenţa funcţională între variabile.

Această dependență în diferite modele este exprimată în moduri diferite. Relație între Și de obicei exprimate ca limite asupra

Dacă tipul de dependenţă F cunoscut, apoi indicatorul Z se găseşte prin substituţie directă Și la această funcționalitate.

Probleme inverse raspunde la intrebarea: cum, in conditiile date alege o soluție
astfel încât indicatorul de performanţă Zîntors la maxim (minim). O astfel de problemă se numește problemă de optimizare a soluției.

Să se rezolve problema directă, adică. este setat modelul de operare si tipul de dependenta F celebru. Atunci problema inversă (adică problema de optimizare) poate fi formulată după cum urmează.

Am vrut să găsesc o astfel de decizie
la care indicatorul de eficienţă Z = opta:

Această formulă se citește astfel: Z există o valoare optimă
preluate toate soluţiile incluse în setul de soluţii posibile X.

Metoda de căutare a extremumului indicatorului de eficiență Zși soluția optimă asociată ar trebui să fie întotdeauna alese în funcție de caracteristicile funcției Fși tipul de constrângeri impuse soluției. (De exemplu, o problemă clasică de programare liniară.)

Cercetare operațională- o știință care se ocupă cu dezvoltarea și aplicarea practică a metodelor matematice, cantitative pentru a justifica deciziile în toate domeniile activității umane cu scop (management organizațional eficient).

Caracteristici comune ale cercetării operaționale

În fiecare sarcină, vorbim despre un fel de eveniment care urmărește un scop specific.

Sunt stabilite unele condiții care caracterizează situația (inclusiv mijloacele de care putem dispune).

În cadrul acestor condiții, este necesar să se ia o astfel de decizie încât evenimentul planificat să fie într-un anumit sens cel mai profitabil.

Caracteristicile cercetării operaționale

O abordare sistematică a analizei problemei puse înseamnă că o anumită sarcină trebuie luată în considerare din punctul de vedere al influenței sale asupra criteriului de funcționare a întregului sistem.

Cel mai mare efect poate fi atins numai cu cercetarea continuă, care asigură continuitatea în trecerea de la o sarcină la alta, apărută în cursul rezolvării celei anterioare.

Deși scopul cercetării operaționale este găsirea soluției optime, dar din cauza complexității calculării problemelor combinatorii, acestea se limitează la găsirea unei soluții „suficient de bună”.

Cercetarea operațională se desfășoară într-un complex, în multe domenii. Pentru realizarea studiului se creează grupuri operaționale:

Concepte de bază ale cercetării operaționale

OPERARE - orice eveniment controlat (adică depinde de alegerea parametrilor), unit printr-un singur plan și care vizează atingerea unui scop.

SOLUȚIE - orice alegere definită a parametrilor în funcție de noi.

SOLUȚII OPTIME – deciziile dintr-un motiv sau altul sunt de preferat altora.

SCOPUL STUDIULUI DE OPERAȚIE este o fundamentare cantitativă preliminară a soluțiilor optime.

ELEMENTE DE SOLUȚIE - parametri, a căror totalitate formează o soluție.

INDICATORUL DE PERFORMANȚĂ (FUNȚIA ȚINTĂ) este un criteriu cantitativ care permite compararea diferitelor soluții din punct de vedere al eficienței și reflectă orientarea țintă a operațiunii (W => max sau W => min).

Cea mai bună soluție este cea care contribuie la atingerea scopului în măsura maximă.

Conceptul de model matematic al unei operații

O descriere schematică, simplificată a unei operații folosind unul sau altul aparat matematic, care reflectă cele mai importante caracteristici ale operației, toți factorii esențiali de care depinde în principal succesul operației.

Probleme directe și inverse ale cercetării operaționale

PROBLEME DIRECTE răspund la întrebarea ce se va întâmpla dacă, în condiții date, luăm o decizie x X, adică. care va fi indicatorul de eficiență W (sau un număr de indicatori).

Pentru a rezolva o astfel de problemă, se construiește un covoraș. un model care vă permite să exprimați unul sau mai mulți indicatori de performanță prin condiții și elemente de soluție date.

PROBLEME INVERSE răspund la întrebarea cum să alegeți o soluție x pentru ca indicatorul de eficiență W să se întoarcă la maxim (minim).

Aceste sarcini sunt mai dificile. Ele pot fi rezolvate printr-o simplă enumerare de soluții la probleme directe.

Când însă numărul de soluții este mare, se folosesc metode de enumerare dirijată, în care soluția optimă se găsește prin efectuarea succesive de „încercări” sau aproximări, fiecare dintre ele apropiindu-ne de cea optimă dorită.

Capitolul 1. Subiectul și sarcinile cercetării operaționale.

§ 1. Ce este cercetarea operațională și ce face.

§ 2. Concepte şi principii de bază ale cercetării operaţionale.

§ 3. Modele matematice ale operaţiilor.

Capitolul 2. Varietăți de sarcini în cercetarea operațională și abordări ale soluționării acestora.

§ 4. Probleme directe şi inverse ale cercetării operaţionale. Sarcini deterministe.

§ 5. Problema alegerii unei soluţii în condiţii de incertitudine.

§ 6. Probleme multicriteriale ale cercetării operaţionale. „Abordarea sistemelor”.

Capitolul 3. Programarea liniară.

§ 7. Probleme de programare liniara.

§ 8. Problema principală a programării liniare.

§ 9. Existenta unei solutii 03LP si modalitati de gasire a acesteia.

§ 10. Problema transportului de programare liniara.

§ 11. Probleme de programare intregi. Conceptul de programare neliniară.

Capitolul 4. Programare dinamică.

§ 12. Metoda de programare dinamică.

§ 13. Exemple de rezolvare a problemelor de programare dinamică.

§ 14. Problema programării dinamice în formă generală. Principiul optimității.

capitolul 5 procese aleatorii Markov.

§ 15. Conceptul unui proces Markov.

§ 16. Fluxuri de evenimente.

§ 17. Ecuaţiile lui Kolmogorov pentru probabilităţi de stare. Probabilitățile finale ale stărilor.

Capitolul 6

§ 18. Sarcini ale teoriei cozii de aşteptare. Clasificarea sistemelor de aşteptare.

§ 19. Schema morții și reproducerii. Mică formulă.

§ 20. Cele mai simple sisteme de asteptare si caracteristicile acestora.

§ 21. Probleme mai complicate în teoria cozilor.

Capitolul 7. Modelarea statistică a proceselor aleatoare (metoda Monte Carlo).

§ 22. Ideea, scopul și domeniul de aplicare al metodei.

§ 23. Lot unic și forme de organizare a acestuia.

§ 24. Determinarea caracteristicilor unui proces aleator staționar dintr-o implementare.

Capitolul 8

§ 25. Subiectul şi problemele teoriei jocurilor.

§ 26. Jocuri matrice antagoniste.

§ 27. Metode de rezolvare a jocurilor finite.

§ 28. Probleme ale teoriei soluţiilor statistice.

SUBIECTUL ŞI OBIECTIVELE CERCETĂRII OPERAŢIONALE

Concepte și principii de bază ale cercetării operaționale

În această secțiune, ne vom familiariza cu terminologia, conceptele de bază și principiile științei „cercetării operaționale”.

O operațiune este orice eveniment (un sistem de acțiuni) unit printr-o singură idee și care vizează atingerea unui scop (toate evenimentele discutate în paragrafele 1 - 8 din paragraful anterior sunt „operații”).

O operațiune este întotdeauna un eveniment controlat, adică depinde de noi cum să alegem unii dintre parametrii care îi caracterizează organizarea. „Organizare” aici este înțeleasă în sensul larg al cuvântului, inclusiv ansamblul mijloacelor tehnice utilizate în operațiune.

Orice alegere definită a parametrilor în funcție de noi se numește soluție. Deciziile pot fi de succes și nereușite, rezonabile și nerezonabile. Soluțiile sunt numite optime dacă sunt preferate altora dintr-un motiv sau altul. Scopul cercetării operaționale este o justificare cantitativă preliminară a soluțiilor optime.

Uneori (relativ rar) în urma studiului, este posibil să se indice o singură soluție strict optimă, mult mai des - să se identifice o zonă de soluții optime (rezonabile) practic echivalente în cadrul căreia se poate face alegerea finală.

Rețineți că însăși luarea deciziilor depășește sfera studiului operațiunii și intră în competența persoanei responsabile, de cele mai multe ori - un grup de persoane cărora li sa dat dreptul de a face alegerea finală și care sunt responsabile pentru această alegere. Atunci când fac o alegere, aceștia pot lua în considerare, alături de recomandările care decurg din calculul matematic, o serie de considerații (de natură cantitativă și calitativă) care nu au fost luate în considerare de acest calcul.

Prezența indispensabilă a unei persoane (ca autoritate finală de luare a deciziei) nu este anulată nici măcar în prezența unui sistem de control complet automatizat, care, se pare, ia o decizie fără participarea umană. Nu trebuie să uităm că însăși crearea unui algoritm de control, alegerea uneia dintre posibilele sale opțiuni, este, de asemenea, o decizie, și una foarte responsabilă. Odată cu dezvoltarea automatelor de control, funcțiile umane nu sunt anulate, ci pur și simplu mutate de la un nivel, elementar, la altul, superior. În plus, o serie de sisteme de control automatizate asigură intervenția umană activă în timpul procesului controlat.

Acei parametri, a căror totalitate formează o soluție, se numesc elemente ale soluției. Ca elemente ale soluției pot apărea diverse numere, vectori, funcții, semne fizice etc.. De exemplu, dacă se întocmește un plan pentru transportul mărfurilor omogene din punctele de plecare A 1, A 2, ..., A m spre destinații ÎN 1,В 2 , ..., В n , atunci elementele soluției vor fi numerele x ij , arătând câtă marfă va fi trimisă de la primul punct de plecare A i V j-a destinație În j . Set de numere X 11 , X 12, …, X 1 n , …, X m 1 , X m2, …, xmn formează o soluție.

În cele mai simple probleme de cercetare operațională, numărul elementelor de soluție poate fi relativ mic. Dar în majoritatea problemelor de importanță practică, numărul de elemente de soluție este foarte mare, pe care cititorul le poate verifica încercând să selecteze și să „numească după nume” elementele de soluție din exemplele 1 - 8 din paragraful anterior. Pentru simplitate, vom desemna întregul set de elemente ale soluției printr-o literă Xși spune „decizie X".

Pe lângă elementele de soluție de care, într-o oarecare măsură, le putem dispune, în orice sarcină de cercetare operațională sunt date și condiții „disciplinare” care sunt fixate de la bun început și nu pot fi încălcate (de exemplu, capacitatea de încărcare a mașinii; dimensiunea sarcinii planificate;

caracteristicile de greutate ale echipamentelor etc.). În special, astfel de condiții includ mijloacele (materiale, tehnice, umane) de care avem dreptul să dispunem și alte restricții impuse soluției. În totalitatea lor, ele formează așa-numitul „set de soluții posibile”.

Să notăm din nou acest set cu o literă X, ci faptul că soluţia X aparține acestui set, îl vom scrie sub formă de formulă: X X(a se citi: element X incluse in set X).

Este vorba de faptul că în multitudinea de soluții posibile X evidențiați soluțiile respective X(uneori - una, și mai des - o gamă întreagă de soluții), care dintr-un punct de vedere sau altul sunt mai eficiente (mai reușite, mai de preferat) decât altele. Pentru a compara diferite soluții în ceea ce privește eficiența, trebuie să aveți un fel de criteriu cantitativ, așa-numitul indicator de eficiență (este adesea numit „funcția obiectivă”). Acest indicator este ales astfel încât să reflecte orientarea țintă a operației. „Cea mai bună” soluție va fi considerată cea care contribuie la atingerea scopului în măsura maximă. Pentru a selecta măsura de performanță „spune după nume”. W,În primul rând, trebuie să te întrebi: ceea ce vrem La ce ne străduim prin efectuarea operațiunii? Atunci când alegem o soluție, vom prefera în mod firesc una care inversează indicatorul de eficiență W maxim (sau minim). De exemplu, aș dori să maximizez venitul dintr-o operațiune; dacă costurile sunt un indicator al eficienței, este de dorit să le minimizeze. Dacă este de dorit să maximizăm indicatorul de eficiență, îl vom scrie în formular W => max, iar dacă este minimizat - W => min.

Foarte des, operațiunea este însoțită de acțiunea unor factori aleatori („capricii” vremii, fluctuații ale cererii și ofertei, defecțiuni ale dispozitivelor tehnice etc.). În astfel de cazuri, de obicei, nu valoarea în sine, pe care am dori să o maximizăm (minimizam), ci valoarea sa medie (așteptările matematice) este luată ca indicator al eficienței.

În unele cazuri, se întâmplă ca operația, însoțită de factori aleatori, să urmărească un scop foarte specific. A, care poate fi realizat doar complet sau deloc atins (schema „da-nu”) și nu ne interesează niciun rezultat intermediar. Apoi, ca indicator al eficienței, se alege probabilitatea atingerii acestui scop. R(A). De exemplu, dacă un obiect este tras cu o condiție indispensabilă pentru a-l distruge, atunci indicatorul de eficiență va fi probabilitatea de a distruge obiectul.

Alegerea greșită a indicatorului de performanță este foarte periculoasă. Operațiunile organizate din punctul de vedere al unui criteriu ales fără succes pot duce la costuri și pierderi nejustificate (amintim, de exemplu, notoriul „val” ca principal criteriu de evaluare a activității economice a întreprinderilor).

Pentru a ilustra principiile alegerii unui indicator de eficiență, să revenim din nou la exemplele 1 - 8 din § 1, alegem pentru fiecare dintre ele un indicator natural de eficiență și indicăm dacă este necesar să îl maximizăm sau să îl minimizăm. Atunci când examinăm exemplele, trebuie să rețineți că nu toate au posibilitatea de a alege un indicator de eficiență dictat fără ambiguitate de descrierea verbală a sarcinii, astfel încât să existe diferențe între cititor și autor pe această problemă.

1. Plan de aprovizionare a întreprinderilor. Sarcina operațiunii este de a asigura aprovizionarea cu materii prime cu costuri minime de transport. Indicator de performanta R- costul total al transportului materiilor prime pe unitatea de timp, de exemplu, o lună ( R => min).

2. Construirea unui tronson de autostrada. Este necesară planificarea construcției în așa fel încât să fie finalizată cât mai curând posibil. Un indicator natural al eficienței ar fi timpul de finalizare a construcției, dacă nu ar fi asociat cu factori aleatori (defecțiuni ale echipamentelor, întârzieri în efectuarea lucrărilor individuale). Prin urmare, ca indicator al eficienței, puteți alege timpul mediu așteptat T finalizarea constructiei (T => min).

3. Vânzarea mărfurilor de sezon. Ca indicator al eficienței, putem lua profitul mediu așteptat P din vânzarea mărfurilor pentru sezon (P => max).

4. Protecția drumurilor împotriva zăpezii. Acesta este cel mai avantajos plan de protecție împotriva zăpezii din punct de vedere economic, prin urmare, ca indicator al eficienței, puteți alege costurile medii pe unitatea de timp (de exemplu, pe an) R pentru întreținerea și exploatarea drumurilor, inclusiv costurile asociate atât cu construcția de dispozitive de protecție, cât și cu eliberarea drumului și întârzierile în trafic (R => min).

5. Raid antisubmarin. Din moment ce raidul are un scop foarte specific A - distrugerea bărcii, apoi ca indicator al eficienței, ar trebui să alegeți probabilitatea R(A) că barca va fi distrusă.

6. Controlul selectiv al produselor. Măsura naturală a performanței sugerată de enunțul problemei este costul mediu așteptat. R pentru control pe unitatea de timp, cu condiția ca sistemul de control să ofere un anumit nivel de calitate, de exemplu, procentul mediu de refuzuri nu este mai mare decât cel specificat ( R=> min).

7. Examen medical. Ca indicator al eficienței, puteți alege procentul mediu (cota) Q pacienţii şi purtătorii infecţiei care au fost identificaţi (Q=> Verifica).

8. Serviciul bibliotecă. O oarecare vagitate a fost admisă în mod deliberat în formularea problemei:

nu este clar ce se înțelege prin „cel mai bun serviciu pentru clienți” sau „întâmpinarea nevoilor acestora în cea mai mare măsură posibilă”. Dacă calitatea serviciului este judecată după timpul în care abonatul care a solicitat cartea așteaptă să fie primită, atunci timpul mediu poate fi luat ca indicator al eficienței. T așteptările cititorului care a solicitat cărții la carte ( T=> min). Puteți aborda problema dintr-o perspectivă ușor diferită, alegând numărul mediu ca indicator al eficienței. M cărți emise pe unitatea de timp (M => max).

Exemplele luate în considerare sunt special alese pentru a fi atât de simple încât alegerea unui indicator de eficiență este relativ ușoară și este direct dictată de formularea verbală a sarcinii, orientarea (aproape întotdeauna) fără ambiguitate a țintei. Cu toate acestea, în practică, acest lucru nu este întotdeauna cazul. Cititorul se poate convinge de acest lucru încercând, de exemplu, să aleagă un indicator al eficienței transportului urban. Ce ar trebui luat ca un astfel de indicator? Viteza medie de circulație a pasagerilor în oraș? Sau numărul mediu de pasageri transportați? Sau numărul mediu de kilometri pe care va trebui să-i parcurgă o persoană, pe care transportul nu-i poate livra la locul potrivit? Este ceva de gândit aici!

Din păcate, în majoritatea problemelor de importanță practică, alegerea unui indicator de eficiență nu este simplă și se rezolvă ambiguu. Pentru orice sarcină complexă, o situație este tipică când eficacitatea unei operațiuni nu poate fi caracterizată în mod exhaustiv printr-un singur număr - trebuie să implice pe alții pentru a o ajuta. Ne vom familiariza cu astfel de probleme „multicriteriale” în § 6.

Exemple de rezolvare a problemelor de programare dinamică

În această secțiune, vom lua în considerare (și chiar vom rezolva până la sfârșit) câteva exemple simple (extrem de simplificate) de probleme de programare dinamică

1. Aşezarea celui mai avantajos traseu între două puncte. Să ne amintim problema 4 din paragraful precedent și să o rezolvăm până la capăt în condiții extrem de (și intenționat) simplificate. Trebuie să construim o cale de legătură

două puncte AȘi ÎN, dintre care al doilea se află la nord-est de primul. Pentru simplitate, să spunem. că așezarea potecii constă dintr-o serie de trepte, iar la fiecare treaptă ne putem deplasa fie spre est, fie spre nord; orice cale de la A V ÎN este o linie întreruptă în trepte, ale cărei segmente sunt paralele cu una dintre axele de coordonate (Fig. 13.1). Costurile de construcție ale fiecăruia dintre aceste segmente sunt cunoscute. Este necesar să se tragă o astfel de cale de la A V ÎN, unde costul total este minim.

Cum să o facă? Puteți face una din două moduri: fie parcurgeți toate opțiunile de cale posibile și alegeți cea pe care costurile sunt minime (și cu un număr mare de segmente acest lucru este foarte, foarte dificil!); sau despărțiți procesul de tranziție din A V ÎNîn pași individuali (un pas - un segment) și optimizați controlul pe pași. Se pare că a doua metodă este incomparabil mai convenabilă! Aici, ca și în alte părți în cercetarea operațională, există avantaje căutării intenționate și organizate pentru o soluție față de enumerarea naivă „oarbă”.

Să demonstrăm cum se face acest lucru cu un exemplu specific. Împărțiți distanța de la A inainte de ÎNîn direcția est, să zicem, în 7 părți, iar în direcția nord - în 5 părți (în principiu, fragmentarea poate fi arbitrar mică). Apoi orice cale de la A V ÎN cuprinde T\u003d 7 + 5 \u003d= 12 segmente îndreptate spre est sau nord (Fig. 13.2). Să punem pe fiecare dintre segmente un număr care exprimă (în unele unități arbitrare) costul trasării unei căi de-a lungul acestui segment. Este necesar să alegeți o astfel de cale din A V ÎN, pentru care suma numerelor de pe segmente este minimă.

Vom considera calea construită ca un sistem controlat S, deplasându-se sub influenţa controlului din starea iniţială A la finală ÎN. Starea acestui sistem înainte de începerea fiecărei etape va fi caracterizată de două coordonate: est (X) si nordica (y), ambele sunt întregi (0 X 5 7, 0 la 5). Pentru fiecare dintre stările sistemului (punctul nodal al grilei dreptunghiulare din Fig. 13.2), trebuie să găsim controlul optim condiționat: mergem din acest punct spre nord (controlul „c”) sau spre est (controlul „c”). c"). Acest control este ales astfel încât costul tuturor pașilor rămași (inclusiv acesta) să fie minim. Vom continua să numim acest cost „câștig optim condiționat” (deși în acest caz nu este un „câștig”, ci o „pierdere”) pentru o anumită stare a sistemului. Sînainte de a începe pasul următor.

Vom desfășura procedura de optimizare condiționată în direcția opusă - de la sfârșit până la început. În primul rând, efectuăm optimizarea condiționată a ultimului pas, al 12-lea. Luați în considerare separat colțul din dreapta sus al grilei noastre dreptunghiulare (Fig. 13.3). Unde putem fi după al 11-lea pas? Numai

unde într-un (ultim) pas poți ajunge ÎN, adică într-unul din puncte ÎN 1 sau LA 2 . Dacă suntem la punct ÎN 1 , nu avem de ales (control forțat): trebuie să mergem spre est și ne va costa 10 unități. Să scriem acest număr 10 într-un cerc în apropierea punctului ÎN 1 , iar controlul optim va fi indicat printr-o săgeată scurtă care emană din ÎN 1şi îndreptată spre est. Pentru punct LA 2 controlul este de asemenea forțat (nord), debitul până la capăt este 14, îl vom scrie în cerc în punctul LA 2 . Astfel, se face optimizarea condiționată a ultimului pas și câștigul optim condiționat pentru fiecare dintre puncte B1, B2 găsit și înregistrat în cana corespunzătoare.

Acum să optimizăm penultimul (al 11-lea) pas. După penultima (al 10-lea) pas, am putea ajunge la unul dintre puncte C1, C2, C3(Fig. 13.4). Să găsim pentru fiecare dintre ele un control optim condiționat și un profit optim condiționat. Pentru punct De la 1 management forțat: mergi spre est;

ne va costa 21 de unități până la final (11 la acest pas, plus 10, scrise în cerc la ÎN 1). Numărul 21 este scris într-un cerc la un punct De la 1 . Pentru punct De la 2 managementul nu mai este forțat: putem merge și spre est și spre nord. În primul caz, vom cheltui 14 unități la acest pas și din LA 2 până la sfârșit - încă 14, doar 28 de unități. Dacă mergem spre nord, vom cheltui 13 + 10, pentru un total de 23 de unități. Prin urmare, controlul optim condiționat la punct De la 2 - mergeți spre nord (marcați acest lucru cu o săgeată și scrieți numărul 23 într-un cerc lângă C 2), Pentru punct De la 3 controlul este din nou forțat (“c”), va costa 22 de unități până la sfârșit (puneți săgeata spre nord, scrieți numărul 22 într-un cerc când De la 3).

În mod similar, „în retragere” de la penultimul pas înapoi, găsim pentru fiecare punct cu coordonate întregi controlul optim condiționat („c” sau „b”), pe care îl notăm cu o săgeată, și câștigul optim condiționat (cheltuieli pentru capătul drumului), pe care îl scriem în cerc. Se calculează astfel: debitul la un pas dat se adaugă debitului deja optimizat, scris în cercul unde duce săgeata. Astfel, la fiecare pas, optimizăm doar acest pas, iar cei care îl urmează sunt deja optimizați. Rezultatul final al procedurii de optimizare este prezentat în Fig. 13.5.

Astfel, optimizarea condiționată a fost deja realizată: indiferent unde ne aflăm, știm deja unde să mergem (săgeată) și cât ne va costa să ajungem la final (număr în cerc). Într-un cerc la un punct A rambursarea optimă pentru întreaga construcție a căii de la A V ÎN:

W* = 118.

Acum rămâne să construim un control optim necondiționat - o traiectorie care duce de la AȘi ÎNîn cel mai ieftin mod. Pentru a face acest lucru, trebuie doar să „ascultați de trăgători”, adică să citiți ce prescriu aceștia să facă la fiecare pas. O astfel de traiectorie optimă este marcată în Fig. 13,5 s-au încercuit de două ori. Controlul optim necondiționat corespunzător va fi:

x* =(s, s, s, s, în, în, s, în, în, în, în, în),

adică trebuie să facem primii patru pași spre nord, următorii doi către est, apoi din nou unul spre nord și restul cinci către est. Problema rezolvata.

Rețineți că în cursul optimizării condiționate, putem întâlni cazul în care ambele controale pentru un anumit punct al planului sunt optime, adică duc la același cost al fondurilor din acest punct până la sfârșit. De exemplu, în punctul cu coordonatele (5; 1) ambele controale „c” și „b” sunt optime și dau fluxul până la capăt egal cu 62. Alegem în mod arbitrar oricare dintre ele (în cazul nostru, am ales „c”; am putea la fel de bine să alegem „c”). Astfel de cazuri de alegere ambiguă a controlului optim sunt întâlnite constant în programarea dinamică; în viitor, nu le vom marca în mod special, ci pur și simplu alegem arbitrar oricare dintre opțiunile echivalente. Desigur, controlul optim al întregului proces poate depinde de acest arbitrar, dar nu și de câștigul optim. În general, în problemele de programare dinamică (precum și în problemele de programare liniară), soluția este departe de a fi întotdeauna unică.

Și acum să revenim la început și să încercăm să rezolvăm problema într-un mod „naiv”, alegând la fiecare pas, începând de la primul, direcția cea mai profitabilă (pentru acest pas) (dacă sunt două, alegem orice). În acest fel obținem controlul

x = (s, s, în, în, în, în, s, în, în, în, s, s).

Să calculăm costurile pentru această traiectorie. Vor fi egali W=10 +12 +8+10 +11 +13 +15+8 + +10+9+8+14=128, ceea ce este cu siguranță mai mult decât W* = 118. În acest caz diferența nu este foarte mare, dar în altele poate fi semnificativă.

În problema rezolvată mai sus, condițiile au fost simplificate în mod deliberat până la extrem. Desigur, nimeni nu va conduce calea ferată „pe trepte”, deplasându-se doar spre nord sau spre est. Am făcut o astfel de simplificare pentru a alege doar dintre două controale în fiecare punct: „de la” sau „la”. În loc de două direcții posibile, ar fi posibil să se introducă mai multe dintre ele și, în plus, să se facă pași mai mici; acest lucru nu are o importanță fundamentală, dar, desigur, complică și prelungește calculele.

Rețineți că sarcini similare celor considerate mai sus sunt întâlnite foarte des în practică: de exemplu, atunci când alegeți calea cea mai rapidă între două puncte sau cel mai economic (din punct de vedere al consumului de combustibil) câștigul de viteză și altitudine de către o aeronavă.

Să facem o remarcă trecătoare. Cititorul atent a observat probabil că în problema noastră punctele AȘi ÎN(începutul și sfârșitul) nu sunt în principiu diferite unul de celălalt: ar fi posibil să se construiască controale optime condiționate nu de la sfârșit la început, ci de la început până la sfârșit și necondiționat - în direcția opusă. Într-adevăr, așa este: în orice problemă de programare dinamică, „începutul” și „sfârșitul” pot fi schimbate. Aceasta este complet echivalentă cu metoda descrisă anterior în ceea ce privește calculul, dar este oarecum mai puțin convenabil când se explică verbal ideea metodei: este mai ușor de argumentat, referindu-se la condițiile „deja stabilite” de la începutul acestei pas decât celor care încă „vin” după acest pas. În esență, ambele abordări sunt complet echivalente.

2. Problema alocării resurselor. Metoda de programare dinamică face posibilă rezolvarea cu succes a multor probleme economice (vezi, de exemplu, ). Luați în considerare una dintre cele mai simple astfel de probleme. Avem ceva stoc de fonduri (resurse) la dispoziție LA, care ar trebui distribuite între Tîntreprinderile P 1 , P 2 , ..., P m . Fiecare dintre întreprinderi i atunci când investesc în el X generează venituri pe baza X, adică reprezentând o anumită funcție ( X). Toate funcțiile ( X) (i = 1, 2, ..., T) sunt date (desigur, aceste funcții sunt nedescrescătoare). Întrebarea este cum să alocați fondurile LA. intre intreprinderi, astfel incat in total sa dea venitul maxim?

Această problemă se rezolvă cu ușurință prin metoda programării dinamice.Deși în formularea ei nu conține o mențiune a timpului, totuși se poate desfășura mental operația de distribuire a fondurilor într-o anumită secvență, considerând investiția fondurilor în întreprinderea P 1 ca fiind primul pas, iar în P 2 etc.

Sistem gestionat Sîn acest caz, fondurile sau resursele care sunt distribuite. Starea sistemului Sînainte ca fiecare pas să fie caracterizat de un număr S- rezerva de numerar neinvestită încă. În această problemă, „controalele pasului” sunt mijloacele x 1, x 2, ..., x 3, alocate afacerilor. Este necesar să găsiți controlul optim, adică un astfel de set de numere x 1, x 2, ..., xm, la care venitul total este maxim:

(13.1)

Vom rezolva această problemă mai întâi într-o formă generală, formulă și apoi - pentru date numerice specifice. Găsiți pentru toată lumea i- pasul este recompensa optimă condiționată (de la acest pas până la sfârșit), dacă am abordat acest pas cu o marjă de fonduri S. Indicați recompensa optimă condiționată W i (S), iar controlul optim condiționat corespunzător este fondurile în care sunt investite i afacere, - x i (S).

Să începem optimizarea de la ultima, T - Etapa. Să ajungem la acest pas cu restul fondurilor S. Ce ar trebui sa facem? Evident, investește toată suma Sîn întregime întreprinderii P m. Prin urmare, controlul optim condiționat pe m-al-lea pas: acordați ultimei întreprinderi toate fondurile disponibile S, adică

și recompensa optimă condiționată

Wm (S)= (S).

Având în vedere o întreagă gamă de valori S(plasându-le suficient de aproape), noi pentru fiecare valoare S noi vom sti x m (S)Și Wm (S). Ultimul pas este optimizat.

Să trecem la penultimul (T- 1) pasul. Să ne apropiem de el cu o rezervă de fonduri S. Denota L m -1 (S) recompensa optimă condiționată în ultimii doi pași: ( m- 1)-m și m-m (care este deja optimizat). Dacă alocam la ( m- 1) pasul ( m- 1)a-a întreprindere înseamnă X, atunci ultimul pas va fi S x. Recompensa noastră pentru ultimii doi pași va fi egală cu

,

și trebuie să-l găsești X, la care acest câștig este maxim:

Semnul înseamnă că valoarea maximă este preluată de toate X, ceea ce este posibil (a investi mai mult decât S, nu putem) din expresia în acolade. Acest maxim este recompensa optimă condiționată pentru ultimii doi pași și apoi valoarea X, la care se atinge acest maxim este controlul optim conditionat pe (T- 1) pasul.

şi controlul optim condiţional corespunzător x i (S) - acea valoare X, la care se atinge acest maxim.

Continuând în acest fel, ajungem în sfârșit la prima întreprindere P 1 . Aici nu trebuie să schimbăm valorile S; stim sigur ca stocul inainte de primul pas este egal cu LA:

Deci, se găsește câștigul (venitul) maxim din toate întreprinderile. Acum rămâne doar „să citești recomandările”. Acest sens X, la care se atinge maximul (13.4), iar la prima treaptă există un control optim. După ce investim aceste fonduri în prima întreprindere, vom avea LA- .„Citind” recomandarea pentru această valoare S, alocam suma optima de fonduri celei de-a doua intreprinderi:

,

si tot asa pana la final.

Acum să rezolvăm un exemplu numeric. Stocul inițial de fonduri K = 10 (unități convenționale) și este necesar să-l distribuie optim între cinci întreprinderi (t = 5). Pentru simplitate, vom presupune că sunt investite doar sume întregi de fonduri. funcții de venit ( X) sunt date în Tabelul 13.1.

Tabelul 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

În fiecare coloană, pornind de la o anumită cantitate de investiții, veniturile încetează să crească (în realitate, aceasta corespunde faptului că fiecare întreprindere este capabilă să „stăpânească” doar o sumă limitată de fonduri).

Să efectuăm optimizarea condiționată așa cum este descris mai sus, începând de la ultimul pas. De fiecare dată când ajungem la pasul următor, având o rezervă de fonduri S,încercăm să alocăm una sau alta sumă de fonduri pentru acest pas, luăm câștigul la acest pas conform tabelului 13.1, îl adăugăm la câștigul deja optimizat la toți pașii următori până la final (având în vedere că avem deja mai puține fonduri, doar printr-o asemenea sumă de fonduri, pe care le-am alocat) și găsim investiția la care această sumă atinge maximul. Această investiție este controlul optim condiționat la acest pas, iar maximul în sine este câștigul optim condiționat.

Tabelul 13.2 prezintă rezultatele optimizării condiționate pentru toți pașii. Tabelul este structurat astfel: prima coloană prezintă valorile stocului de fonduri S, cu cu care abordam acest pas. În plus, tabelul este împărțit în cinci perechi de coloane, corespunzătoare numărului pasului. Prima coloană a fiecărei perechi conține valoarea

Tabelul 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

control optim condiționat, în al doilea - profit optim condiționat. Tabelul este umplut de la stânga la dreapta, de sus în jos. Decizia la al cincilea - ultimul - pas este forțată: toate fondurile sunt alocate;

La toți ceilalți pași, soluția trebuie optimizată. Ca urmare a optimizării secvențiale a pasilor 5, 4, 3, 2 și 1, vom obține o listă completă a tuturor recomandărilor pentru un control optim și un câștig optim necondiționat W* pentru întreaga operațiune - în acest caz, este egal cu 5,6. În ultimele două coloane din Tabelul 13.2, este completată doar o singură linie, deoarece știm exact starea sistemului înainte de începerea primului pas:

S0 = K = 10. Controalele optime la toate etapele sunt încadrate. Astfel, am ajuns la concluzia finală: trebuie să alocăm două unități din zece primei întreprinderi, cinci unități celei de-a doua, două celei de-a treia, niciuna celei de-a patra, o unitate celei de-a cincea. Cu această distribuție, venitul va fi maxim și egal cu 5,6.

Pentru a clarifica cititorului cum este completat tabelul 13.2, vom demonstra acest lucru pe un eșantion de calcul. De exemplu, trebuie să optimizăm soluția x 3(7)- ce să facem în a treia etapă, dacă am abordat-o cu o rezervă de fonduri S= 7, și care este maximul pe care îl putem câștiga cu toate cele rămase

Tabelul 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

pași, inclusiv al treilea? Să presupunem că toți pașii de după al treilea (al 4-lea și al 5-lea) au fost deja optimizați, adică primele două perechi de coloane din Tabelul 13.2 au fost completate. Sa gasim X 3 (7) și W 3(7). Pentru a face acest lucru, vom compila o placă auxiliară (vezi tabelul 13.3). Prima coloană listează toate atașamentele posibile. X pe treapta a treia, nedepasind S = 7.În a doua coloană - ce va rămâne după o astfel de investiție din stocul de fonduri S = 7.În a treia coloană - câștigul din a treia etapă din investiție Xîn a treia întreprindere se completează după coloană (tabelul 13.1). În a patra coloană - plata optimă pentru toți pașii rămași (al patrulea și al cincilea), cu condiția să ne apropiem de al patrulea pas cu fondurile rămase (completate în coloana i = 4 tabele 13.2). În a cincea coloană - suma a două plăți: pas și optimizat în continuare pentru o anumită investiție Xîn a treia etapă.

Dintre toate plățile din ultima coloană, este selectată cea maximă (în tabelul 13.3 este egal cu W 3(7) = 3,6 și controlul corespunzător X(7) = 2).

Se pune întrebarea: ce se întâmplă dacă în tabelul auxiliar de tip 13.3 maximul este atins pentru mai mult de un X, și la două sau mai multe? Răspundem: nu contează pe care să o alegem; castigul nu depinde de el. În general, în problemele de programare dinamică, soluția nu ar trebui să fie deloc unică (am menționat deja acest lucru).

3. Problema încărcării mașinii. Folosind metoda de programare dinamică, puteți rezolva cu succes o serie de probleme de optimizare descrise în Capitolul 3, în special unele probleme de programare cu numere întregi. Rețineți că integralitatea soluțiilor, care face problemele de programare liniară atât de dificilă, în acest caz nu complică, ci, dimpotrivă, simplifică procedura (cum a fost simplificată pentru noi prin integralitatea înglobărilor în problema anterioară).

Ca exemplu, luați în considerare problema încărcării unei mașini (am menționat-o deja în capitolul anterior): există un anumit set de obiecte P 1 , P 2 ,..., P n (fiecare într-o singură copie); greutățile lor sunt cunoscute q 1 , q 2 , ..., q n si cost de la 1, cu 2 , ..., cu n . Capacitatea de încărcare a mașinii este Q.Întrebarea este care dintre articole ar trebui să fie luate în mașină, astfel încât costul lor total (cu greutatea totală Q) a fost maximul?