Linear Programming

Linear Programming (LPP) is a powerful mathematical technique used for optimization, where the goal is to find the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. It plays a crucial role in various fields such as economics, business, engineering, and military applications.

1.0What is Linear Programming?

There are also some problems where we have to minimize a linear function subject to certain conditions determined by a set of linear inequalities with variables as non-negative. Such problems are called Linear Programming Problems.

Linear Programming Problems (LPPs) are optimization challenges where the goal is to minimize (or maximize) a linear function subject to a set of linear inequalities and conditions, with the variables constrained to be non-negative. These problems are fundamental in various fields, allowing for the efficient allocation of resources, cost reduction, and strategic planning within defined limits.

Thus, a Linear Programming Problem is one that is concerned with finding the optimal value (maximum or minimum value) of a linear function (called objective function) of several variables (say x and y), subject to the conditions that the variables are non-negative and satisfy a set of linear inequalities (called linear constraints). The term linear implies that all the mathematical relations used in the problem are linear relations while the term programming refers to the method of determining a particular programme or plan of action.

A Linear Programming Problem (LPP) involves the following components:

• Objective: Finding the optimal value (maximum or minimum) of a linear function, known as the objective function.
• Variables: The objective function is dependent on several variables (e.g., x and y).
• Non-negativity: The variables are constrained to be non-negative.
• Constraints: The variables must satisfy a set of linear inequalities, referred to as linear constraints.

2.0How to Solve Linear Programming Problems?

Solving Linear Programming Problems (LPP) involves several systematic steps to find the optimal solution, either to maximize or minimize the objective function subject to given constraints. Here is a step-by-step guide:

1. Formulate the Problem

• Define the Objective Function: Clearly state the linear function to be maximized or minimized.

Example: Maximize Z = 3x + 4y

• List the Constraints: Identify all the linear inequalities or equations that constrain the variables.

$\begin{array}{rl}& x+2y\le 8\\ & 3x+y\le 6\\ & x,y\ge 0\end{array}$

• Identify Non-negativity Constraints: Ensure that all variables are non-negative $x\ge 0$, $y\ge 0$.

2. Graphical Method (for Two-Variable Problems)

• Plot the Constraints: Draw the lines corresponding to each linear inequality on a graph.
• Determine the Feasible Region: Identify the area where all constraints overlap; this is the feasible region.
• Find the Vertices: Determine the corner points (vertices) of the feasible region.
• Evaluate the Objective Function: Calculate the value of the objective function at each vertex.
• Identify the Optimal Solution: Choose the vertex that gives the maximum or minimum value of the objective function.

3. Simplex Method (for Larger Problems)

• Set Up the Initial Simplex Tableau: Construct a tableau with the objective function and constraints.
• Identify the Pivot Element: Choose the element to pivot based on specific rules (e.g., the most negative value in the bottom row for maximization).
• Perform Pivot Operations: Adjust the tableau by performing row operations to change the pivot element to 1 and all other elements in the pivot column to 0.
• Iterate: Repeat the pivot operations until there are no negative indicators in the bottom row (for maximization) or no positive indicators (for minimization).
• Read the Solution: Extract the solution from the final tableau where the optimal values of the variables are found.

4. Dual Simplex Method

• Used when the initial solution is infeasible, but optimality conditions are satisfied.
• Adjusts infeasibilities iteratively until a feasible and optimal solution is found.

3.0Linear Programming Solved Examples

Example 1: 

A furniture dealer specializes in selling only two products: tables and chairs. He has Rs. 5000 available to invest and can store up to 60 pieces in total. The cost to purchase a table is Rs. 250, while a chair costs Rs. 50. The dealer can make a profit of Rs. 50 on each table and Rs. 15 on each chair. Assuming that he can sell all the items he purchases, how should he allocate his investment to maximize his profit?

Solution:

This problem can be formulated as below.

Let x and y be the required numbers of tables and chairs respectively. Then, clearly, we have

x ≥ 0,

y ≥ 0; 

x + y ≤ 60;

250x + 50y ≤ 5000. i.e., 5x+ y ≤ 100

Let P be the profit function. Then, P = 50 + 15y.

Now, we have to maximize P

Now, $x+y=60\Rightarrow \frac{x}{60}+\frac{y}{60}=1.$

This line meets the axes at (60, 0) and (0, 60). Plot these points and join them to get the line x + y = 60 

Also, 5x + y = $100\Rightarrow \frac{x}{20}+\frac{y}{100}=1$ .  

This line meets the axes at (20, 0) and (0, 100). Plot these points and

join them to get the line 5x + y = 100.

Also, the line x = 0 is the y-axis and the line y = 0 is the x-axis.

These four straight lines enclose the quadrilateral OABC.

The coordinates of the points O, A, B, C are (0, 0), (20, 0), (10, 50) and (0, 60) respectively.

At these points, the corresponding values of P = 50x + 50 +15y are 0, 1000, 1250 and 900 respectively. Clearly, it is maximum at B (10, 50). 

In other words, we can say that

Maximize. P = 50x + 15y

X + y ≤ 6 0

250x + 50y ≤ 5000

x ≥ 0, y ≥ 0.

So, for a maximum profit, the dealer should purchase 10 tables and 50 chairs

Example 2: 

