Introduction and Mathematical Formulation

Introduction to Linear Programming

In many real-life situations, we have to make the best possible decision while working under limited resources such as money, time, raw materials, labor, storage, or machine hours. Linear Programming (LP) is a mathematical method used to determine the optimal value of a linear objective subject to a set of linear restrictions.

Common goals in such problems are:

• Maximizing profit, production, output, or reach.
• Minimizing cost, time, wastage, or risk.

The word Linear means that both the objective function and all the constraints must be linear expressions in the variables, that is, the variables appear only to the first power and are not multiplied together.

The word Programming here does not refer to computer coding. It refers to planning or deciding the best schedule, strategy, or course of action.

Thus, a Linear Programming Problem (LPP) is essentially a problem of choosing values of variables so that a linear objective is optimized while all the given conditions are satisfied.

Basic Terminology of LPP

Before formulating any Linear Programming Problem, it is important to understand its main components:

• Decision Variables: These are the unknown quantities whose values are to be determined. They represent the actual decisions to be made. For example, the number of chairs and tables to produce, or the amount of two foods to mix. They are usually denoted by $x, y$ or $x_1, x_2, \dots$.

• Objective Function: This is the linear function that is to be optimized. It may have to be maximized or minimized depending on the problem. It is usually denoted by $Z$. Example: $$Z = 250x + 75y$$ Here $Z$ may represent total profit, cost, or some other measurable quantity.

• Constraints: These are the restrictions placed on the decision variables. They arise from limited resources or required conditions. Constraints are written as linear equations or inequalities such as: $$2x + 3y \le 100, \quad x + y \ge 20, \quad x + y = 50.$$

• Non-negativity Restrictions: In almost all practical situations, the decision variables cannot be negative. For example, we cannot produce a negative number of units. Therefore, we write: $$x \ge 0, \quad y \ge 0.$$

Together, these components completely describe an LPP.

General Mathematical Form of LPP

A Linear Programming Problem involving two variables $x$ and $y$ can be written in the general form:

Optimize (Maximize or Minimize): $$Z = ax + by$$

Subject to constraints: $$c_1x + d_1y \le e_1 \quad (\text{or } \ge, =)$$ $$c_2x + d_2y \le e_2 \quad (\text{or } \ge, =)$$ $$\vdots$$ $$c_nx + d_ny \le e_n \quad (\text{or } \ge, =)$$

And non-negativity restrictions: $$x \ge 0, \quad y \ge 0$$

Here, $a, b, c_i, d_i,$ and $e_i$ are real constants.

A valid LPP must satisfy these conditions:

• The objective function must be linear.
• All constraints must be linear.
• The variables must satisfy non-negativity restrictions unless the problem explicitly states otherwise.

This mathematical model is the starting point for graphical or algebraic solution methods.

Steps for Mathematical Formulation of LPP

The most important skill in Linear Programming is converting a word problem into a mathematical model. A systematic approach is:

1. Identify the Decision Variables: Decide what quantities need to be found and assign variables to them. Example: Let $x$ be the number of chairs and $y$ be the number of tables.

2. Identify the Objective: Determine what is to be maximized or minimized. Example: profit, cost, production, reach, or time.

3. Form the Objective Function: Express the required quantity as a linear function of the variables. Example: If profit on one unit of product A is Rs 40 and on one unit of product B is Rs 30, then $$Z = 40x + 30y.$$

4. Identify the Constraints: Translate all given limitations into linear inequalities or equations. Important keywords:

• at most $\Rightarrow \le$
• at least $\Rightarrow \ge$
• exactly $\Rightarrow =$
• cannot exceed $\Rightarrow \le$
• not less than $\Rightarrow \ge$

1. Add Non-negativity Restrictions: Since quantities like number of units, kilograms, hours, etc. cannot be negative, include $$x \ge 0, \quad y \ge 0.$$

2. Write the Final Mathematical Model Clearly: Present the objective function first, followed by all constraints and then the non-negativity conditions.

This step-by-step structure prevents mistakes and makes the formulation neat and exam-ready.

Example 1: Manufacturing Problem

