0.1 Linear Programming - Mathematics

1 Linear ObjectivesBy the end of this unit you will be able to: formulate simple Linear Programming problems in terms of an objective function to be maxi-mized or minimized subject to a set of constraints. find feasible solutions for maximization and minimization Linear Programming problems usingthe graphical method of solution. solve maximization Linear Programming problems using the simplex method. construct the Dual of a Linear Programming problem. solve minimization Linear Programming problems by maximizing their IntroductionOne of the major applications of Linear algebra involving systems of Linear equations is in findingthe maximum or minimum of some quantity, such as profit or cost.

2 In Mathematics the processof finding an extreme value (maximum or minimum) of a quantity (normally called a function) isknown Programming (LP)is a branch of Mathematics which dealswith modeling a decision problem and subsequently solving it by mathematical techniques. Theproblem is presented in a form of a Linear function which is to be optimized ( maximized orminimized) subject to a set of Linear constraints. The function to be optimized is known as theobjective Programming finds many uses in the business and industry, where a decision maker may wantto utilize limited available resources in the best possible manner.

3 The limited resources may includematerial, money, manpower, space and time. Linear Programming provides various methods ofsolving such problems. In this unit, we present the basic concepts of Linear Programming problems,their formulation and methods of Formulation of Linear Programming problemsMathematically, the general Linear Programming problem (LPP) may be stated as:Maximize or MinimizeZ=c1x1+c2x2+..+cnxnsubject toa11x1+a12x2+..+a1nxn( ,=, )b1a21x1+a22x2+..+a2nxn( ,=, )b2(1)..am1x1+am2x2+..+amnxn( ,=, )bmx1, x2.

4 , xn 0wherei(i)the functionZis the objective function.(ii)x1, x2, .. , xnare the decision variables.(iii)the expression ( ,=, ) means that each constraint may take any one of the three signs.(iv)cj(j= 1, .. , n) represents the per unit cost or profit to thejthvariable.(v)bi(i= 1, .. , m) is the requirement or availability of theithconstraint.(vi)x1, x2, .. , xn 0 is the set of non-negative restriction on the LPP. In real life problemsnegative decision variables have no valid this module we shall only discuss cases in which the constraints are strictly inequalities (eitherhave a or ).

5 In formulating the LPP as a mathematical model we shall follow the following four thedecision variablesand assign symbols to them (egx,y,z,..orx1,x2,x2,..). These decision variables are those quantities whose values we wish to the set if constraints and express them in terms of inequalities involving thedecision the objective function and express it is terms of the decision thenon-negativity will use the following product mix problem to illustrate the formulation of an ExampleA paint manufacturer produces two types of paint, one typeof standard quality (S) and the other of top quality (T).

6 To make these paints, he needs two ingre-dients, the pigment and the resin. Standard quality paint requires 2 units of pigment and 3 units ofresin for each unit made, and is sold at a profit of R1 per unit. Top quality paint requires 4 unitsof pigment and 2 units of resin for each unit made, and is sold at a profit of per unit. Hehas stocks of 12 units of pigment, and 10 units of resin. Formulate the above problem as a linearprogramming problem to maximize his profit?We make the following table from the given (R/Unit) follow the four steps outlined above for solving LP our prototype Example , the number of units of S-type and T-type paint are the first constraint is the number of units of pigment available, while the second constraintis the number of units of resin available.

7 It is required that the total pigment and resin useddoes not exceed 12 and 10, : for S is 2 Resin: S = 3for T is 4T = 2 Therefore the required mathematical expressions for the constraints are2S+ 4T 123S+ 2T we letPbe the profit, then the objective in our example is to maximize profitsP=S+ , the number of units of S times R1plusthe number of units of T times . addition to the given constraints, there are nonnegativity constraints which ensure that thesolution is meaningful. This is a requirement that whatever the decision, the decision variablesshould not be 0, T 0We can now write the complete mathematical model of the problem described in Example asMaximise:P=S+ to: 2S+ 4T 123S+ 2T 10S 0, T 0(2)The above problem is an example of a maximization LPP.

8 Maximization LPPs are usually identifiedby the in all the constraints. Minimization problems can be identified by a in all the the next example we formulate a minimization (Diet problem) A house wife wishes to mix two types of foodF1andF2in such a way that thevitamin contents of the mixture contain at least 8 units of vitamin A and 11 units of vitamin E60/Kg and FoodF2costs E80/kg. FoodF1contains 3 units/kg of vitamin A and 5units/kg of vitamin B while FoodF2contains 4 units/kg of vitamin A and 2 units/kg of vitamin this problem as a Linear Programming problem to minimize the cost of the make the following table from the given (in Kg)RequirementcontentF1F2(in units)Vitamin A (units/kg)348 Vitamin B (units/kg)5211 Cost (E/Kg)6080iiiIn formulating the LPP we use the following number of kilograms of the foodsF1andF2contained in the mixture are the decisionvariables.

9 Let the mixture containx1Kg of FoodF1andx2Kg of this example, the constraints are the minimum requirements of the vitamins. The minimumrequirement of vitamin A is 8 units. Therefore3x1+ 4x2 8 Similarly, the minimum requirement of vitamin B is 11 units. Therefore,5x1+ 2x2 cost of purchasing 1 Kg of foodF1is cost of purchasing 1 Kg of foodF2is total cost of purchasingx1Kg of foodF1andx2Kg of foodF2isC= 60x1+ 80x2which is the objective non-negativity conditions arex1 0, x2 0 Therefore the mathematical formulation of the LPP isMinimize:C= 60x1+ 80x2 Subject to: 3x1+ 4x2 85x1+ 2x2 11x1 0, x2 The graphical method of solutionThegraphical methodof solving a Linear Programming problem is used when there are only twodecision variables.

10 If the problem has three or more variables, the graphical method is not that case we use thesimplex methodwhich is discussed in the next begin by giving some important definitions and concepts that are used in the methods of solvinglinear Programming set of values of decision variables satisfying all the constraints of a Linear pro-gramming problem is called asolutionto that solutionAny solution which also satisfies the non-negativity restrictions of theproblem is called afeasible feasible solutionAny feasible solution which maximizes or