REFERAT CERCETARI OPERATIONALE

53
Bazele cercetării operaţionale FACULTATEA DE ŞTIINŢE ECONOMICE DISCIPLINA CERCETĂRI OPERAŢIONALE COORDONATOR MASTERAND 2011 / 2012 1

description

Proiect detaliat cercetarea operationala ca stiinta

Transcript of REFERAT CERCETARI OPERATIONALE

PROGRAMARE LINIAR

Programarea liniar

Bazele cercetrii operaionale

FACULTATEA DE TIINE ECONOMICE

DISCIPLINA

CERCETRI OPERAIONALE

COORDONATOR

MASTERAND2011 / 2012

PROGRAMAREA LINIAR

Prezentare general

Mulimea sistemelor economice concrete i multitudinea problemelor conducerii acestora au creat o diversitate de reprezentri economico-matematice, denumite modele.

Varietatea acestora este determinat, n principal, de structura "obiectului" analizat, de scopul cercetrii precum i de informaia disponibil.

Modelele de programare matematic i mai ales subclasa acestora modelele de programare liniar ocup un loc deosebit de important, att n teoria ct i n practica economic. Teoria economic a beneficiat de aportul abordrii interdisciplinare care a permis aprofundarea analizei eficienei maximale a sistemelor complexe, a permis descoperirea unor concepte noi ale optimului economic, a perfecionat metodele de cercetare i cunoatere iar practica economic s-a mbogit cu un instrument deosebit de util analizei economice i fundamentrii deciziilor.

Structura modelului general de programare liniar se constituie n primul rnd prin mulimea de activiti {A1, A2, ... An} care compun sistemul economic analizat, mulimea de resurse utilizate {R1, R2, ... Rm} precum i prin relaiile tehnico-economice dintre acestea. Legtura dintre activiti i resurse este determinat de tehnologia de fabricaie corespunztoare fiecrei activiti Aj (j=1,...,n) i poate fi caracterizat numeric prin vectorul coloan a(j) de componente (a1j, a2j, ... amj). Elementele {aij, i = 1,...,m; j = 1,...,n} se numesc coeficieni tehnici sau coeficieni de consum specific i arat ce cantitate din resursa Ri se consum pentru producerea unei uniti din produsul (serviciul) Pj (ca rezultat al activitii Aj). Toate "tehnologiile" de fabricaie definite de vectorii coloan a(j) se pot organiza ntr-o matrice A cu m linii i n coloane; fiecare linie se refer la o resurs Ri (i = 1,...,m) i fiecare coloan se refer la o activitate Aj (j = 1,...,n).

Notnd cu xj (j = 1,...,n) rezultatul activitii Aj ntr-o perioad dat i cu bi (i = 1,...,m) cantitile disponibile din resursele Ri (i = 1,...,m), se pot scrie matematic urmtoarele restricii tehnico-economice:

(1) sau A(x ( b

unde A = ; x = i b =

Fiecare inecuaie/restricie ncorporeaz dou afirmaii:

a. cantitatea consumat dintr-o resurs nu poate depi volumul disponibil (propoziie de logic economic)

b. consumul total Rij din resursa Ri pentru efectuarea activitii Aj este proporional cu intensitatea acesteia, adic cu xj, deci Rij(() = aij ( xj (ipotez simplificatoare)

Sistemul de restricii (1) realizeaz legtura dintre resurse i activiti prin intermediul celor m restricii liniare.

Modelul problemei de programare liniar conine restricii de tipul (1) precum i un criteriu de "performan" care s permit evaluarea eficienei fiecrei activiti. n funcie de scopul urmrit, putem alege drept criteriu de eficien un indicator care msoar efortul, unul care msoar rezultatul sau un indicator exprimat ca raport ntre rezultat i efort (sau efort pe rezultat).

Este evident c eficiena maxim nseamn minimizarea efortului i maximizarea rezultatului, iar conceptul de optim se definete, n acest caz, ca un program x( Rn care minimizeaz sau maximizeaz o funcie obiectiv i, n acelai timp, satisface toate restriciile tehnico-economice.

Presupunnd c fiecare component a vectorului linie c = (c1, c2, ..., cn) msoar eficiena unei uniti din rezultatul activitii Aj, atunci se poate introduce funcia liniar:

f(x) = c1(x1 + c2(x2 + ... + cn(xncare evalueaz performana oricrui program x.

Sintetiznd, obinem urmtorul program de programare liniar:

Relaiile (1), (2) i (3) constituie mpreun modelul general al unei probleme de programare liniar, avnd fiecare un rol specific:

1. relaia (1), unde f(x) = este denumit funcia obiectiv de eficien a problemei, evalueaz eficiena/performana fiecrei variante de program x;

2. relaiile (2) de tipul reprezint restricii de tip resurse; iar restriciile de tipul se refer la restricii tehnico-economice de tip calitativ (i ca urmare indicatorul bk este limita inferioar impus "reetei optime";

3. relaia (3) xj ( 0 j = 1,...,n, numit condiia de nenegativitate a variabilelor, asigur obinerea unei soluii realizabile din punctul de vedere al logicii economice.

Dup cum s-a artat la nceput, structura concret a unei aplicaii n economie este determinat n primul rnd de obiectivul urmrit. Astfel, n cazul problemei determinrii structurii sortimentale optime a produciei, se cunosc cantitile disponibile (cantitile de care se poate face rost pe perioada analizat) din fiecare materie prim {bi, i =1,...,m}, coeficienii tehnologici {aij, i = 1,...,m, j = 1,...,n} (aij reprezint cantitatea din materia prim i necesar fabricrii unei uniti din produsul de tipul j), cantitile maxime {, j = 1,...,n} i minime {, j = 1,...,n} ce pot fi produse din fiecare sortiment n perioada analizat i profiturile unitare {pj, j = 1,...,n} ale fiecrui tip de produs. Se cere gsirea acelor cantiti xj care trebuie fabricate din fiecare tip de produs astfel nct s se obin profitul maxim, n condiiile nedepirii disponibilurilor din fiecare resurs.

Pentru simplificarea modelului, se presupune c preul unui bun nu depinde de cantitatea produs din acesta sau din celelalte, consumul din fiecare materie prim este direct proporional cu cantitatea produs i, pentru fiecare bun, consumurile dintr-o resurs sau alta nu se condiioneaz reciproc.

Problema matematic echivalent este:

n unele probleme, n loc de profiturile pj se cunosc veniturile unitare vj sau costurile unitare cj sau alt criteriu de eficien, scopul fiind maximizarea venitului, minimizarea costurilor respectiv optimul indicatorului de eficien respectiv, sau toate la un loc. De asemenea pot lipsi condiiile de limitare a produciei sau pot exista i alte condiii.

La o problem de programare operativ a produciei restriciile se refer la o serie de maini (utilaje) cu care se execut produsele dorite, bi fiind disponibilul de timp al utilajului i pe perioada analizat iar aij timpul necesar prelucrrii unui produs de tipul j pe utilajul i, scopul fiind maximizarea produciei.

Ca urmare, modelul are forma:

Dac se dorete obinerea unui meniu (reete furajere), care s asigure necesarurile {bi, i = 1,...,m} dintr-un numr de m substane eseniale organismului, avnd la dispoziie un numr de n alimente, cunoscndu-se cantitile {aij, i = 1,...,m, j = 1,...,n} din fiecare substan pe care le conine o unitate de msur din fiecare aliment i costurile {cj, j = 1,...,n} unei uniti de msur din fiecare aliment, putem scrie modelul:

Variabilele xj reprezint, n acest caz, cantitatea din fiecare aliment ce va intra n meniu iar f(x) = este costul total al reetei definit de vectorul x.

Vom ncheia exemplificarea cu prezentarea modelului amestecului optim de produse petroliere. Presupunem c o rafinrie dispune de n tipuri de benzine, prin amestecarea acestora urmnd s obin o benzin cu m caracteristici impuse i la un pre minim posibil. O serie de caracteristici trebuie s fie ndeplinite cu o limit inferioar (de exemplu cifra octanic), altele cu o limit superioar (de exemplu densitatea sau temperatura de fierbere) i altele cu egalitate (de exemplu cantitatea necesar), aceste limite fiind, i = 1,...,m1 , , i = 1,...,m2 respectiv , i = 1,...,m3 cu m1 + m2 + m3 = m. De asemenea, trebuie inut cont de cantitile disponibile din fiecare benzin Di, i = 1,...,n. Se cunosc caracteristicile fiecrei benzine disponibile, date ntr-o matrice A ( Mm(n, unde aij este valoarea caracteristicii i pentru benzina j i preurile unitare ale fiecrei benzine, notate pj, j = 1,...,n. Dac notm cu xj, j = 1,...,n, cantitile din fiecare benzin care vor forma amestecul optim, atunci avem de rezolvat problema:

Programarea matematicSe observ c toate aceste probleme, cu toate c reprezint situaii economice total diferite, sunt aplicaii n sfera activitii economice ale urmtoarei probleme de optimizare:

n care funciile f,gi : Rn ( R pot avea orice form i proprieti (liniare, convexe, continui, difereniabile etc) iar ( poate fi orice submulime a lui Rn (continu sau discret, mrginit sau nemrginit, convex sau neconvex, finit sau infinit etc) i n care dorim s gsim minimul sau maximul funciei f n variabilele xi care ndeplinesc restriciile 1.2 i 1.3. O astfel de problem se numete problem de programare matematic.

Funcia (1.1) se numete funcia obiectiv a problemei de optimizare. n aplicaiile economice, ea reprezint criteriul de performan urmrit: maximizarea beneficiului, maximizarea produciei marf, minimizarea costului produciei, maximizarea gradului de ncrcare al utilajelor sau minimizarea timpului de staionare al acestora, maximizarea veniturilor etc.

Inegalitile (1.2), n care gi sunt funcii de n variabile iar bi sunt constante, se numesc restricii ale problemei de optimizare. Ele traduc n limbaj matematic condiiile de natur economic sau tehnologic n care se desfoar procesul economic modelat, cum ar fi: nedepirea stocurilor disponibile de resurse (materii prime, capaciti de producie, for de munc, fonduri bneti, timp etc), ndeplinirea sau depirea unor indicatori economici (producia fizic, net) etc.

Condiiile (1.3), impuse "direct" variabilelor, depind de natura problemei studiate. De cele mai multe ori, ( este mulimea vectorilor x = (xl,...,xn) ( Rn cu toate componentele nenegative i acest fapt se justific prin aceea c, n general, xi reprezint "nivelele" unor activiti de producie, nivele care nu pot fi negative. n unele probleme de optimizare, cum ar fi cele de croire sau ordonanare, variabilele desemneaz mrimi indivizibile i deci nu pot lua dect valori ntregi. Mulimea ( va fi format n acest caz din vectori x cu toate componentele ntregi i nenegative. n alte probleme, ca de pild cele de afectare, portofoliu etc, variabilele nu pot lua dect valorile 0 sau 1 (variabile bivalente) i ca atare ( va fi format din vectorii x = (x1, ,xn) cu toate componentele 0 sau 1. Caracteristic acestor tipuri de probleme este faptul c ( devine o submulime discret din Rn, de unde i numele generic de probleme de optimizare discret dat acestora.

O soluie a unei astfel de probleme are deci trei proprieti:

P1. verific restriciile 1.2

P2. verific restriciile "directe" 1.3

P3. optimizeaz funcia obiectiv pe mulimea vectorilor care ndeplinesc condiiile P1. i P2.

n teoria programrii matematice se folosesc, pentru claritatea i simplitatea expunerii, urmtoarele noiuni:

soluie a problemei de optimizare =un vector x ( Rn care verific restriciile 1.2

soluie admisibil a problemei de optimizare=un vector x ( Rn care verific restriciile 1.2 i 1.3 ( o soluie care verific restriciile 1.3

soluie optim a problemei de optimizare=un vector x ( Rn care verific restriciile 1.2 i 1.3 i optimizeaz funcia obiectiv pe mulimea tuturor vectorilor cu aceast proprietate

( o soluie care verific restriciile 1.3 i optimizeaz funcia obiectiv pe mulimea tuturor soluiilor cu aceast proprietate

( o soluie admisibil care optimizeaz funcia obiectiv pe mulimea soluiilor admisibile

Izvort din studiul problemelor extremale ale analizei matematice clasice, programarea matematic a cunoscut n ultimele decenii o dezvoltare spectaculoas, explicabil numai n parte prin progresele nregistrate n matematic. ntradevr, aceast dezvoltare a fost puternic stimulat de creterea vertiginoas a complexitii activitilor economice, care a furnizat probleme cu structuri din ce n ce mai complicate, ca i de rapida perfecionare a mijloacelor automate de calcul, singurele capabile s testeze eficiena practic a metodelor teoretice elaborate. La rndul ei, programarea matematic, prin rezultatele ei, a adus un considerabil aport la perfecionarea metodelor de conducere n economie i a impulsionat cercetrile n plan teoretic privind modelarea sistemelor economice complexe, studiul i interpretarea legilor i proceselor economice.

n ceea ce privete rezolvarea acestor probleme, este evident c varietatea extrem a acestora face imposibil gsirea unui algoritm practic care s le poat rezolva pe toate, dar putem gsi (sau ne putem atepta s gsim), pentru fiecare caz particular, un algoritm de rezolvare care s-i trag eficacitatea tocmai din folosirea tuturor particularitilor cazului respectiv. n prezent exist sute de algoritmi de rezolvare, cercetarea problemei evolund din ce n ce mai mult spre testarea i mbuntirea acestora dect spre gsirea unora noi.

Problema de programare liniar

Definiia 1. Dac ntr-o problem de programare matematic funcia obiectiv f i funciile gi, din restriciile 1.2, sunt funcii liniare atunci problema se numete problem de programare liniar. O problem de programare liniar este, deci, un caz particular al problemelor de programare matematic i, innd cont de forma oricrei funcii liniare, rezult c forma general a oricrei probleme de programare liniar este:

unde cj (coeficienii funciei obiectiv), aij (coeficienii restriciilor) i bi (termenii liberi) sunt constate reale.

Forma conic 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 nc destul de complicat, prin faptul c orice restricie poate avea trei forme diferite iar obiectivul poate fi minimizarea sau maximizarea funciei f. Este puin probabil c exist un algoritm i simplu i aplicabil la toate cazurile.

Din acest motiv este mult mai simplu s gsim o anumit form (ct mai simpl) cu proprietatea c pentru orice problem P, exist o alta problem P' de aceast form, echivalent cu problema iniial P (spunem c dou probleme sunt echivalente dac exist un izomorfism ntre mulimile soluiilor celor dou probleme i un homeomorfism ntre funciile lor obiectiv) i s dispunem de un algoritm care s rezolve problemele de aceast form i de o regul prin care s gsim soluia problemei iniiale P din soluia problemei P', gsit cu acest algoritm.

n acest sens (dar i din cauza frecvenei apariiei lor n practic) s-au evideniat dou forme ale problemelor de programare liniar, forma canonic i forma standard.

Definiia 2. Spunem c o problem este la forma canonic dac are una din urmtoarele dou forme:

Forma canonic de minimForma canonic de maxim

Aceast form este cel mai des ntlnit n practic (vezi problema determinrii structurii sortimentale optime a produciei sau problema dietei) i, n plus, restriciile economice sunt n general inegaliti i foarte rar egaliti. De asemenea, aceast form este invariant la anumite transformri (vezi problema dual) i asigur existena soluiei (orice problem la aceast form, care are termenii liberi i coeficienii restriciilor pozitivi, are soluie).

Definiia 3. Spunem c o problem este la forma standard dac are forma:

Aceast form, dei nenatural din punct de vedere economic, este cea care se preteaz cel mai bine la rezolvarea cu metodele algebrei clasice.

Propoziie. Pentru orice problem de programare liniar P exist o problem la forma canonic PFC i o problem la forma standard PFS echivalente cu P.

Demonstraie. ntr-adevr:

a) orice problem de maxim poate fi transformat n una de minim i reciproc folosind relaia:

max f(x) = min f(x)

b) orice restricie de tipul "(" poate fi transformat ntr-o restricie de forma "(" i reciproc folosind relaia:

( ( ( ( ( ( (c) orice restricie inegalitate poate fi transformat n egalitate, prin introducerea unei variabile suplimentare nenegative i folosind relaiile:

( ( ( ( i ( ( ( (

Toate variabilele introduse pentru transformarea inegalitilor n egaliti se numesc variabile de abatere sau variabile de compensare.

d) orice restricie egalitate poate fi transformat n restricii inegalitate, folosind relaia:

( = ( (

e) orice variabil cu restricie de semn negativ (x ( 0) poate fi nlocuit cu o variabil cu restricie de semn pozitiv (y ( 0), folosind relaia:

x ( 0 (

f) orice variabil fr restricie de semn poate fi nlocuit cu dou variabile cu restricie de semn pozitiv, folosind relaia:

x oarecare (

Se demonstreaz fr un efort matematic deosebit c dac P' se obine din P folosind doar transformrile de mai sus (numite i transformri elementare) atunci P i P' sunt dou probleme echivalente i ntre soluiile lor optime exist o bijecie.

Din cele de mai sus rezult cum poate fi adus orice problem de programare liniar la forma standard (sau canonic) i cum se obine soluia problemei iniiale din soluia problemei la forma standard (sau canonic).

Exemplu: Problemei P de mai jos i corespunde problema la forma standard PFS alturat:

PPFS

(min) f = 3x1 2x2 + 4x3

(max) g = +3a1 + 2y2 2z2 4x3

Problema PFS are o singur soluie optim:

a1 = 3, y2 = , z2 = 0, x3 = 0, x4 = , x5 = 0, x6 = , x7 = 0

care d un maxim al funciei g egal cu .

Acestei soluii i corespunde singura soluie optim pentru P:

x1 = -3, x2 = , x3 = 0

care d un minim al funciei f, egal cu .

Rezolvarea problemei de programare liniar.Analiza problemei

Fie o problem P despre care presupunem (fr a restrnge generalitatea) c a fost adus la forma standard. De asemenea presupunem (tot fr a restrnge generalitatea) c variabilele problemei au fost numerotate i denumite xj cu j = 1,...,n (n = numrul de necunoscute), coeficienii variabilelor din funcia obiectiv f cu cj (cj = coeficientul variabilei xj), c n ecuaii variabilele apar n ordinea indicilor, ecuaiile fiind numerotate de la 1 la m (m = numrul de ecuaii) i c am notat cu bi termenul liber al ecuaiei i i cu aij coeficientul variabilei j din ecuaia i. n acest caz putem aeza variabilele problemei ntr-un vector cu n componente, coeficienii funciei obiectiv ntr-un vector cu n componente, termenii liberi ntr-un vector cu m componente, coeficienii variabilelor din ecuaii ntr-o matrice cu m linii i n coloane i vom avea:

x = , c = , b = , A =

(vom nota cu xT, cT i bT transpuii acestor vectori i cu AT transpusa matricei A).

Alegerea aezrii ca vectori coloan a fost fcut din raiuni de uurin a calculelor i a memorrii acestora. Dup aceste notaii, problema poate fi scris mult mai simplu:

sau

Se tie c un sistem de forma A(x = b are soluie doar dac rang(A) = rang(), unde este matricea extins obinut adugnd matricei A vectorul b, n acest caz sistemul devenind echivalent cu sistemul obinut prin eliminarea restriciilor care nu corespund minorului principal (dac sistemul nu are soluie atunci evident nici problema nu are soluii, caz care este total neinteresant).

Presupunem c au fost eliminate aceste restricii. Dac rang A = n atunci sistemul are o singur soluie care, dac este admisibil, este i soluia optim cutat, altfel problema nu are soluie. Este evident c i acest caz este la fel de neinteresant ca primul.

Presupunem deci n continuare c:

rang(A) = m < n

Rezolvarea sistemului A(x = b se poate face ntr-un mod simplu (cel puin teoretic) folosind algebra matricial astfel:

mprim coloanele matricei A n dou submatrici: minorul principal (notat cu B, care este o matrice ptratic 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);

mprim variabilele problemei n doi vectori: vectorul variabilelor principale (corespunztoare coloanelor bazei) i vectorul variabilelor secundare (notat cu xS). Fcnd eventual o renumerotare, pentru uurina expunerii i fiind evident c nu se restrnge generalitatea problemei, presupunem c variabilele principale sunt chiar primele m (aceast presupunere va fi fcut de cte ori va fi posibil, fr a mai specifica acest lucru).

aducem succesiv sistemul la forma de mai jos:

A(x = b ( (BS)(= b ( B(xB + S(xS = b ( B(xB = b S(xS ( xB = B-1(b B-1(S(xS

soluia sistemului va fi submulimea lui Rn:

DB = {x = {xB,xS} / xS ( Rn-m oarecare, xB = B-1(b B-1(S(xS}

Orice alegere a lui xS d o soluie. Dintre toate alegerile posibile este remarcabil (prin simplitatea ei) soluia xS = 0, care duce la soluia particular:

xB =

numit soluia de baz asociat bazei B. Deci xB este xB = B-1(b la care se adaug n-m zerouri. Cu toate acestea, vor fi ambele numite soluie de baz, rezultnd din context de care este vorba.

Observaie: Este evident c fiecrui minor principal al sistemului (= minor de dimensiune m = baz) i corespunde o unic soluie de baz. O soluie de baz care are toate componentele nenule strict pozitive se va numi soluie de baz admisibil iar o soluie optim care este de baz se va numi soluie optim de baz. Se observ c o soluie de baz are cel mult m componente diferite de 0. Din cauza importanei lor n rezolvarea problemei, vom evidenia soluiile de baz care au mai puin dect m componente nenule, numite soluii degenerate i pe cele care au fix m elemente nenule, numite soluii nedegenerate.

DB este izomorf cu Rn, adic are tot attea elemente cte puncte sunt ntr-un spaiu cu n__m dimensiuni. "Alegndu-le" din acestea doar pe cele cu toate elementele pozitive, gsim mulimea n care vom "cuta" vectorul (vectorii) care d (dau) extremul lui f.

Rezolvarea problemei poate duce la urmtoarele rezultate:

R1. Sistemul A(x = b nu are soluii sau nu are soluii admisibile. n acest caz problema nu are soluie.

R2. Imaginea funciei obiectiv pe mulimea soluiilor admisibile este nemrginit (la +( ntr-o problem de maxim sau la -( ntr-o problem de minim). n acest caz spunem c problema are optim infinit.

R3. Imaginea funciei obiectiv pe mulimea soluiilor admisibile este mrginit. n acest caz problema are cel puin o soluie i spunem c problema are optim finit.

Greutatea gsirii soluiei problemei const n imensitatea numrului de soluiilor posibile ale sistemului i n respectarea condiiei de nenegativitate a celor printre care cutm extremul dorit al funciei f. Este natural ca primele ncercri n rezolvare s caute n primul rnd o limitare ct mai puternic a locului n care cutm. Pe baza unor reprezentri geometrice ale problemei au fost descoperite urmtoarele proprieti ale problemei, care poart denumirea de teoreme fundamentale ale programrii liniare:

Teorema 1. Dac problema de programare liniar are soluii admisibile atunci are i soluii de baz admisibile.

Teorema 2. Dac problema de programare liniar are soluii optime atunci are i soluii optime de baz.

Teorema 3. Mulimea soluiilor admisibile (optime) este nchis i convex. Dac este i mrginit atunci punctele extremale ale acesteia sunt chiar soluiile admisibile (optime) de baz ale problemei.

Cele dou teoreme realizeaz efectiv trecerea ctre o problem rezolvabil pe calculator. ntr-adevr, deoarece o baz este un minor de ordinul m al matricii A i unei baze i corespunde o unic soluie de baz rezult c sunt cel mult soluii de baz, adic un numr finit. n acest moment s-ar prea c nu avem dect s lsm calculatorul s calculeze toate soluiile de baz i valorile funciei obiectiv n cele admisibile gsind-o prin comparare pe cea care d minimul sau maximul funciei printre acestea. Totui, aceast variant se dovedete nepractic la o analiz mai atent, innd cont de urmtoarele observaii:

1. faptul c numrul soluiilor de baz este finit ne asigur doar c problema se va termina cndva, ceea ce, din punct de vedere economic, este evident nemulumitor. Noi dorim ca problema s fie rezolvat n timp util, adic repede. Rezolvnd problema ca mai sus vom avea, pentru o problem cu 50 variabile i 20 restricii, de calculat, listat i comparat soluii de baz, adic n jur de 1020. Presupunnd c suntem dotai cu un supercalculator care ar termina un miliard de baze pe secund, rezolvarea ar dura 3000 ani. De altfel, o problem ca cea de sus este foarte mic n comparaie cu problemele "serioase" ce au peste 1000 de variabile i 100 de restricii. n plus, un calculator ca cel de sus nu exist nc, deci n nici un caz nu e disponibil ntreprinderilor obinuite.

2. Cu algoritmul de mai sus vom gsi cea mai bun soluie dintre soluiile admisibile de baz, fr ns s tim dac problema admite, de fapt, optim (ar putea s aib optim infinit).

3. Nu vom ti dac un minor de m(m este baz dect dup ce-i vom calcula determinantul i nu vom ti dac soluia de baz corespunztoare este admisibil dect dup ce o vom calcula.

4. Soluia optim, odat gsit, nu va fi recunoscut ca atare dect dup ce vom calcula toate celelalte soluii de baz, chiar dac ea a aprut chiar la nceputul calculelor.

n concluzie, pentru a fi eficient, un algoritm ar trebui s aib urmtoarele proprieti:

a) s dispun de un criteriu de recunoatere a faptului c problema nu are soluii admisibile;

b) s dispun de un criteriu de recunoatere a faptului c problema are optim infinit;

c) s dispun de un criteriu de recunoatere dac o soluie este optim sau nu;

d) s treac de la o soluie de baz admisibil la una cel puin la fel de bun (o soluie x este mai bun dect o soluie y dac f(x) > f(y) ntr-o problem de maxim i f(x) < f(y) ntr-o problem de minim;

e) s treac de la o soluie la cea mai bun dintre soluiile cel puin la fel de bune posibile ca succesoare;

f) s nu revin la o soluie deja analizat;

g) s efectueze un numr de iteraii comparabil polinomial cu dimensiunea problemei.

h) s nu introduc erori de rotunjire (sau nu prea mari);

i) s fie ct mai simplu de implementat;

Condiiile de mai sus reprezint de fapt un algoritm ideal. La nceputurile cercetrii operaionale era suficient, de fapt, i un algoritm care s ndeplineasc mcar condiiile b), c), d), e) i h). Acest algoritm a fost dat de G.B. Dantzig, n 1947, care la numit algoritmul simplex. El rmne i n zilele noastre cel mai eficient algoritm n ceea ce privete viteza de lucru, simplitatea i implementarea pe calculator, pentru problemele care apar efectiv n practica economic.

Totui, el nu ndeplinea condiiile a), f) i g).

Condiia a) este relativ uor de ndeplinit i ea este acoperit prin introducerea unei faze iniiale suplimentare la algoritmul simplex, rezultnd algoritmul simplex n dou faze.

Condiia f) a fost pus n momentul n care s-a observat c, n condiiile existenei soluiilor degenerate, se poate ajunge n situaia cnd, de la o soluie dat, nu se poate ajunge dect la una la fel de bun i tot aa, astfel nct, dac nu se iau msuri de evitare, se poate ajunge la o soluie care a mai fost, fenomen numit ciclare. Astfel de exemple a fost efectiv gsite, unul fiind exemplul lui Beale prezentat mai jos:

Se observ imediat baza admisibil B0 = (a1,a2,a3), de la care, aplicnd algoritmul sub forma clasic, se vor obine succesiv bazele admisibile B1 = (a4,a2,a3), B2 = (a4,a5,a3), B3 = (a6,a5,a3), B4 = (a6,a7,a3), B5 = (a6,a2,a3), B6 = (a4,a2,a3) ... . Cititorul poate verifica uor c toate aceste baze au ca soluie de baz soluia (0,0,1,0,0,0,0) i valoarea funciei 0, dar nu ndeplinesc condiia de optim. Pe de alt parte se vede c B6 = B1 i deci algoritmul va repeta la infinit aceast succesiune de baze, neatingnd niciodat valoarea maxim , corespunztoare soluiei (,0,0,1,0,1,0).

Aceast situaie este ngrijortoare nu att din considerente practice imediate (nc nu a fost gsit o problem din practic la care s apar acest fenomen, toate exemplele existente fiind artificial construite, ca i cel de mai sus) ct din faptul c un algoritm implementat pe calculator s-ar putea s fie pus n faa unei astfel de probleme, situaie n care n-am putea rezolva problema nici pe calculator, nici manual, ea fiind prea mare. Situaia a fost depit prin diferite tehnici suplimentare adugate celei de trecere la o soluie cel puin la fel de bun (insuficient, cum s-a vzut), cea mai cunoscut fiind cea care folosete ordonarea lexicografic a soluiilor, care va fi prezentat i n aceast carte.

n fine, referitor la condiia g), a durat mult timp pn s-a demonstrat c algoritmul, sub aceast form, nu este n timp polinomial, un exemplu fiind clasa de probleme de mai jos, gsit de Klee i Minty n 1972, n care algoritmul trebuie s analizeze 2n baze (n = numrul de necunoscute) pn la gsirea celei optime.

Pentru o astfel de problem, la 100 de variabile, algoritmul va avea 2100 ( 1030 iteraii, i chiar la o vitez de un miliard iteraii pe secund (mult peste puterea unui calculator actual) va termina n 1013 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 gsii algoritmi care nu folosesc tabelele simplex, primul fiind algoritmul de punct interior al lui Karmakar, despre care s-a demonstrat c lucreaz n timp polinomial.

n ceea ce privete erorile de rotunjire, inevitabile cnd se fac calculele pe un calculator, algoritmul se comport ntr-adevr foarte ru, orice eroare propagndu-se imediat la tot tabelul cu efecte foarte mari. Acest lucru poate fi ns depit aplicnd o variant a algoritmului, numit varianta revizuit a algoritmului simplex.

Toate punctele slabe ale algoritmului, amintite mai sus, nu au nmormntat ns algoritmul simplex, deoarece folosirea acestuia aduce informaii mult mai ample dect gsirea soluiei propriu-zise, este mult mai maleabil n cazul modificrilor ulterioare ale datelor problemei (vezi analiza senzitivitii soluiei la datele problemei), se preteaz mult mai bine la interpretri economice, este uor de scris un program de calculator asociat, este implementat pe foarte multe calculatoare i n plus, aa cum aminteam mai sus, nc nu a aprut o problem practic n faa cruia s clacheze. Noii algoritmi rmn doar ca alternative teoretice sau pentru cazurile n care algoritmul simplex este lent, dar ei nu-l pot nlocui complet.

Fundamentarea matematic a algoritmului simplex

Algoritmul simplex pleac de la presupunerea c dispunem deja de o soluie admisibil de baz xB, corespunztoare unei baze B. De asemenea, presupunem c am rezolvat sistemul A(x = b folosind aceast baz, rezultnd astfel variabilele principale n funcie de cele secundare:

xB = B-1(b B-1(S(xSnlocuind variabilele, cu formula gsit, n funcia obiectiv, obinem:

f(x) = ((B-1(b B-1(S(xS) + (xS = (B-1(b ((B-1(S )(xS =

= f(xB) ((B-1(S )(xS = f(xB) (z )(xS = f(xB) ((xS

unde:

f(xB) = (B-1(b este valoarea funciei obiectiv n soluia de baz

(B-1(S = z este un vector n-m componente z = (zm+1, zm+2,...,zn).

( = z este un vector n-m componente ( = ((m+1, (m+2,..., (n)

Obinem urmtoarea form a problemei:

Din motive de organizare i concentrare a datelor problemei, Danzig le-a trecut pe acestea ntr-un tabel ca cel de mai jos, numit tabel simplex.

c1 c2 ... cm cm+1 ... cn

cBxBxBx1 x2 ... xm xm+1 ... xn

c1c2

cmx1x2

xmB-1(b Im B-1(S

f(xB) 0 zm+1 ... zn

0 (m+1 ... (n

Fiecrei soluii de baz i corespunde un tabel simplex i reciproc, deci, de fiecare dat cnd vom vorbi de un tabel simplex, vom spune i care este baza asociat.

Din forma funciei obiectiv se vede c:

ntr-o problem de maxim:

xB este soluie optim (

EMBED Equation.3 oricare ar fi xS ( 0 (( ( 0 oricare ar fi xS ( 0 ( (j ( 0, j = 1,...,n (toi (j sunt pozitivi)

ntr-o problem de minim:

xB este soluie optim (

EMBED Equation.3 oricare ar fi xS ( 0 (( ( 0 oricare ar fi xS ( 0 ( (j ( 0, j = 1,...,n (toi (j negativi)

Pentru a evita complicarea expunerii vom presupune n continuare c problema este de maxim, pentru cazul de minim raionamentul fiind analog.

Rezultatul obinut reprezint criteriul de recunoatere a optimalitii soluiei sau, mai simplu, criteriul de optim.

Dac soluia nu este optim atunci exist evident o alt soluie de baz admisibil mai bun. Se poate demonstra c dac x i y sunt dou soluii admisibile de baz cu f(x) ( f(y) i numrul de variabile principale prin care difer cele dou este k, cu 1 ( k ( m, atunci exist un ir de soluii admisibile de baz: {x1 = x, x2, ..., xk = y} astfel nct:

1. f(xi) ( f(xi+1) oricare ar fi 1 ( i < k

2. xi difer de xi+1 printr-o singur variabil, oricare ar fi 1 ( i < k

Din cele de mai sus rezult c e suficient s cutm o soluie de baz admisibil mai bun doar printre cele care difer de cea actual printr-o singur variabil.

Trebuie deci s gsim acea variabil principal care iese din baz i acea variabil secundar care intr n baz. Rezultatul schimbrii trebuie s fie:

1. o soluie de baz (deci coloanele corespunztoare noii variabile s formeze un minor principal);

2. o soluie admisibil (adic s aib toate componentele pozitive);

3. o soluie mai bun;

4. cea mai bun posibil dintre soluiile mai bune.

Presupunem c nlocuim variabila principal xi (1( i ( m) cu variabila secundar xj (m+1 ( j ( m). Aceasta este echivalent cu a scoate din ecuaia i (singura n care apare xi) variabila xj, n funcie de variabila xi i de celelalte variabile secundare. Este evident c acest lucru (care este echivalent cu faptul c noua soluie trebuie s fie de baz) este posibil doar dac coeficientul lui xj din aceast ecuaie este diferit de 0 (aij ( 0). n acest caz avem succesiv:

xi + + aij(xj = xi ( xj + + (xi = (xi (( xj = (xi (xinlocuind variabila xj n celelalte ecuaii obinem:

xs + + asj(((xi (xi ) = xs (( xs + (xi = xs (xi pentru s = 1,...,m i s ( i

Conform formulelor de mai sus rezult c noua soluie de baz este admisibil dac:

xs (xi ( 0 oricare ar fi s =1,...,m diferit de i ( ( oricare ar fi s =1,...,m, s ( ii n urma schimbrii noua soluie de baz va fi:

= (xi i = xs (xi pentru s ( i

n concluzie, dac ne hotrm s introducem n baz variabila j, singura variabil care o poate nlocui (pentru ca noua soluie s fie admisibil de baz) nu poate fi dect aceea care corespunde acelui aij strict pozitiv din coloana j din matricea B-1(S, pentru care se obine valoarea minim a rapoartelor dintre componentele soluiei de baz actuale i componentele coloanei j. Pentru evidenierea acestora, ele se noteaz cu (s i avem:

(i =

Condiia de mai sus este numit criteriul de ieire din baz.

Mai nainte am vzut ce efect are schimbarea unei variabile din baz asupra sistemului. Este important ns s vedem efectul ei i asupra funciei obiectiv. Valoarea funciei obiectiv n noua soluie de baz va fi:

f() = =

Pentru ca aceast soluie s fie cel puin la fel de bun trebuie ca:

f() ( f(xB) ( ( f(xB) ( (j ( 0

n concluzie, dac vrem s obinem o soluie strict mai bun vom alege o variabil xj corespunztoare unui (j < 0. Noua soluie va exista efectiv doar dac pe coloana j din matricea B-1(S exist o component aij strict pozitiv i va fi efectiv strict mai bun doar dac componenta corespunztoare xi din soluia de baz este diferit de 0, mbuntirea fiind egal cu .

Situaia n care toate componentele coloanei j din matricea B-1(S sunt mai mici sau egale cu 0 este lmurit de urmtoarea teorem:

Teorem: Dac pe coloana j din matricea B-1(S, corespunztoare unei variabile xj cu (j < 0, toate componentele sunt mai mici sau egale cu zero atunci problema are optim infinit.

Demonstraie: Fie o soluie particular a sistemului, n care variabila secundar xj = ( > 0, ( oarecare iar celelalte sunt 0. n acest caz, variabilele principale vor fi: y(i = xi aij(( i vor fi toate pozitive, innd cont de faptul c toi aij ( 0 i, deci, soluia va fi admisibil. Pentru o astfel de soluie, valoarea funciei obiectiv este:

f(y() = f(xB) (j((. i avem:

deci imaginea funciei f este nemrginit i afirmaia este demonstrat.

Presupunem n continuare c exist o component aij strict pozitiv. Deoarece dorim s trecem la cea mai bun dintre bazele posibile, vom alege dintre toate variabilele cu (j < 0, pe cea pentru care se obine:

Aceast condiie este criteriul de intrare n baz.

Deoarece calculul necesar gsirii acestuia este laborios, Danzig a preferat nlocuirea acestei alegeri cu alegerea acelui j care corespunde celui mai negativ (j (= ), variant care este uor de aplicat, mbuntete soluia i prin care se obine, n marea majoritate a cazurilor, acelai j.

n acest moment tim cum s gsim o soluie mai bun, dac ea exist i am putea calcula din nou elementele necesare analizrii noii soluii, din tabelul simplex, folosind formulele fiecruia:

xB = B-1(b

z = (B-1(A

( = z c

Acest mod de lucru este efectiv folosit n anumite variante ale algoritmului simplex (vezi forma revizuit) dar el presupune calcularea inversei matricei B, ceea ce necesit foarte mult timp. Acest motiv era suficient de convingtor pentru ca Danzig s-i fi pus problema dac nu cumva noul tabel simplex poate fi calculat pe baza fostului tabel simplex, fcnd mult mai puine calcule i utiliznd formule uor de memorat i aplicat. Aceast ntrebare era natural de pus, dac inem cont c noua soluie difer de fosta soluie printr-o singur variabil. Aceste formule au fost efectiv gsite, ele putnd fi obinute urmrind efectul nlocuirii lui xi cu xj asupra sistemului:

noua soluie de baz se obine din fosta soluie cu formulele deja gsite mai sus:

= (xi i

= xs (xi pentru s ( i

noii coeficienii ai variabilelor n cele m ecuaii vor fi:

1. variabil principal xs va avea coeficientul 1 n ecuaia k i 0 n celelalte ecuaii;

2. o variabil secundar xk, diferit de xi, va avea coeficienii n ecuaiile s ( i i coeficientul n ecuaia i.

3. noua variabil secundar xi va avea coeficienii n ecuaiile s ( i i coeficientul n ecuaia i.

4. noua valoare a funciei obiectiv va fi: f() =

5. noii (j i obinem nlocuind n funcia obiectiv variabila xj n funcie de xi:

f(x) = f() (j(( (xi + (xi) =

= (xi =

= f() (xi

de unde rezult c pentru k ( i i

Dei par s fie foarte multe formule complicate, frumuseea algoritmului i meritul lui Danzig const tocmai n faptul c toate respect o regul vizual uor de memorat, numit regula dreptunghiului, aa cum se va vedea n algoritmul simplex.

ALGORITMUL SIMPLEX

Reamintim c presupunem c problema este la forma standard de maxim i c dispunem de o soluie de baz admisibil.

Pasul 1. Se construiete tabelul simplex corespunztor bazei de care dispunem n ordinea urmtoare:

1. pe linia a doua se trec toate variabilele ntr-o ordine oarecare;

2. pe prima linie se trec coeficienii funciei obiectiv, fiecare deasupra variabilei corespunztoare;

3. se construiete matricea A, fiecare coloan fiind format din coeficienii unei variabile din toate ecuaiile (ordinea n care se parcurg ecuaiile trebuie s fie aceeai pentru toate variabilele), avnd grij ca, coloanele s fie trecute n ordinea n care au fost trecute variabilele pe linia 2;

4. se construiete baza B, ordinea coloanelor fiind cea n care apar ele n matricea A;

5. se calculeaz B-1;

6. se calculeaz B-1(A i se trece n partea central a tabelului;

7. se trec variabilele principale n a doua coloan, n aa fel nct, la intersecia liniei i coloanei corespunztoare acestei variabile, s se afle valoarea 1.

8. se trec n prima coloan coeficienii corespunztori variabilelor principale din funcia obiectiv, fiecare n dreptul variabilei corespunztoare;

9. se calculeaz soluia de baz cu formula B-1(b, avnd grij ca ordinea n care au fost trecui termenii liberi n vectorul b s fie aceeai cu ordinea n care au fost parcurse ecuaiile la formarea matricii A;

10. se trec n a treia coloan valorile variabilelor principale din soluia de baz, fiecare n dreptul variabilei corespunztoare;

11. se calculeaz f(xB) nmulind dou cte dou componentele coloanei 1 cu cele din coloana 3 aflate pe aceeai linie i adunnd toate produsele ntre ele (adic facem produsul scalar dintre cB i xB);

12. se calculeaz pe rnd fiecare zj j = 1,...,n un zj obinndu-se nmulind scalar cB cu coloana j din B-1(A aflat n centrul tabelului (aceast linie se calculeaz i se trece doar n primul tabel, scopul ei fiind calcularea lui ();

13. se calculeaz pe rnd fiecare (j j = 1,...,n scznd din linia lui z linia lui c ((j = zj - cj)

Pasul 2. Se analizeaz valorile (j corespunztoare variabilelor secundare (e uor de vzut c ntotdeauna, cei corespunztori variabilelor principale sunt toi 0, deci neinteresani).

dac toi sunt mai mari sau egali cu 0 atunci soluia actual este cea optim. Dac exist (j = 0 n afara bazei, atunci pot aprea dou cazuri:

1) toate elementele din coloana aj din B-1(A sunt mai mici sau egale cu 0. Atunci toate soluiile de forma xB - aj(( sunt soluii optime, unde ( > 0 oarecare;

2) exist o component aij a coloanei aj strict pozitiv. Atunci introducnd variabila xj n baz n locul variabilei principal xi obinem alt soluie de baz optim.

Dac apar numai cazuri de tipul 2), obinem toate soluiile de baz optime, mulimea tuturor soluiilor optime fiind format din toate combinaiile convexe ale acestora. Dac apare i cazul 1) atunci mulimea soluiilor optime este nemrginit fiind format din combinaiile convexe ale soluiilor de forma xB - aj(( unde xB sunt toate soluiile optime de baz.

dac exist (j < 0 atunci l alegem pe cel mai negativ: (k = . Variabila xj va fi cea care intr n noua baz. Dac minimul este multiplu atunci alegem, la ntmplare, unul dintre acetia (cei minimi).

Pasul 3. Se analizeaz elementele coloanei aj din B-1(A, corespunztoare variabilei alese la pasul 2.

Dac toate sunt mai mici sau egale cu 0 atunci problema are optim infinit i algoritmul ia sfrit;

Dac exist componente strict pozitive, pentru acestea se calculeaz rapoartele (s = . Variabila xi corespunztoare raportului minim este cea care va iei din baz. Dac acest minim este multiplu sunt posibile dou cazuri:

1) minimul este strict pozitiv. n acest caz se alege unul dintre acetia la ntmplare;

2) minimul este 0. Atunci xi corespunztori sunt 0, deci soluia este degenerat i noua soluie este la fel de bun. Aceast situaie poate duce la ciclarea algoritmului i alegerea la ntmplare nu mai este suficient, fiind nevoie de o regul de alegere suplimentar care s evite ciclarea. O metod de alegere se bazeaz pe faptul c, aa cum vom vedea, ntotdeauna prima baz este matricea unitate i n dreptul ei, n toate tabelele simplex, se va afla inversa bazei corespunztor fiecruia. n acest caz, pentru poziiile n care s-a obinut minimul mprim prima coloan a lui B-1 la coloana aj i alegem minimul dintre aceste rapoarte. Dac minimul dintre acetia este tot multiplu continum procedeul, pentru poziiile ce dau noul minim, cu coloana a doua din B-1 i aa mai departe, pn minimul rmne unic. Nu este posibil s se epuizeze toate coloanele lui B-1 i minimul s rmn multiplu, deoarece, n acest caz, am avea: , pentru toi indicii jk ai coloanelor lui B-1, i1 i i2 fiind doi din indicii care dau acelai minim pn la sfrit sau altfel scris pentru orice jk ( liniile i1 i i2 din B-1 sunt proporionale, fapt ce contrazice faptul c B-1 este inversabil.

Pasul 4. Se calculeaz componentele tabelului simplex corespunztor noii baze pe baza tabelului actual i folosind urmtoarele reguli:

1. se ncadreaz elementul aij, aflat la intersecia coloanei variabilei care intr n baz cu linia variabilei care iese din baz, care a fost numit de Danzig pivot, ntr-un dreptunghi

2. coloana pivotului va avea 1 n dreptul pivotului i 0 n rest (inclusiv (j);

3. linia pivotului este linia actual mprit la pivot (inclusiv n soluia de baz);

4. restul elementelor se calculeaz cu regula dreptunghiului (inclusiv soluia de baz, ( i f(xB)). Regula dreptunghiului se bazeaz pe observaia c n toate formulele prin care se calculeaz acestea nu apare dect valoarea lor actual, pivotul i cele dou elemente care ar completa dreptunghiul ce are poziia de calculat i pivotul pe diagonal. Regula dreptunghiului se enun literar astfel: "noua valoare = produsul dintre elementele de pe diagonala pivotului minus produsul dintre cele aflate pe cealalt diagonal totul mprit la pivot". (pentru scurtarea timpului de lucru se poate observa c elementele unei linii care are 0 pe coloana pivotului rmn aceleai i de asemenea elementele unei coloane care are 0 pe linia pivotului)

Operaia de calculare a noului tabel prin regulile de mai sus poart denumirea de pivotare.

Pasul 5. Se reia algoritmul de la pasul 2.

Exemplu: Fie problema de programare liniar:

pentru care tim c baza format din coloanele a1, a2, a3 este admisibil. Pentru rezolvare vom aduce problema la forma standard de maxim introducnd variabilele de abatere x7, x8, x9 obinnd:

Vom aeza n tabelul simplex variabilele n ordinea indicilor i vom avea:

c = , A = , B = , cB =

vom calcula matricea B-1 = i pe baza acesteia soluia de baz xB = B-1(b = i matricea B-1(A = care se trec n tabelul simplex:

3 2 1 4 3 5 0 0 0

cBxBxB x1 x2 x3 x4 x5 x6 x7 x8 x9

3

2

1x1x2x31

2

3

i n final se vor calcula valoarea funciei obiectiv n aceast soluie, zj i (j:

3 2 1 4 3 5 0 0 0

cBxBxB x1 x2 x3 x4 x5 x6 x7 x8 x9

3

2

1x1x2x31

2

3

10

Din tabel se observ c exist (j < 0, acetia fiind (4, (5, (6, (8 iar minimul lor este (6.

Observaie Dac vom cuta acel (j care d cea mai bun mbuntire vom avea de gsit acel (j dintre cei negativi pentru care se obine i deci de calculat:

= =

= =

= =

= =

i n final max (,,,) = i corespunde tot lui (6.

n concluzie, soluia actual nu este optim i soluia cea mai bun dintre cele posibile ca succesoare va avea variabila x6 printre cele principale.

Analiznd coloana a6 observm c exist componente strict pozitive (de fapt, n acest caz sunt chiar toate) i calculm pentru acestea rapoartele (i obinnd:

(1 = = , (2 = = 14, (3 = =

deci minimul corespunde variabilei x1 i aceasta este cea care va iei din baz. n cest moment cunoatem noua baz i vom construi tabelul simplex pe baza regulilor de calcul de la pasul 4:

1. pivotul este a16 =

4. de exemplu, pentru elementul de pe poziia a34 avem dreptunghiul:

i noua valoare de pe aceast poziie va fi: = 1

n final, tabelul corespunztor noii baze va fi:

3 2 1 4 3 5 0 0 0

cBxBxB x1 x2 x3 x4 x5 x6 x7 x8 x9

5

2

1x6x2x3

Continund algoritmul vom gsi tabelele:

3 2 1 4 3 5 0 0 0

cBxBxB x1 x2 x3 x4 x5 x6 x7 x8 x9

5

2

0x6x2x8

3 2 1 4 3 5 0 0 0

cBxBxB x1 x2 x3 x4 x5 x6 x7 x8 x9

5

3

0x6x5x85

1

2

28

Ultimul tabel conine soluia optim, deoarece toi (j ( 0. Deoarece nu mai exist nici un (j = 0 n afara celor din baz rezult c soluia optim este unic.

Determinarea unei soluii de baz admisibile de start

Presupunem nc odat c problema este la forma standard.

Algoritmul simplex necesit, pentru pornire, o soluie admisibil de baz. Gsirea acesteia pur i simplu prin ncercri nu este deloc o sarcin uoar, gndindu-ne c aceasta presupune gsirea unui minor principal, inversarea acestuia i calcularea soluiei, abia n acest moment putnd vedea dac aceasta are toate componentele pozitive, aceast cutare putnd dura foarte mult.

Rezolvarea problemei pleac de la observaia c singura baz pentru care calculul de mai sus se poate face imediat este matricea unitate, caz n care soluia de baz corespunztoare este chiar vectorul termenilor liberi. Aceasta presupune ca problema s aib toi termenii liberi mai mari sau egali cu 0 i n matricea A s existe toate coloanele matricii unitate.

Dac toi termenii liberi pot fi fcui mai mari sau egali cu 0 foarte simplu, prin nmulirea eventual cu 1 a restriciei respective, existena tuturor coloanelor matricii unitate este evident c este foarte puin probabil i mai greu de obinut.

n acest sens plecm de la observaia c existena unui vector din coloana unitate printre coloanele matricii A este echivalent cu existena unei variabile care apare doar n ecuaia corespunztoare lui 1 din acel vector, cu coeficientul 1. Acest lucru poate fi obinut n dou moduri:

a) ncepnd de la prima ecuaie, cutm o variabil care are coeficientul de acelai semn cu termenul liber, o scoatem din aceast ecuaie n funcie de celelalte variabile, o nlocuim n celelalte i repetm procedeul pornind de la a doua ecuaie. Pot aprea trei cazuri:

1) la un moment dat obinem o ecuaie n care toi coeficienii variabilelor au semn contrar termenului liber, mcar unul dintre toi fiind diferit de 0. n acest caz ecuaia nu are evident soluie admisibil(pozitiv) i deci problema nu are soluie;

2) toi coeficienii variabilelor i termenul liber sunt 0. n acest caz rezult c aceast ecuaie rezult din cele anterioare i ea va fi eliminat, trecndu-se la urmtoarea;

3) se epuizeaz toate ecuaiile. n acest moment, variabilele care au fost scoase din fiecare ecuaie formeaz baza dorit.

Procedeul de mai sus poate prea atractiv, dar presupune introducerea unui algoritm diferit de simplex, cu efect asupra omogenitii calculelor i a vitezei de lucru. De asemenea, prin efectuarea calculelor de mai sus, datele problemei nu mai au semnificaia economic iniial, ne mai putndu-se face interpretri economice.

b) Pentru toi vectorii coloan introducem n ecuaiile corespunztoare cte o variabil cu coeficientul 1. Vom obine evident un nou sistem de restricii i rmne de vzut ce legtur este ntre soluiile acestuia i cel iniial. Cele dou sisteme au forma:

A(x = b i A(x + y = b

Este evident c o soluie a primului sistem este soluie i a celui de-al doilea (lum y = 0) iar o soluie a celui de-al doilea este soluie i pentru primul doar dac y = 0. Scopul nostru va fi deci, ca pornind de la soluia iniial a celei de-a doua probleme s ajungem la o soluie a acesteia n care y = 0. innd cont c n soluiile de baz, variabilele secundare sunt toate egale cu 0, vom ncerca s scoatem din baz variabilele y. Scopul algoritmului simplex este ns maximizarea funciei obiectiv, nu scoaterea a uneia sau alteia din variabile din baz. Pentru a echivala cele dou scopuri putem proceda n dou feluri:

1) Alegem o nou funcie obiectiv care s-i ating extremul printre soluiile pozitive chiar pentru y = 0 i n momentul cnd am obinut soluia respectiv pornim cu aceasta ca soluie iniial algoritmul simplex pentru fosta problem.

2) Adugm la fosta funcie obiectiv noile variabile cu nite coeficieni de asemenea natur alei nct aportul variabilelor y la valoarea funciei s fie contrar scopului dorit (foarte mari pozitivi ntr-o problem de minim i foarte mari negativi ntr-o problem de maxim).

Vom detalia n continuare cele dou metode:

Algoritmul simplex n dou faze

Dat problema de programare liniar la forma standard de maxim:

n care am aranjat deja ca toi termenii liberi s fie pozitivi (b ( 0).

Faza 1 Construim problema:

pe care o rezolvm cu algoritmul simplex pornind rezolvarea de la baza matrice unitate, putnd ajunge la dou situaii:

1) minimul funciei g este strict pozitiv. Aceasta este echivalent cu faptul c egalitatea Ax + y = b se poate obine doar pentru y > 0 sau altfel spus Ax > b pentru orice x ( 0, deci sistemul Ax = b nu are soluii admisibile i n concluzie problema iniial nu are soluie.

2) minimul funciei g este 0. n acest caz, soluia optim obinut are y = 0, deci verific Ax = b fiind n concluzie o soluie admisibil de baz a primei probleme.

Faza 2 ncepnd de la soluia gsit la faza 1 se rezolv problema iniial cu algoritmul simplex.

Dezavantajul metodei const n faptul c tabelul simplex final de la faza 1 trebuie modificat pentru a obine tabelul simplex iniial de la faza 2 (vectorii x, c, cB, z, (, f(xB), se elimin coloanele corespunztoare lui y) i n plus nu vom mai avea n tabelele simplex ale problemei iniiale inversa bazei (care se gsea n dreptul coloanelor matricii unitate din prima faz) necesar n anumite variante ale algoritmului simplex.

Metoda bazei artificiale (metoda penalizrii)

Dat problema de programare liniar la forma standard de maxim:

n care am aranjat deja ca toi termenii liberi s fie pozitivi (b ( 0).

Construim problema:

n care M este o constant presupus foarte mare (mai mare dect orice constant care ar putea apare n rezolvarea problemei). Rezolvm problema cu algoritmul simplex pornind rezolvarea de la baza matrice unitate, putnd ajunge la trei situaii:

1) problema are optim infinit. n acest caz, problema iniial are optim infinit.

2) problema are optim finit i n soluia de baz avem cel puin o variabil din vectorul y. n acest caz problema iniial nu are soluii admisibile.

3) problema are optim finit i n soluia de baz nu avem nici o variabil din vectorul y. n acest caz problema iniial are optim finit, soluia optim i maximul funciei fiind aceleai cu cele ale problemei modificate.

n final vom remarca faptul c variabilele y nu corespund unor mrimi economice ca celelalte, ele fiind introduse doar ca un artificiu de calcul pentru a putea porni algoritmul simplex. Din acest motiv ele se numesc variabile artificiale.

Exemplu Fie problema de programare liniar:

Forma standard a problemei va fi:

Avem deja termenii liberi i o coloan a matricii unitate corespunztoare variabilei x3. Pentru a obine i a doua coloan vom introduce variabila x5 cu coeficientul 1 n a doua ecuaie i n final vom avea de rezolvat problema:

Algoritmul simplex n dou fazeMetoda bazei artificiale

Aplicnd algoritmul simplex n dou faze vom obine n prima faz succesiunea de tabele:

00001

cBxBxBx1x2x3x4x5

0x31031100

1x52140-11

2140-11

140-10

00001

cBxBxBx1x2x3x4x5

0x3

01

0x2

10

00000-1

Am obinut optimul egal cu 0 n soluia de baz (x3,x2) care va fi soluia iniial pentru algoritmul simplex aplicat problemei iniiale n a doua faz. Eliminm din tabel coloana lui x5, nlocuim valorile coeficienilor funciei obiectiv i deci i valoarea acesteia, valorile ( i obinem tabelul:

2300

cBxBxBx1x2x3x4

0x3

01

3x2

10

00

2300

cBxBxBx1x2x3x4

0x340-1113

2x12140-1

4050-2

2300

cBxBxBx1x2x3x4

0x4

0

1

2x1

1

0

0

0

2300

cBxBxBx1x2x3x4

0x43811041

3x2103110

307030

Soluia optim a primei probleme este deci x1 = 0 i x2 = 10 care d un maxim al funciei egal cu 30. Dac aplicm a doua metod vom obine succesiv tabele:

2300-M

cBxBxBx1x2x3x4x5

0x31031100

-Mx52140-11

-2M-M-4M0M-M

-M-2-4M-30M0

2300-M

cBxBxBx1x2x3x4x5

0x3

01

3x2

10

00

M+

2300-M

cBxBxBx1x2x3x4x5

0x340-1113-3

2x12140-11

4050-22+M

2300-M

cBxBxBx1x2x3x4x5

0x4

0

1-1

2x1

1

00

0

0M

2300-M

cBxBxBx1x2x3x4x5

0x43811041-1

3x21031100

307030M

Rezultatul final este evident acelai.

VARIANTE ALE ALGORITMULUI SIMPLEX

1. Algoritmul simplex dual

Pentru expunerea acestui algoritm trebuie introduse noiunile de baz dual admisibil i soluie dual admisibil de baz. Prin definiie numim:

soluie de baz dual admisibil=soluie de baz pentru care toi (j ( 0

baz dual admisibil=baz corespunztoare unei soluii de baz dual admisibile

Ca i n cazul algoritmului simplex, pentru a putea rezolva problema cu algoritmul simplex dual trebuie s dispunem deja de o baz iniial dual admisibil. Aceast soluie poate exista ca urmare a unor calcule anterioare (vezi capitolul cu reoptimizarea) sau, ca i n cazul algoritmului simplex, poate fi aplicat o procedur prin care s gsim aceast baz. Prezentarea acesteia este mai complicat dect cea de la algoritmul simplex astfel nct:

dac dispunem de o baz dual admisibil vom rezolva problema cu algoritmul simplex dual

dac nu dispunem de o baz dual admisibil vom rezolva problema cu algoritmul simplex.

Pentru a evita orice confuzie, vom numi n continuare algoritmul simplex obinuit algoritm simplex primal i o baz admisibil baz primal admisibil.

Se observ c o soluie dual admisibil nu este n general primal admisibil i reciproc, iar o soluie care este simultan primal i dual admisibil este o soluie optim i reciproc.

Presupunem c am adus problema la forma standard de maxim i dispunem de o baz dual admisibil i dispunem deja de de o baz dual admisibil. Algoritmul simplex dual const n urmtorii pai:

Pasul 1. Se construiete tabelul simplex asociat acestei baze, la fel ca i la algoritmul simplex primal;

Pasul 2. Se analizeaz componentele soluiei:

Dac toate componentele sunt mai mari sau egale cu 0 atunci soluia este i primal admisibil, deci optim.

Dac exist componente strict negative, variabila corespunztoare celei mai negative (xi = ) este cea care iese din baz. Dac minimul este multiplu se ia una la ntmplare.

Pasul 3. Se analizeaz linia li corespunztoare variabilei xi aleas la pasul 2:

Dac toate componentele aij j = 1,...,n sunt mai mari sau egale cu 0, atunci am avea o ecuaie cu toi coeficienii necunoscutelor pozitivi i termenul liber strict negativ, deci problema nu are soluii primal admisibile.

Dac exist componente strict negative, atunci pentru acestea se gsete acel indice pentru care se obine (prin am notat modulul numrului (). Dac minimul este multiplu alegem unul dintre acetia la ntmplare. Variabila corespunztoare acestuia este cea care intr n baz.

Pasul 4. Se construiete tabelul corespunztor noii baze aplicnd aceleai reguli ca la algoritmul simplex primal;

Pasul 5. Se reia algoritmul de la pasul 2

2. Forma secundar

Este evident c modul de organizare al datelor n tabelul simplex nu este unicul mod de a organiza datele ntr-un tabel. Forma secundar este tocmai o astfel de alternativ. Presupunem i n acest caz c problema este la forma standard de maxim, c problema este la forma standard i c dispunem de o soluie iniial de baz care este primal sau dual admisibil.

Pasul 1. Datele problemei vor fi organizate ntr-un tabel de forma:

cS

cxfxS

f(xB)(S

cBxBxB = B-1(bB-1(S

cSxS0In-m

Se observ c singura diferena este c la coloana variabilelor bazei din stnga se adaug i cele secundare, pe orizontal se las doar variabilele secundare iar n loc de matricea unitate n dreptul variabilelor principale vom avea matricea unitate n dreptul celor secundare (dar cu minus), ( fiind calculat la fel, neglijndu-se cei din dreptul variabilelor principale, care oricum erau 0.

Pasul 2. + Pasul 3. Se gsesc variabila care iese din baz i cea care intr n baz cu aceleai reguli ca la algoritmul simplex primal sau, dup caz, ca la cel dual.

Pasul 4. Se construiete tabelul asociat noii baze aplicnd regulile:

1) Pivotul este acelai ca la tabelul simplex;

2) Linia pivotului are 1 n dreptul pivotului i 0 n rest;

3) Coloana pivotului se mparte la pivotul cu semn schimbat

4) Celelalte elemente se calculeaz cu regula dreptunghiului

Pasul 5. Se reia algoritmul de la pasul 2.

Exemplu Fie problema de programare liniar rezolvat mai sus:

Forma standard a problemei va fi:

iar dup introducerea variabilelor artificiale obinem:

Tabelul corespunztor va fi:

230

cBxBxBx1x2x4

-2M-M-2-4M-3M

2x10-100

3x200-10

0x310310

0x4000-1

-Mx5214-1

Aplicm simplex primal i obinem cel mai negativ (j corespunztor lui x2 i (i minim corespunztor lui x5. n acest moment avem o soluie de baz a problemei iniiale i putem elimina variabila x5. Obinem:

2-M020

cBxBxBx1x5x4cBxBxBx1x4

M+-

-

2x10-1002x10-10

3x2- (3x2-

0x3

-0x3

0x4000-10x400-1

-Mx500-10

i n continuare:

3030

cBxBxBx2x4cBxBxBx2x3

45-2

2x124-12x1

3x20-10(3x20-10

0x34-1130x300-1

0x400-10x4

20

cBxBxBx1x3

3073

(2x10-10

3x21031

0x300-1

0x438114

Din rezolvarea de mai sus se observ c aceast metod este mai eficient doar dac numrul variabilelor secundare este mai mic dect numrul variabilelor principale. Totui, motivul principal pentru care a fost introdus aceast variant, este existena unor probleme n care, pe parcursul rezolvrii, se adaug foarte multe restricii (de exemplu rezolvarea problemelor n numere ntregi), pentru o restricie n plus tabelul simplex mrindu-se cu o linie i o coloan (cum se va vedea la capitolul de reoptimizare) iar tabelul corespunztor formei secundare doar cu o linie.

3. Forma revizuit a algoritmului simplex

O problem mare (de exemplu cu 1000 variabile i 100 restricii) necesit n algoritmul simplex introducerea, memorarea i lucrul cu un tabel cu 100.000 componente, adic un numr imens de date. Din acest motiv, i remarcnd faptul c n algoritmul simplex doar o parte din acestea contribuie efectiv la luarea deciziilor, s-a construit un algoritm care s in cont de observaiile de mai sus, numit "forma revizuit a algoritmului simplex", n care se lucreaz cu minimul necesar din datele tabelului simplex. Astfel, pentru testarea soluiei actuale i trecerea eventual la o nou baz avem nevoie doar de urmtoarele elemente:

(1) inversa bazei curente B-1(2) componentele vectorului ( pentru a face testul de optim i a gsi variabila care intr n baz (dac soluia nu e optim)

(3) coloana ak din B-1A corespunztoare celui mai negativ (j (dac exist strict negativi) pentru a face testul de optim infinit

(4) soluia curent pentru a gsi variabila care iese din baz (dac mai e cazul)

Aceste elemente se aeaz ntr-un tabel de forma:

cB

xBxB = B-1bB-1

f(xB) = (B-1

numit tabelul simplex redus.

Operaiile ce se efectueaz n cadrul algoritmului simplex revizuit sunt (presupunem c problema este la forma standard de maxim i deinem o soluie admisibil de baz i inversa bazei corespunztoare):

Pasul 1. Se calculeaz (j corespunztori variabilelor secundare cu formula cunoscut:

(j = (B-1(Pj - cj = (Pj - cj

unde Pj este coloana corespunztoare variabilei xj din matricea iniial.

Pasul 2. Se analizeaz (j calculai:

dac toi sunt mai mari sau egali cu 0 soluia curent este optim. STOP

dac exist (j strict negativi se alege minimul dintre acetia (k, variabila xk va intra n baz i se trece la pasul 3.

Pasul 3. Se calculeaz ak = B-1Pk care se ataeaz ca nou coloan la tabel:

cB

xBxB = B-1bB-1ak = B-1Pk

f(xB) = (B-1(k

Pasul 4. Se analizeaz componentele coloanei ak:

dac toate sunt mai mici sau egale cu 0 problema are optim infinit. STOP

dac exist aik strict pozitivi se alege cel pentru care se obine:

ark =

i variabila xr va iei din baz apoi se trece la pasul 5.

Pasul 5. Se pivoteaz ntregul tabel simplex i se elimin ultima coloan.

Pasul 6. Se reia algoritmul de la pasul 2.

Exemplu Fie problema de programare liniar rezolvat mai sus:

Forma standard a problemei va fi:

iar dup introducerea variabilelor artificiale obinem:

Iteraia 1. Prima baz este B = I2 = B-1 corespunztoare variabilelor x3 i x5 de unde rezult xB = i = (0,-M)(I2 = (0,-M). Primul tabel redus va fi:

0

-Mx3

x510

21

00

1

-2M0-M

Se calculeaz (S = (S cS = (0,-M)( = de unde rezult c cel mai negativ este (2 i vom calcula coloana a2 = I2( = care se adaug la tabelul anterior rezultnd:

0

-Mx3

x510

21

00

11

4

-2M0-M-4M-3

(i minim este cel corespunztor lui x5 i deci variabila x2 va intra n locul variabilei x5.

Dup pivotare i eliminarea ultimei coloane obinem:

0

3x3

x2

1

0-

0

Deoarece variabila artificial x5 a ieit din baz ea va fi eliminat din problem.

Iteraia 2. (S = (S cS = (0,)( = ()

cel mai negativ este (1 i vom calcula coloana a1 = ( = care se adaug la tabelul anterior rezultnd:

0

3x3

x2

1

0-

0

(i minim este cel corespunztor lui x2 i deci variabila x1 va intra n locul variabilei x2.

Dup pivotare i eliminarea ultimei coloane obinem:

0

2x3

x14

21

0-3

1

402

Iteraia 3. (S = (S cS = (0,2)( = ()

cel mai negativ este (4 i vom calcula coloana a4 = ( = care se adaug la tabelul anterior rezultnd:

0

2x3

x14

21

0-3

13

-1

402-2

(i minim este cel corespunztor lui x3 i deci variabila x4 va intra n locul variabilei x3.

Dup pivotare i eliminarea ultimei coloane obinem:

0

2x4

x1

-1

0

0

Iteraia 4. (S = (S cS = (,0)( = ()

cel mai negativ este (2 i vom calcula coloana a2 = ( = care se adaug la tabelul anterior rezultnd:

0

2x4

x1

-1

0

EMBED Equation.3

0

(i minim este cel corespunztor lui x1 i deci variabila x2 va intra n locul variabilei x1.

Dup pivotare i eliminarea ultimei coloane obinem:

0

3x4

x238

104

1-1

0

3030

Iteraia 5. (S = (S cS = (3,0)( = () >0 deci soluia este optim (i unic) STOP

Chiar dac la prima vedere calculele par mai mprtiate i deci mai lente, pentru probleme mari, pe calculator se economisete foarte mult memorie i se mrete foarte mult viteza de calcul.

Totui, marele avantaj al acestei metode este acela c, la fiecare iteraie, se folosesc datele problemei iniiale, ceea ce face ca erorile inerente de rotunjire s nu se propage, rmnnd n limite acceptabile.

n m zerouri

(3)

(2)

(1)

unde I1 ( I2 = {1,2,...,m}

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

(() De aici rezult posibilitatea s calculm coeficienii aij pe baza informaiilor disponibile privind cantitile consumate Rij i nivelul xj: aij = EMBED Equation.3 ; i = 1,...,m; j = 1,...,n

21

_997773831.unknown

_997780383.unknown

_997809811.unknown

_999980909.unknown

_999984287.unknown

_1058358949.unknown

_1058359425.unknown

_1058359702.unknown

_1058361147.unknown

_1058367517.unknown

_1058361138.unknown

_1058359631.unknown

_1058359082.unknown

_1058359261.unknown

_1058358983.unknown

_999987477.unknown

_999987690.unknown

_999988138.unknown

_1055680353.unknown

_1055680383.unknown

_999987717.unknown

_999987663.unknown

_999984348.unknown

_999984358.unknown

_999983523.unknown

_999981625.unknown

_997904462.unknown

_997905160.unknown

_997980266.unknown

_998039689.unknown

_998053995.unknown

_998055053.unknown

_998055346.unknown

_998055691.unknown

_998055861.unknown

_998056565.unknown

_998056570.unknown

_998056597.unknown

_998055988.unknown

_998056401.unknown

_998056425.unknown

_998056030.unknown

_998055889.unknown

_998055731.unknown

_998055801.unknown

_998055201.unknown

_998054386.unknown

_998054518.unknown

_998054927.unknown

_998054946.unknown

_998054536.unknown

_998054447.unknown

_998054344.unknown

_998054369.unknown

_998054046.unknown

_998053184.unknown

_998053447.unknown

_998053869.unknown

_998053889.unknown

_998053794.unknown

_998053234.unknown

_998051319.unknown

_998051700.unknown

_998052448.unknown

_998052479.unknown

_998051712.unknown

_998051388.unknown

_998050362.unknown

_998051240.unknown

_998040319.unknown

_997998984.unknown

_998000769.unknown

_998039629.unknown

_998000664.unknown

_998000689.unknown

_998000724.unknown

_998000579.unknown

_998000604.unknown

_997999049.unknown

_997981160.unknown

_997998795.unknown

_997998816.unknown

_997981032.unknown

_997905179.unknown

_997905191.unknown

_997905316.unknown

_997908158.unknown

_997906382.unknown

_997906831.unknown

_997906941.unknown

_997907141.unknown

_997907164.unknown

_997906973.unknown

_997906888.unknown

_997906785.unknown

_997906298.unknown

_997906346.unknown

_997905354.unknown

_997905105.unknown

_997868348.unknown

_997902894.unknown

_997903123.unknown

_997904043.unknown

_997902117.unknown

_997902686.unknown

_997901240.unknown

_997900011.unknown

_997814215.unknown

_997819845.unknown

_997819906.unknown

_997815861.unknown

_997812421.unknown

_997812595.unknown

_997809919.unknown

_997781959.unknown

_997807771.unknown

_997808424.unknown

_997809698.unknown

_997809798.unknown

_997809591.unknown

_997808077.unknown

_997782785.unknown

_997807721.unknown

_997807754.unknown

_997782384.unknown

_997782683.unknown

_997782734.unknown

_997782652.unknown

_997782344.unknown

_997781296.unknown

_997781350.unknown

_997781365.unknown

_997781329.unknown

_997781222.unknown

_997781249.unknown

_997780686.unknown

_997780749.unknown

_997780619.unknown

_997780640.unknown

_997780540.unknown

_997777172.unknown

_997779388.unknown

_997780350.unknown

_997780364.unknown

_997780238.unknown

_997780279.unknown

_997780292.unknown

_997779577.unknown

_997778195.unknown

_997778961.unknown

_997778001.unknown

_997775282.unknown

_997776370.unknown

_997776548.unknown

_997775335.unknown

_997775086.unknown

_997775266.unknown

_997774863.unknown

_997552938.unknown

_997639812.unknown

_997646015.unknown

_997648568.unknown

_997648941.unknown

_997646908.unknown

_997640014.unknown

_997640101.unknown

_997640001.unknown

_997637920.unknown

_997639480.unknown

_997639688.unknown

_997639302.unknown

_997638125.unknown

_997638419.unknown

_997637982.unknown

_997638104.unknown

_997596896.unknown

_997597696.unknown

_997599994.unknown

_997601164.unknown

_997631546.unknown

_997636235.unknown

_997601505.unknown

_997600347.unknown

_997597726.unknown

_997597682.unknown

_997597290.unknown

_997597425.unknown

_997597232.unknown

_997594196.unknown

_997595156.unknown

_997595177.unknown

_997596799.unknown

_997593959.unknown

_997594056.unknown

_997594022.unknown

_997557176.unknown

_997556936.unknown

_997556993.unknown

_997557070.unknown

_997556716.unknown

_997365488.unknown

_997535944.unknown

_997552490.unknown

_997552508.unknown

_997552617.unknown

_997549265.unknown

_997549028.unknown

_997379756.unknown

_997454778.unknown

_997534614.unknown

_997379822.unknown

_997365527.unknown

_997365657.unknown

_997365503.unknown

_997047418.unknown

_997282363.unknown

_997282552.unknown

_997282784.unknown

_997282415.unknown

_997282308.unknown

_997281045.unknown

_997282203.unknown

_997042986.unknown

_997044468.unknown

_997047226.unknown

_997043230.unknown

_997018358.unknown

_997018394.unknown

_997018298.unknown