ML Aggarwal Class 12 Maths Solutions Section C Chapter 03 Linear Programming

Chapter 3: Linear Programming

 

Introduction

You already know about linear equations and linear inequations in one and two variables. These can be worked out either algebraically or graphically - using a line diagram for one variable, or on two-dimensional graph paper for two variables x and y. First, we will review how to solve a system of linear inequations. After that, we will use this knowledge widely in tackling problems on linear programming.

 

Section 3.1: Graphical Solution of Linear Inequations

A statement of any one of the following types is called a linear inequation (or inequality) in one variable x or y:

• (i) x < a (ii) x ≤ a (iii) x > a (iv) x ≥ a
• (v) y < b (vi) y ≤ b (vii) y > b (viii) y ≥ b

where a and b are real numbers.

A statement of any one of the following types is called a linear inequation (or inequality) in two variables x and y:

• (i) ax + by + c < 0 (ii) ax + by + c ≤ 0
• (iii) ax + by + c > 0 (iv) ax + by + c ≥ 0

where a, b, c are real numbers and at least one of a and b is non-zero.

A straight line l divides the Cartesian plane into two parts. Each part is called a half plane. A vertical line divides the plane into left half and right half planes. A non-vertical line divides the plane into lower half and upper half planes.

An ordered pair (α, β) of real numbers may or may not satisfy a given inequation (in one or two variables).

The set of all ordered pairs of real numbers which satisfy a given inequation is called the solution set of the inequation.

Since there is a one-to-one match between ordered pairs of real numbers and points on a coordinate plane, we can show the solution set of a given inequation (in one or two variables) by the points on a coordinate plane. The set of all points whose coordinates satisfy a given inequation is called the solution region or feasible region or graph of the inequation. Every point in this region is called a feasible solution.

To find the graphical solution of an inequation in one variable:

• (i) Draw the straight line x = a (or y = b) as the case may be.
• (ii) The straight line x = a divides the coordinate plane into two halves.
• (iii) One half shows the graph of x < a and the other half shows the graph of x > a. Shade the solution region of the given inequation.
• (iv) If an inequation is of the form x ≤ a or x ≥ a, then the points on the line x = a are also part of the solution region. Draw a dark line in the solution region.
• (v) If an inequation is of the form x < a or x > a, then the points on the line x = a are not included in the solution region. Draw a line (or broken line) in the solution region.

Example: Consider the inequation x ≥ 1 in one variable. Draw the straight line x = 1, which is a vertical line. It splits the plane into two halves. The points which lie to the right of the line x = 1 or on the line x = 1 satisfy the given inequation x ≥ 1. Hence, the solution set of the given inequation is {(x, y); x, y ∈ ℝ, x ≥ 1}.

To find the graphical solution of an inequation in two variables:

• (i) Draw the straight line ax + by + c = 0.
• (ii) The straight line ax + by + c = 0 divides the coordinate plane into two halves.
• (iii) One half shows the graph of ax + by + c < 0 and the other half shows the graph of ax + by + c > 0.
• (iv) To identify which half plane the inequation represents, pick any point (α, β) not lying on the line ax + by + c = 0. Check whether it satisfies the inequation or not. If it does, then the inequation shows the half plane containing the point. Shade this region. If it does not, then the inequation shows the half plane which does not contain the point. For ease, we usually pick the point (0, 0). However, if (0, 0) lies on the line, pick any other point of the plane not lying on the line.
• (v) If an inequation is of the form ax + by + c ≤ 0 or ax + by + c ≥ 0, then the points on the line ax + by + c = 0 are also part of the solution region. Draw a dark line in the solution region.
• (vi) If an inequation is of the form ax + by + c < 0 or ax + by + c > 0, then the points on the line are not to be part of the solution region. Draw a line (or broken line) in the solution region.

Example: Consider the inequation 3x + 4y ≥ 12 in two variables. First, draw the straight line 3x + 4y = 12. Setting y = 0, we get x = 4. Setting x = 0, we get y = 3. Therefore, the line passes through points A(4, 0) and B(0, 3). The line splits the coordinate plane into two halves. We note that the point O(0, 0) lies below the line AB and does not satisfy the given inequation 3x + 4y ≥ 12 (because 3.0 + 4.0 = 0 < 12). Hence, the graph of the given inequation 3x + 4y ≥ 12 is that part of the coordinate plane which lies above the line AB (including the points on the line AB).

