Fluxuri optime în reţele dinamice şi algoritmi de aflare a lor
|
StatutTeza a fost susţinută pe 25 ianuarie 2008 în CSSşi aprobată de CNAA pe 28 februarie 2008 Autoreferat – 0.41 Mb / în românăTezaCZU 519.1
|
Cuvinte Cheie
fluxuri în reţele, reţele dinamice, flux de cost minim, flux maximal, fluxuri cu mai multe produse, metoda reţelei extinseAdnotare
Teza se referă la domeniul de cercetare a problemelor de optimizare legate de aflarea fluxurilor optime în reţele dinamice cu un singur produs şi cu mai multe produse. Această direcţie este o dezvoltare firească a teoriei fluxurilor statice şi are o aplicare largă la investigarea şi rezolvarea multor probleme practice.
În teză sunt cercetate două probleme de bază legate de aflarea fluxurilor optime în reţele dinamice: problema fluxului de cost minim şi problema fluxului maximal. În reţelele dinamice pentru problemele date fluxul parcurge arcele în timp şi costurile de trecere a fluxului prin arce sunt neliniare şi depind de timp şi de flux. Problemele considerate sunt cercetate pe reţelele dinamice când toţi parametrii reţelei depind de timp. Aceste probleme generalizează problemele clasice statice şi extind unele modele dinamice cunoscute de optimizare pe reţele. Se consideră că funcţia capacităţii arcelor reţelei şi funcţia cererii-ofertei nodurilor reţelei depind de timp, iar funcţia costului pe arcele reţelei depinde atât de timp cât şi de flux. În cazul general pentru reţelele cu mai multe produse se consideră că timpurile de tranzit pe arcele reţelei depind de tipul de produs ce intră în ele. Mai mult ca atât, este cercetat model dinamic când funcţiile timpurilor de tranzit pe arcele reţelei depind de valoarea fluxului şi de momentul intrării fluxului în arcul respectiv. Pentru rezolvarea problemelor considerate sunt elaboraţi şi teoretic argumentaţi algoritmi eficienţi bazaţi pe metoda programării dinamice şi metoda reţelei extinse. Sunt formulate şi cercetate variantele multicriteriale ale problemelor menţionate bazate pe concepţia teoriei jocurilor cooperatiste şi noncooperatiste. Sunt analizate unele abordări şi metode de aflare a soluţiilor optime în sensul Pareto şi Nash pentru probleme multicriteriale. Se arată legătura problemei de control optimal pe reţea cu problema de aflare a fluxului de cost minim pe reţeaua cu funcţii concave ale costului pe arce. În mediul de programare Visual Studio 2005 sunt elaborate programele de construire a reţelelor extinse şi reduse pentru reţelele dinamice cu un singur produs şi cu mai multe produse pentru problemele examinate.
Teza este scrisă în limba engleză.
Cuprins
- 1.1. Fluxuri statice: definiţii şi unele proprietăţi
- 1.1.1. Fluxul cu un singur produs
- 1.1.2. Fluxul cu mai multe produse
- 1.2. Problema fluxului maximal
- 1.3. Problema fluxului de cost minim
- 1.3.1. Cazul liniar
- 1.3.2. Cazul neliniar
- 1.4. Problema fluxului multi-produs de cost minim
- 1.4.1. Funcţia-scop continuu diferenţiabilă şi convexă
- 1.4.2. Funcţia-scop separabilă
CAPITOLUL 2. Problemele fluxului dinamic cu un singur produs şi metoda reţelei extinse pentru rezolvarea lor
- 2.1. Problema fluxului dinamic de cost minim
- 2.2. Metoda de rezolvare a problemei fluxului dinamic de cost minim
- 2.3. Modelul dinamic cu stocarea fluxului în noduri
- 2.4. Modelul dinamic cu stocarea fluxului în noduri şi funcţiile constante de cerere-ofertă
- 2.5. Algoritmul
- 2.6. Abordări pentru rezolvarea problemelor fluxului dinamic de cost minim cu diferite tipuri ale funcţiilor de cost şi unele generalizări
- 2.7. Determinarea fluxurilor de cost minim în reţele dinamice cu funcţiile de timp de tranzit ce depind de flux şi de timp
- 2.8. Algoritmul de rezolvare a problemei fluxului maximal pe reţeaua dinamică
CAPITOLUL 3. Problemele fluxului dinamic cu mai multe produse şi algoritmi de soluţionare a lor
- 3.1. Problema fluxului multi-produs de cost minim pe reţeaua dinamică
- 3.2. Metoda de rezolvare a problemei fluxului dinamic multi-produs de cost minim
- 3.2.1. Reţeaua dinamică cu diferite timpuri de tranzit pe un arc pentru diferite produse
- 3.2.2. Reţeaua dinamică cu funcţii separabile de cost şi fără restricţii asupra capacităţilor mutuale ale arcelor
- 3.2.3. Reţeaua dinamică cu comune timpuri de tranzit pe un arc pentru diferite produse
- 3.3. Algoritmul
- 3.4. Exemple
- 3.5. Unele generalizări
- 3.6. Construirea reţelei extinse în timp pentru grafuri aciclice
- 3.7. Problema fluxului dinamic multi-produs de cost minim cu funcţiile de timp de tranzit ce depind de flux şi de timp
- 3.8. Algoritmul de rezolvare a problemei fluxului dinamic multi-produs maximal
CAPITOLUL 4. Fluxurile dinamice optime în sistemele decizionale
- 4.1. Abordarea teoretică de joc pentru rezolvarea problemelor multicriteriale de flux multi-produs pe reţele
- 4.1.1. Echilibrul Pareto-Nash pentru jocuri multicriteriale
- 4.1.2. Modelele multicriteriale de flux multi-produs
- 4.1.3. Comentarii
- 4.2. Problemele fluxului dinamic de cost minim fără restricţii asupra capacităţilor arcelor
- 4.2.1. Problemele fluxului de cost minim cu funcţiile de cost ce nu depind de flux şi probleme de sinteză a reţelelor
- 4.2.2. Problemele fluxului de cost minim cu funcţiile concave de cost şi probleme de control optimal pe reţele
Referenţi Oficiali
- Dumitru Zambiţchi
doctor, conferenţiar universitar - Gheorghii Doneţ
doctor habilitat în ştiinţe fizico-matematice, profesor universitar, Institutul de Cibernetică V. M. Gluşkov, Academia Naţională de Ştiinţe a Ucrainei, Kiev, Ucraina
Teze
Acte Normative