A furniture dealer deals in only two items: tables and chairs. He has Rs 50,000 to invest and space to store at most 60 pieces. A table costs Rs 2500 and a chair Rs 500. He estimates that from the sale of one table, he can make a profit of Rs 250, and from the sale of one chair, a profit of Rs 75. Formulate this problem as an LPP to maximize his profit.

Solution: Step 1: Choose the decision variables. Let the number of tables be $x$ and the number of chairs be $y$.

Step 2: Form the objective function. Profit from one table = Rs 250. Profit from one chair = Rs 75. Therefore, total profit is $$Z = 250x + 75y.$$ The objective is to maximize $Z$.

Step 3: Write the investment constraint. Cost of one table = Rs 2500, so cost of $x$ tables = $2500x$. Cost of one chair = Rs 500, so cost of $y$ chairs = $500y$. Total investment cannot exceed Rs 50,000: $$2500x + 500y \le 50000.$$ Dividing throughout by 500, we get the simplified form: $$5x + y \le 100.$$

Step 4: Write the storage constraint. The total number of pieces stored can be at most 60: $$x + y \le 60.$$

Step 5: Add non-negativity conditions. $$x \ge 0, \quad y \ge 0.$$

Step 6: Final LPP. Maximize $$Z = 250x + 75y$$ subject to $$5x + y \le 100$$ $$x + y \le 60$$ $$x \ge 0, \quad y \ge 0.$$

Example 2: Diet Problem

A dietician wishes to mix two types of foods in such a way that the vitamin contents of the mixture contain at least 8 units of vitamin A and 10 units of vitamin C. Food I contains 2 units/kg of vitamin A and 1 unit/kg of vitamin C. Food II contains 1 unit/kg of vitamin A and 2 units/kg of vitamin C. It costs Rs 50 per kg to purchase Food I and Rs 70 per kg to purchase Food II. Formulate this problem as a linear programming model to minimize the cost of such a mixture.

Solution: Step 1: Define the variables. Let $x$ kg of Food I and $y$ kg of Food II be used.

Step 2: Form the objective function. Cost of Food I = Rs 50 per kg, so cost of $x$ kg = $50x$. Cost of Food II = Rs 70 per kg, so cost of $y$ kg = $70y$. Therefore, total cost is $$Z = 50x + 70y.$$ The objective is to minimize $Z$.

Step 3: Write the vitamin A constraint. Food I contributes $2x$ units of vitamin A. Food II contributes $y$ units of vitamin A. Total vitamin A must be at least 8 units: $$2x + y \ge 8.$$

Step 4: Write the vitamin C constraint. Food I contributes $x$ units of vitamin C. Food II contributes $2y$ units of vitamin C. Total vitamin C must be at least 10 units: $$x + 2y \ge 10.$$

Step 5: Add non-negativity conditions. $$x \ge 0, \quad y \ge 0.$$

Step 6: Final LPP. Minimize $$Z = 50x + 70y$$ subject to $$2x + y \ge 8$$ $$x + 2y \ge 10$$ $$x \ge 0, \quad y \ge 0.$$

Example 3: Production Scheduling

A factory manufactures two types of screws, A and B. Each type of screw requires the use of two machines, an automatic and a hand operated. It takes 4 minutes on the automatic and 6 minutes on the hand-operated machine to manufacture a package of screws A, while it takes 6 minutes on the automatic and 3 minutes on the hand-operated machine to manufacture a package of screws B. Each machine is available for at most 4 hours on any day. The manufacturer can sell a package of screws A at a profit of Rs 7 and screws B at a profit of Rs 10. Formulate the LPP to maximize profit.

Solution: Step 1: Define the decision variables. Let $x$ be the number of packages of screw A and $y$ be the number of packages of screw B.

Step 2: Form the objective function. Profit from one package of A = Rs 7. Profit from one package of B = Rs 10. Hence, $$Z = 7x + 10y.$$ The objective is to maximize $Z$.

Step 3: Convert machine availability into minutes. Each machine is available for 4 hours per day. Since 1 hour = 60 minutes, $$4 \text{ hours} = 240 \text{ minutes}.$$

