3.2 Solution Methods

• What does a linear programming problem aim to optimize?

  Objective function
• The objective function in linear programming defines the quantity to be maximized or minimized
• What is the feasible region in a linear programming problem?

  Set of all possible solutions
• The optimal solution in linear programming is the point within the feasible region that maximizes or minimizes the objective function.
• What is the primary use of the graphical method in linear programming?

  Solve 2-variable problems
• In the graphical method, constraints are represented as lines on the graph
• How is the optimal solution found in the graphical method?

  Evaluate objective function at corner points
• Steps involved in the simplex method

  1️⃣ Convert to standard form

  2️⃣ Set up initial simplex tableau

  3️⃣ Iterate to optimal solution
• Slack variables are added to convert less than or equal to constraints into equalities.
• The initial simplex tableau represents the system with basic variables having coefficients of 1
• How is the pivot column selected in the simplex method?

  Most negative value in objective function row
• Iteration in the simplex method stops when all values in the objective function row are non-negative.
• What is the objective of a linear programming problem?

  Optimize a linear function
• The objective function in linear programming defines the quantity to be maximized or minimized
• The feasible region in linear programming is the set of solutions satisfying all constraints.
• What type of linear programming problems can the graphical method solve?

  Problems with two variables
• Steps of the graphical method

  1️⃣ Plot the constraints and shade the feasible region

  2️⃣ Define the objective function

  3️⃣ Evaluate the objective function at corner points
• The optimal solution in the graphical method is found at a corner point of the feasible region.
• The simplex method is an iterative algebraic technique used to solve linear programming problems by exploring corner points of the feasible region
• Steps of the simplex method

  1️⃣ Convert to standard form

  2️⃣ Set up initial tableau

  3️⃣ Iterate to optimal solution
• What variables are added to convert inequality constraints to equalities in the simplex method?

  Slack and surplus variables
• The pivot column in the simplex method is identified by the most negative value in the objective function row.
• In the simplex method, the optimal solution for the example problem is $x =$$2$ and $y =$$4$, with a $Z$ value of 26
• What is the purpose of duality in linear programming?

  Convert primal to dual problem
• Match the primal problem with its dual counterpart:

  Maximization ↔️ Minimization

  Coefficients of objective function become constraints ↔️ Constraint constants become coefficients of objective function

  Constraints are $\leq$ inequalities ↔️ Constraints are $\geq$ inequalities
• The dual problem in linear programming provides an alternative perspective on the original problem.