To solve a system of linear inequations:

• (i) Draw the graphs (or solution regions) of all the given linear inequations.
• (ii) Find the common part of the coordinate plane which satisfies all the given linear inequations.
• (iii) This common part of the coordinate plane is the required solution of the given inequations. Label the corner points clearly.

 

Section 3.2: Linear Programming

In real-world situations, resources are limited and must be used wisely. In a military operation, the goal is to cause maximum damage to an enemy at minimum cost and loss. In an industry, management always tries to make the best use of its resources. A business owner would like to earn unlimited profits, but is held back by limited manpower, capital, and market demand. A salaried person tries to make investments so that returns are high but income tax is kept low.

In all these cases, if constraints are shown by linear equations or inequations (in one, two, or more variables), and a particular plan of action from many choices must be picked, we use linear programming. The word "linear" means that all inequations used and the function to be maximized or minimized are linear. The word "programming" refers to planning (choosing amongst alternatives) rather than computer programming in the traditional sense.

Linear programming is thus a method for finding the best values of a linear function when the solution must satisfy certain constraints shown as linear equations or inequations.

A practical problem may involve many variables and is usually worked out by using the Simplex Method and a computer. In this chapter, we focus on linear functions with two variables, so they can be worked out by drawing a graph on the xy-plane.

Three Classical Linear Programming Problems (L.P.P.):

(i) Manufacturing problems: When a firm can make different products in different amounts, and each product needs fixed manpower, machine hours, labour hours per unit, storage space per unit, etc., it must choose which products to make and in what quantities to maximize profits.

(ii) Diet problems: Different foods have different amounts of nutrients (vitamins, minerals, etc.). In diet problems, we must determine what amounts of different foods should be included in a diet to minimize cost while still providing a certain (minimum) amount of each nutrient.

(iii) Transportation problems: A factory may have different godowns at different places and must send its products to many locations from these godowns. The problem is to find what amounts should be moved from what godowns to what places so that the total transportation cost is as low as possible.

Some Definitions:

Objective Function: If a₁, a₂, ..., aₙ are constants and x₁, x₂, ..., xₙ are variables (called decision variables), then the linear function Z = a₁x₁ + a₂x₂ + ... + aₙxₙ which is to be worked on (maximized or minimized) is called the objective function. It is always non-negative. In business, the objective function of total profit or volume of production is usually to be maximized, while the objective function of total production cost or production time is to be minimized.

Non-negative Restrictions: The values of the variables x₁, x₂, …, xₙ in an L.P.P. are always non-negative (≥ 0). Thus, x₁ ≥ 0, x₂ ≥ 0, …, xₙ ≥ 0. For two variables x and y, this means we will work only in the first quadrant of the coordinate plane.

Constraints: The inequations or equations on the variables of an L.P.P. are called constraints. They may use =, >, ≥, < or ≤.

Feasible Region and Feasible Solution: The common region set by all the constraints of an L.P.P. is called a feasible region. Every point in this region is called a feasible solution to the L.P.P. The feasible region is always a convex set - if any two points in this set are joined by a straight line segment, all the points on this segment also lie in the set. Note that the feasible region can be bounded or unbounded, but it is always convex.

Optimal Solution: A feasible solution which maximizes or minimizes the objective function is called an optimal solution. An L.P.P. may have zero, one, or more than one optimal solution.

Basic Requirements of Linear Programming:

• (i) There must be a well defined goal to achieve (to maximize or minimize).
• (ii) There must be limited availability of resources - that is, there are constraints or limits on how limited resources can be used or split among different competing activities.
• (iii) There are a finite number of decision variables (activities or products) and a finite number of constraints.
• (iv) All the elements of an L.P.P. should be countable/measurable.
• (v) Both the objective function and constraints must be shown in terms of linear equations or inequations.
• (vi) Planning requires that there must be alternative courses of action - that is, there are alternatives available to which resources can be put.
• (vii) All decision variables should take on non-negative values.

