Slide 1

  • Linear Programming Problems - A Solved Example

Slide 2

  • In linear programming, we deal with optimizing a linear objective function.
  • Constraints represent limitations or restrictions on the variables.
  • The feasible region is the set of all points satisfying all the constraints.
  • The optimal solution is the point in the feasible region that maximizes or minimizes the objective function.

Slide 3

  • Let’s consider an example of a linear programming problem.
  • A company manufactures two products P1 and P2.
  • The company has limited resources such as labor and raw materials.
  • The goal is to maximize the profit.

Slide 4

  • Let x1 be the number of units of P1 produced.
  • Let x2 be the number of units of P2 produced.
  • The objective function represents the profit: Z = 40x1 + 30x2.
  • The constraints are:
    • 2x1 + x2 ≤ 1000 (labor constraint)
    • 3x1 + 2x2 ≤ 2400 (raw material constraint)
    • x1, x2 ≥ 0 (non-negativity constraint)

Slide 5

  • Let’s graphically represent the feasible region.
  • Plot the constraints on a coordinate plane.
  • Shade the region of the feasible solutions.
  • The feasible region is the intersection of all shaded regions.

Slide 6

  • Graph of constraint 1: 2x1 + x2 ≤ 1000 (labor constraint) Example equation: 2x1 + x2 = 1000 Example solution: x1 = 400, x2 = 200
  • The feasible region is below or on the line.

Slide 7

  • Graph of constraint 2: 3x1 + 2x2 ≤ 2400 (raw material constraint) Example equation: 3x1 + 2x2 = 2400 Example solution: x1 = 400, x2 = 800
  • The feasible region is below or on the line.

Slide 8

  • Graph of constraint 3: x1, x2 ≥ 0 (non-negativity constraint)
  • The feasible region is in the first quadrant.

Slide 9

  • To find the optimal solution, we need to locate the corner points of the feasible region.
  • These corner points are the intersections of the constraint lines.
  • In this example, there are four corner points: A, B, C, and D.

Slide 10

  • Find the value of the objective function at each corner point.
  • Calculate Z = 40x1 + 30x2 for each point.
  • Compare the values to determine the maximum profit.
  • The corner point with the highest objective function value is the optimal solution.

Slide 11

  • Corner point A: x1 = 0, x2 = 0
    • Z = 40(0) + 30(0) = 0
  • Corner point B: x1 = 400, x2 = 200
    • Z = 40(400) + 30(200) = 24,000
  • Corner point C: x1 = 400, x2 = 800
    • Z = 40(400) + 30(800) = 48,000
  • Corner point D: x1 = 600, x2 = 0
    • Z = 40(600) + 30(0) = 24,000
  • The optimal solution is at corner point C with a maximum profit of 48,000.

Slide 12

  • The optimal solution can be found mathematically using the simplex method.
  • The simplex method is an algorithm for solving linear programming problems.
  • It starts with an initial corner point and iteratively moves towards the optimal solution.
  • The process involves finding a pivot element and performing row operations to update the constraints.

Slide 13

  • To solve the example problem using the simplex method, we set up the following table: | | x1 | x2 | S1 | S2 | RHS | ||-|-|-|-|–| | Z | -40|-30 | 0 | 0 | 0 | | S1| 2 | 1 | 1 | 0 | 1000| | S2| 3 | 2 | 0 | 1 | 2400|
  • The bottom row represents the coefficients of the constraints.
  • The right-hand side (RHS) column represents the resources available for each constraint.

Slide 14

  • Identify the pivot element.
  • Choose the most negative coefficient in the topmost row (except the objective function coefficient).
  • In this case, the pivot element is -40. | | x1 | x2 | S1 | S2 | RHS | ||-|-|-|-|–| | Z | -40|-30 | 0 | 0 | 0 | | S1| 2 | 1 | 1 | 0 | 1000| | S2| 3 | 2 | 0 | 1 | 2400|
  • The pivot element is located in row 1, column 1.

Slide 15

  • Perform row operations to update the table and find a new pivot element. | | x1 | x2 | S1 | S2 | RHS | ||-|-|-|-|–| | Z | 0 |-30 | 60 | 0 | 48,000 | | S1| 0 | 1/2| 1/2| -1/4| 500 | | S2| 1 | 2/3| 0 | 1/3 | 800 |
  • The pivot element is now 1/2.

Slide 16

  • Continue performing row operations to update the table and find a new pivot element. | | x1 | x2 | S1 | S2 | RHS | ||-|-|-|-|–| | Z | 0 | 0 | 60 | 45 | 54,000 | | S1| 0 | 1 | 1 | -1/2| 1,000 | | S2| 1 | 0 | -2/3 | 1/3 | 400 |
  • There are no negative coefficients in the topmost row, indicating that the optimal solution has been reached.

Slide 17

  • The final table after the simplex method: | | x1 | x2 | S1 | S2 | RHS | ||-|-|-|-|–| | Z | 0 | 0 | 60 | 45 | 54,000 | | x2| 0 | 1 | 1 | -1/2| 1,000 | | x1| 1 | 0 | -2/3 | 1/3 | 400 |
  • The bottom row represents the values of the variables.
  • The right-hand side (RHS) column represents the resources used for each constraint.

