Scribd Logo
Upload

Welcome to Scribd!

  • 43 views

    LP Ravan

    Uploaded by

    vahid
    The document discusses convex sets and linear programming. It defines convex sets and proves some properties about them, such as the intersection of convex sets being convex. It then applies these concepts to linear functions and proves that a linear function achieves its maximum and minimum values at the vertices of a convex polygon.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    LP Ravan

    Uploaded by

    vahid
    43 views4 pages
    The document discusses convex sets and linear programming. It defines convex sets and proves some properties about them, such as the intersection of convex sets being convex. It then applies these concepts to linear functions and proves that a linear function achieves its maximum and minimum values at the vertices of a convex polygon.

    Original Description:

    ede

    Original Title

    LP_ravan

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses convex sets and linear programming. It defines convex sets and proves some properties about them, such as the intersection of convex sets being convex. It then applies these concepts to linear functions and proves that a linear function achieves its maximum and minimum values at the vertices of a convex polygon.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    43 views4 pages

    LP Ravan

    Uploaded by

    vahid
    The document discusses convex sets and linear programming. It defines convex sets and proves some properties about them, such as the intersection of convex sets being convex. It then applies these concepts to linear functions and proves that a linear function achieves its maximum and minimum values at the vertices of a convex polygon.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 4

    Konveksni skupovi

    Neka je V vektorski prostor nad poljem F. (U daljem tekstu interesovae nas samo vektorski prostor Rn .)
    Neka su A, B V. Oznaimo sa AB sledei skup vektora

    AB = {C : t A + (1 t) B, 0 t 1}.

    Skup vektora S V je konveksan ako za svaka dva vektora A, B skupa S vai da je AB S.


    Teorema 1 Neka je {Si : i I} familija konveksnih skupova. Tada je i skup S = {Si : i I} konveksan
    skup.
    Dokaz. Neka su A, B S. Na osnovu definicije preseka skupova sledi da za svako i I vai A, B Si .
    Prema definiciji konveksnog skupa, tada za svako i I vai AB Si , odakle AB S. 

    2
    1.1 Sluaj R

    Neka su u ravni date take A(xA , yA ) i B(xB , yB ), i pretpostavimo da je C(xC , yC ) taka koja pripada u
    dui AB. Tada, za neko t [0, 1], vai

    OC = OB + t(OA OB),

    OC = tOA + (1 t)OB,
    (xC , yC ) = t(xA , yA ) + (1 t)(xB , yB ),
    (xC , yC ) = (txA + (1 t)xB , tyA + (1 t)yB ).

    Znai,
    AB = {(txA + (1 t)xB , tyA + (1 t)yB ) : t [0, 1]}
    Primetimo da se za t = 0 taka C poklapa sa B, doke se ona za t = 1 poklapa sa A.
    Za realne brojeve a, b, c sa osobinom (a, b) 6= (0, 0) kaemo da je skup taaka

    {(x, y) R2 : ax + by c} (1.1)

    poluravan.

    Teorema 2 Poluravan je konveksan skup.

    Dokaz. Neka je poluravan S data sa (1.1) i A, B S. Tada je

    axA + byA c (1.2)


    axB + byB c (1.3)

    Posmatrajmo proizvoljnu taku C AB datu sa

    (xC , yC ) = (txA + (1 t)xB , tyA + (1 t)yB ), t (0, 1).

    1
    2 CHAPTER 1. KONVEKSNI SKUPOVI

    Ako nejednainu (1.3) pomnoimo sa t > 0, a nejednainu (1.3) sa (1 t) > 0, tada je

    taxA + tbyA tc
    (1 t)axB + (1 t)byB (1 t)c

    odakle je zbir levih strana manji ili jednak sa zbirom desnih strana

    a(txA + (1 t)xB ) + b(tyA + (1 t)yB ) c tj.



    axC + byC c. to znai da C AB.
    

    Posledica 1 Presek familije poluravni je konveksan skup.


    2
    Linearno programiranje - interpretacija u R

    Neka je data linearna funkcija f : R2 R definisana sa f (x, y) = cx + dy.

    Teorema 3 Ako za take A(xA , yA ) i B(xB , yB ) vai

    f (xA , yA ) f (xB , yB ),

    tada za svako C AB vai


    f (xA , yA ) f (xC , yC ) f (xB , yB ).

    Dokaz. Vrednost funkcije f u taki C moemo zapisati na sledei nain:

    f (xC , yC ) = f (txA + (1 t)xB , tyA + (1 t)yB )


    = c(txA + (1 t)xB ) + d(tyA + (1 t)yB )
    = t(cxA + dyA ) + (1 t)(cxB + dyB ).

    Odatle imamo dva zakljuka:

    (i) f (xC , yC ) t(cxB + dyB ) + (1 t)(cxB + dyB ) = cxB + dyB = f (xB , yB ).

    (ii) f (xC , yC ) t(cxA + dyA ) + (1 t)(cxA + dyA ) = cxA + dyA = f (xA , yA ).

    
    Neka je S koveksan poligon zadat sledeim sistemom linearnih nejednaina:

    a1 x + b1 y c1
    a2 x + b2 y c2
    (2.1)
    ... ... ...
    an x + bn y cn .

    Za taku V sa osobinama

    (i) V S i

    (ii) V pripada preseku rubova dve razliite poluravni date nejednainama (2.1)

    kaemo da je ekstremna taka (vrh, teme) skupa S.

    Teorema 4 Neka S ogranien konveksan poligon. Tada f dostie svoju najveu (tj. najmanju) vrednost
    bar u jednom od temena datog poligona.

    Dokaz. Neka je {V1 , . . . , Vm } skup svih temena datog konveksnog poligona i pretpostavimo da je M teme
    u kojem f ne dostie manju vrednost nego u ostalim temenima. Pretpostavimo da postoji taka N S u
    kojoj je f (M ) < f (N ). Ako je taka N na rubu poligona, tvrdjenje sledi na osnovu prethodnog tvrdjenja.
    U suprotnom, pretpostavimo da N lei u unutranjosti datog poligona. Povucimo pravu p kroz take M

    3
    4 CHAPTER 2. LINEARNO PROGRAMIRANJE - INTERPRETACIJA U R2

    i N, i oznaimo presek ruba poligona i prave p sa L. Taka L pripada dui Vi Vj za neka dva temena sa
    ossobinom f (Vi ) f (Vj ). Tada je

    f (M ) < f (N ) f (L) f (Vj )

    to daje kontradikciju sa pretpostavkom da je M teme u kojem nije vrednost funkcije manja nego u
    nekom drugom temenu. 

    Teorema 5 Neka je f (x, y) = cx + dy i neka je S neogranien konveksan poligon. Ako f dostie svoju
    najveu (tj. najmanju) vrednost nad S, onda f ima tu vrednost bar u jednom od temena datog poligona.

    Primer 1 Odrediti maksimalnu i minimalnu vrednost funkcije


    f (x, y) = x 2y,

    f (x, y) = x + y,
    ako je
    x + y 5
    3x + y 0
    0 x 4
    0 y 3

    You might also like