Problema croirii
Un numar de repere uni sau bidimensionale trebuie executate în cantitati date. Aceste repere se obtin prin decupare din niste suporti (bare sau foi). Acoperirea unui suport cu diferite repere se poate face în mai multe moduri (bineînteles ca este exclusa orice suprapunere totala sau partiala a reperelor).
O modalitate de acoperire a unui suport poarta numele de RETETA DE CROIRE. Dupa decuparea reperului din suport conform unei retete ramâne un REST ce nu mai poate fi utilizat. Problema consta în a alege acele retete de croire prin care sa se obtina reperele în cantitatile dorite cu MINIMUL POSIBIL de rest.
FORMALIZAREA MATEMATICA
Sa începem prin a descrie modelul UNIDIMENSIONAL de croire. Reperele vor fi identificate prin niste numere întregi reprezentând lungimea lor într-o unitate de masura adecvata.
Fie m = numarul de repere distincte care trebuie taiate si
• l1, l2,…, lm = lungimile lor;
• L = lungimea suportului din care se taie reperele.
O reteta de croire se identifica printr-un vector m dimensional cu componente întregi (a1, a2, …, am), unde ai = numarul de repere i (deci cu lungimea li) ce rezulta prin taierea conform retetei.
Evident: a1l1 + a2l2 + … + amlm d L , iar L – (a1l1 + a2l2 + … + amlm) = restul retetei = ri.
• Á1, Á2, …, Án = retetele posibile de croire a reperelor din suportul dat.
• b1, b2, …, bm = cantitatile în care reperele trebuie executate.
• r1, r2,…, rn = resturile inutilizabile ce rezulta din aplicarea O DATA a retetelor Á1, Á2, …, Án.
În activitatea de producere a cantitatilor necesare de repere fiecare reteta va fi aplicata de un numar de ori, posibil zero.
• xj = numarul de aplicari ale retetei Áj = MULTIPLICITATEA retetei Áj.
Restul total rezultat din aplicarea retetelor Á1,…, Án cu multiplicitatile x1,…, xn este dat de expresia:
f = r1x1 + r2x2 + … + rnxn
Conditia de realizare a cantitatilor cerute de repere se transcrie astfel:
Cercetari operationale cibernetica anu 3
Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.
