mansci Flashcards
definition of linear programming
linear programming is a mathematical method to determining the best possible outcome in a mathematical model with linear relationships. it is often used in optimization problems where the objective is to maximize or minimize a linear function subject to a set of constraints.
application of LP
linear programming is widely used in economics, business, engineering, military, transportation, and manufacturing, where optimization of resources is key.
components of LP
Decision variables- these are the variables that we need to solve for. they represent the unknowns of the problem.
Objective Function- a linear function that needs to maximize or minimize.
Formulating a LP problem
IDENTIFY THE DECISION VARIABLES- determine what quantities need to be solved for.
WRITE THE OBJECT FUNCTION- express the objective (maximization/minimization) as a linear function of the decision variable.
DEFINE THE CONSTRAINTS- identify the limitations or requirements in terms of linear inequalities or equalities
SPECIFY NON-NEGATIVITY RESTRICTION- ensure all decision variables are non-negative
GRAPHICAL SOLUTION METHOD (FOR TWO-VARIABLE LP PROBLEM)
STEP 1: plot the constraints as lines on a graph
STEP 2: identify the feasible region (the area where all constraints are satisfied)
STEP 3: plot the objective function and use a method, such as “isoprofit” or “isocost” lines to find the optimal points (maximum/minimum) within the feasible region.
STEP 4: the optimal solution is at a corner point (vertex) of the feasible region, as per fundamental theorem of LP.
STEP OF SIMPLEX METHOD
STEP 1: converting inequalities into equalities by introducing slack variables.
STEP 2: solving the system equations iteratively to move towards the optimal solution by improving the objective function at each step.
THE SIMPLEX METHOD INVOLVES:
Initial feasible solution
iterative improvement
optimality test
Key Theorems in Linear Programming
- Fundamental Theorem of Linear Programming
- Optimality Condition
Special Cases in LP
infeasibility
unbounded solutions
degeneracy
Software for Solving LP Problems
MATLAB
EXCEL SOLVER
LINDO
GAMS (GENERAL ALGEBRAIC MODELING SYSTEM)
PYTHON (WITH LIBRARIES LIKE PULP AND SCIPY)
Linear programming is a mathematical method for determining the best possible outcome in a mathematical model with _______ relationships.
linear
Linear programming is often used in _______ problems where the objective is to maximize or minimize a linear function.
optimization
In linear programming, _______ _______ are the variables that we need to solve for and represent the unknowns of the problem.
decision variables
The _______ _______ is a linear function that needs to be maximized or minimized in a linear programming problem.
objective function
To formulate a linear programming problem, the first step is to identify the _______ _______.
decision variables
In a graphical solution method for two-variable LP problems, the _______ _______ is the area where all constraints are satisfied.
feasible region
The optimal solution in a graphical method is found at a _______ point (vertex) of the feasible region.
corner
For larger LP problems, the _______ _______ is commonly used to find the optimal solution iteratively.
simplex method
n the Simplex Method, _______ variables are introduced to convert inequalities into equalities.
slack
The _______ principle states that if the primal has an optimal solution, then the dual also has an optimal solution, and the value of the objective function is the same for both.
duality
In duality, the primal problem involves _______ the objective function subject to constraints.
maximizing
The Fundamental Theorem of Linear Programming states that if an LP problem has an optimal solution, it occurs at one of the _______ of the feasible region.
vertices
If no solution satisfies all constraints in an LP problem, the problem is said to be _______.
infeasible
An LP problem is considered _______ if the objective function can be improved indefinitely without violating any constraints.
unbounded
_______ occurs when more than one basic feasible solution exists, which can lead to cycling in the Simplex method.
Degeneracy
_______ _______ provides insight into how sensitive the optimal solution is to changes in the coefficients of the objective function
Sensitivity Analysis
In sensitivity analysis, it is important to understand how much the _______ can change without affecting the optimal solution.
constraints
One software tool available for solving large-scale LP problems is _______ _______.
Excel Solver (other valid answers: MATLAB, LINDO, GAMS)
_______ is a widely used software library in Python for solving linear programming problems.
PuLP (other valid answer: SciPy)