I linear programming

I LINEAR PROGRAMMING

In a decision-making embroilment, model formulation is important because it represents the essence of business decision problem. The term formulation is used to mean the process of converting the verbal description and numerical data into mathematical expressions which represents the relevant relationship among decision factors, objectives and restrictions on the use of resources. Linear Programming (LP) is a particular type of technique used for economic allocation of ‘scarce’ or ‘limited’ resources, such as labour, material, machine, time, warehouse space, capital, energy, etc. to several competing activities, such as products, services, jobs, new equipment, projects, etc. on the basis of a given criterion of optimally. The phrase scarce resources mean resources that are not in unlimited in availability during the planning period. The criterion of optimality generally is either performance, return on investment, profit, cost, utility, time, distance, etc.

George B Dantzing while working with US Air Force during World War II, developed this technique, primarily for solving military logistics problems. But now, it is being used extensively in all functional areas of management, hospitals, airlines, agriculture, military operations, oil refining, education, energy planning, pollution control, transportation planning and scheduling, research and development, etc. Even though these applications are diverse, all I.P models consist of certain common properties and assumptions. Before applying linear programming to a real-life decision problem, the decision-maker must be aware of all these properties and assumptions.

The word linear refers to linear relationship among variables in a model. Thus, a given change in one variable will always cause a resulting proportional change in another variable. For example, doubling the investment on a certain project will exactly double the rate of the return. The word programming refers to modelling and solving a problem mathematically that involves the economic allocation of limited resources by choosing a particular course of action or strategy among various alternative strategies to achieve the desired objective.

STRUCTURE OF LINEAR PROGRAMMING

General Structure of LP Model

The general structure of LP model consists of three components.

1. Decision variables (activities): We need to evaluate various alternatives (courses of action) for arriving at the optimal value of objective function. Obviously, if there are no alternatives to select from, we would not need LP. The evaluation of various alternatives is guided by the nature of objective function and availability of resources. For this, we pursue certain activities usually denoted by x1, x2…xn. The value of these activities represents the extent to which each of these is performed. For example, in a product-mix manufacturing, the management may use LP to decide how many units of each of the product to manufacture by using its limited resources such as personnel, machinery, money, material, etc.

These activities are also known as decision variables because they arc under the decision maker’s control. These decision variables, usually interrelated in terms of consumption of limited resources, require simultaneous solutions. All decision variables are continuous, controllable and non-negative. That is, x1>0, x2>0, ….xn>0.

2. The objective function: The objective function of each L.P problem is a mathematical representation of the objective in terms of a measurable quantity such as profit, cost, revenue, distance, etc. In its general form, it is represented as:

Optimise (Maximise or Minimise) Z = c1x1 + c2X2. … cnxn

Where Z is the measure-of-performance variable, which is a function of x1, x2 …, xn. Quantities c1, c2…cn are parameters that represent the contribution of a unit of the respective variable x1, x2…, xn to the measure-of-performance Z. The optimal value of the given objective function is obtained by the graphical method or simplex method.

3. The constraints: There are always certain limitations (or constraints) on the use of resources, e.g. labour, machine, raw material, space, money, etc. that limit the degree to which objective can be achieved. Such constraints must be expressed as linear equalities or inequalities in terms of decision variables. The solution of an L.P model must satisfy these constraints. The linear programming method is a technique for choosing the best alternative from a set of feasible alternatives, in situations in which the objective function as well as the constraints can be expressed as linear mathematical functions.

APPLICATION AREAS OF LINEAR PROGRAMMING

Linear programming is the most widely used technique of decision-making in business and Industry and in various other fields. In this section, we will discuss a few of the broad application areas of linear programming.

Agricultural Applications

These applications fall into categories of farm economics and farm management. The former deals with agricultural economy of a nation or region, while the latter is concerned with the problems of the individual farm.

The study of farm economics deals with inter-regional competition and optimum allocation of crop production. Efficient production patterns can be specified by a linear programming model under regional land resources and national demand constraints.

Linear programming can be applied in agricultural planning, e.g. allocation of limited resources such as acreage, labour, water supply and working capital, etc. in a way so as to maximise net revenue.

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 minimising the amount of aviation gasoline used. A variation of the transportation problem that maximises the total tonnage of bombs dropped on a set of targets and the problem of community defence against disaster, the solution of which yields the number of defence units that should be used in a given attack in order to provide the required level of protection at the lowest possible cost.

Production Management

1. 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 maximise the total contribution, subject to all constraints.
2. 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 minimise total operation costs.
3. 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 minimise the total elapse time.
4. 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.
5. 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 minimise the trim loss.

Financial Management

1. 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.
2. 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

1. 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. (if) 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.
2. Physical distribution: Linear programming determines the most economic and efficient manner of locating manufacturing plants and distribution centres for physical distribution.

Personnel Management

• Staffing problem: Linear programming is used to allocate optimum manpower to a particular job so as to minimise 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 organisations has been done with the help of linear programming technique.

Other applications of linear programming lie in the area of administration, education, fleet utilisation, awarding contracts, hospital administration and capital budgeting.

