Dual Problems When Primal in Standard Form

The main objective behind using linear programming is to help identify best allocation of various company resources. When it is referred as the allocation process, then it is certain to include resources like money, material, manpower, and machines etc. that can finally specify activities and also optimize the objectives.

Through linear programming it is also possible to attain the maximum use of any productive factors which can finally help in enhancing decision making quality. With the help of linear programming you can easily highlight bottlenecks in regard to production processes.

While analyzing the primal or dual pair you will get to know about different properties related to problem formulation:

1. The number found in dual variables appear to be same as that of primal constraints
2. The primal as well as dual variables can easily satisfy the non-negativity condition
3. The inequalities appear to be reversed in direction
4. The number related to dual constraints turns out to be same as that of primal variables
5. The maximization problem referred in primal can become maximization problem in dual problem

The standard form of LPP

Suppose, x₁, x₂, ……x_n turns out to be decision variables in case of general LPP. So, it is important to determine values of different variables such as:

Maximize z = c₁ x₁ + c₂ x₂ + …..+ c_n x_n

Subject to the constraints:

a₁₁ x₁ + a₁₂ x₂ + …….. + a_1n x_n = b₁

a₂₁ x₁ + a₂₂ x₂ + …….. + a_2n x_n = b₂

…………………………………………………….

a_m1 x₁ + a_m2 x₂ + …….. + a_mn x_n = b_m

x₁, x₂, …, x_n ≥ 0.

When a linear programming problem is written in such a form then it is said to have standard form. This can further be solved through simplex method.

While discussing about primal or dual problem, it is identified that both shares relationship in regard to solution:

• The primal as well as dual problem comes up with same value when it is referred for optimal objective function. This turns out to be the fact only in case problems come with optimal solutions.
• If x becomes feasible solution to primal problem and then Y is also a feasible solution to dual problem, then it states as w(y) >=  z(x). It is a feature that offers estimate of bounds in regard to dual optimal value and the feasible primal solution is available.

While discussing about simplex method in LPP, it is important to identify that each and every linear program can easily be converted into standard form

In standard form the objective is maximized and constraints become equals as well as variable turn out to be non-negative.

This can be performed in the following manner:

• When the problem is minimized as z and then converted to maximum –z
• When constraint is and this can be converted into equality constraint just by adding up non-negative slack variable. This can finally result in constraint , where

In case the constraint is , then certainly convert into equality constraint just by subtracting any non-negative surplus variable .