Dualidade

Disponível somente no TrabalhosFeitos
  • Páginas : 3 (629 palavras )
  • Download(s) : 0
  • Publicado : 19 de dezembro de 2012
Ler documento completo
Amostra do texto
ISEGI - Nova
undergraduate program
(licenciatura)
Fall 2012
1

operations research:
duality
1.  finding the dual of a linear programming
problem
2.  economic interpretation of the dualproblem
3.  the dual Simplex method

operations research:
duality
Primal

Dual

The matrix with the constraint coefficients in the dual problem
is AT, where A is the matrix with the constraintcoefficients in
the corresponding primal problem.

operations research:
duality
Max problem
constraint i



Min problem
variable i




=
variable j


unrestricted sign

≥constraint j







unrestricted sign

=

Matrix A

Matrix AT

Coefficients of the objective function

Independent terms of constraints

Independent terms of constraintsCoefficients of the objective function

operations research:
duality

 
 

The dual of a dual problem is the primal problem
If x is any feasible solution of the primal and w is any feasiblesolution of the dual, then

 

If x* is a feasible solution of the primal and w* is a feasible
solution of the dual, such that

, then they are

optimal solutions of the respective problems 

A feasible solution x* for the primal is optimal iff there is a
feasible solution w* for the dual such that

operations research:
duality
Economic interpretation of the dual problemExample: factory produces desks, tables and chairs
Inputs/Output

Desk

Table

Chair

Total available

Wood (amount)

8

6

1

48

Assembling (hours)

4

2

1.5

20Polishing (hours)

2

1.5

0.5

8

Profit per unit (Euros)

60

30

20
unit profit corresponding to each output

amount of inputs
that producing one
desk requires

available amounts operations research:
duality
Economic interpretation of the dual problem
Primal

Dual

Let’s imagine that an entrepreneur wants to buy all the resources of the factory.
The current...
tracking img