Optimizare combinatorială

Proiect
8/10 (1 vot)
Conține 1 fișier: doc
Pagini : 23 în total
Cuvinte : 7318
Mărime: 360.11KB (arhivat)
Publicat de: Crin Balint
Cost: 10 puncte
Profesor îndrumător / Prezentat Profesorului: Daniele Zaharie
UNIVERSITATEA DE VEST DIN TIMISOARA FACULTATEA DE MATEMATICA SI INFORMATICA

Extras din proiect

O problema de optimizare (adica o functie de mai multe variabile care trebuie maximizata sau minimizata cu satisfacerea unui set finit de restrictii) are caracter combinatorial daca fiecare variabila poate lua independent un numar de valori numerice apriori cunoscute de exemplu: valori întregi, nenegative inferioare unui prag dat sau numai valori 0 sau 1.

Analiza noastra se va restrânge la acele probleme cuantificabile matematic prin datele amintite: functia obiectiv, variabilele, restrictiile, valori permise variabilelor, deoarece clasa de probleme combinatoriale este cu mult mai larga.

Caracteristica unei probleme combinatoriale este ca numarul combinatiilor posibile de valori este finit. Aceste combinatii se numesc Solutii ale problemei si multimea lor se va nota cu ©. Combinatiile care, în plus, satisfac restrictiile problemei, si ele în numar finit, se vor numi Solutii Admisibile si multimea lor se va nota cu A. Cu aceste notatii, o problema combinatoriala se formalizeaza astfel:

Data fiind o functie definita în toate elementele din © sa se determine x*A cu proprietatea:

f(x*) = max f(x)

La prima vedere o problema de programare liniara este o problema combinatoriala deoarece solutia sa optima se poate gasi inspectând doar multimea A SAB care este finita. Exista totusi o mare deosebire: o solutie bazica nu poate fi construita prin acordarea de valori variabilelor întrucât din start plaja de valori admisibile este infinita. În notatiile de mai sus, A poate fi socotita finita, însa multimea © a combinatiilor posibile de valori date variabilelor este R+n care este infinit. Sansa de a da peste un element din A considerând o combinatie de valori sau alta este practic nula.

Exemplul tipic de problema combinatoriala pe care îl avem în vedere , este Problema de Optimizare cu Variabile Bivalente (vezi problema de afectare, problema alegerii proiectelor de investitii). Aici numarul total de combinatii posibile, respectiv numarul de elemente din © este 2n unde n este numarul variabilelor.

În general o problema combinatoriala se rezolva prin Enumerarea Totala sau Partiala a multimii © a solutiilor sale. Vorbim de enumerare totala daca determinarea elementului optimal x*A necesita generarea tuturor combinatiilor posibile de valori date variabilelor deci a tuturor elementelor din ©. Enumerarea partiala reprezinta determinarea lui x* prin generarea efectiva a unei parti din © partea negenerata fiind recunoscuta ca necontinând elemente optimale. Indiferent de schema de enumerare, o data generat un element x© se efectueaza urmatoarele operatii:

1. Se cerceteaza daca xA; daca NU se trece la generarea altui element din ©. Daca DA:

2. Se compara f(x) cu valoarea obiectivului f în cel mai bun element din A gasit anterior; daca se îmbunatateste valoarea obiectivului (în sensul optimului), x se retine ca cel mai bun element din A, gasit. În caz contrar x se abandoneaza si se trece la generarea unui nou element din ©.

Este important de retinut faptul ca generarea multimii © sau chiar a unei parti nu înseamna în nici un caz memorarea elementelor generate si aceasta pentru doua motive: sunt foarte multe si apoi nu sunt necesare (exceptând cel mai bun element din A gasit la un stadiu sau altul al enumerarii).

Schema logica din figura 1 formalizeaza rezolvarea problemelor de optimizare combinatoriala (P). Ea foloseste o “locatie” xCMB realizata de obicei sub forma unui vector în care se depoziteza ”cel mai bun” element din A gasit pâna la un anumit moment si o variabila zCMB care retine valoarea obtinuta în xCMB. În cazul unui obiectiv de maxim, initial zCMB = - , xCMB = 0. În cuprinsul schemei, punctul delicat îl constituie modul de generare efectiva a elementului din ©, mod care va fi discutat ulterior.

Neajunsul evident al enumerarii explicite a tuturor solutiilor problemei (P) rezida în numarul mare al acestora. Generarea unei solutii prin atribuire de valori variabilelor este o operatie practic instantanee pe un calculator (sunt necesare anumite precautii pentru evitarea generarii unei solutii de mai multe ori); chiar si verificarea restrictiilor de catre o combinatie generala nu dureaza prea mult si totusi, verificarea atâtor solutii face ca timpul total sa depaseasca lesne limita rezonabilului.

Alte trei clase de probleme formalizabile matematic pentru care numarul de solutii admisibile este foarte mare sunt urmatoarele:

a) Problema ordonantarii prelucrarii unor repere pe mai multe utilaje. Se cunosc timpii de prelucrare ai reperelor pe fiecare utilaj în parte, precum si ordinea în care utilajele trebuie parcurse. Problema consta în stabilirea ordinii de lansare în fabricatie a reperelor astfel încât timpul total de asteptare al utilajului sa fie minim. Este clar ca numarul total de solutii este n!, unde n = numarul de repere ce trebuie prelucrate. Ori pentru n = 20 avem: 20!=243.290.200.816.664.000 numar usor de scris dar greu de imaginat ca marime.

