Problema de transport

Metoda transporturilor poartǎ aceastǎ denumire deoarece se foloseste pentru rezolvarea problemelor de programare liniarǎ ce au de a face cu deplasǎri de sarcini in retele de transport.

Prin extensie, metoda transporturilor se aplicǎ, in problemele de transbordǎri si asignare.

Aceasta problema apare frecvent in planificarea distribuirii bunurilor si a serviciilor de la cateva unitati de aprovizionare la anumite adrese.

De obicei cantitatea de bunuri aflate la fiecare unitate de aprovizionare (origine, furnizor, centru de productie, fabrici, oferta) este fixa sau limitata;

La fiecare unitate adresanta (sau destinatie, beneficiar, centru de distributie, cerere) se afla o cantitate de bunuri specificata prin comanda sau cerere.

Din cauza varietatii mari de rute de transport si a diferitelor costuri pentru aceste rute, obiectivul este de a stabili cate unitati de marfa pot fi transportate de la fiecare origine la fiecare destinatie in asa fel incat toate cererile sa fie satisfacute, iar costurile de transport sa fie micsorate.

Sa ilustram problema transportului printr-un exemplu, sa zicem, al companiei Tofan Group care are de transportat un produs de la 3 fabrici la 4 destinatii. Compania opereaza in Bucuresti, Floresti si Brasov. Capacitatile de productie ale acestor fabrici (cantitatile disponibile la furnizor in perioada urmatoare de 3 luni pentru un anume tip de anvelope sunt:

1. Bucuresti 5000 unitati

2. Floresti 6000 unitati

3. Brasov 2500 unitati

Sa presupunem ca firma distribuie anvelope prin 4 centre de distribuire regionale, localizate in Braila, Cluj, Arad si Suceava, iar prognoza pe urmatoarele 3 luni de cerere este (cantitati necesare la beneficiar

1. Braila 6000 unitati

2. Cluj 4000 unitati

3. Arad 2000 unitati

4. Suceava 1500 unitati

Conducerea firmei ar dori sa stabileasca cat din productia sa trebuie transportata de la fiecare fabrica pana la fiecare destinatie de distribuire. Putem construi un grafic alcatuit din 2 grupuri de cercuri, numite noduri (fabrici si centre de distribuire) intre care se realizeaza 12 rute de distribuire, numite arce; graficul astfel obtinut se numeste retea. Se observa ca problema transportului poate fi reprezentata grafic sub forma unei retele, iar din acest motiv putem vorbi de problema fluxului in retea.

Observatie:Costurile de productie sunt identice la cele 3 fabrici, deci singurele costuri variabile implicate sunt cele de transport.

Astfel, problema devine una de determinare a rutelor de transport care pot fi folosite si a cantitatii de marfuri ce urmeaza a fi transportata pe fiecare ruta, in asa fel incat toate cererile de distribuire sa fie onorate la un cost minim de transport. Costul pentru fiecare unitate transportata pe fiecare ruta este (matricea costurilor unitare de transport

Pentru rezolvarea acestei probleme se poate folosi un model de programare liniara.

Vom folosi variabilele de decizie duble:

x_ij - numarul de unitati transportate de la origina i la destinatia j.

matricea cantitatilor transportate, planul de transport ce trebuie determinat si optimizat

cu notatiile:

i = indexul originii, i = 1,2,3

j = indexul destinatiei, j = 1,2,3,4

c_ij = costul per unitatea de transport de la originea i la destinatia j

a_i = oferta sau capacitatea (disponibilul) exprimata in unitati la originea i

b_j = cererea (necesarul) in unitati la destinatia j

De vreme ce obiectivul problemei transportului este de a minimaliza costurile de transport, putem folosi datele referitoare la cost din tabelul de mai sus pentru a elabora urmatoarele expresii ale costului:

Costuri de transport pentru unitati transportate

din Bucuresti = 3x₁₁+2x₁₂+7x₁₃+6x₁₄

din Floresti = 7x₂₁+5x₂₂+2x₂₃+3x₂₄

din Brasov = 2x₃₁+5x₃₂+4x₃₃+5x₃₄

Suma acestor expresii va furniza functia obiectiv care arata costurile totale de transport pentru firma Tofan Group.

Restrictiile problemei de programare liniara

- Cu 3 origini (sau fabrici) problema firmei Tofan Group va avea 3 formulari ale ofertei:

x₁₁+x₁₂+x₁₃+x₁₄ ≤ 5000 (oferta Bucuresti)

x₂₁+x₂₂+x₂₃+x₂₄ ≤ 6000 (oferta Floresti)

2x₃₁+5x₃₂+4x₃₃+5x₃₄ ≤ 2500 (oferta Brasov)

- Cu cele 4 centre de distribuire ca destinatii vom avea nevoie de urmatoarele 4 formule ale cererii:

x₁₁+ x₂₁+ x₃₁ = 6000 (cerere Braila)

x₁₂+ x₂₂+ x₃₂ = 4000 (cerere Cluj)

x₁₃+ x₂₃+ x₃₃ = 2000 (cerere Arad)

x₁₄+ x₂₄+ x₃₄ = 1500 (cerere Suceava)

Din combinarea functiei obiective cu formulele restranse intr-un singur model, reiese urmatoarea formulare de programare liniara cu 12 variabile si 7 restrictii in sistem:

(min) 3x₁₁+2x₁₂+7x₁₃+6x₁₄+7x₂₁+5x₂₂+2x₂₃+3x₂₄+2x₃₁+5x₃₂+4x₃₃+5x₃₄

Solutia data de computer pentru aceasta problema de programare liniara la care s-a redus problema de transport a firmei Tofan Group arata un cost minim de 39.500 unitati monetare. Valorile variabilelor arata cantitatile optime de marfa care se vor transporta pe fiecare ruta (x₁₁=3500, x₁₂=1500, x₂₂=2500, x₂₃=2000, x₂₄=1500, x₃₁=2500). Alte valori ale variabilelor de decizie arata cantitatile de marfa ramase de transportat si rutele.

Consideratii generale

Variatiile problemei de baza de transport pot include una sau mai multe din situatiile urmatoare:

1. oferta totala nu este egala cu cererea totala;
2. functia obiectiva este mai degraba maximizata decat minimizata;
3. constrangeri aparute pe anumite rute, cum ar fi capacitatea drumului sau garantiile minime de transport ale soselei;
4. drumuri inacceptabile

Cu anumite modificari la modelul de programare liniara, aceste situatii pot fi luate in considerare atunci cand vrem sa obtinem solutia optima de transport.

Una din situatiile care apar frecvent este cea in care oferta totala nu este egala cu cererea totala (total disponibil difera de total necesar):

• daca oferta totala este mai mare decat cererea totala, nu este necesara nici o modificare in modelul de programare liniara; interpretam ca oferta nefolosita sau cantitatea de marfuri netransportata de la origine

Diferenta dintre total disponibil si total necesar este absorbita de un beneficiar fictiv introdus in problema doar pentru a o echilibra si astfel a-i putea aplica algoritmul, costurile de transport asociate pe rutele care-l implica pe acest beneficiar fiind considerate nule.

• daca oferta totala este mai mica decat cererea totala,

modelul de programare liniara nu va avea o solutie practica deoarece conditiile cererii nu pot fi indeplinite; in acest caz este necesara o modificare in modelul de programare liniara pentru a ajunge la solutia dorita; mai precis, se foloseste o origine marioneta (furnizor fictiv) care sa absoarba diferenta pana la totalul cererii; se acorda un cost 0 pe unitatea transportata pe orice ruta pornind de la aceasta fabrica marioneta.

Intr-o solutie optima, destinatiile care arata transporturi primite de la furnizorul fictiv, vor fi destinatiile cu o cerere nesatisfacuta.

Observatii:

i) In unele modele poate fi mai convenabil sa luam in considerare mai degraba profitul sau beneficiile per unitate transportata decat costul per unitate. Folosind drept coeficienti profitul sau beneficiul in functia obiectiva vom rezolva un program liniar mai degraba maximizat decat minimizat.

ii) Formula problemei de transport poate fi mai departe modificata pentru a lua in calcul capacitatile de transport ale uneia sau ale mai multor rute. De exemplu, sa presupunem ca ruta Brasov Braila (originea 3 spre destinatia 1) are capacitatea de 1000 unitati din cauza spatiului limitat disponibil modului normal de transport. Aceasta capacitate limitata de transport a rutei poate fi luata in calcul prin adaugarea unei formule prescurtate care specifica o limita superioara pentru variabila de decizie corespunzatoare. Cu x₃₁ aratand cantitatea de marfuri transportata din Brasov la Braila, formula prescurtata a capacitatii rutei va fi: x₃₁ ≤ 1000

La fel cerintele minime ale rutei pot fi garantate; de exemplu: x₂₂ ≥ 2000 va garanta ca o comanda emisa anterior pentru o livrare de la Floresti la Cluj de 2000 de unitati va fi mentinuta in solutia optima.

iii) Unele rute pot fi inacceptabile. Putem face fata acestei situatii acordand un cost arbitrar ridicat per unitate pentru oricare din rutele inacceptabile. Solutia costului minim de transport va evita ruta inacceptabila din cauza acestui cost.

