Buna ziua
Am si o problema de programare liniara si anume:
sa se stabileasca min(3x+103y)avand
10x+9y<=10
8x+3y>=9
x,y>=0
intra in domeniu?

[Citat] Buna ziua Am si o problema de programare liniara si anume: sa se stabileasca min(3x+103y)avand 10x+9y<=10 8x+3y>=9 x,y>=0 intra in domeniu?

Nu exista nici un punct de coordonate (x,y) care sa satisfaca toate conditiile
10x+9y<=10
8x+3y>=9
x,y>=0

Va puteti convinge usor desenand fiecare dintre drepte si gasind semiplanul dat de inecuatie.

Verificati enuntul.

Buna ziua
Imi cer scuze -este evident gresala mea
Am verificat enuntul si asa este !
De fapt problema de programare liniara era asa:
Sa se rezolve problema de programare liniara :
min(ax+by)
cx+dy<=e
fx+gy>=h unde a=3,b=103,c=10,d=9,e=149,f=8,g=3,h=9 cu x,y>=0.
Nu am vrut sa va supar cu exprimarea generala dar cand am inlocuit am gresit!
Acum se poate sa mi se rezolve?multumesc mult!
andrei

[Citat] Buna ziua Imi cer scuze -este evident gresala mea Am verificat enuntul si asa este ! De fapt problema de programare liniara era asa: Sa se rezolve problema de programare liniara : min(ax+by) cx+dy<=e fx+gy>=h unde a=3,b=103,c=10,d=9,e=149,f=8,g=3,h=9 cu x,y>=0. Nu am vrut sa va supar cu exprimarea generala dar cand am inlocuit am gresit! Acum se poate sa mi se rezolve?multumesc mult! andrei

Bun, sa rezolvam impreuna.
Care sunt taieturile celor doua drepte de ecuatii

cx + dy = e si
fx + gy = h

cu axele de coordonate ?
Care este regiunea pe care avem de minimizat ceva?
In care din cele patru colturi se atinge minimul?

Pai atunci eu cred ca trebuie sa facem asa:
reprezentam grafic cele doua drepte care impreuna cu axele de coordonate x1 si x2 determina un patrulater si anume:
A(1,125 si zero),B(14,9 si zero),C(16(5) si zero),D(0 si 3).
Construind acest patrulater obsrvam ca minimizarea se realizeaza doar pentru un singur varf si anume varful A.
Asa o fi?

[Citat] Pai atunci eu cred ca trebuie sa facem asa: reprezentam grafic cele doua drepte care impreuna cu axele de coordonate x1 si x2 determina un patrulater si anume: A(1,125 si zero), B(14,9 si zero), C(16,(5) si zero) (puse invers), D(0 si 3). Construind acest patrulater observam ca minimizarea se realizeaza doar pentru un singur varf si anume varful A. Asa o fi?

Cam asa, ecuatiile dreptelor de marginire sunt
x = 0
y = 0
10 x + 9y = 149 care este drepta prin B( 149/10 si 0 ) , C( 0 si 149/9 = 16,555... )
8x + 3y = 9 care este dreapta prin A( 9/8 si 0) , D( 0 si 3 ) .

