Rules for Forming the Dual Linear Programming Problem

Given the importance of duality, a list of simple rules that can be used to form the dual program to any given primal program would be useful. Four such rules exist. They are as follows:

1. Change a maximize objective to minimize, and vice versa.

2. Reverse primal constraint inequality signs in dual constraints (i.e., change > to <, and < to >).

3. Transpose primal constraint coefficients to get dual constraint coefficients.

4. Transpose objective function coefficients to get limits in dual constraints, and vice versa.

(The word transpose is a matrix algebra term that simply means that each row of coefficients is rearranged into columns so that row 1 becomes column 1, row 2 becomes column 2, and so on.)

To illustrate the rules for transformation from primal and dual, consider the following simple example.

Primal Problem

subject to a11 Q1 + a12Q2 + a13Q3 < ra a21Q1 + a22Q2 + a23Q3 < r2 Q1, Q2, Q3 > 0

where n is profits and Q is output. Thus, n1, n2 and n3 are unit profits for Q1, Q2 and Q3, respectively. The resource constraints are given by r1 and r2. The constants in the primal constraints reflect the input requirements for each type of output. For example, a11 is the amount of resource r1 in one unit of output Q1. Similarly, a12 is the amount of resource r1 in one unit of output Q2, and a13 is the amount of resource r1 in one unit of output Q3. Thus, a11Q1 + a12Q2 + a13Q3 is the total amount of resource r1 used in production. The remaining input requirements, a21, a22 and a23, have a similar interpretation. For convenience, this primal problem statement can be rewritten in matrix notation as follows:

Was this article helpful?

0 0
Your Retirement Planning Guide

Your Retirement Planning Guide

Don't Blame Us If You End Up Enjoying Your Retired Life Like None Of Your Other Retired Friends. Already Freaked-Out About Your Retirement? Not Having Any Idea As To How You Should Be Planning For It? Started To Doubt If Your Later Years Would Really Be As Golden As They Promised? Fret Not Right Guidance Is Just Around The Corner.

Get My Free Ebook


Post a comment