Un mod alternativ de a lucra cu rute inacceptabile este pur si simplu indepartarea variabilei de decizie corespunzatoare din formularea programarii liniare; de exemplu, daca ruta Bucuresti Arad ar fi declarata inacceptabila, x₁₃ ar putea fi scos din formula programarii liniare. Rezolvand modelul cu 11 variabile si 7 formule prescurtate am putea obtine solutia optima, garantand ca ruta Bucuresti Arad nu a fost folosita.

iv) - c_ij ), situatiile c_ij=- si c_ij=+ sunt rezervate pentru anumite probleme speciale: costul negativ are semnificatia de beneficiu pe unitatea de produs livrata.

Formularea economica a problemei de transport

Un produs se transporta de la m centre furnizoare la n centre de consum (beneficiari)

Se cunosc:

matricea costurilor unitare de transport;

cantitatile disponibile la fiecare furnizor;

cantitatile necesare la fiecare beneficiar.

Se cere a se determina planul optim de transport, matricea cantitatilor transportate:

astfel incat costurile totale de transport sa fie minime.

Observatii:

1. P.T. este o problema care poate fi modelata matematic ca P.P.L. vizand minimizarea costurilor de transport si deci, si pentru problemele de transport existǎ algoritmi de optimizare si programe de calculator.
2. O P.P.L. asociata unei P.T. devine o problema de maxim daca in locul costurilor de transport c_ij, in functia obiectiv (1) se folosesc profiturile aduse firmei de transport prin deplasarea unei unitǎti de marfǎ de la punctul i la punctul j, sub aceleasi restrictii privind disponibilul, necesarul si nenegativitatea solutiilor.

