Programare în numere întregi

Programare in numere intregi

Este binecunoscut faptul ca modelarea prin programare liniara reprezinta un mijloc puternic si eficace pentru studiul proceselor economice in vederea imbunatatirii performantelor acestora.

O proprietate foarte importanta a variabilelor de decizie, dintr-un program liniar era aceea ca o data cu doua valori permise, puteau lua oricand orice alta valoare intermediara; aceasta proprietate „de a putea varia continuu” era esentiala in fundamentarea metodelor de determinare a solutiilor optime.

Nu putine sunt situatiile practice, modelate cu ajutorul programarii liniare in care unele variabile de decizie nu au sens economic decat daca au numai valori intregi.

De exemplu, daca outputul unei activitati este masurat in unitati indivizibile e clar ca valorile permise ale devariabilei care indica nivelul activitatii respcetive trebuie sa fie numere intregi. La fel, repartizarea personalului muncitor, al utilajelor sau al mijloacelor de transport pe diverse activitati trebuie exprimata tot prin cantitati intregi.

Sa luam drept exemplu un fermier ce are nevoie de 107 funti de ingrasamant. Acesta poate fi obtinut fie in saci de 35 funti la pretul de 14 u.m sacul,fie in saci de 24 funti a 12 u.m. fiecare. Obiectivul sau este de a cumpara cantitatea necesara de ingrasamant la cel mai mic cost.

Notam cu x1 si x2 numarul sacilor de 35, respectiv 24 funti cumparati de fermier. Asadar obtinem: [ min]f= 14x1+x2 ’ costul sacilor achizitionati

35x1+24x2 e107’ asigurarea achizitionarii cantitatii de ingrasamant dorite ;x1, x2e0, intregi

In modelul rezultat, conditia „x1, x2” intregi inseamna pur si simplu ca fermierul nu poate cumpara o jumatate sau o treime de sac; ori cumpara un sac intreg ori nu. Fara aceasta conditie avem de-a face cu o problema uzuala de programare liniara.

Poate mai importante sunt situatiile in care trebuie luate decizii de tip „Da sau NU” ca de exemplu:

- Se poate aproba realizarea unui anumit protocol de dezvoltare?

- Se poate initia o activitate implican un anumit cost fix de pregatire?

- Se poate amplasa o facilitate intr-un anumit loc?

Existand doar doua posibilitati, de a amplasa sau de a respinge, asemenea decizii pot fi reprezentate prin variabile cu numai doua valori permise, 0(decizie negativa) sau 1(decizie afirmativa)

Sa luam un nou exemplu economic pentru a evidentia cele spuse: In cadrul unui proiect de extindere si dezvoltare, conducerea unei firme studiaza oportunitatea construirii unei noi fabrici fie in orasul A, fie in orasul B, poate chiar in amandoua si a cel mult un depozit intr-unul din cele doua orase, alegerea amplasamentului fiind insa conditionata de construirea unei fabrici in localitatea respectiva. In tabelul urmator sunt indicate: valoarea prezenta neta a diferitelor alternative, capitalul necesar acestor investitii si capitalul disponibil pentru intregul proiect de dezvoltare:

Nr crit. Alternativa decizionala Variabila de decizie Valoare neta Capital necesar

1 Construirea unei fabrici in A X1 9mil 6mil

2 Construirea unei fabrici in B X2 5mil 3mil

3 Construirea unui depozit in A X3 6mil 5mil

4 Construirea unui depozit in B X4 4mil 2mil

Capital disponibil 10mil

Unde x1 =1 daca alternativa decizionala j se aproba (j=1, 2 ,3, 4) si x1 =0 daca alternativa decizionala se respinge.

Conditiile specificate in proiectul de dezvoltare se formalizeaza astfel:

- Cel mult un depozit poate fi construit: x3+x4 d1 ( deoarece x3, x4 nu pot lua decat valorile 0 sau 1, se elimina posibilitatea construirii a doua depozite in ambele orase deoarece x3=1, x4 =1 nu satisfac inegalitatea)

- Depozitul nu poate fi construit in lipsa unitatii productive:x3dx1 , x4dx2 ( este clar ca x1 =0 implica necesitatea x3 =0, etc.)

- Incadrarea in capitalul disponibil : 6x1 + 3x2 + 5x3 + 2x4 d x2

- Maximizarea valorii prezente nete totale a obiectivelor care se vor realiza:

Rezulta urmatorul model matematic:

[max] f= 9x1 + 5x2 + 6x3 + 4x4

: 6x1 + 3x2 + 5x3 + 2x4 d10

x3 + x4 d1

-x1 +x3 d0

-x2 +x4 d0

X1 d1, Xje0 intregi ” Xj {0,1} j=1, 2, 3, 4

Domenii de aplicare a programarii in numere intregi

1.Problema monezilor.

Cum poate fi platita o suma de bani astfel incat?

- Numarul tipurilor valorice de monezi utilizate la plata sa nu depaseasca o limita data;

- Numarul total al monezilor necesare platii sa fie minim.

Pentru formalizare avem nevoie de urmatoarele notatii:

S= suma este plata

n=numarul total al tipurilor valorice de monezi disponibile pentru plata

p= numarul maxim de tipuri valorice de monezi ce pot fi utilizate la plata sumei S;l

aj= valoarea monezii de tip j;

mj= numarul monezilor de tip j disponibile in casa.

Introducem variabilele: xj = numarul monezilor de tip j utilizate la plata sumei S;

Rezulta urmatorul program:

[min]f= ;