Linear Programming (LP) is a mathematical technique used for optimization, where the goal is to maximize or minimize a linear objective function subject to a set of linear constraints. It is widely used in various fields such as economics, engineering, military, and transportation.

1. Objective Function: A linear function that needs to be maximized or minimized. \[ \text{Maximize or Minimize } 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: Linear inequalities or equations that restrict the values of the decision variables. \[ \begin{align*} 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{align*} \] where \( a_{ij} \) are coefficients and \( b_i \) are constants.

3. Feasible Region: The set of all possible points that satisfy all the constraints. It is typically a convex polytope.

4. Optimal Solution: The point within the feasible region that maximizes or minimizes the objective function.

Consider a company that produces two products, P1 and P2. The profit from P1 is $40 per unit, and the profit from P2 is $30 per unit. The company has 100 hours of labor and 80 units of raw material available. Producing one unit of P1 requires 2 hours of labor and 1 unit of raw material, while producing one unit of P2 requires 1 hour of labor and 1 unit of raw material. The goal is to maximize the profit.

Formulation

1. Decision Variables: \[ x_1 = \text{number of units of P1 produced} \] \[ x_2 = \text{number of units of P2 produced} \]

2. Objective Function: \[ \text{Maximize } Z = 40x_1 + 30x_2 \]

3. Constraints: \[ \begin{align*} 2x_1 + x_2 &\leq 100 \quad \text{(labor constraint)}
   x_1 + x_2 &\leq 80 \quad \text{(raw material constraint)}
   x_1, x_2 &\geq 0 \quad \text{(non-negativity constraint)} \end{align*} \]

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

1. Graphical Method: Suitable for problems with two decision variables. The feasible region is plotted on a graph, and the optimal solution is found at the vertices of the feasible region.

2. Simplex Method: An iterative algorithm that moves from one vertex of the feasible region to another, improving the objective function at each step until the optimal solution is reached.

3. Interior-Point Methods: These methods approach the optimal solution from within the feasible region rather than from the boundaries.

For the example problem, we can solve it graphically:

1. Plot the Constraints: \[ \begin{align*} 2x_1 + x_2 &\leq 100
   x_1 + x_2 &\leq 80
   x_1, x_2 &\geq 0 \end{align*} \]

2. Identify the Feasible Region: The area where all constraints overlap.

3. Evaluate the Objective Function at the Vertices of the Feasible Region: \[ \begin{array}{|c|c|c|} \hline \text{Vertex} & (x_1, x_2) & Z = 40x_1 + 30x_2
   \hline (0, 0) & (0, 0) & 0
   (0, 80) & (0, 80) & 2400
   (50, 0) & (50, 0) & 2000
   (20, 60) & (20, 60) & 3200
   \hline \end{array} \]

4. Optimal Solution: The maximum profit is $3200, achieved by producing 20 units of P1 and 60 units of P2.

Problem: A factory produces two types of gadgets, G1 and G2. Each G1 requires 3 hours of machining and 1 hour of assembly. Each G2 requires 2 hours of machining and 2 hours of assembly. The factory has 120 hours of machining time and 80 hours of assembly time available each week. The profit from G1 is $50 per unit, and the profit from G2 is $40 per unit. Formulate and solve the linear programming problem to maximize the profit.

Solution:

1. Decision Variables: \[ x_1 = \text{number of units of G1 produced} \] \[ x_2 = \text{number of units of G2 produced} \]

2. Objective Function: \[ \text{Maximize } Z = 50x_1 + 40x_2 \]

3. Constraints: \[ \begin{align*} 3x_1 + 2x_2 &\leq 120 \quad \text{(machining constraint)}
   x_1 + 2x_2 &\leq 80 \quad \text{(assembly constraint)}
   x_1, x_2 &\geq 0 \quad \text{(non-negativity constraint)} \end{align*} \]

4. Graphical Solution:

   • Plot the constraints on a graph.
   • Identify the feasible region.
   • Evaluate the objective function at the vertices of the feasible region.

Vertices and Objective Function Evaluation: \[ \begin{array}{|c|c|c|} \hline \text{Vertex} & (x_1, x_2) & Z = 50x_1 + 40x_2
\hline (0, 0) & (0, 0) & 0
(0, 40) & (0, 40) & 1600
(40, 0) & (40, 0) & 2000
(20, 30) & (20, 30) & 2900
\hline \end{array} \]

Optimal Solution: The maximum profit is $2900, achieved by producing 20 units of G1 and 30 units of G2.

Linear programming is a powerful tool for solving optimization problems with linear constraints and objectives. By understanding the key concepts and methods, such as the graphical method and the simplex method, you can effectively tackle a wide range of real-world problems. In the next section, we will explore combinatorial optimization algorithms, which deal with problems where the solution space is discrete.