Linear programming problems can be used to solve many problems in transportation, production, and commodity pricing. Variations of linear programming problems can arise when one wants to answer questions of maximization or minimization, but the overall techniques is homogenous among most variations of the problems. Non-linear programming problems, such as the Cobb-Douglas Production Function maximization can be handled with multivariable calculus, but many interesting problems such as the assigment model or the transportation model are discrete in nature. As the number of constraints approaches infinity then the linear-programming problem becomes non-linear and subject to these calculus techniques. In this entry the continuity of the function will be replaced with finite constraints so that only the methods used in linear programming will be useful, but it is important to note that in the limit there is a convergence between the linear and non-linear programming methods.
Linear Programming is a technique for optimizing a linear objective function subject to a set of linear constraints. Typically the set of linear constraints are in the form of equalities and inequalites which converm a convex polyhedron. This convex set determines the feasible solution region in cases where the problem has a feasible solution and is properly defined. The method for solving linear optimization problems within this feasible convex set is called the Simplex Method. The simplex method was created by George Dantzing who earned Bachelor’s degrees in mathematics and physics at the University of Maryland. Mr. Dantzing also earned a Master Degree in Mathematics from the University of Michigan and later completed his PhD at Berkeley where he arrived late to one of his statistics classes and assumed that the problems written on the board where homework. He went home and solved the problems. The problems where unsolved (unproved) statistical theorems and this legendary story was the inspiration for the 1997 movie GoldWill Hunting.
Dr. Dantzing worked on his linear programming models to help the war effort during WWII and was able to use the simplex method to help the U.S. Army better plan for logistics, transportation, and diet plans. Dr. Dantzing also worked at RandCorporation, The Airforce Office of the Comptroller, and U.S. Airforce Office of Statistical Control. He later became professor of Industrial Engineering at UC Berkely where he formed the Operations Research Center. He later joined Stanford where he held the title Professor of Operations Research and Computer Science.
Example (Source–An Introduction to Linear Programming and Game Theory, THIE and KEOUGH, 2008)
Imagine that you are a new manager in a petroleum refinery and you were hired to minimized the cost of refining petroleum into gasoline and diesel. There are four different processes to refine produce the diesel and gasoline. Each process involves varying amounts of labor and two raw materials (hydrogen and water). The four processes also produce different quantities of gasoline and diesel, and you can also purchase gasoline for a certain price. There are minimum production quotas for gasoline (2600) and diesel (1300). There are also a set of constraint on the inputs which limit the amounts that can be used of each; 450 labor hours, 4200 gallons of water, and 2000 cubin feet of hydrogen. The table below summarizes the cost of 1 hour of operation of each process.
Your goal as a manager is to pick the process or combination of processes and purchases of gasoline will meet or exceed the quotas and still be within the resource constraints. This is in essence a cost minimization problem with several linear constraints. The formal mathematical formulation of this kind of a problem in general would be.
Where “c” is the cost vector transposed so that it would be a column vector, “x” is the combination of processes that are part of our objective. The dot product of these two vectors forms the objective function. The matrix “A” would have the columns as processes and the rows as cost per raw material so that the entry aij would be the cost of using resource i in production process j.
The problem in the above table has been augmented with a varibles section where you will place your objective function and constraints. Once helpful formula that comes in handy is the =SUMPRODUCT(C4:F4,C$15:F$15). The SUMPRODUCT function is the same a the dot product function used commonly in linear algebra and multivariable calculus. The inputs are two arrays of similar dimension whom you want to take the dot product of. You can use the SUMPRODUCT function to specify the objective function which will be the dot product of, <process 1, process 2, process 3, process 4><cost of process 1, cost of process 2, cost of process 3, cost of process 4>. The constraints will follow a similar construct with the exception of the inequalities. Here is an example of the labor constraint dot product, <process 1, process 2, process 3, process 4>< 8,10,6,12> <= 450.
Once the objective function and the constraint formulas have been placed in the in the spreadsheet you can begin using Excel Solver.
Here is how you find and use solver on Excel:
1) Go to Tools and look for Solver.
1a) If you can’t find solver then go to add ons and find the Solver and add it to your toolbar
2) Open up the solver and unput all of the constraints and the objective function into the solver
3) Make sure you go to the Options tab and specify a linear model and non-zero values.
4) Click solve and you should get the numbers in the above matrix
Conclusion: Based on this example you will minimize cost by using 4.8 hours of the first process, 25.1 hours of the second process, 12.1 hours of the fourth process, and you will buy 181 gallons of gasoline from the third party. This will yield a minimum cost of $26, 845 and no other combination of production processes would yield a smaller cost. All resources will be used except 14 hours of labor which can be used as a buffer in avoiding overtime expenses should there be some mechanical problem. The quota for gasoline and diesel production are also meet so we have solved the problem within the production constraints and minimized the cost.