Skip to Main Content
Linear Programming and Resource Allocation Modeling
book

Linear Programming and Resource Allocation Modeling

by Michael J. Panik
November 2018
Intermediate to advanced content levelIntermediate to advanced
448 pages
12h 24m
English
Wiley
Content preview from Linear Programming and Resource Allocation Modeling

6Duality Theory

6.1 The Symmetric Dual

Given a particular linear programming problem, there is associated with it another (unique) linear program called its dual. In general, duality theory addresses itself to the study of the connection between two related linear programming problems, where one of them, the primal, is a maximization (minimization) problem and the other, the dual, is a minimization (maximization) problem. Moreover, this association is such that the existence of an optimal solution to any one of these two problems guarantees an optimal solution to the other, with the result that their extreme values are equal. To gain some additional insight into the role of duality in linear programming, we note briefly that the solution to any given linear programming problem may be obtained by applying the simplex method to either its primal or dual formulation, the reason being that the simplex process generates an optimal solution to the primal‐dual pair of problems simultaneously. So with the optimal solution to one of these problems obtainable from the optimal solution of its dual, there is no reason to solve both problems separately. Hence the simplex technique can be applied to whichever problem requires the least computational effort.

We now turn to the expression of the primal problem in canonical form and then look to the construction of its associated dual. Specifically, if the primal problem appears as

then its dual is

Henceforth, this form of the dual will ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Model Building in Mathematical Programming, 5th Edition

Model Building in Mathematical Programming, 5th Edition

H. Paul Williams
Fundamentals of Deep Learning, 2nd Edition

Fundamentals of Deep Learning, 2nd Edition

Nithin Buduma, Nikhil Buduma, Joe Papa

Publisher Resources

ISBN: 9781119509448Purchase book