Download - Cursul 10 Recapitulare

Transcript
  • 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 artificiale din bazcare au )aloarea zero0 pot fi+

    ariabilele artificiale din bazcare au )aloarea zero0 pot fi+

    eliminate &mpreuncu restricia asociat.eliminate &mpreun

    cu restricia asociat.

    sau

    &nlocuite cu o )ariabila problemei date.

    &nlocuite cu o )ariabila problemei date.

  • 7/25/2019 Cursul 10 Recapitulare

    19/32

    Recapitulare 1:

    #etoda celor dou aze

    Faza 1. Se rezol) 7'a8

    cu baza iniial Im.

    0az =

    7'8 nu aresoluie.

    nu

    0

    n i

    + B

    Faza (. Se rezol) 7'8cu baza admisibil B.

    00

    i jy =1,j n =

    Se elimin restricia i0Se &nlocuie#te cu0n i

    x + kx

    da

    da da

    nu

    nu

    7'8 are optiminfinit.

    7'8 are optim finit.TO!

    TO!

  • 7/25/2019 Cursul 10 Recapitulare

    20/32

    Recapitulare (;

    "egenerare i ciclare

    Descre#terea funciei obiecti)+

    ( )k kr

    rk

    z

    xz

    c

    z y

    = %

    Metoda perturbrii 7A. ,harnes0 1:3(8

    ( ){ } ( )1

    inf , cu , 0.n

    j j

    j

    c x A x b x b b A =

    = = + >0f

    !ropoziia ". Fie B " (A1, # ,Am) o baz primal admisibil. %tunci exist

    astfel nct0B > ( ) ( ) ( )1 0, 0, .Bx B b = >

    0rx

    !ropoziia #. Fie B primal admisibil n condiiile (eoremei de sc'imbare a

    bazei i %tunci, astfel nct criteriul de

    ieire din baz este ndeplinit pentru un sinur indice( ) ( )0, 0, .Bx > ' 0 >

    ( ), 0, ' $r

    ( ) ( )1min 0 .

    r i

    iki m

    rk ik

    x xy

    y y

    = >

  • 7/25/2019 Cursul 10 Recapitulare

    21/32

    Recapitulare (1

    $ema Far%asin%o's%iFie ,onsiderm urmtoarele sisteme liniare+

    A x bx = 0 0

    A u

    b u

  • 7/25/2019 Cursul 10 Recapitulare

    22/32

    Recapitulare ((

    "ualitate (n optimizarea liniar

    { }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

    inf

    n raport 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

    { }1 1 2 2 3 3

    11 1 21 2 31 3 1

    12 1 22 2 32 3 2

    13 1 23 2 33 3 3

    1 3

    %up

    n raport cu

    b u b u b u

    A u A u A u cA u A u A u c

    A u A u A u c

    u u

    + +

    + + + + =

    + + 0 0

    f

    f

    f

    f

    'roblema primal+

    'roblema dual+

    7 ' 8

    7 D 8

    """""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""

  • 7/25/2019 Cursul 10 Recapitulare

    23/32

    Recapitulare (-

    Reguli de asociere a problemelor duale

    ?nei probleme de minimizare &i corespunde o problem de

    maximizare0 #i reciproc. ,oeficienii din funcia obiecti) a unei probleme de)in

    coeficienii termenului liber &n cealalt problem0 #i reciproc. Matricea restriciilor dintr$o problem este matricea transpus

    din cealalt problem0 #i reciproc.

    Fiecrei restricii dintr$o problem &i corespunde o )ariabil &ncealalt problem0 #i reciproc.

    Relaia de asociere este urmtoarea+ unei restricii concordante &i corespunde o )ariabil nenegati)

    #i reciproc

    unei restricii egalitate &i corespunde o )ariabil oarecare 7frcondiii de semn80 #i reciproc unei restricii neconcordante &i corespunde o )ariabil nepoziti)

    #i reciproc.

    ( )0 ,

    ( )0 ,

  • 7/25/2019 Cursul 10 Recapitulare

    24/32

    Recapitulare (2

    Teoreme de dualitate

    Fie , ,m n m nA b c R R R #i definim domeniile de admisibilitate+

    { } { }| , , | ,n mx A x b x u A u c u= = 0 0R RP D f

    ,onsiderm perechea de probleme 7canonice8 duale+

    { }

    { }

    inf | ...........................

    %up | ...........................

    c x x

    b u u

    P

    D

    f

    f

    7 ' 8

    7 D 8

    Teorem 7dualitate slab8. Dac domeniile de admisibilitate

    atunci are loc relaia#

    , , P D, ,x u P D .c x b u

    Teorem 7dualitate tare8. Dac domeniile de admisibilitate

    i astfel nct atunci, este soluie

    optim pentru 7'8 i este soluie optim pentru 7D8.

    , , P D, ,x u P D ,c x b u = x

    u

  • 7/25/2019 Cursul 10 Recapitulare

    25/32

    Recapitulare (3

    Teorema 7fundamental a dualitii8. Fiind dat perec'ea de probleme duale7'8 i 7D8 doar una din urmtoarele afirmaii are loc#

    a* i +n cazul acesta i soluii

    optime pentru 7'8, respecti! 7D8, astfel nctb* i

    c* i sau i +n cazul acesta problema

    care are soluii admisibile are optimul infinit.

    . P D

    .c x b u = % %

    ,x u % %P D

    .= = P D

    = P D .= P D

    Teorem 7tare a ecarturilor complemetare8. Dac

    atunci, pentru 7'8 i 7D8 exist soluiile optime respecti! astfel nct

    , , P D, ,x u% %

    ( ) ( ), .A x b u c A u x + > + >0 0% % % %f

    Teorem 7slab a ecarturilor complemetare8. Fie%tunci,

    , .x u P Dx este soluie optim pentru 7'8

    u este soluie optim pentru 7D8

    ( )

    ( )

    0,

    0.

    u A x b

    x c A u

    =

    =

    f

  • 7/25/2019 Cursul 10 Recapitulare

    26/32

    Recapitulare (4

    )lgoritmul simplex dualMatricea de bazBse numete dual admisibil, dac

    1c B A c B

    Teorem (optim): Dac baza B esteprimal idual admisibil, atunci eaeste optimpentru problemele 7'8 i 7D8.

    Teorem (domeniu vid). FieB o baz dual admisibil. Dac exist o

    component pentru care atunci problema 7'8

    nu are soluie.

    0,ix < 0, 1, ,ijy j n =

    Teorem (schimbarea bazei): Fie o baz dual

    admisibil i componenta pentru care exist( )1 2 mss sB A A A= L

    0,rx < 0.rjj cu y

  • 7/25/2019 Cursul 10 Recapitulare

    27/32

    Recapitulare (5

    Paii algoritmului simplex dual 'asul ;. Se determin 7dac exist

  • 7/25/2019 Cursul 10 Recapitulare

    28/32

    Recapitulare (6

    )lgoritmul simplex adaptatpentru problema de transport

    x11 x12 x1n

    x21 x22 x2n

    xm1 xm2 xmn

    a1

    a2

    am

    b1 b2 bn

    m Depozite

    n @eneficiari

    Marf disponibil

    Marf solicitat

    c11 c1n

    cm1 cmn

    Matriceacosturilor

  • 7/25/2019 Cursul 10 Recapitulare

    29/32

    Recapitulare (:

    1 1

    minm n

    ij ij

    i j

    c x= =

    &n raport cu

    1

    , 1, ,n

    ij i

    j

    x a i m=

    = =

    1

    , 1, ,m

    ij j

    i

    x b j n=

    = =0, 1, , 1, .

    ijx i m j n = =

    Forma standard a problemei de transport+

    Teorem. 7'T8 are o soluie admisibil dac i numai dac

    7'T8

    1 1

    0, 1, ; 0, 1, ; .m n

    i j i j

    i j

    a i m b j n a b= =

    = = = Teorema. anul matricei este " m + n 1.

    Determinarea unei soluii iniiale de baz+

    Metoda colului de *

    Metoda costului minim

    Testul de optimalitate Schimbarea soluiei de baz

  • 7/25/2019 Cursul 10 Recapitulare

    30/32

    Recapitulare -;

    Reoptimizare,onsiderm problema+ { }inf | ,c x A x b x = 0f

    ( ), , , .m n m n

    A b c rang A m n

    =