Programarea liniara

PAGE

Programarea liniar

Progamarea liniar, ca disciplin matematic, a aprut la mijlocul secolului nostru, primele lucrri fiind publicate de L. Kantorovici (1939) i F. Hitchcock (1941).

Primele probleme rezolvate se refereau la organizarea optim a transporturilor maritime, necesitile de aprovizionare a frontului, planificarea misiunilor aviaiei de bombardament.

n 1947 G. Dantzig i J. Von Newmann creeaz metoda simplex care st la baza rezolvrii problemelor de programare liniar. Ulterior programarea liniar a cunoscut un mare avnt prin lucrrile unor matematicieni i economiti ca T. Koopmans, L. Ford, D. Fulkerson, W. Cooper, H. Kuhn, gsindu-i un cmp foarte larg de aplicaii n economie.

Necesitile reale ale vieii economice au condus la apariia i dezvoltarea altor tipuri de programri, cum ar fi:

programarea ptratic;

programarea convex;

programarea n numere ntregi;

programarea stohastic;

programarea dinamic;

toate acestea fiind nglobate n termenul generic de programare matematic.

Metodele de programare liniar au o larg rspndire n rezolvarea unor probleme privind optimizarea managementului activitilor economice, astfel:

determinarea structurii optime a sortimentului de producie;

amplasarea optim a unor obiective industiale;

folosirea eficient a resurselor;

utilizarea optim a capacitilor de producie;

optimizarea trasporturilor;

optimizarea produciei i a stocajului

repartizarea optim a sarcinilor de producie.

Exist pentru acest tip de probleme dou ci de rezolvare: una analitic cu ajutorul algoritmului SIMPLEX i alta geometric.

Rezolvarea analitic face posibil operarea cu un numr mai mare de variabile (n mod uzual trei pentru o operare manual), avantajul fiind constituit i de faptul c metoda se preteaz la nglobarea ei n programe specializate sub diferite platforme: turbo pascal, C++ etc.

Rezolvarea pe cale geometric are limitri legate de numrul de variabile (maxim dou), dar i de numrul de restricii i totui este mai utilizat datorit simplitii cu care se opereaz.

Rezolvarea pe cale geometric a unei probleme de programare liniar presupune parcurgerea urmtoarelor etape:

elaborarea modelului de programare liniar cu un numar de m restricii i 2 variabile;

reprezentarea grafic;

determinarea soluiei optime;

concluzii.

Exemple de probleme de programare liniar

a) Problema planului optim de producie.

Fie mainile

care fabric sau consum produsele

, n cantiti date pe unitatea de timp, anume

din

pentru maina

. (Dac

produce n unitatea de timp cantitatea

din

atunci

, dac consum atunci

, iar dac

,

nu produce i nu consum

). Producia (respectiv consumul) produsului

nu trebuie s fie sub limita (respectiv s depeasc)

(respectiv

dac

) pentru

.

Fie

timpul de funcionare al mainii

, iar

beneficiul obinut prin funcionarea lui

n unitatea de timp,

. Un sistem de numere reale

constituie un plan optim de producie, dac maximizez beneficiul total adic funcia:

n condiiile restrictive:

.

Dac

reprezint costul funcionrii mainii

n unitatea de timp, atunci se va cere minimizarea funciei de cost

.

b) Problema dietei (a amestecului).

S se determine cantitile

din alimentele

,

, alctuind o diet

astfel nct costul acesteia

s fie minim, unde

reprezint costul unitar al alimentului

, dac se mai cunoate componena n substane nutritive

(cum ar fi: glucide, lipide, vitamine) a alimentelor

,

, dat prin matricea:

unde

este cantitatea de substan

coninut n unitatea din alimentul

i se cere ca fiecare diet s conin cel puin cantitile

din substana

,

. Deci, matematic problema se transcrie:

c) Problema folosirii optime a resurselor.

O unitate economic trebuie s produc produsele

avnd la dispoziie cel mult cantitile

din resursele

. tiind c producerea unei uniti din produsul

necesit cantitatea

din resursa

i c prin livrarea unei uniti din acelai produs se obine beneficiul

,

se cere s se determine cantitile

din produsele

astfel ca beneficiul s fie maxim. Deci:

d) Problema de transport.

Se dau depozitele

, avnd disponibil o marf n cantitile

; consumatorii

solicitnd marfa n cantitile b'1, b'2, ..., b'm; i costul unitar

de transport al mrfii de la depozitul

la consumatorul

.

Se cere s se gseasc un sistem de numere nenegative

unde

este cantitatea de marf transportat de la

la

, care s fac minim costul de transport, adic funcia

