Föreläsningar del 3 Flashcards
- Q: What are the steps for solving a maximization problem graphically?
o Prepare a graph of feasible solutions.
o Determine the feasible region.
o Draw the objective function line.
o Move the objective function line toward larger values while staying in the feasible region.
- Q: What is the feasible region?
A: The area that satisfies all constraints simultaneously in a linear programming problem.
- Q: What are slack variables?
A: Extra variables added to “≤” constraints to convert them into equalities.
- Q: What is an extreme point?
A: A corner or vertex of the feasible region where the optimal solution is found.
- Q: What are surplus variables?
A: Extra variables subtracted from “≥” constraints to convert them into equalities.
- Q: What is the purpose of slack and surplus variables?
A: To transform inequalities into equalities for standard form linear programming problems.
- Q: What happens when the objective function line is parallel to a boundary constraint?
A: There are alternate optimal solutions.
- Q: What does it mean if no solution satisfies all constraints?
A: The problem is infeasible.
- Q: When does a linear programming problem have an unbounded solution?
A: When the objective function can increase indefinitely without violating any constraints.
- Q: What are the four steps leading to the simplex method?
- Formulate the problem as an LP.
- Convert it into standard form.
- Set up the tableau form.
- Execute the simplex method.
- Q: What is the standard form of an LP problem?
A: A form where all variables are non-negative, and all constraints are equalities.
- Q: How do you put an LP problem into standard form?
A:
o Add slack variables to ≤ constraints.
o Subtract surplus variables from ≥ constraints.
- Q: What is tableau form?
: A format where:
o The right-hand side is non-negative.
o Each equation has a basic variable with a coefficient of 1, and 0 in other equations.
- Q: What is degeneracy in linear programming?
A: A situation where at least one basic variable equals zero.
Q: What is the reduced cost for a decision variable whose value is 0 in the optimal solution?
A: The reduced cost is the amount the variable’s objective function coefficient must improve before the variable could assume a positive value.
Q: What happens to the reduced cost for a decision variable with a positive value?
it is 0