Step 4: Automatic machine constraint. Each package of A uses 4 minutes. Each package of B uses 6 minutes. Thus, total automatic machine time cannot exceed 240 minutes: $$4x + 6y \le 240.$$ Dividing by 2, $$2x + 3y \le 120.$$

Step 5: Hand-operated machine constraint. Each package of A uses 6 minutes. Each package of B uses 3 minutes. Hence, $$6x + 3y \le 240.$$ Dividing by 3, $$2x + y \le 80.$$

Step 6: Add non-negativity restrictions. $$x \ge 0, \quad y \ge 0.$$

Step 7: Final LPP. Maximize $$Z = 7x + 10y$$ subject to $$2x + 3y \le 120$$ $$2x + y \le 80$$ $$x \ge 0, \quad y \ge 0.$$

Example 4: Investment Problem

A person has Rs 100,000 to invest in two types of bonds. Bond A pays 8% interest per year, and Bond B pays 10% interest per year. To manage risk, the investor wants to invest at least Rs 20,000 in Bond A, and the amount invested in Bond B should not exceed the amount invested in Bond A. Formulate the LPP to maximize the annual return.

Solution: Step 1: Define the variables. Let Rs $x$ be invested in Bond A and Rs $y$ be invested in Bond B.

Step 2: Form the objective function. Annual return from Bond A = $0.08x$. Annual return from Bond B = $0.10y$. Therefore, $$Z = 0.08x + 0.10y.$$ The objective is to maximize $Z$.

Step 3: Write the total investment constraint. The total amount invested cannot exceed Rs 100,000: $$x + y \le 100000.$$

Step 4: Minimum investment in Bond A. The investor wants to invest at least Rs 20,000 in Bond A: $$x \ge 20000.$$

Step 5: Risk condition. The amount in Bond B should not exceed the amount in Bond A: $$y \le x.$$

Step 6: Add non-negativity restrictions. Since money invested cannot be negative, $$x \ge 0, \quad y \ge 0.$$

Step 7: Final LPP. Maximize $$Z = 0.08x + 0.10y$$ subject to $$x + y \le 100000$$ $$x \ge 20000$$ $$y \le x$$ $$x \ge 0, \quad y \ge 0.$$

Example 5: Tailor Shop Problem

A tailor has 80 sq. meters of cotton material and 120 sq. meters of woolen material. A suit requires 1 sq. meter of cotton and 3 sq. meters of woolen material. A dress requires 2 sq. meters of cotton and 1 sq. meter of woolen material. The tailor makes a profit of Rs 500 on a suit and Rs 400 on a dress. Formulate the LPP to maximize his profit.

Solution: Step 1: Define the variables. Let $x$ be the number of suits and $y$ be the number of dresses.

Step 2: Form the objective function. Profit on one suit = Rs 500. Profit on one dress = Rs 400. Hence, $$Z = 500x + 400y.$$ The objective is to maximize $Z$.

Step 3: Cotton material constraint. Each suit requires 1 sq. meter of cotton, so $x$ suits require $x$ sq. meters. Each dress requires 2 sq. meters of cotton, so $y$ dresses require $2y$ sq. meters. Total cotton available is 80 sq. meters: $$x + 2y \le 80.$$

Step 4: Woolen material constraint. Each suit requires 3 sq. meters of woolen material. Each dress requires 1 sq. meter of woolen material. Total woolen available is 120 sq. meters: $$3x + y \le 120.$$

Step 5: Add non-negativity conditions. $$x \ge 0, \quad y \ge 0.$$

Step 6: Final LPP. Maximize $$Z = 500x + 400y$$ subject to $$x + 2y \le 80$$ $$3x + y \le 120$$ $$x \ge 0, \quad y \ge 0.$$

Example 6: Crop Allocation Problem

A cooperative society of farmers has 50 hectares of land to grow two crops, X and Y. The profit from crops X and Y per hectare are estimated as Rs 10,500 and Rs 9,000 respectively. To control weeds, a liquid herbicide has to be used for crops X and Y at rates of 20 litres and 10 litres per hectare respectively. Further, no more than 800 litres of herbicide should be used in order to protect fish and wildlife using a pond which collects drainage from this land. Formulate an LPP to maximize the total profit of the society.

