Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Doar rabdarea si perseverenta in invatare aduce rezultate bune. stiinta, numere naturale, teoreme, multimi, calcule, ecuatii, sisteme
Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

Informatica


Index » educatie » Informatica
» Rezolvarea problemelor de programare liniara


Rezolvarea problemelor de programare liniara


REZOLVAREA PROBLEMELOR DE PROGRAMARE LINIARA

 FUNDAMENTELE ALGORITMULUI SIMPLEX

Consideram problema de programare liniara sub forma standard:

min (max) (z = c’x)

Ax = b                                                                                     (1)



x ³ 0

unde

A I Mm,n(R) ,  b I Rm , c I Rn , x I Rn .

Presupunem in plus ca liniile matricei A sunt liniar independente (rang(A) = m £ n).

Luam in discutie cazul m<n, deoarece in caz contrar problema de optimizare este triviala.

In detaliu, problema (1) devine:


min (max) (z =)

                                           (2)

.

Definitia 1.      (i). Vectorul x I Rn  se numeste program al problemei (1) daca satisface sistemul de restrictii, deci daca Ax = b, x0.

(ii). Programul x se numeste program de baza al problemei (1) daca coloanele matricei A, corespunzatoare componentelor nenule ale lui x sunt liniar independente.

(iii). Programul de baza x se numeste nedegenerat daca are exact m componente nenule si degenerat in caz contrar.

(iv). Se numeste program optim al problemei (1) un program care confera functiei obiectiv valoarea optima.

Notam cu P si respectiv cu S multimea programelor, respectiv multimea programelor optime ale problemei (1):

           

Observatii.      (i). Un program de baza are cel mult m componente nenule.

(ii). Oricarei baze B ce se obtine din matricea A, (BI Mm(R), rang B = m), care satisface proprietatea ca , i se asociaza programul de baza

 

unde, xB=B-1b, xS = 0 si invers (oricare program de baza corespunde cel putin unei baze B).

(iii). Daca B este o baza si A = ( B S ), sistemul Ax = b este echivalent cu

xB = B-1b - B-1SxS                                             (3)

sau, mai detaliat :

,                       (4)

unde am notat :

 si .            (5)

Am folosit notatia simplificata urmatoare:

                                   

                                    .

 

(iv). In baza relatiei (3) functia obiectiv poate fi exprimata numai cu ajutorul variabilelor secundare astfel:

                                (6)

unde:

                                  (7)

                                   (8)

            Intr-adevar,

                       

Fie acum x un program de baza corespunzator bazei B, adica  () si

Presupunem in cele ce urmeaza ca  si ca problema (1) este problema de minimizare.

Teorema 1. (Test de optimalitate).

Daca , atunci problema de programare liniara (1) are optim finit; B este baza optima, un program optim este    , iar valoarea optimului este .

Demonstratie. Din (6) deoarece si  rezulta ca , prin urmare B este baza optima, iar  este valoarea functiei obiectiv.

Teorema

Daca exista astfel incat  atunci programul asociat bazei B nu este optim (cu exceptia eventual a cazului cand programul este degenerat) si el poate fi imbunatatit daca

Demonstratie. Din (6) tinand seama de faptul ca  si  rezulta:

,

deci baza B nu mai ramane optima, existand o baza mai buna care se obtine din baza B prin introducerea in baza a coloanei (variabilei) ak (xk).

Teorema 3. (Criteriul de imbunatatire a programului).

Daca exista cu  si cu , atunci  poate creste pana la valoarea:

                                                                (9)

pentru care se obtine un nou program de baza asociat bazei:

Demonstratie. Intr-adevar, datorita conditiei , cresterea lui  este limitata de minimul mentionat in enunt, deoarece pentru a nu iesi din tronsonul programelor, adica pentru ca , din (5) rezulta:

                        , adica,

                        .

In ipoteza ca minimul se atinge pentru indicele , atunci  poate creste pana la valoarea (9).

Teorema 4. (Criteriul de recunoastere a infinititudinii optimului).

Daca existacu  si daca  pentru toti , atunci problema are optim infinit (-).

Demonstratie. Din (4)  deoarece  rezulta ca:

,

deci xk poate creste nemarginit (), iar din (6) rezulta ca:

                        .

Observatie. Functia obiectiv tinde catre de-a-lungul razei:

                       

