Programare intreaga si Programare intreaga mixta

Programare intreaga si Programare intreaga mixta
(Integer Programming, Mixed Integer Programming)

Exista situatii practice in care natura concreta a fenomenelor modelate impune cerinta ca variabilele supuse restrictiilor problemei sa nu poata lua valori decat numere intregi.

Modulele "Integer Programming" si "Mixed Integer Programming" permit rezolvarea problemelor in care :

a)     toate variabile sunt intregi;

b)     numai o parte din variabile sunt intregi ( problema mixta);

c)     variabilele sunt 0 -1 (variabile booleene).

Caracteristici

numarul de variabile [2 30]

numarul de restrictii [1 30];

Observatii:

in cazul variabilelor booleene trebuie impuse conditiile suplimentare x_i <1, i= 1,..n., unde "n" este numarul variabilelor. Evident, daca 0≤ x_i ≤1 si x_i este intreg, rezulta x_i =0 sau1.

Exemplu

O firma doreste sa investeasca suma de 2670 u.m. in domeniul imobiliar. Se pot achizitiona 3 tipuri de obiective; acestea necesita un timp diferit lunar pentru intretinere: beneficiul net anual obtinut din exploatare este diferit pentru fiecare obiectiv.

Pretul de cumparare (u.m.), beneficiul net anual (u.m.) si timpul lunar necesar (ore) sunt:

Firma nu poate aloca mai mult de 250 ore lunar pentru intretinere. Numarul maxim disponibil de obiective O1 este de 5 iar de obiective O3 este de 4.

Sa se determine solutia optima de achizitie care realizeaza beneficiul anual maxim.

Rezolvare:

Fie X1 = numarul de obiective O1 care vor fi cumparate;

X2 = numarul de obiective O2 care vor fi cumparate;

X3 = numarul de obiective O3 care vor fi cumparate.

Problema de programare discreta are toate variabilele numere intregi. Solutia obtinuta este prezentata in pagina 57.

Probleme propuse:

1. Introduceti si executati problema din exemplu. Reluati problema cu modulul Linear Programming si comparati solutiile.

2. Un transportator trebuie sa incarce marfuri de diferite sorturi in limita capacitatii de 70t. Cele 5 marfuri sunt caracterizate printr-o greutate si printr-o valoare specifica, date in continuare:

Transportul trebuie sa contina cel putin 2 unitati (containere) din M2 si cel mult 6 unitati din M1, 4 unitati din M3, 5 unitati din M4 si 8 unitati din M5.

Stabiliti solutia optima de alegere a incarcaturii, astfel ca valoarea totala a marfurilor transportate sa fie maxima.

3. Se considera ca un produs software este format din mai multe programe si fiecare program prin executie indeplineste o anumita functie, necesara utilizatorului.

Ipotezele modelului:

I1. Pentru fiecare program se cunoaste fiabilitatea si costul;

I2. Utilizatorul dispune de o suma limitata pentru achizitionarea produsului software;

I3. Utilizatorul cunoaste frecventa de utilizare a fiecarei functii din produsul software.

Sa se maximizaze fiabilitatea medie prin alegerea unei multimi optime de programe fara redundanta.

Datele problemei sunt:

bugetul disponibil = 12 u.m.

pentru functia 1 sunt disponibile 4 programe;

frecventa de utilizare = 0.75;

pentru functia 2 sunt disponibile 3 programe;

frecventa de utilizare = 0.25;

4. Rezolvati problema 3 in cazul in care frecventele de utilizare sunt: pentru functia 1 - 0.25, iar pentru functia 2 - 0.75.

5. O companie doreste sa investeasca; se propun 4 proiecte. Se cunosc:

Stabiliti decizia companiei.