Solution: Step 1: Define the variables. Let $x$ hectares be allocated to crop X and $y$ hectares be allocated to crop Y.

Step 2: Form the objective function. Profit per hectare from crop X = Rs 10,500. Profit per hectare from crop Y = Rs 9,000. Hence, $$Z = 10500x + 9000y.$$ The objective is to maximize $Z$.

Step 3: Land constraint. Total available land is 50 hectares: $$x + y \le 50.$$

Step 4: Herbicide constraint. Crop X requires 20 litres per hectare, so $x$ hectares require $20x$ litres. Crop Y requires 10 litres per hectare, so $y$ hectares require $10y$ litres. Total herbicide used should not exceed 800 litres: $$20x + 10y \le 800.$$ Dividing by 10, $$2x + y \le 80.$$

Step 5: Add non-negativity restrictions. $$x \ge 0, \quad y \ge 0.$$

Step 6: Final LPP. Maximize $$Z = 10500x + 9000y$$ subject to $$x + y \le 50$$ $$2x + y \le 80$$ $$x \ge 0, \quad y \ge 0.$$

Example 7: Cargo Loading Problem

A cargo plane has three compartments for storing cargo: front, center, and rear. These compartments have capacity limits on both weight and space. The front compartment can take 10 tons of weight and 6800 cubic feet of space. The center can take 16 tons and 8700 cubic feet. The rear can take 8 tons and 5300 cubic feet. The plane is offered two types of cargo: Type 1 yields a profit of Rs 300/ton, requires 480 cubic feet/ton. Type 2 yields a profit of Rs 400/ton, requires 650 cubic feet/ton. We want to formulate a simple LPP to maximize profit, assuming cargo can be split across compartments, so we just look at total plane capacity.

Solution: Step 1: Compute total capacities of the plane. Total weight capacity: $$10 + 16 + 8 = 34 \text{ tons}.$$ Total space capacity: $$6800 + 8700 + 5300 = 20800 \text{ cubic feet}.$$

Step 2: Define the variables. Let $x$ tons of cargo type 1 be loaded and $y$ tons of cargo type 2 be loaded.

Step 3: Form the objective function. Profit from cargo type 1 = Rs 300 per ton. Profit from cargo type 2 = Rs 400 per ton. Hence, $$Z = 300x + 400y.$$ The objective is to maximize $Z$.

Step 4: Write the weight constraint. Total weight loaded cannot exceed 34 tons: $$x + y \le 34.$$

Step 5: Write the space constraint. Each ton of cargo type 1 requires 480 cubic feet. Each ton of cargo type 2 requires 650 cubic feet. Total space cannot exceed 20800 cubic feet: $$480x + 650y \le 20800.$$

Step 6: Add non-negativity restrictions. $$x \ge 0, \quad y \ge 0.$$

Step 7: Final LPP. Maximize $$Z = 300x + 400y$$ subject to $$x + y \le 34$$ $$480x + 650y \le 20800$$ $$x \ge 0, \quad y \ge 0.$$

Example 8: Mining Problem

A mining company operates two mines. Mine I produces 1 ton of high-grade, 3 tons of medium-grade, and 5 tons of low-grade ore per day. Mine II produces 2 tons of high-grade, 2 tons of medium-grade, and 2 tons of low-grade ore per day. The company needs at least 80 tons of high-grade, 160 tons of medium-grade, and 200 tons of low-grade ore. It costs Rs 2000 per day to operate Mine I and Rs 2500 per day to operate Mine II. Formulate the LPP to minimize the cost.

Solution: Step 1: Define the variables. Let $x$ be the number of days Mine I is operated and $y$ be the number of days Mine II is operated.

Step 2: Form the objective function. Operating cost of Mine I = Rs 2000 per day. Operating cost of Mine II = Rs 2500 per day. Therefore, $$Z = 2000x + 2500y.$$ The objective is to minimize $Z$.

Step 3: Write the ore requirements.

• High-grade ore: Mine I produces 1 ton/day, Mine II produces 2 tons/day. Required at least 80 tons: $$x + 2y \ge 80.$$

