REALIZAREA UNUI MODEL DE OPTIMIZARE A DIMENSIUNII SI STRUCTURII ACTIVITATILOR DIN EXPLOATATIA AGRICOLA

1. METODA VARIANTELOR LOGICE SAU METODA CONSTRUCTIVA

Se cauta variante care folosesc complet cat mai multe resurse. In acesta situatie se calculeaza aportul marginal al unei resurse care reprezinta oscilatia pro prin ocilatii ale resurselor cu o tului total cand se produce o crestere sau descrestere a resursei folosite complet cu o unitate. Se calculeaza in acest fel aportul marginal pentru toate resursele folosite in intregime.( ApmR1, ApmR2,)

Se apreciaza varianta care ofera cele mai bune oportunitati exploatatiei In rezolvarea problemei se poate recurge la procurarea unor inputuri din afara exploatatiei. De exemplu forta de munca sezoniera. Acest lucru se admite numai daca aportul marginal ( Ex. ApmR1) al unei unitati de resursa este mai mare decat costul achizitionarii acestei unitati de resursa ( CachR1). Deci ApmR1>cahR1

Se procedeaza in acelasi fel pentru fiecare resura consumata in intregime. In aprecierea costului achizitionarii resursei se tine cont si de cheltuielile colaterale ale inputului. De exemplu pentru forta de munca se tine cont de cheluielile de transport, cazare, hrana, asigurari sociale etc.

2. METODA PROGRAMARII LINIARE DE OPTIMIZARE A DIMENSIUNII SI STRUCTURII CULTURILOR EXPLOATATIEI AGRICOLE

Metodele moderne se refera atat la proiectarea de variante tehnologice, dar si la alegerea variantei care corespunde cel mai bine unui obiectiv (exemplu profit maxim pe unitatea de produs etc.).

Aceste metode utilizeaza ca baza de date atat experienta celui care proiecteaza aceste tehnologii, dar si observatii statistice, normative si date experimentale.

PROGRAMAREA LINIARA

Multimea sistemelor economice concrete si multitudinea problemelor conducerii acestora au creat o diversitate de reprezentari economico-matematice, denumite modele.

Varietatea acestora este determinata, in principal, de structura 'obiectului' analizat, de scopul cercetarii precum si de informatia disponibila.

Modelele de programare matematica si mai ales subclasa acestora - modelele de programare liniara - ocupa un loc deosebit de important, atat in teoria cat si in practica economica. Teoria economica a beneficiat de aportul abordarii interdisciplinare care a permis aprofundarea analizei eficientei maximale a sistemelor complexe, a permis descoperirea unor concepte noi ale optimului economic, a perfectionat metodele de cercetare si cunoastere iar practica economica s-a imbogatit cu un instrument deosebit de util analizei economice si fundamentarii deciziilor.

Structura modelului general de programare liniara se constituie in primul rand prin multimea de activitati care compun sistemul economic analizat, multimea de resurse utilizate precum si prin relatiile tehnico-economice dintre acestea. Legatura dintre activitati si resurse este determinata de tehnologia de fabricatie corespunzatoare fiecarei activitati A_j (j=1,,n) si poate fi caracterizata numeric prin vectorul coloana a^(j) de componente (a_1j, a_2j, a_mj). Elementele se numesc coeficienti tehnici sau coeficienti de consum specific si arata ce cantitate din resursa R_i se consuma pentru producerea unei unitati din produsul (serviciul) P_j (ca rezultat al activitatii A_j). Toate 'tehnologiile' de fabricatie definite de vectorii coloana a^(j) se pot organiza intr-o matrice A cu m linii si n coloane; fiecare linie se refera la o resursa R_i (i = 1,,m) si fiecare coloana se refera la o activitate A_j (j = 1,,n).

Notand cu x_j (j = 1,,n) rezultatul activitatii A_j intr-o perioada data si cu b_i (i = 1,,m) cantitatile disponibile din resursele R_i (i = 1,,m), se pot scrie matematic urmatoarele restrictii tehnico-economice:

sau A xij £ bi

unde A = ; x = si b =

Fiecare inecuatie/restrictie incorporeaza doua afirmatii:

a.              cantitatea consumata dintr-o resursa nu poate depasi volumul disponibil (propozitie de logica economica)

b.              consumul total R_ij din resursa R_i pentru efectuarea activitatii A_j este proportional cu intensitatea acesteia, adica cu x_j, deci R_ij = a_ij x_j (ipoteza simplificatoare)

Sistemul de restrictii (1) realizeaza legatura dintre resurse si activitati prin intermediul celor m restrictii liniare.

Modelul problemei de programare liniara contine restrictii de tipul (1) precum si un criteriu de 'performanta' care sa permita evaluarea eficientei fiecarei activitati. In functie de scopul urmarit, putem alege drept criteriu de eficienta un indicator care masoara efortul, unul care masoara rezultatul sau un indicator exprimat ca raport intre rezultat si efort (sau efort pe rezultat).

Este evident ca eficienta maxima inseamna minimizarea efortului si maximizarea rezultatului, iar conceptul de optim se defineste, in acest caz, ca un program xI Rⁿ care minimizeaza sau maximizeaza o functie obiectiv si, in acelasi timp, satisface toate restrictiile tehnico-economice.