Advantages of Linear Programming:

Linear programming has uses in military operations, choosing an optimal product line, diet problems, and transportation problems. It helps in picking the best alternative from a set of feasible alternatives so that profit is maximized or costs are minimized. Other areas of use include:

• (i) Picking the best media mix (radio, TV, newspapers, hoardings, magazines, internet) to increase advertising reach within a set publicity budget.
• (ii) Finding shortest routes for travelling salesmen.
• (iii) Helping a farmer pick the best crop mix to lower risk and raise profit.

So linear programming helps in:

• (i) Picking the best choice from a set of choices so that profit is maximized or cost is minimized.
• (ii) Taking into account not only internal factors like manpower, machines, budget, storage space, etc. but also outside factors like market demand, purchasing power of the customer, etc.
• (iii) Finding bottlenecks in the production process.
• (iv) Picking the best production policy and inventory policy so that seasonal changes in demand can be managed.

Limitations of Linear Programming:

• (i) It deals with optimizing a single goal. In real life, there may be many goals.
• (ii) The idea that input and output variables are directly connected is not always true. Usually, the more you produce, the less the average cost per unit (economies of scale).
• (iii) The straight-line nature of variables assumes that resources needed for multiple activities add up. However, product mix usually means that the need is less than the sum.
• (iv) In real life, many decision variables take whole numbers, e.g., number of workers. Linear programming deals with variables having ongoing values.

 

Section 3.3: Formulation of an L.P.P. in Two Variables x and y

There are three steps in the mathematical formulation of an L.P.P. and solving it:

(i) To identify the objective function as a linear combination of variables (x and y) and to build all constraints, that is, linear equations and inequations involving these variables. Thus, an L.P.P. can be stated mathematically as:

Maximize (or minimize) Z = ax + by

subject to the conditions:

aᵢx + bᵢy ≤ (or ≥ or = or > or <) cᵢ, where i = 1 to n

and the non-negative restrictions:

x ≥ 0, y ≥ 0.

(ii) To find the solutions (feasible region) of these equations and inequations by some mathematical method. Here we will study only the graphical method.

(iii) To find the optimal solution - that is, to pick particular values of the variables x and y that give the desired value (maximum or minimum) of the objective function.

 

Question 1. A shopkeeper deals in two items - wall hangings and artificial plants. He has Rs 15000 to invest and space to store at most 80 pieces. A wall hanging costs him Rs 300 and an artificial plant Rs 150. He can sell a wall hanging at a profit of Rs 50 and an artificial plant at a profit of Rs 18. Assuming that he can sell all the items that he buys, formulate a linear programming problem in order to maximize his profit.
Answer: Let x be the number of wall hangings and y be the number of artificial plants that the dealer buys and sells. Then the profit of the dealer is Z = 50x + 18y, which is the objective function. Since a wall hanging costs Rs 300 and an artificial plant costs Rs 150, the cost of x wall hangings and y artificial plants is 300x + 150y. The dealer can put in at most Rs 15000. Therefore, the investment constraint is 300x + 150y ≤ 15000, which simplifies to 2x + y ≤ 100. Since the dealer has space to store at most 80 pieces, another constraint (space constraint) is x + y ≤ 80. The number of wall hangings and artificial plants cannot be negative. Thus the non-negativity constraints are x ≥ 0, y ≥ 0. The mathematical formulation of the L.P.P. is: Maximize Z = 50x + 18y subject to the constraints 2x + y ≤ 100, x + y ≤ 80, x ≥ 0, y ≥ 0.
In simple words: A dealer wants to buy wall hangings and plants with Rs 15000 to earn the most profit. We write down what limits him (money and space) and what he wants to maximize (profit), and express this as a math problem with variables x and y.

Exam Tip: Always define your variables clearly at the start. Write the profit (or cost) formula first as the objective function, then list each constraint as a separate inequation in the standard form.

 