Formularea matematicǎ a problemei de transport

Modelul matematic al problemei P.T. echilibrate

functia obiectiv (1)

restrictiile legate de surse (2)

restrictiile legate de destinatii (3)

, conditiile de

nenegativitate ale variabilelor decizionale

(nu pot fi admise transporturi negative).

Conditia de echilibru:

T este cantitatea totala de marfa care se gaseste in depozite si care este ceruta de centrele de consum;

(2) reprezinta totalul cantitatilor transportate de de furnizorul F_i catre toti beneficiarii;

(3) reprezinta totalul cantitatilor transportate catre beneficiarul B_j plecand de la toti furnizorii;

numarul variabilelor este egal cu mn, iar al restrictiilor cu m+n;

matricea tehnologica are numai componente egale cu 0 sau 1;

restrictiile sunt egalitati;

Fiind deci o P.P.L., P.T. beneficiaza de algoritmul simplex pentru rezolvare. Una din metode este sa se treaca la forma duala a problemei si apoi sa se aplice algoritmul simplex. Totusi, forma ei speciala a permis introducerea altor metode de calcul, pornind cu determinarea solutiei initiale si sfarsind cu metoda de rezolvare. Pe acestea le vom prezenta in cele ce urmeaza.

Propozitie:

Orice problema de transport are o solutie admisibila.

Demonstratie:

Daca luam solutia atunci aceasta are in mod evident componente pozitive si verifica sistemul de restrictii:

Din aceasta propozitie rezulta ca orice problema de transport admite si o solutie optima.

Propozitie:

Rangul matricei A a restrictiilor unei probleme de transport echilibrate este egal cu m+n-1.

