CHSE Odisha Class 12 Math Notes Chapter 3 Linear Programming

Odisha State Board CHSE Odisha Class 12 Math Notes Chapter 3 Linear Programming will enable students to study smartly.

CHSE Odisha 12th Class Math Notes Chapter 3 Linear Programming

Definition:
A general linear programming problem LPP is to obtain x₁, x₂, x₃ …… , x_n so as to

Optimize:
Z = c₁x₁ + c₂x₂ + c₃x₃ + ……. + c_nx_n … (A)
subject to
a₁₁x₁ + a₁₂x₂ + ……. + a_1nx_n  ≤ (or ≥) b₁
a₂₁x₁ + a₂₂x₂ + ……. + a_2nx_n  ≤ (or ≥) b₂ … (B)
where x₁, x₂, …… , x_n ≥ … 0 … (C)
and a_ij, b_i, c_j with i = 1, 2, … , m; j = 1, 2, … ,n are real constants.

In the LPP given above, the function Z in (A) is called the objective function. The variables x₁ x₃, ……, x_n are called decision variables. The constants c₁ c₂, ……, c_n are called cost coefficients. The inequalities in (B) are called constraints. The restrictions in (C) are called non-negative restrictions. The solutions which satisfy all the constraints in (B) and the non-negative restrictions in (C) are called feasible solutions.

The LPP involves three basic elements:

1. Decision variables whose values we seek to determine,
2. Objective (goal) that we aim to optimize,
3. Constraints and non-negative restrictions that the variables need to satisfy.

Types of Linear Programming Problems

As we have already discussed we come across different types of problems which we need solve depending on the objective functions and the constraints. Here we discuss a few important types of LPPs. before learning how to formulate them.

(i) Manufacturing Problem
A manufacturer produces different items so as to maximise his profit. He has to determine the number of units of products he must produce while satisfying a number of constraints because each unit of product requires availability of some amount of raw material, certain manpower, certain machine hours etc.

(ii) Diet Problem
Suppose a person is advised to take vitamins/nutrients of two or more types. The vitamins/nutrients are available in different proportions in different types of foods. If the person has to take a minimum amount of the vitamins/nutrients then the problem is to determine appropriate quantity of food of each type so that cost of food is kept at the minimum.

(iii) Allocation Problem
In this type of problem one has to allocate different resources/tasks to different units/persons depending on the nature of the gain or outcome.

(iv) Transportation Problem
These problems involve transporting materials from sources to destinations for sale or distribution of products or collection of raw materials etc. Here the aim is to use various options for transportation such as distance, time etc so as to keep the cost of transportation to a minimum.

Working procedure to solve LPP graphically
Step-1. Taking all inequations of the constraints as equations, draw lines represented by each equation and considering the inequalities of the constraint inequations complete the feasible region.
Step-2. Determine the vertices of the feasible region either by inspection or by and solving the two equations of the intersecting lines.
Step-3. Evaluate the objective function Z = ax + by at each vertex.
Case (i) F.R. is bounded: The vertex which gives the optional value (maximum or minimum) of Z gives the desired optional solution to the LPP.
Case (ii) F.R. is unbounded: When M is the maximum value of Z at a vertex Vmax, determine the open half plane corresponding to the inequation ax + by > M. If this open half plane has no points in common with the F.R. then M is the maximum value of Z and the point Vmax gives the desired solution. Otherwise, Z has no maximum value.

Similarly consider the open half plane ax+by < m when m is the minimum value of Z at the vertex Vmin. If this half-plane has no point common with the F.R. then m is the minimum value of Z and Vmin gives the desired solution. Otherwise Z has no minimum value.