Linear and Non-Linear Programming - Report Example

"Programming, both linear and non-linear, is entirely a mathematical technique. Its economic meaning is therefore nil". (W.Baumol). Introduction: Most of the decision models are formulated in terms of mathematical symbols and relations. Mathematics gives precision which is important in decisions. Decisions have to be precise and sharp. To the extent that the economic decisions are measurable and quantifiable, the use of mathematics is acceptable. Symbols and numbers alone do not suffice; additionally, the logic of reasoning behind those numbers and symbols is also required. Scientific decisions arrived through the use of mathematical tools and statistical techniques should have an intuitive appeal and logical support, otherwise, the manager will be in trouble. Regression, for example, may help the manager to forecast his sales based on past record, but he must make sure that the user of his product has not undergone any changes in taste and preference. Therefore, an econometric model may prove a better aid than pure mathematics and statistics. Linear and Non linear programming: In linear programming, the statement of the optimisation (maximisation or minimisation, as the case may be) problem runs in a linear form where these variables are restricted to values satisfying a system of linear constraints, i.e., a system of linear equations, and linear inequalities. In any optimisation, problem involving a single inequality constraint, the LaGrange method can still be used and is quite simple. However, when more than one inequality constraint is involved, linear programming will be a better method. In fact, the linear programming technique differs from the classical optimisation technique based on calculus, and it deals with optimisation problem in which the optimiser faces inequality constraints, and where the constraints as well as the objective function are all linear rather than non-linear. For example, while making the purchase decision, the buyer is required to finance the expenditure out of his or her budgeted income, B. Thus: B=Px X+Py Y, where x and y are quantities of two items purchased at their respective prices, Px and Py. In linear programming, the budge constraint takes the form of an inequality; Px X+Py Y, < B By liberalising the constraint requirement, this new (linear programming) framework of optimisation makes the problem more interesting and more realistic. Linear Programming (LP) is a mathematical method to determine optimum allotment of scarce resources. LP can be applied practically in almost all aspects of business like Transportation & distribution, advertising & production planning and the like. A linear programming solves the objective functions which are to be optimized and is linear. As such, the relations between the variables which correspond to the resources will also become linear. This problem solving method was first formulated and solved in the late 1940's. Seldom there is a novel mathematical technique being used with such a wide application as LP. In the present days this theory is productively implemented to problems of capital budgeting, conservation of resources, economic growth prediction, and transportation systems. Of late LP has also helped to solve and unite many outstanding applications. The most vital facet of a linear programming problem is to set it up appropriately for manual or automated solution. This calls for properly understanding the natures of the objective function and constraints so that their equations and inequalities may be well planned and formatted. Problem solving: The Transportation Problem Transportation models play a key role in logistics and supply chain management for decreasing cost and enhancing service. Therefore, the goal is to find the most cost effective way to transport the goods. Let us consider a model with 2 origins and 2 destinations. The supply and demand at each origin (e.g.; warehouse) O1, O2 and destination (e.g.; market) D1 and D2, together with the unit transportation cost are summarized in the following table. The Unit Transportation Cost Matrix D1 D2 Supply O1 20 30 200 O2 10 40 100 Demand 150 150 300 Let Xij's denote the amount of shipment from source i to destination j. The LP formulation of the problem minimizing the total transportation cost is: Min 20X11 + 30X12 + 10X21 + 40X22 subject to: X11 + X12 = 200 X21 + X22 = 100 X11 + X21 = 150 X12 + X22 = 150 all Xij 0 The feasible region is bounded so that one can use the algebraic method. This is because the transportation problem is a balanced one (total supply = total demand) and all constraints are in equality form. Moreover, any one of the constraints will be redundant too. (It should be kept in mind that adding any two constraints and subtracting another one, we obtain the remaining one). If we delete the last constraint, the problem reduces to: Min 20X11 + 30X12 + 10X21 + 40X22 subject to: X11 + X12 = 200 X21 + X22 = 100 X11 + X21 = 150 all Xij 0 However, the algebraic method has no limitation on the LP dimension. The constraints are already at binding (equality) position. It should be noted that we have here, m=3 equality constraints with (four implied non-negative) decision variables. Therefore, out of these four variables there is utmost m=3 variables with positive value and the rest must be at zero level. For example, by setting any one of the variables in turn to zero, we get: X11 X12 X21 X22 Total Transportation Cost 0 200 150 -50 infeasible 200 0 -50 150 infeasible 150 50 0 100 8500 50 150 100 0 6500 Now by setting any one (or more) variables to zero, it is easy to see, by inspecting the constraints that all other solutions are infeasible. Thus, from the above table, we obtain the optimal strategy to be: X11 = 50, X12 = 150, X21 = 100, and X22 = 0, with the least total transportation cost of $6,500. The findings in the above example can be generalized by Algebraic Method in the following main Economic result: Given an LP having a bounded feasible region, with m constraints (excluding any sign constraints such as non-negativity conditions) and n decision variables, if n m then at most m decision variables have positive value at the optimal solution and the rest of (i.e., n-m) decision variables must be set at zero level. This result holds if the problem has a bounded unique optimal solution. Courtesy (http://www.mirrorservice.org/sites/home.ubalt.edu/ntsbarsh/Business-stat/opre/partVIII.htm#rCarpenterPr) Non-linear program: Production and Operation Management Applications: Most of the practical nonlinear mathematical program leads to optimizing a quotient of 2 functions subject to a set of linear constraints. The following fractional optimization problem is from Chadha (1999) that is solved by a specialized solution algorithm therein. Max f(X) = (2X1 + 6X2) / (X1 + X2 + 1) subject to: X1+ X2 4 3X1 + X2 6 X1-X2 = 0 X1 0, X2 0 Clearly, the non-negativity conditions indicate that the denominator of the objective function does not vanish within the feasible region; therefore, this is a continuous optimization problem with bounded feasible region. We now follow the algorithm: Step 1: Since the feasible region is only a line segment, there are no interior critical points. Step 2: Keep in mind that, for this two-dimensional problem, the feasible region is the line segment joining the following two vertices: A=(3/2, 3/2), and B=(2, 2) with f(A)= 3, and f(B)= 16/5. Step 3: Finding the critical points on the line segment: The parametric representation of the line segment AB is: X1 = 3/21 + 22 = 3/21 + 2(1 - 1) = 2 - 1/2 X1 = 3/21 + 22 = 3/21 + 2(1 - 1) = 2 - 1/2 Therefore, the parametric representation of the problem over AB is: Max f(1) = (16 -41) / (5 - 1), for 0 1 1 The derivative of f(1) is: f '(1) = -4 /(5 - 1)2 which is always negative over its domain. And as such, there is no critical point for this problem. Step 4: Now by evaluating f(X) at vertices, we conclude that the optimal solution is at (2, 2) with an optimal value of 16/5. This solution is superior to the solution (X1, X2) = (3/2, 3/2), with objective value of 3, obtained in the above reference. By having the above information, one can readily construct the numerical tight bounds for the objective function, that is, 3 (2X1 + 6X2) / (X1 + X2 + 1) 16/5, is over its feasible region. Conclusion: It cannot be said that linear and non linear programming does have any economic values. Most of the economic decisions can be taken based on linear and non linear problem solving methods. References: 1. Journal of Economic Behavior & Organization, Volume 65, Issues 3-4, March 2008, Pages 573-584 2. Arsham, H 2005, Tight bounding of continuous functions over polyhedrons: A new introduction to exact global optimization, International Journal of Pure and Applied Mathematics, 19(3), 393-413. 3. Chadha, S 1999, A linear fractional program with homogenous constraints, Opsearch, 36(4), 390-398. 4. http://www.mirrorservice.org/sites/home.ubalt.edu/ntsbarsh/Business-stat/opre/partVIII.htm#rCarpenterPr 5. Salvatore, D 2008, Look Inside This Book Managerial Economics : Principles & Worldwide App, Oxford University Press N Delhi 6. Craig Petersen, H, Cris Lewis, W 1990, Managerial economics London, Collier Macmillan Read More