In cazul problemei (1) de maximizare teoremele 1 - 4 devin:

Teorema 1’. Daca, atunci problema de programare liniara (1) are optim finit; B este baza optima, un program optim este    , iar valoarea optimului este .

Teorema 2’. Daca exista astfel incat  atunci programul asociat bazei B nu este optim (cu exceptia eventual a cazului cand programul este degenerat) si el poate fi imbunatatit daca

Teorema 3’. Daca exista cu  si cu , atunci  poate creste pana la valoarea:

pentru care se obtine un nou program de baza asociat bazei:

Teorema 4’. Daca exista cu  si daca  pentru toti , atunci problema are optim infinit (+).

Observatie. Oricarei baze B i se asociaza sistemul de valori; .

Aceste valori se trec intr-un tabel, numit tabel simplex, de forma urmatoare:

c1

…

cl

…

cm

cm+1

…

ck

…

cn

cj

VB

VVB

x1

…

xl

…

xm

xm+1

…

xk

…

xn

c1

x1

1

…

0

…

0

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

cl

xl

0

…

1

…

0

…

…



…

…

…

…

…

…

…

…

…

…

…

…

…

cm

xm

0

…

0

…

1

…

…

0

0

…

0

0

…

…

Am presupus ca primele m variabile (coloane) sunt variabile (coloane) de baza.

Algoritmul simplex este o metoda de explorare sistematica si economica a programelor de baza ale unei probleme de programare liniara, sau, cu alte cuvinte, o metode de trecere de la un program de baza la altul in sensul optimizarii (maximizarii, sau minimizarii) functiei obiectiv, pana la atingerea optimului, daca acesta exista.

Algoritmul simplex este asadar un algoritm iterativ, fiecare iteratie corespunde unei baze (unui program de baza, unui tabel simplex).  

Prima linie si prima coloana a tabelului simplex sunt utile numai la prima iteratie a algoritmului simplex.

Teorema 5. Formulele de transformare ale tabelului simplex prin trecere de la baza  la  sunt:

  ; ,;

            , ; , , ;(10)

                                                       

;

, .

                                                                                                           

            Demonstratie. Se folosesc relatiile (5) si (6). Din (5), pentru i = l rezulta:

,                        

si mai departe

,

de unde, prin identificare, rezulta primele doua relatii din (10). Am notat:  si  .

            In aceeasi relatie (5) inlocuim pe    obtinut mai sus si rezulta:

= =             ,

de unde, prin identificare, rezulta urmatoarele doua relatii din (10).

Ultimele doua relatii din (10) se obtin, tot prin identificare, din relatia (6) in care folosim aceeasi expresie a lui  rezultata din (5):   

           

Algoritmul simplex in cazul problemei (1) de minimizare consta in urmatoarele:

Pasul 1.   Se determina o baza initiala  (de preferat );

Se calculeaza , ,  ,  si se intocmeste tabelul simplex corespunzator bazei .

Pasul    Testul de optimalitate si criteriul de intrare in baza.

2.1.            Daca  pentru toti , atunci baza  este

optima, deci programul corespunzator bazei ,

este programul optim, iar este valoarea optima a

functiei obiectiv. STOP.

2.2.            Daca exista astfel incat atunci baza

nu este optima si ea poate fi imbunatatita introducand in baza pe .

Luam  astfel incat .

Pasul 3.   Criteriul de iesire din baza.

3.1.            Daca exista  astfel incat si,

 ,  atunci problema are optim infinit. STOP.

3.         Daca exista astfel incat si exista astfel incat , atunci se determina astfel incat:

.

In acest caz iese din baza.

Pasul 4.   Se trece de la baza  la ,

,

se transforma tabelul simplex dupa formulele date de teorema 5 si se reia algoritmul de la pasul

Observatie. In cazul in care problema este de maximizare Pasul 2 devine Pasul 2’, iar Pasul 3 devine Pasul 3’:

Pasul 2’.   Testul de optimalitate si criteriul de intrare in baza.

2’.1.     Daca  pentru toti , atunci baza  este

optima, deci programul corespunzator bazei ,

este programul optim, iar este valoarea optima a

functiei obiectiv. STOP.

2’.        Daca exista astfel incat atunci baza

nu este optima si ea poate fi imbunatatita introducand in baza  pe .

Luam  astfel incat .

  METODA CELOR DOUA FAZE

