Algoritmul Simplex Dual

Imagine preview
(7/10 din 1 vot)

Acest referat descrie Algoritmul Simplex Dual.
Mai jos poate fi vizualizat un extras din document (aprox. 2 pagini).

Arhiva contine 1 fisier doc de 10 pagini .

Iti recomandam sa te uiti bine pe extras si pe imaginile oferite iar daca este ceea ce-ti trebuie pentru documentarea ta, il poti descarca. Ai nevoie de doar 4 puncte.

Domeniu: Economie

Extras din document

Există situaţii în care pentru rezolvarea unui program liniar, dispunem de o soluţie de bază care nu este admisibilă.

Admisibilitate primală şi duală

Fie (P) un program liniar în formă standard:

Fie B o bază a programului (P), I mulţimea indicilor coloanelor din B, J mulţimea indicilor coloanelor din A care nu sunt în B. Am scris (P) în forma:

numită forma explicită a programului (P) în raport cu baza B.

Să considerăm acum dualul programului (P):

Aducem sistemul de inegalităţi uA ≥ c la forma standard introducând variabilele de abatere v1, v2, ..., vn reunite în vectorul linie v.

Partiţionând:

sistemul liniar din (FSQ) devine succesiv:

Deoarece B este nesingulară rezultă:

(1)

Introducem u:

Eliminăm u din funcţia obiectiv duală:

In acest fel, am adus (FSQ) la forma echivalentă:

Variabilele originale ui , i=1,...,m fiind legate de variabilele vj , j=1,...,n prin relaţia (1).

Programul (QB) se va numi forma explicită a dualului (Q) în raport cu baza B.

Pentru a sublinia simetria existentă între problemele (PB) şi (QB) le vom scrie alăturat atât scalar cât şi matricial:

Cu ajutorul relaţiei (1) am rescris dualul (Q) în alte variabile care sunt supuse condiţiei de nenegativitate ca şi variabilele programului primal (P). Putem vorbi acum de soluţii şi soluţii admisibile pentru programul (Q) şi când facem acest lucru ne referim la forma echivalentă (QB).

Fisiere in arhiva (1):

  • Algoritmul Simplex Dual.doc