Slide 18

  • The optimal solution:
    • x1 = 400 units of P1
    • x2 = 800 units of P2
  • The maximum profit: Z = 48,000
  • These values satisfy all the constraints and maximize the objective function.

Slide 19

  • In summary, linear programming is a powerful tool for optimizing solutions.
  • It involves setting up an objective function and constraints.
  • Graphical methods and the simplex method can be used to find the optimal solution.
  • The optimal solution is the point that maximizes or minimizes the objective function within the feasible region.

Slide 20

  • Practice problems:
    1. Maximize Z = 5x + 3y subject to the constraints 2x + y ≤ 10, x + 2y ≤ 8, x, y ≥ 0.
    2. Minimize Z = 4x + 6y subject to the constraints x + y ≥ 4, 2x + 3y ≥ 6, x, y ≥ 0.
    3. A company produces two products and wants to maximize profit. The constraints are: 3x + 5y ≤ 40, 5x + 2y ≤ 30, x, y ≥ 0. Find the optimal solution and maximum profit.

Slide 21

  • Linear programming is a technique used to find the best possible solution to a problem.
  • It involves optimizing an objective function while satisfying a set of constraints.
  • The objective function represents what we want to maximize or minimize.
  • The constraints represent limitations or restrictions on the variables.
  • Linear programming is widely used in various fields such as business, engineering, and economics.

Slide 22

  • The general form of a linear programming problem:
    • Maximize (or Minimize) Z = c1x1 + c2x2 + … + cnxn
    • Subject to:
      • a11x1 + a12x2 + … + a1nxn ≤ b1
      • a21x1 + a22x2 + … + a2nxn ≤ b2
      • …
      • am1x1 + am2x2 + … + amnxn ≤ bm
      • x1, x2, …, xn ≥ 0
  • Z: Objective function
  • c1, c2, …, cn: Coefficients of the variables in the objective function
  • a11, a12, …, amn: Coefficients of the variables in the constraints
  • b1, b2, …, bm: RHS (right-hand side) values of the constraints
  • x1, x2, …, xn: Decision variables

Slide 23

  • Graphical method is one way to solve linear programming problems.
  • It involves plotting the feasible region and determining the optimal solution.
  • The feasible region represents all the points that satisfy the constraints.
  • The optimal solution is the point that maximizes or minimizes the objective function within the feasible region.
  • This method is useful when there are only two decision variables.

Slide 24

  • The steps to solve a linear programming problem using the graphical method:
    1. Identify the objective function and constraints.
    2. Write the equations for the constraints.
    3. Graph the equations and shade the feasible region.
    4. Locate the corner points of the feasible region.
    5. Calculate the objective function at each corner point.
    6. Determine the optimal solution based on the objective function values.

Slide 25

  • Example: Maximize Z = 3x - 2y subject to the constraints:
    • 2x + y ≤ 10
    • x + 2y ≤ 8
    • x, y ≥ 0
  • Solution:
    1. Write the equations for the constraints:
      • 2x + y = 10
      • x + 2y = 8
    2. Graph the equations and shade the feasible region. [Graphical representation of the feasible region]

Slide 26

  • Example (continued): 3. Locate the corner points of the feasible region:
    • A: (0, 5)
    • B: (4, 0)
    • C: (2, 3)
    1. Calculate the objective function at each corner point:
      • Z(A) = 3(0) - 2(5) = -10
      • Z(B) = 3(4) - 2(0) = 12
      • Z(C) = 3(2) - 2(3) = 0
    2. Determine the optimal solution:
      • The maximum value of Z is 12 at point B.

Slide 27

  • The graphical method is not feasible when there are more than two decision variables.
  • In such cases, the simplex method is used to solve linear programming problems.
  • The simplex method is an iterative algorithm that starts with an initial basic feasible solution and moves towards the optimal solution.
  • It involves finding a pivot element and performing row operations to update the table.

Slide 28

  • The steps to solve a linear programming problem using the simplex method:
    1. Set up the initial table with the objective function, variables, and constraints.
    2. Identify the pivot element.
    3. Perform row operations to update the table.
    4. Repeat steps 2 and 3 until the optimal solution is reached.
    5. Find the optimal solution and maximum (or minimum) value of the objective function from the final table.

Slide 29

  • The simplex method involves three types of pivot operations:
    1. Minimum ratio test: Determine the most limiting constraint to select the pivot column.
    2. Pivot row: Select the row to pivot on (row having the least ratio from the minimum ratio test).
    3. Row operations: Perform row operations to update the table and find a new pivot element. [Example of a table and pivot operations]

Slide 30

  • Linear programming problems require careful analysis and solution to optimize the objective function.
  • The graphical method is suitable for problems with few decision variables.
  • The simplex method is effective for problems with more decision variables.
  • Choose the appropriate method based on the complexity of the problem.
  • Practice different types of problems to improve problem-solving skills in linear programming.