Linear Programming Problem (LPP) 2.1 INTRODUCTION Linear Programming constitutes a set of Mathematical Metho and solution of certain kinds of constrained optimizatio The Mathematical presentation of a Linear Progra tive function and one or more linear constraints wit mn problems. mming, Problem in the form of a ¥ linear chien h equations or inequations cons tions/inequations. This technique has met outstanding success in the solution of sade like production planning and scheduling, personal assignment, finance plannine, tions, competitive decision making and so on 2.2 GENERAL MODEL OF THE LINEAR PROGRAMMING PROBLEM Maximize/Minimize Z = ¢,x, +¢,x, +... +¢,x, subject to the constraints aX) $a,.%) 4... tax, +. +a,x +. The above problem can be expressed using mathematical symbol as follows: Maximize/Minimize Z = }\¢,x, iaLinear Programming Problem (LPP) 7 Subject to SIME N20 (forje t, 2, 2.3 CHARACTERISTICS OF AN LPP a) Regarding the symbol used in the General Model each constraint can take either $ or = or 2. by The decision variables x,'s should take non-negative values only. (j= 1, 2, 0.) Mm) ©) The valu 3 Aye (fori SW Qe je 2. . n) can be got from the given information. These values are called parameters and assumed to be ced constants, 2.4 ASSUMPTIONS OF LINEAR PROGRAMMING The Model of Linear Programming is based on certainty, and devisability assumptions rity (which contains proportionality and additivity), It requires that the objective function and the constraints of linear programming problems lead themselves to a mathematical formulation in linear form. The term proportionality means that the contribution of each decision variable to the value of the objective function is proportional to the value assumed by the decision variable, Also additivity implies that the overall contribu- tions of the objective are obtained by the algebraic sum of the individual contributions. Certainty: It implies that the parameters c, b, and a, (for i= 1, ..... M5 j= 1, «sss. n) of a Linear Programming model are fixed i.e., known with certainty, Devisability: It requires that the decision variables be continuous, such that they can assume any value (fractional or Integer), based on the limitations imposed on the decision variables. + Common errors one can think of while constructing the constraints are i, Insertion of inconsistent constraints Omission of some constraints iii. Usage of different dimensions in right and left hand side of a constraint iv. Clerical errors + Areas in which we can apply Linear Programming Techniques. i, Product-Mix ii, Use of Resources iii. Blending Problems iv. Staffing Problem y. Production Scheduling vi. Transportation Problem vii. Assignment problem viii. Networks etc. *2.4.1 Limitations of Linear Programming 1. ‘The applications of LPP is possible iff we can express the given situation in the form of Linear objective and linear constraints, 2. The coefficients of the variables preserved in the objective and the constraints must be known well in advance.St 8 Operations Research Regarding th is a chance for us to have fractional values, 3. 1g the solution of an LPP, there is a cl be admissible in the decision making process, 4. Whenever if the Number of variables and constraints are more, we may require the help of com. puters to solve it. 2 S 5. Using this technique management make decision for only one objective at a time, ‘That is multiply goals can not be achieved through this. Which can nop 2.5 FORMULATION OF AN LPP Example: 1 Product-Mix Problem The Krishna Company wishes to schedule the production of two items namel Management of the company has to decide as to how many chairs and Tables to be prodused per day to paximize the profit. The following information is available to the Management, The profit per item is £35 and %55 respectively. In order to produce the two items that requires resources. wood ly chairs and tables, The |, manpower Requirement per Unit Manpower Wood (kg) | (persons) | Machine (hr) Chair 6 2 4 Table 12 3 6 Formulate an LP model to determine the daily production rate of various Models in order to maximize the profit. Formulation: Step 1: Identify the decision variables. Let the number of units of chairs and tables to be produced be x, and x, respectively. Step 2: Identify the constraints. In this problem the constraints are the limited availability of the three Tesources wood, manpower and machine hour. In addition to that we restrict the variables x,, x, to have only non-negative values, Step 3: Identify the objective. Here it is maximization of profit. ‘Then tabulate the given items: No. of Units to} ProfivUnit Requirement of Raw Materials/Unit Items be Produced in Wood (kg) | Men Machine (hr) Chair x 35 6 2 4 Table x Ee s : 4 Maximum availability 1500 15 120Linear Programming Probien (LPP) @ Construction of the objective tinetion: Profit fhom ohatre Profit trom tables; ‘Total Profit, (ic) Max Where Z is the name of the objective th Construction of constraint for wood: yk 55x, tion, Wood requirement for chairs : Wood requirement for tables + 6x, 12x, Total wood requirement Given maximum availability is 1500 kgs GX, +b 12x, 5 1500 mn order {0 achieve the maximization of the objective fimetion, wo can make use ofall 1500 kgs or less than 1500 kgs. Similarly, the other two cons ints are 2x, 4+3x,S75 (men) x, + 6x, $120 (machine) In addition, we restrict the variables Xp Xy X, (0 have only non-negative valu ‘Thus, the Linear Programming Problem for our product mix problem becom: Max Z = 35x, + 55x, St. 6x, + 12x, $ 1500 2x, +3x, $75 4x, + 6x, $120 XX, 20 *Example: 2 A firm manufactures three products A,B and C. The profits are %3, %2 and &4 respectively. The firm has two machines. The processing time in minutes for each machine on each product is given below. Products. A B c Machines D 4 3 5. E 2 2 4 Machines D and E have 2,000 and 2,500 machine-minutes respectively. The firm must manufacture at least 100A’s; 200B’s and 50C’s but not more than 150 C’s. Formulate a linear programming model to maximize the total profit. Let x,, x, & x, be the number of units to be produced in product A, B and C respectively, *These questions have appeared in Indian university examination papers.Tabulate the given information as follows, Products No. of Profit Machine/nts Units ® b b A 3 4 2 B 2 3 2 i ci Ss : 7 : 50 150) Max. availability 2,000 2,500 alt Max Z= 3x, 42x, 44x, Subject to the constraints 4x, +3x,4+5x, << 2000 2x, +2x,+4x, << 2500 i 2100; x,2200; x,>50; X58 150; xx 20 *Example: 3 Formulate the following problem as an LP model: oe: A co-operative farm owns 100 acres of land and has 725,000 in funds available f ce a total of 3,500 man-hours worth of ki S during June-August. Ifany of these nian. of the farm will use them to work on a neighbouring farm for &2 per hour during September-May and %3 per hour during June-August. Cash income can be obtained fret che three main crops and two types of livestock: dairy cows and laying hens, No investment funds are needed fete crops, Howover, eich cow will require an investment outlay of €3,200 and each hen will require 215, Moreover, each cow will require 1.5 acres of land, 100 man-hours of work during Seplember-May gnd another 30 man-hours during June-August. Each cow will produce a net ann e 3,500 for the farm. The cor ing September-May 0.4 man chicken house membersto'a for investinent. The labour during the months September. “hours are not needed, some members h income of responding figures for cach hen are: no acreages, (6 man-hours dt hours during June-August, and an annual neteash income of 3200. i accommodate a maximum of 4,000 hens and the size of the cattle-shed limits the imum 6f 32 cows,” Estimated man-hours and income per acre planted in each of the three crops are: Man-Hours: Paddy Bajra sone 25 September-May 40 20 40 June-August 50 35 Net Annual Cash 5 800 850 Income (®) 1,200