Dualidade

Páginas: 3 (629 palavras) Publicado: 19 de dezembro de 2012
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...

Por favor, assinar para o acesso.