Maharashtra Board Class 12 Maths Commerce Part II Chapter 6 Linear Programming PDF Download

Linear Programming

Let's Study

Meaning of L.P.P.

Mathematical formula of L.P.P.

Solution of L.P.P. by graphical Method

Let's Recall

Linear inequations

A linear equation in two variables namely \(ax + by + c = 0\), where \(a, b, c \in \mathbb{R}\) and \((a,b) \neq (0,0)\), represents a straight line. A straight line makes three disjoint parts of the plane: the points lying on the straight line and two half planes on either side, which are represented by \(ax + by + c < 0\) or \(ax + by + c > 0\).

The set of points \(\{(x, y) | ax + by + c < 0\}\) and \(\{(x, y) | ax + by + c > 0\}\) are two open half planes. The two sets have the common boundary \(\{(x,y) | ax + by + c = 0\}\).

In the earlier classes, we have studied graphical solution of linear equations and linear inequations in two variables. In this chapter, we shall study these graphical solutions to find the maximum/minimum value of a linear expression.

Let's Learn

6.1 Linear Programming Problem (L.P.P.)

Linear programming is used in industries and government sectors where attempts are made to increase the profitability or efficiency and to reduce wastage. These problems are related to efficient use of limited resources like raw materials, man-power, availability of machine time, cost of material and so on.

Linear Programming is a mathematical technique designed to help for planning and decision making. Linear Programming problems are also known as optimization problems. Mathematical programming involves optimization of a certain function, called objective function, subject to given conditions or restrictions known as constraints.

Meaning of L.P.P.

Linear implies all the mathematical functions containing variables of index one. A L.P.P. may be defined as the problem of maximizing or minimizing a linear function subject to linear constraints.

These constraints may be equations or inequations.

Now we formally define the terms related to L.P.P. as follows.

1) Decision Variables: The variables involved in L.P.P. are called decision variables.

2) Objective function: A linear function of decision variables which is to be optimized, i.e. either maximized or minimized, is called objective function.

3) Constraints: Conditions under which the objective function is to be optimized, are called constraints. These are in the form of equations or inequations.

4) Non-negativity constraints: In some situations, the values of the variables under considerations may be positive or zero due to the imposed conditions. These constraints are referred as non-negativity constraints.

Teacher's Note

Linear Programming helps factories decide how much to make to earn the most profit. For example, a biscuit factory decides how many biscuits and cookies to make to earn maximum money.

Exam Trick

Remember: L.P.P. means finding the best answer. Just like you find the best price when shopping, L.P.P. finds the best profit or lowest cost.

Points to Remember

L.P.P. is used to maximize profit or minimize cost.
Decision variables are the things we want to decide, like how many items to make.
Constraints are the limits, like how many hours the machine can work.
Objective function is what we want to make biggest or smallest.

6.2 Mathematical Formulation of L.P.P.

Step 1: Identify the decision variables as \((x,y)\) or \((x_1, x_2)\).

Step 2: Identify the objective function and write it as mathematical expression in terms of decision variables.

Step 3: Identify the different constraints and express them as mathematical equations or inequations.

The General Mathematical Form of L.P.P.

The L.P.P. can be put in the following form.

Maximize \(z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n\) ............(1)

subject to the constraints.

\[\begin{align} a_{11} x_1 + a_{12} x_2 &\leq b_1 \\ a_{21} x_1 + a_{22} x_2 &\leq b_2 \\ &\vdots \\ a_{m1} x_1 + a_{m2} x_2 &\leq b_m \end{align}\]

(2)

and each \(x_i \geq 0\) for \(i = 1, 2\) (3)

1) The linear function in (1) is called the objective function.

2) Conditions in (3) are called non-negativity constraints.

Note:

i) We shall study L.P.P. with only two variables.

ii) We shall restrict ourselves to L.P.P. involving non-negativity constraints.

Teacher's Note

