Analiza Economico Matematica a Problemelor Aflate In Dualitate
INTRODUCERE
Cercetarea operațională a apărut în timpul celui de-al doilea război mondial, când liderii militari au cerut inginerilor și matematicienilor să studieze probleme legate de securitatea convoaielor militare de nave împotriva submarinelor și a operațiilor de bombardare., însă a căpătat o dezvoltare exponențială în ultimii 20 de ani, împreună cu alte discipline ale organizării cum ar fi cibernetica, informatica și psihologia organizării.
În prezent, cercetarea operațională este numită adesea și Știința managementului , deoarece furnizează metode științifice și tehnice de luare a deciziilor optime în management, prin care se pot determina cele mai bune căi de operare ale unui sistem.
Lucrarea este structurată astfel încât să cuprindă aspectele necesare pentru a putea concluziona referitor la optimizarea afacerilor unei firme prin metode simplex.
Structura se regăsește astfel
Capitolul I Generalități asupra problemelor de programare liniară
Capitolul II Metode simplex pentru modele liniare
Capitolul III Analiza economico-matematică a problemelor aflate în dualitate
Capitolul IV Postoptimizare în programarea liniară
Capitolul V Studiu de caz la firma SC.Platin Systems.SRL
CAPITOLUL I : GENERALITĂȚI ASUPRA PROBLEMELOR DE PROGRAMARE LINIARĂ
Introducere
Mulțimea sistemelor economice concrete și multitudinea problemelor conducerii acestora au creat o diversitate de reprezentări economico- matematice,denumite modele.
Varietatea acestora este determinată,în principal, de structura "obiectului" analizat,de scopul cercetării precum și de informația disponibilă.
Modelele de programare matematică și mai ales subclasa acestora- modele de programare liniară- ocupă un loc deosebit de important, atât în teoria cât și în practica economică. Teoria economică a beneficiat aportul abordării interdisciplinare care a permis aprofundarea analizei eficienței maximale a sistemelor complexe, a permis descoperirea unor concepte noi ale optimului economic, a perfecționat metodele de cercetare și cunoaștere, iar practica economică s-a îmbogățit cu un instrument deosebit de util analizei economice și fundamentării deciziilor.
Structura modelului general de programare liniară se constituie în primul rând prin mulțimea de activități care compun sistemul economic analizat, mulțimea de resurse utilizate precum și relațiile tehnico- economice dintre acestea. Legătura dintre activități și resurse este determinate de tehnologia de fabricație corespunzătoare fiecărei activități și poate fi caracterizată numeric prin vectorul coloană de componente (. Elementele se numesc coeficienți tehnici sau coeficienți de consum specific și arată ce cantitate din resursa se consuma pentru producerea unei unități din produsul (serviciul) ( ca rezultat al activității ). Toate "tehnologiile" de fabricație definite de vactorii coloană se pot organiza într-o matrice A cu m linii și n coloane; fiecare linie se referă la o resursa și fiecare coloană se referă la o activitate (j=1,…,n).
Notând cu rezultatul activității într-o perioadă data și cu (i=1, … , m) cantitățile disponibile din resursele , se pot scrie mathematic următoarele restricții tehnico-economice:
…+ ≤ sau A
…………………………………
…+ ≤
Unde A= ; x=și b =
Fiecare inecuație/ restrictive încorporează două afirmații :
Cantitatea consumată dintr-o resursă nu poate depăși volumul disponibil ( propoziție de logică economică)
Consumul total din resursa pentru efectarea activității este proportional cu intensitatea acesteia, adică cu , deci = (ipoteză simplificatoare)
Sistemul de restricții (1) realizează legătura dintre resurse și activități prin intermediul celor m restricții liniare.
Modelul problemei de programare liniară conține restricții de tipul (1) precum și un criteriu de "performanță" care să permită evaluarea eficienței fiecărei activități. În funcție de scopul urmărit, putem alege drept criteriu de eficiență un indicator care măsoară efortul, unul care măsoară rezultatul sau un indicator exprimat ca raport între rezultat și efort( sau efort pe rezultat).
Este evident că eficiența maximă înseamnă minimizarea efortului și maximizarea rezultatului, iar conceptul de optim se definește, în acest caz, ca un program x care minimizează sau maximizează o funcție obiectiv și, în același timp, satisface toate restricțiile tehnico-economice.
Presupunând că fiecare componentă a vectorului linie c = ( măsoară eficiența unei unități din rezultatul activității , atunci se poate introduce funcția liniară:
f(x) =
care evoluează performanța oricărui program x.
Sintetizând, obținem următorul program de programare liniară:
optim(1)
Relațiile (1),(2) și (3) constituie împreună modelul general al unei probleme de programare liniară, având fiecare un rol specific:
Relația (1) , unde f(x)= este determinată de funcția obiectiv de eficiență a problemei, eveluează eficiența/performanța fiecărei variante de program x;
Relațiile (2) de tipul reprezintă restricții de tip resurse; iar restricțiile de tipul se referă la restricții tehnico-economice de tip calitativ(și ca urmare indicatorul este limita impusă "rețetei optime";
Relația (3) , numită condiția de nenegativitate a variabilelor, asigură obținerea unei soluții realizabile din punctul de vedere al logicii economice.
După cum s-a arătat la început, structura concretă a unei aplicații în economie este determinată ân primul rând de obiectivul urmărit.
Problema de programare liniară
Definitia 1. Dacă într-o problemă de programare matematică funcția obiectiv f și funcțiile din restricțiile 1,2, sunt funcții liniare atunci problema se numește problemă de programare liniară. O problemă de progrmare liniară este, deci, un caz particular al problemelor de programare matematică și, ținând cont de forma oricărei funcții liniare, rezultă că forma generală a oricărei probleme de programare liniară este :
unde (coeficienții funcției obiectiv), (coeficienții restricțiilor) și (termenii liberi) sunt constante reale.
Forma canonică și forma standard a unei probleme de programare liniară
Cu toate că problema de programare liniară este cea mai simplă dintre problemele de programare matematică, ea este incă destul de complicată, prin faptul că orice restricție poate avea trei forme diferite, iar obiectivul poate fi minimizarea sau maximizarea funcției f. Este puțin probabil că există un algoritm și simplu și aplicabil la toate cazurile. Din acest motiv, este mult mai simplu să găsim o anumită formă ( cât mai simplă) cu proprietatea că pentru orice problemă P, există o altă problemă P' de această formă, echivalentă cu problema inițială P ( spunem că două probleme sunt echivalente dacă există un izomorfism între mulțimile soluțiilor celor două probleme și un homeorfism între funcțiile lor obiectiv) și să dispunem de un algoritm care să rezolve problemele de această formă și de o regulă prin care să găsim soluția problemei inițiale P din soluția problemei P' , găsită cu acest algoritm.
În acest sens( dar și din cauza frecvenței apariției lor în practică) s-au evidențiat două forme ale problemelor de programare liniară, forma canonică și forma standard.
Definitia 2. Spunem că o problemă este la forma canonică dacă are una din următoarele două forme:
Acestă formă este cel mai des întâlnită în practică, și în plus, restrițiile economice sunt în general inegalități și foarte rar egalități. De asemenea, această formă este invariantă la anumite transformări și asigură existența soluției( orice problemă la această formă, care are termenii liberi și coeficienții restricțiilor pozitivi, are soluție).
Definitia 3. Spunem că o problemă este la forma standard dacă are forma:
Această formă, deși nenaturală din punct de vedere economic, este cea care se pretează cel mai bine la rezolvarea cu metodele algebrei clasice.
Propoziție . Pentru orice problemă de programare liniarăP există o problemă la forma canonică PFC și o problemă la forma standard PFS echivalente cu P.
Demonstrație. Într-adevăr:
Orice problemă de maxim poate fi transformată în una de minim și reciproc, folosind relația :
maxf(x)= – minf(-x)
Orice restricție de tipul "≤" poate fi transformată într-o restricție de forma "≥" și reciproc folosind relația:
Orice restricție inegalitate poate fi transformată în egalitate, prin introducerea unei variabile suplimentare nenegative și folosind relațiile:
și
Toate variabilele introduse pentru transformarea inegalităților în egalități se numesc variabile de abatere sau variabile de compensare.
Orice restricție egalitate poate fi transformată în restricții inegalitate, folosind relația:
Orice variabilă cu restricție de semn negativă ( x ≤ 0) poate fi înlocuită cu restricție de semn pozitivă ( y ≥ 0 ), folosind relația:
Orice variabilă fără restricție de semn poate fi înlocuită cu doua variabile cu restricție de semn pozitivă, folosind relația:
X oarecare⇔
Se demonstrează fără un efort matematic deosebit că dacă se obține din P folosind doar transformările de mai sus( numite și transformări elementare) atunci P și sunt două probleme echivalente și între soluțiile lor optime există o bijecție.
Din cele de mai sus rezultă cum poate fi adusă orice problemă de programare liniară la forma standard( sau conică ) și cum se obține soluția problemei inițiale din soluția problemei la forma standard ( sau conică).
Exemplu : Problemei P de mai jos îi corespunde problema la forma standard PFS alăturată:
Problema PFS are o singură soluție optimă:
care dă un maxim al funcției g egal cu .
Acestei soluții îi corespunde singura soluție optimă pentru P:
care dă un minim al funcției f egal cu – .
Rezolvarea problemei de programare liniară
Analiza problemei
Fie o problemă P despre care presupunem ( fără a restrânge generalitatea) că a fost adusă la forma standard. De asemenea presupunem ( tot fără a restrânge generalitatea) că variabilele problemei au fost numerotate și denumite cu j=1,…,n (n= numărul de necunoscute), coeficienții variabilelor din funcția obiectiv f cu (= coeficientul variabilei ), că în ecuații variabilele apar ăn ordinea indicilor, ecuațiile fiind numerotate de la 1 la m ( m= numărul de ecuații) și că am notat cu termenul liber al ecuației și cu coeficientul variabilei j din ecuația i. În acest caz putem așeza variabilele problemei într-un vector cu n componente, coeficienții funcției obiectiv într-un vector cu n componente, termenii liberi într-un vector cu m componente, coeficienții variabilelor din ecuații într-o matrice cu m linii și n coloane și vom avea:
x = , c = , b = , A=
(vom nota cu transpușii acestor vectori și cu transpusa matricei A).
Alegerea așezării ca vectori coloană a fost făcută din rațiuni de ușurință a calculelor și a memorării acestora. După aceste notații, problema poate fi scrisă mult mai simplu:
(min) f= (min) f=
sau
Se știe că un sistem de forma are soluție doar dacă rang(A) = rang(, unde este matricea extinsă obținută adăugând matricei A vectorul b, în acest caz sistemul devenind echivalent cu sisemul obținut prin eliminarea restricțiilor care nu corespund minorului principal ( dacă sistemul nu are soluție atunci evident nici problema nu are soluții, caz care este total neinteresant).
Presupunem că au fost eliminate aceste restricții. Dacă rang A = n, atunci sistemul are o singură soluție care, dacă este admisibilă, este și soluția optimă căutată , altfel problema nu are soluție. Este evident că și acest caz este la fel de neinteresant ca primul.
Presupunem deci în continuare că:
rang(A) = m < n
Rezolvarea sistemului se poate face într-un mod simplu ( cel puțin theoretic) folosind algebra matriceală astfel :
(n= numărul de necunoscute), coeficienții variabilelor din funcția obiectiv f cu (= coeficientul variabilei ), că în ecuații variabilele apar ăn ordinea indicilor, ecuațiile fiind numerotate de la 1 la m ( m= numărul de ecuații) și că am notat cu termenul liber al ecuației și cu coeficientul variabilei j din ecuația i. În acest caz putem așeza variabilele problemei într-un vector cu n componente, coeficienții funcției obiectiv într-un vector cu n componente, termenii liberi într-un vector cu m componente, coeficienții variabilelor din ecuații într-o matrice cu m linii și n coloane și vom avea:
x = , c = , b = , A=
(vom nota cu transpușii acestor vectori și cu transpusa matricei A).
Alegerea așezării ca vectori coloană a fost făcută din rațiuni de ușurință a calculelor și a memorării acestora. După aceste notații, problema poate fi scrisă mult mai simplu:
(min) f= (min) f=
sau
Se știe că un sistem de forma are soluție doar dacă rang(A) = rang(, unde este matricea extinsă obținută adăugând matricei A vectorul b, în acest caz sistemul devenind echivalent cu sisemul obținut prin eliminarea restricțiilor care nu corespund minorului principal ( dacă sistemul nu are soluție atunci evident nici problema nu are soluții, caz care este total neinteresant).
Presupunem că au fost eliminate aceste restricții. Dacă rang A = n, atunci sistemul are o singură soluție care, dacă este admisibilă, este și soluția optimă căutată , altfel problema nu are soluție. Este evident că și acest caz este la fel de neinteresant ca primul.
Presupunem deci în continuare că:
rang(A) = m < n
Rezolvarea sistemului se poate face într-un mod simplu ( cel puțin theoretic) folosind algebra matriceală astfel :
Împărțim coloanele matricei A în două submatrici: minorul principal ( notat cu B, care este matrice pătratică de dimensiune m și va fi numit bază a sistemului) și restul coloanelor( notat cu S, care este o matrice cu m linii și n-m coloane);
Împărțim variabilele problemei în doi vectori : vectorul variabilelor principale ( corespunzătoare coloanelor bazei) și vectorul variabilelor secundare( notat cu ). Făcând eventual o renumerotare, pentru ușurința expunerii și fiind evident că nu se restrânge generalitatea problemei, presupunem că variabilele principale sunt chiar primele m ( această presupunere va fi făcută de câte ori va fi posibil, fără a mai specifica acest lucru).
Aducem succesiv sistemul la forma de mai jos:
= b⇔ B
Soluția sistemului va fi submulțimea lui :
Oricare alegere a lui dă o soluție. Dintre toate alegerile posibile este remarcabilă ( prin simplitatea ei) soluția =0, care duce la soluția particulară:
n-m zerouri
numită soluția de bază asociată bazei B. Deci este la care se adaugă n-m zerouri. Cu toate acestea, vor fi ambele numite soluție de bază, rezultând din context de care este vorba.
Observație: Este evident că fiecărui minor principal al sistemului(minor de dimensiune m= bază) îi corespunde o unică soluție de bază. O soluție de bază care are toate componentele nenule strict pozitive se va numi soluție de bază admisibilă , iar o soluție optimă care este de bază se va numi soluție optimă de bază. Se observă că o soluție de bază are cel mult m componente diferite de 0. Din cauza importanței lor în rezolvarea problemei, vom evidenția soluțiile de bază care au mai puțin decât m componente nenule, numite soluții nedegenerate.
este izomorfă cu , adică are tot atâtea elemente câte puncte sunt într-un spațiu cu n – m dimensiuni. " Alegându-le " din acestea doar pe cele cu toate elementele pozitive, găsim mulțimea în care vom "căuta" vectorul (vectorii) care dă (dau) exemplul lui f.
Rezolvarea problemei poate duce la următoarele rezultate:
R1. Sistemul A nu are soluții sau nu are soluții admisibile. În acest caz problema nu are soluție.
R2. Imaginea funcției obiectiv pe mulțimea soluțiilor admisibile este nemărginită ( la într-o problemă de maxim sau la – într-o problem de minim). În acest caz spunem că problema are optim infinit.
R3. Imaginea funcției obiectiv pe mulțimea soluțiilor admisibile este mărginită. În acest caz problema are cel puțin o soluție și spunem că problema are optim finit.
Greutatea găsirii soluției problemei constă în intensitatea numărului de soluții posibile ale sistemului și în respectarea condiției de nenegativitate a celor printer care căutăm extremul dorit al funcției f. este natural ca primele încercări în rezolvare să caute în primul rând o limitare cât mai puternică a locului în care căutăm. Pe baza unor reprezentări geometrice ale problemei au fost descoperite următoarele proprietăți ale problemei, care poartă denumirea de teoreme fundamentale ale programării liniare:
Teorema 1: Dacă problema de programare liniară are soluții admisibile atunci are și soluții de bază admisibile.
Teorema 2: Dacă problema de programare liniară are soluții optime atunci are și soluții optime de bază.
Teorema 3: Mulțimea soluțiilor admisibile ( optime ) este închisă și convexă. Dacă este și mărginită atunci punctele extremale ale acesteia sunt chiar soluțiile admisibile (optime ) de bază ale problemei.
Cele două teoreme realizează efectiv trecerea către o problem rezolvabilă pe calculator. Într-adevăr , deoarece o bază este un minor de ordinul m al matricii A și unei baze îi corespunde o unică soluție de bază rezultă că sunt cel mult soluții de bază. Adică un număr finit. În acest moment s-ar părea că nu avem decât să lăsăm calculatorul să calculeze toate soluțiile de bază și valorile funcției obiectiv în cele admisibile găsind-o prin comparare pe cea care dă minimul sau maximul funcției printer acestea. Totuși, această variantă se dovedește nepractică la o analiză mai atentă, ținând cont de următoarele observații:
Faptul că numărul soluțiilor de bază este finit ne asigură doar că problema se va termina cândva, ceea ce , din punct de vedere economic, este evident nemulțumitor. Noi dorim ca problema să fie rezolvată în timp util, adică repede. Rezolvând problema ca mai sus vom avea pentru o problemă cu 50 variabile și 20 restricții, de calculat , listat și comparat soluții de bază, adică în jur de . Presupunând că suntem dotați cu un super calculator care ar termina un milliard de baze pe secundă, rezolvarea ar dura 3000 ani. De altfel, o problem ca cea de sus este foarte mică în comparație cu problemele " serioase" ce au peste 1000 de variabile și 100 de restricții. În plus, un calculator ca cel de sus nu există incă, deci în niciun caz nu e disponibil întreprinderilor obișnuite.
Cu algoritmul de mai sus vom găsi cea mai bună soluție dintre soluțiile admisibile de bază, fără însă să știm dacă problema admite, de fapt, optim ( ar putea să aibă optim infinit)
Nu vom ști dacă un minor de m*m este bază decât după ce-i vom calcula determinantul și nu vom ști dacă soluția de bază corespunzătoare este admisibilă decât după ce o vom calcula.
Soluția optimă, odată găsită, nu va fi recunoscută ca atare decât după ce vom calcula toate celelalte soluții de bază, chiar dacă ea a apărut chiar la începutul calculelor.
În concluzie, pentru a fi eficient, un algoritm ar trebui să aibă următoarele proprietăți :
Să dispună de un criteriu de recunoaștere a faptului că problema mu are soluții admisibile
Să dispună de un criteriu de recunoaștere a faptului că problema are optim infinit
Să dispună de un criteriu de recunoaștere dacă o soluție este optimă sau nu
Să treacă de la o soluție de bază admisibilă la una cel puțin la fel de bună ( o soluție x este mai bună decât o soluție y dacă f (x) > f (y) într-o problem de maxim și f (x) < f (y) într-o problemă de minim
Să treacă de la o soluție la cea mai bună dintre soluțiile cel puțin la fel de bune posibile ca succesoare
Să nu revină la o soluție deja analizată.
Să efectueze un număr de iterații comparabil polinomial cu dimensiunea problemei
Să nu introducă erori de rotunjire ( sau nu prea mari )
Să fie cât mai simplu de implementat.
Condițiile de mai sus reprezintă de fapt un algoritm ideal. La începuturile cercetării operaționale era suficient , de fapt, și un algoritm care să îndeplinească măcar condițiile b) , c) , d) , e) și h). Acest algoritm a fost dat de G.B Dantzig , în 1947, care la numit algoritmul simplex. El rămâne și în zilele noastre cel mai eficient algoritm în ceea ce privește viteza de lucru, simplitatea și implementarea pe calculator, pentru problemele care apar efectiv în practica economică. Totuși el nu îndeplinea condițiile a) , f) și g).
Condiția a) este relative ușor de îndeplinit și ea este acoperită prin introducerea unei faze inițiale suplimentare la algoritmul simplex, rezultând algoritmul simplex în două faze.
Condiția f) a fost pusă în momentul în care s-a observat că, în condițiile existenței soluțiilor degenerate, se poate ajunge în situația când, de la o soluție dată, nu se poate ajunge decât la una la fel de bună și tot așa, astfel încât, dacă nu se iau măsuri de evitare, se poate ajunge la o soluție care a mai fost, fenomen numit ciclare. Astfel de exemple a fost efectiv găsite, unul fiind exemplul lui Beale prezentat mai jos:
(max) f = – 20 + – 6
Se observă imediat baza admisibilă de la care, aplicând algoritmul sub forma clasică, se vor obține succesiv bazele admisibile , , , , , … . Cititorul poate verifica ușor că toate aceste baze au ca soluții de bază soluția (0,0,1,0,0,0,0) și valoarea funcției 0, dar nu îndeplinesc condiția de optim. Pe de altă parte se vede că și deci algoritmul va repeat la infinit această succesiune de baze, neatingând niciodată valoarea maximă , corespunzătoare soluției ( , 0 , 0 , 1 , 0 , 1, 0 ).
Această situație este îngrijorătoare nu atât din considerente practice immediate ( încă nu a fost găsită o problem din practică la care să apară acest fenomen, toate exemplele existente fiind artificial construite, ca și cel de mai sus) cât din faptul că un algoritm implementat pe calculator s-ar putea să fie pus în fața unei astfel de problemă, situație în care n-am putea rezolva problema nici pe calculator, nici manual , ea fiind prea mare. Situația a fost depășită prin diferite tehnici suplimentare adăugate celei de trecere la o soluție cel puțin la fel de bună ( insuficientă, cum s-a văzut), cea mai cunoscută fiind cea care folosește ordonarea lexicografică a soluțiilor.
Referitor la condiția g) , a durat mult timp până s-a demonstrate că algoritmul, sub această formă, nu este în timp polynomial, un exemplu fiind clasa de problem de mai jos, găsită de Klee și Minty în 1972, în care algoritmul trebuie să analizeze baze ( n= numărul de necunoscute) până la găsirea celei optime.
(max) f =
Pentru o astfel de problemă, la 100 de variabile, algoritmul va avea iterații, și chiar la o viteză de un milliard iterații pe secundă ( mult peste puterea unui calculator actual) va termina în ani.
Nu se știe încă dacă există sau nu o altă modalitate de trecere de la o bază la alta, folosind tabelele simplex, prin care algoritmul să devină în timp polinomial. Au fost însă găsiți algoritmi care nu folosesc tabelele simplex, primul fiind algoritmul de punct interior al lui KamaKar, despre care s-a demonstrate că lucrează în timp polynomial.
În ceea ce privește erorile de rotunjire, inevitabile când se fac calculele pe un calculator, algoritmul se comport într-adevăr foarte rău, orice eroare propagându-se imediat la tot tabelul cu efecte foarte mari . Acest lucru poate fi însă depășit aplicând o variant a algoritmului, numită varianta revizuită a algoritmului simplex.
Toate punctele slabe ale algoritmului, amintite mai sus, nu au înmormântat însă algoritmul simplex, deoarece folosirea acestuia adduce informații mult mai ample decât găsirea soluției propriu-zise, este mult mai maleabil în cazul modificărilor ulterioare ale datelor problemei, se pretează mult mai bine la interpretări economice, este ușor de scris un program de calculator asociat, este implementat pe foarte multe calculatoare și în plus, așa cum aminteam mai sus, încă nu a apărut o problem practică în fața căruia să clacheze. Noii algoritmi rămân doar ca alternative teoretice sau pentru cazurile în care algoritmul simplex este lent, dar ei nu-l pot înlocui complet.
Capitolul II : METODE SIMPLEX PENTRU MODELE LINIARE
2.1. Algoritmul simplex primal. Descriere.
Pentru rezolvarea modelelor liniare, au apărut, începând cu 1948, mai multe metode , dintre care amintim : metoda simplex cu variantele sale, metoda Kantorovici, metoda relaxării. Dintre toate metodele apărute în literatura de specialitate, cea mai răspândită este cea elaborată de G.B.Dantzig.
Algoritmul propus de Dantzig permite determinarea unei soluții admisibile de bază optime, dacă există prin examinarea parțiala dirijată a mulțimii soluțiilor admisibile de bază , mai précis, vor fi testate o parte din soluțiile admisibile de bază. În mod empiric, pe baza unor experiențe de calcul effectuate timp de 10 ani, s-a stability că soluția optimă, dacă există, se obține după cel mult 3m iterații (m=rangA) .Fiecare dintre aceste noi iterații constă în găsirea unei noi soluții
Admisibile de bază căreia îi corespunde o valoare mai bună a funcției obiectiv decât în situația precedent.
2.2. Teoreme fundamentale ale algoritmului simplex
Se consideră o problemă de programare liniară sub forma standard:
(P)
Fie o SAB corespunzătoare bazei =,în raport cu care se va explicita sistemul de restricții =(·b-·,unde = sunt valorile variabilelor bazice , deci, componentele negative ale vectorului .
Teorema 1 : Criteriul de îmbunătățire a unei soluții admisibile de bază
Fie problema de programare liniară (P), o bază în și soluția admisibilă de bază corespunzătoare ei. Dacă pentru un indice j J – , – < 0 și există cel puțin un indice s a.i > 0 , atunci poate fi înlocuită printr-o soluție admisibilă de bază cel puțin la fel de bună, în sensul f ≤ f (). Soluția admisibilă corespunde bazei dedusă din prin înlocuirea lui , k , cu , l . Indicii l și k sunt dați de relațiile :
II.1.1 – {- <0 } și
II.1.2 = {׀>0}.
Teorema 2: Testul de optimalitate
O soluție admisibilă de bază , X , a problemei (P) este optimă dacă și numai dacă
II.1.3 – ≥ 0 ,∀ j J.
Observația 1: Dacă există a. î. să fie identificate relațiile II.1.3 –numite criteriu de optimalitate- atunci [max]f(x)+∞ .
Observația2: Relația:
II.1.4 – ≤0 ,∀ j J este criteriu de optimalitate dacă se cere minimizarea funcției liniare f .
Observația 3: – = 0 ,∀ s , unde reprezintă mulțimea indicilor variabilelor bazice.
Corolar: Soluția optimă este unic determinată dacă
II.1.5 – >0 ,∀ j J – ( adică , oricare j pentru care este nebazic).
Teorema 3: Testul de optim infinit
Dacă pentru o soluție admisibilă de bază a problemei considerate există un indice lJ – a.i. – ≤0 și ≤ 0 , ∀ s , atunci (P) are optim infinit.
Observația 4: Pentru problemele cu funcția obiectiv [min]f , criteriul de recunoaștere a optimului nemărginit (teorema 3) este :
J – a.i. – > 0 și ≤ 0 ,∀ s .
Din enunțul teoremei rezultă că o problemă de programare liniară are optim infinit dacă există un vector nebazic cu toate componentele nenegative (= ( , ≤ 0 ,∀ s ), pentru care – nu satisfice criteriul de optimalitate al tipului său de optim.
Concluziile celor 3 teoreme sunt sistematizate în tabelul următor :
2.3. Generarea SAB prin metode particulare
În continuare, vom analiza cazul în care matricea A, după aducerea la forma standard, nu conține o bază unitate din spațiul . În general, în matricea A din modelele matematice corespunzăoare unor procese reale nu apare complet , pentru a genera o soluție admisibilă de bază a problemei date, dacă acest lucru este posibil, se poate alege una din variantele :
Scrierea explicită a sistemului de restricții în raport cu o bază din .
Metoda celor două faze.
Metoda bazei artificiale.
2.3.1. Metoda bazei artificiale
Se consideră un model matematic sub forma sa standard:
II.2.1 și rang =m<n, b≥0, J a.i. ≥ 0.
Presupunem că matricea A nu conține o bază unitate de ordinul m. Prin această metodă se urmărește generarea unei SAB pentru (II.2.1), dacă acest lucru este posibil, folosind numai algoritmul simplex primal.
Metoda bazei artificiale presupune parcurgerea următoarelor etape:
Etapa1: se extinde problema prin introducerea a m variabile artificiale care vor fi penalizate în funcția obiectiv:
II.2.2,
unde a, este matricea unitate de ordin m, = este vectorul coloană cu componentele , i ,variabile artificiale. Din scrierea , rezultă soluția de start: .
Etapa2: Se aplică algoritmul simplex problemei extinse. Presupunem că după k iterații, k , k<∞, avem – ≥ 0, j= , deci, problema extinsă adimite soluție optimă finită.
La baza discuției ce va urma, relative la existent sau nonexistent soluției optime a problemei inițiale,stau următoarele teoreme :
După oprirea algoritmului, se discută natura problemei inițiale după care urmează :
Cazul 1: Soluția optimă a problemei extinse nu conține nici o variabilă artificială cu valoare strict pozitivă ⇒soluția optimă a problemei II.2.1 se obține considerând numai valorile optimale ale variabilelor ,…, .
Cazul2:În soluția optimă există cel puțin o variabilă artificială cu valoare strict pozitivă; în acest caz, problema initială nu are soluție.
2.3.2. Metoda celor două faze
Se mențin ipotezele de lucru de la metoda bazei artificiale. Ca și la metoda precedentă, se numește generarea unei SAB pentru II.2.1 ori de câte ori calculul direct al unei astfel de soluții este dificil datorită dimensiunilor problemei (m și/sau n foarte mari). Aceste două metode pun la dispoziția utilizatorului procedee generale de generare a soluțiilor admisibile de bază, sau informația că problema nu are soluții ceea ce ar putea indica o modelare greșită a procesului economic.
Metoda celor două faze constă în parcurgerea următoarelor etape:
Faza 1 : Scopul acestei etape este de a obține , dacă este posibil, o SAB de start II.2.1, aplicând algoritmul simplex-primal problemei auxiliare:
II.2.3 AX+B·=( ,…, , unde este variabila artificială adăugată numai parții stângi a restricției i,i, iar B este matricea unitate de ordinul m = rangA.
II.2.4 X, ,
II.2.5 [min]W= .
La această fază obiectivul va fi maximizarea sumei valorilor artificiale din restricții, indiferent de tipul de optim al problemei considerate. Din II.2.3 rezultă că variabilele artificiale bazice sunt în SAB de start: = . Se aplică algoritmul simplex primal problemei auxiliare. Admitem că aceasta are soluție optimă finită, deci există o SAB care verifică criteriul de optimalitate : – ≤ 0, ∀j= .
Atunci ,
La baza metodei stau următoarele afirmații:
Tema 1 : Orice soluție admisibilă de bază a problemei II.2.1 este SAB a problemei auxiliare cu =0. Existența unei astfel de soluții atrage în mod necesar [min]W=0.
Tema 2: Orice soluție admisibilă de bază a problemei extinse pentru care W = 0 este o SAB a problemei inițiale.
2.4. Degenerare și ciclare în problema de programare liniară
Definiție: Se numește SAB degenerate pentru II.2.1 dacă numărul valorilor variabilelor bazice strict pozitive este cel mult (m-1) unde m = rangA
Soluțiile admisibile de bază degenerate se pot obține în două moduri :
În sistemul de restricții scris sub forma explicită + R=b, b are cel puțin o componentă egală cu zero și toate celelalte strict pozitive ⇒ valorile variabilelor bazice =b, strict pozitive, sunt în număr de cel mult (m-1).
Există cazul în care, în spațiul bunurilor , vectorul b nu formează un sistem de vectori liniar independent cu orice combinație de (m-1) vectori din A. Din punct de vedere geometric, acest lucru înseamnă că b trece printr-un vârf al poliedrului conex al restricțiilor AX= b. Să presupunem că ( … ) este o bază în , dar ( … b ) nu este un sistem de m vectori liniar independenți. Vectorul b poate fi scris în mod unic în baza ( … ):
II.3.1 + + … + + 0=b.
Din II.3.1 rezultă că are componentele , deci este SAB degenerată.
Să presupunem că unei probleme de programare liniară degenerată i se caută soluția optimă aplicând metoda simplex, și , la o anumită iterație, raportul nu este unic determinat. Metoda perturbațiilor (A.Chanes) și metoda lexicografică (B.B. Dantzing și P. Wolfw) sunt două metode ce nu înlătură degenerarea, ci creează posibilitatea continuării algoritmului prin înlăturarea arbitrariului în determinarea vectorului ce va fi eliminat din bază, vector situate pe una din liniile rapoartelor minime de valori egale.
2.4.1. Metoda lexicografică
Presupunem că la iterația p , vectorul , l J , trebuie să intre în bază, toate componentele sale , s I, sunt strict pozitive și
= = = = .
Se pune întrebarea : care din cei doi vectori va fi eliminat, sau ?
T.II.3.1
Min
Decizia va fi luată după parcurgerea următorilor pași :
Pasul 1: Se împart elementele liniei k , începând cu , la eventualul element pivot . Se împart elementele liniei r la eventualul element pivot , și se așează sub celelalte rapoarte în ordinea dată de coloanele tabelului simplex:
, , , … , , , …, ;
, , , … , , , …, ;
Pasul 2 :
Operația 1 : Se compară rapoartele din a doua coloană: DA Se trece la operația 2
= ?
NU
STOP. Pivotul iterației va fi numitorul raportului
minim. Va fi eliminat din bază vectorul situat
în linia pivotului.
Operația 2: k := k+1 ⇒Operatia 1.
După cel mult n operații se poate stabili vectorul care trebuie eliminat.
2.4.2. Metoda perturbațiilor
Pasul 1 : Fie (0,1) arbitrar de mic. Se trece la o problemă perturbată, de forma :
[max] f =
II.3.2 + = b+
≥0, j=
Dacă soluția admisibilă de bază corespunde bazei formată din primii m vectori, atunci restricțiile din II.3.2 se mai pot scrie:
II.3.3 +) + =b(),
unde b()=b+.
Pasul 2 : Prin modificarea de la pasul 1 s-a obținut o problemă nedegenerată. Presupunem că este vectorul ce va face parte din noua bază ( se acceptă ipotezele expuse la metoda lexicografică). Vom aplica acum criteriul de eliminare din bază:
=
2.4.3. Ciclarea
Dacă valoarea funcției scop nu se modifică pe parcursul câtorva iterații succesive, este posibil să apară fenomenul de ciclare, adică să se revină la una dintre soluțiile admisibile de bază prin care s-a trecut deja.
Deși criteriul de intrare în bază ne dă posibilitatea de a alege între două variabile, am ales întotdeauna prima variabilă din partea de sus a tabelelor. Dacă însă vom alege la un moment dat alte variabile care ies din bază decât cele alese anterior putem ajunge la soluția optimă, evitând astfel ciclarea.
2.5. Algoritmul simplex revizuit
Acest algoritm este o formă “revizuită” a algoritmului simplex primal, care se recomandă a fi folosită atunci când rezolvarea modelului matematic se face cu ajutorul calculatorului. Ideea de bază este de a reține datele inițiale,apoi, folosind matricea sistemului de restricții se va construi o matrice inversă, se vor calcula , = b și – , în funcție de care se ia decizia de a opri algoritmul sau de a-l continua trecând la o soluție admisibilă de bază mai bună.
Considerăm problema de programare liniară la forma standard:
Min f(x)= cX
II.4.1 {AX=b ,
X≥0
Unde A (R); rangA=m ≤ n; b; c, X .
Pentru aplicarea algoritmului simplex revizuit, se construiește “completata” problemei II.4.1:
min(x) =
II.4.2 .
X≥0,
Etape:
Pas 0: Se determină B baza primal admisibilă și se calculează : , , , .
Pas 1 : Se calculează – = – , ∀ j R. Dacă – ≤ 0,∀ j [1,…,n}-B=R ⇒ soluție optimă. Dacă nu, se trece la Pasul 2.
Pas 2 :Alegem k astfel încât =>0. Se calculează =. Dacă ≤0, problema are optim nemărginit (-∞).Dacă nu, se trece la Pasul 3.
Pas 3 :Alegem r după regula =. Se înlocuiește coloana cu coloana , și se formează noua bază admisibilă , . Se revine la Pasul 1.
2.6. Algoritmul simplex dual
Când s-a aplicat modelul simplex primal s-a apelat, pe tot parcursul algoritmului, la soluții admisibile de bază (SAB) și regulile sale au fost stabilite impunându-se condiția de nenegativitate a variabilelor din model.
Cu ajutorul teoriei dualității se poate formula un nou algoritm de rezolvare a problemelor de programare liniară, pornind de la o soluție de bază care nu respectă, total sau parțial, condiția de nenegativitate, și anume algoritmul simplex dual. Conceptul de bază cu care se operează este cel de soluție dual realizabilă (SDR)
Definiție: Se numește soluție dual realizabilă a unei probleme de programare liniară, o soluție de bază care are cel puțin o componentă strict negativă și care verifică criteriul de optimalitate al modelului liniar.
Algoritmul simplex-dual este o procedură de explorare orientată a soluțiilor dual-admisibile până la obținerea soluției optime sau până la evidențiera faptului că problema nu admite soluții.În general, stabilirea unei soluții dual-admisibile este greu de realizat, motiv pentru care acest algoritm se aplică atunci când o soluție dual realizabilă se poate stabili cu un volum mic de calcule,când restricțiile sunt cu precădere de forma “≥” , sau când aceasta se obține prin modificarea unor caracteristici numerice din model. Acest algoritm poate fi privit ca dualul algoritmului simplex-primal,deoarece reflectă aplicarea acestuia la problema duală.
Schema de desfășurare a algoritmului simplex-dual, este următoarea:
DA
NU
Capitolul III : ANALIZA ECONOMICO – MATEMATICĂ A PROBLEMELOR AFLATE ÎN DUALITATE
Problema de bază a cărei soluție se găsește prin metode de programare liniară este numită “problemă primală”. Fiecărei problem e primale îi corespunde o “problemă duală”, care aduce unității de decizie informațiile adiționale.Natura problemei duale depinde de problema primală. Dacă problema primală este o problemă de maximizare,atunci duala ei va fi o problemă de minimizare. Analog,dacă primala este de minimizare, duala va fi de maximizare.
Analiza problemei primale
Pentru a realiza analiza economică a operațiilor algoritmului simplex primal se va considera un model clasic de stabilire a unui program optim de fabricație.
Problema primală :
III.1.1 [max]f = 20+10+12
III.1.2
III.1.3 ≥0, ∀ j
Problema duală (semnificațiile economice ale relațiilor dualei depind de procesul modelat prin primală și tipul restricțiilor primalei și vor fi depuse în paragraful 2 ):
III.1.4 [min] g = 680+800
III.1.5
III.1.6
Reluăm tabelul simplex-primal și îl analizăm din punctul de vedere propus:
T.III.1.1
Criteriul de intrare în bază :
⇒ produsul este cel mai rentabil deoarece va provoca cea mai mare creștere a funcției economice venit total, și anume :
III.1.7 =0+
Egalitatea apare ca un caz particular când soluția de start este formată numai din variabile de abatere.
Criteriul de ieșire din bază este invariabil la tipul optim.
Conform consumurilor specific din cele trei resurse disponibile în cantități egale cu 680, 800 respectiv 900, numărul maxim de produse care pot fi fabricate este 180; resursa este prima resursă care se consumă prin introducerea lui în programul de fabricație.
T.III.1.2
Informațiile conținute în ultima iterație :
Problema primală admite soluție optimă finită (≥ 0 nedegenerată () și unic determinată ( nu există vector nebazic cu ). Soluția optimă este
= . Astfel, venitul maxim de 4150 u.m este obținut dacă structura programului de fabricație este . Prin programul optim, resursele sunt consumate integral. Din resursa rămâne un stoc de 555 unități. Calculăm cunsumul din :
și concluzionăm că cele 555 unități pot fi folosite pentru 4 x 125 noi programe, rămânând un stoc de 55 unități. Este posibil ca această imobilizare de fonduri fixe să mărească cheltuielile totale de fabricație. Produsul este nerentabil în condițiile actuale.
Venitul total este maxim și egal cu :
.
Dacă problema primală admite soluție optimă finită, atunci și duala sa admite solutie optimă finită și :
elemente ce apar în linia în dreptul vectorilor ce au format prima bază. Mai mult,
[min]g = [max]f = 4150.
Forma standard a problemei duale este . Înlocuim aici citit anterior :
Așadar , este soluția optimă pentru forma standard a dualei problemei analizate.
Din iterația a doua, construim în același mod vectorul . Înlocuindu-l în forma standard a dualei obținem :
Cum ≥ 0, și soluția nu este admisibilă pentru duală. Se știe că dacă cX=Ub și soluția admisibilă de bază X nu este optimă, atunci U nu este soluție admisibilă pentru duală, ceea ce tocmai am verificat.
Efectuând aceleași calcule cu elementele din tabelul optimal, găsim că deoarece , în acest caz, este optimă.
Analiza economico-matematică a problemelor primală-duală
Problema primal este calea originală prin care se enunță matematic problema propusă a fi rezolvată.
Se consideră m resurse, , , …, (materii prime, material, forță de muncă, capacitate de producție, etc.) care participă la realizarea a n produse , , …, . Notăm cu venitul obținut în urma valorificării unei unități , iar cu nivelul activității , ∀ j .
Obiectivul problemei este :
III.2.1[max]f==
Restricțiile sunt date de disponibilul limitat de resurse:
≤ , ∀ i , adică,
III.2.2 ≤
∀ i .
Desigur, condiția de nenegativitate este de asemenea impusă :
≥ 0, ∀ j .
Problema duală este unic determinată pentru o problemă primală dată. Programul său liniar utilizează aceleași date de intrare, dar cu alte semnificații algebrice.
Obiectivul :
III.2.3 [min] g = =
Restricțiile sunt date de:
≥ , ∀ j , ceea ce înseamnă
III.2.4 ≥ , j= .
Problema duală se rezolvă în condițiile:
≥ 0, ∀ i .
Dacă probelma primală admite soluție optimă finită, atunci și duala are optim finit și
III.2.5 [max] f ( ) = [min]g ( ).
Această relație are următoarea interpretare:
=
Unități monetare Număr produse
Venit total optim măsurat în
unități monetare
Din cauza egalității, variabila trebuie să aibă semnificația unui preț “atașat” resursei ; acesta va fi numit “preț umbră” sau “ preț intern” sau “preț de eficiență”.
Explicitând relația III.1.5 , găsim
III.2.6 + … + = [max] f = [min] g = + … + + …+ , și considerând
III.2.7 := + 1 ,
Obținem :
III.2.8 + …+ (+ 1) +…+ = = [max] f + .
Din ultimele două relații, rezultă semnificația lui : acesta arată cu cât crește valoarea optimală a programului primal dacă disponibilul din resursa crește cu o unitate. Această valoare poate fi privită ca o evaluare obiectiv determintată a unei unități din resursa . Prețurile umbră sunt costuri impuse sau de oportunitate ale factorilor de producție ( resurse, în cazul considerat). Ei sunt indicatori cruciali pentru analiza programului optim și pentru modificarea lui în cazul redefinirii valorilor unor disponibile. Scrise ca un șir descrescător, valorile optimale ale variabilei duale indică ordinea de referință în aprovizionarea suplimentară din cele m resurse; se poate astfel estima importanța relativă a celor m resurse în realizarea scopului declarat.
Resursele care sunt consumate prin programul optim au prețuri umbră nenule,iar cele care nu sunt consumate integral au prețuri umbră nule. Valorile , i , depind de cantitățile de resurse disponibile , de valoarea consumurilor specifice , j , și de tipul restricțiilor primalei. În cazul > 0 ,i , ea va reprezenta aportul valoric ( contribuția bănească) la venitul total al unei unități din resursa și , în același timp, reflectă deficitul relativ al resursei în raport cu eficiența sistemului, măsurată prin venit.
Din punct de vedere matematic, ,…, sunt multiplicatorii lui Lagrange; ei dau informații despre rata de creștere sau descreștere a lui f(X) la o creștere de o unitate a unui disponibil.
Din III.2.6 rezultă că un program este optim dacă și numai dacă există un sistem de prețuri umbră ( ,…, ) astfel încât valoarea resurselor exprimată prin ele egalează valoarea maximă a funcției obiectiv f . Prețurile umbră, ale căror valori sunt stabilite prin rezolvarea problemei primale, au o mare importanță practică, deoarece indică cu cât va crește venitul firmei dacă se decide mărirea producției prin suplimentarea unor resurse.
Să revenim la III.2.4 înlocuind prin semnificația găsită , obținem:
≥
pentru j fixat. Această restrictive exprimă un paradox,
≥
care va fi înlăturat prin utilizarea teoremei ecarturilor complementare.
Teorema ecarturilor complementare
Se consideră un cuplu de probleme duale simetrice
Condiția necesară și suficientă pentru ca un cuplu de soluții admisibile de bază și să fie optime este ca ele să satisfacă simultan relațiile :
III.2.9 (A- b) = 0 ,
III.2.10 (c – A) = 0.
Din III.2.10 se va analiza produsul
III.2.11 = 0 ,i .
Cazul 1 ⇒ = 0⇒ Dacă prin programul optim resursa este consumată integral, atunci devine eficientă mărirea acesteia cu cel puțin o unitate ( + 1). Cu cât valoarea lui este mai mare cu atât crește această eficiență. Pe baza acestei interpretări putem trage concluzia că crește oricât dorim dacă crește.
Pentru a exemplifica teoria care va fi dezvoltată, considerăm două modele duale
Despre care deținem următoarele informații:
Admit soluții optime finite = , respectiv = ;
[max]f = [min]g = 6600.
Primala a fost rezolvată prin algoritmul simplex primal. Din tabelul final am extras baza optimă :
() ,= și – = (0 0 5 3 5 0).
Pentru i=1 relația III.2.1 devine . Soluțiile optime fiind cunoscute, se constată rapid că și = 3 > 0. Din interpretarea prețului umbră u, rezultă că, dacă disponibilul de 700 ar crește cu o unitate, [max]f de 6600 crește cu 3 unități monetare.
Vom parametriza liniar acest disponibil în funcție de :
b= și . Scriem b( în baza (
( = ≥ 0 ⇔
Pentru aceste valori ale lui , () este optimală. În aceste condiții,
f() = 18 .
Pentru = 400 ⇒ =⇒ = = .
Rezultatul obținut este foarte interesant deoarece s-a obținut un program de fabricație cu consumul integral al tuturor resurselor, dacă crește cu 400 de unități, iar se mențin. Valoarea maximă a funcției obiectiv va fi, în acest caz, [max]f =8200 u.m.
Cazul 2 0⇒ = 0. Dacă prin programul optimal resursa i nu este complet utilizată, prețul său umbră este nul. Pentru i=3, din III.2.11 , rezultă :
( , unde reprezintă consumul din resursa , iar 800 este disponibilul din aceeași resursă.
Din relația matriceală III.2.10, considerăm produsul:
III.2.12 (, care va fi analizat în 2 circumstanțe.
Cazul 3 > 0 ⇒= , cu interpretarea: este rentabilă prelucrarea produsului deoarece valoarea consumurilor unitare din cele m resurse calculate pe baza prețurilor ( umbră) interne nu depășește venitul așteptat.
Pentru j=1, se observă că
[18-( )]=0,
=1 =3 =1
Cu = 250 > 0. Coeficienții variabilelor dualei sunt elementele vectorului și reprezintă consumurile specifice din cele trei resurse pentru un produs .
Ca urmare, avem următoarea interpretare :
–
Cazul 4 ⇒ = 0 ⇒ fabricarea lui nu este rentabilă deoarece evaluarea resurselor consumate pentru o unitate prin prețurile umbră depășește venitul așteptat de la o unitate . Pentru cazul numeric menționat mai sus și i = 3 , avem :
[15-( 4)]=[15-20] = 0 ⇒ = 0 ⇒este nerentabil în condițiile date.
În finalul paragrafului revenim la problemele duale date de relațiile III.1.1 –III.1.3 , respective III.1.4 – III.1.6, pentru a le analiza prin prisma teoremei ecarturilor complementare.
Din teoremele fundamentale ale dualității rezultă că duala unei problem ce admite soluție optimă finită are, de asemenea, soluție optimă finită și [max]f = [min] g. Soluția optimă a dualei poate fi stabilită aplicând metoda simplex sau o variantă a acesteia.
Rezolvarea dată în T.III.1.1 – T.III.1.2 ne facilitează aflarea soluției optime a dualei. Deoarece baza initială a fost , soluția optimă a dualei este dată de valorile din ultimul tabel simplex. Astfel, iar valoarea minimă a funcției obiectiv din duală este :
[min]g = 680 0+800 +900 = 4150= [max]f .
Cele două soluții optime, trebuie să verifice relațiile:
conform teoremei ecarturilor complementare.
Să analizăm o parte dintre aceste relații:
Valoarea optimă a variabilei este strict pozitivă , atunci a doua relație este adevărată ⇔. Dacă prețul intern ce caracterizează resursa a doua( fondul de timp disponibil al secției 2) este strict pozitiv, atunci această resursă este complet utilizată în programul optim de producție. Valoarea de dă creșterea lui [max]f = 4150 dacă fondul de timp al secției 2 crește cu o unitate. Dacă problemele duale nu sunt simetrice, și în practică acest lucru este frecvent, poate fi strict negativ, ceea ce înseamnă că matricea disponibilului resursei I este nerentabilă, deoarece duce la micșorarea lui [max]f .
În prima relație avem , de unde rezultă că trebuie să fie 0, și, într-adevăr, . În acest caz, interpretarea economică este următoarea: dacă programul optim nu presupune epuizarea fondului de timp disponibil al secției 1, atunci prețul de eficiență al resursei este nul. Eficiența măririi acestui fond este nulă, în realitate ar provoca pierderi (resursă nestocabilă).
În penultima relație,
⇒ = 0.
Produsul de tip 2 nu intră în programul optim de fabricație, deoarece valoarea timpilor de prelucrare la cele trei secții a unui produs de tipul 2, calculate pe baza prețurilor interne optime, depășește profitul său unitar.
Din antepenultima și ultima relație rezultă că este rentabilă prelucrarea a 125 produse de tipul 1 și a produse de tipul 2, pentru ca valorile timpilor de prelucrare obținute prin evaluarea acestora cu ajutorul prețurilor interne nu depășesc profiturile.
Un program de producție este optim sub aspectul profitului dacă și numai dacă există un sistem de prețuri interne(prețuri umbră) care să egaleze profiturile cu cheltuielile, [max]f = [min]g. Prețurile interne apar ca expresie a valorii resurselor luate în considerație în modelul matematic. Valorile lor optime sunt nule pentru resursele excedentare și nenule numai pentru resursele folosite integral în programul de optim.
Capitolul IV : POSTOPTIMIZARE ÎN PROGRAMAREA LINIARĂ
Aspectul economic al postoptimizării
Soluția optimă finită a modelului unui process economic poate reprezenta un program optim de fabricație, o repartiție optimă, o rație optimă într-o anumită perioadă și în condiții exprimate matematic în modelul elaborat. Ea oferă informații pentru luarea unei decizii optime în anumite condiții, deci pentru decident este foarte important să știe dacă o soluție optimă este stabilă și dacă o mică modificare a unor date numerice implică modificări mari ale soluției optime. În analiza unor procese economice reale prezintă interes în cunoașterea modului în care se schimbă soluția optimă a unui model liniar odată cu variația unuia sau a mai multor elemente ale programului.
În practica economică, se produc frecvent astfel de modificări, prin schimbarea anumitor aspecte ale procesului tehnologic și/ sau a prețurilor materiilor prime sau semifabricatelor și/sau scăderea vânzărilor, etc. În alte cazuri, variabilele modelului trebuie supuse unor restricții noi, de exemplu încadrarea într-un anumit disponibil al unei resurse care de la un moment dat devine deficitară și care nu a fost luată in considerație inițial. Nu este exclus nici cazul în care se pune problema schimbării structurii programului prin introducerea de noi produse ce par rentabile.
Apar astfel modele liniare cu coeficienți variabili ale căror soluții optime, dacă există, trebuie determinate pentru deciziile ce vor fi luate să fie optimale.
Problematica expusă mai sus poartă denumirea de oprimizare și este caracterizată prin faptul că variația coeficienților este directă. Pentru abordarea unitară a cazurilor în care modificarea procesului economic produce schimbarea unor date numerice se va lucra cu un model liniar care admite soluție optimă finită, de forma :
.
Se pune întrebarea cum influențează aceste schimbări rezolvarea și soluția optimă a problemei inițiale? Se poate răspunde în două moduri :
R1 Noul model poate fi rezolvat independent de cunoașterea soluției optime pentru problema inițială și a elementelor din tabelul simplex care o conține.
R2 Se scrie modelul de aceeași structură cu cel inițial în care cel puțin o dată numerică este modificată sau modelul este extins prin introducerea de noi restricții sau variabile. Se vor utiliza o parte din elementele tabelului simplex care conține soluția optimă a problemei inițiale pentru a rezolva problema modificată. Acest procedeu poartă denumirea de postoptimizare sau reoptimizare și este preferat primului procedeu deoarece volumul de calcul este redus simțitor.
Orice tip de postoptimizare presupune parcurgerea a două etape :
Etapa 1. Rezolvarea problemei ce modelează procesul economic într-o anumită perioadă.
Etapa 2.Se studiază influența modificării unor elemente ale modelului sau extinderii lui asupra optimalității soluției găsite la Etapa 1.Acest lucru se realizează prin refacerea unor calcule utilizând anumite elemente din tabelul simplex optimal.
Postoptimizare prin modificarea coeficienților funcției scop
În practică, profiturile, prețurile de vânzare, costurile unitare de transport, rețele de schimb ale monedei naționale în alte unități monetare,prețurile de achiziție, de fabricație și alte asemenea elemente sunt elemente supuse unor modificări repetate și uneori de amploare. Coeficienții variabilelor din funcția scop pot avea aceste semnificații.
Formulare matematică
Se consideră modelul liniar
IV.2.1 ,
care admite soluția optimă finită
IV.2.2 ,
și se va specifica algoritmul folosit pentru aflarea acesteia. În cazurile ce vor fi analizate în prezenta lucrare se va utiliza algoritmul simplex-primal cu tabelul optimal de forma:
T.IV.2.1
Se cere să se stabilească soluția optimă, dacă există, a problemei de programare liniară:
IV.2.3 [max]=
IV.2.4 AX=b,
IV.2.5 X≥0,
Unde diferă de c prin cel puțin o componentă, = c + deci vectorul are cel puțin o componentă diferită de 0.
Dacă analizăm cu atenție elementele din tabelul optimal(T.IV.2.1) vom constata că ele pot fi clasificate în două categorii:
Elemente în a căror formule de calcul nu intervin coeficienții funcției scop :
.
Elemente care sunt afectate de modificarea elementelor vectorului c.
T.IV.2.2
Ce valori vor avea acestea după modificarea lui c?Soluția optimă se menține? Și dacă nu, cum se va afla noua soluție dacă există? Vom afla răspunsurile la aceste întrebări după parcurgerea următorilor pași:
Pasul 1:
Se identifică baza initială și se citește .
Se scrie .
Se construiește ca fiind acea parte a vectorului care are componentele respective egale cu coeficienții variabilelor bazice.
Pasul 2 :
Se citește baza optimală B pentru modelul inițial( vezi tabelul IV.2.1).
Dacă este nebazic, j, (se calculează
=.
Se verifică dacă sunt împlinite condițiile de optimalitate după modificarea lui c:
Pentru [max]f⇒ ?
Dacă NU⇒Pasul 3
Dacă DA⇒STOP. Soluția optimă a problemei inițiale este optimă și pentru problema postoptimizată și
[max]== (c + )=(
Pasul 3 :
Din teorema de optimalitate formulată pentru problema de maxim, rezultă că există cel puțin o diferență strict negativă cu , deci B nu mai este optimal pentru problema postoptimizată. Pe de altă parte,valorile variabilelor bazice, nedepinzând de c, rămân pozitive, ceea ce ne permite să tragem concluzia că soluția va fi soluție admisibilă de bază pentru programul inițial. Se va verifica existența soluției optime a problemei cu c modificat, aplicând algoritmul simplex-primal cu soluția de start
Postoptimizarea în cazul modificării vectorului b
Formulare matematică
Se consideră un program liniar
care admite soluție optimă finită ,cu tabelul optimal T.IV.2.1.
Presupunem că vectorul b își modifică cel puțin o componentă ,, cu 0, prin creșterea capacității de producție sau modificarea disponibilului dintr-o resursă care nu a fost primită în timp util sau din alte cauze similar. Examinând cu atenție T.IV.2.1, se va observa că modificarea lui b afectează valorile variabilelor bazice( și valoarea funcției scop ; celelalte elemente rămân neschimbate și subliniem faptul că se menține criteriul de optimalitate. Noul tabel va avea modificată doar coloana soluției, după cum se poate observa în tabelul următor:
T.IV.3.1
Ne propunem să studiem natura următoarei probleme modificate:
În acest caz procedeul de postoptimizare este următorul:
Pasul 1:
Se identifică baza inițială și se citește .
Pasul 2:
Se calculează noile valori ale variabilelor bazice; din punct de vedere algebric, se scrie în baza B :
IV.3.1=(=
Valoarea funcției obiectiv se modifică astfel:
IV.3.2 +.
Pentru este verificat criteriul de optimalitate, deci pentru a-i asigura optimalitatea mai trebuie să impunem condiția de non-negativitate a componentelor sale :≥ 0 ?
Dacă DA, atunci STOP. Noile valori optime ale variabilelor bazice sunt respectiv egale cu , iar valoarea funcției scop este dată de relația IV.3.2.
Dacă NU, se trece la Pasul 3.
Pasul 3 :
Rezultă că s astfel încât < 0.Cum criteriul de optimalitate se menține, rezultă că s-a generat o soluție dual realizabilă pentru problema postoptimalizată. Se aplică algoritmul simplex-dual cu soluția de start :
Postoptimizarea în cazul modificării vectorului
Formulare matematică
Într-o problemă de programare liniară se reprezintă modelul unui process economic,componentele vectorului pot reprezenta consumuri specifice din m resurse utilizate pentru a obține un produs j , timpi de prelucrare, sau altele. În general, aceste elemente, numite coeficienți tehnologici, sunt supuse unei variații lente în timp.Totuți, atunci când intervin modificări ale tehnologiei de fabricație, o parte a coeficienților tehnologici se modifică.Să presupunem că numai un vector își schimbă componentele. Considerăm problema de programare liniară :
X=b;
X≥0;
[max]f =
care admite soluție optimă finită. Prin modificarea vectorului ea devine:
X=b;
X≥0;
[max]f =
Cunoscând tabelul simplex optimal al problemei inițiale, vom studia influența modificării lui și , j asupra optimalității soluției sale.
Cu vectorii se pot forma două mulțimi disjuncte:
Mulțimea vectorilor nebazici,
Mulțimea vectorilor bazici,
Și prin urmare deosebim două cazuri :
Cazul 1. Vectorul este nebazic relativ la baza optimă B.
T.IV.4.1
Natura programului postoptimizat va fi stabilită printr-un procedeu descris în cele ce urmează.
Pasul 1
Se citește .
Se scrie vectorul în baza B : = , j \ .
Se calculeaăa
Pasul 2
Pentru [max]f ,
Dacă DA, atunci STOP⇒este soluție optimă finită și pentru problema modificată.
Dacă NU, se trece la Pasul 3.
Pasul 3
≤ 0, (
Dacă DA, atunci STOP, problema modificată admite optim infinit, [max]f = .
Dacă NU, se trece la Pasul 4
Pasul 4
nu este soluție optimă pentru problema postoptimizată. Deoarece , nu se mai verifică criteriul de optimalitate, ca urmare este o soluție admisibilă de bază pentru problema postoptimizată. Pentru a-i stabili natura se aplică algoritmul simplex-primal cu soluția de start . Practic, se copiază tabelulIV.4.1, mai puțin coloana lui , care va fi completată cu rezultatele obținute la Pasul 1. Noua baza va conține vectorul .
T.IV.4.2
Cazul 2. Vectorul aparține bazei optime B
Este știut faptul că modificarea componentelor unui vector bazic provoacă modificarea scrierii vectorilor nebazici în respectiva bază:
.
Cum se poate afla
Spre deosebire de celelalte tipuri de potoptimizări, aici avem trei variante de acțiune pentru a stabili natura programului modificat.
V1. Se operează modificarea în model și se rezolvă ca un program liniar independent față de cel inițial.
.
V2. Se scrie matricea A din forma standard A=(
Se citește baza optimă B=(
Se construiește matricea pătratică de ordinul m cu coloanele , citite-excepție făcând care va fi înlocuit cu – din matricea A. Dacă există inversa sa, atunci aceasta va fi .
Se reconstituie iterația cu baza B și , apoi se ia decizia de STOP sau continuarea rezolvării problemei postoptimizate.
Aceste variante implică un volum mare de calcule, chiar pentru m și n relativ mici, motiv pentru care se va opta pentru varianta următoare.
V3. Se aplică procedeul de optimizare care constă în parcurgerea a cel mult cinci pași.
Pasul 1
În tabelul simplex optimal al problemei rezolvate, se citesc:
;
Baza optimă B și se notează cu k locul vectorului modificat în această bază.
Pasul 2
Se află componentele vectorului modificat în baza B : = .
Componenta k este diferită de 0?
Dacă NU, atunci STOP⇒ nu există soluție optimă.
Dacă DA, atunci se trece la Pasul 3.
Pasul 3
Se construiește vectorul .
Pasul 4
Fie matricea unitate de ordinul m . Prin vom înțelege matricea ce diferă de numai prin coloana k și anume:
⇒.
Se calculează : =
Pasul 5
Se constituie iterația problemei postoptimizate, în care apare baza optimă a problemei inițiale:
T.IV.4.3
Analizând diferențele , și valorile variabilelor bazice date de
, deosebim patru cazuri sistematizate în următorul tabel pentru problema de maxim:
T.IV.4.4
Observație : Pentru problema de minim, în T.IV.4.4 se înlocuiește ≥ 0 cu ≤ 0 , și [max] cu [min]. Celelalte condiții și comentarii rămân valabile.
Postoptimizarea în cazul adăugării unor restricții
Formulare matematică
Se consideră un program liniar care admite soluție optimă finită. Fie aceasta în forma standard
IV.5.1
Să presupunem că se cunoaște soluția optimă a acestui program obținută prin aplicarea algoritmului simplex primal. Tabelul simplex primal ne oferă forma explicită a problemei IV.5.1 , corespunzătoare bazei optime B, și anume:
unde variabilele bazice sunt exprimate în funcție de variabilele secundare .
Să presupunem , de asemenea, că într-o etapă ulterioară obținerii soluției optime a problemei IV.5.1 apare necesitatea introducerii unor restricții suplimentare în modelul analizat, ceea ce presupune modificarea matricei A din IV.5.1 prin adăugarea unor linii și ca urmare A devine .
Ne propunem să studiem natura problemei postoptimizate
,
unde , sunt elemente cunoscute și obținute prin bordarea lui A și, respective b, cu k linii.
Schema de optimizare este următoarea :
Pasul 1
Cele k restricții suplimentare se transformă în egalități prin adăugarea a k variabile de ecart , i= ; acestea devin , i= și deci problema postoptimizată poate fi scrisă acum :
[max]f =
.
Pasul 2
Se elimină variabilele bazice din cele k restricții noi:
i=
Pasul 3
Dacă i= , atunci s-a obținut soluția optimă a problemei postoptimizate. În caz contrar, soluția obținută nu e admisibilă, dar verifică criteriul de optim, deci se continuă cu algoritmul simplex dual până la determinarea soluției sale optime.
Postoptimizare în cazul adăugării unor noi variabile
Formula matematică
Se consideră un program liniar care admite soluție optimă finită
IV.6.1 ,
unde sunt vectorii coloană ai matricei coeficienților tehnologici A.
Observație: Relația a doua din programul liniar IV.6.1 poate fi scrisă în forma echivalentă :
Suntem interesați în rezolvarea problemei postoptimizate
IV.6.2 ,
unde coeficienții ai funcției scop și vectorii din spațiul bunurilor sunt presupuși cunoscuți. Aceasta revine la rezolvarea problemei de programare liniară în care matricea coeficienților tehnologici se obține din A prin adăugarea celor k vectori coloană .
Rezolvarea problemei extinse se bazează pe următoarea observație din cadrul teoriei generale : dacă este soluție optimă a problemei IV.6.1 corespunzătoare bazei optime B, atunci vectorul ( este soluție admisibilă pentru problema IV.6.2.
Schema de rezolvare presupune parcurgerea următorilor pași:
Pasul 1
Se calculează
Pasul 2
Formulăm întrebarea : adică sau cu notația de la pasul 1,
Dacă DA, atunci ( este soluție optimă pentru IV.6.2.
Dacă NU, atunci fie
Alegem astfel încât și vectorul intră în bază dacă are cel puțin o componentă strict pozitivă; în caz contrar, modelul extins are optim infinit.
În continuare se aplică algoritmul simplex primal până la obținerea soluției optime(dacă există) a problemei postoptimizate.
Capitolul V : STUDIU DE CAZ LA FIRMA SC.Platin Systems.SRL
5.1. Prezentarea firmei SC.Platin Systems.SRL
Sc.Platin Systems.SRL a fost înființată în anul 1994 și este organizată ca societate cu răspundere limitată .
Această firmă este situată în Ploieșsti, și are ca domeniu de activitate comercializarea de calculatoare, componente, monitoare, periferice si de asemenea, oferă și asistență software și servicii de proiectare, instalare și întreținere rețele de calculatoare, server-e ( de e-mail, FTP, web) , precum și servicii de reparații calculatoare.
5.1.1. Date de contact
Cod Unic de Înregistrare RO 5072946
Număr de înmatriculare la Registrul Comerțului J29/21/94
Adresă : Ploiești, Str Gheorghe Doja, Nr 29, Bl 34D2, Sc B, Ap 1
Telefon 0244-591-818
0244-518-141
Email [anonimizat]
Program de lucru luni – vineri 09-18, cu excepția sărbătorilor legale.
5.1.2. Informații financiare
5.2. Identificarea și rezolvarea unei probleme de programare liniară la nivelul firmei
Firma SC. Platin Systems. SRL asamblează și comercializează 3 tipuri de computere P1 – HP , P2 – Lenovo și P3 – Platin Systems. Profiturile obținute de firmă, timpii de execuție și capacitățile de lucru disponibile sunt înregistrate în tabelul următor (1.1)
T 1.1
Din experiența comercială a firmei rezultă că în planul de afaceri HP – urile ocupă până la din vânzările firmei.
Se cere să se determine planul zilnic optim de producție și comercializare al firmei, astfel încât să se obțină profit maxim.
Rezolvare
Modelul problemei de programare liniară în formă canonică este
Forma standard a modlului va fi următoarea
unde sunt variabile ecart( de compensare).
Se construiesc matricele
Matricea termenilor liberi =
Matricea asociata restricțiilor A =
T 1.2
Deoarece avem valori negative printre valorile lui (-35, -25, -15 ) Soluția nu este optimă.
T 1.3
Deoarece avem valori negative printre valorile lui (-55, -45) Soluția nu este optimă.
T 1.4
Deoarece nu mai avem valori negative printre valorile lui Soluția este optimă.
= 35
= 35
= 0
= 20
= 0
= 0
5.2.1. Analiza sensibilității coeficienților funcției – obiectiv
Variația coeficientului lui ( Vom nota acest coeficient cu )
F = + 25 + 15
Introducem datele de intrare referitoare la această funcție în tabelul (1.4) și recalculăm funcțiile aferente. Obținem tabelul (1.5)
T 1.5
Întrucât în acest tabel a rezultat ≥ 0 pentru toate valorile, înseamnă că soluția optimă a rămas neschimbată. Datele de pe linia se pot scrie astfel
Pentru ca aceste soluții să fie adevărate, este necesar să se verifice inegalitățile
De aici rezultă mărimile coeficientului și anume
Domeniul de variație al coeficientului este
25 ≤ ≤ ∞
Aplicarea algoritmului determinării variației coeficientului variabilei
T 1.6
Deoarece în tabel există decât valori pozitive, se poate calcula numai limita inferioară
LI = max 30-95 30-55 30-5 = -65 -25 25 = 25
Așa cum am văzut și mai sus, limita superioară la acest coeficient nu există, și fiind o problema de maximizare, se poate adopta LS = ∞. Așadar, se confirmă că domeniul optimalității coeficientului lui este 25 ≤ ≤ ∞
Variația coeficientului lui ( vom nota acest coeficient cu )
F = + + 15
Introducem datele de intrare referitoare la această funcție în tabelul (1.4) și recalculăm funcțiile aferente. Obținem tabelul (1.7)
T 1.7
Întrucât în acest tabel a rezultat ≥ 0 pentru toate valorile, înseamnă că soluția optimă a rămas neschimbată. Datele de pe linia se pot scrie astfel
≥ 0 ≥ 0 ≥ 0
Pentru ca aceste soluții să fie adevărate, este necesar să se verifice inegalitățile
≥ 0
De aici rezultă mărimile coeficientului și anume
Domeniul de variație al coeficientului este
6 ≤ ≤ 30
Aplicarea algoritmului determinării variației coeficientului variabilei
T 1.8
LS = min 25-(-5) = 30
LI = max 25-19 25-55 = 6 -30 = 6
Așadar, se confirmă că domeniul optimalității coeficientului lui este 6 ≤ ≤ 30
Variația coeficientului lui ( vom nota acest coeficient cu )
F = + +
Introducem datele de intrare referitoare la această funcție în tabelul (1.4) și recalculăm funcțiile aferente. Obținem tabelul (1.9)
T 1.9
Întrucât în acest tabel a rezultat ≥ 0 pentru toate valorile, înseamnă că soluția optimă a rămas neschimbată. Datele de pe linia se pot scrie astfel
–
Pentru ca aceste soluții să fie adevărate, este necesar să se verifice inegalitățile
Domeniul de variație al coeficientului este
Algoritmul prin care se confirmă domeniul optimalității nu se poate aplica pentru că nu face parte din baza finală.
Limitele variației coeficienților funcției – obiectiv
5.2.2. Analiza sensibilității termenilor liberi ai restricților
O schimbare favorabilă de capacitate la una dintre restricții trebuie să verifice relația de principiu
Relația de mai sus se adaptează ușor la construcția vectorială ( pe linii și pe coloane ) a tabelului simplex final din rezolvarea primalei. Pentru o restricție oarecare i (i = 1, 2, …, m) această relație se dezvoltă astfel
Pentru aplicația de mai sus, relația se poate concretiza, pentru restricția 1 și variabila ecart în felul următor
De aici se poate calcula ușor , astfel încât soluția problemei să rămână fezabilă, adică pozitivă. Vom avea
20 + 1 ≥ 0
35 +
35 +
Rezolvarea acestor inegalități în raport cu conduce la
Restricția 2, variabila ecart
Vom avea
20-1
35 +
35 +
Rezultatul conduce la
Pentru a obține o soluție fezabilă toate cele 3 inegalități de mai sus trebuie satisfăcute. Întrucât au rezultat trei valori diferite ( două negative și una pozitivă ), este necesar saă fie satisfăcute cele mai restrictive dintre acestea, și anume cea pozitivă că este singură, și una dintre cele negative.
Ca atare, trebuie să satisfacă următoarele condiție
-140 ≤ ≤ 20
În consecință, știind că timpul disponibil pentru montajul computerelor este de 160 ore – om/ zi, rezultă că soluția problemei rămâne fezabilă dacă se cuprinde între limitele
( 160 – 140 ) ≤ ≤ ( 160 + 20 )
Cea de-a treia restricție nu consumă resurse, ci este o restricție de raporturi între elementele mixului productiv și are termenul liber egal cu 0.
5.2.3. Proiectarea unei aplicații C++ pentru implementarea algoritmului simplex
Se realizează implementarea algoritmului simplex in C++ și se rezolvă aplicația identifictă la nivelul firmei SC. Platin Systems.SRL cu ajutorul programului creat.
Date de intrare
R: Maximizare = Y, Minimizare = N
NV: Numărul de variabile ale funcției obiectiv ( Pentru a maximiza sau minimiza)
NC: Numărul de restricții
TS: Tabel simplex de dimensiuni NC+1 x NV+1
R1: =1 pentru maximizare, = -1 pentru minimizare
R2: Variabile auxiliare pentru intrări
NOPTIMAL Boolean dacă este fals, continuă iterații
XMAX: Păstrează coeficientul cel mai mare al funcției obiectiv
RAP Păstrează cel mai mic raport > 0
P1,P2: Linia, Coloana indexată de pivot
XERR: Boolean dacă este adevărat, nu există soluție.
Date de ieșire
V: Vectorul ce conține componentele soluției optime
Rezultat final:
Codul sursă folosit pentru rezolvarea aplicației identificată la nivelul firmei SC.Platin Systems.SRL se află în Anexa 1.
Concluzii :
În concluzie, așa cum se deduce și din studiul de caz prezentat, programarea liniară este extrem de eficientă în optimizarea activității economice la nivelul firmei studiate, aplicarea algoritmului simplex conducând în final la creșterea profitului.
ANEXE
Anexa 1
/*
METODA SIMPLEX
–––––
Lista variabilelor principale:
R: MAXIMIZARE = Y, MINIMIZARE = N
NV: NUMARUL DE VARIABILE ALE FUNCTIEI OBIECTIV( PENTRU A MAXIMIZA SAU MINIMIZA)
NC: NUMARUL DE RESTRICTII
TS: TABEL SIMPLEX DE DIMENSIUNI NC+1 X NV+1
R1: =1 PENTRU MAXIMIZARE, =-1 PENTRU MINIMIZARE
R2: VARIABILE AUXILIARE PENTRU INTRARI
NOPTIMAL BOOLEAN DACA ESTE FALS, CONTINUA ITERATII
XMAX: PASTREAZA COEFICIENTUL CEL MAI MARE AL FUNCTIEI OBIECTIV
RAP PASTREAZA CEL MAI MIC RAPORT > 0
V: VARIABILE AUXILIARE
P1,P2: LINIA, COLOANA INDEXATA DE PIVOT
XERR: BOOLEAN DACA ESTE ADEVARAT, NU EXISTA SOLUTIE.
––––––––––––––––––
DESCRIEREA PROBLEMEI:
FIRMA SC.PLATIN SYSTMS.SRL PRODUCE 3 TIPURI DE CALCULATOARE CU DIVERSE PROFITURI : 30€, 25€ SI 15€.
Fiecare tip trebuie sa indeplineasca urmatoarele conditii:
1) Timpii de executie pentru montaj sa nu depaseasca 160 ore/calculator.
2) Timpii de executie pentru testare sa nu depaseasca 140 ore/calculator.
3) HP-urile ocupa pana la 1/2 din vanzarile firmei.
Se cere sa se determine planul zilnic optim de productie si comercializare al firmei, astfel incat sa se obtina profit maxim.
––––––––––––––––––
Rulare :
(Maximizeaza 30 X1 + 25 X2 + 15 X3 cu conditiile:
3 X1 + X2 + 3 X3 <= 160
2 X1 + 2 X2 + 3 X3 <= 140
X1 – X2 – X3 <= 0 )
PROGRAMARE LINIARA:
MAXIMIZARE ? Y
NUMARUL DE VARIABILE ALE FUNCTIEI OBIECTIV ? 6
NUMARUL DE RESTRICTII ? 3
COEFICIENTII DE INTRARE AI FUNCTIEI OBIECTIV:
#1 ? 30
#2 ? 25
#3 ? 15
Termenul liber ? 0
RESTRICTIA #1:
#1 ? 3
#2 ? 1
#3 ? 3
Termenul liber ? 160
RESTRICTIA #2:
#1 ? 2
#2 ? 2
#3 ? 3
Termenul liber ? 140
RESTRICTIA #3:
#1 ? 1
#2 ? -1
#3 ? -1
Termenul liber ? 0
REZULTAT:
VARIABILA #1: 35
VARIABILA #2: 35
VARIABILA #3: 0
VARIABILA #4: 20
VARIABILA #5: 0
VARIABILA #6: 0
FUNCTIA OBIECTIV: 1925
(Producand si comercializand 35, 35 si 0 calculatoare de tipul HP, LENOVO si PLATIN SYSTEMS, firma poate face lunar un profit de 1925€
*/
#include <stdio.h>
#include <math.h>
#define CMAX 10 // Numarul maxim de variabile din functia obiectiv
#define VMAX 10 // Numarul maxim de restrictii
int NC, NV, NOPTIMAL,P1,P2,XERR;
double TS[CMAX][VMAX];
void Data() {
double R1,R2;
char R;
int I,J;
printf("\n PROGRAMARE LINIARA \n\n");
printf(" MAXIMIZARE (Y/N) ? "); scanf("%c", &R);
printf("\n NUMARUL DE VARIABILE DIN FUNCTIA OBIECTIV ? "); scanf("%d", &NV);
printf("\n NUMARUL DE RESTRICTII ? "); scanf("%d", &NC);
if (R == 'Y' || R=='y')
R1 = 1.0;
else
R1 = -1.0;
printf("\n COEFICIENTI DE INTRARE AI FUNCTIEI OBIECTIV :\n");
for (J = 1; J<=NV; J++) {
printf(" #%d ? ", J); scanf("%lf", &R2);
TS[1][J+1] = R2 * R1;
}
printf(" Termenul liber ? "); scanf("%lf", &R2);
TS[1][1] = R2 * R1;
for (I = 1; I<=NC; I++) {
printf("\n RESTRICTIE #%d:\n", I);
for (J = 1; J<=NV; J++) {
printf(" #%d ? ", J); scanf("%lf", &R2);
TS[I + 1][J + 1] = -R2;
}
printf(" Termenul liber ? "); scanf("%lf", &TS[I+1][1]);
}
printf("\n\n REZULTAT:\n\n");
for(J=1; J<=NV; J++) TS[0][J+1] = J;
for(I=NV+1; I<=NV+NC; I++) TS[I-NV+1][0] = I;
}
void Pivot();
void Formula();
void Optimizare();
void Simplex() {
e10: Pivot();
Formula();
Optimizare();
if (NOPTIMAL == 1) goto e10;
}
void Pivot() {
double RAP,V,XMAX;
int I,J;
XMAX = 0.0;
for(J=2; J<=NV+1; J++) {
if (TS[1][J] > 0.0 && TS[1][J] > XMAX) {
XMAX = TS[1][J];
P2 = J;
}
}
RAP = 999999.0;
for (I=2; I<=NC+1; I++) {
if (TS[I][P2] >= 0.0) goto e10;
V = fabs(TS[I][1] / TS[I][P2]);
if (V < RAP) {
RAP = V;
P1 = I;
}
e10:;}
V = TS[0][P2]; TS[0][P2] = TS[P1][0]; TS[P1][0] = V;
}
void Formula() {;
//Etichete: e60,e70,e100,e110;
int I,J;
for (I=1; I<=NC+1; I++) {
if (I == P1) goto e70;
for (J=1; J<=NV+1; J++) {
if (J == P2) goto e60;
TS[I][J] -= TS[P1][J] * TS[I][P2] / TS[P1][P2];
e60:;}
e70:;}
TS[P1][P2] = 1.0 / TS[P1][P2];
for (J=1; J<=NV+1; J++) {
if (J == P2) goto e100;
TS[P1][J] *= fabs(TS[P1][P2]);
e100:;}
for (I=1; I<=NC+1; I++) {
if (I == P1) goto e110;
TS[I][P2] *= TS[P1][P2];
e110:;}
}
void Optimizare() {
int I,J;
for (I=2; I<=NC+1; I++)
if (TS[I][1] < 0.0) XERR = 1;
NOPTIMAL = 0;
if (XERR == 1) return;
for (J=2; J<=NV+1; J++)
if (TS[1][J] > 0.0) NOPTIMAL = 1;
}
void Rezultate() {
//Etichete: e30,e70,e100;
int I,J;
e30:for (I=1; I<=NV; I++)
for (J=2; J<=NC+1; J++) {
if (TS[J][0] != 1.0*I) goto e70;
printf(" VARIABILA #%d: %f\n", I, TS[J][1]);
e70: ;}
printf("\n FUNCTIA OBIECTIV: %f\n", TS[1][1]);
e100:printf("\n");
}
int main() {
Data();
Simplex();
Rezultate();
return 1;
}
Bibliografie
Boroș E. , Opriș D. Introducere în optimizarea liniară și aplicații, Editura Facla, Timișoara, 1979.
Ciobanu Gh. , Nica V. , Mustață F. , Mărăcine V. Cercetări operaționale cu aplicații în economie, Matrix Rom, București, 1996.
Ciucu G. , Craiu V. , Ștefănescu A. , Ștefănescu M. Statistică matematică și cercetări operaționale, volumul III, Editura didactică și pedagocică, București, 1978.
Iorga V. Programare în C, Editura Albastră, 2011
Kaufmann A. Metode și modele ale cercetării operaționale, volumul II, Editura tehnică, București, 1967.
Logofătu D. Bazele programării în C – Aplicații, Editura Polirom, 2006.
Lange O. Decizii optime, Editura Științifică, București, 1970.
Malița M. , Zidăroiu C. Matematica Organizării, Editura tehnică, București, 1975.
Mihoc Gh. , Nădejde I. Programare matematică, Editura Științifică, București, 1967
Mihoc Gh. , Ștefănescu A. Programare Matematică, Editura didactică și pedagogică, București, 1973
Nădejde I. , Bergthaller C. , Zidăroiu C. , Sburlan S. Probleme de cercetare operațională, Editura Academiei, București,1971.
Nica V. , Mustață F. , Ciobanu Gh., Mărăcine V. Cercetări operaționale, Matrix Rom, București, 1998
Pătrașcu A. , Zaharia M. , Tănăsescu A. Bazele Informaticii- Elemente de programare C/C++, Editura Universtitară, 2011.
Preda V. , Bad M. Culegere de probleme de cercetări operaționale, partea I, Tipologia Universității București, 1978.
Ștefănescu A. , Zidăroiu C. Cercetări operaționale, Editura didactică și pedagocică, București, 1981.
Țigănescu E. , Mustață F. , Nica V. , Marin D. Culegere de probleme pentru disciplina cercetări operaționale cu aplicații în economie, Tipografia ASE, București, 1988.
Zidăroiu C. Curs de cercetare operațională, Tipografia Universității București, 1978.
Zidăroiu C. Programare liniară, Editura tehnică, București, 1983
http://www.juridice.ro/156618/societate-cu-raspundere-limitata-vs-societate-pe-actiuni.html
Bibliografie :
Boroș E. , Opriș D. : Introducere în optimizarea liniară și aplicații, Editura Facla, Timișoara, 1979.
Ciobanu Gh. , Nica V. , Mustață F. , Mărăcine V. : Cercetări operaționale cu aplicații în economie, Matrix Rom, București, 1996.
Ciucu G. , Craiu V. , Ștefănescu A. , Ștefănescu M. : Statistică matematică și cercetări operaționale, volumul III, Editura didactică și pedagocică, București, 1978.
Iorga V. : Programare în C, Editura Albastră, 2011
Kaufmann A. : Metode și modele ale cercetării operaționale, volumul II, Editura tehnică, București, 1967.
Logofătu D. : Bazele programării în C – Aplicații, Editura Polirom, 2006.
Lange O. : Decizii optime, Editura Științifică, București, 1970.
Malița M. , Zidăroiu C. : Matematica Organizării, Editura tehnică, București, 1975.
Mihoc Gh. , Nădejde I. : Programare matematică, Editura Științifică, București, 1967
Mihoc Gh. , Ștefănescu A. : Programare Matematică, Editura didactică și pedagogică, București, 1973
Nădejde I. , Bergthaller C. , Zidăroiu C. , Sburlan S. : Probleme de cercetare operațională, Editura Academiei, București,1971.
Nica V. , Mustață F. , Ciobanu Gh., Mărăcine V. : Cercetări operaționale, Matrix Rom, București, 1998
Pătrașcu A. , Zaharia M. , Tănăsescu A. : Bazele Informaticii- Elemente de programare C/C++, Editura Universtitară, 2011.
Preda V. , Bad M. : Culegere de probleme de cercetări operaționale, partea I, Tipologia Universității București, 1978.
Ștefănescu A. , Zidăroiu C. : Cercetări operaționale, Editura didactică și pedagocică, București, 1981.
Țigănescu E. , Mustață F. , Nica V. , Marin D. : Culegere de probleme pentru disciplina cercetări operaționale cu aplicații în economie, Tipografia ASE, București, 1988.
Zidăroiu C. : Curs de cercetare operațională, Tipografia Universității București, 1978.
Zidăroiu C. : Programare liniară, Editura tehnică, București, 1983
http://www.juridice.ro/156618/societate-cu-raspundere-limitata-vs-societate-pe-actiuni.html
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Analiza Economico Matematica a Problemelor Aflate In Dualitate (ID: 135638)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.