Scribd
Upload
21 views8 pages

Dual Problems

The document discusses duality in linear programming, specifically the relationships between primal and dual linear programs. It explains that the primal and dual problems swap their objective functions, variables and constraints. For example, in the primal the number of variables is equal to the number of constraints in the dual. It also describes properties of primal-dual pairs, such as if one problem is feasible the other is too with the same optimal value, and if one problem is unbounded so is the other. It provides examples of obtaining the dual linear program given various primal problems.

Uploaded by

julee kumari
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
21 views8 pages

Dual Problems

The document discusses duality in linear programming, specifically the relationships between primal and dual linear programs. It explains that the primal and dual problems swap their objective functions, variables and constraints. For example, in the primal the number of variables is equal to the number of constraints in the dual. It also describes properties of primal-dual pairs, such as if one problem is feasible the other is too with the same optimal value, and if one problem is unbounded so is the other. It provides examples of obtaining the dual linear program given various primal problems.

Uploaded by

julee kumari
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 8

Duality in Linear Programming

Primal-Dual Relationships (Pairs)


Primal LP Dual LP
Maximization Problem Minimization Problem
Number of Variables Number of Constraints
≤ or ≥ type of constraint Non-negative variable
= type constraints Unrestricted Variable
Unrestricted Variable = type constraint
Objective function coefficient for jth RHS constant for jth constraint
variable
RHS constraint for ith constraint Objective function coefficient for ith
variable
Coefficient (aij) for jth variable in ith Coefficient (aij) for ith variable in jth
constraint constraint.
Primal-Dual Properties
• If the primal or dual has a finite solutions, then the other one
also possesses the same with equal values of the objective.
• If any of the two problems has only an infeasible solution,
then the values of the objective function of the other is
unbounded.
• The value of the objective function for any feasible solution of
the primal is less than the value of the objective function for
any feasible solution of the dual.
Primal-Dual Properties
• If either the primal or dual has an unbounded objective
function value, the solution to the other problem is unbounded.
• If the primal has a feasible solution but the dual does not have,
then the primal will not have a finite optimal solution and vice
versa.
Problem 1
Obtain the dual for the primal LPP given below:
Minimize Z = x1 – 3x2 – 2x3
Subject to the constraints:
3x1 –x2 +2x3 ≤ 7
2x1 – 4x2 ≥ 12
-4x1 +3x2 +8x3 = 10

Where x1,x2≥0 and x3 is unrestricted


Problem 2
Obtain the dual for the primal LPP given below:

Maximize Z = 2x1 + x2 +x3


Subject to the constraints:
x1 + x2 + x3 ≥ 6
3x1 – 2x2 + 3x3 = 3
-4x1 +3x2 -6x3 = 1
Where x1, x2 and x3 ≥ 0
Problem 3
Obtain the dual for the primal LPP given below:
Maximize Z = 3x1 + x2 +2x3 – x4
Subject to the constraints:
2x1 – x2 + 3x3 +x4 = 1
x1 + x2 –x3 –x4 = 3
x1, x2 ≥ 0 and x3, x4 are unrestricted in sign
Problem 4
Minimize Z = 3x1 -2x2 + x3
Obtain the dual for the primal LPP given below:
Subject to the constraints:
2x1 – 3x2 + x3 ≤ 5
4x1 – 2x2 ≥ 9
-8x1 + 4x2 + 3x3 = 8
x1, x2 ≥ 0 and x3 is unrestricted

You might also like