Question 2. (Diet problem) A diet is to contain at least 80 units of vitamin A and 100 units of minerals. Two foods F₁ and F₂ are available. Food F₁ costs Rs 4 per kg and F₂ costs Rs 5 per kg. One kg of food F₁ contains 3 units of vitamin A and 4 units of minerals. One kg of food F₂ contains 6 units of vitamin A and 3 units of minerals. We wish to find the minimum cost for a diet that is made up of a mixture of these two foods and also meets the minimum nutritional requirements. Formulate this as a linear programming problem.
Answer: Let the mixture include x kg of food F₁ and y kg of food F₂. The table below organizes the given information:

The minimum need for vitamin A is 80 units, so 3x + 6y ≥ 80. The minimum need for minerals is 100 units, so 4x + 3y ≥ 100. Also x ≥ 0, y ≥ 0. Since the cost of food F₁ is Rs 4 per kg and the cost of food F₂ is Rs 5 per kg, the total cost of purchasing x kg of food F₁ and y kg of food F₂ is Z = 4x + 5y, which is the objective function. The mathematical formulation of the L.P.P. is: Minimize Z = 4x + 5y subject to the constraints 3x + 6y ≥ 80, 4x + 3y ≥ 100, x ≥ 0, y ≥ 0.
In simple words: We want to mix two foods cheaply while making sure they provide enough vitamins and minerals. We set up the problem by listing what each food gives per kg, what the minimum needs are, and what we want to minimize (the cost).

Exam Tip: For diet or nutrition problems, always make a table to organize the nutrient content and requirements. The inequations will use ≥ (at least) for minimum requirements and ≤ for maximum limits.

 

Question 3. (Manufacturing problem) A manufacturer produces nuts and bolts for industrial machinery. It takes 1 hour of work on machine A and 3 hours on machine B to produce a package of nuts. It takes 3 hours on machine A and 1 hour on machine B to produce a package of bolts. He earns a profit of Rs 2.50 per package on nuts and Rs 1 per package on bolts. Form a linear programming problem to maximize his profit, if he operates each machine for at most 12 hours.
Answer: Suppose that x packages of nuts and y packages of bolts are made. The goal of the maker is to maximize the profit, 2.50x + 1y. The time needed on machine A to make x packages of nuts and y packages of bolts is 1.x + 3.y = x + 3y. The time needed on machine B is 3.x + 1.y = 3x + y. From the given data, we can state the L.P.P. as: Maximize Z = 2.50x + y subject to the constraints x + 3y ≤ 12 (Machine A constraint), 3x + y ≤ 12 (Machine B constraint), x ≥ 0, y ≥ 0 (Non-negativity constraints).
In simple words: A maker wants to build nuts and bolts to earn the most profit, but each machine can run for at most 12 hours. Different products use different amounts of time on each machine, so we set up a math problem to find the best mix.

Exam Tip: For manufacturing problems, identify which machine(s) each product uses and how long it takes. Write each machine's time limit as a separate constraint, and check that all variables are non-negative.

 

Question 4. (Transportation problem) A brick maker has two depots A and B, with stocks of 30000 and 20000 bricks respectively. He gets orders from three builders P, Q and R for 15000, 20000 and 15000 bricks respectively. The cost (in Rs) of moving 1000 bricks to the builders from the depots is given below:

The maker wishes to find how to meet the order so that transportation cost is as low as possible. Formulate the L.P.P.
Answer: To simplify, assume that 1 unit = 1000 bricks. Suppose depot A gives x units to P and y units to Q, so that depot A gives 30 - x - y bricks to builder R. Now as P wants a total of 15000 bricks, it wants (15 - x) units from depot B. Similarly Q wants (20 - y) units from B and R wants 15 - (30 - x - y) = (x + y - 15) units from B. Using the transportation cost given in the table, total transportation cost is Z = 40x + 20y + 20(30 - x - y) + 20(15 - x) + 60(20 - y) + 40(x + y - 15) = 40x - 20y + 1500. The constraints are that all quantities of bricks given from A and B to P, Q, R are non-negative, that is, x ≥ 0, y ≥ 0, 30 - x - y ≥ 0, 15 - x ≥ 0, 20 - y ≥ 0, x + y - 15 ≥ 0. Hence the problem can be stated as L.P.P. as: Minimize Z = 40x - 20y + 1500 subject to the constraints x + y ≥ 15, x + y ≤ 30, x ≤ 15, y ≤ 20, x ≥ 0, y ≥ 0.
In simple words: A brick maker has stocks at two places and must send them to three builders. We write the total cost formula by tracking what comes from each depot to each builder, then set up constraints to make sure all orders are met and all stocks are used properly.

