Cercetări Operaționale

PROGRAMARE ÎN NUMERE ÎNTREGI

Capitolele 1 si 2 ale cursului de Cercetari Operationale din anul III au ca suport Notele de curs ale Domnului Profesor Vasile Nica si lucrarea “Capitole Speciale ale Cercetarilor Operationale” a aceluiasi autor, editata de Centrul de Învatamânt Economic Deschis la Distanta din Academia de Studii Economice Bucuresti.

1.1 Definirea unei probleme de programare liniara în numere întregi

Sa se determine x1, x2, …, xn care maximizeaza functia:

f = c1x1 + c2x2 + … + cnxn (1)

cu satisfacerea restrictiilor:

a restrictiilor de nenegativitate:

xj e 0 , oricare ar fi j = 1,…, n (3)

si a conditiilor de integritate:

xj , întregi j = 1, ..., n , (4)

În (1) si (2) coeficientii b1 ,…, bn si a11, a12, … , amn se vor presupune în mod constant întregi. Cerinta nu este deloc restrictiva pentru ca, în mod obisnuit, datele, oricare ar fi problema, sunt numere rationale.

Problemele (1)–(4) = (Integer Linear Programming) se prezinta în forma standard. Considerarea aproape în exclusivitate a acestei forme nu constituie o restrângere a generalitatii noastre pentru ca oricare ar fi inecuatia (cu coeficienti întregi!), ea poate fi transformata în egalitate prin introducerea unei variabile de abatere în maniera binecunoscuta din programarea liniara. Este evident ca si variabilele de abatere vor satisface restrictiile de nenegativitate.

Ignorând conditia de integritate, primele trei conditii formeaza o problema standard de programare liniara denumita în continuare (LP).

Pentru comoditatea scrierii adaptam notatiile matriciale uzuale:

(max)f = cÅx (max)f = cÅx

( ILP ) AÅx = b ( LP ) AÅx = b

x e 0 x e 0

x ÎNTREG

Sa punem în evidenta multimea de Solutii Admisibile ale celor doua probleme:

AILP = { x  R n ú AÅx = b , x e 0 , x întreg}

ALP = { x  R n ú AÅx = b , x e 0 } Ò A ILP ‚ ALP

De aici rezulta ca (LP) este o RELAXARE a lui (ILP).

Sa presupunem pentru moment ca ambele probleme au Solutii Optime finite. În mod constant vom nota cu x0 solutia optima a programului ILP (Solutie Optima Întreaga), în timp ce solutia optima a programului LP este x* (Solutie Optima Neîntreaga – Fractionara).

avem f ( x0 ) d f ( x*)

Este posibil ca x* sa aiba toate componentele întregi Ò x* = x0. Conditia de integritate (4) complica enorm rezolvarea programului (ILP). Vom sublinia acest lucru printr-o paralela între trasaturile cele mai importante ale Multimilor de Solutii Admisibile ale celor doua probleme: (LP) si (ILP).

Exemplu numeric:

(max) f = 3x1 – x2 (max) f = 3x1 – x2

3x1 – 2x2 d 3 3x1 – 2x2 d 3

5x1 + 4x2 e 10 5x1 + 4x2 e 10

(ILP) 2x1 + x2 d 5 (LP) 2x1 + x2 d 5

x1,2 e Ø relaxata x1,2 e Ø

x1,2  Z

Figura 1 pune în evidenta multimea solutiilor admisibile ALP ca fiind poligonul convex ABCD. Solutia optima x* se afla într-un punct extrem al acestui poligon. Reprezentând grafic curbele de nivel ale functiei obiectiv se deduce ca: x* a A adica , f (x*) = 30 / 7.