A young man rides his motorcycle at two different speeds: 25 km per hour, costing him Rs. 2 per kilometer for petrol, and 40 km per hour, costing Rs. 5 per kilometer. With Rs. 100 available for petrol, he wants to determine the maximum distance he can cover within one hour. Frame this scenario as a linear programming problem and then solve it.

Solution:

Suppose that the young man rides x km at 25 km per hour and y km at 40 km per hour. Then, we have to maximize P = x + y.

Clearly:

x ≥ 0, 

y ≥ 0, 

2x + 5y ≤ 100.

Since the available time is at most one hour, we have

$\frac{x}{25}+\frac{y}{40}\le 1$ or  8x + 5y ≤ 200

Now, we solve the system of the inequations.

2x + 5y = 100 ⇒$\frac{x}{50}+\frac{y}{20}=1$ .

This line meets the axes at (50, 0) and (0, 20). Plot these points and join them to get the line 2x + 5y = 100.

In other words, 

Maximize Z = x + y

8x + 5y ≤ 200

2x + 5y ≤ 100

x ≥ 0, y ≥ 0

So, Z = x + y is maximum when $x=\frac{50}{3}$ and $y=\frac{40}{3}$ . Thus, the young man can cover the maximum distance of 30 km, if he rides $\frac{50}{3}$  km at 25 km/h and $\frac{40}{3}$ km at 40 km/h 

Example 3: 

Suppose every gram of wheat provides 01. g of proteins and 0 25. g of carbohydrates, and the corresponding values for rice are 0 05. g and 0 5. g respectively. Wheat costs RS. 5 and rice RS. 20 per kilogram. The minimum daily requirements of proteins and carbohydrates for an average man are 50 g and 200 g respectively. In what quantities should wheat and rice be combined in the daily diet to provide the minimum daily requirements of proteins and carbohydrates at minimum cost, assuming that both wheat and rice are to be taken in the diet? 

Solution:

Let x g of wheat and y g of rice be mixed to fulfill the requirements. Then, we have to minimize the cost function.

$\mathrm{Z}=\frac{5\mathrm{x}}{1000}+\frac{20\mathrm{y}}{1000}\text{, i.e., }\mathrm{Z}=\frac{\mathrm{x}}{200}+\frac{\mathrm{y}}{50}$ …(i)

x g of wheat and y g of rice must give at least 50 g of proteins.

So, we must have

0.1 x + 0.05 y ≥ 50 or 2x + y ≥ 1000.

Similarly, x g of wheat and y g of rice must give at least 200 g of carbohydrates.

So, we must have

0.25x +0.5y ≥ 200 or x + 2y ≥ 800.

Thus, we have to minimize 

$\mathrm{Z}=\frac{\mathrm{x}}{200}+\frac{\mathrm{y}}{50}$ , subject to the constraints

x > 0, 

y > 0, 

2x + y ≥ 1000 and 

x + 2y ≥ 800.

2x + y = 1000 ⇒ $\frac{x}{500}+\frac{y}{1000}=1$

Minimize

$Z=\frac{5x}{1000}+\frac{20y}{1000}$

i.e. $Z=\frac{x}{200}+\frac{y}{50}$

2x +y ≥ 1000

x +2y ≥ 800

Clearly, at B we have x = 0, and at C we have y = 0. Also, the value of Z at E (400, 200) = 6. So, we must have 400 g of wheat and 200 g of rice

Example 4: 

A chemical industry manufactures two compounds, A and B. The table below shows the amount of ingredients C and D (in units per kg) required for compounds A and B, along with the minimum requirements for C and D, and the costs per kg of compounds A and B.

Find the quantities of A and B which would minimize the cost.

Solution:

Let x kg of A and y kg of B be produced. Then,

x ≥ 0, y ≥ 0, x + 2y ≥ 80 and 3x +y ≥ 75.

Then the cost function is given by Z = 4x + 6y.

Minimize Z = 4x + 6y.

Subject to the constraints.

X +2y ≥ 80

3x +y ≥ 75

x ≥ 0. y ≥ 0. 

Thus Z is minimum at Q (14,33)

Hence, for a minimum cost, 14 kg of a and 33 kg of B must be taken.

4.0Linear Programming Practice problems

1. A man has Rs. 1500 to spend on purchasing rice and wheat. A bag of rice costs Rs. 180, and a bag of wheat costs Rs. 120. With a storage capacity of only 10 bags, he earns a profit of Rs. 11 per bag of rice and Rs. 8 per bag of wheat. How many bags of each should he buy to maximize his profit? 

2. A manufacturer produces nuts and bolts for industrial machinery. To produce a packet of nuts, it requires 1 hour on machine A and 3 hours on machine B, while producing a packet of bolts requires 3 hours on machine A and 1 hour on machine B. The manufacturer earns a profit of Rs. 17.50 per packet of nuts and Rs. 7 per packet of bolts. If the machines can operate for a maximum of 12 hours each day, how many packets of each should be produced daily to maximize profit? Additionally, calculate the maximum profit achievable.

3. A dealer wishes to purchase a number of fans and sewing machines. He has only ` Rs.5760 to invest and has space for at most 20 items. A fan costs him Rs. 360 and a sewing machine, Rs. 240. He expects to gain Rs.22 on a fan and Rs.18 on a sewing machine. Assuming that he can sell all the items he can buy, how should he invest the money in order to maximize the profit?