When we write an L.P.P., we first decide what we want (objective function). Then we write the limits we have (constraints). For example, a tailor wants to make shirts and pants to earn most profit, with the limit of cloth available.

Exam Trick

Remember the three steps: First decide variables (what to find), then write objective (what to maximize/minimize), then write constraints (what limits us).

Points to Remember

Step 1 is always to identify decision variables and give them names like x and y.
Step 2 is to write the objective function - what we want to maximize or minimize.
Step 3 is to write all the constraints as equations or inequalities.
Every variable must follow the non-negativity constraint, meaning it must be greater than or equal to zero.

Solved Examples

Ex. 1:

A manufacturer produces bicycles and tricycles, each of which must be processed through two machines, A and B. Machine A has maximum of 120 hours available and machine B has a maximum of 180 hours available. Manufacturing a bicycle requires 4 hours on machine A and 10 hours on machine B. Manufacturing a tricycle requires 6 hours on machine A and 3 hours on machine B. If profits are Rs. 65 for a bicycle and Rs. 45 for a tricycle, formulate L.P.P. to maximize profit.

Solution:

Let Z be the profit which can be made by manufacturing and selling x tricycles and y bicycles. \(x \geq 0, y \geq 0\).

Total profit \(z = 45x + 65y\)

Maximize \(Z = 45x + 65y\)

Machine	Tricycles (x)	Bicycles (y)	Availability
A	6	4	120
B	3	10	180

From the above table, remaining conditions are:

\[\begin{align} 6x + 4y &\leq 120 \\ 3x + 10y &\leq 180 \end{align}\]

Therefore, the required formulated L.P.P. is as follows.

Maximize \(z = 45x + 65y\) (objective function)

Subject to \(6x + 4y \leq 120\), \(3x + 10y \leq 180\) (Constraints)

\(x, y \geq 0\) (Non-negativity Constraints)

Ex. 2:

Diet for a sick person must contain at least 4000 units of vitamins, 50 units of minerals and 1500 calories. Two foods F1 and F2 cost Rs. 50 and Rs. 75 per unit respectively. Each unit of food F1 contains 200 units of Vitamins, 1 unit of minerals and 40 calories, whereas each unit of food F2 contain 100 units of vitamins, 2 units of minerals and 30 calories. Formulate the above problem as L.P.P. to satisfy sick person's requirements at minimum cost.

Solution:

Let x units of food F1 and y units of food F2 be fed to sick persons to meet his requirements at minimum cost. \(x \geq 0, y \geq 0\).

Food/Product	F1 (x) Per Unit	F2 (y) Per Unit	Minimum requirement
Vitamin	200	100	4000
Minerals	1	2	50
Calories	40	30	1500
Cost/Unit Rs.	50	75

The sick person's problem is to determine x and y so as to minimize the total cost.

Total cost = \(z = 50x + 75y\)

Minimize \(z = 50x + 75y\)

The remaining conditions are:

\(200x + 100y \geq 4000\)

\(x + 2y \geq 50\)

\(40x + 30y \geq 1500\)

where x, y denote units of food F1 and F2 respectively.

\(\therefore x, y \geq 0\)

\(\therefore\) The L.P.P. is as follows.

Minimize \(z = 50x + 75y\) subject to the constraints

\(200x + 100y \geq 4000\)

\(x + 2y \geq 50\)

\(40x + 30y \geq 1500\)

\(x \geq 0, y \geq 0\)

Teacher's Note

When we solve real problems like diet planning or factory production, we must write down the exact limits and what we want to achieve. This helps us find the best answer.

Exam Trick

Always make a table when formulating L.P.P. It helps you see all the information clearly and write correct constraints.

Points to Remember

Read the problem carefully to find what needs to be decided (variables).
Write down all the limits given in the problem (constraints).
Identify if we need to maximize profit or minimize cost (objective function).
Always check that all variables are greater than or equal to zero.

This is a preview of the first 3 pages. To get the complete book, click below.