LINEAR PROGRAMMING APPLICATIONS
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
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
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
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 20x1, where x1 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 52/3 units of product A and 101/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 52/3 units of product A and 101/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.
LINEAR PROGRAMMING APPLICATIONS
The following are the various linear programming applications:
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 number 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 lowest cost.
The producers may like to know the increase 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 different 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 production 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 distribution 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 outlet, 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 different sources which they transport to several refineries 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 refineries and transportation of products to sales outlets. Thus L.P. is widely used in petroleum industry.
PERSONNEL ASSIGNMENT PROBLEMS
These problems are similar to distribution problems. An accounting firm would like to find out the best method of assigning audit staff personnel to various audit activities within the audit office constraints, and simultaneously meeting the professional and economic objectives of the offices. L.P. and assignment 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 incorporated in such models. John R. McNamara developed one such capacity planning model for electric utilities based on L.P. to minimize the costs of satisfying 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.
| Also Study | Also Study | Also Study |
| Operations Research | Linear Programming | Assignment |
| Linear programming problems | Linear programming applications | Models of Operations research |