Presupunand ca fiecare componenta a vectorului linie c = (c₁, c₂, , c_n) masoara eficienta unei unitati din rezultatul activitatii A_j, atunci se poate introduce functia liniara:

f(x) = c₁ x₁ + c₂ x₂ + + c_n x_n

care evalueaza performanta oricarui program x.

Sintetizand, obtinem urmatorul program de programare liniara:

unde I1 È I2 =

     

Relatiile (1), (2) si (3) constituie impreuna modelul general al unei probleme de programare liniara, avand fiecare un rol specific:

relatia (1), unde f(x) = este denumita functia obiectiv de eficienta a problemei, evalueaza eficienta/performanta fiecarei variante de program x;

relatiile (2) de tipul reprezinta restrictii de tip resurse; iar restrictiile de tipul se refera la restrictii tehnico-economice de tip calitativ (si ca urmare indicatorul b_k este limita inferioara impusa 'retetei optime';

relatia (3) x_j ³ 0 j = 1,,n, numita conditia de nenegativitate a variabilelor, asigura obtinerea unei solutii realizabile din punctul de vedere al logicii economice.

Daca se doreste obtinerea unui meniu (retete furajere), care sa asigure necesarurile dintr-un numar de m substante esentiale organismului, avand la dispozitie un numar de n alimente, cunoscandu-se cantitatile din fiecare substanta pe care le contine o unitate de masura din fiecare aliment si costurile unei unitati de masura din fiecare aliment, putem scrie modelul:

Variabilele x_j reprezinta, in acest caz, cantitatea din fiecare aliment ce va intra in meniu iar f(x) = este costul total al retetei definita de vectorul x.

Se observa ca toate aceste probleme, cu toate ca reprezinta situatii economice total diferite, sunt aplicatii in sfera activitatii economice ale urmatoarei probleme de optimizare:

in care functiile f,g_i : Rⁿ R pot avea orice forma si proprietati (liniare, convexe, continui, diferentiabile etc.) iar W poate fi orice submultime a lui Rⁿ (continua sau discreta, marginita sau nemarginita, convexa sau neconvexa, finita sau infinita etc.) si in care dorim sa gasim minimul sau maximul functiei f in variabilele x_i care indeplinesc restrictiile 1.2 si 1.3. O astfel de problema se numeste problema de programare matematica.

Functia (1.1) se numeste functia obiectiv a problemei de optimizare. In aplicatiile economice, ea reprezinta criteriul de performanta urmarit: maximizarea beneficiului, maximizarea productiei marfa, minimizarea costului productiei, maximizarea gradului de incarcare al utilajelor sau minimizarea timpului de stationare al acestora, maximizarea veniturilor etc.

Inegalitatile (1.2), in care g_i sunt functii de n variabile iar b_i sunt constante, se numesc restrictii ale problemei de optimizare. Ele traduc in limbaj matematic conditiile de natura economica sau tehnologica in care se desfasoara procesul economic modelat, cum ar fi: nedepasirea stocurilor disponibile de resurse (materii prime, capacitati de productie, forta de munca, fonduri banesti, timp etc.), indeplinirea sau depasirea unor indicatori economici (productia fizica, neta) etc.

Conditiile (1.3), impuse 'direct' variabilelor, depind de natura problemei studiate. De cele mai multe ori, W este multimea vectorilor x = (x_l,,x_n) I Rⁿ cu toate componentele nenegative si acest fapt se justifica prin aceea ca, in general, x_i reprezinta 'nivelele' unor activitati de productie, nivele care nu pot fi negative. In unele probleme de optimizare, cum ar fi cele de croire sau ordonantare, variabilele desemneaza marimi indivizibile si deci nu pot lua decat valori intregi. Multimea W va fi formata in acest caz din vectori x cu toate componentele intregi si nenegative. In alte probleme, ca de pilda cele de afectare, portofoliu etc., variabilele nu pot lua decat valorile 0 sau 1 (variabile bivalente) si ca atare W va fi formata din vectorii x = (x₁, .,x_n) cu toate componentele 0 sau 1. Caracteristic acestor tipuri de probleme este faptul ca W devine o submultime discreta din Rⁿ, de unde si numele generic de probleme de optimizare discreta dat acestora.

O solutie a unei astfel de probleme are deci trei proprietati:

P1.            verifica restrictiile 1.2

P2.            verifica restrictiile 'directe' 1.3

P3.            optimizeaza functia obiectiv pe multimea vectorilor care indeplinesc conditiile P1. si P2.

In teoria programarii matematice se folosesc, pentru claritatea si simplitatea expunerii, urmatoarele notiuni:

Izvorata din studiul problemelor externale ale analizei matematice clasice, programarea matematica a cunoscut in ultimele decenii o dezvoltare spectaculoasa, explicabila numai in parte prin progresele inregistrate in matematica. Intr‑adevar, aceasta dezvoltare a fost puternic stimulata de cresterea vertiginoasa a complexitatii activitatilor economice, care a furnizat probleme cu structuri din ce in ce mai complicate, ca si de rapida perfectionare a mijloacelor automate de calcul, singurele capabile sa testeze eficienta practica a metodelor teoretice elaborate. La randul ei, programarea matematica, prin rezultatele ei, a adus un considerabil aport la perfectionarea metodelor de conducere in economie si a impulsionat cercetarile ‑ in plan teoretic ‑ privind modelarea sistemelor economice complexe, studiul si interpretarea legilor si proceselor economice.

In ceea ce priveste rezolvarea acestor probleme, este evident ca varietatea extrema a acestora face imposibila gasirea unui algoritm practic care sa le poata rezolva pe toate, dar putem gasi (sau ne putem astepta sa gasim), pentru fiecare caz particular, un algoritm de rezolvare care sa-si traga eficacitatea tocmai din folosirea tuturor particularitatilor cazului respectiv. In prezent exista sute de algoritmi de rezolvare, cercetarea problemei evoluand din ce in ce mai mult spre testarea si imbunatatirea acestora decat spre gasirea unora noi.

Problema de programare liniara

Definitia 1. Daca intr-o problema de programare matematica functia obiectiv f si functiile g_i, din restrictiile 1.2, sunt functii liniare atunci problema se numeste problema de programare liniara. O problema de programare liniara este, deci, un caz particular al problemelor de programare matematica si, tinand cont de forma oricarei functii liniare, rezulta ca forma generala a oricarei probleme de programare liniara este:

unde c_j (coeficientii functiei obiectiv), a_ij (coeficientii restrictiilor) si b_i (termenii liberi) sunt constate reale.

Forma conica si forma standard a unei probleme de programare liniara

Cu toate ca problema de programare liniara este cea mai simpla dintre problemele de programare matematica, ea este inca destul de complicata, prin faptul ca orice restrictie poate avea trei forme diferite iar obiectivul poate fi minimizarea sau maximizarea functiei f. Este putin probabil ca exista un algoritm si simplu si aplicabil la toate cazurile.

Din acest motiv este mult mai simplu sa gasim o anumita forma (cat mai simpla) cu proprietatea ca pentru orice problema P, exista o alta problema P' de aceasta forma, echivalenta cu problema initiala P (spunem ca doua probleme sunt echivalente daca exista un izomorfism intre multimile solutiilor celor doua probleme si un homeomorfism intre functiile lor obiectiv) si sa dispunem de un algoritm care sa rezolve problemele de aceasta forma si de o regula prin care sa gasim solutia problemei initiale P din solutia problemei P', gasita cu acest algoritm.

In acest sens (dar si din cauza frecventei aparitiei lor in practica) s-au evidentiat doua forme ale problemelor de programare liniara, forma canonica si forma standard.

Definitia 2. Spunem ca o problema este la forma canonica daca are una din urmatoarele doua forme:

Aceasta forma este invarianta la anumite transformari (cum ar fi problema duala) si asigura existenta solutiei (orice problema la aceasta forma, care are termenii liberi si coeficientii restrictiilor pozitivi, are solutie).

Definitia 3. Spunem ca o problema este la forma standard daca are forma:

Aceasta forma, desi nenaturala din punct de vedere economic, este cea care se preteaza cel mai bine la rezolvarea cu metodele algebrei clasice.

Propozitie Pentru orice problema de programare liniara P exista o problema la forma canonica PFC si o problema la forma standard PFS echivalente cu P.

Demonstratie. Intr-adevar:

a)        orice problema de maxim poate fi transformata in una de minim si reciproc folosind relatia:

max f(x) = - min f(-x)

b)        orice restrictie de tipul '£' poate fi transformata intr-o restrictie de forma '³' si reciproc folosind relatia:

a £ b Û a ³ b

c)        orice restrictie inegalitate poate fi transformata in egalitate, prin introducerea unei variabile suplimentare nenegative si folosind relatiile:

a £ b Û si a ³ b Û

Toate variabilele introduse pentru transformarea inegalitatilor in egalitati se numesc variabile de abatere sau variabile de compensare.

d)        orice restrictie egalitate poate fi transformata in restrictii inegalitate, folosind relatia:

a b Û

e)        orice variabila cu restrictie de semn negativa (x £ 0) poate fi inlocuita cu o variabila cu restrictie de semn pozitiva (y ³ 0), folosind relatia:

x £ Û

f)  orice variabila fara restrictie de semn poate fi inlocuita cu doua variabile cu restrictie de semn pozitiva, folosind relatia:

x oarecare Û

Se demonstreaza fara un efort matematic deosebit ca daca P' se obtine din P folosind doar transformarile de mai sus (numite si transformari elementare) atunci P si P' sunt doua probleme echivalente si intre solutiile lor optime exista o bijectie.

Din cele de mai sus rezulta cum poate fi adusa orice problema de programare liniara la forma standard (sau canonica) si cum se obtine solutia problemei initiale din solutia problemei la forma standard (sau canonica).

Rezolvarea problemei poate duce la urmatoarele rezultate:

R1.           Sistemul A x = b nu are solutii sau nu are solutii admisibile. In acest caz problema nu are solutie.

R2.           Imaginea functiei obiectiv pe multimea solutiilor admisibile este nemarginita (la +¥ intr-o problema de maxim sau la -¥ intr-o problema de minim). In acest caz spunem ca problema are optim infinit.

R3.           Imaginea functiei obiectiv pe multimea solutiilor admisibile este marginita. In acest caz problema are cel putin o solutie si spunem ca problema are optim finit.

Greutatea gasirii solutiei problemei consta in imensitatea numarului de solutiilor posibile ale sistemului si in respectarea conditiei de nenegativitate a celor re care cautam extremul dorit al functiei f. Este natural ca primele incercari in rezolvare sa caute in primul rand o limitare cat mai puternica a locului in care cautam. Pe baza unor reprezentari geometrice ale problemei au fost descoperite urmatoarele proprietati ale problemei, care poarta denumirea de teoreme fundamentale ale programarii liniare:

Teorema 1. Daca problema de programare liniara are solutii admisibile atunci are si solutii de baza admisibile.

Teorema 2. Daca problema de programare liniara are solutii optime atunci are si solutii optime de baza.

Teorema 3. Multimea solutiilor admisibile (optime) este inchisa si convexa. Daca este si marginita atunci punctele extremale ale acesteia sunt chiar solutiile admisibile (optime) de baza ale problemei.

Cele doua teoreme realizeaza efectiv trecerea catre o problema rezolvabila pe calculator. Intr-adevar, deoarece o baza este un minor de ordinul m al matricii A si unei baze ii corespunde o unica solutie de baza rezulta ca sunt cel mult solutii de baza, adica un numar finit. In acest moment s-ar parea ca nu avem decat sa lasam calculatorul sa calculeze toate solutiile de baza si valorile functiei obiectiv in cele admisibile gasind-o prin comparare pe cea care da minimul sau maximul functiei re acestea. Totusi, aceasta varianta se dovedeste nepractica la o analiza mai atenta, tinand cont de urmatoarele observatii:

faptul ca numarul solutiilor de baza este finit ne asigura doar ca problema se va termina candva, ceea ce, din punct de vedere economic, este evident nemultumitor. Noi dorim ca problema sa fie rezolvata in timp util, adica repede. Rezolvand problema ca mai sus vom avea, pentru o problema cu 50 variabile si 20 restrictii, de calculat, listat si comparat solutii de baza, adica in jur de 10²⁰. Presupunand ca suntem dotati cu un supercalculator care ar termina un miliard de baze pe secunda, rezolvarea ar dura 3000 ani. De altfel, o problema ca cea de sus este foarte mica in comparatie cu problemele 'serioase' ce au peste 1000 de variabile si 100 de restrictii. In plus, un calculator ca cel de sus nu exista inca, deci in nici un caz nu e disponibil intreprinderilor obisnuite.

Cu algoritmul de mai sus vom gasi cea mai buna solutie dintre solutiile admisibile de baza, fara insa sa stim daca problema admite, de fapt, optim (ar putea sa aiba optim infinit).

Nu vom sti daca un minor de m m este baza decat dupa ce-i vom calcula determinantul si nu vom sti daca solutia de baza corespunzatoare este admisibila decat dupa ce o vom calcula.

Solutia optima, odata gasita, nu va fi recunoscuta ca atare decat dupa ce vom calcula toate celelalte solutii de baza, chiar daca ea a aparut chiar la inceputul calculelor.

In concluzie, pentru a fi eficient, un algoritm ar trebui sa aiba urmatoarele proprietati:

a)        sa dispuna de un criteriu de recunoastere a faptului ca problema nu are solutii admisibile;

b)        sa dispuna de un criteriu de recunoastere daca o solutie este optima sau nu;

c)        sa treaca de la o solutie de baza admisibila la una cel putin la fel de buna (o solutie x este mai buna decat o solutie y daca f(x) > f(y) intr-o problema de maxim si f(x) < f(y) intr-o problema de minim;

d)        sa treaca de la o solutie la cea mai buna dintre solutiile cel putin la fel de bune posibile ca succesoare;

e)        sa nu revina la o solutie deja analizata;

f)  sa efectueze un numar de iteratii comparabil polinomial cu dimensiunea problemei.

g)        sa nu introduca erori de rotunjire (sau nu prea mari);

h)        sa fie cat mai simplu de implementat;

3. MODELUL MATEMATIC DE OPTIMIZARE A DIMENSIUNII EXPLOATATIEI AGRICOLE.

in optimizarea dimensiunii exploatatiei agricole se utilizeaza algoritmul simplex care va fi prezentat succint din punct de vedere matematic.

Algoritmul simplex pleaca de la presupunerea ca dispunem deja de o solutie admisibila de baza x_B, corespunzatoare unei baze B. De asemenea, presupunem ca s-a rezolvat sistemul A x = b folosind aceasta baza, rezultand astfel variabilele principale in functie de cele secundare:

Presupunem astfel ca problema este la forma standard de maxim si ca dispunem de o solutie de baza admisibila.

Pasul 1.   

Pasul 2.    Se construieste tabelul simplex corespunzator bazei de care dispunem in ordinea urmatoare:

pe linia a doua se trec toate variabilele intr-o ordine oarecare;

pe prima linie se trec coeficientii functiei obiectiv, fiecare deasupra variabilei corespunzatoare;

se construieste matricea A, fiecare coloana fiind formata din coeficientii unei variabile din toate ecuatiile (ordinea in care se parcurg ecuatiile trebuie sa fie aceeasi pentru toate variabilele), avand grija ca, coloanele sa fie trecute in ordinea in care au fost trecute variabilele pe linia 2;

se construieste baza B, ordinea coloanelor fiind cea in care apar ele in matricea A;

se calculeaza B^-1;

se calculeaza B^-1 A si se trece in partea centrala a tabelului;

se trec variabilele principale in a doua coloana, in asa fel incat, la intersectia liniei si coloanei corespunzatoare acestei variabile, sa se afle valoarea 1.

