12th Com Maths Part 2 Chapter 6 (Digest) Maharashtra state board

Chapter 6 Linear programming

Open with Full Screen in HD Quality

HD PDF

Project on Linear programming

Linear programming (LP) is a mathematical method used to determine the best possible outcome or solution from a given set of parameters or list of requirements, which are represented by linear relationships. It is widely used in various fields such as economics, business, engineering, and military applications for optimization purposes.

Key Components of Linear Programming

1. Objective Function:

   • This is the function that needs to be optimized (maximized or minimized). It is a linear equation that represents the goal of the LP problem.
   • Example: $Z = c_1x_1 + c_2x_2 + \cdots + c_nx_n$
   • Here, $Z$ is the objective function, $c_i$ are coefficients, and $x_i$ are the decision variables.

2. Decision Variables:

   • These are the variables that decision makers will decide the values of in order to achieve the best outcome as defined by the objective function.
   • Example: $x_1, x_2, \ldots, x_n$

3. Constraints:

   • These are the limitations or requirements expressed as linear inequalities or equations that the decision variables must satisfy.
   • Example: $$\begin{align*} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n &\leq b_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n &\leq b_2 \\ &\vdots \\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n &\leq b_m \end{align*}$$
   • Here, $a_{ij}$ are the coefficients of the constraints, and $b_i$ are the right-hand side constants.

4. Non-negativity Restriction:

   • Decision variables are often required to be non-negative.
   • Example: $x_i \geq 0$ for all $i$

Formulating a Linear Programming Problem

A linear programming problem can be formulated in a standard form as follows:

1. Maximize or Minimize the Objective Function: $$\text{Maximize (or Minimize)} \quad Z = c_1x_1 + c_2x_2 + \cdots + c_nx_n$$
2. Subject to Constraints: $$\begin{align*} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n &\leq b_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n &\leq b_2 \\ &\vdots \\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n &\leq b_m \end{align*}$$
3. And Non-negativity Restrictions: $$x_1, x_2, \ldots, x_n \geq 0$$

Solving Linear Programming Problems

Linear programming problems can be solved using various methods, including:

1. Graphical Method:
   • Used for problems with two decision variables. It involves plotting the constraints on a graph to find the feasible region and then identifying the optimal solution within this region.
2. Simplex Method:
   • A widely used algorithm that systematically examines the vertices of the feasible region to find the optimal solution. It is effective for larger problems with more than two variables.
3. Interior-Point Methods:
   • These methods approach the solution from within the feasible region and are often used for very large-scale linear programming problems.

Applications of Linear Programming

Linear programming is used in a variety of applications such as:

• Resource Allocation: Determining the most efficient way to allocate resources such as labor, materials, and machinery.
• Production Scheduling: Planning production schedules to maximize efficiency and minimize costs.
• Diet Problems: Finding the most cost-effective way to meet nutritional requirements.
• Transportation Problems: Optimizing the transportation of goods to minimize costs.

Example

Consider a simple LP problem:

Objective: Maximize $Z = 3x_1 + 2x_2$

Subject to:

$$\begin{align*} x_1 + x_2 &\leq 4 \\ 2x_1 + x_2 &\leq 5 \\ x_1, x_2 &\geq 0 \end{align*}$$

The graphical method would involve plotting these constraints and finding the feasible region. The optimal solution lies at one of the vertices of this region. For the Simplex method, we would set up a tableau and iterate to find the maximum $Z$.

In summary, linear programming is a powerful tool in optimization that helps in making the best decisions within given constraints, ensuring optimal use of resources.