Linear Programming Flashcards
What is Linear Programming (LP)?
The process of maximizing or minimizing an objective function subject to constraints.
What is an Objective Function in LP?
A function to maximize or minimize.
What are Constraints in LP?
Limitations that restrict possible solutions.
Define Decision Variables in the context of LP.
Variables that affect the objective function.
What is a Feasible Solution?
Satisfies all constraints.
What is an Optimal Solution?
The feasible solution that provides the best (maximum or minimum) value for the objective function.
List the steps for model formulation in LP.
- Understand the problem
- Define decision variables
- Express the objective function in terms of decision variables
- Write down all constraints using decision variables
- Ensure non-negativity constraints are included
How is a Maximization Problem formulated in LP?
Maximize Z=5x1+7x2 subject to constraints.
What is a Feasible Region in LP?
The area where all constraints hold.
Define Extreme Points in the context of LP.
The corners of the feasible region where optimal solutions exist.
What are Slack Variables?
Added to ‘≤’ constraints to convert them into equalities.
What are Surplus Variables?
Subtracted from ‘≥’ constraints to convert them into equalities.
What is Standard Form LP?
All constraints written as equalities with slack/surplus variables.
True or False: Optimal solutions in LP always occur at extreme points.
True.
What computational tools assist in solving LP problems?
- Excel Solver
- MATLAB
- Python
What is the goal in Minimization Problems?
To reduce the objective function value.
Fill in the blank: In LP, an Optimal Solution is found at _______.
[extreme points]
What are Alternative Optimal Solutions?
Occurs when multiple solutions yield the same optimal value.
Define Infeasibility in LP.
No feasible region exists (no solution satisfies all constraints).
What is Unboundedness in LP?
The objective function can increase indefinitely without violating constraints.
List the steps of the Simplex Method.
- Convert LP into standard form
- Construct the initial simplex tableau
- Determine the entering variable
- Determine the leaving variable
- Generate the next tableau by pivoting
- Repeat until optimal solution reached
How is Infeasibility detected in the Simplex Method?
When an artificial variable remains positive in the final tableau.
What indicates Unboundedness in the Simplex Method?
All entries in an entering column are non-positive.
What is Degeneracy in the Simplex Method?
Occurs when a basic variable equals zero.
What are the main approaches to solving LP problems?
- Graphical Methods for small problems
- Simplex Method for larger problems
- Computer-Based Approaches for real-world problems
True or False: Graphical Methods are useful for large LP problems.
False.