se trec in prima coloana coeficientii corespunzatori variabilelor principale din functia obiectiv, fiecare in dreptul variabilei corespunzatoare;

se calculeaza solutia de baza cu formula B^-1 b, avand grija ca ordinea in care au fost trecuti termenii liberi in vectorul b sa fie aceeasi cu ordinea in care au fost parcurse ecuatiile la formarea matricii A;

se trec in a treia coloana valorile variabilelor principale din solutia de baza, fiecare in dreptul variabilei corespunzatoare;

se calculeaza f(x_B) inmultind doua cate doua componentele coloanei 1 cu cele din coloana 3 aflate pe aceeasi linie si adunand toate produsele intre ele (adica facem produsul scalar dintre c_B si x_B);

se calculeaza pe rand fiecare z_j j = 1,,n un z_j obtinandu-se inmultind scalar c_B cu coloana j din B^-1 A aflata in centrul tabelului (aceasta linie se calculeaza si se trece doar in primul tabel, scopul ei fiind calcularea lui D

se calculeaza pe rand fiecare D_j j = 1,,n scazand din linia lui z linia lui c (D_j = z_j - c_j)

Pasul 3.    Se analizeaza valorile D_j corespunzatoare variabilelor secundare (e usor de vazut ca intotdeauna, cei corespunzatori variabilelor principale sunt toti 0, deci neinteresanti).

daca toti sunt mai mari sau egali cu 0 atunci solutia actuala este cea optima. Daca exista D_j = 0 in afara bazei, atunci pot aparea doua cazuri:

toate elementele din coloana a_j din B^-1 A sunt mai mici sau egale cu 0. Atunci toate solutiile de forma x_B - a_j l sunt solutii optime, unde l > 0 oarecare;

exista o componenta a_ij a coloanei a_j strict pozitiva. Atunci introducand variabila x_j in baza in locul variabilei principala x_i obtinem alta solutie de baza optima.

Daca apar numai cazuri de tipul 2), obtinem toate solutiile de baza optime, multimea tuturor solutiilor optime fiind formata din toate combinatiile convexe ale acestora. Daca apare si cazul 1) atunci multimea solutiilor optime este nemarginita fiind formata din combinatiile convexe ale solutiilor de forma x_B - a_j l unde x_B sunt toate solutiile optime de baza.

daca exista D_j < 0 atunci il alegem pe cel mai negativ: D_k . Variabila x_j va fi cea care intra in noua baza. Daca minimul este multiplu atunci alegem, la intamplare, unul dintre acestia (cei minimi).

Pasul 4.    Se analizeaza elementele coloanei a_j din B^-1 A, corespunzatoare variabilei alese la pasul 2.

Daca toate sunt mai mici sau egale cu 0 atunci problema are optim infinit si algoritmul ia sfarsit;

Daca exista componente strict pozitive, pentru acestea se calculeaza rapoartele q_s Variabila x_i corespunzatoare raportului minim este cea care va iesi din baza. Daca acest minim este multiplu sunt posibile doua cazuri:

minimul este strict pozitiv. In acest caz se alege unul dintre acestia la intamplare;

minimul este 0. Atunci x_i corespunzatori sunt 0, deci solutia este degenerata si noua solutie este la fel de buna. Aceasta situatie poate duce la ciclarea algoritmului si alegerea la intamplare nu mai este suficienta, fiind nevoie de o regula de alegere suplimentara care sa evite ciclarea. O metoda de alegere se bazeaza pe faptul ca intotdeauna prima baza este matricea unitate si in dreptul ei, in toate tabelele simplex, se va afla inversa bazei corespunzator fiecaruia. In acest caz, pentru pozitiile in care s-a obtinut minimul impartim prima coloana a lui B^-1 la coloana a_j si alegem minimul dintre aceste rapoarte. Daca minimul dintre acestia este tot multiplu continuam procedeul, pentru pozitiile ce dau noul minim, cu coloana a doua din B^-1 si asa mai departe, pana minimul ramane unic. Nu este posibil sa se epuizeze toate coloanele lui B^-1 si minimul sa ramana multiplu, deoarece, in acest caz, am avea: , pentru toti indicii j_k ai coloanelor lui B^-1, i₁ si i₂ fiind doi din indicii care dau acelasi minim pana la sfarsit sau altfel scris pentru orice j_k Þ liniile i₁ si i₂ din B^-1 sunt proportionale, fapt ce contrazice faptul ca B^-1 este inversabila.

Pasul 5.    Se calculeaza componentele tabelului simplex corespunzator noii baze pe baza tabelului actual si folosind urmatoarele reguli:

- se incadreaza elementul a_ij, aflat la intersectia coloanei variabilei care intra in baza cu linia variabilei care iese din baza, care a fost numit de Danzig pivot, intr-un dreptunghi

