According to Encyclopedia Britannica, linear programming is a mathematical modelling technique in which a linear function is maximized or minimized when subjected to various constraints. This technique has been useful for guiding quantitative decisions in business planning, in industrial engineering, and—to a lesser extent—in the social and physical sciences.
Application of the method of linear programming were first attempted in the late 1930s by the Soviet mathematician Leonid Kantorovich and by the American economist Wassily Leontief in the are of manufacturing schedules and of economics, respectively, but their work was ignored for decades. During the World Was II, linear programming was used extensively to deal with transportation, scheduling, and allocation of resources subject to certain restrictions such as costs and availability. These applications did much to establish the acceptability of this method, which gained further acceptance in 1974 with the introduction of simplex problem by George Dantzig, an American mathematician which simplified the solution of linear programming to a greater extent.
However, as increasingly more complex problems involving more variables were attempted, the number of necessary operations expanded exponentially and exceeded the computational capacity of even the most powerful computers. Then, in 1979, the Russian mathematician Leonid Khachiyan discovered a polynomial-time algorithm—in which the number of computational steps grows as a power of the number of variables rather than exponentially—thereby allowing the solution of hitherto inaccessible problems. However, the algorithm developed by Khachiyan which was called the ellipsoid method was slower than the simplex method when practically applied. In 1984 Indian mathematician Narendra Karmarkar discovered another polynomial-time algorithm, the interior point method, that proved competitive with the simplex method.
Basically, linear programming is looking at how objective can be achieved. Objectives are either to maximise an opportunity that add value or minimise action plan that will erode value. What readily comes to mind are usually maximising profits and minimising cost. This minimisation or maximisation objectives are usually subject to some constraints. These constraints are those resources that are needed to achieve the objectives but are in themselves limited in supply thereby making the decision maker to work within the available resources. There is also a constraint which is very important if we are to solve linear programming problem and that is what we referred to as the non-negativity constraint. The non-negativity implies that 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.
The next step after getting our objective and constraints spelt out is to solve the linear programming problem. There are basically two methods that can be used to achieve this. The first is the graphical method where the variable of the constraints are plotted on a graph and see how those variables are bounded. The bound of the graph will then be use to decide which of the (x,y) variable will fit into the objective already stated and this will also depend on whether the problem is maximisation or minimisation one. The other solution is known as the simplex method which is a set of iteration of the variables of the constraint equation and then substitute the result into the objective function to decide which is the optimal and again depending on whether the problem is minimum or maximum problem.
Linear programming problems have been proven to be a tool good enough for any optimal problem that can be expressed as a linear relationship in the face of some constraints. Advanced computing tool has also made the solution to any linear problem easy thereby, making decision making much easier for decision makers.
SGD
Your mind and your emotions