04_Linear Programming Flashcards
What is an extreme point in a LP
- an extreme point in an LP with n decision variables is defined by the intersection of n of the m>n hyperplanes
- if we have m hyperplanes and n <= m variables, the # of possibele extreme points is
m = number of constraints
Standard Form of an LP
4 items
- All variables are nonnegative
- Constraints except non-negativity constraints of variables are stated as equalities
- RHS of each constraint is nonnegative
- For each constraint, except non-negativity constraint we have a variable with coefficient of 1 in that constraint and coefficients of 0 in all other constraints and in the objective function
When do you introduce Slack Variable and when Surplus Variable?
When transforming LP into standard form
Slack Variable
- when <= in constraint
- sj > 0
- positive
Surplus Variable
- when >= in constraint
- sj > 0
- negative
In which order to transform into Standard form?
- Maximize Objective Function
- Nonnegativity Constraint
- Are all constraints stated as equalities?
- Is RHS nonnegative?
- Isolate variables in each constraint
What is the Intuition of the Simplex Method
PROCEDURE (PIVOT STEPS):
- Given an extreme point, determine whether there exists a better neighbor or not
a. “No”: Stop, you’re at an optimal extreme point or there exists none
b. “Yes”: Go to a better one
Basic Variable in Simplex Algorithm
- extreme point
- decide whether to pivot to next extreme point or whether optimal solution has been found
What to do when variables aren’t isolated in standard form?
How do you solve for an optimal solution
2 Methods
- Big-M Method
- Two Phase Method
An optimal solution of a linear program is always a…
corner point of the feasible region
Gauß-Jordan Algorithm
Graphical Solution of LP
- allows to solve a set of m linear equations with m variables
- applies elementary row operations to obtain identity matrix for LHS
- elementary row operations: multiply rows by constant, adding and subtratcting multiples of rows from each other
What is the Basis in an LP in canonical form?
- set of all basic variables
What is a Basic Variable
- variable that appears with +1 in one constraint and 0 in all other constaraints including objective function
- # of BV = # of equations / constraints / m
When is a basic solution optimal
- when non basic variables in objective function are < = 0
Change of the basis
Pivot Step
- occurs when moving from one basic feasible solution to another
- by removing one former BV from the basis and introducin one former non basic variable to the basis
When to stop pivoting?
simplex method
- when optimal solution is found
- or simplex shows objective function is unbounded of feasible region (unbounded solution)
What to do when > =
- introduce negative surplus variable
- introduce artifical variable
- to avoid artifical variable in the Basis multiply artifical varible with -M in objective function