Linear Programming Linear programming is a nonstatistical mathematical technique whereby the maximization or minimization of a linear expresion of variables, call the objective function, is determined in the presence of known or assumed restrictions, call constraint. In essence, it's a procedure for solving the problems in which there are more variables than simultaneous equations in which the variables are expressed. No probability or statistics are needed to study linear programming. The mathematics involved in linear programming is relatively easy to understand and to manipulate in contrast to calculus.
Linear equations and inequations form the mathematical skeleton around which linear programming is built. A linear function called the object function is to be maximized or minimized in some sense, like optimzed.Most real world problems have many possible solutions. The purpose of optimization is to choose from among many possible solutions the "best" possible solutions. Some example of "best" are highest profit, lowest cost, largest sales, lowest production time, etc. The optimization of the objective functions take place in teh presence of known or assumed restriction.
The technical term constraints is used to describe the restrictions present in linear programming problem.The constraints are expressed mathemically as inequalities. In a practical real-world situation, the constraints are generated by the presence of limited resources or commodities such as capital manpower and raw material. Mathematically, inequations can be converted to equations by the introduction of slack variables. Linear programming can be dated from the year 1947 when G.B.
Dantzing evolved an efficent technique call the Simplex Method, for solving linear programming problems.The following decades, the rapid development of both the theory and applications of linear programming which were aided by the simultaneous introduction of the electronic computers. One of the first probelm to be solved by the simplex method was Stigler's diet problem (1945). Here is the diet problem Protein Fat Carbohydrate Cost 100g bread 40 5 205 2.
2p 100g cheese 60 380 60 12p Minimal daily requirement 300 790 1350 The problem is determine how much bread and cheese Mrs. Jones should buy each day in order to minimize the cost of the diet, whilst fulfilling the calorie requirements. Suppose shy buys x' * 100g of cheese and x'' * 100g of cheese, then the mathematical problem, known as a linear programme is as follows. Minimize z=2.2x' + 12x'' (Cost Of Diet) Subject To 40x' + 60x'' > or = 300 (At least 300 cal of protein) 5x' + 380x'' > or = 790 (At least 790 cal of fat) 205x' + 60x'' > or = 1350 (At least 1350 cal of carbo.) x' > or = 0, x2 > = 0 (quantites must be non-negative) The easiest and most illustrative method of solving problems in two unknowns is the graphical method.
The value of x' and x'' satisfying 40x' + 60x'' > or = 300 lies in the upper half-plane bounded by the straight line 40x' + 60x'' = 300, so the x' and x'' satistying all the above inequalities lie in the intersection of their respective half - plane.Interger Solutions Provided the supplies and demands are positive intergers, the matrix minimum method always leads to and optimal solution with integer values as the method only involves operations on integers which results in integers. Obviously a non-integer optimal solution would be useless. Uniqueness It can happen that two or more differnet allocations of ships between ports give rise to thesame minimum cost. However, if v'=u'.
