LINEAR PROGRAMMING PROBLEMS – GNDU PREVIOUS YEAR QUESTIONS
Define linear programming? Discuss its applications in various functions quoting examples from real life?
Answer:
Linear programming deals with the optimization (maximization or minimization) of a linear function, called objective function, involving number of variables, subject to the set of variables, subject to the set of linear equalities and for inequalities called constraints and variables should be non-negative.
ACCORDING TO SAMUELSON AND SLOW
“ The analysis of problems in which a linear function of variables is to be maximised or minimised when these variables are subjected to number of constraints in the form of linear inequalities.”
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.”
In linear programming, ‘Linear’ means that all the relation used in the problems are linear whereas ‘programming’ stands for the process of finding a plan of action.
HISTORY: The technique of linear programming was formulated by a Russian mathematician L.V. Kantorovich. But the present version of simplex method was developed by George B. Dentzig in 1947. Linear programming (LP) is an important technique of operations research developed for optimum utilization of resources.
BASIC REQUIREMENTS 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.
Z= c1x1+ c2x2+ ……..cnxn
Where x1, x2……..xn are decision variables of objective function.
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.
OBJECTIVE TO BE MATHEMATICALLY EXPRESSED
One should be able to express the firm’s objectives and constraints as mathematical linear equations or equations.
ASSUMPTIONS OF LPP MODEL
PROPORTIONALITY OR LINEARITY
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.
DIVISIBILITY
Decision variables are allowed to assume continuous non-negative values i.e. decision variables may assume integral or fractional values.
If decision variables are restricted to assume only integral values, the problems is solved by integer linear programming techniques.
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 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.
ENERGY PRODUCTION OPTIMIZATION
Linear programming can be used to optimize energy production by determining the optimal mix of energy sources to meet demand while minimizing costs and environmental impact. For example, a utility company can use linear programming to determine the optimal mix of coal, natural gas, and renewable energy sources to generate electricity and meet energy demand.
AGRICULTURE
Linear programming is used in agriculture to optimize crop selection, planting schedules, and fertilization strategies. For example, a farmer can use linear programming to optimize crop selection to maximize yield and profitability.
LINEAR PROGRAMMING PROBLEMS REAL LIFE EXAMPLES
- In 2013, Dutch delta Program Commissioner used mixed integer non-linear programming to derive an optimal investment strategy for strengthening dikes for protection against high water and keeping fresh water supplies up to standard resulting in savings of 8 billion euros in investment costs.
- In 2010, Mexico’s Central Security depository INDEVAL, used linear programming to develop a secure and automatic clearing and settlement engine to determine the set of transactions that can be settled to maximise the number of traded securities, thereby efficiently processing transactions averaging 250 billion dollars daily and optimally using available cash and security balances.
- In 2005, Motorola used mixed integer programming to develop internet enables supplier negotiation software with flexible bidding formats, multi-stage negotiation capabilities multiple online negotiation formats and optimized selection of vendors to support its global procurement function, automated negotiations formats and optimized selection of vendors to support its global procurement function, automated negotiations and management of a heterogenous supply base of more than thousand vendors with different product portfolios and delivery capabilities, thereby resulting in savings of more than 600 million dollars.