ADVANTAGES OF LINEAR PROGRAMMING

Following are certain advantages of linear programming:

1. 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.
2. Linear programming techniques improve the quality of decisions. The decision-making approach of the user of this technique becomes more objective and less subjective.
3. 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 docs 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.
4. Highlighting of bottlenecks in the production processes is the most significant advantage of this technique. For example, when a bottleneck occurs, some machines cannot meet demand while other remains idle for some of the time.
5. 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.

LIMITATIONS OF LINEAR PROGRAMMING

• There should be an objective which should be clearly identifiable and measurable in quantitative terms. It could be, for example, maximisation of sales, of profit, minimisation of cost, and so on, which is not possible in real life.
• The activities to be included should be distinctly identifiable and measurable in quantitative terms, for instance, the products included in a production planning problem and all the activities can’t be measured in quantitative terms for example if labour is sick, which will decrease his performance which can’t be measured.
• The resources of the system which arc to be allocated for the attainment of the goal should also be identifiable and measurable quantitatively. They must be in limited supply. The technique would involve allocation of these resources in a manner that would trade off the returns on the investment of the resources for the attainment of the objective.
• The relationships representing the objective as also the resource limitation considerations, represented by the objective function and the constraint equations or inequalities, respectively must be linear in nature, which is not possible.
• There should be a series of feasible alternative courses of action available to the decision makers, which are determined by the resource constraints.

When these stated conditions are satisfied in a given situation, the problem can be expressed in algebraic form, called the Linear Programming Problem (LPP) and then solved for optimal decision.

• While solving an LP model, there is no guarantee that we will get integer valued solutions.

For example, in finding out how many men and machines would be required lo perform a particular job, a non-integer valued solution will be meaningless. Rounding off the solution to the nearest integer will not yield an optimal solution. In such cases, integer programming is used to ensure integer value to the decision variables.

• Linear programming model does not take into consideration the effect of time and uncertainty. Thus, the LP model should be defined in such a way that any change due to internal as well as external factors can be incorporated.
• Sometimes large-scale problems can be solved with linear programming techniques even when assistance of computer is available. For it, the main problem can be fragmented into several small problems and solving each one separately.
• Parameters appearing in the model are assumed to be constant but in real-life situations, they are frequently neither known nor constant.
• Parameters like human behaviour, weather conditions, stress of employees, demotivated employee can’t be taken into account which can adversely effect any organisation
• Only one single objective is dealt with while in real life situations, problems come with multi-objectives.

II SITUATION ANALYSIS

Phang furniture system Inc. (Fursys) manufactures two models of stools, Potty which is basic model and a better model called Hardy.

SUPPLIES

Maximum of 350 pounds plastic per day at the rate of $1.5 per pound by Keow supplies Up to 30 boxes of legs per day at the rate of $7.5 per box. Each box has 10 sets of legs by Yuen supplies Using linear programming the optimal production should be determined for maximum profit.

Decision Variables

The production units are in terms of number on daily basis. Therefore the decision variables are:

Let, X1 = No. of Potty’s production daily

X2 = No. of Hardy’s production daily

Objective Function

The objective in the problem is to attain maximum profit. We have selling price for Potty and Hardy as $12.75 and $18. We need to calculate the unit profit gained by selling Potty and Hardy.

Cost of production for 1 Potty = one pound plastic + one set of leg

= ($1.5*1) + $0.75(1)

= $2.25

Profit made by selling = $12.75 – $2.25 = $10.5

Cost of production for 1 Hardy = 1.5 pound of plastic + one set of leg

= ($1.5*1.5) + ($0.75*1)

= $3

Unit profit made by selling Hardy = $18 – $3 = $15

Constraints

Plastic

Potty requires one pound of plastic and Hardy requires 1.5 pound plastic. So the total plastic used daily is:

(1)X1 + (1.5)X2

This plastic supply can’t exceed the limit of 350 pounds daily, so constraint is

(1)X1 + (1.5)X2 <= 350

Legs

Both the model require one set of each legs each for its production. So the sets of legs used daily is

(1)X1 + (1)X2

The no of set of legs can’t exceed the limit of 300, so the constraint is

(1)X1 + (1)X2 <= 300

Production time

Potty can be manufactured in 15 minutes and Hardy can be manufactured in 24minutes. So the total time taken for manufacturing both stools in order to achieve maximum profit is:

(15)X1 + (24)X2

The production time can’t exceed 80 hours(4800 minutes) on daily basis. Therefore the constraint is,

(15)X1 + (24)X2 <=4800

Non-negativity

Negative production of Potty and Hardy stool is not possible. Therefore,

X1,X2 >=0

Mathematical model

Maximize, 10.5X1 + 15X2 (total daily profit)

Subject to constraints, X1 + 1.5X2 <= 350(plastic in pound)

X1 + X2 <= 300(sets of legs)

15X1 + 24X2 <= 4800(production time in minutes)

X1,X2 >=0(non-negativity)

Solution from winqsb

