Cursul 10 Recapitulare

of 32

  • date post

    26-Feb-2018
  • Category

    Documents

  • view

    224
  • download

    0

Embed Size (px)

Transcript of Cursul 10 Recapitulare

  • 7/25/2019 Cursul 10 Recapitulare

    1/32

    Recapitulare 1

    Coninutul

    cursului:

    Teorema fundamental a programrii liniare.Teoremele algoritmului simplex primal.

    Algoritmul simplex. Formule de schimbarea bazei.

    Determinarea unei baze primal admisibile. Metoda celor dou

    faze.Sisteme liniare de inegaliti. !ema Far"a#$Min"o%s"i.

    Dualitate &n programarea liniar. Teoreme de dualitate.

    Algoritmul simplex dual.

    'roblema transporturilor.

    'ostoptimizare #i programare liniar parametric.

    'rogramare liniar &n numere &ntregi.

  • 7/25/2019 Cursul 10 Recapitulare

    2/32

    Recapitulare (

    Notaii i cteva defniiiA x b =

    unde reprezint )ectorul necunoscutelor.

    *otm+

    Fie+ #i considerm sistemul+,m n mA b R Rnx R

    ( )

    ( )

    1 2

    1 2

    , , , linia '' '' a matricei ;

    , , , coloana '' '' a matricei .

    i i i in

    j

    j j mj

    A a a a i A

    A a a a j A

    =

    =

    L

    L f

    1, 1, .

    nj

    i i j

    jA x b A x b i m A x b

    = = = = =,onsiderm ( ) .rang A m n= Matricea de baz ( )1 2 ... .mss sB A A A=

    'artiionarea matricei+ ( ) .A B R= M *otaii+{ }1 2, ,..., ,ms s s=B

    { }1,2,..., \ .n=R B

    'artiionarea )ariabilei+ , .n

    xx x

    x

    =

    R

    B

    R

  • 7/25/2019 Cursul 10 Recapitulare

    3/32

    Recapitulare -

    1 1A x b B x R x b x B b B R x = + = = B R B R

    ectorul se nume#te soluiea sistemului dacnv R .A v b =

    / soluie a sistemului este numit soluie de baz0 daccomponentele ei diferite de zero corespund unor coloane liniar

    independente ale matricei A.

    Deoarece rang(A)= m0 cel mult m componente ale unei soluii debaz pot fi nenule. Dac soluia de baz are exact m componentenenule0 ea se nume#te nedegenerat &n caz contrar ea se nume#tedegenerat.

    'entru orice baz B0 se poate obine o soluie de baz+

    1B bvv

    v

    = = 0B

    B

    RR

  • 7/25/2019 Cursul 10 Recapitulare

    4/32

    Recapitulare 2

    Probleme de optimizare

    liniarFie #in

    R . R

    Tipuri de restricii &n raport cu felul problemei de optimizare+

    minimizare

    concordant

    x

    f

    neconcordant

    x

    f

    maximizare

    concordant

    x

    f

    neconcordant

    x

    f

  • 7/25/2019 Cursul 10 Recapitulare

    5/32

    Recapitulare 3

    Forma general:,onine toate tipurilede restricii #i )ariabile care pot aprea.

    { }1 1 2 2 3 3

    11 1 12 2 13 3 1

    21 1 22 2 23 3 2

    31 1 32 2 33 3 3

    1 3

    concordante

    egalitate

    necon

    inf

    n rapo

    cordante

    rt cu

    c x c x c x

    A x A x A x b

    A x A x A x b

    A x A x A x b

    x x

    + +

    + + + + = + +

    0 0

    f

    Datele problemei+ , , , 1 3, 1 3.i j jim n nm

    ij i jA b c i j

    R R R

    *ecunoscutele problemei sunt grupate &n trei )ariabile )ectoriale+

    ,1 3,jn

    jx j R1

    2

    3

    are componente nenegative;

    oarecare;

    are componente nepozitive.

    x

    x

    x

  • 7/25/2019 Cursul 10 Recapitulare

    6/32

    Recapitulare 4

    Forma standard:

    ,onine restricii egalitate#i )ariabile nenegati)e.

    { }inf , 0c x A x b x = f

    Datele problemei+ , , .m n m nA b c R R R

    Forma canonic:

    ,onine restricii concordante#i )ariabile nenegati)e.

    { }inf , 0c x A x b x f

    Datele problemei+ , , .m n m n

    A b c R R R

  • 7/25/2019 Cursul 10 Recapitulare

    7/32

    Recapitulare 5

    Forma mixt:,onine restricii concordante #i egalitate0 #i )ariabile nenegati)e.

    1 1

    2 2

    inf , 0A x b

    c x xA x b

    =

    f

    Datele problemei+

    1 1

    2 2

    1 1

    2 2

    ,

    , .,

    m n m

    n

    m n m

    A b

    cA b

    R R

    RR R

  • 7/25/2019 Cursul 10 Recapitulare

    8/32

    Recapitulare 6

    Teorema undamental aprogramri liniare,onsiderm problema de programare liniar &n forma standard+

    { }inf | ,c x A x b x = 0f

    7'8

    Fr a restr9nge generalitatea0 presupunem+ ( ) .rang A m n= ,kR

    1 ,k kY B A= 0

  • 7/25/2019 Cursul 10 Recapitulare

    11/32

    Recapitulare 11

    Lema (substituiei): Fie nesinular i

    !ectorul "onsiderm matricea#( )1 2 mss s m mB A A A = L R

    { }1 2, , ,..., .k m

    mA k s s s =BR

    ( )1 1 1 .mr r

    ss ks sAB A A A A +

    =% L L

    $otm !ectorul ( )1 1 2, , ..., .k k

    k k mk Y B A y y y= = f

    %u loc urmtoarele afirmaii#

    .

    &entru a!em#

    ( )det 0 0, .rk rB y unde r loc s =% B

    0,rky ( )1 1rB E B = %

    unde 1, 1,11

    ,..., , , ,...,r k r k k mk

    rk rk rk rk rk

    y yy y

    y y y y y

    + =

    f

    ( ) ( )1 1 1

    1

    ,

    10

    ik

    rk

    r r mr

    rk

    y

    y

    E e e e e

    y

    +

    = =

    O M M

    L L L

    L L M O M

    L L L

    M M O1 .i me este vector unitar cu in pozitia i R

  • 7/25/2019 Cursul 10 Recapitulare

    12/32

    Recapitulare 1(

    Teorem (schimbarea bazei): Fie o baz

    primal admisibil. &resupunem c exist astfel nct

    i !ectorul are cel puin un element poziti!.

    Dac aleem indicele astfel nct

    ( ) 0k kz c >,kR1k kY B A=

    ( ), ,r rs loc s r =BB

    1min 0 ,ir ik

    i mrk ik

    xxy

    y y

    = >

    ( )1 2 mss sB A A A= L

    atunci, matricea este o baz primal

    admisibil, pentru care

    ( )1 1 1 mr r ss ks sAB A A A A +=% L L1 1 .z c B b c B b z = =% %%

    BB

  • 7/25/2019 Cursul 10 Recapitulare

    13/32

    Recapitulare 1-

    Paii algoritmului simplex primal 'asul ;. Se determin 7dac exist ,k

    Y 0

    kR 0k kz c >( ), ,r rs loc s r =B

    1min 0 .ir ik

    i mrk ik

    xx yy y = >

    \ ,rs k

    B B A A=% U( )1 1rB E B

    = % #i se re)ine la 'asul 1.

    ,z

  • 7/25/2019 Cursul 10 Recapitulare

    14/32

    Recapitulare 12

    Formule pentru sc!imbarea bazeiRecalcularea elementelor din algoritmul simplex &n urma schimbrii uneibaze se face cu a>utorul !emei substituiei.

    aloarea nou Formul de calcul cu )alori )echi

    *otm+ ( )1 11

    i mijj m

    B

    = ( )1 11

    ij i mj m

    B

    = %%

    pentru 1, , , 1, ;

    pentru 1, .

    ik rj

    ij ij

    rk

    rj

    rj

    rk

    yi m i r j m

    y

    j my

    = = =

    = =

    %

    %

    ( )1 1,rB E B = %A)em+ de unde rezult+

  • 7/25/2019 Cursul 10 Recapitulare

    15/32

    Recapitulare 13

    ( ) ( )1 1

    1

    10

    r r

    ik ik i r

    rk rk i

    r r

    rk rk

    x B b E B b E x

    y yx x

    y yx

    x xy y

    = = = =

    = =

    %%

    O M M M

    ML L L

    MM O M M

    L L LM

    M M O M

    ( )

    pentru ;

    unde pentru .

    iki i r

    rk

    rr

    rk

    yx x x i ry

    xx r loc k k

    y

    =

    = =

    %

    %% B

    alorile soluiei de baz+

  • 7/25/2019 Cursul 10 Recapitulare

    16/32

    Recapitulare 14

    ,omponentaj+ ( ) , 1 .rj

    j j k k

    rk

    u u z c j m

    y

    = %

    alorile pentru multiplicatorii simplex+

    'entru matricea 1 ,Y B A= % %pentru 1, , ;

    1, .

    ikij ij rj

    rk

    rj

    rj

    rk

    yy y y i m i r

    y

    y

    y j ny

    = =

    = =

    %

    %

    aloarea funciei obiecti)+( )k k

    r

    rk

    z cz z x

    y

    = %

    aloarea costurilor reduse+ ( ) ( )

    , 1 .k k rj

    j j j j

    rk

    z c yz c z c j n

    y

    = %

  • 7/25/2019 Cursul 10 Recapitulare

    17/32

    Recapitulare 15

    "eterminarea unei baze primaladmisibile,onsiderm problema de programare liniar &n forma standard+{ }inf | ,c x A x b x = 0

    f

    7'8

    , .,,m n m nbA b c 0R R Runde

    { }min | , ,a a a

    m

    x A x x b x x

    + = e I 0 0

    f

    Acestei probleme &i asociem problema artificial+

    7'a8( )1,...,1 ,m= e

    f

    R ( )1 2, ,..., ,a m

    n n n mx x x x+ + += f

    Runde

    iar Im este matricea unitate de ordinul m.

    Teorem. Dac !aloarea minim a problemei 7'a80 atunci

    problema iniial7'8nu are soluie.

    0,az >

    Teorem. Dac atunci i B este o

    baz primal admisibil a problemei iniiale7'8.{ }1,..., ,n n m + + = B 0az =

  • 7/25/2019 Cursul 10 Recapitulare

    18/32

    Recapitulare 16

    Teorem. Dac !aloarea minim a lui 7'a8 este i exist

    pentru care atunci,

    i restricia i0 din 7'8 este o combinaie liniar de celelalte restricii.

    0az = 0 ,n i+ B( )

    0 0 00, 1, , ,i jy j n i loc n i= = = +B ( ) 1rang A m

    Teorem. Dac !aloarea minim a lui 7'a8este i exist

    pentru care atunci, se poate

    efectua o sc'imbare de baz prin care !ectorul unitar din B s fie nlocuit

    de coloana Ak

    .

    0az = 0 ,n i+ B( ) { }

    00 0, 1,..., , 0,i ki loc n i k n y= + B

    0ie

    Observaie. Dac toate )ariabilele artificiale au )aloarea zero =inclusi) cele care au mai rmas &n baz.

    0,az =

    ariabilele