Optimizare combinatorială

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.