coloana pivotului va avea 1 in dreptul pivotului si 0 in rest (inclusiv D_j

linia pivotului este linia actuala impartita la pivot (inclusiv in solutia de baza);

restul elementelor se calculeaza cu regula dreptunghiului (inclusiv solutia de baza, D si f(x_B)). Regula dreptunghiului se bazeaza pe observatia ca in toate formulele prin care se calculeaza acestea nu apare decat valoarea lor actuala, pivotul si cele doua elemente care ar completa dreptunghiul ce are pozitia de calculat si pivotul pe diagonala. Regula dreptunghiului se enunta literar astfel: 'noua valoare = produsul dintre elementele de pe diagonala pivotului minus produsul dintre cele aflate pe cealalta diagonala totul impartit la pivot'. (pentru scurtarea timpului de lucru se poate observa ca elementele unei linii care are 0 pe coloana pivotului raman aceleasi si de asemenea elementele unei coloane care are 0 pe linia pivotului)

Operatia de calculare a noului tabel prin regulile de mai sus poarta denumirea de pivotare.

Daca toate componentele sunt mai mari sau egale cu 0 atunci solutia este si primal admisibila, deci optima.

Pasul 6.    Se reia algoritmul de la pasul 2daca exista componente strict negative.

Concret, pentru ceea ce am realizat metoda presupune parcurgerea urmatoarelor etape:

1 Stabilirea modelului matematic

2 Rezolvarea modelului prin metoda SIMPLEX si interpretarea primal-duala a solutiei

1.Stabilirea modelului matematic

Modelul matematic cuprinde:

a) Functia obiectiv

1)Resurse

2) Restrictiile modelului

b) Conditia de nenegativitate

a) Functia obiectiv sau scop

exemplu : C1*X1 + C2*X2 + C3*X3 ++ Ci*Xi ++ CnXn

in care :

X1Xn = activitatile ( hectare culturi,capete animale )

C1Cn = aportul unei UM din activitate (profit ,cheltuieli energie etc.)

Obiectivul poate fi de maxim sau de minim ,in functie de scopul propus;

b) Restrictiile modelului in conditiile optimizarii dimensiunii

Pentru modelul de optimizare a structurii si dimensiunii unei exploatatii agricole

Ø      restrictii tehnice :

Ø      L1 - suprafata culturilor de baza nu poate depasi suprafata de care dispune exploatatia agricola (ST1, ST2, ST3)

X1 + X2+ + Xi+. ..Xn <=ST1, ST2, ST3

Ø      restrictii economice :

Ø      L10 - zile norma ce vor fi consumate nu pot depasi zile normale disponibile (ZND)

ZN1*X1 + ZN2*X2+..+Ni*Xi++Nn*Xn <= ZND

Ø      restrictii de rotatie :

Ø      L20 - suprafata culturilor X1,X2 si X5 nu trebuie sa ocupe mai mult decat 1/2 din suprafata totala :

X1 + X2 + + X5 <= ST1/2, ST2/2, ST3/2

Schema reprezinta legatura dintre matricea coeficientilor tehnici generata de produsul program AGR4 (matricea initiala), modificarea ei cu ajutorul programelor procsms_simpex.prg, aleglidp.prg, intreb.prg si intrebDN.prg (matricea finala), rezolvarea modelului si interpretarea solutiei primale si duale.

Intocmirea interactiva a matricei se face accesind ( care ruleaza sub FOX )

procsms_simpex.prg

AGR4    Programul Simplex

Solutii

FUNCTIA OBIECTIV (generata automat)     C1.x1+c2 .x2+c3.x3+ +cn.xn

F1 F2 Denu- Mire L1 L2 Lm

RESURSE (interactiv) 1 2 3.. n

STOT1 m+2

STOT m+1

ST3/2

ST2/2

ST1/2

ST3

ST2

ST1

Interactiv

APLICATIA PRODUSUL PROGRAM AGR4 MIJLOC DE GENERARE AUTOMATA A MATRICEI COEFICIENTILOR TEHNICI

Pentru optimizarea suprafetei si profilului unei exploatatii agricole trebuie sa selectam un plan si un cod de ferma realizate de Produsul Program AGR4

PLANUL SE INTOCMESTE ASTFEL:

Se aleg culturile din baza de date care vor intra in modelul de programare liniara.

Se face o verificare formala prin Listare fisa

Se opereaza Calcul fisa

Se listeaza pe ecran Recapitulatie fisa

In PLAN se intocmeste un PLAN ( ex PLVG199) cu fisele culturilor selectate

ATENTIE !!!

In acest PLAN suprafata culturilor va fi de 1 Ha

Se calculeaza planul.

Descrierea modului de lucru asupra matricii generate de programul AGR

Se cauta in fisierul AGR4 programul procsms_simpex.prg care se acceseaza

Se selecteaza Codul PLANULUI ( ex PLVG199) si un cod de ferma realizate de Produsul Program AGR4

in continuare vor fi prezentate fazele de generare a matricei modelului.

In prima faza de completare a matricilor F si A suntem intrebati daca **** -dorim o listare a matricei , Iimplicit este NU.

in functie de marimea marticilor este posibil sa asteptam cateva secunde lucru semnalat de program. Pe ecran ne v-a aparea gradul de completare in procente .

**** Automat calculatorul genereaza o matrice care contine :

a.          Numarul de coloane este egal cu numarul de culturi introduse in PLAN ( ex PLVG199);

b.         numarul de linii ( restrictii) este variabil . Sunt inscrise necesarurile de ZN manual , ZN mecanic si necesarul de apa pe fiecare luna in parte in dreptul fiecarei culturi . ( Ar fi 36 de linii , insa calculatorul nu retine decat liniile unde gaseste valori. Daca de exemplu in luna ianuarie nu se efectueaza nici-o lucrare mecanica acel rand ( restrictiie) nu se retine)