Pentru aplicarea algorimului simplex este necesara existenta unei baze initiale, de dorit matrice unitate, deci a unui program de baza initial. Mentionam doua metode pentru determinarea unui program de baza initial: metoda celor doua faze si metoda penalitatii. Vom prezenta in continuare prima dintre metodele mentionate.

Prima faza ne permite sa determinam o baza initiala  (in cazul in care aceasta exista).

            Ne propunem sa rezolvam problema:

                                                                                       (11)

Etapa 1. Se rezolva problema de programare liniara:

                                                            (12)     

Am presupus , , fiind vectorul variabilelor artificiale.

 Observatii. (i). Nu este necesar sa se introduca m variabile artificiale. Este insa necesar sa se introduca atatea variabile artificiale cati vectori unitari lipsesc  pentru a forma o baza unitara.

(ii). Problema (12) se poate scrie in detaliu astfel:

                                           (12’)                                       

(iii). Problema (12) poseda un program de baza initial (in limbaj geometric, multimea Pa a programelor problemei (12) poseda un varf) de forma:

            .

(iv). Valoarea minima a functiei obiectiv a problemei (12) este .

(v). Daca  atunci multimea P a programelor problemei (11) este vida.

(vi). Daca  atunci, indiferent de faptul ca nici-o variabila artificiala nu este variabila de baza, sau ca exista cel putin o variabila artificiala de baza (evident cu valoare nula), un varf al multimii Pa programelor problemei (12) este un varf al multimii P a programelor problemei (11), caz in care se trece la etapa

Etapa  Se rezolva problema initiala, pornind cu baza obtinuta in finalul etapei 1. Daca atunci etapa a doua este consistenta, in caz contrar etapa a doua este inconsistenta, problema initiala neadmitand programe de baza.

Observatii. (i). Daca nici-o variabila artificiala nu face parte din baza, se aplica algoritmul simplex pentru multimea P si functia obiectiv z pana se obtine optimul.

(ii). Daca exista cel putin o variabila artificiala in baza, aplicam algoritmul simplex pentru multimea Pa, cu mentiunea ca ne restrangem numai la muchiile lui Pa, care mentin valoarea nula a lui w, caz in care programul optim (varful optim) va apartine si lui P.

Observatie. Din relatiile (5), (7) si (8) rezulta ca in cadrul unei iteratii simplex, pentru calculul elementelor tabelului simplex este suficienta cunoasterea inversei bazei curente, adica B-1.

Deoarece nu toate elementele tabelului simplex sunt necesare in cadrul unei iteratii, iar calculul tuturor elementelelor scade eficienta algoritmului, prezentam in continuare algoritmul simplex-revizuit care constituie o varianta “mai economica” a algoritmului simplex. Aceasta varianta este recomandata indeosebi atunci cand n >> m.

Tabelul algoritmului simplex-revizuit are urmatoarea forma:

0

-1

0

.

.

.

0

Prima linie a tabelului corespunde primei faze (daca aceasta este necesara), iar cea de a doua linie a tabelului corespunde celei de a doua faze.

In cadrul algoritmului simplex-revizuit un rol deosebit il joaca matricea incadrata din tabelul asociat acestuia si matricea extinsa, adica matricea:

.

Observatii: (i).  ;

            (ii).

            (iii). ;

            (iv). ;

            (v). .







Copyright © 2017 - Toate drepturile rezervate

Informatica


Access
Adobe photoshop
Autocad
Baze de date
C
Calculatoare
Corel draw
Excel
Foxpro
Html
Internet
Java
Linux
Mathcad
Matlab
Outlook
Pascal
Php
Powerpoint
Retele calculatoare
Sql
Windows
Word


Proiect informatic analiza si proiectarea sistemului informational privind evidenta cǍrtilor din biblioteca filialǍ de stiinte economice
Principii de proiectare si sabloane de proiectare
ATESTAT PROFESIONAL INFORMATICA FARMACIE
Controlul accesului
DAREA IN FUNCTIUNE A SISTEMULUI INFORMATIC
Efectul Stroop. Implicatii ale cuvintelor tabu in Efectul Stroop.
Auditul - provocarea guvernantei corporative
Descrierea designului aplicatiei - Centru de testare offline
Proiectarea Software - Modele ale proiectarii software
Globalizarea sistemelor informationale