b) Problema comis voiajorului. Un comis voiajor trebuie sa viziteze n orase c1,…,cn. Se cunoaste matricea timpilor de deplasare de la un oras la altul, bineînteles acolo unde exista legaturi directe. Comis voiajorul pleaca dintr-un anumit oras, sa zicem c1, si trebuie sa treaca prin fiecare oras, o singura data, întorcându-se în final în orasul de plecare. Problema este ca din cele (n-1)! succesiuni posibile sa se aleaga acel drum caruia îi corespunde timpul total de deplasare minim.

c) Nu în ultimul rând în clasa problemelor de optimizare combinatoriala putem include si problemele de programare liniara în numere întregi (PLI). Într-adevar, pentru aceasta problema si în special pentru cele practice se pot sti de la bun început nivelele maxime admise pentru valorile întregi ce le pot lua variabilele si în consecinta numarul combinatiilor posibile de valori acordate acestora este finit.

Dupa cum am specificat deja, unul din punctele delicate ale oricarei scheme de enumerare îl constituie generarea combinatiilor de valori date variabilelor problemei. Acest proces trebuie sa satisfaca doua conditii:

1. nici o combinatie nu trebuie generata de mai multe ori;

2. nici o combinatie posibila nu trebuie omisa.

Preview document

Optimizare combinatorială - Pagina 1
Optimizare combinatorială - Pagina 2
Optimizare combinatorială - Pagina 3
Optimizare combinatorială - Pagina 4
Optimizare combinatorială - Pagina 5
Optimizare combinatorială - Pagina 6
Optimizare combinatorială - Pagina 7
Optimizare combinatorială - Pagina 8
Optimizare combinatorială - Pagina 9
Optimizare combinatorială - Pagina 10
Optimizare combinatorială - Pagina 11
Optimizare combinatorială - Pagina 12
Optimizare combinatorială - Pagina 13
Optimizare combinatorială - Pagina 14
Optimizare combinatorială - Pagina 15
Optimizare combinatorială - Pagina 16
Optimizare combinatorială - Pagina 17
Optimizare combinatorială - Pagina 18
Optimizare combinatorială - Pagina 19
Optimizare combinatorială - Pagina 20
Optimizare combinatorială - Pagina 21
Optimizare combinatorială - Pagina 22
Optimizare combinatorială - Pagina 23

Conținut arhivă zip

  • Optimizare Combinatoriala.doc

Alții au mai descărcat și

Probabilitatea de Lovire în Cazul unei Poziții Date a Traiectoriei Medii Fața de Tinta

1. CONSIDERATII GENERALE Succesul împotriva unui adversar este evident condiţionat de calitatea armamentului din dotarea unităţilor, subunitătilor...

Teoria Jocurilor

1. Introducere Teoria jocurilor, este o ramură a matematicii aplicate care abordează problema comportamentului optim în jocurile cu 2 sau mai...

Tehnici Evoluate de Conducere

Calcul evolutiv. Principiile calculului evolutiv Este inspirat de procesele de evolutie din natura bazate pe principiile ereditatii si a...

Metode Tradiționale de Reprezentare a Cunoașterii

1. Problematica reprezentarii simbolice Înainte de a studia aceasta tema, trebuie sa ne putem pune totusi întrebarea: este posibila reprezentarea...

Evenimente Naturale care se Autoconsolideaza prin Circuite de Feedback

“Feedback-ul este ceea ce lipsea din stiinta, in afara lui Newton”, spunea omul de stiinta britanic Steve Grand. “Noi credeam ca este un fenomen...

Sisteme bazate pe cunoștințe în conducerea proceselor

Programul realizeaza determinarea procesului de incalzire ,respectiv racire intr-o camera si a timpului (maxim respectiv minim) in functie de trei...

Sisteme Informatice de Asistare a Deciziilor

1. INTRODUCERE ÎN BAZELE INTELIGENłEI ARTIFICIALE 1.1.Definirea domeniului inteligentei artificiale. În general notiunea de inteligentă este...

Problema naufragiului

#include <stdio.h> #include <conio.h> #include <values.h> int gr[20],a,b,v,Frontiera[20],Teritoriu[20],n,m,f[20],nod,aux; void elimina(int nod)...

Te-ar putea interesa și

Rețele Neuronale

Procese de învatare in sisteme cu inteligenta artificiala Inteligenta artificiala, ca si in cazul inteligentei biologice se dobândeste printr-un...

Proiectarea și Optimizarea Problemelor de Programare Semidefinită

Acest proiect de diplomă a fost implementat pentru proiectarea şi optimizarea problemelor de programare semidefinită, care mai apoi poate fi...

Implementarea algoritmilor evolutivi

Conceptul de evoluţie a fost propus de savantul englez Charles Darwin în 1859 în celebra sa carte “Originea speciilor prin selecţie naturală”....

Componente Software pentru Managementul Portofoliilor de Acțiuni

Abstract 4 Introducere 5 Algoritmi genetici 6 Introducere 6 Structura generala a unui algoritm genetic 8 Structuri de date 10 Construirea...

Rezolvarea problemei rucsacului folosind tehnici de metauristici

Rezumare In aceasta lucrare mi-am propus o metodologie hibrida pentru rezolvarea unei problem de optimizare, mai exact problema rucsacului....

Tehnici Evoluate de Conducere

Calcul evolutiv. Principiile calculului evolutiv Este inspirat de procesele de evolutie din natura bazate pe principiile ereditatii si a...

Categorii de sisteme inteligente

1. Introducere Tot mai larga circulaţie de care se bucură termenul de "inteligenţă artificială" este pe deplin justificată: devine din ce în ce în...

Sistem inteligent pentru dezvoltarea câmpurilor petroliere

Capitolul I: Proces economic. Tehnologii inteligente Domeniul inteligenţei artificiale, sau IA, îşi propune să inţeleagă entităţile inteligente....

Ai nevoie de altceva?