Exam Tip: For transportation problems, set up a network diagram showing supply points (depots) and demand points (builders). Express the total cost carefully by accounting for each supply-demand pair, and ensure all constraints (supply limits and demand requirements) are included.

 

Section 3.4: Graphical Method of Solving an L.P.P.

Theorem 1: Let R be the feasible region for an L.P.P. and Z = ax + by be the objective function. When Z has an optimal value (maximum or minimum), subject to the constraints shown by linear inequations, this optimal value must happen at a corner point (vertex) of the feasible region.

Theorem 2: Let R be the feasible region for an L.P.P. and Z = ax + by be the objective function. If R is bounded, then the objective function Z has both a maximum and a minimum value on R and each of these happens at a corner point (vertex) of R.

Remark: If R is unbounded, then the objective function may or may not have a maximum or minimum value. However, if it (maximum or minimum) exists, then by Theorem 1, it must happen at a corner point of R.

There are two methods of finding the optimal solution in the feasible region.

(i) Corner Point Method

To work out an L.P.P. graphically, we follow these steps:

• 1. Change the given linear constraints into equalities and then draw their graphs which will be straight lines.
• 2. Find the feasible region of the L.P.P. and find the corner points.
• 3. Work out the objective function Z = ax + by at each corner point, and let M and m be respectively the largest and smallest values.
• 4. If feasible region R is bounded, then M and m are the maximum and minimum values of Z.
• 5. If feasible region R is unbounded, then:
  • (a) M is the maximum value of Z if the open half plane ax + by > M has no point in common with the feasible region. Otherwise Z has no maximum value.
  • (b) m is the minimum value of Z if the open half plane ax + by < m has no point in common with the feasible region. Otherwise Z has no minimum value.
• 6. If two corner points of the feasible region are both optimal solutions of the same type - that is, both give the same maximum or minimum values - then every point on the line segment joining these points gives the same optimal solution.

(ii) Iso-profit or Iso-cost Method

In this method, we pick a fixed value k of the objective function such that Z = ax + by = k is a straight line, called an iso-profit or iso-cost line. Every point on this line yields the same (iso) profit or cost (= k). Now move this line parallel to itself over the feasible region so that it goes through all corner points. For maximization, the corner matching the iso-profit line farthest from the origin gives the maximum value. For minimization, the corner matching the iso-cost line closest to the origin gives the minimum value. If the objective function has the same slope as one of the constraints, the iso-profit or iso-cost line will align with one of the outer lines of the feasible region and we may have many optimal solutions.

 

Exercise 3.1

Solve the following systems of linear inequations:

• 1. 3x + 2y > 5 and y > 2.
• 2. 3x + 2y < 6 and x + 2y > 4.
• 3. 2x + 3y < 12, x ≥ 2 and y ≥ 1.
• 4. x - 2y + 11 > 0, 2x - 3y + 18 ≥ 0 and y ≥ 0.
• 5. x + 2y ≤ 8, x - y ≤ 2, x > 0 and y > 0.
• 6. 3x + 2y - 6 < 0, 3x + 2y ≥ 18

 

Exercise 3.2

Formulate each of the following as a linear programming problem:

Question 1. A furniture dealer deals in only two items - tables and chairs. He has Rs 20000 to invest and space to store at most 80 pieces. A table costs him Rs 800 and a chair costs him Rs 200. He can sell a table for Rs 950 and a chair for Rs 280. Assume that he can sell all the items that he buys. Formulate this problem as an L.P.P. so that he can maximize his profit.
Answer: Maximize Z = 150x + 80y, subject to the constraints 4x + y ≤ 100, x + y ≤ 80, x ≥ 0, y ≥ 0.
In simple words: A dealer buys tables and chairs with Rs 20000. He wants to make as much profit as possible. We write down what stops him (money and space) and turn it into a math problem.

