]]>
LearnNext
Get a free home demo of LearnNext

Available for CBSE, ICSE and State Board syllabus.
Call our LearnNext Expert on 1800 419 1234 (tollfree)
OR submit details below for a call back

clear

Linear Programming Problem

12,135 Views
Have a doubt? Clear it now.
live_help Have a doubt, Ask our Expert Ask Now
format_list_bulleted Take this Lesson Test Start Test

Linear Programming Problem - Lesson Summary

Now the graphical method of linear inequalities to solve linear programming problems.

Problems that seek to maximise (or minimise) profit (or cost) form a general class of problems are called optimisation problems.

Ex:

A manufacturer makes two models A and B of a product. Each model should be processed by two machines. To complete one unit of model A, machine I and II work for 1 hour and 2 hours, respectively. To complete one unit of model B, machines I and II must work 4 hours and 2 hours, respectively. Machine I may not operate more than 8 hours per day and machine II not more than 10 hours per day. If the profits on models A and B per unit are Rs 100 and Rs 200, respectively, how many units of each model should the manufacturer produce per day to get the maximum profit?

Let no. of units of Model A = x

No. of units of Model B = y ≥ 0 and y ≥ 0

Time taken by Machine I to make 1 unit of both the models = (1.x + 4.y) hours

Machine I cannot be used for more than 8 hours.

⇒ x + 4y ≤ 8

Machine II should be used for (2x + 2y) hours.

Machine II cannot be used for more than 10 hours.

⇒2 x + 2y ≤ 10

⇒ x + y ≤ 5

The profit on model A is Rs 100 and model B is Rs 200.

Total profit = 100x + 200y

Objective function (Z) = 100x + 200 y

Maximise Z = 100x + 200 y


Objective function:
A linear function, Z = ax + by, where a, b are constants, which has to be maximised or minimised subject to linear inequality constraints, is called a linear objective function.

Maximise Z = 100x + 200 y,

Subject to the constraints:

x ³ 0; y ³ 0; x + 4y ≤ 8; and x + y ≤ 5

i) x + 4y = 8

  x

  0

  8

  y

  2

  0

The ordered pairs are (0, 2) and (8, 0).

x + y ≤ 5

ii) x + y = 5

  x

  0

  5

  y

  5

  0

The ordered pairs are (0, 5) and (5, 0).

The common region of all the inequalities is known as the feasible region or feasible solution.

Theorem1:
Let R be the feasible region for a linear programming problem, and let Z = ax + by be the objective function. If R is closed (bounded), then objective function Z has both a maximum and a minimum value on R, and each of these occurs at a corner point (vertex) of R.


Theorem 2:
If R is open (unbounded), then a maximum or a minimum value of the objective function may not exist. However, if it exists, it must occur at a corner point of R.

When the feasible region is closed, let P and Q be the maximum and minimum values of the objective function.

Case (i) - If the open half plane determined by ax + by > P has no point in common with the feasible region, then P is the maximum value of the objective function; else, there is no maximum value.

Case (ii): Q is the minimum value of Z, if the open half plane determined by ax + by < Q has no point in common with the feasible region. Otherwise, Z has no minimum value.

This method of finding the maximum or minimum value of an objective function is known as the 'Corner Point Method'.

Substitute the corner points in the Objective function Z = 100x + 200 y

   Corner points (x, y)

   Value of the objective function, Z = 100x + 200y

  O (0,0)

   Z = 100(0) + 200(0) = 0

  A (5,0)

   Z = 100(5) + 200(0) = 500

  B (4,1)

   Z = 100(4) + 200(1) = 600

  C (0,2)

   Z = 100(0) + 200(2) = 400












The maximum value of the objective function is 600, which is at B (4, 1).

No. of units of model A = 4

No. of units of model B = 1.

Comments(0)

Feel the LearnNext Experience on App

Download app, watch sample animated video lessons and get a free trial.

Desktop Download Now
Tablet
Mobile
Try LearnNext at home

Get a free home demo. Book an appointment now!

GET DEMO AT HOME