12th Mathematics (Arts & Science) Part 1 Chapter 7 Solution (Digest) Maharashtra state board

Chapter 7 Linear Programming

Open with Full Screen in HD Quality

HD PDF

Project on Linear Programming

Linear programming (LP) is a mathematical method used for optimizing a linear objective function, subject to a set of linear inequality or equality constraints. This technique is widely used in various fields such as economics, engineering, military, transportation, and manufacturing for decision-making and resource allocation.

Key Concepts

1. Objective Function:

   • The function that needs to be maximized or minimized. It is a linear function of the decision variables.
   • Example: $Z = c_1x_1 + c_2x_2 + \ldots + c_nx_n$, where $c_1, c_2, \ldots, c_n$ are coefficients, and $x_1, x_2, \ldots, x_n$ are decision variables.

2. Constraints:

   • A set of linear inequalities or equalities that the decision variables must satisfy.
   • Example: $$\begin{cases} a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n \leq b_1 \\ a_{21}x_1 + a_{22}x_2 + \ldots + a_{2n}x_n \leq b_2 \\ \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \ldots + a_{mn}x_n \leq b_m \end{cases}$$
   • Here, $a_{ij}$ are the coefficients of the constraints, and $b_1, b_2, \ldots, b_m$ are the constants on the right side of the inequalities.

3. Feasible Region:

   • The set of all possible points (combinations of decision variables) that satisfy all the constraints. It is typically a convex polytope in n-dimensional space.

4. Optimal Solution:

   • A point in the feasible region where the objective function reaches its maximum or minimum value.
   • In many cases, the optimal solution lies at a vertex (or corner point) of the feasible region.

Formulation of a Linear Programming Problem

A typical linear programming problem can be formulated as follows:

• Objective: Maximize or minimize $Z = c_1x_1 + c_2x_2 + \ldots + c_nx_n$
• Subject to constraints: $$\begin{cases} a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n \leq b_1 \\ a_{21}x_1 + a_{22}x_2 + \ldots + a_{2n}x_n \leq b_2 \\ \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \ldots + a_{mn}x_n \leq b_m \\ x_1, x_2, \ldots, x_n \geq 0 \end{cases}$$

Solving Linear Programming Problems

1. Graphical Method (for two-variable problems):

   • Plot the constraints on a graph to identify the feasible region.
   • Evaluate the objective function at each vertex of the feasible region to find the optimal value.

2. Simplex Method:

   • An iterative algorithm that moves along the edges of the feasible region to find the optimal vertex.
   • Suitable for larger problems and provides an efficient way to handle constraints and optimize the objective function.

3. Interior-Point Methods:

   • Approaches that traverse the interior of the feasible region rather than the edges.
   • Can be more efficient than the Simplex Method for very large problems.

Example

Problem: Maximize $Z = 3x + 2y$

Subject to:

$${x+y≤4x≤2y≤3x,y≥0⎨⎧​x+y≤4x≤2y≤3x,y≥0​$$

Solution:

• Graph the constraints to identify the feasible region.
• Determine the coordinates of the vertices of the feasible region.
• Evaluate the objective function $Z$ at each vertex:
  • (0, 0): $Z = 3(0) + 2(0) = 0$
  • (2, 0): $Z = 3(2) + 2(0) = 6$
  • (0, 3): $Z = 3(0) + 2(3) = 6$
  • (1, 3): $Z = 3(1) + 2(3) = 9$

The optimal solution is at (1, 3) with $Z = 9$.

Applications of Linear Programming

1. Resource Allocation: Determining the best way to allocate limited resources to maximize profit or minimize cost.
2. Production Planning: Optimizing the production process to meet demand while minimizing costs.
3. Transportation and Logistics: Finding the most efficient routes and schedules for transportation to minimize costs or time.
4. Portfolio Optimization: Allocating investments to maximize returns while managing risk.

Linear programming provides a powerful tool for optimization in a variety of practical problems, enabling decision-makers to find the best possible solutions within given constraints.