Algoritmul Simplex

ALGORITMUL SIMPLEX

Algoritmul simplex se bazeaz pe metoda eliminrii complete de rezolvare a unui sistem de ecuaii liniare adaptat scopului urmrit, adic gsirea numai a soluiilor cu componente nenegative, respectiv a soluiei pentru care funcia liniar f are valoarea optim.

Presupunem mai departe c opt = max, deoarece dac se cere minim din relaia max (-f) = - min (f) rezult c este suficient s se determine max (-f), iar apoi cu semn schimbat vom avea min f.

ntrebrile la care trebuie s rspund algoritmul simplex sunt urmtoarele: cum pornim, cum trecem de la o soluie la alta mai bun i cum ne oprim.

Fie problema de programare liniar:

Folosind metoda eliminrii complete se determin o soluie de baz i presupunem c s-au redus primele m coloane:

n ipoteza c ( i ( 0, i = soluia de baz este:

x B0 = ( (1, (2, , (m, 0, , 0 ) t i f (x B0 ) = c1 (1 + c2 (2 + + cm (m.

Trecem de la soluia de baz x B0 la o alt soluie de baz x B1 care s fie mai bun i n care necunoscuta principal s fie x m+1 n locul lui x 1. Aceasta se face reducnd coloana lui x m+1 i presupunnd c pivot este ( 1, m+1.

Avem:

Dac elementele de pe ultima coloan sunt ( 0 atunci soluia nou obinut este soluie de baz:

x B1 =

Avem i , i = rezult ( 1m+1 (0 i (raport minim) adic trecerea de la o soluie de baz la alt soluie de baz se face reducnd o coloan cu respectarea condiiilor n alegerea pivotului:

- elementul pivot trebuie s fie pozitiv;

- dac n coloana care se reduce sunt mai multe elemente pozitive atunci pivotul va fi acela care furnizeaz cel mai mic raport cnd termenii liberi se mpart la elementele pozitive corespunztoare, din aceast coloan.

Soluia obinut x B1 va fi mai bun dect x B0 dac f (x B1 ) f (x B0 ) ( 0.

Avem f (x B1 ) f (x B0 ) = c m+1 - c 1 ( 1 c 2 - - c m = = (c m+1 (c 1 ( 1m+1 + c 2 ( 2m+1 + + c m ( mm+1 )( =

= ( (c m+1 f m+1) dac f m+1 = c 1 ( 1m+1 + c 2 ( 2m+1 ++ c m ( mm+1 = c BP m+1

Cum ( ( 0 se obine condiia c m+1 f m+1 ( 0, care ne asigur c prin trecerea de la x B0 la soluia x B1 s-a obinut o soluie mai bun.

Atunci cnd toate diferenele c j f j ( 0 soluia nu se mai poate mbuntii i acea soluie de baz este soluia optim a problemei.

Etapele algoritmului simplex sunt:

se determin o soluie de baz a problemei;

se calculeaz valorile f j = c B P j, j = ;

dac exist diferene c j f j ( 0 se trece la o alt soluie de baz (prin reducerea coloanei cu diferena c j f j cea mai mare) iar dac nu exist c j f j ( 0 se trece la etapa 5;

se repet etapele 2 i 3 pn nu mai exist diferene c j f j ( 0 ;

se scrie soluia optim: variabilele bazice au valorile corespunztoare n coloana termenilor liberi, iar cele secundare sunt toate zero, iar valoarea pentru f max = cB B 1 b.

Calculele presupuse de etapele algoritmului simplex se pot organiza ntr-un tabel informaional, denumit tabelul simplex, n care sunt uor de gsit numeroase informaii ale soluionrii prin intermediul rezultatelor numerice.

Prin trecerea de la o etap (iteraie) a tabloului simplex la alta se ine seama de urmtoarele reguli:

se mparte linia pivotului cu pivotul;

coloana pivotului va avea cifra 1 n locul pivotului i zero n rest;

elementele celorlalte coloane ale noului tablou simplex se determin folosind regula dreptunghiului.

Cazul soluiei infinite. Exist situaii n care funcia de optimizat are un maxim infinit, adic valoarea ei poate fi fcut orict de mare. Aceasta se ntmpl dac exist o diferen cj - fj pozitiv, dar pe coloana acesteia nu exist nici un element pozitiv, care s fie luat pivot.

Degenerarea n problemele de programare liniar. Soluia de baz este degenerat dac numrul componentelor sale mai mari dect 0 este mai mic dect m (n coloana b exist 0). Aceast situaie apare, fie la nceput, fie pe parcurs, cnd la introducerea n baz a unui vector, exist mai multe componente pozitive care furnizeaz acelai raport minim. Pentru a evita fenomenul de ciclare, elementul pivot va fi ales acela care furnizeaz cea mai mic linie n ordonarea lexicografic.

Definiie Linia (x1, x2, , xn ; x) este mai mic n ordonarea lexicografic dect linia (y1, y2, , yn ; y) dac x ( y sau x = y i x1 ( y1, sau x = y, x1 = y1, i x2 ( y2, sau x = y, x1 = y1, , xn-1 = yn-1 i xn ( yn.

Soluii multiple. Soluia general. Analiznd tabelul simplex care conine soluia optim se constat c numrul zerourilor din linia diferenelor c j f j este mai mare dect m (diferenele c j f j corespunztoare vectorilor bazei optime sunt nule ) atunci problema poate avea mai multe soluii optime. Celelalte soluii optime se obin reducnd pe rnd, dac este posibil, coloanele care au diferena c j f j = 0. Dup obinerea tuturor soluiilor optime se scrie soluia general ca i combinaie liniar convex a acestora.

Probleme cu soluii impuse. Exist situaii practice n care, din motive diverse, anumite componente ale soluiei sunt restricionate s ia:

1. anumite valori, adic xj = pj pentru un j dat;

2. valori n anumite intervale, adic pj ( xj ( qj, pentru un j dat.

Astfel de situaii sunt socotite modele sau probleme cu soluii impuse atunci cnd restricii precum cele menionate sunt altele dect cele de semn.

Dac se impune condiia xj = pj, atunci se reduce problema la (n-1) variabile, renunnd la variabila xj n funcia obiectiv, dar i n restriciile problemei.

Dac se adaug o restricie de tipul pj ( xj ( qj atunci la restriciile problemei iniiale se mai adaug noi restricii pj ( xj i xj ( qj.

Soluiile problemelor cu soluii impuse nu mai sunt soluii de baz (ele pot avea mai multe componente strict pozitive dect dimensiunea bazei).

Exemplu S se rezolve problema de programare liniar:

(max( f = 4 x 1 +2 x 2 + 5 x 3 + x 4

Pentru rezolvare construim tabelul simplex urmtor:

cBB4251000c

P1P2P3P4P5P6P7b

-

-

0

0-

-

P6P71

-1

2

13

[2]

1

2-1

1

2

12

5

1

20

-1

0

00

0

1

00

0

0

15

3

8

7

-

2

0

0-

P2P6P7[5/2]

-1 /2

5/2

20

1

0

0-5/2

1 /2

3/2

0-11/2

5/2

-3/2

-33/2

-1 /2

1/ 2

10

0

1

00

0

0

11/ 2

3/2

13/2

4

4

2

0

0P1

P2P6P71

0

0

00

1

0

0-1

0

[4]

2-11/5

7/5

4

7/53/5

-1/5

-1

-1/50

0

1

00

0

0

11/5

8/5

6

18/5

fjcj fj4

02

0-4

9-6

72

-20

00

04

-

4

2

5

0P1

P2P3P71

0

0

00

1

0

00

0

1

0-6/5

7/5

1

-3/57/20

-1/5

-1/4

[3/10]1/ 4

0

1/ 4

-1/ 20

0

0

117/10

8/5

3/ 2

3/5

fjcj fj4

02

05

03

-2-1/ 4

1/ 49/4

-9/40

035/2

-

4

2

5

0P1

P2P3P51

0

0

00

1

0

00

0

1

0-1/ 2

1

1/ 2

-20

0

0

15/6

-1/ 3

-1/6

-5/3-7/6

2/ 3

5/6

10/31

2

2

2

fjcj fj4

02

05

05/2

-3/ 20

011/6

-11/65/6

-5/618

-

Astfel, soluia optim a problemei generale este:

x opt = (1, 2, 2, 0) t, f max = 18.

Se vede c nu au fost scrise valorile necunoscutelor de compensare

x 5 = 2, x 6 = 0, x7 = 0.

DUALITATEA

Fie problema de programare liniar numit problem primal (1)

(min( f = cx

(1)

Definiie Se numete duala acestei probleme urmtoarea problem de programare liniar: (max( g = yb

(2)

Teorema Are loc una i numai una din afirmaiile:

a) ambele probleme au soluii optime finite i atunci g max = f minb) una dintre probleme are soluie infinit, iar cealalt problem nu are soluie (posibil) (este incompatibil)

c) una dintre probleme are soluie degenerat, iar cealalt problem poate avea soluii optime multiple.

Definiie Se numete cuplu de probleme duale forma simetric problemele urmtoare:

(min( f = cx

(max( g = yb

(1) i (2)

DIAGRAMA LUI TUCKERPROBLEMA DUALVariabilex1 ( 0x2 ( 0....xn ( 0RelaiiConstante

yn+1 ( 0a11a12....a1n(b1

yn+2 ( 0a21a22....a2n(b2

............................

yn+m ( 0am1am2....amn(bm

Relaii((....((max( g

Constantec1c2....cn(min( f

x = (x1, x2, .. , xn) t - vectorul variabilelor primale de structur

x = (xn+1, xn+2, .. , xn+m) t - vectorul variabilelor primale de compensare

y = (y1, y2, .. , yn) - vectorul variabilelor duale de compensare

y = (yn+1, yn+2, .. , yn+m) - vectorul variabilelor duale de structurn iteraia optim a tabelului simplex se afl componentele soluiilor ambelor probleme, adic:

cBBP1PnPn+1Pn+mb

Componentele bazice ale soluiei optime a

problemei primale

fj

cj- fjfmin = gmax

Variabile duale de compensareVariabile duale de structura-

Exemplu S se rezolve problemele duale simetrice:

(max( f = 3 x1 + 5 x2 + 2 x3 (min( g = 6 y4 + 5 y5 + 7 y6

Rezolvare:

Vom rezolva, pe rnd, cele dou probleme cu algoritmul simplex i apoi vom evidenia, n fiecare tabel i soluia optim a celeilalte probleme:

cBB352000c

P1P2P3P4P5P6b

0

0

0P4P5P63

1

22

[2]

-11

2

11

0

00

1

00

0

16

5

7

fj

cj fj0

30

50

20

00

00

00

-

0

5

0P4P2P6[2]

1/ 2

5/20

1

0-1

1

21

0

0-1

1/ 2

1/ 20

0

11

5/2

19/2

fj

cj fj5/2

1/ 25

05

-30

05/2

-5/20

025/2

-

3

5

0P1P2P61

0

00

1

0-1/ 2

5/4

13/41/ 2

-1/ 4

-5/4-1/ 2

3/ 4

7/40

0

11/ 2

9/4

33/4

fj

cj fj3

05

019/4

-1/ 41/ 4

-1/ 49/4

-9/40

051/4

-

Astfel soluia optim este: x opt = (1/ 2, 9/4, 0, 0, 0, 33/4 ) t, fmax = 51/4.

Soluia problemei duale este y opt = (0, 0, 11/4, 1/ 4, 9/4, 0 ), valori luate din linia cj fj dar cu semn schimbat iar g min = 51/4.

Ne putem convinge de acest fapt prin rezolvarea direct a problemei duale:

bBB000657b

Q1Q2Q3Q4Q5Q6c

-

-

--

-

--1

0

00

-1

00

0

-1[3]

2

11

2

22

-1

13

5

2

6

-

-Q4-

--1/ 3

2/3

1/30

-1

00

0

-11

0

01/3

4/3

[5/3]2/3

-7/3

1/31

3

1

6

-

5Q4Q5

--2/5

2/5

1/50

-1

01/5

[4/5]

-3/51

0

00

0

13/5

-13/5

1/54/5

11/5

3/5

6

0

5Q4Q3Q5-1/ 2

1/ 2

1/ 21/ 4

-5/4

-3/40

1

01

0

00

0

15/4

-13/4

-7/41/ 4

11/4

9/4

gi

bi gi-1/ 2

1/ 2-9/4

9/40

06

05

0-5/4

33/451/4

-

Cum toate diferenele bi gi ( 0, avem soluia optim g min = 51/4 cu yopt = (0, 0, 11/4, 1/ 4, 9/4, 0) respectiv pentru problema primal avem x opt = (1/ 2, 9/4, 0, 0, 0, 33/4 ) t, valori luate din linia bi gi iar fmax = 51/4 = g min . Se vede, ntr-adevr, c s-au obinut aceleai soluii.

Algoritmul simplex dual

Exist situaii cnd prin nmulirea unor restricii cu (-1) apar n tabel vectori ce pot fi considerai n baz, caz n care se adopt o metod puin modificat fa de algoritmul simplex. De fapt este vorba de aplicarea algoritmului simplex, dar asupra problemei duale. Etapele sunt aceleai, dar, dac n coloana b exist elemente negative, atunci alegerea elementului pivot se va face respectnd urmtoarele dou condiii:

- pe linia elementului negativ din coloana b se alege element pivot negativ;

- dac sunt mai multe elemente negative pe aceast linie atunci pivotul va fi acela care furnizeaz cel mai mic raport, n valoare absolut, dar considerat fa de elementele corespunztoare din linia c j f j.

Exemplul S se rezolve, folosind algoritmul simplex dual urmtoarea problem de programare liniar:

(min( f = 4 x1 + 5 x2 + 3 x3

Rezolvare:

(min( f = 4 x1 + 5 x2 + 3 x3

cBB453000c

P1P2P3P4P5P6b

0

0

0P4P5P6-3

-1

[-2]-2

1

-1-1

-2

11

0

00

1

00

0

1-6

-5

-8

fj

cj fj0

40

50

30

00

00

00

-

0

5

0P4P5P10

0

1-1/ 2

3/2

1/ 2-5/2

[-5/2]

-1/ 21

0

00

1

0-3/2

-1/2

-1/26

-1

4

fj

cj fj4

02

3-2

50

00

0-2

216

-

0

3

4P4P3P10

0

1-2

-3/5

1/50

1

01

0

0-1

-2/5

-1/5-1

1/5

-2/57

2/5

21/5

fj

cj fj4

0-1

63

00

0-2

2-1

118

-

Soluia optim va fi x opt = (21/5, 0, 2/5, 7, 0, 0) t i f min = 18.

REOPTIMIZAREA PROBLEMELOR DE PROGRAMARE LINIAR

Modificarea vectorului c

Pornind de la soluia optim a problemei (1) vrem s determinm soluia optim a problemei

(1)

(2)

Se pleac de la iteraia optim a tabelului simplex a problemei (1) n care se recalculeaz elementele liniei cj(1) - fj(1) :

dac cj(1) - fj(1) ( 0 atunci soluia optim a problemei (1) este soluie

optim i pentru problema (2)

dac cj(1) - fj(1) ( 0 atunci se trece la mbuntirea soluiei .

Modificarea vectorului b

Pornind de la soluia optim a problemei (1) vrem s determinm soluia optim a problemei

(3)

Se consider iteraia optim a problemei (1) n care se recalculeaz coloana termenilor liberi B 1 b (1):

dac B 1 b (1) ( 0 atunci soluia este optim;

dac exist elemente n aceast coloan negative, atunci se continu cu

algoritmul simplex dual.

Modificarea unui vector coloan P j din matricea A

Pornind de la soluia optim a problemei (1) vrem s determinm soluia optim a problemei .

(4)

Se consider iteraia optim a problemei (1) n care se recalculeaz elementele coloanei P j astfel B 1 P j(1) .

- dac vectorul P j nu face parte din baza optim atunci se verific condiia de optim doar pentru acest vector i se acioneaz n consecin;

- dac vectorul P j face parte din baza optim atunci se trece la schimbarea bazei.

Adugarea de noi coloane la matricea A

Pornind de la soluia optim a problemei (1) vrem s determinm soluia optim a problemei:

(5)

Pentru reoptimizare se procedeaz ca n precedentele cazuri utiliznd B1. Se vor calcula valorile din liniile f j i c j f j corespunztoare noii coloane i se va aciona n consecin.

Modificarea unei linii a matricei restriciilor

- Pornind de la soluia optim a problemei (1) vrem s determinm soluia optim a problemei:

(6)

- Modificarea unei linii a matricei restriciilor nseamn de fapt modificarea simultan a mai multor coloane ale acestei matrici i ca urmare sunt posibile cazurile:

1) linia modificat nu schimb elementele coloanelor bazice i atunci sunt afectate doar diferenele cj-fj ,2) linia modificat schimb elemente ale coloanelor bazice i atunci sunt afectate att diferenele cj-fj ct i soluia xB.

Observaie

Utilitatea practic a reoptimizrii se poate reflecta prin:

1) eficiena procedeului n raport cu soluionarea problemei modificate ca o problem nou, atunci cnd se poate, deoarece calculele se reiau de la soluia optim a problemei date i se studiaz efectul modificrilor asupra optimalitii soluiei;

2) posibilitatea simulrii unor modificri pentru a cunoate existena sau inexistena unor soluii optime sub influena variaiilor elementelor definitorii ale modelului.

PROGRAMARE LINIAR PARAMETRIC

Considerm problema de programare liniar:

i vom analiza cazurile cnd vectorii b i respectiv c depind liniar de un parametru.

Parametrizarea vectorului c

Fie problema de programare liniar parametric

unde vectori constani.

Pentru rezolvarea problemei (2) se parcurg etapele:

1) pentru t = t0 (fixat) se rezolv problema cu algoritmul simplex;

2) se reoptimizeaz problema de la 1) cu datele c(t);

3) din condiiile de optim cj(t) fj(t) 0 se deduce un subinterval [,] n care soluia gsit este optim.

dac [, ] = [a, b] atunci rezolvarea s-a ncheiat.

dac [, ] [a, b] atunci se trece la etapa urmtoare;

4) se ia i se continu cu reoptimizarea obinnd un nou subinterval [1, 1] etc. se continu astfel, pn cnd reunirea subintervalelor gsite coincide cu [a, b].

Observaie Condiiile de optim cj(t) fj(t) 0 sunt cele care conduc la determinarea subintervalelor n care soluia este optim.

Parametrizarea vectorului b

n problema de programare liniar parametric

unde b(t) = b1 +tb2, t[a, b], b1 +b2 vectori constani

Pentru rezolvarea problemei (3) se parcurg etapele:

1) pentru t = t0 [a, b] se rezolv problema n mod obinuit;

2) se reoptimizeaz problema de la 1) cu datele d(t);

3) din condiiile de admisibilitate B-1b(t) 0 se deduce un interval real [, ] n care soluia gsit este admisibil deci i optim. Dac [, ] = [a, b] rezolvarea s-a ncheiat, astfel ([, ] [a, b]) se trece la etapa urmtoare.

4) se ia t[a, b]\[, ] i se continu cu reoptimizarea aplicnd algoritmul simplex dual, pn cnd reuniunea subintervalelor gsite coincide cu [a, b].

Observaie Condiiile de admisibilitate B-1b(t) 0 sunt acelea care conduc la determinarea subintervalelor n care soluia este optim.

PROBLEME DE TRANSPORT

S considerm m furnizori (distribuitori, productori, etc.) F 1 Fm ai unui produs identic de care ei dispun n cantitile a 1 a m precum i n consumatori sau beneficiari (utilizatori) B 1 B n al cror necesar este respectiv b 1 b n . S notm cu x ij cantitatea care se transport (transfer , aloc) de la F i la B j i cu cij cheltuielile unitare de transport de la F i la B j. Costul transportului cantitii x ij de la F i la B j va fi egal cu c ij x ij iar pentru toi furnizorii i toi beneficiarii costul total va fi egal cu f = care trebuie minimizat. Evident, la nivelul furnizorului F i cantitatea total furnizat va fi egal cu , iar tot ceea ce i poate reveni beneficiarului B j este . Se caut acea variant de transport (sau de alocare) care s satisfac toi partenerii F i i B j i s conduc la un cost total minim, ceea ce nseamn problema:

1. De obicei se urmrete satisfacerea total att a cererii ct i a disponibilului i prin urmare restriciile problemei apar ca egaliti. Acestora li se pot aduga i alte restricii cu semnificaii diverse.

2. Dac n locul unui anumit produs care s poat fi efectiv transportat considerm c a 1 a m sunt suprafee cultivabile de o aceeai calitate, iar B 1 Bn sunt n culturi care au nevoie de un astfel de teren, atunci problema amplasrii optime a culturilor are modelul matematic anterior, dar nu este vorba de o operaiune de transport. Este unul din motivele pentru care spunem modele de tip transport.

Alocarea optim de fonduri bnetiS considerm un anumit fond bnesc de valoare S uniti monetare (u.m) care trebuie repartizat sau alocat:

1. la un moment dat pentru n activiti sau

2. unei anumite activiti la n momente (adic ealonat).

S notm cu x j, j =, partea din fond care se aloc pentru activitatea de ordin j (sau la momentul j) i cu cj, profitul unitar realizat pentru fiecare unitate monetar investit sau alocat. Atunci profitul total va fi: f = c1 x1 + c2 x2 + + cn xn urmnd a fi maximizat, ceea ce conduce la problema:

Este posibil adugarea unor restricii de forma ( j ( x j ( ( j, 1 ( j ( p ( n, n care x j ( ( j ( 0 ar nsemna un prag sau nivel minimal necesar util sub care investiia nu prezint interes, iar x j ( ( j ( S ar nsemna un nivel maximal posibil de credit garantat care poate fi acoperit de ctre debitor prin diverse garanii sau cu averea sa. n acest caz problema devine:

Avnd n vedere consideraiile i exemplul prezentat, putem rezuma faptul c, sub form general, un model liniar de tip transport poate fi scris astfel:

unde: - reprezint fie costul total al operaiunii de tip transport (cnd opt = min), fie profitul total al operaiunii de tip transport (cnd opt = max).

ai reprezint disponibilul furnizorului Fi, ;

bj reprezint necesarul beneficiarului Bj, ;

cij reprezint costul unitar (sau profitul unitar) pe relaia ;

xij reprezint cantitatea transportat (alocat, repartizat, transferat) de la furnizorul Fi la beneficiarul Bj, ; restricia arat c nu se poate aloca tuturor beneficiarilor mai mult dect este disponibil furnizorului Fi;

restricia arat c de la toi furnizorii se aloc pentru beneficiarul Bj cel puin ct este necesarul su;

reprezint disponibilul (sau oferta) tuturor furnizorilor iar reprezint necesarul (sau cererea) tuturor beneficiarilor n ipoteza c nsumrile au sens (n caz contrar nu are sens problema).

Se spune c o problem de tip transport este:

echilibrat dac oferta total este egal cu cererea total a = b

neechilibrat dac oferta total difer de cererea total (a b)

Pentru a evita explicaii i scrieri numeroase i greoaie n prezentarea unei probleme de tip transport, cel mai adesea, se recurge la sintetizarea tuturor informaiilor (cerere, ofert, costuri sau beneficii unitare) ntr-un tabel sub forma urmtoare: (preciznd doar cerina min sau max).

Bj

FiB1B2................BnDisponibil

F1................a1

F2................a2

................................................................................................

Fm................am

Necesarb1b2................bna

b

1. Ansamblul poart denumirea de csu.

2. Conceptul de echilibrare este fundamental pentru construirea procedurii de soluionare a unei probleme de tip transport.

3. Dac egalitatea ntre disponibilul total i necesarul total nu are loc se poate trece la o problem echilibrat prin considerarea fie a unui furnizor fictiv, Fm+1, fie a unui beneficiar fictiv, Bn+1, care ofer sau solicit, diferena dintre cele dou sume.

4. ntruct algoritmul presupune un volum mare de calcule, pentru acest tip de problem de programare liniar se va prezenta un algoritm distributiv.

Metode de gsire a unei soluii iniiale

a) Metoda nord-vest const n a atribui, pe rnd, valori variabilelor ncepnd cu cea din colul nord-vest a tabelului, apoi se continu la fel cu subtabelul rmas.

Astfel x11 = min (a1, b1), dac min (a1, b1) = a1 atunci x12 = ... =x1n = 0, dac min (a1, b1) = b1 atunci x21 = ... = xm1 = 0 i apoi vom continua cu x21 = min (a2, b1-a1) respectiv n cealalt situaie cu x12 = min (a1-b1, b2) etc.

Acest procedeu se repet pn cnd este atribuit i ultima valoare variabilelor.

Valoarea 0 este marcat n tabel printr-un punct.

Exemplu S se stabileasc o soluie iniial folosind metoda nord-vest pentru problema de transport avnd modelul matematic urmtor:

4040 30

2525 20

1035201035

520

[min]f = 4x11 + 2x12 + x13 + 2x21 + x22 + 3x23

f = 4 10 + 2 30 + 1 5 + 3 20 = 165.

b) Metoda elementului (costului ) minim const n a atribui, pe rnd, valori variabilelor ncepnd cu aceea pentru care costul unitar este minim. Apoi se continu cu variabila pentru care costul unitar este minim dintre cele rmase etc. Dac sunt mai multe costuri minime egale atunci se va considera mai nti acea variabil care poate lua valoare mai mare. Valoarea variabilei se determin ca i la metoda nord-vest, considernd minimul dintre disponibilul i necesarul corespunztor.

c) Metoda costului minim pe linie const din a aloca pentru fiecare csu (i, j) o cantitate xij egal cu minimul dintre cererea i oferta existent n momentul acelei alocri, procedeul aplicndu-se pe fiecare linie n ordinea cresctoare a costurilor unitare cij. Algoritmul poate ncepe cu oricare linie dar pentru organizarea calculelor acesta ncepe cu prima linie i decurge ca i n cazul metodei colului din nord-vest.

d) Metoda costului minim pe coloan este un procedeu analog cu precedentul cu singura deosebire c se aplic pe fiecare coloan, preferabil ncepnd cu prima coloan.

Exemplu Folosind metoda elementului minim s se stabileasc o soluie iniial pentru problema formulat n exemplul precedent.

40 30 10

25

1035

1020

x22 = min (25, 35) deci x21 = x23 = 0 apoi x13 = min (40, 20) = 20 iar x12 = min (20, 10) = 10 i x11 = 10. Avem f = 410 + 210 + 120 +125 = 105. mbuntirea soluiei

Fie problema de transport:

Scriem duala acesteia notnd cu u1, u2, ..., um, v1, v2, ..., vn variabilele actuale.

1)Din teorema dualitii avem c este soluie optim dac variabilele duale verific restriciile din problema (2) adic:

(3) ui + vj = cij dac

(4) ui + vj cij dac

2) (3) i (4) sunt de fapt condiiile de optimizare pentru o soluie de baz x = (xij) a problemei de transport.

3) (3) este un sistem de m + n 1 ecuaii cu m + n necunoscute. Pentru rezolvare se alege u1 = 0 i atunci rezolvarea se face direct pe tabelul de soluii, cnd ui i vj se vor trece la marginea tabelului, de aceea se mai numesc i valori marginale.

Definiii

1) O soluie x = (xij) a problemei (1) se numete nedegenerat dac are exact m + n 1 valori nenule, n caz contrar ea va fi soluie degenerat.

2) Se numete ciclu al unei csue o succesiune de csue dou cte dou alturate n aceeai linie, sau respectiv n aceeai coloan.

3) ntr-un ciclu csuele impare sunt: prima (liber), a treia (ocupat), a cincea (ocupat) etc., iar csuele pare sunt a doua (ocupat), a patra (ocupat) etc.

4) Procedeul de mbuntire a unei soluii const n a trece de la o soluie la alt soluie mai bun. Aceasta se realizeaz prin modificarea valorilor variabilelor din csuele ce formeaz un ciclu dup cum urmeaz:

se determin valoarea minim a valorilor variabilelor din csuele pare;

se adun aceast valoare minim la valorile variabilelor din csuele impare;

se scade aceast valoare minim din valorile variabilelor din csuele pare.

ALGORITMUL DISTRIBUTIV

Etapele algoritmului distributiv pentru determinarea soluiei optime a problemei de transport (1) sunt:

1) se determin o soluie iniial de baz;

2) se calculeaz valorile variabilelor duale (valorile marginale) ui, vj ca soluii ale sistemului de ecuaii ui + vj = cij, unde indicii i, j sunt cei ai variabilelor bazice (csuele ocupate);

3) se verific optimalitatea soluiei de baz, adic se verific inegalitatea ui + vj cij pentru toi indicii corespunztori variabilelor nebazice (csue libere);

4) - dac soluia de baz nu este optim se mbuntete soluia;

5) se reiau etapele 2), 3), 4) cu noua soluie de baz i se continu pn cnd toate condiiile de optimalitate sunt ndeplinite;

6) se scrie soluia optim i se calculeaz valoarea minim a funciei scop.

Exemplu S se rezolve problema de transport formulat n exemplul anterior

Rezolvare: Vom parcurge etapele algoritmului distributiv, direct pe tabel. Considerm soluia iniial obinut prin metoda nord-vest. Avem:

v1 = 4v2 = 2v3 = 4

u1 = 040

u2 = 125

103520

ntruct u1 + v3 = 4 > 1 = c13 i u2 + v1 = 3 > 2 = c21 soluia este optim.

Formnd ciclul csuei (1,3) se trece la o soluie mai bun i marcm cu + csuele impare i cu - csuele pare. Se obine soluia:

v1 = 4v2 = 2v3 = 1

u1 = 0

u2 = 1

Deoarece u2 + v1 = 3 > 2 = c21, soluia nu este optim i formm ciclul csuei (2, 1) pentru a obine o soluie mai bun.

v1 = 3v2 = 2v3 = 1

u1 = 0

u2 = -1

Aceasta este soluia optim a problemei de transport:

i fmin = 2 20 + 1 20 + 2 10 +1 15 = 95.

Rezolvarea problemelor de maximizare Exist suficiente situaii practice ale cror modele matematice sunt probleme liniare de tip transport avnd forma matematic:

Pentru determinarea soluiilor de baz, metoda colului din nord-vest rmne neschimbat iar metoda costului minim se nlocuiete cu metoda costului maxim. n ceea ce privete determinarea soluiei optime pornind de la o soluie de baz nedegenerat, n cazul problemei de maximizare se verific inegalitatea ui + vj cij pentru toi i i j.

Degenerare Degenerarea apare, de obicei, n urmtoarele situaii:

la determinarea soluiei iniiale de baz cnd valoarea disponibilului este egal cu valoarea necesarului deci se taie att linia ct i coloana corespunztoare (exceptnd ultima csu ocupat);

n procesul de mbuntire a soluiei cnd valoarea minim din csuele pare este atins n dou sau mai multe csue.

n aceste situaii se obin mai puine csue ocupate, deci variabilele duale nu pot fi determinate. Acest neajuns se nltur prin considerarea unor csue libere ca fiind ocupatecu 0. Acest 0 se consider n csuele cu costuri minime, care nu formeaz cicluri cu csuele deja ocupate, astfel nct n final numrul csuelor ocupate este m + n 1.

Cnd degenerarea apare n a doua situaie, zerourile eseniale se nscriu n acel csue pare care devin libere i n care costurile sunt mai mici.

Soluii multiple Pot exista mai multe soluii atunci cnd, dei soluia este optim, exist csue libere la care ui + vj = cij deci condiia de optim este verificat cu egalitate. Celelalte soluii optime, dac exist, se vor obine urmnd procedeul mbuntirii soluiei cu csuele libere n care ui + vj = cij. Soluia general va fi combinaia liniar convex a soluiilor gsite.

REOPTIMIZAREA PROBLEMELOR DE TRANSPORT

Fie problema de transport:

pe care o presupunem rezolvat cu algoritmul distributiv.

Reoptimizarea n cazul modificrii matricei costurilor

Plecnd de la tabelul care conine soluia optim a problemei (1) se verific optimalitatea acestei soluii folosind elementele :

dac atunci soluia este optim i pentru problema modificat;

dac cel puin o condiie de optim nu este ndeplinit atunci se va trece la mbuntirea soluiei.

Reoptimizarea problemelor de transport n cazul modificrii i/sau necesarului

Pornind de la tabelul care conine soluia optim a problemei (1) cu noile cantiti pentru disponibil i/sau necesar se vor ocupa exact aceleai csue, chiar cu riscul apariiei, n unele csue, a unei valori negative.

Dac toate csuele sunt ocupate cu valori nenegative atunci soluia rmne optim i pentru problema modificat.

Dac cel puin ntr-o csu apare o valoare negativ atunci cnd se formeaz ciclul acestei csue, cu vrf pozitiv n aceast csu se vor modifica valorile variabilelor din csuele acestui ciclu cu cantitatea egal cu valoarea negativ din csua de pornire i apoi se procedeaz dup caz.

Probleme de transport parametrice

Considerm problema de transport:

Parametrizarea matricei C

Presupunem c problema (1) este parametric , . Rezolvarea problemei se face n urmtoarele etape:

1) Pentru t = t0 [a, b] se rezolv problema n mod obinuit;

2) Se reoptimizeaz problema cu valorile cij(t);

3) Din condiiile de optim ui(t) + vj(t) cij(t) se deduce un subinterval [, ] n care soluia gsit este optim. Dac [, ] = [a, b] atunci rezolvarea s-a ncheiat, n caz contrar se continu cu etapa urmtoare.

4) Se ia t [a, b]- [, ] i se continu cu reoptimizarea pn cnd reunirea intervalelor gsite coincide cu [a, b].

Parametrizarea disponibilului i/sau necesarului

Considerm problema (1) n care i/sau , t[a, b]. Rezolvarea problemei se face n urmtoarele etape:

1) pentru t = t0[a, b] se rezolv problema n mod obinuit;

2) se reoptimizeaz problema cu noile valori ai(t), bj(t), decupnd exact aceleai csue ca la punctul 1);

3) din condiiile de admisibilitate (valorile variabilelor din csuele ocupate s fie nenegative) se deduce un subinterval [, ] n care soluia este optim. Dac [, ] = [a, b] atunci rezolvarea s-a ncheiat, n caz contrar se continu cu etapa urmtoare;

4) se ia t [a, b] - [, ] i se continu cu reoptimizarea din cazul cnd soluia nu este admisibil, pn ce reuniunea subintervalelor gsite coincide cu [a, b].

PROBLEME DE TIP TRANSPORT SPECIALE

Exist anumite probleme practice care se aseamn cu modele liniare de tip transport dar care au anumite particulariti sau condiii speciale care se adaug celor care definesc modelul iniial. Prin anumite transformri ele sunt aduse la forma unui model de tip transport i se rezolv cu algoritmul distributiv, dup care se revine la problema iniial.

Modele cu centre legate Se poate ntmpla ca, din motive diverse, doi sau mai muli furnizori s aib oferta grupat (sau ofert de grup), doi sau mai muli consumatori s aib cererea grupat (sau cerere de grup) dar i una i alta, dar costurile unitare s fie individualizate.

Presupunem c furnizorii F1 Fp, p < m au oferta comun. Vom nota cu FG furnizorul grupat. Aducerea problemei la forma obinuit nseamn personalizarea furnizorului comun i acest lucru poate fi realizat prin:

1) identificarea furnizorului grupat cu unul dintre furnizori ceea ce poate conduce de fapt la p probleme obinuite;

2) definirea costurilor (sau beneficiarilor) furnizorului grupat prin n cazul problemelor de minimizare sau prin n cazul problemelor de maximizare.

n mod analog, dac avem cererea grupat B1 Bq, q < n, putem introduce beneficiarul grupat BG a crui personalizare se poate face prin:

1) identificarea beneficiarului grupat cu unul dintre beneficiari, fiind condui la q probleme obinuite;

2) definirea costurilor (sau beneficiilor) beneficiarului grupat prin:

pentru probleme de minimizare sau prin :

pentru probleme de maximizare.

Dac problema are att furnizor grupat ct i beneficiar atunci se poate proceda ca mai sus, secvenial; determinnd mai nti furnizorul comun

i apoi beneficiarul comun sau invers.

Observaie n oricare din situaiile cu elemente grupate se ajunge la mai multe probleme n funcie de modul de alegere sau de definire a personalizrii elementului comun. Aceste probleme sunt diferite n general i implicit i soluiile lor optime sunt diferite. Ca urmare, problema iniial poate fi soluionat n funcie de aceste alegeri, altfel spus, soluia optim a problemei iniiale (cu centre legate) depinde de modul de personalizare a centrelor legate (sau grupate).

Modele cu legturi interzise Dei este vorba de un acelai produs att la ofert ct i la cerere, exist situaii practice de incompatibilitate (sau de necooperare, sau legturi interzise, sau rute interzise) pe anumite relaii sau cupluri (Fi, Bj).

Presupunem c relaia sau legtura Fi0 Bj0 este incompatibil, atunci n tabelul problemei de transport se haureaz csua (i0, j0) pentru a fi evitat n calcule, dup care se rezolv problema n mod obinuit.

Este posibil ca n cazul mai multor (sau al prea multor) restricii de necooperare problema s nu aib soluii admisibile i implicit soluii optime.

Modele cu soluii impuse O problem de tip transport este considerat cu soluii impuse dac exist cel puin o restricie suplimentar de forma: .

Problema impune alocare obligatorie a cantitii xi0j0 = d pe relaia (Fi0, Bj0), 1 i0 m, 1 j0 n. Ca urmare problema iniial se modific la nivelul furnizorului Fi0 care va dispune de cantitatea (ai0 d) i la nivelul beneficiarului Bj0 care va solicita (bj0 d). Relaia impus (Fi0, Bj0) va rmne acum ca o legtur interzis i se rezolv problema.

Exemplu Un grup de trei bnci finaneaz un anumit obiectiv a crui realizare dureaz patru ani. Disponibilul bancar, necesarul anual precum i costurile unitare ale operaiunii (uniti cheltuite pentru 100 uniti investite) sunt date n tabelul urmtor (fondurile se exprim n milioane). Se cere planul optim de finanare avnd n vedere c banca B3 aloc exact 20 u.m. n ultimul an i 40 u.m. n anul al doilea.

Ani

BnciA1 A2A3A4Disponibil

bancar

B1100

B2200

B3300

Necesar

anual175175120130600

Rezolvare:

Deoarece x14 = 20 u.m. i x32 = 40 u.m. problema modificat (ca i cum ar avea legturi interzise) este dat de tabelul:

Ani

BnciA1 A2A3A4Disponibil

bancar

B1 4

20100

B2200

B3 5

40300

Necesar

anual175175120130600

Observaie Din cauza celor dou csue blocate o soluie iniial de baz nu poate fi gsit aplicnd metodele cunoscute. Este necesar s se aib n vedere poziiile ocupate, de la nceput sau pe parcurs.

Aplicm metoda costului minim pe linie i obinem soluia optim care evident c nu mai este soluie de baz i anume:

v1 = -2v2 =1v3 = 1v4 = 0

u1 = 0

4

20 80

u2 = 1200 65

u3= 3 5

40260 85 40

175

135120

40110

45

, fmin = 885.

c12

EMBED PBrush

x11

c11

x12

EMBED PBrush

c1n

x1n

EMBED PBrush

c21

x21

EMBED PBrush

c22

x22

EMBED PBrush

c2n

x2n

EMBED PBrush

xm1

cm1

EMBED PBrush

xm2

cm2

EMBED PBrush

xmn

cmn

EMBED PBrush

cij

EMBED PBrush

xij

4

x11

EMBED PBrush

2

x12

EMBED PBrush

1

x13

EMBED PBrush

4

10

EMBED PBrush

2

30

EMBED PBrush

1

EMBED PBrush

2

x21

EMBED PBrush

1

x22

EMBED PBrush

3

x23

EMBED PBrush

2

EMBED PBrush

1

5

EMBED PBrush

3

20

EMBED PBrush

4

10

EMBED PBrush

2

10

EMBED PBrush

1

20

EMBED PBrush

2

EMBED PBrush

1

25

*

3

10

4

4

EMBED PBrush

30

-

2

2

EMBED PBrush

+

4

1

EMBED PBrush

3

2

EMBED PBrush

5

+

1

1

EMBED PBrush

20

-

3

3

EMBED PBrush

20

EMBED PBrush

EMBED PBrush

3

2

10

-

4

4

EMBED PBrush

30

+

2

2

EMBED PBrush

20

4

1

EMBED PBrush

+

3

2

EMBED PBrush

25

-

1

1

EMBED PBrush

3

3

EMBED PBrush

10

3

4

EMBED PBrush

2

2

20

EMBED PBrush

4

1

20

EMBED PBrush

2

2

10

EMBED PBrush

1

1

15

EMBED PBrush

0

3

EMBED PBrush

1

EMBED PBrush

4

EMBED PBrush

4

EMBED PBrush

2

EMBED PBrush

5

EMBED PBrush

1

EMBED PBrush

1

EMBED PBrush

5

EMBED PBrush

4

EMBED PBrush

3

EMBED PBrush

2

EMBED PBrush

3

EMBED PBrush

1

EMBED PBrush

4

EMBED PBrush

2

EMBED PBrush

5

EMBED PBrush

1

EMBED PBrush

1

EMBED PBrush

4

EMBED PBrush

3

EMBED PBrush

0

2

5

4

4

4

4

4

PAGE 4

_1267202807.unknown

_1267202900.unknown

_1267203224.unknown

_1267203242.unknown

_1267203336.unknown

_1267203338.unknown

_1267203339.unknown

_1267203337.unknown

_1267203258.unknown

_1267203334.unknown

_1267203335.unknown

_1267203262.unknown

_1267203249.unknown

_1267203232.unknown

_1267203238.unknown

_1267203229.unknown

_1267203180.unknown

_1267203209.unknown

_1267203213.unknown

_1267203184.unknown

_1267202910.unknown

_1267203175.unknown

_1267202906.unknown

_1267202862.unknown

_1267202882.unknown

_1267202890.unknown

_1267202896.unknown

_1267202887.unknown

_1267202874.unknown

_1267202879.unknown

_1267202870.unknown

_1267202835.unknown

_1267202845.unknown

_1267202850.unknown

_1267202841.unknown

_1267202825.unknown

_1267202830.unknown

_1267202821.unknown

_1267202501.unknown

_1267202755.unknown

_1267202788.unknown

_1267202797.unknown

_1267202802.unknown

_1267202792.unknown

_1267202769.unknown

_1267202778.unknown

_1267202761.unknown

_1267202617.unknown

_1267202738.unknown

_1267202743.unknown

_1267202622.unknown

_1267202529.unknown

_1267202533.unknown

_1267202506.unknown

_1267202312.unknown

_1267202337.unknown

_1267202385.unknown

_1267202401.unknown

_1267202341.unknown

_1267202325.unknown

_1267202329.unknown

_1267202315.unknown

_1267202292.unknown

_1267202302.unknown

_1267202305.unknown

_1267202298.unknown

_1267202282.unknown

_1267202287.unknown

_1099234574.unknown

_1267202277.unknown

_1099245784.unknown

_1099249403.unknown

_1099249470.unknown

_1099247009.unknown

_1099234636.unknown

_1099055934.unknown

_1099060883.unknown

_1098979587.unknown