Comisia de atestare
Comisia de acreditare
Comisiile de experţi
Dispoziţii, instrucţiuni
Acte normative
Nomenclator
Instituţii
Consilii
Seminare
Teze
Conducători de doctorat
Deţinători de grad
Doctoranzi
Postdoctoranzi
CNAA logo

 română | русский | english

CNAA / Teze / 2007 / august /

Modele de control optimal discret şi soluţionarea jocurilor dinamice pe reţele


Autor: Anatoli Iusiumbeli
Gradul:doctor în ştiinţe fizico-matematice
Specialitatea: 01.01.09 - Cibernetică matematică şi cercetări operaţionale
Anul:2007
Conducător ştiinţific: Dmitrii Lozovanu
doctor habilitat, profesor universitar, Universitatea de Stat din Moldova
Instituţia: Universitatea de Stat din Moldova
CSS: DH 30-01.01.09
Universitatea de Stat din Moldova

Statut

Teza a fost susţinută pe 24 august 2007 în CSS
şi aprobată de CNAA pe 18 octombrie 2007

Autoreferat

Adobe PDF document0.44 Mb / în română

Cuvinte Cheie

problemă de control optimal, soluţie optimală în sensul Nash, condiţie de regularitate, c-jocuri, programare dinamică

Adnotare

În teză se cercetează problema de control optimal discret pe reţele dinamice. Metodele de bază pentru cercetarea şi soluţionarea unor astfel de probleme sunt bazate pe principiul programării dinamice. Este extinsă metoda programării dinamice pentru problema de control optimal în cazul când dinamica sistemului este descrisă cu ajutorul unui graf orientat de treceri, unde stările sistemului corespund vârfurilor grafului, iar arcele exprimă posibilitatea de trecere a sistemului dintr-o stare în alta în orice moment de timp. Sunt expuse unele rezultate ce argumentează algoritmii polinomiali elaboraţi pentru soluţionarea problemelor de control optimal pe reţele dinamice. Este generalizat algoritmul Dijkstra de determinare a drumurilor optimale, în cazul când reţeaua dinamică satisface condiţia de regularitate. Este elaborat algoritmul de soluţionare a problemei de control optimal pe reţele dinamice bazat pe metoda reţelei extinse.

Printre problemele cercetate, este expusă abordarea teoretică a variantei de joc pentru problema de control optimal discret cu criteriul integral de cost în timp, când stările iniţială şi cea finală ale sistemului sunt fixate. S-a arătat că cercetarea şi soluţionarea acestor probleme pot fi reduse la determinarea strategiilor optimale în aşa numitele c-jocuri. Din aceste considerente, în teză sunt argumentate metode şi algoritmi eficienţi pentru determinarea strategiilor optimale ale jucătorilor în c-jocuri. Sunt cercetate c-jocuri dinamice, care sunt strict legate de problema controlului optimal multicriterial în forma poziţională. S-a demonstrează că variantele de joc ale problemelor de control optimal cercetate pot fi reduse la o clasă specială a c-jocuri dinamice pe reţele.

În teză a fost formulată şi cercetată problema determinării echilibrului Nash pentru problema de control optimal multicriterial discret, ce reprezintă soluţia jocului noncooperatist dinamic. S-au formulat condiţiile suficiente de existenţă ale echilibrului Nash. În baza acestor rezultate s-au elaborat algoritmi polinomiali de determinare a strategiilor optimale ale jucătorilor pentru problema cercetată.

Se analizează separat problema în cazul când numărul de etape ale sistemului dinamic este fixat şi cazul fără restricţii asupra numărului de etape.

S-a efectuat testarea algoritmilor propuşi pe baza unor exemple concrete, precum şi elaborarea de programe în limbajul C++.

Cuprins


Capitolul I. Probleme de control optimal. Metode şi algoritmi
  • § 1.1 Probleme clasice de control optimal. Noţiuni preliminare
    • 1.1.1 Principiul maxim al lui Pontreaghin
  • § 1.2 Problema de control optimal discret
  • § 1.3 Metoda programării dinamice pentru problema controlului optimal discret
  • § 1.4 Problema de control optimal pe reţele şi algoritmi de soluţionare ai acesteia
    • 1.4.1 Enunţul problemei de control optimal pe reţea şi metoda programării dinamice
    • 1.4.2 Condiţia de regularitate
    • 1.4.3 Algoritmul de determinare a soluţiei optimale pe reţele pentru cazul static
    • 1.4.4 Algoritmul de determinare a soluţiei optimale bazat pe metoda reţelei extinse
    • 1.4.5 Un algoritm de soluţionare a problemei de control optimal în sistemul dinamic, când numărul de treceri al sistemului este fixat

Capitolul II. Jocuri dinamice. Problema de control optimal pe reţele dinamice cu p jucători
  • § 2.1 Enunţul problemei şi proprietăţile de bază
    • 2.1.1 Problema controlului optimal multicriterial pentru sisteme discrete cu un număr fixat de etape
    • 2.1.2 Problema controlului optimal multicriterial pentru cazul sistemelor discrete fără restricţii asupra numărului de etape
  • §2.2 Determinarea soluţiilor optime în cazul reţelei de joc cu p jucători.
    • 2.2.1 c-jocuri pe reţele dinamice
    • 2.2.2 Teorema de existenţă şi optimalitate
    • §2.3 Algoritmii de determinare a strategiilor optime în c-jocuri dinamice