Demonstratie:

Matricea restrictiilor P.T. are forma:

Adunand primele m restrictii se obtine:

.

Se obtine in membrul stang suma tuturor variabilelor PT, iar in membrul drept suma T, adica restrictiile nu sunt independente. In loc de rangul m+n, A are rangul m+n-1.

Corolar:

O solutie de baza a PT are un numar de componente nenule egal cel mult cu m+n-1.

Ne intereseaza solutia de baza deoarece, solutia optima a problemei se afla printre solutiile realizabile de baza.

Determinarea unei solutii initiale de baza pentru P.T.

Exista mai multe metode speciale concepute in acest scop:

1. metoda costului minim (din tabel, de pe linie, de pe coloana),
2. metoda coltului de Nord-Vest,etc.

Vom ilustra aceste metode pe un exemplu.

Exemplu:

Un produs trebuie transportat de la 3 depozite D₁, D₂, D₃ catre 4 centre de consum C₁, C₂, C₃, C₄. Costurile de transport, necesarul centrelor de consum si disponibilul depozitelor sunt date in tabelul de mai jos.

Sa se stabileasca ce cantitati trebuie transportate de la fiecare depozit la fiecare centru de consum, astfel incat costul total al transportului sa fie minim.

Problema este echilibrata, variabilele de decizie sunt in numar de 12, deoarece aici numarul depozitelor este m=3, iar numarul centrelor de consum este n=4.

Aranjam variabilele in tabel, in fiecare casuta aparand si variabila respectiva x_ij si costul unitar de transport, asa cum este el dat in tabelul precedent (cele doua matrice C si X suprapuse in acelasi tabel)

Modelul primal este:

[min]

O solutie initiala de baza are exact m+n-1=3+4-1=6 componente nenule,daca este solutie nedegenerata de baza si un numar mai mic de 6 componente nenule daca este solutie degenerata de baza.

Metoda costului minim din tabel

Se alege minimul costurilor din tabel, in cazul exemplului nostru 0=c₁₂ sau 0=c₃₁ si se trimite pe ruta sau cantitatea maxima posibil de transportat, tinand seama de disponibil si de necesar. Prin urmare, vom trimite:

x₁₂=min=min=15t

pe ruta si in felul acesta, atat disponibilul depozitului F₁ cat si necesarul centrului B₂ s-au epuizat. Rezulta ca x₁₁=x₁₃=x₁₄=0 si ca x₂₂=x₃₂=0.

Apoi:

x₃₁=min=min=5t,

deci x₃₂=x₃₃=x₃₄=0 si x₁₁=x₂₁=0.

Acum mai raman de stabilit celelalte cantitati x₂₃, x₂₄. Alegem costul minim si constatam ca cel mai mic cost este 9=c₂₃, deci x₂₃=min=15, prin urmare x₃₃=0 si urmeaza costul 20=c₂₄, deci x₂₄=min=10

Solutia initiala X₀, determinata prin metoda minimului din tabel, este urmatoarea:

X₀:

Ea are numai 4 componente nenule in loc de 6 , deci este o solutie degenerata de baza.

Valoarea functiei de eficienta este unitati monetare.

Metoda minimului pe linie

Se porneste cu calculul variabilelor de pe prima linie si nu se paraseste aceasta linie pana cand nu au fost stabilite toate variabilele. Se alege costul minim de pe prima linie:

0=c₁₂x₁₂=min=15t. Rezulta x₁₁=x₁₃=x₁₄=0. Disponibilul primei linii a fost epuizat.

Se trece la a doua linie. Costul minim de pe a doua linie este 7=c₂₂, dar x₂₂=0 deoarece centrul B₂ si-a satisfacut necesarul prin alegerea x₁₂=15. Urmeaza in ordinea marimii c₂₃=9x₂₃=min=15t.

Raman de repartizat inca 10 t ale depozitului F₂.

Costul urmator este c₂₁=12x₂₁=min=5t, etc.

Prin metoda minimului pe linie s-a aflat solutia:

X₁=

unitati monetare. Solutia este degenerata.

Solutia initiala aflata prin metoda minimului pe coloana se afla la fel ca aceea determinata prin metoda minimului pe linie, numai ca repartizarea se face pe centre de consum, deci pe coloane.

