Elements of a Linear Programming Problem (LPP)
Primal, Canonical, Dual and Graphical Solutions
Linear programming is viewed as a revolutionary development giving man the ability to state general objectives and to find, by means of the simplex method, optimal policy decisions for a broad class of practical decision problems of great complexity. In the real world, planning tends to be ad hoc because of the many special-interest groups with their multiple objectives. ~George Dantzig
The LPP technique was first introduced in 1930 by Russian mathematician Leonid Kantorovich in the field of manufacturing schedules and by American economist Wassily Leontief in the field of economics. After a decade during World War II, these techniques were heavily adopted to solve problems related to transportation, scheduling, allocation of resources, etc. In 1950, the first simplex method algorithm for LPP was created by American mathematician George Dantzig.
Elements of a basic LPP
Decision Variables: These are the unknown quantities that are expected to be estimated as an output of the LPP solution.
Objective Function: All linear programming problems aim to either maximize or minimize some numerical value representing profit, cost, production quantity, etc. It evaluates the amount by which each decision variable would contribute to the net present value of a project or an activity.
Objective Function coefficient: The amount by which the objective function value would change when one unit of a decision variable is altered, is given by the corresponding objective function coefficient.
Constraints: The restrictions or limitations on the total amount of a particular resource required to carry out the activities that would decide the level of achievement in the decision variables. In the standard form of a linear programming problem, all constraints are in the form of equations.
Non-negative constraints: Each decision variable in any Linear Programming model must be positive irrespective of whether the objective function is to maximize or minimize the net present value of an activity. This is a critical restriction.
The other two elements are Resource availability and Technological coefficients which can be better discussed using an example below. A feasible solution to the linear programming problem should satisfy the constraints and non-negativity restrictions. A feasible solution to an LPP with a maximization problem becomes an optimal solution when the objective function value is the largest (maximum). Similarly, a feasible solution to an LPP with a minimization problem becomes an optimal solution when the objective function value is the least (minimum).
Any LPP assumes that the decision variables always have a power of one, i.e. they are not raised to any power greater or lesser than one.
The dual representation of LPP
Any LPP problem can be converted to its corresponding pair, also known as dual which can give the same feasible solution of the objective function. If the primal is a maximization problem then all the constraints associated with the objective function must have “less than equal to” restrictions with the resource availability, unless a particular constraint is unrestricted (mostly represented by “equal to” restriction). If any constraint has any “greater than equal to” restriction with resource availability then primal is advised to be converted into a canonical form (multiplying with a “minus”) so that restriction of a maximization problem is transformed into “less than equal to”.
Similarly, if the primal is a minimization problem then all the constraints associated with the objective function must have “greater than equal to” restrictions with the resource availability unless a particular constraint is unrestricted (mostly represented by “equal to” restriction). If any constraint has any “less than equal to” restriction with resource availability then primal is advised to be converted into a canonical form (multiplying with a “minus”) so that restriction of a minimization problem is transformed into “greater than equal to”.
The aforementioned steps of canonical form are only necessary when one is required to rewrite a primal LPP to its corresponding dual form by hand. In general, designated software is capable of solving the problem implicitly.
The necessary conditions for applying LPP are a defined objective function, limited supply of resource availability, and non-negative and interrelated decision variables.
If the decision variables are non-positive (i.e. “less than equal to zero” instead of “greater than equal to zero”) then they need to be transformed in the canonical form before dual exercise.
Graphical Solution
We can see that the value of the objective function value for both the primal and dual LPP remains the same at 1288.9. In primal, the objective was to maximize because of which no other point other than Point-C (X1=51.1, X2=52.2) can give any higher value of the objective function (15*X1 + 10*X2). Hence although the feasible region is the shaded region inside points A, B, C & D, yet the optimal solution is achieved at Point-C. In the primal case, any points below the constraint lines 1 & 2 are desirable, because we want to maximize the objective function for given restricted constraints having limited availability.
However, in the dual case, any points above the constraint lines 1 & 2 are desirable, because we want to minimize the objective function for given constraints which are abundant. The objective was to minimize because of which no other point other than Point-B (Y1=4.4, Y2=11.1) can give any lower value of the objective function (65*Y1 + 90*Y2).
Therefore for a maximization problem, the optimal point moves away from the origin, whereas for a minimization problem, the optimal point comes closer to the origin.
The limitation of this graphical illustration is that in cases of more than 2 decision variables we would need more than 2 axes and thus the representation becomes difficult. Hence the optimal point can still be checked in cases where we have 2 decision variables and 2 or more constraints of a primal problem, however, the corresponding dual having more than 2 decision variables become clumsy to plot.
Linear programming has nothing to do with computer programming. The use of the word programming here means “choosing a course of action”. Linear programming involves choosing a course of action when the mathematical model of the problem contains only linear functions. ~AWSCCFO
Footnotes
This article is an introduction to the elements of the Linear Programming Problem (LPP). Hence understanding the concepts touched upon briefly may help to grasp the applications related to LPP.
LPP applications are the backbone of more advanced concepts on applications related to Integer Programming Problem (IPP), Multicriteria Decisions, and Non-Linear Programming Problem.
The conversion between primal to dual and then again dual of the dual to get back primal are quite common in entrance examinations that require intermediate mathematics like GATE, IES, etc.
These concepts also help in applications related to Operations Research along with Statistics and Machine learning. Apart from Microsoft Excel, the “PuLP” package in python and “IpSolve” in R may be exploited for solving small to medium scale problems.
References
An introduction to Management Science by Anderson, Sweeney, Williams, Camm, Cochran, Fry, Ohlman
Web and Open Video platform sharing knowledge on LPP
Professor Prahalad Venkateshan, Production and Quantitative Methods, IIM-Ahmedabad
Linear programming was and is perhaps the single most important real-life problem. ~Keith Devlin