Noi in continuare avem urmatoarele posibilitati : de a adauga coloane, de a introduce operatorii relationali (<, = sau >), de a introduce valoarea termenului liber , de a adauga linii ( in general restricii agrotehnice de rotatie dar si unele restricii de piata ( de a nu produce mai mult de .tone).

**** La urmatoarea operatie suntem interogati daca dorim sa adaugam coloane, NU fiind modul implicit.

in urmatoarea faza introducem

**** - operatori relationali in functie de cerinte (<, = sau >),

Se va introduce operatorul relational < care inseamna ca in timpul rezolvarii resursele pot fi mai mici decat cele pe care le introducem sau cel mult egale cu aceste resurse. In momentul cand se intoducem = suntem obligati sa consumam acea resursa iar cand se introduce > de asemenea suntem obligati ca prin rezolvarea modelului resursa respectiva sa fie egala sau mai mare decat valoarea inscrisa de noi. Semnele = sau > se introduc dupa o prima rezolvare cu semnul < pentru a vedea ca modelul are o solutie, deoarece = sau > poat bloca rezolvarea pentru gasirea unei solutii.

**** - urmeaza o interogare legata de numarul de termeni liberi pe care dorim sa-i utilizam, ( pentru inceput trecem 1); si

**** - valoarea termenului liber pentru toate restrictiile modelului

pe ecran vor fi afisate liniile din matrice in urmatoarea ordine : Zn manual pe luni, ZN mecanic pe luni, Consum apa de irigat pe luni, consum azot, consum fosfor, consum potasiu, Retributii manual, Retributii mecanizaat, Lucrari terti, Chelt totale. Valorile aproximative vor fi calculate inainte de inceperea calculului

**** - urmeaza o interogare daca dorim sau nu adaugarea de o noua linie, valoarea implicita pentru iesire fiind NU.

Atentie !!! Se vor adaga linii.

O noua linie presupune : valoarea fiecarui coeficient al variabilelor, operatorul relational (<, = sau >), valoarea termenului liber si denumirea restictiei ce va fi adaugata.

Vom introduce valorile variabilelor astfel : de EXEMPLU

Pentru: X1 + X2 + + X5 < ST

Se introduc :

Termenii care se introduc : 1 1 1 < ST

si urmata de denumirea liniei, in cazul nostru SUPRAFATA TOTALA,

Nu exita limite in ceea ce priveste numarul de linii (restrictii) ce vor putea fi adaugate.

Recomandam ca liniile sa fie scrise pe o foaie pentru a le introduce corect in model.

**** - urmeaza o interogare daca mai dorim sau nu adaugarea de noi linii, valoarea implicita pentru iesire fiind NU.

**** - odata cu terminarea adaugarii de linii suntem intrebati daca dorim listarea informatiilor obtinute (implicit NU).

*** Pentru o eventuala refolosire a matricii putem introduce un nume sub care se va salva fisierul. Acest fisier v-a avea o extensie de tip DBF.

*** Daca dorim sa stergem o linie din marice indicam numarul ei, pe care l-am putut nota cand am adaugat valorile termenului liber

*** daca nu introducem valoarea 999.

in final obtinem matricea pe care trebuie sa o denumim

**** introduceti numele fisierului de structura fara indicarea extensiei ( ex. TOpt1) fisier care va fi preluat pentru rezolvare in programul SIMPLEX .

*** - Doriti rezolvarea modelului ? implicit este NU

Daca ai scris Y atunci esti in programul SIMPLEX de optimizare.

5. PRODUSUL PROGRAM SIMPLEX DE INTOCMIRE, REZOLVARE SI INTERPRETARE A MODELULUI MATEMATIC DE OPTIMIZARE A DIMENSIUNII SI STRUCTURII CULTURILOR EXPLOATATIEI AGRICOLE

INTOCMIREA MODELULUI MATEMATIC

de programare liniara pentru stabilirea dimensiunii activitatilor din exploatatia agricola:

1 Stabilirea modelului matematic

2 Rezolvarea modelului prin metoda SIMPLEX si interpretarea primal-duala a solutiei

1.Stabilirea modelului matematic

Modelul matematic cuprinde:

a) Functia obiectiv

1)Resurse

2) Restrictiile modelului

b) Conditia de nenegativitate

a) Functia obiectiv sau scop

exemplu : C1*X1 + C2*X2 + C3*X3 ++ Ci*Xi ++ CnXn

in care :

X1Xn = activitatile ( hectare culturi,capete animale )

C1Cn = aportul unei UM din activitate (profit, cheltuieli energie etc.)

Obiectivul poate fi de maxim sau de minim, in functie de scopul propus;

b) Restrictiile modelului in conditiile optimizarii dimensiunii

Pentru modelul de optimizare a structurii si dimensiunii unei exploatatii agricole

Ø      restrictii tehnice :

Ø      L1 - suprafata culturilor de baza nu poate depasi suprafata de care dispune exploatatia agricola (ST1, ST2, ST3)

X1 + X2+ + Xi+. ..Xn <=ST1, ST2, ST3

Ø      restrictii economice :

Ø      L10 - zile norma ce vor fi consumate nu pot depasi zile normale disponibile (ZND)

ZN1*X1 + ZN2*X2+..+Ni*Xi++Nn*Xn <= ZND

Ø      restrictii de rotatie :

Ø      L20 - suprafata culturilor X1,X2 si X5 nu trebuie sa ocupe mai mult decat 1/2 din suprafata totala :