Metoda coltului de Nord-Vest pentru alegerea unei solutii initiale de baza

Aceasta metoda nu are in vedere criteriul economic al costurilor, ci numai amplasarea formala a marfii dupa pozitia componentei in tabel. Au prioritate componentele aflate in coltul de N-V al tabelului.

Astfel,x₁₁ este prima componenta din coltul de N-V al tabelului. O alegem automat si o luam egala cu 5t, deoarece:

x₁₁= min=min=5t.

Taiem cu o linie coloana 1, deoarece necesarul lui B₁ a fost satisfacut si catre el nu se vor mai face transporturi.

Urmatorul colt de N-V al tabelului a ramas dupa ce am eliminat coloana intai si este al variabilei x₁₂, a carei marime urmeaza sa o stabilim astfel:

x₁₂=min=10.

Taiem linia intai, deoarece F₁ nu mai are disponibil, iar necesarul centrului B₂ ramane egal cu 5.

In tabelul ramas, coltul de N-V este al casutei (2.2) deci

x₂₂=min=5t.

Se trece la coloana a doua si ramane x₂₃ in coltul de N-V. Luam x₂₃=min=15t, deci coloana a treia urmeaza sa fie anulata, iar disponibilul lui F₂ ramane egal cu 5. Coltul de N-V al tabelului ramas este (2,4), deci

x₂₄=min=5t

In sfarsit, a ramas numai x₃₄=5t si solutia X₂ obtinuta prin metoda coltului de N-V este:

X₂=

unitati monetare. Aceasta solutie nu este degenerata.

Observatie: Dintre cele trei solutii determinate, cea mai buna, desigur, este solutia X₀, deoarece functia de eficienta are valoarea cea mai mica.

Metoda potentialelor pentru determinarea unei solutii optime a P.T.

Este o metoda de testare si de optimizare a solutiei unei P.T. si are la baza rezultatele P.L. (simplexul aplicat formei duale a P.T.)

Pas 1. Se determina o solutie initiala de baza

Pas 2. (criteriul de optim) Se testeaza solutia obtinuta cu ajutorul unei conditii de optim. Daca solutia se gaseste optima, STOP. Daca nu, se trece la pasul 3.

Pas 3. (criteriul de intrare in baza) Se determina o variabila dintre cele nebazice care sa intre in baza, sa devina nenula deci si pentru care solutia se imbunatateste.

Pas 4. (criteriul de iesire din baza) Se determina o variabila care paraseste baza, utilizand conditia de admisibilitate. Se obtine astfel o alta solutie de baza care trebuie din nou verificata daca este optima, deci se reia algoritmul de la pasul 2.

Rezultatul teoretic care sta la baza acestei metode de optimizarea unei solutii primal admisibile pentru problema de transport este:

Teorema Dantzig (conditia de optimalitate)

