Linear Programming

Step I: In every LPP, certain decisions are to be made. These decisions are represented by decision variables. These decision variables are those quantities whose values are to be determined. Identify the variables and denote them as x₁, x₂, x₃ …. or x, y and z etc.

Step II: Identify the objective function and express it as a linear function of the variables introduced in Step I.

Step III: In a LPP, the objective function may be in the form of maximising profits or minimising costs. Hence, identify the type of optimisation, i.e., maximisation or minimisation.

Step IV: Identify the set of constraints stated in terms of decision variables and express them as linear inequations or equations as the case may be.

Step V: Add the non-negativity restrictions on the decision variables, as in the physical problems. Negative values of decision variables have no valid interpretation.

Max (or min) Z = c₁x₁ + c₂x₂ + . . . + c_nx_n, where c₁,c₂, . . . c_n are constants and x₁, x₂, … x_n are called decision variables such that Ax$\le (\ge )$B and x_i$\ge$ 0.

5x + 2y ≤ 10, x ≥ 0,y ≥ 0.

It is being given that at least one of each must be produced. (C.B.S.E. 2017)

subject to the constraints:

3x + 5y ≤ 15, 5x + 2y ≤ 10, x ≥ 0,y ≥ 0. (N.C.E.R.T)

x +y ≥ 8, 3x + 5y ≤ 15, x ≥ 0, y ≥ 0. (N.C.E.R.T.)

Z = – 50x + 20y

subject to the constraints:

2x-y ≥ – 5, 3x +y ≥ 3, 2x – 3y ≤ 12, x,y ≥ 0. (N.C.E.R.T.)

Hence, find the shortest distance between the lines. (C.B.S.E. Sample Paper 2018-19)

Draw the line AB: 5.v + 2y = 10 …(1),

which meets x-axis at A (2, 0) and y-axis at B (0,5).

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

Hence, the graph of the given LPP is as shown (shaded):

Draw the st. lines x + 2y = 10 and 2x + y = 8.

These lines meet at E (2,4).

Hence, the solution of the given linear inequations is shown as shaded in the following figure :

From the above shaded portion, the linear constraints are :

2x + y ≥ 2,x – y ≤ 1,

x + 2y ≤ 8, x ≥ 0, y ≥ 0.

Let ‘x’ neclaces and ‘y’ bracelets be manufactured per day.

Then LPP problem is:

Maximize Z = 100x+300y

Subject to the constraints : x + y ≤ 24,

(1) (x) + $\frac{1}{2}$y ≤ l6,

i.e. 2x + y ≤ 32

and x ≥ 1

and y ≥ 1

i.e. x – 1 ≥ 0

and y – 1 ≥ 0.

Let ‘x’ be the number of old hens and ‘y’ the number of young hens.

Profit = (3x + 5y) $\frac{30}{100}$ – (x + y) (1)

= $\frac{9x}{10}$+$\frac{3}{2}$yx – y

= $\frac{y}{2}$−$\frac{x}{10}$=$\frac{5y-x}{10}$

∴ LPP problem is:

Maximize Z = $\frac{5y-x}{10}$ subject to:

x ≥ 0,

y ≥ 0,

x + y ≤ 20 and

2x + 5y ≤ 80.

The system of constraints is :

3x + 5y ≤ 15 …(1)

5x + 2y ≤ 10 …(2)

and x ≥ 0, y≥ 0 …(3)

The shaded region in the following figure is the feasible region determined by the system of constraints (1) – (3):

It is observed that the feasible region OCEB is bounded. Thus we use Corner Point Method to determine the maximum value of Z, where:

Z = 5x + 3y …(4)

The co-ordinates of O, C, E and B are (0, 0), (2,0), $\left(\frac{20}{19},\frac{45}{19}\right)$ (Solving 3x + 5y = 15 and 5x + 2y – 10) and (0, 3) respectively.

We evaluate Z at each comer point:

The system of constraints is :

x +y ≥ 8, , x ≥ 0, y ≥ 0…(1)

3x + 5y ≤ 15 …(2)

and x ≥ 0, y ≥ 0 …(3)

It is observed that there is no point, which satisfies all (1) – (3) simultaneously.

Thus there is no feasible region.

Hence, there is no feasible solution.

Solution:

The system of constraints is :

2x-y ≥ – 5 …(1)

3x +y ≥ 3 …(2)

2x – 3y ≤ 12 …(3)

and x,y ≥ 0 …(4)

The shaded region in the following figure is the feasible region determined by the system of constraints (1) – (4).

t is observed that the feasible region is unbounded.

We evaluate Z = – 50x + 20y at the corner points:

A (1, 0), B (6, 0), C (0, 5) and D (0, 3):

From the table, we observe that – 300 is the minimum value of Z.

But the feasible region is unbounded.

∴– 300 may or may not be the minimum value of Z. ”

.

For this, we draw the graph of the inequality.

– 50x + 20y < – 300

i.e. – 5x + 2y < – 30.

Since the remaining half-plane has common points with the feasible region,

∴ Z = – 50x + 20y has no minimum value.

The given system of constraints is:

x – 2y ≤ 2 …(1)

3x + 2y < 12 …(2)

-3x + 2y ≤ 3 …(3)

and x ≥ 0, y ≥ 0.

The shaded region in the above figure is the feasible region determined by the system of constraints (1) – (4). It is observed that the feasible region OAHGF is bounded. Thus we use Corner Point Method to determine the maximum and minimum value of Z, where

Z = 5x + 2y …(5)

The co-ordinates of O, A, H, G and F are :

(0, 0). (2. 0), $\left(\frac{7}{2},\frac{3}{4}\right)$ and $\left(\frac{3}{2},\frac{15}{4},\frac{3}{2}\right)$

respectively. [Solving x

2y = 2 and 3x + 2y = 12 for

H and -3x + 2y = 3 and

3x + 2y = 12 for G]

We evaluate Z at each corner point: