+ All Categories

Download - Curs 2009-2010

Transcript
  • Tehnici de optimizare - Cursul 1 1

    Istoric

    Dificulti de abordare i/sau rezolvare

    Planul de nvmnt (= 10 sptmni)

    TEHNICI DE OPTIMIZARE

    ANTON BTTORESCU

  • Tehnici de optimizare - Cursul 1 2

    TEHNICI DE OPTIMIZARE

    CURS = 2 ORE / SPTMN

    SEMINAR = 1 OR / SPTMN

    FORMA DE EXAMINARE: examen ! (scris)

    2 subiecte de teorie:

    enunuri cu demonstraii;

    enunuri descriptive.

    1 exerciiu de seminar (cu subpuncte)

  • Tehnici de optimizare - Cursul 1 3

    Coninutul cursului:

    Modele de optimizare liniar i programe software.

    Algoritmul simplex primal i algoritmul simplex dual.

    Interpretarea economic a valorilor i soluiilor.

    Metode de partiionare i relaxare.

    Metode pentru probleme de optimizare neliniar.

  • Tehnici de optimizare - Cursul 1 4

    Bibliografie

    A. tefnescu, C. Zidroiu, "Cercetri Operaionale", Ed. Did. i Pedagogic, Bucureti, 1981.

    H. Karloff, Linear Programming, Progress in Theoretical Computer Science, Birkhuser, 1991, Berlin.

    A. Bttorescu, "Metode de optimizare liniar", Ed. Universitii din Bucureti, 2003.

    V. Preda, M. Bad, "Culegere de probleme de cercetri operaionale", Tipografia Universitii din Bucureti, 1978.

    http://www.ilog.com/ www.maximalsoftware.com

  • Tehnici de optimizare - Cursul 1 5

    Exemplu optimizare neliniar( ) ( )( )( ) ( ) 4 3 2: , 2 1 3 5 7 5 31 30f f x x x x x x x x x = + = + + R R

  • Tehnici de optimizare - Cursul 1 6

    [ ] ( ) 4 3 2: 0, 5.6 , 7 5 31 30f f x x x x x = + + R

  • Tehnici de optimizare - Cursul 1 7

    Exemplu optimizare liniar

    { }2 3 , unde min maxoptim x y optim+ = Cu ndeplinirea condiiilor:

    S se determine:

    48 2 35 3 15

    2 102 16

    x yx yx yx y

    x y

    + +

    +

    +

  • Tehnici de optimizare - Cursul 1 8

    Rezolvare grafic

  • Tehnici de optimizare - Cursul 1 9

    Notaii i cteva definiii

    Vom nota cu o matrice cu m linii i n coloane: m nA R

    ( )11 12 1

    21 22 211

    1 2

    n

    n

    i mijj n

    m m mn

    a a a

    a a aA a

    a a a

    = =

    , 1 ,1 ,ija i m j n Runde,

    Transpusa matricei A o vom nota cu

    .

    n mA Rf

    Mulimea matricelor de aceeai dimensiune formeaz un spaiu vectorial peste corpul numerelor reale.

    ( ) ( )1 11 1

    , , , ,m n

    i m i mij ij ijj n j n

    A B A B a b B b

    + = + =R R

  • Tehnici de optimizare - Cursul 1 10

    Produsul matricelor: este matricea:,m k k nA B R R

    1, , 1 , 1 .

    km n

    ij il ljl

    A B C c a b i m j n=

    = = R

    Determinantul unei matrice ptratice este numruln nA R

    ( ) ( ) ( ) ( )1 1 2 2detn

    n nA a a a

    = S

    Dac matricea A se numete nesingular, iar n acest caz, exist o unic matrice A-1 numit matrice invers:

    det 0,A

    1 1

    1 0 00 1 0

    0 0 1

    n n

    nA A A A

    = = =

    I

    R

  • Tehnici de optimizare - Cursul 1 11

    Un vector coloana este considerat ca fiind o matriceiar transpusa acesteia este un vector linie.

    nv R1,

    nv R

    ( ) ( )1

    21 2 1 2, , , , , , ,n n

    n

    v

    vv v v v v v v v

    v

    = = =

    f f

    Produsul scalar a doi vectori1

    , , .

    nn

    i ii

    x y x y x y y x=

    = = R f f

    pentru orice 1, ,

    pentru orice 1, ni i

    i i

    x y x y i n

    x y x y i n y x +

    = = =

    = R

    Definim relaiile:

    n particular, 0, 1, .n ix x i n =0 R

  • Tehnici de optimizare - Cursul 1 12

    Sisteme de ecuaii liniare

    11 1 12 2 1 1

    21 1 22 2 2 2

    1 1 2 2

    n n

    n n

    m m mn n m

    a x a x a x ba x a x a x b

    A x b

    a x a x a x b

    + + + = + + + =

    = + + + =

    Fie: i considerm sistemul de ecuaii liniare:,m n mA b R R

    nx Runde reprezint vectorul necunoscutelor.Notm: ( )

    ( )1 2

    1 2

    , , , linia '' '' a matricei ;

    , , , coloana '' '' a matricei .

    i i i in

    jj j mj

    A a a a i A

    A a a a j A=

    =

    f

    1, 1, .

    nj

    i i jj

    A x b A x b i m A x b=

    = = = =

  • Tehnici de optimizare - Cursul 1 13

    Teorema Kronecker-Capelli :

    Ecuaii principale, respectiv variabile principale.

    Ecuaii secundare, respectiv variabile secundare.

    Prin eliminarea ecuaiilor secundare, considerm:

    Pentru m = n, avem soluia unic:

    Pentru m < n, avem o infinitate de soluii.

    Exist m coloane liniar independente ale matricei A, care formeaz

    o matrice de baz:

    Restul coloanelor formeaz matricea R.

    ( ) ( ) { }min ,rang A rang A b r m n= =

    ( ) .rang A m n= 1

    .x A b=

    ( )1 2 ... .mss sB A A A=

  • Tehnici de optimizare - Cursul 1 14

    Partiionarea matricei: ( ).A B R= Notm mulimea de indici corespunztoare coloanelor lui B cu

    { }1 2, ,..., ,ms s s=Biar mulimea de indici corespunztoare coloanelor lui R cu

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

    Partiionarea variabilei n care,, ,nx

    x xx

    =

    R

    B

    R

    ( ) ( )1 2, ,..., m mi s s six x x x x= = RB B f variabile de baz (principale)( ) n mj jx x = RR R variabile secundare

  • Tehnici de optimizare - Cursul 1 15

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

    Vectorul se numete soluie a sistemului dacnv R .A v b =

    O soluie a sistemului este numit soluie de baz, dac componentele ei diferite de zero corespund unor coloane liniar independente ale matricei A.

    Deoarece rang(A) = m, cel mult m componente ale unei soluii de baz pot fi nenule. Dac soluia de baz are exact m componente nenule, ea se numete nedegenerat; n caz contrar ea este degenerat.

    Pentru orice baz B, se poate obine o soluie de baz: 1B bv

    vv

    = = 0

    B B

    R R

  • Tehnici de optimizare - Cursul 2 1

    Probleme de optimizare liniar

    maximizare

    concordant neconcordant

    O problem de optimizare const din minimizarea sau maximizarea unei anumite funcii - numit funcie obiectiv - n prezena unor restricii care trebuie satisfcute.

    ( ){ } ( ){ }inf | sup |f x x f x x = P PEste suficient s studiem doar probleme de minimizare, deoarece

    n R . RFie iTipuri de restricii n raport cu felul problemei de optimizare:

    ,x f ,x f ,x f ,x f

    minimizare

    concordant neconcordant

  • Tehnici de optimizare - Cursul 2 2

    Forma general:

    Conine toate tipurile de restricii i variabile care pot aprea.

    { }1 1 2 2 3 311 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 bA x A x A x bA x A x A x b

    x x

    + +

    + + + + =

    + + 0 0

    f f f

    Datele problemei: , , , 1 3, 1 3.i j jim n nmij i jA b c i j R R RNecunoscutele problemei sunt grupate n trei variabile vectoriale:

    ,1 3,jnjx j R1

    2

    3

    are componente nenegativeoarecare

    are componente nepo

    ;

    ;

    zitive.

    x

    x

    x

  • Tehnici de optimizare - Cursul 2 3

    Forma standard:

    Conine restricii egalitate i variabile nenegative.

    { }inf , 0c x A x b x = fDatele problemei: , , .m n m nA b c R R R

    Forma canonic:

    Conine restricii concordante i variabile nenegative.

    { }inf , 0c x A x b x fDatele problemei: , , .m n m nA b c R R R

  • Tehnici de optimizare - Cursul 2 4

    Forma mixt:

    Conine restricii concordante i egalitate, i variabile nenegative.

    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 bc

    A b

    R RR

    R R

    Formele problemelor de programare liniar sunt echivalente!

    Alegerea formei n funcie de necesiti:

    forma standard pentru algoritmi;

    forma canonica pentru dualitate.

  • Tehnici de optimizare - Cursul 2 5

    Transformri echivalente:

    Sensul unei inegaliti se schimb prin nmulire cu 1. Transformarea unei inegaliti ntr-o ecuaie:

    y se numete variabil ecart (slack variable). Transformarea unei ecuaii n inegaliti:

    O variabil nepozitiv

    O variabil oarecare

    , 0x x y

    yx x y

    + =

    =

    f f

    f f

    xx

    x

    =

    f

    f

    f

    0 0.x x x =

    ,

    unde 0, 0.x x x x

    x x

    +

    +

    =

    R

  • Tehnici de optimizare - Cursul 2 6

    Teorema fundamental a programri liniareConsiderm problema de programare liniar n forma standard:

    { }inf | ,c x A x b x = 0f (P)Fr a restrnge generalitatea, presupunem: ( ) .rang A m n= =f

    este evident o soluie de baz.

    Dac sunt liniar independente, atunci v este o soluie admisibil de baz.

    0k v= = 01.k { }1 2, ,..., kA A A

    Considerm: Rezult:( )1 2, , ,..., ,0,...,0 .n ky y y y y =R f,i .y A y =0 0

    Definim vectorul: ( ) , .x v y = + RAvem: ( ) ( ) ,A x A v y A v A y A v b = + = + = =deci, este o soluie a sistemului pentru orice( )x A x b = . R

    Dac sunt liniar dependente,astfel nct:

    1, 1, , 0,

    k

    i ii

    y i k y=

    = >R

    1.

    k iii

    A y=

    = 0{ }1 2, ,..., kA A A

  • Tehnici de optimizare - Cursul 2 8

    Deoarece avem:( ) 0, 1, ,ix i k n = = +( ) ( ) 0, pentru 1, .i i ix x v y i k = + =0

    dac 0, dac 0.i ii ii i

    v vy yy y

    > > =

    >

    <

  • Tehnici de optimizare - Cursul 2 9

    nv RFie o soluie optim a problemei (P) cuRaionm analog ca n cazul precedent:

    0, 1, .iv i k> =

    Dac sunt liniar dependente, exist un interval astfel nct este soluie admisibil.

    { }1 2, ,..., kA A A[ ] ( )', '' x v y = +

    ( )c v c x c v c y = + f f f fDin relaia: [ ], avem 0.c y f

    Observaie: Deoarece 0, 0 0.c y < > =f

    n caz contrar, lund contradicie!

    { } 0,sign c y c y =

  • Tehnici de optimizare - Cursul 2 10

    n general, mulimea soluiilor admisibile a problemei (P) este infinit, spre deosebire de cea a soluiilor admisibile de baz, care are cel mult elemente. Importana teoremei fundamentale a programrii liniare const n aceea c, pentru determinarea unei soluii optime, dac ea exist, cutarea este redus de la o mulime infinit, la una finit, fiind suficient investigarea doar a soluiilor de baz.

    Cnm

  • Tehnici de optimizare - Cursul 2 11

    Teoremele algoritmului simplexConsiderm problema de programare liniar n forma standard:

    { }inf | ,c x A x b x = 0f (P)( ), , , .m n m nA b c rang A m n =

  • Tehnici de optimizare - Cursul 2 12

    n raport cu baza B, soluia de baz este:1x x B b

    xx

    = = =

    0 0B

    R

    Matricea de baz B se numete primal admisibil, dac 1 .B b 0Funcia obiectiv se poate exprima astfel:

    ( ) ( )j

    jj

    jj j j j j

    j j

    z c x c x c x c x Y x c x

    c x c Y c x z z c x

    = = + = + =

    = =

    f f f f f

    f f

    B B R R B R RR

    B BR R

    unde am notat: , ,1 .jjz c x z c Y j n= = B Bf f

    Teorem (optim): Fie B o baz primal admisibil. Dac ( ) 0,j jz c pentru orice atunci baza B este optim.,j RDemonstraie. Pentru orice soluie admisibil avem:nv R

    ( ) .j j jj

    z c v z z c v z

    = = R

    f

  • Tehnici de optimizare - Cursul 3 1

    Teoremele algoritmului simplexConsiderm problema de programare liniar n forma standard:

    { }inf | ,c x A x b x = 0f (P)( ), , , .m n m nA b c rang A m n =

  • Tehnici de optimizare - Cursul 3 2

    Soluia de baz corespunztoare lui B :1x x B b

    xx

    = = =

    0 0B

    R

    Matricea de baz B se numete primal admisibil, dac 1 .B b 0Funcia obiectiv se poate exprima astfel:

    ( ) ( )j

    jj

    jj j j j j

    j j

    z c x c x c x c x Y x c x

    c x c Y c x z z c x

    = = + = + =

    = =

    f f f f f

    f f

    B B R R B R RR

    B BR R

    unde am notat: , ,1 .jjz c x z c Y j n= = B Bf f

    Teorem (optim): Fie B o baz primal admisibil. Dac ( ) 0,j jz c pentru orice atunci baza B este optim.,j RDemonstraie. Pentru orice soluie admisibil avem:nv R

    ( ) .j j jj

    z c v z z c v z

    = = R

    f

  • Tehnici de optimizare - Cursul 3 3

    Teorem (optim infinit): Fie B o baz primal admisibil. Dac exist un indice astfel nct i atunci problema (P) are optimul (-)infinit.

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

    Demonstraie. Fie Definim vectorul:

    ( ) ( )( ) ( )( )

    , undek

    loc k n mloc k

    x x Yx e

    x e

    = =

    =

    R

    R

    B

    R

    R

    este vector unitar.

    , 0. R

    Se verific fr dificultate c: ( )( ) ( ) ( )

    ,

    .

    k k

    x

    A x B x R x b A A b

    = + = + =

    0

    B R

    Rezult, este soluie admisibil pentru (P).( )0, x Funcia obiectiv este: ( ) ( ) ( )

    ( ) ( )k k k kc x c x c x

    c x Y c z z c

    = + =

    = + =

    B B R R

    B

    f f f

    f

    Deoarece rezult:( ) 0,k kz c > ( )lim .c x = f

  • Tehnici de optimizare - Cursul 3 4

    Observaie.

    n condiiile Teoremei de optim infinit, baza B definete o soluie nenul a sistemului omogen

    ( ),k

    n

    loc k

    v Yv v

    v e

    = =

    = R

    B

    R

    R

    { }, :A x x = 0 0

    Acest vector reprezint o direcie (raz) de-a lungul creia soluiile admisibile

    ( ) xx v = + 0

    B

    Rsunt nemrginite.

    Vectorul v se mai numete direcia spre ()infinit, i mpreun cu soluia de baz, pentru descrie o muchie nemrginit a domeniului de admisibilitate.

    [ )0, ,

  • Tehnici de optimizare - Cursul 3 5

  • Tehnici de optimizare - Cursul 3 6

    Lema (substituiei): Fie nesingular i vectorul Considerm matricea:

    ( )1 2 mss s m mB A A A = R{ }1 2, , ,..., .k m mA k s s s =BR

    ( )1 1 1 .mr r ss s k sAB A A A A += Notm vectorul ( )1 1 2, ,..., .k k k k mkY B A y y y= = fAu loc urmtoarele afirmaii:

    .

    Pentru avem:

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

    rky ( )1 1rB E B =

    unde 1, 1,1 1,..., , , ,...,r k r kk mkrk rk rk rk rk

    y yy yy y y y y

    +

    =

    f

    ( ) ( )1 1 11

    ,

    10

    ik

    rkr r m

    r

    rk

    yy

    E e e e e

    y

    +

    = =

    1 .i me este vector unitar cu in pozitia iR

  • Tehnici de optimizare - Cursul 3 7

    Demonstraie. Din notaia rezult:1k kY B A=1

    jm

    sk kjk

    jA B Y A y

    =

    = =

    Prin absurd, coloanele lui liniar dependente. Contradicie!0rky = B

    Prin absurd, are coloanele liniar dependente. Deci, existdet 0B =

    1, 0,

    m

    j jj

    =

    >R astfel nct1,

    .

    jm

    s

    jr

    kr

    j jA A

    =

    + = 0

    Avem: n caz contrar obinem Contradicie!det 0.B =nlocuind pe Ak i regrupnd termenii, obinem:

    ( )1,

    ,j r

    ms s

    j jk r rk rj j r

    A y A y =

    + + = 0

    adic o combinaie liniar de coloane ale matricei B care este egal cu zero i deci toi coeficienii trebuie s fie nuli. Dar, Contradicie!0.rk ry

    Fie det 0.B

    Fie acum 0.rky

    0.r

  • Tehnici de optimizare - Cursul 3 8

    Coloanele lui B i coincid pentru Avem deci,B .j r

    , .

    js jA B e j r=

    1

    jm

    skjk

    jA A y

    =

    =0,rky Deoarece din relaia rezult:

    1,

    1jrm

    s jks k

    j j r rk rk

    yA A A B

    y y

    =

    = + =

    Prin urmare, putem scrie:

    ( ) ( )1 1.r rB B E B E B = =

  • Tehnici de optimizare - Cursul 3 9

    Teorem (schimbarea bazei): Fie o baz primal admisibil. Presupunem c exist astfel nct i vectorul are cel puin un element pozitiv. Dac alegem indicele astfel nct

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

    ( ), ,r rs loc s r =BB

    1min 0 ,ir iki m

    rk ik

    xx yy y

    = >

    ( )1 2 mss sB A A A=

    atunci, matricea este o baz primal

    admisibil, pentru care

    ( )1 1 1 mr r ss ks sAB A A A A += )

    1 1.z c B b c B b z

    = = BBf f

    Demonstraie. Evident, Din Lema substituiei rezult c este o matrice nesingular.Trebuie artat c

    B0.rky >

    1.B b

    0

  • Tehnici de optimizare - Cursul 3 10

    ( ) ( )1 1r rB b E B b E x = = =

    1

    10

    ik iki r

    rk rki

    r r

    rk rk

    y yx x

    y yx

    x x

    y y

    = =

    0.rrk

    x

    yEvident, Dac 0, 0.rik i ik

    rk

    xy x yy

    <

    Dac 0

    0

    0, 0.ir rik i ik ikrk ik rk

    xx xy x y yy y y

    >

    > =

    14243

  • Tehnici de optimizare - Cursul 3 11

    innd seama c pentru avem obinem: k B ( ) ,loc k r=B ( ) ( )1 1r rz c B b c E B b c E x = = = = B B Bf f f

    ( )1

    , , , ,

    10

    i

    ik

    rk

    s k

    rk

    yy

    c c x

    y

    = =

  • Tehnici de optimizare - Cursul 3 12

    , , , ,i

    i

    s ik ks

    i r rk rk

    c y cc x

    y y

    = + =

    i i

    rs i s ik k

    i r i r rk

    xc x c y c

    y

    =

    r r

    rs r s rk

    rk

    xc x c y

    y+ =

    ( )1 1 0

    0

    .

    i i

    k

    m m

    r rs i s ik k k k

    i i rk rk

    z z

    x xc x c y c z z c z

    y y= =

    >

    = =

    14243123 14243

  • Tehnici de optimizare - Cursul 3 13

    Paii algoritmului simplex Pasul 0. Se determin (dac exist?!) o baz primal admisibil B i se

    calculeaz B-1. Pasul 1. Se calculeaz

    Pasul 2. (test de optimalitate) Dac atunci s-a obinut valoarea optim i soluia optim de baz STOP.

    Pasul 3. (test de optim infinit) Dac pentru care i atunci problema are optim (-)infinit. STOP.

    Pasul 4. (schimbarea bazei) Se alege cu i de determin astfel nct

    Se formeaz matricea se calculeaz inversa

    1 1, , , .x B b z c x Y B A z c c Y c = = = = B B

    f f f f f

    ,z c 0, .x x x= = 0B R

    k R 0k kz c > ,kY 0

    k R 0k kz c >( ), ,r rs loc s r =B1min 0 .ir iki m

    rk ik

    xx yy y

    = >

    \ ,rs kB B A A= U ( )1 1rB E B = i se revine la Pasul 1.

    ,z

  • Tehnici de optimizare - Cursul 3 14

    Formule pentru schimbarea bazei

    Fiecare iteraie a algoritmului simplex este caracterizat de inversa bazei primal admisibile B-1. 1

    1

    1

    1; ;;

    ;

    x B bz c x c B bY B Az c c

    u c Bb

    AY c

    u

    u c

    =

    = = =

    =

    =

    =

    =

    B B

    B

    Bf f

    f f f ff

    f f

    f

    f

    Componentele vectorului u se numesc multiplicatori simplex.Componentele lui z c se numesc costuri reduse.

    Recalcularea elementelor din algoritmul simplex n urma schimbrii unei baze se face cu ajutorul Lemei substituiei. (Sunt cunoscui indicii sr i k , precum i vectorul Yk .)

    Valoarea nou Formul de calcul cu valori vechi

  • Tehnici de optimizare - Cursul 3 15

    Notm: ( )1 11

    i mijj m

    B

    = ( )1 11

    ij i mj m

    B

    =

    pentru 1, , , 1, ;

    pentru 1, .

    rj ikij ij

    rk

    rjrj

    rk

    yi m i r j m

    y

    j my

    = = =

    = =

    Valorile pentru noua invers a matricei de baz:

    ( )1 1,rB E B = Avem:

    de unde rezult:

  • Tehnici de optimizare - Cursul 3 16

    ( ) ( )1 1

    1

    10

    r r

    ik iki r

    rk rki

    r r

    rk rk

    x B b E B b E x

    y yx x

    y yx

    x x

    y y

    = = = =

    = =

    ( ) pentru ;

    unde pentru .

    iki i r

    rk

    rr

    rk

    yx x x i r

    yx

    x r loc k ky

    =

    = =

    B

    Valorile soluiei de baz:

  • Tehnici de optimizare - Cursul 3 17

    ( ) ( )1 1, , , ,is k ru c B c c E B = = Bf f

    , , , ,i

    i

    i i r r

    ijs ik k

    j si r rk rk

    rj

    rj rks ij s ik k s rj s rj

    i r i r rk rk

    c y cu c

    y y

    yc c y c c c

    y y

    = + =

    = +

    Componenta j:

    ( ) , 1 .rjj j k krk

    u u z c j my

    =

    Valorile pentru multiplicatorii simplex:

  • Tehnici de optimizare - Cursul 3 18

    ( ) ( )1 1ik

    ij rjrk

    j j j jr r

    rj

    rk

    yy yy

    Y B A E B A E Yyy

    = = = =

    Pentru matricea coloana este: 1

    ,Y B A

    =

    , 1,j

    Y j n=

    pentru 1, , ;ikij ij rjrk

    rjrj

    rk

    yy y y i m i ry

    yy

    y

    = =

    =

  • Tehnici de optimizare - Cursul 3 19

    1

    1

    m

    j jj

    z c B b u b u b

    =

    = = = Bf f

    Valoarea funciei obiectiv:

    ( ) ( )1 1 1

    m m mrj k k

    j k k j j j rj jj j jrk rk

    z cz u z c b u b b

    y y

    = = =

    = =

    ( )k kr

    rk

    z cz z x

    y

    =

  • Tehnici de optimizare - Cursul 3 20

    ( )( )

    1

    1 1

    1 1

    j jj j j j

    m m

    rii ij j i k k ij j

    i i rk

    m mk k

    i ij j ri iji irk

    z c c B A c u A c

    u a c u z c a cy

    z cu a c a

    y

    = =

    = =

    = = =

    = = =

    =

    Bf f

    Valoarea costurilor reduse:

    ( ) ( ) , 1 .k k rjj j j jrk

    z c yz c z c j n

    y

    =

  • Tehnici de optimizare - Cursul 3 21

    Organizarea calculelor

    Tabloul simplex standard

    cj ck

    cB V.B x x j x k

    csi x si x i yij yik

    csr x sr x r yrj yrk

    z zj cj zk ck

    xB x Y B1 A

    z z c

    1i

    m

    s ii

    z c x=

    =

    1i

    m

    j j s ij ji

    z c c y c=

    =

  • Tehnici de optimizare - Cursul 3 22

    Tabloul simplex revizuit xB x B1

    z u

    cB V.B. x k

    csi x si x i ij yik

    csr x sr x r rj yrk

    z uj zk ck

    1i

    m

    s ii

    z c x=

    =

    1i

    m

    j s iji

    u c =

    =

    0kk k kz c u A c = >f

    1k kY B A=

  • Tehnici de optimizare - Cursul 3 23

    Regula dreptunghiului

    Linia pivotului se mparte la pivot:

    Coloana pivotului devine un vector unitar:

    Restul elementelor din tablou, se calculeaz dup regula dreptunghiului:

    Elementul se numete pivot. Restul elementelor le redenumim0,rky .ijt

    , 0, .rjrj

    rk

    tt j n

    y= =

    1i 0, 1, 1, .rk ikt t i m i r= = = +

    1, 1, ,,

    0, , .rj ik

    ij ijrk

    t t i m i rt t

    y j n j k = +

    = =

  • Tehnici de optimizare - Cursul 4 1

    Determinarea unei baze primal admisibileConsiderm problema de programare liniar n forma standard:

    { }inf | ,c x A x b x = 0f (P), .,,

    m n m nbA b c 0R R Runde

    { }min | , ,a a amx A x x b x x + = e I 0 0fAcestei probleme i asociem problema artificial:

    (Pa)( )1,...,1 ,m= e f R ( )1 2, ,..., ,a mn n n mx x x x+ + += f Runde

    iar Im este matricea unitate de ordinul m .

    Proprieti ale problemei (Pa) :

    matricea restriciilor:

    Im este o baz primal admisibil:

    are o soluie optim finit:

    ( ) ( ) ( ), ;m n mm mA rang A m n m + = < +I I R1 ;m b b

    = I 0

    10.

    ma a

    a n ii

    x z x x +=

    = 0 = ef

  • Tehnici de optimizare - Cursul 4 2

    Concluzie: (Pa) se poate rezolva cu algoritmul simplex.Fie B baza optim a problemei (Pa) iar mulimea indicilor de baz.BTeorem. Dac valoarea minim a problemei (Pa), atunci problema iniial (P) nu are soluie.

    0,az >

    Demonstraie. Prin absurd, dac (P) are o soluie admisibil, conform TFPL are i o soluie admisibil de baz.

    Fie B* baza corespunztoare. Ea este format doar din coloane ale matricei A !

    Avem: deci B* este baz primal admisibil i pentru (Pa), iar

    variabilele xa sunt secundare!

    Deci, (Pa) are o soluie admisibil (de baz), pentru care,

    Teorem. Dac atunci i B este o baz primal admisibil a problemei iniiale (P).

    { }1,..., ,n n m + + = B 0az =

    Demonstraie. Evident, B este format doar din coloane a matricei A.

    1*

    ,B b 0

    valoarea optim. Contradicie.0a a ax x z= =

  • Tehnici de optimizare - Cursul 4 3

    Teorem. Dac valoarea minim a lui (Pa) este i exist pentru care atunci,i restricia i0 din (P) 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

    Demonstraie. Notm: i( )1 11

    i mijj m

    B

    = ( ) 1 .i jY y B A= = Din ipotez,

    0 0 0 0 0 001 1,

    0 , 1, .m m

    i j i k kj i k kj i i i jk k k i

    y a a a j n = =

    = = = + =

    Deoarece B conine vectorul n B-1 vom avea0 ,ie0 0

    1.i i =Deci,

    0 001,

    , 1, ,m

    i j i k kjk k i

    a a j n=

    = = 0 001,

    ,

    m

    i i k kk k i

    A A=

    =

    adic, linia este combinaie liniar de celelalte linii. Deci,0i

    A ( ) 1.rang A m Sistemul fiind compatibil, rezult i

    0 001,

    .

    m

    i i k kk k i

    b b=

    =

  • Tehnici de optimizare - Cursul 4 4

    Observaie. Dac toate variabilele artificiale au valoarea zero ! inclusiv cele care au mai rmas n baz.

    0,az =

    Variabilele artificiale din bazcare au valoarea zero, pot fi:

    eliminate mpreuncu restricia asociat.

    Teorem. Dac valoarea minim a lui (Pa) este i exist pentru care atunci, se poate

    efectua o schimbare de baz prin care vectorul 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

    Demonstraie. Din Lema substituiei, ( )0 0 det 0.i ky B n plus, din formulele de schimbare a bazei, deoarece

    0

    1 1, 1, ,0

    .

    i ii

    x x i m B b B bx

    z z

    = = = =

    =

    0

    sau

    nlocuite cu o variabila problemei date.

  • Tehnici de optimizare - Cursul 4 5

    Metoda celor dou faze

    Faza 1. Se rezolv (Pa)cu baza iniial Im.

    0az =(P) nu are

    soluie.nu

    0n i + B

    Faza 2. Se rezolv (P)cu baza admisibil B.

    00i jy =

    1,j n =

    Se elimin restricia i0Se nlocuiete cu0n ix + kx

    da

    da da

    nu

    nu

    (P) are optim infinit.(P) are optim finit. STOP

    STOP

  • Tehnici de optimizare - Cursul 4 6

    Exemple

  • Tehnici de optimizare - Cursul 4 7

    Degenerare i ciclare

    Descreterea funciei obiectiv:( )k k

    r

    rk

    zxz

    cz

    y

    =

    Metoda perturbrii (A. Charnes, 1952)( ){ } ( )

    1inf , cu , 0.

    nj j

    jc x A x b x b b A

    =

    = = + >0f

    Propoziia 1. Fie B = (A1, , Am) o baz primal admisibil. Atunci exist astfel nct0B > ( ) ( ) ( )1 0, 0, .Bx B b = > Demonstraie. Avem ( ) ( )11 , unde ,..., I .n j j m mjx x Y Y Y == + =

    0r

    x

    Pe componente, pentru ( )1

    1, , 1 .n

    i j ii i ij

    j mi m x x y

    = +

    = = + +

    Rezult, 0,i >Lum { }1min ,..., .B m = Rezult, ( ) ( )0, , 0.B x >

    ( ) 0.i ix >suficient de mic, pentru care

  • Tehnici de optimizare - Cursul 4 8

    Propoziia 2. Fie B primal admisibil n condiiile Teoremei de schimbare a bazei i Atunci, astfel nct criteriul de ieire din baz este ndeplinit pentru un singur indice

    Observaie. Dac n algoritmul simplex alegerea indicelui r nu este unic, dup efectuarea iteraiei se obine o soluie de baz degenerat.

    ( ) ( )0, 0, .Bx > ' 0 >( ), 0, ' :r

    Demonstraie. Trebuie ca

    ( ) ( )1min 0 .r i iki m

    rk ik

    x xy

    y y

    = >

    ( ) ( ), cu 0, 0 ,s st t stsk tk

    sk tk

    x xs t y y

    y y

    > >

    10.

    nsj tj js t

    stjsk tk sk tk

    y yx xy y y y

    =

    +

    adic, Dac 0,s t

    sk tk

    x x

    y y

    =

    ,1 , 0. Altfel, det 0 !sp tpsk tk

    y yp p n B

    y y

    =

    Lum { }' min 0 , 0, 0 .st sk tks t y y = > > >

  • Tehnici de optimizare - Cursul 5 1

    Dualitate n optimizarea liniarProblema 1.

    D1 = 13 D2 = 17

    B1 = 12

    B2 = 8

    B3 = 10

    5

    2

    3

    3

    4

    2

    S se distribuie marfa din depozite la beneficiari, n aa fel nct, costul total de transport s fie minim.

    { }11 12 13 21 22 2311 12 13

    21 22 23

    11 21

    12 22

    13 23

    min 5 2 3 3 4 21317

    128

    100, 1, 2, 1, 2,3.ij

    x x x x x x

    x x x

    x x x

    x x

    x x

    x x

    x i j

    + + + + +

    + + +

    = =

    Dac notm

    cantitatea de marf transportat de la depozitul Di ctre beneficiarul Bj, modelul matematic este:

    , 1, 2, 1,2,3,ijx i j= =

  • Tehnici de optimizare - Cursul 5 2

    Problema 2.

    D1 = 13

    D2 = 17

    Cumpr Vnd

    B1 = 12

    B2 = 8

    B3 = 10

    u1

    u2

    v1

    v3

    v2

    Condiie: diferena dintre preul de vnzare i cel de cumprare s nu depeasc costul unitar de transport de la depozitul Di la beneficiarul Bj.

    { }1 2 1 2 31 1

    2 1

    3 1

    1 2

    2 2

    3 2

    max 13 17 12 8 10523342

    0, 1, 2, 0, 1,2,3.i j

    u u v v v

    v u

    v u

    v u

    v u

    v u

    v u

    u i v j

    + + +

    = =

    S se stabileasc costurile de cumprare i vnzare a mrfii n aa fel nct s se obin un beneficiu maxim.

  • Tehnici de optimizare - Cursul 5 3

    { }1 1 2 2 3 311 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 bA x A x A x bA x A x A x bx x

    + +

    + +

    + + =

    + +

    0 0

    f f f

    { }1 1 2 2 3 311 1 21 2 31 3 1

    12 1 22 2 32 3 2

    13 1 23 2 33 3 3

    1 3

    sup

    n raport cu

    b u b u b u

    A u A u A u cA u A u A u cA u A u A u cu u

    + +

    + +

    + + =

    + +

    0 0

    f f f

    f f f

    f f f

    f f f

    Problema primal:

    Problema dual:

    ( P )

    ( D )

    =========================================================================

  • Tehnici de optimizare - Cursul 5 4

    Reguli de asociere a problemelor duale

    Unei probleme de minimizare i corespunde o problem de maximizare, i reciproc.

  • Tehnici de optimizare - Cursul 5 5

    { }1 1 2 2 3 311 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 bA x A x A x bA x A x A x bx x

    + +

    + +

    + + =

    + +

    0 0

    f f fProblema primal:

    Problema dual:

    ( P )

    ( D )

    =========================================================================

    { }1 1 2 2 3 311 1 21 2 31 3 1

    12 1 22 2 32 3 2

    13 1 23 2 33 3 3

    1 3

    sup

    n raport cu

    b u b u b u

    A u A u A u cA u A u A u cA u A u A u cu u

    + +

    + +

    + + =

    + +

    0 0

    f f f

    f f f

    f f f

    f f f

  • Tehnici de optimizare - Cursul 5 6

    Reguli de asociere a problemelor duale

    Unei probleme de minimizare i corespunde o problem de maximizare, i reciproc.

    Coeficienii din funcia obiectiv a unei probleme devin coeficienii termenului liber n cealalt problem, i reciproc.

  • Tehnici de optimizare - Cursul 5 7

    { }1 1 2 2 3 311 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 bA x A x A x bA x A x A x bx x

    + +

    + +

    + + =

    + +

    0 0

    f f f

    { }1 1 2 2 3 311 1 21 2 31 3 1

    12 1 22 2 32 3 2

    13 1 23 2 33 3 3

    1 3

    sup

    n raport cu

    b u b u b u

    A u A u A u cA u A u A u cA u A u A u cu u

    + +

    + +

    + + =

    + +

    0 0

    f f f

    f f f

    f f f

    f f f

    Problema primal:

    Problema dual:

    ( P )

    ( D )

    =========================================================================

  • Tehnici de optimizare - Cursul 5 8

    Reguli de asociere a problemelor duale

    Unei probleme de minimizare i corespunde o problem de maximizare, i reciproc.

    Coeficienii din funcia obiectiv a unei probleme devin coeficienii termenului liber n cealalt problem, i reciproc.

    Matricea restriciilor dintr-o problem este matricea transpus din cealalt problem, i reciproc.

  • Tehnici de optimizare - Cursul 5 9

    { }1 1 2 2 3 311 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 bA x A x A x bA x A x A x bx x

    + +

    + +

    + + =

    + +

    0 0

    f f f

    { }1 1 2 2 3 311 1 21 2 31 3 1

    12 1 22 2 32 3 2

    13 1 23 2 33 3 3

    1 3

    sup

    n raport cu

    b u b u b u

    A u A u A u cA u A u A u cA u A u A u cu u

    + +

    + +

    + + =

    + +

    0 0

    f f f

    f f f

    f f f

    f f f

    Problema primal:

    Problema dual:

    ( P )

    ( D )

    =========================================================================

  • Tehnici de optimizare - Cursul 5 10

    Reguli de asociere a problemelor duale

    Unei probleme de minimizare i corespunde o problem de maximizare, i reciproc.

    Coeficienii din funcia obiectiv a unei probleme devin coeficienii termenului liber n cealalt problem, i reciproc.

    Matricea restriciilor dintr-o problem este matricea transpus din cealalt problem, i reciproc.

    Fiecrei restricii dintr-o problem i corespunde o variabil n cealalt problem, i reciproc.Relaia de asociere este urmtoarea: unei restricii concordante i corespunde o variabil nenegativ

    i reciproc; unei restricii egalitate i corespunde o variabil oarecare (fr

    condiii de semn), i reciproc; unei restricii neconcordante i corespunde o variabil nepozitiv

    i reciproc.

    ( )0 ,

    ( )0 ,

  • Tehnici de optimizare - Cursul 5 11

    { }1 1 2 2 3 311 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 bA x A x A x bA x A x A x bx x

    + +

    + +

    + + =

    + +

    0 0

    f f f

    { }1 1 2 2 3 311 1 21 2 31 3 1

    12 1 22 2 32 3 2

    13 1 23 2 33 3 3

    1 3

    sup

    n raport cu

    b u b u b u

    A u A u A u cA u A u A u cA u A u A u cu u

    + +

    + +

    + + =

    + +

    0 0

    f f f

    f f f

    f f f

    f f f

    Problema primal:

    Problema dual:

    ( P )

    ( D )

    =========================================================================

  • Tehnici de optimizare - Cursul 5 12

    { }1 1 2 2 3 311 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 bA x A x A x bA x A x A x bx x

    + +

    + +

    + + =

    + +

    0 0

    f f f

    { }1 1 2 2 3 311 1 21 2 31 3 1

    12 1 22 2 32 3 2

    13 1 23 2 33 3 3

    1 3

    sup

    n raport cu

    b u b u b u

    A u A u A u cA u A u A u cA u A u A u cu u

    + +

    + +

    + + =

    + +

    0 0

    f f f

    f f f

    f f f

    f f f

    Problema primal:

    Problema dual:

    ( P )

    ( D )

    =========================================================================

  • Tehnici de optimizare - Cursul 5 13

    { }1 1 2 2 3 311 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 bA x A x A x bA x A x A x bx x

    + +

    + +

    + + =

    + +

    0 0

    f f f

    { }1 1 2 2 3 311 1 21 2 31 3 1

    12 1 22 2 32 3 2

    13 1 23 2 33 3 3

    1 3

    sup

    n raport cu

    b u b u b u

    A u A u A u cA u A u A u cA u A u A u cu u

    + +

    + +

    + + =

    + +

    0 0

    f f f

    f f f

    f f f

    f f f

    Problema primal:

    Problema dual:

    ( P )

    ( D )

    =========================================================================

  • Tehnici de optimizare - Cursul 5 14

    { }1 1 2 2 3 311 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 bA x A x A x bA x A x A x bx x

    + +

    + +

    + + =

    + +

    0 0

    f f f

    { }1 1 2 2 3 311 1 21 2 31 3 1

    12 1 22 2 32 3 2

    13 1 23 2 33 3 3

    1 3

    sup

    n raport cu

    b u b u b u

    A u A u A u cA u A u A u cA u A u A u cu u

    + +

    + +

    + + =

    + +

    0 0

    f f f

    f f f

    f f f

    f f f

    Problema primal:

    Problema dual:

    ( P )

    ( D )

    =========================================================================

  • Tehnici de optimizare - Cursul 5 15

    { }1 1 2 2 3 311 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 bA x A x A x bA x A x A x bx x

    + +

    + +

    + + =

    + +

    0 0

    f f f

    { }1 1 2 2 3 311 1 21 2 31 3 1

    12 1 22 2 32 3 2

    13 1 23 2 33 3 3

    1 3

    sup

    n raport cu

    b u b u b u

    A u A u A u cA u A u A u cA u A u A u cu u

    + +

    + +

    + + =

    + +

    0 0

    f f f

    f f f

    f f f

    f f f

    Problema primal:

    Problema dual:

    ( P )

    ( D )

    =========================================================================

  • Tehnici de optimizare - Cursul 5 16

    { }1 1 2 2 3 311 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 bA x A x A x bA x A x A x bx x

    + +

    + +

    + + =

    + +

    0 0

    f f f

    { }1 1 2 2 3 311 1 21 2 31 3 1

    12 1 22 2 32 3 2

    13 1 23 2 33 3 3

    1 3

    sup

    n raport cu

    b u b u b u

    A u A u A u cA u A u A u cA u A u A u cu u

    + +

    + +

    + + =

    + +

    0 0

    f f f

    f f f

    f f f

    f f f

    Problema primal:

    Problema dual:

    ( P )

    ( D )

    =========================================================================

  • Tehnici de optimizare - Cursul 5 17

    { }{ }{ }{ }

    { }

    primala n form standard: inf | ,problema dual: sup |primala n form canonic: inf | ,problema dual: sup | ,

    inf

    primala n form mixt: n raprt cu:

    c x A x b x

    b u A u c

    c x A x b x

    b u A u c u

    c x

    =

    0

    0

    0

    f

    f f

    f

    f f

    f

    { }

    1 1

    2 2

    1 1 2 2

    1 1 2 2

    1

    ,

    sup

    problema dual: n raprt cu:,

    A x bx

    A x b

    b u b u

    A u A u cu

    =

    +

    +

    0

    0

    f f

    f f

  • Tehnici de optimizare - Cursul 5 18

    Teoreme de dualitateFie , ,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 fConsiderm perechea de probleme (canonice) duale:

    { }{ }

    inf | ...........................sup | ...........................

    c x x

    b u u

    P

    D

    f

    f

    ( P )( D )

    Teorem (dualitate slab). Dac domeniile de admisibilitateatunci are loc relaia:

    , , P D, ,x u P D

    .c x b u f f

    Demonstraie. Pentru avem:

    ,

    A x bu A x u b

    u

    00

    f f.

    xx A u x c

    A u c

    00

    f f f

    f

    , ,x u P D

    Prin urmare, .c x x A u u A x b u = f f f f f

  • Tehnici de optimizare - Cursul 5 19

    Teorem (dualitate tare). Dac domeniile de admisibilitatei astfel nct atunci, este soluie

    optim pentru (P) i este soluie optim pentru (D) .

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

    u

    Demonstraie. Presupunem prin absurd c nu este optim pentru (P).xAtunci, astfel nct Contradicie!0x P 0 .c x c x b u < = f f f

    Teorema (fundamental a dualitii). Fiind dat perechea de probleme duale (P) i (D) doar una din urmtoarele afirmaii are loc:

    a) i n cazul acesta i soluii optime pentru (P), respectiv (D), astfel nct

    b) i c) i sau i n cazul acesta problema

    care are soluii admisibile are optimul infinit.

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

    .= = P D = P D .= P D

  • Tehnici de optimizare - Cursul 5 20

    Demonstraie. Considerm matricea ptratic de ordinul n+m+1:

    0

    n

    m

    A cS A b

    c b

    =

    00

    f

    f f

    Deoarece putem aplica consecina Lemei Farkas-Minkowski:exist astfel nct i

    ,S S= f1, ,

    n mz z+ + 0R .S z S z z + >0 0Notm: unde Avem:

    , , .n mx u r R R R

    ,

    ,

    0,

    x

    u

    r

    00

    , (1), (2)

    0, (3)

    A u crA x br

    c x b u

    +

    +

    00

    f

    f f

    , (4), (5)

    0. (6)

    x A u crA x u br

    c x b u r

    + >

    + >

    + + >

    00

    f

    f f

    ( ), , ,z x u r= f

    0r > 0r =

  • Tehnici de optimizare - Cursul 5 21

    Cazul 0.r > Definim: i x ux u

    r r= =

    Evident, mprind relaiile (1) i (2) la r, obinem:i .x u 0 0 i .A x b A u c f

    Deci, i ,x u P D

    Din dualitatea slab

    Din relaia (3) / rc x b uc x b u

    f f

    f f.c x b u = f f

    Din dualitatea tare rezult optime pentru (P), respectiv (D).ix u

    i . P Dadic,

  • Tehnici de optimizare - Cursul 5 22

    00 0 din (2)

    0,x

    x c x A uA u c

    00 123

    f f f

    f

    Nu putem avea i . P DPrin absurd, dac exist avem:

    0 0i ,x u P D

    0

    00 din (1)

    0,A x b

    u b u A xu

    00

    f f

    deci, Contradicie! cu (6)0 .x c u b f f

    Rezult:

    i .= = P D

    i sau i . = = P D P D

    Cazul 0.r =

  • Tehnici de optimizare - Cursul 5 23

    Presupunem, spre exemplu, c exist 0 .x P

    Definim vectorul ( ) 0 , , 0.x x x = + RAvem evident i( )x 0

    ( ) 0 00 din (2)

    .A x A x A x A x b

    = +

    Deci, ( ), 0 , .x R P

    00, din (1)din (6)

    0,c x b u x A u

    < f f f fDeoarece

    rezult, ( ) 00

    lim lim .c x c x c x

    + >

    0

    0

    f

    Demonstraie. Rezult din (4) i (5) pentru cazul r > 0 .Teorem (slab a ecarturilor complemetare). FieAtunci,

    , .x u P Dx este soluie optim pentru (P) u este soluie optim pentru (D)

    ( )( )

    0,

    0.

    u A x b

    x c A u

    =

    =

    f

    f f

    Demonstraie. Din TFD a) rezult: Deci,0.c x b u =f fc x b u A x x Au u+ = f f ff f ( ) ( ) 0.u A x b x c A u + =f f f

    0 0Adunm membru cu membru relaiile din enun i obinem: .c x b u = f f

    Din teorema de dualitate tare rezult ca soluiile sunt optime.

  • Tehnici de optimizare - Cursul 6 1

    Algoritmul simplex dualConsiderm problema de programare liniar n forma standard:

    { }inf | ,c x A x b x = 0f (P)i duala ei, { }sup |b u A u c f f (D)

    ( ), , , .m n m nA b c rang A m n =

  • Tehnici de optimizare - Cursul 6 2

    Matricea de baz B se numete dual admisibil, dac 1c B A c f fB

    Teorem (optim): Dac baza B este primal i dual admisibil, atunci ea este optim pentru problemele (P) i (D).

    Algoritmul simplex primal:

    Determin B(i)primal admisibil

    i = 0

    STOP

    B(i) dual admisibil ?

    B(i) optim !

    i i + 1

    da

    da

    nu

    nu(P) are optim

    ( ) ?

  • Tehnici de optimizare - Cursul 6 3

    Algoritmul simplex dual:

    Determin B(i)dual admisibil

    i = 0

    STOP

    B(i) primal admisibil ?

    B(i) optim !i i + 1

    da

    da

    nu

    nu

    Teorem (domeniu vid). Fie B o baz dual admisibil. Dac exist o component pentru care atunci problema (P) nu are soluie.

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

    Demonstraie. Notm i linia i a lui B1.1u c B= f fB1

    iB

    Definim vectorul: ( ) 1, , 0.iu u B = f f R

    (D) are optim (+ ) ?

  • Tehnici de optimizare - Cursul 6 4

    Pentru orice avem:1, ,j n=

    ( ) 1j j jiu A u A B A = f fijyjz

    j ijz y= 0

    dual admis.B

    deci, este o soluie admisibil pentru problema (D).( )0, u

    Valoarea funciei obiectiv este: ( ) 1i iu b u b B b z x = = f f

    ( ) ( )lim lim .iu b z x = + = +f0>

    Problema (D) are optimul + i din T.F.D. rezult c (P) nu are soluie.

    jcjz jc( ) ju A f

  • Tehnici de optimizare - Cursul 6 5

    Teorem (schimbarea bazei): Fie o baz dual admisibil i componenta pentru care exist Dac alegem indicele astfel nct

    ( )1 2 mss sB A A A= 0,rx < 0.rjj cu y

  • Tehnici de optimizare - Cursul 6 6

    ( ) ( ) .k k rjj j j jrk

    z c yz c z c

    y

    =

    Din formulele de schimbare a bazei avem:

    B fiind dual admisibil, rezult: ( ) 0, 1, .j jz c j n =Dac evident0,rjy 0.j jz c

    Dac avem:0,rjy < 0.j j k kj j rjrj rk

    z c z cz c y

    y y

    =

    0

    0 0 este suficient s lum

    Notm1 1 1 1

    0.m n m n

    i j iji j i j

    S a b x= = = =

    = = = Dac 0 0 0, , .i j ijS a b x i j= = = =

    1 1 1, 1, .

    m m mi j j

    ij i ji i i

    a b bx a b j n

    S S= = =

    = = = =

    1 1 1, 1, .

    n n ni j i

    ij j ij j j

    a b ax b a i m

    S S= = =

    = = = =

    Observaie. Putem considera mereu , 1, ,0 1, .ij i m jc n= =

    0, 1, , 1, .i jija b

    x i m j nS

    = = =

    { }11

    0pentru max ,0iji m

    j nc

    =

    ( )1 1 1 1 1 1 1 1

    m n m n m n m n

    ij ij ij ij ij ij iji j i j i j i j

    c x c x x c x S = = = = = = = =

    + = + = +

    = constant1 10

    m n

    iji j

    ij xc= =

    (PT) are optim finit !

  • Tehnici de optimizare - Cursul 6 13

    1 1 1

    1 1 1

    1 1 1

    1 1 1

    1 1 1

    1 1 1

    = a1

    = a2

    = am

    = b1= b2

    = bn

    x11 x12 x1n x21 x22 x2n xm1 xm2 xmnoferta

    cererea

    Structura matricei restriciilor:

    Teorema. Rangul matricei este = m + n 1.Demonstraie. Rangul este < m + n .

    ( )11 21 1,1 1 2det , , , , , , 1 0.m m m mnA A A A A A = Se elimin linia m + 1

    i atunci,

  • Tehnici de optimizare - Cursul 6 14

    Metoda colului de N V.

    1i j= = { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    1j j +

    1i i +

    ?i j m n+ +Stop

    da

    danu

    nu

    13

    17

    11

    19

    7 18 9 16 10

    Exemplu.

    Determinarea unei soluii iniiale de baz

  • Tehnici de optimizare - Cursul 6 15

    Metoda colului de N V.

    x11 13

    17

    11

    19

    7 18 9 16 10

    Exemplu.

    1i j= = { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    1j j +

    1i i +

    ?i j m n+ +Stop

    da

    danu

    nu

    Determinarea unei soluii iniiale de baz

  • Tehnici de optimizare - Cursul 6 16

    Metoda colului de N V.

    7 6

    17

    11

    19

    0 18 9 16 10

    Exemplu.

    1i j= = { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    1j j +

    1i i +

    ?i j m n+ +Stop

    da

    danu

    nu

    Determinarea unei soluii iniiale de baz

  • Tehnici de optimizare - Cursul 6 17

    Metoda colului de N V.

    7 x12 6

    17

    11

    19

    0 18 9 16 10

    Exemplu.

    1i j= = { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    1j j +

    1i i +

    ?i j m n+ +Stop

    da

    danu

    nu

    Determinarea unei soluii iniiale de baz

  • Tehnici de optimizare - Cursul 6 18

    Metoda colului de N V.

    7 6 0

    17

    11

    19

    0 12 9 16 10

    Exemplu.

    1i j= = { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    1j j +

    1i i +

    ?i j m n+ +Stop

    da

    danu

    nu

    Determinarea unei soluii iniiale de baz

  • Tehnici de optimizare - Cursul 6 19

    Metoda colului de N V.

    7 6 0

    x22 17

    11

    19

    0 12 9 16 10

    Exemplu.

    1i j= = { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    1j j +

    1i i +

    ?i j m n+ +Stop

    da

    danu

    nu

    Determinarea unei soluii iniiale de baz

  • Tehnici de optimizare - Cursul 6 20

    Metoda colului de N V.

    7 6 0

    12 5

    11

    19

    0 0 9 16 10

    Exemplu.

    1i j= = { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    1j j +

    1i i +

    ?i j m n+ +Stop

    da

    danu

    nu

    Determinarea unei soluii iniiale de baz

  • Tehnici de optimizare - Cursul 6 21

    Metoda colului de N V.

    7 6 0

    12 x23 5

    11

    19

    0 0 9 16 10

    Exemplu.

    1i j= = { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    1j j +

    1i i +

    ?i j m n+ +Stop

    da

    danu

    nu

    Determinarea unei soluii iniiale de baz

  • Tehnici de optimizare - Cursul 6 22

    Metoda colului de N V.

    7 6 0

    12 5 0

    11

    19

    0 0 4 16 10

    Exemplu.

    1i j= = { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    1j j +

    1i i +

    ?i j m n+ +Stop

    da

    danu

    nu

    Determinarea unei soluii iniiale de baz

  • Tehnici de optimizare - Cursul 6 23

    Metoda colului de N V.

    7 6 0

    12 5 0

    x33 11

    19

    0 0 4 16 10

    Exemplu.

    1i j= = { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    1j j +

    1i i +

    ?i j m n+ +Stop

    da

    danu

    nu

    Determinarea unei soluii iniiale de baz

  • Tehnici de optimizare - Cursul 6 24

    Metoda colului de N V.

    7 6 0

    12 5 0

    4 7

    19

    0 0 0 16 10

    Exemplu.

    1i j= = { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    1j j +

    1i i +

    ?i j m n+ +Stop

    da

    danu

    nu

    Determinarea unei soluii iniiale de baz

  • Tehnici de optimizare - Cursul 6 25

    Metoda colului de N V.

    7 6 0

    12 5 0

    4 x34 7

    19

    0 0 0 16 10

    Exemplu.

    1i j= = { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    1j j +

    1i i +

    ?i j m n+ +Stop

    da

    danu

    nu

    Determinarea unei soluii iniiale de baz

  • Tehnici de optimizare - Cursul 6 26

    Metoda colului de N V.

    7 6 0

    12 5 0

    4 7 0

    19

    0 0 0 9 10

    Exemplu.

    1i j= = { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    1j j +

    1i i +

    ?i j m n+ +Stop

    da

    danu

    nu

    Determinarea unei soluii iniiale de baz

  • Tehnici de optimizare - Cursul 6 27

    Metoda colului de N V.

    7 6 0

    12 5 0

    4 7 0

    x44 19

    0 0 0 9 10

    Exemplu.

    1i j= = { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    1j j +

    1i i +

    ?i j m n+ +Stop

    da

    danu

    nu

    Determinarea unei soluii iniiale de baz

  • Tehnici de optimizare - Cursul 6 28

    Metoda colului de N V.

    7 6 0

    12 5 0

    4 7 0

    9 10

    0 0 0 0 10

    Exemplu.

    1i j= = { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    1j j +

    1i i +

    ?i j m n+ +Stop

    da

    danu

    nu

    Determinarea unei soluii iniiale de baz

  • Tehnici de optimizare - Cursul 6 29

    Metoda colului de N V.

    7 6 0

    12 5 0

    4 7 0

    9 x45 10

    0 0 0 0 10

    Exemplu.

    1i j= = { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    1j j +

    1i i +

    ?i j m n+ +Stop

    da

    danu

    nu

    Determinarea unei soluii iniiale de baz

  • Tehnici de optimizare - Cursul 6 30

    Metoda colului de N V.

    7 6 0

    12 5 0

    4 7 0

    9 10 0

    0 0 0 0 0

    Exemplu.

    1i j= = { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    1j j +

    1i i +

    ?i j m n+ +Stop

    da

    danu

    nu

    Determinarea unei soluii iniiale de baz

  • Tehnici de optimizare - Cursul 6 31

    Metoda colului de N V.

    7 6 13

    12 5 17

    4 7 11

    9 10 19

    7 18 9 16 10

    Exemplu.

    1i j= = { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    1j j +

    1i i +

    ?i j m n+ +Stop

    da

    danu

    nu

    Determinarea unei soluii iniiale de baz

  • Tehnici de optimizare - Cursul 6 32

    Determinarea unei soluii iniiale de bazMetoda costului minim.

    { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    { }\I I iStop

    da

    nu

    { }{ }1,2, ,1, 2, ,

    I m

    J n

    =

    =

    { }

    ,

    minij rkr I k J

    c c

    =

    { }\J J j? ?

    I J= =

    nu

    da

    13

    17

    11

    19

    7 18 9 16 10

    Exemplu.

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

    Matricea costurilor

  • Tehnici de optimizare - Cursul 6 33

    Determinarea unei soluii iniiale de bazMetoda costului minim.

    { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    { }\I I iStop

    da

    nu

    { }{ }1,2, ,1, 2, ,

    I m

    J n

    =

    =

    { }

    ,

    minij rkr I k J

    c c

    =

    { }\J J j? ?

    I J= =

    nu

    da

    13

    x24 17

    11

    19

    7 18 9 16 10

    Exemplu.

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

    Matricea costurilor

  • Tehnici de optimizare - Cursul 6 34

    Determinarea unei soluii iniiale de bazMetoda costului minim.

    { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    { }\I I iStop

    da

    nu

    { }{ }1,2, ,1, 2, ,

    I m

    J n

    =

    =

    { }

    ,

    minij rkr I k J

    c c

    =

    { }\J J j? ?

    I J= =

    nu

    da

    Exemplu.

    Matricea costurilor

    13

    16 1

    11

    19

    7 18 9 0 10

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

  • Tehnici de optimizare - Cursul 6 35

    Determinarea unei soluii iniiale de bazMetoda costului minim.

    { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    { }\I I iStop

    da

    nu

    { }{ }1,2, ,1, 2, ,

    I m

    J n

    =

    =

    { }

    ,

    minij rkr I k J

    c c

    =

    { }\J J j? ?

    I J= =

    nu

    da

    Exemplu.

    Matricea costurilor

    x13 13

    16 1

    11

    19

    7 18 9 0 10

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

  • Tehnici de optimizare - Cursul 6 36

    Determinarea unei soluii iniiale de bazMetoda costului minim.

    { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    { }\I I iStop

    da

    nu

    { }{ }1,2, ,1, 2, ,

    I m

    J n

    =

    =

    { }

    ,

    minij rkr I k J

    c c

    =

    { }\J J j? ?

    I J= =

    nu

    da

    Exemplu.

    Matricea costurilor

    9 4

    16 1

    11

    19

    7 18 0 0 10

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

  • Tehnici de optimizare - Cursul 6 37

    Determinarea unei soluii iniiale de bazMetoda costului minim.

    { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    { }\I I iStop

    da

    nu

    { }{ }1,2, ,1, 2, ,

    I m

    J n

    =

    =

    { }

    ,

    minij rkr I k J

    c c

    =

    { }\J J j? ?

    I J= =

    nu

    da

    Exemplu.

    Matricea costurilor

    9 4

    16 1

    11

    x41 19

    7 18 0 0 10

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

  • Tehnici de optimizare - Cursul 6 38

    Determinarea unei soluii iniiale de bazMetoda costului minim.

    { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    { }\I I iStop

    da

    nu

    { }{ }1,2, ,1, 2, ,

    I m

    J n

    =

    =

    { }

    ,

    minij rkr I k J

    c c

    =

    { }\J J j? ?

    I J= =

    nu

    da

    Exemplu.

    Matricea costurilor

    9 4

    16 1

    11

    7 12

    0 18 0 0 10

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

  • Tehnici de optimizare - Cursul 6 39

    Determinarea unei soluii iniiale de bazMetoda costului minim.

    { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    { }\I I iStop

    da

    nu

    { }{ }1,2, ,1, 2, ,

    I m

    J n

    =

    =

    { }

    ,

    minij rkr I k J

    c c

    =

    { }\J J j? ?

    I J= =

    nu

    da

    Exemplu.

    Matricea costurilor

    9 x15 4

    16 1

    11

    7 12

    0 18 0 0 10

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

  • Tehnici de optimizare - Cursul 6 40

    Determinarea unei soluii iniiale de bazMetoda costului minim.

    { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    { }\I I iStop

    da

    nu

    { }{ }1,2, ,1, 2, ,

    I m

    J n

    =

    =

    { }

    ,

    minij rkr I k J

    c c

    =

    { }\J J j? ?

    I J= =

    nu

    da

    Exemplu.

    Matricea costurilor

    9 4 0

    16 1

    11

    7 12

    0 18 0 0 6

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

  • Tehnici de optimizare - Cursul 6 41

    Determinarea unei soluii iniiale de bazMetoda costului minim.

    { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    { }\I I iStop

    da

    nu

    { }{ }1,2, ,1, 2, ,

    I m

    J n

    =

    =

    { }

    ,

    minij rkr I k J

    c c

    =

    { }\J J j? ?

    I J= =

    nu

    da

    Exemplu.

    Matricea costurilor

    9 4 0

    x22 16 1

    11

    7 12

    0 18 0 0 6

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

  • Tehnici de optimizare - Cursul 6 42

    Determinarea unei soluii iniiale de bazMetoda costului minim.

    { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    { }\I I iStop

    da

    nu

    { }{ }1,2, ,1, 2, ,

    I m

    J n

    =

    =

    { }

    ,

    minij rkr I k J

    c c

    =

    { }\J J j? ?

    I J= =

    nu

    da

    Exemplu.

    Matricea costurilor

    9 4 0

    1 16 0

    11

    7 12

    0 17 0 0 6

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

  • Tehnici de optimizare - Cursul 6 43

    Determinarea unei soluii iniiale de bazMetoda costului minim.

    { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    { }\I I iStop

    da

    nu

    { }{ }1,2, ,1, 2, ,

    I m

    J n

    =

    =

    { }

    ,

    minij rkr I k J

    c c

    =

    { }\J J j? ?

    I J= =

    nu

    da

    Exemplu.

    Matricea costurilor

    9 4 0

    1 16 0

    x35 11

    7 12

    0 17 0 0 6

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

  • Tehnici de optimizare - Cursul 6 44

    Determinarea unei soluii iniiale de bazMetoda costului minim.

    { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    { }\I I iStop

    da

    nu

    { }{ }1,2, ,1, 2, ,

    I m

    J n

    =

    =

    { }

    ,

    minij rkr I k J

    c c

    =

    { }\J J j? ?

    I J= =

    nu

    da

    Exemplu.

    Matricea costurilor

    9 4 0

    1 16 0

    6 5

    7 12

    0 17 0 0 0

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

  • Tehnici de optimizare - Cursul 6 45

    Determinarea unei soluii iniiale de bazMetoda costului minim.

    { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    { }\I I iStop

    da

    nu

    { }{ }1,2, ,1, 2, ,

    I m

    J n

    =

    =

    { }

    ,

    minij rkr I k J

    c c

    =

    { }\J J j? ?

    I J= =

    nu

    da

    Exemplu.

    Matricea costurilor

    9 4 0

    1 16 0

    6 5

    7 x42 12

    0 17 0 0 0

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

  • Tehnici de optimizare - Cursul 6 46

    Determinarea unei soluii iniiale de bazMetoda costului minim.

    { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    { }\I I iStop

    da

    nu

    { }{ }1,2, ,1, 2, ,

    I m

    J n

    =

    =

    { }

    ,

    minij rkr I k J

    c c

    =

    { }\J J j? ?

    I J= =

    nu

    da

    Exemplu.

    Matricea costurilor

    9 4 0

    1 16 0

    6 5

    7 12 0

    0 5 0 0 0

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

  • Tehnici de optimizare - Cursul 6 47

    Determinarea unei soluii iniiale de bazMetoda costului minim.

    { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    { }\I I iStop

    da

    nu

    { }{ }1,2, ,1, 2, ,

    I m

    J n

    =

    =

    { }

    ,

    minij rkr I k J

    c c

    =

    { }\J J j? ?

    I J= =

    nu

    da

    Exemplu.

    Matricea costurilor

    9 4 0

    1 16 0

    x32 6 5

    7 12 0

    0 5 0 0 0

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

  • Tehnici de optimizare - Cursul 6 48

    Determinarea unei soluii iniiale de bazMetoda costului minim.

    { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    { }\I I iStop

    da

    nu

    { }{ }1,2, ,1, 2, ,

    I m

    J n

    =

    =

    { }

    ,

    minij rkr I k J

    c c

    =

    { }\J J j? ?

    I J= =

    nu

    da

    Exemplu.

    Matricea costurilor

    9 4 0

    1 16 0

    5 6 0

    7 12 0

    0 0 0 0 0

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

  • Tehnici de optimizare - Cursul 6 49

    Determinarea unei soluii iniiale de bazMetoda costului minim.

    { }min ,ij i jx a b= i i ijj j ij

    a a x

    b b x

    ?0ia =

    { }\I I iStop

    da

    nu

    { }{ }1,2, ,1, 2, ,

    I m

    J n

    =

    =

    { }

    ,

    minij rkr I k J

    c c

    =

    { }\J J j? ?

    I J= =

    nu

    da

    Exemplu.

    Matricea costurilor

    9 4 13

    1 16 17

    5 6 11

    7 12 19

    7 18 9 16 10

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

  • Tehnici de optimizare - Cursul 6 50

    Determinarea unei soluii iniiale de baz

    Matricea costurilor

    9 4 13

    1 16 17

    5 6 11

    7 12 19

    7 18 9 16 10

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

    7 6 13

    12 5 17

    4 7 11

    9 10 19

    7 18 9 16 10

    Metoda colului de N V.Costul total = 193

    Metoda costului minim. Costul total = 137

  • Tehnici de optimizare - Cursul 7 1

    Soluii iniiale de baz

    Matricea costurilor

    9 4 13

    1 16 17

    5 6 11

    7 12 19

    7 18 9 16 10

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

    7 6 13

    12 5 17

    4 7 11

    9 10 19

    7 18 9 16 10

    Metoda colului de N V.Costul total = 193

    Metoda costului minim. Costul total = 137Este soluia optim ?

  • Tehnici de optimizare - Cursul 7 2

    Matricea costurilor

    9 4 13

    1 16 17

    5 6 11

    7 12 19

    7 18 9 16 10

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

    3 10 13

    6 11 17

    6 5 11

    7 12 19

    7 18 9 16 10

    O soluie mai bun.Costul total = 132

    Metoda costului minim. Costul total = 137

  • Tehnici de optimizare - Cursul 7 3

    Testul de optimalitate

    1 1min

    m n

    ij iji j

    c x= =

    n raport cu1

    , 1, ,n

    ij ij

    x a i m=

    = =

    1, 1, ,

    m

    ij ji

    x b j n=

    = =

    0, 1, , 1, .ijx i m j n = =

    Forma standard a problemei de transport:

    (PT)

    Condiia de existen a soluiei:

    1 10, 1, ; 0, 1, ; .

    m n

    i j i ji j

    a i m b j n a b= =

    = = =

  • Tehnici de optimizare - Cursul 7 4

    1 1 1

    1 1 1

    1 1 1

    1 1 1

    1 1 1

    1 1 1

    = a1

    = a2

    = am

    = b1= b2

    = bn

    x11 x12 x1n x21 x22 x2n xm1 xm2 xmn

    c11 c12 c1n c21 c22 c2n cm1 cm2 cmn

    Structura datelor n problema de transport:

    Rangul matricei restriciilor este m + n 1.Matricea restriciilor este total unimodular: orice minor = +1, 1 sau 0.

  • Tehnici de optimizare - Cursul 7 5

    Fie B o baz optim i soluia optim de baz a problemei (PT).

    ( ), ,ijx i j B

    ( )0, , , 1 ,1 .ij ijz c i j i m j n n particular, pentru ( ), , 0.ij iji j z c =BDar, unde( ) ( ) ( ) ( )1 1o o o, , .ij ij ij m nij i jz c B A u v A u v A + = = = + RBf f fRezult,

    ( )( )

    , , ,

    , , .

    i j ij

    i j ij

    u v c i ju v c i j

    + = +

    BB

    Dac este o soluie optim de baz, atunci

    va fi soluia optim a dualei problemei (PT).( ), ,ijx i j B

    ( ) ( ), , ,i ju v i j B

    Avem:

  • Tehnici de optimizare - Cursul 7 6

    1 1 1

    1 1 1

    1 1 1

    1 1 1

    1 1 1

    1 1 1

    = a1

    = a2

    = am

    = b1= b2

    = bn

    x11 x12 x1n x21 x22 x2n xm1 xm2 xmn

    c11 c12 c1n c21 c22 c2n cm1 cm2 cmn

    Duala problemei de transport:

    u1

    u2

    um

    v1

    v2

    vn

    1 1max , 1, , 1,

    m n

    i i j j i j iji j

    a u b v u v c i m j n= =

    + + = =

    (DT)

  • Tehnici de optimizare - Cursul 7 7

    Teorema slab a ecarturilor complementare: Fie soluiile admisibile respectiv pentru (PT) i (DT).Acestea sunt optime, dac i numai dac,

    ( ), , , 1 ,1 ,ij i jx u v i m j n

    10, 1, ,

    n

    i ij ij

    u x a i m=

    = =

    10, 1, ,

    m

    j ij ji

    v x b j n=

    = =

    ( ) 0, 1, , 1, .ij i j ijx u v c i m j n + = = =Dac soluia admisibil de baz este: ( )0, , ,ijx i j> B

    ( )0, , .i j iju v c i j+ = Bpentru ca aceasta s fie optim, trebuie ca:

    Condiii evident satisfcute !

    Problem: Cum putem identifica existena unei soluii admisibile a problemei duale (DT) care s verifice condiia de optimalitate ?

    Condiii evident satisfcute pentru

    ( )0, , .ijx i j= B

  • Tehnici de optimizare - Cursul 7 8

    ( ), , .i j iju v c i j+ = BConsiderm sistemul:Acesta are ecuaii i m + n variabile.( ) 1card m n= + BRangul matricei acestui sistem este m + n 1, deci sistemul este compatibil nedeterminat.

    Rezolvarea sistemului: se d unei variabile ui sau vj o valoare arbitrar, iar restul variabilelor se calculeaz succesiv din ecuaiile respective.

    Fie soluia obinut., 1, , , 1, ,i ju i m v j n= =Dac ( ), , ,i j iju v c i j+ B soluia este dual admisibil.Teorema ecarturilor complementare

    soluie de baz optim pentru problema (PT).

    ( ), , ,ijx i j B

    Dac ( ), , 0 ,r k rk rk rkr k u v c z c + = >Bsoluia de baz nu ndeplinete condiia de optimalitate pentru problema (PT).

    ( ), , ,ijx i j B

  • Tehnici de optimizare - Cursul 7 9

    Schimbarea soluiei de bazFie ( ), , .r k rkr k u v c + >B Se introduce n baz variabila 0.rkx x= Schimbarea bazei conform algoritmului simplex:

    ( )( )

    ( )( )( ) ( )

    ( )( )

    , , \ , ,

    0.

    ij rkij ij st

    st rk

    strk

    st rk

    yx x x i j s t

    y

    xx x

    y

    =

    = =

    B

    ( )( ) ( ) ( )( )( )( )min 0

    ijstij rkij

    st rk ij rk

    xx yy y

    = >B

    Criteriul de ieire din baz:( )\ ,s tB

    Recalcularea valorilor corespunztoare noii baze: ( ) ( )\ , ,s t r k= UB B

    Care sunt valorile componentelor vectorului ?( ) ( )1 ork rkY B A=

  • Tehnici de optimizare - Cursul 7 10

    Considerm dou selecii de cte p indici distinci:{ } { }1 2 1 2, , , 1, 2, , , , , , 1, 2, , .p pi i i m j j j n

    Definiie. Mulimea perechilor ( ) ( ) ( ) ( ) ( )1 1 1 2 2 2 1, , , , , , , , , ,p p pi j i j i j i j i jse numete ciclu.

    Observaie: orice ciclu are un numr par de elemente = 2p.Propoziie. Dac mulimea indicilor (i,j) a unor coloane A(ij) din matricea restriciilor a problemei (PT) formeaz un ciclu, atunci aceste coloane sunt liniar dependente.

    Demonstraie. Notm vectorul unitar: .i m ne +R ( )ij i m j m nA e e + + = + R

    ( ) ( ) ( ) ( ) ( ) ( )12 31 1 1 2 2 231 1 1 2 2 2 2

    1

    p p p

    p p p

    i j i ji ji j i j i j

    m ji m j i m j i m j i

    i m j i m j

    A A A A A Ae e e e e e e e

    e e e e

    ++ + +

    + +

    + + + =

    + + + +

    + +

    0.=

    Corolar. Mulimea indicilor de baz nu conine cicluri.B

  • Tehnici de optimizare - Cursul 7 11

    Propoziie. Pentru orice pereche exist un ciclu unic format din aceast pereche i elemente din

    ( ), ,r k B.B

    Determinarea elementelor lui ( ) ( )1 o .rk rkY B A=

    ( ) ( )( )( )

    ( )( )

    o o

    rk rk ijij rk

    ijA B Y y A

    = = B

    Avem: Combinaie liniar (unic) cu vectorii A(ij) din baz.

    Dar exist i un ciclu unic: ( ) ( ) ( ) ( ) ( ){ }1 1 1, , , , , , , , , ,p p pr k r j i j i j i k= CBB

    pentru care ( ) ( ) ( ) ( ) ( ) ( )1 1 1 1 2 .p p pi j i krk rj i j i jA A A A A A= + +

    0 1 2 2p-2 2p-1

    Rezult: ( )( )

    ( )( )( )

    1 pentru , de ordin 1 pentru , de ordi pan

    0 pentru ,

    imparrij rk

    i jy i j

    i j

    =

    CCC

  • Tehnici de optimizare - Cursul 7 12

    = + 1

    ( )( ) ( ) ( )( )( )( )min 0

    ijstij rkij

    st rk ij rk

    xx yy y

    = >B

    Criteriul de ieire din baz:

    ( ){ }min , de ordin impar st ijx x i j= Cadic,

    Perechea de indici va prsi baza( ),s t .B

  • Tehnici de optimizare - Cursul 7 13

    Formulele de schimbare a soluiei de baz:

    ( )( )

    ( )( )( ) ( )

    ( )( )

    , , \ , ,

    0.

    ij rkij ij st

    st rk

    strk

    st rk

    yx x x i j s t

    y

    xx x

    y

    =

    = =

    B

    = + 1, 1, 0

    = + 1

    Rezult:( )( )( )

    pentru , de ordin imparpentru , de ordin parpentru ,

    ij

    ij ij

    ij

    x x i jx x x i j

    x i j

    = +

    CCC

  • Tehnici de optimizare - Cursul 7 14

    Matricea costurilor

    9 4 13

    1 16 17

    5 6 11

    7 12 19

    7 18 9 16 10

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

    Metoda costului minim. Costul total = 137

    Exemplu( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 2 , 3,5 , 4,1 , 4, 2=B

  • Tehnici de optimizare - Cursul 7 15

    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 2 , 3,5 , 4,1 , 4, 2=B

    Matricea costurilor

    9 4 13

    1 16 17

    5 6 11

    7 12 19

    7 18 9 16 10

    0

    5 8 2 4 3

    4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

    ui

    vj

    Rezolvarea sistemului: pentru

    Valoare iniial: v2 = 0 .( ) ,i j iju v c i j+ = B

  • Tehnici de optimizare - Cursul 7 16

    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 2 , 3,5 , 4,1 , 4, 2=B

    Matricea costurilor

    9 4 13

    1 16 17

    5 6 11

    7 12 19

    7 18 9 16 10

    0

    5 8 2 4 3

    3 4 3 4 1 5

    3 4 2 1 3

    2 3 2 1 3

    ui

    vj

    Rezolvarea sistemului: pentru

    Valoare iniial: v2 = 0 .( ) ,i j iju v c i j+ = B

  • Tehnici de optimizare - Cursul 7 17

    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 2 , 3,5 , 4,1 , 4, 2=B

    Matricea costurilor

    9 4 13

    1 16 17

    5 6 11

    7 12 19

    7 18 9 16 10

    0

    5 8 2 4 3

    3 4 3 4 1 5

    4 3 4 2 1 3

    2 3 2 1 3

    ui

    vj

    Rezolvarea sistemului: pentru

    Valoare iniial: v2 = 0 .( ) ,i j iju v c i j+ = B

  • Tehnici de optimizare - Cursul 7 18

    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 2 , 3,5 , 4,1 , 4, 2=B

    Matricea costurilor

    9 4 13

    1 16 17

    5 6 11

    7 12 19

    7 18 9 16 10

    0

    5 8 2 4 3

    3 4 3 4 1 5

    4 3 4 2 1 3

    3 2 3 2 1 3

    ui

    vj

    Rezolvarea sistemului: pentru

    Valoare iniial: v2 = 0 .( ) ,i j iju v c i j+ = B

  • Tehnici de optimizare - Cursul 7 19

    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 2 , 3,5 , 4,1 , 4, 2=B

    Matricea costurilor

    9 4 13

    1 16 17

    5 6 11

    7 12 19

    7 18 9 16 10

    0

    5 8 2 4 3

    3 4 3 4 1 5

    4 3 4 2 1 3

    3 2 3 2 1 3

    ui

    vj

    Rezolvarea sistemului: pentru

    Valoare iniial: v2 = 0 .( ) ,i j iju v c i j+ = B

  • Tehnici de optimizare - Cursul 7 20

    Matricea costurilor

    9 4 13

    1 16 17

    5 6 11

    7 12 19

    7 18 9 16 10

    0 -2

    5 8 2 4 3

    3 4 3 4 1 5

    4 3 4 2 1 3

    3 2 3 2 1 3

    ui

    vj

    Rezolvarea sistemului: pentru

    Valoare iniial: v2 = 0 .( ) ,i j iju v c i j+ = B

    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 2 , 3,5 , 4,1 , 4, 2=B

  • Tehnici de optimizare - Cursul 7 21

    Matricea costurilor

    9 4 13

    1 16 17

    5 6 11

    7 12 19

    7 18 9 16 10

    0 -2 -1

    5 8 2 4 3

    3 4 3 4 1 5

    4 3 4 2 1 3

    3 2 3 2 1 3

    ui

    vj

    Rezolvarea sistemului: pentru

    Valoare iniial: v2 = 0 .( ) ,i j iju v c i j+ = B

    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 2 , 3,5 , 4,1 , 4, 2=B

  • Tehnici de optimizare - Cursul 7 22

    Matricea costurilor

    9 4 13

    1 16 17

    5 6 11

    7 12 19

    7 18 9 16 10

    -1 0 -2 -1

    5 8 2 4 3

    3 4 3 4 1 5

    4 3 4 2 1 3

    3 2 3 2 1 3

    ui

    vj

    Rezolvarea sistemului: pentru

    Valoare iniial: v2 = 0 .( ) ,i j iju v c i j+ = B

    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 2 , 3,5 , 4,1 , 4, 2=B

  • Tehnici de optimizare - Cursul 7 23

    Matricea costurilor

    9 4 13

    1 16 17

    5 6 11

    7 12 19

    7 18 9 16 10

    -1 0 -2 -1

    4 5 8 2 4 3

    3 4 3 4 1 5

    4 3 4 2 1 3

    3 2 3 2 1 3

    ui

    vj

    Rezolvarea sistemului: pentru

    Valoare iniial: v2 = 0 .( ) ,i j iju v c i j+ = B

    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 2 , 3,5 , 4,1 , 4, 2=B

  • Tehnici de optimizare - Cursul 7 24

    Matricea costurilor

    9 4 13

    1 16 17

    5 6 11

    7 12 19

    7 18 9 16 10

    -1 0 -2 -2 -1

    4 5 8 2 4 3

    3 4 3 4 1 5

    4 3 4 2 1 3

    3 2 3 2 1 3

    ui

    vj

    Rezolvarea sistemului: pentru

    Valoare iniial: v2 = 0 .( ) ,i j iju v c i j+ = B

    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 2 , 3,5 , 4,1 , 4, 2=B

  • Tehnici de optimizare - Cursul 7 25

    Matricea costurilor

    9 4 13

    1 16 17

    5 6 11

    7 12 19

    7 18 9 16 10

    -1 0 -2 -2 -1

    4 5 8 2 4 3

    2 4 3 4 1 5

    4 3 4 2 1 3

    2 2 3 2 1 3

    ui

    vj

    Rezolvarea sistemului: pentru

    Valoare iniial: v2 = 0 .( ) ,i j iju v c i j+ = B

    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 2 , 3,5 , 4,1 , 4, 2=B

  • Tehnici de optimizare - Cursul 7 26

    Matricea costurilor

    9 4 13

    1 16 17

    5 6 11

    7 12 19

    7 18 9 16 10

    -1 0 -2 -2 -1

    4 5 8 2 4 3

    3 4 3 4 1 5

    4 3 4 2 1 3

    3 2 3 2 1 3

    ui

    vj

    Test de optimalitate: pentru ?( ) ,i j iju v c i j+ B( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 2 , 3,5 , 4,1 , 4, 2=B

  • Tehnici de optimizare - Cursul 7 27

    Matricea costurilor

    9 4 13

    1 16 17

    5 6 11

    7 12 19

    7 18 9 16 10

    -1 0 -2 -2 -1

    4 5 8 2 4 3

    3 4 3 4 1 5

    4 3 4 2 1 3

    3 2 3 2 1 3

    ui

    vj

    Test de optimalitate: pentru ?( ) ,i j iju v c i j+ B( )3 4 34 3, 4u v c+ > B !

    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 2 , 3,5 , 4,1 , 4, 2=B

  • Tehnici de optimizare - Cursul 7 28

    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 2 , 3,5 , 4,1 , 4, 2=B

    ( ){ }3,4=C

    Matricea costurilor

    9 4 13

    1 16 17

    5 +x 6 11

    7 12 19

    7 18 9 16 10

    -1 0 -2 -2 -1

    4 5 8 2 4 3

    3 4 3 4 1 5

    4 3 4 2 1 3

    3 2 3 2 1 3

    ui

    vj

    mbuntirea soluiei de baz.Determinarea unui ciclu.

  • Tehnici de optimizare - Cursul 7 29

    ( ) ( ){ }3,4 , 3,2=C

    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 2 , 3,5 , 4,1 , 4, 2=B

    Matricea costurilor

    9 4 13

    1 16 17

    5-x +x 6 11

    7 12 19

    7 18 9 16 10

    -1 0 -2 -2 -1

    4 5 8 2 4 3

    3 4 3 4 1 5

    4 3 4 2 1 3

    3 2 3 2 1 3

    ui

    vj

    mbuntirea soluiei de baz.Determinarea unui ciclu.

  • Tehnici de optimizare - Cursul 7 30

    ( ) ( ) ( ){ }3,4 , 3,2 , 2,2=C

    Matricea costurilor

    9 4 13

    1+x 16 17

    5-x +x 6 11

    7 12 19

    7 18 9 16 10

    -1 0 -2 -2 -1

    4 5 8 2 4 3

    3 4 3 4 1 5

    4 3 4 2 1 3

    3 2 3 2 1 3

    ui

    vj

    mbuntirea soluiei de baz.Determinarea unui ciclu.

    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 2 , 3,5 , 4,1 , 4, 2=B

  • Tehnici de optimizare - Cursul 7 31

    Matricea costurilor

    9 4 13

    1+x 16-x 17

    5-x +x 6 11

    7 12 19

    7 18 9 16 10

    -1 0 -2 -2 -1

    4 5 8 2 4 3

    3 4 3 4 1 5

    4 3 4 2 1 3

    3 2 3 2 1 3

    ui

    vj

    mbuntirea soluiei de baz.Determinarea unui ciclu.

    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 2 , 3,5 , 4,1 , 4, 2=B

    ( ) ( ) ( ) ( ){ }3,4 , 3,2 , 2,2 , 2,4=C

  • Tehnici de optimizare - Cursul 7 32

    ( ) ( ) ( ) ( ){ }3,23,4 , , 2 , 4,2 , 2=C

    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 2 , 3,5 , 4,1 , 4, 2=B

    Matricea costurilor

    9 4 13

    1+x 16-x 17

    5-x +x 6 11

    7 12 19

    7 18 9 16 10

    -1 0 -2 -2 -1

    4 5 8 2 4 3

    3 4 3 4 1 5

    4 3 4 2 1 3

    3 2 3 2 1 3

    ui

    vj

    mbuntirea soluiei de baz.Determinarea unui ciclu.

    x = min { 5, 16 } = 5

  • Tehnici de optimizare - Cursul 7 33

    Matricea costurilor

    9 4 13

    6 11 17

    5 6 11

    7 12 19

    7 18 9 16 10

    2 3 2 1 3

    0 5 8 2 4 3

    0 4 3 4 1 5

    0 3 4 2 1 3

    0 2 3 2 1 3

    ui

    vj

    Rezolvarea sistemului: pentru

    Valoare iniial: u1 = 0 .( ) ,i j iju v c i j+ = B

    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 4 , 3,5 , 4,1 , 4, 2=B

  • Tehnici de optimizare - Cursul 7 34

    Matricea costurilor

    9 4 13

    6 11 17

    5 6 11

    7 12 19

    7 18 9 16 10

    2 3 2 1 3

    0 5 8 2 4 3

    0 4 3 4 1 5

    0 3 4 2 1 3

    0 2 3 2 1 3

    ui

    vj

    Test de optimalitate: pentru ?( ) ,i j iju v c i j+ B( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 4 , 3,5 , 4,1 , 4, 2=B

  • Tehnici de optimizare - Cursul 7 35

    Matricea costurilor

    9 4 13

    6 11 17

    5 6 11

    7 12 19

    7 18 9 16 10

    2 3 2 1 3

    0 5 8 2 4 3

    0 4 3 4 1 5

    0 3 4 2 1 3

    0 2 3 2 1 3

    ui

    vj

    Test de optimalitate: pentru ?( ) ,i j iju v c i j+ BSoluie optim. Valoarea optim = 137 + 5(1 4 + 3 1) = 132

    +

    +

    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 4 , 3,5 , 4,1 , 4, 2=B

  • Tehnici de optimizare - Cursul 7 36

    Matricea costurilor

    9 4 13

    6 11 17

    5 6 11

    7 12 +x 19

    7 18 9 16 10

    2 3 2 1 3

    0 5 8 2 4 3

    0 4 3 4 1 5

    0 3 4 2 1 3

    0 2 3 2 1 3

    ui

    vj

    Condiie: pentru De exemplu,( ) ( ) , . .4,3i j iju v c i j+ = B BDeterminarea unei alte soluii optime:

    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 4 , 3,5 , 4,1 , 4, 2=B

    ( ){ }4,3=C

  • Tehnici de optimizare - Cursul 7 37

    Matricea costurilor

    9-x 4 13

    6 11 17

    5 6 11

    7 12 +x 19

    7 18 9 16 10

    2 3 2 1 3

    0 5 8 2 4 3

    0 4 3 4 1 5

    0 3 4 2 1 3

    0 2 3 2 1 3

    ui

    vj

    Condiie: pentru De exemplu,( ) ( ) , . .4,3i j iju v c i j+ = B BDeterminarea unei alte soluii optime:

    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 4 , 3,5 , 4,1 , 4, 2=B

    ( ) ( ){ }4,3 , 1,3=C

  • Tehnici de optimizare - Cursul 7 38

    Matricea costurilor

    9-x 4+x 13

    6 11 17

    5 6 11

    7 12 +x 19

    7 18 9 16 10

    2 3 2 1 3

    0 5 8 2 4 3

    0 4 3 4 1 5

    0 3 4 2 1 3

    0 2 3 2 1 3

    ui

    vj

    Condiie: pentru De exemplu,( ) ( ) , . .4,3i j iju v c i j+ = B BDeterminarea unei alte soluii optime:

    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,3 , 1,5 , 2, 2 , 2, 4 , 3, 4 , 3,5 , 4,1 , 4, 2=B

    ( ) ( ) ( ){ }4,3 , 1,3 , 1,5=C

  • Tehnici de optimizare - Cursul 7 39

    Matricea costurilor

    9-x 4+x 13

    6 11 17

    5 6-x 11

    7 12 +x 19

    7 18 9 16 10

    2 3 2 1 3

    0 5 8 2 4 3

    0 4 3 4 1 5

    0 3 4 2 1 3

    0 2 3 2 1 3

    ui

    vj

    Condiie:


Top Related