Regiunea pe care avem de minimizat este patrulaterul ADCB.
(De ce? (0,0) nu verifica conditia legata de dreapta AD, deci luam "celalalt" semiplan". Apoi (0,0) verifica conditia legata de BC, deci ramanem in semiplanul cu (0,0). Intersectam aceste semiplane cu primul cadran...)

Acum se ia vectorul care determina expresia de minimizat, acel (a,b) = (3,103) din "produsul scalar"

ax + by = (a,b) . (x,y)

se deseneaza pe aceeasi hartie (cu originea in 0), se traseaza (tot prin 0) perpendiculara pe aceasta directie (a,b). Pe aceasta perpendiculara produsul scalar de mai sus este nul. Acum "impingem" (translatam) aceasta perpendiculara in directia vectorului (a,b) continuu, putin cate putin pana dam de primul colt.

Cu cat mergem mai "sus" (in directia lui (a,b)) cu atat dam de o valoare mai mare. Deci minimul se atinge in primul colt inghitit de aceasta "impingere" (translatare paralela continua a dreptei de nivel..).
Primul colt inghitit este A, simtul pentru numere ne spune ca mai bine il inmultim pe 3 cu 9/8 decat pe 103 cu 3 daca vrem sa facem economie...

Buan seara
Nu va suparati dar nu am inteles de unde a rezultat ca (a,b)=(3,103) si care este de fapt ecuatia dreptei care reprezinta directia (a,b)?Pentru a duce apoi perpendiculara.
Poate ca nu sant asa de complicate dar eu nu prea le-am inteles.Se poate sa imi dati lamuriri?Multumesc foarte mult
Andrei

[Citat] Buan seara Nu va suparati dar nu am inteles de unde a rezultat ca (a,b)=(3,103) si care este de fapt ecuatia dreptei care reprezinta directia (a,b)?Pentru a duce apoi perpendiculara. Poate ca nu sant asa de complicate dar eu nu prea le-am inteles.Se poate sa imi dati lamuriri?Multumesc foarte mult Andrei

Buna.
Lucrurile sunt foarte simple.
Sa luam un exemplu foarte simplu.
Ne legem de functia
f(x,y) = 2x+y = (2,1) . (x,y) produs scalar, pentru a avea si intuitia geometrica,
care este definita pentru toti (x,y) din plan.

Unde se anuleaza aceasta functie?
In primul rand in (0,0).
Apoi in vectorul (-1,2) care este perpendicular pe (2,1), produsul scalar se anuleaza. Apoi pe toti vectorii de forma (-a, 2a). (Se anuleaza produsul scalar.)

Desenam acum aceasta dreapta
(D)
parametrizata prin (-a,2a). Care este ecuatia ei? Nu este de mirare poate ca ecuatia ei este 2x+y = 0.

Sa translatam acum aceasta dreapta... Cum arata de exemplu dreapta de ecuatie
2x + y = 2?
(Rog a se schita.) Taieturile ei sunt (1,0) si (0,2).
Desigur ca si pe aceasta dreapta functia "de optimizat" este constanta, anume constant egala cu 2. (Prin definitie!)

Ce am facut? Am translatat "linia de nivel" (D: 2x+y=0) in mod paralel pana am dat la ceva bucata de drum de 2x+y = 2.
Orice punct dintre cele doua drepte, va fi "inghitit" de aceasta translatare. Punctele inghitite mai repede au in ele valoarea lui f(x,y) mai mica.

Asadar, daca vrem sa vedem unde este minima functia f(x,y) = 2x+y pe o regiune (convexa) din plan scrijelita pe langa punctul (7,7) (sa zicem) facem "optic" asa: Translatam continuu dreapta 2x+y = 0 in directia vectorului normal la ea (2,1) pana ce "inghitim primul punct". In acest punct se atinge minimul.
Daca o mai translatam mai departe, maturand regiunea respectiva pana la ultimul contact, ei bine, acest ultim contact este cel in care se atinge maximul. Asa ceva trebuie explicat la scoala / la catedra. Nu inteleg sensul optimizarii daca nici pentru lucruri simple nu se da exemplul simplu. Mai tarziu vin teoreme care asigura ca minimul se realizeaza pe o "fata" a politopului si algoritmi care "descopera fata" in intregime. (Printr-o mutare din colt in colt.) Nu stiu cum se poate face optimizare fara a explica din prima ce este un colt si pe care din ele functia obiectiv are minim/ maxim (din punct de vedere intuitiv.)

Sper ca am raspuns la intrebare. Daca nu, putem sporovai in liniste mai departe.
(Tot aici, deschiderea unui nou subiect nu este de dorit...)

Buna seara
Da,acum este clar.
Iata cam ce am inteles eu:se porneste de la expresia de minimizat si anume min(ax+by)respectiv ax+by=(3,103)(x,y).
Este vorba de fapt de o dreapta pe care o reprezint grafic.
Directia de deplasare este intr-adevar vectorul perpendicular pe ea si al carei ecuatii se deduce tinand cont ca relatia intre pante este m1m2=-1.
Deci pot sa reprezint grafic si aceasta directie.Mergand apoi "in sus"pe aceasta directie (incepand de la dreapta deja reprezentata grafic)dau peste varful A,care este chiar solutia problemei.
Va multumesc foarte mult pentru explicatiile date care m-au facut sa inteleg rezolvarea problemei.Sper ca am inteles bine.
Imi cer scuze ca am revenit pe alt subiect,nu am stiut ca sigur ca era mai bine sa intru tot pe acelasi subiect.
Data viitoare asa voi face!
Andrei

Eu sunt cel care multumeste, singurul lucru care conteaza este intelegerea si sansa de a da mai departe ceea ce stim! Numai bine si tot asa mai departe!

Buna ziua
Intelegand foarte bine rezolvarea grafica,acum imi extind pretentiile si as fi curios sa aflu rezolvarea analitica(algoritmul simplex).
Ma mai puteti ajuta?Daca nu aveti timp nu e nici o problema dar fata de faptul ca am inteles foarte bine explicatiile de la metoda grafica ....
Cu multumiri
Andrei