Dualidade

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 dual problem
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 constraint coefficients 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 constraints

Coefficients 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 feasible solution 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 problem
Example: 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

20

Polishing (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 owner