Assignment WINQSB output.bmp

According to WINQSB, when Potty produced(X1) = 266.67 and Hardy produced(X2) = 33.33, Fursys can get a maximum profit of 3,300. Therefore the optimum solution is

X1 = 266.67

X2 = 33.33

Net income

Fursys makes a maximum profit of $3300 per day. Its fixed cost, namely for overheads and family labour is about $2800 per day. Therefore,

Net income of Fursys is = Profit- Fixed cost

= $3300-$2800 = $500

Sensitivity Analysis

Range of optimality

After achieving optimal solution, Fursys will be concerned about how the solution may be affected if any one of the objective function co-efficient is changed. Depending on the value of the objective function co-efficient the optimal solution may vary.

Assignment WINQSB output.bmp

From above table we can conclude that:

9.375 <= C1 (UNIT COST OF ONE POTTY) >= 15

10.500 <=C2 (UNIT COST OF ONE HARDY) >=16.800

Reduced costs:

The amount, the optimal profit will change per unit increase in the variable from its lower bound, while assuming there are no changes in the input parameters is called reduced costs. Reduces costs are usually zero.

Shadow price:

Shadow price is the premium value above the existing unit value for the resource if the need arises to purchase more resources, which means slack or surplus is zero.

When there is a slack or surplus of resources there is no need to purchase more. Hence the shadow price is zero. In the above problem after one day of production, there is a surplus of 33.333 pounds of plastic, therefore there is no shadow price. But all sets of legs were used to manufacture stools and therefore the slack or surplus for sets of legs is zero. So it has a shadow price of $3. Now if Fursys wants to buy more sets of legs it has a perceives value to pay is

original price + shadow price = $0.75 + $3 = $3.75 per set of legs

Range of feasibility:

The range of feasibility is the range of values for which the shadow prices of resources remain unchanged, however optimal solution will change. When the amount or number of resources goes beyond the range, a new shadow price arises.

In this problem, when the number of legs go beyond 320, the value of the shadow price changes. Therefore, for the same shadow price, only 20 more sets of legs can be purchased. Likewise when we see for the plastics to be bought, the upper limit is infinity and since there’s already surplus of plastic, there’s no need to buy anymore.

Analysis of available solutions

Option1: Seeking additional source of plastic

As shown in figure from winqsb output that at the end of a day’s production there is a surplus of plastic 33.333 pounds. Since there is surplus of plastic, there is no need to look for additional sources of plastic.

However if the demand of the products increase and surplus is finished then Fursys can purchase additional plastic. From the range of feasibility we can see that the upper limit of the amount of plastic is infinity, therefore any amount of plastic can be purchased.

Option2: Taking up Yuen Supplies offer to deliver an extra cost of 10 sets of legs

From the WINQSB solution we can see that the maximum sets of legs the maximum no of set of legs can be purchased per day is 320. The current number of legs used per day is 300, so we can conclude that Fursys can buy 10 extra set of legs from Yuen supplies as it is under feasibility.

Option3: Adding a part time worker (4 hours a day) for $50 per day

Fursys considers its labour cost as sunk for business. By adding up an extra worker, the cost of worker will be considered as sunk cost only.

Adding up a worker will increase production time by 240 minutes per day, this lies within the limit of range of feasibility. Hence option of extra worker can be taken into account.

Application of 100% rule to evaluate option 2 and 3 can be implemented at the same time

100% rule is used to evaluate whether different options available for a company are feasible or not. It involves calculations of increase or decrease in an objective function coefficient to the maximum possible increase or decrease as determined by the limits of the range of optimality. Here we will consider option 2 and 3 for Fursys and will see if both options are feasible at the same time.

Option 2 considered first

When Fursys buy 10 extra set of legs then:

Total cost of legs = 300*0.75(for 300 legs) + 25(for extra 10 legs)

= $250

Cost of 310 legs = $250

Cost of 1 leg = 250/310 = $.80

When Fursys buys 300 legs then cost of each set of leg =$ 0.75

So there is an increase in price of legs by $.05 by buying 10 extra set of legs, since profit is inversely proportional to increase in cost price so profit decrease by $0.05 for both Potty and Hardy

Applying 100% rule

New cost price for Potty’s is = $10.45

Now we will calculate % change in profit

Formula is: percentage change = (change/maximum change) * 100

= (0.05/1.125) * 100

= 4.44%

New cost price for Hardy’s is = $14.95

Similarly like potty we will calculate % change in profit for hardy

Formula is: percentage change = (change/maximum change) * 100

= 1.11%

Option 3

(diagram)

The additional worker works for 4 hours i.e. 240 minutes and will receive $50 as wages

Since Fursys considers labour cost as sunk cost so there will be no effect on cost of product

Now calculating % change for time constraint. Maximum permissible production time is 600 minutes. We will calculate % change in time

Formula is: percentage change = (change/maximum change) * 100

= (240/600)*100

= 40%

According to 100% rule, adding all percentage change we get 45.5% which is less then 100%, so option 2 and option 3 can be used together.

Recommendations