## January 27, 2014

### 10th Class - Imp Concepts in Maths - Polynomials Over Integers

Linear Programming problem: A Linear programming problem consists of minimizing (or maximizing) an objective function f = ax + by where a, b ∈ R, subject to certain constraints expressed as linear inequations in x and y.

A closed convex polygon is the set of all points within and on some polygon with a finite number of vertices.

An open convex region is the set of all the points within and on some polygon, which is open in one side, with a finite number of vertices.

The solution set of a system of finite number of linear equations and inequations in two unknowns is one of the following subsets.
(i) A closed convex polygon
(ii) An open convex polygon
(iii) An empty set

The Fundamental Theorem:

If the values of the expression f = ax + by are considered over the set of points constituting a non-empty closed convex polygon, then the maximum (or minimum) of 'f' occurs on at least one of the vertices of the polygon.

Graphical method of solving an LPP for which the solution set of the constraints is a closed convex polygon.
(i) Draw the graph of the system of inequation.
(ii) Find the vertices of the closed convex polygon.
(iii) Determine the value of the objective function at each of these vertices.
(iv) The vertex at which the objective function has the maximum (or minimum) value gives the required solution.

Feasible Region:

The solution set of constraints of an LPP is a convex set (open or closed) called the feasible region.

Feasible solution:

Any point (x, y) in the feasible region gives a solution to LPP called the feasible solution.

Iso profit line:

Any line belonging to the system of parallel lines given by the objective function for various values of the objective function f, is called an Iso profit line.