WHAT IS LINEAR PROGRAMMING

Linear programming is a powerful quantitative technique (or operational research technique) designs to solve allocation problem.

The term ‘linear programming’ consists of the two words ‘Linear’ and ‘Programming’. The word ‘Linear’ is used to describe the relationship between decision variables, which are directly proportional. For example, if doubling (or tripling) the production of a product will exactly double (or triple) the profit and required resources, then it is linear relationship. The word ‘programming’ means planning of activities in a manner that achieves some ‘optimal’ result with available resources. A programme is ‘optimal’ if it maximises or minimises some measure or criterion of effectiveness such as profit, contribution (i.e. sales-variable cost), sales, and cost.

Thus, ‘Linear Programming’ indicates the planning of decision variables, which are directly proportional, to achieve the ‘optimal’ result considering the limitations within which the problem is to be solved.

ACCORDING TO WILLIAM M. FOX

“Linear programming is a planning technique that permits some objective function to be minimized or maximized within the framework of given situational restrictions.”

HISTORICAL BACKGROUND

The technique of linear programming was formulated by a Russian mathematician L.V. Kantorovich. But the present version of simplex method was developed by Geoge B. Dentzig in 1947. Linear programming (LP) is an important technique of operations research developed for optimum utilization of resources.

TERMINOLOGY OF LINEAR PROGRAMMING

LINEAR FUNCTION

A linear function contains terms each of which is composed of only a single, continuous variable raised to (and only to) the power of 1.

OBJECTIVE FUNCTION

The objective function of a linear programming problem is a linear function of the decision variable expressing the objective of the decision maker. For example, maximisation of profit or contribution, minimisation of cost/time.

CONSTRAINTS

The constraints indicate limitations on the resources, which are to be allocated among various decision variables. These resources may be production capacity, manpower, time, space or machinery. These must be capable of being expressed as linear equation (i.e. =) on inequalities (i.e. > or<; type) in terms of decision variables. Thus, constraints of a linear programming problem are linear equalities or inequalities arising out of practical limitations.

NON-NEGATIVITY RESTRICTION

Non-negativity restriction indicates that all decision variables must take on values equal to or greater than zero.

DIVISIBILITY

Divisibility means that the numerical values of the decision variables are continuous and not limited to integers. In other words, fractional values of the decision variables must be permissible in obtaining optimal solution.

DECISION VARIABLES

The decision variables refer to the economic or physical quantities, which are competing with one another for sharing the given limited resources. The relationship among these variables must be linear under linear programming. The numerical values of decision variables indicate the solution of the linear programming problem.

FEASIBLE SOLUTION

Any non-negative solution which satisfies all the constraints is known as a feasible solution. The region comprising all feasible solutions is referred to as feasible region.

OPTIMAL SOLUTION

A feasible solution, which optimizes the objective function, is known as Optimal Solution. An optimal solution is always feasible but all feasible solutions cannot be optimal.

TYPES OF VARIABLES IN LINEAR PROGRAMMING

SLACK VARIABLE

Slack variables are defined to transform an inequality expression into an equality expression with an added slack variable. The slack variable is defined by setting a lower bound of zero (>0).

SURPLUS VARIABLE

A surplus variable refers to the amount by which the values of the solution exceeds the resources utilized. These variables are also known as negative slack variables. In the objective function, it carries a zero coefficient. In order to obtain the equality constraint, the surplus variable is added to the greater than or equal to the type constraints.

ARTIFICIAL VARIABLE

When the problems related to the mixed constraints are given and the simplex method has to be applied, then the artificial variable is introduced. The artificial variable refers to the kind of variable which is introduced in the linear program model to obtain the initial basic feasible solution. It is utilized for the equality constraints and for the greater than or equal inequality constraints. There is no meaning of the artificial variables in the physical sense.

ASSUMPTIONS OF LINEAR PROGRAMMING

PROPORTIONALITY

The basic assumption underlying the linear programming is that any change in the constraint inequalities will have the proportional change in the objective function. This means, if product contributes Rs 20 towards the profit, then the total contribution would be equal to 20x₁, where x₁ is the number of units of the product.

For example, if there are 5 units of the product, then the contribution would be Rs 100 and in the case of 10 units, it would be Rs 200. Thus, if the output (sales) is doubled, the profit would also be doubled.

ADDITIVITY

The assumption of additivity asserts that the total profit of the objective function is determined by the sum of profit contributed by each product separately. Similarly, the total amount of resources used is determined by the sum of resources used by each product separately. This implies, there is no interaction between the decision variables.

CONTINUITY

Another assumption of linear programming is that the decision variables are continuous. This means a combination of outputs can be used with the fractional values along with the integer values.

For example, If 5²/3 units of product A and 10¹/3 units of product B to be produced in a week. In this case, the fractional amount of production will be taken as a work-in-progress and the remaining production part is taken in the following week. Therefore, a production of 17 units of product A and 31 units of product B over a three-week period implies 5²/3 units of product A and 10¹/3 units of product B per week.

CERTAINTY

