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 īn retele de transport.

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

Aceasta problema apare frecvent īn planificarea distribuirii bunurilor si a serviciilor de la cāteva 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 cāte unitati de marfa pot fi transportate de la fiecare origine la fiecare destinatie īn asa fel īncāt 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 īn Bucuresti, Floresti si Brasov. Capacitatile de productie ale acestor fabrici (cantitatile disponibile la furnizor īn perioada urmatoare de 3 luni pentru un anume tip de anvelope sunt:

Bucuresti 5000 unitati

Floresti 6000 unitati

Brasov 2500 unitati

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

Braila 6000 unitati

Cluj 4000 unitati

Arad 2000 unitati

Suceava 1500 unitati

Conducerea firmei ar dori sa stabileasca cāt din productia sa trebuie transportata de la fiecare fabrica pāna la fiecare destinatie de distribuire. Putem construi un grafic alcatuit din 2 grupuri de cercuri, numite noduri (fabrici si centre de distribuire) īntre 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 īn 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, īn asa fel īncāt 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 īn unitati la originea i

b_j = cererea (necesarul) īn 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 restrānse īntr-un singur model, reiese urmatoarea formulare de programare liniara cu 12 variabile si 7 restrictii īn 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 decāt minimizata;
3. constrāngeri 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 īn considerare atunci cānd vrem sa obtinem solutia optima de transport.

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

• daca oferta totala este mai mare decāt cererea totala, nu este necesara nici o modificare īn 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 īn 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 decāt cererea totala,

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

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

Observatii:

i) Īn unele modele poate fi mai convenabil sa luam īn considerare mai degraba profitul sau beneficiile per unitate transportata decāt costul per unitate. Folosind drept coeficienti profitul sau beneficiul īn functia obiectiva vom rezolva un program liniar mai degraba maximizat decāt minimizat.

ii) Formula problemei de transport poate fi mai departe modificata pentru a lua īn 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 īn calcul prin adaugarea unei formule prescurtate care specifica o limita superioara pentru variabila de decizie corespunzatoare. Cu x₃₁ aratānd cantitatea de marfuri transportata din Brasov la Braila, formula prescurtata a capacitatii rutei va fi: x₃₁

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 īn solutia optima.

iii) Unele rute pot fi inacceptabile. Putem face fata acestei situatii acordānd 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 īndepartarea 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. Rezolvānd modelul cu 11 variabile si 7 formule prescurtate am putea obtine solutia optima, garantānd 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 īncāt costurile totale de transport sa fie minime.

Observatii:

1. P.T. este o problema care poate fi modelata matematic ca P.P.L. vizānd 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 īn locul costurilor de transport c_ij, īn 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 īn 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 plecānd 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 sfārsind cu metoda de rezolvare. Pe acestea le vom prezenta īn cele ce urmeaza.

Propozitie:

Orice problema de transport are o solutie admisibila.

Demonstratie:

Daca luam solutia atunci aceasta are īn 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:

Adunānd primele m restrictii se obtine:

.

Se obtine īn membrul stāng suma tuturor variabilelor PT, iar īn membrul drept suma T, adica restrictiile nu sunt independente. Īn 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 īn 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 īn tabelul de mai jos.

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

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

Aranjam variabilele īn tabel, īn fiecare casuta aparānd si variabila respectiva x_ij si costul unitar de transport, asa cum este el dat īn tabelul precedent (cele doua matrice C si X suprapuse īn 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, īn cazul exemplului nostru 0=c₁₂ sau 0=c₃₁ si se trimite pe ruta sau cantitatea maxima posibil de transportat, tinānd seama de disponibil si de necesar. Prin urmare, vom trimite:

x₁₂=min=min=15t

pe ruta si īn felul acesta, atāt disponibilul depozitului F₁ cāt 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 ramān 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 īn 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 pāna cānd 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 īn ordinea marimii c₂₃=9x₂₃=min=15t.

Ramān de repartizat īnca 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 īn vedere criteriul economic al costurilor, ci numai amplasarea formala a marfii dupa pozitia componentei īn tabel. Au prioritate componentele aflate īn 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 īntāi si este al variabilei x₁₂, a carei marime urmeaza sa o stabilim astfel:

x₁₂=min=10.

Taiem linia īntāi, deoarece F₁ nu mai are disponibil, iar necesarul centrului B₂ ramāne egal cu 5.

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

x₂₂=min=5t.

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

x₂₄=min=5t

Īn sfārsit, 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 īn baza) Se determina o variabila dintre cele nebazice care sa intre īn 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, utilizānd 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 īi corespunde un cuplu de numere reale u_i, v_j astfel īncāt . 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 īn 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 R

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

Īn general, modelul dual al P.T. este:

Daca īn "g" īnlocuim a_i,b_j cu expresiile date de sistemul primal, obtinem:

Īn 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 īntotdeauna compatibil

nedeterminat, m+n-1 ecuatii liniare cu m+n necunoscute, avānd 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 īndeplinita, atunci nu este solutie optima si vom constitui o alta solutie īmbunatatita.

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

īn 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 īntr-un tabel, adica īn matricea

- apoi se testeaza

:

Cum exista , atunci solutia nu este optima si se trece la īmbunatatirea 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, avānd numai vārfuri īn casute (celule) ocupate īn matricea solutiei X₀ , vārfuri pe care le numerotam alternativ cu +q q q q,., etc;

q se alege minimul valorilor aflate īn celulele cu semnul "-"; q=min=35;

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

Pentru solutia nou gasita x₁ s-a reluat algoritmul, rezolvāndu-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 īnca 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 l_j 0, j=1,k, este tot o solutie optima (care nu e de baza).

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 īnca 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₂₃=

l l l l l l l l l l

l l l

x₃₁+2x₂₂=6l l l l l l l l l l l l l 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.

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

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

Sa se aduca la expresia canonica forma patratica: , utilizānd metoda valorilor si vectorilor proprii. Sa se determine si baza corespunzatoare.

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

Sa se costruiasca modelul matematic asociat problemei de mai jos si sa se determine solutia optima pentru problema de programare liniara rezultata, utilizānd 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 cāstigul net pe ha este de 30000 u.m., respectiv 60000 u.m. Se investesc 25000 u.m. īn cultura celor doua feluri de plante. Pe cāte ha trebuie cultivate fiecare din aceste plante, pentru ca sa se obtina un beneficiu cāt mai mare?

R: ; optim 330000.

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

.

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

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

R: ; optim 12.

Sa se studieze liniar independenta vectorilor din :

si sa se descompuna vectorul īn baza formata de acestia.

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

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

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

Algoritmul Simplex primal (enunt si interpretare economica).

O īntreprindere comerciala dispune de 800 tone de fructe aflate īn trei depozite , repartizate astfel: īn sunt 450 tone, īn sunt 150 iar 200 tone īn . 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.

Sa se determine matricea operatorului liniar si sa se diagonalizeze, precizānd 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.