i s nu depeasc disponibilul din nici un depozit, adic:

i s satisfac mcar cererea fiecrui consumator, adic:

Sistemul

care ndeplinete aceste condiii se numete program de transport. Evident, existena unui program de transport impune condiia ca disponibilul total s depeasc sau s fie mcar egal cu cererea total, adic:

Dac restriciile problemei sunt date ca egaliti atunci i relaia (1) devine egalitate, i n acest caz problema de transport se numete echilibrat.

n caz contrar spunem c avem o problem de transport neechilibrat.

Datele problemei de transport pot fi nscrise ntr-un tablou de forma:

Tabelul (T)

Consumatori

Depozite

Disponibil

Cerere

Aplicaia 1

O microntreprindere este specializat n fabricarea de seturi de piese de tipul buce (A) i arbori (B), care fac parte din ansamblul cutie de viteze a unui automobil.

Acestea pot fi utilizate pe trei tipuri de maini unelte universale (U1, U2, U3).

S se determine cantitatea optim de seturi de piese ce trebuie realizat lunar n condiiile realizrii unui beneficiu total maxim.

Sa dau:

norma de timp Tij [min/set piese];

fondurile disponibile Fdi [min/lun];

beneficiul planificat Bj [lei/set piese].

n tabelul urmtor sunt prezentate valorile pentru fiecare dintre aceti parametrii:

Tipuri de produse

Utilaje Tij [min/set piese]Fdi [min/lun]

AB

U11199.900

U27128.400

U36169.600

Bj [lei/set piese]90100-

Rezolvare geometric:

Elaborarea modelului matematic de programare liniar.

Funcia obiectiv este definit de relaia:

(1)

Sistemul de restrictii:

(2)

Condiii de nenegativitate:

(3)

Reprezentarea grafic a ecuaiilor dreptelor din sistemul de restricii i a funciei obiectiv:

(4)

Determinarea soluiei problmei:

Se constat c maximul funciei este atins n punctul B, adic cel care este cel mai ndeprtat punct de dreapta , situat n cmpul soluiilor.

Coordonatele punctului B se obin din ecuaiile dreptelor i care se intersecteaz n punctul B:

(5)

(6)

Concluzii:

Calcularea funciei obiectiv cu soluiile anterior obinute:

(7)

Beneficiul lunar maxim va fi deci, egal cu mrimea funciei obiectiv.

ncrcarea utilajelor va fi:

- utilajul U1:

- utilajul U2:

- utilajul U3:

B

D//D0

PAGE 7

_865168571.unknown

_865226651.unknown

_865230011.unknown

_1011962586.unknown

_1224366045.unknown

_1224366088.unknown

_1224366141.unknown

_1224366159.unknown

_1224366169.unknown

_1224366151.unknown

_1224366108.unknown

_1224366117.unknown

_1224366098.unknown

_1224366069.unknown

_1224366079.unknown

_1224366056.unknown

_1224366015.unknown

_1224366030.unknown

_1011962632.unknown

_1195979035.bin

_865231105.unknown

_865231487.unknown

_865231567.unknown

_865231245.unknown

_865231406.unknown

_865230142.unknown

_865230366.unknown

_865230083.unknown

_865227711.unknown

_865229644.unknown

_865229712.unknown

_865229777.unknown

_865229692.unknown

_865229421.unknown

_865229486.unknown

_865228308.unknown

_865229387.unknown

_865227826.unknown

_865227151.unknown

_865227449.unknown

_865227580.unknown

_865227198.unknown

_865226924.unknown

_865227058.unknown

_865226745.unknown

_865226823.unknown

_865225285.unknown

_865225544.unknown

_865226468.unknown

_865226541.unknown

_865225592.unknown

_865225426.unknown

_865225506.unknown

_865225319.unknown

_865168844.unknown

_865169375.unknown

_865225149.unknown

_865169374.unknown

_865168710.unknown

_865168763.unknown

_865168657.unknown

_865167274.unknown

_865167682.unknown

_865168125.unknown

_865168281.unknown

_865168325.unknown

_865168249.unknown

_865167959.unknown

_865167999.unknown

_865167777.unknown

_865167415.unknown

_865167515.unknown

_865167545.unknown

_865167470.unknown

_865167341.unknown

_865167382.unknown

_865167323.unknown

_865166734.unknown

_865167023.unknown

_865167149.unknown

_865167230.unknown

_865167084.unknown

_865166867.unknown

_865166884.unknown

_865166989.unknown

_865166747.unknown

_865166475.unknown

_865166614.unknown

_865166733.unknown

_865166492.unknown

_865166325.unknown

_865166428.unknown

_865166176.unknown