Exam Tip: Calculate the profit per item first (selling price - cost) for each product. Express money and space limits as constraint inequations before writing the objective function.

 

Question 2. A diet for a sick person must contain at least 3000 units of vitamins, 60 units of minerals and 1600 units of calories. Two foods F₁ and F₂ are available at a cost of Rs 6 and Rs 5 per unit respectively. One unit of F₁ contains 200 units of vitamins, 1 unit of mineral and 40 units of calories, while one unit of F₂ contains 100 units of vitamins, 2 units of minerals and 40 units of calories. The aim is to formulate a mixture of foods F₁ and F₂ which gives these minimum levels of nutrients and also costs the least. Formulate it as L.P.P.
Answer: Minimize Z = 6x + 5y, subject to the constraints 2x + y ≥ 30, x + 2y ≥ 60, x + y ≥ 40, x ≥ 0, y ≥ 0.
In simple words: We need to pick a mix of two foods that costs the least but still provides the minimum vitamins, minerals, and calories a sick person needs.

Exam Tip: For diet problems, divide each nutrient requirement by its amount per unit to get the constraint inequation. Use ≥ for "at least" and ≤ for "at most" requirements.

 

Question 3. A retired person wants to invest an amount of up to Rs 20000. His broker suggests investing in two types of bonds A and B. Bond A yields 10% return on the amount put in and bond B yields 15% return on the amount put in. After some thought, he decides to put at least Rs 5000 in bond A and no more than Rs 8000 in bond B. He also wants to put at least as much in bond A as in bond B. Formulate as L.P.P. to maximize his return on investments.
Answer: Maximize Z = 0.10x + 0.15y, subject to the constraints x + y ≤ 20000, x ≥ 5000, y ≤ 8000, x ≥ y, x ≥ 0, y ≥ 0.
In simple words: An investor wants to split his money between two bonds to get the best return, while following rules about minimum and maximum amounts in each bond and relationships between them.

Exam Tip: Parse the text carefully to separate upper and lower bounds, and express relationships between variables (e.g., "at least as much in A as in B" means x ≥ y) as individual constraints.

 

Question 4. A maker has three machines M₁, M₂ and M₃ set up in his factory. Machines M₁ and M₂ can be run for at the most 12 hours, whereas machine M₃ must be run for at least 5 hours a day. The maker makes only two items, each needing the use of these three machines. The following table shows the number of hours needed on these machines for making 1 unit of A or B.

He makes a profit of Rs 60 on item A and Rs 40 on item B. He wants to know how many of each item he should make to have maximum profit. Formulate it as L.P.P.
Answer: Maximize Z = 60x + 40y, subject to the constraints x + 2y ≤ 12, 2x + y ≤ 12, x + (5/4)y ≥ 5, x ≥ 0, y ≥ 0.
In simple words: A maker wants to build two products to earn the most profit, while making sure he uses his three machines within their allowed working hours (or minimum working hours for M₃).

Exam Tip: For each machine, write one constraint showing the total hours used (sum of hours per unit times quantity of each item). Use ≤ for maximum time and ≥ for minimum time.

 

Question 5. There is a factory at two places P and Q. From these places, a certain item is sent to each of three depots at A, B and C. The weekly needs of the depots are 5, 5 and 4 units of the item, while the making capacity of the factories at P and Q are 8 and 6 units. The cost of moving per unit is given below:

How many units should be moved from each factory to each depot in order that moving cost is as low as possible? Formulate the above linear programming problem mathematically.
Answer: Minimize Z = x - 7y + 190 subject to the constraints x + y ≤ 8, x ≤ 5, y ≤ 5, x + y ≥ 4, x ≥ 0, y ≥ 0. (Note: Here x and y represent the amounts transported from factory P to depot A and depot B respectively.)
In simple words: Two factories must send products to three depots. We write the total moving cost formula using what each factory sends to each depot, then make sure all depots get what they need and no factory ships more than it makes.

Exam Tip: In transportation problems, use a network to track supply and demand. Let variables represent specific supply-demand pairs and write the cost formula by summing over all such pairs. Always check that supply totals equal demand totals.