Fiecarei variabile bazice x_ij a unei solutii de baza ii corespunde un cuplu de numere reale u_i, v_j astfel incat . Daca pentru variabilele bazice notam , atunci solutia optima se obtine daca toate diferentele sunt negative (

Demonstratie: Se aplica algoritmul simplex de optimizare a solutiei initiale de baza pentru forma duala a unei probleme de transport echilibrate.

Vom considera , pentru simplificarea scrierii, cazul m=2, n=3; rezultatele obtinute vor fi valabile si in cazul general. Modelul (PL) corespunzator va fi:

(min) f=c₁₁x₁₁+c₁₂x₁₂+c₁₃x₁₃+c₂₁x₂₁+c₂₂x₂₂+c₂₃x₂₃

x₁₁+x₁₂+x₁₃ = a₁ (variabila duala:u₁)

x₂₁+x₂₂+x₂₃ = a₂ (variabila duala:u₂)

x₁₁+x₂₁=b₁ (variabila duala:v₁)

x₁₂+x₂₂=b₂ (variabila duala:v₂)

x₁₃+x₂₃=b₃ (variabila duala:v₃)

x_ij 0; i=1,2; j=1,3

Modelul dual corespunzator are aspectul:

(max)g=a₁u₁+a₂u₂+b₁v₁+b₂v₂+b₃v₃

u₁+v₁ c₁₁

u₁+v₂ c₁₂

u₂+v₁ c₂₁

u₁+v₃ c₁₃

u₂+v₂ c₂₂

u₂+v₃ c₂₃ u_i+v_j c_ij; i=1,2; j=1,3

u_i,v_j IR

Se stie ca pentru orice solutie X a modelului primal, si pentru orice solutie Y a modelului dual, avem: g(y) f(x)

max = min

y x

In general, modelul dual al P.T. este:

Daca in g inlocuim a_i,b_j cu expresiile date de sistemul primal, obtinem:

In final, din relatia: g(y) f(x) se deduce:

aceasta relatie permite organizarea rezolvarii.

Daca se alege o solutie posibila oarecare a modelului, ea este solutia de baza (adica are sanse sa fie solutie optima) daca are numaul de componente X_ij^*>0 cel mult egal cu m+n-1.

pentru indicii i,j pentru care x_ij^*>0, se rezolva sistemul

u_i+v_j=c_ij

Observatie:

acest sistem este intotdeauna compatibil

nedeterminat, m+n-1 ecuatii liniare cu m+n necunoscute, avand una din necunoscute secundare pentru care se alege o valoare arbitrara.

pentru indicii i,j care participa la scrierea

sistemului, termenii ramasi sunt nuli din cauza faptului ca X_ij^* = 0;

Aparent, expresia u_i+v_j=c_ij are aspectul cerut de conditia de optim (sub rezerva ca e nevoie ca, pentru i,j care nu participa la scrierea sistemului, sa avem: u_i+v_j c_ij)

- daca conditia u_i+v_j c_ij nu este indeplinita, atunci nu este solutie optima si vom constitui o alta solutie imbunatatita.

Aplicatii

1. Fie problema de transport:

Se cere solutia de cost total minim.

Solutie:

Folosim metoda potentialelor pentru verificarea optimalitatii solutiei initiale x⁰:

Rezolvam sistemul u_i+v_j=c_ij pentru acei indici aflati

in celulele ocupate ale solutiei X₀, adica pentru indicii bazici.

Sistemul e simplu nedeterminat (6 ecuatii,5 necunoscute), deci se pleaca de la o valoare arbitrara pentru una din variabilele duale; solutia particulara determinata pentru acest sistem se trece intr-un tabel, adica in matricea

- apoi se testeaza

:

Cum exista , atunci solutia nu este optima si se trece la imbunatatirea ei.

intra o valoare arbitrara q pe pozitia (2,2) din matricea

diferenta, unde s-a gasit cea mai mare dintre valorile pozitive ce nu satisfac criteriul de optim.

determinam un ciclu poligonal cu laturi verticale si

orizontale, avand numai varfuri in casute (celule) ocupate in matricea solutiei X₀ , varfuri pe care le numerotam alternativ cu +q q q q,, etc;

q se alege minimul valorilor aflate in celulele cu semnul -; q=min=35;

- rezulta modificarile in matricea solutiei x⁰, care arata variabila ce paraseste baza.

Pentru solutia nou gasita x₁ s-a reluat algoritmul, rezolvandu-se iar sistemul cu noile variabile duale, s-a construit dinnou matricea costurilor reduse, si s-a verificat conditia de optim, care stabileste ca x₁ este optima.

Sa comparam functiile obiectiv pentru cele doua solutii:

, iar

Observatii:

- daca D_ij0 ( )i,j si ( ) (i₀,j₀) pentru care D_iojo =0, atunci modelul admite inca o solutie optima de baza, cu x_iojo 0;

daca modelul admite solutiile optime de baza

x₁,x₂,.,x_k, atunci x=l₁x₁+l₂x₂+.+l_kx_k, unde l₁ l₂ l_k=1, l_j 0, j=1,k, este tot o solutie optima (care nu e de baza).

2 .Fie problema de transport:

a)Se cere solutia optima a problemei.

b)Se cere solutia optima pentru care avem:

x₂₃=maxim

x₃₁+2x₂₃ 80

Solutie:

Vom aplica metoda potentialelor: drept solutie initiala, folosim

X₀=

X₁ :

Deci solutia

X₂ =

X₂ se gaseste optima.

Cum tabelul diferentei D contine trei valori zero problema data mai are inca alte trei solutii optime de baza, notate X₃,X₄,X₅.