Another underlying assumption of linear programming is a certainty, i.e. the parameters of objective function coefficients and the coefficients of constraint inequalities are known with certainty. Such as profit per unit of product, availability of material and labor per unit, requirement of material and labor per unit are known and is given in the linear programming problem.

FINITE CHOICES

This assumption implies that the decision maker has certain choices, and the decision variables assume non-negative values. The non-negative assumption is true in the sense, the output in the production problem cannot be negative. Thus, this assumption is considered feasible.

Thus, while solving for the linear programming problem, these assumptions should be kept in mind such that the best alternative is chosen.

APPLICATIONS OF LINEAR PROGRAMMING

The following are the various applications of linear programming:

PRODUCTION MANAGEMENT

• Product mix: A company can produce several different products, each of which requires the use of limited production resources. In such cases, it is essential to determine the quantity of each product to be produced knowing its marginal contribution and amount of available resource used by it. The objective is to maximize the total contribution, subject to all constraints.
• Production planning: This deals with the determination of minimum cost production plan over planning period of an item with a fluctuating demand, considering the initial number of units in inventory, production capacity, constraints on production, manpower and all relevant cost factors. The objective is to minimize total operation costs.
• Assembly-line balancing: This problem is likely to arise when an item can be made by assembling different components. The process of assembling requires some specified sequence(s). The objective is to minimize the total elapse time.
• Blending problems: These problems arise when a product can be made from a variety of available raw materials, each of which has a particular composition and price. The objective here is to determine the minimum cost blend, subject to availability of the raw materials, and minimum and maximum constraints on certain product constituents.
• Trim loss When an item is made to a standard size (e.g. glass, paper sheet), the problem that arises is to determine which combination of requirements should be produced from standard materials in order to minimize the trim loss.

FINANCIAL MANAGEMENT

• Portfolio selection: This deals with the selection of specific investment activity among several other activities. The objective is to find the allocation which maximises the total expected return or minimises risk under certain limitations.
• Profit planning: This deal with the maximisation of the profit margin from investment in plant facilities and equipment, cash in hand and inventory.

MARKETING MANAGEMENT

• Media selection: Linear programming technique helps in determining the advertising media mix so as to maximise the effective exposure, subject to limitation of budget, specified exposure rates to different market segments, specified minimum and maximum number of advertisements in various media. Example: Travelling salesman problem. The problem of salesman is to find the shortest route from a given city, visiting each of the specified cities and then returning to the original point of departure, provided no city shall be visited twice during the tour. Such type of problems can be solved with the help of the modified assignment technique.
• Physical distribution: Linear programming determines the most economic and efficient manner of locating manufacturing plants and distribution centers for physical distribution.

PERSONNEL MANAGEMENT

• Staffing problem: Linear programming is used to allocate optimum manpower to a particular job so as to minimize the total overtime cost or total manpower.
• Determination of equitable salaries: Linear programming technique has been used in determining equitable salaries and sales incentives.
• Job evaluation and selection: Selection of suitable person for a specified job and evaluation of job in organizations has been done with the help of linear programming technique.

DIET PROBLEMS

Animal feeds are produced by mixing a num­ber of ingredients each of which contains different proportions of protein, vitamins, minerals, etc. The animal feeds produced must meet certain nutritional levels as specified by the Government, at the low­est cost.

The producers may like to know the in­crease in cost when the nutritional level of the feed is increased. This problem is also associated with pharmaceutical, fertilizer, lawn seed and pet food industries. L.P. is an answer to such problems.

ADVERTISING BUDGET ALLOCATION

A firm has limited funds for advertising budget allocation, e.g., T.V., radio, newspaper, magazines, bill broads, neon-advertisements, etc. and it would like to know how much money should be allocated to which medium for getting the maximum benefit. T.V. advertising may again be split as day or evening shows, depending on the type of audiences. The fund allocation problem can be solved by L.P.

PROCESS SELECTION

This problem is similar to diet problems. It deals with product that can be produced by using any one (or, more) of several processes, each involving dif­ferent proportions of various inputs. A firm would like to produce the product by combining two or more processes and inputs in such a way that pro­duction costs are minimized. L.P. can suggest an answer to such problems.

DISTRIBUTION PROBLEMS

Many firms have two or more plants where a certain product is produced and several warehouses at different locations for storing the products before sending them to various retail outlets.

The distri­bution costs also differ for various routes used from production plant to warehouse and to sales outlet. Management must decide the shipping assignments, i.e., how many units should go from each sales out­let, with a minimizing view to shipping cost. Such problems can be solved by transportation and L.P. techniques.

OIL PROCESSING AND TRANSPORTATION PROBLEMS

Large petroleum firms receive crude oil from dif­ferent sources which they transport to several re­fineries where various products are produced jointly in the cracking process. L.P. is used to find out the optimum product-mix, the best method of allocation of crude oil from different sources to the various re­fineries and transportation of products to sales out­lets. Thus L.P. is widely used in petroleum industry.

PERSONNEL ASSIGNMENT PROBLEMS

These problems are similar to distribution prob­lems. An accounting firm would like to find out the best method of assigning audit staff personnel to various audit activities within the audit office con­straints, and simultaneously meeting the profession­al and economic objectives of the offices. L.P. and as­signment techniques can be used for solution of such problems.

LONG-RANGE CAPACITY PLANNING FOR ELECTRIC UTILITIES

Good long-range planning models are necessary for energy related complicated problems. Demand projections for future years and information relating to operation and investment costs should be incor­porated in such models. John R. McNamara devel­oped one such capacity planning model for electric utilities based on L.P. to minimize the costs of sat­isfying projected demands.

The model is simple, user-oriented, and can be used to solve problems quickly. Besides these L.P. can be applied to various other fields of decision making.

APPLICATIONS IN ENGINEERING

Engineers also use linear programming to help solve design and manufacturing problems. For example, in airfoil meshes, engineers seek aerodynamic shape optimization. This allows for the reduction of the drag coefficient of the airfoil. Constraints may include lift coefficient, relative maximum thickness, nose radius and trailing edge angle. Shape optimization seeks to make a shock-free airfoil with a feasible shape. Linear programming therefore provides engineers with an essential tool in shape optimization.

MILITARY APPLICATIONS

Military applications include the problem of selecting an air weapon system against enemy so as to keep them pinned down and at the same time minimizing the amount of aviation gasoline used. A variation of the transportation problem that maximizes the total tonnage of bombs dropped on a set of targets and the problem of community defense against disaster, the solution of which yields the number of defense units that should be used in a given attack in order to provide the required level of protection at the lowest possible cost.

WHAT IS LINEAR PROGRAMMING– ADVANTAGES

OPTIMUM USE OF RESOURCES: Linear programming helps in attaining the optimum use of productive resources. It also indicates how a decision-maker can employ his productive factors effectively by selecting and distributing (allocating) these resources.

IMPROVE QUALITY OF DECISIONS: Linear programming techniques improve the quality of decisions. The decision-making approach of the user of this technique becomes more objective and less subjective.

PRACTICAL SOLUTIONS: Linear programming techniques provide possible and practical solutions since there might be other constraints operating outside the problem which must be taken into account. Just because we can produce so many units does not mean that they can be sold. Thus, necessary modification of its mathematical solution is required for the sake of convenience to the decision-maker.

RE-EVALUATION OF PLANS: Linear programming also helps in re-evaluation of a basic plan for changing conditions. If conditions change when the plan is partly carried out, they can be determined so as to adjust the remainder of the plan for best results.

SCIENTIFIC APPROACH: Operations Research provides a scientific approach to solve the problems. All the aspects directly or indirectly related to the problem are studied and optimal solution is arrived at.

LIMITATIONS OF LINEAR PROGRAMMING

Following are the disadvantages or limitations of linear programming:

• SINGLE OBJECTIVE: Linear programming takes into account a single objective only, i.e., profit maximization or cost minimization. However, in today’s dynamic business environment, there is no single universal objective for all organizations.
• CERTAINTY: Linear Programming assumes that the values of co-efficient of decision variables are known with certainty. Due to this restrictive assumption, linear programming cannot be applied to a wide variety of problems where values of the coefficients are probabilistic.
• “Nothing is certain but death and taxes.” -Benjamin Franklin
• DIVISIBILITY: In linear programming, the decision variables are allowed to take non-negative integer as well as fractional values. However, we quite often face situations where the planning models contain integer valued variables. For instance, trucks in a fleet, generators in a powerhouse, pieces of equipment, investment alternatives and there are a myriad of other examples. Rounding off the solution to the nearest integer will not yield an optimal solution. In such cases, linear programming techniques cannot be used.
• COMPLEX: It is complex to determine the particular objective function
• LINEAR RELATIONSHIP: This technique is based on the hypothesis of linear relations between inputs and outputs. This means that inputs and outputs can be added, multiplied and divided. But the relations between inputs and outputs are not always clear. In real life, most of the relations are non-linear.
• WRONG ASSUMPTIONS: This technique presumes perfect competition in product and factor markets. But perfect competition is not a reality.
• CONSTANT REURNS: The LP technique is based on the hypothesis of constant returns. In reality, there are either diminishing or increasing returns which a firm experiences in production.
• COMPLICATED TECHNIQUE: It is a highly mathematical and complicated technique. The solution of a problem with linear programming requires the maximization or minimization of a clearly specified variable. The solution of a linear programming problem is also arrived at with such complicated method as the simplex method which comprises of a huge number of mathematical calculations.
• Even if a particular objective function is laid down, it may not be so easy to find out various technological, financial and other constraints which may be operative in pursuing the given objective.
• Given a Specified objective and a set of constraints it is feasible that the constraints may not be directly expressible as linear inequalities.
• Mostly, linear programming models present trial and error solutions and it is difficult to find out really optimal solutions to the various economic complexities.

CONCLUSION

Linear programming has turned out to be a highly useful tool of analysis for the business executives. It is being increasingly made use of in theory of the firm, in managerial economics, in inter regional trade, in general equilibrium analysis, in welfare economics and in development planning.

Also Study	Also Study	Also Study
Operations Research	Linear Programming	Assignment
Linear programming problems	Linear programming applications	Models of Operations research