• Medium-grade ore: Mine I produces 3 tons/day, Mine II produces 2 tons/day. Required at least 160 tons: $$3x + 2y \ge 160.$$

• Low-grade ore: Mine I produces 5 tons/day, Mine II produces 2 tons/day. Required at least 200 tons: $$5x + 2y \ge 200.$$

Step 4: Add non-negativity restrictions. The number of operating days cannot be negative: $$x \ge 0, \quad y \ge 0.$$

Step 5: Final LPP. Minimize $$Z = 2000x + 2500y$$ subject to $$x + 2y \ge 80$$ $$3x + 2y \ge 160$$ $$5x + 2y \ge 200$$ $$x \ge 0, \quad y \ge 0.$$

Example 9: Advertising Campaign

A company wants to launch an advertising campaign using radio and television. Each radio ad costs Rs 3000 and reaches 1,000 people. Each TV ad costs Rs 10,000 and reaches 4,000 people. The total advertising budget is Rs 60,000. The company wants to run at least 5 radio ads and at least 2 TV ads. Formulate the LPP to maximize the total number of people reached.

Solution: Step 1: Define the variables. Let $x$ be the number of radio advertisements and $y$ be the number of television advertisements.

Step 2: Form the objective function. Each radio ad reaches 1000 people, so $x$ radio ads reach $1000x$ people. Each TV ad reaches 4000 people, so $y$ TV ads reach $4000y$ people. Hence, $$Z = 1000x + 4000y.$$ The objective is to maximize $Z$.

Step 3: Write the budget constraint. Cost of one radio ad = Rs 3000. Cost of one TV ad = Rs 10000. Total budget available = Rs 60000. Therefore, $$3000x + 10000y \le 60000.$$ Dividing by 1000, $$3x + 10y \le 60.$$

Step 4: Minimum advertisement requirements. At least 5 radio ads: $$x \ge 5.$$ At least 2 TV ads: $$y \ge 2.$$

Step 5: Add non-negativity restrictions. These are already implied by $x \ge 5$ and $y \ge 2$, but in standard formulation it is still acceptable to mention them separately if desired.

Step 6: Final LPP. Maximize $$Z = 1000x + 4000y$$ subject to $$3x + 10y \le 60$$ $$x \ge 5$$ $$y \ge 2.$$

Example 10: Blending Problem

A manufacturer produces an alloy consisting of metals A and B. The alloy must contain at least 20% of metal A and at most 50% of metal B. The manufacturer has 100 kg of metal A and 150 kg of metal B available. Metal A costs Rs 50/kg and metal B costs Rs 40/kg. Formulate an LPP to minimize the cost of producing 100 kg of the alloy.

Solution: Step 1: Define the variables. Let $x$ be the number of kilograms of metal A used and $y$ be the number of kilograms of metal B used.

Step 2: Form the objective function. Cost of metal A = Rs 50 per kg. Cost of metal B = Rs 40 per kg. Therefore, $$Z = 50x + 40y.$$ The objective is to minimize $Z$.

Step 3: Total quantity condition. Since exactly 100 kg of alloy must be produced, $$x + y = 100.$$

Step 4: Composition constraints. At least 20% of the 100 kg alloy must be metal A: $$x \ge 20.$$ At most 50% of the 100 kg alloy can be metal B: $$y \le 50.$$

Step 5: Availability constraints. Available metal A = 100 kg, so $$x \le 100.$$ Available metal B = 150 kg, so $$y \le 150.$$ These are true but not restrictive once $x+y=100$ is imposed. Still, they may be mentioned for completeness.

Step 6: Add non-negativity restrictions. $$x \ge 0, \quad y \ge 0.$$

Step 7: Final LPP. Minimize $$Z = 50x + 40y$$ subject to $$x + y = 100$$ $$x \ge 20$$ $$y \le 50$$ $$x \ge 0, \quad y \ge 0.$$

Note: Since $x + y = 100$, the condition $y \le 50$ implies $x \ge 50$. So the condition $x \ge 20$ is weaker than the condition forced by $y \le 50$. The formulation is still mathematically valid as written.