• determinarea solutiei X₃:

=> X₃=

• determinarea solutiei X₄:

=> X₄ =

• determinarea solutiei X₅:

=> X₅ =

Solutia optima generala X_G este data de:

X_G= l₁x₂+l₂x₃+l₃x₄+l₄x₅

Unde: l₁ l₂ l₃ l₄=1

l_1,2,3,4 0

Avem:X_G=

b) Din X_G, gasim: x₂₃=

=85l₁+20l₃+85l₄=20(13l₁+4l₃+13l₄)+5(l₁ l₂ l₃ l₄

=20+5(13l₁+4l₃+13l₄

x₃₁+2x₂₂=6l₁+195l₂+20l₃+35l₄=20(l₁ l₂ l₃ l₄)+5(9l₁+35l₂ l₄)=20(9l₁+35l₂ l₄

Problema devine:

(maxim)f=133l₁+4l₃+13l₄

13l₁+4l₃+13l₄ 12

l₁ l₂ l₃ l₄=1

l_1,2,3,4 0

aceasta problema se rezolva folosind algoritmul simplex.

TESTE DE AUTOEVALUARE

1. Spatii vectoriale (Definitii, exemple).
2. Utilizati algoritmul Simplex pentru:R: x=0,y=3,z=2; optim 11.
3. Sa se aduca la expresia canonica forma patratica: , utilizand metoda vectorilor si valorilor proprii.

1.     Coordonatele unui vector intr-o baza. Modificarea coordonatelor unui vector la schimbarea bazei.

2.     Demonstrati cu ajutorul algoritmului Simplex ca problema nu are solutii posibile:

3.     Sa se aduca la expresia canonica forma patratica: , utilizand metoda valorilor si vectorilor proprii. Sa se determine si baza corespunzatoare.

1.     Subspatii liniare (Definitie, exemple, operatii cu subspatii).

2.     Sa se costruiasca modelul matematic asociat problemei de mai jos si sa se determine solutia optima pentru problema de programare liniara rezultata, utilizand algoritmul simplex:

In cadrul unei livezi sunt destinate 8 ha de teren pentru a se cultiva doua feluri de plante A si B. Investitiile necesare pe hectar sunt respectiv de 2000 u.m. si 5000 u.m. iar castigul net pe ha este de 30000 u.m., respectiv 60000 u.m. Se investesc 25000 u.m. in cultura celor doua feluri de plante. Pe cate ha trebuie cultivate fiecare din aceste plante, pentru ca sa se obtina un beneficiu cat mai mare?

R: ; optim 330000.

3.     Utilizand metoda Jacobi sa se aduca la o expresie canonica forma patratica:

.

1.     Operatori liniari pe spatii vectoriale (Definitie, exemple, operatii; nucleul si imaginea unui operator liniar).

2.     Sa se rezolve problema de programare liniara prin trecere la forma duala:

R: ; optim 12.

3.     Sa se studieze liniar independenta vectorilor din :

si sa se descompuna vectorul in baza formata de acestia.

1.     Forme fundamentale ale PPL, solutii, clasificare (interpretare economica).

2.     Sa se diagonalizeze matricea A= si sa se determine . Sa se precizeze baza fata de care maricea A admite forma diagonala.

3.     Sa se determine costul minim de transport daca se cunosc: matricea costurilor unitare de transport, cantitatile disponibile la fiecare furnizor si cele necesare fiecarui beneficiar ca in tabloul:

R: 325

1.     Algoritmul Simplex primal (enunt si interpretare economica).

2.     O intreprindere comerciala dispune de 800 tone de fructe aflate in trei depozite , repartizate astfel: in sunt 450 tone, in sunt 150 iar 200 tone in . Aceasta cantitate trebuie transportata la doua fabrici astfel: la 550 tone, iar la 250 tone. Matricea costurilor unitare de transport este urmatoarea: . Se cere planul optim de transport.

3.     Sa se determine matricea operatorului liniar si sa se diagonalizeze, precizand baza corespunzatoare.

Nota asupra examinarii

Examinarea se face in scris, cu bilet individual ce contine o cerinta teoretica si doua aplicatii din tematica aferenta examenului respectiv.