X1 + X2 + + X5 <= ST1/2, ST2/2, ST3/2

REZOLVAREA MODELULUI

In caz ca ai ratat preluarea directa pentru continuare se procedeaza astfe:

- se acceseaza qb executabil

- in FILE se acceseaza Lp13.bas

- se acceseaza comanda RUN , Start

Produsului Program SIMPLEX se prezinta astfel :

' OPTIMIZAREA STRUCTUTII CULTURILOR '

' Metoda PROGRAMARII LINIARE - SIMPLEX'

'-------- ----- ------ ----- ----- ----- ----- ------'

' - ATENTIE ! DATELE SUNT CITITE DIN FISIER'

'-------- ----- ------ ----- ----- ----- ----- ------'

' - Te rog sa introduci : '

' M pentru intoarcere in meniul APLICATIE'

-------- ----- ------ -------- ----- ------ -

' Nume fisier fara extensie'..NUMELE FISIERULUI

-------- ----- ------ -------- ----- ------ -

' - Apasa o tasta pentru continuare '

Se afiseaza pe ecran:

' Nr. de restrictii de tip / > / = '; G

' Nr. de restrictii de tip / = / = '; E

' Nr. de restrictii de tip / < / = '; L

FE1$ = 'MAXIM PROFIT'

FE2$ = 'MAXIM MARJA BRUTA'

'-------- ----- ------ ----- ----- ----- ----- ------'

' -Numar de functii obiectiv 2'

' 1. '; FE1$

' 2. '; FE2$

'-------- ----- ------ ----- ----- ----- ----- ------'

' - Alege functia de optimizat /1,2, '; .., se alege 1

' Nr. de termeni liberi = '; se inscrie 1

' - Doresti imprimarea matricei ? N/D '; Implicit NU

Se afiseaza pe ecran:

' Matricea coeficientilor :'

' Termenul liber nr. '; 1

' - Apasa o tasta pentru continuare ';

Se afiseaza solutia mdelului , respectiv solutia primala si solutia duala astfel:

VARIABILE PRIMALE

'Variabila: Denumire: Marime : Valoarea Aport '

' in Functii. Ob.: la Func. Ob.:'

-------- ----- ------ -------- ----- ------ ----- ----- ----- ----- ----

' - Apasa o tasta pentru continuare '; ..

'VARIABILE DUALE:'

'-------- ----- ------ -------- ----- ------ ----- ----- ----------'

'Variabila:' 'Denumire:' "Valoare' 'APORT '

-------- ----- ------ -------- ----- ------ ----- ----- -------------

'VALOAREA FUNCTIEI OBIECTIV = '----- ----- --------- ----- -------'

INTERPRETAREA SOLUTIILOR MODELULUI DE OPTIMIZARE A DIMENSIUNII SI A STRUCTURII CULTURILOR EXPLOATATIEI AGRICOLE.

Solutia primala ofera cunoasterea dimensinii fiecarei culturi (ha) ce poate fi cultivata pentru a obtine profitul maxim de pe cele ha pe care le are exploatatia .

In cazul de mai jos pentru cele 200 ha se poate cultiva grau ( 12,05 ha) si pb consum (187,95 ha) si se obtine un profit de 322 072 lei, rezultat din 12,05x5238 + 187,95x1377

Restrictiile care conditioneaza aceste culturi sunt L6 ZNMAN7 (220 zn) si L30 STOT (200 ha), care sunt consumate in intregime din multitudinea de restrictii.

Acestor resrictii le sunt atasate costurile duale sau costurile de oportunitate. Este interesant de remarcat ca valoarea functiei obiectiv de 322 072 lei se poate obtine si din produsul

220 ZN x 211,40 lei/zn + 200 HAx1377,88 lei/zn

Dupa rezolvarea primului model se pot pune urmatoarele probleme :

- cum sunt utilizate resursele de care distunem pentru diferite dimensiuni ale exploatatie,

- care sunt modificarile de structura a culturilor pentru aceeasi suprafata a exploatatiei agricole , daca modificam valoarea resurselor

Prima problema este exemplificata in tabel in care s-au pastrat resursele la acelasi nivel si s-a parametrizat suprafata respectiv: 200ha, 250ha si 300ha.

Se constata ca pe masura ce suprafata a crescut exploatatia poate cultiva mai multe culturi iar resursele care sunt limitative cresc.

Pentru a parametriza suprafata culivata s-a procedat astfel:

- s-a rezolvat primul model si s-au notat rezultatele: solutia primala si solutia duala;

- s-a iesit din program si s-a modicat in fisierul (ex Opt1.txt) cu suprafetele de 200ha cu 250ha si cu 300ha. Modificarea se face direct in fisier : se acceseaza direct fisierul se face modificarea la linia respectiva dupa care se salveaza : Save sau Save As

ATENTIE !!! fisierul modificat va fi salvat cu o alta denumire ex. Fisierul Opt2.txt si respectiv Opt3.txt.

In acelasi fel se pot modifica si alte restrictii cu redenumirea fisierului parinte.

EXEMPLU : Parametrizarea suprafetei totale (STOT) pentru optimizarea dimensiunii exploatatiei agricole la acela nivel de resurse

BIBLIOGRAFIE

1. Draghici Manea si colab.Manualul de utilizare a. Produsului-Program AGR4, Ed Ceres 2006, Bucuresti