One of the most important discoveries in the development of linear programming was the concept of duality. It discovered the fact that every linear programming problem has associated with it another linear programming problem. The original problem is called the primal, while the other is called its dual. In general, either problem can be considered as the primal, and the other considered as its dual.

Linear programming problems are optimization problems in which the objective function and the constraints are all linear. In the primal problem, the objective function is a linear combination of n variables. There are m constraints, each of which places an upper bound on a linear combination of the n variables. The goal is to maximize the value of the objective function subject to the constraints. A solution is a vector (a list) of n values that achieves the maximum value for the objective function. In the dual problem, the objective function is a linear combination of the m values that are the limits in the m constraints from the primal problem. There are n dual constraints, each of which places a lower bound on a linear combination of m dual variables.

The relationship between the primal and dual problems is a very useful one. The optimal solution of either problem reveals information concerning the optimal solution of the other problem. If the optimal solution to one is known, then the optimal solution to the other is readily available. This fact is important because a situation may arise where the dual is easier to solve than the primal.

Consider a simple example:

• There is a small company in which has recently become engaged in the production of office furniture. The company manufactures tables, desks and chairs. The production of a table requires 8 kgs of wood and 5 kgs of metal and is sold for \$80; a desk uses 6 kgs of wood and 4 kgs of metal and is sold for \$60; and a chair requires 4 kgs of both metal and wood and is sold for \$50. We would like to determine the revenue maximizing strategy for this company, given that their resources are limited to 100 kgs of wood and 60 kgs of metal.

  Max. $Z = 80x_1 + 60x_2 + 50x_3 \\ 8X_1 + 6X_2 + 4X_3 ≤ 100 \\ 5X_1 + 4X_2 + 4X_3 ≤ 60 \\ X_1, X_2, X_3≥ 0$

  Where $X_1, X_2, X_3$ are the number of tables, desks and chairs to be manufactured.

• Now consider that there is a much bigger company which has been the lone producer of this type of furniture for many years. They don't appreciate the competition from this new company; so they have decided to tender an offer to buy all of their competitor's resources and therefore put them out of business. The challenge for this large company then is to develop a linear program which will determine the appropriate amount of money that should be offered for a unit of each type of resource, such that the offer will be acceptable to the smaller company while minimizing the expenditures of the larger company.

  Min. $W = 100Y_1 + 60Y_2 \\ 8Y_1 + 5Y_2≥80 \\ 6Y_1 + 4Y_2 ≥ 60 \\ 4Y_1 + 4Y_2 ≥ 50 \\ Y1, Y2≥ 0$

  Where $Y_1, Y_2$ are the prices per kg of wood and metal respectively.