Linear Programming Problems - Introduction

• Definition of linear programming
• Components of a linear programming problem
• Objective function and constraints
• Feasible region and optimal solution
• Graphical representation of linear programming problems

Components of a Linear Programming Problem

• Decision variables
• Objective function
• Constraints
• Non-negativity constraints
• Formulation of a linear programming problem

Decision Variables

• Variables that represent the quantities to be determined
• Usually denote by x1, x2, x3, …
• Example: Let x1 represent the number of units of product A to be produced.

Objective Function

• Represents the goal or objective of the problem
• Can be in the form of maximize or minimize
• Example: Maximize profit, minimize cost

Constraints

• Restrictions or limitations on the decision variables
• Examples: Limited resources, production capacity
• Inequality constraints: <=, >=
• Equality constraints: =

Non-negativity Constraints

• Decision variables must be non-negative
• x >= 0 for all decision variables

Formulation of a Linear Programming Problem

• Identify the decision variables
• Write the objective function
• Write the constraints
• Determine the non-negativity constraints

Feasible Region

• Represents the set of all feasible solutions
• Defined by the constraints
• Constraints create boundaries and shapes the feasible region

Optimal Solution

• Solution that maximizes or minimizes the objective function
• Located at a vertex (corner point) of the feasible region
• Can be found graphically or using optimization techniques

Graphical Representation of LP Problems

• Utilize the Cartesian coordinate system
• Plot constraints as lines or curves
• Intersection of constraints creates feasible region
• Optimal solution lies on a vertex of the feasible region

11. Decision Variables:

• Variables that represent the quantities to be determined
• Can be denoted by x, y, z or any other letters
• Example: Let x represent the number of chairs to be produced

12. Objective Function:

• Represents the goal or objective of the problem
• Can be in the form of maximize or minimize
• Example: Maximize profit, minimize cost
• Usually denoted by Z

13. Constraints:

• Restrictions or limitations on the decision variables
• Examples: Limited resources, production capacity
• Inequality constraints: <=, >=
• Equality constraints: =
• Example: 5x + 3y <= 10

14. Non-negativity Constraints:

• Decision variables must be non-negative
• x >= 0, y >= 0 for all decision variables
• Negative values do not make sense in most real-world problems

15. Formulation of a Linear Programming Problem:

• Identify the decision variables
• Write the objective function
• Write the constraints using inequalities or equalities
• Determine the non-negativity constraints
• Example: Maximize Z = 2x + 3y subject to 5x + 3y <= 10, x >=0, y >= 0

16. Feasible Region:

• Represents the set of all feasible solutions
• Defined by the constraints
• Constraints create boundaries and shape the feasible region
• Example: Feasible region bounded by lines and curves

17. Optimal Solution:

• Solution that maximizes or minimizes the objective function
• Located at a vertex (corner point) of the feasible region
• Can be found graphically or using optimization techniques
• Example: Optimal solution at (x, y) = (2, 3)

18. Graphical Representation of LP Problems:

• Utilize the Cartesian coordinate system
• Plot constraints as lines or curves
• Intersection of constraints creates feasible region
• Optimal solution lies on a vertex of the feasible region

19. Example: Maximizing Profit:

• Objective: Maximize profit
• Decision variables: x = number of Product A, y = number of Product B
• Constraints: 2x + 3y <= 10, x >= 0, y >= 0
• Objective function: Z = 5x + 4y
• Feasible region: Shaded area bounded by constraints
• Optimal solution: Vertex (x, y) that maximizes Z

20. Example: Minimizing Cost:

• Objective: Minimize cost
• Decision variables: x = number of Product X, y = number of Product Y
• Constraints: 3x + 2y <= 12, x >= 0, y >= 0
• Objective function: Z = 4x + 2y
• Feasible region: Shaded area bounded by constraints
• Optimal solution: Vertex (x, y) that minimizes Z

21. Simplex Method:

• Method for solving linear programming problems algebraically
• Iterative process that systematically improves the objective value
• Identifies the optimal solution and corresponding optimal values of decision variables
• Steps:
  1. Convert the linear programming problem into standard form
  2. Create the initial simplex tableau
  3. Perform simplex iterations until an optimal solution is reached
  4. Update the tableau by selecting a pivot element and performing row operations

22. Standard Form of LP Problem:

• Minimization problem:
  • Objective function: Minimize Z = c1x1 + c2x2 + … + cnxn
  • Constraints:
    • a11x1 + a12x2 + … + a1nxn >= b1
    • a21x1 + a22x2 + … + a2nxn >= b2
    • …
    • am1x1 + am2x2 + … + amnxn >= bm
  • Non-negativity constraints: x1 >= 0, x2 >= 0, …, xn >= 0

23. Simplex Tableau:

• Table representation of a linear programming problem in standard form
• Contains the coefficients of the objective function and constraints
• Includes additional columns for slack, surplus, and artificial variables
• Rows represent constraints and the bottom row represents the objective function

24. Pivot Element:

• Element used for row operations during simplex iterations
• Selected to enter the basis or leave the basis
• Should be non-negative for the entering variable and produce a positive ratio for the leaving variable
• Determines the direction of movement towards the optimal solution

25. Row Operations:

• Operations performed on the simplex tableau during iterations
• Include scaling, row replacement, and pivot operations
• Designed to improve the objective value and bring the tableau closer to the optimal solution
• Keep the basic variables non-negative and improve the non-basic variables

26. Iteration Steps:
27. Select the pivot column (entering variable) by identifying the most negative coefficient in the bottom row.
28. Calculate the ratio for each positive values in the pivot column (leaving variable).
29. Select the pivot row with the smallest positive ratio.
30. Use row operations to make the pivot element 1 and other elements in the pivot column 0.
31. Update the tableau by performing row operations on the remaining elements.
32. Repeat steps 1-5 until no negative values exist in the bottom row.

27. Optimality Test:

• Process to determine if the current solution is optimal
• Based on the values in the bottom row of the tableau
• If all values are non-negative or zero, the solution is optimal
• If there is at least one negative value, the iteration process continues

28. Degeneracy and Cycling:

• Degeneracy: When the solution during the simplex iterations has one or more basic variables at zero
• Cycling: When the simplex method fails to reach an optimal solution due to repetitive steps and loops
• Solutions:
  • Bland’s rule: Select the entering variable with the smallest index
  • Anti-cycling rule: Introduce artificial variables and use a penalty method to discourage degeneracy and cycling

29. Example: Maximizing Profit - Simplex Method:

• Objective: Maximize profit
• Decision variables: x = number of Product A, y = number of Product B
• Constraints: 2x + 3y <= 10, x >= 0, y >= 0
• Objective function: Z = 5x + 4y
• Initial tableau: Formulating initial tableau with slack variables
• Iterations: Perform simplex iterations until an optimal solution is reached
• Optimal solution: Vertex (x, y) that maximizes Z

30. Example: Minimizing Cost - Simplex Method:

• Objective: Minimize cost
• Decision variables: x = number of Product X, y = number of Product Y
• Constraints: 3x + 2y <= 12, x >= 0, y >= 0
• Objective function: Z = 4x + 2y
• Initial tableau: Formulating initial tableau with slack variables
• Iterations: Perform simplex iterations until an optimal solution is reached
• Optimal solution: Vertex (x, y) that minimizes Z